linux-api.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Randy Dunlap <rdunlap@infradead.org>
To: Waiman Long <Waiman.Long@hp.com>,
	Thomas Gleixner <tglx@linutronix.de>,
	Ingo Molnar <mingo@kernel.org>,
	Peter Zijlstra <peterz@infradead.org>,
	Darren Hart <dvhart@linux.intel.com>,
	Davidlohr Bueso <davidlohr@hp.com>,
	Heiko Carstens <heiko.carstens@de.ibm.com>
Cc: linux-kernel@vger.kernel.org, linux-api@vger.kernel.org,
	linux-doc@vger.kernel.org, Jason Low <jason.low2@hp.com>,
	Scott J Norton <scott.norton@hp.com>
Subject: Re: [RFC PATCH 5/5] futex, doc: add a document on how to use the spinning futexes
Date: Mon, 21 Jul 2014 08:45:06 -0700	[thread overview]
Message-ID: <53CD3582.707@infradead.org> (raw)
In-Reply-To: <1405956271-34339-6-git-send-email-Waiman.Long@hp.com>

On 07/21/2014 08:24 AM, Waiman Long wrote:
> This patch adds a new document file on how to use the spinning futexes.
> 
> Signed-off-by: Waiman Long <Waiman.Long@hp.com>
> ---
>  Documentation/spinning-futex.txt |  109 ++++++++++++++++++++++++++++++++++++++
>  1 files changed, 109 insertions(+), 0 deletions(-)
>  create mode 100644 Documentation/spinning-futex.txt
> 
> diff --git a/Documentation/spinning-futex.txt b/Documentation/spinning-futex.txt
> new file mode 100644
> index 0000000..e3cb5a2
> --- /dev/null
> +++ b/Documentation/spinning-futex.txt
> @@ -0,0 +1,109 @@
> +Started by: Waiman Long <waiman.long@hp.com>
> +
> +Spinning Futex
> +--------------
> +
> +There are two main problems for a wait-wake futex (FUTEX_WAIT and
> +FUTEX_WAKE) when used for creating user-space lock primitives:
> +
> + 1) With a wait-wake futex, tasks waiting for a lock are put to sleep
> +    in the futex queue to be woken up by the lock owner when it is done
> +    with the lock. Waking up a sleeping task, however, introduces some
> +    additional latency which can be large especially if the critical
> +    section protected by the lock is relatively short. This may cause
> +    a performance bottleneck on large systems with many CPUs running
> +    applications that need a lot of inter-thread synchronization.
> +
> + 2) The performance of the wait-wake futex is currently
> +    spinlock-constrained.  When many threads are contending for a
> +    futex in a large system with many CPUs, it is not unusual to have
> +    spinlock contention accounting for more than 90% of the total
> +    CPU cycles consumed at various points in time.
> +
> +Spinning futex is a solution to both the wakeup latency and spinlock
> +contention problems by optimistically spinning on a locked futex
> +when the lock owner is running within the kernel until the lock is
> +free. This is the same optimistic spinning mechanism used by the kernel
> +mutex and rw semaphore implementations to improve performance. The
> +optimistic spinning was done without taking any lock.

                       is done

> +
> +Implementation
> +--------------
> +
> +Like the PI and robust futexes, a lock acquirer has to atomically
> +put its thread ID (TID) into the lower 30 bits of the 32-bit futex
> +which should has an original value of 0. If it succeeds, it will be

                have

> +the owner of the futex. Otherwise, it has to call into the kernel
> +using the new FUTEX_SPIN_LOCK futex(2) syscall.
> +
> +The kernel will use the setting of the most significant bit
> +(FUTEX_WAITERS) in the futex value to indicate one or more waiters
> +are sleeping and need to be woken up later on.
> +
> +When it is time to unlock, the lock owner has to atomically clear
> +the TID portion of the futex value. If the FUTEX_WAITERS bit is set,
> +it has to issue a FUTEX_SPIN_UNLOCK futex system call to wake up the
> +sleeping task.
> +
> +A return value of 1 from the FUTEX_SPIN_UNLOCK futex(2) syscall
> +indicates a task has been woken up. The syscall returns 0 if no
> +sleeping task is found or spinners are present to take the lock.
> +
> +The error number returned by a FUTEX_SPIN_UNLOCK call on an empty
> +futex can be used to decide if the spinning futex functionality is
> +implemented in the kernel. If it is present, the returned error number
> +should be ESRCH. Otherwise it will be ENOSYS.
> +
> +Currently, only the first and the second arguments (the futex address
> +and the opcode) of the futex(2) syscall is used. All the other

                                           are used.

> +arguments must be set to 0 or NULL to avoid forward compatibility
> +problem.
> +
> +The spinning futex requires the kernel to have support for the cmpxchg
> +functionality. For architectures that don't support cmpxchg, spinning
> +futex will not be supported as well.
> +
> +Usage Scenario
> +--------------
> +
> +A spinning futex can be used as an exclusive lock to guard a critical
> +section which are unlikely to go to sleep in the kernel. The spinners

                 is

> +in a spinning futex, however, will fall back to sleep in a wait queue
> +if the lock owner isn't running. Therefore, it can also be used when
> +the critical section is long and prone to sleeping. However, it may
> +not have the performance benefit when compared with a wait-wake futex
> +in this case.
> +
> +Sample Code
> +-----------
> +
> +The following are sample code to implement a simple lock and unlock

                 is

> +function.
> +
> +__thread int tid;	/* Thread ID */
> +
> +void mutex_lock(int *faddr)
> +{
> +	if (cmpxchg(faddr, 0, tid) == 0)
> +		return;
> +	for (;;)
> +		if (futex(faddr, FUTEX_SPIN_LOCK, ...) == 0)
> +			break;
> +}
> +
> +void mutex_unlock(int *faddr)
> +{
> +	int old, fval;
> +
> +	if ((fval = cmpxchg(faddr, tid, 0)) == tid)
> +		return;
> +	/* Clear only the TID portion of the futex */
> +	for (;;) {
> +		old  = fval;
> +		fval = cmpxchg(faddr, old, old & ~FUTEX_TID_MASK);
> +		if (fval == old)
> +			break;
> +	}
> +	if (fval & FUTEX_WAITERS)
> +		futex(faddr, FUTEX_SPIN_UNLOCK, ...);
> +}
> 


-- 
~Randy

  reply	other threads:[~2014-07-21 15:45 UTC|newest]

Thread overview: 51+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2014-07-21 15:24 [RFC PATCH 0/5] futex: introduce an optimistic spinning futex Waiman Long
2014-07-21 15:24 ` [RFC PATCH 1/5] futex: add new exclusive lock & unlock command codes Waiman Long
2014-07-21 16:42   ` Thomas Gleixner
2014-07-22 18:22     ` Waiman Long
     [not found]       ` <53CEABD7.3030509-VXdhtT5mjnY@public.gmane.org>
2014-07-22 21:00         ` Thomas Gleixner
     [not found] ` <1405956271-34339-1-git-send-email-Waiman.Long-VXdhtT5mjnY@public.gmane.org>
2014-07-21 15:24   ` [RFC PATCH 2/5] futex: add optimistic spinning to FUTEX_SPIN_LOCK Waiman Long
     [not found]     ` <1405956271-34339-3-git-send-email-Waiman.Long-VXdhtT5mjnY@public.gmane.org>
2014-07-21 17:15       ` Davidlohr Bueso
     [not found]         ` <1405962929.11927.19.camel-5JQ4ckphU/8SZAcGdq5asR6epYMZPwEe5NbjCUgZEJk@public.gmane.org>
2014-07-22 18:46           ` Waiman Long
2014-07-21 20:17     ` Jason Low
2014-07-22 19:34       ` Waiman Long
2014-07-21 15:24 ` [RFC PATCH 3/5] spinning futex: move a wakened task to spinning Waiman Long
2014-07-21 15:24 ` [RFC PATCH 4/5] spinning futex: put waiting tasks in a sorted rbtree Waiman Long
2014-07-21 15:24 ` [RFC PATCH 5/5] futex, doc: add a document on how to use the spinning futexes Waiman Long
2014-07-21 15:45   ` Randy Dunlap [this message]
2014-07-22  3:19     ` Waiman Long
2014-07-21 16:42 ` [RFC PATCH 0/5] futex: introduce an optimistic spinning futex Andi Kleen
2014-07-21 16:45   ` Andi Kleen
     [not found]     ` <871tte3bjw.fsf-KWJ+5VKanrL29G5dvP0v1laTQe2KTcn/@public.gmane.org>
2014-07-21 17:20       ` Darren Hart
     [not found]     ` <CFF29A00.9D44A%dvhart@linux.intel.com>
     [not found]       ` <CFF29A00.9D44A%dvhart-VuQAYsv1563Yd54FQh9/CA@public.gmane.org>
2014-07-21 17:41         ` Darren Hart
     [not found]           ` <CFF29E4A.9D44E%dvhart-VuQAYsv1563Yd54FQh9/CA@public.gmane.org>
2014-07-21 20:16             ` Thomas Gleixner
2014-07-21 21:27               ` Peter Zijlstra
2014-07-21 21:31                 ` Andy Lutomirski
2014-07-21 21:47                   ` Thomas Gleixner
2014-07-21 22:41                     ` Darren Hart
2014-07-22  1:01                       ` Thomas Gleixner
2014-07-22  1:34                         ` Steven Rostedt
2014-07-22  2:31                           ` Mike Galbraith
2014-07-22  3:06                           ` Davidlohr Bueso
     [not found]                           ` <20140721213457.46623e2f-f9ZlEuEWxVcJvu8Pb33WZ0EMvNT87kid@public.gmane.org>
2014-07-22  7:47                             ` Peter Zijlstra
2014-07-22  8:39                               ` Thomas Gleixner
2014-07-22  8:48                                 ` Peter Zijlstra
2014-07-22  9:59                                   ` Thomas Gleixner
2014-07-22 20:25                                     ` Waiman Long
2014-07-22 20:52                                       ` Thomas Gleixner
2014-07-22 20:21                         ` Waiman Long
2014-07-22 21:03                           ` Thomas Gleixner
2014-07-22  0:32                   ` Davidlohr Bueso
2014-07-22  7:35                     ` Peter Zijlstra
2014-07-21 21:43                 ` Thomas Gleixner
2014-07-21 18:24     ` Thomas Gleixner
2014-07-22 18:35     ` Waiman Long
2014-07-22 18:28   ` Waiman Long
     [not found]   ` <8761iq3bp3.fsf-KWJ+5VKanrL29G5dvP0v1laTQe2KTcn/@public.gmane.org>
2014-07-23  4:55     ` Mike Galbraith
2014-07-23  6:57       ` Peter Zijlstra
2014-07-23  7:25         ` Mike Galbraith
2014-07-23  7:35           ` Peter Zijlstra
2014-07-23  7:39             ` Mike Galbraith
2014-07-23  7:52               ` Peter Zijlstra
2014-07-21 21:18 ` Ingo Molnar
2014-07-21 21:41   ` Thomas Gleixner
     [not found]   ` <20140721211801.GA12149-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
2014-07-22 19:36     ` Waiman Long

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=53CD3582.707@infradead.org \
    --to=rdunlap@infradead.org \
    --cc=Waiman.Long@hp.com \
    --cc=davidlohr@hp.com \
    --cc=dvhart@linux.intel.com \
    --cc=heiko.carstens@de.ibm.com \
    --cc=jason.low2@hp.com \
    --cc=linux-api@vger.kernel.org \
    --cc=linux-doc@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@kernel.org \
    --cc=peterz@infradead.org \
    --cc=scott.norton@hp.com \
    --cc=tglx@linutronix.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).