Export to GitHub

btstack - issue #403

First item is sometimes skipped when iterating through linked lists


Posted on Jun 16, 2014 by Swift Dog

I'm fairly new to new the code, so I might be missing something here, but from what I've seen, sometimes the first item is skipped when iterating through a linked list. Few examples I've found: - linked_list_remove: Skips the first item, and documents that "assumes that data_source_t.next is first element in data_source". But from what I've seen, in the posix run loop for example, this isn't true. - l2cap_handle_connection_failed_for_addr: Skips the first channel. - When handling HCI_EVENT_DISCONNECTION_COMPLETE in l2cap_event_handler,the first channel is skipped. - rfcomm_multiplexer_finalize skips the first channel.

It seems that the first item in linked lists (at least the ones I've seen) is valid and shouldn't be skipped.

Comment #1

Posted on Jun 16, 2014 by Swift Ox

Hi. Motivated by the issue about the problem iterating over a list while the current item is removed, I've started to create a robust list iterator implementation and will start using it. Handling the case that the current item gets removed by some other means (like linked_list_remove(..) is actually non-trivial and not covered in the text books I've seen).

The comment about data_sources is certainly not at the right place in linked_list.c. As far as I know, linked_list_remove works correctly, even for the first one.

Did you collect the examples above by testing the implementation or by looking at the code? (thanks anyway)

Comment #2

Posted on Jun 16, 2014 by Swift Dog

Hi Thanks for your fast reply. I'm testing btstack on windows, and I've replaced malloc\free with HeapAlloc\HeapFree so I could use Microsoft's Application Verifier, which helped me identify memory usage problems like use after free. It helped me debug a few problems I was facing, one of them I believe was caused by a timer being accessed by the run loop after it was freed. After going through the code, I suspect it was caused by an l2cap channel's rtx timer being freed, but not removed from the run loop's timers list. I believe it might be related (but not necessarily) to linked_list_remove always accessing "it->next", thus skipping the first item. While going through the code I've came across another place which was skipping the first item, which led me to manually search loops which start from the "next" item.

Comment #3

Posted on Jun 16, 2014 by Swift Ox

linked_list_remove is correct, as it is initialized with a pointer to the pointer to first item to allow for removal of the first element. it->next is equal to *head in this case.

nice idea with using a verifier. I guess I should learn to use Valgrind at one point.

I'll continue with the linked_list_iterator as that allows to review and verify a single implementation instead of checking every list iterator in the code. (and there are quite a few)

Comment #4

Posted on Jun 17, 2014 by Swift Dog

Yeah you are right about linked_list_remove, I've opened another issue for what i believe was causing the timer problem.

Comment #5

Posted on Jul 31, 2014 by Swift Ox

closing this one as the linked_list code is correct (not guilty until proven otherwise) and the linked_list_iterator can handle removal of current or later elements while iterating over it.

Status: WontFix

Labels:
Type-Defect Priority-Critical