Re: [PATCH v2 5/7] rbtree, uprobes: Use rbtree helpers

[Peter Zijlstra]

On Mon, Jan 25, 2021 at 09:59:49PM -0800, Davidlohr Bueso wrote:
> On Mon, 25 Jan 2021, Peter Zijlstra wrote:
> 
> > Reduce rbtree boilerplate by using the new helpers.
> 
> This reminds me of:
> 
> https://lore.kernel.org/lkml/20200207180305.11092-6-dave@xxxxxxxxxxxx/
> 
> Would a walk optimization (list+rbtree) serve here? Not sure how big
> the uprobes_trees gets.

Oh, that's patch set is horrible.. You can do a linked list with the
unused node pointers directly.

  https://en.wikipedia.org/wiki/Threaded_binary_tree

So instead of using NULL for the empty rb_{left,right} pointers, use
pointers with the LSB set to differentiate them from regular leaf
pointers.

Other than that, threaded rb-trees would be awesome. I've meant to
implement them a number of times but never had the time to do the
tree-wide clean up of the rb_tree API to enable them.