tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Patch: passive serialization

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.


- I belive that I have accurately implemented the algorithm described in
  the patent.

- The patch is against an earlier version of NetBSD and may not compile.

- It has not been tested and so should be considered as illustrating the
  concept only. The code does seem to be ok.

- No memory barriers are required on the reader side as issuing a cross-call
  makes CPUs in an MP system behave as if they were strongly ordered and
  without store buffers, in respect to certain types and method of
  operation. Proof not provided!

- Readers must do this, and must not block while in the critical section:

        /* do lookup operation */

- Writers do:

        /* make updates, install new data items for readers. */
        /* publish the updates. */
        /* now safe to destroy any old data items. */

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


** this means it is 'patent-free' in the United States

Home | Main Index | Thread Index | Old Index