From patchwork Fri Jun 2 07:53:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 102358 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp866438vqr; Fri, 2 Jun 2023 01:08:09 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7rFKnUNxUj3J9TAcsz5b75zk93TnxPweZ+DFv04gOpG8NLzTo6poSlLmku25F//Sh6QGmg X-Received: by 2002:a05:6a00:240e:b0:651:7133:3f59 with SMTP id z14-20020a056a00240e00b0065171333f59mr2266881pfh.3.1685693289087; Fri, 02 Jun 2023 01:08:09 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1685693289; cv=none; d=google.com; s=arc-20160816; b=HydeCmczYhq8uVip/nVBwNncOXSNBIaN0dObvbERj2ckXtD7LbACUOzbK1sj935AQL F4uM4y/646Olwsz64bbSM+gbNSV8zMm29S/Az/Caq1IJ6oURvmXyGXan+Pk1ntd/eN6/ lPQlPb1GOh1VklNc9MA9L6J2gF8kz8uFVWVQKOqGnozMdMGnhrw+x7JNSR0ioxqNDAsU uI1AyeyLBSTBkfDJcAYpL4Jt+Y6db9OQbhdppFNOF8HNBEHRC4LyfzRMQ613i1bKJd9t 3GaLCPoPbI8vIplILkwj/+OcpB/UOc9lJZyUeFll3NsyqvY4fw3qpb4fjS24zhI+qUMz jZ0Q== 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=k3FMdTRR6nTW2Kjg3j35z+e3Gvtk7et+Y9W5l7vMbdM=; b=LlLClK3jrEQFHA1nhhEm+H9IAZ4vlTcKYsFu/5Mnn3nyn7P85ppkyDldoLm+SD1oIA af24FYNTj3QSR66gTzBRNdTLBMoeBgFrGDxYQ9PfSGc2Ex7WB/4+l4fB1OkurM7ZOddo F4LpgoONX/4CeANrTYCyUGiDhC+mzgntG4Y5kXcGtOOnG1YbXY4WyuEuJZJNSSso26px 5NRaDqp7kx0TLKKzwC2Xd1F2Iy2hWHbvtG30rFZK9SufvBvQGa0dhfMHcgROCbTSpS+e mi5jpW49kfMeHfIml9fnpJrQg+wMDw/ezpleqhE/VQr2ytkavw88cGdA9W/Rd+04cWd2 OaSQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=C6of11iF; 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 q5-20020aa79825000000b0065024e6e7c7si318315pfl.331.2023.06.02.01.07.55; Fri, 02 Jun 2023 01:08:09 -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=C6of11iF; 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 S233929AbjFBHyc (ORCPT + 99 others); Fri, 2 Jun 2023 03:54:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51060 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233840AbjFBHya (ORCPT ); Fri, 2 Jun 2023 03:54:30 -0400 Received: from mail-oi1-x233.google.com (mail-oi1-x233.google.com [IPv6:2607:f8b0:4864:20::233]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AEFCC198 for ; Fri, 2 Jun 2023 00:54:04 -0700 (PDT) Received: by mail-oi1-x233.google.com with SMTP id 5614622812f47-397f13944f2so1536804b6e.0 for ; Fri, 02 Jun 2023 00:54:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1685692444; x=1688284444; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=k3FMdTRR6nTW2Kjg3j35z+e3Gvtk7et+Y9W5l7vMbdM=; b=C6of11iFU3UUYTGr2Ndf8tNfq5ggz43N2+NM+L6xQgx2Qv4tvsKd1Qe+n1V7x1AyNJ EsqbQlL7OSuCNiUl+S9dtMYcRAID3lSD4fVl/hgUGPK7usosEP4yikSKP/+Oy0frrFwI sM/g1pX9f6lHpC6D5xvY9eq7WiNMgIZgiNqg8wQTb5dRajGvDmnVg41SdunozLL2tAJV /Cqo0RibXvwtX0KbvkbmmuB8FHLZJwSU7Igea5jKE+sz9r06fIDtZ9pgaRE1hAct5CNh oHzfNXPPidCifSJnzTTPQp0SqY3i8z4dYks25DEwF3wruFCSXS9AY3mk6YpFgmj2YUfc tzdQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685692444; x=1688284444; 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=k3FMdTRR6nTW2Kjg3j35z+e3Gvtk7et+Y9W5l7vMbdM=; b=KcDPVD0HSQ9VFX9Msb/v/NJ2ZHsYOZ/2VDJ7AH/kD0K/BS4NZ1eISgOcrbMXkDh3se 3f/h4COR5szni3Igi95608YiFboi1/kZg5tdBcfeHLug1WTdtuRL6Ha6eHzD30TW5m4W yIlr0z1XTKzDal9TO7UljNpxIHfTiX3OGvdak89grPstmUPyWmj8pjl6JcylBAWuJ2gG hTDAbaZGRPUNOAW/rSWuyAsxXg/TJ96H8ErwXCVfumHIwTiMuCjMTrr7XZ6i5twayp4J Gsb9XIxKsD/8irWYyDfmgojwNGFodcbfYYyUDKdrB9Zm1/EXrl6bz6rL8IcJbdMZOILQ ajcg== X-Gm-Message-State: AC+VfDx4ipMMIQCrkKZFYI2hE2sR4FSjE0QUNio4a05u81XQVB3Ucqr+ Rv/aB7lZu4+WKBEwpK3isi0Usw== X-Received: by 2002:a05:6808:2c6:b0:398:6008:f465 with SMTP id a6-20020a05680802c600b003986008f465mr1877942oid.4.1685692443997; Fri, 02 Jun 2023 00:54:03 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id 21-20020a170902c11500b001ac94b33ab1sm636572pli.304.2023.06.02.00.54.01 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 02 Jun 2023 00:54:03 -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 1/2] maple_tree: optimize mas_wr_append(), also improve duplicating VMAs Date: Fri, 2 Jun 2023 15:53:52 +0800 Message-Id: <20230602075353.5917-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=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_NONE,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED autolearn=ham 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?1767577526568455953?= X-GMAIL-MSGID: =?utf-8?q?1767577526568455953?= When the new range can be completely covered by the original last range without touching the boundaries on both sides, two new entries can be appended to the end as a fast path. We update the original last pivot at the end, and the newly appended two entries will not be accessed before this, so it is also safe in RCU mode. This is useful for sequential insertion, which is what we do in dup_mmap(). Enabling BENCH_FORK in test_maple_tree and just running bench_forking() gives the following time-consuming numbers: before: after: 17,874.83 msec 15,738.38 msec It shows about a 12% performance improvement for duplicating VMAs. Signed-off-by: Peng Zhang Reviewed-by:Liam R. Howlett --- lib/maple_tree.c | 33 ++++++++++++++++++++++----------- 1 file changed, 22 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 7dd54afe66ed..cfd9fad308a2 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4199,10 +4199,10 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) * * Return: True if appended, false otherwise */ -static inline bool mas_wr_append(struct ma_wr_state *wr_mas) +static inline bool mas_wr_append(struct ma_wr_state *wr_mas, + unsigned char new_end) { unsigned char end = wr_mas->node_end; - unsigned char new_end = end + 1; struct ma_state *mas = wr_mas->mas; unsigned char node_pivots = mt_pivots[wr_mas->type]; @@ -4214,16 +4214,27 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end); } - if (mas->last == wr_mas->r_max) { - /* Append to end of range */ - rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry); - wr_mas->pivots[end] = mas->index - 1; - mas->offset = new_end; + if (new_end == wr_mas->node_end + 1) { + if (mas->last == wr_mas->r_max) { + /* Append to end of range */ + rcu_assign_pointer(wr_mas->slots[new_end], + wr_mas->entry); + wr_mas->pivots[end] = mas->index - 1; + mas->offset = new_end; + } else { + /* Append to start of range */ + rcu_assign_pointer(wr_mas->slots[new_end], + wr_mas->content); + wr_mas->pivots[end] = mas->last; + rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); + } } else { - /* Append to start of range */ + /* Append to the range without touching any boundaries. */ rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->content); - wr_mas->pivots[end] = mas->last; - rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); + wr_mas->pivots[end + 1] = mas->last; + rcu_assign_pointer(wr_mas->slots[end + 1], wr_mas->entry); + wr_mas->pivots[end] = mas->index - 1; + mas->offset = end + 1; } if (!wr_mas->content || !wr_mas->entry) @@ -4270,7 +4281,7 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) goto slow_path; /* Attempt to append */ - if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas)) + if (mas_wr_append(wr_mas, new_end)) return; if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas)) From patchwork Fri Jun 2 07:53:53 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 102359 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp867439vqr; Fri, 2 Jun 2023 01:10:36 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ55ZEPojMrJ3+SY5UlUkfqk2rMh4FUB31ybeEMwAW1LWxtbZTKC3D5obs0dEg31TGj62kUZ X-Received: by 2002:a05:6358:716:b0:127:9efe:7839 with SMTP id e22-20020a056358071600b001279efe7839mr11086136rwj.7.1685693435577; Fri, 02 Jun 2023 01:10:35 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1685693435; cv=none; d=google.com; s=arc-20160816; b=C4EAztDqbQ640lv1oFZT+Dp7D9mNU03Ugi7WUht8H5EEnEVa1eZhOuhJbQTaSxXTc5 y8zP0lC8+IUkjz/U2AV966S3hB/fH3AcrVAnslTIClYOdB2gbD/ay6qI8bDKQT0h+TKT xqfLG/obb1YX/TYnywgPWDPvQmG6G7Z69ckMWDRWndLy5wyKGHSXgCMKuZJeR7H8luYt hwUPiDcSYcTVUFKWYmSfyyCtZGWxSjbmfTVxSjqCm5hEEpTzYdMBmAaTkT2TGxwjTNcy 5jL516loWvV8Ov28tC4crZLxG76aJXzo4WYdvnPle9F2d9FbOOXm1m0YIt1967qDXTuR h2VQ== 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=3qN5IJXyn5VJIlxZlQKMd5j0PC5dVod7lJR5xLLQiyk=; b=DQrw9iw7fauMWL+wkutHeTWOtHHXyAnDjeMk7dKaXvbMPTDMSwfg3Mej0nzD08pZMf r0do+canEYbkjpvgSrXqcMPYv3YMtODBJ0IgJq08gaq5VP6mizkAneA7EOSQDbW+Z0sp KoUY6baP6HV96mFULTV2QBDh6sNE8Mph7YcMZ53SULRhAPTazxqtZzSrEy1ow+JKtKZg 99/cuOF3MNvDsJCuhLosURYHR5i6DR0v1KBByoDdKkLql78xLWkZu82LscTTU5klQ4rS G7XO11FfdssZgggyIzGi6jyydDN6cqCEgtGhG+o2z+E4KJbwVm9SamF8wCElacH/t/Mj Xe9w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=DN+DM58D; 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 w14-20020a63934e000000b0053faf4483fasi637460pgm.143.2023.06.02.01.10.20; Fri, 02 Jun 2023 01:10:35 -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=DN+DM58D; 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 S232674AbjFBHyN (ORCPT + 99 others); Fri, 2 Jun 2023 03:54:13 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51106 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233860AbjFBHyJ (ORCPT ); Fri, 2 Jun 2023 03:54:09 -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 AB16D1A6 for ; Fri, 2 Jun 2023 00:54:07 -0700 (PDT) Received: by mail-pl1-x630.google.com with SMTP id d9443c01a7336-1b034ca1195so8834545ad.2 for ; Fri, 02 Jun 2023 00:54:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1685692447; x=1688284447; 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=3qN5IJXyn5VJIlxZlQKMd5j0PC5dVod7lJR5xLLQiyk=; b=DN+DM58DdgoV9FCQEn2L2Ee0umqXsCmAlN/5VriCaaB3AbhKoop5Gxcp9Mz2St/Flu GEJtT6c5cPrGmIKzKZFsDGC/Zp2gPrPeOUYxUhiBpGnJsxx75efukFTRI9nBpjus/DHi sFI5/mVTBP5NpxGZ3JNoOi5lxQUJA+fMaSenPlpydHDWok7Lha4W6mLuLQyT1VVH0GVF XdqujabuPB+y1/u2P5cZWYSgfQhrkHhJ9ljHkObKZlBi4SFou+Q/+5qqA/tXP9AUK8/J i5kHx4DFaxFx57TGO14gjmdCpBNLQLRT+omnN2hYxwTA6uvr8Bakku9hvmKrMSeRAWzg V0+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685692447; x=1688284447; 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=3qN5IJXyn5VJIlxZlQKMd5j0PC5dVod7lJR5xLLQiyk=; b=JfoGjSc4y0kJ9yZZn2qI2MtMwt+NBkOIg5OkpgKNxLKBvrQbZUG+0GX6XM0+0nZF0J DwQ+qVMy+5SCb1DFp1oCFTGtIOhVu2cxt24Ul7g/am6Yf7MMrBBAZJoAw9vAuiwCFWPc krL/Ss8ArQdPzdOhFdnQFHeBKdLJqtvuXcRR4VTsGshoNfehFGDZiZQXlFi8OapJd/OO Fz7H3K2/lQ0XJVefH+27UdZWqJJxuSqok/9ojuPtBj+P0J+pqa7H3d23SS4545lEEbFB ijek6PZoFOMpvkZD6UJGrGCLuBiETFGeFi4tlVBWSw/Te2E7BzFTFPLOcQX6ywqmpTaZ 68kA== X-Gm-Message-State: AC+VfDxaLTiQpywKShqXfaZJmaUwjOXQ5Gp5gzFWxMCzw7CPuU5ulJnE L78w6aN9X3OOOdg1K464v/d9Eg== X-Received: by 2002:a17:902:da90:b0:1b1:a4e2:a2ce with SMTP id j16-20020a170902da9000b001b1a4e2a2cemr834040plx.20.1685692446988; Fri, 02 Jun 2023 00:54:06 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id 21-20020a170902c11500b001ac94b33ab1sm636572pli.304.2023.06.02.00.54.04 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 02 Jun 2023 00:54:06 -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 2/2] maple_tree: add a fast path case in mas_wr_slot_store() Date: Fri, 2 Jun 2023 15:53:53 +0800 Message-Id: <20230602075353.5917-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230602075353.5917-1-zhangpeng.00@bytedance.com> References: <20230602075353.5917-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_NONE,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED autolearn=ham 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?1767577679770294402?= X-GMAIL-MSGID: =?utf-8?q?1767577679770294402?= When the new range overwrites three ranges and does not touch the boundaries on both sides, 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 can 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 | 33 +++++++++++++++++++++------------ 1 file changed, 21 insertions(+), 12 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index cfd9fad308a2..ec82441ca3e8 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4100,23 +4100,32 @@ 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)) { + /* Overwriting three ranges, but don't touch the boundaries */ + 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);