В Helium мы создаем и управляем комплексными интеллектуальными сенсорными системами для различных промышленных и корпоративных вертикалей. Это означает, что у нас есть код, охватывающий весь путь от прошивки встроенного устройства до веб-интерфейсов, а также кучу промежуточного кода. Одна из проблем со встроенной частью системы заключается в том, что тестирование может быть сложнее из-за ограничений встроенного программирования. Случалось ли вам когда-нибудь без причины перезагружать кабельный модем или точку доступа? Да, это одна из причин. Я собираюсь немного рассказать о том, как мы в Helium хотим, чтобы наши устройства в полевых условиях просто работали и избегали подхода просто перезагрузите его при устранении неполадок.
Недавно я преследовал некоторые проблемы с повреждением стека в некоторых наших прошивках, которые были рядом с одной из структур данных, используемых прошивкой; в основном круговой буфер. Я подумал, не связан ли сценарий, который я тестировал, с ошибкой в этой структуре данных, поэтому я решил использовать инструмент, который никогда раньше не использовал; Erlang QuickCheck for C (или сокращенно EQC-C).
Quickcheck, для тех, кто не знаком, — это инструмент тестирования на основе свойств. В настоящее время существуют его клоны на нескольких разных языках, но он возник на языке Haskell (который мы также используем в Helium). QuviQ предлагает коммерческую версию для Erlang, которая предоставляет ряд дополнительных мощных функций, одной из которых является EQC-C.
У нас уже давно есть лицензия QuickCheck, и мы с большим успехом использовали ее при тестировании нашей внутренней инфраструктуры на основе Erlang и даже при тестировании встроенного ПО методом «черного ящика» (об этом в другой раз). Я видел, как Джон Хьюз говорил об EQC-C, но никогда не имел возможности его использовать. Однако эта проблема с повреждением стека сводила меня с ума, поэтому я решил, что пришло время попробовать.
Итак, сегодня я расскажу, как вы можете быстро проверить код C. Однако я не буду использовать код из нашей прошивки. Вместо этого я покажу вам EQC-C на некоторых структурах данных C с открытым исходным кодом, что сделает его более чистым и интересным примером (круговой буфер в прошивке оказался без ошибок). В частности, я буду тестировать реализацию хэш-карты из ремейка видеоигры с открытым исходным кодом, в котором я участвую, OpenOMF (кстати, мы использовали эту хэш-карту и для libhelium).
Код для тестирования
Прежде всего, давайте взглянем на API, который мы будем тестировать:
Как видите, это довольно просто. Вы можете создавать, вставлять, удалять, итерировать и очищать хэш-карту. Итак, как мы на самом деле протестируем это? Оказывается, EQC-C работает, компилируя ваш код C каким-то волшебным образом, который позволяет обернуть C API в модуль Erlang, который затем позволяет вам написать обычный тест EQC, чтобы, ну, протестировать его.
Преодоление разрыва между Erlang и C
Все волшебство начинается с функции eqc_c:start(). В этом случае это происходит так (на Erlang REPL):
1> eqc_c:start(hashmap, [{c_src, “hashmap.c”},
{cppflags, “-I ../../include/ -std=c99”},
{cflags,”-lm”},
{additional_files, [“iterator.c”]}]).
Starting Quviq QuickCheck version 1.36.1
(compiled at {{2015,9,8},{9,10,49}})
Licence for Helium reserved until {{2016,1,6},{8,59,18}}
ok
2>
Здесь происходит куча всего, но в основном мы сообщаем ему файл C, который мы хотим скомпилировать, настраиваем некоторые пути включения, убеждаемся, что мы связываем его с математической библиотекой, а также связываем его с iterator.c, потому что хэш-карта поддерживает итерацию.
Теперь, как по волшебству, у нас есть модуль Erlang hashmap, реализующий C API:
2> hashmap:<tab> ... hashmap_clear/1 hashmap_create/2 hashmap_create_with_allocator/3 hashmap_del/3 hashmap_delete/2 hashmap_free/1 hashmap_get/5 hashmap_idel/2 hashmap_iget/4 hashmap_iput/4 hashmap_iter_begin/2 hashmap_iter_next/1 hashmap_put/5 hashmap_reserved/1 hashmap_sdel/2 hashmap_sget/4 hashmap_size/1 hashmap_sput/4 ...
На самом деле в этом модуле есть много других функций. EQC-C имеет возможность генерировать функции только для определений в файле C, а не для прототипов, но нам понадобятся некоторые функции из iterator.c позже, поэтому нам нужно сгенерировать кучу дополнительных функций.
Принимая это за спину
Теперь мы можем использовать это как модуль Erlang из REPL, хотя это немного громоздко, потому что нам нужно использовать указатели C EQC-C:
2> rr("hashmap.hrl").[allocator_t,div_t,hashmap_node_t,hashmap_pair_t,hashmap_t,
iterator_t,ldiv_t,lldiv_t]
3> HM = eqc_c:alloc({struct, hashmap_t}).
{ptr,{struct,hashmap_t},20516928}
4> hashmap:hashmap_create(HM, 6).
ok
5> hashmap:hashmap_put(HM, eqc_c:create_string("hello"), 5, eqc_c:create_string("world"), 5).
{ptr,void,20517648}
Итак, на самом деле здесь происходит довольно много. Сначала мы читаем определения записей, которые EQC-C сгенерировал из структур, которые он видел при компиляции. Затем мы фактически выделяем память для одной из этих структур, используя eqc_c:alloc(). Это возвращает {ptr, …}, который на самом деле является дескриптором указателя C. Затем мы можем использовать этот указатель для вызова hashmap_create(), чтобы фактически инициализировать хэш-карту. Как только мы инициализировали хэш-карту, мы можем сохранить в ней что-то, используя hashmap_put(). Для этого мы используем вспомогательную функцию EQC-C, называемую create_string(), которая выделяет char* и инициализирует ее строкой, которую вы ей предоставляете. hashmap_put также требует, чтобы мы указывали длину параметров, которые мы передаем (поскольку он не предполагает, что ключи и значения заканчиваются нулем), поэтому мы передаем 5 в обоих случаях. Как только мы делаем put, мы возвращаем указатель на только что созданный элемент hashmap, как и обещает C API.
Теперь, чтобы получить что-то обратно из из хэш-карты, это становится немного сложнее. Давайте еще раз посмотрим на подпись для hashmap_put:
int hashmap_get(hashmap *hm, const void *key, unsigned int keylen, void **val, unsigned int *vallen);
Таким образом, он принимает указатель void** и беззнаковый int*, где он заполняет адрес значения для этого ключа и его размер. С этим немного сложнее работать, и мне потребовалось некоторое время, чтобы понять это, но вот как вы это делаете:
6> Val = eqc_c:alloc({ptr, unsigned_char}).
{ptr,{ptr,unsigned_char},10064640}
7> ValLen = eqc_c:alloc(unsigned_int).
{ptr,unsigned_int,10064672}
8> Res = hashmap:hashmap_get(HM, eqc_c:create_string("hello"), 5, Val, ValLen).
0
Итак, мы выделили указатель unsigned char** и указатель unsigned int* и передали их в hashmap_get(). Функция get вернула 0, что является кодом успешного возврата, поэтому мы «получили» что-то, но как мы на это смотрим? EQC-C предоставляет способы чтения указателя (а также указатели приведения), поэтому давайте посмотрим, что мы получили в ответ:
9> Len = eqc_c:deref(ValLen). 5 10> eqc_c:read_array(eqc_c:deref(Val), Len). "world"
Вот и все, это работает! Что произойдет, если мы попробуем с отсутствующим ключом?
13> f(Len).
ok
14> hashmap:hashmap_get(HM, eqc_c:create_string("nothere"), 7, Val, ValLen).
1
15> Len = eqc_c:deref(ValLen).
0
Что ж, код возврата от get() теперь равен 1, что означает, что поиск не удался, а указатель длины теперь содержит 0, как и ожидалось.
Давайте напишем свойство!
Итак, это все хорошо, но чем это лучше прославленного FFI? По правде говоря, на самом деле это не так (помимо обеспечения некоторой хорошей изоляции, чтобы ошибки сегментации не убивали виртуальную машину Erlang), EQC-C — это просто инструмент, позволяющий вам раскрыть мощь Erlang QuickCheck в вашем коде C, и это то, что к этому все идет.
Один из инструментов QuickCheck называется eqc_statem, в документации он описан так:
Этот модуль предоставляет функции для тестирования операций с побочными эффектами, которые задаются через абстрактный конечный автомат.
Что в принципе верно. eqc_statem — это способ тестирования некоторого компонента с сохранением состояния путем создания «команд» для этого компонента и проверки того, что ваши инварианты выполняются. «Обычная» быстрая проверка больше касается проверки инвариантов для конкретной функции (работает ли она для всех отсортированных массивов и не работает для всех несортированных массивов и т. д.). Большинство реализаций QuickCheck в основном ориентированы на эту более простую форму тестирования, но eqc_statem позволяет вам тестировать гораздо более сложные системы с любой степенью детализации, которую вы хотите. Вы можете проверить, что вся система придерживается некоторых инвариантов для некоторых входных данных, или, в этом случае, вы можете протестировать что-то меньшее, например структуру данных.
eqc_statem работает, определяя обратные вызовы для команд, генераторы аргументов для этих команд, предварительные условия для этих команд (если допустимо сгенерировать эту команду в данный момент), постусловия, в которых вы проверяете свои инварианты, и «следующее состояние», в котором вы обновляете состояние своей модели. чтобы отразить изменения, внесенные командой в тестируемую систему.
Давайте посмотрим, что мы бы определили для hashmap_create, очевидной отправной точки:
Итак, нам на самом деле нужно определить состояние модели, чтобы у нас было с чем протестировать наш код C. Состояние, которое нам нужно для этого, на самом деле очень простое, оно просто содержит указатель на хэш-карту, размер, с которым мы создали хэш-карту, и пустой список Erlang, который мы будем использовать для моделирования поведения хэш-карты.
Наше предварительное условие просто говорит: «генерировать хэш-карту только в том случае, если хэш-карта в состоянии не определена». Это эффективно заставляет EQC генерировать эту команду в качестве первой в любом тесте. Для генератора аргументов мы генерируем число от 4 до 10 в качестве «размера» хэш-карты.
Затем у нас есть сама команда создания, мы выделяем hashmap_t, как и раньше, а затем создаем хэш-карту и возвращаем указатель. Функция _next просто обновляет наше состояние, сохраняя указатель в состоянии модели. Наконец, поскольку у нас нет никаких инвариантов для проверки, здесь нет постусловия.
Теперь, когда мы увидели смоделированную команду, давайте объединим ее с шаблоном, чтобы создать свойство QuickCheck, которое вы действительно можете запустить:
Единственная действительно интересная вещь, которая здесь новая, — это недвижимость. В нем говорится, что «для всех наборов сгенерированных команд выполнение команд не должно нарушать никаких инвариантов». Поскольку у нас нет никаких инвариантов, это пока не очень интересно, но мы все равно можем запустить его:
1> c(hashmap_eqc).
{ok,hashmap_eqc}
2> eqc:quickcheck(hashmap_eqc:prop_correct()).
Starting Quviq QuickCheck version 1.36.1
(compiled at {{2015,9,8},{9,10,49}})
Licence for Helium reserved until {{2016,1,6},{8,59,18}}
……………………………………………………………………………………….
OK, passed 100 tests
100% {hashmap_eqc,hashmap_create,1}
true
Итак, мы провели 100 тестов, все они прошли, и команда, которую мы запускали, была hashmap_create в 100% случаев. Не очень интересно. Давайте смоделируем еще немного API.
Положить его на линию
Теперь, когда мы моделируем put(), становится все интереснее. Предварительным условием является то, что у нас есть созданная хэш-карта, поэтому элемент хэш-карты состояния модели не может быть неопределенным. Это довольно просто. Далее, используя генератор аргументов, мы генерируем 3 аргумента; указатель на хэш-карту, ключ и значение. Мы хотим сгенерировать ключи, которых еще нет в хэш-карте, поэтому мы используем макрос SUCHTHAT, чтобы сказать, что нам нужен непустой список char(), которых еще нет в списке ключи в состоянии модели и что это значение также не должно быть пустым.
Фактическая командная функция, hashmap_put, принимает эти сгенерированные аргументы и фактически выполняет размещение, как мы видели ранее. Сейчас я тщательно убираю за собой, чтобы не утечь память. Возвращаемое значение команды — это значение, возвращаемое фактической функцией C hashmap_put (хотя в данном случае мы ее не используем).
Наконец, следующая функция добавляет кортеж {Key, Value} в наш список, который мы используем для моделирования состояния хэш-карты.
Если мы добавим это к тому, что у нас было раньше (вместе с соответствующими директивами экспорта), мы увидим что-то вроде этого:
eqc:quickcheck(hashmap_eqc:prop_correct()).
……………………………………………………………………………………….
OK, passed 100 tests
91.7% {hashmap_eqc,hashmap_put,3}
8.3% {hashmap_eqc,hashmap_create,1}
true
Поскольку мы можем вызвать hashmap_create только в том случае, если хэш-карты еще нет, hashmap_put теперь доминирует в распределении сгенерированных команд. У нас по-прежнему нет никаких постусловий для проверки наших инвариантов, так что все проходит. Итак, давайте добавим что-то, что можно протестировать, например get().
Серьёзно
Хорошо, здесь происходит намного больше, давайте разберем это.
Мы уже видели это предварительное условие. Ничего слишком интересного. Наш генератор аргументов имеет 2 предложения: одно для случаев, когда у нас есть ключи в хэш-карте, и одно для случаев, когда их нет. Когда у нас ДЕЙСТВИТЕЛЬНО есть ключи в хэш-карте, мы выбираем один из ключей из модели, которую, как мы знаем, мы сохранили, но у нас также есть возможность сгенерировать ключи, которые могут НЕ отображаться в хэш-карте, поэтому мы также можем протестировать неудачные поиски. . Когда хэш-карта пуста, мы просто пытаемся использовать случайный ключ.
Фактическая командная функция, опять же, похожа на то, что мы делали ранее в REPL. Из командной функции мы возвращаем кортеж из 3, содержащий результат функции C, значение возвращаемой длины и значение, возвращаемое при поиске хэш-карты (или неопределенное, если длина равна 0).
Теперь, наконец, у нас есть постусловие. Постусловие говорит, что если ожидалось, что ключ будет в хэш-карте, код возврата должен быть 0, а значение, считанное из хэш-карты, должно быть таким же, как мы сохранили в модели. Если ключа НЕТ в хэш-карте, мы ожидаем, что код возврата будет равен 1, а возвращаемая длина будет равна 0.
Если мы соединим это с тем, что у нас было раньше, и запустим, ну, все равно все пройдет. Я думаю, что хэш-карта хорошо справляется с основами.
Забывание вещей
Далее смоделируем clear(), это будет легко:
Очень просто — все, что мы делаем, это вызываем очистку и устанавливаем нашу модель так, чтобы пустой список был моделью для карты. Это означает, что любые поиски ПОСЛЕ очистки не должны ничего возвращать. Опять же, как и ожидалось, если мы обновляем тест, все проходит. Делаем удаление:
Генератор аргументов здесь аналогичен генератору для get(). Если карта не пуста, мы выбираем ключ из карты или случайный ключ; если карта пуста, мы генерируем случайный ключ. Команда проста, постусловие просто проверяет, равен ли код возврата 0, если ключ был в хэш-карте, и 1, если нет, а функция _next удаляет ключ, который мы удалили из нашей модели.
Давайте соберем все это вместе и запустим 1000 тестов:
eqc:quickcheck(eqc:numtests(1000, hashmap_eqc:prop_correct())).
……………………………………………………………………………………….(x10)………………………………………………………………………………
OK, passed 1000 tests
23.94% {hashmap_eqc,hashmap_get,2}
23.62% {hashmap_eqc,hashmap_delete,2}
23.24% {hashmap_eqc,hashmap_put,3}
23.10% {hashmap_eqc,hashmap_clear,1}
6.10% {hashmap_eqc,hashmap_create,1}
true
Прогулка по хэш-карте
Все по-прежнему проходит, и мы генерируем хороший набор операций с хэш-картой. Что еще мы можем протестировать? Две оставшиеся интересные функции — это функции итерации: hashmap_iter_begin и hashmap_delete (которая принимает итератор). Давайте используем итератор, чтобы вывести состояние хеша и сравнить каждый ключ с нашей моделью:
Таким образом, нам на самом деле нужна была вспомогательная функция для прохода по итератору до тех пор, пока мы не достигнем NULL, что указывает на конец хеша. Мы также используем здесь cast_ptr для приведения указателей void, которые мы получаем от iter_next(), к соответствующим типам, чтобы мы могли извлечь пары ключ/значение. Как только мы нажимаем NULL, мы возвращаем накопленный список из двух кортежей и используем его в качестве возврата из нашей командной функции. Постусловие сравнивает, соответствует ли отсортированный список моделей отсортированному списку, который мы выгрузили из хэш-карты.
Проблема с голубиной дырой
Однако, даже при всей этой изобретательности, у нас все еще нет неудач. Что, если мы намеренно попытаемся сделать значения потерянными, перезаписав существующие ключи? Это будет выглядеть примерно так:
Таким образом, мы генерируем пару ключ-значение для put(), которая намеренно создает ключ как один из ключей, уже находящихся в хэш-карте, и сгенерированное значение НЕ ДОЛЖНО уже присутствовать в хэш-карте. Это даст нам хороший способ увидеть, что происходит, когда мы «обновляем» ключ в хэш-карте.
Давайте запустим его и посмотрим, что произойдет:
10> eqc:quickcheck(eqc:numtests(1000, hashmap_eqc:prop_correct())).
..Failed! After 3 tests.
[{set,{var,1},{call,hashmap_eqc,hashmap_create,”\n”}},
{set,{var,2},{call,hashmap_eqc,hashmap_get,[{var,1},”±”]}},
{set,{var,3},{call,hashmap_eqc,hashmap_compare,[{var,1}]}},
{set,{var,4},{call,hashmap_eqc,hashmap_get,[{var,1},”õ”]}},
{set,{var,5},{call,hashmap_eqc,hashmap_compare,[{var,1}]}},
{set,{var,6},{call,hashmap_eqc,hashmap_delete,[{var,1},”\””]}},
{set,{var,7},{call,hashmap_eqc,hashmap_compare,[{var,1}]}},
{set,{var,8},{call,hashmap_eqc,hashmap_compare,[{var,1}]}},
{set,{var,9},{call,hashmap_eqc,hashmap_clear,[{var,1}]}},
{set,{var,10},{call,hashmap_eqc,hashmap_clear,[{var,1}]}},
{set,{var,11},{call,hashmap_eqc,hashmap_put,[{var,1},”y”,”T”]}},
{set,{var,12},{call,hashmap_eqc,hashmap_replace,[{var,1},”y”,”j”]}},
{set,{var,13},{call,hashmap_eqc,hashmap_compare,[{var,1}]}},
{set,{var,14},{call,hashmap_eqc,hashmap_get,[{var,1},[155]]}},
{set,{var,15},{call,hashmap_eqc,hashmap_clear,[{var,1}]}},
{set,{var,16},{call,hashmap_eqc,hashmap_put,[{var,1},”º”,”r”]}},
{set,{var,17},{call,hashmap_eqc,hashmap_compare,[{var,1}]}},
{set,{var,18},{call,hashmap_eqc,hashmap_put,[{var,1},”Ý”,”ä”]}}]
hashmap_eqc:hashmap_create(10) -> {ptr, {struct, hashmap_t}, 18817040}
hashmap_eqc:hashmap_get({ptr, {struct, hashmap_t}, 18817040}, “±”) ->
{1, 0, undefined}
hashmap_eqc:hashmap_compare({ptr, {struct, hashmap_t}, 18817040}) -> []
hashmap_eqc:hashmap_get({ptr, {struct, hashmap_t}, 18817040}, “õ”) ->
{1, 0, undefined}
hashmap_eqc:hashmap_compare({ptr, {struct, hashmap_t}, 18817040}) -> []
hashmap_eqc:hashmap_delete({ptr, {struct, hashmap_t}, 18817040}, “\””) -> 1
hashmap_eqc:hashmap_compare({ptr, {struct, hashmap_t}, 18817040}) -> []
hashmap_eqc:hashmap_compare({ptr, {struct, hashmap_t}, 18817040}) -> []
hashmap_eqc:hashmap_clear({ptr, {struct, hashmap_t}, 18817040}) -> ok
hashmap_eqc:hashmap_clear({ptr, {struct, hashmap_t}, 18817040}) -> ok
hashmap_eqc:hashmap_put({ptr, {struct, hashmap_t}, 18817040}, “y”, “T”) ->
{ptr, void, 18825440}
hashmap_eqc:hashmap_replace({ptr, {struct, hashmap_t}, 18817040}, “y”, “j”) ->
{ptr, void, 18825552}
hashmap_eqc:hashmap_compare({ptr, {struct, hashmap_t}, 18817040}) ->
[{“y”, “T”}, {“y”, “j”}]
Reason:
Post-condition failed:
{hash_mismatch, [{“y”, “j”}], [{“y”, “T”}, {“y”, “j”}]}
{postcondition,{hash_mismatch,[{“y”,”j”}],[{“y”,”T”},{“y”,”j”}]}} /= ok
false
Да! Контрпример! Мы нашли ошибку. Мы ожидали, что хэш-карта будет содержать [{"y", "j"}], но на самом деле она содержала [{"y", "T"}, {"y", "j"}], у нас было 2 значения для " клавиша у. Это ошибка (по крайней мере, в том, как мы определяем семантику этой хэш-карты). Если мы взглянем на реализацию функции hashmap_put(), то увидим, что она не очищает предыдущее значение этого ключа. Я сообщил об этом автору, и он сделал эту фиксацию, чтобы исправить и протестировать этот сценарий, давайте попробуем:
3> eqc:check(hashmap_eqc:prop_correct()). OK, passed the test. true
eqc:check() повторно запустит последний контрпример для данного свойства, поэтому, как только вы обнаружите сбой, вы сможете протестировать только этот сбой, пока не исправите его. Ошибка раздавлена. Давайте проведем еще несколько тестов, чтобы убедиться…
hashmap_eqc:hashmap_create(9) -> {ptr, {struct, hashmap_t}, 89178928}
hashmap_eqc:hashmap_delete({ptr, {struct, hashmap_t}, 89178928}, [159, 166, 202]) -> 1
hashmap_eqc:hashmap_delete({ptr, {struct, hashmap_t}, 89178928}, [1]) -> 1
hashmap_eqc:hashmap_put({ptr, {struct, hashmap_t}, 89178928}, [19], “{²”) ->
{ptr, void, 89183696}
hashmap_eqc:hashmap_iter_delete({ptr, {struct, hashmap_t}, 89178928}, [28, 92, 116]) -> 1
hashmap_eqc:hashmap_clear({ptr, {struct, hashmap_t}, 89178928}) -> ok
hashmap_eqc:hashmap_iter_delete({ptr, {struct, hashmap_t}, 89178928}, “È”) -> 1
hashmap_eqc:hashmap_clear({ptr, {struct, hashmap_t}, 89178928}) -> ok
hashmap_eqc:hashmap_put({ptr, {struct, hashmap_t}, 89178928}, “;”, “OÀO”) ->
{ptr, void, 89184336}
hashmap_eqc:hashmap_replace({ptr, {struct, hashmap_t}, 89178928}, “;”, “´S”) ->
{ptr, void, 89184576}
hashmap_eqc:hashmap_put({ptr, {struct, hashmap_t}, 89178928}, [3, 208], “ðE”) ->
{ptr, void, 89184992}
hashmap_eqc:hashmap_get({ptr, {struct, hashmap_t}, 89178928}, [142, 227, 49]) ->
{1, 0, undefined}
hashmap_eqc:hashmap_compare({ptr, {struct, hashmap_t}, 89178928}) ->
[{“;”, [180, 83, 0]}, {[3, 208], “ðE”}]
Reason:
Post-condition failed:
{hash_mismatch, [{[3, 208], “ðE”}, {“;”, “´S”}],
[{[3, 208], “ðE”}, {“;”, [180, 83, 0]}]}
{postcondition,{hash_mismatch,[{[3,208],”ðE”},{“;”,”´S”}],
[{[3,208],”ðE”},{“;”,[180,83,0]}]}} /= ok
false
5> [180, 83].
“´S”
О, теперь к значению добавлен случайный нулевой байт... что? Оказывается, исправление просто перераспределяет значение, но не сбрасывает длину значения, поэтому мы считываем длину значения в неопределенную память. Плохо. Я нажал исправление на исправление.
Удаляет, еще раз
Там не так много интересного для тестирования. Странные разновидности put/get — это только те, которые автоматически присваивают тип за вас. Единственная оставшаяся интересная функция — это hashmap_delete(), которую вы используете для удаления, когда перебираете хэш-карту. Давайте смоделируем эту команду.
Итак, снова мы генерируем ключ, как мы это делали для put и del, но на этот раз мы повторяем хэш, пока не найдем этот ключ, а затем передаем итератор в этой точке в hashmap_delete. В постусловии мы проверяем, что возвращаемое значение было ожидаемым, существующие ключи должны возвращать 0, несуществующие ключи должны возвращать 1 (если мы выпадаем из конца итератора, мы все равно пытаемся удалить итератор). Функция next_state удаляет ключ с карты.
Давайте соберем все это вместе и запустим сейчас:
OK, passed 1000 tests
15.28% {hashmap_eqc,hashmap_compare,1}
15.13% {hashmap_eqc,hashmap_iter_delete,2}
14.99% {hashmap_eqc,hashmap_get,2}
14.97% {hashmap_eqc,hashmap_clear,1}
14.92% {hashmap_eqc,hashmap_delete,2}
14.49% {hashmap_eqc,hashmap_put,3}
5.63% {hashmap_eqc,hashmap_create,1}
4.59% {hashmap_eqc,hashmap_replace,3}
true
Проверка на утечки
Ну, я думаю, это тоже работает, как и ожидалось. Как насчет проверки утечек памяти? В EQC-C есть классный способ запустить сгенерированную программу на C с помощью команды-оболочки, давайте попробуем. Просто добавь
{exec_command_line, fun(Exe) -> {os:find_executable("valgrind"), ["--leak-check=full", Exe]} end}
В конец списка параметров eqc_c:start для запуска команды под управлением valgrind. Давайте сделаем хороший длинный пробег, например, 15 минут:
eqc:quickcheck(eqc:testing_time(900, hashmap_eqc:prop_correct())).
==23954== Invalid read of size 8
==23954== at 0x41F52D: hashmap_delete (hashmap.c:461)
==23954== by 0x41387A: __eqc_c_wrapper_hashmap_delete (__eqc_tmp145296883325291_wrapper.c:3574)
==23954== by 0x4253ED: __eqc_c_interpreter_loop (eqc_c_lib.c:620)
==23954== by 0x42556F: __eqc_c_interpreter (eqc_c_lib.c:639)
==23954== by 0x41C39B: main (__eqc_tmp145296883325291_wrapper.c:5970)
==23954== Address 0x6bb0cf8 is 8 bytes before a block of size 2,048 alloc’d
==23954== at 0x4C28C10: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==23954== by 0x41C752: hashmap_create_with_allocator (hashmap.c:59)
==23954== by 0x41C8AB: hashmap_create (hashmap.c:81)
==23954== by 0x4135A2: __eqc_c_wrapper_hashmap_create (__eqc_tmp145296883325291_wrapper.c:3537)
==23954== by 0x4253ED: __eqc_c_interpreter_loop (eqc_c_lib.c:620)
==23954== by 0x42556F: __eqc_c_interpreter (eqc_c_lib.c:639)
==23954== by 0x41C39B: main (__eqc_tmp145296883325291_wrapper.c:5970)
Time limit reached: 900.0 seconds.
OK, passed 39965 tests
14.9205% {hashmap_eqc,hashmap_put,3}
14.8869% {hashmap_eqc,hashmap_get,2}
14.8748% {hashmap_eqc,hashmap_clear,1}
14.8599% {hashmap_eqc,hashmap_compare,1}
14.8477% {hashmap_eqc,hashmap_delete,2}
14.8462% {hashmap_eqc,hashmap_iter_delete,2}
6.0068% {hashmap_eqc,hashmap_create,1}
4.7573% {hashmap_eqc,hashmap_replace,3}
true
3>
User switch command
→ q
==22494== [../src/utils]
==22494== HEAP SUMMARY:
==22494== in use at exit: 0 bytes in 0 blocks
==22494== total heap usage: 1,244,999 allocs, 1,244,999 frees, 105,542,040 bytes allocated
==22494==
==22494== All heap blocks were freed — no leaks are possible
==22494==
==22494== For counts of detected and suppressed errors, rerun with: -v
==22494== ERROR SUMMARY: 62690 errors from 1 contexts (suppressed: 0 from 0)
О, недопустимое чтение размера 8 в hashmap_delete, в чем причина? Оказывается, передача законченного итератора в hashmap_delete приводит к недопустимому чтению. Мы можем довольно легко исправить это, и тогда прогон будет чистым.
Теперь, за исключением большого количества аллокаций/освобождений (что и ожидается), все выглядит хорошо. Вот почему я был так осторожен в очистке после всех моих выделений ранее. Я хотел иметь возможность проверить, есть ли в структуре данных какие-либо утечки.
Поиск плохого поведения и проверка покрытия
Как насчет проверки неопределенного поведения C или переполнения буфера в стеке? Мы можем добавить их в cflags для запуска eqc_c:
-fsanitize=undefined -fno-sanitize-recover -fstack-protector-strong
Это приведет к остановке программы из-за неопределенного поведения, а также установит красные зоны между элементами в стеке, поэтому переполнение приведет к ошибке несопоставленной страницы и сбою программы. Мы также можем получить некоторые числа о том, сколько раз каждая строка попадала в цель, используя эти cflags:
-fprofile-arcs -ftest-coverage
Еще один прогон:
Time limit reached: 900.0 seconds.
OK, passed 37209 tests
14.9676% {hashmap_eqc,hashmap_clear,1}
14.9604% {hashmap_eqc,hashmap_compare,1}
14.8948% {hashmap_eqc,hashmap_iter_delete,2}
14.8553% {hashmap_eqc,hashmap_get,2}
14.8513% {hashmap_eqc,hashmap_delete,2}
14.7747% {hashmap_eqc,hashmap_put,3}
5.9534% {hashmap_eqc,hashmap_create,1}
4.7425% {hashmap_eqc,hashmap_replace,3}
true
4>
User switch command
→ q
^andrew@macbookpro:: ==27754== [../src/utils]
==27754== HEAP SUMMARY:
==27754== in use at exit: 72,704 bytes in 1 blocks
==27754== total heap usage: 1,107,152 allocs, 1,107,151 frees, 97,994,853 bytes allocated
==27754==
==27754== LEAK SUMMARY:
==27754== definitely lost: 0 bytes in 0 blocks
==27754== indirectly lost: 0 bytes in 0 blocks
==27754== possibly lost: 0 bytes in 0 blocks
==27754== still reachable: 72,704 bytes in 1 blocks
==27754== suppressed: 0 bytes in 0 blocks
==27754== Reachable blocks (those to which a pointer was found) are not shown.
==27754== To see them, rerun with: — leak-check=full — show-leak-kinds=all
==27754==
==27754== For counts of detected and suppressed errors, rerun with: -v
==27754== ERROR SUMMARY: 59201 errors from 1 contexts (suppressed: 0 from 0)
И посмотрим на покрытие:
$ gcov hashmap.c File ‘hashmap.c’ Lines executed:89.25% of 186 Creating ‘hashmap.c.gcov’
Вот отчет. Строки имеют префикс количества вызовов. Строки без кода начинаются с тире, а недоступные строки — с префиксом #####. Единственные недостигнутые строки, о которых я действительно беспокоюсь, это 346 и 368. 346 достижима, если вы делаете глупые вещи с итераторами (например, двойная итерация, удаление с помощью одного итератора и попытка удаления со вторым). 368, я думаю, мертвый код.
Конец пути
Вот финальный тест EQC. Настоящая прелесть этого заключается в том, что, в отличие от обычного набора тестов, вы можете запускать миллионы сгенерированных тестов. На самом деле, я обычно не считаю тест EQC завершенным, если он не прошел как минимум миллион итераций. Я часто находил сумасшедшие ошибки после 750 000 тестов, которые оказывались законными, и такие ошибки, которые, если бы вы видели это в производственной среде, вы бы приписали космическим лучам, переворачивающим биты или что-то в этом роде. Как только вы расскажете EQC о тестируемой системе, он может бесконечно тестировать эту систему. Вам не нужно тратить много времени на размышления о действительно плохих пограничных случаях, чтобы превратить их в модульные тесты, EQC использует базовые знания о системе, чтобы найти эти пограничные случаи для вас.
Если вам нужна дополнительная информация, на сайте QuviQ есть гораздо больше информации, документации, тематических исследований, сообщений в блогах и видео. Вы также можете загрузить EQC-mini, функции которого аналогичны Haskell QuickCheck (без eqc_statem или EQC-C). Вы также можете ознакомиться с недавним наймом Helium, кражей Скотта Воукса, которая похожа на QuickCheck в C, или test.check ветерана Helium Рейда Дрейпера для Clojure. Также, вероятно, есть клон QuickCheck для вашего любимого языка.
