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 AEDA7C7EE23 for ; Thu, 18 May 2023 09:27:40 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id EC805280002; Thu, 18 May 2023 05:27:39 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E76CF900005; Thu, 18 May 2023 05:27:39 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D21F0900003; Thu, 18 May 2023 05:27:39 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id BA793900003 for ; Thu, 18 May 2023 05:27:39 -0400 (EDT) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 94B71AE134 for ; Thu, 18 May 2023 09:27:39 +0000 (UTC) X-FDA: 80802848238.24.AFA218F Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) by imf08.hostedemail.com (Postfix) with ESMTP id A9223160016 for ; Thu, 18 May 2023 09:27:37 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=f2Wnhvlv; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684402057; a=rsa-sha256; cv=none; b=sPnkWJzZEWVF7DmVKhzcVDgYKp/oUalsgXQvtY0Jo6xOhyMVgnpE47E6hrVo34ZGF5dh9F 9Z3OU/UbCRNOhOyi2GQ66cFUfJBt2X8c/UoIiMQCnao5FVTWgBb1XYYD+Ip+DT0KNUNeKa jrQed79cTBGW/LYlA9elXGpvoX7KKuU= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=f2Wnhvlv; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684402057; 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-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=wSani2RG74ENszir6YKYpOk7wlORB/U+hT2qJfC/37w=; b=RByThABqC9Ijkq3wOHRcFsixPQtFL13k4XsdTVjOrd9dY6wsH761fDcRnFH2cQcHD4oms8 fcxEqrsq0FDUqSWOPGK9+fH7RyhRm5cgfON6zA4s771Y3IcKfJXgi7akbuAL57NND6pBUE mkXEkn43cyOzsIywPPjHvZTVTmKrzgA= Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-64384c6797eso1406856b3a.2 for ; Thu, 18 May 2023 02:27:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684402056; x=1686994056; h=content-transfer-encoding:in-reply-to:from:cc:references:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=wSani2RG74ENszir6YKYpOk7wlORB/U+hT2qJfC/37w=; b=f2WnhvlvGt/Iy6xTwm/ELn5F6JNejWqd+MVcF67lDFmUaGH1n1mwS7zxkxpakrjR/T oicroJpUsNYYanIje8NGNckK0qRlHNn07x4ltVY8K76TzUvPqfeXHcrjzoZegUiNCMEU or6pOiPgrwGek9BlzivMsWx9sgHNZWwnWeR3EytLkoDQmau5Rlelz85j9BqHKycdJO3G hHlQavazTqNhsQvkGPTE8o8xKBhgXoK2IYGpLAtTeo1ZCPQeNTMKtk/oLyOsBt2vhIN9 pfmBx4tE4HoH1pTKr8BfAJ95d0ECAh0AUkRS6fAczbF/Hb0M9mwjN7F2szxCPoi5cg8c x0WA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684402056; x=1686994056; h=content-transfer-encoding:in-reply-to:from:cc:references:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=wSani2RG74ENszir6YKYpOk7wlORB/U+hT2qJfC/37w=; b=T8m12WiY9oMvzYxMW0Xap+8SLCp5kGxomSHnTsBOJCySaswjZSl6tpOfZp8iQ4C3f6 2vq4EJsJnSJbQLp6zvRg1UilF4J0ghUXT/yWiD51eki+zlYKFLylJOxxesz0WimP/M0Z RuVxyZyCYauKqfdlT7XTHgMBDvKFafjbkyuL4hlSWfwULJKc+lo9eKjN11Q+LXR8u/U4 6SnyfHt9nm+y3zYsjQIeUSqc/StS9uQj93wnjESSxJIj+7GeEGwdgDw6EQiaWrdvzICQ pEd7gMx6t+SKFDPtyiiQIatiMNFbjrquP1alTBt63lq0r8M4CJldHGpYqyvoF0tqDgJZ VkdQ== X-Gm-Message-State: AC+VfDz0TFucYRS9SnIbaZ+HEshEaicyJ9D139xma7/Zf2zcivrqAppZ CvbRADykMByu7lnZgE9Px+xGEA== X-Google-Smtp-Source: ACHHUZ47IVM+ryiNznhRL+Fn4N4tF6nkRP/mG3BIuklC7X/uGAzb7O6UaHght5K9D+yN1BNdr0h7WQ== X-Received: by 2002:a05:6a00:114f:b0:63d:6744:8caf with SMTP id b15-20020a056a00114f00b0063d67448cafmr3461488pfm.26.1684402056623; Thu, 18 May 2023 02:27:36 -0700 (PDT) Received: from [10.200.9.101] ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id c17-20020aa78e11000000b006414289ab69sm937470pfr.52.2023.05.18.02.27.34 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 18 May 2023 02:27:36 -0700 (PDT) Message-ID: <13a3e7cd-b8bf-1aef-b2f0-465ee77f8638@bytedance.com> Date: Thu, 18 May 2023 17:27:32 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.10.1 Subject: Re: [PATCH v2 08/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient. To: "Liam R. Howlett" References: <20230517085809.86522-1-zhangpeng.00@bytedance.com> <20230517085809.86522-9-zhangpeng.00@bytedance.com> <20230517224812.knkhqmrweggsbnuk@revolver> Cc: Peng Zhang , akpm@linux-foundation.org, linux-mm@kvack.org, maple-tree@lists.infradead.org, linux-kernel@vger.kernel.org From: Peng Zhang In-Reply-To: <20230517224812.knkhqmrweggsbnuk@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspam-User: X-Stat-Signature: 3rzmgk9i9bsaepaidsi4ybnzwaa4r6z5 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: A9223160016 X-HE-Tag: 1684402057-166825 X-HE-Meta: U2FsdGVkX192+iiEGdHkU2xs5willZneRX4vZqP1Xq177on2lEWamYHzsdiGxrUbjzqqceD5knRHQsXyMpiKdlHB1ND6lum2za/28g7giXlGHTQqSVepdi1YWMEbV2pScxjm6ne7EBhDX5rMdyW3EqamtVLmZGq9mnYH34s0x6DVyec2heUaRvFLjCiLg2vPF5/9+fDd8PlCamQVTE2TBYTnElD3x54LaoRhyjSczaTv21rnYCIkhAPg9ETtVaXmTgFq/37YrtgRMmu+asAAGrni7RIY7Yqdydzi/DcPKVktzCfkSXtEi51/C10iDtszGKCKDSsjXkvl5rQKtovQHKfsQXT6vNHVsTBalHqsqSLABk9rfUh0nMgGC30eDJ0A9Xk2z48M6qKXRv99wozhRI4rXQYr8INQysgEdqleRtjhlLq2jzEriD2y2nlqeg7F19HYyjZk7HMN7jpiumIzPQBXot/kCLt3qNOCAlu+WWAn9VOPk5pyP5Vha6dRI6hkOBpWyoHwZUqpqs89hlBexO6pZJODzVDI51LNvxEnjjz3YxlDYmFNoGY+cuy0OmeoR6kB4rKErPy1m16fWbhOFfFsLMget5OlpHyrfVPuGDuxZft/RjfkT7haeBGABLi8qmDcxikv0d/NDRay8FqNHcQ0YSiPG4ecRo+Yb68VYGzSKd4uX6Y33pNc5QAViUNMTRegKS0o5+znMtsy79J09k5qrjoRpdhujadMzoGvruc54aP8Gwjbzu0GS6DzUolzTLLzRLY8Zxu91zmAav8nErupk5a3BzsFl8JuB/o549Rv3WiJsutjEzRFK3m6XeAb/oL9jMENLERTGh0anBdy8D8OylPETM2KMew2Er7E+wcdLtSaellfQCe6uZxCOM6ZkSFtrzVqSJfYvD8eiKbxVyU5QKzGr5+doPoOX/i6N8+6isNGARgNRFHIGQ2fh+DjidQjZnFtAuiLEOC8IAJ 9+agJDOD FoR9Nf0qgkz6lZyKStwsqXGhhecyf582bSzAha+CpLXk6w6A2N2uGWjZWREJLJhgSD8jKxPFUk2zleYdheqGicydlR4xdUs9y03Cmv/S39ccXxqWoUZaPXVk8+XYZQJrwyaKtCsW3VZuxKsws3li8+Lk2pnG7B8rxX8WHnEpRnVnymQ7y8YpkU1LQl1hvU0jQT4gfnqoVCT/Ccl/+UCyG3W+NcAjlhGYN3JMmq8rHHLSOXNnyLf31OH+Iw3c7BL/EAnbX4paAeCsOg0YLFmMxkey4DVbDax/KF+rCtkVbJGRINwacsvF3wpTsVZSpVVfOi+t6MpO3CqzpMul7n2hzNkjfouGiIcEzUyjR79xSkVtgZprbSNp+c20irUEMehTg9XFvq/bPq7gxI4MOB/jgCCZT8hhXa0Q2L4IYyFXdXHSfcmCOL/GSjAi9hmy2rl7xyDOaH1333iZEGS0axYjP3FLbFhuCSE3JJTLsD4qKbxaxuv6l0RFdbYTaxw71okSyo2b8 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000089, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 在 2023/5/18 06:48, Liam R. Howlett 写道: > * Peng Zhang [230517 04:59]: >> 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 | 59 ++++++++++++++++++++---------------------------- >> 1 file changed, 24 insertions(+), 35 deletions(-) >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index bbe4c6f2858c..25a8b7d5d598 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -4200,49 +4200,38 @@ 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; >> + 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))) >> + if (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; >> - >> - /* Overwriting all of offset and a portion of offset + 1. */ >> + if (mas->index == wr_mas->r_min && mas->last < lmax) { >> + /* Overwriting the range and over a part of the next range. */ >> + 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) { >> + /* Overwriting a part of the range and over the next range */ >> + 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; > > Again here, I think you have already verified this will be a slot store > by offset_end - offset == 1 and new_end == wr_mas->node_end. > > The checking of the slots for the gap could be moved outside the > statements. WDYT? Yes, I'll address this in v3. Thanks. > >> + } >> >> - /* 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; >> } >> >> @@ -4396,7 +4385,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 >>