%Concurrency
%Thadeu Cascardo

# Races

# Classical increment examples

* Threads are incrementing a counter
* Thread A reads the counter from memory
* Thread A is interrupted
* Thread B reads the counter from memory
* Thread B increments the counter
* Thread B saves the counter to memory
* Thread A executes and now has the wrong value in its registers

# Critical section

In the last example, the section of code that increments the *global*
counter is a critical section.

# Shared data

The problem in here is sharing data with multiple threads. When sharing,
we need to serialize the access, that is, only one thread may execute
the critical section at a time.

# Classical problems

* The Philosophers' Dinner
* The Barber Shop
* Consumer and Producer

# Linux historical race handling

* cli/sti
* BKL
* semaphores/old mutexes
* spinlocks
* RCU
* new mutexes

# Semaphores and mutexes

# Semaphores

* include linux/semaphore.h
* kernel/semaphore.c
* down(sem)
* up(sem)
* sema\\_init(sem, val)
* init\\_MUTEX(sem)
* init\\_MUTEX\\_LOCKED(sem)
* DECLARE\\_MUTEX(varname)
* down\\_interruptible(sem)

# New mutex

* Ingo Molnar's design
* Documented at Documentation/mutex-design.txt

# How to use the new mutex

* struct mutex
* mutex\\_init(mtx)
* DEFINE\\_MUTEX(varname)
* mutex\\_lock
* mutex\\_unlock

# When you should or should not use them

* They both sleep, so take care: no atomic contexts
* When the critical section may sleep

# Spinlocks

* include linux/spinlock.h
* Documentation/spinlocks.txt

# How to declare them

* DEFINE\\_SPINLOCK
* spinlock\\_t
* spin\\_lock\\_init

# How to use them

* spin\\_lock
* spin\\_unlock
* spin\\_lock\\_irqsave
* spin\\_unlock\\_irqrestore

# When you should and should not use them

* They can be used in atomic contexts
* They lock the processor when "waiting", so use for fast critical
  sections
* They create an atomic context themselves, so *do not* sleep while
  using them

# Atomic

* atomic\\_t
* ATOMIC\\_INIT(val)
* atomic\\_read(v)
* atomic\\_set(v, i)
* atomic\\_add\\_return(i, &v)
* atomic\\_add(i, &v)
* atomic\\_inc(i, &v)
* atomic\\_sub
* atomic\\_dec
* atomic\\_dec\\_and\\_test

# Bitmap

May be used for locking, but spinlocks are better nowadays.

# Per-CPU

* linux/percpu.h
* DEFINE\\_PER\\_CPU(type, name)
* get\\_cpu\\_var(name)
* put\\_cpu\\_var(name)
* per\\_cpu(name, cpu)
* alloc\\_percpu(type)
* free\\_percpu
* cpu = get\\_cpu()
* per\\_cpu\\_ptr(var, cpu)
* put\\_cpu()

# RCU

* rcu\\_read\\_lock
* rcu\\_dereference
* rcu\\_read\\_unlock
* rcu\\_assign\\_pointer
* synchronize\\_rcu
* call\\_rcu

# RCU for lists

* linux/rculist.h
* list_add_rcu
* list_add_tail_rcu
* list_del_rcu
* list_for_each_entry_rcu