The Linux Kernel/Multitasking/Synchronization

Synchronization Thread Synchronization (computer science) synchronization is defined as a mechanism which ensures that two or more concurrent processes or threads do not simultaneously execute some particular program segment known as mutual exclusion (mutex). When one thread starts executing the critical section (serialized segment of the program) the other thread should wait until the first thread finishes. If proper synchronization techniques are not applied, it may cause a race condition where, the values of variables may be unpredictable and vary depending on the timings of context switches of the processes or threads. User space synchronization POSIX Timers ⚲ APIs 2 timer_create – creates a POSIX timer 2 timer_settime – starts or modifies a timer 2 timer_gettime – retrieves the remaining time of a timer 2 timer_delete – deletes a POSIX timer 2 clock_nanosleep – suspends execution for a specified time ⚙️ Internals linux/posix-timers.h kernel/time/itimer.c – interval timer (setitimer/getitimer) kernel/time/posix-timers.c – POSIX clock and timer operations kernel/time/posix-cpu-timers.c – per-process/thread CPU timers posix_cpu_timer_set – function setting up CPU timers Futex A 2 futex ↪ do_futex (short for "Fast User space muTex") is a kernel system call that programmers can use to implement basic locking, or as a building block for higher-level locking abstractions such as semaphores and POSIX mutexes or condition variables. A futex consists of a kernel space wait queue that is attached to an aligned integer in user space. Multiple processes or threads operate on the integer entirely in user space (using atomic operations to avoid interfering with one another), and only resort to relatively expensive system calls to request operations on the wait queue (for example to wake up waiting processes, or to put the current process on the wait queue). A properly programmed futex-based lock will not use system calls except when the lock is contended; since most operations do not require arbitration between processes, this will not happen in most cases. The basic operations of futexes are based on only two central operations futex_wait and futex_wake though implementation has more operations for more specialized cases. WAIT (addr, val) checks if the value stored at the address addr is val, and if it is puts the current thread to sleep. WAKE (addr, val) wakes up val number of threads waiting on the address addr. ⚲ API uapi/linux/futex.h linux/futex.h ⚙️ Internals: kernel/futex 🔨 stress-ng --futex 📖 References Futex 7 futex Futex API reference kernel-hacking/locking.html#futex-api-reference kernel/syscalls futex File locking ⚲ API: 2 flock Semaphore 💾 History: Semaphore is part of System V IPC 7 sysvipc ⚲ API 2 semget 2 semctl 2 semop ⚙️ Internals: ipc/sem.c 🔨 stress-ng --sem Kernel space synchronization For kernel mode synchronization Linux provides three categories of locking primitives: sleeping, per CPU local locks and spinning locks. rust/kernel/sync.rs – Rust bindings for locking primitives Read-Copy-Update Common mechanism to solve the readers–writers problem is the read-copy-update (RCU) algorithm. Read-copy-update implements a kind of mutual exclusion that is wait-free (non-blocking) for readers, allowing extremely low overhead. However, RCU updates can be expensive, as they must leave the old versions of the data structure in place to accommodate pre-existing readers. ⚲ The core API in linux/rcupdate.h is quite small: rcu_read_lock marks an RCU-protected data structure so that it won't be reclaimed for the full duration of that critical section. rcu_read_unlock is used by a reader to inform the reclaimer that the reader is exiting an RCU read-side critical section. Note that RCU read-side critical sections may be nested and/or overlapping. synchronize_rcu blocks until all pre-existing RCU read-side critical sections on all CPUs have completed. Note that synchronize_rcu will not necessarily wait for any subsequent RCU read-side critical sections to complete. For example, consider the following sequence of events: CPU 0CPU 1CPU 21.rcu_read_lock()2.enters synchronize_rcu()3. rcu_read_lock()4.rcu_read_unlock()5.exits synchronize_rcu()6.rcu_read_unlock() thumb|upright=2|RCU API communications between the reader, updater, and reclaimer Since synchronize_rcu is the API that must figure out when readers are done, its implementation is key to RCU. For RCU to be useful in all but the most read-intensive situations, synchronize_rcu's overhead must also be quite small. Alternatively, instead of blocking, synchronize_rcu may register a callback to be invoked after all ongoing RCU read-side critical sections have completed. This callback variant is called call_rcu in the Linux kernel. rcu_assign_pointer - The updater uses this function to assign a new value to an RCU-protected pointer, in order to safely communicate the change in value from the updater to the reader. This function returns the new value, and also executes any Memory barrier instructions required for a given CPU architecture. Perhaps more importantly, it serves to document which pointers are protected by RCU. rcu_dereference - The reader uses this function to fetch an RCU-protected pointer, which returns a value that may then be safely dereferenced. It also executes any directives required by the compiler or the CPU, for example, a volatile cast for gcc, a memory_order_consume load for C/C++11 or the memory-barrier instruction required by the old DEC Alpha CPU. The value returned by rcu_dereference is valid only within the enclosing RCU read-side critical section. As with rcu_assign_pointer, an important function of rcu_dereference is to document which pointers are protected by RCU. The RCU infrastructure observes the time sequence of rcu_read_lock, rcu_read_unlock, synchronize_rcu, and call_rcu invocations in order to determine when (1) synchronize_rcu invocations may return to their callers and (2) call_rcu callbacks may be invoked. Efficient implementations of the RCU infrastructure make heavy use of batching in order to amortize their overhead over many uses of the corresponding APIs. ⚲ API rcu_nocbs – no-callback CPUs linux/rcupdate.h linux/rculist.h – RCU-protected linked list operations ⚙️ Internals kernel/rcu – read-copy-update implementation 📖 References Avoiding Locks: Read Copy Update kernel-hacking/locking.html?#avoiding-locks-read-copy-update RCU concepts RCU RCU initialization 📚 Further reading Reduce synchronize_rcu() latency Sleeping locks Mutexes ⚲ API linux/mutex.h linux/completion.h mutex has owner and usage constraints, easier to debug than semaphore rt_mutex blocking mutual exclusion locks with priority inheritance (PI) support ww_mutex Wound/Wait mutexes: blocking mutual exclusion locks with deadlock avoidance rw_semaphore readers–writer semaphores percpu_rw_semaphore completion - use completion for synchronization task with ISR and task or two tasks. wait_for_completion complete 🔨 stress-ng --mutex 💾 Historical semaphore - use mutex instead semaphore if possible linux/semaphore.h linux/rwsem.h 📖 References Completions - “wait for completion” barrier APIs scheduler/completion.html Mutex API reference kernel-hacking/locking.html#mutex-api-reference LWN: completion events per CPU local lock On normal preemptible kernel local_lock calls preempt_disable. On RT preemptible kernel local_lock calls migrate_disable and spin_lock. Any changes applied to spinlock_t also apply to local_lock. ⚲ API linux/local_lock.h local_lock, preempt_disable local_lock_irqsave, local_irq_save etc 📖 References local_lock locking/locktypes.html#local-lock PREEMPT_RT caveats: spinlock_t, rwlock_t, migrate_disable and local_lock locking/locktypes.html#spinlock-t-and-rwlock-t Proper locking under a preemptive kernel locking/preempt-locking.html Local locks in the kernel Spinning locks Spinlocks a spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available. Since the thread remains active but is not performing a useful task, the use of such a lock is a kind of busy waiting. Once acquired, spinlocks will usually be held until they are explicitly released, although in some implementations they may be automatically released if the thread being waited on (that which holds the lock) blocks, or "goes to sleep". Spinlocks are commonly used inside kernels because they are efficient if threads are likely to be blocked for only short periods. However, spinlocks become wasteful if held for longer durations, as they may prevent other threads from running and require rescheduling. 👁 For example kobj_kset_join uses spinlock to protect assess to the linked list. Enabling and disabling of kernel preemption replaced spinlocks on uniprocessor systems (disabled CONFIG_SMP). Most spinning locks becoming sleeping locks in the CONFIG_PREEMPT_RT kernels. ⚲ API linux/spinlock.h spinlock_t raw_spinlock_t linux/bit_spinlock.h bit_spin_lock 📖 References Introduction to spinlocks Queued spinlocks Seqlocks A seqlock (short for "sequential lock") is a special locking mechanism used in Linux for supporting fast writes of shared variables between two parallel operating system routines. It is a special solution to the readers–writers problem when the number of writers is small. It is a reader-writer consistent mechanism which avoids the problem of writer starvation. A seqlock_t consists of storage for saving a sequence counter seqcount_t/seqcount_spinlock_t in addition to a lock. The lock is to support synchronization between two writers and the counter is for indicating consistency in readers. In addition to updating the shared data, the writer increments the sequence counter, both after acquiring the lock and before releasing the lock. Readers read the sequence counter before and after reading the shared data. If the sequence counter is odd on either occasion, a writer had taken the lock while the data was being read and it may have changed. If the sequence counters are different, a writer has changed the data while it was being read. In either case readers simply retry (using a loop) until they read the same even sequence counter before and after. ⚲ API seqlock_t DEFINE_SEQLOCK, seqlock_init, read_seqlock_excl, write_seqlock seqcount_t seqcount_init, read_seqcount_begin, read_seqcount_retry, write_seqcount_begin, write_seqcount_end linux/seqlock.h 👁 Example: mount_lock, defined in fs/namespace.c 📖 References Sequence counters and sequential locks locking/seqlock.html SeqLock Spinning or sleeping locks {| class="wikitable" ! !! normal !! on preempt RT |- | spinlock_t, || raw_spinlock_t || rt_mutex_base, rt_spin_lock, sleeping |- | rwlock_t || spinning || sleeping |- | local_lock || preempt_disable|| migrate_disable, rt_spin_lock, sleeping |} Low level The compiler might optimize away or reorder writes to variables leading to unexpected behavior when variables are accessed concurrently by multiple threads. ⚲ API asm-generic/rwonce.h – prevent the compiler from merging or refetching reads or writes. linux/compiler.h barrier – prevents the compiler from reordering instructions around the barrier asm-generic/barrier.h – generic barrier definitions arch/x86/include/asm/barrier.h – force strict CPU ordering mb – ensures that all memory operations before the barrier are completed before any memory operations after the barrier are started ⚙️ Internals Atomics driver-api/basics.html#atomics linux/atomic.h – atomic operations wrapper asm-generic/atomic.h linux/atomic/atomic-instrumented.h atomic_dec_and_test ... 📚 Further reading Volatile_(computer_programming)#In_C_and_C++ volatile – prevents the compiler from optimizations Memory barrier – enforces an ordering constraint on memory operations 🔨 stress-ng --lockbus ... ⚙️ Locking internals linux/lockdep.h – runtime locking correctness validator linux/debug_locks.h lib/locking-selftest.c – locking correctness self-tests kernel/locking – locking primitives mutex_waiter, timer_list, wait_queue_head_t kernel/locking/locktorture.c – module-based torture test facility for locking 📖 Locking references locking locking Lock types and their rules locking/locktypes.html 😴 sleeping locks locking/locktypes.html#sleeping-locks mutex, rt_mutex, semaphore, rw_semaphore, ww_mutex, percpu_rw_semaphore on preempt RT: local_lock, spinlock_t, rwlock_t 😵‍💫 spinning locks locking/locktypes.html#spinning-locks: raw_spinlock_t, bit spinlocks on non preempt RT: spinlock_t, rwlock_t Unreliable Guide To Locking kernel-hacking/locking.html LKMPG: Synchronization Synchronization primitives