Re: Patch: passive serialization

[Andrew Doran <ad%netbsd.org@localhost>]

Please note that in the following message and all communication on this
topic to date, I do not speak for any company, seperate entity or party,
but instead speak as a private individual. *

On Sun, Jan 11, 2009 at 07:10:59PM +0000, Mindaugas Rasiukevicius wrote:

> Andrew Doran <ad%netbsd.org@localhost> wrote:
> > This patch implements an algorithm similar to read-copy-update *. It is
> > covered by the lapsed US patent 4809168 ** and is a good technique for
> > making some table or lookup-type operations lockless. See ras_lookup()
> > for a good application.
> > 
> >     http://www.netbsd.org/~ad/cleanout/psync.diff
> >     http://www.google.com/patents?id=E14WAAAAEBAJ&dq=4809168
> > 
> 
> This is really cool!

If you interested in running with it there are a few things I think could
use doing. Maybe you have better ideas.

- make the read side explicit, eg xc_sync_enter(syncobj) ... exit(...)
- rename xc_sync() to xc_sync_publish() or something.
- make xc_sync_init() allocate the object dynamically and hide structure.
- make xc_sync_init() take a XC_HIGHPRI as a flag for future use.

> I just wonder if there are ways to validate that it is really patent-free.

In my opinion as a layman it is, having interpreted the patent in an
unforgiving way, although I can give no guarantee of that. IPI based
checkpointing may or may not be covered by the claims and descriptions.

Purely as a matter of record I do not advocate infringing on software
patents but abhor and strongly discourage any infringement of patents, and
it is with this in mind that I made the original posting in full and honest
belief that what I have written is true: the technique does not infringe any
other patents that I am aware of, because the technique is covered by an
existing lapsed patent. I am not an expert in this field and so my
interpretation of the situation cannot be relied on. *

> > Notes:
> > 
> > - I belive that I have accurately implemented the algorithm described in
> >   the patent.
> 
> What is the main difference between passive serialization and "traditional"
> RCU algorithm?

For the purposes of this implementation I am only interested in the text of
the existing, lapsed patent. I encourage others to investigate the situation
more fully.

> It would probably be good to add some comments that/how code should _not_
> diverge, as that might cause violations.

I think that would be useful. I copy here for the public good one
interesting section of text from the patent that I referenced.

        "It should be understood that, in general, application of the
        invention is not limited to the monitoring of references by hardware
        processors alone. Processors are themselves part of a larger
        category of "processes" which includes, for example, tasks in a
        multi-processing operating system, virtual processors and the like."

I encourage anyone interested to read the full text of the patent.
 
> > - It could be modified to use synchronization points other than context
> >   switch. For example, a low-priority soft interrupt on all CPUs, triggered
> >   via IPI. In that case the reader would do 'splsoftclock()+splx()'. The
> >   patent would have to be inspected to see if this is covered.
> 
> Any benefits using this?

Synchronization happens much more quickly. It would allow publishing updates
from a soft interrupt. Otherwise there is a kind of priority inversion,
where the soft interrupt would wait on relatively low priority cross-call
threads. As I mentioned earlier using high priority realtime xcall threads
would be one possible solution (although less than ideal).

> That would need a support for XC_HIGHPRI, that is, MI IPI interface,
> right?

Yes. That should not be hard to do given that SMP support is not widespread.
I think all MD code would need to provide is:

- a function to IPI one CPU
- a function to IPI all CPUs but the current CPU
- a callback into the MI xcall code when an IPI is processed

Thanks,
Andrew

* I apologise for being so verbal, but I would like this to be very clear.