mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Alex Kogan <alex.kogan@oracle.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: linux@armlinux.org.uk, mingo@redhat.com, will.deacon@arm.com,
	arnd@arndb.de, longman@redhat.com, linux-arch@vger.kernel.org,
	linux-arm-kernel@lists.infradead.org,
	linux-kernel@vger.kernel.org,
	Steven Sistare <steven.sistare@oracle.com>,
	Daniel Jordan <daniel.m.jordan@oracle.com>,
	dave.dice@oracle.com, Rahul Yadav <rahul.x.yadav@oracle.com>,
	Thomas Gleixner <tglx@linutronix.de>
Subject: Re: [PATCH 3/3] locking/qspinlock: Introduce starvation avoidance into CNA
Date: Tue, 5 Feb 2019 16:07:37 -0500	[thread overview]
Message-ID: <4A727687-51F9-4FD0-9608-CDBAD6A6EF07@oracle.com> (raw)
In-Reply-To: <20190205092256.GN17528@hirez.programming.kicks-ass.net>

[ Resending after correcting an issue with the included URL and correcting a typo 
in Waiman’s name — sorry about that! ]

> On Feb 5, 2019, at 4:22 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> 
> On Mon, Feb 04, 2019 at 10:35:09PM -0500, Alex Kogan wrote:
>> 
>>> On Jan 31, 2019, at 5:00 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>>> 
>>> On Wed, Jan 30, 2019 at 10:01:35PM -0500, Alex Kogan wrote:
>>>> Choose the next lock holder among spinning threads running on the same
>>>> socket with high probability rather than always. With small probability,
>>>> hand the lock to the first thread in the secondary queue or, if that
>>>> queue is empty, to the immediate successor of the current lock holder
>>>> in the main queue.  Thus, assuming no failures while threads hold the
>>>> lock, every thread would be able to acquire the lock after a bounded
>>>> number of lock transitions, with high probability.
>>>> 
>>>> Note that we could make the inter-socket transition deterministic,
>>>> by sticking a counter of intra-socket transitions in the head node
>>>> of the secondary queue. At the handoff time, we could increment
>>>> the counter and check if it is below a threshold. This adds another
>>>> field to queue nodes and nearly-certain local cache miss to read and
>>>> update this counter during the handoff. While still beating stock,
>>>> this variant adds certain overhead over the probabilistic variant.
>>> 
>>> (also heavily suffers from the socket == node confusion)
>>> 
>>> How would you suggest RT 'tunes' this?
>>> 
>>> RT relies on FIFO fairness of the basic spinlock primitives; you just
>>> completely wrecked that.
>> 
>> This is true that CNA trades some fairness for shorter lock handover
>> latency, much like any other NUMA-aware lock.
>> 
>> Can you explain, however, what exactly breaks here?
> 
> Timeliness guarantees. FIFO-fair has well defined time behaviour; you
> know exactly how long you get to wait before you acquire the lock,
> namely however many waiters are in front of you multiplied by the worst
> case wait time.
Got it — thanks for the clarification!

> 
> Doing time analysis on a randomized algorithm isn't my idea of fun.
> 
>> It seems that even today, qspinlock does not support RT_PREEMPT, given
>> that it uses per-CPU queue nodes.
> 
> It does work with RT, commit:
> 
>  7aa54be29765 ("locking/qspinlock, x86: Provide liveness guarantee")
> 
> it a direct result of RT observing funnies with it. I've no idea why you
> think it would not work.
Just trying to get to the bottom of it — as of today, qspinlock explicitly assumes
no preemption while waiting for the lock.

Here is what Waiman had to say about that in https://lwn.net/Articles/561775:

"The idea behind this spinlock implementation is the fact that spinlocks
are acquired with preemption disabled. In other words, the process
will not be migrated to another CPU while it is trying to get a
spinlock.”

This was back in 2013, but the code still uses per-CPU queue nodes,
and AFAICT, preemption will break things up.

So what you are saying is that RT would be fine assuming no preemption in
the spinlock as long as it provides FIFO? Or there is some future code patch 
that will take care of the “no preemption” assumption (but still assume FIFO)?

Thanks,
— Alex

  parent reply	other threads:[~2019-02-05 21:08 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-01-31  3:01 [PATCH 0/3] Add NUMA-awareness to qspinlock Alex Kogan
2019-01-31  3:01 ` [PATCH 1/3] locking/qspinlock: Make arch_mcs_spin_unlock_contended more generic Alex Kogan
2019-01-31  3:01 ` [PATCH 2/3] locking/qspinlock: Introduce CNA into the slow path of qspinlock Alex Kogan
2019-01-31 17:38   ` Waiman Long
2019-02-01 21:26     ` Alex Kogan
2019-01-31  3:01 ` [PATCH 3/3] locking/qspinlock: Introduce starvation avoidance into CNA Alex Kogan
2019-01-31 10:00   ` Peter Zijlstra
2019-02-05  3:35     ` Alex Kogan
2019-02-05  9:22       ` Peter Zijlstra
2019-02-05 13:48         ` Waiman Long
2019-02-05 21:07         ` Alex Kogan [this message]
2019-02-05 21:12           ` Waiman Long
2019-01-31  9:56 ` [PATCH 0/3] Add NUMA-awareness to qspinlock Peter Zijlstra
2019-02-01 21:20   ` Alex Kogan

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=4A727687-51F9-4FD0-9608-CDBAD6A6EF07@oracle.com \
    --to=alex.kogan@oracle.com \
    --cc=arnd@arndb.de \
    --cc=daniel.m.jordan@oracle.com \
    --cc=dave.dice@oracle.com \
    --cc=linux-arch@vger.kernel.org \
    --cc=linux-arm-kernel@lists.infradead.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux@armlinux.org.uk \
    --cc=longman@redhat.com \
    --cc=mingo@redhat.com \
    --cc=peterz@infradead.org \
    --cc=rahul.x.yadav@oracle.com \
    --cc=steven.sistare@oracle.com \
    --cc=tglx@linutronix.de \
    --cc=will.deacon@arm.com \
    /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

all inboxes | Powered by JetHome®