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: 94148 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6926993vqo; Mon, 15 May 2023 06:37:12 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4KwTYDl2Kb3h+ENtBxNoc9T9qTPz4JyGg7OVr8P3sH/kKc0z/3AqW8az4f+3Db0rbMWsv+ X-Received: by 2002:a05:6a00:2d12:b0:624:2e60:f21e with SMTP id fa18-20020a056a002d1200b006242e60f21emr47861550pfb.29.1684157832420; Mon, 15 May 2023 06:37:12 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684157832; cv=none; d=google.com; s=arc-20160816; b=Yx81T+ToX3EpNMpGvGEBQUV0aa5RErPuP+f1foCShHhKuneHIpRfq9IwXfrgQREOWk 2tVniY50Wn5Ug9AnC4GembgSy4EggyHJNzMpi1zECDuwTQyC0jxx8KMZHxlyWLvtbMxB LAgQ8Eu3QB6jDod6rwOrMlTm2tyRW2naHV5T/2KL/lFzuEAezBBmGbxS25GAqf2WfJ/+ QxnZg5pz9KMqJqN0wBFvQ4xq1YpBpVCXfQOO5Mtzet/DZfcMRY8JWqLH+zJGWcIbQFa3 QCYZAbML4+6aruZXl6D19Ij1vttHWv2aQvSSRi5jItWJaKBnv0xsbYaiCaWoCfauSp+c mcfQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=EveqtihCJt7fcxXdeINag7+zgOnp1O/guDL1F4v1dKU=; b=MWCmE3xdkYFEWr8DeY8JGipRagEPWD6tVBj0yQXxpep1+F+eXyQ4raUkOY/PSq/OhZ ykC+BOjZnfTTUzo8Y9QyoWYJ5OLA1jh6QssSoWyNChTKHNtmxhGjhqLltu4LgjCwGouh qkrpk/4uA0qE2Iiy7i6KtGoGhRAS7Btk2qI4fBYBcylo06gKa8W0N1Ojnz57/bqP4OXY nNwrr6M1GqkT+5RoG+jFYJPLfa+2A8om2lBgWt3GGO6PXpql1lZLteSZSzhN0gqY+0oc u+tK7mvl66vKbuYQguTthgUQf2TMiFinPzLsOJGslZ/Aqq1ikPG09V8MN4yLNs/ZiMse DkeQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=iH5wFnjA; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id g13-20020aa79dcd000000b0063b8350bdb6si17424443pfq.23.2023.05.15.06.36.59; Mon, 15 May 2023 06:37:12 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=iH5wFnjA; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242225AbjEONTE (ORCPT + 99 others); Mon, 15 May 2023 09:19:04 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36712 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241373AbjEONS4 (ORCPT ); Mon, 15 May 2023 09:18:56 -0400 Received: from mail-pg1-x530.google.com (mail-pg1-x530.google.com [IPv6:2607:f8b0:4864:20::530]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4889910A for ; Mon, 15 May 2023 06:18:28 -0700 (PDT) Received: by mail-pg1-x530.google.com with SMTP id 41be03b00d2f7-5208be24dcbso9137435a12.1 for ; Mon, 15 May 2023 06:18:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156708; x=1686748708; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=EveqtihCJt7fcxXdeINag7+zgOnp1O/guDL1F4v1dKU=; b=iH5wFnjAsZmRlAplDuTJ9I2hT2yvPCtbCKAQtoKqkq9S613j7lIiGO7vKZbSxzeW9h y+bsbpYKxsSfj0ALt0rm64PBjNnXlkahKtOH0yA3Cur9j3p8fSEUf6LVDIwbYOyemyEx JbYvB6KqpsD9G8GEDUDuDf2iQmVs2gW09IIshiqQf6gjH417PbMKiSGifdc7GmoEQfm0 KYF8J1oWTM6zH6D4HVei6jdxOb9NOAUCc5G2cdQbBoM16/K567m0A03DOMoHDmNhYIRZ QiTRh5AtBQdJ1rnV9qTdcMXoAqu/IC34CoDAq4WgSRaGVQANFFafyPMJBUaFX4iT1wXS W+vw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156708; x=1686748708; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=EveqtihCJt7fcxXdeINag7+zgOnp1O/guDL1F4v1dKU=; b=Zg9PvVcYtyK36IWuGPlk3xYX2RV7DJBbvtvmPTKXkSbOF35PRAK5KLwY/HriRVjyBs e5MWTqE0MuoNaoLGCzF3O98922wbUlz//ZwAoO4QMdRC0guScTuZI0wBgdl5WCuQ+Tza KDjyWCtxu5t6Q/KCAKietNyUqnZvt8Lj5YB/T1h9M/5TVn3ACRs8bwcQ8/NWPZTupXl7 L/POaf8PTJSsw0i26eagJaymnXwZHib4Tcqr8no6ekRLM94A+wOr4XseduEpWdClc8lf /cBsCAj3e1oMIicj2SBi+cIWf6VXzB6d7/ZJhNs6KTgAwenjOhjMzmooasLsFfdahjQ2 y8Qg== X-Gm-Message-State: AC+VfDwdWnQd6dKY+HcsW2tj9ho3F57cOgFvdsNzWmj1aYtJ04HRLlZW HgoDSO04+rqVOCOsyhVvtRmwQA== X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765967483105749281?= X-GMAIL-MSGID: =?utf-8?q?1765967483105749281?= 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: 94138 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6917297vqo; Mon, 15 May 2023 06:22:15 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6fs0qJcJqu/oUfkNzGJ6ERMBInxQ/iPuBYrXSYd4g1RKC5rGBEWk1MquS5oWGdDuzYenRc X-Received: by 2002:a05:6a20:429b:b0:101:4c8c:d1fa with SMTP id o27-20020a056a20429b00b001014c8cd1famr31314147pzj.5.1684156935503; Mon, 15 May 2023 06:22:15 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684156935; cv=none; d=google.com; s=arc-20160816; b=x37KpRmanzCiRE3XK1uFqZO/30D6vWWVIowpMBiIKY95uozCT2bCnQBurP5B/ReyI6 BQfoM/QjIJcSH/Iyh0MbXni6ehWbwVeucTtU5Xhc6t9JoABDzjDoZzzW+yQi/Rt35tja I45Vin4PHa6Gjv1NyhsgAPlim30Dg+nKwivmLSBS4YHAM+SlTudqqPVjzdpGrWyxj1SD x90T+pwBvHLX7KdgoOFlnG4GYGxPpMoWDrscH9Wb8s247cN9PoZCvnWehqusL3vCkvU2 qTQ+1VmDJ6hnUzWC/dZQ2T7kCFOnGdjgVizu0Yggee0qc/M6pp1putKWYOKWS3ksVaXH 8gIA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=7SqZWlsfkbxEd4BsTm1MhrUO1FrEvEzjaPkEdKk7VYI=; b=ivwP/ZCQcXW+nPM9lzey4x5xjV457prNJaowT45O47ruCvuQY83sMLJnKID/SFopQV IpDpZpYCoZ/gjo+kmvvbV44IjRQEVfFsQBcKEW5GBNgf8m4T9niTrGUS5PibQ3OflNCW iKkblItxoa5DDBR2i9QTyYbrzRrPR8eeJr3eIrudJe0UQCl8FpeaqkcALzhyxBfGXSGl kF2kAw1tzbOWk2GxsUYrMy+BnYHYOh343MxXHXKFRO4Vkq65xMz8PBhVXUi/oU0Wdpz9 5bqgX0wJ2Im9M2/22sFoKdps/wtFtY8oVVJen/wpqXlClRKgAbgxjhLNQvQ1l4C2MJ8f +rYQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=V4yvdebI; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id i186-20020a6387c3000000b0052c87a89084si15942816pge.374.2023.05.15.06.22.00; Mon, 15 May 2023 06:22:15 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=V4yvdebI; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S241998AbjEONSh (ORCPT + 99 others); Mon, 15 May 2023 09:18:37 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36786 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241895AbjEONSd (ORCPT ); Mon, 15 May 2023 09:18:33 -0400 Received: from mail-pg1-x532.google.com (mail-pg1-x532.google.com [IPv6:2607:f8b0:4864:20::532]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4D66B1700 for ; Mon, 15 May 2023 06:18:31 -0700 (PDT) Received: by mail-pg1-x532.google.com with SMTP id 41be03b00d2f7-52c30fbccd4so11766043a12.0 for ; Mon, 15 May 2023 06:18:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156711; x=1686748711; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=7SqZWlsfkbxEd4BsTm1MhrUO1FrEvEzjaPkEdKk7VYI=; b=V4yvdebIzkZLzBXRdBJ/cqlNoldxsWjHV+VVk67DXhofASL/pQ6Sn/RCFW7Rit5oF5 eN76yVDQO2rdOlHRbBhgVTYaCnQ1mgf6eLRo++EXcdBEFpoZdNigL3UQaELWi1EcgsGX 8YiAsABMNMu0jqrcVUBl4HlHzlHsKYVVl1wNagcLVG6hQHBfBbhmDiC/Q7kYyweQ1At9 2RLHAfkffK1DlgF30rG5KAP7UaTjJ8Uhdtkv/Pw7AcWh6Y5OF6KOSZ4+Uqz9sEWdUWNA wQnD8S6lAFuhOojjwHM/Wfr84k66hoMehS9bhtXwct8hf+cerazoCuwks9SlHPlrwBqZ Bsrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156711; x=1686748711; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=7SqZWlsfkbxEd4BsTm1MhrUO1FrEvEzjaPkEdKk7VYI=; b=fhpiLqfRfbTJcgg0aySiqCJ2FMC58ZMIl++I+1jx37ZhKFad2hHTzKZIp+Ai909xb4 /0BoFLI+LP1IaSGx54bQxSpv9pqE/db+GIOPSPMcNEhXisPUFRllAI925WrkLErQIIdX 1yTVhc34IM+5vO+YjKmYGf7KmC+xbjx0olaj35GUtm7M8jKzUuiza8D8MH+xo6SbJ98N U48kWG2+YB0Lq87zns+YYmQPWeZgv4kcwSo2H4cTbLv/RtfPmAVdMimH6LimiD35mSp+ KRy3/goZPz13s+xCZ74sFMMN0+Ss3NZ5AWmeOseC8zNgbNMCHShqUGx3NT7fLHGSz2ra GU+g== X-Gm-Message-State: AC+VfDxhJ29YKp3bFt9Wbbu/FVLmvg3NK9wiS7r9TakJDTLQ06sHJqjy A2a2ze4Sac6aoZ+iOVgqpgQXQw== X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765966542750612164?= X-GMAIL-MSGID: =?utf-8?q?1765966542750612164?= 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: 94139 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6917553vqo; Mon, 15 May 2023 06:22:37 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5BFK3UFiZ4AxVUoGrxaZYxngPd29HpGKwtr4FOX2CbJ2SQTY0fkCMf99eaOQhSneLOcrcs X-Received: by 2002:a05:6a00:2d0b:b0:5a8:9858:750a with SMTP id fa11-20020a056a002d0b00b005a89858750amr33930687pfb.13.1684156957552; Mon, 15 May 2023 06:22:37 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684156957; cv=none; d=google.com; s=arc-20160816; b=pAnNJLhxsk4jgmKJSSV80FR85k3/tsey677zuy3k5esNA+ivQ5oZrgAXs2mpk4cZFR 1QXeLn6DJTp6DitWXZiPu5EBqs2l4MBSfBbuMmiQYcTzmmoaki0qYEj3UqcvaZQgfYdW 0NVjw9ytHUlI2sivMDhl1Ui5fG8zNw8f9sWzYyOd216SWa6WRZkMaavUDRzMvRIPKA7s pTZAM1RBNB192p4szbxBusq/4ShtTRsDX2ew1GmzIShLt9pEwsbxG8F+S6kkx2m6V81y e1MYhP2H0j/zwR7le6jxmD1VYOZAGte8/D7G7t4D9ocrOqmNzxs44U8ul7nuDLSu+Ybn OrLQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=eE6bxJv4UCRwtMUAfojMihpw2t2wf00Glyx+cFFRLZY=; b=q8PxryN7FbytirHModWgZoxH5qQDvJkfWsCWWmzPl7qU/sxueghWWTPZ0QL60MgQXW qnKxENxl7IBx7G8+w+7w1eW3d2PXotN2MaWX5hjcjOhOZKwD7H/oFJm8AeoK55zvGevr csb2gGPJGKHL8DbqXPs5r79X3LRo1ICkP4mnWnAtBr4/2/Ee7Yd2543ko0MADDDFsU+B IEGtjYB94a/GQoc3Jty05cK0vgfj4xTDNyRgRpeAvMLQjJtldnrun1WYnW46cHDbW2GE OyjrLLL5IEbD3Q6HM5hf6FSULMEaPxXztbB0AIzPnBHMoXfLbfKr/LQiDiugIRzMq25x uf/A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b="i/UBgAcv"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id t17-20020a639551000000b0050fad5c9f36si15908756pgn.354.2023.05.15.06.22.22; Mon, 15 May 2023 06:22:37 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b="i/UBgAcv"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242146AbjEONTI (ORCPT + 99 others); Mon, 15 May 2023 09:19:08 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36856 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242126AbjEONTA (ORCPT ); Mon, 15 May 2023 09:19:00 -0400 Received: from mail-pf1-x42c.google.com (mail-pf1-x42c.google.com [IPv6:2607:f8b0:4864:20::42c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1BF5C19AE for ; Mon, 15 May 2023 06:18:34 -0700 (PDT) Received: by mail-pf1-x42c.google.com with SMTP id d2e1a72fcca58-64ab2a37812so19850730b3a.1 for ; Mon, 15 May 2023 06:18:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156713; x=1686748713; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=eE6bxJv4UCRwtMUAfojMihpw2t2wf00Glyx+cFFRLZY=; b=i/UBgAcvtHHk0md0xZxj0CroBxW4tMrmR2bdSTljlwKSLUD37aMCqdoB3xk08hTz8B ufwwpJ4/L8cFSKLhE/WqTszR14LYvDzpcrIs/zqzfddiaq+2m2lw0NJCccNrlxMYyUvJ z+6U/6D/Qxi0hOTLOqKuqc5SYDLXl3MalzJyFHBS690apJ25rDfSJMcS5XNL7Ad4MgoG 2ZruXFiyPzOqwMXcHF1dtyY9Ilkr7c+KJiyAfj3qLEGXNCE+n1yWwNIF9IM3kY5B2ipY kRutjohJOwPgYtotGv0CjxTX4YlT2ubdXf6t1Lx3YoAzu+mX2+WJ34qbuIwPJloqSmRd USGg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156713; x=1686748713; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=eE6bxJv4UCRwtMUAfojMihpw2t2wf00Glyx+cFFRLZY=; b=f/pnXCjAos5xuHFEOGX1ydddRn6H9dbJzfjsKitgOE9Sgu/86zdG8uFanMrerXk2Dp Juhx34Erm0c57HA7hemJSIcG+gE54CS3MCZV/NoVy/QteBfShOvoUuysJ1eGohxBG8a0 lO1QeojkBw1FdxNeF2CfNp0cRFvopbtwEsVcjiI2ABQx6qdG5L8NIaVCK8UT7XecA+3/ 3KUpuNXJVUE1sU9MKY918NzrNEz/rI/RhIJhS71jmJAi08tGyeup95B8g8xn8l18oqIu 0Ldi6vwbIBsONmcrGam2DTRat/gPNZ3y3Uoq1Vq+4GCeYmWTjCEygwgeIg0pd2NI/by9 s86g== X-Gm-Message-State: AC+VfDwm0mKftVx3yLAR2Nd1FElA6eGXoLvyQgEmcguPGo7ziXtcPDhj rkxEra/s+cyS9wY7Rjg0JkIR1g== X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765966565980849196?= X-GMAIL-MSGID: =?utf-8?q?1765966565980849196?= 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: 94143 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6922093vqo; Mon, 15 May 2023 06:30:17 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6hYTPhCtfUXc5Ujxax3cjaDDE4Og0gHxJ0KJKVLdVOMjd+hzB2M6Kf7NxwrU5SaK77GnJZ X-Received: by 2002:a17:90a:bf88:b0:24e:f37:a6a2 with SMTP id d8-20020a17090abf8800b0024e0f37a6a2mr33021222pjs.21.1684157416915; Mon, 15 May 2023 06:30:16 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684157416; cv=none; d=google.com; s=arc-20160816; b=vdWtOjEou1YARcG72SUfuy7yOV4zPc6NUxLkcqROllfyhywDp5gvLtnsNWu0yZCeBa /m7MtdyAXvA3VZ93C2nDiQuapylUWa9Hetm/vWhEoOhrk3jOvx91Ia3+aI/lmlXwMmYC dUyWnz8EhtGyeHAgTtr6pxi9V1DKNHwzY6NLRwsPGRI7pvBV5svmzTjbDhwhJCxX885K tXfeeCRLCu7xSo07SDTEhY9sexXgi5wE0Dwcjn6dnigt6k2fUA089HTID4YWI4P1hmcH tpDt5uju7syNhu3MEriJVzVgngE3tTrkf+nuPS8izL0PsmFrhPTm1AAUc0lkwZCejT94 ualQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=aUBDvQ6OxE85hUN75/9d6LlRGyHmdnE5erOpWtw5OfM=; b=AePdb+Axm6azkNGfbFPsk24L+GihTKQznrm/2ZKvJjqnph/CY9rTZjiDmTbC9sHVq7 soN1+W+J7j8Fj+IAgDUnSMy5xafLcfPcgBC2l0rHDNWIOVoSthh+I7lpF80PcsaOpQPO Gr1PJUlWTLp1ZN5a79e8JxSUGCpVuvEth4vO7e5OKu/z/NbPbVqaXMJ7HMMogJJFOuDQ UVymtxi9PQTCJVMJn6EfLeOCnC6HJYUJ75JE9CmWiJlewFlAJ26Y8F2xn8Ej77sYIT1s QY6hBSaBxUsKCXUz3oDOeJ+EGrC0hpW0gwR3Pptbowm4baV/W+NbTJ4vANcs3NdwxqBe zGgQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=h6Vztwd3; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id l11-20020a17090a850b00b0024e1eed547esi32198384pjn.96.2023.05.15.06.30.00; Mon, 15 May 2023 06:30:16 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=h6Vztwd3; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242324AbjEONTT (ORCPT + 99 others); Mon, 15 May 2023 09:19:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36838 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242161AbjEONTB (ORCPT ); Mon, 15 May 2023 09:19:01 -0400 Received: from mail-pl1-x62e.google.com (mail-pl1-x62e.google.com [IPv6:2607:f8b0:4864:20::62e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EA3B21FC1 for ; Mon, 15 May 2023 06:18:36 -0700 (PDT) Received: by mail-pl1-x62e.google.com with SMTP id d9443c01a7336-1ab1b79d3a7so87373935ad.3 for ; Mon, 15 May 2023 06:18:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156716; x=1686748716; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=aUBDvQ6OxE85hUN75/9d6LlRGyHmdnE5erOpWtw5OfM=; b=h6Vztwd3Q0rJzgXIQWj9b7a7rcwv/TKvfWHjSn7rPgPVnAwzRGI2GP2i+o8GYuMB5E aFz5inFtgIpGyz7XUMKZ8NAGKJ2UwZd/ZzAsQAY/TwHMA4dDvZVjhcKJH8cmgzKa5Swx p7DSkm4BzQ79R2MDK7TXkdd1dZguunFOryYbs46vMi+egL28fjmiOO8jIrx4iOF7vr9i OKY+sLoB5kvFPjKxPj9sWkbW/s0CEXb2sziSUikSXgmAk/sgii1jOrPbYFVaMPRcUgCE xd68Wj7Am3v6yO7HSaTtRVlczCvuTvBSSnCmKeycX0FpAHhU7HQbnQ2JhGJPm6fRGUeY drcA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156716; x=1686748716; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=aUBDvQ6OxE85hUN75/9d6LlRGyHmdnE5erOpWtw5OfM=; b=Edon8czEWICPxWiLwf8eso8JOaeLsbcaxSq7EHN0nh+3zqwNlciC/rTfu1KfPi5H9v WFtCPujSVCfO5mEf1vO6yGpqnNP4UFZOYLvW5eDlD0g/Xp9Tno/PIdk3818tB7Ieg8q0 9tiENXLh9ij0D6lieECok3E+XjiuWALn8nMHFoGuzMIUPdyybjuduEq+eeGj5wwRI6Qc ss6b4PNEdCZLan9IVW7e0tM6FWj60w0N5+8EHlVRDA4/04VeS7xGjXDvrP/t7IwcbdMH qh880ygCdixQE1kmJkvOq0w8Cp22McMmXvB2RXuuYUE+veMreUR0PJwyFbTbHX7HVDxu P+mA== X-Gm-Message-State: AC+VfDzc0U1Bi8OyLo2CLum50FeQJCqM3YDW9uo4QnTPHJrIfYA2GuMw XmQ/D8CAJf7PXUsWpZtge4s1/g== X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765967047558839297?= X-GMAIL-MSGID: =?utf-8?q?1765967047558839297?= 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: 94150 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6927347vqo; Mon, 15 May 2023 06:37:45 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ75VYjSHydxCdeJQ66Cnbw839yKweLD+5dSrK2e1izjxOsP0s9lbcnTCl/bercKqoQbUS29 X-Received: by 2002:a17:903:124f:b0:1ac:451d:34a with SMTP id u15-20020a170903124f00b001ac451d034amr44714812plh.33.1684157864794; Mon, 15 May 2023 06:37:44 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684157864; cv=none; d=google.com; s=arc-20160816; b=LlKY6v7pr1vLqNr0sli4W+KSryTVs2J8ze3HbwUWyxkK2Tf3C6/P6PCTXQV3gzYqUJ 2AXPlE58n5UR5vmaOA3XuvmUycPgAk8KNy/ATGEYDxtAxMoie7Ca+pBRsAyJCm67wtSB 28RYDHnVcjXERwQh1zVJGkVMsV7MfflvdTCrxl1h9/9lcI8PL1BaEIzFhAcrHs9NdtNK HaJDEtASeWU0J/xIu9wjVB/caG8GlkkrPuhd0SSC5V6b8oy0JpEvJYAGuy0AQgFKtV1M XQTdhxOY/IeBzTvhk0uQ+UPJ8sV82CA2V0Ka7/1uNHTxCTqBe5iQB7X0X08WSEcVsQN8 fUkQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=sHW4PAZciOvQN8kO9ncypAlcJrM+C64frREEyy2mYLs=; b=R3GglCpdDAm5+TEYmd7tyR9lCWuqEAV5fD6Mb6l0inXEWuRjM36HVo/Byvwx5yXn6X S9utqptSThzyOLSdbvbn+dnVaQuMg8B/sFx4KVRS0oU5yPvg/3tGCBumzGnh2jlnKcDr 9QVyjQAXHncnP+FByVacRPu+873dE5/W+/wz/U3Vm9tg2KkggY2aloUnR70TlBi4caQf TWtWnXI0sWN6kh/Ak02fqFnFgIa5pkAsbp6FkMQmMABSoX+IO1zmrzkUs0kiiR+dPi5Z HhZK12CMKdAgV+zGrcCfPV58rLPKxJkAH6JQULUJO67TG7Gta51KryjOCmV6uibWjT9z Z9Tw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=RXRsj1EZ; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id l16-20020a170902f69000b001a64b2dc495si17501250plg.462.2023.05.15.06.37.01; Mon, 15 May 2023 06:37:44 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=RXRsj1EZ; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S241866AbjEONT3 (ORCPT + 99 others); Mon, 15 May 2023 09:19:29 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37074 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242244AbjEONTG (ORCPT ); Mon, 15 May 2023 09:19:06 -0400 Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com [IPv6:2607:f8b0:4864:20::102e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 54C3410E7 for ; Mon, 15 May 2023 06:18:40 -0700 (PDT) Received: by mail-pj1-x102e.google.com with SMTP id 98e67ed59e1d1-250175762b8so11100595a91.1 for ; Mon, 15 May 2023 06:18:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156719; x=1686748719; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=sHW4PAZciOvQN8kO9ncypAlcJrM+C64frREEyy2mYLs=; b=RXRsj1EZsY6H5AtAWlNnNwgRH9USWx7rFebmnNSxWVp7B1o8CDstfKLsgde6nsABW+ pMXRGo37YS/kX6dHNMteA59tSoCGxbUBLZ6cO6Wq1ucLmJE1mXUSHZL5qT97ZRlk+fbJ YgjpDtflzI7axWqu49cUqsNwfPNMCiyD3qq/tywbO7P5f/mCdDy0qhzolJj52EcCpGAr GKc9dC3OBrqikC20SzF+ImqrLV8XP+pqYgT4oug34pP7t7GokRQqeHLdEQLgrABz7mAS Fw+7+talhdXjs4z04CsjkXHbdEZEdD1QbNbIUtQaIk+BveA94b6E915qmJKJ6sFUuUS/ qcvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156719; x=1686748719; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=sHW4PAZciOvQN8kO9ncypAlcJrM+C64frREEyy2mYLs=; b=GSIApPwJ7SZrRwH2MJsKEjqxx4PidutpiUwz+VxihY+ADgprG7ogY4D59jeb4HiEOY QNxYXGtp6hLnFr0FH6giqqDTXW59GPXdbAVYI3BZ+IcI88p8xaTj4iIgR73kOg710sce FgIqeTLPL3ioji7rV5d57hJsLfTj6lRrFl6sN6flDCPBPh2k1ryfb47gxOOoS4Zorkjt SGhCRTYdoSxRC/HVjQSthknSsjkUOpWP2SmHmLVC0joDMOT3FaWayKgs24EbQWs4aYcO 9TJObbApvC71yPaIzdwIP/8jPJ2NM3s6DUoJ9zZegvwt9I15IXEyJzlct+3rLBJNYZYL vTQQ== X-Gm-Message-State: AC+VfDxzR5r42foem8PSCxIUES2ikIA3VIb+uHvGk1HeMPdsRyT3QA0X aKIJ44wf5vbnmJYMKwA8g2KvvA== X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765967516988904855?= X-GMAIL-MSGID: =?utf-8?q?1765967516988904855?= 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: 94147 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6926937vqo; Mon, 15 May 2023 06:37:08 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4f/ZyelNodjAlurzemvZ0WFDgKre1WrzFfm2MyBV2cPxmjwV3JxM6CsGBDKZ2JUcIARLKN X-Received: by 2002:a17:90b:2305:b0:247:6022:9595 with SMTP id mt5-20020a17090b230500b0024760229595mr33958400pjb.45.1684157828023; Mon, 15 May 2023 06:37:08 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684157828; cv=none; d=google.com; s=arc-20160816; b=05ms4WcjnYMDSWlJUuZSpkaK/N4uDapJRRzDQxXYnJ7T6OOfs/44rdwmyuEO/KZ+dI W1i4j1guwTidI40UwWiM+JCdH/KbXftbdEl3g0JUL31B0xDBjXz2PfkhOQ9N3fnXX/f/ ROeRNdmojI0vAWUSnAtF7WNm1MKfq/BvyYNfqfcafhWzAs2X2rR1W4TkQl+Y2c02Qinz cL2iBal/w40+AvmN/wAtC2PAVbPnOLy6SQ0wEY9M6ybpcCPbAoIRvmfgRDyKriiCjUd3 YMhnTVmSXJs8cSbflpeGcZoFtqlxHvHN+WVnVpQJW02oR/SqOYDRpqQ+ochintATkp5T 4lSA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=lo1IIZfKjDP5LNi0dc+D12owX90CR8s5tkIi0vNkd7U=; b=AG2aNm4IH6EQ9bDzDBrCetXDfuoDB461q+cWu8m7SgqL64f7Rooshu3NSbS4XgSm5E cYMVfNGcsoV3gq+dzBLIoPz09JI4JFWmE5YY5bLBiwsGeMhXfit6u1+JGvM1P5OKOGoQ eVtAqk/05cZ40Eol45IeVGsotalubbcYNsIRL4twSF2uuKorloAHdTyVMFwHnkdNusIf qbcrH+U5uWcfqU+5a1qQNsUsQvdt3SqNlekFuQwGUfhBv9usdUB/h7ABaojubFR3r8zL zy4zI0aGgCUd2ja+zo5qJuvDMYFytNRCxN/QUDKOD4rJwwry0oEI05wpshzMBoqiDQtt OKVQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=iRq9sScO; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id 29-20020a17090a035d00b0024e341eddabsi26919896pjf.53.2023.05.15.06.36.55; Mon, 15 May 2023 06:37:08 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=iRq9sScO; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242130AbjEONT7 (ORCPT + 99 others); Mon, 15 May 2023 09:19:59 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37374 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242098AbjEONTX (ORCPT ); Mon, 15 May 2023 09:19:23 -0400 Received: from mail-pg1-x536.google.com (mail-pg1-x536.google.com [IPv6:2607:f8b0:4864:20::536]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7FF9419A6 for ; Mon, 15 May 2023 06:18:42 -0700 (PDT) Received: by mail-pg1-x536.google.com with SMTP id 41be03b00d2f7-5208be24dcbso9137603a12.1 for ; Mon, 15 May 2023 06:18:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156722; x=1686748722; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=lo1IIZfKjDP5LNi0dc+D12owX90CR8s5tkIi0vNkd7U=; b=iRq9sScOWZTCRfloTGbziN9cAC64a11zOsNkjp+5c1soI+3pRGWoucKuYa0+afBrM9 KP8InFDQgvCjKmHotLh2wYIyXRzWHtTPq+Eu/2q4uz7EHQaV09LS/cg0LBz50XCOSenv 5TIATnqEPFgNUuV8mtQuISYyzUH0xhNubca3DObs4XwCQmcEhgMKj6lZoQBSaPM42/p3 ZPnakXFKNosi63bdx6zJYoyHGjOpg2rxmoG3YBjH17UsScQn6r/yNgXEZSpXMSaiPPvO sVodHaxkosK0wFyiC0Hn2X0gh8Q5Iww84zRZZ4k5Aa2XQix6BKn1naSGI7OW3PhFCTqn VtCw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156722; x=1686748722; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=lo1IIZfKjDP5LNi0dc+D12owX90CR8s5tkIi0vNkd7U=; b=YQpevQl3CrWyhZqUs/Cqo5sOMj1fDC0nuGdLKCJNbOOfX7DcND+7YtaVFXspvEdZ+B ILDHR7lRBwp3E65yUh05HZA8WbF607jvWhGvEpETth2AtxV78SOHavPOXC62d7CQDBI2 0RoEF37ZGb0cB67SxOlQwf3g2NGiuUS7+29Wn1LY+68kSpiDjEKWEPHXOgbASAAFTnrr F8xdPrLWsXoZyc/aQ7ttot8k8zn+PCGVd1MmRTxXkEv0WzqvDnnoAScNvZbb2IgnVkT7 3LyNaYxXv+wtk5rGTI2BP14BAMeDB1xP7CrFcz4p7nSRMCiayWG1oarK9UwYx0mNAw+Q 8j/w== X-Gm-Message-State: AC+VfDzINvCkH4VGeSYxYsJ2WbppwWeGG9rrJsG6igl8rEtP3/lqwGe4 N969vAr75tFAW0fCSwV5iuEUrg== X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765967478463472024?= X-GMAIL-MSGID: =?utf-8?q?1765967478463472024?= 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: 94141 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6920470vqo; Mon, 15 May 2023 06:27:36 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7NMiuzaAV4MPNf1KejoFNXg5Hf3CgZKmRYJYuYQ4puOgfcCWr25kBvmup1t7afDwHwO78E X-Received: by 2002:a17:902:f54c:b0:19c:dbce:dce8 with SMTP id h12-20020a170902f54c00b0019cdbcedce8mr46621381plf.15.1684157256013; Mon, 15 May 2023 06:27:36 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684157255; cv=none; d=google.com; s=arc-20160816; b=Id925l2eFcY7ezIa7+sIUKbKBsx5DvkRRinGPrBF+PZnBtSz0lN7JbRmnP6TXUtgO+ K1MlC0b38W0VLN6IEOfjzbbbRraxEKJFXhUMAUK8QA75ZroNtm9E8vHBRGLQA6jruXPO Hphpy6kR/53zPNdP5kAE1Vni1qrdksZRemnNmfqVg9cEk9hZvlllo7bbWx9s+9JYHnBb +S6TaAuegGN5tXTvGYiew4ehdBQFkvTZ5CIgyHARpacs76SSAQM3wBmv9my5EYfFnr7o DbWK0z0Iw8ONF5JtzYUqyL8g2ZsMc7b9nJhlAyPvruLZWSQeSvq3Qc0vYwVPqq3Ds8Js RVPw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=IqadHapDxpeqihp1W5tQfDBPl6INO7/UDDkBv5UKJVo=; b=Kgt0wTelbRux93pL2adBAneKcC3pCpz6TuhH0lDuwZJzZyZkIEZZXFH90Zo+m+tUAx Nw926L16KBaN2Wu33z1ejsd1x4fnktq3PC8pqx+Hi+w/ou+s+S606+MQFD+jsHz1qR7z w06Np1KoUR5VkWbZ3UG8Qa4b0miBNmARETwt7GNiREAkuXa7C9px/eI9zOsWEaRcVQrS 4L4pXLsTstschwVzcU05LyJ0qDNEiIh5g9IU5Omoieun9WEWK1DwjtagJG2YXNREszmL 5qxplNBHxRzd7IGVhGM6ZWH1QCfA6/Iv9Dy8tVKQktUfO8hW2jRk89UHCU4n0s+tf3Wc KNlQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=IeSw9vO+; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id h2-20020a170902748200b001aafaf1a917si15139220pll.472.2023.05.15.06.27.20; Mon, 15 May 2023 06:27:35 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=IeSw9vO+; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242293AbjEONTL (ORCPT + 99 others); Mon, 15 May 2023 09:19:11 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37394 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242153AbjEONTA (ORCPT ); Mon, 15 May 2023 09:19:00 -0400 Received: from mail-pj1-x102c.google.com (mail-pj1-x102c.google.com [IPv6:2607:f8b0:4864:20::102c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 56850213D for ; Mon, 15 May 2023 06:18:45 -0700 (PDT) Received: by mail-pj1-x102c.google.com with SMTP id 98e67ed59e1d1-24e25e2808fso11438619a91.0 for ; Mon, 15 May 2023 06:18:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156725; x=1686748725; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=IqadHapDxpeqihp1W5tQfDBPl6INO7/UDDkBv5UKJVo=; b=IeSw9vO+5tUCyqhG3uAeGFw3l+kw0p1+xquqjvHnxWcTDJpp+QiZkleh9ZA4o1vRFP LFFQ9RUFpkMznTFDy38B1W2fNinp8wPwPa1vtTRBHgSp5UQx6f2PLig0LbQE8kmt6nO2 QHifAX+73dgUs5UZCtQTdz+QmY/BG7O+cWyKNZ2SpAwB1jo34DRBYtzAt9oEuDSXwuyH FZBXRiFYlwH9i0Q+eZJosITIX0uZu/Fe1ibGzExVWrN66H/hxtWiiRn3gHzxcuvN2BUN iAM0kqw3LiFeiTNOMvkWinAY0QaMmwaZK+eQhVvcwmAFnAs1R0wdpBUmHRoT/A04NjMv 2I5w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156725; x=1686748725; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=IqadHapDxpeqihp1W5tQfDBPl6INO7/UDDkBv5UKJVo=; b=WVCw7CGITLrwLkGgjuwyoYSwhhH8OSV5562xvRf3n086cn9fEn2C6TH46HeDh2Uifb TYk1eIVvMd4bV1OSI7PLvdk3TQ4rFkOSF+eSsk6cET8ryDGOSdi6FzLL3XQUahKKs1wQ sHnC9Y9KWnXkVXmmeHHuTSOK9dCGK/QlgZ+JvCDXMYdyjf5UB0pbfxPzgxeHPUPKoGFH yQNJMcBBt6qCjX/as+cGuyGgwPN33jIxZPDw2iiVXlJb8HcxEXq6poqTUGgJ9+CM3tXL x+UQ53CudBTww2X4ulE5r700eNbS+A1S98CSP7XD+HMQAnWaitAyxrB9gj5CfaMCO3zk K5dA== X-Gm-Message-State: AC+VfDyFragYkG8oeBKcTtypEK540yy4qdY1R/JcDZNu3NSlOglkdFHi CkOaJHVoBIpFty9WHTCah0+wSg== X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765966878705611732?= X-GMAIL-MSGID: =?utf-8?q?1765966878705611732?= 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: 94151 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6927702vqo; Mon, 15 May 2023 06:38:19 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5udPn18KH6d8UakT2H7V6Rm7h/vFyz+77VTRyGEd+Fb+ESTrClx1yA4PsMRm70+Cb42RsR X-Received: by 2002:a17:902:bf02:b0:1ae:2b95:7125 with SMTP id bi2-20020a170902bf0200b001ae2b957125mr574374plb.63.1684157899178; Mon, 15 May 2023 06:38:19 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684157899; cv=none; d=google.com; s=arc-20160816; b=Jj8h/GQ3BFoyXQ9snLgtRgJc+lfXcj9n+NQjfCQzbY2tANtiMAYanJvDqyWfnszB/l RZw8Ld4TXmlpwGxUExf7cif2gH+X/gfYbQZv0qZsP8mVWbD5bVa0qMSctdnD9yH2qduJ w+3AXQTO/gfTYYkDGbekaad8DCFctlmQZZ8xQdrNgychBwHBRxDGUa0LFU5axagRMMZB JCSzoDCF9vPYh/hbEYZ46GXU1OJHrBUnvf6OGXnHPJ0kPY/WsORgITjwoH7lFFqnnpLv vr8gw4Bp7/yP6qhWcBl032TQm2pBq3OCefJN9sbth2+/8F1h42gHre7rH5tlFwJg4q3E 711Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=qZYylnYxW+ETURaA5WORPRH9YUugjQDKMo5It+GAwgw=; b=uzGJkccA4Zw+5hh7kxAA7blslT6X1EQ5zfmu07Hy/eq7QEhGjgDro7hTmZgnKhmCWt eG9jt85u/PK5tuq2UCpsbe/dUYHTGaCwesfAqKQdp0WaKAYPZUiiioQDeuzXAE8iMzmj +tXiEC13YQ6p/raJDF/nYVtLNTTakRaQxLOnODCWwZMgsIo/6slI2BNT3ufQO1KgK/Wx arA5o1jiwPZdT9w45aBzcrMfdeDaH3d6h1QduRY+3uiyq64iLtEVLIXl/g9a13cY5ezL 11JStG7xTePy/wiUCLzJo+6j/bg4/pJqW0OwEHaNcgiKEf+X7XkwrmsyuNq3xRoZx5vS B1qw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=DPCRZ8Pe; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id ng6-20020a17090b1a8600b0024df18639fasi12542719pjb.154.2023.05.15.06.38.06; Mon, 15 May 2023 06:38:19 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=DPCRZ8Pe; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242224AbjEONUC (ORCPT + 99 others); Mon, 15 May 2023 09:20:02 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36728 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242238AbjEONT1 (ORCPT ); Mon, 15 May 2023 09:19:27 -0400 Received: from mail-pj1-x1035.google.com (mail-pj1-x1035.google.com [IPv6:2607:f8b0:4864:20::1035]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3BC6F2710 for ; Mon, 15 May 2023 06:18:48 -0700 (PDT) Received: by mail-pj1-x1035.google.com with SMTP id 98e67ed59e1d1-24dfc3c662eso8556481a91.3 for ; Mon, 15 May 2023 06:18:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156727; x=1686748727; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=qZYylnYxW+ETURaA5WORPRH9YUugjQDKMo5It+GAwgw=; b=DPCRZ8PeVk1ENmOw52Z4ScPAKBiBTNsBCVNhldQbntOjXs6YxIBoJg714Omnu0afA0 zLGyzQ1A5K2TjqjCmQzNeqSRW3COE5zPefIhvLUj/Crqmo8UwQUio/fNg0PgZcoBikON zVBn1YYEGaayJt5l73HdrrEcbmkQY77TbGi3x4JLLXEgnDL47DabM9MSP32oohkmterc GN47DENhqMPgATZtYIw24/XavgPj+Qgkwx07ymQGqty/GVBBeFDSpZj2AIWedhbl43SS JQkTuP1mYv/7GA3VbvoaGdzMSswSjyL84Y11OsgVsXxMg7pINKoAGiGJtOvgf780ZDTS A0tg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156727; x=1686748727; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=qZYylnYxW+ETURaA5WORPRH9YUugjQDKMo5It+GAwgw=; b=S37jNbh/gHIKWepEuSTya+XBcWW5ovfcz+w/VAdKzLA8T8R+mfGF0sr8v9SUO+8F4D FCD5PwTTLZNDlkuoY4/CxHaiAvtoDqesOgsatvOnGZ8FRRzVAlI2kf2NkYnaZ4OEW21D FdMcxlO+UCW3+R8NbrA3sb7aXW4zllC8FW9bXlzK2ByNT/MmNOJv6nzeqhFEKDTtWBMH c0Xlyct21DsRS7Ws0VI0zhdHEP/CLZ8nKjTsz5UYk2Q7cBmYOtiZHGH+I3aaiQe4jY+h zlUVCW7VL4tre3yswimP7m3C6+B5xAQYuOMz8Pvb9GRM1AKNalkf5twX+paEcn2b/hDW TmcQ== X-Gm-Message-State: AC+VfDz5kvSzuePcmaqLT5wpQkNARKmkW/JqCmVpEai1FNgjP196jIez SBxzrKJ64iUD5fSRNh8yQUqK7/bEssPdDlAg1QI= X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765967553236461553?= X-GMAIL-MSGID: =?utf-8?q?1765967553236461553?= 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: 94140 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6920352vqo; Mon, 15 May 2023 06:27:24 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5mIyjR9E1O198NZG5MYS70tPwUE35Buu4MF5adku/naJrtmD435j/DIM5dl8PdH0pehFEJ X-Received: by 2002:a17:902:f68e:b0:1ac:9ab5:9d77 with SMTP id l14-20020a170902f68e00b001ac9ab59d77mr28538827plg.12.1684157244043; Mon, 15 May 2023 06:27:24 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684157244; cv=none; d=google.com; s=arc-20160816; b=tYgdbCwHhdHGaLl3xem2ProdoyAVrDfUiodG8jvqKaj+uHIqaGrSwjKb/qfcDpwNaf BqcsSxGaGAbguRK3M5sGxT+pIvz0H/h7F/zxU/CjHEqvPmgSSWuFNcPm3fNFqHYFBK2N WhwhDB3oE3UnykfWTzrfoHJEFOrXRts2L3z7RbNteRh+VvaxpJhbrNf6jt7lK8VfsvLb QIvi7ZjWUIE5c/bI+bbOIjfgAxIn4EQKVji6Vamw3r16U+xdPl3BnzCEf1XBdLgoN+al YDM+tvoOB8BG0GNzlbvhL3uMtermGRXuW2U3vAq3IqljsUJcp7Va7CSZL9laPF7ZV+Io 31bA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=9RjXFpMPucyoGVPKV00U7wCkXQqL8U9B4PmEKn2WMSk=; b=iPcm1BZyor+3fhDheSfMgKSVSFJyATcVx/LPi3ZYwlysmt3F9h62IrFopqB2yT1iqc AAAmOe4a1YShmlGXl8OpiHQ61/crThNEiU8Ykg+cc55Qv8euWwbNJCdgcPatGXLBBAZT PpoR9CMy2s2uaRL6+aqw83OPVREx8ywM1Hbafic19Q0ZlmQ72Lp2f0au7s0dVdjRoh9z yyhO8NdUUrR2aZoHKNR2IIDbVVQ5g631oyMyU15BfUyYPKktlTP4z+ZBH2Ja7KxVW16L 83Gc/WAxHEb4HKAUcCiMVHYrExKOkMCL1TX4S6pyGTwxW+80HeGzFOOPnG+7H57HLFPO HzGQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=g3X23mAk; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id y10-20020a170902864a00b0019f359c651esi14943422plt.556.2023.05.15.06.27.06; Mon, 15 May 2023 06:27:24 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=g3X23mAk; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242027AbjEONTc (ORCPT + 99 others); Mon, 15 May 2023 09:19:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37388 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241911AbjEONTG (ORCPT ); Mon, 15 May 2023 09:19:06 -0400 Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com [IPv6:2607:f8b0:4864:20::102e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 93C642737 for ; Mon, 15 May 2023 06:18:50 -0700 (PDT) Received: by mail-pj1-x102e.google.com with SMTP id 98e67ed59e1d1-250175762b8so11100748a91.1 for ; Mon, 15 May 2023 06:18:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156730; x=1686748730; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=9RjXFpMPucyoGVPKV00U7wCkXQqL8U9B4PmEKn2WMSk=; b=g3X23mAk6kwEgqva0ZnSNN22eZiDL8T82so2num2UEwvQuEHuuabGkvETt7Q66yOlo 7sCxUGlSRdfbawSg3H0s/f5vwrXh9sR2wEApaj6MSgjyAGwixK4D0O2KZEF4rn3SMhPa 7odAfMZB0Nola4ha7jDUcXu/FzIHyu115GV8+4COEOE7VZVh9PVShj6IGKWcE/s5HgMV KcnfgrjKV4nHeILCPRy5qr06r+9wwiHpSwWOiSSOdk9njUM6w2RMr9csBkiWBy2Zh6OQ WZBKoSB8Mo2MD6Aozp/k5sI8+7i4+WxTVhsda+0VLxHL046q2kNIfpbtrRezaW6YALmf VZsQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156730; x=1686748730; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=9RjXFpMPucyoGVPKV00U7wCkXQqL8U9B4PmEKn2WMSk=; b=GYh9yXhV+6yzCUSMzUMeCkj/SvLGyutkv4vxtynYbvLjr7fTCkNHTIThmhHo5YOWn1 pRng1uwOvzQWFdTZvGc4l1mvHNCWL0wbC8sAJn9LsQYPZHoEKOy4ibDhC2Dt6ukgHb9u /SVnKnCES4ow8uwMDxvBWqU8jiMlV6Hu31OFg0XqmXfmnuM5vhL0BO1DoBu4sXWT4bmD 8igv7zsjpQuL478vPPypnqvNA/Y39qsKf5uw6AeOynfhedimCACTTdhTnbEwp7SQfBr+ 6HLAs5qtxTuvxSp6D6Kl04C7boQcwuF+z+EcMU1bJdsimbAZd2flnaOhrtPeSrJRxlgN 1xNg== X-Gm-Message-State: AC+VfDzCOOJLiUE7BAIZX+YUCF4mvuxKwsvkRiSxDLaq1TdcgjPygvL5 5J3U2xMoqfJszKrscOtrLEhTwQ== X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765966866460257469?= X-GMAIL-MSGID: =?utf-8?q?1765966866460257469?= 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: 94149 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp6927296vqo; Mon, 15 May 2023 06:37:40 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7jHMKmm52VzphCigol5bUKgBYyMcbLeikgLg6cyE1yF0feEpwZge/0uZMqN5+8JsjTIvDB X-Received: by 2002:a17:90a:df07:b0:24d:ecf7:cabb with SMTP id gp7-20020a17090adf0700b0024decf7cabbmr33186502pjb.22.1684157860044; Mon, 15 May 2023 06:37:40 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684157860; cv=none; d=google.com; s=arc-20160816; b=B4DAqZQvjiOzBPurmQKhI23d3kFRqvHKJ0F5CJeTdqWQHOG65cC5U9Hi4x4i8oTZDH UX6S8zi1Go6g8UkZNP1YE1xhzgBEmqFexdKri9hkxOHHbGiZW7/fYNqi7JMXB3d4YW+G 07fQv8YfbEM81No3EgXMcp/jpklsjzv/onAVcZzLTB8kDPaYIAQF66M5Xn7nmOei7ew+ q0Q/p3/RwliSZ4JTyiawDC9hgjgxSOmzyu1OzON2hYMDjMKNZU/9iMvs/sg+J+fFGQ0W C+FnEyvIwvfwEi5EXzXdFSTxlE1CsMRsuO5Zwx7dsRrfq21zqJkvXGDa0AtLqgQNl/eE Gvjw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=ArSLVUhdR9DQTTW/HQ0w3hLWCHQGeUGpXjVNbpJHsbw=; b=UTQRIDddjIYZXKjZmC8cUmaDtVVVcca2VzIOVyXZZeGmRRk/S/PZDcmg6sGEXxveGn 5tbf/3GrutPga/oipYH+apNlhLgKG7hONU1x7RbqPyiTCpY7MPopVXu3oCRopb0Gs3SQ 8FYsp9cnPS5n/lueGanUfOo6w2M0txHWtg7jPKPde3ZM/cqrjwUz9NB7ncpT0uy6xcAr EaWwQ9Ip4LRM/I9pY4odFWLuNDRXRYjDy+jvMO/aymJrQ4g0lSenxPwIRW6Sb0R0xE2n rHHNlxHf++KFcLJ9kPLIt4M9qkqavboloWAn2qQq0ovLPPqLUypyjqRo14xmDoSIBMx9 tLzA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=OY1tnyrN; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id 29-20020a17090a035d00b002336940f887si25618737pjf.61.2023.05.15.06.37.27; Mon, 15 May 2023 06:37:40 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=OY1tnyrN; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242274AbjEONUG (ORCPT + 99 others); Mon, 15 May 2023 09:20:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37554 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241917AbjEONTb (ORCPT ); Mon, 15 May 2023 09:19:31 -0400 Received: from mail-pf1-x429.google.com (mail-pf1-x429.google.com [IPv6:2607:f8b0:4864:20::429]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A42E82D4F for ; Mon, 15 May 2023 06:18:53 -0700 (PDT) Received: by mail-pf1-x429.google.com with SMTP id d2e1a72fcca58-643b7b8f8ceso7258939b3a.1 for ; Mon, 15 May 2023 06:18:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156733; x=1686748733; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=ArSLVUhdR9DQTTW/HQ0w3hLWCHQGeUGpXjVNbpJHsbw=; b=OY1tnyrNCLJ8dOnmp29AF4fQG0LVxASZn702ct1srPN3WTfsxFNCBRYdQLYwc6kuWt o70JfEDVIFUdVdNeIH/jJPOcRv9jEbVvhWXHoX+VGSuoQzE4KAv2rLMaD5HqYeqThYB2 leU3yXWK2fpP4YQP7Nl4A6y2ls2C4xj20yTIY9f5SnUx6QaV0HKLQbNCKwV3+/ZHg3bn hwgtpNiJfKbcLKuvi/rJSfuqMI3aUr0+XWuap/hwlD0We5HkP++9q+9T/JB7ZhTWl5TL 0NSOdoksiwNTnC1LHb060N3xyPjGvo8Xmw6pLH5YEXuU+R3+mn9q+We4wQvInISp/lEs cKzw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156733; x=1686748733; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=ArSLVUhdR9DQTTW/HQ0w3hLWCHQGeUGpXjVNbpJHsbw=; b=AwULWNdhoIdTKo/BFbXsVKRCR9Pi2gE4qID6MZYdf5ovfeI0DQC0vla39JZ+lBurmE a9CbhSx5Yu2ucjI7d259GJ/Q2O1YsyaUQmLB2LUiYYfUcGt0/VtoxvJpuqiOq9os37qx ij3aos9U5LWo25zedeUTAoOa3gqcwKjFfoGjOtN37facE3aqRn2PuQbleoweBY8mJ6HN 5jVdgkek+TaFh07RNW0vlKlgDdmnD1SVeUmwiYG8oln/sUGR5xdTjUE36xTilAtNAabF 4JPhE4uU8BI2KAPqyFt1FfPF2hX0JEirE1eNkoC/RJfTWPI9eB80nQvIDCsslXlC1KMi nHOg== X-Gm-Message-State: AC+VfDz70fVPTfiMl467lialtL1RXGKdEb1pm6DS5B7W7l5QB8o0BOJm HPLHq8/prueQJny9tzbjX+ETuyznbBjCnxR5vGU= X-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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765967512241190172?= X-GMAIL-MSGID: =?utf-8?q?1765967512241190172?= 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))