From patchwork Thu Jun 15 08:43:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13280891 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 DCB0CEB64DD for ; Thu, 15 Jun 2023 08:43:24 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7E36D8E0002; Thu, 15 Jun 2023 04:43:24 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 7699B6B007E; Thu, 15 Jun 2023 04:43:24 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5E42A8E0002; Thu, 15 Jun 2023 04:43:24 -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 4C44D6B007B for ; Thu, 15 Jun 2023 04:43:24 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 21E96160B0E for ; Thu, 15 Jun 2023 08:43:24 +0000 (UTC) X-FDA: 80904343128.23.1606AD3 Received: from mail-qt1-f170.google.com (mail-qt1-f170.google.com [209.85.160.170]) by imf29.hostedemail.com (Postfix) with ESMTP id 3E6CF120010 for ; Thu, 15 Jun 2023 08:43:22 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=L9gTbOit; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.160.170 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=1686818602; 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:in-reply-to:references:references:dkim-signature; bh=5k+8W6YpzHgSdUoJtesRB/pITjbosIv5ydX8Qu9f+Qw=; b=x9hmYRUB0aCplB7a+yukKFhjrJqm2AuxKcBiLaX9TqyFDtcZ+kXSXS6H2JZ41iPWlXjn3M mHBgAmnA2UI+RPtjPXdBJdQKFa0ohiLwlBbVwL7mcqHDjekczQ/N56yVGL5//2nvA7xpAa zzFxKJpdfFL1XJzBY5bknGMCCNJIC08= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686818602; a=rsa-sha256; cv=none; b=1XEz1X57VP5lJMUWID7WhHAUFcvaXHHdobpC8Cf5y0OsNLvd9GpSjvw1FRtUykif4gpA5c r7EJ6tbK+7dpdDKv6AmZ3lUIJBIon2ejdS7L5AHH2yCHs6gEb4ZuhbCk+6rnjWJy6VlsvL Hmn0xOdlzbAsw+995BNaYD6fwY14SkY= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=L9gTbOit; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.160.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-qt1-f170.google.com with SMTP id d75a77b69052e-3f9df7eb837so26840991cf.2 for ; Thu, 15 Jun 2023 01:43:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686818601; x=1689410601; 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=5k+8W6YpzHgSdUoJtesRB/pITjbosIv5ydX8Qu9f+Qw=; b=L9gTbOitjaiPVT1mPvKyA+1gkxVyHMUzILsZcki0A+ChBTywUw6NohiYLb1g1Ardc1 kMAEK5cFZZyUlbGGsMPuTdcRTmS+qB9DFC4KgbL+jedtkpUufHaDhGxSORQtenv5dxno 53zz55fJrTGOcwFkp3egUxDvqcto70rlu4gNyigvXcG/YlYSDa5Yehb8/c3sY9VPVH+W OTskE0Q7hvjBIGv50tIr95U8WiwV8dHyfjmjSvCSn45KdtpRTCdehu9SH6SLo2PF+1ik scfWicjFjDVMCw1azV116jpQLpvcldBAYY2FooqN0XwEDKBgjANfcgs0fzIgdXbiEPZC MxJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686818601; x=1689410601; 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=5k+8W6YpzHgSdUoJtesRB/pITjbosIv5ydX8Qu9f+Qw=; b=MFxtvQV7noWMJcLIykmdELYzQfzfMucJhIC9Nu4RbUiymYHlvYNszFkEiCkmGEBzVB DsnvsGyTBlbcS5loI3q8e5rS5bQFEjaMiIBF2GdnZE3I62yJO9zbwGjy277rbr1tzYy6 ngJBnWRiZ3QR7P4UhXSMdkuecZP1+j6PpsbA3m8Bht4Z5DUU3T/oD0uSNl7F/XKQGcHb 14ZafnP+hl4CUEtMGyM5LE233DPwy4HlMOrAo9dwFZRWM1xK7pr8V9qPcEgRdxhAEtRj DLRLmRSPAaoV9b+0UDHaiXzwuQLVFoVHuYnNWXwQPxa5Qg6b1/vtTjgWBTE/4AW10c7F D5wg== X-Gm-Message-State: AC+VfDx61nGyflymPBMd0u3lHA0+G+B+WAbjzdGIryWf0JN8ZND4bNmM S5U+o2hzXfJqDBieF8+QV5VQNQ== X-Google-Smtp-Source: ACHHUZ56d5EfqOSVGPZP9YSkx1pVZ80Ypp/B7oY4uWraBWTQMEVsdq6dzt7z8dyRJ7J/IUMgpqTn6Q== X-Received: by 2002:a05:622a:1a9d:b0:3f8:64ea:9f5c with SMTP id s29-20020a05622a1a9d00b003f864ea9f5cmr5909163qtc.35.1686818601115; Thu, 15 Jun 2023 01:43:21 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id i21-20020aa78b55000000b0064fe06fe712sm11139783pfd.129.2023.06.15.01.43.18 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 01:43:20 -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 v3 4/4] maple_tree: add a fast path case in mas_wr_slot_store() Date: Thu, 15 Jun 2023 16:43:01 +0800 Message-Id: <20230615084301.97701-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615084301.97701-1-zhangpeng.00@bytedance.com> References: <20230615084301.97701-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Stat-Signature: o6k5r7izfnronyn7368zjpthfx15w6ni X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 3E6CF120010 X-Rspam-User: X-HE-Tag: 1686818602-438957 X-HE-Meta: U2FsdGVkX1/VvKDAjSFWf/8p79sBRqF4xeinyStw8d9f27KN4XRedJJByfVEbAzB3K6TouD+LxlcWz3zzz4V7Ch0fGqpWTKNg6XYALAGlwMg44xVnuSUvvram/WECIBsKlzfUcVo2dFpDhaYBTsha+ASCoDRoTDytl+8IqzW4d45CBa75sOl7ZTYlKm1snLx9V3fcROkZpzgI8Q0YC33E9BCP0GU6l7SBrnicelxndI2YGmvNLBMxiqvMRW8u/dnBUPJ6OpY1xJ/uV99jVYtU6V7ddh3RdDLrmlyq8LjsGmoOgkAUoqc0sq0yFJlJ6g/kkU1X3K4diF/3Vy4pSijtb6nAVSAM8hxk6TAVjwyf+hkr/vxdQAyygGn7XuG2d+mvEsyuI2Euiu2F/NoFxp0ZGeTOV+MRal5M211d2mkP3htJEjKJll+1GmrRDseaYAvBzMmt7aARUWRVeGItpQJ/9Sxk+OVP3BPk86GysRlO0Xabmo/zuSG6gKpc+bVSiq80AZvt7I7cY2H1pC9dbhQWsn0lPG+xqJH2wY2aB1OVMc8GQEm12jHtogI8A9ILbS/vM5JxCWXwxk0nlG91qVzETPaSy/gr7cRNr0+DX/1vMUUpSIktaa3KuDQGCAMloQcKRBfd2tzGnUO27JCbZJ64qw8RuPX5pixMRUlGfXlw5zvDEeRg2CrRM807PkVUwCpYKV95ph/hL0YFPf6yFrwoeWMQKm+n8uygJC/fdshfzJOdUULkjbJIpAygcj6DKflRa8BOhPQnhUNfkxpMc3Q+FJv2mYAn2gthIcvC1GDX7RMktIraeL/RH1XQSEfjwZSt2LxFXW+mcxgxagA3XGw9L5oq9ZDCejlkD52dZBkTSQPtkK+DvCr01STMLFUW6iSyzs1Eds1ySqlmZSs4qCwCnaiBXp0PpU7d3yoiref0cCR9XjnxTKt8L+Y7EnQ/reirttYNhmQmcgWdBpT/pD Jq2A00si p9eaw8yar7oEZTWfDEz3MgaRTOVMInhyOKJH8SnpWYYrldFSPU/FfWdE6jRjpVxkXs4CJr6TQz7rHx5PgfPZ7Q/+SgsSF7HwYN8mJmIg4HeGS2c0XjdukR9zE8q7x1wpy22j79BmdBWAU/pAEkt4NqwsTLfEaKV1m6kiGQRl0/yahXL3rcZ4fcuqBumhdXvx8CmLwxsmClrj4PDZZwb/+0GHoD4dNKfEjTpxnuSNyF+CMEHqw0WKUgGGw4apf8uFN3rZGFO5fi5mG8AJEpUW9Z8O0Ivq2Jqm2Kk/qOkexV/QxaTiwskaHxoYRub+d6J7PBe2El3TypvGKhy+HeAyZo0F8p5YTCAjs/Px2OBHphtJKNPXosgBOF7fv0rwHhnNT1NjWtJif/EfQjHg121OgzIcb6GZSyjQM6f2xdu0GWpqCZPhLwAkkmAmCAdCVhCdFCabEJRtJmkf/lYM= 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: When expanding a range in two directions, only partially overwriting the previous and next ranges, the number of entries will not be increased, so we can just update the pivots as a fast path. However, it may introduce potential risks in RCU mode (although it may pass the test), because it updates two pivots. We only enable it in non-RCU mode for now. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 36 ++++++++++++++++++++++++------------ 1 file changed, 24 insertions(+), 12 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index da4af6743b30..bff6531fd0bc 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4100,23 +4100,35 @@ static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; unsigned char offset = mas->offset; + void __rcu **slots = wr_mas->slots; bool gap = false; - if (wr_mas->offset_end - offset != 1) - return false; - - gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset); - gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1); + gap |= !mt_slot_locked(mas->tree, slots, offset); + gap |= !mt_slot_locked(mas->tree, slots, offset + 1); - if (mas->index == wr_mas->r_min) { - /* Overwriting the range and over a part of the next range. */ - rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry); - wr_mas->pivots[offset] = mas->last; - } else { - /* Overwriting a part of the range and over the next range */ - rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry); + if (wr_mas->offset_end - offset == 1) { + if (mas->index == wr_mas->r_min) { + /* Overwriting the range and a part of the next one */ + rcu_assign_pointer(slots[offset], wr_mas->entry); + wr_mas->pivots[offset] = mas->last; + } else { + /* Overwriting a part of the range and the next one */ + rcu_assign_pointer(slots[offset + 1], wr_mas->entry); + wr_mas->pivots[offset] = mas->index - 1; + mas->offset++; /* Keep mas accurate. */ + } + } else if (!mt_in_rcu(mas->tree)) { + /* + * Expand the range, only partially overwriting the previous and + * next ranges + */ + gap |= !mt_slot_locked(mas->tree, slots, offset + 2); + rcu_assign_pointer(slots[offset + 1], wr_mas->entry); wr_mas->pivots[offset] = mas->index - 1; + wr_mas->pivots[offset + 1] = mas->last; mas->offset++; /* Keep mas accurate. */ + } else { + return false; } trace_ma_write(__func__, mas, 0, wr_mas->entry);