tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

RCU (or equivalent) for NetBSD?


I have several builders for data structures which can be
modified by a single writer while lookups are concurrently
being performed by N readers, including a pretty good longest
match route lookup structure and some other utility search
structures.  The algorithms attempt to guarantee that
lookups in progress across a modification will always return
"correct" results, which in this case is defined to be either
the pre-modification result or the post-modification result and
nothing else.

There is a generic problem with putting a structure which
works like this to use (actually two related problems).  When
a modification removes a data item, so that it is no longer
referenced by the remaining structure, the deleted item can't be
freed or modified it until it can be proven that all lookups in
the structure which might have started before the modification
have completed to ensure that private references to the deleted
stuff can no longer exist in a reader.  In addition, while
ensuring "correct" results for lookups in progress across a single
modification isn't rocket science guaranteeing correct results across
several modifications sometimes is, so even if a modification
doesn't delete memory from the structure you would sometimes still
like to be able to defer starting a subsequent modification until
all lookups begun prior to the previous modification have

For Linux RCU provides generic infrastructure to solve this
problem.  RCU isn't the only way to solve this but it is a very
good way; it minimizes the read-side overhead, which is exactly
what you'd like for read-mostly data structures.  I do know there
are patents related to RCU but it looks to me like the only
one important for the basic technique has a 1993 filing date
and will expire this year.

Could the NetBSD kernel now acquire RCU, or RCU-like,
infrastructure?  I suspect I am incapable of designing this
myself but I have a pretty good idea about what it would
usefully enable.

Dennis Ferguson

Home | Main Index | Thread Index | Old Index