Glibc NPTL library pthread_ mutex_ Lock and pthread_ mutex_ Analysis of unlock

  One 、futex brief introduction

    futex The full name is fast user-space locking, That is, fast user space lock , stay linux Next use C Language to write multithreaded programs , It is often used where thread synchronization is required pthread_mutex_lock() Function to lock the critical region , If locking fails, the thread will hang , This is mutex . however pthread_mutex_lock It is not an immediate system call , Instead, it is performed in the user mode first CAS operation , Determine whether other threads have acquired the lock , If the lock is acquired by another thread , Then make system calls sys_futex(), Suspends the current thread .futex Can be used in multithreaded programs , It can also be used in multiprocess programs . Mutex is a 32 The value of a .

   1. In multithreaded programs ： Mutex is usually a global variable , All threads share this variable , If the value is 0, Description is not obtained by other threads , At this point, the lock can be obtained successfully , Then set the mutex to 1. If the value is 1, Description obtained by other threads , At this point, the current thread needs to fall into the kernel state and hang .

   2. In multiprocessing ： Mutexes are generally expressed in shared memory , Use mmap perhaps shmat System call creation , So the virtual addresses of mutexes may be different , But the physical address is the same . The strategy for obtaining locks is the same as above .

Two 、pthread_mutex_lock Lock process

    In a multithreaded program, first define pthread_mutex_t Lock variables of type , And then call pthread_mutex_lock(&lock) Lock , call pthread_mutex_unlock(&lock) Unlock ,pthread_mutex_t Variables have four properties ：

1.PTHREAD_MUTEX_TIMED_NP, This is the default , It's a common lock . Let's start with CAS, If it fails, it will fall into kernel state and suspend the thread 2.PTHREAD_MUTEX_RECURSIVE_NP, Reentrant lock , Allow the same thread to successfully acquire the same lock multiple times , And through many times unlock Unlock . If it's a different thread request , When the locking thread is unlocked, it will compete again . 3. PTHREAD_MUTEX_ERRORCHECK_NP, Error detection lock , If the same thread requests the same lock , Then return to EDEADLK, Otherwise and PTHREAD_MUTEX_TIMED_NP The type of action is the same . This ensures that when multiple locking is not allowed, there will be no deadlock in the simplest case . 4.PTHREAD_MUTEX_ADAPTIVE_NP, Adaptive lock , This lock is first spin acquired in a multi-core processor , If the number of spins exceeds the configured maximum number , Will also fall into the kernel state and hang .

You can call pthread_mutex_init Function pair mutex To initialize . The default property is PTHREAD_MUTEX_TIMED_NP. Look at the source code ：

//pthread_mutex_t  Mutex properties 
//PTHREAD_MUTEX_TIMED_NP, This is the default , It's a common lock . Let's start with CAS, If it fails, it will fall into kernel state and suspend the thread 
//PTHREAD_MUTEX_RECURSIVE_NP, Reentrant lock , Allow the same thread to successfully acquire the same lock multiple times , And through many times unlock Unlock . If it's a different thread request , When the locking thread is unlocked, it will compete again .
// PTHREAD_MUTEX_ERRORCHECK_NP, Error detection lock , If the same thread requests the same lock , Then return to EDEADLK, Otherwise and PTHREAD_MUTEX_TIMED_NP The type of action is the same . This ensures that when multiple locking is not allowed, there will be no deadlock in the simplest case .
//PTHREAD_MUTEX_ADAPTIVE_NP, Adaptive lock , This lock is first spin acquired in a multi-core processor , If the number of spins exceeds the configured maximum number , Will also fall into the kernel state and hang .
int
__pthread_mutex_lock (pthread_mutex_t *mutex)
{
  assert (sizeof (mutex->__size) >= sizeof (mutex->__data));
  // Get mutex type 
  unsigned int type = PTHREAD_MUTEX_TYPE_ELISION (mutex);

  LIBC_PROBE (mutex_entry, 1, mutex);

  if (__builtin_expect (type & ~(PTHREAD_MUTEX_KIND_MASK_NP
				 | PTHREAD_MUTEX_ELISION_FLAGS_NP), 0))
    return __pthread_mutex_lock_full (mutex);
  // If it is the default attribute 
  if (__glibc_likely (type == PTHREAD_MUTEX_TIMED_NP))
    {
      FORCE_ELISION (mutex, goto elision);
    simple:
      /* Normal mutex.  */
      //LLL_MUTEX_LOCK Is a macro 
      LLL_MUTEX_LOCK (mutex);
      assert (mutex->__data.__owner == 0);
    }
  // If you have a reentrant property , That is, recursive lock 
  else if (__builtin_expect (PTHREAD_MUTEX_TYPE (mutex)
			     == PTHREAD_MUTEX_RECURSIVE_NP, 1))
    {
      /* Recursive mutex.  */
      // Get the current thread id
      pid_t id = THREAD_GETMEM (THREAD_SELF, tid);

      // Determine whether the current thread already holds the lock , That is, mutually exclusive __owner Property is the thread that holds it id
      if (mutex->__data.__owner == id)
	{
	  /* Just bump the counter.  */
	  // If the number of recursive lock acquisition overflows , You make a mistake 
	  if (__glibc_unlikely (mutex->__data.__count + 1 == 0))
	    /* Overflow of the counter.  */
	    return EAGAIN;
      // The number of times a lock is recursively acquired plus one 
	  ++mutex->__data.__count;
      // Returns lock successfully 
	  return 0;
	}
      // If the lock is acquired for the first time, use LLL_MUTEX_LOCK Macro acquire lock 
      /* We have to get the mutex.  */
      LLL_MUTEX_LOCK (mutex);

      assert (mutex->__data.__owner == 0);
      // The number of times the lock is held is initialized to 1
      mutex->__data.__count = 1;
    }
   // If it is PTHREAD_MUTEX_ADAPTIVE_NP Type of lock 
  else if (__builtin_expect (PTHREAD_MUTEX_TYPE (mutex)
			  == PTHREAD_MUTEX_ADAPTIVE_NP, 1))
    {
    // Not smp framework , Direct use LLL_MUTEX_LOCK Macro acquire lock 
      if (! __is_smp)
	goto simple;
    // If it is smp The architecture uses LLL_MUTEX_TRYLOCK Macro acquire lock 
      if (LLL_MUTEX_TRYLOCK (mutex) != 0)
	{
	  // If it doesn't work 
	  int cnt = 0;
	  // Get the maximum number of spins 
	  int max_cnt = MIN (MAX_ADAPTIVE_COUNT,
			     mutex->__data.__spins * 2 + 10);
	  // Spin lock 
	  do
	    {
	    // If the number of spins exceeds the maximum number 
	      if (cnt++ >= max_cnt)
		{
		  // Then use LLL_MUTEX_LOCK Get the lock 
		  LLL_MUTEX_LOCK (mutex);
		  break;
		}
	      atomic_spin_nop ();
	    }
	  while (LLL_MUTEX_TRYLOCK (mutex) != 0);
     
	  mutex->__data.__spins += (cnt - mutex->__data.__spins) / 8;
	}
      assert (mutex->__data.__owner == 0);
    }
  else
    {
      // This branch is PTHREAD_MUTEX_ERRORCHECK_NP Type of lock 
      // Get thread id
      pid_t id = THREAD_GETMEM (THREAD_SELF, tid);
      assert (PTHREAD_MUTEX_TYPE (mutex) == PTHREAD_MUTEX_ERRORCHECK_NP);
      /* Check whether we already hold the mutex.  */
      // If the current thread id And hold mutex Thread of lock id equally , That is, the same thread repeatedly acquires locks , It will return an error 
      if (__glibc_unlikely (mutex->__data.__owner == id))
	return EDEADLK;
      // If it is not the same thread, follow the general LLL_MUTEX_LOCK To get the lock 
      goto simple;
    }

  pid_t id = THREAD_GETMEM (THREAD_SELF, tid);

  /* Record the ownership.  */
  // Record the thread that acquires the lock id
  mutex->__data.__owner = id;
#ifndef NO_INCR
  ++mutex->__data.__nusers;
#endif

  LIBC_PROBE (mutex_acquired, 1, mutex);

  return 0;
}

Copy

The specific process of locking is LLL_MUTEX_LOCK Hongli

# define LLL_MUTEX_LOCK(mutex) \
  lll_lock ((mutex)->__data.__lock, PTHREAD_MUTEX_PSHARED (mutex))
# define LLL_MUTEX_TRYLOCK(mutex) \
  lll_trylock ((mutex)->__data.__lock)
/* 
 * CAS The core macro of the operation ,cas Operational judgment (mutex)->__data.__lock Is the value of 0, If 0, Is set to 1,ZF=1
 * 1. Determine whether you are in a multithreaded environment 
 * 2. If it is not a multi-threaded environment, call directly cmpxchgl Order to proceed cas operation , If it is multithreaded, it needs to be in cmpxchgl Before the order 
 *  add lock Instructions 
 * 3. If cas Success jumps to the label 18, If cas If it fails, call __lll_lock_wait Subroutines 
 */
# define __lll_lock_asm_start "cmpl $0, %%gs:%P6\n\t"			      \
			      "je 0f\n\t"				      \
			      "lock\n"					      \
			      "0:\tcmpxchgl %1, %2\n\t"
//LLL_PRIVATE by 0, So I won't take the first branch , Take the second branch 
#define lll_lock(futex, private) \
  (void)								      \
    ({ int ignore1, ignore2;						      \
       if (__builtin_constant_p (private) && (private) == LLL_PRIVATE)	      \
	 __asm __volatile (__lll_lock_asm_start				      \
			   "jz 18f\n\t"				      \
			   "1:\tleal %2, %%ecx\n"			      \
			   "2:\tcall __lll_lock_wait_private\n" 	      \
			   "18:"					      \
			   : "=a" (ignore1), "=c" (ignore2), "=m" (futex)     \
			   : "0" (0), "1" (1), "m" (futex),		      \
			     "i" (MULTIPLE_THREADS_OFFSET)		      \
			   : "memory");					      \
       else								      \
	 {								      \
	   int ignore3;							      \
	   __asm __volatile (__lll_lock_asm_start			      \
			     "jz 18f\n\t"			 	      \
			     "1:\tleal %2, %%edx\n"			      \
			     "0:\tmovl %8, %%ecx\n"			      \
			     "2:\tcall __lll_lock_wait\n"		      \
			     "18:"					      \
			     : "=a" (ignore1), "=c" (ignore2),		      \
			       "=m" (futex), "=&d" (ignore3) 		      \
			     : "1" (1), "m" (futex),			      \
			       "i" (MULTIPLE_THREADS_OFFSET), "0" (0),	      \
			       "g" ((int) (private))			      \
			     : "memory");				      \
	 }								      \
    })
// The subroutine starts with sys_futex system call 
// From the inline assembly code above, we can see ,edx = futex,ecx = 0
// System call parameter transfer rules , No more than 6 Function call with arguments , The left to right parameters are used separately ebx,	ecx
//edx,esi,edi,ebp Express 		
__lll_lock_wait:
	pushl	%edx
	pushl	%ebx
	pushl	%esi
	//ebx yes sys_futex The first parameter of the system call is futex
	movl	%edx, %ebx
	//edx It's the third parameter   The value is 2
	movl	$2, %edx
	xorl	%esi, %esi	/* No timeout.  */
	//ecx Is the second parameter, that is  FUTEX_WAIT sign 
	LOAD_FUTEX_WAIT (%ecx)
    // here eax = 0,edx = 2, So skip to the label 2
	cmpl	%edx, %eax	/* NB:	 %edx == 2 */
	jne 2f

1:	movl	$SYS_futex, %eax
	ENTER_KERNEL
// take edx Assign a value to eax  here eax = 2
2:	movl	%edx, %eax
// Mutex and eax The value of , The value of the mutex is 2,eax = 1 or 0
	xchgl	%eax, (%ebx)	/* NB:	 lock is implied */
//eax and eax Conduct and operate , It's not equal to 0 Then jump to 1, Otherwise, the stack will be released 
// be equal to 0 It indicates that other threads have released the lock , At this time, you do not need to sleep but to acquire the lock again 
	testl	%eax, %eax
	jnz	1b

	popl	%esi
	popl	%ebx
	popl	%edx
	ret

Copy

pthread_mutex_lock The core process of obtaining locks is as follows ：

1. Perform corresponding operations according to the lock type , If it is an ordinary lock, proceed to CAS operation , If CAS If you fail, go ahead sys_futex The system call suspends the current thread

2. If it is a recursive lock , Then judge the current thread id Whether or not the thread holding the lock id Whether it is equal or not , If the equality statement is reentrant , Increase the number of locks by one . Otherwise to CAS Operation acquire lock , If CAS If you fail, go ahead sys_futex The system call suspends the current thread .

3. If it is an adapter lock , Spin operation will be performed when acquiring the lock , When the number of spins exceeds the maximum , Is to sys_futex The system call suspends the current thread .

4. If it is an error detection lock , Then judge whether the lock has been acquired by the current thread , If so, an error is returned , Otherwise to CAS Operation acquire lock , The error detection lock can avoid the deadlock of the common lock .

Be careful ： After a lock acquisition failure , Will set the mutex to 2, Then make a system call to suspend , This is to enable the unlocking thread to discover that other threads waiting for mutexes need to be awakened

3、 ... and 、pthread_mutex_unlock Unlock process

int
internal_function attribute_hidden
__pthread_mutex_unlock_usercnt (pthread_mutex_t *mutex, int decr)
{
	// Get lock type 
  int type = PTHREAD_MUTEX_TYPE_ELISION (mutex);
  // If it's a normal type 
  if (__builtin_expect (type, PTHREAD_MUTEX_TIMED_NP)
      == PTHREAD_MUTEX_TIMED_NP)
    {
      /* Always reset the owner field.  */
    normal:
      mutex->__data.__owner = 0;
      if (decr)
	/* One less user.  */
	--mutex->__data.__nusers;

      /* Use lll_unlock Macro to unlock   */
      lll_unlock (mutex->__data.__lock, PTHREAD_MUTEX_PSHARED (mutex));

      LIBC_PROBE (mutex_release, 1, mutex);

      return 0;
    }
  else if (__glibc_likely (type == PTHREAD_MUTEX_TIMED_ELISION_NP))
    {
      /* Don't reset the owner/users fields for elision.  */
      return lll_unlock_elision (mutex->__data.__lock, mutex->__data.__elision,
				      PTHREAD_MUTEX_PSHARED (mutex));
    }
  else if (__builtin_expect (PTHREAD_MUTEX_TYPE (mutex)
			      == PTHREAD_MUTEX_RECURSIVE_NP, 1))
    {
      /* Recursive mutex.  */
      if (mutex->__data.__owner != THREAD_GETMEM (THREAD_SELF, tid))
	return EPERM;
      
      if (--mutex->__data.__count != 0)
	/* We still hold the mutex.  */
	return 0;
      goto normal;
    }
  else if (__builtin_expect (PTHREAD_MUTEX_TYPE (mutex)
			      == PTHREAD_MUTEX_ADAPTIVE_NP, 1))
    goto normal;
  else
    {
      /* Error checking mutex.  */
      assert (type == PTHREAD_MUTEX_ERRORCHECK_NP);
      if (mutex->__data.__owner != THREAD_GETMEM (THREAD_SELF, tid)
	  || ! lll_islocked (mutex->__data.__lock))
	return EPERM;
      goto normal;
    }
}

Copy

The unlocking process and locking process correspond to each other , If it is an ordinary lock, it can be unlocked directly . If it is a recursive lock , Then the number of times the lock is acquired is reduced by one , Reduced to 0 Unlock . It mainly depends on lll_unlock macro .

//1. take ebx Set as the address of the mutex in user space ,sys_futex The first parameter of 
//2. Set the mutex to 0, Indicates the lock is released 
//3.ecx It's the operands FUTEX_WAKE, That is to say sys_futex Of op Parameters 
//4. take edx Set to 1  Indicates that only one thread will be awakened ,sys_futex The third parameter of , And then start sys_futex system call 
__lll_unlock_wake:
	pushl	%ebx
	pushl	%ecx
	pushl	%edx

	movl	%eax, %ebx
	movl	$0, (%eax)
	LOAD_FUTEX_WAKE (%ecx)
	movl	$1, %edx	/* Wake one thread.  */
	movl	$SYS_futex, %eax
	ENTER_KERNEL

	popl	%edx
	popl	%ecx
	popl	%ebx
	ret

Copy

Four 、sys_futex System call parsing

  sys_futex Is the core system call for thread suspension and wakeup , Located in the kernel source code kernel/futex.c Under the document , Let's look at this function :

/*
 *pthread_mutex_lock,pthread_cond_wait,pthread_cond_signal This function is called . If in user mode CAS Failure ,
 * Then make a system call to suspend the operation 
 *uaddr Indicates the address of the mutex in user space ,op Indicates the type of operation ,utime Indicates the suspend time 
 */

asmlinkage long sys_futex(u32 __user *uaddr, int op, u32 val,
			  struct timespec __user *utime, u32 __user *uaddr2,
			  u32 val3)
{
	struct timespec t;
	// initialization timeout
	unsigned long timeout = MAX_SCHEDULE_TIMEOUT;
	u32 val2 = 0;
    // If the sleep time is set and the operation type is FUTEX_WAIT
	if (utime && (op == FUTEX_WAIT || op == FUTEX_LOCK_PI)) {
		// Copy the sleep time from user space to the variable t
		if (copy_from_user(&t, utime, sizeof(t)) != 0)
			return -EFAULT;
		// Verify sleep time 
		if (!timespec_valid(&t))
			return -EINVAL;
		// If the operation type is FUTEX_WAIT, The sleep time is converted to the system clock 
		if (op == FUTEX_WAIT)
			timeout = timespec_to_jiffies(&t) + 1;
		else {
			timeout = t.tv_sec;
			val2 = t.tv_nsec;
		}
	}
	/*
	 * requeue parameter in 'utime' if op == FUTEX_REQUEUE.
	 */
	if (op == FUTEX_REQUEUE || op == FUTEX_CMP_REQUEUE)
		val2 = (u32) (unsigned long) utime;
    // call do_futex
	return do_futex(uaddr, op, val, timeout, uaddr2, val2, val3);
}

Copy

, This function mainly converts the sleep time to the kernel system clock , In the end by the do_futex Perform specific operations .

// Select the specific function according to the operation type , For example, if locking fails, the system will call futex_wait Suspends the current thread 
long do_futex(u32 __user *uaddr, int op, u32 val, unsigned long timeout,
		u32 __user *uaddr2, u32 val2, u32 val3)
{
	int ret;

	switch (op) {
	case FUTEX_WAIT:
		ret = futex_wait(uaddr, val, timeout);
		break;
	case FUTEX_WAKE:
		ret = futex_wake(uaddr, val);
		break;
	case FUTEX_FD:
		/* non-zero val means F_SETOWN(getpid()) & F_SETSIG(val) */
		ret = futex_fd(uaddr, val);
		break;
	case FUTEX_REQUEUE:
		ret = futex_requeue(uaddr, uaddr2, val, val2, NULL);
		break;
	case FUTEX_CMP_REQUEUE:
		ret = futex_requeue(uaddr, uaddr2, val, val2, &val3);
		break;
	case FUTEX_WAKE_OP:
		ret = futex_wake_op(uaddr, uaddr2, val, val2, val3);
		break;
	case FUTEX_LOCK_PI:
		ret = futex_lock_pi(uaddr, val, timeout, val2, 0);
		break;
	case FUTEX_UNLOCK_PI:
		ret = futex_unlock_pi(uaddr);
		break;
	case FUTEX_TRYLOCK_PI:
		ret = futex_lock_pi(uaddr, 0, timeout, val2, 1);
		break;
	default:
		ret = -ENOSYS;
	}
	return ret;
}

Copy

do_futex The function mainly consists of op Variable to determine which function to call , It mainly includes sleep and wake-up , It mainly depends on futex_wait and futex_wake, because pthread_mutex_lock The operand passed in is FUTEX_WAIT.

//uaddr  Mutex user space address ,val = 2,time It's sleep time 
static int futex_wait(u32 __user *uaddr, u32 val, unsigned long time)
{
	// Get the current process 
	struct task_struct *curr = current;
	// Create a waiting queue 
	DECLARE_WAITQUEUE(wait, curr);
	// Hash array subscript address 
	struct futex_hash_bucket *hb;
	// Hash element 
	struct futex_q q;
	u32 uval;
	int ret;

	q.pi_state = NULL;
 retry:
	down_read(&curr->mm->mmap_sem);
    // initialization futex_q Of key member , Mainly for key Of address,mm,offset assignment ,address It's a mutex 
    // At the address of user space 4KB Alignment of values ,mm Is the of the current process mm,offset They are mutexes and 4KB The offset of the alignment value 
	ret = get_futex_key(uaddr, &q.key);
	if (unlikely(ret != 0))
		goto out_release_sem;
    // Get the index address of the hash array 
	hb = queue_lock(&q, -1, NULL);
	// Get the value of the mutex in user space atomically 
	ret = get_futex_value_locked(&uval, uaddr);
    // If the fetch fails 
	if (unlikely(ret)) {
		queue_unlock(&q, hb);

		/*
		 * If we would have faulted, release mmap_sem, fault it in and
		 * start all over again.
		 */
		up_read(&curr->mm->mmap_sem);

		ret = get_user(uval, uaddr);

		if (!ret)
			goto retry;
		return ret;
	}
	ret = -EWOULDBLOCK;
	// If the value of the mutex is changed, an error is returned directly 
	if (uval != val)
		goto out_unlock_release_sem;

	/*  If the value of the mutex remains the same , Will q Add hash table   */
	__queue_me(&q, hb);

	/*
	 * Synchronous semaphore 
	 */
	up_read(&curr->mm->mmap_sem);

	/*
	 * There might have been scheduling since the queue_me(), as we
	 * cannot hold a spinlock across the get_user() in case it
	 * faults, and we cannot just set TASK_INTERRUPTIBLE state when
	 * queueing ourselves into the futex hash.  This code thus has to
	 * rely on the futex_wake() code removing us from hash when it
	 * wakes us up.
	 */

	/* add_wait_queue is the barrier after __set_current_state. */
	// Set the current thread to sleep interruptible state 
	__set_current_state(TASK_INTERRUPTIBLE);
	// Join the wait queue 
	add_wait_queue(&q.waiters, &wait);
	/*
	 *  If the waiting queue is not null
	 */
	if (likely(!list_empty(&q.list)))
		// Reschedule 
		time = schedule_timeout(time);
	// Reset the current process to the running state 
	__set_current_state(TASK_RUNNING);

	/*
	 * NOTE: we don't remove ourselves from the waitqueue because
	 * we are the only user of it.
	 */

	/*  Remove from hash table key */
	if (!unqueue_me(&q))
		return 0;
	if (time == 0)
		return -ETIMEDOUT;
	/*
	 * We expect signal_pending(current), but another thread may
	 * have handled it for us already.
	 */
	return -EINTR;

 out_unlock_release_sem:
	queue_unlock(&q, hb);

 out_release_sem:
	up_read(&curr->mm->mmap_sem);
	return ret;
}

Copy

The main process is to add the current process to the waiting queue , Then reschedule other processes to run . A mutex test will be performed before the real sleep , If it is released by another process, the sleep time of the process can be set . There are some important data structures in the function ,struct futex_hash_bucket Is a hash linked list ,struct futex_q Is a hash element ,union futex_key yes key. First, the mutex of the user space will be wrapped as a futex_key, And then futex_key The packing is futex_q Add to hash table . It is mainly for the following wake-up operations to quickly find the sleep process corresponding to the user space mutex .

//futex Hash list 
struct futex_hash_bucket {
       spinlock_t              lock;
       struct list_head       chain;
};
//futex Hash array 
static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
//futext key Consortium , Shared , private , A combination of the two , Since the analysis focuses on thread synchronization, we mainly focus on private 
union futex_key {
	struct {
		unsigned long pgoff;
		struct inode *inode;
		int offset;
	} shared;
	struct {
		unsigned long address;
		struct mm_struct *mm;
		int offset;
	} private;
	struct {
		unsigned long word;
		void *ptr;
		int offset;
	} both;
};

struct futex_q {
	struct list_head list;
	// Waiting queue elements 
	wait_queue_head_t waiters;

	/*  Spin lock when hash table is inserted  */
	spinlock_t *lock_ptr;

	/*  Of the hash element key */
	union futex_key key;

	/* For fd, sigio sent using these: */
	int fd;
	struct file *filp;

	/* Optional priority inheritance state: */
	struct futex_pi_state *pi_state;
	// The process that the hash element points to 
	struct task_struct *task;
};


static inline struct futex_hash_bucket *
queue_lock(struct futex_q *q, int fd, struct file *filp)
{
	struct futex_hash_bucket *hb;

	q->fd = fd;
	q->filp = filp;
    // Initialize wait queue 
	init_waitqueue_head(&q->waiters);
    
	get_key_refs(&q->key);
	// return q->key Hash to array subscript address 
	hb = hash_futex(&q->key);
	q->lock_ptr = &hb->lock;
    // Spin lock 
	spin_lock(&hb->lock);
	return hb;
}
static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
{
	// take q Insert into hash linked list 
	list_add_tail(&q->list, &hb->chain);
	//q The task property of is set to the current process 
	q->task = current;
	// Spin lock unlock 
	spin_unlock(&hb->lock);
}

Copy

Wrap the mutex of user space as a hash element and put it in the hash table , And add the hash element to the waiting queue linked list , And then call schedule_timeout Function calls other processes . Look again schedule_timeout function

fastcall signed long __sched schedule_timeout(signed long timeout)
{
	// Define timer 
	struct timer_list timer;
	unsigned long expire;

	switch (timeout)
	{
	// If the sleep time is the maximum , Then the timer does not need to be set , Call directly schedule Call other processes to run 
	// At this time, it needs to be awakened by other processes , Otherwise you will sleep all the time 
	case MAX_SCHEDULE_TIMEOUT:
		schedule();
		goto out;
	default:
		/*
		 *  If timeout Small and 0  You make a mistake 
		 */
		if (timeout < 0)
		{
			printk(KERN_ERR "schedule_timeout: wrong timeout "
				"value %lx from %p\n", timeout,
				__builtin_return_address(0));
			current->state = TASK_RUNNING;
			goto out;
		}
	}
    // If timeout Is the normal timing , Set the expiration time 
	expire = timeout + jiffies;
    // Set the timer ,process_timeout Is after the timer has timed out , Function of callback 
	setup_timer(&timer, process_timeout, (unsigned long)current);
	__mod_timer(&timer, expire);
	// call schedule Schedule other processes to run 
	schedule();
	// The timer is deleted when the current process is rescheduled 
	del_singleshot_timer_sync(&timer);
    // Calculate timeout 
	timeout = expire - jiffies;
    // If you return 0, It means that the timing time is up , Otherwise, it means that you are awakened before the scheduled time .
 out:
	return timeout < 0 ? 0 : timeout;
}

Copy

This function first determines timeout Value

1. If timeout Is equal to the maximum , Then the timer is not set to schedule directly , At this time, the current process needs to be awakened by other processes , Otherwise it will sleep all the time .

2. If timeout Less than 0 Returns an error

3. If timeout>=0 Less than the maximum , Set a timer .Linux The kernel timer callback function is completed through soft interrupts , After each clock interrupt , The clock soft interrupt flag will be set , Then it wakes up ksoftirqd The kernel thread handles the clock soft interrupt , The clock soft interrupt handler will traverse the timer linked list , If there is a timeout timer, perform a function callback . You can see that the registered callback function is process_timeout, That is, if no other process wakes up the dormant process during the dormancy time , It will trigger after the sleep time process_timeout function .

Look again process_timeout function ：

/*
 *  timer： Timer 
 * function： The callback function triggered after the timer expires 
 *  data： Represents the current process's task_struct
 *
 */
static inline void setup_timer(struct timer_list * timer,
				void (*function)(unsigned long),
				unsigned long data)
{
	timer->function = function;
	timer->data = data;
	init_timer(timer);
}
// Function to call back after timer timeout 
static void process_timeout(unsigned long __data)
{
	// Wake up the process bound to the timer , The main operation is to __data Process from waiting queue , Move to run queue 
	// And set the process status , Then reschedule 
	wake_up_process((struct task_struct *)__data);
}

Copy

You can see that the process that has just been dormant is waked up .

Look at the wake-up operation futex_wake function

static void wake_futex(struct futex_q *q)
{
	// Delete the hash element from the hash linked list 
	list_del_init(&q->list);
	if (q->filp)
		send_sigio(&q->filp->f_owner, q->fd, POLL_IN);
	/*
	 *  Wakes up the waiting thread 
	 */
	wake_up_all(&q->waiters);
	/*
	 * The waiting task can free the futex_q as soon as this is written,
	 * without taking any locks.  This must come last.
	 *
	 * A memory barrier is required here to prevent the following store
	 * to lock_ptr from getting ahead of the wakeup. Clearing the lock
	 * at the end of wake_up_all() does not prevent this store from
	 * moving.
	 */
	wmb();
	q->lock_ptr = NULL;
}

Copy

Here we call wake_up_all Function to wake up , The wake-up kernel function will eventually be called try_to_wake_up. The core logic of the wake-up function , Is to move the process from the waiting queue to the running queue , Set the process state to TASK_RUNNING, Re participate in scheduling . The specific wake-up logic involves the knowledge of kernel process scheduling , There is no analysis here .

futex_wait and futex_wake summary ：

1.futex_wait The current process / Thread task_struct And mutex are wrapped into a struct futex_q The elements of , With mutex It's packaged futex_key For hash table key Do hash calculation , And then futex_q Element into hash table . And then call schedule_timeout Process / Thread hanging .

2.futex_wake Will be based on the mutex futex_q Element from the hash table , In this way, you can get all the threads sleeping on the mutex , Then, it will traverse the linked list elements from front to back nr_wakes A process / Threads .