mutex-design.txt 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
  1. Generic Mutex Subsystem
  2. started by Ingo Molnar <mingo@redhat.com>
  3. "Why on earth do we need a new mutex subsystem, and what's wrong
  4. with semaphores?"
  5. firstly, there's nothing wrong with semaphores. But if the simpler
  6. mutex semantics are sufficient for your code, then there are a couple
  7. of advantages of mutexes:
  8. - 'struct mutex' is smaller on most architectures: .e.g on x86,
  9. 'struct semaphore' is 20 bytes, 'struct mutex' is 16 bytes.
  10. A smaller structure size means less RAM footprint, and better
  11. CPU-cache utilization.
  12. - tighter code. On x86 i get the following .text sizes when
  13. switching all mutex-alike semaphores in the kernel to the mutex
  14. subsystem:
  15. text data bss dec hex filename
  16. 3280380 868188 396860 4545428 455b94 vmlinux-semaphore
  17. 3255329 865296 396732 4517357 44eded vmlinux-mutex
  18. that's 25051 bytes of code saved, or a 0.76% win - off the hottest
  19. codepaths of the kernel. (The .data savings are 2892 bytes, or 0.33%)
  20. Smaller code means better icache footprint, which is one of the
  21. major optimization goals in the Linux kernel currently.
  22. - the mutex subsystem is slightly faster and has better scalability for
  23. contended workloads. On an 8-way x86 system, running a mutex-based
  24. kernel and testing creat+unlink+close (of separate, per-task files)
  25. in /tmp with 16 parallel tasks, the average number of ops/sec is:
  26. Semaphores: Mutexes:
  27. $ ./test-mutex V 16 10 $ ./test-mutex V 16 10
  28. 8 CPUs, running 16 tasks. 8 CPUs, running 16 tasks.
  29. checking VFS performance. checking VFS performance.
  30. avg loops/sec: 34713 avg loops/sec: 84153
  31. CPU utilization: 63% CPU utilization: 22%
  32. i.e. in this workload, the mutex based kernel was 2.4 times faster
  33. than the semaphore based kernel, _and_ it also had 2.8 times less CPU
  34. utilization. (In terms of 'ops per CPU cycle', the semaphore kernel
  35. performed 551 ops/sec per 1% of CPU time used, while the mutex kernel
  36. performed 3825 ops/sec per 1% of CPU time used - it was 6.9 times
  37. more efficient.)
  38. the scalability difference is visible even on a 2-way P4 HT box:
  39. Semaphores: Mutexes:
  40. $ ./test-mutex V 16 10 $ ./test-mutex V 16 10
  41. 4 CPUs, running 16 tasks. 8 CPUs, running 16 tasks.
  42. checking VFS performance. checking VFS performance.
  43. avg loops/sec: 127659 avg loops/sec: 181082
  44. CPU utilization: 100% CPU utilization: 34%
  45. (the straight performance advantage of mutexes is 41%, the per-cycle
  46. efficiency of mutexes is 4.1 times better.)
  47. - there are no fastpath tradeoffs, the mutex fastpath is just as tight
  48. as the semaphore fastpath. On x86, the locking fastpath is 2
  49. instructions:
  50. c0377ccb <mutex_lock>:
  51. c0377ccb: f0 ff 08 lock decl (%eax)
  52. c0377cce: 78 0e js c0377cde <.text.lock.mutex>
  53. c0377cd0: c3 ret
  54. the unlocking fastpath is equally tight:
  55. c0377cd1 <mutex_unlock>:
  56. c0377cd1: f0 ff 00 lock incl (%eax)
  57. c0377cd4: 7e 0f jle c0377ce5 <.text.lock.mutex+0x7>
  58. c0377cd6: c3 ret
  59. - 'struct mutex' semantics are well-defined and are enforced if
  60. CONFIG_DEBUG_MUTEXES is turned on. Semaphores on the other hand have
  61. virtually no debugging code or instrumentation. The mutex subsystem
  62. checks and enforces the following rules:
  63. * - only one task can hold the mutex at a time
  64. * - only the owner can unlock the mutex
  65. * - multiple unlocks are not permitted
  66. * - recursive locking is not permitted
  67. * - a mutex object must be initialized via the API
  68. * - a mutex object must not be initialized via memset or copying
  69. * - task may not exit with mutex held
  70. * - memory areas where held locks reside must not be freed
  71. * - held mutexes must not be reinitialized
  72. * - mutexes may not be used in irq contexts
  73. furthermore, there are also convenience features in the debugging
  74. code:
  75. * - uses symbolic names of mutexes, whenever they are printed in debug output
  76. * - point-of-acquire tracking, symbolic lookup of function names
  77. * - list of all locks held in the system, printout of them
  78. * - owner tracking
  79. * - detects self-recursing locks and prints out all relevant info
  80. * - detects multi-task circular deadlocks and prints out all affected
  81. * locks and tasks (and only those tasks)
  82. Disadvantages
  83. -------------
  84. The stricter mutex API means you cannot use mutexes the same way you
  85. can use semaphores: e.g. they cannot be used from an interrupt context,
  86. nor can they be unlocked from a different context that which acquired
  87. it. [ I'm not aware of any other (e.g. performance) disadvantages from
  88. using mutexes at the moment, please let me know if you find any. ]
  89. Implementation of mutexes
  90. -------------------------
  91. 'struct mutex' is the new mutex type, defined in include/linux/mutex.h
  92. and implemented in kernel/mutex.c. It is a counter-based mutex with a
  93. spinlock and a wait-list. The counter has 3 states: 1 for "unlocked",
  94. 0 for "locked" and negative numbers (usually -1) for "locked, potential
  95. waiters queued".
  96. the APIs of 'struct mutex' have been streamlined:
  97. DEFINE_MUTEX(name);
  98. mutex_init(mutex);
  99. void mutex_lock(struct mutex *lock);
  100. int mutex_lock_interruptible(struct mutex *lock);
  101. int mutex_trylock(struct mutex *lock);
  102. void mutex_unlock(struct mutex *lock);
  103. int mutex_is_locked(struct mutex *lock);