From patchwork Mon May 15 13:17:48 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241436 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 B5032C77B75 for ; Mon, 15 May 2023 13:18:33 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2AD01900002; Mon, 15 May 2023 09:18:33 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 25E50280001; Mon, 15 May 2023 09:18:33 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 124DF900005; Mon, 15 May 2023 09:18:33 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id ECA41900002 for ; Mon, 15 May 2023 09:18:32 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 968BA120FA4 for ; Mon, 15 May 2023 13:18:32 +0000 (UTC) X-FDA: 80792543664.07.DDD43E9 Received: from mail-pg1-f179.google.com (mail-pg1-f179.google.com [209.85.215.179]) by imf26.hostedemail.com (Postfix) with ESMTP id 96950140016 for ; Mon, 15 May 2023 13:18:30 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=iH5wFnjA; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156710; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=EveqtihCJt7fcxXdeINag7+zgOnp1O/guDL1F4v1dKU=; b=cBGIzXBG8AYHQUtODr6+bDfYzEDXXkJxep3DvxJcNM7sUJ2WZk0BDJe/lP5J6qHwNMGJof 2NBj7Ms4QynrJnI7elxFG/ezlOwsIO85lqh6ld+DFgcFJhvzhrKnbypuleppI+DInXuwQ/ TnBzZl5dJ7Y6fD0qAflNVkLudzs8Ng0= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156710; a=rsa-sha256; cv=none; b=lgxBhHaPpWrElvJC2yspRy0w1idcuJBYi7Kk6+naryFIo3mwlZBCa+MIHLMoLU7DpmQ29f IH/O9dAnY5OgKtgpNMlQjbgzCF0HwpsQl2HIwSFts3qeWyKUPM+Xt6zqOov/Ofj5AbwdAr Gkyu/WclAi6JWQEFFJoWpYaWBVmns+8= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=iH5wFnjA; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pg1-f179.google.com with SMTP id 41be03b00d2f7-53033a0b473so6211226a12.0 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=IprYp2MEKp4EOclELPZG2Cm56vxMQTzNL1AT0GXETn1aEWlnWU5mBZAYod+JhQPypW JT7zU/hG+X5Cw7OUnp1a+43CpGfhfFZNQJB624mVZEIuDoqBU+SjTSI97BzjO0PIQIUj CcMK807Di/9mEXLDI02nleFAolfW/rdIDfSJtxPKtj0y6W03bNEEVMUkbxkA+1u+K0mT ofIkYFKxu3rJrhOltKrcMU1ZtZvbhq9ZWk+1hgNolWAAdCuOqCJUTdVaEQcfFP+XjW/w cpNgPz1QagKThIw3u2y+xGNG3HOptmE2RX4FWC086qY0hPdxzVDrNhkWNcha3cNUiuxi oWmA== X-Gm-Message-State: AC+VfDxtRsiGdau9xKytk4At03XJYP67Ld2PbpMfoMeItPhajq9/+hgv AwOLoQvnxUHMOx4wJ+qGzxdgBw== 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 X-Rspamd-Queue-Id: 96950140016 X-Rspam-User: X-Rspamd-Server: rspam06 X-Stat-Signature: p8a88k7eurhh4djj8cfogw76axjhgmta X-HE-Tag: 1684156710-121926 X-HE-Meta: U2FsdGVkX188sZx7niZvhd5lB/OipUl2Wb6X9XyTgLG2HnoKg8+Wp4kkx2jwV3IZwgZXI1OYCbxeFzg7RVKxlIfIBIT+bFpz24vbgsOOBVF7b1ExVq0u/ZIotXV0OqJ0Ba02xeCvna8I1gm/8HAr9sUSrufFp3D4/jVGvWGY8pACWi6t/ovJM49PQHEDwWuYO6AeziW0mkhJUTK+iF2sIDa06nWMjK8U706ICIheeYEKSYwdw8oWrSrWFBWw5xeL/fthgSaDd06sDaGLPHCR0rGCJGhuPQL0/PYAzzIiflLfX10LFX7ilaUy6HMyWJ9epjDdqO1x2TIM8/bZTzFwcJiZRXtH5kuJLJrR8gVSpVraJC0y8WJ5tWGZkDsXw4C149qPQAes5QK4dysfUwYcAz+nLq0aZCxAuivQjVep/QGeGWWx9BiPgWif6y8qTNM97AHDoQuqXy4bt9nXhDfFNLsWqLxyya+n3CnsQnZyo4IBJ2QZhNeRHEQNYJj12pdG/59VgnqbLXVOodBBEZdbgty6fywZ2s1TNSc1/a5hWAupj03ueycciL7ThW/bg3h+OXsHIO6yLhQmhF5JVv634+dGU/rlOXVlxggjA97SlKZTCIXLV8egBM7kWTfu5324nonopUABv8mz3iZYHHcRDeftue748wr6b4D1DTdYDamAvzKhVRaT2WjsAIlh0RG+JOlQfmDrsxcct5crRh1GRAZBSqOokiDzDzmtvSRmWjYxgNruOE+rW0+KJTEAwLH0YbST16BCVfY1ytS3PdY0jZo2NI6yfTuWWY6H4dJhEEcr+HQqcGcK7aKE93iVARCaH/cbARv/IBfrOs3LjtLHZY7nxFk6d3RWGFk+4OmFkI1wmwGRZD7DSinqPHnqpl0h54fX1hR6pOk2U6XKu48K5lGNkRtbbGCem0Gvp+s9AOjW7ChWJ7ZSSfvoErbk4xrZGPKAsyZSGoxSYDMEClY 4XlN7OwY z86HlSb1gMCXmjcmffgh9bDgfQliC4e9ACcdeYf3xauO6geqb5DuXDPMVQLtw5yjxmItd5o93OVPOKkMl0AOKo+Jh8v/Xz1KTlY8J0UK3khq3hwTkAJSoSYXBWX5ctW/waXTofvwGsxQoMd48i6x7raROt5H18yUEzfc1rMBA7grQ1StzkhCWIrvAvMsPW7JaHuE0KA0+i+ixfTlJBygqQibtBxilRanj5tL3SsWaqPJgmFQa5sDJIwVf2iiwiAHONAjYic6r9y70PtnvDK8YZHOcDqUM+Nvu+B8zw8NVqPO8SXvTokd6oeqGGxzE6uZLFf5hPMOMN81uEIUjRMpuTEG/7zugS8XyI+3hi66XGky/FV8sTJd+3VmqYeVP+gB3d+nPAkeuCZ2FryecP74N67gfHnCYwwqMcQjPNm3QsJLvxiJVWkTBLK8IGMjJp5M30E4LVJe3Fqwm3J4= 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: 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); } -#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 = expected + 1; - int ret; - - ret = mtree_alloc_range(mt, &result, ptr, size, start, end, - GFP_KERNEL); - MT_BUG_ON(mt, ret != eret); - if (ret) - return; - - MT_BUG_ON(mt, result != 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 = expected + 1; - int ret; - - ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end, - GFP_KERNEL); - MT_BUG_ON(mt, ret != eret); - if (ret) - return; - - MT_BUG_ON(mt, result != 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)); */ } - -#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[] = { - /* 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[] = { - /* - * 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[] = { - 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 = ARRAY_SIZE(range); - int req_range_count = ARRAY_SIZE(req_range); - unsigned long min = 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 = 0; i < range_count; i += 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 = 0; i < ARRAY_SIZE(holes); i += 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 != (holes[i+1] >> 12)); - MT_BUG_ON(mt, mas.index != (holes[i+1] >> 12) - (holes[i+2] >> 12)); - min = holes[i+1] >> 12; - mas_reset(&mas); - } - - mas_unlock(&mas); - for (i = 0; i < req_range_count; i += 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[] = { - /* 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[] = { - /* 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[] = { - 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 = ARRAY_SIZE(range); - int req_range_count = ARRAY_SIZE(req_range); - unsigned long min = 0x565234af2000; - MA_STATE(mas, mt, 0, 0); - - mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY, - GFP_KERNEL); - for (i = 0; i < range_count; i += 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 = 0; i < ARRAY_SIZE(holes); i += 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 != holes[i] >> 12); - min = holes[i+1]; - mas_reset(&mas); - } - mas_unlock(&mas); - for (i = 0; i < req_range_count; i += 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); -#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); check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */ From patchwork Mon May 15 13:17:49 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241437 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 2B621C77B7D for ; Mon, 15 May 2023 13:18:35 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9B220280002; Mon, 15 May 2023 09:18:34 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 96127280001; Mon, 15 May 2023 09:18:34 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7B485280002; Mon, 15 May 2023 09:18:34 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 6199D280001 for ; Mon, 15 May 2023 09:18:34 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 20690AE4A2 for ; Mon, 15 May 2023 13:18:34 +0000 (UTC) X-FDA: 80792543748.23.05B9CFE Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) by imf21.hostedemail.com (Postfix) with ESMTP id ECED01C0015 for ; Mon, 15 May 2023 13:18:31 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=V4yvdebI; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156712; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=7SqZWlsfkbxEd4BsTm1MhrUO1FrEvEzjaPkEdKk7VYI=; b=Ttde982GzRoX3DNOaLEkkH4kURNc73GW3quWgdOiSpFPj+COzq9EeCzFYyi7vMtXToy2cy LiFbSFHyU+Qw8Ml0TOyPcatjgRD8sEvSOr/ZSM1hVxSRrGQ7Xen2MmJAcSDW2A3H25gLx6 aBEJanu/CQ2krZ33MVJz0nCUWTTp/rU= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156712; a=rsa-sha256; cv=none; b=mKUsDgzyKZCNbHKKqnD/SJqbEhQZa8RiKbISLqYTqAYmgVMW6NuV9xP5n/ezu/WA1V39bV HD4Bgv16ohGONM4c4nbt6JN11mD/Nk71M9RNjbwIdG47mgBDBE706D/h0lP2Ou039m6QJv 6dArQRTGDq9KD2oZHuZTDPaZx/AUnJk= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=V4yvdebI; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-24df4ef05d4so10850586a91.2 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=EJYR76N7dlDPTE/5LMvdeXQrgpE6A21aBVH+NYZaCwWH8rRMRvOE6S2GTpIlHJOaP1 srMo7Mc+OZYYR3jFh/CQbsfzFJvy1A0Zy7qVi+JV95ddvvyVnMiRS9O1ahAcoy4USWjW Ax5u2sA56egSbbENzDLKlRERFKDjeEvQExTvnHmWoyZ5NLvcxt5rY3tKlNtQ/oK/nAmr cuv7k60rxv3pf7OpbLpAqXDBLeQiS682KhpG4vBEp/97BLo/t+MviIEsew6MiWYSIRkp vkTNOJrUoBX/P/B5wpUxAAmJklyQ9zNhl0gn6a0rN2Ggbr9qgLFL+innch8BmSEksQie HkOg== X-Gm-Message-State: AC+VfDyS3ClKQH8iXmg8Y9+xetLX7BuPhu9Licd5GJ8X8BaYT3U2w94M C/xQdrMp+4oO33p5xvmREYbroQ== 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 X-Stat-Signature: ka7348ft1f8c6ib8eubg54ksot4bwcqg X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: ECED01C0015 X-Rspam-User: X-HE-Tag: 1684156711-553750 X-HE-Meta: U2FsdGVkX1+PGqmqoa9wic99JmzZ8ew/bCLbEwOgGqL6th0++QLEWYZWxgZ5Dh0z9pEMC5z5MJ02jxDQyjG1c+SX3C/pYsYBDFLMRtfxj1UswYvGxexulTDHfpJhg28DOfTyNgOT7rbAwUbPFzAwQQX/5BjdbQEK5DMttTKs2G3sm0TfnKhocJxCqOpVbTRMcjbyV42/Dd4fBo4RLP0MeQk4tQfb89pf//GjOFieiL03jRvUXQfOo3ldsJzhmPyHI4iXa0+mXIuo1IhxmgdVig+s3sw/uFvAAKHBR/4TROgGpu3QH9RrJBovsB62WF7j00QmphurEPJz0hFRVLI4k3SbwwjXxRlTl74bd6mnc8efGtngScQwoHK1WyXcFpAqvlAsFY41fan4i2QRnPdo3MliV0aysXWLzGuhfW7WAFj3ssUH1rqR6gF/sTuF2Hg/HNZJEWPt4QEiwaMd3mhhFsFu68B36dXq60KKW0a5mQgzji4RnfbXKar0MFRGHUC8/0HbOMuxDN11BRYIyiL57V9uigsepwUlrpvaJaCiACi9jQbOK2rCq9UTLYnysDlbWgACfCcQWK2aVUNl7A8vJvTimEc21Kpr8IVPV5Wc0OwCkNTxGKelXwr9PIJ7rWk0g12v93/N/CQUWtazfkikJ81Sa9mbWeZKgikllk2JpymJtUCjXJYis7lGw+52M5IjNBgppdOoZlBIArv1B+oj9ceqZgJVFpf0OcIxOHGuKMJ0f5PFQWTdVytarwb7nuFi2xVeOrJymrRljzTnLK5qQNgK5io+YORIvvMLr91JsBHsNIibc++A90IMtSfiaCq5y9tly1VRiHn0RjsySVTeT21kG+/SBo3Hv8X7D3YVnaOSJuMm8Hv8rjd82UqqgbOaySc4jNlHIGZwrg70Q2/E7JxwF6VEmDk16QWveptKiYEksgJvSofTqL5ZyaD8U/JzkhGW2pLrUbZZnNxqmqO Xzujo/B0 ttQ+j2Kt+l12/S0Vrnjw9WkUlfUjJuhAaNkIIFa+Oq41RVqLZk37ZeQQjpHmUZDjO8BR17dgm9cA0Aevu3P1pvJHyY3rxRghxEEAroH9vRfl5VD25j7I/wg/WJn/bLbbpw8iZcbutVsMiWAEgbx+NxAr/rf004TCRzB77LtZJsp9UzlGVO2uFL5ysN3WtgDLbI4/mY/hDVm38BTz9NPqqvYCHuTUOcuBlASlKKv1B/BvyIkFz1b/Is/kV1b38hwTQF6bWpSQq891Q0ZdEptsPQG3xif3eBQ9uhpHqy+3RGaK7YdOuBKmG/31E3rqvUnkV+xs06I/boj9t1/pt/SddE1SWGHXznYYOwSufAd8mSHyOR35/2npJDaX4kkWc0TVg0giy5QCG2BuTm/UyuU9TJjGFAwPICMD86MLDmo6Kp/NiETpHwYgcRwoqnuyxA0Q2RB94/JoN26d79hs= 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: 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, unsigned long size) } } -/* - * 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 = mte_parent_slot(mas->node); - struct maple_enode *mn = 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 = mas->index; - mas->last = 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 = mte_node_type(mas->node); - pivots = ma_pivots(mas_mn(mas), ptype); - mas->max = mas_safe_pivot(mas, pivots, pslot, ptype); - mas->min = mas_safe_min(mas, pivots, pslot); - mas->node = mn; - mas->offset = 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, unsigned long min, } EXPORT_SYMBOL_GPL(mas_empty_area_rev); -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 == 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 = mas->min; - if (mas->offset) - min = mas_pivot(mas, mas->offset - 1) + 1; - - if (mas_is_err(mas)) - return xa_err(mas->node); - - if (mas->index < min) - mas->index = 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 = 0; - - ret = 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 == 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 long index, void *entry, } EXPORT_SYMBOL(mtree_insert); -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 = 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 = 0; - mas.index = min; - mas.last = max - size + 1; - ret = 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 = 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 = 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 From patchwork Mon May 15 13:17:50 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241438 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 1F767C77B7D for ; Mon, 15 May 2023 13:18:38 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A51B7280003; Mon, 15 May 2023 09:18:37 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 989CE280001; Mon, 15 May 2023 09:18:37 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 82BB0280003; Mon, 15 May 2023 09:18:37 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 65EFA280001 for ; Mon, 15 May 2023 09:18:37 -0400 (EDT) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 2FA8641231 for ; Mon, 15 May 2023 13:18:37 +0000 (UTC) X-FDA: 80792543874.21.E085BC4 Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) by imf10.hostedemail.com (Postfix) with ESMTP id E3733C0011 for ; Mon, 15 May 2023 13:18:34 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="i/UBgAcv"; spf=pass (imf10.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156714; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=eE6bxJv4UCRwtMUAfojMihpw2t2wf00Glyx+cFFRLZY=; b=JbPB5mjJyws/1MoqiiGxTwqNNLe8BU87cb/xlZqDjtgVN1/8gxK9buiZYHfzvaGrfG3Jhi 1EmSIxHnTF1M9bTRPd1TiLzhCHCXAHEs8fk97LFmVtrlLP9EvpVeX0pWpejFjwsEJ4K1LP KbUYcYvd+HbRBX/8Tpf8Y0UfrG/+jkQ= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="i/UBgAcv"; spf=pass (imf10.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156715; a=rsa-sha256; cv=none; b=SNTgSVVVWQjJpe8byKBFQGZhjtR6kaKFPS5tdhiGNojK04AvBFdCdkRe7vwefD1bDZ3KLW HYW96mU6KgnI7SnNyR5tobP8Mjj5Yw4hkLzgzlFFGQ3hO0ZIDMzbc5c9QhcLk6bNvyV81/ WVefY2pV6CPdvg5oAqlWsg4I6RIQbqg= Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-64a9335a8e7so20685917b3a.0 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=MeK9tX6/uVjubYZZE7/xGMYX1q5knGNXc3XrmM4lu/5hceHw3csOZcN1qxevW/eb9a CfjGphjq/JZi2GjGX/iK378JcuDNkwGl4FHNQcW5yThpgf3WTRAlvH+sogdgintqPVVe S7ixWwsfjAGtAcVJEl1Tm+U1Ejm82ZfkB/YOInqZpzMUR4u6Xwn9Xe5cdHtv8OPRfMWS bxHuNZV4sZkQTS1hWU+2lF/OJ12NxMLhq71leBmeh13J7Y3MIrpzZmcCkG+hFzqlmMPq XmckvBdqNDePzO81Xkj5X2Cz39rwNCZM7f5jeAYpa9CUELleLA91mWgAtozmyv3EeMXB +wkA== X-Gm-Message-State: AC+VfDx8CyOzb5BZD+aT/cD1/VvvWtV/YPZJ8G/UQE4pROetbeK1nvd2 gPN3Z6MvQJb3LN/3OymLYLKLKw== 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 X-Stat-Signature: 1u3xz6wi9tud9w3mzna55wguigg67grb X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: E3733C0011 X-Rspam-User: X-HE-Tag: 1684156714-493609 X-HE-Meta: U2FsdGVkX1/d2j8pvqiFGmlNptmX5obfRRWNzG0fAlAXbv/coNpbHUVtKL3OsbkV1e+OygLEAsYZxRH+bVAah/xOo0yPkhZtJCdsoan3Jj3aHcOuC7CfsgkUOnWXm2wjY28bAHue3Gc1RHwLcl4x+A74OwGVmr5MuRB3gApAohuRZQYIPVks3WXZnXWxP7o8LuLitmFwn+pH2zLzxrf8Gw91a49K2YSI/X205xKWUTJdkjrk2t1P0Sgk7cCmUeePdjVkO4Dw9L7EYGHaNpwMS/Lv6gFridSt6kNV9dbXPwfv3BqbizgDidL/ecYVlpFu6eoE0Qw4uyMTyq8EB0B1px5yE8Gzo03O9ulq1R2kX1qmFYPWysr9EUWzxQv6dnM3wMK2W+1Mw36oekuxSJlXapBk8s8BkLi0AEtNXVFLxikK6I6ALzGPJXGjzZoNjkTcYZYBbsYKLpuIG0huOwunX117xhd/5Gluj1cRCpGKDRflEn2xsoGS0pdyUg03qneyPjLWkoRX7FBFZ3+RM+qY5mvOJ5OK1xNKrxzolJtnQ3cJXpo6P+pWU/SpiS9yHm1BtM5WEgQ5vBbcF/8NX8HPfW8anlqcp530IjXkk4p4EC12hNrT8d9ZsLPSHcSLHcTp6XehCXTJOcXDE7eKnZC1ZKz6swZT4AiUj+V/3Kr1pCJAeGlnkK1WpKcD9ST6A35RyirGAk/LyQr+a6yosGPZ/I4jZHgcQwplTCj3kJUQCPGAsNZ8PvYQQHZrpAXm6sT757iQ7yTzvCYcL2Jlrm/gYnvovgarBezagEYoZBBkMBzqacFGdTrtyND7urb0prvvhHu9XxcN0FNsjUhmQfb+zCxZ6MRGNRastbDaueIyYZEviwU/FDxLGQLrQHdabxMaDUFl25R+Lf+RW6e24V+sssBqWsKTpXcVljUd46LXdxPNklfYDdsgPOfJq0Vlatc495y4vLsw3OR5+yK3GEc SCx/rsLP RISEpKwaI3F/D2msobWiWbmMsnN8yPgrYFRGiU3NOrVY9MaLyAZMIVqow2m0eyF3DpACM0rP9ucy7d/8FIwkPuvuMEoAyxk6wLsyAt8g9sj2VO9UskKnNqYjbDJzgLmH8ssq9Eg3mSfisyeYSn66tQpCtAOIOGuF8nsTZPTGv2+xQ4Xr8nLgrNGdX5Wjkejv59ZyG0jGBFwndfL2jHbteb2mGydCqdIYkwt6wseHYyjkpUAlzXcymV2TU6mQDkYeDeyRj1JdL4sjLKA5NJ5vcnYZo/LDQk3ZSvmu5wiPwwMsBjqnvSHks+6kU9VrLgVLDJGnq1Sl51/mUOZ2581TuSe2OZ+5r8wdz/tlEx/l5EmQhem819chf04oLfdzgb14B44THjtEG+SeFUEu9R3xTfke1o18N+8CVpOQ7ETh6FrPHtz9XgW2igeY3EDJzVD3tdDwqB6Jk8geMqFc= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000075, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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 = 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 *child) - __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 != MA_ERROR(-ENOMEM))) { mas_destroy(mas); From patchwork Mon May 15 13:17:51 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241439 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 0142EC7EE23 for ; Mon, 15 May 2023 13:18:40 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 82AD2280004; Mon, 15 May 2023 09:18:40 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 7DC7A280001; Mon, 15 May 2023 09:18:40 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6CA58280004; Mon, 15 May 2023 09:18:40 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 537ED280001 for ; Mon, 15 May 2023 09:18:40 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 8CF291C8974 for ; Mon, 15 May 2023 13:18:39 +0000 (UTC) X-FDA: 80792543958.27.A8F0BB4 Received: from mail-pl1-f169.google.com (mail-pl1-f169.google.com [209.85.214.169]) by imf03.hostedemail.com (Postfix) with ESMTP id 839E82000E for ; Mon, 15 May 2023 13:18:37 +0000 (UTC) Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=h6Vztwd3; spf=pass (imf03.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.169 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156717; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=aUBDvQ6OxE85hUN75/9d6LlRGyHmdnE5erOpWtw5OfM=; b=R30G49Zp8XzhiT9E+h7rHbTaAeTJiliHynXjfRrfNa4xaOkMo5+eIMJB3JsU55hVCOa/zw KlR81A2EV5nFznmEj8wREfPISfK4JTOiWYrTCzEumuFqEG88XOavlxrXum/MZihseJJ/6l GtUHH/6UisHBcC4xrs5qyXVXQhwOpdI= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156717; a=rsa-sha256; cv=none; b=QY5TYZOXFZcfR9tnh7OPpZlRYsC467T2lAED4uD59GxgP+kgQv7Qd5dokS19hz1llYl/Of l7kkcLo+7Og9LH1cDQ/SCe7lSwGvB44ctLxH7O1sUAaBVY52EEwvVfG6ADFQoi4+s0K2iB /YOjbYlbLFsV6CjdA5rK+vfMs++ZG8M= ARC-Authentication-Results: i=1; imf03.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=h6Vztwd3; spf=pass (imf03.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.169 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pl1-f169.google.com with SMTP id d9443c01a7336-1aaea43def7so87461365ad.2 for ; Mon, 15 May 2023 06:18:37 -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=WDknFBjgvZkaKBbf5AfY4KLeawWDXs+pHa+Pg/9agoKFhWOMJKwyQd1ra3K/Qjp1o5 H4jPC63VSf9w6Lr8hFTRclrd+M6A0lq0SCyAj3P/sBBM2eZVZW0Q4tlykz/9S+Rvmtkz jXhQnQySRJexmJFaZtC+solho8yJLmT3gwIEAkWH1u9G47YqqMLHilbuO28Z9o/p9Qwt in2U2pUqj41enpoHO+KUa8xGHg4rEFFK4s0PgCcIhYqOPL1WdRx2EFIVmtXL9Fkouk/r tbyF8wO8PS4SPHgI3GS30oQLXvca84RhIBYn/Ddmqczu49D+bgyqBWiyQNDsi4iSsqef mnhg== X-Gm-Message-State: AC+VfDzS5LeoYQhNsi/M3X6dHpkzdCHtuykQ7RW4Q/JwYa8tFTTl91ph Ju+/yza41woNArJdfRu43QbTLA== 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 X-Rspamd-Queue-Id: 839E82000E X-Rspam-User: X-Rspamd-Server: rspam06 X-Stat-Signature: bus5cfrj8q8coqtrkgtedk6bp1xi44zd X-HE-Tag: 1684156717-281879 X-HE-Meta: U2FsdGVkX18oeJWy2d3+P2lVtgtR9XelYFH77e1/g9G0LtTe99NxMvR1fGOZyxlMYkmVc55ckiRsB0IQTFgHRBPQ4aIGGdOdV91dtN5ijGD5/jDE59RxU2gZ8pYBycrtGvgypLlqHfYzgoLNdSyeLMdTthCTqbho7x6+poi5oeBdrrQWfRxrKlF1fy557+mZvRp3jLFkBy0qRrwhXQpqmA+ICYeh7EbtzetNbOouZmLsLbHIDDOJZCSeezE7BF1kNQFY+yupwsKb7blG3hHl+88P434srTGFJlu6yHs1XGW0AjJ7yYjYmJN+v3nnt2lVEELzUFKqpmzLONCkszi6iGd313TEjEkn4YgxJSccrZ5apf6HGgVeletbVqDyyULSNkOQhdQ3/9dzYAPaW7K9FPDP4h6aaGBUIAOl+Ks979RyyfcZrDL8h3UFydwExxnJr8l0KhrYEkGcAhi1wgOMzbS893zq+KZAl9ynO9kA75qZPl8LLepD4vgLiH3HjGbAuliyhgGcurhjP4eqoZ4/D9VJS97mtcXEHvebWfOOlfUcrVqj+gwBeY8ew3rXHrYmYuWKvMCRnOQ4BF7RUNz7luRIZemvj4R8AoLAyaGeSH4zp2ohCMirOnIyBR6z0MH155XskCq58LfdmYb949lODxIYW1j5qPcR8U6w042OKm0SAPebiqwdnB7qfjEtTAnVWdNDRkrW5tDrWOFmAlOPMnXjndflaDewoV93cxvTZrLibaTlNaOVOhhKwFDqBJdaiRFWxPZaPLM3jgQCti6fbYGkEsR7Xhyo35xQBZ5kwfkyVbnYGAYqKBV5eZR/QZfQEOmJ1gBaQwKey5IV0dHhKqp/EePWI0OmhTZQfGbv1O/xn1BZTQQ1Jevyde93yQhOIkANAaTvojncIyrCeESskI6UeGj6fzfHX5Bl2rqgANs63iYSg31AGt7bZNjz95I833Sj7uK/0KFAq1NMCUu qdKPtWSM a6IHwEYBrWkiW0yykulQV6jkK1hoK/Xd6K9QBvpwvRT3MQmxLNgEgWzpllyli98Cp0lYNARLgim3H97JcjEwGhPgx62xCdOKd3qWZmNhNMzObMqi7kk4c1oOMXmlNU+D61oqemQq6BuZM84+xsQZc0peRg4hsCGj2gBeSHLR7AXWjVSVGVKSenaAAtLFBtaJq4sRJLCMjN74CPdJFHjg7NfSsLNcpqT6CxSQu8I/3lhgxEc299FLWUJswkx9zalM7PgW8HQgj3HReOgSh3A2adRILRo1NpG/mkIoIVXT1cgUMZIM/lBPXl5Ae/Lb34NiiBCaqsegK3bUd49UxDqPNrqAXZTb4wbkJn3zvTVGfRWDNUzAE6895tPCE16CBMr9y9BX/ubfKbXY0XOLxf77RRvN196P4pei8y9gi1Ezw4/Bgbq3TqZiOiuWCjsP5LWPViX7tJXuDHnQbZYAwTbitRIyaKScOipK5wZQ6LJJXpz68JtY= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000124, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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_mas) { unsigned long max; unsigned long last = wr_mas->mas->last; - unsigned long piv = wr_mas->r_max; enum maple_type type = wr_mas->type; void *entry = wr_mas->entry; - /* Contained in this pivot */ - if (piv > last) + max = 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 = 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 == max) && entry) - return false; - + } else if (last == 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 == ULONG_MAX) && (last == max)) - return false; - } else if (piv == last) { - if (entry) - return false; - - /* Detect spanning store wr walk */ - if (last == ULONG_MAX) + if (entry || last == 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; } From patchwork Mon May 15 13:17:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241440 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 0059EC7EE2C for ; Mon, 15 May 2023 13:18:42 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 91546280005; Mon, 15 May 2023 09:18:42 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 8C5B4280001; Mon, 15 May 2023 09:18:42 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7B46D280005; Mon, 15 May 2023 09:18:42 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 64313280001 for ; Mon, 15 May 2023 09:18:42 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 274741C8853 for ; Mon, 15 May 2023 13:18:42 +0000 (UTC) X-FDA: 80792544084.26.F532F2C Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) by imf22.hostedemail.com (Postfix) with ESMTP id 475BAC0012 for ; Mon, 15 May 2023 13:18:40 +0000 (UTC) Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RXRsj1EZ; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156720; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=sHW4PAZciOvQN8kO9ncypAlcJrM+C64frREEyy2mYLs=; b=Hy+yJ8Xw34zusxvgNp+v8z4gISLuDore7i2uKk22amPvy0Fi1CUqBApVe1jz+3hH+dCPv5 lLvo3aVt8ISjd9SHTjyob25+PmT/qiBlBh55Ohc8NVku5k9zJ5WmUPz4CCibedKGtsxO8N dHs1ZvTMAPkOD5x65OAv+ycpJXByTno= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156720; a=rsa-sha256; cv=none; b=0a/A8NjJb+QXQnGucJtg601IbnRxQXF9qt3sTV6N+T/kigkWM9Tr1UiY1ZzsjlQkHXYAuY vKn14ekhdBw7TRB50gAFrmxuQm12HHnx4Hsv0MyiVuoqOx+86Dt79yVvrg8dqorClF7IFa Erz00HQ1WZBN1uhgrrAtqPs2ZLvGpeQ= ARC-Authentication-Results: i=1; imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RXRsj1EZ; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-24e4f674356so11420730a91.3 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=Qmz05Jj132HrxLqDgLPCBIHEH49ATMvdeOyElXS1N010yNQybHs+X2+jp/JqszVhOm jPv+HfCm+UoS78NueQP74tHnLoZifDHAG6U96S5bE19GQ9b8p286NKZr9FhXpeyucIvE OzSsYwbixUVt0E8imNWMhQKdpXyWccvcqqofy9n4EEOsFkZ3nXlonS6sri9eqyfd/zqF WxTAM82KoFZ/HOyAbHsIWZwPnOf6UtPuOmVHtzhtfu3MG+NcPzzJlbXjxwRBi6U1zgrZ ckdB3sQv5FTON8W7nSHqll1povc+D+wRLyunowlT/hnJyIMyu4M0G1ewriFyyfjUsPM+ AQbg== X-Gm-Message-State: AC+VfDxBE1kai97Vo3QG1wxgq9nwzSvC+daU/7RYE+7QIf2wYk0hEFbT HCBF4F/Se568T3WMmsWzxCqF+Q== 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 X-Rspamd-Queue-Id: 475BAC0012 X-Rspam-User: X-Rspamd-Server: rspam06 X-Stat-Signature: dfiur7e3iqo7ynsja5umaw6h5mbwmdzp X-HE-Tag: 1684156720-951189 X-HE-Meta: U2FsdGVkX19IHMA0OyXhBv3uetfklPv+8ifdMF7pZFFqyvYt5DTS2N5cLjXe9gbfCVQy+m71INKbptr/snf4YT/pOtJdgBA/GLWLw3JpmL7oofS9bfRB5CYm5hXArxyjZcrqh7jStxupYWjlm7ZATLQj7y3HUV29iuZ+nlfvXvQ5w9riZHU4x3E/kKJqHG2EqgNY3kY64kmn966dm0oK+da2h7KAQpW6Pf3XX36VWS+VmV7eEzJisx+yENLfQvBthfI82D1Z5t3wo0SNEqF60y+c3TbGxNqbVaOV047u1sUnPWB99LIk4h8Khjm4hnxXbdEwN/K+yBLHqFghmqppRsAX4qQurwFVt2GQZzCI1Sm9/wKta47TT6ycR709d5+hZGB5bvSfBTV21JKJ6bZukTQ37ge8lafcat4OXa3c5Iz/TpSCJ6CdyBoBMirWTsZtmtWqBY6d4dUveNemWJ8g8p+/VO3+4/tE4stIP/DHRbXOwPQ7184GX6nlisK9XrD86rlm16ajp0MOlPBQKET7jexsb9brhUelNPMXzSwq5BTWHsHgmtIJxIUWO21VyErT0sCFRxZKaZnmy0CHfIoHzojoBm9EtIDGpQCgGCvUO6zLkZZ1S6V/BX+AHtTG0rXzLcf7Xi3ExnD2HrWLBOSK46no0O7Q7S2NP0w+CX6ug7Wxqby+WBIy+HSpVUIaNkmL/Eai/V7Vzf60is9YsmzDoTArL9BonJx6ewkdYU/iPmSBM3boFfsh1vWLMUnev6GlqomyehOuBE05HhLudrH8J2yXqAy2rd4P1HurqD0NycwcC61SDYapAI0JsO+H6o1/4yUMG7qpq9Mc4UYLuzX0MoKx8VA9hjREY41HZo9ROaURNDZznqzOp/wNX5kqzOvpzIMMX5blBa8zOZlUiygYEnQnkDaPlei4cuYzQdbgSxWvumkSUTV0WVmvlPvYkHrIyzfGAt1lmNBwyPVo2gJ l4NFdqeq 9oCk864NrtZZSJgedSUqbtoW2eusQQrqSlThIOR20EsXZcltNHOYjmCil8go+y4WhaaZbJbrjB2+p8WLPsEemCPtVFY8WFpYuWhtf7cx6IA+WWX7qIMFNalGxuoskH/dGr9T4k/NKKL0I2mecvyveLVSyWS7s21kgPR/4kzSkMHEPwPPYJ/uDk0FDxPgenFYi8tcntLagmG+61bTF0HqHl/yXAUfnZjrS+phMs05oD28nCSZMNfVUOTvjA+gF1FKnai9QZMqfAhH6GEqJYVAD/8lQwyUT0Vfz1ISXURSt3HKUZFjp/gqI4hjz2GylBzfOUyzuFSa915aPNpRyVVLoDNAf0PITLWHJpnNJePKd7yW7aWMluEZNZh/8iC6r0DgIJJz570mNiI8HKgUpwgRGCncJqKoadWX3GhR67i6yoPMvZ5Xmyy04pCbNzGwiI+8rUeuLM23feFrxFOI= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000021, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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 = wr_mas->mas; - 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 = wr_mas->end_piv; - - /* Check next slot(s) if we are overwriting the end */ - if ((mas->last == wr_mas->end_piv) && - (wr_mas->node_end != wr_mas->offset_end) && - !wr_mas->slots[wr_mas->offset_end + 1]) { - wr_mas->offset_end++; - if (wr_mas->offset_end == wr_mas->node_end) - mas->last = mas->max; - else - mas->last = wr_mas->pivots[wr_mas->offset_end]; - wr_mas->end_piv = mas->last; + } else { + /* Check next slot(s) if we are overwriting the end */ + if ((mas->last == wr_mas->end_piv) && + (wr_mas->node_end != wr_mas->offset_end) && + !wr_mas->slots[wr_mas->offset_end + 1]) { + wr_mas->offset_end++; + if (wr_mas->offset_end == wr_mas->node_end) + mas->last = mas->max; + else + mas->last = wr_mas->pivots[wr_mas->offset_end]; + wr_mas->end_piv = mas->last; + } } if (!wr_mas->content) { From patchwork Mon May 15 13:17:53 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241441 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 C90E5C77B7D for ; Mon, 15 May 2023 13:18:45 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5B98F280006; Mon, 15 May 2023 09:18:45 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 569CF280001; Mon, 15 May 2023 09:18:45 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 4596D280006; Mon, 15 May 2023 09:18:45 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 2C2C1280001 for ; Mon, 15 May 2023 09:18:45 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id EDC161A0542 for ; Mon, 15 May 2023 13:18:44 +0000 (UTC) X-FDA: 80792544168.01.B61ECF6 Received: from mail-pj1-f49.google.com (mail-pj1-f49.google.com [209.85.216.49]) by imf18.hostedemail.com (Postfix) with ESMTP id 1B7E61C0005 for ; Mon, 15 May 2023 13:18:42 +0000 (UTC) Authentication-Results: imf18.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=iRq9sScO; spf=pass (imf18.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.49 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156723; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=lo1IIZfKjDP5LNi0dc+D12owX90CR8s5tkIi0vNkd7U=; b=helZeUbTODxNMiLHMu7qZXkur5z3ZcLSZv6kXErV8P9ErIsRhcFM5E5hyrNxfXSwLQZ1KV RDUUNnnkgUiQY70PQfryKejGKd3nPQyaqPy9wqrtCoTxzqpuyMApDr5ff9YoTqtRxYuzoC q9rbY01KWhGfaOPoiYrVUM7nkZPUtEM= ARC-Authentication-Results: i=1; imf18.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=iRq9sScO; spf=pass (imf18.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.49 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156723; a=rsa-sha256; cv=none; b=0lWuPKLkXJyHI3siVZhMLtA0I4KF7TeomlIXreMSRxrP9DAqAyadkLwSdu2vpxDEwbTvi7 PO2RizxlwC686urleWkT4DAvbIQhlBOSfUrkWSULX5alKAnNQpnLPejKxCtUqTQ8Q96mb3 1PfOSvwY5kFHeaZEEP5ZGiVR1rr3fJw= Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-24df161f84bso8727179a91.3 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=YpNX6d3tqqDpWzPurmlVWisDafxLYpVK0NBkln87vVW7f2g36/+s0nVHeG6nsfUzbu t6o0G+qDKCrkcERX1vnMf44fRJazIJJdsTzVBOZGz7efUWpQU1oACT/v9jcrr5WO7spF 5egxy1KEzXmeWfju/eeofKIN/vPoHubY5OV6QLJfUzDeDOJ81P4kZIZBkduVc065YV3k 2axkUDXXPSVEr7Hxu1TNgD/Ah3/IcYfGtJQW5xbZPvA6qZD91R1+wi5ixDLXLlZxf81N QSoiWAr9W602Grel50KJvhtiIkf6eg0xBQksjrz0P6OaD7ZOb7FUkWc66esUx7YIkkCe jvjA== X-Gm-Message-State: AC+VfDwB7c2H3RgRHgUWtBBnA9P0jl+SfDLjoFamm16d0ZB1Zjjmm76f L+e8/ey0bXOC8I6xybvxpsGRdg== 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 X-Stat-Signature: hmjnxgi5j6ob44drmh3dmhc9uqt5qc6k X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: 1B7E61C0005 X-Rspam-User: X-HE-Tag: 1684156722-573590 X-HE-Meta: U2FsdGVkX19rY61hqcFsgo4tuhCTT1PpibhuN9IVU5Z9lu59c6PFYYGsCWxQyIt15tjVWw4UCncM+nTH37pJG9QJLnWeb3EQ/xKCKL4cgkPKsp124ubFPw+g/7wKTtTmenWiBE6g2lrEczDREoJwPY8adpnpadD9geZGV/cVboJcKi8DqPjXd9NnG/3/51WrqEHStql7RZv860dGxdcj3oNeDblUS4xZ1ksq8rWcr5XAQe5j7YGviomkTBwpvx15DptXQMuD9q0Td1WS2GG1qWN0ZE9wyyvtahdVCS3OFZpRSGoijy5zdkou/RFN3+3xyxJ992V7Pu2JKzeUL4eAG1Xuba29bJShto/Gp94tqE6pd+LGcxtPjUhRnSL2bVC34rWr3EMCY9r9r+UJopY94tLdlblvgiHS4qO/luuTgQe4gbyhxQAT3SblPMtPwfjEx7gQxYQesWiaKThS6/i5IX/p/N1eBvDmEa3NqyQ/TF/zUoeQVkdcT/jlRRCafP0Bc/HWIqfUD/HeF+WvqyBaWwYwMJKuHIV515dlkPjVvBGrPhQIYjr3vNxoaoNaI3XTsVNRmPTlq15PNUM/0DAoElVh1qnnU1mzY43ugIKp/voYUPM0VZTfLbXQ7bggeq0QPYTPenDcM7dPmGJ+byhVPdVkwSuofXRyu50isW1nZKWT/BhcBuvM0Lz8X/8KSG/WaMpeadG9Ycy576wbmwNrCa6QKc6W/4aDgfcOU8m42uxBJSPyuh3ePBhy/QAgtTdrXZQqm9nKcynVuXVLwN2ZCeeLpVlbSX9wXYhx2OBpoE4J3l63ubsQdXdsvp4hw1RRW+UtIO7ZvQy3aW8qNt28g2/ptTB7Y87MoWzPh8QNP/cLtjQDNlVlgx3OpZsInbIn9LuAE63IrbErq8Vf+9EL2MtwnEiInufKxviql+iqSH05F2NnIsFnbjSCvsQJc5tenj+yN7rj35v8fzrZS2e IJvyfazQ 7RZ5iP4UL7VWPS4s23Ov8HotLniEhTLr1pBo8Jro85aJG31W5G6NSYttzq8wmhm7c7Ufr/NOnmcyuz/SSrZB0jMhHCZJx27hBw6zKficCpOzrPDTApddG6IuGNACo7o+uzIABYz9N0UBVwtxvtbxzPa0CxAAP4gqsbWUbFvn/JsLD2kjffJo5fn5dwHfibykgXKWz3vHWmnfe/SN2XJAXD4ZeEZUfP9TmxrnKBEoVK7j4ulyk2BCjNSOZ++BAFex/Mw1i980euL/9cM/tH9twWhEHRxsPhifE3QVRyNJsIVCbVkjNdhj9DYncLDqb2FLFGWUNkKu2P2SZg+GM+MKOsT2YvxyEoqqdYLkIr14UvhtWFxkMfo4qqI0EblAO7sJgWXjTo6FD8uZklmY7seSU9WL7Hxw+QNGkQL1+PYN0A9eOQO8+FgRKRbOLbd1OeOxZzw1eKqvJKLVDkMM= 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: 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_state *wr_mas) } } +static inline bool mas_wr_replace(struct ma_wr_state *wr_mas) +{ + struct ma_state *mas = wr_mas->mas; + + if (wr_mas->r_min == mas->index && wr_mas->r_max == 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 = 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 = wr_mas->mas; - /* Direct replacement */ - if (wr_mas->r_min == mas->index && wr_mas->r_max == 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; - } /* Attempt to append */ node_slots = mt_slots[wr_mas->type]; From patchwork Mon May 15 13:17:54 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241442 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 6DDE2C77B75 for ; Mon, 15 May 2023 13:18:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 013C2280007; Mon, 15 May 2023 09:18:49 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id F0723280001; Mon, 15 May 2023 09:18:48 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DCEB9280007; Mon, 15 May 2023 09:18:48 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id C6092280001 for ; Mon, 15 May 2023 09:18:48 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 76ACA8104B for ; Mon, 15 May 2023 13:18:48 +0000 (UTC) X-FDA: 80792544336.01.FA952BC Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) by imf12.hostedemail.com (Postfix) with ESMTP id 33E0940013 for ; Mon, 15 May 2023 13:18:45 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=IeSw9vO+; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156726; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=IqadHapDxpeqihp1W5tQfDBPl6INO7/UDDkBv5UKJVo=; b=A+af5uFi/PbqcFHl1xK4zLaZP/oMsg0BOArLvoUAU53OPrQrW65FMMzr7XvIxwZR9o6d0T vyJS8VgPUiN1ecoQR0yuMhujjfebFJ7RFFPh7MPdkb5Qmwz82o9IZPX0qpJbaj67vk1uHZ FONaz6qo1LtSU/CyVLMoCVDWewo7qhg= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=IeSw9vO+; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156726; a=rsa-sha256; cv=none; b=wrN27Tlayd9TyM4StGnlRfa9RJ5sp/tJCNxNyeMW1fVp8DzRxk84fche+OUkJ/b9ZsPANz F3JEyq23IVedr+/yzUVAP2xDg38fQ1FuiQvBp2nN7rce0a1316q9c0Qb46ReLHZALX+vlt eQbnpCHmJFcMjwJQ8yuL+zbZ77AK+T8= Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-24e0c29733fso11445467a91.2 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=jkkaZokUFmTkUueHbQncRDekWPxg2NC24X62DhSi0jv0pQ4bXLanuFz+JvBrOtxtxr liYm3PahSubYdjgmyCxu6aSmoDe6KcV0egT4SeGMBLc9dhdfBvM2rpxsOPFKCu/ylPXG 9s8yfZ8zqJqQS5coITkBKPDQTRQqPHL37O553GN8g+M751shBwuuej+35wiyP8v7VJfu X8Z9ffy3gZCu9iRgeJWxI6Nh90w5uOVbc2Y7laWAtD2e5tAg2HEROBH3d+pG6SI42NTy C8ml8cnLKL/n7GomsL75vGYxSlTPplwcEQXoeQLknLDRlRpcUGVv5hvDSDdWmyaLvXbg dygQ== X-Gm-Message-State: AC+VfDzEBvjGxMtZ0qQDLC89ex4n+WmOMZq+PIKAnQ7REIKUZUImIOB7 NWvCWNQjU39aAhiP3X8t01g4wA== 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 X-Stat-Signature: b3g6jn3diu5w1sc6pe78f3bpimhn75px X-Rspam-User: X-Rspamd-Queue-Id: 33E0940013 X-Rspamd-Server: rspam07 X-HE-Tag: 1684156725-190068 X-HE-Meta: U2FsdGVkX18zGRz00Ow4l0IJ8OCNBC/6dASFECe9OdgGSC+F1IKI2QYQBYde5kiEnIWstRM9SfDHC/J+UUHRAQe/D/WMfsA4rHqaASlr5/jeb2ARjlAfg8KXWldo+H9g30C3IHH/55KAyWPyqEnS/gxFXweaMmS/QoSsCHV0SLcJmf/SD7243k/IZnBxTHeOEMx+QcP2Da1E9vlcy7QFyDaGEtCDIDYw0a0ApnTQ8cwlo4vJjdzOWqqn3ClJgoAVEFSTPU923gNWwKc7A7thlxmnAaIiNKycDHrE8sjP8TmNPtEOUD7Ch7NYaUy9jrfvsN5tlFcPj3XMQn/F4skm3y5nz9WPboXsRy1QXp8M0n3RwoOwEbevIX48xPnnib62FR8j+sIcS/DoSgIhujnQB28M9TJhvz5rJnekOeqlpCeQxUKUag9/cxwSWkA57/peLrn7ooxIzCSXFTcpuiTZLApCvfwd7HJJfFcb0rc5LEOR1WyF9cQJbaDVgkweWyjLF5MzDdQrO7x+ZgWDwBh09Xm0/Q14iqwSZ5YZjjSKLbNm3/hMBJyf3Wr+KrDQL28sEORIIkg0fsCdTCprWPD3PzfuT8R+1zEGmUCGJArMQoY9uPYp+G7e02gEtBdbNdihpAylaXH/ro/CX0PvrA4Hh/3vWMt9d4MoPuWVpfosZsVeNLQVlGtzym1nOjlgmsZogU27TG1L/+OzK0ausWN3Q08PpmY5mMHTRIKT0MhRlUVx0zKTS81/lB5XJeumayoiN8aqa2dHK1ALPjVumFMM1idiKUqeP57YfzW4IsbV4lgUcaJMzqGA2VMdQoFIjmUGw6rZYy5ivlnYLPXKJmUYSVktkI0Aq8Il/TyznTEnQQKWEo3G+9jq9xxdzdx7/0Ydpnz3Ane7sXwEok/nJpj6upTGePuCQUjKnHeuwgq1HkpURnQOQLTpf8RxLmHMNpaun7aDwtDAiXTnc29PXX3 fzr1Kqa0 GCAjm/F0Vio9KIHaZF0QQfc+m4A75CdC9mxXzsONNiQ0L6S9+esp1ZAKs1IgKyyFHn4kreFdzomFtxO4Ge5G8vXf4gED79E/+J3FqoaqdWkpmlW0/4ym17MWFdajnNa9pZkhklxkwoIfLSWge06v67aPB/Od9CXRxB+RpbCggAA0FlB1wuacoyzGNrKato5P1JFLYstBf9NiEm4p0f4D0kNL3ltQlaHHPxaMgZVumQ3t5QIhNaQ/bOvQClrl/CLXx6A/T3CP967mc3fJucrqFDxr3JnX7paav6rXEn6z2pWA0KGodJGhS/tmo716eZdn6Pe7MNRnUR7uBtiQcJunUnoft5s8ewCrgSatVTKGgm++0uXWKbeFTAIcYhLZ+aCorTorU96lJPGcNUxazmMJGxs3fEynkmC63T7+X51/xOYm+bhGoMxyPMl1LHuIAL3hVivvRpGSxTW9CbuA= 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: 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; } +static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) +{ + struct ma_state *mas = wr_mas->mas; + unsigned char new_end = wr_mas->node_end + 2; + + new_end -= wr_mas->offset_end - mas->offset; + if (wr_mas->r_min == mas->index) + new_end--; + if (wr_mas->end_piv == mas->last) + new_end--; + + return new_end; +} + static inline bool mas_wr_append(struct ma_wr_state *wr_mas) { unsigned char end = wr_mas->node_end; @@ -4356,25 +4370,22 @@ static void mas_wr_bnode(struct ma_wr_state *wr_mas) static inline void mas_wr_modify(struct ma_wr_state *wr_mas) { - unsigned char node_slots; - unsigned char node_size; struct ma_state *mas = wr_mas->mas; + unsigned char new_end; /* Attempt to direct replace */ if (mas_wr_replace(wr_mas)) return; - /* Attempt to append */ - node_slots = mt_slots[wr_mas->type]; - node_size = wr_mas->node_end - wr_mas->offset_end + mas->offset + 2; - if (mas->max == ULONG_MAX) - node_size++; - - /* slot and node store will not fit, go to the slow path */ - if (unlikely(node_size >= node_slots)) + /* + * new_end exceeds the size of the maple node and cannot enter the fast + * path. + */ + new_end = mas_wr_new_end(wr_mas); + if (new_end >= mt_slots[wr_mas->type]) goto slow_path; - 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 == wr_mas->node_end) && mas_wr_append(wr_mas)) { if (!wr_mas->content || !wr_mas->entry) mas_update_gap(mas); From patchwork Mon May 15 13:17:55 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241443 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 B999DC7EE23 for ; Mon, 15 May 2023 13:18:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 45A6E280008; Mon, 15 May 2023 09:18:51 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 40A30280001; Mon, 15 May 2023 09:18:51 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2AAF7280008; Mon, 15 May 2023 09:18:51 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 10C6E280001 for ; Mon, 15 May 2023 09:18:51 -0400 (EDT) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id D435F41251 for ; Mon, 15 May 2023 13:18:50 +0000 (UTC) X-FDA: 80792544420.30.5040C40 Received: from mail-pg1-f182.google.com (mail-pg1-f182.google.com [209.85.215.182]) by imf29.hostedemail.com (Postfix) with ESMTP id 9DCD1120003 for ; Mon, 15 May 2023 13:18:48 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=DPCRZ8Pe; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156728; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=qZYylnYxW+ETURaA5WORPRH9YUugjQDKMo5It+GAwgw=; b=z4zA4rvZ2a7arOzsp/5p037v8RVHFjfxsVIBQ4/2ITsL8KCRn/bGl1pJbPU6f1LInJ5blo oBxy22JoTZTA7nBYd5F10KSX8Q5u34U5+NNwiBZHUNnOkN5Ebbyn7xlZ5d4ESWkYr63XqX dmP7C0Rl/Hp63UKd3s2TlMSohEnNc04= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=DPCRZ8Pe; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156728; a=rsa-sha256; cv=none; b=Af/aJuDXof4cyS7LFOIoSqy/g9jnPVcxWdTDb90k04ylgcbSSgfTsqJSO0WyTKSUf8JS1q 312XVB9ehy6adPpa4nqo3BqVSSuKQvm/SRg/tmq/JqBUjU15h6m78c2HXrGjJ7kIC5mnLy nc4F9lBVcst2sw93MT0RsjLD+GQxHOc= Received: by mail-pg1-f182.google.com with SMTP id 41be03b00d2f7-53404873a19so1071283a12.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=ScoHYaGM5ZE4HObLgClSRZjQuR7jl7xYGtZpx1XIX64FlOnA92kRfHZjUB8vOI4kkz gh/Ni7NeWVYMKSbJZHxc0dsHCh+cmcr73Eh/E1Z8Na7P6MZbJDe/3VOiFC0a1ar1kvw6 oK0kHhz0aOhV0ws2wptmcop2JefzQNet82DHIFv65wFTpQGZIguBEIEBWSXpxd8By2sp Lbix2MzTHmCOfCGv7de86WywqapFafz9/bwcf+98ulCk28Bfr1ITwnGSCKeRyj0M34t1 hpTzD0nPcOjSm9mLqt3afo3uunzDSeLabdyRiD3IXFJoFCh/l46UaZ+rVMnhAIWbV44x LGbA== X-Gm-Message-State: AC+VfDytwuBl5SQIKVXGr02eIymS4WocCkdRb506WA0XpcdAb8UxjPVn veCDVvuptqLRQsy9d8nmoJgWpw== 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 X-Stat-Signature: epzjksjczgyi9jntfuygojjkwxwwenbt X-Rspam-User: X-Rspamd-Queue-Id: 9DCD1120003 X-Rspamd-Server: rspam07 X-HE-Tag: 1684156728-769730 X-HE-Meta: U2FsdGVkX1+Mg/lb8leGdPjog4iKQJC8WjmZne+ZGa8wyjePFXUKrMCzQqPpzxoIxGl0ltSbSAzNEk0ZuUr5+0LlflB/kPogHOYDeGL7JCP+1C00DsVwauhxHD1wgTT39ypgc96h2b0W+/yFGp0pah3Um4Dz6cP4fXIX4c97uuc/twU0Ca69xZU+Kp1W4mN9tYg+gc0PuSfP8ow7Rqt2SVucxIRXd4A/66QctZtJhupS+AOlQcmbCQNR7xBYJaaalKy02oxL6WfNx6pOnj9LawEMguYFzpeIjBiskhPpGEEaXw401b+xGvFPgM2E989bBPkx2TL23lTcx4pg2dnvbH39Njet2tA8mJ2klHrZweHImIHz3VIr9e1KczfDaLyqZNpAREyRPhsyGNTtAfnUvsFi931mNIeU35UzU7J6SArfjoWXv+322Ot9z5R/JpFwHYGRfOD8vlSu/5FHbwBi+I4OEHT2koe58YZUv4YeSnCS2LiLUclf/kCECEaPiERco9+qBjUr072hCBAdch8tX1FZtaiDRFlN1BI+9Xy06FdDqtSS/FiWnUCvTdgd9t1u8ua0si7cZhSx+FBm2iSdH2Zw1tLJfiUXzsOTu9iJaWaXeXiIEvWGSHOipIOpkaNxqvKjpndMLw5ih9lMgY8N+9qrGK4x6vFiJ5YE3GUznZspcpvy4w1DBjNNdwCoXuccH+hYyWyx0ROGrIA7x/YciYYIhlL1M23kZztZCn/wEm6IppT1COFRbbpLJotTMUpKiheArhlR4z3uCgzy34CleL811M0EsmJ3J8Ry3C6zX2HqmsuQ2Vhl0Rc5sW+5+SyflV1M0Q/D5XRQp0G+GWorLmug/encq+UMtrqpYcf1dfJIAULJMufz5tW63dZNsUQy+lupG/s5Be2YJxBldI8MXbu6O09pP8akVtUjyaMsEL8OOEzF0q/E25Li+wMVEwVw9OAn+ThbBFWNUrV54DV UfloRcex Q0p2brfhyN0sG/iJq2UO4Fofsw28gzwjJYFktZmwtFbtVg1fWzkzoxgItkTutBaOGJSoX9c/Itd4vrw6cu7Rc3PioTk33OwcRJC+sOGZWOtBsTbOySotNkB3NTpe5gd0QhurqKGAj9x7nNfaT+f02VQSmoTwM3bOQDHb/rTPGSPe+LoHk9pUffG2ntvhpErMfp9cXRNpvf0Q9SGpdpaA0GeDvnFw9eKIi5bzpu3fmlKGFDiGN5JkBud/uQnq83ZPzUpWmBnsKbQw+x5xKRK/IGeUoAP1wgex/gDvW5AiEcFFl0laKQzOgJdfdmRTVYfaEMFWjtmLnziqP4jPuMFsxbezt8fsSkq8W3Sl9kYHmCN9WXJHQan+imtHfjGiTLFNdttsHo6ZIi2Ia1YOMu8Z7IvhSqWJ9zTrpCMn/6qDZ7uE7cC4fPv+kOpbcb2JdQY19ftyuPs7Z9dCIaec= 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: 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; } +/* + * 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 = wr_mas->node_end; @@ -4322,7 +4347,11 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) struct ma_state *mas = wr_mas->mas; unsigned char node_pivots = mt_pivots[wr_mas->type]; + if (!(mas->offset == wr_mas->node_end)) + return false; + if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) { + /* Case 1 */ if (new_end < node_pivots) wr_mas->pivots[new_end] = wr_mas->pivots[end]; @@ -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); rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry); - mas->offset = new_end; wr_mas->pivots[end] = mas->index - 1; - - return true; - } - - if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) { + mas->offset = new_end; + } else if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) { + /* Case 2 */ if (new_end < node_pivots) wr_mas->pivots[new_end] = wr_mas->pivots[end]; @@ -4346,10 +4372,13 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) wr_mas->pivots[end] = mas->last; rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); - return true; + } else { + return false; } - return false; + if (!wr_mas->content || !wr_mas->entry) + mas_update_gap(mas); + return true; } /* @@ -4385,12 +4414,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) if (new_end >= mt_slots[wr_mas->type]) goto slow_path; - if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) && - (mas->offset == 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 == wr_mas->node_end + 1 && mas_wr_append(wr_mas)) return; - } if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas)) return; From patchwork Mon May 15 13:17:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241444 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 6BDE8C77B7D for ; Mon, 15 May 2023 13:18:54 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id F0895280009; Mon, 15 May 2023 09:18:53 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id EBBBE280001; Mon, 15 May 2023 09:18:53 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D80F5280009; Mon, 15 May 2023 09:18:53 -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 C4221280001 for ; Mon, 15 May 2023 09:18:53 -0400 (EDT) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 6E6321412BF for ; Mon, 15 May 2023 13:18:53 +0000 (UTC) X-FDA: 80792544546.06.9D24014 Received: from mail-pg1-f170.google.com (mail-pg1-f170.google.com [209.85.215.170]) by imf27.hostedemail.com (Postfix) with ESMTP id 6CA1C40010 for ; Mon, 15 May 2023 13:18:51 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=g3X23mAk; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156731; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=9RjXFpMPucyoGVPKV00U7wCkXQqL8U9B4PmEKn2WMSk=; b=L8X9YNK2oefC8NCEFERUge2bVD3khIjmivQond3nUBzxdaX+xLUDN4HQ7vrTjtZz9ZjsbF QPFa/6xhwMDpwb8r8H7GflpudKWEF5UNB2tVMXOjxdEHkcDATOYBFxBFR7kElbvTnLwXJW fIVVEW27euytBxnZ0QdGtmOCZQpWt/0= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156731; a=rsa-sha256; cv=none; b=mjhefbHeC2SD9CzLgXHxKi4BVV8IJhWoYOU3UQEAfFOPMltRQj1GNNyD8zFqHqG2iIlYYf 9RzpfRh23PrfFww4TfFnUGQ0IJNtH1q3QVeG8apqM6pOkPp8l02kiZ7/qeP889dLx38hlb pBTitya3pGwwg5znMFNYVXr/XBRqJEo= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=g3X23mAk; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pg1-f170.google.com with SMTP id 41be03b00d2f7-52cbd7e73d2so9502045a12.3 for ; Mon, 15 May 2023 06:18:51 -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=c47EuqGBKirgE6XClT9IjPip0C++KyUMP+mRpy/9OpmfOOGWsMvR9RqfgR1vTDI2xU en88ai7OgstX+9UuPNNtyCrhBha103wps1oqYsd6j7SOxpLWx7MSo6MYgY4CxjWXTY/e rZrusPIffEPZdWtxs0du3oLLakbrkDLx560MF8KI1xmxK4iKNQL2shw0oVjIO6kpexiy S72DLJgSMccAcTFILI/GhMUu5NCjiKeU5HKX9D8F+HMlxfKFi5crRKBOqb6JSsP0IoUb AqpthBgbO/E0vSAd7qBeQRM3m6mFR2G58J3w5rLMPD3M6+XbaLhArHnySBhPvc6CosLO ukew== X-Gm-Message-State: AC+VfDy5rlklXfdzv5upfrgNlgBriKkER3CP5ZWqOpmdoJbfGUrYmYzZ ELuRfS9O7ObEjEMjr20+5uCuEEjC/70s9ZN+aJw= 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 X-Stat-Signature: ww793x7hf1qbzoabo9mq3ui4csqw1rjb X-Rspamd-Server: rspam03 X-Rspam-User: X-Rspamd-Queue-Id: 6CA1C40010 X-HE-Tag: 1684156731-102949 X-HE-Meta: U2FsdGVkX19rgo/Tqxmp13VTyXdXnscxMAq2vigOoJ7Qf6AwMIVX+aorSWSRT4DLz+Cy7LNB7C4br/UvGLsS9Qlrc4adqvyeRd+29E5bu+V+YPmPpo3SBeaB9Qs5UwhgNjwfbjLZ7dVcl4jXHRc9AcIAB2/xU4dy6UZm0TuCIxrmGiBiBj0DReJ9yPAfQE++U5Vyg2LDsEsB3ls+ZOTvFgGTMISyFrmi0Ak34hSMdJIYJCPE+6ZBLrxHRdGRYjUS0OFNPAzoE9E2MVB32p7KmC6DzWwyKnlDepvgYvwAUiroAurWwjZ3tiHzYkdy7FkLuvvuqz3KP6eonFK4xFEvmnS1erGmQY4aeWhObY9hEjWiXDrIY8nXVOC/1xJaAechVLyz3V0g2C/giDgzxsCrHWpx2Lot5hXNazHnfOF5rWCj8BlHsC0+Rak4vVjh8pPLYUW0Ut0nK/cNf/bYhhxRKMmaW5yw34RNcFOBtquzjHNeAG/pXPf9d0+Ez1IT+cRIteWBkKSUkDFCxGa+ET8Jc/OqWGgFhXu9qmGmSzeTCbG85lH4kzxEvs9rclxmSe2vevSOPm9NJzyIxfoUp/H/IPLodoijrzp5tSWlPDhpr0sKIpncuz/ZbVMTzw/TOyuHV2SqXpTElCwPip+wjvUU6oE6vKRKA13C4a1lqwR/BJF7Cu+uXn2x4LZTn2JtsDoZEjhfnBsO1sYz8+ApWycxc0T9PHQkyzq/qxDo8Ib8S4dNyKPupKjj7WO1E3ggDqp3D8FZ78KfMODh0ig+EV6zRcHluXJoYACfEvY7T1mCP/oZXlF6OfnOBMNASk2DFT/fzBIMzDqi5/6yMk6GJzuiorJ5ZxK/MVH2pklTjw8x4gWYJvTLyPHHAKPI8/chbA/3LC86b5VvrHSJ/w2D+o+Zp7VBU/KUxrzLiCY3yIWdmzOAqMDl/R9bPK+YO2ObmoAaFuMi3jiXe2i5yY9g904 y4O7ssRj fSvRo+33/GNe4+TFjm1EthYm61bEVn9SnwwwES4PF9ufu7Nnl5PKCMbMciHV4FPAuPzTZ5ArVwLrqe/Q9IyF74+17FfMCDgvZT/CcqnXSif7H1bYmOBw+sPG39/x62gEQ5OGz6xu91reNDnWuPRPV1G+SMkFYU5Iq0ekFcS/ZMgbBeTi/goTu8pqVQK7BRIPUsqiPvKGJu8/5XLwXnMcIWAuyjLx2DgR/VihzdMotfht6KesXridTS5XlRJWlKmgJKMcdU9wUwfum4dejN8P9aME94BZWZN9xVAGWotRE3F20Kupy7KMgMkRj1gogLEJyJ0hYyA9NIgr2v69pBXGKJe+2Ov6tPTEuuApmw0mJ4vp+Oz3VfSCo8TDuyNUvx1kT4EXPeMNBNer5rLJpnY1+2L48w7TnHu6cflEE96CfG4r6ShqQPJz29ja0pSerA+RuVNNugfXr2Qj7bBc9GATU390RFFe8hddYOFoYNgJSEVTM7y+x/vgwprC8sg== 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: 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_state *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 = wr_mas->mas; - unsigned long lmax; /* Logical max. */ unsigned char offset = mas->offset; + unsigned char offset_end = wr_mas->offset_end; + unsigned long lmax = wr_mas->end_piv; /* Logical max. */ + bool gap = false; - if ((wr_mas->r_max > mas->last) && ((wr_mas->r_min != mas->index) || - (offset != wr_mas->node_end))) - return false; - - if (offset == wr_mas->node_end - 1) - lmax = mas->max; - else - lmax = wr_mas->pivots[offset + 1]; - - /* going to overwrite too many slots. */ - if (lmax < mas->last) + if (offset_end - offset != 1) return false; - if (wr_mas->r_min == mas->index) { - /* overwriting two or more ranges with one. */ - if (lmax == mas->last) - return false; - - /* Overwriting all of offset and a portion of offset + 1. */ + if (mas->index == wr_mas->r_min && mas->last < lmax) { + /* Case 1 */ + gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset); + gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1); rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry); wr_mas->pivots[offset] = mas->last; - goto done; - } - - /* Doesn't end on the next range end. */ - if (lmax != mas->last) + } else if (mas->index > wr_mas->r_min && mas->last == lmax) { + /* Case 2 */ + gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset); + gap |= !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] = mas->index - 1; + mas->offset++; /* Keep mas accurate. */ + } else { return false; + } - /* 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] = mas->last; - - rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry); - wr_mas->pivots[offset] = 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; } @@ -4418,7 +4427,7 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas)) return; - if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas)) + if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas)) return; else if (mas_wr_node_store(wr_mas)) return; From patchwork Mon May 15 13:17:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241445 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 4BD4DC77B7D for ; Mon, 15 May 2023 13:18:57 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D0E2D900005; Mon, 15 May 2023 09:18:56 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C962E900004; Mon, 15 May 2023 09:18:56 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B0FB3900005; Mon, 15 May 2023 09:18:56 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 97F48900004 for ; Mon, 15 May 2023 09:18:56 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 5870C1A12BC for ; Mon, 15 May 2023 13:18:56 +0000 (UTC) X-FDA: 80792544672.07.1125A54 Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) by imf23.hostedemail.com (Postfix) with ESMTP id 3F59A140019 for ; Mon, 15 May 2023 13:18:54 +0000 (UTC) Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=OY1tnyrN; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156734; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=ArSLVUhdR9DQTTW/HQ0w3hLWCHQGeUGpXjVNbpJHsbw=; b=2qkOg3XRmRWz2fzBwX5klm5UuMHd/OVq8Skj2K4VlM2foVcKt3d/xUUZ2ErNIXgEvQpo27 q3yPirkPwLb5lWonZO3aH6FCqcsr+yIa5zlr9PTHUs/VUc/KXlxcfEhd1grjy5Bcq5GCZA wANmqFj3UH3mYmIKctR6g5J6+Qwexp8= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156734; a=rsa-sha256; cv=none; b=2uu8i1L4P3W2JD9jMLtdz/3CoY0FI6FzXqbn/m0D+sEYzmPR1ekmR2fo7qD2TfyIjevZgq sMv3Zl3j4xiVPjhyg+Ld+ZoLcEfoeC3p7RfR8ERBjPRfjcvGC3H3DQ8oOLodkbZEIFzUNO wrhMuALhAPJZEqK6WBw/g3gcFYQGlRw= ARC-Authentication-Results: i=1; imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=OY1tnyrN; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-643b7b8f8ceso7258938b3a.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=QTVrvKNyl6DAOKdhWjbqT1h6h7X2zoz/YCwFj78XKhLF6rQX7XkOttjLOZkuFhbLyv B+9vvG94XoTwQnRNZmfWLKiXZ8UxCNeXj01VM2yHjT3BUFHneQLslAlZtJJD0EXb0nRZ Nu2fjKo/dlZlDp6MTkHj1fJMD+asumdHHwRZW5NCIxK42/auJxqSBbppUGv1xlkZ0GWK vo7Kd0agbcWAftrvizSDZRsJ82bCau1OoCn2e2Zxmiq6y/RflpukqfW0bxue/kcT2iXf cRTGucDS79fyolDb9KNNprQlVF8gAwbYynyICwxelM5Uskk9p9cHpUtNsSnOKU3GFSgG Ei6A== X-Gm-Message-State: AC+VfDyZJHikauJW16li5JFns96UOVB1zSip9dAW0OX9+nNAdBfZVe5p 86PY/r+ZgKWjaHr9etcPbu8XYA== 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 X-Stat-Signature: y4yjsgcrcmo63us8pjcs6adfb19uajkx X-Rspamd-Server: rspam03 X-Rspam-User: X-Rspamd-Queue-Id: 3F59A140019 X-HE-Tag: 1684156733-236783 X-HE-Meta: U2FsdGVkX18EdxcOctLhj0WEPSAydKvSwu6C2ti9Gp5DtqFbOoSlmPi+WUVbUpoGNJMeRa/LW0xwbODMQ4zmpKe69meFP9SXi9MDkS4xE88N4h39N4yS6e3uCWOvYwX5H/xWfMQWpUFuE7sp1+RwXWS6T+k3GCo9a+sD2V20ZqpebmvlbTxO74TfujxgoFzAtnX7cWVljUkwVsypytcAOChdA4u19KTm77KxsshMWeCoa1vMCHibb+1D4aQHzb1mO375OA7rDAYXrBp8bWjSZbKY7yBPWF9Mq+9smyKlk/Ttq8wVZ4SrYi4EF0c/ghaYvqMF9ashIPyA9wiQIIDscPtmg711ogs3o/TA2y6Zhy/4Gy7xcf6VWT2YBadi/OftmK7veI5O6TovsazEhkrNALyUfU7t1JbLh6r52g1bmri9LqQR4wfi5p47e3Kn7JssxHM8S2X4mVY/rQBI3izwht1xpLesPQTT3lHIoU1lpNkJ5AZE1+UzG3ZFUVAxAim48qfnP5lasMbZw1oPu2mUEViERknSRbHn5K2U5K9EpcH/QtinSLHM7EJ0TxWSlCHme7wQ3E0B4qnTyHu1pbVCDpNmtvBHJdTCTp6xLYrnyKAo5xHsgHt1T9cZKSPq0PHDcg+sPN9/zt+J4e4AkcxTEd4SoBX4PEOvxbkfSopU/QdGM/izmHFg7bq5m1Tp04dBnOuilYBPHJRcTd/0WgxuAsH6ZU5/azhjmzOf8NehcUA75Td0lYYTu90chA/r6KWU9Yek3RydqW0JSk9LnapKAKL/O346onTHPU8rO9AYArvrJ5PCzkczJt1hXBLzPoGqhXIjyAH/SC0IbjsVkqofs05OMGUOuITTQfHRCuHrbxOx+bgQs1x71jTHkqt72cxYk1YMzruXL5Q/NyDi7074z0xqIDnnAQSvLfTV/fAuwxNoi9cjzZDx5r6A8+eR85XTvvV7NIrPlKdpE7VYpSa DyZ7MIf0 1LUgVSZ9mleaimC+/1GAcqNz5hQzCuGcDjr9SeEhpEygjQa3/p6SGoH/tWYolLKj6gFkTSDN3KBVK3iSZRuFkUDCaolC4RJO67KZzR7PALdUZdTzIFy2V8laCFBUoz39rSYYBzWTwuLzzx3Vq6QOM2zN273FNhSbwqsap5znnzdru/aVxKXqzRTZmcKSzji3sAZpvvPiQGFw0TOUaDQa5uji5q5IjKc7aJ5tPsQSfPaNlWpUDl8wpGYRl2+rm3ZkCjDIILZ3BQFBR4bfm78eljqgPz0iMBCF+zpwwaUsrHTfIyb2sck3TLPYEAmbjq7unrbEex3G7J2ANTPv6HuiUG6tg6B43e5Lph7pTohCyCYaS92AmhNjR3HudlMmUJXyqf7ttBKgR07AfSz+CJWXLsqDyJvKblRqNhpaiP9/5YkIhZnip2V9qHAyVmZsxHYQrXDuN987gjlk2VUE= 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: 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_wr_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 = wr_mas->mas; void __rcu **dst_slots; unsigned long *dst_pivots; unsigned char dst_offset; - unsigned char new_end = wr_mas->node_end; - unsigned char offset; - unsigned char node_slots = mt_slots[wr_mas->type]; struct maple_node reuse, *newnode; - unsigned char copy_size, max_piv = mt_pivots[wr_mas->type]; + unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type]; bool in_rcu = mt_in_rcu(mas->tree); - offset = mas->offset; - if (mas->last == wr_mas->r_max) { - /* runs right to the end of the node */ - if (mas->last == mas->max) - new_end = offset; - /* don't copy this offset */ + if (mas->last == 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 == ULONG_MAX)) - mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type); - - new_end++; - } else { - if (wr_mas->end_piv == mas->last) - wr_mas->offset_end++; - - new_end -= 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 >= node_slots) - return false; + else if (unlikely(wr_mas->r_max == ULONG_MAX)) + mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type); /* Not enough data. */ if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) && @@ -4128,47 +4103,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas) dst_pivots = ma_pivots(newnode, wr_mas->type); dst_slots = 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 = offset; + memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset); + memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset); /* 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++] = mas->index - 1; + rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content); + dst_pivots[mas->offset++] = mas->index - 1; } /* Store the new entry and range end. */ - if (dst_offset < max_piv) - dst_pivots[dst_offset] = mas->last; - mas->offset = dst_offset; - rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry); + if (mas->offset < node_pivots) + dst_pivots[mas->offset] = mas->last; + rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry); /* * 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 >= mas->max) { - new_end = dst_offset; + if (wr_mas->offset_end > wr_mas->node_end) goto done; - } - dst_offset++; + dst_offset = mas->offset + 1; /* Copy to the end of node if necessary. */ copy_size = 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 = max_piv - dst_offset; + memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end, + sizeof(unsigned long) * (copy_size - 1)); - memcpy(dst_pivots + dst_offset, - wr_mas->pivots + wr_mas->offset_end, - sizeof(unsigned long) * copy_size); - } - - if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1)) + if (new_end < node_pivots) dst_pivots[new_end] = mas->max; done: @@ -4429,7 +4393,8 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) if (new_end == 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; if (mas_is_err(mas))