From nobody Wed Dec 17 13:54:09 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8DF2BC77B73 for ; Wed, 19 Apr 2023 09:36:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232662AbjDSJgw (ORCPT ); Wed, 19 Apr 2023 05:36:52 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33938 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232968AbjDSJgt (ORCPT ); Wed, 19 Apr 2023 05:36:49 -0400 Received: from mail-pf1-x432.google.com (mail-pf1-x432.google.com [IPv6:2607:f8b0:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7BC3493FC for ; Wed, 19 Apr 2023 02:36:39 -0700 (PDT) Received: by mail-pf1-x432.google.com with SMTP id d2e1a72fcca58-63b35789313so2359109b3a.3 for ; Wed, 19 Apr 2023 02:36:39 -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=Rh3HHMe6CoiaRRov9wxC0CTa9keR0+UQEg2VyLPS6ue34ijat9zmLLcsUv3GN6ZXmM 0LKLKym6diEfjrV/KMojBz78+m/YTdW5TzrEJfDGUphLxyyWjROYnyBi4DRDZLYy2Tdt l35mI9Jd/r/mGF1vdN3mB8yDZ/jqpAh9Dlno/0c5yz7yWonchfdzjxiutA4SGinnPu/T GtvFHt3H608I6hnKT02XkR540UI3kGSHLS+B0+bMTIUZL+TQr6EK3IC0sPfEHN/1OXxL Yb2wgkEx3AaaDftmtYQIeEeoKvB7TPt7Hbr5e6cjNgahkT+suf1rWZaVL2sOCXzSAScz UpAA== X-Gm-Message-State: AAQBX9fYy78oCvfneBYKGtbDTlHlQ1BZU+NMO+1L3waFgAJ+vPKkwPVx DgL2W5Gk7rnvjFzZtAHwmhzpSw== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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 *ma= s, 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 =3D 0; - - if (!unlikely(mas_is_none(mas))) - start++; + if (!unlikely(mas_is_none(mas)) && min =3D=3D 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 */ =20 - if (start < min) - start =3D min; - if (fwd) { - mas->index =3D start; - mas->last =3D start + size - 1; - return; + mas->index =3D min; + mas->last =3D min + size - 1; + } else { + mas->last =3D max; + mas->index =3D max - size + 1; } - - mas->index =3D max; + return 0; } =20 /* @@ -5297,10 +5300,8 @@ int mas_empty_area(struct ma_state *mas, unsigned lo= ng min, return -EBUSY; =20 /* 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); =20 /* The start of the window can only be within these values */ mas->index =3D min; @@ -5356,10 +5357,8 @@ int mas_empty_area_rev(struct ma_state *mas, unsigne= d long min, } =20 /* 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); =20 /* The start of the window can only be within these values. */ mas->index =3D min; --=20 2.20.1