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 9D7B2C77B7A for ; Tue, 16 May 2023 07:27:39 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0EC16280002; Tue, 16 May 2023 03:27:39 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 07588900002; Tue, 16 May 2023 03:27:39 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E7EBC280002; Tue, 16 May 2023 03:27:38 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id D537C900002 for ; Tue, 16 May 2023 03:27:38 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 99E581401C0 for ; Tue, 16 May 2023 07:27:38 +0000 (UTC) X-FDA: 80795288196.13.A7B5798 Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) by imf09.hostedemail.com (Postfix) with ESMTP id E27DC140006 for ; Tue, 16 May 2023 07:27:35 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=C5zki00O; spf=pass (imf09.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=1684222056; 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=3VrihHlX4gfqH1aDetunLHoNMhaVXNYRIMdChx9m30s=; b=7CPdBjoItslKD1SeT/o3kcXiswjL9A72/ZV8USSiMQ5MM1Fz6YLmAmq2yWufGSpPAVz3Bu DQ34sKIJs7IhmcGMRiHu/uYDCOCGn4oXgZ9iBFBpCqSydTMGPaEEBf/SPv03KSZfb4ywAh suL9O5q3gdcuM5bvqoDh+nO4axCWUi0= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684222056; a=rsa-sha256; cv=none; b=bVB/TjToYxDVqctkiebugVqgikbfhiNtivqLY4fQ1CZe7QcaMSvfNEQs6SqEJMK69S6SNI BdnbLTzXX+SYWChYwTUi58RIdmp/3uvoNrayWq1xxOcnwGS7fws9H7t4dXkmC9mZvd7GT+ 6ulMLgms4t6hWBjkwKisxSqDEYehKBY= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=C5zki00O; spf=pass (imf09.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 Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-643912bca6fso10785608b3a.0 for ; Tue, 16 May 2023 00:27:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1684222054; x=1686814054; h=content-transfer-encoding:in-reply-to:cc:from:references:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=3VrihHlX4gfqH1aDetunLHoNMhaVXNYRIMdChx9m30s=; b=C5zki00OG/Di/cP+PHSnsCOkSCPbwkL4V81xLbfY4pVggsLfdhYrskvUIALYYFgql6 4gJqNkWTfTYZofZdCzKb3LABW4xcuqkL4A3fOK6hOUmEKUn0PhouTh/3QB8i4JSyqlQq G25+HtHqiwNVmHPkr/4aORinBDAQE+ckCW+eriH7AfPr+AWdFHjnou/WxnrZdFJB93Mr 52XHHE9BUlRe9djIkCBmR4vQfSg3BKd7LAdz+zhw6NY+EwkbNUPlMUny45/n/13ORKCR nuL5XG90LWPhvKwXDYjv3Asc4n8XdNsePhSv/KTlkHc9VHMzCfRbR5iz5y68/ZvPd1xk tdgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684222054; x=1686814054; h=content-transfer-encoding:in-reply-to:cc:from:references:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=3VrihHlX4gfqH1aDetunLHoNMhaVXNYRIMdChx9m30s=; b=eDES5+ZtX6e+whostfVPAMcfRVco3juiH4823RTnRns3MqWDVrfz+ZVwY2FaH3uFd6 RV0V4DuJL/+tAXR7t5JNCUFRdK6WxUiU24BcbO5wYVs+HyxTmnu/Hd6R3jB8dlq9YpyA xLAhORx305D9AWpBi9UKfEkMrLu0fKCFaU4CzyCYbdvAKZVy/ruChCCnCle7rrIocIM6 XSrbJHc6D2ELxcOPB0ORpgziTPWKPtUSpB0e8MtXuCiEy4VhZv6OS89YrcQcpfZUAQGf FtDsfnpffBa0sqk6ZbpKUKUAsdiCytIc1M1yXSSm96N9WeqGv8uqJMR9qDU880QEe44l HVEw== X-Gm-Message-State: AC+VfDwylWcGqcB+kIi6CTywuDuuVJ0KP3GsNZ1cOzql7cA/aZzR6ZHb XvwmsR8P1vhnMC5XmL9S2AJr+w== X-Google-Smtp-Source: ACHHUZ4Ij3/JcncsA3FDxe3yhdEY6/kPht/VxPatiLCmVCATaxIua2fY071UHEQt47R+beIWtFjjAA== X-Received: by 2002:a05:6a00:1821:b0:644:d77:a2c5 with SMTP id y33-20020a056a00182100b006440d77a2c5mr50250878pfa.29.1684222054509; Tue, 16 May 2023 00:27:34 -0700 (PDT) Received: from [10.200.9.178] ([139.177.225.227]) by smtp.gmail.com with ESMTPSA id s26-20020aa7829a000000b0063b6cccd5dcsm12429514pfm.194.2023.05.16.00.27.31 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 16 May 2023 00:27:34 -0700 (PDT) Message-ID: <4e40b88c-4419-56df-d720-177cf76e95a6@bytedance.com> Date: Tue, 16 May 2023 15:27:29 +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 09/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient. To: "Liam R. Howlett" References: <20230515131757.60035-1-zhangpeng.00@bytedance.com> <20230515131757.60035-10-zhangpeng.00@bytedance.com> <20230515180147.hgwk2vccsph7poxa@revolver> From: Peng Zhang Cc: Peng Zhang , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, maple-tree@lists.infradead.org In-Reply-To: <20230515180147.hgwk2vccsph7poxa@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Stat-Signature: fzhhqgfnjo5uzmt5h9u8bwfco1tx6t3z X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: E27DC140006 X-Rspam-User: X-HE-Tag: 1684222055-645562 X-HE-Meta: U2FsdGVkX1+q78yUu2c7XEEVeEN3SZaq6ugV1seA7jNJ1H816SZHCDhmWQ7aCgRpgDWVPRu6uSDOFdHIR0Mmkmn0TIPTMzw8iVDsT73V0V99l07AwGmUPAjf/YyZHy5bXWpekzLwqekHHIEzr/zyS85flpu9Smxh9K5Qv69vHQ7eippVsTZ0KNZVNL2g/72u30YZsqwBzTXHcQE/AtwDkFnRQxGYEql2I0Gldqiicfo4E5PD/sHeHHRlhuEGoBMvxFVqczwib10qTLHcnb66n/+GXAVgW4SqsLA1RmneMdl64LgJb2teee4BDe7bE3NvVEHMnpfmOqVFShcdmodspNC/9hQr6oaxf3i2NyLVBmsPALIv2/DPVpeXBqWjLjknZN5gvvMKbnZwmq3KzjnVz0apdKuIHak9PBiOrhTOxajAP5z10nZklmCsBFGizEOOqBi2fqMYQp5D+aub5bXwolhDLUKxuVxTs6YgXSB1ECHVejKe3SZemmFQ8eiMEUf/wVD+1yCj/jwT5gGYxlMszeVQ4E5CRsGwsF1e9dlobzf16DlXF1WK7mxHVsloDGIzysJ5kqdhDIju/3Eme56+Ym261p+dcoalNhW6X5YbzExhO7ThcVzaVVETw46xtyAYuHAsBGNVmrsnpUhaLh2IddRZFgd6YcLfvDRQ+QtaOZcktsYvvIR0j9JYXJafnJV97+lSsVa8fjSUlRFhPI1sYzdBNMs1iJ2YQoShmBvJrlAlRzcbt6KudOrY3yYAtH5BRma/UwF1Z4Ng+AtiYQz6NfrSBT8S22gszCIFNci1iE3vx9qtufvoDsPJNi7Qe04ydm3bgeB/e/pVa4BpIQt2ICxRoTiPooxI1sZiV/1h6XJOVcvXGByMjpuKNwSkuvf9sygY+sre9S1v1rDRQbAYR6d818/47EWW7prp6+66sCW8mEIbUecxmdCd+vmQefKoB1wxJB2MqxTaTS1N8Ox Vs6vmA5K uL7iN829ATKhBTCkNomXQ/CR5aW9LMAEKULVfeeUWtE5w0L8JVUjQxxnkWYL3ZEE9QKu/hbI2o+ZgPw7T6AooctlxzcJqQyfcahgHpWlE98LgXQxRFWYW9sub/gowlL1H1PUpc2d/OHQxOXQWHjHbeVajCfA0KsIilUyhNmOFpQaaJPqR41ZbjFopSuv7kGEzeeo3bZ/ftQCjT4hZI+NMfWWa5ywVIVZjqCkmvDIgO9gdxOeliNEn/mdHgvsHX6cuM1D7luGXQJkisxmYLHhjd03MURBbE8Pifwbw2Bg0UluOT3gaIL/3Z+PhcYYCWye06TAhHYlbONb9zt1A+w8hYMO8KsT0Kr8mSTuxS+7CLD0BlmKVTqD74P8gNSq2y2LB7+NuRvoBVFf/g7IrBxxrpJ0Sy0jgdBFxMBIz249iLYvSusjwLzEJTJfjqyaF9axcd8HAGBG9vcuPPXTWn2t0d9yTKcHEztco0OKo7nlAZKvjwatsDi45dEuI1WedjFAlERbv X-Bogosity: Ham, tests=bogofilter, spamicity=0.000002, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 在 2023/5/16 02:01, Liam R. Howlett 写道: > * Peng Zhang [230515 09:18]: >> 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. > > Please drop the cases from the comments. These aren't that complicated > to need diagrams. > > Case 1: Overwriting the range and over a part of the next range > Case 2: Overwriting a part of the range and over the entire next range > >> >> 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; > > These two lines need to be in opposite order to ensure a reader sees > either the value or the previous value. If you overwrite something with > a new value, it is possible that a reader looking for the next range > will get the value stored at offset (but not entry). Please think again, did you think wrong? It doesn't happen, swapping the order introduces the problem. If we update the pivot first, it will cause a part of the value of the range indexed by offset to change to the value of the range indexed by offset+1, which is illegal. My assignment order remains the same as the previous version. > >> + 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; >> -- >> 2.20.1 >> >