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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <YA/hHg8mH+e6cGOs@hirez.programming.kicks-ass.net>
Date:   Tue, 26 Jan 2021 10:30:06 +0100
From:   Peter Zijlstra <peterz@...radead.org>
To:     Davidlohr Bueso <dave@...olabs.net>
Cc:     linux-kernel@...r.kernel.org, walken@...gle.com, mingo@...nel.org,
        tglx@...utronix.de, oleg@...hat.com, irogers@...gle.com,
        juri.lelli@...hat.com, vincent.guittot@...aro.org
Subject: Re: [PATCH v2 5/7] rbtree, uprobes: Use rbtree helpers

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@stgolabs.net/
> 
> 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.