From patchwork Mon May 15 13:17:55 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13241443 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id B999DC7EE23 for ; Mon, 15 May 2023 13:18:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 45A6E280008; Mon, 15 May 2023 09:18:51 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 40A30280001; Mon, 15 May 2023 09:18:51 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2AAF7280008; Mon, 15 May 2023 09:18:51 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 10C6E280001 for ; Mon, 15 May 2023 09:18:51 -0400 (EDT) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id D435F41251 for ; Mon, 15 May 2023 13:18:50 +0000 (UTC) X-FDA: 80792544420.30.5040C40 Received: from mail-pg1-f182.google.com (mail-pg1-f182.google.com [209.85.215.182]) by imf29.hostedemail.com (Postfix) with ESMTP id 9DCD1120003 for ; Mon, 15 May 2023 13:18:48 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=DPCRZ8Pe; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684156728; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=qZYylnYxW+ETURaA5WORPRH9YUugjQDKMo5It+GAwgw=; b=z4zA4rvZ2a7arOzsp/5p037v8RVHFjfxsVIBQ4/2ITsL8KCRn/bGl1pJbPU6f1LInJ5blo oBxy22JoTZTA7nBYd5F10KSX8Q5u34U5+NNwiBZHUNnOkN5Ebbyn7xlZ5d4ESWkYr63XqX dmP7C0Rl/Hp63UKd3s2TlMSohEnNc04= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=DPCRZ8Pe; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684156728; a=rsa-sha256; cv=none; b=Af/aJuDXof4cyS7LFOIoSqy/g9jnPVcxWdTDb90k04ylgcbSSgfTsqJSO0WyTKSUf8JS1q 312XVB9ehy6adPpa4nqo3BqVSSuKQvm/SRg/tmq/JqBUjU15h6m78c2HXrGjJ7kIC5mnLy nc4F9lBVcst2sw93MT0RsjLD+GQxHOc= Received: by mail-pg1-f182.google.com with SMTP id 41be03b00d2f7-53404873a19so1071283a12.3 for ; Mon, 15 May 2023 06:18:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684156727; x=1686748727; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=qZYylnYxW+ETURaA5WORPRH9YUugjQDKMo5It+GAwgw=; b=DPCRZ8PeVk1ENmOw52Z4ScPAKBiBTNsBCVNhldQbntOjXs6YxIBoJg714Omnu0afA0 zLGyzQ1A5K2TjqjCmQzNeqSRW3COE5zPefIhvLUj/Crqmo8UwQUio/fNg0PgZcoBikON zVBn1YYEGaayJt5l73HdrrEcbmkQY77TbGi3x4JLLXEgnDL47DabM9MSP32oohkmterc GN47DENhqMPgATZtYIw24/XavgPj+Qgkwx07ymQGqty/GVBBeFDSpZj2AIWedhbl43SS JQkTuP1mYv/7GA3VbvoaGdzMSswSjyL84Y11OsgVsXxMg7pINKoAGiGJtOvgf780ZDTS A0tg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684156727; x=1686748727; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=qZYylnYxW+ETURaA5WORPRH9YUugjQDKMo5It+GAwgw=; b=ScoHYaGM5ZE4HObLgClSRZjQuR7jl7xYGtZpx1XIX64FlOnA92kRfHZjUB8vOI4kkz gh/Ni7NeWVYMKSbJZHxc0dsHCh+cmcr73Eh/E1Z8Na7P6MZbJDe/3VOiFC0a1ar1kvw6 oK0kHhz0aOhV0ws2wptmcop2JefzQNet82DHIFv65wFTpQGZIguBEIEBWSXpxd8By2sp Lbix2MzTHmCOfCGv7de86WywqapFafz9/bwcf+98ulCk28Bfr1ITwnGSCKeRyj0M34t1 hpTzD0nPcOjSm9mLqt3afo3uunzDSeLabdyRiD3IXFJoFCh/l46UaZ+rVMnhAIWbV44x LGbA== X-Gm-Message-State: AC+VfDytwuBl5SQIKVXGr02eIymS4WocCkdRb506WA0XpcdAb8UxjPVn veCDVvuptqLRQsy9d8nmoJgWpw== X-Google-Smtp-Source: ACHHUZ5C3a8EuB22F2PmBbCR3ZqQP/cE8EemzucBxOnJ66cgYoelctIkw/FI/byhP2XlRFxSjJgcXQ== X-Received: by 2002:a17:90b:3ec2:b0:250:ca6c:d7a8 with SMTP id rm2-20020a17090b3ec200b00250ca6cd7a8mr20083096pjb.29.1684156727502; Mon, 15 May 2023 06:18:47 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id gl20-20020a17090b121400b0024749e7321bsm14190014pjb.6.2023.05.15.06.18.45 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 15 May 2023 06:18:47 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 08/10] maple_tree: Add comments and some minor cleanups to mas_wr_append() Date: Mon, 15 May 2023 21:17:55 +0800 Message-Id: <20230515131757.60035-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230515131757.60035-1-zhangpeng.00@bytedance.com> References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Stat-Signature: epzjksjczgyi9jntfuygojjkwxwwenbt X-Rspam-User: X-Rspamd-Queue-Id: 9DCD1120003 X-Rspamd-Server: rspam07 X-HE-Tag: 1684156728-769730 X-HE-Meta: U2FsdGVkX1+Mg/lb8leGdPjog4iKQJC8WjmZne+ZGa8wyjePFXUKrMCzQqPpzxoIxGl0ltSbSAzNEk0ZuUr5+0LlflB/kPogHOYDeGL7JCP+1C00DsVwauhxHD1wgTT39ypgc96h2b0W+/yFGp0pah3Um4Dz6cP4fXIX4c97uuc/twU0Ca69xZU+Kp1W4mN9tYg+gc0PuSfP8ow7Rqt2SVucxIRXd4A/66QctZtJhupS+AOlQcmbCQNR7xBYJaaalKy02oxL6WfNx6pOnj9LawEMguYFzpeIjBiskhPpGEEaXw401b+xGvFPgM2E989bBPkx2TL23lTcx4pg2dnvbH39Njet2tA8mJ2klHrZweHImIHz3VIr9e1KczfDaLyqZNpAREyRPhsyGNTtAfnUvsFi931mNIeU35UzU7J6SArfjoWXv+322Ot9z5R/JpFwHYGRfOD8vlSu/5FHbwBi+I4OEHT2koe58YZUv4YeSnCS2LiLUclf/kCECEaPiERco9+qBjUr072hCBAdch8tX1FZtaiDRFlN1BI+9Xy06FdDqtSS/FiWnUCvTdgd9t1u8ua0si7cZhSx+FBm2iSdH2Zw1tLJfiUXzsOTu9iJaWaXeXiIEvWGSHOipIOpkaNxqvKjpndMLw5ih9lMgY8N+9qrGK4x6vFiJ5YE3GUznZspcpvy4w1DBjNNdwCoXuccH+hYyWyx0ROGrIA7x/YciYYIhlL1M23kZztZCn/wEm6IppT1COFRbbpLJotTMUpKiheArhlR4z3uCgzy34CleL811M0EsmJ3J8Ry3C6zX2HqmsuQ2Vhl0Rc5sW+5+SyflV1M0Q/D5XRQp0G+GWorLmug/encq+UMtrqpYcf1dfJIAULJMufz5tW63dZNsUQy+lupG/s5Be2YJxBldI8MXbu6O09pP8akVtUjyaMsEL8OOEzF0q/E25Li+wMVEwVw9OAn+ThbBFWNUrV54DV UfloRcex Q0p2brfhyN0sG/iJq2UO4Fofsw28gzwjJYFktZmwtFbtVg1fWzkzoxgItkTutBaOGJSoX9c/Itd4vrw6cu7Rc3PioTk33OwcRJC+sOGZWOtBsTbOySotNkB3NTpe5gd0QhurqKGAj9x7nNfaT+f02VQSmoTwM3bOQDHb/rTPGSPe+LoHk9pUffG2ntvhpErMfp9cXRNpvf0Q9SGpdpaA0GeDvnFw9eKIi5bzpu3fmlKGFDiGN5JkBud/uQnq83ZPzUpWmBnsKbQw+x5xKRK/IGeUoAP1wgex/gDvW5AiEcFFl0laKQzOgJdfdmRTVYfaEMFWjtmLnziqP4jPuMFsxbezt8fsSkq8W3Sl9kYHmCN9WXJHQan+imtHfjGiTLFNdttsHo6ZIi2Ia1YOMu8Z7IvhSqWJ9zTrpCMn/6qDZ7uE7cC4fPv+kOpbcb2JdQY19ftyuPs7Z9dCIaec= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Add comment for mas_wr_append(), move mas_update_gap() into mas_wr_append(), and other cleanups to make mas_wr_modify() cleaner. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 52 ++++++++++++++++++++++++++++++++++++------------ 1 file changed, 39 insertions(+), 13 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 20082ef8c396c..538e49feafbe4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4315,6 +4315,31 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) return new_end; } +/* + * mas_wr_append: Attempt to append + * @wr_mas: the maple write state + * + * Return: True if appended, false otherwise + * + * Case 1: + * r_min r_max/end_piv + * +-------+-------+ + * original range: | |offset | + * +-------+-------+ + * +---+ + * overwrite: | | + * +---+ + * index last + * Case 2: + * r_min r_max/end_piv + * +-------+-------+ + * original range: | |offset | + * +-------+-------+ + * +---+ + * overwrite: | | + * +---+ + * index last + */ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) { unsigned char end = wr_mas->node_end; @@ -4322,7 +4347,11 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) struct ma_state *mas = wr_mas->mas; unsigned char node_pivots = mt_pivots[wr_mas->type]; + if (!(mas->offset == wr_mas->node_end)) + return false; + if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) { + /* Case 1 */ if (new_end < node_pivots) wr_mas->pivots[new_end] = wr_mas->pivots[end]; @@ -4330,13 +4359,10 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end); rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry); - mas->offset = new_end; wr_mas->pivots[end] = mas->index - 1; - - return true; - } - - if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) { + mas->offset = new_end; + } else if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) { + /* Case 2 */ if (new_end < node_pivots) wr_mas->pivots[new_end] = wr_mas->pivots[end]; @@ -4346,10 +4372,13 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) wr_mas->pivots[end] = mas->last; rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); - return true; + } else { + return false; } - return false; + if (!wr_mas->content || !wr_mas->entry) + mas_update_gap(mas); + return true; } /* @@ -4385,12 +4414,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) if (new_end >= mt_slots[wr_mas->type]) goto slow_path; - if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) && - (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) { - if (!wr_mas->content || !wr_mas->entry) - mas_update_gap(mas); + /* Attempt to append */ + if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas)) return; - } if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas)) return;