[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: Patch: passive serialization
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
> 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,
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
* I apologise for being so verbal, but I would like this to be very clear.
Main Index |
Thread Index |