WW #3

[Денис Лочмелис]

На данный момент container_of указывает со сдвигом на один разряд в записи адреса указателя. Я не стал втыкать такой жесткий костыль, поэтому не работает remove и print (print работает, но показывает чушь).

[Sokolov Viacheslav]

Смысл intrusive_list в том, что аллоцировать вершину списка отдельно не нужно.

  8 struct point {
  9     int x, y;
 10     intrusive_node* node;
 11 };

должно быть так

  8 struct point {
  9     int x, y;
 10     intrusive_node node;
 11 };

[Sokolov Viacheslav]

 75     char command[10] = {0};
 76     scanf("%10s", command);
 77

если буфер размера 10, то читать можно только 9 символов, еще 0 должен влезть

[Денис Лочмелис]

Поправил это и еще несколько штук.

[Денис Лочмелис]

Replying to Sokolov Viacheslav:
Но длина команд же и так не больше 5. Если будет ввод больше 10 символов, то он гарантированно некорректный и дальше считывать смысла нет. (Вроде.)

[Sokolov Viacheslav]

Replying to Денис Лочмелис:

Replying to Sokolov Viacheslav:
Но длина команд же и так не больше 5. Если будет ввод больше 10 символов, то он гарантированно некорректный и дальше считывать смысла нет. (Вроде.)

Ну, неправильное поведение надо на корню пресекать. Формально так делать неправильно.

[Sokolov Viacheslav]

• include отсутствует
• повторная сборка делает что-то нетривиальное (lab_03.elf -> lab_03); у целей не хватает зависимостей (например, obj/main.o от src/main.c и include/clicst.h)
• intrusive_node* curprev = to_rem->prev; // cannot be NULL - вместо комментария лучше оставить assert

• в remove_node не должно быть free, этот метод делает только unlink, то есть удаляет вершину из списка и ничего более
• все include должны быть наверху

• list->head не освобождается
• сейчас программа не работает на тестовых данных:

0x561eaf9352900x561eaf9356e00x561eaf9357203
0x561eaf9357600x561eaf935778
0x561eaf935738
0x561eaf9356f8
0x561eaf9352a8

Unknown command.
0x561eaf935778
0x561eaf935738
0x561eaf9356f8
0x561eaf9352a8

free(): invalid pointer
terminated by signal SIGABRT (Abort)

-

            iter = iter->prev;
            free(point_container(iter->next));

iter может быть NULL в этот момент

В общем тут до рабочей версии еще далеко. В идеале хотелось бы изолировать все детали реализации списка (наличие фиктивной вершины) в файле clist.c, а в main.c работать только с вершинами, относящимися к точкам.

[Денис Лочмелис]

• добавил \include
• как ни пробовал, повторная сборка / удаление все делают правильно
• заменил комментарии на assert

• как это не должно быть free? Надо же очистить память для point, помимо node (которая действительно внутри clist.c)
• все include теперь наверху

• видимо, подразумевалось, что при exit остатки листа не удаляются. Теперь удаляются
• так и не понял, что не так. Можно входные данные для этого примера?

• немного поправил и добавил assert

[Денис Лочмелис]

Видимо, имелся в виду пример из условия. Но он у меня прекрасно работает...

[Sokolov Viacheslav]

Основные проблемы:

Makefile:

• повторный запуск make делает что-то не тривиальное из-за неправильного названия цели

  lab_03: obj/main.o obj/clist.o 
          gcc obj/main.o obj/clist.o $(flags) -o lab_03.elf
  

и указания lab_03 в .PHONY

╰─>$ make
mkdir obj
gcc src/main.c -Wall -Wextra -Werror -Iinclude -c -o obj/main.o 
gcc src/clist.c -Wall -Wextra -Werror -Iinclude -c -o obj/clist.o 
gcc obj/main.o obj/clist.o -Wall -Wextra -Werror -Iinclude -o lab_03.elf
┬─[nicesap@nicesap-Inspiron-5570:~/H/s/l/lab_03]─[14:27:19]
╰─>$ make
gcc obj/main.o obj/clist.o -Wall -Wextra -Werror -Iinclude -o lab_03.elf

а должно быть

╰─>$ make
mkdir obj
gcc src/main.c -Wall -Wextra -Werror -Iinclude -c -o obj/main.o 
gcc src/clist.c -Wall -Wextra -Werror -Iinclude -c -o obj/clist.o 
gcc obj/main.o obj/clist.o -Wall -Wextra -Werror -Iinclude -o lab_03
┬─[nicesap@nicesap-Inspiron-5570:~/H/s/l/lab_03]─[14:29:35]
╰─>$ make
make: Nothing to be done for 'all'.

• отсутствуют зависимости .o от .h, .c, что приводит к тому, что проект не пересобирется, если были изменения в файлах (отсюда может быть "а у меня работает")

Множество ошибок, которые легко ловятся с помощью компиляции с -fsanitize=address:

• чтение из только что освобожденной памяти

   64         free(point_container(iter->next)); // frees a point                                          
   65         remove_node(list, iter->next)
  

==6774==ERROR: AddressSanitizer: heap-use-after-free on address 0x6030000000b0 at pc 0x5579a2463998 bp 0x7fffba2d3980 sp 0x7fffba2d3970
READ of size 8 at 0x6030000000b0 thread T0
    #0 0x5579a2463997 in remove_node (/home/nicesap/HSE/svn/lochmelis.denis/lab_03/lab_03+0x2997)
    #1 0x5579a2462bc1 in remove_point (/home/nicesap/HSE/svn/lochmelis.denis/lab_03/lab_03+0x1bc1)
    #2 0x5579a24632d9 in main (/home/nicesap/HSE/svn/lochmelis.denis/lab_03/lab_03+0x22d9)
    #3 0x7f0464884b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #4 0x5579a24627d9 in _start (/home/nicesap/HSE/svn/lochmelis.denis/lab_03/lab_03+0x17d9)

В методе remove_point

 30     intrusive_node* iter = list->head;                                                               
 31     assert(iter);
 32     while(iter->prev != NULL){                                                                       
 33         if(point_container(iter)->x == x && point_container(iter)->y == y){
 34             iter = iter->prev;
 35             free(point_container(iter->next)); // frees a point
 36             remove_node(list, iter->next);
 37         }else{

в 33 строке на первой итерации цикла будет обращение к памяти, не соответствующей никакому point (потому что list->head - фиктивная вершина)

то же в функции show_all_points

на этом проблемы не заканчиваются, -fsanitize=address в помощь

Кроме того,

• Вы точно понимаете, что делает "%200d"? В чем отличие от "%d"?
• Правильный комментарий. Считать можно максимум 199 символов. То есть "%199s".

  74     char command[200] = {0}; // max length = 199
  75     scanf("%200s", command);
  

ловится с помощью address sanitizer

==5115==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fffc63baa18 at pc 0x7f22c66441da bp 0x7fffc63ba680 sp 0x7fffc63b9e08
WRITE of size 201 at 0x7fffc63baa18 thread T0
    #0 0x7f22c66441d9  (/usr/lib/x86_64-linux-gnu/libasan.so.4+0x631d9)
    #1 0x7f22c6644fa8 in __isoc99_vscanf (/usr/lib/x86_64-linux-gnu/libasan.so.4+0x63fa8)
    #2 0x7f22c66450ae in __isoc99_scanf (/usr/lib/x86_64-linux-gnu/libasan.so.4+0x640ae)
    #3 0x5600feca00d8 in main (/home/nicesap/HSE/svn/lochmelis.denis/lab_03/lab_03+0x20d8)
    #4 0x7f22c6211b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #5 0x5600fec9f7d9 in _start (/home/nicesap/HSE/svn/lochmelis.denis/lab_03/lab_03+0x17d9)

Address 0x7fffc63baa18 is located in stack of thread T0 at offset 552 in frame
    #0 0x5600fec9ff3b in main (/home/nicesap/HSE/svn/lochmelis.denis/lab_03/lab_03+0x1f3b)

  This frame has 6 object(s):
    [32, 36) 'x'
    [96, 100) 'y'
    [160, 164) 'x'
    [224, 228) 'y'
    [288, 296) 'list'
    [352, 552) 'command' <== Memory access at offset 552 overflows this variable

Общий комментарий:
Рекомендую разобраться с Makefile. Собирать программу всегда с -g -fsanitize=address -fsanitize=undefined. Не откладывать реализацию лабораторной до последнего момента.

Баллы:
ставлю за стиль написания кода (именование, проверка контрактов, выравнивание) - с этим все неплохо (но можно еще чуть лучше) и за реализацию собственно списочной части (как-то так оно и должно выглядеть).