* [GIT PULL] XArray for 4.20
@ 2018-10-23 20:08 Matthew Wilcox
2018-10-24 3:29 ` Matthew Wilcox
2018-10-28 18:50 ` Linus Torvalds
0 siblings, 2 replies; 6+ messages in thread
From: Matthew Wilcox @ 2018-10-23 20:08 UTC (permalink / raw)
To: Linus Torvalds; +Cc: linux-kernel
Hi Linus,
Please consider pulling the XArray patch set. The XArray provides an
improved interface to the radix tree data structure, providing locking
as part of the API, specifying GFP flags at allocation time, eliminating
preloading, less re-walking the tree, more efficient iterations and not
exposing RCU-protected pointers to its users.
This patch set
1. Introduces the XArray implementation
2. Converts the pagecache to use it
3. Converts memremap to use it
The page cache is the most complex and important user of the radix tree,
so converting it was most important. Converting the memremap code
removes the only other user of the multiorder code, which allows us to
remove the radix tree code that supported it.
I have 40+ followup patches to convert many other users of the radix tree
over to the XArray, but I'd like to get this part in first. The other
conversions haven't been in linux-next and aren't suitable for applying
yet, but you can see them in the xarray-conv branch if you're interested.
In preparing this pull request, I realised I messed up and pushed a
rebase from two days ago to infradead. There's no substantial change
from the version I pushed out to infradead for linux-next testing on
September 29th (mostly test suite and documentation cleanups).
The following changes since commit 291d0e5d81e101392379217b06251fe8c27f1f80:
Merge tag 'for-linus-20180929' of git://git.kernel.dk/linux-block (2018-09-29 14:52:14 -0700)
are available in the Git repository at:
git://git.infradead.org/users/willy/linux-dax.git xarray
for you to fetch changes up to 3a08cd52c37c793ffc199f6fc2ecfc368e284b2d:
radix tree: Remove multiorder support (2018-10-21 10:46:48 -0400)
----------------------------------------------------------------
Matthew Wilcox (90):
Update email address
idr: Permit any valid kernel pointer to be stored
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 XArray load operation
xarray: Add XArray marks
xarray: Add XArray unconditional store operations
xarray: Add XArray conditional store operations
xarray: Add XArray iterators
xarray: Extract entries from an XArray
xarray: Destroy an XArray
xarray: Step through an XArray
xarray: Add xas_for_each_conflict
xarray: Add xas_create_range
xarray: Add xa_reserve and xa_release
xarray: Add MAINTAINERS entry
xarray: Track free entries in an XArray
ida: Convert to XArray
page cache: Rearrange address_space
page cache: Convert hole search to XArray
page cache: Add and replace pages using the XArray
page cache: Convert page deletion to XArray
page cache: Convert find_get_entry to XArray
page cache: Convert find_get_entries to XArray
page cache: Convert find_get_pages_range to XArray
page cache: Convert find_get_pages_contig to XArray
page cache; Convert find_get_pages_range_tag to XArray
page cache: Convert find_get_entries_tag to XArray
page cache: Convert filemap_map_pages to XArray
radix tree test suite: Convert regression1 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
mm: Convert is_page_cache_freeable to XArray
pagevec: Use xa_mark_t
shmem: Convert shmem_radix_tree_replace to XArray
shmem: Convert shmem_confirm_swap to XArray
shmem: Convert find_swap_entry 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
memfd: Convert memfd_wait_for_pins to XArray
memfd: Convert memfd_tag_pins 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
dax: Rename some functions
dax: Hash on XArray instead of mapping
dax: Convert dax_insert_pfn_mkwrite to XArray
dax: Convert dax_layout_busy_page to XArray
dax: Convert __dax_invalidate_entry to XArray
dax: Convert dax writeback to XArray
dax: Convert dax_lock_mapping_entry to XArray
dax: Convert page fault handlers to XArray
page cache: Finish XArray conversion
radix tree: Remove radix_tree_update_node_t
radix tree: Remove split/join code
radix tree: Remove radix_tree_maybe_preload_order
radix tree: Remove radix_tree_clear_tags
radix tree test suite: Convert tag_tagged_items to XArray
radix tree test suite: Convert iteration test to XArray
xarray: Move multiorder account test in-kernel
xarray: Move multiorder_shrink to kernel tests
xarray: Move multiorder_check to in-kernel tests
xarray: Add range store functionality
memremap: Convert to XArray
radix tree test suite: Remove __item_insert
radix tree test suite: Remove multiorder benchmarking
radix tree tests: Move item_insert_order
radix tree tests: Convert item_kill_tree to XArray
radix tree tests: Convert item_delete_rcu to XArray
radix tree test: Convert multiorder tests to XArray
radix tree: Remove multiorder support
.clang-format | 1 -
.mailmap | 7 +
Documentation/core-api/index.rst | 1 +
Documentation/core-api/xarray.rst | 435 ++++++
MAINTAINERS | 17 +-
arch/parisc/kernel/syscall.S | 2 +-
arch/powerpc/include/asm/book3s/64/pgtable.h | 4 +-
arch/powerpc/include/asm/nohash/64/pgtable.h | 4 +-
drivers/gpu/drm/i915/i915_gem.c | 17 +-
drivers/input/keyboard/hilkbd.c | 2 +-
drivers/pci/hotplug/acpiphp.h | 2 +-
drivers/pci/hotplug/acpiphp_core.c | 4 +-
drivers/pci/hotplug/acpiphp_glue.c | 2 +-
drivers/staging/erofs/utils.c | 18 +-
fs/btrfs/compression.c | 6 +-
fs/btrfs/extent_io.c | 12 +-
fs/buffer.c | 14 +-
fs/dax.c | 907 +++++------
fs/ext4/inode.c | 2 +-
fs/f2fs/data.c | 6 +-
fs/f2fs/dir.c | 2 +-
fs/f2fs/f2fs.h | 2 +-
fs/f2fs/inline.c | 2 +-
fs/f2fs/node.c | 6 +-
fs/fs-writeback.c | 25 +-
fs/gfs2/aops.c | 2 +-
fs/inode.c | 2 +-
fs/isofs/dir.c | 2 +-
fs/nfs/blocklayout/blocklayout.c | 2 +-
fs/nilfs2/btnode.c | 26 +-
fs/nilfs2/page.c | 29 +-
fs/proc/task_mmu.c | 2 +-
include/linux/fs.h | 63 +-
include/linux/idr.h | 18 +-
include/linux/pagemap.h | 10 +-
include/linux/pagevec.h | 8 +-
include/linux/radix-tree.h | 178 +--
include/linux/swap.h | 22 +-
include/linux/swapops.h | 19 +-
include/linux/xarray.h | 1293 +++++++++++++++-
kernel/memremap.c | 76 +-
lib/Kconfig | 5 +-
lib/Kconfig.debug | 3 +
lib/Makefile | 3 +-
lib/idr.c | 401 ++---
lib/radix-tree.c | 834 ++--------
lib/test_xarray.c | 1238 +++++++++++++++
lib/xarray.c | 2036 +++++++++++++++++++++++++
mm/Kconfig | 4 +-
mm/filemap.c | 724 ++++-----
mm/huge_memory.c | 17 +-
mm/khugepaged.c | 178 +--
mm/madvise.c | 2 +-
mm/memcontrol.c | 2 +-
mm/memfd.c | 105 +-
mm/migrate.c | 48 +-
mm/mincore.c | 2 +-
mm/page-writeback.c | 72 +-
mm/readahead.c | 10 +-
mm/shmem.c | 193 +--
mm/swap.c | 6 +-
mm/swap_state.c | 119 +-
mm/truncate.c | 27 +-
mm/vmscan.c | 10 +-
mm/workingset.c | 70 +-
tools/include/asm-generic/bitops.h | 1 +
tools/include/asm-generic/bitops/atomic.h | 9 -
tools/include/asm-generic/bitops/non-atomic.h | 109 ++
tools/include/linux/bitmap.h | 1 +
tools/include/linux/kernel.h | 1 +
tools/include/linux/spinlock.h | 12 +-
tools/testing/radix-tree/.gitignore | 1 +
tools/testing/radix-tree/Makefile | 11 +-
tools/testing/radix-tree/benchmark.c | 141 +-
tools/testing/radix-tree/bitmap.c | 23 +
tools/testing/radix-tree/generated/autoconf.h | 2 +-
tools/testing/radix-tree/idr-test.c | 71 +-
tools/testing/radix-tree/iteration_check.c | 109 +-
tools/testing/radix-tree/linux/bug.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/radix-tree.h | 1 -
tools/testing/radix-tree/linux/rcupdate.h | 2 +
tools/testing/radix-tree/main.c | 66 +-
tools/testing/radix-tree/multiorder.c | 609 +-------
tools/testing/radix-tree/regression1.c | 75 +-
tools/testing/radix-tree/regression2.c | 8 +-
tools/testing/radix-tree/regression3.c | 23 -
tools/testing/radix-tree/tag_check.c | 33 +-
tools/testing/radix-tree/test.c | 131 +-
tools/testing/radix-tree/test.h | 13 +-
tools/testing/radix-tree/xarray.c | 35 +
93 files changed, 7054 insertions(+), 3812 deletions(-)
create mode 100644 Documentation/core-api/xarray.rst
create mode 100644 lib/test_xarray.c
create mode 100644 lib/xarray.c
create mode 100644 tools/include/asm-generic/bitops/non-atomic.h
create mode 100644 tools/testing/radix-tree/bitmap.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/xarray.c
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GIT PULL] XArray for 4.20
2018-10-23 20:08 [GIT PULL] XArray for 4.20 Matthew Wilcox
@ 2018-10-24 3:29 ` Matthew Wilcox
2018-10-28 18:50 ` Linus Torvalds
1 sibling, 0 replies; 6+ messages in thread
From: Matthew Wilcox @ 2018-10-24 3:29 UTC (permalink / raw)
To: Linus Torvalds; +Cc: linux-kernel
On Tue, Oct 23, 2018 at 01:08:25PM -0700, Matthew Wilcox wrote:
> In preparing this pull request, I realised I messed up and pushed a
> rebase from two days ago to infradead. There's no substantial change
> from the version I pushed out to infradead for linux-next testing on
> September 29th (mostly test suite and documentation cleanups).
I found the git hash from back then and pushed out a branch that is what
has been in linux-next:
git://git.infradead.org/users/willy/linux-dax.git xarray-2018-09-29
I can send you the fixes later in the merge window, if that's what
you'd prefer.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GIT PULL] XArray for 4.20
2018-10-23 20:08 [GIT PULL] XArray for 4.20 Matthew Wilcox
2018-10-24 3:29 ` Matthew Wilcox
@ 2018-10-28 18:50 ` Linus Torvalds
2018-10-28 19:13 ` Matthew Wilcox
1 sibling, 1 reply; 6+ messages in thread
From: Linus Torvalds @ 2018-10-28 18:50 UTC (permalink / raw)
To: willy; +Cc: Linux Kernel Mailing List
On Tue, Oct 23, 2018 at 1:08 PM Matthew Wilcox <willy@infradead.org> wrote:
<
> Please consider pulling the XArray patch set.
Pulled.
I took the more recent version of yours, because by the time I
actually had time to review this thing for pulling, even the recent
version had been in linux-next for a week.
Of course, I don't think linux-next has been updated, so it's all
moot, but the point is that I didn't get the feeling that it was all
some very recent code.
I do like how the conversions look, with the code in some cases
notably simpler. And it looks like at least one of the conflicts
(fs/dax.c) was due to a bug-fix to the old code where your simpler
xarray replacement didn't have the problem.
NOTE! I did get some conflicts with other stuff, and while the
conflict resolution all looked pretty straightforward, this does want
looking at.
Particularly the mm/workingset.c code.
It's still undergoing my build tests to verify my merge, but that
should be completed soon. I'll do a basic boot test too due to the
core nature of these changes, but assuming it all passes I'll push
this out within the next 30 minutes and would appreciate people giving
it a second look for verification.
Thanks,
Linus
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GIT PULL] XArray for 4.20
2018-10-28 18:50 ` Linus Torvalds
@ 2018-10-28 19:13 ` Matthew Wilcox
2018-10-28 19:21 ` Linus Torvalds
0 siblings, 1 reply; 6+ messages in thread
From: Matthew Wilcox @ 2018-10-28 19:13 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Linux Kernel Mailing List
On Sun, Oct 28, 2018 at 11:50:19AM -0700, Linus Torvalds wrote:
> On Tue, Oct 23, 2018 at 1:08 PM Matthew Wilcox <willy@infradead.org> wrote:
> <
> > Please consider pulling the XArray patch set.
>
> Pulled.
Thanks!
> I took the more recent version of yours, because by the time I
> actually had time to review this thing for pulling, even the recent
> version had been in linux-next for a week.
>
> Of course, I don't think linux-next has been updated, so it's all
> moot, but the point is that I didn't get the feeling that it was all
> some very recent code.
>
> I do like how the conversions look, with the code in some cases
> notably simpler. And it looks like at least one of the conflicts
> (fs/dax.c) was due to a bug-fix to the old code where your simpler
> xarray replacement didn't have the problem.
Yes, that's right. It turned out to be a problem for any multiorder
radix tree user, and that was a consequence of how the radix tree API
worked for multiorder entries. The XArray API just works better for
multiorder entries.
> NOTE! I did get some conflicts with other stuff, and while the
> conflict resolution all looked pretty straightforward, this does want
> looking at.
>
> Particularly the mm/workingset.c code.
I've been rebasing the xarray-conv branch on your tree pretty regularly
this week, so I have a fairly good idea how I think it should look.
I'll check to see if you & I have the same thoughts when you push it out.
> It's still undergoing my build tests to verify my merge, but that
> should be completed soon. I'll do a basic boot test too due to the
> core nature of these changes, but assuming it all passes I'll push
> this out within the next 30 minutes and would appreciate people giving
> it a second look for verification.
Thank you.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GIT PULL] XArray for 4.20
2018-10-28 19:13 ` Matthew Wilcox
@ 2018-10-28 19:21 ` Linus Torvalds
2018-10-28 19:27 ` Matthew Wilcox
0 siblings, 1 reply; 6+ messages in thread
From: Linus Torvalds @ 2018-10-28 19:21 UTC (permalink / raw)
To: willy; +Cc: Linux Kernel Mailing List
On Sun, Oct 28, 2018 at 12:13 PM Matthew Wilcox <willy@infradead.org> wrote:
>
> On Sun, Oct 28, 2018 at 11:50:19AM -0700, Linus Torvalds wrote:
>
> > NOTE! I did get some conflicts with other stuff, and while the
> > conflict resolution all looked pretty straightforward, this does want
> > looking at.
> >
> > Particularly the mm/workingset.c code.
>
> I've been rebasing the xarray-conv branch on your tree pretty regularly
> this week, so I have a fairly good idea how I think it should look.
> I'll check to see if you & I have the same thoughts when you push it out.
It's pushed out now. I'm running the kernel now, but have done only
basic boot testing (in addition to my usual build tests), no real
stress-tests.
Linus
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GIT PULL] XArray for 4.20
2018-10-28 19:21 ` Linus Torvalds
@ 2018-10-28 19:27 ` Matthew Wilcox
0 siblings, 0 replies; 6+ messages in thread
From: Matthew Wilcox @ 2018-10-28 19:27 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Linux Kernel Mailing List
On Sun, Oct 28, 2018 at 12:21:19PM -0700, Linus Torvalds wrote:
> On Sun, Oct 28, 2018 at 12:13 PM Matthew Wilcox <willy@infradead.org> wrote:
> >
> > On Sun, Oct 28, 2018 at 11:50:19AM -0700, Linus Torvalds wrote:
> >
> > > NOTE! I did get some conflicts with other stuff, and while the
> > > conflict resolution all looked pretty straightforward, this does want
> > > looking at.
> > >
> > > Particularly the mm/workingset.c code.
> >
> > I've been rebasing the xarray-conv branch on your tree pretty regularly
> > this week, so I have a fairly good idea how I think it should look.
> > I'll check to see if you & I have the same thoughts when you push it out.
>
> It's pushed out now. I'm running the kernel now, but have done only
> basic boot testing (in addition to my usual build tests), no real
> stress-tests.
Yep, no differences in how we resolved the conflicts.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2018-10-28 19:27 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-10-23 20:08 [GIT PULL] XArray for 4.20 Matthew Wilcox
2018-10-24 3:29 ` Matthew Wilcox
2018-10-28 18:50 ` Linus Torvalds
2018-10-28 19:13 ` Matthew Wilcox
2018-10-28 19:21 ` Linus Torvalds
2018-10-28 19:27 ` Matthew Wilcox
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®