From patchwork Tue Apr 11 04:10:04 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 81717 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp2326906vqo; Mon, 10 Apr 2023 21:38:34 -0700 (PDT) X-Google-Smtp-Source: AKy350aoK/aml3RKstAY9KeoKAh65FH9un2e8pmOV96zF8M88sT5+JSmOXE6pcQgC3Z7iuIsqIqV X-Received: by 2002:aa7:94b8:0:b0:637:1845:cbca with SMTP id a24-20020aa794b8000000b006371845cbcamr6399835pfl.28.1681187913723; Mon, 10 Apr 2023 21:38:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1681187913; cv=none; d=google.com; s=arc-20160816; b=tMzo7cV09HjlqjcXRuw+ZdLOBatAcdn0XfSB84PDeIfz3Ul1UK/Rwk7RAYjqTHocVF FsxNefjVCnjyyV+0D5OzY4rTpLEozi7l0c7+Tw34/jvrV5pLlmAkwnP/nzTHbLk0733X Vj8PE7tC3S+tNlcosgf6QeHuJD3rHCfF6yL2soLCmLp7ME1DPJDeiH/fs0YmmPcv/od9 ijJLtdQiaiFomxIjsFFVlduMp5tWRigRpCZ0eEgd6QeYgRrlRvPNfsRQkbbrGKmVZzYf vaV+9r4Rnzvr9qFqeuI+ROZ8UdFFZ91ApJSe8hHYPvNqBaNSuGZj4nXE7LzDIQC4eIhz tt3A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :message-id:date:subject:cc:to:from:dkim-signature; bh=eN2VsvcD5hPHo+/vlmQCptxa+XrNBTPC8kVbJFk1whI=; b=cZzBXC9xRIZNCE5tzz3Ne3V+CpnWMwG9tuajzkTEWiqqk1B9btQOf61W51OylM0LGt +ioMHRKhlsZCrCnQ062jfDycoy+FUhm41PJeiml4iK7LXN8iS2509xrCfogIq8dREUph X4iAIbJxN/BJ7hioSoGQxBJA0pcmC1ZiT4A+ARUjA90yO6O50Jsve7FjEk4mgXE8W0FR GurXzCO2WEeihKRt6m5QabZ6S85s2p5JRS1zdutoG2EnngQPVIQPBtbBGvh23E08Lr1Y WLmvcXOp+HxFJovwqjdIsw55/MbuFZ5iOnh/VhJnMy1TcbRTABF0kSz6FVazgp4R+JPB 2pjQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=UZFe1vqI; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id l7-20020a622507000000b005a8ef5a4becsi12268880pfl.311.2023.04.10.21.38.21; Mon, 10 Apr 2023 21:38:33 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=UZFe1vqI; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230002AbjDKEKq (ORCPT + 99 others); Tue, 11 Apr 2023 00:10:46 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60868 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230025AbjDKEKm (ORCPT ); Tue, 11 Apr 2023 00:10:42 -0400 Received: from mail-pj1-x1029.google.com (mail-pj1-x1029.google.com [IPv6:2607:f8b0:4864:20::1029]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id DC7B419BE for ; Mon, 10 Apr 2023 21:10:15 -0700 (PDT) Received: by mail-pj1-x1029.google.com with SMTP id o2-20020a17090a0a0200b00246da660bd2so853224pjo.0 for ; Mon, 10 Apr 2023 21:10:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1681186215; x=1683778215; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=eN2VsvcD5hPHo+/vlmQCptxa+XrNBTPC8kVbJFk1whI=; b=UZFe1vqI+wN9iQAUaKh6UKtom6rHOvL9AJb7n/MojmI9ZlaKauWs5yldPgww5XsKyn AlJQyJYQhn+WWTx5NiuImiFc8uLeQZ5Y7sTp5zmkOliTiMGJ9ZWK8AJUNJx4aFfXqLY6 5Yylfkgcg2+ivHSGJaPPTRC+JShlBzyW8LxWC6vHPEeEuKIywsq7dT5fxb5vW6i8TfEn 4F217cam94a5ZTgzS/rY9XurNwkQkqtQKY66vg39eNTvW2+UVcTwccas4Afk1giVpINj l3q7iKBhwrFa9UDTdMtI1CgWPG5ugokypEJ2HJq+hfikd0mBJZjB7m1d6mBR1tyyJaxe CSug== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1681186215; x=1683778215; 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=eN2VsvcD5hPHo+/vlmQCptxa+XrNBTPC8kVbJFk1whI=; b=3IYejwIhbG0YFcY5Q/L0LvX5UwWxjVYWxf1IiRnGQjmSyNAytt/xc8r+v28fB+z2wE a39ZKRuDzkb/JXOhKFlb4CKd5/jBzQt5uZzrMU9FfA6CSftTtnBkXbkm0lqL7PwxNslr A2wpTUbEmGQ8oppPE81ZhyplIpdSjyjU4slOaIMC5OOWmAhPw1+E4DAyPTn+9ObLFyCz 0tHw68MWltBA/iPM9b9Ds/XJk8eWqcCfPENjyPR0v4mB8lCOwXYx8vbwK7TOJ9XcyqNy RcsHGILis8BhsCjTrZI5kfauY45/1H/JncUcCqAWXOqXzTTyXgaKOXC1+wnq8xgskz64 Ee7g== X-Gm-Message-State: AAQBX9dpiqym/J3LjvS9mdrgVjZfSHlqxYszPDNscxHP3S8+uh1BFCLz AigNRmudgcA5iD/eFiVw0LSkYg== X-Received: by 2002:a17:902:d2d2:b0:1a1:bcf:db5f with SMTP id n18-20020a170902d2d200b001a10bcfdb5fmr20291415plc.25.1681186215375; Mon, 10 Apr 2023 21:10:15 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.248]) by smtp.gmail.com with ESMTPSA id g13-20020a170902868d00b00198f36a8941sm5567317plo.221.2023.04.10.21.10.12 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Apr 2023 21:10:14 -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 , stable@vger.kernel.org Subject: [PATCH v2 1/2] maple_tree: Fix a potential memory leak, OOB access, or other unpredictable bug Date: Tue, 11 Apr 2023 12:10:04 +0800 Message-Id: <20230411041005.26205-1-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) MIME-Version: 1.0 X-Spam-Status: No, score=-0.2 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1762853297739616200?= X-GMAIL-MSGID: =?utf-8?q?1762853297739616200?= In mas_alloc_nodes(), "node->node_count = 0" means to initialize the node_count field of the new node, but the node may not be a new node. It may be a node that existed before and node_count has a value, setting it to 0 will cause a memory leak. At this time, mas->alloc->total will be greater than the actual number of nodes in the linked list, which may cause many other errors. For example, out-of-bounds access in mas_pop_node(), and mas_pop_node() may return addresses that should not be used. Fix it by initializing node_count only for new nodes. Also, by the way, an if-else statement was removed to simplify the code. Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang Cc: Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 19 +++++++------------ 1 file changed, 7 insertions(+), 12 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index dd1a114d9e2b..938634bea2d6 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1303,26 +1303,21 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) node = mas->alloc; node->request_count = 0; while (requested) { - max_req = MAPLE_ALLOC_SLOTS; - if (node->node_count) { - unsigned int offset = node->node_count; - - slots = (void **)&node->slot[offset]; - max_req -= offset; - } else { - slots = (void **)&node->slot; - } - + max_req = MAPLE_ALLOC_SLOTS - node->node_count; + slots = (void **)&node->slot[node->node_count]; max_req = min(requested, max_req); count = mt_alloc_bulk(gfp, max_req, slots); if (!count) goto nomem_bulk; + if (node->node_count == 0) { + node->slot[0]->node_count = 0; + node->slot[0]->request_count = 0; + } + node->node_count += count; allocated += count; node = node->slot[0]; - node->node_count = 0; - node->request_count = 0; requested -= count; } mas->alloc->total = allocated; From patchwork Tue Apr 11 04:10:05 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 81709 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp2320885vqo; Mon, 10 Apr 2023 21:19:51 -0700 (PDT) X-Google-Smtp-Source: AKy350aaCbn+0xSmlzdc97HUx7G18B+zvGv3r6cUJ3tn0ExZLmiqrx1djOnE0OJESPSGCQIjnLgZ X-Received: by 2002:a17:906:7d8f:b0:948:ab25:aaeb with SMTP id v15-20020a1709067d8f00b00948ab25aaebmr8985890ejo.15.1681186791099; Mon, 10 Apr 2023 21:19:51 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1681186791; cv=none; d=google.com; s=arc-20160816; b=Q1yTF/0u4CJVRG4Eqbnsaav7S5fnsC06wexW40V8FfAOaPlzUPukeUGqmojs5S5Tnu lCIv/FxvxM4xTVS3jjMsGYZMibSP0IiDMPFfcjaLmZXN8ZgXaYyagM6KkhDZxNejItVu 8Cv32lhut/Qld3dvrZ0Ef++SrgiD0V/9Wy2h9Mbs3y70DnMoBMtTscDXOGy5BTTItpcP b/RU1lNFiTlHvPEqWvPkZNyzcSqgXoBI1fHufFvpR5AI4Apn5UpocfCfalMJRbBh+Vl4 KHBSZhLBbavH5r9Xr+9bskm7dhjX3jM/IUgbr/NYHeYJBz1kqUsW1dlLYSRf+C/kk6Jl D2yg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=8JQC2S3AsB/qfFz4i+cFB5iM5W1998ocJck2gmcRviY=; b=fbhCr+D7yq2yvrrydW8wC8mm0GBZnkYjPmDM6TV0cjDLp+a5ypVL4kIm4HDvWYrYmC sBar+TVrpzz2G+CXi1sOlnHPE8Tu2zR6bQOMvKIS7u3+Cs4aCIjJA8hGt07ZMO5brLoC zhABFULJkWcU6JB/0mD9i6GbozBYpYWJxugJUgp/KeB1HgwvKlAkKN4rr9dUFhQVsA81 Nq71ip+i5Llk520w2wVOYYjSsCQ4MHcWN1LW4PR0ZZjQoPUHQliVcB93vaeMfTePzXX2 2H92GrpIZUA0piHy00XVEqb48aspzVeauoFvbGo4+eMqs8Xsqlf0iWYY9RiORjgMzoOz oKQQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=c+OhbwPD; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id c4-20020aa7d604000000b005024e71ba26si7132737edr.447.2023.04.10.21.19.27; Mon, 10 Apr 2023 21:19:51 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=c+OhbwPD; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229830AbjDKEKV (ORCPT + 99 others); Tue, 11 Apr 2023 00:10:21 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60888 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229656AbjDKEKT (ORCPT ); Tue, 11 Apr 2023 00:10:19 -0400 Received: from mail-pl1-x630.google.com (mail-pl1-x630.google.com [IPv6:2607:f8b0:4864:20::630]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C655B1BC8 for ; Mon, 10 Apr 2023 21:10:18 -0700 (PDT) Received: by mail-pl1-x630.google.com with SMTP id w11so6642615plp.13 for ; Mon, 10 Apr 2023 21:10:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1681186218; x=1683778218; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=8JQC2S3AsB/qfFz4i+cFB5iM5W1998ocJck2gmcRviY=; b=c+OhbwPDKLL1YNc5EklJLAoqBP4lWpvwS3T5ff8jGJ5C+odIS/4hjxEOVVxtvZVEwv jiUDUhhQFVa+X70eGWbAkz8hgQkj4ZBGKssBaI95xPjXCpulKL6LgTwL6hbYH/EoPiwm WKlzj64HS5Q6+cZt67J5vP9bvpFKVLRHoQRRINLir3+/TTRVTqe5clr/DAnpV9pbNsJj y2p5bEQZocHzfMafDtq+qVDlL8oYMJI1S6ND5+uU5I+IF3uxtMdsZX+hBn3qBT3fAjOq BIyYESuShEQBUZNrUVcTHkf8mjIbPBVlZevxF0/E/FjfhM/LjIhx2Yo70YBfK1OKN/tb +aeg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1681186218; x=1683778218; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=8JQC2S3AsB/qfFz4i+cFB5iM5W1998ocJck2gmcRviY=; b=XDCSuvAn8pwa4eqmu1xoD0LliZY2O0NVz/SBCK1fvkqJi0phtuW6HNhHuxoNUMvWsc PbOENxqLWxP0rr0orsYLZ6WkIzZtvkL7EZFb8TLdUYusYcKmUO2OreZkXOln5iN1j8He YNBeRSL+nQt1lYEnaEOBhlEwceQOu9AkpZ1cWxdaYbnZMC7X1+y0dJgRoE0YqzbmFA79 hiiGS/nAqJvB7ybolYV0UGIbXcYWaJ+6Vzj9gtq/2BENb8b6sMKB2FCpN8Z50Bjp/JoP Hqpoi3E3h8YPRnYpXeZhVjbwiSVLHNHsURTGrvWQRh0oN1U/DmnBHYxm8B106PoNf8pp t4+g== X-Gm-Message-State: AAQBX9dnjfauyqh2GYJQjydDylHMrAZIvmmufFttmOC0qA2Frk4PhWEx 2C7LjIBlaYiwqllG6sioEhnNyw== X-Received: by 2002:a17:902:fa48:b0:1a6:4480:dfed with SMTP id lb8-20020a170902fa4800b001a64480dfedmr4852064plb.49.1681186218323; Mon, 10 Apr 2023 21:10:18 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.248]) by smtp.gmail.com with ESMTPSA id g13-20020a170902868d00b00198f36a8941sm5567317plo.221.2023.04.10.21.10.15 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Apr 2023 21:10:18 -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 v2 2/2] maple_tree: Add a test case to check maple_alloc Date: Tue, 11 Apr 2023 12:10:05 +0800 Message-Id: <20230411041005.26205-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230411041005.26205-1-zhangpeng.00@bytedance.com> References: <20230411041005.26205-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.2 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1762852120796592816?= X-GMAIL-MSGID: =?utf-8?q?1762852120796592816?= Add a test case to check whether the number of maple_alloc structures is actually equal to mas->alloc->total. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 4c89ff333f6f..9286d3baa12d 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -55,6 +55,28 @@ struct rcu_reader_struct { struct rcu_test_struct2 *test; }; +static int get_alloc_node_count(struct ma_state *mas) +{ + int count = 1; + struct maple_alloc *node = mas->alloc; + + if (!node || ((unsigned long)node & 0x1)) + return 0; + while (node->node_count) { + count += node->node_count; + node = node->slot[0]; + } + return count; +} + +static void check_mas_alloc_node_count(struct ma_state *mas) +{ + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 1, GFP_KERNEL); + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 3, GFP_KERNEL); + MT_BUG_ON(mas->tree, get_alloc_node_count(mas) != mas->alloc->total); + mas_destroy(mas); +} + /* * check_new_node() - Check the creation of new nodes and error path * verification. @@ -69,6 +91,8 @@ static noinline void check_new_node(struct maple_tree *mt) MA_STATE(mas, mt, 0, 0); + check_mas_alloc_node_count(&mas); + /* Try allocating 3 nodes */ mtree_lock(mt); mt_set_non_kernel(0);