From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 760AAC74A5B for ; Wed, 29 Mar 2023 16:23:11 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E08E36B0072; Wed, 29 Mar 2023 12:23:10 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D9CBC6B0074; Wed, 29 Mar 2023 12:23:10 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C33E86B0075; Wed, 29 Mar 2023 12:23:10 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id B17BC6B0072 for ; Wed, 29 Mar 2023 12:23:10 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 770C240BFE for ; Wed, 29 Mar 2023 16:23:10 +0000 (UTC) X-FDA: 80622455340.08.0264C79 Received: from mail-wm1-f43.google.com (mail-wm1-f43.google.com [209.85.128.43]) by imf01.hostedemail.com (Postfix) with ESMTP id 7038540007 for ; Wed, 29 Mar 2023 16:23:08 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=RSO+my1D; spf=pass (imf01.hostedemail.com: domain of lstoakes@gmail.com designates 209.85.128.43 as permitted sender) smtp.mailfrom=lstoakes@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1680106988; a=rsa-sha256; cv=none; b=q8HPz/kmFXJWZbFcGsdi8ymmJp8CrhPvtm9S0UdCk4QXUQsiOJYK4+kL0ekeN7Yl5iYb2l dlCrSFrchAhNQjMVwyhexI9OvZwhdDypMM8pxZEEMLxzdiyHCSmDs136Dgd0daW1AXOuz3 VwxjvJMnkQ5qjkAb6RsuFPcDnUQN3to= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=RSO+my1D; spf=pass (imf01.hostedemail.com: domain of lstoakes@gmail.com designates 209.85.128.43 as permitted sender) smtp.mailfrom=lstoakes@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1680106988; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=GlibarqBbZ4Q0mPsWReLWgLf3BnPWtPZlsUlpY0M8PQ=; b=uX9hOwoarc0g6+XFmxuUisYgQ9akWhI9kdDfsTK8nnSNGzz0bUq7Sv0BZBH/Xjo+gQWkSL Bbw2JbdO0PqIQzsEA8UczgQZmz3TWQZdkHXif4aIizNE/bJ3hrfXrPM8VccLfgEInG/IkF hPZn32q45KD3atkVonTs8qWlbxZYqP0= Received: by mail-wm1-f43.google.com with SMTP id d11-20020a05600c3acb00b003ef6e6754c5so6399295wms.5 for ; Wed, 29 Mar 2023 09:23:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1680106987; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=GlibarqBbZ4Q0mPsWReLWgLf3BnPWtPZlsUlpY0M8PQ=; b=RSO+my1D55gcMaKHDx5zQ3TCPd3DaIBAgXOqlGdI8tctkJGeKTNSV8irKwETa6Qr/q ygvt0qW05COhtQdgjp79ou02U9SeEA05pUU047PBx83ycFUMVKrQHgKZWDZWeRgeV+3/ ZFagReelZMGVg+QmwFTVVu+UMiiQ1OQSLo8DV73K0Kl2GPv6aKVD/lGZ3dk2Vdmgt8ww rH7lnBjcZuNzajuALBDctf7jOSp84d6TTAYW6pM1Fxyw6CL3Fc1ov3CVNpYtYQ80PBFZ RudhmGJxext9IcHG3VmYjZ4Xz+B5XDLLvnBJ2EIUGJaogZjnhRKGcAajlA6iJ0yVYfYr 9vjg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1680106987; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=GlibarqBbZ4Q0mPsWReLWgLf3BnPWtPZlsUlpY0M8PQ=; b=fxMo0LvTFlgODSzeVn8QS2Zt7O26urpbyhyJXh4wirXFhPGN8wCNc3yAWwGdpZZvfu 7HAt0yCuBxye3P31nz1Udkk9YCcc3c3j4eieXJ34BDZ1GjcRCl5SEnqdxFxdX7LUEEL4 sKwOK6/yJbXq+R+PHQiUldnY0+ZGaukaC/WZgGPLcl3NTfrRioZavK7nuBsC+oQC3PFj uakYsrXT8D5+KFlFA5D/7/RXMCahIZa3OsNWOxA13X0WdaYqNa0GfCmysl4DMdpxTh6J 4C4M/BUQOPKeh/BuQtl9tRP28loYnAZq9hQUySJjCEMVtPKTXbzRqbHpfyquiqMuMpHl dG7g== X-Gm-Message-State: AO0yUKWcs5p7RBKNaecjmeVNFlwAKukMeLXU81t4+VyBsxM8KhEbKTU7 arCSfGv7Uu6+mAUnFzkv7Ok= X-Google-Smtp-Source: AK7set+kPI0uPHX/+oeAOe4CloIOapYtWqi+nps/c/zQdsmvNuNSHHfB15M0OOakmiPQu34zcSwxtw== X-Received: by 2002:a1c:790b:0:b0:3ee:56f7:75d2 with SMTP id l11-20020a1c790b000000b003ee56f775d2mr15645326wme.20.1680106986790; Wed, 29 Mar 2023 09:23:06 -0700 (PDT) Received: from localhost ([208.34.186.1]) by smtp.gmail.com with ESMTPSA id x15-20020a05600c21cf00b003ee1b2ab9a0sm2699424wmj.11.2023.03.29.09.23.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 29 Mar 2023 09:23:05 -0700 (PDT) Date: Wed, 29 Mar 2023 17:23:04 +0100 From: Lorenzo Stoakes To: Uladzislau Rezki Cc: Andrew Morton , linux-mm@kvack.org, LKML , Baoquan He , Christoph Hellwig , Matthew Wilcox , Dave Chinner , Oleksiy Avramchenko Subject: Re: [PATCH v3 1/2] mm: vmalloc: Remove a global vmap_blocks xarray Message-ID: References: <20230327170126.406044-1-urezki@gmail.com> <132e2d5c-0c1f-4fff-850c-b3fb084455bb@lucifer.local> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Rspam-User: X-Rspamd-Queue-Id: 7038540007 X-Rspamd-Server: rspam01 X-Stat-Signature: gahagrcudhdhoaznic9i8b9tewdm6jsc X-HE-Tag: 1680106988-201039 X-HE-Meta: U2FsdGVkX18To6Pi76AYFKF3q8J438J9sH6OGJLEfuluieNHyv/1eMXKCIythHlHuKWxSl0zS50ngI2NUIs4PCxj54Eotm1CoKBjONxApfbMkDHwUkIW4aeZbRTiWICsh9E81gFqfGlqHoWGvuAIglno1h4YWlDiz/nsyCLHkbVTdMEJZLvzdtbqriiJjFKnZ/9FGsapOwW543pZ9owWKFlmNfngQ0cVfdnD0nwcOxwX+2cugsW4TlrRs2w4OpZK8pxoLAu0BmiZhOOXSS5qdlWx+/FJavHEWqZSKjQZU8sM0n1i9WWNlgHsbvj2NNavdEew3B0PupGUegpKBiIJOb7yfNZ8XC28kI9LQ81fNwn1GAtkqSOz17a7fVgNQtNQc2xv/t99BfiBrRS1/vV5X1shkE1Ul94DC666FcvrIYkkLdXyYlEgD4p2xx7IO6woZMOFwOhElUkhjQF4Ovqc72qwrMoEYigo4w5hPHNIBxp8amXtyV9mAzgNgwIeidbtnJfDnBD6cPAWRev54aN6PFsrJA1cNMjnEH4xomu7JfvoVAq8T+5edFzEXIa+BPTJ4JDL7CiCW1hKo+dFo5UiA4OeJbCyJOkqqezCdcj8XnDFa6ZrLUC0FN44KzH3D+Kf6KXkYOI8f0TfVGquTDWAYp2w390znYosvIOXqoCCf9Us48JRneCywxsVa3ysyFbIinEA022S8U7UvGx7TEWGJgUhhuW4pv3S54ea9rfjvLKucuGLuWvOv1/9Twe8az+My1psnwIisgmvycqqfwb5QfiA8vpeyBC8XGOYSs5gKF6SrwIu1XtXtYTXTifI7rxlPITbMqa8wwFgc/66SfCmMYQPU7Tx7b54B7FwbJyN8pUQU9+luocwtZTPHOZnIBQwY062Y+yVp4bt0popBQH6H3lthvIY7jm5LxLvhz36iw2Sd0Ce19rpRz8l6mM9bBCx3Eqpzra5rTEgEz67JN6 d3y+XGdv LppMRsHulymFqo7RAnAm90a0lfHyjwNu2s3i8O37ZnSpqr2Nt6G3JETBNpHa/CNipT5EYB3ecT4AbgfGv0zKi8RWSP7wEdmdr9X0P5t060nL3jes5BM6Y28WYiv77UGM4oXMao8G9eJsaMR6robSbkEefzSnMeTEHSBks5zyVhnvi8tECBOAppgM5Xf7N0fSx/Jb27Fc8NKe1B0l8jTmThhDVe2kVX8qB1rWBWHMb+Yz12H9sdUiTmzUnaZJpY1jHQM+mc6LBrzDsMhqWs1wk40R4GKbwywRj9iHpSCogPPXovR8G53LFUYUJ++upeXKdUNThgjyNU2U0Z2tIyc1SvwflLEOxhyzhU9D426/2DO/iPLnJn3gvS/HYvHRbGhfCe/Uw6EYq14iJRfDmbnhGVoKZAE4apSjCChB2Cj8S9Mr1XLhdhGjW4vVc6IhQxFaOV5bHiR2DeAmrH5XYKIjJtl2a7m2PMor/6bD7dSeVRCZ491I= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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 > > > + * |------|------|------|------|------|------|... > > > + * 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 > * |------|------|------|------|------|------|... > * 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 :) > > -- > Uladzislau Rezki >