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 A9D2DC74A5B for ; Wed, 29 Mar 2023 17:59:02 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 314266B0072; Wed, 29 Mar 2023 13:59:02 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 29D236B0074; Wed, 29 Mar 2023 13:59:02 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1171E900002; Wed, 29 Mar 2023 13:59:02 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id EE17F6B0072 for ; Wed, 29 Mar 2023 13:59:01 -0400 (EDT) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id BEF3340D5C for ; Wed, 29 Mar 2023 17:59:01 +0000 (UTC) X-FDA: 80622696882.10.2CB813D Received: from mail-ed1-f51.google.com (mail-ed1-f51.google.com [209.85.208.51]) by imf13.hostedemail.com (Postfix) with ESMTP id CAE3C20008 for ; Wed, 29 Mar 2023 17:58:59 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=BGSy5Ivp; spf=pass (imf13.hostedemail.com: domain of urezki@gmail.com designates 209.85.208.51 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=1680112739; a=rsa-sha256; cv=none; b=hdMbvTspGx5ZqyD9Wj4c1bIUxDFExz8WIPPzfDXuLgHQu7cjgvrrMLUmUydi77bAlJdVaK /g9P68lCGk6ebHJGgBCwu0JtXvN2819a9CrKf0XBpG8Geoapb7/c9EUfS++xx3Hjn5Slvq yn+hqCzgogtvh5FrBtjo/s1nUfE/Pvk= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=BGSy5Ivp; spf=pass (imf13.hostedemail.com: domain of urezki@gmail.com designates 209.85.208.51 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=1680112739; 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=CrJBG4j0MX3RJtzvHtYn32M+HCCSyQiEld3ZxAOtBC0=; b=iOV4HdqSkLuZ7eFZpdnys7P9vJYIaepFr3rUwGjbUhNXfQWRow8J1DKidwA6GoYffBD+G6 QMniJg8XCNoJNy/R3sxSiUgtW24Q4mGG6Zj1Be0z02DLXzbrIG9mFm98NXYagtK5e5p9Qn 3VRDQ6Zi2X282VFGfBJwqFxQYZQOG+0= Received: by mail-ed1-f51.google.com with SMTP id x3so66613728edb.10 for ; Wed, 29 Mar 2023 10:58:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1680112738; 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=CrJBG4j0MX3RJtzvHtYn32M+HCCSyQiEld3ZxAOtBC0=; b=BGSy5IvpSG595wNMfojAGix57LvoKoJAyGkOtWROfZ1I1d7ESYhs7Yo1wI0cqUHoVS JdwFz5B7uWp/3OaVFlz4xSaFwFNVMnp5bbSqxTWcurR1B0VRm8Vkq2Lb7TbCefmbGzJp kRJgdzT1jOzFgWy/m8VgrvH0jt52g716d1DSUXkkGfnVIs3qQVJFlbL9e6QLectuyNb2 IqHH6feXZd2p6w1t51ATa4f+9A7lttPhcVnJXd9GyMosY9iOQMPPZ0qBT31haE7bj6Fl fhy+qTA78tfL1Zwv2zFwJQO8k80BQVjr1B5nM9QS/DfWZWf6YZyIHRhhpwPtNJ8WsoD6 PHJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1680112738; 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=CrJBG4j0MX3RJtzvHtYn32M+HCCSyQiEld3ZxAOtBC0=; b=PikQFaApHatcIaQkj/5jxlxO/DyOngY+L0iqFJB/GO/wp7socbUIacwJU3S5QivhSz zumulqJfDRz3dtGG63ujNxBqMbnrTob0rOmvXm9sZIVckDNuMEuZ+mPlVMDVOy4gDQIL o7X+v8d4VGliTqc9/ylYK+D2aOjbhykaLuASUjdt3E5r8MGn8lFgDvARFpLGnZ0Nqwnw BDm1lPAhON1dIb1LC1uHprqNXvGe/v7JkYaYthjICirKdQuDVbNVdK5rFoGafjQ8aK90 Wfk+vNbjyuUWj/ZQ6Ij0mjZPnI1t5g2zJDIeT2MHGEyx9ftnif7zG/DhfKiyR8st9lrD L1Mg== X-Gm-Message-State: AAQBX9du1qTxBdjy1m9jZ7o7N8s98SEc1E4yBMH01hMs07vUgYxbfGRq lAsWeVCZiEIglR0rVuACrprIJuhJgcs= X-Google-Smtp-Source: AKy350b5bWyYa2pQhB7T397LxSlDTtO5CdfVLDLtkRV8ip3h1rjrRIUGLFB48p5UJ8VkXrWNtNaV1w== X-Received: by 2002:ac2:59c6:0:b0:4e9:5f90:748 with SMTP id x6-20020ac259c6000000b004e95f900748mr5957347lfn.9.1680112253181; Wed, 29 Mar 2023 10:50:53 -0700 (PDT) Received: from pc636 (host-90-233-209-50.mobileonline.telia.com. [90.233.209.50]) by smtp.gmail.com with ESMTPSA id u4-20020ac251c4000000b004db1a7e6decsm5546238lfm.205.2023.03.29.10.50.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 29 Mar 2023 10:50:52 -0700 (PDT) From: Uladzislau Rezki X-Google-Original-From: Uladzislau Rezki Date: Wed, 29 Mar 2023 19:50:50 +0200 To: Lorenzo Stoakes Cc: Uladzislau Rezki , 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: CAE3C20008 X-Rspamd-Server: rspam01 X-Stat-Signature: iftau5ggkyofo43dkh4g9frtfe3qe318 X-HE-Tag: 1680112739-495587 X-HE-Meta: U2FsdGVkX19BK+ANFLGHqhpguKdWb14rNIWuJJYAQsC+l+rnPEqAqpSVLqXi/R/x9wX/RJPSyr77xoPt3VpXMJnamccGnIn3SIlS2RHCaaysunAnRAUk9o9tpqxpUQYJZ+MIy3eth9Y2sf/SJf+eBUNVzQgWhMkdIU0OMlJdfXtQoqhVGv6lV6XM0fYyWe3XMaRMAh2h7ZhozGlyyxZvkr+gsruTstZl7ioyDu9+koODIaItvUiOp57oNn/ZgNyNMCBm4kQxKm3YcDZgp3iYewRVXw1KoIWF1ESt6/3eUjAQjhcvGj7Jsjkrfd/T21td9FP0V9PFkF4jU4F9RWD3E1QrRb9Q98Mn35I86HFPlmqBIafOktlM8mZjyuAlJyCnYLW0keArLHU67ZjforZnDYH22FHZs/7zW3oLbjIWh1txCKapr8QoQymJpJcUQdyLFUcZi91J3OnoHxtJo8VQBmnX51Lz53gNSiNX+L0PQB8w1rBxlJ8DiDhu5voNgP6a8TR4D3Bfj7W7oZATy2hm3YkFqakbh6RBpXE7rIg0jUvXrXi5kbOoXj8fMih2qWVZ9ntueQYCQb1hilF1cvOTiV/yfzOfdM/IFSJ/nMh+wT6//Yfkwp0xLAtFxIklCq/QLJKW1Fur+xood4sxYY4eRt2P2IUBBK5kB/tGQ5NU1Q3qxqpukzyWeq/qWFIeH0N8l8v/t6N/d+Xt+e/5iDbD3rgAZgLVM2xHDXrEPcBVFz401piLkVc85UlWfNGx8FkiWINP8N64K5MtVZIeGVFVYYegMGciTL26mnPRjKa5KCe+TF2YL/Zii0clSlGgJuCW5dBabFwOM/TT0hLHdaCeq2fVdp2Vr8W7xgCkfhfJSX6i95A1k2RAi1/B7Wkph0ggtcmIWCYWmKVEWoF0wiIheK3AHJ3eUcu/vToWZUCwDox2Ae5yhnTOf60dLNtROICaZFw7jMB6ESSJc+l+iSS oyZ/aIwY EeTKGSLG33pJnzdGxtb8zm/phEULTkmaJvnxB+sayu/w06fkPkTsh+WsrHVhm2wXj1qx83KaNLtWeLjv/BDG+2vcNIjy4ISHJQ5rZrTEe4853zjfwd5g/lyGL1ed8avLJ/SxUyrHLqwGocMoGBcwU29+I2JpTNHtxiIR867hKBXHz+5WiKAZ/ffMp6/SXhhTrdqHqPsO8Fgsm1Afg5QKDkR6t6x41gWUteou54mAxvOKCJl5JHuAlSVEowVqx1yCaT/p6oJTrXIhtb4EomppMVNNvNVZcFPZdNgDEeh+rfqWmdLZH0YGE4qjapiWDdb8sUkiKzqeGYgc3O2mswnL6htX671wQBb63LjmMrAoduoBRITKBFpvKa/wZNysv31B1aL3DpqNtNvHGnndgF6NLLLmzxDFCLDo8mZvjGeqBI2oO7aa8cjlT16xbKJQ+5n7evCS5ZyCtrPQRN1dbm1ua72K+1IvPVJ46XMxmgx5i+xT+tLYt5idpQ+Amzw== 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: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 > > > > + * |------|------|------|------|------|------|... > > > > + * 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 :) > 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