kern/llsync: rework lockless synchronization

Use a global checkpoint identifier as a generation counter and remove
reset interrupts.

For some reason I can't remember, using reset interrupts was thought to
be more efficient, perhaps because accessing a global variable on each
checkpoint looked expensive. But it's really not scalable, and a
read-mostly global variable can get cached locally and not incur expensive
access.

In addition, add a decent amount of documentation about the semantics
with regard to the rest of the system. Explicitely state that checkpoints
are triggered by context switches and that it's not allowed to block
inside read-side critical sections. Make periodic events attempt to trigger
checkpoints too. Add a thread-local read-side critical section nesting
counter so that it can be reliably determined whether the processor is
running a read-side critical section or not.

1 files changed, 89 insertions, 35 deletions

diff --git a/kern/llsync.h b/kern/llsync.h
index 1919b62a..0d7438bb 100644
--- a/kern/llsync.h
+++ b/kern/llsync.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013 Richard Braun.
+ * Copyright (c) 2013-2014 Richard Braun.
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -16,6 +16,55 @@
  *
  *
  * Lockless synchronization.
+ *
+ * The llsync module provides services similar to RCU (Read-Copy Update).
+ * As such, it can be thought of as an efficient reader-writer lock
+ * replacement. It is efficient because read-side critical sections
+ * don't use expensive synchronization mechanisms such as locks or atomic
+ * instructions. Lockless synchronization is therefore best used for
+ * read-mostly objects. Updating still requires conventional lock-based
+ * synchronization.
+ *
+ * The basic idea is that read-side critical sections are assumed to hold
+ * read-side references, and objects for which there may be read-side
+ * references must exist as long as such references may be held. The llsync
+ * module tracks special system events to determine when read-side references
+ * can no longer exist.
+ *
+ * Since read-side critical sections can run concurrently with updates,
+ * it is important to make sure that objects are consistent when being
+ * accessed. This is achieved with a publish/subscribe mechanism that relies
+ * on the natural atomicity of machine word updates in memory, i.e. all
+ * supported architectures must guarantee that, when updating a word, and
+ * in turn a pointer, other processors reading that word obtain a valid
+ * value, that is either the previous or the next value of the word, but not
+ * a mixed-up value. The llsync module provides the llsync_assign_ptr() and
+ * llsync_read_ptr() wrappers that take care of low level details such as
+ * compiler and memory barriers, so that objects are completely built and
+ * consistent when published and accessed.
+ *
+ * As objects are published through pointers, multiple versions can exist at
+ * the same time. Previous versions cannot be deleted as long as read-side
+ * references may exist. Operations that must wait for all read-side references
+ * to be dropped can be either synchronous, i.e. block until it is safe to
+ * proceed, or be deferred, in which case they are queued and later handed to
+ * the work module. As a result, special care must be taken if using lockless
+ * synchronization in the work module itself.
+ *
+ * The two system events tracked by the llsync module are context switches
+ * and a periodic event, normally the periodic timer interrupt that drives
+ * the scheduler. Context switches are used as checkpoint triggers. A
+ * checkpoint is a point in execution at which no read-side reference can
+ * exist, i.e. the processor isn't running any read-side critical section.
+ * Since context switches can be very frequent, a checkpoint is local to
+ * the processor and lightweight. The periodic event is used to commit
+ * checkpoints globally so that other processors are aware of the progress
+ * of one another. As the system allows situations in which two periodic
+ * events can occur without a single context switch, the periodic event is
+ * also used as a checkpoint trigger. When all checkpoints have been
+ * committed, a global checkpoint occurs. The occurrence of global checkpoints
+ * allows the llsync module to determine when it is safe to process deferred
+ * work or unblock update sides.
  */
 
 #ifndef _KERN_LLSYNC_H
@@ -30,10 +79,6 @@
 
 /*
  * Safely assign a pointer.
- *
- * This macro enforces memory ordering. It should be used to reference
- * objects once they're completely built, so that readers accessing the
- * pointer obtain consistent data.
  */
 #define llsync_assign_ptr(ptr, value)   \
 MACRO_BEGIN                             \
@@ -48,27 +93,31 @@ MACRO_END
  */
 #define llsync_read_ptr(ptr) (ptr)
 
+/*
+ * Read-side critical section enter/exit functions.
+ *
+ * It is not allowed to block inside a read-side critical section.
+ */
+
 static inline void
 llsync_read_enter(void)
 {
-    thread_preempt_disable();
+    int in_read_cs;
+
+    in_read_cs = thread_llsync_in_read_cs();
+    thread_llsync_read_inc();
+
+    if (!in_read_cs)
+        thread_preempt_disable();
 }
 
 static inline void
 llsync_read_exit(void)
 {
-    thread_preempt_enable();
-}
+    thread_llsync_read_dec();
 
-/*
- * Report that a processor has reached a checkpoint.
- *
- * Called during context switch.
- */
-static inline void
-llsync_checkin(unsigned int cpu)
-{
-    llsync_cpus[cpu].checked = 1;
+    if (!thread_llsync_in_read_cs())
+        thread_preempt_enable();
 }
 
 /*
@@ -77,34 +126,39 @@ llsync_checkin(unsigned int cpu)
 void llsync_setup(void);
 
 /*
- * Report that a processor will be regularly checking in.
+ * Manage registration of the current processor.
  *
- * Registered processors perform checkpoint commits and receive checkpoint
- * reset interrupts.
- */
-void llsync_register_cpu(unsigned int cpu);
-
-/*
- * Report that a processor has entered a state in which checking in becomes
- * irrelevant (e.g. the idle loop).
+ * The caller must not be allowed to migrate when calling these functions.
+ *
+ * Registering tells the llsync module that the current processor reports
+ * context switches and periodic events.
+ *
+ * When a processor enters a state in which checking in becomes irrelevant,
+ * it unregisters itself so that the other registered processors don't need
+ * to wait for it to make progress. For example, this is done inside the
+ * idle loop since it is obviously impossible to enter a read-side critical
+ * section while idling.
  */
-void llsync_unregister_cpu(unsigned int cpu);
+void llsync_register(void);
+void llsync_unregister(void);
 
 /*
- * Commit a pending checkpoint.
+ * Report a context switch on the current processor.
  *
- * Checking in is a light processor-local operation. Committing a checkpoint
- * is a heavier global one, and is performed less often, normally during the
- * system timer interrupt.
+ * Interrupts and preemption must be disabled when calling this function.
  */
-void llsync_commit_checkpoint(unsigned int cpu);
+static inline void
+llsync_report_context_switch(void)
+{
+    llsync_checkin();
+}
 
 /*
- * Reset the checkpoint pending state of a processor.
+ * Report a periodic event on the current processor.
  *
- * Called from interrupt context.
+ * Interrupts and preemption must be disabled when calling this function.
  */
-void llsync_reset_checkpoint(unsigned int cpu);
+void llsync_report_periodic_event(void);
 
 /*
  * Defer an operation until all existing read-side references are dropped,