Subj : Re: Hazard Pointers w/o memory barrier.
To   : comp.programming.threads
From : Chris Thomasson
Date : Thu May 05 2005 01:50 am

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

That seems fairly generic. Does a patent for this kind of stuff need to 
drill down on "specific" quiescent states, or can they actually get away 
with highly abstract claims?




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

Ahhh.




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

I see. My implementation does something like this. It's polling algorithm 
only has to observe a "certain" state of a per-thread and/or per-cpu 
data-structure once in order to detect quiescent state. The algorithm 
detects quiescent/grace periods by sampling information from threads and/or 
cpu info.




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


Are these some of them:

6,219,690
5,727,209
5,608,893
5,442,758

I really need to examine each of these. I hope they don't tie up every damn 
technique!




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

My unpublished stuff has logic that monitors cpu and/or threads bundled up 
in a "single algorithm" that uses pthreads and can run on Linux and Windows; 
I don't know how IBM lawyers would take that. Humm... I want to be able to 
use my implementation without getting sued!

:O




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

:)

.