General Concurrency Control Guidelines

Resources

Essential Linux Device Drivers, pg 39

kernel/Documentation/spinlocks.txt

kernel/Documentation/atomic_ops.txt

kernel/Documentation/mutex-design.txt

kernel/Documentation/rt-mutex.txt

kernel/Documentation/rt-mutex-design.txt

kernel/Documentation/RCU/whatisRCU.txt

kernel/Documentation/RCU/rcu.txt

kernel/Documentation/RCU/arrayRCU.txt

kernel/Documentation/RCU/listRCU.txt

http://lwn.net/Articles/146861/

Vanilla Linux

The concurrency control rules for vanilla Linux mostly carry over to PREEMPT-RT. The one exception is that preemption(not blocking) is allowed in more contexts. Remember that although PREEMPT-RT allows preemption to occur in many more contexts this is not the same as allowing blocking to occur in those contexts. Preeemption allows a better task to run but blocking suspends the current task for an indefinite period. Here are the rules for vanilla Linux:

Non-Blocking CC

Spinlocks

Run continually until lock is acquired

Generally, a spinlock should be held for a short amount of time because the waiters for the lock will be eating up CPU time busy waiting.

Can be acquired in interrupt context

Blocking and preemption are illegal, some examples are:

acquiring a mutex

calling the scheduler

kmalloc

GFP_ATOMIC is ok but can fail

printk

tracek from ftrace is ok

cancelling a hrtimer(hrttimer_cancel)

but attempting to cancel is safe(hrtimer_try_to_cancel)

the timer will cancel if not already running

cannot wait for timer callbacks to finish

Safe Operations:

starting an hrtimer

wake_up_process

as long as the runqueue_lock is not already held

API

spin_lock

spin_unlock

spin_lock_irqsave

spin_lock_irqrestore

spin_lock_irq

spin_unlock_irq

spin_try_lock

preempt_disable/enable

Protects per-cpu data if the data is accessed only by its corresponding CPU in thread context.

preempt_enable will call the scheduler if TIF_NEED_RESCHED is set.

preempt_disable/enable are used internally by spin_lock and spin_unlock.

Therefore, spin_unlock may invoke the scheduler.

If preempt_enable invokes the scheduler then PREEMPT_ACTIVE will be set

PREEMPT_ACTIVE is ored into the preempt_count()

preempt_count() is maintained in the thread info

Current task will NOT sleep(be taken off the runqueue) if PREEMPT_ACTIVE is set

TASK_INTERRUPTIBLE and TASK_UNINTERRUPTIBLE ignored by scheduler

task will be TASK_RUNNING when returning from preempt_enable

old state is lost

local_irq_disable/enable

Disable and enable interrupts without saving the current interrupt state.

Unsafe to use in a code path that might already have interrupts disabled.

local_irq_save/local_irq_restore resolves this danger

Safe to use if the code path does not already involve interrupts.

Useful for making per-cpu data interrupt safe.

local_irq_save/restore

Disable and enable interrupts

save state of interrupts

Safe to use in a code path that already has interrupts disabled.

Used in conjunction with other primitives if section is reachable by interrupt context.

RCU

Readers see data that is potentially outdated. Writers copy data and update the copy then present the copy as the current data. Readers may continue to use the old data.

Readers are lockless but must use rcu_read_lock/rcu_read_unlock.

RCU should only be used when there are many more readers than writers

RCU is only suited for data that is referred to by pointers

List based RCU operations are predefined for easy usage of RCU with lists.

You should not sleep in an RCU read side section.

Writers
Updating an RCU protected pointer

Acquire associated spinlock/mutex

Copy the current data using rcu_deref and kmalloc

Use rcu_assign_pointer to set copy as current data

Deleting data from an RCU protected list

Use list_del_rcu to unlink data from list

Call call_rcu/synchronize_rcu to allow readers to finish using the data

Call kfree after synchronize_rcu or inside the call_rcu callback

API

rcu_read_lock

rcu_read_unlock

synchronize_rcu

call_rcu

list_*_rcu

Runqueue Lock

spinlock

not preemptable

always used in conjunction with interrupts being disabled

There is a lock for each runqueue and there is one runqueue for each CPU.

Each scheduling class maintains its own runqueue information within the runqueue for each CPU

The scheduling classes all share the same runqueue locks

If each scheduilng class had a different lock then multiple locks would have to be acquired at scheduling time.

Protects scheduling data inside the task structure.

Protects data maintained by scheduling classes.

Acquired

scheduling time

Scheduling for a CPU cannot occur if its runqueue lock is acquired.

a task is changing scheduling classes

a task is moving between CPUs

cpu affinity data structures are set for a task

Seqlock

Reader-weriter lock that gives writers preference.

Not currently relevant to KUSP code.

Rwlock

Reader-writer lock.

Does not allow blocking operations.

Not currently relevant to KUSP code.

Blocking CC

These forms of concurrency control allow blocking operations to be performed in critical sections.

Mutex

Thread will sleep if the lock cannot be acquired immediately

Cannot be acquired in interrupt context.

Blocking operations can be performed.

API

mutex_*

Semaphores

Older form of mutual exclusion

Blocking operations are allowed while holding a semaphore.

Semaphores can have a count. The mutex API is a simplification of the semaphore API that assumes that the count is always 1.

Not currently reelevant to KUSP code.

RWSem

Similar to a reader-writer lock.

Allows blocking operations.

SRCU

Sleepable RCU

This is a special form of RCU that allows read side critical sections to sleep.

It can only be used in thread context. This includes both read and write sections.

It does not support the asynchronous call_rcu interface.

Atomic Operations

Vanilla kernel provides atomic integer operations and atomic bit operations.

Variable type for atomic integer field must be atomic_t.

Variable must be initialized using ATOMIC_INIT or atomic_set

Variable type for atomic bit field must be unsigned long.

Memory barrier semantics are automatic for operations that return a value.

Memory barrier sematnics are not provided for operations that do not return a value.

Specific memory barrier calls can be made before performing an operation.

CPU may reorder these operations if memory barrier semantics are not enforced.

Reordering can be especially dangerous for reference counts because memory may seem to be freeable when it is not.

API

atomic_*

*_bit

PREEMPT-RT

PREEMPT-RT introduces preemptible spinlocks and preemptible RCU. These features work because most interrupt handlers and all softirqs occur in thraed context. However, though these actions now occur in thread context, these threads should not perform blocking operations.

Atomic Spinlock

The non-preemptable vanilla spinlock API is renamed to the atomic spinlock API in PREEMPT-RT. Atomic spinlocks are only used in contexts where RT spinlocks cannot be used, such as interrupt context.

API

atomic_spin_lock

atomic_spin_unlock

atomic_spin_lock_irqsave

atomic_spin_lock_irqrestore

atomic_spin_lock_irq

atomic_spin_unlock_irq

atomic_spin_try_lock

Blocking and preemption are illegal

Illegal operations:

calling the scheduler

acquiring a mutex

acquiring a rt-spinlock

kmalloc

not even GFP_ATOMIC

kmalloc uses rt-spinlocks

printk

tracek from ftrace is ok

cancelling a hrtimer(hrttimer_cancel)

but attempting to cancel is safe(hrtimer_try_to_cancel)

the timer will cancel if not already running

cannot wait for timer callbacks to finish

CCSM write operations

Safe operations:

starting an hrtimer

wake_up_process

as long as the runqueue_lock is not already held

CCSM read operations

DSKI events

But be careful of what active filters are used because some active filters may perform blocking operations

RT Spinlock

An RT spinlock is a preemptable spinlock that causes waiters to sleep if the lock is held by a different task.

preemption allowed

Most vanilla spinlocks are converted into RT spinlocks.

Like vanilla spinlocks, blocking operations cannot be performed while holding an RT spinlock.

Sometimes you can get away with it without the system instantly exploding (since thread context is used) but it is considered evil.

RT spinlocks may cause a task to block inside the RT spinlock code but this is considered to be a special case of blocking. RT spinlocks can be acquired in some contexts where blocking operations are not allowed in vanilla Linux.

An RT spinlock can be acquired in a preemptable RCU read section.

An RT spinlock can be acquired in most interrupt handlers and softirqs because these sections occur in thread context under PREEMPT-RT.

Cannot be used in interrupt context

Ie: non-threaded interrupt handlers and the initial interrupt processing code that wakes up the itnerrupt threads

Safe operations

kmalloc using GFP_ATOMIC

but may fail if no memory is immediately available

RT-Mutex

Same rules as vanilla mutexes.

PREEMPT RCU

Preemptible RCU allows a thread to be preempted during a read side critical section. Blocking is still not allowed. SRCU is still for read-side critical sections that sleep.

Rwlock

Preemption allowed blocking not-allowed

not really r/w under PREEMPT-RT

uses rt-spinlocks internally

supposedly r/w has latency issues?