Kernel(FreeBSD) Concurrency

Today, I had to revisit how FreeBSD system call path was synchronized. And here it is:

Kernel data structures are tradionally protected by the following synchronization methods.

• Interrupt disabling
• Spinlock
• System priority level
• Mutex

Disabling interrupts is the easiest method because only one code path can be executed with in a interrupt disbale/enable boundary. However exceptions are there which dont honour interrupts disabled attribute.

Eg:

1. Exceptions
2. Faults
3. NMI

Disabling interrupts wont work on SMP because interrupts can be disabled/enabled only on current CPU. Disabling interrupts is problematic if the code path takes longer time to complete. Because the kernel would have lost interrupts from devices.

Spinlocks is a datastructure residing on memory and acceissible from all the processors on the system. Before entering a critical code path spinlock is taken and all other access to that code path is prohibted and the other cpus will be in a loop trying to get the lock and enter. There are certain rules while creating a spinlock to avoid dead locks and gain performance from SMP.

1. Locking order heierarchy should be maintained to avoid dead locks.
2. Fine grained locks instead of single big lock to gain performance on SMP.

Spinlock alone would cause a dead lock in a preemptive kernel. Avoiding this in easy way is disabling interrupt because scheduler wont run. However it again would introduce a problem of losing interrupts.

system priority level or SPL is the prefered method to use with spinlock to avoid lock issues and also get interrupts from devices. SPL rules:

• And all spinlocks are at greater SPL than scheduler.
• All spinlocks should have a associated SPL and at that or greater SPL level only the spinlock should be taken.

Note:

1. In simpler term spl is equivalent to masking interrupts.
2. SPL is per processor, so the spinlock should have locking order hierarchy, otherwise deadlock for sure.

Mutexes used because even with fine grained spinlock there is performance penalty when other CPUs are waiting(looping) for a spinlock. Mutex solves this problem by scheduling out the looping threads in the other CPUs and selecting other threads to run.

Note:

• Mutex cant be used in certain situations eg: a interrupt handler which runs without context cant take mutex because it might be put into sleep.
• Combining mutex and spinlock requires only one condition - after a spinlock is taken no mutex acquire should be attempted.

FreeBSD 6.x uses mutex and spinlock - MUTEX_DEF and MUTEX_SPIN.

MUTEX_DEF - Is a mutex which result in going to sleep.

MUTEX_SPIN - Is a spinlock which never puts the caller into sleep but spins and also disables interrupts.

When FreeBSD was optimized for SMP, spinlocks were removed and mutex was introduced.

It also introduced context full interrupt handlers; now interrupt handlers can sleep, so can use mutex. Since most of the system calls was not ported to SMP, they were protected using a big mutex called Giant.

Giant - Gaint is a MUTEX_DEF which protects the code path of most system calls.