From mboxrd@z Thu Jan 1 00:00:00 1970 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 A39A9C433EF for ; Thu, 3 Feb 2022 16:02:57 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 35B998D0158; Thu, 3 Feb 2022 11:02:57 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 30B358D0157; Thu, 3 Feb 2022 11:02:57 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1D3E68D0158; Thu, 3 Feb 2022 11:02:57 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0238.hostedemail.com [216.40.44.238]) by kanga.kvack.org (Postfix) with ESMTP id 08C8C8D0157 for ; Thu, 3 Feb 2022 11:02:57 -0500 (EST) Received: from smtpin14.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay03.hostedemail.com (Postfix) with ESMTP id B706D82C1D3E for ; Thu, 3 Feb 2022 16:02:56 +0000 (UTC) X-FDA: 79101937152.14.569B33F Received: from mail-ua1-f53.google.com (mail-ua1-f53.google.com [209.85.222.53]) by imf11.hostedemail.com (Postfix) with ESMTP id 501D540004 for ; Thu, 3 Feb 2022 16:02:56 +0000 (UTC) Received: by mail-ua1-f53.google.com with SMTP id u76so6033757uau.3 for ; Thu, 03 Feb 2022 08:02:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=yQV3gPl1yDUBgxhny6R2vDhSuqKPXgGrUGZ3acHuiKk=; b=f/Gne2cEJE032CfqiT7wIXCMdEMeDWaNJaLR0uJbv/ll95V4w9Muj9+2Dt+ZFGTzIK ZT0l0HlLnM5cR4zkia5kROkDaIeFVJXpm5sjYGPQpxHGVfBJo4PQwkCFB+YE5/OqxFKR WbKW8TcLvT38g0muYFRVMgWjPY5EBGj2/a5/onaMv3+av491P+ABP/UovecDJkMIxIK6 TVSo/g+g4mHE+K06lvS0qQobDByynd+Njzk9WMCQQ0WDF053NsNl67QNSqrDUIfunIaK 4kZ3IHjk2ZCYsnFVjDyoaDKaWhI0/GeWokBMv3cSnVDCXpcu3F3RvxJSvR0JCLau8HtS dyqA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=yQV3gPl1yDUBgxhny6R2vDhSuqKPXgGrUGZ3acHuiKk=; b=b9HN5JDaLHplFFPo0sHdeK7H9iGCFbFpXIlCKelYB3pFzryMemT3vOAY5FTuJDkfeN o54DFyw0qB/Enr4hEY+XMpAcxqQaxoteTuNlUPv5XWdwbgqsBDy1xICCM9z42gIzkFAv rjI8WXbAzBqYN4CRLYHxau1VRynBtryWGtGgk98rXla8Dc2xrtgq9aLR07JxgOwmSp5a J5nH42aQhksXKm8xF1kxdse0RmCD/kbiF3seXgyqPFLmXb3gDQbjc7gcpGex0E+dEL9S 262P8giR/6N4gWnrH2YBdCNln2V+/HfeLiJXrSFJ3+fQ96USwDBi5YMRYNVTXAe640lv tvtg== X-Gm-Message-State: AOAM531sEZQ8vGW/9s5b4lPBpXcglM/EpjdahHBZ9VxZeIOnr27WM5Rp hs4onc7MPFC97GoalaMNNNMJ1M6yGKSk5xwMntI= X-Google-Smtp-Source: ABdhPJyhBbjRx1aCHhjU2k8YsIrOTaKsE/26P0h7qLgq7eQonjXjzD0pD9bIMm0zB/xqXcpOBnsVgM90Bnk9OZjiSv8= X-Received: by 2002:ab0:6398:: with SMTP id y24mr8266775uao.92.1643904175454; Thu, 03 Feb 2022 08:02:55 -0800 (PST) MIME-Version: 1.0 References: <20220202024137.2516438-1-Liam.Howlett@oracle.com> <20220202024137.2516438-8-Liam.Howlett@oracle.com> In-Reply-To: <20220202024137.2516438-8-Liam.Howlett@oracle.com> From: Mark Hemment Date: Thu, 3 Feb 2022 16:02:43 +0000 Message-ID: Subject: Re: [PATCH v5 07/70] Maple Tree: Add new data structure To: Liam Howlett Cc: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton Content-Type: text/plain; charset="UTF-8" Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=googlemail.com header.s=20210112 header.b="f/Gne2cE"; spf=pass (imf11.hostedemail.com: domain of markhemm@googlemail.com designates 209.85.222.53 as permitted sender) smtp.mailfrom=markhemm@googlemail.com; dmarc=pass (policy=quarantine) header.from=googlemail.com X-Rspam-User: nil X-Rspamd-Queue-Id: 501D540004 X-Stat-Signature: su47ce1q69hun7kgr36ofzepcgp5ez9r X-Rspamd-Server: rspam12 X-HE-Tag: 1643904176-889493 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: On Wed, 2 Feb 2022 at 02:42, Liam Howlett wrote: > > From: "Liam R. Howlett" > > 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 kernel > 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 the > 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 leaf > nodes. With the increased branching factor, it is significantly shorter than > the rbtree so it has fewer cache misses. The removal of the linked list > between subsequent entries also reduces the cache misses and the need to pull > in the previous and next VMA during many tree alterations. > > Signed-off-by: Matthew Wilcox (Oracle) > Signed-off-by: Liam R. Howlett > --- > 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 ... > +Allocating Nodes > +---------------- > + > +Allocations are usually handled internally to the tree, however if allocations > +need to occur before a write occurs then calling mas_entry_count() will > +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. mas_entry_count() has been renamed to mas_expected_entries(). (Note: test code is still using mas_entry_count()). Cheers, Mark