Pp. 155–164 of the Proceedings

UNIX-derived operating systems have traditionally have a simplistic approach to process synchronization which is unsuited to multiprocessor application. Initial FreeBSD SMP support kept this approach by allowing only one process to run in kernel mode at any time, and also blocked interrupts across multiple processors, causing seriously suboptimal performance of I/O bound systems. This paper describes work done to remove this bottleneck, replacing it with fine-grained locking. It derives from work done on BSD/OS and has many similarities with the approach taken in SunOS 5. Synchronization is performed primarily by a locking construct intermediate between a spin lock and a binary semaphore, termed mutexes. In general, mutexes attempt to block rather than to spin in cases where the likely wait time is long enough to warrant a process switch. The issue of blocking interrupt handlers is addressed by attaching a process context to the interrupt handlers. Despite this process context, an interrupt handler normally runs in the context of the interrupted process and is scheduled only when blocking is required.

Introduction

Use of processor time

• There is only one processor. All code runs on it.
• If both an interrupt handler and a process are available to run, the interrupt handler runs.
• Interrupt handlers have different priorities. If one interrupt handler is running and one with a higher priority becomes runnable, the higher priority interrupt immediately preempts the lower priority interrupt.
• The scheduler runs when a process voluntarily relinquishes the processor, its time slice expires, or a higher-priority process becomes runnable. The scheduler chooses the highest priority process which is ready to run.
• If the process is in kernel mode when its time slice expires or a higher priority process becomes runnable, the system waits until it returns to user mode or sleeps before running the scheduler.

Kernel data objects

int
fork1(p1, flags, procp)
	struct proc *p1;
	int flags;
	struct proc **procp;
{
	struct proc *p2, *pptr;

...
	/* Allocate new proc. */
	newproc = zalloc(proc_zone);

	item = z->zitems;
	z->zitems = ((void **) item)[0];
...
	return item;

What happens if the currently executing process is interrupted exactly between the first two lines of the code above, maybe because a higher priority process wants to run? item contains the pointer to the process structure, but z->z_items still points to it. If the interrupting code also allocates a process structure, it will go through the same code and return a pointer to the same memory area, creating the process equivalent of Siamese twins.

UNIX solves this issue with the rule ``The UNIX kernel is non-preemptive''. This means that when a process is running in kernel mode, no other process can execute kernel code until the first process relinquishes the kernel voluntarily, either by returning to user mode, or by sleeping.

Synchronizing processes and interrupts

Protection

The naming goes back to the early days of UNIX on the PDP-11. The PDP-11 had a relatively simplistic level-based interrupt structure. When running at a specific level, only higher priority interrupts were allowed. UNIX named functions for setting the interrupt priority level after the PDP-11 SPL instruction, so initially the functions had names like spl4 and spl7. Later machines came out with interrupt masks, and BSD changed the names to more descriptive names such as splbio (for block I/O) and splhigh (block out all interrupts).

Interrupt code does not need to perform any special synchronization: by definition, processes don't run when interrupt code is active.

Blocking interrupts has a potential danger that an interrupt will not be serviced in a timely fashion. On PC hardware, this is particularly evident with serial I/O, which frequently generates an interrupt for every character. At 115200 bps, this equates to an interrupt every 85 µs. In the past, this has given rise to the dreaded silo overflows; even on fast modern hardware it can be a problem. It's also not easy to decide interrupt priorities: in the early days, disk I/O was given a high priority in order to avoid overruns, while serial I/O had a low priority. Nowadays disk controllers can handle transfers by themselves, but overruns are still a problem with serial I/O.

Waiting for the other half

The top half of a driver calls sleep or tsleep when it wants to wait for an event, and the bottom half calls wakeup when the event occurs. In more detail,

• The process issues a system call read, which brings it into kernel mode.
• read locates the driver for the device and calls it to initiate a transfer.
• read next calls tsleep, passing it the address of some unique object related to the request. tsleep stores the address in the proc structure, marks the process as sleeping and relinquishes the processor. At this point, the process is sleeping.
• At some later point, when the request is complete, the interrupt handler calls wakeup with the address which was passed to tsleep. wakeup runs through a list of sleeping processes and wakes all processes waiting on this particular address.

In addition, it is permissible for more than one process to wait on a specific address. In extreme cases dozens of processes wait on a specific address, but only one will be able to run when the resource becomes available; the rest call tsleep again. The term thundering horde has been devised to describe this situation. FreeBSD has partially solved this issue with the wakeup_one function, which only wakes the first process it finds. This still involves a linear search through a possibly large number of process structures, and it has the potential to deadlock if two unrelated events map to the same address.

Adapting the UNIX model to SMP

• More than one processor is available. Code can run in parallel.
• Interrupt handlers and user processes can run on different processors at the same time.
• The ``non-preemption'' rule is no longer sufficient to ensure that two processes can't execute at the same time, so it would theoretically be possible for two processes to allocate the same memory.
• Locking out interrupts must happen in every processor. This can adversely affect performance.

The initial FreeBSD model

MPgetlock_edx:
1:
	movl	(%edx), %eax
	movl	%eax, %ecx
	andl	$CPU_FIELD,%ecx
	cmpl	_cpu_lockid, %ecx
	jne	2f
	incl	%eax
	movl	%eax, (%edx)
	ret
2:
	movl	$FREE_LOCK, %eax
	movl	_cpu_lockid, %ecx
	incl	%ecx
	lock
	cmpxchg	%ecx, (%edx)
	jne	1b
	GRAB_HWI
	ret

How to solve the dilemma

• Counting semaphores were originally designed to share a certain number of resources amongst potentially more consumers. To get access, a consumer decrements the semaphore counter, and when it is finished it increments it again. If the semaphore counter goes negative, the process is placed on a sleep queue. If it goes from -1 to 0, the first process on the sleep queue is activated. This approach is a possible alternative to tsleep and wakeup synchronization. In particular, it avoids a lengthy sequential search of sleeping processes.
• SunOS 5 uses turnstiles to address the sequential search problem in tsleep and wakeup synchronization. A turnstile is a separate queue associated with a specific wait address, so the need for a sequential search disappears.
• Spin locks have already been mentioned. FreeBSD used to spin indefinitely on the BKL, which doesn't make any sense, but they are useful in cases where the wait is short; a longer wait will result in a process being suspended and subsequently rescheduled. If the average wait for a resource is less than this time, then it makes sense to spin instead.
• Blocking locks are the alternative to spin locks when the wait is likely to be longer than it would take to reschedule. A typical implementation is similar to a counting semaphore with a count of 1.
• Condition variables are a kind of blocking lock where the lock is based on a condition, for example the absence of entries in a queue.
• Read/write locks address a different issue: frequently multiple processes may read specific data in parallel, but only one may write it.

One big problem with all locking primitives with the exception of spin locks is that they can block. This requires a process context: a UNIX interrupt handler can't block. This is one of the reasons that the old BKL was a spinlock, even though it could potentially use up most of processor time spinning.

The new FreeBSD implementation

The most radical difference in SMPng are:

• Interrupt code (``bottom half'') now runs in a process context, enabling it to block if necessary. This process context is termed an interrupt thread.
• Interrupt lockout primitives (splfoo) have been removed. The low-level interrupt code still needs to block interrupts briefly, but the interrupt service routines themselves run with interrupts enabled. Instead of locking out interrupts, the system uses mutexes, which may be either spin locks or blocking locks.

Interrupt threads

• The process context allows a uniform approach to synchronization: it is no longer necessary to provide separate primitives to synchronize the top half and the bottom half. In particular, the spl primitives are no longer needed. For compatibility reasons, the calls have been retained, but they translate to no-ops.
• The action of scheduling another process takes significantly longer than interrupt overhead, which also remains.
• The UNIX approach to scheduling does not allow preemption if the process is running in kernel mode.

• If the thread has to block.
• If the interrupt nesting level gets too deep.

From a scheduling viewpoint, the threads differ from normal processes in the following ways:

• They never enter user mode, so they do not have user text and data segments.
• They all share the address space of process 0, the swapper.
• They run at a higher priority than all user processes.
• Their priority is not adjusted based on load: it remains fixed.
• An additional process state SWAIT has been introduced for interrupt processes which are currently idle: the normal ``idle'' state is SSLEEP, which implies that the process is sleeping.

Experience with the initial implementation met expectations: we have seen no stability problems with the implementation, and the performance, though significantly worse, was not as bad as we had expected.

At the time of writing, we have improved the implementation somewhat by allowing limited kernel preemption, allowing interrupt threads to be scheduled immediately rather than having to wait for the current process to leave kernel mode. The potential exists for complete kernel preemption, where any higher priority process can preempt a lower priority process running in the kernel, but we are not sure that the benefits will outweigh the potential bug sources.

The final lazy scheduling implementation has been tested, but it is not currently in the -CURRENT kernel. Due to the current kernel lock implementation, it would not show any significant performance increase, and problems can be expected as additional kernel components are migrated from under Giant.

Not all interrupts have been changed to threaded interrupts. In particular, the old fast interrupts remain relatively unchanged, with the restriction that they may not use any blocking mutexes. Fast interrupts have typically been used for the serial drivers, and are specific to FreeBSD: BSD/OS has no corresponding functionality.

Locking constructs

• The default locking construct is the spin/sleep mutex. This is similar in concept to a semaphore with a count of 1, but the implementation allows spinning for a certain period of time if this appears to be of benefit (in other words, if it is likely that the mutex will become free in less time than it would take to schedule another process), though this feature is not currently in use. It also allows the user to specify that the mutex should not spin. If the process cannot obtain the mutex, it is placed on a sleep queue and woken when the resource becomes available.
• An alternate construct is a spin mutex. This corresponds to the spin lock which was already present in the system. Spin mutexes are used only in exceptional cases.

In addition to these locks, the FreeBSD project has included two further locking constructs:

Condition variables are built on top of mutexes. They consist of a mutex and a wait queue. The following operations are supported:

• Acquire a condition variable with cv_wait(), cv_wait_sig(), cv_timedwait() or cv_timedwait_sig().
• Before acquiring the condition variable, the associated mutex must be held. The mutex will be released before sleeping and reacquired on wakeup.
• Unblock one waiter with cv_signal().
• Unblock all waiters with cv_broadcast().
• Wait for queue empty with cv_waitq_empty.
• Same functionality available from the msleep function.

Shared/exclusive locks, or sx locks, are effectively read-write locks. The difference in terminology came from an intention to add additional functionality to these locks. This functionality has not been implemented, so currently sx locks are the same thing as read-write locks: they allow access by multiple readers or a single writer.

The implementation of sx locks is relatively expensive:

struct sx {
	struct lock_object sx_object;
	struct mtx	sx_lock;
	int		sx_cnt;
	struct cv	sx_shrd_cv;
	int		sx_shrd_wcnt;
	struct cv	sx_excl_cv;
	int		sx_excl_wcnt;
	struct proc	*sx_xholder;
};

• Create an sx lock with sx_init().
• Attain a read (shared) lock with sx_slock() and release it with sx_sunlock().
• Attain a write (exclusive) lock with sx_xlock() and release it with sx_xunlock().
• Destroy an sx lock with sx_destroy.

Removing the Big Kernel Lock

• Giant is used in a similar manner to the BKL, but it is a blocking mutex. Currently it protects all entry to the kernel, including interrupt handlers. In order to be able to block, it must allow scheduling to continue.
• sched_lock is a spin lock which protects the scheduler queues.

Idle processes

Recursive locking

There is much discussion both in the literature and in the FreeBSD SMP project as to whether recursive locking should be allowed at all. In general, we have the feeling that recursive locks are evidence of untidy programming. Unfortunately, the code base was never designed for this kind of locking, and in particular library functions may attempt to reacquire locks already held. We have come to a compromise: in general, they are discouraged, and recursion must be specifically enabled for each mutex, thus avoiding recursion where it was not intended.

Migrating to fine-grained locking

One of the dangers of this approach is that locking conflicts might not be recognized until very late. In particular, the FreeBSD project has different people working on different kernel components, and it does not have a strong centralized architectural committee to determine locking strategy. As a result, we developed the following guidelines for locking:

• Use sleep mutexes. Spin mutexes should only be used in very special cases and only with the approval of the SMP project team. The only current exception to this rule is the scheduler lock, which by nature must be a spin lock.
• Do not tsleep() while holding a mutex other than Giant. The implementation of tsleep() and cv_wait() automatically releases Giant and gains it again on wakeup, but no other mutexes will be released.
• Do not msleep() or cv_wait() while holding a mutex other than Giant or the mutex passed as a parameter to msleep(). msleep() is a new function which combines the functionality with atomic release and regain of a specified mutex.
• Do not call a function that can grab Giant and then sleep unless no mutexes (other than possibly Giant) are held. This is a consequence of the previous rules.
• If calling msleep() or cv_wait() while holding Giant and another mutex, Giant must be acquired first and released last. This avoids lock order reversals.
• Except for the Giant mutex used during the transition phase, mutexes protect data, not code.
• Do not msleep() or cv_wait() with a recursed mutex. Giant is a special case and is handled automagically behind the scenes, so don't pass Giant to these functions.
• Try to hold mutexes for as little time as possible.
• Try to avoid recursing on mutexes if at all possible. In general, if a mutex is recursively entered, the mutex is being held for too long, and a redesign is in order.

There are a number of reasons why we persist with this approach:

• FreeBSD is a volunteer project. Developers do what they think is best. They are unlikely to agree to an alternative implementation.
• We do not currently have enough architectural direction, nor enough experience with other SMP systems, to come up with an ideal locking strategy. This derives from the volunteer nature of the project, but note also that large UNIX vendors have found the choice of locking strategy to be a big problem.
• Unlike large companies, there is much less concern about throwaway implementations. If we find that the performance of a system component is suboptimal, we will discard it and start with a different implementation.

Migrating interrupt handlers

if ((ih->ih_flags & IH_MPSAFE) == 0)
        mtx_lock(&Giant);
....
ih->ih_handler(ih->ih_argument);
if ((ih->ih_flags & IH_MPSAFE) == 0)
        mtx_unlock(&Giant);

A typical strategy planned for migrating device drivers involves the following steps:

• Add a mutex to the driver softc.
• Set the INTR_MPSAFE flag when registering the interrupt.
• Obtain the mutex in the same kind of situation where previously an spl was used. Unlike spls, however, the interrupt handlers must also obtain the mutex before accessing shared data structures.

Probably the most difficult part of the process will involve larger components of the system, such as the file system and the networking stack. We have the example of the BSD/OS code, but it's currently not clear that this is the best path to follow.

Kernel trace facility

For example, the function sched_ithd, which schedules the interrupt threads, contains the following code:

CTR3(KTR_INTR, 
     "sched_ithd pid %d(%s) need=%d",
     ir->it_proc->p_pid, 
     ir->it_proc->p_comm, 
     ir->it_need);
...
if (ir->it_proc->p_stat == SWAIT) {
	CTR1(KTR_INTR, 
            "sched_ithd: setrunqueue %d",
	    ir->it_proc->p_pid);

for (;;) {
	CTR3(KTR_INTR, 
             "ithd_loop pid %d(%s) need=%d",
	     me->it_proc->p_pid, 
             me->it_proc->p_comm, 
             me->it_need);
...
	CTR1(KTR_INTR, 
            "ithd_loop pid %d: done",
             me->it_proc->p_pid);
	mi_switch();
	CTR1(KTR_INTR, 
             "ithd_loop pid %d: resumed",
             me->it_proc->p_pid);

2791 968643993:219224100 cpu1 ../../i386/isa/ithread.c:214 ithd_loop pid 21 ih=0xc235f200: 0xc0324d98(0) flg=100
2790 968643993:219214043 cpu1 ../../i386/isa/ithread.c:197 ithd_loop pid 21(irq0: clk) need=1 
2789 968643993:219205383 cpu1 ../../i386/isa/ithread.c:243 ithd_loop pid 21: resumed
2788 968643993:219190856 cpu1 ../../i386/isa/ithread.c:158 sched_ithd: setrunqueue 21
2787 968643993:219179402 cpu1 ../../i386/isa/ithread.c:120 sched_ithd pid 21(irq0: clk) need=0

• Entry 2787 shows the arrival of an interrupt at the beginning of sched_ithd. The second value on the trace line is the time since the epoch, followed by the CPU number and the file name and line number. The remaining values are supplied by the program to the CTR3 function.
• Entry 2788 shows the second trace call in sched_ithd, where the interrupt handler is placed on the run queue.
• Entry 2789 shows the entry into the main loop of ithd_loop.
• Entries 2790 and 2791 show the exit from the main loop of ithd_loop.

Witness facility

The witness code also checks various other conditions such as verifying that one does not recurse on a non-recursive lock. For sleep locks, witness verifies that a new process would not be switched to when a lock is released or a lock is blocked on during an acquire while any spin locks are held. If any of these checks fail, the kernel will panic.

Project status

• June 2000: Ported the BSD/OS mutex code and replaced the Big Kernel Lock with Giant and sched_lock.
• September 2000: Replaced interrupt handlers with heavyweight interrupt processors. Initial commit to the FreeBSD source tree.
• November 2000: Made softclock MP-safe and migrate from under Giant.
• January 2001: Implemented condition variables.
• March 2001: Implemented read/write locks (called ``shared/exclusive'' or sx locks).
• March 2001: Complete locking of enough of the proc structure to allow signal handlers to be moved from under Giant.

• Split NFS into client and server.
• Add locking to NFS.
• Make the IP stack thread-safe.
• Create mechanism in cdevsw structure to protect thread-unsafe drivers.
• Complete locking struct proc.
• Cleanup the various mp_machdep.c's, unify various SMP API's such as IPI delivery, etc.
• Make printf() safe to call in almost any situation to avoid deadlocks.
• Make mbuf system use condition variables instead of msleep() and wakeup().
• Remove the MP safe syscall flag from the system call table and add explicit mtx_lock of Giant to all system calls which need it.
• Use per-CPU buffers for ktr to reduce synchronization.
• Remove the priority argument from msleep() and cv_wait().
• Implement lazy interrupt thread switching (context stealing).
• Lock structs filedesc, pgrp, sigio, session and ifnet.
• Make the virtual memory subsystem thread-safe.
• Convert select() to use condition variables.
• Reimplement kqueue using condition variables.
• Conditionalize atomic operations used for debugging statistics.
• Lock the virtual file system code.

Performance

Acknowledgements

• John Baldwin rewrote the low level interrupt code for i386 SMP, made much code machine independent, worked on the WITNESS code, converted allproc and proctree locks from lockmgr locks to sx locks, created a mechanism in cdevsw structure to protect thread-unsafe drivers, locked struct proc and unified various SMP API's such as IPI delivery.
• Jake Burkholder ported the BSD/OS locking primitives for i386, implemented msleep(), condition variables and kernel preemption.
• Matt Dillon converted the Big Kernel spinlock to the blocking Giant lock and added the scheduler lock and per-CPU idle processes.
• Jason Evans made malloc and friends thread-safe, converted simplelocks to mutexes and implemented sx (shared/exclusive) locks.
• Greg Lehey implemented the heavy-weight interrupt threads, rewrote the low level interrupt code for i386 UP, removed spls and ported the BSD/OS ktr code.
• Bosko Milekic made sf_bufs thread-safe, cleaned up the mutex API and made the mbuf system use condition variables instead of msleep().
• Doug Rabson ported the BSD/OS locking primitives. implemented the heavy-weight interrupt threads and rewrote the low level interrupt code for the Alpha architecture.

Bibliography

Marshall Kirk McKusick, Keith Bostic, Michael J. Karels, John S. Quarterman, The Design and Implementation of the 4.4BSD Operating System, Addison-Wesley 1996.

Curt Schimmel, UNIX Systems for Modern Architectures, Addison-Wesley 1994.

Uresh Vahalia, UNIX Internals. Prentice-Hall, 1996.

Further reference

This paper was originally published in the Proceedings of the FREENIX Track: 2001 USENIX Annual Technical Conference, June 25-30, 2001, Boston, Masssachusetts, USA Last changed: 21 June 2001 bleu

Technical Program Conference index USENIX Home