Subversion Repositories or1k_soc_on_altera_embedded_dev_kit

Generic Mutex Subsystem

started by Ingo Molnar 

  "Why on earth do we need a new mutex subsystem, and what's wrong

   with semaphores?"

firstly, there's nothing wrong with semaphores. But if the simpler

mutex semantics are sufficient for your code, then there are a couple

of advantages of mutexes:

 - 'struct mutex' is smaller on most architectures: .e.g on x86,

   'struct semaphore' is 20 bytes, 'struct mutex' is 16 bytes.

   A smaller structure size means less RAM footprint, and better

   CPU-cache utilization.

 - tighter code. On x86 i get the following .text sizes when

   switching all mutex-alike semaphores in the kernel to the mutex

   subsystem:

        text    data     bss     dec     hex filename

     3280380  868188  396860 4545428  455b94 vmlinux-semaphore

     3255329  865296  396732 4517357  44eded vmlinux-mutex

   that's 25051 bytes of code saved, or a 0.76% win - off the hottest

   codepaths of the kernel. (The .data savings are 2892 bytes, or 0.33%)

   Smaller code means better icache footprint, which is one of the

   major optimization goals in the Linux kernel currently.

 - the mutex subsystem is slightly faster and has better scalability for

   contended workloads. On an 8-way x86 system, running a mutex-based

   kernel and testing creat+unlink+close (of separate, per-task files)

   in /tmp with 16 parallel tasks, the average number of ops/sec is:

    Semaphores:                        Mutexes:

    $ ./test-mutex V 16 10             $ ./test-mutex V 16 10

    8 CPUs, running 16 tasks.          8 CPUs, running 16 tasks.

    checking VFS performance.          checking VFS performance.

    avg loops/sec:      34713          avg loops/sec:      84153

    CPU utilization:    63%            CPU utilization:    22%

   i.e. in this workload, the mutex based kernel was 2.4 times faster

   than the semaphore based kernel, _and_ it also had 2.8 times less CPU

   utilization. (In terms of 'ops per CPU cycle', the semaphore kernel

   performed 551 ops/sec per 1% of CPU time used, while the mutex kernel

   performed 3825 ops/sec per 1% of CPU time used - it was 6.9 times

   more efficient.)

   the scalability difference is visible even on a 2-way P4 HT box:

    Semaphores:                        Mutexes:

    $ ./test-mutex V 16 10             $ ./test-mutex V 16 10

    4 CPUs, running 16 tasks.          8 CPUs, running 16 tasks.

    checking VFS performance.          checking VFS performance.

    avg loops/sec:      127659         avg loops/sec:      181082

    CPU utilization:    100%           CPU utilization:    34%

   (the straight performance advantage of mutexes is 41%, the per-cycle

    efficiency of mutexes is 4.1 times better.)

 - there are no fastpath tradeoffs, the mutex fastpath is just as tight

   as the semaphore fastpath. On x86, the locking fastpath is 2

   instructions:

    c0377ccb :

    c0377ccb:       f0 ff 08                lock decl (%eax)

    c0377cce:       78 0e                   js     c0377cde <.text.lock.mutex>

    c0377cd0:       c3                      ret

   the unlocking fastpath is equally tight:

    c0377cd1 :

    c0377cd1:       f0 ff 00                lock incl (%eax)

    c0377cd4:       7e 0f                   jle    c0377ce5 <.text.lock.mutex+0x7>

    c0377cd6:       c3                      ret

 - 'struct mutex' semantics are well-defined and are enforced if

   CONFIG_DEBUG_MUTEXES is turned on. Semaphores on the other hand have

   virtually no debugging code or instrumentation. The mutex subsystem

   checks and enforces the following rules:

   * - only one task can hold the mutex at a time

   * - only the owner can unlock the mutex

   * - multiple unlocks are not permitted

   * - recursive locking is not permitted

   * - a mutex object must be initialized via the API

   * - a mutex object must not be initialized via memset or copying

   * - task may not exit with mutex held

   * - memory areas where held locks reside must not be freed

   * - held mutexes must not be reinitialized

   * - mutexes may not be used in hardware or software interrupt

   *   contexts such as tasklets and timers

   furthermore, there are also convenience features in the debugging

   code:

   * - uses symbolic names of mutexes, whenever they are printed in debug output

   * - point-of-acquire tracking, symbolic lookup of function names

   * - list of all locks held in the system, printout of them

   * - owner tracking

   * - detects self-recursing locks and prints out all relevant info

   * - detects multi-task circular deadlocks and prints out all affected

   *   locks and tasks (and only those tasks)

Disadvantages

-------------

The stricter mutex API means you cannot use mutexes the same way you

can use semaphores: e.g. they cannot be used from an interrupt context,

nor can they be unlocked from a different context that which acquired

it. [ I'm not aware of any other (e.g. performance) disadvantages from

using mutexes at the moment, please let me know if you find any. ]

Implementation of mutexes

-------------------------

'struct mutex' is the new mutex type, defined in include/linux/mutex.h

and implemented in kernel/mutex.c. It is a counter-based mutex with a

spinlock and a wait-list. The counter has 3 states: 1 for "unlocked",

waiters queued".

the APIs of 'struct mutex' have been streamlined:

 DEFINE_MUTEX(name);

 mutex_init(mutex);

 void mutex_lock(struct mutex *lock);

 int  mutex_lock_interruptible(struct mutex *lock);

 int  mutex_trylock(struct mutex *lock);

 void mutex_unlock(struct mutex *lock);

 int  mutex_is_locked(struct mutex *lock);

 void mutex_lock_nested(struct mutex *lock, unsigned int subclass);

 int  mutex_lock_interruptible_nested(struct mutex *lock,

                                      unsigned int subclass);