Lock-free tdb lookups

[David Collier-Brown]

Joe Seigh wrote:
> I took a look at the tdb source.  It would be pretty straightforward
> to make it read lock-free except for the transactional stuff.
> Transactions have to be atomic w.r.t. other operations.  I can't see
> any way of making things lock-free without infringing, in part at least,
> on patent application 20050198030 "Efficient support of consistent cyclic
> search with read-copy-update" by Paul McKenney, file in March 2004,
> and probably on anything else filed on software transactional memory.
> 
> So "Closed on account of patents" I guess.

If this is strictly lookups, are there uses of the tdb that
do not require consistency, merely atomicity?

If not, a former colleague used to recommend an algorithm
from many moons ago which did not guarantee consistency,
but allowed the reader to detect it was trying to read
while the data was inconsistent and return EAGAIN or ESTART.

That one was easy: there was a transaction-number field at
the beginning and the end of the updated location,
and the writer guaranteed to write the transaction
counter into the first number field, change the data
in between and then write the transaction number into
the last one.  ICL used this in disks, so you could
detect a half-complete write on power failure (;-))

This last might be an patent-free approach, or perhaps
prior art.

--dave
-- 
David Collier-Brown,      | Always do right. This will gratify
Sun Microsystems, Toronto | some people and astonish the rest
davecb at canada.sun.com     |                      -- Mark Twain
(416) 263-5733 (x65733)   |