Message-ID: <ZCR6erByRH0g19wd@pc636>
Date:   Wed, 29 Mar 2023 19:50:50 +0200
From:   Uladzislau Rezki <urezki@...il.com>
To:     Lorenzo Stoakes <lstoakes@...il.com>
Cc:     Uladzislau Rezki <urezki@...il.com>,
        Andrew Morton <akpm@...ux-foundation.org>, linux-mm@...ck.org,
        LKML <linux-kernel@...r.kernel.org>, Baoquan He <bhe@...hat.com>,
        Christoph Hellwig <hch@...radead.org>,
        Matthew Wilcox <willy@...radead.org>,
        Dave Chinner <david@...morbit.com>,
        Oleksiy Avramchenko <oleksiy.avramchenko@...y.com>
Subject: Re: [PATCH v3 1/2] mm: vmalloc: Remove a global vmap_blocks xarray

On Wed, Mar 29, 2023 at 05:23:04PM +0100, Lorenzo Stoakes wrote:
> On Wed, Mar 29, 2023 at 05:01:11PM +0200, Uladzislau Rezki wrote:
> > Hello, Lorenzo!
> >
> > > >  /*
> > > > - * XArray of vmap blocks, indexed by address, to quickly find a vmap block
> > > > - * in the free path. Could get rid of this if we change the API to return a
> > > > - * "cookie" from alloc, to be passed to free. But no big deal yet.
> > > > + * In order to fast access to any "vmap_block" associated with a
> > > > + * specific address, we store them into a per-cpu xarray. A hash
> > > > + * function is addr_to_vbq() whereas a key is a vb->va->va_start
> > > > + * value.
> > > > + *
> > > > + * Please note, a vmap_block_queue, which is a per-cpu, is not
> > > > + * serialized by a raw_smp_processor_id() current CPU, instead
> > > > + * it is chosen based on a CPU-index it belongs to, i.e. it is
> > > > + * a hash-table.
> > > > + *
> > > > + * An example:
> > > > + *
> > > > + *  CPU_1  CPU_2  CPU_0
> > > > + *    |      |      |
> > > > + *    V      V      V
> > > > + * 0     10     20     30     40     50     60
> > > > + * |------|------|------|------|------|------|...<vmap address space>
> > > > + *   CPU0   CPU1   CPU2   CPU0   CPU1   CPU2
> > > > + *
> > > > + * - CPU_1 invokes vm_unmap_ram(6), 6 belongs to CPU0 zone, thus
> > > > + *   it access: CPU0/INDEX0 -> vmap_blocks -> xa_lock;
> > > > + *
> > > > + * - CPU_2 invokes vm_unmap_ram(11), 11 belongs to CPU1 zone, thus
> > > > + *   it access: CPU1/INDEX1 -> vmap_blocks -> xa_lock;
> > > > + *
> > > > + * - CPU_0 invokes vm_unmap_ram(20), 20 belongs to CPU2 zone, thus
> > > > + *   it access: CPU2/INDEX2 -> vmap_blocks -> xa_lock.
> > > >   */
> > >
> > > OK so if I understand this correctly, you're overloading the per-CPU
> > > vmap_block_queue array to use as a simple hash based on the address and
> > > relying on the xa_lock() in xa_insert() to serialise in case of contention?
> > >
> > > I like the general heft of your comment but I feel this could be spelled
> > > out a little more clearly, something like:-
> > >
> > >   In order to have fast access to any vmap_block object associated with a
> > >   specific address, we use a hash.
> > >
> > >   Rather than waste space on defining a new hash table  we take advantage
> > >   of the fact we already have a static per-cpu array vmap_block_queue.
> > >
> > >   This is already used for per-CPU access to the block queue, however we
> > >   overload this to _also_ act as a vmap_block hash. The hash function is
> > >   addr_to_vbq() which hashes on vb->va->va_start.
> > >
> > >   This then uses per_cpu() to lookup the _index_ rather than the
> > >   _cpu_. Each vmap_block_queue contains an xarray of vmap blocks which are
> > >   indexed on the same key as the hash (vb->va->va_start).
> > >
> > >   xarray read acceses are protected by RCU lock and inserts are protected
> > >   by a spin lock so there is no risk of a race here.
> > >
> > /*
> >  * In order to fast access to any "vmap_block" associated with a
> >  * specific address, we use a hash.
> >  *
> >  * A per-cpu vmap_block_queue is used in both ways, to serialize
> >  * an access to free block chains among CPUs(alloc path) and it
> >  * also acts as a vmap_block hash(alloc/free paths). It means we
> >  * overload it, since we already have the per-cpu array which is
> >  * used as a hash table.
> 
> Nit - it may be worth highlighting that when used as a hash it the 'cpu' is
> not in fact a cpu but rather a hash key.
> 
> E.g. just add on the end of this something like:-
> 
> When used as a hash table the 'cpu' passed to per_cpu is not actually a CPU
> but rather the hash key.
> 
> >  *
> >  * A hash function is addr_to_vbq() which hashes any address to
> >  * a specific index(in a hash) it belongs to. This then uses a
> >  * per_cpu() macro to access the array with specific index.
> 
> May need a tweak if you are happy with my review that we can simply have a
> helper that returns the xarray in which case we won't necessary have this
> function :) but depends of course on how the respin looks!
> 
> >  *
> >  * An example:
> >  *
> >  *  CPU_1  CPU_2  CPU_0
> >  *    |      |      |
> >  *    V      V      V
> >  * 0     10     20     30     40     50     60
> >  * |------|------|------|------|------|------|...<vmap address space>
> >  *   CPU0   CPU1   CPU2   CPU0   CPU1   CPU2
> >  *
> >  * - CPU_1 invokes vm_unmap_ram(6), 6 belongs to CPU0 zone, thus
> >  *   it access: CPU0/INDEX0 -> vmap_blocks -> xa_lock;
> >  *
> >  * - CPU_2 invokes vm_unmap_ram(11), 11 belongs to CPU1 zone, thus
> >  *   it access: CPU1/INDEX1 -> vmap_blocks -> xa_lock;
> >  *
> >  * - CPU_0 invokes vm_unmap_ram(20), 20 belongs to CPU2 zone, thus
> >  *   it access: CPU2/INDEX2 -> vmap_blocks -> xa_lock.
> >  *
> >  * This technique allows almost remove a lock-contention in locking
> >  * primitives which protect insert/remove operations.
> 
> This sentence is a little confusing, perhaps rephrase a little:-
> 
> This technique almost always avoids lock contention on insert/remove,
> however the xarray spinlock protects against any contention that remains.
> 
> >  */
> > Are you find with it?
> 
> Other than the small nits above (sorry!) it seems fine! Thanks for
> updating, much appreciated :)
> 
Good. Made the changes. I will upload a new vX patch. Everything
that makes it more clear for readers is worth to do :)

--
Uladzislau Rezki

Powered by blists - more mailing lists