From: Alex Kogan <alex.kogan@oracle.com>
To: Waiman Long <longman@redhat.com>
Cc: linux-arch@vger.kernel.org, guohanjun@huawei.com, arnd@arndb.de,
Peter Zijlstra <peterz@infradead.org>,
dave.dice@oracle.com, jglauber@marvell.com, x86@kernel.org,
will.deacon@arm.com, linux@armlinux.org.uk,
linux-kernel@vger.kernel.org, mingo@redhat.com, bp@alien8.de,
hpa@zytor.com, steven.sistare@oracle.com, tglx@linutronix.de,
daniel.m.jordan@oracle.com, linux-arm-kernel@lists.infradead.org
Subject: Re: [PATCH v8 3/5] locking/qspinlock: Introduce CNA into the slow path of qspinlock
Date: Mon, 6 Jan 2020 10:02:26 -0500 [thread overview]
Message-ID: <1E203DB5-E35B-48AA-90DC-286FE479BB91@oracle.com> (raw)
In-Reply-To: <fcba7eee-b98f-5381-ea33-6fd94a9e66a6@redhat.com>
> On Jan 3, 2020, at 5:14 PM, Waiman Long <longman@redhat.com> wrote:
>
> On 12/30/19 2:40 PM, Alex Kogan wrote:
>> +/*
>> + * cna_scan_main_queue - scan the main waiting queue looking for the first
>> + * thread running on the same NUMA node as the lock holder. If found (call it
>> + * thread T), move all threads in the main queue between the lock holder and
>> + * T to the end of the secondary queue and return 0
>> + * (=SUCCESSOR_FROM_SAME_NUMA_NODE_FOUND); otherwise, return the encoded
> Are you talking about LOCAL_WAITER_FOUND?
Ahh, yes — good catch!
>> + * pointer of the last scanned node in the primary queue (so a subsequent scan
>> + * can be resumed from that node).
>> + *
>> + * Schematically, this may look like the following (nn stands for numa_node and
>> + * et stands for encoded_tail).
>> + *
>> + * when cna_scan_main_queue() is called (the secondary queue is empty):
>> + *
>> + * A+------------+ B+--------+ C+--------+ T+--------+
>> + * |mcs:next | -> |mcs:next| -> |mcs:next| -> |mcs:next| -> NULL
>> + * |mcs:locked=1| |cna:nn=0| |cna:nn=2| |cna:nn=1|
>> + * |cna:nn=1 | +--------+ +--------+ +--------+
>> + * +----------- +
>> + *
>> + * when cna_scan_main_queue() returns (the secondary queue contains B and C):
>> + *
>> + * A+----------------+ T+--------+
>> + * |mcs:next | -> |mcs:next| -> NULL
>> + * |mcs:locked=C.et | -+ |cna:nn=1|
>> + * |cna:nn=1 | | +--------+
>> + * +--------------- + +-----+
>> + * \/
>> + * B+--------+ C+--------+
>> + * |mcs:next| -> |mcs:next| -+
>> + * |cna:nn=0| |cna:nn=2| |
>> + * +--------+ +--------+ |
>> + * ^ |
>> + * +---------------------+
>> + *
>> + * The worst case complexity of the scan is O(n), where n is the number
>> + * of current waiters. However, the amortized complexity is close to O(1),
>> + * as the immediate successor is likely to be running on the same node once
>> + * threads from other nodes are moved to the secondary queue.
>> + *
>> + * @node : Pointer to the MCS node of the lock holder
>> + * @pred_start: Pointer to the MCS node of the waiter whose successor should be
>> + * the first node in the scan
>> + * Return : LOCAL_WAITER_FOUND or encoded tail of the last scanned waiter
>> + */
>> +static u32 cna_scan_main_queue(struct mcs_spinlock *node,
>> + struct mcs_spinlock *pred_start)
>> +{
>> + struct cna_node *cn = (struct cna_node *)node;
>> + struct cna_node *cni = (struct cna_node *)READ_ONCE(pred_start->next);
>> + struct cna_node *last;
>> + int my_numa_node = cn->numa_node;
>> +
>> + /* find any next waiter on 'our' NUMA node */
>> + for (last = cn;
>> + cni && cni->numa_node != my_numa_node;
>> + last = cni, cni = (struct cna_node *)READ_ONCE(cni->mcs.next))
>> + ;
>> +
>> + /* if found, splice any skipped waiters onto the secondary queue */
>> + if (cni) {
>> + if (last != cn) /* did we skip any waiters? */
>> + cna_splice_tail(node, node->next,
>> + (struct mcs_spinlock *)last);
>> + return LOCAL_WAITER_FOUND;
>> + }
>> +
>> + return last->encoded_tail;
>> +}
>> +
>>
>> +/*
>> + * Switch to the NUMA-friendly slow path for spinlocks when we have
>> + * multiple NUMA nodes in native environment, unless the user has
>> + * overridden this default behavior by setting the numa_spinlock flag.
>> + */
>> +void cna_configure_spin_lock_slowpath(void)
> Nit: There should be a __init.
True. I will fix that.
>> +{
>> + if ((numa_spinlock_flag == 1) ||
>> + (numa_spinlock_flag == 0 && nr_node_ids > 1 &&
>> + pv_ops.lock.queued_spin_lock_slowpath ==
>> + native_queued_spin_lock_slowpath)) {
>> + pv_ops.lock.queued_spin_lock_slowpath =
>> + __cna_queued_spin_lock_slowpath;
>> +
>> + pr_info("Enabling CNA spinlock\n");
>> + }
>> +}
>
> Other than these two minor nits, the rests looks good to me.
Great. I will revise and resubmit.
Best regards,
— Alex
_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
next prev parent reply other threads:[~2020-01-06 15:04 UTC|newest]
Thread overview: 39+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-12-30 19:40 [PATCH v8 0/5] Add NUMA-awareness to qspinlock Alex Kogan
2019-12-30 19:40 ` [PATCH v8 1/5] locking/qspinlock: Rename mcs lock/unlock macros and make them more generic Alex Kogan
2019-12-30 19:40 ` [PATCH v8 2/5] locking/qspinlock: Refactor the qspinlock slow path Alex Kogan
2019-12-30 19:40 ` [PATCH v8 3/5] locking/qspinlock: Introduce CNA into the slow path of qspinlock Alex Kogan
2020-01-03 22:14 ` Waiman Long
2020-01-06 15:02 ` Alex Kogan [this message]
2020-01-21 13:48 ` Peter Zijlstra
2020-01-21 14:42 ` Peter Zijlstra
2019-12-30 19:40 ` [PATCH v8 4/5] locking/qspinlock: Introduce starvation avoidance into CNA Alex Kogan
2020-01-06 15:33 ` Waiman Long
2020-01-21 13:29 ` Peter Zijlstra
2020-01-21 13:50 ` Peter Zijlstra
2020-01-21 21:19 ` Daniel Bristot de Oliveira
2020-01-21 15:45 ` Waiman Long
[not found] ` <3862F8A1-FF9B-40AD-A88E-2C0BA7AF6F58@oracle.com>
2020-01-24 7:52 ` Peter Zijlstra
2020-01-24 14:42 ` Waiman Long
2020-01-24 15:13 ` Peter Zijlstra
2020-01-24 15:19 ` Waiman Long
[not found] ` <8D3AFB47-B595-418C-9568-08780DDC58FF@oracle.com>
[not found] ` <714892cd-d96f-4d41-ae8b-d7b7642a6e3c@redhat.com>
2020-01-25 11:16 ` Peter Zijlstra
[not found] ` <1669BFDE-A1A5-4ED8-B586-035460BBF68A@oracle.com>
[not found] ` <45660873-731a-a810-8c57-1a5a19d266b4@redhat.com>
2020-01-24 18:51 ` Waiman Long
2020-01-25 11:20 ` Peter Zijlstra
2020-01-25 19:57 ` Waiman Long
[not found] ` <693E6287-E37C-4C5D-BE33-B3D813BE505D@oracle.com>
2020-01-24 21:12 ` Waiman Long
2020-01-24 21:27 ` Alex Kogan
2020-01-25 0:38 ` Waiman Long
2020-01-25 11:19 ` Peter Zijlstra
2020-01-30 22:05 ` Alex Kogan
2020-02-03 13:45 ` Peter Zijlstra
2020-02-03 14:59 ` Waiman Long
2020-02-03 15:28 ` Peter Zijlstra
2020-02-03 15:47 ` Waiman Long
[not found] ` <83762715-F68C-42DF-9B41-C4C48DF6762F@oracle.com>
2020-02-04 17:27 ` Peter Zijlstra
2020-02-04 17:39 ` Waiman Long
2020-02-04 17:53 ` Alex Kogan
2019-12-30 19:40 ` [PATCH v8 5/5] locking/qspinlock: Introduce the shuffle reduction optimization " Alex Kogan
2020-01-22 9:56 ` Peter Zijlstra
2020-01-06 15:48 ` [PATCH v8 0/5] Add NUMA-awareness to qspinlock Waiman Long
2020-01-08 5:09 ` Shijith Thotton
2020-01-21 9:21 ` Shijith Thotton
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=1E203DB5-E35B-48AA-90DC-286FE479BB91@oracle.com \
--to=alex.kogan@oracle.com \
--cc=arnd@arndb.de \
--cc=bp@alien8.de \
--cc=daniel.m.jordan@oracle.com \
--cc=dave.dice@oracle.com \
--cc=guohanjun@huawei.com \
--cc=hpa@zytor.com \
--cc=jglauber@marvell.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=steven.sistare@oracle.com \
--cc=tglx@linutronix.de \
--cc=will.deacon@arm.com \
--cc=x86@kernel.org \
/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).