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 6D79AC678D4 for ; Tue, 7 Mar 2023 13:05:58 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0E9D06B0074; Tue, 7 Mar 2023 08:05:58 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 07205280002; Tue, 7 Mar 2023 08:05:58 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E301F280001; Tue, 7 Mar 2023 08:05:57 -0500 (EST) 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 CD60A6B0074 for ; Tue, 7 Mar 2023 08:05:57 -0500 (EST) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 8033980B7A for ; Tue, 7 Mar 2023 13:05:57 +0000 (UTC) X-FDA: 80542124754.21.87DADCA Received: from mail-pj1-f53.google.com (mail-pj1-f53.google.com [209.85.216.53]) by imf23.hostedemail.com (Postfix) with ESMTP id 86635140015 for ; Tue, 7 Mar 2023 13:05:53 +0000 (UTC) Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RBo4mnr9; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.53 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1678194354; 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=t+FdsTGZzqFZqYBTn3Ql+ChMDk8iUlybGRvDY8ZJ9VU=; b=EyxEGPfm5+uzhn34yfEJOEHfRg3BkZ8aGfDHZL7Xl9xD6tSkxB9FlFhsFdgcKck1lG4WlY 7TAVe5LczyddH9tskwi61UmpweDCVAzgzoLtcx+Wp5tsZzvbkEFdBaSqwhTxGX/GLY2VN+ Qqw2IEllqthxzIfCjcwWZW8on/pWBrE= ARC-Authentication-Results: i=1; imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RBo4mnr9; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.53 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1678194354; a=rsa-sha256; cv=none; b=cTEryO4Zh1jhUtnlEvknlBDPSYDfs6IT0LVgU7ewkM+2KBqtGhW5rkNLczhEKFi45p45Hw UqilIx7qFlTZ7p1doWMeuaqtMZJIN3tMoZJeN8LAp9O4zUQ2hzlvMzte6Hrgl3Z9RcOapM lLRgXIinkwN9a+bAm8dCEQnIIfjBxK4= Received: by mail-pj1-f53.google.com with SMTP id kb15so13139275pjb.1 for ; Tue, 07 Mar 2023 05:05:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678194352; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=t+FdsTGZzqFZqYBTn3Ql+ChMDk8iUlybGRvDY8ZJ9VU=; b=RBo4mnr9UV/76xDxoNtIFvN1XW6fFx1PY1NBiBdZog7bPokCU7XM5kQUk6LQDiqV8U YrWsVdVwtGNZwuuLoYW6ov2pXHIYRzRFDStHthlQfInnIps8GwfB74TucjDdimqbaXWW jICL4WCdizqK/+1J5HKRHPrCGRMxzoIkWYkkUUTQ+oxVF0Ur3093L3wwZ0Q722cllW1B u0rzZ07flKCpWM59XBHvlep+JW4VRVWPp2BtO6W1ZUbEFwqU/rzxSNhpfst5RKm62J/6 funSPnYuZXt/hBhouBzzFqflnpGbyAr/NuB79F3VqIawrzBMUqgALdIigjDFBKSL+HRe 1SAQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678194352; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=t+FdsTGZzqFZqYBTn3Ql+ChMDk8iUlybGRvDY8ZJ9VU=; b=t4tpLUyiE41SQm7qx+Gi8eYrZ16AWk8rxmINV8UMY1b2wLBjQxTXUABHdovdbBOw+j 3mHbkzMNfo/rJXQPVZ8HcYlsSM7r62kbFzJao07HjHL++6+tDxu3+j1imaoqYh969wrO QAJbbtCIBNAeYRTIzmB3BuFAJTOEm7RJxGI/kZvC66tbDRq5f1+lvIfz7Qz/GKdu+cY7 9GeBttZoHehOXxLc9YUr7CDNjgJagSiyBuNK+Wlzf8eIhPn8M7AJoycHtPlxP/XWUR3x QiLgYsuXScf9EdwwqcVCl9qO42z939431dnQEDQEcJiu4wYBTZ4We9o78mv5tEghmr04 nfGQ== X-Gm-Message-State: AO0yUKVqwVaMwsJ0RB+TZ8hCH4lDd0VdKm6ERUzexUqGAjbv0HzNKuQZ KEl40I93knBIH2oego6bXql4HA== X-Google-Smtp-Source: AK7set9tOFhM95hUX3pEY5rK2bAommdGqvpRofEUa/4iWeTx414xIKOjt0Uc2cc+J9isMI7He9+sOg== X-Received: by 2002:a17:902:d2c9:b0:19a:c4a0:5b1b with SMTP id n9-20020a170902d2c900b0019ac4a05b1bmr19927045plc.1.1678194351908; Tue, 07 Mar 2023 05:05:51 -0800 (PST) Received: from [10.200.8.102] ([139.177.225.254]) by smtp.gmail.com with ESMTPSA id s7-20020a170902988700b00198fb25d09bsm8322729plp.237.2023.03.07.05.05.48 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 07 Mar 2023 05:05:51 -0800 (PST) Message-ID: Date: Tue, 7 Mar 2023 21:05:46 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 Subject: Re: [PATCH 1/2] maple_tree: Fix mas_skip_node() end slot detection To: "Liam R. Howlett" Cc: Stable@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, Andrew Morton , Snild Dolkow References: <20230303021540.1056603-1-Liam.Howlett@oracle.com> From: Peng Zhang In-Reply-To: <20230303021540.1056603-1-Liam.Howlett@oracle.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Stat-Signature: axkoc1norkhsufcxe8irq1ftizf3akdj X-Rspam-User: X-Rspamd-Queue-Id: 86635140015 X-Rspamd-Server: rspam06 X-HE-Tag: 1678194353-343731 X-HE-Meta: U2FsdGVkX187XuM1JHvN/GZ/hRTeR732l008PUvO0RViEzzzfjjd9ZFl0sAQKunhJmYpwnnC3uW2ORB0fR2tW+xnl2auhoIYeLji8zbfJucSGKGe0QEIjUjBkSwGq2G2Z964GdGuVM7N5Lj7qs4DAPooPqhe1VLIDde0snxeo3/Fzwq8NYnue+0Rq3smA6YJmJUx8gvdTlFNlgOUo7XYEzjsxfbiSBiprailzm8SH1ALA3vI0kuPIf1b0/9HIK+7lFf2OK7aoySBu0jiUVCfVh+sHqroYA/qlFZ7MBJQNgQNRfY90XPbdSuNOnxlCS3ko8L/KFoAYtRtF8acvZSg3Wf27l15VonMnRayc5jM/T1h36N61XtE3DGs3Bm4M2X9fEL27XDLR+OgMsvMdQ8TEfEdSMf/fq/qLC1zI21LEL32uTA5aVv1RX+P+1gyfd4+S9xs+lMeSzhzRI+ocrG9oYKgCjmDXXsfVk1XQIgRi9+UfbY5370gMOhBti8GdCtm1ZOOUDV+/8uOlpMZxxJPiryzZUwElTkGYRRBeayhjo1Z3T8yHSJ/4lDRuP4gZ9lDTboB33h9UEy/Dud/6/+j9vsiivc+7qgTqon5BZFFropr/baLg754UlqZEgR8vHFyf6aV5fk7QNm7ZAKwr5CQBwLmIVqzjO687OqJT74ioZgfocJv9nViIVTlPUmXVqCn7qBUq1dqqZTAJziUzAu4lYN0PvWVLOUzxf4HiA8SZ23CBcmqIiVJqOVw/+egt1WA3CZfWzg63QyxyI0bqUhalsQBrWVi5nERMdGdEpR0UbyNCoV1GIrh9roZ6BoCPDUU8+6es3baoHkX3jKYi/Nz6YMpLMzZcLXktXjKRdVIcpXcNB6HmZGzR1fMOrrvkvK4wjhYvI6joadATfLFtu5M9t22V1dxR/OF/iIaIKfZBV8MVcWURpgpHXuQ6AYy0dTIIF4sVybJOgmk7QOglnj VBH/3oiH CvwzuyYUi4AbCM0HKUXyV3J8g7lboHkaHLOITD53/bsnAv1+WAQffqF62OglM1ar/+qqyYQGUDUocEFph/G4ZD9mFJsVkXygRUeK2MIxAGuNikXtIYCfbiXxAFTxEwcr/PZhhxcs14dskM5Gcodm5rchk1oKp0JLvEF9lT6xRum8wdZphzin+C1lH5wpuUwwku6fydDRQC6mT7EuDQ3bJEJiRCNNSv0xZ5BhKG7vfCTYoZMGtAnFoUsUrdZ8e977nHf1Zf7B3757AajGalD7jPPPadFoMrFTJ/Mb+ecwm9tn2pDhLSGUW9WOkgWu2yShSB6vvsDCEDYjJ9IAVNhhKXkgULUuMvj1YbXkha0rLY8+5MH5lD9/2k0c2gC2PCJ7lqKn+oENTf0kzC/huqvP9iaaAPqVzVo2ETtvIfaIYZZMBRlS4RTyt86eeHu0geQA9Hdm2de65ZHy2cF62PKsCMd60c+LVD+j8D2Z/rpZly+EdSxbpdLgsnisN4D+OyZhLkYf+Pb7k3VESKdcBaHQwMkV2knqni2g+SEZt9+lS6pNkX8GFa76M1buye9A5NWNJwN5NsT65vDZhbr1Se7ljukrCL8BPPoDj++vNsImFuXFkZwgipJhMuJDc+Q== 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: Hi, Liam, > mas_skip_node() is used to move the maple state to the node with a > higher limit. It does this by walking up the tree and increasing the > slot count. Since slot count may not be able to be increased, it may > need to walk up multiple times to find room to walk right to a higher > limit node. The limit of slots that was being used was the node limit > and not the last location of data in the node. This would cause the > maple state to be shifted outside actual data and enter an error state, > thus returning -EBUSY. > > The result of the incorrect error state means that mas_awalk() would > return an error instead of finding the allocation space. > > The fix is to use mas_data_end() in mas_skip_node() to detect the nodes > data end point and continue walking the tree up until it is safe to move > to a node with a higher limit. > > mas_skip_node() may also be passed a maple state in an error state from > mas_anode_descend() when no allocations are available. Return on such > an error state immediately. > > Reported-by: Snild Dolkow > Link: https://lore.kernel.org/linux-mm/cb8dc31a-fef2-1d09-f133-e9f7b9f9e77a@sony.com/ > Cc: > Fixes: 54a611b60590 ("Maple Tree: add new data structure") > Signed-off-by: Liam R. Howlett Reviewed-by: Peng Zhang > --- > lib/maple_tree.c | 25 ++++++++++--------------- > 1 file changed, 10 insertions(+), 15 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 2be86368237d..2efe854946d6 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -5188,34 +5188,29 @@ static inline bool mas_rewind_node(struct ma_state *mas) > */ > static inline bool mas_skip_node(struct ma_state *mas) > { > - unsigned char slot, slot_count; > unsigned long *pivots; > enum maple_type mt; > > - mt = mte_node_type(mas->node); > - slot_count = mt_slots[mt] - 1; > + if (mas_is_err(mas)) > + return false; > + > do { > if (mte_is_root(mas->node)) { > - slot = mas->offset; > - if (slot > slot_count) { > + if (mas->offset >= mas_data_end(mas)) { > mas_set_err(mas, -EBUSY); > return false; > } > } else { > mas_ascend(mas); > - slot = mas->offset; > - mt = mte_node_type(mas->node); > - slot_count = mt_slots[mt] - 1; > } > - } while (slot > slot_count); > + } while (mas->offset >= mas_data_end(mas)); > > - mas->offset = ++slot; > + mt = mte_node_type(mas->node); > pivots = ma_pivots(mas_mn(mas), mt); > - if (slot > 0) > - mas->min = pivots[slot - 1] + 1; > - > - if (slot <= slot_count) > - mas->max = pivots[slot]; > + mas->min = pivots[mas->offset] + 1; > + mas->offset++; > + if (mas->offset < mt_slots[mt]) > + mas->max = pivots[mas->offset]; There is a bug here, the assignment of mas->min and mas->max is wrong. The assignment will make them represent the range of a child node, but it should represent the range of the current node. After mas_ascend() returns, mas-min and mas->max already represent the range of the current node, so we should delete these assignments of mas->min and mas->max. > > return true; > } Sincerely yours, Peng.