First item is sometimes skipped when iterating through linked lists

[GoogleCodeExporter]

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.

Original issue reported on code.google.com by kob...@mce-sys.com on 16 Jun 2014 at 2:33

[GoogleCodeExporter]

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)

Original comment by matthias.ringwald@gmail.com on 16 Jun 2014 at 2:44

[GoogleCodeExporter]

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.

Original comment by kob...@mce-sys.com on 16 Jun 2014 at 3:21

[GoogleCodeExporter]

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)

Original comment by matthias.ringwald@gmail.com on 16 Jun 2014 at 5:48

[GoogleCodeExporter]

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

Original comment by kob...@mce-sys.com on 17 Jun 2014 at 9:46

[GoogleCodeExporter]

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. 

Original comment by matthias.ringwald@gmail.com on 31 Jul 2014 at 9:23

• Changed state: WontFix