lkml.org 
[lkml]   [2005]   [Dec]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC] lockless radix tree readside
Joe Seigh wrote:

> Well, I don't have a kernel development set up so I can't comment on
> the specific patch but I have done some minor experimentation with reader
> lock-free b-trees, specifically insert, delete, and rotate (no actual
> balancing heuristics though) so I can comment on what some of the
> general issues are.
>
> You need to have a serialization point in your tree modifications so
> the change becomes atomically visible to threads reading the tree.

Yes, that is the memory barrier in rcu_assign_pointer.

> This is important for the semantics of your data structure. It's not
> good to have a node become temporarily invisible to readers if the
> tree operation involved moving a node or subtree around with more than
> a single link modification. So you will likely find yourself needing to
> use
> COW (copy on write) or PCOW (partial copy on write), particularly on
> deletes of non leaf nodes. PCOW is naturally better, especially if you
> can minimize the number of nodes that have to be copied.
>

Fortunately the radix tree never needs to do anything like this.
It doesn't move nodes or subtrees - the only modification operations
needed are to insert and delete items (ignoring the tag operations,
which are done under lock).

> So that's probably what you want to have in your documentation; what
> the serialization points are, your COW or PCOW mechanism, and how
> they preserve semantics.
>
> Also I assume you're returning lookups by value and not reference
> unless they're refcounted (which naturally since you're using RCU
> can be incremented safely if the refcount is not zero)
>

It can return either. It is up to the reader to do the right thing
in either case (which will need a note in the API comments).

Thanks,
Nick

--
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-12-06 23:38    [W:0.386 / U:0.252 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site