[trivial] Lwt_sequence.fold_r may visit items twice or more during concurrent removal

[stijn-devriendt]

Looking at https://github.com/ocsigen/lwt/blob/master/src/core/lwt_sequence.ml#L206
the fold_r skips to the next node instead of the previous one when node_active is false.

This might cause a node to be visited twice or more.

[aantron]

Fixing this particular issue in isolation should be as easy as changing the line to say node_prev instead of node_next.

I've created a separate issue (#406) for writing an actual test suite for Lwt_sequence.

Actually triggering this bug is a bit involved. I believe you have to first delete the current node inside f, and then also delete its next and/or previous node.

This is because... (picture):

...  <->  C  <->  N  <->  ...

C is the current node at some point during traversal, and N is a next (resp., previous) node, and we want to reach N from C with N not "active."

• When a node N becomes not active, the previous and next nodes are updated not to point to it. This code is thread-safe in current OCaml due to the global lock, and it does not interact with Lwt concurrency either. So, under ordinary circumstances, removing N would make it impossible to go from C to N.
• So, the only way to reach a not active node N during traversal, is for C's node_next/node_prev to not have been updated by the removal code linked above.
• In order for those links not to be updated, C must become not the next/previous node of N. For that, C must first get removed, which will unlink it from the point of view of N, but will not update the links in C: C will still point to N. When N is then also removed, the removal doesn't update the links in C, so C still points to the now-inactive node N. The traversal will then happily reach an inactive node.

[aantron]

Was fixed by the linked commit, in PR #434.