[PATCH 00/62] XArray November 2017 Edition

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



From: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>

I've lost count of the number of times I've posted the XArray before,
so time for a new numbering scheme.  Here're two earlier versions,
https://lkml.org/lkml/2017/3/17/724
https://lwn.net/Articles/715948/ (this one's more loquacious in its
description of things that are better about the radix tree API than the
XArray).

This time around, I've gone for an approach of many small changes.
Unfortunately, that means you get 62 moderate patches instead of dozens
of big ones.

Some of these can and should go in independently of whether the XArray
is a good idea.  The first four fix some things in the test-suite.
Patch 6 changes the API for the IDR cyclic allocation.  Patch 7 changes
the API for the IDR 'extended' API that was recently added without my
review.

Patch 15 is messy and breaks any time anybody touches the page cache.
I'd like it to go in soon.  All it's doing is removing the page cache's
private spinlock and having it explicitly use the spinlock now embedded
in the xarray.

Patches 16-30 are all the fun infrastructure, adding pieces of the
xarray API.  This is probably a good place to focus review, particularly
if you're intent on critiquing the API.

Patches 31 onwards start actually using the new API, taking advantage of
the built-in locking and memory allocation to get rid of the preload
API.  There's probably the most scope for bugs here; I've tried to
understand the locking schemes used in thirty different places, and
maybe I got some of them wrong.

There will need to be many more patches.  Dozens, maybe hundreds.  Once
we've converted all the calls to radix_tree_insert() over to
xa_store(), we can get rid of the GFP flags stored in the xarray head.
That'll make the mm people a little happier.  Once we've got rid of
idr_preload(), we can get rid of the per-CPU cache of radix_tree_nodes.
I have a lot more enhancements on my todo list, but I'd like to get
something merged in the next cycle, and if I wait until my todo list is
empty, I will get nothing merged.

If you looked at earlier iterations, there was much more support for
huge pages.  That's not in this revision; I couldn't debug the problems
I was seeing.  I still have all that code, and I'm intending to put it
back in; it's just a bit down the todo list right now.

Matthew Wilcox (62):
  tools: Make __test_and_clear_bit available
  radix tree test suite: Remove ARRAY_SIZE
  radix tree test suite: Check reclaim bit
  idr test suite: Fix ida_test_random()
  radix tree: Add a missing cast to gfp_t
  idr: Make cursor explicit for cyclic allocation
  idr: Rewrite extended IDR API
  Explicitly include radix-tree.h
  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 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 xa_init
  xarray: Add xas_for_each_tag
  xarray: Add xa_get_entries and xa_get_tagged
  xarray: Add xa_destroy
  xarray: Add xas_prev_any
  xarray: Add xas_find_any / xas_next_any
  Convert IDR to use xarray
  ida: Convert to using xarray
  page cache: Convert page_cache_next_hole to XArray
  page cache: Use xarray for adding pages
  page cache: Convert page_cache_tree_delete to xarray
  page cache: Convert find_get_entry to xarray
  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
  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
  block: Remove IDR preloading
  rxrpc: Remove IDR preloading
  cgroup: Remove IDR wrappers
  dca: Remove idr_preload calls
  ipc: Remove call to idr_preload
  irq: Remove call to idr_preload
  scsi: Remove idr_preload in st driver
  firewire: Remove call to idr_preload
  drm: Remove drm_minor_lock and idr_preload
  drm: Remove drm_syncobj_fd_to_handle
  drm: Remove qxl driver IDR locks
  drm: Replace virtio IDRs with IDAs
  drm: Replace vmwgfx IDRs with IDAs
  net: Redesign act_api use of IDR
  mm: Convert page-writeback to XArray

 Documentation/cgroup-v1/memory.txt              |    2 +-
 Documentation/vm/page_migration                 |   14 +-
 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/powerpc/platforms/cell/spufs/sched.c       |    2 +-
 arch/unicore32/include/asm/cacheflush.h         |    6 +-
 block/genhd.c                                   |   23 +-
 drivers/block/brd.c                             |   87 +-
 drivers/dca/dca-sysfs.c                         |   22 +-
 drivers/firewire/core-cdev.c                    |   20 +-
 drivers/gpu/drm/amd/amdgpu/amdgpu_gem.c         |    8 +-
 drivers/gpu/drm/drm_dp_aux_dev.c                |    5 +-
 drivers/gpu/drm/drm_drv.c                       |   25 +-
 drivers/gpu/drm/drm_gem.c                       |   27 +-
 drivers/gpu/drm/drm_syncobj.c                   |   23 +-
 drivers/gpu/drm/etnaviv/etnaviv_gem_submit.c    |    6 +-
 drivers/gpu/drm/i915/i915_debugfs.c             |    4 +-
 drivers/gpu/drm/i915/i915_gem.c                 |   17 +-
 drivers/gpu/drm/msm/msm_gem_submit.c            |   10 +-
 drivers/gpu/drm/qxl/qxl_cmd.c                   |   26 +-
 drivers/gpu/drm/qxl/qxl_drv.h                   |    2 -
 drivers/gpu/drm/qxl/qxl_kms.c                   |    2 -
 drivers/gpu/drm/qxl/qxl_release.c               |   12 +-
 drivers/gpu/drm/vc4/vc4_gem.c                   |    4 +-
 drivers/gpu/drm/virtio/virtgpu_drv.h            |    6 +-
 drivers/gpu/drm/virtio/virtgpu_kms.c            |   18 +-
 drivers/gpu/drm/virtio/virtgpu_vq.c             |   12 +-
 drivers/gpu/drm/vmwgfx/vmwgfx_drv.c             |    6 +-
 drivers/gpu/drm/vmwgfx/vmwgfx_drv.h             |    2 +-
 drivers/gpu/drm/vmwgfx/vmwgfx_resource.c        |   28 +-
 drivers/infiniband/core/cm.c                    |    5 +-
 drivers/infiniband/hw/mlx4/cm.c                 |    3 +-
 drivers/infiniband/hw/mlx4/mlx4_ib.h            |    1 +
 drivers/rapidio/rio_cm.c                        |    3 +-
 drivers/rpmsg/qcom_glink_native.c               |    7 +-
 drivers/scsi/st.c                               |   18 +-
 drivers/staging/lustre/lustre/llite/glimpse.c   |    2 +-
 drivers/staging/lustre/lustre/mdc/mdc_request.c |   10 +-
 drivers/target/target_core_device.c             |    4 +-
 drivers/usb/host/xhci.h                         |    1 +
 fs/afs/write.c                                  |    2 +-
 fs/btrfs/compression.c                          |    4 +-
 fs/btrfs/extent_io.c                            |    8 +-
 fs/btrfs/inode.c                                |    4 +-
 fs/buffer.c                                     |   13 +-
 fs/cifs/file.c                                  |    2 +-
 fs/dax.c                                        |  204 ++--
 fs/f2fs/data.c                                  |    6 +-
 fs/f2fs/dir.c                                   |    6 +-
 fs/f2fs/gc.c                                    |    2 +-
 fs/f2fs/inline.c                                |    6 +-
 fs/f2fs/node.c                                  |    8 +-
 fs/fs-writeback.c                               |   18 +-
 fs/fscache/cookie.c                             |    2 +-
 fs/fscache/object.c                             |    2 +-
 fs/inode.c                                      |   11 +-
 fs/kernfs/dir.c                                 |    5 +-
 fs/nfsd/nfs4state.c                             |    4 +-
 fs/nfsd/state.h                                 |    1 +
 fs/nilfs2/btnode.c                              |   20 +-
 fs/nilfs2/page.c                                |   22 +-
 fs/notify/inotify/inotify_user.c                |   15 +-
 fs/proc/loadavg.c                               |    2 +-
 fs/proc/task_mmu.c                              |    2 +-
 fs/xfs/libxfs/xfs_sb.c                          |   11 +-
 fs/xfs/libxfs/xfs_sb.h                          |    2 +-
 fs/xfs/xfs_aops.c                               |   15 +-
 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                          |   71 +-
 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/drm/drm_file.h                          |    7 +-
 include/linux/backing-dev.h                     |   12 +-
 include/linux/fs.h                              |   68 +-
 include/linux/fscache.h                         |    1 +
 include/linux/fsnotify_backend.h                |    1 +
 include/linux/idr.h                             |  204 ++--
 include/linux/kernfs.h                          |    1 +
 include/linux/mm.h                              |    3 +-
 include/linux/pagemap.h                         |    4 +-
 include/linux/pid_namespace.h                   |    1 +
 include/linux/radix-tree.h                      |  111 +-
 include/linux/swapops.h                         |   19 +-
 include/linux/xarray.h                          |  717 +++++++++++
 include/net/act_api.h                           |   27 +-
 include/net/sctp/sctp.h                         |    1 +
 ipc/util.c                                      |   28 +-
 kernel/bpf/syscall.c                            |    8 +-
 kernel/cgroup/cgroup.c                          |   63 +-
 kernel/irq/timings.c                            |    4 +-
 kernel/pid.c                                    |    6 +-
 kernel/pid_namespace.c                          |   12 +-
 lib/Makefile                                    |    2 +-
 lib/dma-debug.c                                 |    1 +
 lib/idr.c                                       |  470 ++++----
 lib/radix-tree.c                                |  348 ++----
 lib/xarray.c                                    | 1444 +++++++++++++++++++++++
 mm/filemap.c                                    |  306 ++---
 mm/huge_memory.c                                |   10 +-
 mm/khugepaged.c                                 |   51 +-
 mm/madvise.c                                    |    2 +-
 mm/memcontrol.c                                 |    4 +-
 mm/migrate.c                                    |   31 +-
 mm/mincore.c                                    |    2 +-
 mm/page-writeback.c                             |   79 +-
 mm/readahead.c                                  |    4 +-
 mm/rmap.c                                       |    4 +-
 mm/shmem.c                                      |  196 ++-
 mm/swap.c                                       |    2 +-
 mm/swap_state.c                                 |   17 +-
 mm/truncate.c                                   |   34 +-
 mm/vmalloc.c                                    |   37 +-
 mm/vmscan.c                                     |   12 +-
 mm/workingset.c                                 |   34 +-
 net/rxrpc/af_rxrpc.c                            |    2 +-
 net/rxrpc/ar-internal.h                         |    1 +
 net/rxrpc/conn_client.c                         |   21 +-
 net/sched/act_api.c                             |  135 +--
 net/sched/cls_basic.c                           |   20 +-
 net/sched/cls_bpf.c                             |   20 +-
 net/sched/cls_flower.c                          |   32 +-
 net/sched/cls_u32.c                             |   44 +-
 net/sctp/associola.c                            |    3 +-
 net/sctp/protocol.c                             |    1 +
 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/spinlock.h                  |    2 +
 tools/testing/radix-tree/.gitignore             |    2 +
 tools/testing/radix-tree/Makefile               |   14 +-
 tools/testing/radix-tree/idr-test.c             |   28 +-
 tools/testing/radix-tree/linux.c                |    2 +-
 tools/testing/radix-tree/linux/kernel.h         |    2 -
 tools/testing/radix-tree/linux/rcupdate.h       |    2 +
 tools/testing/radix-tree/linux/xarray.h         |    2 +
 tools/testing/radix-tree/multiorder.c           |   53 +-
 tools/testing/radix-tree/test.c                 |    8 +-
 tools/testing/radix-tree/xarray-test.c          |  122 ++
 156 files changed, 4178 insertions(+), 2454 deletions(-)
 create mode 100644 include/linux/xarray.h
 create mode 100644 lib/xarray.c
 create mode 100644 tools/include/asm-generic/bitops/non-atomic.h
 create mode 100644 tools/testing/radix-tree/linux/xarray.h
 create mode 100644 tools/testing/radix-tree/xarray-test.c

-- 
2.15.0




[Index of Archives]     [Linux Ext4 Filesystem]     [Union Filesystem]     [Filesystem Testing]     [Ceph Users]     [Ecryptfs]     [AutoFS]     [Kernel Newbies]     [Share Photos]     [Security]     [Netfilter]     [Bugtraq]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux Cachefs]     [Reiser Filesystem]     [Linux RAID]     [Samba]     [Device Mapper]     [CEPH Development]

  Powered by Linux