From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id AE41CC7EE29 for ; Mon, 22 May 2023 05:07:45 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4CB6C90000F; Mon, 22 May 2023 01:07:45 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 47D0D900002; Mon, 22 May 2023 01:07:45 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 31C7590000F; Mon, 22 May 2023 01:07:45 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 234BD900002 for ; Mon, 22 May 2023 01:07:45 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id EC3CE4044B for ; Mon, 22 May 2023 05:07:44 +0000 (UTC) X-FDA: 80816708448.20.B6F418F Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) by imf10.hostedemail.com (Postfix) with ESMTP id 1CC0AC0011 for ; Mon, 22 May 2023 05:07:42 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=fw0PRf8Q; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf10.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684732063; 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=qKVnArPifyAdGV9PIImrukiWg2xfu85fuVT0WT/x1lU=; b=n+H9T2FoUgG6nxWNCOzck8OaO3tY+Kc3FudWw6Fzu21Lq/6ghGaMrPYWooBDXl6BHGD3ob O6L0YSUkmqhgy4Y5f/Cefxb2fOkNdfZtbNzp1cPOHisECBMnL7h5Mr34lWMPDZbi5Po4oX NCy7Zpi0eiJLnbnq0wMESVfAb9j9LsU= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=fw0PRf8Q; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf10.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684732063; a=rsa-sha256; cv=none; b=lm5y66bkJf2mIWHu6+n9EHd2zySwKJ9bCyzf7VP3eBpz8xfhI/gXPSOfyS59MMVK8/rAc1 MHPOQi3ncw+zZNNf7/orHUIa2IY7eK5Lobdeapr8SBOCSrQ3W8chYWgjcNTFwaufyCTINd KIrkXgtJD9iCtLC2OloZ2ASfy6roAM8= Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-64d2b42a8f9so2715930b3a.3 for ; Sun, 21 May 2023 22:07:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684732062; x=1687324062; 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=qKVnArPifyAdGV9PIImrukiWg2xfu85fuVT0WT/x1lU=; b=fw0PRf8Q3oQzgqHErNvDCU259xWd4Me2ceXFQD8pISEEcIEQZmk7bW7OJ3mBQ0eywD v7wNxQOQTVF4JZf9ON/6V5aCR3dkMK/NNESMj6wazF1zAw2gwqe+5A9004QgW40Jn8wf NRquXTchX9dImyrXbMIRvklOEHCfUofQg2xsBQ54kLTzcXz6ITsMt/ENw3oUKSUkw01t ZugU1Bcs0+eIsKfAO0I/jngb59O1PU0WvWi6+TwcGR4tuPzFQajmv63m1xEB1W3F+6HZ hJT0pSolSpSQKQ/rqzJP5/QiQVzYL5TvoE5uUy4y/Z8Tftr+0PeYqUwLgjtERfdeYo2D hh2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684732062; x=1687324062; 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=qKVnArPifyAdGV9PIImrukiWg2xfu85fuVT0WT/x1lU=; b=Nt30E+ayXgc7HW8ogJk4UBSLgOkdUXg8kzBqeViae6tEsWd4JwSUPXZLnua3O+8Rut OZ91RZPrLIxqWT8bFWPOINKZMciDdSfMwQxmMWIBH9CoqzCbgIvX0v+FQurdIpTUK78Z ljlaqV1KjODWOAa02JaItK7GJN+O/hgvXv171iqhQDvhluZSdsfVSfpu6+yrLQaQvZ0Q alY8OGD8fZM4cTCCTtJcf1kyoqMoZfomymD1O5Ik3xF6CguNSEGEVwecdmP5c9h9n3fX BZ4sSvQ8O9PBRJohmBtGQYJhJuu0W7mxzBEjesC8Jj1srf4mUrYJaqKjRRhaMHtTdpvD xLGA== X-Gm-Message-State: AC+VfDyLVnyHSlSSaXWQSuygqbqxCG6BQ0ZdVJ37HWGMOwPFMeazyquV MqMWn80U9FMTaoyaJ/fDfb0n4i29YjnNHu9O/o8= X-Google-Smtp-Source: ACHHUZ4ZdOhjPoifK2FNOzw1Dpvr4gjGQyxiMVErjYNnHLBNabOF7Yl4YngE2n94wMJZLny9Vh53Og== X-Received: by 2002:a05:6a20:3956:b0:107:17f6:940b with SMTP id r22-20020a056a20395600b0010717f6940bmr11393229pzg.41.1684732061987; Sun, 21 May 2023 22:07:41 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id t10-20020a62ea0a000000b0063b5776b073sm3247519pfh.117.2023.05.21.22.07.39 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 21 May 2023 22:07: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 v3 08/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient. Date: Mon, 22 May 2023 13:06:54 +0800 Message-Id: <20230522050656.96215-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230522050656.96215-1-zhangpeng.00@bytedance.com> References: <20230522050656.96215-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 1CC0AC0011 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: sembeaitq93cn333t69hxcyd6x3d5oar X-HE-Tag: 1684732062-731007 X-HE-Meta: U2FsdGVkX1/eXU/L/Kom1P6tYFkhIstvVi2d2kTkXClQKnof93dVZMFxeYf89jmN4eY5fru2Rs8wtWpS2TqZXf+Fhm+otiF82UX4E+v2Wyn433uqy/+PYzVMTq2AWCRhfBRaM7tQTlOffJwEAP/1cRZ5jO7/bdxd+K1qC6f7UrNVCiaDb6hEcIunc+PMjdmNhgRUcBoe51d9jIxDt4Mas3yII9U7a2VdbuB82+UqGPObSoa6HZgtPM5W2LykWt+v2kHOfOxqvO4P/TbYQVilNrWTkvcDzQEGvMTNms6O4SGLwZ0SwjteFLBx3nJwSlMMLfvUl2ic/jjQaD9XCZCEPtJK3TFgKkPDgc0wC1GYEJDajFqfHN4eML/uAuvTbRnkaNMVu+D1kUfAX80Jc2eVd+FXrKFvo41xH7dKdkgnYN2oGM2dKKRoBmY2eeBiWsaZuvEWjoGQqT3d0LrlnbiIUQycl7vnMND9k56OwoIOESzUkGP7jopbNiEdcUxFiM7O8O1e31DOasiYbIw5zpB6kJ/JUUnbWIcvdQ+1Kd881HHY/NjjIBwRwlAUnnRiqNNEQbqHEsCZOKmy3PBVnFUQTbAGvbuN+mg767RGsp56l0IOku+ZDECG+kez185Yyg6WbmzOEmlQ2ohmCzNc1CHYvuHO+gZlvTe/CLkAACMNiLfkE3jRPOELO7vihLVS+GJwa6oWOG9lIWzZUXrO1Y+SIEwZ0V7yT5NMLh20H7fXer8L07r1YJPNXRLO/Vxbvy2ClsRpT6YXMdeIawT4AWjTMd/Mhn7J6vXi73O4tWbW1K6oqk0Ozs/hib5AMbA6qPB/pMQME7vbMhe7//iYP7dzYEJ6SnQQYBNS9D60zbbQ/HX0yIe1tKyOdM9H96U6A8uFz6fX/CET+ymN1WmMDk0mNsm4BdkgNh6q9cMJZDdhZrC5Ccvj+6Sp5Kw8cq8TVMfJI7s2acLvOexgIhBvwNu Jic2T0Ib 34xTiuAe2vG8vLnteBRnL4s7b1nA+BJYdvkjnec9gIXoVtXhiHplBEHLvEYZspZ2hpRZFjuR6Dw8a+ZT7Xs4jo7d06vIudMdA6i92CjU2pKwlGCSHnZI86zu83ELad9l573G4vJSW730HYN5vz6IjI0B4GOnWKM46+idWDOwmdc3IVV2OLS0xdFcB7BT+Vxx+J5y7roPb3lDZ7DkNZha1Hzf/XI5jX311/FnW4qswB7YzEXZk2JmDOcyuCdmujSQ0f6ia4EVJpX9mdKtVncm/HUcp/yZCnY12qJinKlYYGRt592oQAyOxYvx3zSiq0D/KrAlAoyNioQLgJu+vWPMYRZAmqZxQ/VdMH+ww/KOURZr38udJwj2Dp9v9N2Liq9shWKGFcc2n3OTmbnpKXVyqb1QlHOA4SVsrtS0VfD3rPLrAMghQmGNynCQVyOIhtWrcO9opAHVjMhaayNKX+j+ZeE2qV0xPLW83/m8HrxeLs6ZgR+MXtt6QsT6IsQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000055, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: The code of mas_wr_slot_store() is messy, make it clearer and concise, and add comments. In addition, get whether the two gaps are empty to avoid calling mas_update_gap() all the time. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 53 +++++++++++++++++------------------------------- 1 file changed, 19 insertions(+), 34 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index afbfdcdde5db..1fc872f7683c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4203,49 +4203,34 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas) 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; + bool gap = false; - if ((wr_mas->r_max > mas->last) && ((wr_mas->r_min != mas->index) || - (offset != wr_mas->node_end))) + if (wr_mas->offset_end - offset != 1) 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) - return false; - - if (wr_mas->r_min == mas->index) { - /* overwriting two or more ranges with one. */ - if (lmax == mas->last) - return false; + gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset); + gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1); - /* Overwriting all of offset and a portion of offset + 1. */ + if (mas->index == wr_mas->r_min) { + /* Overwriting the range and over a part of the next range. */ rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry); wr_mas->pivots[offset] = mas->last; - goto done; + } else { + /* Overwriting a part of the range and over the next range */ + rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry); + wr_mas->pivots[offset] = mas->index - 1; + mas->offset++; /* Keep mas accurate. */ } - /* Doesn't end on the next range end. */ - if (lmax != mas->last) - 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; } @@ -4392,7 +4377,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; -- 2.20.1