[PATCH v4 00/73] XArray version 4

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>

I looked through some notes and decided this was version 4 of the XArray.
Last posted two weeks ago, this version includes a *lot* of changes.
I'd like to thank Dave Chinner for his feedback, encouragement and
distracting ideas for improvement, which I'll get to once this is merged.

Highlights:
 - Over 2000 words of documentation in patch 8!  And lots more kernel-doc.
 - The page cache is now fully converted to the XArray.
 - Many more tests in the test-suite.

This patch set is not for applying.  0day is still reporting problems,
and I'd feel bad for eating someone's data.  These patches apply on top
of a set of prepatory patches which just aren't interesting.  If you
want to see the patches applied to a tree, I suggest pulling my git tree:
http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray-2017-12-04
I also left out the idr_preload removals.  They're still in the git tree,
but I'm not looking for feedback on them.

Changes since v3:

XArray API differences:
 - Store a pointer to the struct xarray in the xa_state (changes almost
   every prototype in the advanced API).
 - Added xas_lock() etc to operate on the XArray stored in the xa_state.
 - Added xa_erase() as a synonym for xa_store(..., NULL, 0).
 - Added __xa_erase() which is an exact replacement for radix_tree_delete();
   it assumes you are holding the xa_lock.
 - Renamed xa_next() to xa_find_after().
 - Renamed xas_next() to xas_next_entry().
 - Renamed xas_prev_any() and xas_next_any() to xas_prev() and xas_next().
 - Changed the semantics of xas_prev() and xas_next() substantially
   (see their kernel-doc).
 - Renamed skip entry to zero entry.
 - Introduced a new XAS_BOUNDS state to distinguish between an xa_state
   that has not been walked and an xa_state that has walked off the
   current end of the array.
 - Changed xas_set_err() to take a negative errno, not a positive one.
   XAS_ERROR still takes a positive errno, but this is an undocumented
   internal part of the implementation, not an API.
 - Changed behaviour when returning a multi-index entry; xas.xa_index
   is now always set to the first (canonical) index of this entry.
   Before, it was never rewound.  Eg if you have an entry occupying
   indices 4-7, and called xas_load() with xas.xa_index set to 6, it
   will now set xas.xa_index to 4.
 - Changed xas_nomem() to release any allocated memory if there is no
   ENOMEM error.  This means that (unless the user explicitly bypasses
   calling xas_nomem() on some path), there's no need to call xas_destroy()
   and it is removed from the API.
 - Added xas_create_range() for the benefit of our current hugepage users.
   I hope to be able to remove it again once they are converted to use
   multi-index entries.
 - Add xa_get_maybe_tag() which will call xa_get_entries() if you specify
   XA_NO_TAG and xa_get_tagged otherwise.

IDR API differences:
 - Removed the IDR cyclic API change (decided not to do it after all).
 - Made idr_alloc_ul() and idr_alloc_u32() assign the ID before inserting
   the pointer into the IDR, so a lookup cannot find an uninitialised object.

Bug fixes:
 - Made INIT_RADIX_TREE() initialise the xa_lock correctly so lockdep
   doesn't whine about it.
 - Fixed a locking bug in the IPC IDR conversion.
 - If we call xas_store(&xas, NULL) and that causes the XArray to shrink,
   set the xas to the XAS_BOUNDS state so we don't dereference a pointer
   to a node which has been passed to RCU free.  This is only a problem
   on !SMP machines.
 - Fixed bug when shrinking the XArray to a single entry at index 0.
 - Fixed bug where we could scan off the end of the slot array when storing
   a NULL.
 - Made xas_pause() not do anything if we're in an error state.  Before, it
   would have dereferenced a NULL pointer.
 - Fixed a bug in xa_find_after().  it just plain didn't work.  Now there is
   a test-case for it.

Conversions:
 - Converted backing dev cgroup code from radix tree to XArray.
 - Converted the USB XHCI driver from radix tree to XArray.
 - Moved btrfs_page_exists_in_range() guts to page cache code.
 - Renamed page_cache_{next,prev}_hole() to ..._gap().  The page cache
   doesn't cache holes.
 - Finished the page cache conversion.

Miscellaneous:
 - Documentation.  Lots and lots of documentation.  xarray.rst, more XArray
   kernel-doc and also IDR kernel-doc which has been missing for years.
 - Added MAINTAINERS entry for XArray/IDR.
 - Deleted the now-unused parts of the radix tree API (see git tree).
 - Added XA_DEBUG code and enable it in test-suite.
 - Improved code generation for initialising xa_state by explicitly
   initialising the struct padding (stupid gcc).
 - Stub out more code if CONFIG_RADIX_TREE_MULTIORDER isn't enabled.
 - Added more tests to the test-suite.
 - Removed the IDR preload conversions from this patch set (see git tree).

Matthew Wilcox (73):
  xfs: Rename xa_ elements to ail_
  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
  xarray: Add xa_for_each
  xarray: Add xas_for_each_tag
  xarray: Add xa_get_entries, xa_get_tagged and xa_get_maybe_tag
  xarray: Add xa_destroy
  xarray: Add xas_next and xas_prev
  xarray: Add xas_create_range
  xarray: Add MAINTAINERS entry
  idr: Convert to XArray
  ida: Convert to XArray
  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
  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 cgroup writeback 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
  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

 Documentation/cgroup-v1/memory.txt              |    2 +-
 Documentation/core-api/index.rst                |    1 +
 Documentation/core-api/xarray.rst               |  287 +++++
 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 +-
 drivers/block/brd.c                             |   87 +-
 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 +-
 drivers/usb/host/xhci-mem.c                     |   70 +-
 drivers/usb/host/xhci.h                         |    6 +-
 fs/afs/write.c                                  |    2 +-
 fs/btrfs/btrfs_inode.h                          |    7 +-
 fs/btrfs/compression.c                          |    6 +-
 fs/btrfs/extent_io.c                            |   16 +-
 fs/btrfs/inode.c                                |   70 --
 fs/buffer.c                                     |   22 +-
 fs/cifs/file.c                                  |    2 +-
 fs/dax.c                                        |  382 +++---
 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/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_buf_item.c                           |   10 +-
 fs/xfs/xfs_dquot.c                              |   37 +-
 fs/xfs/xfs_dquot_item.c                         |   11 +-
 fs/xfs/xfs_icache.c                             |  142 +--
 fs/xfs/xfs_icache.h                             |   10 +-
 fs/xfs/xfs_inode.c                              |   24 +-
 fs/xfs/xfs_inode_item.c                         |   22 +-
 fs/xfs/xfs_log.c                                |    6 +-
 fs/xfs/xfs_log_recover.c                        |   80 +-
 fs/xfs/xfs_mount.c                              |   22 +-
 fs/xfs/xfs_mount.h                              |    6 +-
 fs/xfs/xfs_mru_cache.c                          |   72 +-
 fs/xfs/xfs_qm.c                                 |   32 +-
 fs/xfs/xfs_qm.h                                 |   18 +-
 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-defs.h                |    2 +-
 include/linux/backing-dev.h                     |   14 +-
 include/linux/fs.h                              |   68 +-
 include/linux/idr.h                             |  173 ++-
 include/linux/mm.h                              |    2 +-
 include/linux/pagemap.h                         |   16 +-
 include/linux/pagevec.h                         |    8 +-
 include/linux/radix-tree.h                      |   95 +-
 include/linux/swap.h                            |    5 +-
 include/linux/swapops.h                         |   19 +-
 include/linux/xarray.h                          |  887 +++++++++++++
 kernel/pid.c                                    |    2 +-
 lib/Makefile                                    |    2 +-
 lib/idr.c                                       |  617 +++++----
 lib/radix-tree.c                                |  413 ++----
 lib/xarray.c                                    | 1520 +++++++++++++++++++++++
 mm/backing-dev.c                                |   28 +-
 mm/filemap.c                                    |  746 ++++-------
 mm/huge_memory.c                                |   23 +-
 mm/khugepaged.c                                 |  182 ++-
 mm/madvise.c                                    |    2 +-
 mm/memcontrol.c                                 |    4 +-
 mm/migrate.c                                    |   41 +-
 mm/mincore.c                                    |    2 +-
 mm/page-writeback.c                             |   78 +-
 mm/readahead.c                                  |   10 +-
 mm/rmap.c                                       |    4 +-
 mm/shmem.c                                      |  311 ++---
 mm/swap.c                                       |    6 +-
 mm/swap_state.c                                 |  124 +-
 mm/truncate.c                                   |   45 +-
 mm/vmalloc.c                                    |   39 +-
 mm/vmscan.c                                     |   14 +-
 mm/workingset.c                                 |   78 +-
 tools/include/linux/spinlock.h                  |    2 +
 tools/testing/radix-tree/.gitignore             |    2 +
 tools/testing/radix-tree/Makefile               |   15 +-
 tools/testing/radix-tree/idr-test.c             |   29 +-
 tools/testing/radix-tree/linux/bug.h            |    1 +
 tools/testing/radix-tree/linux/kconfig.h        |    1 +
 tools/testing/radix-tree/linux/rcupdate.h       |    2 +
 tools/testing/radix-tree/linux/xarray.h         |    3 +
 tools/testing/radix-tree/multiorder.c           |   53 +-
 tools/testing/radix-tree/regression1.c          |   68 +-
 tools/testing/radix-tree/test.c                 |    8 +-
 tools/testing/radix-tree/xarray-test.c          |  468 +++++++
 103 files changed, 5309 insertions(+), 2908 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/xarray.h
 create mode 100644 tools/testing/radix-tree/xarray-test.c

-- 
2.15.0