Generic mutex subsystem 내부 구조

Kernel mutex의 의미

Ingo Molnar가 시작하고 Davidlohr Bueso가 갱신한 문서다. Linux kernel에서 mutex는 학술 문헌의 일반적인 mutual exclusion 개념만을 뜻하는 것이 아니라 shared-memory system의 실행을 직렬화하는 특정 locking primitive를 뜻한다.

Mutex는 binary semaphore와 비슷하게 동작하는 sleeping lock이다. 2006년에 binary semaphore의 대안으로 도입되었으며 더 단순한 interface와 당시 기준 더 작은 code 같은 장점이 있었다. 배경은 https://lwn.net/Articles/164802/ 에서 확인할 수 있다.

struct mutex와 owner field

Mutex는 include/linux/mutex.h에 정의된 struct mutex로 표현되고 kernel/locking/mutex.c에서 구현된다. Lifetime 동안 lock state를 추적하기 위해 atomic variable인 ->owner를 사용한다.

owner에는 현재 lock owner의 struct task_struct *가 들어 있으며 owner가 없으면 NULL이다. task_struct pointer는 최소 L1_CACHE_BYTES에 맞춰 align되므로 아래쪽 3 bit는 waiter list가 비어 있지 않은지 같은 추가 state를 저장하는 데 사용한다.

기본 구조에는 wait queue와 그 queue 접근을 직렬화하는 spinlock도 들어 있다. CONFIG_MUTEX_SPIN_ON_OWNER=y system에는 optimistic spinner를 queueing하는 MCS lock인 ->osq가 추가된다.

Acquire path 1: fast path

Fast path는 cmpxchg()로 owner를 current task로 atomic하게 바꿔 lock 획득을 시도한다. 경쟁이 없는 경우에만 성공한다. cmpxchg()는 owner word를 0UL과 비교하므로 아래쪽 state bit 세 개도 모두 0이어야 한다. 경쟁 상태라면 다음 path로 넘어간다.

Acquire path 2: optimistic spinning

Mid path는 optimistic spinning이라고도 한다. Lock owner가 현재 실행 중이고 need_resched가 가리키는 더 높은 priority의 runnable task가 없다면 lock 획득을 기다리며 spin한다. Owner가 실행 중이라면 곧 lock을 해제할 가능성이 높다는 판단에 기반한다.

Mutex spinner는 MCS lock queue에 들어가 한 번에 하나의 spinner만 mutex를 두고 경쟁한다. Mellor-Crummey와 Scott이 제안한 MCS lock은 공정하고 각 CPU가 local variable에서 spin하므로 일반 test-and-set spinlock의 비싼 cacheline bouncing을 피한다.

Sleeping lock의 optimistic spinning에 맞춘 MCS-like lock은 reschedule이 필요해진 spinner가 MCS queue에서 빠져나갈 수 있다는 추가 성질을 갖는다. Reschedule이 필요한 spinner가 owner를 계속 기다린 뒤 MCS lock을 얻자마자 slow path로 가는 낭비를 줄인다.

Acquire path 3: sleep

마지막 수단인 slow path에서도 lock을 얻지 못하면 task를 wait queue에 넣고 unlock path가 깨울 때까지 sleep한다. 보통 TASK_UNINTERRUPTIBLE 상태로 block된다.

형식상 kernel mutex는 sleepable lock이지만 optimistic spinning 때문에 실제로는 hybrid lock에 가깝다. 즉시 sleep해 task를 전환하는 대신 짧은 시간 busy-wait하면 여러 workload에서 성능이 크게 좋아진다. rw-semaphore도 같은 기법을 사용한다.

Mutex subsystem이 강제하는 규칙

• 한 번에 하나의 task만 mutex를 보유할 수 있다.
• Owner만 mutex를 unlock할 수 있다.
• 여러 번 unlock할 수 없다.
• Recursive locking과 recursive unlocking은 허용하지 않는다.
• Mutex는 API를 통해서만 초기화한다.
• Task는 mutex를 보유한 채 exit해서는 안 된다.
• 보유 중인 lock이 놓인 memory 영역을 free해서는 안 된다.
• 보유 중인 mutex를 다시 초기화해서는 안 된다.
• Tasklet, timer 같은 hardware 또는 software interrupt context에서 mutex를 사용할 수 없다.

CONFIG_DEBUG_MUTEXES를 enable하면 이 semantic을 완전히 검사하고 강제한다. Debug code는 출력에 mutex symbol name을 사용하고, acquire 지점과 function symbol을 추적하며, system의 모든 held lock을 나열하고 owner를 추적한다. Self-recursion과 여러 task가 만드는 circular deadlock도 찾아 관련 lock과 task만 출력한다.

mutex_unlock()과 object lifetime

Mutex와 rwsem 같은 대부분의 sleeping lock은 자신이 차지하는 memory에 대한 암묵적 reference를 제공하지 않는다. 즉 mutex_unlock()과 함께 해제되는 object reference가 자동으로 생기지 않는다.

이는 spin_unlock()이나 completion_done()이 돌아간 뒤 lock 구현이 해당 memory를 더 이상 만지지 않는다고 보장할 수 있는 것과 다르다.

mutex_unlock()은 내부적으로 lock을 release한 뒤에도 mutex structure에 접근할 수 있다. 따라서 다른 context가 mutex를 획득했다는 사실만으로 이전 mutex_unlock() context가 structure 사용을 끝냈다고 가정해서는 안 된다.

Mutex 사용자는 release operation이 진행 중인 동안 mutex가 파괴되지 않도록 보장해야 한다. 구체적으로 mutex_unlock() caller는 function이 반환할 때까지 mutex object가 살아 있도록 해야 한다.

Mutex API

/* static definition */
DEFINE_MUTEX(name);

/* dynamic initialization */
mutex_init(mutex);

/* uninterruptible acquisition */
void mutex_lock(struct mutex *lock);
void mutex_lock_nested(struct mutex *lock, unsigned int subclass);
int  mutex_trylock(struct mutex *lock);

/* interruptible acquisition */
int mutex_lock_interruptible_nested(struct mutex *lock,
                                    unsigned int subclass);
int mutex_lock_interruptible(struct mutex *lock);

/* acquire when decrement reaches zero */
int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock);

/* release and state query */
void mutex_unlock(struct mutex *lock);
int mutex_is_locked(struct mutex *lock);

크기와 사용 기준

초기 설계 목적과 달리 struct mutex는 kernel에서 큰 lock 구조체에 속한다. 예를 들어 x86-64에서 struct mutex는 32 byte, struct semaphore는 24 byte, rw_semaphore는 40 byte다. 구조체가 클수록 CPU cache와 memory footprint를 더 많이 사용한다.

엄격한 mutex semantic이 사용 목적에 맞지 않거나 critical region의 성질 때문에 lock을 공유할 수 없는 경우가 아니라면 다른 locking primitive보다 mutex를 우선해서 사용한다.