<p>Ok, I think I got it now! The state corruption happens definitely within the thread, but not due to a remove happening just as something is added to the neighbor cache, but much earlier. It does not lead to a problem immediately due to a quirk of <code>clist</code> where the first element is not <code>list</code> or <code>list.next</code>, but <code>list.next->next</code>, so that most of its operations can be done in <em>O(1)</em>: <code>list</code> is just the entry point into the list, so it never appears in it itself, <code>list.next</code> is the last element of the list, so things can be appended in <em>O(1)</em> and <code>list.next->next</code> is the first.</p>
<p>It's pretty hard to explain, but when the last two <strong>elements</strong> are by change removed directly after each other when the NC is full (which introduces NULL pointers at the last and first <strong>position</strong>) and then two new NC entries are added (which have the same pointer as the removed ones), the NULL pointer at the <strong>position</strong> is first moved to the second <strong>position</strong> and then kept there, due to</p>
<p><a href="https://github.com/RIOT-OS/RIOT/blob/e78069b3163ec61ec5b691c1eefa5d68309b3263/core/include/clist.h#L115">https://github.com/RIOT-OS/RIOT/blob/e78069b3163ec61ec5b691c1eefa5d68309b3263/core/include/clist.h#L115</a></p>
<p>When another entry is tried to be added, the cache-out mechanism starts running (since the NC is full again) and tries to pop the first <strong>element</strong> (which is the NULL pointer) and it crashes.</p>
<p>When just the <strong>last</strong> element is removed the situation "fixes" itself, since the entry is still referred to by the first position, so re-adding it just leads to a loop of one (breaking the list, but not the system ;-)).</p>
<p>I provided a unittest to reproduce and illustrate the crash (<a class="commit-link" data-hovercard-type="commit" data-hovercard-url="https://github.com/RIOT-OS/RIOT/commit/2451fb36f8d5abea2cbb10cc61d60f597a0518e2/hovercard" href="https://github.com/RIOT-OS/RIOT/commit/2451fb36f8d5abea2cbb10cc61d60f597a0518e2"><tt>2451fb3</tt></a> while writing this message).</p>

<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">—<br />You are receiving this because you are subscribed to this thread.<br />Reply to this email directly, <a href="https://github.com/RIOT-OS/RIOT/pull/10975#issuecomment-461917017">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AEn7YBhW2zqe0dUjgbIsbdbbt2WeJd6Gks5vLc86gaJpZM4awWHA">mute the thread</a>.<img src="https://github.com/notifications/beacon/AEn7YOqnSlVH3RNJekYdmtSBj_sXVIsiks5vLc86gaJpZM4awWHA.gif" height="1" width="1" alt="" /></p>
<script type="application/json" data-scope="inboxmarkup">{"api_version":"1.0","publisher":{"api_key":"05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":{"external_key":"github/RIOT-OS/RIOT","title":"RIOT-OS/RIOT","subtitle":"GitHub repository","main_image_url":"https://github.githubassets.com/images/email/message_cards/header.png","avatar_image_url":"https://github.githubassets.com/images/email/message_cards/avatar.png","action":{"name":"Open in GitHub","url":"https://github.com/RIOT-OS/RIOT"}},"updates":{"snippets":[{"icon":"PERSON","message":"@miri64 in #10975: Ok, I think I got it now! The state corruption happens definitely within the thread, but not due to a remove happening just as something is added to the neighbor cache, but much earlier. It does not lead to a problem immediately due to a quirk of `clist` where the first element is not `list` or `list.next`, but `list.next-\u003enext`, so that most of its operations can be done in *O(1)*: `list` is just the entry point into the list, so it never appears in it itself, `list.next` is the last element of the list, so things can be appended in *O(1)* and `list.next-\u003enext` is the first.\r\n\r\nIt's pretty hard to explain, but when the last two **elements** are by change removed directly after each other when the NC is full (which introduces NULL pointers at the last and first **position**) and then two new NC entries are added (which have the same pointer as the removed ones), the NULL pointer at the **position** is first moved to the second **position** and then kept there, due to \r\n\r\nhttps://github.com/RIOT-OS/RIOT/blob/e78069b3163ec61ec5b691c1eefa5d68309b3263/core/include/clist.h#L115\r\n\r\nWhen another entry is tried to be added, the cache-out mechanism starts running (since the NC is full again) and tries to pop the first **element** (which is the NULL pointer) and it crashes.\r\n\r\nWhen just the **last** element is removed the situation \"fixes\" itself, since the entry is still referred to by the first position, so re-adding it just leads to a loop of one (breaking the list, but not the system ;-)).\r\n\r\nI provided a unittest to reproduce and illustrate the crash (2451fb36f8d5abea2cbb10cc61d60f597a0518e2 while writing this message)."}],"action":{"name":"View Pull Request","url":"https://github.com/RIOT-OS/RIOT/pull/10975#issuecomment-461917017"}}}</script>
<script type="application/ld+json">[
{
"@context": "http://schema.org",
"@type": "EmailMessage",
"potentialAction": {
"@type": "ViewAction",
"target": "https://github.com/RIOT-OS/RIOT/pull/10975#issuecomment-461917017",
"url": "https://github.com/RIOT-OS/RIOT/pull/10975#issuecomment-461917017",
"name": "View Pull Request"
},
"description": "View this Pull Request on GitHub",
"publisher": {
"@type": "Organization",
"name": "GitHub",
"url": "https://github.com"
}
}
]</script>