evict_to_len crash: node in linked list but missing from hash trie

[droideck]

Environment

• concread 0.5.10, plus diagnostic commit dd13f6a
• rustc 1.88.0
• Consumer: 389-ds-base

Problem

Under sustained concurrent load, evict_to_len panics because a node popped from the freq/rec linked list has no corresponding entry in the hash trie. cache.get_mut(&key) returns None for a key that was inserted moments earlier in the same commit.

This happens when a read transaction completes and try_quiesce_stats opportunistically acquires the write lock to commit pending cache maintenance.

Initial crash (concread 0.5.10, no diagnostics)

#13 ARCache::evict_to_len                            (mod.rs:1346)
      r = Option::None
      owned = LLNodeOwned { inner: 0x7f91877cfb40 }
#14 ARCache::evict                                   (mod.rs:1455)
      rec_to_len=120587, freq_to_len=4243, delta=1, p=86482
#15 ARCache::commit                                  (mod.rs:1694)
      commit_txid=40047203
#17 ARCache::try_quiesce_stats                       (mod.rs:693)
      tlocal: items=0, hit: len=0
      CursorWrite.length=136719, stats.includes=1
#18 cache_char_read_complete                         (cache.rs:228)

Diagnostic build crash (0.5.10 + dd13f6a)

I've added scanning for duplicates in the source list and checks against the destination ghost list, then reproduced:

evict_to_len: KEY MISSING from cache map for key "<dn_value>".
  Popped node ptr=0x7fb8d8ac7470, node_txid=41318110, node_size=1
  commit_txid=41318110, ll.len()=107677, to_ll.len()=34329,
  target_size=107677, dupes_remaining_in_src_ll=0,
  key_found_in_dest_ghost_ll=false

#12 ARCache::evict_to_len                            (mod.rs:1457)
      in_to_ll = false, dupes_in_ll = 0
      r = Option::None
      owned = LLNodeOwned { inner: 0x7fb8d8ac7470 }
#13 ARCache::evict                                   (mod.rs:1584)
      rec_to_len=107677, freq_to_len=17153, delta=1, p=84990
#14 ARCache::commit                                  (mod.rs:1881)
      commit_txid=41318110
#16 ARCache::try_quiesce_stats                       (mod.rs:711)
      tlocal: items=0, hit: len=0
      CursorWrite.length=159160, stats.includes=1
#17 cache_char_read_complete                         (cache.rs:228)

IIUC, node_txid == commit_txid means the node was added to the rec list during this commit by one of the drain functions. node_size=1 is HAUNTED_SIZE, consistent with a Haunted revival (I filed the drain_inc_rx size bug fix). No duplicates in the source list, key not in the ghost list. The key string itself is intact and readable in the panic message -- the linked list node's memory is fine. The hash trie just can't find it.

I wasn't able to find any place where we remove a cache map entry without removing the corresponding linked list node... And 389DS's code is fine too.

[droideck]

I am a bit at a loss here...
Is there any path where state from the linked lists or drain functions could cascade into a key being present in a list but absent from the hash trie?

Also, will it be okay to change the evict_to_len KEY MISSING panic to log-and-skip: pop() already removed the node from the linked list, so freeing the orphaned node heals the inconsistency and lets the cache continue.
Would you be open to that, or do you prefer a different recovery approach?

[Firstyear]

Something does feel off here yes. I'm more worried that this means we're double removing something so I'd rather resolve that then mask the "warning" here, as that could lead to a memory leak in some way.

Remember, even calling remove to the cache, it's not a true remove. It's just telling the cache to mark the item as haunted. So I doubt that 389 could cause this with it's inputs. If it was a 389 bug it'd be a use after free on a key dereference or something.

What's odd is that the commit function works in two phases - a grow phase, then an evict phase. But even then the evict shouldn't be removing anything, it's transferring to haunted. So I think this has to be occuring over multiple commits.

You'll see this in drain_tlocal_inc and drain_inc_rx - both assert and check that when they insert, the item did not already exist in the cache. If it's a duplicate insertion, we use the existing item and update it's linked list node state. So that should eliminate the possibility of there being two different list nodes related to one key. And yet, this bug indicates that this must be happening.

This means since it's happening in evict to len, that a key that is in recent/frequent which now is bad. So the order events likely has to involve these steps:

txn 0 - key is inserted
txn 1 - key is moved to haunted
txn 2 - haunted is drained as min txid is passed (causes cache item to be removed)
txn 3 - evict to len called and key was still present in freq/rec, but no longer in the cache.

So what we need to work out is what happened between these events for the key to be able to move to haunted, but also remain in freq/recent.

Given that we aren't triggering the duplicate key insert checks, we have to be adding the linked list node somewhere without updating the cache properly.

Another possibility could be that the key is changing - within the rust code we don't allow key manipulation but if 389 passes in a pointer for the key, it cuold then be changing that key content. This would make it so that the key could duplicate in the linked lists without the collision.

Some thoughts on how to progress:

• Add a stricter check on k to ensure at insert compared to when it's accessed in a node that it hasn't change (eg hashing the input key in some manner)
• A verification for the linked lists to assert their items all have a relevant cache entry, and that entry matches to the linked list item.

What do you think? Given the reproducer you have, is it affected by adding more verifications? I know sometimes if you add more checks it can slow things down and mask the issue.