Re: Patch: passive serialization

[Mindaugas Rasiukevicius <rmind%netbsd.org@localhost>]

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!

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

> 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? It would probably be good to add some comments that/how code
should _not_ diverge, as that might cause violations.

> - Readers must do this, and must not block while in the critical section:
> 
>       kpreempt_disable();
>       /* do lookup operation */
>       kpreempt_enable();
> 
> - Writers do:
> 
>       mutex_enter(&update_lock);
>       /* make updates, install new data items for readers. */
>       /* publish the updates. */
>       xc_sync(&sync_ojbect);
>       /* now safe to destroy any old data items. */
>       mutex_exit(&update_lock);
> 

You probably also meant that readers should no longer use any references
to the data after enable? How about putting these under, for example,
crit_reader_enter(), crit_writer_enter(), etc interface?

> - 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? That would need a support for XC_HIGHPRI, that is,
MI IPI interface, right?

-- 
Best regards,
Mindaugas