From patchwork Wed Apr 19 09:36:25 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13216556 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 CED12C77B73 for ; Wed, 19 Apr 2023 09:36:43 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4E22E8E0002; Wed, 19 Apr 2023 05:36:43 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 493978E0001; Wed, 19 Apr 2023 05:36:43 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 35A3E8E0002; Wed, 19 Apr 2023 05:36:43 -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 222418E0001 for ; Wed, 19 Apr 2023 05:36:43 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id E12E4402A4 for ; Wed, 19 Apr 2023 09:36:42 +0000 (UTC) X-FDA: 80697635844.16.ECC8972 Received: from mail-pf1-f182.google.com (mail-pf1-f182.google.com [209.85.210.182]) by imf20.hostedemail.com (Postfix) with ESMTP id 6371B1C001D for ; Wed, 19 Apr 2023 09:36:40 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=dsaPplrS; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.182 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=1681897001; 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:references:dkim-signature; bh=LNDvSkvV+/ToXS+qJrVwxLURoAuxWbEh9gZvAqemOP4=; b=5SmjyPraj6WJhTVVqvHG9ZLisUdafU7bKBHtf3Ichf+XrjQ2rxp4xA+LQOsoVnKxyADQ0l A8nQ9IHdMSo5P56IgUdbe5IUSioiZ7T7+Ug/IZduQhh/D4CNvKcrS0wrnu8iD+78syOSJn 6WlzqfvXQ3pjrIX8iVxTon+C/lv/NM0= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=dsaPplrS; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.182 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=1681897001; a=rsa-sha256; cv=none; b=lGHJzZqr1EZtKUOB5SDBQooOWahJzBuKbxXJS/LCSPrdCZVf/y8zqHEAVu6UGXoeKgZyR4 Us1JPXHBCcd0RNxPZC66B3MXUhIO+v+lxYfPKxVKRd8u+wgMedlOvrZ4R2fkNoQULP+iK/ U1fR602I66wsey8LvOxDhuV16iaAYlo= Received: by mail-pf1-f182.google.com with SMTP id d2e1a72fcca58-63b5c4c76aaso2244691b3a.2 for ; Wed, 19 Apr 2023 02:36:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1681896999; x=1684488999; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=LNDvSkvV+/ToXS+qJrVwxLURoAuxWbEh9gZvAqemOP4=; b=dsaPplrSm+V7HQC686iPovHEcm4ECYs2V6cZJDJXiu3RytL/PEdS6HOGWQSMiHsVDc nCYtjV9irGhfSUBhjNCXJyNElcSm6+piQN2GBwwcRjSO/DSjkwv1Ym+mZ+h1xmyHl11k LFrcaftzL1uYsAxTkvxqRMh3Pk2y0pvdrLBCFWowwOsLRHOTTHUG+9vuYP2lcc5EKG/o kbs5P2D2b/4fY3Rm+4eN2fQArfpN/jIPBtFYHj/2qlQdL7sPeF8OVFxVccTwtrfz7lzs ali08ZRgYoWVH5lVYx/is7qKakyRir3tzoJ720VyBxc6Opx0xEqiEWYhX3ix2DHnN+af NPng== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681896999; x=1684488999; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=LNDvSkvV+/ToXS+qJrVwxLURoAuxWbEh9gZvAqemOP4=; b=Q0BG171V9GVM/3aUQDODIJZkcoqKMZZ6flzwx4E2NR/stabqIVn47TkHm7lus887s/ GwFqRVByOU9rVtmGQp+f3LSnPmK2OwAuKnWJjrhH59E3tN41IqMaZcQocl6O9e1QQEoL eTvNp9FGa6/F1I3STr66cTCp6GWTQubQEyr8o98Muu2n74oNp0XOTN6zDIpWz1A7Vm6k X9EL1bwvz18oK2afl4Z5XuFdNBKnrtqW6H8p3KeZ+H/VIOIe3mIL4e3kdwfKyXogik8S uxSDEGyJlprpfoXzsUzZZxBGRps8YlXE/b5Yu1EC9vRKu3vIbdjqrNHVCoRP12TvaCVv 7qMg== X-Gm-Message-State: AAQBX9dReU/MpWbwKA2D5eNsaiHDFsm9qMN/k4qORs7S9Au7Jql3rV0C eyRq1odXyvo75YfkoFMaqj9iLA== X-Google-Smtp-Source: AKy350YZ4OSrl1pFAAUYg1YKp/3Afckkw7hOT0Wq6GcrIp9gnsCT+DWQ0wFC0D4d0jLZW/30s9ClDg== X-Received: by 2002:a05:6a00:1a55:b0:63c:1be4:5086 with SMTP id h21-20020a056a001a5500b0063c1be45086mr3183139pfv.6.1681896998993; Wed, 19 Apr 2023 02:36:38 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.248]) by smtp.gmail.com with ESMTPSA id c17-20020a62e811000000b0063b8f17768dsm5257165pfi.129.2023.04.19.02.36.36 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 19 Apr 2023 02:36:38 -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] maple_tree: Fix allocation in mas_sparse_area() Date: Wed, 19 Apr 2023 17:36:25 +0800 Message-Id: <20230419093625.99201-1-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) MIME-Version: 1.0 X-Stat-Signature: cgdnf5uyaj4wqptmjtfysbukcbymq86d X-Rspam-User: X-Rspamd-Queue-Id: 6371B1C001D X-Rspamd-Server: rspam06 X-HE-Tag: 1681897000-959363 X-HE-Meta: U2FsdGVkX19HYXPaIKtvc6KVC0pH+l9X+m6MUz9R54buRIvrv0NThWUckT8UstOu7tS7O33+tqFRGXsm3AiAmmbjnHwP8AV+y1N1Mv4n47nSfHLgFM4yDVZAeOl5F0iNyyAldX2J+bh0JxnpcLagHaZCHmaGDdE6YnC2IMAos3JT31GN4PYpBMgQiMzc8Bn7yNfd6+TsVP7SdBU+qUKKj6a2z5CTKkozhtDTYgg9hfLfFAfhc54LMXiG153w2qv8q3CXVxN4h+dYoPWbnw/NVK0l9WqA3eEaHUT7SBCj+qozD1oo7dl64/g+72pzDjlNkhAuVPSUQaspreb7ZgKr0nKk2IKs/LHXEhmGC4qAe2J6bFNaTFoJrbI3H3ETwVy2xMsHVTWrUplmFGrjFEc8ov+b0nK3/+udzaC1hmevjv/i6S6DIp0SPn10APk1lXl9oP7M73cgL80AnFqw1GuxGDRM1mMIEnUfpnrT7F7FH0xU4AfEFBUSagw5RtqevYE6R/6jxL1foUwuPT1/4lfzbqrNWgX9p6EwwmU3NUOaciCupJlfmF93GsN8ZpLskIyw8mMDNTx1auCHDVtnIL5F6c34v+vy6ofLiYpVLsSZGF0wPN8bnCPqr4S7pq1zZJp1ofipw/59u87hffY3i4eiNHwpGr5cGhSOSI197wnRm0c3HrWCEbqkX3rC27Nnr/Ohl3A6GBaSoFXKHhqIrhlQYoKc9H+oD22nWEBpZUaHyeip87cYBNna/p5Mw6Ny2fqX/spQnhA5sOHfW5EpnOfRnbKV1lQC3x7Eai51OgtqlrXwJuBka77/yDHuB3aXjAXDeJvBMEuN3RSSZMil3MDk1/1bO9Ryl9fPPZe8zVG66wUzpU99b4asRwPCCDsRiDMnyMpcy90W7/WmZ8YBr7IxOnCrg+2wuJ0Vpxrf9KmQGyL1tnzevHmzNwp4ruLhfx6roUqGpb7/RVRktpm8xkt uV5gVMkS jPM6zu3iIdwbAF0w+rcqAEv6DlusVcY4dLC+rHp+QV0Urvrno08tvfur7zXVe4ThcBTQmXnzy6ETlI+aq4+9TeIe41rCYYxaFFXOUbILe30O/GlvKCesre5t/Rug9VrT3oP4r2YVIjuHCekpIolRIb8RV2kz/tnxVnBWRuGIqTRL130FbGdTi9+uRnMcHUlTMHfQHNeSC4LH2++96w1sjX8p+g7+B1V8S8pnIb8hVKrXHisTcs8OsSQNSSMTMsdoZJVdHweRVXLvQlUpxajTy6YzE/pf+zX7gnjrd65IptGGN/I36/m6rI/aCbu7zOq8zGslZJUVQ7euxODm8FYUDX7ubdeJWsxX2G2bdyDDOkfa+g62suG4nXc717M01+GWcPnGH30j9+m/ppymfof0uYdkUnkTO2HtWXJdu7X7dsjXBb9d1gKPdmBM3ypjI4oanf1lKdp6c3WH4Dm41kBF+fcYF0bNEhC2GusiZ 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: In the case of reverse allocation, mas->index and mas->last do not point to the correct allocation range, which will cause users to get incorrect allocation results, so fix it. If the user does not use it in a specific way, this bug will not be triggered. Also re-checks whether the size is still satisfied after the lower bound was increased, which is a corner case and is incorrect in previous versions. Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang --- lib/maple_tree.c | 41 ++++++++++++++++++++--------------------- 1 file changed, 20 insertions(+), 21 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9172bcee94b48..110a36479dced 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5250,25 +5250,28 @@ static inline void mas_fill_gap(struct ma_state *mas, void *entry, * @size: The size of the gap * @fwd: Searching forward or back */ -static inline void mas_sparse_area(struct ma_state *mas, unsigned long min, +static inline int mas_sparse_area(struct ma_state *mas, unsigned long min, unsigned long max, unsigned long size, bool fwd) { - unsigned long start = 0; - - if (!unlikely(mas_is_none(mas))) - start++; + if (!unlikely(mas_is_none(mas)) && min == 0) { + min++; + /* + * At this time, min is increased, we need to recheck whether + * the size is satisfied. + */ + if (min > max || max - min + 1 < size) + return -EBUSY; + } /* mas_is_ptr */ - if (start < min) - start = min; - if (fwd) { - mas->index = start; - mas->last = start + size - 1; - return; + mas->index = min; + mas->last = min + size - 1; + } else { + mas->last = max; + mas->index = max - size + 1; } - - mas->index = max; + return 0; } /* @@ -5297,10 +5300,8 @@ int mas_empty_area(struct ma_state *mas, unsigned long min, return -EBUSY; /* Empty set */ - if (mas_is_none(mas) || mas_is_ptr(mas)) { - mas_sparse_area(mas, min, max, size, true); - return 0; - } + if (mas_is_none(mas) || mas_is_ptr(mas)) + return mas_sparse_area(mas, min, max, size, true); /* The start of the window can only be within these values */ mas->index = min; @@ -5356,10 +5357,8 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, } /* Empty set. */ - if (mas_is_none(mas) || mas_is_ptr(mas)) { - mas_sparse_area(mas, min, max, size, false); - return 0; - } + if (mas_is_none(mas) || mas_is_ptr(mas)) + return mas_sparse_area(mas, min, max, size, false); /* The start of the window can only be within these values. */ mas->index = min;