Message-ID: <2019726322.96838.1659473613204.JavaMail.zimbra@efficios.com>
Date:   Tue, 2 Aug 2022 16:53:33 -0400 (EDT)
From:   Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:     Peter Oskolkov <posk@...gle.com>
Cc:     Peter Oskolkov <posk@...k.io>,
        Peter Zijlstra <peterz@...radead.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        Thomas Gleixner <tglx@...utronix.de>,
        "Paul E . McKenney" <paulmck@...nel.org>,
        Boqun Feng <boqun.feng@...il.com>,
        "H. Peter Anvin" <hpa@...or.com>, Paul Turner <pjt@...gle.com>,
        linux-api <linux-api@...r.kernel.org>,
        Christian Brauner <christian.brauner@...ntu.com>,
        Florian Weimer <fw@...eb.enyo.de>,
        David Laight <David.Laight@...lab.com>,
        Carlos O'Donell <carlos@...hat.com>,
        Chris Kennelly <ckennelly@...gle.com>
Subject: Re: [PATCH v3 00/23] RSEQ node id and virtual cpu id extensions

----- On Aug 2, 2022, at 1:06 PM, Peter Oskolkov posk@...gle.com wrote:

> On Tue, Aug 2, 2022 at 8:01 AM Mathieu Desnoyers
> <mathieu.desnoyers@...icios.com> wrote:
>>
> 
> [...]
> 
>> >
>> > We have experimented with several approaches here. The one that we are
>> > currently using is the "flat" model: we allocate vcpu IDs ignoring numa nodes.
>> >
>> > We did try per-numa-node vcpus, but it did not show any material improvement
>> > over the "flat" model, perhaps because on our most "wide" servers the CPU
>> > topology is multi-level. Chris Kennelly may provide more details here.
>>
>> I would really like to know more about Google's per-numa-node vcpus
>> implementation.
>> I suspect you guys may have taken a different turn somewhere in the design which
>> led to these results. But having not seen that implementation, I can only guess.
>>
>> I notice the following Google-specific prototype extension in tcmalloc:
>>
>>   // This is a prototype extension to the rseq() syscall.  Since a process may
>>   // run on only a few cores at a time, we can use a dense set of "v(irtual)
>>   // cpus."  This can reduce cache requirements, as we only need N caches for
>>   // the cores we actually run on simultaneously, rather than a cache for every
>>   // physical core.
>>   union {
>>     struct {
>>       short numa_node_id;
>>       short vcpu_id;
>>     };
>>     int vcpu_flat;
>>   };
>>
>> Can you tell me more about the way the numa_node_id and vcpu_id are allocated
>> internally, and how they are expected to be used by userspace ?
> 
> Based on a "VCPU policy" flag passed by the userspace during rseq registration
> request, our kernel would:
> - do nothing re: vcpus, i.e. behave like it currently does upstream;
> - allocate VCPUs in a "flat" manner, ignoring NUMA;
> - populate numa_node_id with the value from the function with the same name in
>  https://elixir.bootlin.com/linux/latest/source/include/linux/topology.h
>  and allocate vcpu_id within the numa node in a tight manner.
> 
> Basically, if there are M threads running on node 0 and N threads
> running on node 1 at time T, there will be [0,M-1] vcpu IDs associated with
> node 0 and [0,N-1] vcpu IDs associated with node 1 at this moment
> in time. If a thread migrates across nodes, the balance would change
> accordingly.
> 
> I'm not sure how exactly tcmalloc tried to use VCPUs under this policy, and
> what were the benefits expected. The simplest way would be to keep
> a freelist per node_id/vcpu_id pair (basically, per vcpu_flat in the union),
> but this would tend to increase the number of freelists due to thread
> migrations,
> so benefits should be related to memory locality, and so somewhat difficult to
> measure precisely.

So, based on your explanation of the Google implementation, for each memory space,
the kernel keeps per-numa-node vcpu-id allocation domains.

This leaves two choices to userspace AFAIU:

1) Userspace takes the vcpu_flat (int, combining the short node_id with the short vcpu_id)
   as index in a sparse array. The sparseness of the array may be unwelcome in terms of
   memory and cache footprint.

2) Userspace could take a 2-level approach: using the short node_id to index an array of
   "numa node" objects, which would then point to a 2nd level indexed by short vcpu_id.
   This adds an extra pointer dereference on the fast-path, and touches additional cache
   lines on the fast path as well, which is probably unwelcome. In addition, keeping track
   of this 2-level table adds extra complexity in userspace, and requires that user-space
   designs its data structure specifically for NUMA, which is unusual considering that NUMA
   is typically just an optimization hint to improve locality of memory accesses.

Hopefully I did not miss anything there.

So here is how I did things differently.

I realized that when userspace uses a rseq_abi()->cpu_id as index into per-cpu data structures,
it expects that when any of the process' threads observe a numa_node_id when running on behalf
of a given cpu_id once in the process lifetime, this topology is invariant [1]. IOW, the same
cpu_id should always run on the same NUMA node in the future.

This characteristic is what allows indexing by cpu_id to index data structures that have a
good NUMA locality: on first use of a given cpu_id, memory allocation can be done on behalf of
the right NUMA node, and then all per-cpu accesses are guaranteed to be local.

So I applied this concept to vcpu_ids.

The trick here is mostly to add a per-numa-node bitmap to the mm_struct in addition to the bitmap
tracking the current vcpu_id allocation. The per-numa-node bitmap keeps track of which vcpu_ids
have been allocated on behalf of each numa node in the past.

So when a thread running on a given NUMA node needs to find the lowest vcpu_id which is available,
it uses cpumask_first_one_and_zero(node_cpumask, cpumask) to find the first bit which has both
been allocated already for this NUMA node, and is currently not in use by another thread.

There is also a node_alloc_vcpumask bitmap which keeps track of which vcpu have already been
allocated in the past, across all NUMA nodes. This allows scanning efficiently for the first
vcpu which was _not_ yet allocated, and is currently unused with
cpumask_first_zero_and_zero(node_alloc_cpumask, cpumask).

With this, user-space can simply use the vm_vcpu_id field as index into the per-vcpu array,
and the NUMA locality is implicit. Upon initial allocation of the numa-local memory, it just
needs to read both vm_vcpu_id and numa_node_id fields within a rseq critical section to
ensure there is no migration between the two field loads.

So as long as the scheduler does a good job at keeping the number of threads per NUMA node
relatively constant by pushing back against thread migration across NUMA nodes over the process
lifetime, there should not be too many extra vcpu_ids needed. In the worse-case scenario, the
number of vcpu_ids needed is equal to the number of online cpus in the system.

The performance overhead of keeping track of those additional bitmaps for NUMA locality should
be minimal considering that the only update needed in the per-numa-node bitmap and the
node_alloc_vcpumask bitmap is the first time a vcpu_id is assigned within a process. The rest
is lookup only. And even there, the optimizations I have put in place skip those lookups in
the common scenarios entirely.

Thanks,

Mathieu

[1] There is the exception of Power CPU hotplug which can reconfigure the NUMA topology,
    but this seems like a rather odd and rare corner-case. It is supported by my implementation,
    but userspace would have to deal with this kind of reconfiguration on its own to
    preserve NUMA locality.

> 
> Chris Kennelly may offer more details here.
> 
> Thanks,
> Peter

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Powered by blists - more mailing lists