f.f.o. :: /add |
Александр Фенстер |
| add@fenster.name | fenster.name |
Первое задание у ФИТа в этом семестре —
сделать bc-подобный целочисленный (int) калькулятор с поддержкой переменных.
Данный конкретный студент потратил довольно много времени на поиск и устранение всех утечек памяти
и обращений за пределы массивов (чистый прогон valgrind'ом —
одно из требований для сдачи в этом семестре) и наконец пришёл сдавать окончательный вариант программы.
Проверяю (сразу под валгриндом) и вижу следующую странность (жирным шрифтом показан мой ввод):
5-3
2
3-5
==27846== Invalid read of size 1
==27846== at 0x80492E3: hash (vars.c:12)
==27846== by 0x8049407: GetValue (vars.c:51)
==27846== by 0x80490A0: main (main.c:115)
==27846== Address 0x4194864 is 0 bytes after a block of size 4 alloc'd
==27846== at 0x4024C4C: malloc (vg_replace_malloc.c:195)
==27846== by 0x8049034: main (main.c:103)
==27846==
-2
Первая мысль — надо же, где же он там, интересно, работает с массивом, за пределы которого он вылазит. Вторая мысль — зачем в этом примере обращаться к хэш-функции: переменных же нет, от чего он считает хэш? Дальше было долгое ковыряние кода, в процессе которого был написан примерно следующий тесткейс:
$ ./calc
6513248+1
6513249 # простые примеры работают
ab=5
ab+1
6 # и переменные тоже работают,
abc=55 # но после такого присваивания
6513248+1
55 # начинают происходить странные вещи,
6513248+2
6513250 # хотя всё остальное в порядке!
Дело в том, что товарищ при работе с переменными сохранял и обрабатывал не их значения, а их имена в виде
char *. В итоге на этапе вычислений у него образовался стек из структур, содержащих void *
(которые на самом деле хранили либо int *, либо char *),
и при вычислениях и печати результата использовалась следующая логика:
if (GetValue((char *)p))
printf("%d\n", GetValue((char *)p));
else
printf("%d\n", *(int *)p);
Думаю, программирующие на C всё давно поняли и уже раскачиваются в трансе, обхватив голову руками.
Функция GetValue делает поиск полученной параметром строки в хэш-таблице и возвращает 0,
если переменной с таким именем не нашлось. В этом случае p рассматривается как указатель
на int и этот int и принимается за результат.
Если вы заводите переменную с именем abc, строка будет состоять из четырёх байт: символы
с кодами 97, 98, 99 и завершающий 0. На little-endian машине эти четыре байта, рассмотренные как один
int, дадут число 97+98*256+99*256*256=6513249. Программа от появления такого числа впадает
в транс и начинает путать его с переменной.
Объяснить ругань валгринда (вы ещё не забыли, с чего всё начиналось?) теперь проще простого. Если мы
проверяем программу на небольших положительных числах, в старших байтах чисел будет стоять 0, о который
запнётся и остановится функция вычисления хэш-кода имени переменной. Получив –2 (все четыре байта ненулевые),
цикл в вычислении хэш-кода пошёл дальше выделенных под int четырёх байт и валгринд сообщил об ошибке.
Отправил в итоге товарища гулять ещё на неделю. Пусть код перепишет.