Re: [RFC] Lock free fd lookup

From: Keith Owens
Date: Fri Jul 16 2004 - 21:13:53 EST

On Fri, 16 Jul 2004 18:19:36 -0700,
William Lee Irwin III <wli@xxxxxxxxxxxxxx> wrote:
>On Sat, Jul 17, 2004 at 10:55:59AM +1000, Keith Owens wrote:
>> 2-3-4 trees are self balancing, which gave decent lookup performance.
>> Since red-black trees are logically equivalent to 2-3-4 trees it should
>> be possible to use lockfree red-black trees. However I could not come
>> up with a lockfree red-black tree, mainly because an read-black insert
>> requires atomic changes to multiple structures. The 2-3-4 tree only
>> needs atomic update to one structure at a time.
>This actually appears to confirm my earlier assertion about the linkage
>of the data structure. Is this conclusion what you had in mind?

Not quite. The 2-3-4 tree has embedded linkage, but it can be done
lockfree if you really have to. The problem is that a single 2-3-4
list entry maps to two red-black list entries. I could atomically
update a single 2-3-4 list entry, including its pointers, even when the
list was being read or updated by other users. I could not work out
how to do the equivalent update when the list linkage data was split
over two red-black nodes.

The list structure is an implementation detail, the use of 2-3-4 or
red-black is completely transparent to the main code. The main code
wants to lookup a structure from the list, to update a structure, to
insert or to delete a structure without waiting. How the list of
structures is maintained is a problem for the internals of the API.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at