Subj : Re: Hazard Pointers w/o memory barrier.
To   : comp.programming.threads
From : Joe Seigh
Date : Thu May 05 2005 11:31 am

On Thu, 5 May 2005 00:50:27 -0700, Chris Thomasson <_no_damn_spam_cristom@_no_damn_comcast.net_spam> wrote:

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

You try to make the claims as broad as possible without claiming prior
art.  Usually you have a series of claims starting with the most
broadly possible with subsequent claims being narrowed down with
more qualifications and let the patent office thow out the claims
they think are too broad rather than guess how much the patent office
will let you get away with.  This is why you see the claims refer to
previous claims, e.g. "Claim 2: Claim 1 further comprised with ..."
I think we claimed in the first patent that the quiescent states
could be arbitrary.  But a particular way of doing a quiescent state
could be patented if it's new.
>
>
[...]

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

As long as you have the correct synchronization and logic that allows
to infer correctly when the freed object is no longer referenced.
>
>
>
>
>> 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!

They're mostly continuation patents AFAICT.  So I think you only need
to look at the more recent ones.  Plus patent 5,809,168 which has lapsed.
McKenney put the list of patents in the Linux Kernel documentation somewhere.

-- 
Joe Seigh

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

.