Re: [RFC] Lock free fd lookup

From: William Lee Irwin III
Date: Fri Jul 16 2004 - 21:38:51 EST

On Fri, 16 Jul 2004 18:19:36 -0700, William Lee Irwin III wrote:
>> This actually appears to confirm my earlier assertion about the linkage
>> of the data structure. Is this conclusion what you had in mind?

On Sat, Jul 17, 2004 at 12:12:39PM +1000, Keith Owens wrote:
> 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.

2-3 trees have external linkage just like B/B+ trees as I had
envisioned what external linkage is. Terminological issue I guess.

On Sat, Jul 17, 2004 at 12:12:39PM +1000, Keith Owens wrote:
> 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.

That kind of genericity is tough to come by in C. I guess callbacks and
void * can do it when pressed.

-- wli
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