From: David Howells <dhowells@redhat.com>
To: Mike Rapoport <rppt@kernel.org>, Liam Howlett <liam.howlett@oracle.com>
Cc: dhowells@redhat.com,
"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
Date: Fri, 04 Feb 2022 11:24:23 +0000 [thread overview]
Message-ID: <1181363.1643973863@warthog.procyon.org.uk> (raw)
In-Reply-To: <Yfq7J9LU58FqNFVW@kernel.org>
Mike Rapoport <rppt@kernel.org> wrote:
> > +The Maple Tree maintains a small memory footprint and was designed to use
> > +modern processor cache efficiently. The most important user of the Maple Tree
> > +is the virtual memory area.
>
> For me it sounds like VMA *is* the maple tree user. Maybe
I'm having a go at using it for the netfs lib support library to store a list
of dirty regions. So far it looks like it should work for me. It might be
more useful if it had a loff_t index, but I can manage with pgoff_t.
Also isn't the intention to move xarray to use this inside eventually?
I would just drop the last sentence from the docs entirely. If someone wants
to know who is using it, they can probably work it out with grep;-). And,
anyway, once there's more than one user, which is the most important will be
subjective - and if you do put a list of users here, it's likely to get out of
date.
> > +
> > +The Maple Tree can store between 0 and ``ULONG_MAX``. The Maple Tree reserves
>
> ^ values
Indices or keys? Isn't the "value" the thing that is being storing at an
index or index range?
> > +Pre-allocating of nodes is also supported using the advanced API. This is
> > +useful for users who must guarantee a successful store operation within a given
> > +code segment when allocating cannot be done. Allocations of nodes are
> > +relatively small at 256 bytes.
>
> I doubt the size here will get timely updates when the node size will
> change in the code, maybe use "around" or "roughly" to be future proof? :)
I would suggest dropping the number and saying "Nodes are relatively small
allocations". If there's a symbol that specifies this, you could plonk that
in.
> There are a lots of comments describing the maple tree internals here and
> below. Did yaou consider adding a section "Implementation details" or
> something like that to the maple_tree.rst and linking these comments there
> with DOC: and some glue text?
Could even add a maple_tree_gory_details.rst. It doesn't necessarily have to
go in the same document as the API description.
David
next prev parent reply other threads:[~2022-02-04 11:24 UTC|newest]
Thread overview: 83+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-02-02 2:41 [PATCH v5 00/70] Introducing the Maple Tree Liam Howlett
2022-02-02 2:41 ` [PATCH v5 01/70] binfmt_elf: Take the mmap lock when walking the VMA list Liam Howlett
2022-02-02 2:41 ` [PATCH v5 02/70] radix tree test suite: Add pr_err define Liam Howlett
2022-02-02 2:41 ` [PATCH v5 05/70] radix tree test suite: Add support for slab bulk APIs Liam Howlett
2022-02-02 2:41 ` [PATCH v5 04/70] radix tree test suite: Add allocation counts and size to kmem_cache Liam Howlett
2022-02-02 2:41 ` [PATCH v5 03/70] radix tree test suite: Add kmem_cache_set_non_kernel() Liam Howlett
2022-02-02 2:41 ` [PATCH v5 06/70] radix tree test suite: Add lockdep_is_held to header Liam Howlett
2022-02-02 2:41 ` [PATCH v5 07/70] Maple Tree: Add new data structure Liam Howlett
2022-02-02 17:11 ` Mike Rapoport
2022-02-03 2:38 ` Liam Howlett
2022-02-03 8:57 ` Mike Rapoport
2022-02-03 16:02 ` Mark Hemment
2022-02-03 17:29 ` Liam Howlett
2022-02-04 11:24 ` David Howells [this message]
2022-02-02 2:42 ` [PATCH v5 08/70] lib/test_maple_tree: Add testing for maple tree Liam Howlett
2022-02-02 2:42 ` [PATCH v5 11/70] mmap: Use the VMA iterator in count_vma_pages_range() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 10/70] mm: Add VMA iterator Liam Howlett
2022-02-02 2:42 ` [PATCH v5 09/70] mm: Start tracking VMAs with maple tree Liam Howlett
2022-02-02 2:42 ` [PATCH v5 14/70] mm/mmap: Use maple tree for unmapped_area{_topdown} Liam Howlett
2022-02-02 2:42 ` [PATCH v5 13/70] mm/mmap: Use the maple tree for find_vma_prev() instead of the rbtree Liam Howlett
2022-02-02 2:42 ` [PATCH v5 12/70] mm/mmap: Use the maple tree in find_vma() " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 15/70] kernel/fork: Use maple tree for dup_mmap() during forking Liam Howlett
2022-02-03 11:59 ` Mark Hemment
2022-02-03 17:20 ` Liam Howlett
2022-02-02 2:42 ` [PATCH v5 16/70] damon: Convert __damon_va_three_regions to use the VMA iterator Liam Howlett
2022-02-02 2:42 ` [PATCH v5 17/70] proc: Remove VMA rbtree use from nommu Liam Howlett
2022-02-02 2:42 ` [PATCH v5 18/70] mm: Remove rb tree Liam Howlett
2022-02-02 2:42 ` [PATCH v5 19/70] mmap: Change zeroing of maple tree in __vma_adjust() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 22/70] mm/khugepaged: Optimize collapse_pte_mapped_thp() by using vma_lookup() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 21/70] mm: Optimize find_exact_vma() to use vma_lookup() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 20/70] xen: Use vma_lookup() in privcmd_ioctl_mmap() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 23/70] mm/mmap: Change do_brk_flags() to expand existing VMA and add do_brk_munmap() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 25/70] mm/mmap: Use advanced maple tree API for mmap_region() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 24/70] mm: Use maple tree operations for find_vma_intersection() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 26/70] mm: Remove vmacache Liam Howlett
2022-02-02 2:42 ` [PATCH v5 27/70] mm: Convert vma_lookup() to use mtree_load() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 28/70] mm/mmap: Move mmap_region() below do_munmap() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 30/70] mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap() Liam Howlett
2022-02-02 2:42 ` [PATCH v5 29/70] mm/mmap: Reorganize munmap to use maple states Liam Howlett
2022-02-02 2:42 ` [PATCH v5 31/70] arm64: Remove mmap linked list from vdso Liam Howlett
2022-02-02 2:42 ` [PATCH v5 32/70] parisc: Remove mmap linked list from cache handling Liam Howlett
2022-02-02 2:42 ` [PATCH v5 34/70] s390: Remove vma linked list walks Liam Howlett
2022-02-02 2:42 ` [PATCH v5 33/70] powerpc: Remove mmap " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 35/70] x86: Remove vma " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 36/70] xtensa: " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 37/70] cxl: Remove vma linked list walk Liam Howlett
2022-02-02 2:42 ` [PATCH v5 39/70] um: " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 38/70] optee: " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 40/70] binfmt_elf: " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 41/70] coredump: " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 42/70] exec: Use VMA iterator instead of linked list Liam Howlett
2022-02-02 2:42 ` [PATCH v5 44/70] fs/proc/task_mmu: Stop using linked list and highest_vm_end Liam Howlett
2022-02-02 2:42 ` [PATCH v5 43/70] fs/proc/base: Use maple tree iterators in place of linked list Liam Howlett
2022-02-02 2:42 ` [PATCH v5 46/70] ipc/shm: Use VMA iterator instead " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 47/70] acct: " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 45/70] userfaultfd: Use maple tree iterator to iterate VMAs Liam Howlett
2022-02-02 2:42 ` [PATCH v5 48/70] perf: Use VMA iterator Liam Howlett
2022-02-02 2:42 ` [PATCH v5 49/70] sched: Use maple tree iterator to walk VMAs Liam Howlett
2022-02-02 2:42 ` [PATCH v5 50/70] fork: Use VMA iterator Liam Howlett
2022-02-02 2:42 ` [PATCH v5 52/70] mm/gup: Use maple tree navigation instead of linked list Liam Howlett
2022-02-02 2:42 ` [PATCH v5 51/70] bpf: Remove VMA " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 53/70] mm/khugepaged: Stop using vma " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 54/70] mm/ksm: Use vma iterators instead of " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 56/70] mm/memcontrol: Stop using mm->highest_vm_end Liam Howlett
2022-02-02 2:42 ` [PATCH v5 57/70] mm/mempolicy: Use vma iterator & maple state instead of vma linked list Liam Howlett
2022-02-02 2:42 ` [PATCH v5 55/70] mm/madvise: Use vma_find() " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 58/70] mm/mlock: Use vma iterator and " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 60/70] mm/mremap: Use vma_find_intersection() " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 59/70] mm/mprotect: Use maple tree navigation " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 62/70] mm/oom_kill: Use maple tree iterators " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 63/70] mm/pagewalk: Use vma_find() " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 61/70] mm/msync: " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 64/70] mm/swapfile: Use vma iterator " Liam Howlett
2022-02-02 2:42 ` [PATCH v5 65/70] i915: Use the VMA iterator Liam Howlett
2022-02-02 2:42 ` [PATCH v5 67/70] riscv: Use vma iterator for vdso Liam Howlett
2022-02-02 2:42 ` [PATCH v5 66/70] nommu: Remove uses of VMA linked list Liam Howlett
2022-02-02 2:42 ` [PATCH v5 68/70] mm: Remove the vma " Liam Howlett
2022-02-03 12:08 ` Mark Hemment
2022-02-03 17:25 ` Liam Howlett
2022-02-02 2:42 ` [PATCH v5 69/70] mm/mmap: Drop range_has_overlap() function Liam Howlett
2022-02-02 2:42 ` [PATCH v5 70/70] mm/mmap.c: Pass in mapping to __vma_link_file() Liam Howlett
2022-02-04 11:28 ` [PATCH v5 09/70] mm: Start tracking VMAs with maple tree David Howells
2022-02-11 18:23 ` Liam Howlett
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1181363.1643973863@warthog.procyon.org.uk \
--to=dhowells@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=liam.howlett@oracle.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=maple-tree@lists.infradead.org \
--cc=rppt@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox