Page MenuHomePhabricator

Implement COW for the radix tree
ClosedPublic

Authored by deadalnix on Apr 27 2022, 21:34.

Details

Reviewers
Fabien
Group Reviewers
Restricted Project
Commits
rABCdd77141dbdd4: Implement COW for the radix tree
Summary

As per title.

It is now possible to "copy" a radix tree, but noting is actually copied. Instead only the node that get writtent o end up being lazily duplicated.

Test Plan

Added unit tests to cover the COW and move semantic.

Event Timeline

Fabien added inline comments.
src/radix.h
66
80
270

It took me an eternity to understand how this works, so I'm writing it here then you can correct me if I'm wrong. Here with the node but the same applies to the leaf

What you want is to increase the refcount for the node pointer, but getNode()->acquire() is not an option because acquire is a private member. So you need to use the RCUPtr interface to do so, as it is a friend class of the node. The solution is to first create a RCUPtr copy of the node pointer, to increase the refcount. But when the RCUPtr get out of scope and is destroyed, the refcount will be decremented again so it would be a null operation. To avoid that you are releasing the pointer from the RCUPtr first so the RCUPtr is nullified, which prevent the refcount from being decremented when the RCUPtr is destroyed since there is no pointer anymore.

Fabien added inline comments.
src/radix.h
157

Review note: this causes the copy to get out of scope, releasing the node childrens so the refcount doesn't get incremented if the CAS fails

164

Can you please add a comment that this is the unique_ptr being released to avoid calling the node destructor ? This is super confusing.

This revision is now accepted and ready to land.Apr 28 2022, 11:37
This revision was automatically updated to reflect the committed changes.