synchronization

Causes of Concurrency in Userland

pseudo-concurreny: two things do not actually happen at the same time but interleave with each other
true concurreny: two processes are executed in a critical region at the exact same time.

Causes of Concurrency in Kernel

Interrupts
Softirq and tasklets
Kernel preemption
Sleeping and synchronization with user-space
Symmetrical multiprocessing

xxx-safe

interrupt-safe: Code that is safe from concurrent access from an interrupt handler
SMP-safe: Code that is safe from concurrency on symmetrical multiprocessing machines
preempt-safe: Code that is safe from concurrency with kernel preemption

Whenever you write kernel code, you should ask yourself these questions:

Is the data global? Can a thread of execution other than the current one access it?
Is the data shared between process context and interrupt context? Is it shared between two different interrupt handlers?
If a process is preempted while accessing this data, can the newly scheduled process access the same data?
Can the current process sleep (block) on anything? If it does, in what state does that leave any shared data?
What prevents the data from being freed out from under me?
What happens if this function is called again on another processor?
Given the proceeding points, how am I going to ensure that my code is safe from concurrency?

lock contention

The term lock contention, or simply contention, describes a lock currently in use but that another thread is trying to acquire.A lock that is highly contended often has threads waiting to acquire it. High contention can occur because a lock is frequently obtained, held for a long time after it is obtained, or both.

Atomic operations

Atomic Integer Operations
Atomic Bitwise Operations ## Atomic Integer Operations
atomic_t as operand

typedef struct { int counter; } atomic_t;

type checking for atomic operation functions
prevent compiler’s optimization, such as, alias
hide architecture-specific details for implementation
atomic_t has 32 bits
on most architecture, word-size read is always atomic

Atomic Integer Operation	Description
`ATOMIC_INIT(int i)`	At declaration, initialize to i.
`int atomic_read(atomic_t *v)`	Atomically read the integer value of v.
`void atomic_set(atomic_t *v, int i)`	Atomically set v equal to i.
`void atomic_add(int i, atomic_t *v)`	Atomically add i to v.
`void atomic_sub(int i, atomic_t *v)`	Atomically subtract i from v.
`void atomic_inc(atomic_t *v)`	Atomically add one to v.
`void atomic_dec(atomic_t *v)`	Atomically subtract one from v.
`int atomic_sub_and_test(int i, atomic_t *v)`	Atomically subtract i from v and return true if the result is zero; otherwise false.
`int atomic_add_negative(int i, atomic_t *v)`	Atomically add i to v and return true if the result is negative; otherwise false.
`int atomic_add_return(int i, atomic_t *v)`	Atomically add i to v and return the result.
`int atomic_sub_return(int i, atomic_t *v)`	Atomically subtract i from v and return the result.
`int atomic_inc_return(int i, atomic_t *v)`	Atomically increment v by one and return the result.
`int atomic_dec_return(int i, atomic_t *v)`	Atomically decrement v by one and return the result.
`int atomic_dec_and_test(atomic_t *v)`	Atomically decrement v by one and return true if zero; false otherwise.
`int atomic_inc_and_test(atomic_t *v)`	Atomically increment v by one and return true if the result is zero; false otherwise.

Atomic and Ordering

Atomicity ensures that instructions occur without interruption and that they complete either in their entirety or not at all.
Ordering, on the other hand, ensures that the desired, relative ordering of two or more instructions—even if they are to occur in separate threads of execution or even separate processors—is preserved.

64-Bit Atomic Operations

typedef struct { long counter; } atomic64_t;

Same as atomic integer, only operations on 64-bit and return long as its value. All operations have atomic64_ prefix.

Atomic Bitwise Operations

All bitwise operations are in <asm/bitops.h>

The bitop functions are defined to work on unsigned longs: - x64 system the bits numbered: + |0…………..63|64…………127|128………..191|192………..255| - ppc64 system the bits numbered: + |63…………..0|127…………64|191………..128|255………..192| - and on ppc32: + |31…..0|63….32|95….64|127…96|159..128|191..160|223..192|255..224|

Atomic Bitwise Operation	Description
`void set_bit(int nr, void *addr)`	Atomically set the nr -th bit starting from addr.
`void clear_bit(int nr, void *addr)`	Atomically clear the nr -th bit starting from addr.
`void change_bit(int nr, void *addr)`	Atomically flip the value of the nr -th bit starting from addr.
`int test_and_set_bit(int nr, void *addr)`	Atomically set the nr -th bit starting from addr and return the previous value.
`int test_and_clear_bit(int nr, void *addr)`	Atomically clear the nr -th bit starting from addr and return the previous value.
`int test_and_change_bit(int nr, void *addr)`	Atomically flip the nr -th bit starting from addr and return the previous value.
`int test_bit(int nr, void *addr)`	Atomically return the value of the nr - th bit starting from addr.

nr is the bit number, and there are no limitations on the bit number supplied i. e. nr can be greater than word-size on the architecture, but usually we do not use nr greater than word-size.

Atomic bitwise operations and their nonatomic versions are the only way for platform independent bitmap.

Locks

Spin Lock

Spin Lock will disable kernel PREEMPTION before acquire lock, and enable it after release lock.
If acquiring a lock without preemption disabled, the process holding the lock may lose its cpu to other process acquiring that lock too, and this will cause a unexpected long busy-wait.
On uniprocessor machine, spin_lock simply disables kernel preemption
spin_lock_irqsave and spin_unlock_irqstore are implemented partially as macros, so the argument acts like passing by reference.
In spin_ulock_irq*, irq is enabled first, otherwise, preempt_enable may cause reschedule and switch to another process with irq disabled.
CONFIG_DEBUG_SPINLOCK enables a handful of debugging checks in the spin lock code. ### spin_lock

disable preemption
acquire lock (try lock and spin) ### spin_unlock
release lock
enable preemption ### spin_lock_irq
disable local interrupt
disable preemption
acquire lock (try lock and spin) ### spin_unlock_irq
release lock
enable local interrupt
enable preemption ### spin_lock_irqsave
disable local interrupt and save the interrupt flag
disable preemption
acquire lock (try lock and spin) ### spin_unlock_irqrestore
release lock
enable local interrupt and restore the interrupt flag
enable preemption