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 31502C6FD18 for ; Wed, 29 Mar 2023 15:01:23 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 96EDF900003; Wed, 29 Mar 2023 11:01:22 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 91F03900002; Wed, 29 Mar 2023 11:01:22 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7E659900003; Wed, 29 Mar 2023 11:01:22 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 6FBEA900002 for ; Wed, 29 Mar 2023 11:01:22 -0400 (EDT) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 3153A160D57 for ; Wed, 29 Mar 2023 15:01:22 +0000 (UTC) X-FDA: 80622249204.12.8CDAC35 Received: from mail-lj1-f176.google.com (mail-lj1-f176.google.com [209.85.208.176]) by imf10.hostedemail.com (Postfix) with ESMTP id 22DCCC0052 for ; Wed, 29 Mar 2023 15:01:15 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b="SbZx/BNv"; spf=pass (imf10.hostedemail.com: domain of urezki@gmail.com designates 209.85.208.176 as permitted sender) smtp.mailfrom=urezki@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=1680102076; 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=uGkOiPefovVtTgmI0DGR4n+0i+4dhScH7wTyfGZyKZ4=; b=nKVce+aMMBgOhilRggAYHQ/YwacMkajHXi2QZLBSH7ee1w7sJFhKWf+lDdEwdyo2EwlAIy PYgfVmuzjPIgXVLUr67MU7FTOSfm0Uy1RdgAD/QJwu/xWn+mrU/OVrLLldYw/b3+ANoa3x wQiCsImlyrYqiTQACmBHay5+zyGImLA= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b="SbZx/BNv"; spf=pass (imf10.hostedemail.com: domain of urezki@gmail.com designates 209.85.208.176 as permitted sender) smtp.mailfrom=urezki@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1680102076; a=rsa-sha256; cv=none; b=owKxppOCER2Z+Sv8Q12RAVZmJ6gCRenLA66pDOVsCtK/Lyccg1hwqeCfSmGGyKZlsMDMlJ or6ls4U5/qENNfkiX8dR6gVJ88ZA8c1E3bUbxqz1BTdcsLdTAi0XfLgyubi6RdDvrdY/OD qyHWjNB4c4rlJfI2CZr39yeDsPef3kY= Received: by mail-lj1-f176.google.com with SMTP id by8so16424304ljb.12 for ; Wed, 29 Mar 2023 08:01:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1680102074; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:date:from:from:to:cc:subject:date:message-id:reply-to; bh=uGkOiPefovVtTgmI0DGR4n+0i+4dhScH7wTyfGZyKZ4=; b=SbZx/BNv29iJLafH16pVZEH6NzuXGx0/EkmsHJg5oGgkhNyDdyt09RSBTN4LYcBRuP grqHwZEISgRdxBDDokfWKVcUjottoVLqaDkaitFH+NnmGvi/Muekp1G3mb5IygF1TESR Ms4CvR2i0s6AYOzrXehFk8kNV5f1JUVDsYc/Ie2dYX5GTaVe4pouDmvdzJpBW01ooHdk NEdraHc2ngwDVbamZMNVKKnaCpcubm6wisE+kh5OGW1nvA/jnUif5aIgsd51EQ1wPNPY ZcAAU1M+4D8nE0uQOrD7dEcKmAicK0Ly0w0ENcuR0S4mUWuntofVk0pi/VQC8+GljMA/ 6FQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1680102074; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:date:from:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=uGkOiPefovVtTgmI0DGR4n+0i+4dhScH7wTyfGZyKZ4=; b=Zx/SYqztdeAqtnesIv/9vlujPUPU5w0t800s1TyPpb2tm5ykdrCLt+RMiHCJEGFo84 e0xcXhiBTDXJn2AQ8i/cvzJ8buHn5jTZca6C6ftuRxcZlekXzNjnUvcWG1NiHUKDFo0r lUy06eiYnwnvMIlfhv77T/NppBizRpZFvnB5l+IIvGSwyQlwJs260Qgmxt0h1DkDQdgw AmgZQJm3KZV3awf+n6p2U2Ge/120LyKY8G+Guc0mLGyPMK1clFPEVLFb5cOVG2ChtCFW nw4qir58kSveO228aum87WXIj8R3u0MTnIIWV1YpsCIMj8rrY0nwMez6uCOsQmY4RuyJ osCQ== X-Gm-Message-State: AAQBX9di6VUPcSuuiKPRsbfWmhf65QuXcJiaK5oB/9fXk9D22fntoROd f1IrMs90UvI+elTtczIx5HI= X-Google-Smtp-Source: AKy350bmNjSibzz5IjH+FPLvx4k80sgIsDRNsbkYElca1mk18T7z7nd5kgY0LY9/n5OZPy8CMNf9FA== X-Received: by 2002:a2e:80c4:0:b0:295:ba22:360 with SMTP id r4-20020a2e80c4000000b00295ba220360mr7177511ljg.42.1680102073973; Wed, 29 Mar 2023 08:01:13 -0700 (PDT) Received: from pc636 (host-90-233-209-50.mobileonline.telia.com. [90.233.209.50]) by smtp.gmail.com with ESMTPSA id h26-20020a2e901a000000b00298a7f8c4bfsm4771546ljg.67.2023.03.29.08.01.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 29 Mar 2023 08:01:13 -0700 (PDT) From: Uladzislau Rezki X-Google-Original-From: Uladzislau Rezki Date: Wed, 29 Mar 2023 17:01:11 +0200 To: Lorenzo Stoakes Cc: "Uladzislau Rezki (Sony)" , 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: <132e2d5c-0c1f-4fff-850c-b3fb084455bb@lucifer.local> X-Rspamd-Queue-Id: 22DCCC0052 X-Stat-Signature: 9ttkxnw37g7cdych9owspxs14w49gft4 X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1680102075-223070 X-HE-Meta: U2FsdGVkX18KUwSs7VHb7h/QzuRb42XP5FsXT8rD8aUs6J4q/BPYvDskM+s0BQl7xb/usR+rfRVVCcLdMaPsSViHHlc86HFFbI7Brie4PFrSHGDYCJriFSRWxjIv5RUuUtzuJpu+mHZlOCslSpcbxihDFN3DbA698LvaRBz2pcXS52xkcZgJMt+A8lbT3ys5livbd4eRJOydNCYQF1LRiwTe/2d0CG1ES+KQXkI5hj6+yeqRaTuYC0Jjb0yQlWFXXUdYZIM2QwpV8gun3Au8z64GXVTl5npMRRdNDtAPsSQ9jHHIIRUU3EqzRg9UbVC4wiMX6B3i+FnR1o8JOtxImWYlDo8jB2ktM6T5NFIQbI61lXSk+PNsN/B67MiaPxv5lTCG99SY1B/NGb9oA6qUfpzdgWhhlcqVPvBc26/p1m38pP/pjsoeGYrPQUcqdaKRxUtNC0ylrynfc//7AdbgZehFm8clS/DfWvtzSFmgoFUAxcCP3UtDNJ9YJcTvC0b1to/TrT+Y7QUdFnubhkbIh3ADzqaTqSwMTi2KHqY5M/GlMdUt0h4jZh0/TxpITOndP5Af+xTXgFRMM2eWXtWGiRcHjz6zcXnDxrqw8TZNmu3m32rDb/oF4WU8BDDz3gUZPBzzCIlqbE7/zDC4x3cj0MH8sElXQSTOU+cEtQljHL0fa6i9y43hPeWOacaPaDJ3BF/LleuVmpNZKAFrbB29yYgo6AjDWtMdNB2QhI4hewHEBkNzybI4l89KVDdyFdrIGQVEk2pmeJWkiXcZDwYUliZKIjzNxy7jTkWiVUfJZ2zMNXSKOZQCAbGRHd+1imp+KS8DwvU60m1nOgv+4B/6WBvkDfWlCpR4KYhwoLLzH+sJZux+rRD7bhKU2mRJbZssH0f33HqmQaJeMjeGQ/kccsgt7uyGPr7DdcyGJQawXe6iGMWnWdxVsqgNXbTspKhYh+0O2nDaXwBMSUZpBdW +Z0/RlvU zoqjacpQncY5JJRRgolpz4xdX6cd+Eoh8wEHEfSs4fzdgcm+UECSriEbiYahNPL8mspUCgELc+J4LqRV8LSgC6/e8qWC9LtsIy5kB4KzmydZV3c+AnsRqTxiprwb5DAj0PujF0sYjbLNx38o8LTptD4Az90+RVHd+zNTfAfAcz6zhv/ZvM0H2jQCI0+EqEQwM2HoY+7DYNDAqSAk42jocS2k5v4QI6y6oedoYnheO1NnELN+xAeS+sWiXy9DD6rN+hbbOo7zrZxa24yeO5kzpgKTEdXC7PteiLN+gF9ACmRSZnIeLu3O96a7gl1cZGoyrI6bXXF3CI6HFAHsRrYMmHjEpaFhntZJavfiNUwV96UE+qi7Ah6caMdV/KOUvfbM+QciUroknhJFWC5j+JhJKtojob3dExrKjx0CJF+BFg0eMHiZwQeSQ5StMKx+WW38ckT1UkmQoJTIUSgA= 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: 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. * * 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. * * 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. */ Are you find with it? -- Uladzislau Rezki