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;
From:   Liam Howlett <liam.howlett@oracle.com>
To:     Mark Hemment <markhemm@googlemail.com>
CC:     "maple-tree@lists.infradead.org" <maple-tree@lists.infradead.org>,
        "linux-mm@kvack.org" <linux-mm@kvack.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>
Subject: Re: [PATCH v5 07/70] Maple Tree: Add new data structure
Thread-Topic: [PATCH v5 07/70] Maple Tree: Add new data structure
Thread-Index: AQHYF95x/Sfcc+vEiUSQ90JwlBJbIqyB/zeAgAAYIYA=
Date:   Thu, 3 Feb 2022 17:29:07 +0000
Message-ID: <20220203172841.z53nwjus6sp2t7lx@revolver>
References: <20220202024137.2516438-1-Liam.Howlett@oracle.com>
 <20220202024137.2516438-8-Liam.Howlett@oracle.com>
 <CANe_+UhTyOr2SPc=SMhK=7t8Uw+HvehdTw1Ti1XGcLfJ_=BMjA@mail.gmail.com>
In-Reply-To: <CANe_+UhTyOr2SPc=SMhK=7t8Uw+HvehdTw1Ti1XGcLfJ_=BMjA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?dLMeohyCfw2tWz/NthL9iTVIUaQrab5s0q2OFLlEtKGyVKAa/1JY18k7xw4P?=
 =?us-ascii?Q?Cb2uPg8L3gjsZN9DE+DH5vTk+TeZfGRiTm90XvIxeiqbHWHGx/AplQbHxMJ0?=
 =?us-ascii?Q?TaT5aBarDtIymzGGyK+tw+igDU6gqM/jT20wda0lp7pU+RyPdd7Jg0mFwtuw?=
 =?us-ascii?Q?T0RWUm1GJe4JxLZqK4CXEXI5tL0byieH1y5xGLJpoBD44Q8jqWajZEx7ibO+?=
 =?us-ascii?Q?rb4JtvSzQAhS3/bNxrb5yxlTjj7G0bt+DHPtEGmgygPsghSpc22Ke5GgYuTY?=
 =?us-ascii?Q?guHAPMXz5LvypE9wqJIhjWkQrErDwRPRec0RecrKiSOm/QSBYwMCWeBR4RnE?=
 =?us-ascii?Q?n0wMq5IcT52Has7UNQj1mDm3aUJiawKNqQ0bToY5vXIU5MbwIQ6OXVVjXaBh?=
 =?us-ascii?Q?3cGKh7QzDlqoTNjIla/Ea1mW76iI0FQj6SYlDY69ByYT0a6AOZFY9PxAMbup?=
 =?us-ascii?Q?u8kdEG0uvJ+6MjsSyGkNisnaOfktIN1Vtvj/CambxNwDLLBtkrws+OjKNpNu?=
 =?us-ascii?Q?pPUynBjlCEcsvn0shhvfxCxTmjWkp9GF809RQxDHp+OiAbTvwiHAsfps2D+X?=
 =?us-ascii?Q?nslowXOn86OJZAaQz88SeaDGbkS6cgikC6Tf2l0AO61oX4xVmQR7/mekpCJX?=
 =?us-ascii?Q?GDlAJLmHkIGVZNiIcMy8p5l9pNnsDI2kUNTY7w/d0pP+iCYhE0Pg4bxgzWc/?=
 =?us-ascii?Q?+7OHPamEwY9ovvG8xOB5sFTkcQDRzLqPXVO73kI+5RXeJSzN8O3n3xHPmrXy?=
 =?us-ascii?Q?aC/QLHO/GQAx56exUoUnZheEDYrmxUmoGYBo4WEDC5NuYQ6nwpKDZdRfW8nP?=
 =?us-ascii?Q?7eirvF1Wf1BjHAXZff11yULGdwdV8CICRIP73vJZN512uO0dgmg61GjlldPO?=
 =?us-ascii?Q?hlwsyUuIVbZ2Q6yuxv5ynzKaqYWA8qVamNtzoOgg41CYaoNitY/o6w1ag9Sg?=
 =?us-ascii?Q?sE5/wHgX2lOHuV2Cl65hCeTtXzi/E8m0ytzSt7Zq7ABx8AqFTvSF6p0kaVdc?=
 =?us-ascii?Q?OJqKpoTAAszA6i+tLVomdV9ISuvbRuBqqJzR8Zs6aAo2pEnuByaIVaRmYEhF?=
 =?us-ascii?Q?KXzcDxbcsIPxISNXnAqtZDZQRatwHD1UeoSD95ouPP5zmk2S7dMbD7+Rmjm9?=
 =?us-ascii?Q?ucDgkIfXvTwn8/XWxmz+cBww+PoCRzbuhVMTGHifuoUqOJmChsP1i+wfOgmH?=
 =?us-ascii?Q?BX5rqGNesYOwT8vl93tlYvwXOU6wMh2pHi1N10IYkHeRmGBIAcw9skDwMn/j?=
 =?us-ascii?Q?ACaKbA/Z5f0wIKJfYaypseNvBaedT3FTKRpQa1+zRficaY2vd4NoHf5IgjFa?=
 =?us-ascii?Q?2nMzqF//qLmI6zDxxoLxsf+Y1JhE8BSqLQhrSo9fxnriz4u6xxkS569G2ZQE?=
 =?us-ascii?Q?Yiw87bgsGJQRvdHS2VW1NbtvYLNr6Q2lKetScYpWIVYU8REZ+VUGXWbskMUF?=
 =?us-ascii?Q?PLUkYk82aiaJ7gfs0MvEyh8YknFqmWeEZ9RzgwquQRJCXMErFg4ND+rUtEAu?=
 =?us-ascii?Q?RvAiF/rfJ9PCQ6b/pWs1rNncOa0Wqdamg9jQ50GCgyzJ1h2Gt7T3lpJ09xXO?=
 =?us-ascii?Q?JoI6TO2u8WdksdKXM3QMudRQ9tJ4ZtgLkErNNBAAZdo02xImNJk7zq+pxwEi?=
 =?us-ascii?Q?A08BgU7JBt/s2Ob4mfdRm24=3D?=
Content-Type: text/plain; charset="us-ascii"
Content-ID: <527487F24B07AB4D90C328EB9D44BADA@namprd10.prod.outlook.com>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 4f4d7061-4b2b-4cec-ecbf-08d9e73aae86
X-MS-Exchange-CrossTenant-originalarrivaltime: 03 Feb 2022 17:29:07.1520
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: YSOAPEwtSZXXnY8P1Z1llOQGVHvHpJi5BCibDGt2rB1a6QTWwKUj6JERByhpS4cCNv8EM9gT4M8WklN8Vcsk1Q==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA2PR10MB4745
X-Proofpoint-Virus-Version: vendor=nai engine=6300 definitions=10247 signatures=673430
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 adultscore=0
 suspectscore=0 malwarescore=0 bulkscore=0 mlxscore=0 spamscore=0
 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2201110000 definitions=main-2202030105
X-Proofpoint-GUID: xRfsMT1P0szLTXlc3y5wMHulgfiDdM_N
X-Proofpoint-ORIG-GUID: xRfsMT1P0szLTXlc3y5wMHulgfiDdM_N
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

* Mark Hemment <markhemm@googlemail.com> [220203 11:02]:
> On Wed, 2 Feb 2022 at 02:42, Liam Howlett <liam.howlett@oracle.com> wrote=
:
> >
> > From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
> >
> > The maple tree is an RCU-safe range based B-tree designed to use modern
> > processor cache efficiently.  There are a number of places in the kerne=
l
> > that a non-overlapping range-based tree would be beneficial, especially
> > one with a simple interface.  The first user that is covered in this
> > patch set is the vm_area_struct, where three data structures are
> > replaced by the maple tree: the augmented rbtree, the vma cache, and th=
e
> > linked list of VMAs in the mm_struct.  The long term goal is to reduce
> > or remove the mmap_sem contention.
> >
> > The tree has a branching factor of 10 for non-leaf nodes and 16 for lea=
f
> > nodes.  With the increased branching factor, it is significantly shorte=
r than
> > the rbtree so it has fewer cache misses.  The removal of the linked lis=
t
> > between subsequent entries also reduces the cache misses and the need t=
o pull
> > in the previous and next VMA during many tree alterations.
> >
> > Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> > ---
> >  Documentation/core-api/index.rst              |    1 +
> >  Documentation/core-api/maple_tree.rst         |  196 +
> >  MAINTAINERS                                   |   12 +
> >  include/linux/maple_tree.h                    |  673 ++
> >  include/trace/events/maple_tree.h             |  123 +
> >  lib/Kconfig.debug                             |    9 +
> >  lib/Makefile                                  |    3 +-
> >  lib/maple_tree.c                              | 6943 +++++++++++++++++
> >  tools/testing/radix-tree/.gitignore           |    2 +
> >  tools/testing/radix-tree/Makefile             |   13 +-
> >  tools/testing/radix-tree/generated/autoconf.h |    1 +
> >  tools/testing/radix-tree/linux/maple_tree.h   |    7 +
> >  tools/testing/radix-tree/maple.c              |   59 +
> >  .../radix-tree/trace/events/maple_tree.h      |    3 +
> >  14 files changed, 8042 insertions(+), 3 deletions(-)
> >  create mode 100644 Documentation/core-api/maple_tree.rst
> >  create mode 100644 include/linux/maple_tree.h
> >  create mode 100644 include/trace/events/maple_tree.h
> >  create mode 100644 lib/maple_tree.c
> >  create mode 100644 tools/testing/radix-tree/linux/maple_tree.h
> >  create mode 100644 tools/testing/radix-tree/maple.c
> >  create mode 100644 tools/testing/radix-tree/trace/events/maple_tree.h
>=20
> ...
> > +Allocating Nodes
> > +----------------
> > +
> > +Allocations are usually handled internally to the tree, however if all=
ocations
> > +need to occur before a write occurs then calling mas_entry_count() wil=
l
> > +allocate the worst-case number of needed nodes to insert the provided =
number of
> > +ranges.  This also causes the tree to enter mass insertion mode.  Once
> > +insertions are complete calling mas_destroy() on the maple state will =
free the
> > +unused allocations.
>=20
> mas_entry_count() has been renamed to mas_expected_entries().
> (Note: test code is still using mas_entry_count()).

Thanks, I just discovered the test code issue on my side.