linux-kernel - Re: [PATCH v9 0/5] Add NUMA-awareness to qspinlock

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 27 Jan 2020 01:16:36 -0500
From:   Alex Kogan <alex.kogan@...cle.com>
To:     Lihao Liang <lihaoliang@...gle.com>
Cc:     linux@...linux.org.uk, Peter Zijlstra <peterz@...radead.org>,
        mingo@...hat.com, will.deacon@....com, arnd@...db.de,
        longman@...hat.com, linux-arch@...r.kernel.org,
        linux-arm-kernel@...ts.infradead.org, linux-kernel@...r.kernel.org,
        tglx@...utronix.de, bp@...en8.de, hpa@...or.com, x86@...nel.org,
        guohanjun@...wei.com, jglauber@...vell.com, dave.dice@...cle.com,
        steven.sistare@...cle.com, daniel.m.jordan@...cle.com,
        Will Deacon <will@...nel.org>
Subject: Re: [PATCH v9 0/5] Add NUMA-awareness to qspinlock


>>> This is particularly relevant
>>> in high contention situations when new threads keep arriving on the same
>>> socket as the lock holder.
>> In this case, the lock will stay on the same NUMA node/socket for
>> 2^numa_spinlock_threshold times, which is the worst case scenario if we
>> consider the long-term fairness. And if we have multiple nodes, it will take
>> up to 2^numa_spinlock_threshold X (nr_nodes - 1) + nr_cpus_per_node
>> lock transitions until any given thread will acquire the lock
>> (assuming 2^numa_spinlock_threshold > nr_cpus_per_node).
>> 
> 
> You're right that the latest version of the patch handles long-term fairness
> deterministically.
> 
> As I understand it, the n-th thread in the main queue is guaranteed to
> acquire the lock after N lock handovers, where N is bounded by
> 
> n - 1 + 2^numa_spinlock_threshold * (nr_nodes - 1)
> 
> I'm not sure what role the variable nr_cpus_per_node plays in your analysis.

Yeah, that’s a minor point, but let me try to clarify.

The "n-th thread in the main queue” is (at most) the nr_cpus_per_node-th thread 
for some node k. So when the node k gets the preference, that thread will
get the lock after at most nr_cpus_per_node-1 lock transitions. As we consider
the upper bound, your analysis is also correct; mine is just a bit tighter.

Makes sense?

Regards,
— Alex