linux-kernel - Re: [RFC][PATCH 7/9] rbtree: Implement generic latch

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] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 2 Mar 2015 09:05:44 +0100
From:	Peter Zijlstra <peterz@...radead.org>
To:	Michel Lespinasse <walken@...gle.com>
Cc:	mingo@...nel.org, rusty@...tcorp.com.au,
	mathieu.desnoyers@...icios.com, oleg@...hat.com,
	paulmck@...ux.vnet.ibm.com, linux-kernel@...r.kernel.org,
	andi@...stfloor.org, rostedt@...dmis.org, tglx@...utronix.de,
	Andrea Arcangeli <aarcange@...hat.com>,
	David Woodhouse <David.Woodhouse@...el.com>,
	Rik van Riel <riel@...hat.com>
Subject: Re: [RFC][PATCH 7/9] rbtree: Implement generic latch_tree

On Sun, Mar 01, 2015 at 01:17:15PM -0800, Michel Lespinasse wrote:
> On Sat, Feb 28, 2015 at 1:24 PM, Peter Zijlstra <peterz@...radead.org> wrote:
> > Implement a latched RB-tree in order to get RCU style lookups.
> 
> Looks fine to me.
> 
> I wanted to ask, you are writing this as a generic layer even though
> there is a single use at the moment; do you anticipate this will get
> more usage soon ? I may have more comments if I knew what those may be
> (it's probably all fine if the rate of changes is very low such as
> with module load/unload, but I'm not sure what else you have in mind).

It was more an exercise in separation in order to better document the
various parts of this solution.

That said, we could maybe also use this for uprobes. Uprobes have a
global RB tree and every lookup is currently serialized by a spinlock.
I've not yet heard that its really painful, but I imagine a heavy uprobe
workload on big machines will eventually hurt.

And through the years there have been 'demands' for RCU RB-trees, so
maybe there's more potential users out there.

Note that while the update is more expensive than with a single tree,
its still of the same complexity, so its not horrendously more
expensive.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/