From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8F6EBC77B75 for ; Mon, 15 May 2023 13:19:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S241791AbjEONTG (ORCPT ); Mon, 15 May 2023 09:19:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36712 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241373AbjEONS4 (ORCPT ); Mon, 15 May 2023 09:18:56 -0400 Received: from mail-pg1-x530.google.com (mail-pg1-x530.google.com [IPv6:2607:f8b0:4864:20::530]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4889910A for ; Mon, 15 May 2023 06:18:28 -0700 (PDT) Received: by mail-pg1-x530.google.com with SMTP id 41be03b00d2f7-5208be24dcbso9137435a12.1 for ; Mon, 15 May 2023 06:18:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156708; x=1686748708; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=EveqtihCJt7fcxXdeINag7+zgOnp1O/guDL1F4v1dKU=; b=iH5wFnjAsZmRlAplDuTJ9I2hT2yvPCtbCKAQtoKqkq9S613j7lIiGO7vKZbSxzeW9h y+bsbpYKxsSfj0ALt0rm64PBjNnXlkahKtOH0yA3Cur9j3p8fSEUf6LVDIwbYOyemyEx JbYvB6KqpsD9G8GEDUDuDf2iQmVs2gW09IIshiqQf6gjH417PbMKiSGifdc7GmoEQfm0 KYF8J1oWTM6zH6D4HVei6jdxOb9NOAUCc5G2cdQbBoM16/K567m0A03DOMoHDmNhYIRZ QiTRh5AtBQdJ1rnV9qTdcMXoAqu/IC34CoDAq4WgSRaGVQANFFafyPMJBUaFX4iT1wXS W+vw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156708; x=1686748708; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=EveqtihCJt7fcxXdeINag7+zgOnp1O/guDL1F4v1dKU=; b=Zg9PvVcYtyK36IWuGPlk3xYX2RV7DJBbvtvmPTKXkSbOF35PRAK5KLwY/HriRVjyBs e5MWTqE0MuoNaoLGCzF3O98922wbUlz//ZwAoO4QMdRC0guScTuZI0wBgdl5WCuQ+Tza KDjyWCtxu5t6Q/KCAKietNyUqnZvt8Lj5YB/T1h9M/5TVn3ACRs8bwcQ8/NWPZTupXl7 L/POaf8PTJSsw0i26eagJaymnXwZHib4Tcqr8no6ekRLM94A+wOr4XseduEpWdClc8lf /cBsCAj3e1oMIicj2SBi+cIWf6VXzB6d7/ZJhNs6KTgAwenjOhjMzmooasLsFfdahjQ2 y8Qg== X-Gm-Message-State: AC+VfDwdWnQd6dKY+HcsW2tj9ho3F57cOgFvdsNzWmj1aYtJ04HRLlZW HgoDSO04+rqVOCOsyhVvtRmwQA== X-Google-Smtp-Source: ACHHUZ7JMEsSVoqIlBjE6pkY5JjMvLaZiehEFdZD2uDcVkyZJj0xmJh8G6Mir8ezq0lEU2wjPZzOhQ== X-Received: by 2002:a17:90a:9906:b0:23f:83de:7e4a with SMTP id b6-20020a17090a990600b0023f83de7e4amr31914390pjp.7.1684156707618; Mon, 15 May 2023 06:18:27 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.25 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:27 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 01/10] maple_tree: Drop the test code for mtree_alloc_{range,rrange}() Date: Mon, 15 May 2023 21:17:48 +0800 Message-Id: <20230515131757.60035-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Drop the test code for mtree_alloc_{range,rrange}() because we are going to drop them. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/test_maple_tree.c | 389 ------------------------------------------ 1 file changed, 389 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 9939be34e516e..86d7f742d243e 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -97,42 +97,6 @@ static void __init *mtree_test_erase(struct maple_tree *= mt, unsigned long index) return mtree_erase(mt, index); } =20 -#if defined(CONFIG_64BIT) -static noinline void __init check_mtree_alloc_range(struct maple_tree *mt, - unsigned long start, unsigned long end, unsigned long size, - unsigned long expected, int eret, void *ptr) -{ - - unsigned long result =3D expected + 1; - int ret; - - ret =3D mtree_alloc_range(mt, &result, ptr, size, start, end, - GFP_KERNEL); - MT_BUG_ON(mt, ret !=3D eret); - if (ret) - return; - - MT_BUG_ON(mt, result !=3D expected); -} - -static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt, - unsigned long start, unsigned long end, unsigned long size, - unsigned long expected, int eret, void *ptr) -{ - - unsigned long result =3D expected + 1; - int ret; - - ret =3D mtree_alloc_rrange(mt, &result, ptr, size, start, end, - GFP_KERNEL); - MT_BUG_ON(mt, ret !=3D eret); - if (ret) - return; - - MT_BUG_ON(mt, result !=3D expected); -} -#endif - static noinline void __init check_load(struct maple_tree *mt, unsigned long index, void *ptr) { @@ -635,348 +599,6 @@ static noinline void __init check_find_2(struct maple= _tree *mt) /*MT_BUG_ON(mt, !mtree_empty(mt)); */ } =20 - -#if defined(CONFIG_64BIT) -static noinline void __init check_alloc_rev_range(struct maple_tree *mt) -{ - /* - * Generated by: - * cat /proc/self/maps | awk '{print $1}'| - * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}' - */ - - static const unsigned long range[] =3D { - /* Inclusive , Exclusive. */ - 0x565234af2000, 0x565234af4000, - 0x565234af4000, 0x565234af9000, - 0x565234af9000, 0x565234afb000, - 0x565234afc000, 0x565234afd000, - 0x565234afd000, 0x565234afe000, - 0x565235def000, 0x565235e10000, - 0x7f36d4bfd000, 0x7f36d4ee2000, - 0x7f36d4ee2000, 0x7f36d4f04000, - 0x7f36d4f04000, 0x7f36d504c000, - 0x7f36d504c000, 0x7f36d5098000, - 0x7f36d5098000, 0x7f36d5099000, - 0x7f36d5099000, 0x7f36d509d000, - 0x7f36d509d000, 0x7f36d509f000, - 0x7f36d509f000, 0x7f36d50a5000, - 0x7f36d50b9000, 0x7f36d50db000, - 0x7f36d50db000, 0x7f36d50dc000, - 0x7f36d50dc000, 0x7f36d50fa000, - 0x7f36d50fa000, 0x7f36d5102000, - 0x7f36d5102000, 0x7f36d5103000, - 0x7f36d5103000, 0x7f36d5104000, - 0x7f36d5104000, 0x7f36d5105000, - 0x7fff5876b000, 0x7fff5878d000, - 0x7fff5878e000, 0x7fff58791000, - 0x7fff58791000, 0x7fff58793000, - }; - - static const unsigned long holes[] =3D { - /* - * Note: start of hole is INCLUSIVE - * end of hole is EXCLUSIVE - * (opposite of the above table.) - * Start of hole, end of hole, size of hole (+1) - */ - 0x565234afb000, 0x565234afc000, 0x1000, - 0x565234afe000, 0x565235def000, 0x12F1000, - 0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000, - }; - - /* - * req_range consists of 4 values. - * 1. min index - * 2. max index - * 3. size - * 4. number that should be returned. - * 5. return value - */ - static const unsigned long req_range[] =3D { - 0x565234af9000, /* Min */ - 0x7fff58791000, /* Max */ - 0x1000, /* Size */ - 0x7fff5878d << 12, /* First rev hole of size 0x1000 */ - 0, /* Return value success. */ - - 0x0, /* Min */ - 0x565234AF0 << 12, /* Max */ - 0x3000, /* Size */ - 0x565234AEE << 12, /* max - 3. */ - 0, /* Return value success. */ - - 0x0, /* Min */ - -1, /* Max */ - 0x1000, /* Size */ - 562949953421311 << 12,/* First rev hole of size 0x1000 */ - 0, /* Return value success. */ - - 0x0, /* Min */ - 0x7F36D5109 << 12, /* Max */ - 0x4000, /* Size */ - 0x7F36D5106 << 12, /* First rev hole of size 0x4000 */ - 0, /* Return value success. */ - - /* Ascend test. */ - 0x0, - 34148798628 << 12, - 19 << 12, - 34148797418 << 12, - 0x0, - - /* Too big test. */ - 0x0, - 18446744073709551615UL, - 562915594369134UL << 12, - 0x0, - -EBUSY, - - /* Single space test. */ - 34148798725 << 12, - 34148798725 << 12, - 1 << 12, - 34148798725 << 12, - 0, - }; - - int i, range_count =3D ARRAY_SIZE(range); - int req_range_count =3D ARRAY_SIZE(req_range); - unsigned long min =3D 0; - - MA_STATE(mas, mt, 0, 0); - - mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY, - GFP_KERNEL); -#define DEBUG_REV_RANGE 0 - for (i =3D 0; i < range_count; i +=3D 2) { - /* Inclusive, Inclusive (with the -1) */ - -#if DEBUG_REV_RANGE - pr_debug("\t%s: Insert %lu-%lu\n", __func__, range[i] >> 12, - (range[i + 1] >> 12) - 1); -#endif - check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1, - xa_mk_value(range[i] >> 12), 0); - mt_validate(mt); - } - - - mas_lock(&mas); - for (i =3D 0; i < ARRAY_SIZE(holes); i +=3D 3) { -#if DEBUG_REV_RANGE - pr_debug("Search from %lu-%lu for gap %lu should be at %lu\n", - min, holes[i+1]>>12, holes[i+2]>>12, - holes[i] >> 12); -#endif - MT_BUG_ON(mt, mas_empty_area_rev(&mas, min, - holes[i+1] >> 12, - holes[i+2] >> 12)); -#if DEBUG_REV_RANGE - pr_debug("Found %lu %lu\n", mas.index, mas.last); - pr_debug("gap %lu %lu\n", (holes[i] >> 12), - (holes[i+1] >> 12)); -#endif - MT_BUG_ON(mt, mas.last + 1 !=3D (holes[i+1] >> 12)); - MT_BUG_ON(mt, mas.index !=3D (holes[i+1] >> 12) - (holes[i+2] >> 12)); - min =3D holes[i+1] >> 12; - mas_reset(&mas); - } - - mas_unlock(&mas); - for (i =3D 0; i < req_range_count; i +=3D 5) { -#if DEBUG_REV_RANGE - pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\= n", - i, req_range[i] >> 12, - (req_range[i + 1] >> 12), - req_range[i+2] >> 12, - req_range[i+3] >> 12); -#endif - check_mtree_alloc_rrange(mt, - req_range[i] >> 12, /* start */ - req_range[i+1] >> 12, /* end */ - req_range[i+2] >> 12, /* size */ - req_range[i+3] >> 12, /* expected address */ - req_range[i+4], /* expected return */ - xa_mk_value(req_range[i] >> 12)); /* pointer */ - mt_validate(mt); - } - - mt_set_non_kernel(1); - mtree_erase(mt, 34148798727); /* create a deleted range. */ - mtree_erase(mt, 34148798725); - check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414, - 34148798725, 0, mt); - - mtree_destroy(mt); -} - -static noinline void __init check_alloc_range(struct maple_tree *mt) -{ - /* - * Generated by: - * cat /proc/self/maps|awk '{print $1}'| - * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}' - */ - - static const unsigned long range[] =3D { - /* Inclusive , Exclusive. */ - 0x565234af2000, 0x565234af4000, - 0x565234af4000, 0x565234af9000, - 0x565234af9000, 0x565234afb000, - 0x565234afc000, 0x565234afd000, - 0x565234afd000, 0x565234afe000, - 0x565235def000, 0x565235e10000, - 0x7f36d4bfd000, 0x7f36d4ee2000, - 0x7f36d4ee2000, 0x7f36d4f04000, - 0x7f36d4f04000, 0x7f36d504c000, - 0x7f36d504c000, 0x7f36d5098000, - 0x7f36d5098000, 0x7f36d5099000, - 0x7f36d5099000, 0x7f36d509d000, - 0x7f36d509d000, 0x7f36d509f000, - 0x7f36d509f000, 0x7f36d50a5000, - 0x7f36d50b9000, 0x7f36d50db000, - 0x7f36d50db000, 0x7f36d50dc000, - 0x7f36d50dc000, 0x7f36d50fa000, - 0x7f36d50fa000, 0x7f36d5102000, - 0x7f36d5102000, 0x7f36d5103000, - 0x7f36d5103000, 0x7f36d5104000, - 0x7f36d5104000, 0x7f36d5105000, - 0x7fff5876b000, 0x7fff5878d000, - 0x7fff5878e000, 0x7fff58791000, - 0x7fff58791000, 0x7fff58793000, - }; - static const unsigned long holes[] =3D { - /* Start of hole, end of hole, size of hole (+1) */ - 0x565234afb000, 0x565234afc000, 0x1000, - 0x565234afe000, 0x565235def000, 0x12F1000, - 0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000, - }; - - /* - * req_range consists of 4 values. - * 1. min index - * 2. max index - * 3. size - * 4. number that should be returned. - * 5. return value - */ - static const unsigned long req_range[] =3D { - 0x565234af9000, /* Min */ - 0x7fff58791000, /* Max */ - 0x1000, /* Size */ - 0x565234afb000, /* First hole in our data of size 1000. */ - 0, /* Return value success. */ - - 0x0, /* Min */ - 0x7fff58791000, /* Max */ - 0x1F00, /* Size */ - 0x0, /* First hole in our data of size 2000. */ - 0, /* Return value success. */ - - /* Test ascend. */ - 34148797436 << 12, /* Min */ - 0x7fff587AF000, /* Max */ - 0x3000, /* Size */ - 34148798629 << 12, /* Expected location */ - 0, /* Return value success. */ - - /* Test failing. */ - 34148798623 << 12, /* Min */ - 34148798683 << 12, /* Max */ - 0x15000, /* Size */ - 0, /* Expected location */ - -EBUSY, /* Return value failed. */ - - /* Test filling entire gap. */ - 34148798623 << 12, /* Min */ - 0x7fff587AF000, /* Max */ - 0x10000, /* Size */ - 34148798632 << 12, /* Expected location */ - 0, /* Return value success. */ - - /* Test walking off the end of root. */ - 0, /* Min */ - -1, /* Max */ - -1, /* Size */ - 0, /* Expected location */ - -EBUSY, /* Return value failure. */ - - /* Test looking for too large a hole across entire range. */ - 0, /* Min */ - -1, /* Max */ - 4503599618982063UL << 12, /* Size */ - 34359052178 << 12, /* Expected location */ - -EBUSY, /* Return failure. */ - - /* Test a single entry */ - 34148798648 << 12, /* Min */ - 34148798648 << 12, /* Max */ - 4096, /* Size of 1 */ - 34148798648 << 12, /* Location is the same as min/max */ - 0, /* Success */ - }; - int i, range_count =3D ARRAY_SIZE(range); - int req_range_count =3D ARRAY_SIZE(req_range); - unsigned long min =3D 0x565234af2000; - MA_STATE(mas, mt, 0, 0); - - mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY, - GFP_KERNEL); - for (i =3D 0; i < range_count; i +=3D 2) { -#define DEBUG_ALLOC_RANGE 0 -#if DEBUG_ALLOC_RANGE - pr_debug("\tInsert %lu-%lu\n", range[i] >> 12, - (range[i + 1] >> 12) - 1); - mt_dump(mt, mt_dump_hex); -#endif - check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1, - xa_mk_value(range[i] >> 12), 0); - mt_validate(mt); - } - - - - mas_lock(&mas); - for (i =3D 0; i < ARRAY_SIZE(holes); i +=3D 3) { - -#if DEBUG_ALLOC_RANGE - pr_debug("\tGet empty %lu-%lu size %lu (%lx-%lx)\n", min >> 12, - holes[i+1] >> 12, holes[i+2] >> 12, - min, holes[i+1]); -#endif - MT_BUG_ON(mt, mas_empty_area(&mas, min >> 12, - holes[i+1] >> 12, - holes[i+2] >> 12)); - MT_BUG_ON(mt, mas.index !=3D holes[i] >> 12); - min =3D holes[i+1]; - mas_reset(&mas); - } - mas_unlock(&mas); - for (i =3D 0; i < req_range_count; i +=3D 5) { -#if DEBUG_ALLOC_RANGE - pr_debug("\tTest %d: %lu-%lu size %lu expected %lu (%lu-%lu)\n", - i/5, req_range[i] >> 12, req_range[i + 1] >> 12, - req_range[i + 2] >> 12, req_range[i + 3] >> 12, - req_range[i], req_range[i+1]); -#endif - check_mtree_alloc_range(mt, - req_range[i] >> 12, /* start */ - req_range[i+1] >> 12, /* end */ - req_range[i+2] >> 12, /* size */ - req_range[i+3] >> 12, /* expected address */ - req_range[i+4], /* expected return */ - xa_mk_value(req_range[i] >> 12)); /* pointer */ - mt_validate(mt); -#if DEBUG_ALLOC_RANGE - mt_dump(mt, mt_dump_hex); -#endif - } - - mtree_destroy(mt); -} -#endif - static noinline void __init check_ranges(struct maple_tree *mt) { int i, val, val2; @@ -3448,17 +3070,6 @@ static int __init maple_tree_seed(void) check_ranges(&tree); mtree_destroy(&tree); =20 -#if defined(CONFIG_64BIT) - /* These tests have ranges outside of 4GB */ - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_alloc_range(&tree); - mtree_destroy(&tree); - - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_alloc_rev_range(&tree); - mtree_destroy(&tree); -#endif - mt_init_flags(&tree, 0); =20 check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */ --=20 2.20.1 From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B3EEBC77B75 for ; Mon, 15 May 2023 13:18:40 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242051AbjEONSj (ORCPT ); Mon, 15 May 2023 09:18:39 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36786 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241895AbjEONSd (ORCPT ); Mon, 15 May 2023 09:18:33 -0400 Received: from mail-pg1-x532.google.com (mail-pg1-x532.google.com [IPv6:2607:f8b0:4864:20::532]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4D66B1700 for ; Mon, 15 May 2023 06:18:31 -0700 (PDT) Received: by mail-pg1-x532.google.com with SMTP id 41be03b00d2f7-52c30fbccd4so11766043a12.0 for ; Mon, 15 May 2023 06:18:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156711; x=1686748711; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=7SqZWlsfkbxEd4BsTm1MhrUO1FrEvEzjaPkEdKk7VYI=; b=V4yvdebIzkZLzBXRdBJ/cqlNoldxsWjHV+VVk67DXhofASL/pQ6Sn/RCFW7Rit5oF5 eN76yVDQO2rdOlHRbBhgVTYaCnQ1mgf6eLRo++EXcdBEFpoZdNigL3UQaELWi1EcgsGX 8YiAsABMNMu0jqrcVUBl4HlHzlHsKYVVl1wNagcLVG6hQHBfBbhmDiC/Q7kYyweQ1At9 2RLHAfkffK1DlgF30rG5KAP7UaTjJ8Uhdtkv/Pw7AcWh6Y5OF6KOSZ4+Uqz9sEWdUWNA wQnD8S6lAFuhOojjwHM/Wfr84k66hoMehS9bhtXwct8hf+cerazoCuwks9SlHPlrwBqZ Bsrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156711; x=1686748711; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=7SqZWlsfkbxEd4BsTm1MhrUO1FrEvEzjaPkEdKk7VYI=; b=fhpiLqfRfbTJcgg0aySiqCJ2FMC58ZMIl++I+1jx37ZhKFad2hHTzKZIp+Ai909xb4 /0BoFLI+LP1IaSGx54bQxSpv9pqE/db+GIOPSPMcNEhXisPUFRllAI925WrkLErQIIdX 1yTVhc34IM+5vO+YjKmYGf7KmC+xbjx0olaj35GUtm7M8jKzUuiza8D8MH+xo6SbJ98N U48kWG2+YB0Lq87zns+YYmQPWeZgv4kcwSo2H4cTbLv/RtfPmAVdMimH6LimiD35mSp+ KRy3/goZPz13s+xCZ74sFMMN0+Ss3NZ5AWmeOseC8zNgbNMCHShqUGx3NT7fLHGSz2ra GU+g== X-Gm-Message-State: AC+VfDxhJ29YKp3bFt9Wbbu/FVLmvg3NK9wiS7r9TakJDTLQ06sHJqjy A2a2ze4Sac6aoZ+iOVgqpgQXQw== X-Google-Smtp-Source: ACHHUZ5o2obesVD5PMEZoRPcOhk0yxjhISRraF1Wv/wfPVSvpR0BGoHlgKqx3NWmD17MpLvIqgEwow== X-Received: by 2002:a17:90a:ee88:b0:247:13f5:47de with SMTP id i8-20020a17090aee8800b0024713f547demr32771298pjz.44.1684156710773; Mon, 15 May 2023 06:18:30 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.28 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:30 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 02/10] maple_tree: Drop mtree_alloc_{range,rrange}() and related functions. Date: Mon, 15 May 2023 21:17:49 +0800 Message-Id: <20230515131757.60035-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Drop mtree_alloc_{range,rrange}(), mas_{rev_}alloc() and mas_fill_gap(). mtree_alloc_{range,rrange}() currently have no users and can be easily implemented with mas_empty_area{_rev}(). mas_{rev_}alloc() and mas_fill_gap() are just their internal functions, drop them together. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- include/linux/maple_tree.h | 7 -- lib/maple_tree.c | 177 ------------------------------------- 2 files changed, 184 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 542b09118a09f..3dd6edccf83af 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -306,13 +306,6 @@ int mtree_insert(struct maple_tree *mt, unsigned long = index, void *entry, gfp_t gfp); int mtree_insert_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp); -int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, - void *entry, unsigned long size, unsigned long min, - unsigned long max, gfp_t gfp); -int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, - void *entry, unsigned long size, unsigned long min, - unsigned long max, gfp_t gfp); - int mtree_store_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp); int mtree_store(struct maple_tree *mt, unsigned long index, diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b37065a6f570d..49dfe81dfa1b6 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5120,46 +5120,6 @@ static inline void mas_awalk(struct ma_state *mas, u= nsigned long size) } } =20 -/* - * mas_fill_gap() - Fill a located gap with @entry. - * @mas: The maple state - * @entry: The value to store - * @slot: The offset into the node to store the @entry - * @size: The size of the entry - * @index: The start location - */ -static inline void mas_fill_gap(struct ma_state *mas, void *entry, - unsigned char slot, unsigned long size, unsigned long *index) -{ - MA_WR_STATE(wr_mas, mas, entry); - unsigned char pslot =3D mte_parent_slot(mas->node); - struct maple_enode *mn =3D mas->node; - unsigned long *pivots; - enum maple_type ptype; - /* - * mas->index is the start address for the search - * which may no longer be needed. - * mas->last is the end address for the search - */ - - *index =3D mas->index; - mas->last =3D mas->index + size - 1; - - /* - * It is possible that using mas->max and mas->min to correctly - * calculate the index and last will cause an issue in the gap - * calculation, so fix the ma_state here - */ - mas_ascend(mas); - ptype =3D mte_node_type(mas->node); - pivots =3D ma_pivots(mas_mn(mas), ptype); - mas->max =3D mas_safe_pivot(mas, pivots, pslot, ptype); - mas->min =3D mas_safe_min(mas, pivots, pslot); - mas->node =3D mn; - mas->offset =3D slot; - mas_wr_store_entry(&wr_mas); -} - /* * mas_sparse_area() - Internal function. Return upper or lower limit when * searching for a gap in an empty tree. @@ -5307,74 +5267,6 @@ int mas_empty_area_rev(struct ma_state *mas, unsigne= d long min, } EXPORT_SYMBOL_GPL(mas_empty_area_rev); =20 -static inline int mas_alloc(struct ma_state *mas, void *entry, - unsigned long size, unsigned long *index) -{ - unsigned long min; - - mas_start(mas); - if (mas_is_none(mas) || mas_is_ptr(mas)) { - mas_root_expand(mas, entry); - if (mas_is_err(mas)) - return xa_err(mas->node); - - if (!mas->index) - return mas_pivot(mas, 0); - return mas_pivot(mas, 1); - } - - /* Must be walking a tree. */ - mas_awalk(mas, size); - if (mas_is_err(mas)) - return xa_err(mas->node); - - if (mas->offset =3D=3D MAPLE_NODE_SLOTS) - goto no_gap; - - /* - * At this point, mas->node points to the right node and we have an - * offset that has a sufficient gap. - */ - min =3D mas->min; - if (mas->offset) - min =3D mas_pivot(mas, mas->offset - 1) + 1; - - if (mas_is_err(mas)) - return xa_err(mas->node); - - if (mas->index < min) - mas->index =3D min; - - mas_fill_gap(mas, entry, mas->offset, size, index); - return 0; - -no_gap: - return -EBUSY; -} - -static inline int mas_rev_alloc(struct ma_state *mas, unsigned long min, - unsigned long max, void *entry, - unsigned long size, unsigned long *index) -{ - int ret =3D 0; - - ret =3D mas_empty_area_rev(mas, min, max, size); - if (ret) - return ret; - - if (mas_is_err(mas)) - return xa_err(mas->node); - - if (mas->offset =3D=3D MAPLE_NODE_SLOTS) - goto no_gap; - - mas_fill_gap(mas, entry, mas->offset, size, index); - return 0; - -no_gap: - return -EBUSY; -} - /* * mte_dead_leaves() - Mark all leaves of a node as dead. * @mas: The maple state @@ -6481,75 +6373,6 @@ int mtree_insert(struct maple_tree *mt, unsigned lon= g index, void *entry, } EXPORT_SYMBOL(mtree_insert); =20 -int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, - void *entry, unsigned long size, unsigned long min, - unsigned long max, gfp_t gfp) -{ - int ret =3D 0; - - MA_STATE(mas, mt, min, min); - if (!mt_is_alloc(mt)) - return -EINVAL; - - if (WARN_ON_ONCE(mt_is_reserved(entry))) - return -EINVAL; - - if (min > max) - return -EINVAL; - - if (max < size) - return -EINVAL; - - if (!size) - return -EINVAL; - - mtree_lock(mt); -retry: - mas.offset =3D 0; - mas.index =3D min; - mas.last =3D max - size + 1; - ret =3D mas_alloc(&mas, entry, size, startp); - if (mas_nomem(&mas, gfp)) - goto retry; - - mtree_unlock(mt); - return ret; -} -EXPORT_SYMBOL(mtree_alloc_range); - -int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, - void *entry, unsigned long size, unsigned long min, - unsigned long max, gfp_t gfp) -{ - int ret =3D 0; - - MA_STATE(mas, mt, min, max - size + 1); - if (!mt_is_alloc(mt)) - return -EINVAL; - - if (WARN_ON_ONCE(mt_is_reserved(entry))) - return -EINVAL; - - if (min > max) - return -EINVAL; - - if (max < size - 1) - return -EINVAL; - - if (!size) - return -EINVAL; - - mtree_lock(mt); -retry: - ret =3D mas_rev_alloc(&mas, min, max, entry, size, startp); - if (mas_nomem(&mas, gfp)) - goto retry; - - mtree_unlock(mt); - return ret; -} -EXPORT_SYMBOL(mtree_alloc_rrange); - /** * mtree_erase() - Find an index and erase the entire range. * @mt: The maple tree --=20 2.20.1 From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id BBB3EC77B75 for ; Mon, 15 May 2023 13:19:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S241989AbjEONTJ (ORCPT ); Mon, 15 May 2023 09:19:09 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36856 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242126AbjEONTA (ORCPT ); Mon, 15 May 2023 09:19:00 -0400 Received: from mail-pf1-x42c.google.com (mail-pf1-x42c.google.com [IPv6:2607:f8b0:4864:20::42c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1BF5C19AE for ; Mon, 15 May 2023 06:18:34 -0700 (PDT) Received: by mail-pf1-x42c.google.com with SMTP id d2e1a72fcca58-64ab2a37812so19850730b3a.1 for ; Mon, 15 May 2023 06:18:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156713; x=1686748713; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=eE6bxJv4UCRwtMUAfojMihpw2t2wf00Glyx+cFFRLZY=; b=i/UBgAcvtHHk0md0xZxj0CroBxW4tMrmR2bdSTljlwKSLUD37aMCqdoB3xk08hTz8B ufwwpJ4/L8cFSKLhE/WqTszR14LYvDzpcrIs/zqzfddiaq+2m2lw0NJCccNrlxMYyUvJ z+6U/6D/Qxi0hOTLOqKuqc5SYDLXl3MalzJyFHBS690apJ25rDfSJMcS5XNL7Ad4MgoG 2ZruXFiyPzOqwMXcHF1dtyY9Ilkr7c+KJiyAfj3qLEGXNCE+n1yWwNIF9IM3kY5B2ipY kRutjohJOwPgYtotGv0CjxTX4YlT2ubdXf6t1Lx3YoAzu+mX2+WJ34qbuIwPJloqSmRd USGg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156713; x=1686748713; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=eE6bxJv4UCRwtMUAfojMihpw2t2wf00Glyx+cFFRLZY=; b=f/pnXCjAos5xuHFEOGX1ydddRn6H9dbJzfjsKitgOE9Sgu/86zdG8uFanMrerXk2Dp Juhx34Erm0c57HA7hemJSIcG+gE54CS3MCZV/NoVy/QteBfShOvoUuysJ1eGohxBG8a0 lO1QeojkBw1FdxNeF2CfNp0cRFvopbtwEsVcjiI2ABQx6qdG5L8NIaVCK8UT7XecA+3/ 3KUpuNXJVUE1sU9MKY918NzrNEz/rI/RhIJhS71jmJAi08tGyeup95B8g8xn8l18oqIu 0Ldi6vwbIBsONmcrGam2DTRat/gPNZ3y3Uoq1Vq+4GCeYmWTjCEygwgeIg0pd2NI/by9 s86g== X-Gm-Message-State: AC+VfDwm0mKftVx3yLAR2Nd1FElA6eGXoLvyQgEmcguPGo7ziXtcPDhj rkxEra/s+cyS9wY7Rjg0JkIR1g== X-Google-Smtp-Source: ACHHUZ4ax8TBpv+8pqbDdmKnaFXdcM8+Si6LkP9bFQfT0YYvQy8V42QO+LcbU93Ang12fqFYOt+cCQ== X-Received: by 2002:a17:90a:bb05:b0:250:af6d:bd7b with SMTP id u5-20020a17090abb0500b00250af6dbd7bmr22794048pjr.24.1684156713588; Mon, 15 May 2023 06:18:33 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.31 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:33 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 03/10] maple_tree: Remove __must_hold() which does not work Date: Mon, 15 May 2023 21:17:50 +0800 Message-Id: <20230515131757.60035-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" The arguments to __must_hold() seem to be wrong so they should not work, remove them. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 3 --- 1 file changed, 3 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 49dfe81dfa1b6..43a25d3042c1b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1752,7 +1752,6 @@ static inline void mas_adopt_children(struct ma_state= *mas, * leave the node (true) and handle the adoption and free elsewhere. */ static inline void mas_replace(struct ma_state *mas, bool advanced) - __must_hold(mas->tree->lock) { struct maple_node *mn =3D mas_mn(mas); struct maple_enode *old_enode; @@ -1792,7 +1791,6 @@ static inline void mas_replace(struct ma_state *mas, = bool advanced) * @child: the maple state to store the child. */ static inline bool mas_new_child(struct ma_state *mas, struct ma_state *ch= ild) - __must_hold(mas->tree->lock) { enum maple_type mt; unsigned char offset; @@ -6198,7 +6196,6 @@ EXPORT_SYMBOL_GPL(mas_erase); * Return: true on allocation, false otherwise. */ bool mas_nomem(struct ma_state *mas, gfp_t gfp) - __must_hold(mas->tree->lock) { if (likely(mas->node !=3D MA_ERROR(-ENOMEM))) { mas_destroy(mas); --=20 2.20.1 From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 72B49C77B7D for ; Mon, 15 May 2023 13:19:21 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242068AbjEONTT (ORCPT ); Mon, 15 May 2023 09:19:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36838 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242161AbjEONTB (ORCPT ); Mon, 15 May 2023 09:19:01 -0400 Received: from mail-pl1-x62e.google.com (mail-pl1-x62e.google.com [IPv6:2607:f8b0:4864:20::62e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EA3B21FC1 for ; Mon, 15 May 2023 06:18:36 -0700 (PDT) Received: by mail-pl1-x62e.google.com with SMTP id d9443c01a7336-1ab1b79d3a7so87373935ad.3 for ; Mon, 15 May 2023 06:18:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156716; x=1686748716; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=aUBDvQ6OxE85hUN75/9d6LlRGyHmdnE5erOpWtw5OfM=; b=h6Vztwd3Q0rJzgXIQWj9b7a7rcwv/TKvfWHjSn7rPgPVnAwzRGI2GP2i+o8GYuMB5E aFz5inFtgIpGyz7XUMKZ8NAGKJ2UwZd/ZzAsQAY/TwHMA4dDvZVjhcKJH8cmgzKa5Swx p7DSkm4BzQ79R2MDK7TXkdd1dZguunFOryYbs46vMi+egL28fjmiOO8jIrx4iOF7vr9i OKY+sLoB5kvFPjKxPj9sWkbW/s0CEXb2sziSUikSXgmAk/sgii1jOrPbYFVaMPRcUgCE xd68Wj7Am3v6yO7HSaTtRVlczCvuTvBSSnCmKeycX0FpAHhU7HQbnQ2JhGJPm6fRGUeY drcA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156716; x=1686748716; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=aUBDvQ6OxE85hUN75/9d6LlRGyHmdnE5erOpWtw5OfM=; b=Edon8czEWICPxWiLwf8eso8JOaeLsbcaxSq7EHN0nh+3zqwNlciC/rTfu1KfPi5H9v WFtCPujSVCfO5mEf1vO6yGpqnNP4UFZOYLvW5eDlD0g/Xp9Tno/PIdk3818tB7Ieg8q0 9tiENXLh9ij0D6lieECok3E+XjiuWALn8nMHFoGuzMIUPdyybjuduEq+eeGj5wwRI6Qc ss6b4PNEdCZLan9IVW7e0tM6FWj60w0N5+8EHlVRDA4/04VeS7xGjXDvrP/t7IwcbdMH qh880ygCdixQE1kmJkvOq0w8Cp22McMmXvB2RXuuYUE+veMreUR0PJwyFbTbHX7HVDxu P+mA== X-Gm-Message-State: AC+VfDzc0U1Bi8OyLo2CLum50FeQJCqM3YDW9uo4QnTPHJrIfYA2GuMw XmQ/D8CAJf7PXUsWpZtge4s1/g== X-Google-Smtp-Source: ACHHUZ6NrR5fyigxrygUBYxmthRBGrO6hqW7vNZiQJ/rNSdTeNHwNJLwR56D8E8MgAQzd/+5PFOylQ== X-Received: by 2002:a17:902:dace:b0:1ac:6e1f:d1bd with SMTP id q14-20020a170902dace00b001ac6e1fd1bdmr37436369plx.19.1684156716446; Mon, 15 May 2023 06:18:36 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.33 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:36 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 04/10] maple_tree: Simplify mas_is_span_wr() Date: Mon, 15 May 2023 21:17:51 +0800 Message-Id: <20230515131757.60035-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Make the code for detecting spanning writes more concise. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 36 +++++++++--------------------------- 1 file changed, 9 insertions(+), 27 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 43a25d3042c1b..fbb6efc40e576 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3728,41 +3728,23 @@ static bool mas_is_span_wr(struct ma_wr_state *wr_m= as) { unsigned long max; unsigned long last =3D wr_mas->mas->last; - unsigned long piv =3D wr_mas->r_max; enum maple_type type =3D wr_mas->type; void *entry =3D wr_mas->entry; =20 - /* Contained in this pivot */ - if (piv > last) + max =3D unlikely(ma_is_leaf(type)) ? wr_mas->mas->max : wr_mas->r_max; + if (last < max) { + /* Contained in this pivot or this leaf node */ return false; - - max =3D wr_mas->mas->max; - if (unlikely(ma_is_leaf(type))) { - /* Fits in the node, but may span slots. */ - if (last < max) - return false; - - /* Writes to the end of the node but not null. */ - if ((last =3D=3D max) && entry) - return false; - + } else if (last =3D=3D max) { /* - * Writing ULONG_MAX is not a spanning write regardless of the - * value being written as long as the range fits in the node. + * The last entry of leaf node cannot be NULL unless it is the + * rightmost node (writing ULONG_MAX), otherwise it spans slots. + * If this is not leaf node, detect spanning store wr walk. */ - if ((last =3D=3D ULONG_MAX) && (last =3D=3D max)) - return false; - } else if (piv =3D=3D last) { - if (entry) - return false; - - /* Detect spanning store wr walk */ - if (last =3D=3D ULONG_MAX) + if (entry || last =3D=3D ULONG_MAX) return false; } - - trace_ma_write(__func__, wr_mas->mas, piv, entry); - + trace_ma_write(__func__, wr_mas->mas, wr_mas->r_max, entry); return true; } =20 --=20 2.20.1 From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 08B47C77B75 for ; Mon, 15 May 2023 13:19:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242353AbjEONTa (ORCPT ); Mon, 15 May 2023 09:19:30 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37074 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242244AbjEONTG (ORCPT ); Mon, 15 May 2023 09:19:06 -0400 Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com [IPv6:2607:f8b0:4864:20::102e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 54C3410E7 for ; Mon, 15 May 2023 06:18:40 -0700 (PDT) Received: by mail-pj1-x102e.google.com with SMTP id 98e67ed59e1d1-250175762b8so11100595a91.1 for ; Mon, 15 May 2023 06:18:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156719; x=1686748719; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=sHW4PAZciOvQN8kO9ncypAlcJrM+C64frREEyy2mYLs=; b=RXRsj1EZsY6H5AtAWlNnNwgRH9USWx7rFebmnNSxWVp7B1o8CDstfKLsgde6nsABW+ pMXRGo37YS/kX6dHNMteA59tSoCGxbUBLZ6cO6Wq1ucLmJE1mXUSHZL5qT97ZRlk+fbJ YgjpDtflzI7axWqu49cUqsNwfPNMCiyD3qq/tywbO7P5f/mCdDy0qhzolJj52EcCpGAr GKc9dC3OBrqikC20SzF+ImqrLV8XP+pqYgT4oug34pP7t7GokRQqeHLdEQLgrABz7mAS Fw+7+talhdXjs4z04CsjkXHbdEZEdD1QbNbIUtQaIk+BveA94b6E915qmJKJ6sFUuUS/ qcvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156719; x=1686748719; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=sHW4PAZciOvQN8kO9ncypAlcJrM+C64frREEyy2mYLs=; b=GSIApPwJ7SZrRwH2MJsKEjqxx4PidutpiUwz+VxihY+ADgprG7ogY4D59jeb4HiEOY QNxYXGtp6hLnFr0FH6giqqDTXW59GPXdbAVYI3BZ+IcI88p8xaTj4iIgR73kOg710sce FgIqeTLPL3ioji7rV5d57hJsLfTj6lRrFl6sN6flDCPBPh2k1ryfb47gxOOoS4Zorkjt SGhCRTYdoSxRC/HVjQSthknSsjkUOpWP2SmHmLVC0joDMOT3FaWayKgs24EbQWs4aYcO 9TJObbApvC71yPaIzdwIP/8jPJ2NM3s6DUoJ9zZegvwt9I15IXEyJzlct+3rLBJNYZYL vTQQ== X-Gm-Message-State: AC+VfDxzR5r42foem8PSCxIUES2ikIA3VIb+uHvGk1HeMPdsRyT3QA0X aKIJ44wf5vbnmJYMKwA8g2KvvA== X-Google-Smtp-Source: ACHHUZ7OPPdtpNM7SISNyCX81ZSswrdvwKVdZipovJWKD+wJP3pDOfgQHFOEVjljfMa+hOjEX6q3Ig== X-Received: by 2002:a17:90b:3e81:b0:252:a0dc:7950 with SMTP id rj1-20020a17090b3e8100b00252a0dc7950mr13256790pjb.2.1684156719239; Mon, 15 May 2023 06:18:39 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.36 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:39 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 05/10] maple_tree: Make the code symmetrical in mas_wr_extend_null() Date: Mon, 15 May 2023 21:17:52 +0800 Message-Id: <20230515131757.60035-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Just make the code symmetrical to improve readability. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 26 ++++++++++++++------------ 1 file changed, 14 insertions(+), 12 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index fbb6efc40e576..4c649d75a4923 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4256,19 +4256,21 @@ static inline void mas_wr_extend_null(struct ma_wr_= state *wr_mas) { struct ma_state *mas =3D wr_mas->mas; =20 - if (mas->last < wr_mas->end_piv && !wr_mas->slots[wr_mas->offset_end]) + if (!wr_mas->slots[wr_mas->offset_end]) { + /* If this one is null, the next and prev are not */ mas->last =3D wr_mas->end_piv; - - /* Check next slot(s) if we are overwriting the end */ - if ((mas->last =3D=3D wr_mas->end_piv) && - (wr_mas->node_end !=3D wr_mas->offset_end) && - !wr_mas->slots[wr_mas->offset_end + 1]) { - wr_mas->offset_end++; - if (wr_mas->offset_end =3D=3D wr_mas->node_end) - mas->last =3D mas->max; - else - mas->last =3D wr_mas->pivots[wr_mas->offset_end]; - wr_mas->end_piv =3D mas->last; + } else { + /* Check next slot(s) if we are overwriting the end */ + if ((mas->last =3D=3D wr_mas->end_piv) && + (wr_mas->node_end !=3D wr_mas->offset_end) && + !wr_mas->slots[wr_mas->offset_end + 1]) { + wr_mas->offset_end++; + if (wr_mas->offset_end =3D=3D wr_mas->node_end) + mas->last =3D mas->max; + else + mas->last =3D wr_mas->pivots[wr_mas->offset_end]; + wr_mas->end_piv =3D mas->last; + } } =20 if (!wr_mas->content) { --=20 2.20.1 From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4B971C77B75 for ; Mon, 15 May 2023 13:20:01 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242150AbjEONUA (ORCPT ); Mon, 15 May 2023 09:20:00 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37374 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242098AbjEONTX (ORCPT ); Mon, 15 May 2023 09:19:23 -0400 Received: from mail-pg1-x536.google.com (mail-pg1-x536.google.com [IPv6:2607:f8b0:4864:20::536]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7FF9419A6 for ; Mon, 15 May 2023 06:18:42 -0700 (PDT) Received: by mail-pg1-x536.google.com with SMTP id 41be03b00d2f7-5208be24dcbso9137603a12.1 for ; Mon, 15 May 2023 06:18:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156722; x=1686748722; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=lo1IIZfKjDP5LNi0dc+D12owX90CR8s5tkIi0vNkd7U=; b=iRq9sScOWZTCRfloTGbziN9cAC64a11zOsNkjp+5c1soI+3pRGWoucKuYa0+afBrM9 KP8InFDQgvCjKmHotLh2wYIyXRzWHtTPq+Eu/2q4uz7EHQaV09LS/cg0LBz50XCOSenv 5TIATnqEPFgNUuV8mtQuISYyzUH0xhNubca3DObs4XwCQmcEhgMKj6lZoQBSaPM42/p3 ZPnakXFKNosi63bdx6zJYoyHGjOpg2rxmoG3YBjH17UsScQn6r/yNgXEZSpXMSaiPPvO sVodHaxkosK0wFyiC0Hn2X0gh8Q5Iww84zRZZ4k5Aa2XQix6BKn1naSGI7OW3PhFCTqn VtCw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156722; x=1686748722; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=lo1IIZfKjDP5LNi0dc+D12owX90CR8s5tkIi0vNkd7U=; b=YQpevQl3CrWyhZqUs/Cqo5sOMj1fDC0nuGdLKCJNbOOfX7DcND+7YtaVFXspvEdZ+B ILDHR7lRBwp3E65yUh05HZA8WbF607jvWhGvEpETth2AtxV78SOHavPOXC62d7CQDBI2 0RoEF37ZGb0cB67SxOlQwf3g2NGiuUS7+29Wn1LY+68kSpiDjEKWEPHXOgbASAAFTnrr F8xdPrLWsXoZyc/aQ7ttot8k8zn+PCGVd1MmRTxXkEv0WzqvDnnoAScNvZbb2IgnVkT7 3LyNaYxXv+wtk5rGTI2BP14BAMeDB1xP7CrFcz4p7nSRMCiayWG1oarK9UwYx0mNAw+Q 8j/w== X-Gm-Message-State: AC+VfDzINvCkH4VGeSYxYsJ2WbppwWeGG9rrJsG6igl8rEtP3/lqwGe4 N969vAr75tFAW0fCSwV5iuEUrg== X-Google-Smtp-Source: ACHHUZ6sqdEAVKXCZZzGT9Z6sL0SWer+AhnOXHqqOFRcuvjaqR338puxAj51isP5NagP+6F7tjxgTA== X-Received: by 2002:a17:90b:46cd:b0:250:6119:6c1f with SMTP id jx13-20020a17090b46cd00b0025061196c1fmr27787639pjb.19.1684156721988; Mon, 15 May 2023 06:18:41 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.39 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:41 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 06/10] maple_tree: Wrap the replace operation with an inline function. Date: Mon, 15 May 2023 21:17:53 +0800 Message-Id: <20230515131757.60035-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" To make mas_wr_modify() cleaner, wrap the replace operation with an inline function. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 21 +++++++++++++++------ 1 file changed, 15 insertions(+), 6 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4c649d75a4923..ce695adc670ec 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4288,6 +4288,19 @@ static inline void mas_wr_extend_null(struct ma_wr_s= tate *wr_mas) } } =20 +static inline bool mas_wr_replace(struct ma_wr_state *wr_mas) +{ + struct ma_state *mas =3D wr_mas->mas; + + if (wr_mas->r_min =3D=3D mas->index && wr_mas->r_max =3D=3D mas->last) { + rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); + if (!!wr_mas->entry ^ !!wr_mas->content) + mas_update_gap(mas); + return true; + } + return false; +} + static inline bool mas_wr_append(struct ma_wr_state *wr_mas) { unsigned char end =3D wr_mas->node_end; @@ -4347,13 +4360,9 @@ static inline void mas_wr_modify(struct ma_wr_state = *wr_mas) unsigned char node_size; struct ma_state *mas =3D wr_mas->mas; =20 - /* Direct replacement */ - if (wr_mas->r_min =3D=3D mas->index && wr_mas->r_max =3D=3D mas->last) { - rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); - if (!!wr_mas->entry ^ !!wr_mas->content) - mas_update_gap(mas); + /* Attempt to direct replace */ + if (mas_wr_replace(wr_mas)) return; - } =20 /* Attempt to append */ node_slots =3D mt_slots[wr_mas->type]; --=20 2.20.1 From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6B8BCC77B75 for ; Mon, 15 May 2023 13:19:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242296AbjEONTM (ORCPT ); Mon, 15 May 2023 09:19:12 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37394 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242153AbjEONTA (ORCPT ); Mon, 15 May 2023 09:19:00 -0400 Received: from mail-pj1-x102c.google.com (mail-pj1-x102c.google.com [IPv6:2607:f8b0:4864:20::102c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 56850213D for ; Mon, 15 May 2023 06:18:45 -0700 (PDT) Received: by mail-pj1-x102c.google.com with SMTP id 98e67ed59e1d1-24e25e2808fso11438619a91.0 for ; Mon, 15 May 2023 06:18:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156725; x=1686748725; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=IqadHapDxpeqihp1W5tQfDBPl6INO7/UDDkBv5UKJVo=; b=IeSw9vO+5tUCyqhG3uAeGFw3l+kw0p1+xquqjvHnxWcTDJpp+QiZkleh9ZA4o1vRFP LFFQ9RUFpkMznTFDy38B1W2fNinp8wPwPa1vtTRBHgSp5UQx6f2PLig0LbQE8kmt6nO2 QHifAX+73dgUs5UZCtQTdz+QmY/BG7O+cWyKNZ2SpAwB1jo34DRBYtzAt9oEuDSXwuyH FZBXRiFYlwH9i0Q+eZJosITIX0uZu/Fe1ibGzExVWrN66H/hxtWiiRn3gHzxcuvN2BUN iAM0kqw3LiFeiTNOMvkWinAY0QaMmwaZK+eQhVvcwmAFnAs1R0wdpBUmHRoT/A04NjMv 2I5w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156725; x=1686748725; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=IqadHapDxpeqihp1W5tQfDBPl6INO7/UDDkBv5UKJVo=; b=WVCw7CGITLrwLkGgjuwyoYSwhhH8OSV5562xvRf3n086cn9fEn2C6TH46HeDh2Uifb TYk1eIVvMd4bV1OSI7PLvdk3TQ4rFkOSF+eSsk6cET8ryDGOSdi6FzLL3XQUahKKs1wQ sHnC9Y9KWnXkVXmmeHHuTSOK9dCGK/QlgZ+JvCDXMYdyjf5UB0pbfxPzgxeHPUPKoGFH yQNJMcBBt6qCjX/as+cGuyGgwPN33jIxZPDw2iiVXlJb8HcxEXq6poqTUGgJ9+CM3tXL x+UQ53CudBTww2X4ulE5r700eNbS+A1S98CSP7XD+HMQAnWaitAyxrB9gj5CfaMCO3zk K5dA== X-Gm-Message-State: AC+VfDyFragYkG8oeBKcTtypEK540yy4qdY1R/JcDZNu3NSlOglkdFHi CkOaJHVoBIpFty9WHTCah0+wSg== X-Google-Smtp-Source: ACHHUZ7AvLcqhLLRsd3AKclUfZSzUVQ/4fh1rVvWJLa4GbZzqy5/Ip9c+kJ3AEJMnFSgRXXWzKoXXg== X-Received: by 2002:a17:90a:1fca:b0:250:d293:5d9d with SMTP id z10-20020a17090a1fca00b00250d2935d9dmr18534359pjz.43.1684156724763; Mon, 15 May 2023 06:18:44 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.42 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:44 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 07/10] maple_tree: Add mas_wr_new_end() to calculate new_end accurately Date: Mon, 15 May 2023 21:17:54 +0800 Message-Id: <20230515131757.60035-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" The previous new_end calculation is inaccurate, because it assumes that two new pivots must be added (this is inaccurate), and sometimes it will miss the fast path and enter the slow path. Add mas_wr_new_end() to accurately calculate new_end to make the conditions for entering the fast path more accurate. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 33 ++++++++++++++++++++++----------- 1 file changed, 22 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ce695adc670ec..20082ef8c396c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4301,6 +4301,20 @@ static inline bool mas_wr_replace(struct ma_wr_state= *wr_mas) return false; } =20 +static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) +{ + struct ma_state *mas =3D wr_mas->mas; + unsigned char new_end =3D wr_mas->node_end + 2; + + new_end -=3D wr_mas->offset_end - mas->offset; + if (wr_mas->r_min =3D=3D mas->index) + new_end--; + if (wr_mas->end_piv =3D=3D mas->last) + new_end--; + + return new_end; +} + static inline bool mas_wr_append(struct ma_wr_state *wr_mas) { unsigned char end =3D wr_mas->node_end; @@ -4356,25 +4370,22 @@ static void mas_wr_bnode(struct ma_wr_state *wr_mas) =20 static inline void mas_wr_modify(struct ma_wr_state *wr_mas) { - unsigned char node_slots; - unsigned char node_size; struct ma_state *mas =3D wr_mas->mas; + unsigned char new_end; =20 /* Attempt to direct replace */ if (mas_wr_replace(wr_mas)) return; =20 - /* Attempt to append */ - node_slots =3D mt_slots[wr_mas->type]; - node_size =3D wr_mas->node_end - wr_mas->offset_end + mas->offset + 2; - if (mas->max =3D=3D ULONG_MAX) - node_size++; - - /* slot and node store will not fit, go to the slow path */ - if (unlikely(node_size >=3D node_slots)) + /* + * new_end exceeds the size of the maple node and cannot enter the fast + * path. + */ + new_end =3D mas_wr_new_end(wr_mas); + if (new_end >=3D mt_slots[wr_mas->type]) goto slow_path; =20 - if (wr_mas->entry && (wr_mas->node_end < node_slots - 1) && + if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) && (mas->offset =3D=3D wr_mas->node_end) && mas_wr_append(wr_mas)) { if (!wr_mas->content || !wr_mas->entry) mas_update_gap(mas); --=20 2.20.1 From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id CF874C77B7D for ; Mon, 15 May 2023 13:20:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242200AbjEONUD (ORCPT ); Mon, 15 May 2023 09:20:03 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36728 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242238AbjEONT1 (ORCPT ); Mon, 15 May 2023 09:19:27 -0400 Received: from mail-pj1-x1035.google.com (mail-pj1-x1035.google.com [IPv6:2607:f8b0:4864:20::1035]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3BC6F2710 for ; Mon, 15 May 2023 06:18:48 -0700 (PDT) Received: by mail-pj1-x1035.google.com with SMTP id 98e67ed59e1d1-24dfc3c662eso8556481a91.3 for ; Mon, 15 May 2023 06:18:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156727; x=1686748727; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=qZYylnYxW+ETURaA5WORPRH9YUugjQDKMo5It+GAwgw=; b=DPCRZ8PeVk1ENmOw52Z4ScPAKBiBTNsBCVNhldQbntOjXs6YxIBoJg714Omnu0afA0 zLGyzQ1A5K2TjqjCmQzNeqSRW3COE5zPefIhvLUj/Crqmo8UwQUio/fNg0PgZcoBikON zVBn1YYEGaayJt5l73HdrrEcbmkQY77TbGi3x4JLLXEgnDL47DabM9MSP32oohkmterc GN47DENhqMPgATZtYIw24/XavgPj+Qgkwx07ymQGqty/GVBBeFDSpZj2AIWedhbl43SS JQkTuP1mYv/7GA3VbvoaGdzMSswSjyL84Y11OsgVsXxMg7pINKoAGiGJtOvgf780ZDTS A0tg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156727; x=1686748727; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=qZYylnYxW+ETURaA5WORPRH9YUugjQDKMo5It+GAwgw=; b=S37jNbh/gHIKWepEuSTya+XBcWW5ovfcz+w/VAdKzLA8T8R+mfGF0sr8v9SUO+8F4D FCD5PwTTLZNDlkuoY4/CxHaiAvtoDqesOgsatvOnGZ8FRRzVAlI2kf2NkYnaZ4OEW21D FdMcxlO+UCW3+R8NbrA3sb7aXW4zllC8FW9bXlzK2ByNT/MmNOJv6nzeqhFEKDTtWBMH c0Xlyct21DsRS7Ws0VI0zhdHEP/CLZ8nKjTsz5UYk2Q7cBmYOtiZHGH+I3aaiQe4jY+h zlUVCW7VL4tre3yswimP7m3C6+B5xAQYuOMz8Pvb9GRM1AKNalkf5twX+paEcn2b/hDW TmcQ== X-Gm-Message-State: AC+VfDz5kvSzuePcmaqLT5wpQkNARKmkW/JqCmVpEai1FNgjP196jIez SBxzrKJ64iUD5fSRNh8yQUqK7/bEssPdDlAg1QI= X-Google-Smtp-Source: ACHHUZ5C3a8EuB22F2PmBbCR3ZqQP/cE8EemzucBxOnJ66cgYoelctIkw/FI/byhP2XlRFxSjJgcXQ== X-Received: by 2002:a17:90b:3ec2:b0:250:ca6c:d7a8 with SMTP id rm2-20020a17090b3ec200b00250ca6cd7a8mr20083096pjb.29.1684156727502; Mon, 15 May 2023 06:18:47 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.45 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:47 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 08/10] maple_tree: Add comments and some minor cleanups to mas_wr_append() Date: Mon, 15 May 2023 21:17:55 +0800 Message-Id: <20230515131757.60035-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Add comment for mas_wr_append(), move mas_update_gap() into mas_wr_append(), and other cleanups to make mas_wr_modify() cleaner. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 52 ++++++++++++++++++++++++++++++++++++------------ 1 file changed, 39 insertions(+), 13 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 20082ef8c396c..538e49feafbe4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4315,6 +4315,31 @@ static inline unsigned char mas_wr_new_end(struct ma= _wr_state *wr_mas) return new_end; } =20 +/* + * mas_wr_append: Attempt to append + * @wr_mas: the maple write state + * + * Return: True if appended, false otherwise + * + * Case 1: + * r_min r_max/end_piv + * +-------+-------+ + * original range: | |offset | + * +-------+-------+ + * +---+ + * overwrite: | | + * +---+ + * index last + * Case 2: + * r_min r_max/end_piv + * +-------+-------+ + * original range: | |offset | + * +-------+-------+ + * +---+ + * overwrite: | | + * +---+ + * index last + */ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) { unsigned char end =3D wr_mas->node_end; @@ -4322,7 +4347,11 @@ static inline bool mas_wr_append(struct ma_wr_state = *wr_mas) struct ma_state *mas =3D wr_mas->mas; unsigned char node_pivots =3D mt_pivots[wr_mas->type]; =20 + if (!(mas->offset =3D=3D wr_mas->node_end)) + return false; + if ((mas->index !=3D wr_mas->r_min) && (mas->last =3D=3D wr_mas->r_max)) { + /* Case 1 */ if (new_end < node_pivots) wr_mas->pivots[new_end] =3D wr_mas->pivots[end]; =20 @@ -4330,13 +4359,10 @@ static inline bool mas_wr_append(struct ma_wr_state= *wr_mas) ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end); =20 rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry); - mas->offset =3D new_end; wr_mas->pivots[end] =3D mas->index - 1; - - return true; - } - - if ((mas->index =3D=3D wr_mas->r_min) && (mas->last < wr_mas->r_max)) { + mas->offset =3D new_end; + } else if ((mas->index =3D=3D wr_mas->r_min) && (mas->last < wr_mas->r_ma= x)) { + /* Case 2 */ if (new_end < node_pivots) wr_mas->pivots[new_end] =3D wr_mas->pivots[end]; =20 @@ -4346,10 +4372,13 @@ static inline bool mas_wr_append(struct ma_wr_state= *wr_mas) =20 wr_mas->pivots[end] =3D mas->last; rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); - return true; + } else { + return false; } =20 - return false; + if (!wr_mas->content || !wr_mas->entry) + mas_update_gap(mas); + return true; } =20 /* @@ -4385,12 +4414,9 @@ static inline void mas_wr_modify(struct ma_wr_state = *wr_mas) if (new_end >=3D mt_slots[wr_mas->type]) goto slow_path; =20 - if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) && - (mas->offset =3D=3D wr_mas->node_end) && mas_wr_append(wr_mas)) { - if (!wr_mas->content || !wr_mas->entry) - mas_update_gap(mas); + /* Attempt to append */ + if (new_end =3D=3D wr_mas->node_end + 1 && mas_wr_append(wr_mas)) return; - } =20 if ((wr_mas->offset_end - mas->offset <=3D 1) && mas_wr_slot_store(wr_mas= )) return; --=20 2.20.1 From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 68D68C77B75 for ; Mon, 15 May 2023 13:19:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242269AbjEONTd (ORCPT ); Mon, 15 May 2023 09:19:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37388 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241911AbjEONTG (ORCPT ); Mon, 15 May 2023 09:19:06 -0400 Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com [IPv6:2607:f8b0:4864:20::102e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 93C642737 for ; Mon, 15 May 2023 06:18:50 -0700 (PDT) Received: by mail-pj1-x102e.google.com with SMTP id 98e67ed59e1d1-250175762b8so11100748a91.1 for ; Mon, 15 May 2023 06:18:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156730; x=1686748730; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=9RjXFpMPucyoGVPKV00U7wCkXQqL8U9B4PmEKn2WMSk=; b=g3X23mAk6kwEgqva0ZnSNN22eZiDL8T82so2num2UEwvQuEHuuabGkvETt7Q66yOlo 7sCxUGlSRdfbawSg3H0s/f5vwrXh9sR2wEApaj6MSgjyAGwixK4D0O2KZEF4rn3SMhPa 7odAfMZB0Nola4ha7jDUcXu/FzIHyu115GV8+4COEOE7VZVh9PVShj6IGKWcE/s5HgMV KcnfgrjKV4nHeILCPRy5qr06r+9wwiHpSwWOiSSOdk9njUM6w2RMr9csBkiWBy2Zh6OQ WZBKoSB8Mo2MD6Aozp/k5sI8+7i4+WxTVhsda+0VLxHL046q2kNIfpbtrRezaW6YALmf VZsQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156730; x=1686748730; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=9RjXFpMPucyoGVPKV00U7wCkXQqL8U9B4PmEKn2WMSk=; b=GYh9yXhV+6yzCUSMzUMeCkj/SvLGyutkv4vxtynYbvLjr7fTCkNHTIThmhHo5YOWn1 pRng1uwOvzQWFdTZvGc4l1mvHNCWL0wbC8sAJn9LsQYPZHoEKOy4ibDhC2Dt6ukgHb9u /SVnKnCES4ow8uwMDxvBWqU8jiMlV6Hu31OFg0XqmXfmnuM5vhL0BO1DoBu4sXWT4bmD 8igv7zsjpQuL478vPPypnqvNA/Y39qsKf5uw6AeOynfhedimCACTTdhTnbEwp7SQfBr+ 6HLAs5qtxTuvxSp6D6Kl04C7boQcwuF+z+EcMU1bJdsimbAZd2flnaOhrtPeSrJRxlgN 1xNg== X-Gm-Message-State: AC+VfDzCOOJLiUE7BAIZX+YUCF4mvuxKwsvkRiSxDLaq1TdcgjPygvL5 5J3U2xMoqfJszKrscOtrLEhTwQ== X-Google-Smtp-Source: ACHHUZ5n5S0O2+y/OHwn/QDCzc28Z/yx4dDmMDqn2V1pFtwTJV3ORG2KtE90A+CWdcAodTDHpHLsbA== X-Received: by 2002:a17:90a:cb93:b0:250:939f:70a0 with SMTP id a19-20020a17090acb9300b00250939f70a0mr24132189pju.14.1684156730303; Mon, 15 May 2023 06:18:50 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.47 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:50 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 09/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient. Date: Mon, 15 May 2023 21:17:56 +0800 Message-Id: <20230515131757.60035-10-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" The code of mas_wr_slot_store() is messy, make it clearer and concise, and add comments. In addition, get whether the two gaps are empty to avoid calling mas_update_gap() all the time. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 79 +++++++++++++++++++++++++++--------------------- 1 file changed, 44 insertions(+), 35 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 538e49feafbe4..d558e7bcb6da8 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4190,53 +4190,62 @@ static inline bool mas_wr_node_store(struct ma_wr_s= tate *wr_mas) * @wr_mas: the maple write state * * Return: True if stored, false otherwise + * + * Case 1: + * r_min r_max lmax + * +-------+-------+-------+ + * original range: | |offset | end | + * +-----------------------+ + * +-----------+ + * overwrite: | | + * +-----------+ + * index last + * + * Case 2: + * r_min r_max lmax + * +-------+-------+-------+ + * original range: | |offest | end | + * +-------+---------------+ + * +-----------+ + * overwrite: | | + * +-----------+ + * index last */ static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas) { struct ma_state *mas =3D wr_mas->mas; - unsigned long lmax; /* Logical max. */ unsigned char offset =3D mas->offset; + unsigned char offset_end =3D wr_mas->offset_end; + unsigned long lmax =3D wr_mas->end_piv; /* Logical max. */ + bool gap =3D false; =20 - if ((wr_mas->r_max > mas->last) && ((wr_mas->r_min !=3D mas->index) || - (offset !=3D wr_mas->node_end))) - return false; - - if (offset =3D=3D wr_mas->node_end - 1) - lmax =3D mas->max; - else - lmax =3D wr_mas->pivots[offset + 1]; - - /* going to overwrite too many slots. */ - if (lmax < mas->last) + if (offset_end - offset !=3D 1) return false; =20 - if (wr_mas->r_min =3D=3D mas->index) { - /* overwriting two or more ranges with one. */ - if (lmax =3D=3D mas->last) - return false; - - /* Overwriting all of offset and a portion of offset + 1. */ + if (mas->index =3D=3D wr_mas->r_min && mas->last < lmax) { + /* Case 1 */ + gap |=3D !mt_slot_locked(mas->tree, wr_mas->slots, offset); + gap |=3D !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1); rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry); wr_mas->pivots[offset] =3D mas->last; - goto done; - } - - /* Doesn't end on the next range end. */ - if (lmax !=3D mas->last) + } else if (mas->index > wr_mas->r_min && mas->last =3D=3D lmax) { + /* Case 2 */ + gap |=3D !mt_slot_locked(mas->tree, wr_mas->slots, offset); + gap |=3D !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1); + rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry); + wr_mas->pivots[offset] =3D mas->index - 1; + mas->offset++; /* Keep mas accurate. */ + } else { return false; + } =20 - /* Overwriting a portion of offset and all of offset + 1 */ - if ((offset + 1 < mt_pivots[wr_mas->type]) && - (wr_mas->entry || wr_mas->pivots[offset + 1])) - wr_mas->pivots[offset + 1] =3D mas->last; - - rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry); - wr_mas->pivots[offset] =3D mas->index - 1; - mas->offset++; /* Keep mas accurate. */ - -done: trace_ma_write(__func__, mas, 0, wr_mas->entry); - mas_update_gap(mas); + /* + * Only update gap when the new entry is empty or there is an empty + * entry in the original two ranges. + */ + if (!wr_mas->entry || gap) + mas_update_gap(mas); return true; } =20 @@ -4418,7 +4427,7 @@ static inline void mas_wr_modify(struct ma_wr_state *= wr_mas) if (new_end =3D=3D wr_mas->node_end + 1 && mas_wr_append(wr_mas)) return; =20 - if ((wr_mas->offset_end - mas->offset <=3D 1) && mas_wr_slot_store(wr_mas= )) + if (new_end =3D=3D wr_mas->node_end && mas_wr_slot_store(wr_mas)) return; else if (mas_wr_node_store(wr_mas)) return; --=20 2.20.1 From nobody Mon Feb 9 08:29:52 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id F235BC77B75 for ; Mon, 15 May 2023 13:20:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242285AbjEONUH (ORCPT ); Mon, 15 May 2023 09:20:07 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37554 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241917AbjEONTb (ORCPT ); Mon, 15 May 2023 09:19:31 -0400 Received: from mail-pf1-x429.google.com (mail-pf1-x429.google.com [IPv6:2607:f8b0:4864:20::429]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A42E82D4F for ; Mon, 15 May 2023 06:18:53 -0700 (PDT) Received: by mail-pf1-x429.google.com with SMTP id d2e1a72fcca58-643b7b8f8ceso7258939b3a.1 for ; Mon, 15 May 2023 06:18:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156733; x=1686748733; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=ArSLVUhdR9DQTTW/HQ0w3hLWCHQGeUGpXjVNbpJHsbw=; b=OY1tnyrNCLJ8dOnmp29AF4fQG0LVxASZn702ct1srPN3WTfsxFNCBRYdQLYwc6kuWt o70JfEDVIFUdVdNeIH/jJPOcRv9jEbVvhWXHoX+VGSuoQzE4KAv2rLMaD5HqYeqThYB2 leU3yXWK2fpP4YQP7Nl4A6y2ls2C4xj20yTIY9f5SnUx6QaV0HKLQbNCKwV3+/ZHg3bn hwgtpNiJfKbcLKuvi/rJSfuqMI3aUr0+XWuap/hwlD0We5HkP++9q+9T/JB7ZhTWl5TL 0NSOdoksiwNTnC1LHb060N3xyPjGvo8Xmw6pLH5YEXuU+R3+mn9q+We4wQvInISp/lEs cKzw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156733; x=1686748733; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=ArSLVUhdR9DQTTW/HQ0w3hLWCHQGeUGpXjVNbpJHsbw=; b=AwULWNdhoIdTKo/BFbXsVKRCR9Pi2gE4qID6MZYdf5ovfeI0DQC0vla39JZ+lBurmE a9CbhSx5Yu2ucjI7d259GJ/Q2O1YsyaUQmLB2LUiYYfUcGt0/VtoxvJpuqiOq9os37qx ij3aos9U5LWo25zedeUTAoOa3gqcwKjFfoGjOtN37facE3aqRn2PuQbleoweBY8mJ6HN 5jVdgkek+TaFh07RNW0vlKlgDdmnD1SVeUmwiYG8oln/sUGR5xdTjUE36xTilAtNAabF 4JPhE4uU8BI2KAPqyFt1FfPF2hX0JEirE1eNkoC/RJfTWPI9eB80nQvIDCsslXlC1KMi nHOg== X-Gm-Message-State: AC+VfDz70fVPTfiMl467lialtL1RXGKdEb1pm6DS5B7W7l5QB8o0BOJm HPLHq8/prueQJny9tzbjX+ETuyznbBjCnxR5vGU= X-Google-Smtp-Source: ACHHUZ6YT7KoeQeNgm4bcB4ACN2DGOZvEt8Ia9xhmqJ46OkY/eCRFO8DvWR5h4sWDKWbrM68M9ETbg== X-Received: by 2002:a05:6a20:1448:b0:105:55a7:d5ff with SMTP id a8-20020a056a20144800b0010555a7d5ffmr8063212pzi.28.1684156733094; Mon, 15 May 2023 06:18:53 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.50 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:52 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 10/10] maple_tree: Simplify and clean up mas_wr_node_store() Date: Mon, 15 May 2023 21:17:57 +0800 Message-Id: <20230515131757.60035-11-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Simplify and clean up mas_wr_node_store(), remove unnecessary code. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 75 +++++++++++++----------------------------------- 1 file changed, 20 insertions(+), 55 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d558e7bcb6da8..ff4aa01cf88b6 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4066,46 +4066,21 @@ static inline int mas_wr_spanning_store(struct ma_w= r_state *wr_mas) * * Return: True if stored, false otherwise */ -static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas) +static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas, + unsigned char new_end) { struct ma_state *mas =3D wr_mas->mas; void __rcu **dst_slots; unsigned long *dst_pivots; unsigned char dst_offset; - unsigned char new_end =3D wr_mas->node_end; - unsigned char offset; - unsigned char node_slots =3D mt_slots[wr_mas->type]; struct maple_node reuse, *newnode; - unsigned char copy_size, max_piv =3D mt_pivots[wr_mas->type]; + unsigned char copy_size, node_pivots =3D mt_pivots[wr_mas->type]; bool in_rcu =3D mt_in_rcu(mas->tree); =20 - offset =3D mas->offset; - if (mas->last =3D=3D wr_mas->r_max) { - /* runs right to the end of the node */ - if (mas->last =3D=3D mas->max) - new_end =3D offset; - /* don't copy this offset */ + if (mas->last =3D=3D wr_mas->end_piv) wr_mas->offset_end++; - } else if (mas->last < wr_mas->r_max) { - /* new range ends in this range */ - if (unlikely(wr_mas->r_max =3D=3D ULONG_MAX)) - mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type); - - new_end++; - } else { - if (wr_mas->end_piv =3D=3D mas->last) - wr_mas->offset_end++; - - new_end -=3D wr_mas->offset_end - offset - 1; - } - - /* new range starts within a range */ - if (wr_mas->r_min < mas->index) - new_end++; - - /* Not enough room */ - if (new_end >=3D node_slots) - return false; + else if (unlikely(wr_mas->r_max =3D=3D ULONG_MAX)) + mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type); =20 /* Not enough data. */ if (!mte_is_root(mas->node) && (new_end <=3D mt_min_slots[wr_mas->type]) = && @@ -4128,47 +4103,36 @@ static inline bool mas_wr_node_store(struct ma_wr_s= tate *wr_mas) dst_pivots =3D ma_pivots(newnode, wr_mas->type); dst_slots =3D ma_slots(newnode, wr_mas->type); /* Copy from start to insert point */ - memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1)); - memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1)); - dst_offset =3D offset; + memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset); + memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset); =20 /* Handle insert of new range starting after old range */ if (wr_mas->r_min < mas->index) { - mas->offset++; - rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content); - dst_pivots[dst_offset++] =3D mas->index - 1; + rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content); + dst_pivots[mas->offset++] =3D mas->index - 1; } =20 /* Store the new entry and range end. */ - if (dst_offset < max_piv) - dst_pivots[dst_offset] =3D mas->last; - mas->offset =3D dst_offset; - rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry); + if (mas->offset < node_pivots) + dst_pivots[mas->offset] =3D mas->last; + rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry); =20 /* * this range wrote to the end of the node or it overwrote the rest of * the data */ - if (wr_mas->offset_end > wr_mas->node_end || mas->last >=3D mas->max) { - new_end =3D dst_offset; + if (wr_mas->offset_end > wr_mas->node_end) goto done; - } =20 - dst_offset++; + dst_offset =3D mas->offset + 1; /* Copy to the end of node if necessary. */ copy_size =3D wr_mas->node_end - wr_mas->offset_end + 1; memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end, sizeof(void *) * copy_size); - if (dst_offset < max_piv) { - if (copy_size > max_piv - dst_offset) - copy_size =3D max_piv - dst_offset; + memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end, + sizeof(unsigned long) * (copy_size - 1)); =20 - memcpy(dst_pivots + dst_offset, - wr_mas->pivots + wr_mas->offset_end, - sizeof(unsigned long) * copy_size); - } - - if ((wr_mas->node_end =3D=3D node_slots - 1) && (new_end < node_slots - 1= )) + if (new_end < node_pivots) dst_pivots[new_end] =3D mas->max; =20 done: @@ -4429,7 +4393,8 @@ static inline void mas_wr_modify(struct ma_wr_state *= wr_mas) =20 if (new_end =3D=3D wr_mas->node_end && mas_wr_slot_store(wr_mas)) return; - else if (mas_wr_node_store(wr_mas)) + + if (mas_wr_node_store(wr_mas, new_end)) return; =20 if (mas_is_err(mas)) --=20 2.20.1