diff options
Diffstat (limited to 'kern/llsync.h')
| -rw-r--r-- | kern/llsync.h | 124 |
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, |