From : www.makelinux.net/ldd3/chp-5-sect-5
Semaphores are a useful tool for mutual exclusion,but they are not the only such tool provided by the kernel. Instead,most locking is implemented with a mechanism called aspinlock. Unlike
semaphores, spinlocks may beused in code that cannot sleep, such as interrupt handlers. Whenproperly used, spinlocks offer higher performance than semaphores ingeneral. They do, however, bring a different set of constraints ontheir use.
Spinlocks are simple in concept. A spinlock is a mutual exclusiondevice that can have only two values:"locked" and"unlocked." It is usuallyimplemented as a single bit in an integer value. Code wishing to takeout a particular lock tests the
relevant bit. If the lock isavailable, the "locked" bit is setand the code continues into the critical section. If, instead, thelock has been taken by somebody else, the code goes into a tight loopwhere it repeatedly checks the lock until it becomes available.
Thisloop is the "spin" part of aspinlock.
Of course, the real implementation of a spinlock is a bit morecomplex than the description above. The "test andset" operation must be done in an atomic manner sothat only one thread can obtain the lock, even if several arespinning at any
given time. Care must also be taken to avoiddeadlocksonhyperthreadedprocessors—chips that implement multiple, virtual CPUs sharinga single processor core
and cache. So the actual spinlockimplementation is different for every architecture that Linuxsupports. The core concept is the same on all systems, however, whenthere is contention for a spinlock, the processors that are waitingexecute a tight loop and accomplish
no useful work.
Spinlocks are, by their nature, intended for use on multiprocessorsystems, although a uniprocessor workstation running a preemptivekernel behaves like SMP, as far as concurrency is concerned. If anonpreemptive uniprocessor system ever went
into a spin on a lock, itwould spin forever; no other thread would ever be able to obtain theCPU to release the lock. For this reason, spinlock operations onuniprocessor systems without preemption enabled are optimized to donothing, with the exception of the
ones that change the IRQ maskingstatus. Because of preemption, even if you never expect your code torun on an SMP system, you still need to implement proper locking.
5.5.1. Introduction to the Spinlock API
The required include file forthespinlock
primitives is<linux/spinlock.h>. An actual lock has thetype
spinlock_t. Like any other data structure, aspinlock must be initialized. This initialization may be done atcompile time as follows:
spinlock_t my_lock = SPIN_LOCK_UNLOCKED;
or at runtime with:
void spin_lock_init(spinlock_t *lock);
Before entering a critical section, your code must obtain therequisite lock with:
void spin_lock(spinlock_t *lock);
Note that all spinlock waits are, by their nature, uninterruptible.Once you call
spin_lock, you will spin until thelock becomes available.
To release a lock that you have obtained, pass it to:
void spin_unlock(spinlock_t *lock);
There are many other spinlock functions, and we will look at them allshortly. But none of them depart from the core idea shown by thefunctions listed above. There is very little that one can do with alock, other than lock and release it.
However, there are a few rulesabout how you must work with spinlocks. We will take a moment to lookat those before getting into the full spinlock interface.
5.5.2. Spinlocks and Atomic Context
Imagine for a moment that your driver acquires a spinlock and goesabout its business within its critical section. Somewhere in themiddle, your driver loses the processor. Perhaps it has called
afunction (copy_from_user, say) that puts theprocess to sleep. Or, perhaps, kernel preemption kicks in, and ahigher-priority process pushes your code aside. Your code is nowholding a lock that it will not release any time in
the foreseeablefuture. If some other thread tries to obtain the same lock, it will,in the best case, wait (spinning in the processor) for a very longtime. In the worst case, the system could deadlock entirely.
Most readers would agree that this scenario is best avoided.Therefore, the core rule that applies to spinlocks is that any codemust, while holding a spinlock, be atomic. It cannot sleep; in fact,it cannot relinquish the processor for any
reason except to serviceinterrupts (and sometimes not even then).
The kernel preemption case is handled by the spinlock code itself.Any time kernel code holds a spinlock, preemption is disabled on therelevant processor. Even uniprocessor systems must disable preemptionin this way to avoid race conditions.
That is why proper locking isrequired even if you never expect your code to run on amultiprocessor machine.
Avoiding sleepwhileholding a lock can be more difficult; many kernel functions cansleep, and this behavior is not always well documented. Copying datato or from user space is an obvious example:
the required user-spacepage may need to be swapped in from the disk before the copy canproceed, and that operation clearly requires a sleep. Just about anyoperation that must allocate memory can sleep;kmalloc can decide to
give up the processor, andwait for more memory to become available unless it is explicitly toldnot to. Sleeps can happen in surprising places; writing code thatwill execute under a spinlock requires paying attention to everyfunction that you call.
Here's another scenario: your driver is executingand has just taken out a lock that controls access to its device.While the lock is held, the device issues an interrupt, which causesyour interrupt handler to run. The interrupt handler, beforeaccessing
the device, must also obtain the lock. Taking out aspinlock in an interrupt handler is a legitimate thing to do; that isone of the reasons that spinlock operations do not sleep. But whathappens if the interrupt routine executes in the same processor asthe
code that took out the lock originally? While the interrupthandler is spinning, the noninterrupt code will not be able to run torelease the lock. That processor will spin forever.
Avoiding this trap requires disabling interrupts (on the local CPUonly) while the spinlock is held. There are variants of the spinlockfunctions that will disable interrupts for you(we'll see them in the next section). However, acomplete discussion
of interrupts must wait until
Chapter 10.
The last important rule for spinlock usage is that spinlocks mustalways be held for the minimum time possible. The longer you hold alock, the longer another processor may have to spin waiting for youto release it, and the chance of it having
to spin at all is greater.Long lock hold times also keep the current processor from scheduling,meaning that a higher priority process—which really should beable to get the CPU—may have to wait. The kernel developers puta great deal of effort into reducing
kernel latency (the time aprocess may have to wait to be scheduled) in the 2.5 developmentseries. A poorly written driver can wipe out all that progress justby holding a lock for too long. To avoid creating this sort ofproblem, make a point of keeping your
lock-hold times short.
5.5.3. The Spinlock Functions
We have already seen twofunctions,spin_lock and
spin_unlock,that manipulate spinlocks. There are several other functions,however, with similar names and purposes. We will now present thefull set. This discussion will take us into ground we will not beable to cover properly
for a few chapters yet; a completeunderstanding of the spinlock API requires an understanding ofinterrupt handling and related concepts.
There are actually four functions that can lock a spinlock:
void spin_lock(spinlock_t *lock); void spin_lock_irqsave(spinlock_t *lock, unsigned long flags); void spin_lock_irq(spinlock_t *lock); void spin_lock_bh(spinlock_t *lock)
We have already seen how spin_lock works.spin_lock_irqsave disables interrupts (on thelocal processor only) before taking the spinlock; the previousinterrupt state is stored
in flags. If you areabsolutely sure nothing else might have already disabled interruptson your processor (or, in other words, you are sure that you shouldenable interrupts when you release your spinlock), you can usespin_lock_irq
instead and not have to keep trackof the flags. Finally,
spin_lock_bh disablessoftware interrupts before taking the lock, but leaves hardwareinterrupts enabled.
If you have a spinlock that can be taken by code that runs in(hardware or software) interrupt context, you must use one of theforms of
spin_lock that disables interrupts.Doing otherwise can deadlock the system, sooner or later. If you donot access your lock in a hardware interrupt handler, but you do viasoftware interrupts (in code that runs out of a tasklet,
for example,a topic covered in
Chapter 7),you can use spin_lock_bh to safely avoiddeadlocks while still allowing hardware interrupts to be serviced.
There are also four ways torelease a spinlock; the one you use must correspond to the functionyou used to take the lock:
void spin_unlock(spinlock_t *lock); void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags); void spin_unlock_irq(spinlock_t *lock); void spin_unlock_bh(spinlock_t *lock);
Each spin_unlock variant undoes the workperformed by the corresponding
spin_lockfunction. The flags argument passed tospin_unlock_irqrestore must be the same variablepassed to
spin_lock_irqsave. You must also callspin_lock_irqsave andspin_unlock_irqrestore in the same function;otherwise, your code may break on some architectures.
There is also a set of nonblocking spinlockoperations:
int spin_trylock(spinlock_t *lock); int spin_trylock_bh(spinlock_t *lock);
These functions return nonzero on success (the lock was obtained),0 otherwise. There is no"try" version that disablesinterrupts.
5.5.4. Reader/Writer Spinlocks
The kernel provides a reader/writer form of spinlocks thatis directly analogous to the reader/writer semaphores we saw earlierin this chapter. These locks allow any number of readers into acritical
section simultaneously, but writers must have exclusiveaccess. Reader/writer locks have a type ofrwlock_t, defined in<linux/spinlock.h>. They can be declaredand initialized in two ways:
rwlock_t my_rwlock = RW_LOCK_UNLOCKED; /* Static way */ rwlock_t my_rwlock; rwlock_init(&my_rwlock); /* Dynamic way */
The list of functions available should look reasonably familiar bynow. For readers, the following functions are available:
void read_lock(rwlock_t *lock); void read_lock_irqsave(rwlock_t *lock, unsigned long flags); void read_lock_irq(rwlock_t *lock); void read_lock_bh(rwlock_t *lock); void read_unlock(rwlock_t *lock); void read_unlock_irqrestore(rwlock_t *lock, unsigned long flags); void read_unlock_irq(rwlock_t *lock); void read_unlock_bh(rwlock_t *lock);
Interestingly, there is no read_trylock.
The functions for write access are similar:
void write_lock(rwlock_t *lock); void write_lock_irqsave(rwlock_t *lock, unsigned long flags); void write_lock_irq(rwlock_t *lock); void write_lock_bh(rwlock_t *lock); int write_trylock(rwlock_t *lock); void write_unlock(rwlock_t *lock); void write_unlock_irqrestore(rwlock_t *lock, unsigned long flags); void write_unlock_irq(rwlock_t *lock); void write_unlock_bh(rwlock_t *lock);
Reader/writer locks can starve readers
just as rwsems can. This behavior israrely a problem; however, if there is enough lock contention tobring about starvation, performance is poor anyway.