Re: [PATCH v2 2.6.38-rc8-tip 4/20] 4: uprobes: Adding and remove auprobe in a rb tree.
From: Peter Zijlstra
Date: Wed Mar 16 2011 - 03:52:52 EST
On Tue, 2011-03-15 at 23:42 +0100, Eric Dumazet wrote:
> Le mardi 15 mars 2011 Ã 20:48 +0100, Peter Zijlstra a Ãcrit :
> > On Tue, 2011-03-15 at 20:22 +0100, Thomas Gleixner wrote:
> > > I am not sure if its a good idea to walk the tree
> > > > as and when the tree is changing either because of a insertion or
> > > > deletion of a probe.
> > >
> > > I know that you cannot walk the tree lockless except you would use
> > > some rcu based container for your probes.
> > You can in fact combine a seqlock, rb-trees and RCU to do lockless
> > walks.
> > https://lkml.org/lkml/2010/10/20/160
> > and
> > https://lkml.org/lkml/2010/10/20/437
> > But doing that would be an optimization best done once we get all this
> > working nicely.
> We have such schem in net/ipv4/inetpeer.c function inet_getpeer() (using
> a seqlock on latest net-next-2.6 tree), but we added a counter to make
> sure a reader could not enter an infinite loop while traversing tree
Right, Linus suggested a single lockless iteration, but a limited count
> (AVL tree in inetpeer case).
Ooh, there's an AVL implementation in the kernel? I have to ask, why not
use the RB-tree? (I know AVL has a slightly stronger balancing condition
which reduces the max depth from 2*log(n) to 1+log(n)).
Also, if it does make sense to have both and AVL and RB implementation,
does it then also make sense to lift the AVL thing to generic code into
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/