Skip to content

LockFreeOrderedHashMap: iterator protocol can present a null node past the != check under duplicate-heavy churn #18

Description

@Force67

Follow-up from #17. The preamble guard fixes one unguarded window, but a deeper iterator-protocol flaw remains. Reproducer and forensics below so it can be root-caused properly.

Reproducer

Four writer threads hammer insert() over an existing key space (every insert is a duplicate, so the post-CAS duplicate-backoff path runs constantly), one reader thread range-fors the map:

base::LockFreeOrderedHashMap<int, int> m(8);
for (int i = 0; i < 4000; ++i) m.insert(i, int{i});

// writers: m.insert((n * 7919) % 4000, {0});   // duplicate-heavy
// reader:  for (auto& kv : m) { check kv.first in range; }

Under ASan this crashes within seconds (SEGV reading a near-null node inside
the traversal), on the parent of #17 and with #17 applied. Reducing it:

  • Single-threaded interleaved insert/remove/iterate: clean.
  • Happens with insert-only churn (no remove, no GC sweep, no free) — so it
    is structural, not node-lifetime related.
  • Happens with GC freeing disabled entirely (still structural).
  • Happens through ordered_keys_snapshot() readers too — both chain walks are
    affected.
  • ThreadSanitizer reports no data race (all accesses are atomic; this is a
    logical lock-free flaw, not a missing fence).

gdb state at the fault shows the loop comparing begin.currentNode (null)
against end.currentNode and proceeding to dereference it anyway — i.e. the
!=/deref pair can observe a null node from advance_impl's bucket-hop or
the null short-circuit in operator++/skip_deleted. The Michael-Scott
order-chain append and the bucket sweep both look individually sound, so the
flaw is most likely in how the bucket-hop re-read (buckets[bucketIndex]),
the skip-deleted loop, and concurrent splices interact — but I have not
root-caused the exact interleaving.

Impact

zetanet's ack-map retry scan range-fors this map every retry interval, so the
flaw surfaces as the field crashes #17 partially addresses. The production
pattern (unique sequence-number inserts) reduces but does not obviously
eliminate the exposure, since ProcessOutgoingPackets also runs against
long-lived maps under heavy retransmit.

Suggested direction

A formal pass over the iterator protocol (advance/skip/compare vs the three
concurrent mutators: bucket prepend, order-chain append, GC sweep), or a
redesign where iteration hands out epoch-pinned key snapshots instead of live
node pointers.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions