Kernel Synchronization

Locks

• Kernel Locking Techniques
• Linux Kernel Hacking HOWTO: 5. Locking
• Unreliable Guide To Locking

Atomic operations

• <asm-xxx/atomic.h>
  • /path to kernel source/include/asm-xxx/atomic.h

• strcut atomic_t
  • special lock instructions are used to prevent the other processors in the system from working until the current processor has completed the next action.
  • The required instruction is actually called lock on IA-32 systems.
  • If the kernel was compiled without SMP support, the operations are implemented in the same way as for normal variables (only atomic_t encapsulation is observed.)
• struct local_t
  • per-cpu counters

Spinlock

• linux/Documentation/spinlocks.txt
  • Deadlock: an interrupt tries to lock an already locked variable. IFF you know that the spinlocks are never used in interrupt handlers, you can use the non-irq versions. If an interrupt tries to lock an already locked variable. This is ok if the other interrupt happens on another CPU, but it is not ok if the interrupt happens on the same CPU that already holds the lock, because the lock will obviously never be released.

spin_lock(&lock);
...
 <- interrupt comes in:
  spin_lock(&lock);

• Global spinlock list and usage
• Spinlock

• busy waiting
  • While the kernel is waiting for a spinlock to be released, it repeatedly checks whether it can acquire the lock without going to sleep in the meantime.
• Static Initialization

old version:
 static spinlock_t xxx_lock = SPIN_LOCK_UNLOCKED;
new version:
 static DEFINE_SPINLOCK(xxx_lock);
 or
 struct foo bar
 {
  .lock = __SPIN_LOCK_UNLOCKED(bar.lock);
 };

• Dynamic Initialization

spinlock_t xxx_lock;
spin_lock_init(&xxx_lock);

• no spin_lock required
  • locking in the same BH
    • a bottom half is never run on two CPUs at once
  • locking between different BHs
    • only one bottom half ever runs at a time once
  • Locking in the same tasklet
    • a tasklet is never run on two CPUs at once
• spin_lock/spin_unlock
  • locking between different tasklets
    • another tasklet (or bottom half, such as a timer) can run on the other CPUs
  • locking in the same Softirq(use a per-CPU array for better performance)
    • the same softirq can run on the other CPUs
  • locking between different Softirqs
  • UP
    • /path to kernel source/include/linux/spinlock_up.h
    • For kernels compiled without CONFIG_SMP, spinlocks do not exist at all.
  • SMP
• also disables the interrupts on the local CPU
  • used when you acquire a lock in an interrupt handler
  • locking between an interrupt handler and Softirqs/tasklets/BHs
  • spin_lock_irqsave/spin_unlock_irqrestore
    • save_flags(flags);cli()/restore_flags(flags);
  • spin_local_irq/spin_unlock_irq
    • disables and re-enables interrupts unconditionally, in the same manner as cli() and sti().
    • This code is only safe when you know that interrupts were not already disabled before the acquisition of the lock.
• also disables softIRQs(This stops bottom halves from being run on the current CPU. If you're already in a bottom half, this does nothing.)
  • locking between user context and BHs
  • locking between user context and tasklets/Softirqs
  • spin_lock_bh(It disables bottom halves on that CPU, then grabs the lock)
    • local_bh_disable();
    • preempt_disable();
    • spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
  • spin_unlock_bh

Semaphore

• If you have a data structure which is only ever accessed from user context, then you can use a simple semaphore (linux/asm/semaphore.h) to protect it. If you can't get a semaphore, your task will put itself on the queue, and be woken up when the semaphore is released. This means the CPU will do something else while you are waiting, but there are many cases when you simply can't sleep, and so have to use a spinlock instead.
• Semaphores in Linux
• Mutexes
  • a special case of semaphores
  • init_MUTEX/init_MUTEX_LOCKED
  • DECLARE_MUTEX/DECLARE_MUTEX_LOCKED

• sema_init
• down
  • the process is placed in the TASK_UNINTERRUPTIBLE state and cannot receive signals while waiting to enter the critical region.
• down_interruptible
  • the task in the TASK_INTERRUPTIBLE state if the semaphore could not be acquired. As a result, the process can be woken by signals while it is sleeping.
• down_trylock
  • If it fails, the process does not go to sleep to wait for the semaphore but continues execution normally.
• up

Completion Variables

• One task waits on the completion variable while another task performs some work. When the other task has completed the work, it uses the completion variable to wake up any waiting tasks. If this sounds like a semaphore, you are right the idea is much the same. In fact, completion variables merely provide a simple solution to a problem whose answer is otherwise semaphores.

Reader/Writer Locks

• Linux下写者优先的读写锁的设计

• rwlock_t
• rw_semaphore

Read-Copy-Update

The mechanism keeps track of all users of the pointer to the shared data structure. When the structure is supposed to change, a copy (or a new instance that is filled in appropriately, this does not make any difference) is first created and the change is performed there. After all previous readers have finished their reading work on the old copy, the pointer can be replaced by a pointer to the new, modified copy.