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 4B8B9C7619A for ; Thu, 30 Mar 2023 19:34:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DDA966B0072; Thu, 30 Mar 2023 15:34:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D63946B0074; Thu, 30 Mar 2023 15:34:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id BDD926B0078; Thu, 30 Mar 2023 15:34:21 -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 A71DE6B0072 for ; Thu, 30 Mar 2023 15:34:21 -0400 (EDT) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 707491A0B1C for ; Thu, 30 Mar 2023 19:34:21 +0000 (UTC) X-FDA: 80626565922.12.975D95F Received: from mail-wm1-f50.google.com (mail-wm1-f50.google.com [209.85.128.50]) by imf14.hostedemail.com (Postfix) with ESMTP id 68BB4100015 for ; Thu, 30 Mar 2023 19:34:19 +0000 (UTC) Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=jhf6eyRH; spf=pass (imf14.hostedemail.com: domain of lstoakes@gmail.com designates 209.85.128.50 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=1680204859; 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=4AZMjVxZxEEFlOECKFUO1XIhYF75XUZWy+zJLa0qlV4=; b=IGQQjmbK7bAfGaGR3MPX5ZxDxMZr2yTJ7pLuPDw4wMu14Od7tXWeJyJf3ncyjtIhpWMuXm qVkZc4JOaozB2+CmHsKvOpbxiADz8fes8fAozTZCSo9VY8hysliFlIf5HN/gFgSkHkAGrL kDouDvwdTO2G7laRzWaP2bF4CKsQs14= ARC-Authentication-Results: i=1; imf14.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=jhf6eyRH; spf=pass (imf14.hostedemail.com: domain of lstoakes@gmail.com designates 209.85.128.50 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=1680204859; a=rsa-sha256; cv=none; b=7MpmcwlGqjqmjVHnQ4C/hAh0BhhzUMKGdVRruL66Kx+iu1Rxz4PsZAambETk7q9uO2T3y+ rgTh8u1/bTvw1hkh8fqUlQdEJsX9pBWj9sA1Yz8QERJlZPU2akyZEUSXZZb96TEEWScLk3 Sjku/hjhQD/EnmAZ9XDxoa0S5IPrN6E= Received: by mail-wm1-f50.google.com with SMTP id p34so11594361wms.3 for ; Thu, 30 Mar 2023 12:34:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1680204858; 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=4AZMjVxZxEEFlOECKFUO1XIhYF75XUZWy+zJLa0qlV4=; b=jhf6eyRH0FcsNmCeDgv4Sr/YJyLxNKVqQxorDHqNllLRVTlmooppA/U2ra6LMN52uF xAg1E6nJ6zMGBszdBlC8jRpnA6AFj2W41dK/fNJSeJaxdEU2JNTjm67wByX/VwTSP4SH 4vN9T26EK7CenNbwoQ1nuozEMZlw9bsunFiEUC2pLv36zsW8yaLBChY+k8javk6r/D98 jeoU6zFhoUa5v+jEholcK0+BBfNBeYfl08f/5WCCFhZQ5yuASJQH+lgW+qE1NOKMH8mm boJujgOPkq+5RKV9cFbDQ8WoQXIgfN1SCnwZBERtFziToQo7OfCohZs0pjylrJCNELYP +klw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1680204858; 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=4AZMjVxZxEEFlOECKFUO1XIhYF75XUZWy+zJLa0qlV4=; b=XWClAaH4k/ibzh6JOLBYsl2TwddHZedoNXFquMbDMLX6R/gp+yChaptX4GbkHK0IgX VcCwVgO5I6PmVaubg3efd8OrhvfmFhiyvaqtBjTPkwYTbdETISaHbIPyOy6pATSiOJ6R 8h53IUG0F0HVDacTGKuq3e7duGh1OPj0BQDHY7zEJuHY3dzROPgDLGg9O86HZ/EZYB5x oDpNXsOoVr1XfqxDhvT/7XGKTltHevxyJuQpmo38w0doaumgdWi78ArIP1mRAitT20zp xQPdFtai4Zk5z1ACp4GeP9XnkgxoEWATx1vp79xg5ejI5h58hrYiITZl9wq/LXr67s/Y tg/g== X-Gm-Message-State: AO0yUKX0Qf3Ci8UMXuovw7k5W9XUqQ6SVWGJC78ModHhM/nLZH00Bdys YTOVT43xEj8AUd+aTmPtIKo= X-Google-Smtp-Source: AK7set+hPBYyIj3UMAuKoulqJmB/Ujmt7vkg0s05VhX/bGCDjK1WKCkv+HgwcLaCJZnrbPjCPHEizw== X-Received: by 2002:a7b:c7d6:0:b0:3e1:f8af:8772 with SMTP id z22-20020a7bc7d6000000b003e1f8af8772mr18644164wmk.9.1680204857711; Thu, 30 Mar 2023 12:34:17 -0700 (PDT) Received: from localhost (host86-156-84-164.range86-156.btcentralplus.com. [86.156.84.164]) by smtp.gmail.com with ESMTPSA id o5-20020a05600c510500b003ef5bb63f13sm7482669wms.10.2023.03.30.12.34.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 30 Mar 2023 12:34:17 -0700 (PDT) Date: Thu, 30 Mar 2023 20:34:16 +0100 From: Lorenzo Stoakes To: "Uladzislau Rezki (Sony)" Cc: Andrew Morton , linux-mm@kvack.org, LKML , Baoquan He , Christoph Hellwig , Matthew Wilcox , Dave Chinner , Oleksiy Avramchenko Subject: Re: [PATCH v4 1/2] mm: vmalloc: Remove a global vmap_blocks xarray Message-ID: <836e007c-f73e-4a2f-b069-d71a167fd2b9@lucifer.local> References: <20230330190639.431589-1-urezki@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230330190639.431589-1-urezki@gmail.com> X-Stat-Signature: aes79cdf5kpsfwyc787en5xth51cycaq X-Rspam-User: X-Rspamd-Queue-Id: 68BB4100015 X-Rspamd-Server: rspam06 X-HE-Tag: 1680204859-38814 X-HE-Meta: U2FsdGVkX18CavahVF0AVY8m4tDkDARhunQ/rGHmrmmYCXxm416a+VT/rskZtBjjGRMp+PYcEC6ulFYwC4BK2x5U95yBChNw0l8djytIbHI3aAjuC4OfcXG2JCybei7xp5xH1ueA4lygDu47uPsM3jvMr4IEshyFkTjm79ghxRflehOlcpd5eTFDXUlVpqvtMxQomHbvNLOlSb14aSMkEgz5LZNDVZ3ekJcQlDUhJsuCG0PC1DESrdJPoHBe+B1QDzE8oqo8/gSV/kDE6n3t9Iw0P1TfLaskxXgH3ZyEtpabF6dBPy9etIOyIma9xblkiQaFZGaCeQSJo3LwzERVdtz91V7pbn0WA0FbZMtU5w3QgAcT0wiwFkI5EDeaTZFrEWQb5v6CPcc5XOqyVEr4YZV9xAxKXGS6QM2MMKj6EwQY0605Cv/34QsX5yFi/HIytKbahFT3sUSLs1CatW9GWkFNopSCJVOrwzcPgBulVlQE/gOe5eEY4xjeqesw3xFpPd7/itcXAG9UYh8pc7pCwMoYF5SGjCTOkU/KBMTmtHyhocDrQ25GJGA3xM4so0RFAsBjzWabIVksciY9NnPfxi7JXf221WcdaRUtwhIi512ejaWqsxmLI3McxIy6NT45aHl017WsY1kkE7+SJCLnbRbtSKYZFrkLJqhuLVc6RIUnW/ca4Cij/XAYvglEZ2i4xOQx8C+k/ZPJ7rBf5mkg2+23Jc0gsP15ZtdkPbQ8DlXdsZPywp+L/zdkJehxJ+0QnuU44wn/Go5gOmJTnauaqvscsT68uWs2SO9P9w0OEs1JjQEyFTuIWaETH+M61VL/3FxTIs/Ejlu9X9gOJoryo4Ms9NRKmAKw7gCljhczQgANqtEiXCGz3AMmHTix98Trgl+VoOhyuB1lAzgrVx8v5lzMrKpzov9F/BYJR9XtDsWEDTgNlgIn9fNxE30OAIr8d2ckqRT2IsXyTYQZxWs OzGiUbgP m8au8s8kt8inqMnlKyuc/79MwREn4HvHyBzNi0+20Zycq9qlr5iDXLNDFUxl7NB6fFpzJgJFGnyQRQo3HtL9mr/5Mq+OQeKul01/x37icUJn7K8Lq2N4aiFVk8/d4mm3fcLUJTzsqKINL8uQCMhUVRZx4+z5IBWfL51km5zme1vN52vXGrzYhHt0yGbcirACRpESNrb5s7+171jbm1KnOhBuvLeLSs2AOY7QJsQjGJ6OwsqHJa7pQkGrGkKf17OdAXBJICxX0s9IIrR55ZqQjZb1bid43g2Iu9w9Ysv1Q7t5mEcjIX8zpC54BROOdIltBsKUS96j+f4kIeirm4WIOM8gdMTTX6r+DrvhB6c7RSq+XUY4hpexwlNgwFHzkUK7iLvXYtjrxid1iEwkZtNWiZ2p6W6/clENve8Z78kKLCS8LbuSbdPl/PH7w24gK3MeIdtkrk7CT9oCx+W0rl1GlDDLIDY4nCCxsIJra 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 Thu, Mar 30, 2023 at 09:06:38PM +0200, Uladzislau Rezki (Sony) wrote: > A global vmap_blocks-xarray array can be contented under > heavy usage of the vm_map_ram()/vm_unmap_ram() APIs. The > lock_stat shows that a "vmap_blocks.xa_lock" lock is a > second in a top-list when it comes to contentions: > > > ---------------------------------------- > class name con-bounces contentions ... > ---------------------------------------- > vmap_area_lock: 2554079 2554276 ... > -------------- > vmap_area_lock 1297948 [<00000000dd41cbaa>] alloc_vmap_area+0x1c7/0x910 > vmap_area_lock 1256330 [<000000009d927bf3>] free_vmap_block+0x4a/0xe0 > vmap_area_lock 1 [<00000000c95c05a7>] find_vm_area+0x16/0x70 > -------------- > vmap_area_lock 1738590 [<00000000dd41cbaa>] alloc_vmap_area+0x1c7/0x910 > vmap_area_lock 815688 [<000000009d927bf3>] free_vmap_block+0x4a/0xe0 > vmap_area_lock 1 [<00000000c1d619d7>] __get_vm_area_node+0xd2/0x170 > > vmap_blocks.xa_lock: 862689 862698 ... > ------------------- > vmap_blocks.xa_lock 378418 [<00000000625a5626>] vm_map_ram+0x359/0x4a0 > vmap_blocks.xa_lock 484280 [<00000000caa2ef03>] xa_erase+0xe/0x30 > ------------------- > vmap_blocks.xa_lock 576226 [<00000000caa2ef03>] xa_erase+0xe/0x30 > vmap_blocks.xa_lock 286472 [<00000000625a5626>] vm_map_ram+0x359/0x4a0 > ... > > > that is a result of running vm_map_ram()/vm_unmap_ram() in > a loop. The test creates 64(on 64 CPUs system) threads and > each one maps/unmaps 1 page. > > After this change the "xa_lock" can be considered as a noise > in the same test condition: > > > ... > &xa->xa_lock#1: 10333 10394 ... > -------------- > &xa->xa_lock#1 5349 [<00000000bbbc9751>] xa_erase+0xe/0x30 > &xa->xa_lock#1 5045 [<0000000018def45d>] vm_map_ram+0x3a4/0x4f0 > -------------- > &xa->xa_lock#1 7326 [<0000000018def45d>] vm_map_ram+0x3a4/0x4f0 > &xa->xa_lock#1 3068 [<00000000bbbc9751>] xa_erase+0xe/0x30 > ... > > > Running the test_vmalloc.sh run_test_mask=1024 nr_threads=64 nr_pages=5 > shows around ~8 percent of throughput improvement of vm_map_ram() and > vm_unmap_ram() APIs. > > This patch does not fix vmap_area_lock/free_vmap_area_lock and > purge_vmap_area_lock bottle-necks, it is rather a separate rework. > > v1 - v2: > - Add more comments(Andrew Morton req.) > - Switch to WARN_ON_ONCE(Lorenzo Stoakes req.) > > v2 -> v3: > - Fix a kernel-doc complain(Matthew Wilcox) > > v3 -> v4: > - Improve comments about hashing logic(Lorenzo Stoakes) > - Improve code design(Lorenzo Stoakes) > - Keep the addr_to_vb_idx() func. to cut index length(Baoquan He) > > Signed-off-by: Uladzislau Rezki (Sony) > --- > mm/vmalloc.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++------ > 1 file changed, 63 insertions(+), 8 deletions(-) > > diff --git a/mm/vmalloc.c b/mm/vmalloc.c > index 978194dc2bb8..671d6d5d5b78 100644 > --- a/mm/vmalloc.c > +++ b/mm/vmalloc.c > @@ -1911,6 +1911,13 @@ static struct vmap_area *find_unlink_vmap_area(unsigned long addr) > struct vmap_block_queue { > spinlock_t lock; > struct list_head free; > + > + /* > + * An xarray requires an extra memory dynamically to > + * be allocated. If it is an issue, we can use rb-tree > + * instead. > + */ > + struct xarray vmap_blocks; > }; > > struct vmap_block { > @@ -1928,11 +1935,48 @@ struct vmap_block { > static DEFINE_PER_CPU(struct vmap_block_queue, vmap_block_queue); > > /* > - * 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 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. When used as a hash a 'cpu' passed to > + * per_cpu() is not actually a CPU but rather a hash index. > + * > + * A hash function is addr_to_vb_xarray() which hashes any address > + * to a specific index(in a hash) it belongs to. This then uses a > + * per_cpu() macro to access an array with generated 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 almost always avoids lock contention on insert/remove, > + * however xarray spinlocks protect against any contention that remains. > */ > -static DEFINE_XARRAY(vmap_blocks); > +static struct xarray * > +addr_to_vb_xarray(unsigned long addr) > +{ > + int index = (addr / VMAP_BLOCK_SIZE) % num_possible_cpus(); > + > + return &per_cpu(vmap_block_queue, index).vmap_blocks; > +} > > /* > * We should probably have a fallback mechanism to allocate virtual memory > @@ -1970,6 +2014,7 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask) > struct vmap_block_queue *vbq; > struct vmap_block *vb; > struct vmap_area *va; > + struct xarray *xa; > unsigned long vb_idx; > int node, err; > void *vaddr; > @@ -2003,8 +2048,9 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask) > bitmap_set(vb->used_map, 0, (1UL << order)); > INIT_LIST_HEAD(&vb->free_list); > > + xa = addr_to_vb_xarray(va->va_start); > vb_idx = addr_to_vb_idx(va->va_start); > - err = xa_insert(&vmap_blocks, vb_idx, vb, gfp_mask); > + err = xa_insert(xa, vb_idx, vb, gfp_mask); > if (err) { > kfree(vb); > free_vmap_area(va); > @@ -2022,8 +2068,10 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask) > static void free_vmap_block(struct vmap_block *vb) > { > struct vmap_block *tmp; > + struct xarray *xa; > > - tmp = xa_erase(&vmap_blocks, addr_to_vb_idx(vb->va->va_start)); > + xa = addr_to_vb_xarray(vb->va->va_start); > + tmp = xa_erase(xa, addr_to_vb_idx(vb->va->va_start)); > BUG_ON(tmp != vb); > > spin_lock(&vmap_area_lock); > @@ -2135,6 +2183,7 @@ static void vb_free(unsigned long addr, unsigned long size) > unsigned long offset; > unsigned int order; > struct vmap_block *vb; > + struct xarray *xa; > > BUG_ON(offset_in_page(size)); > BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC); > @@ -2143,7 +2192,10 @@ static void vb_free(unsigned long addr, unsigned long size) > > order = get_order(size); > offset = (addr & (VMAP_BLOCK_SIZE - 1)) >> PAGE_SHIFT; > - vb = xa_load(&vmap_blocks, addr_to_vb_idx(addr)); > + > + xa = addr_to_vb_xarray(addr); > + vb = xa_load(xa, addr_to_vb_idx(addr)); > + > spin_lock(&vb->lock); > bitmap_clear(vb->used_map, offset, (1UL << order)); > spin_unlock(&vb->lock); > @@ -3486,6 +3538,7 @@ static void vmap_ram_vread(char *buf, char *addr, int count, unsigned long flags > { > char *start; > struct vmap_block *vb; > + struct xarray *xa; > unsigned long offset; > unsigned int rs, re, n; > > @@ -3503,7 +3556,8 @@ static void vmap_ram_vread(char *buf, char *addr, int count, unsigned long flags > * Area is split into regions and tracked with vmap_block, read out > * each region and zero fill the hole between regions. > */ > - vb = xa_load(&vmap_blocks, addr_to_vb_idx((unsigned long)addr)); > + xa = addr_to_vb_xarray((unsigned long) addr); > + vb = xa_load(xa, addr_to_vb_idx((unsigned long)addr)); > if (!vb) > goto finished; > > @@ -4272,6 +4326,7 @@ void __init vmalloc_init(void) > p = &per_cpu(vfree_deferred, i); > init_llist_head(&p->list); > INIT_WORK(&p->wq, delayed_vfree_work); > + xa_init(&vbq->vmap_blocks); > } > > /* Import existing vmlist entries. */ > -- > 2.30.2 > Very nice! Reviewed-by: Lorenzo Stoakes