From: Matthew Wilcox <willy@infradead.org>
To: Andrew Morton <akpm@linux-foundation.org>
Cc: Matthew Wilcox <mawilcox@microsoft.com>,
linux-kernel@vger.kernel.org, linux-mm@kvack.org,
linux-fsdevel@vger.kernel.org
Subject: [PATCH v7 00/61] XArray version 7 -- for merging
Date: Mon, 19 Feb 2018 11:44:55 -0800 [thread overview]
Message-ID: <20180219194556.6575-1-willy@infradead.org> (raw)
From: Matthew Wilcox <mawilcox@microsoft.com>
This patchset is, I believe, appropriate for merging for 4.17.
It contains the XArray implementation, to eventually replace the radix
tree, and converts the page cache to use it.
Improvements the XArray has over the radix tree:
- The radix tree provides operations like other trees do; 'insert' and
'delete'. But what most users really want is an automatically resizing
array, and so it makes more sense to give users an API that is like
an array -- 'load' and 'store'. We still have an 'insert' operation
for users that really want that semantic.
- Locking is part of the API. This simplifies a lot of users who
formerly had to manage their own locking just for the radix tree.
It also improves code generation as we can now tell RCU that we're
holding a lock and it doesn't need to generate as much fencing code.
The other advantage is that tree nodes can be moved (not yet
implemented).
- GFP flags are now parameters to calls which may need to allocate
memory. The radix tree forced users to decide what the allocation
flags would be at creation time. It's much clearer to specify them
at allocation time.
- Memory is not preloaded; we don't tie up dozens of pages on the
off chance that the slab allocator fails. Instead, we drop the lock,
allocate a new node and retry the operation.
- The XArray provides a cmpxchg operation. The radix tree forces users
to roll their own (and at least four have).
- Iterators take a 'max' parameter. That simplifies many users and
will reduce the amount of iteration done.
- Iteration can proceed backwards. We only have one user for this, but
since it's called as part of the pagefault readahead algorithm, that
seemed worth mentioning.
- RCU-protected pointers are not exposed as part of the API. There are
some fun bugs where the page cache forgets to use rcu_dereference()
in the current codebase.
- Value entries gain an extra bit compared to radix tree exceptional
entries. That gives us the extra bit we need to put huge page swap
entries in the page cache.
- Some iterators now take a 'filter' argument instead of having
separate iterators for tagged/untagged iterations.
This conversion keeps the radix tree and XArray data structures in sync
at all times. That allows us to convert the page cache one function at
a time and should allow for easier bisection.
The page cache is improved by this:
- Shorter, easier to read code
- More efficient iterations
- Reduction in size of struct address_space
- Fewer walks from the top of the data structure; the XArray API
encourages staying at the leaf node and conducting operations there.
Matthew Wilcox (61):
radix tree test suite: Check reclaim bit
radix tree: Use bottom four bits of gfp_t for flags
arm64: Turn flush_dcache_mmap_lock into a no-op
unicore32: Turn flush_dcache_mmap_lock into a no-op
Export __set_page_dirty
xfs: Rename xa_ elements to ail_
fscache: Use appropriate radix tree accessors
xarray: Add the xa_lock to the radix_tree_root
page cache: Use xa_lock
xarray: Replace exceptional entries
xarray: Change definition of sibling entries
xarray: Add definition of struct xarray
xarray: Define struct xa_node
xarray: Add documentation
xarray: Add xa_load
xarray: Add xa_get_tag, xa_set_tag and xa_clear_tag
xarray: Add xa_store
xarray: Add xa_cmpxchg and xa_insert
xarray: Add xa_for_each
xarray: Add xa_extract
xarray: Add xa_destroy
xarray: Add xas_next and xas_prev
xarray: Add xas_create_range
xarray: Add MAINTAINERS entry
page cache: Convert hole search to XArray
page cache: Add page_cache_range_empty function
page cache: Add and replace pages using the XArray
page cache: Convert page deletion to XArray
page cache: Convert page cache lookups to XArray
page cache: Convert delete_batch to XArray
page cache: Remove stray radix comment
page cache: Convert filemap_range_has_page to XArray
mm: Convert page-writeback to XArray
mm: Convert workingset to XArray
mm: Convert truncate to XArray
mm: Convert add_to_swap_cache to XArray
mm: Convert delete_from_swap_cache to XArray
mm: Convert __do_page_cache_readahead to XArray
mm: Convert page migration to XArray
mm: Convert huge_memory to XArray
mm: Convert collapse_shmem to XArray
mm: Convert khugepaged_scan_shmem to XArray
pagevec: Use xa_tag_t
shmem: Convert replace to XArray
shmem: Convert shmem_confirm_swap to XArray
shmem: Convert find_swap_entry to XArray
shmem: Convert shmem_tag_pins to XArray
shmem: Convert shmem_wait_for_pins to XArray
shmem: Convert shmem_add_to_page_cache to XArray
shmem: Convert shmem_alloc_hugepage to XArray
shmem: Convert shmem_free_swap to XArray
shmem: Convert shmem_partial_swap_usage to XArray
shmem: Comment fixups
btrfs: Convert page cache to XArray
fs: Convert buffer to XArray
fs: Convert writeback to XArray
nilfs2: Convert to XArray
f2fs: Convert to XArray
lustre: Convert to XArray
dax: Convert to XArray
page cache: Finish XArray conversion
Documentation/cgroup-v1/memory.txt | 2 +-
Documentation/core-api/index.rst | 1 +
Documentation/core-api/xarray.rst | 361 +++++
Documentation/vm/page_migration | 14 +-
MAINTAINERS | 12 +
arch/arm/include/asm/cacheflush.h | 6 +-
arch/arm64/include/asm/cacheflush.h | 6 +-
arch/nios2/include/asm/cacheflush.h | 6 +-
arch/parisc/include/asm/cacheflush.h | 6 +-
arch/powerpc/include/asm/book3s/64/pgtable.h | 4 +-
arch/powerpc/include/asm/nohash/64/pgtable.h | 4 +-
arch/unicore32/include/asm/cacheflush.h | 6 +-
drivers/gpu/drm/i915/i915_gem.c | 17 +-
drivers/staging/lustre/lustre/llite/glimpse.c | 12 +-
drivers/staging/lustre/lustre/mdc/mdc_request.c | 16 +-
fs/afs/write.c | 9 +-
fs/btrfs/btrfs_inode.h | 7 +-
fs/btrfs/compression.c | 6 +-
fs/btrfs/extent_io.c | 24 +-
fs/btrfs/inode.c | 70 -
fs/buffer.c | 28 +-
fs/cifs/file.c | 9 +-
fs/dax.c | 458 +++----
fs/ext4/inode.c | 2 +-
fs/f2fs/data.c | 9 +-
fs/f2fs/dir.c | 5 +-
fs/f2fs/gc.c | 2 +-
fs/f2fs/inline.c | 6 +-
fs/f2fs/node.c | 10 +-
fs/fs-writeback.c | 37 +-
fs/fscache/cookie.c | 2 +-
fs/fscache/object.c | 2 +-
fs/gfs2/aops.c | 2 +-
fs/inode.c | 11 +-
fs/nfs/blocklayout/blocklayout.c | 2 +-
fs/nilfs2/btnode.c | 41 +-
fs/nilfs2/page.c | 78 +-
fs/proc/task_mmu.c | 2 +-
fs/xfs/xfs_aops.c | 15 +-
fs/xfs/xfs_buf_item.c | 10 +-
fs/xfs/xfs_dquot.c | 4 +-
fs/xfs/xfs_dquot_item.c | 11 +-
fs/xfs/xfs_inode_item.c | 22 +-
fs/xfs/xfs_log.c | 6 +-
fs/xfs/xfs_log_recover.c | 80 +-
fs/xfs/xfs_trans.c | 18 +-
fs/xfs/xfs_trans_ail.c | 152 +--
fs/xfs/xfs_trans_buf.c | 4 +-
fs/xfs/xfs_trans_priv.h | 42 +-
include/linux/backing-dev.h | 12 +-
include/linux/fs.h | 68 +-
include/linux/idr.h | 22 +-
include/linux/mm.h | 3 +-
include/linux/pagemap.h | 16 +-
include/linux/pagevec.h | 8 +-
include/linux/radix-tree.h | 96 +-
include/linux/swap.h | 22 +-
include/linux/swapops.h | 19 +-
include/linux/xarray.h | 1015 ++++++++++++++
kernel/pid.c | 2 +-
lib/Makefile | 2 +-
lib/idr.c | 67 +-
lib/radix-tree.c | 234 ++--
lib/xarray.c | 1667 +++++++++++++++++++++++
mm/filemap.c | 766 ++++-------
mm/huge_memory.c | 23 +-
mm/khugepaged.c | 182 +--
mm/madvise.c | 2 +-
mm/memcontrol.c | 6 +-
mm/migrate.c | 41 +-
mm/mincore.c | 2 +-
mm/page-writeback.c | 78 +-
mm/readahead.c | 10 +-
mm/rmap.c | 4 +-
mm/shmem.c | 312 ++---
mm/swap.c | 6 +-
mm/swap_state.c | 124 +-
mm/truncate.c | 45 +-
mm/vmscan.c | 14 +-
mm/workingset.c | 89 +-
tools/include/linux/spinlock.h | 12 +-
tools/testing/radix-tree/.gitignore | 2 +
tools/testing/radix-tree/Makefile | 15 +-
tools/testing/radix-tree/idr-test.c | 6 +-
tools/testing/radix-tree/linux.c | 2 +-
tools/testing/radix-tree/linux/bug.h | 1 +
tools/testing/radix-tree/linux/gfp.h | 1 +
tools/testing/radix-tree/linux/kconfig.h | 1 +
tools/testing/radix-tree/linux/kernel.h | 5 +
tools/testing/radix-tree/linux/lockdep.h | 11 +
tools/testing/radix-tree/linux/rcupdate.h | 2 +
tools/testing/radix-tree/linux/xarray.h | 3 +
tools/testing/radix-tree/multiorder.c | 83 +-
tools/testing/radix-tree/regression1.c | 68 +-
tools/testing/radix-tree/test.c | 53 +-
tools/testing/radix-tree/test.h | 6 +
tools/testing/radix-tree/xarray-test.c | 556 ++++++++
97 files changed, 5211 insertions(+), 2232 deletions(-)
create mode 100644 Documentation/core-api/xarray.rst
create mode 100644 include/linux/xarray.h
create mode 100644 lib/xarray.c
create mode 100644 tools/testing/radix-tree/linux/kconfig.h
create mode 100644 tools/testing/radix-tree/linux/lockdep.h
create mode 100644 tools/testing/radix-tree/linux/xarray.h
create mode 100644 tools/testing/radix-tree/xarray-test.c
--
2.16.1
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next reply other threads:[~2018-02-19 19:44 UTC|newest]
Thread overview: 72+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-02-19 19:44 Matthew Wilcox [this message]
2018-02-19 19:44 ` [PATCH v7 01/61] radix tree test suite: Check reclaim bit Matthew Wilcox
2018-02-19 19:44 ` [PATCH v7 02/61] radix tree: Use bottom four bits of gfp_t for flags Matthew Wilcox
2018-03-03 12:44 ` Jeff Layton
2018-03-03 17:09 ` Matthew Wilcox
2018-02-19 19:44 ` [PATCH v7 03/61] arm64: Turn flush_dcache_mmap_lock into a no-op Matthew Wilcox
2018-02-19 19:44 ` [PATCH v7 04/61] unicore32: " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 05/61] Export __set_page_dirty Matthew Wilcox
2018-03-03 13:56 ` Jeff Layton
2018-02-19 19:45 ` [PATCH v7 06/61] xfs: Rename xa_ elements to ail_ Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 07/61] fscache: Use appropriate radix tree accessors Matthew Wilcox
2018-03-03 13:57 ` Jeff Layton
2018-02-19 19:45 ` [PATCH v7 08/61] xarray: Add the xa_lock to the radix_tree_root Matthew Wilcox
2018-03-03 14:19 ` Jeff Layton
2018-03-03 14:55 ` Jeff Layton
2018-03-03 16:57 ` Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 09/61] page cache: Use xa_lock Matthew Wilcox
2018-03-03 14:27 ` Jeff Layton
2018-02-19 19:45 ` [PATCH v7 10/61] xarray: Replace exceptional entries Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 11/61] xarray: Change definition of sibling entries Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 12/61] xarray: Add definition of struct xarray Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 13/61] xarray: Define struct xa_node Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 14/61] xarray: Add documentation Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 15/61] xarray: Add xa_load Matthew Wilcox
2018-02-20 7:34 ` Philippe Ombredanne
2018-02-20 12:47 ` Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 16/61] xarray: Add xa_get_tag, xa_set_tag and xa_clear_tag Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 17/61] xarray: Add xa_store Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 18/61] xarray: Add xa_cmpxchg and xa_insert Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 19/61] xarray: Add xa_for_each Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 20/61] xarray: Add xa_extract Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 21/61] xarray: Add xa_destroy Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 22/61] xarray: Add xas_next and xas_prev Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 23/61] xarray: Add xas_create_range Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 24/61] xarray: Add MAINTAINERS entry Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 25/61] page cache: Convert hole search to XArray Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 26/61] page cache: Add page_cache_range_empty function Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 27/61] page cache: Add and replace pages using the XArray Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 28/61] page cache: Convert page deletion to XArray Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 29/61] page cache: Convert page cache lookups " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 30/61] page cache: Convert delete_batch " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 31/61] page cache: Remove stray radix comment Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 32/61] page cache: Convert filemap_range_has_page to XArray Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 33/61] mm: Convert page-writeback " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 34/61] mm: Convert workingset " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 35/61] mm: Convert truncate " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 36/61] mm: Convert add_to_swap_cache " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 37/61] mm: Convert delete_from_swap_cache " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 38/61] mm: Convert __do_page_cache_readahead " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 39/61] mm: Convert page migration " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 40/61] mm: Convert huge_memory " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 41/61] mm: Convert collapse_shmem " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 42/61] mm: Convert khugepaged_scan_shmem " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 43/61] pagevec: Use xa_tag_t Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 44/61] shmem: Convert replace to XArray Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 45/61] shmem: Convert shmem_confirm_swap " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 46/61] shmem: Convert find_swap_entry " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 47/61] shmem: Convert shmem_tag_pins " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 48/61] shmem: Convert shmem_wait_for_pins " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 49/61] shmem: Convert shmem_add_to_page_cache " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 50/61] shmem: Convert shmem_alloc_hugepage " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 51/61] shmem: Convert shmem_free_swap " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 52/61] shmem: Convert shmem_partial_swap_usage " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 53/61] shmem: Comment fixups Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 54/61] btrfs: Convert page cache to XArray Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 55/61] fs: Convert buffer " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 56/61] fs: Convert writeback " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 57/61] nilfs2: Convert " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 58/61] f2fs: " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 59/61] lustre: " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 60/61] dax: " Matthew Wilcox
2018-02-19 19:45 ` [PATCH v7 61/61] page cache: Finish XArray conversion Matthew Wilcox
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=20180219194556.6575-1-willy@infradead.org \
--to=willy@infradead.org \
--cc=akpm@linux-foundation.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mawilcox@microsoft.com \
/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;
as well as URLs for NNTP newsgroup(s).