[PATCH v6 00/99] XArray version 6

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>

This version of the XArray has no known bugs.  I have converted the
radix tree test suite entirely over to the XArray and fixed all bugs
that it has uncovered.  There are additional tests in the test suite for
the XArray, so I now claim the XArray has better test coverage than the
Radix Tree did.  Of course, that is not the same thing as fewer bugs,
but it now stands up to the tender embraces of Trinity without crashing.

You can get this version from my git tree here:
http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray-2018-01-09
which includes a number of other patches that are at least tangentially
related to this patch set.

Most of the work I've done recently has been converting additional users
from the radix tree to the XArray.  That's going pretty well; still 24
radix tree users left to convert.  It's been worth doing because I've
spotted several common patterns that have led to changes (the lock_type,
reserve/release) and some common patterns that I'll add support for
later (chaining multiple entries from a single index, wanting to use
64-bit indices on 32-bit machines, having an array of XArrays, various
workarounds for not having range entries yet).

As far as line count goes, for the whole git tree, we're at:
 212 files changed, 7764 insertions(+), 7002 deletions(-)
with another 1376 lines to delete from radix-tree.[ch].  That doesn't take
into account the 371 lines of xarray.rst, the 587 lines of xarray-test.c,
and the fact that almost half of lib/xarray.c and include/linux/xarray.h
is documentation.

Changes since version 5:

 - Rebased to 4.15-rc8

API changes:
 - Renamed __xa_init() to xa_init_flags().
 - Added DEFINE_XARRAY_FLAGS().
 - Renamed xa_ctx to xa_lock_type; store it in the XA_FLAGS and use separate
   locking classes for each type so that lockdep doesn't emit spurious
   warnings.  It also reduces the amount of boilerplate.
 - Combined __xa_store_bh, __xa_store_irq and __xa_store into __xa_store().
 - Ditto for __xa_cmpxchg().
 - Renamed xa_store_empty() to xa_insert().
 - Added __xa_insert().
 - Added xa_reserve() and xa_release().
 - Renamed XA_NO_TAG to XA_PRESENT.
 - Combined xa_get_entries(), xa_get_tagged() and xa_get_maybe_tag()
   into xa_extract().
 - Added 'filter' argument to xa_find(), xa_find_after() and xa_for_each()
   to match xa_extract() and provide the functionality that would
   have otherwise had to be added in the form of xa_find_tag(),
   xa_find_tag_after() and xa_for_each_tag().
 - Replaced workingset_lookup_update() with mapping_set_update().
 - Renamed page_cache_tree_delete() to page_cache_delete().

New xarray users:
 - Converted SuperH interrupt controller radix tree to XArray.
 - Converted blk-cgroup radix tree to XArray.
 - Converted blk-ioc radix tree to XArray.
 - Converted i915 handles_vma radix tree to XArray.
 - Converted s390 gmap radix trees to XArray.
 - Converted hwspinlock to XArray.
 - Converted btrfs fs_roots to XArray.
 - Converted btrfs reada_zones to XArray.
 - Converted btrfs reada_extents to XArray.
 - Converted btrfs reada_tree to XArray.
 - Converted btrfs buffer_radix to XArray.
 - Converted btrfs delayed_nodes to XArray.
 - Converted btrfs name_cache to XArray.
 - Converted f2fs pids radix tree to XArray.
 - Converted f2fs ino_root radix tree to XArray.
 - Converted f2fs extent_tree to XArray.
 - Converted f2fs gclist radix tree to XArray.
 - Converted dma-debug active cacheline radix tree to XArray.
 - Converted Xen pvcalls-back socketpass_mappings to XArray.
 - Converted net/qrtr radix tree to XArray.
 - Converted null_blk radix trees to XArray.

Documentation:
 - Added a bit more internals documentation.
 - Rewrote xa_init_flags documentation.
 - Added the __xa_ functions to the locking table.
 - Rewrote the section on using the __xa_ functions.

Internal changes:
 - Free up the bottom four bits of the xa_flags, since these are not
   valid GFP flags to pass to kmem_cache_alloc().
 - Moved the XA_FLAGS_TRACK_FREE bit to the bottom bits of the flags to leave
   space for more tags (later).
 - Fixed multiple bugs in xas_find() and xas_find_tag().
 - Fixed bug in shrinking XArray (and add a test case that exercises it).
 - Fixed bug in erasing multi-index entries.
 - Fixed a compile warning with CONFIG_RADIX_TREE_MULTIORDER=n.
 - Added an xas_update() helper.
 - Use ->array to track an xa_node's state through its lifecycle
   (allocated -> rcu_free -> actually free).
 - Made XA_BUG_ON dump the entire tree while XA_NODE_BUG_ON dumps only the
   node that appears suspect.
 - Fixed debugging printks to use %px and pr_cont/pr_info etc.
 - Renamed some internal tag functions.
 - Moved xa_track_free() from xarray.h to xarray.c.

Test suite:
 - Added new tests for xas_find() and xas_find_tag().
 - Added new tests for the update_node functionality.
 - Converted the radix tree test suite to the xarray API.

Matthew Wilcox (99):
  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
  xarray: Add ability to store errno values
  idr: Convert to XArray
  ida: Convert to XArray
  xarray: Add xa_reserve and xa_release
  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 dax_unlock_mapping_entry to XArray
  dax: Convert lock_slot to XArray
  dax: More XArray conversion
  dax: Convert __dax_invalidate_mapping_entry to XArray
  dax: Convert dax_writeback_one to XArray
  dax: Convert dax_insert_pfn_mkwrite to XArray
  dax: Convert dax_insert_mapping_entry to XArray
  dax: Convert grab_mapping_entry to XArray
  dax: Fix sparse warning
  page cache: Finish XArray conversion
  mm: Convert cgroup writeback to XArray
  vmalloc: Convert to XArray
  brd: Convert to XArray
  xfs: Convert m_perag_tree to XArray
  xfs: Convert pag_ici_root to XArray
  xfs: Convert xfs dquot to XArray
  xfs: Convert mru cache to XArray
  usb: Convert xhci-mem to XArray
  md: Convert raid5-cache to XArray
  irqdomain: Convert to XArray
  fscache: Convert to XArray
  sh: intc: Convert to XArray
  blk-cgroup: Convert to XArray
  blk-ioc: Convert to XArray
  i915: Convert handles_vma to XArray
  s390: Convert gmap to XArray
  hwspinlock: Convert to XArray
  btrfs: Convert fs_roots_radix to XArray
  btrfs: Remove unused spinlock
  btrfs: Convert reada_zones to XArray
  btrfs: Convert reada_extents to XArray
  btrfs: Convert reada_tree to XArray
  btrfs: Convert buffer_radix to XArray
  btrfs: Convert delayed_nodes_tree to XArray
  btrfs: Convert name_cache to XArray
  f2fs: Convert pids radix tree to XArray
  f2fs: Convert ino_root to XArray
  f2fs: Convert extent_tree_root to XArray
  f2fs: Convert gclist.iroot to XArray
  dma-debug: Convert to XArray
  xen: Convert pvcalls-back to XArray
  qrtr: Convert to XArray
  null_blk: Convert to XArray

 Documentation/cgroup-v1/memory.txt              |    2 +-
 Documentation/core-api/index.rst                |    1 +
 Documentation/core-api/xarray.rst               |  371 +++++
 Documentation/vm/page_migration                 |   14 +-
 MAINTAINERS                                     |   12 +
 arch/arm/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/s390/include/asm/gmap.h                    |   12 +-
 arch/s390/mm/gmap.c                             |  133 +-
 block/bfq-cgroup.c                              |    4 +-
 block/blk-cgroup.c                              |   52 +-
 block/blk-ioc.c                                 |   13 +-
 block/cfq-iosched.c                             |    4 +-
 drivers/block/brd.c                             |   93 +-
 drivers/block/null_blk.c                        |   87 +-
 drivers/gpu/drm/i915/i915_gem.c                 |   19 +-
 drivers/gpu/drm/i915/i915_gem_context.c         |   12 +-
 drivers/gpu/drm/i915/i915_gem_context.h         |    4 +-
 drivers/gpu/drm/i915/i915_gem_execbuffer.c      |    6 +-
 drivers/gpu/drm/i915/selftests/mock_context.c   |    2 +-
 drivers/hwspinlock/hwspinlock_core.c            |  151 +-
 drivers/md/raid5-cache.c                        |  119 +-
 drivers/sh/intc/core.c                          |    9 +-
 drivers/sh/intc/internals.h                     |    5 +-
 drivers/sh/intc/virq.c                          |   72 +-
 drivers/staging/lustre/lustre/llite/glimpse.c   |   12 +-
 drivers/staging/lustre/lustre/mdc/mdc_request.c |   16 +-
 drivers/usb/host/xhci-mem.c                     |   68 +-
 drivers/usb/host/xhci.h                         |    6 +-
 drivers/xen/pvcalls-back.c                      |   51 +-
 fs/afs/write.c                                  |    9 +-
 fs/btrfs/btrfs_inode.h                          |    7 +-
 fs/btrfs/compression.c                          |    6 +-
 fs/btrfs/ctree.h                                |   31 +-
 fs/btrfs/delayed-inode.c                        |   65 +-
 fs/btrfs/disk-io.c                              |   73 +-
 fs/btrfs/extent_io.c                            |  106 +-
 fs/btrfs/inode.c                                |   72 +-
 fs/btrfs/reada.c                                |  205 ++-
 fs/btrfs/send.c                                 |   19 +-
 fs/btrfs/tests/btrfs-tests.c                    |   29 +-
 fs/btrfs/transaction.c                          |   87 +-
 fs/btrfs/volumes.c                              |    5 +-
 fs/btrfs/volumes.h                              |    5 +-
 fs/buffer.c                                     |   25 +-
 fs/cifs/file.c                                  |    9 +-
 fs/dax.c                                        |  383 ++---
 fs/ext4/inode.c                                 |    2 +-
 fs/f2fs/checkpoint.c                            |   85 +-
 fs/f2fs/data.c                                  |    9 +-
 fs/f2fs/dir.c                                   |    5 +-
 fs/f2fs/extent_cache.c                          |   59 +-
 fs/f2fs/f2fs.h                                  |    6 +-
 fs/f2fs/gc.c                                    |   14 +-
 fs/f2fs/gc.h                                    |    2 +-
 fs/f2fs/inline.c                                |    6 +-
 fs/f2fs/node.c                                  |   10 +-
 fs/f2fs/super.c                                 |    2 -
 fs/f2fs/trace.c                                 |   60 +-
 fs/f2fs/trace.h                                 |    2 -
 fs/fs-writeback.c                               |   37 +-
 fs/fscache/cookie.c                             |    6 +-
 fs/fscache/internal.h                           |    2 +-
 fs/fscache/object.c                             |    2 +-
 fs/fscache/page.c                               |  152 +-
 fs/fscache/stats.c                              |    6 +-
 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/libxfs/xfs_sb.c                          |   11 +-
 fs/xfs/libxfs/xfs_sb.h                          |    2 +-
 fs/xfs/xfs_dquot.c                              |   38 +-
 fs/xfs/xfs_icache.c                             |  146 +-
 fs/xfs/xfs_icache.h                             |   11 +-
 fs/xfs/xfs_inode.c                              |   24 +-
 fs/xfs/xfs_mount.c                              |   22 +-
 fs/xfs/xfs_mount.h                              |    6 +-
 fs/xfs/xfs_mru_cache.c                          |   72 +-
 fs/xfs/xfs_qm.c                                 |   36 +-
 fs/xfs/xfs_qm.h                                 |   18 +-
 include/linux/backing-dev-defs.h                |    2 +-
 include/linux/backing-dev.h                     |   14 +-
 include/linux/blk-cgroup.h                      |    5 +-
 include/linux/fs.h                              |   68 +-
 include/linux/fscache.h                         |    8 +-
 include/linux/idr.h                             |  168 ++-
 include/linux/iocontext.h                       |    6 +-
 include/linux/irqdomain.h                       |   10 +-
 include/linux/mm.h                              |   17 +-
 include/linux/pagemap.h                         |   16 +-
 include/linux/pagevec.h                         |    8 +-
 include/linux/radix-tree.h                      |   97 +-
 include/linux/swap.h                            |   22 +-
 include/linux/swapops.h                         |   19 +-
 include/linux/xarray.h                          | 1052 ++++++++++++++
 kernel/irq/irqdomain.c                          |   39 +-
 kernel/pid.c                                    |    2 +-
 lib/Makefile                                    |    2 +-
 lib/dma-debug.c                                 |  105 +-
 lib/idr.c                                       |  633 ++++----
 lib/radix-tree.c                                |  399 ++----
 lib/xarray.c                                    | 1753 +++++++++++++++++++++++
 mm/backing-dev.c                                |   22 +-
 mm/filemap.c                                    |  766 ++++------
 mm/huge_memory.c                                |   23 +-
 mm/khugepaged.c                                 |  182 +--
 mm/madvise.c                                    |    2 +-
 mm/memcontrol.c                                 |    6 +-
 mm/memory.c                                     |   16 +-
 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/vmalloc.c                                    |   39 +-
 mm/vmscan.c                                     |   14 +-
 mm/workingset.c                                 |   89 +-
 net/qrtr/qrtr.c                                 |   21 +-
 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             |   40 +-
 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/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          |  587 ++++++++
 143 files changed, 6647 insertions(+), 3990 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.15.1