Subj : Re: Hazard Pointers w/o memory barrier.
To   : comp.programming.threads
From : Joe Seigh
Date : Wed May 04 2005 07:53 am

On Tue, 3 May 2005 22:25:18 -0700, Chris Thomasson <_no_damn_spam_cristom@_no_damn_comcast.net_spam> wrote:

>
> What were the claims for the patented version of RCU? Was it the algorithm
> that used two counters and three rcu-batch lists nxtlist->curlist->donelist
> per-cpu?
>
The general technique is to defer freeing objects until every thread has
passed through a quiescent state at least once.  The first patent, which
is the only one in public domain, was tied to a specific implementation
in the VM operating system and the claims were limited to that implementation.
We didn't even think we invented the general technique so it didn't
occur to us to mention it except as the prior art mentioned in the patent,
i.e. the technique MVS used to purge the TLB's in a multiprocessor
configuration.  We didn't mention other techniques that occurred to us
at the time (eg. using timestamps) as part patent analysis (what
techniques could be used to get around the patent) since we didn't
believe at the time it was as good and would have added code to a
performance sensitive part of VM.  Plus doing a patent is a lot of
work and we didn't feel like doing a second one.  The first patent
used processor local events which had to be observed to occur twice
in order to infer that the processor had passed through a quiescent
state at least once since you started a particular deferred free.
Actually when we initally came up with the idea we only thought
of the at least once bit, we didn't realize the indirect events
had to be observed twice until we did the actual implementation
which the patent was based upon.

If you use events that are dependent on the deferred free, e.g.
timestamps, a common counter, or synchronized observation of processor
state, then you only need to observe the event once to correctly infer
that a processor has passed thru a quiescent state.  This can be
used to cut the average delay time in half or in combining tree
logic.  The technique is not mentioned in the first patent explicitly
and cannot be assumed to be in the public domain.  Except for the
processor state which while not mentioned in the first patent was
in the first implementation to handle processors in wait state.

There's multiple patents on this.  Only the first one is in the
public domain.  You'd have to make sure your implementation is
covered by that if you don't want to get permission from IBM.

>
>
>
>> Not really a problem if you're monitoring per processor/thread counters
>> or clocks since that's probably how you'd have to do it but with a commom
>> counter you could speed up the polling somewhat but it wouldn't strictly
>> be covered by the first patent.
>
> Seems that tracking per-cpu counters "and" keeping the batches on per-cpu
> lists would infringe on the patent. Humm... My implementation differs from
> this, but not much.

The per-cpu counters are events and are logically equivalent to the event flags
used in the first patent (events w/ single writer vs. eventcounts) but I
suppose one could be picky here.

>
>
>
>
>>> Yeah. Original SMR is well suited for high write throughput because of
>>> the
>>> guarantees it puts on the way nodes are deleted. This new URCU_SMR thing
>>> can't seem to handle frequent and persistent writes as good as the
>>> original.
>>> It caused some problems in a couple of my algorithms. Its probably a good
>>> idea to export two versions of SMR...
>>>
>> If you have a really high write rate then you would probably be better off
>> with a mutex or one of the write lock-free algorithms.
>
> Unfortunally, using a mutex slows down every test and the kernel usage goes
> off the charts. The specific algorithm that this caused problems with is the
> lock-free stack that AppCore exports. It's heavily optimized for high number
> of writes. It allocates its nodes internally from a three-part cache:
>
[...]

I use a semaphore to limit how much resources the writers can tie up at
any one time.  Seems preferable to running out of free memory.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.