deadlock bug in gc_layer

[jonahgao]

https://github.com/kohler/masstree-beta/blob/cfc62fa6d0f3b7c6d023bba529bed8f8456a674a/masstree_remove.hh#L68

It is unsafe to make_layer_root without locking the node child. In the implementation of make_layer_root, setting the root_bit is not atomic. (Even if it is atomic, there will also be other problem) https://github.com/kohler/masstree-beta/blob/cfc62fa6d0f3b7c6d023bba529bed8f8456a674a/nodeversion.hh#L274

Deadlock Scenario： Thread A：Inserting a key into the node child, lock child (lock_bit is set now)
Thread B: doing gc_layer, runnng inside mark_root, load v and calculate tmpv = v | P::root_bit ( lock_bit is set in tmpv)
Thread A: insert finished, unlock child (lockbit is unset now)
Thread B: assign tmpv back to v , then the node child's lock_bit is set forever

Since the locking order in the same layer is from bottom to up, can a try_lock operation fix this? My tentative solution: https://github.com/chubaodb/masstree-beta/commit/64bad5ebe3a2dbf998ff2e0ac9c24548cf0d226f

[kohler]

Thanks so much for this clean fix! I agree that this is probably the best way to address the problem.

[jonahgao]

Glad to see this issue fixed.