All of lore.kernel.org
 help / color / mirror / Atom feed
* Please pull IDR rewrite
@ 2017-02-28 21:11 Matthew Wilcox
  2017-02-28 23:38 ` Linus Torvalds
  0 siblings, 1 reply; 3+ messages in thread
From: Matthew Wilcox @ 2017-02-28 21:11 UTC (permalink / raw)
  To: Linus Torvalds; +Cc: linux-kernel

Hi Linus,

The most significant part of the following is the patch to rewrite the
IDR & IDA to be clients of the radix tree.  But there's much more,
including an enhancement of the IDA to be significantly more space
efficient, an IDR & IDA test suite, some improvements to the IDR API
(and driver changes to take advantage of those improvements), several
improvements to the radix tree test suite and RCU annotations.

The IDR & IDA rewrite had a good spin in linux-next and Andrew's
tree for most of the last cycle.  Coupled with the IDR test suite,
I feel pretty confident that any remaining bugs are quite hard to hit.
0-day did a great job of watching my git tree and pointing out problems;
as it hit them, I added new test-cases to be sure not to be caught the
same way twice.

The following changes since commit 1b1bc42c1692e9b62756323c675a44cb1a1f9dbd:

  Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net (2017-01-27 12:54:16 -0800)

are available in the git repository at:

  git://git.infradead.org/users/willy/linux-dax.git idr-4.11

for you to fetch changes up to c6ce3e2fe3dacda5e8afb0036c814ae9c3fee9b9:

  radix tree test suite: Add config option for map shift (2017-02-13 21:44:10 -0500)

----------------------------------------------------------------
Matthew Wilcox (30):
      radix tree: Add some implicit includes
      radix tree: constify some pointers
      radix tree test suite: Remove duplicate bitops code
      tools: Provide a definition of WARN_ON
      radix tree test suite: Depend on tools/include/asm files
      radix tree test suite: Remove mempool
      radix tree test suite: Remove types.h
      radix tree test suite: Remove export.h
      radix tree test suite: Reduce kernel.h
      radix tree test suite: Use vpath to find lib files
      radix tree test suite: Remove obsolete CONFIG
      radix-tree: Add radix_tree_iter_tag_clear()
      radix-tree: Add radix_tree_iter_delete
      Reimplement IDR and IDA using the radix tree
      ida: Move ida_bitmap to a percpu variable
      ida: Use exceptional entries for small IDAs
      radix tree test suite: Build separate binaries for some tests
      idr: Return the deleted entry from idr_remove
      radix tree test suite: Introduce kmalloc_verbose
      radix-tree: Chain preallocated nodes through ->parent
      radix-tree: Store a pointer to the root in each node
      radix_tree_iter_resume: Fix out of bounds error
      radix tree test suite: Enable address sanitizer
      radix tree test suite: Fix leaky tests
      radix tree test suite: Fix leaks in regression2.c
      radix tree test suite: Fix split/join memory leaks
      radix tree test suite: Run iteration tests for longer
      radix-tree: Add rcu_dereference and rcu_assign_pointer calls
      radix-tree: Fix __rcu annotations
      idr: Add missing __rcu annotations

Rehas Sachdeva (2):
      radix tree test suite: Dial down verbosity with -v
      radix tree test suite: Add config option for map shift

 drivers/atm/nicstar.c                              |    5 +-
 drivers/block/drbd/drbd_main.c                     |    6 +-
 drivers/firewire/core-cdev.c                       |    3 +-
 drivers/gpu/drm/amd/amdgpu/amdgpu_bo_list.c        |    4 +-
 drivers/gpu/drm/amd/amdgpu/amdgpu_ctx.c            |   10 +-
 drivers/net/wireless/marvell/mwifiex/txrx.c        |    4 +-
 drivers/target/target_core_user.c                  |    4 +-
 include/linux/idr.h                                |  148 ++-
 include/linux/radix-tree.h                         |  179 +--
 init/main.c                                        |    3 +-
 lib/Makefile                                       |    3 +
 lib/idr.c                                          | 1242 +++++---------------
 lib/radix-tree.c                                   |  761 ++++++++----
 mm/workingset.c                                    |    6 +-
 net/mac80211/status.c                              |    4 +-
 tools/include/asm-generic/bitops/atomic.h          |    3 +
 tools/include/asm/bug.h                            |    8 +
 tools/include/linux/bitmap.h                       |    1 +
 tools/include/linux/bitops.h                       |    1 -
 tools/include/linux/compiler.h                     |    4 +
 tools/include/linux/spinlock.h                     |    5 +
 tools/testing/radix-tree/.gitignore                |    4 +
 tools/testing/radix-tree/Makefile                  |   46 +-
 tools/testing/radix-tree/benchmark.c               |    6 +-
 tools/testing/radix-tree/generated/autoconf.h      |    2 -
 tools/testing/radix-tree/idr-test.c                |  444 +++++++
 tools/testing/radix-tree/iteration_check.c         |    2 +-
 tools/testing/radix-tree/linux.c                   |   39 +-
 tools/testing/radix-tree/linux/bitops.h            |  160 ---
 tools/testing/radix-tree/linux/bitops/__ffs.h      |   43 -
 tools/testing/radix-tree/linux/bitops/ffs.h        |   41 -
 tools/testing/radix-tree/linux/bitops/ffz.h        |   12 -
 tools/testing/radix-tree/linux/bitops/find.h       |   13 -
 tools/testing/radix-tree/linux/bitops/fls.h        |   41 -
 tools/testing/radix-tree/linux/bitops/fls64.h      |   14 -
 tools/testing/radix-tree/linux/bitops/hweight.h    |   11 -
 tools/testing/radix-tree/linux/bitops/le.h         |   53 -
 tools/testing/radix-tree/linux/bitops/non-atomic.h |  110 --
 tools/testing/radix-tree/linux/export.h            |    2 -
 tools/testing/radix-tree/linux/gfp.h               |   10 +-
 tools/testing/radix-tree/linux/idr.h               |    1 +
 tools/testing/radix-tree/linux/init.h              |    2 +-
 tools/testing/radix-tree/linux/kernel.h            |   55 +-
 tools/testing/radix-tree/linux/mempool.h           |   16 -
 tools/testing/radix-tree/linux/percpu.h            |    5 +-
 tools/testing/radix-tree/linux/preempt.h           |   10 +
 tools/testing/radix-tree/linux/radix-tree.h        |   25 +
 tools/testing/radix-tree/linux/types.h             |   23 -
 tools/testing/radix-tree/main.c                    |   53 +-
 tools/testing/radix-tree/multiorder.c              |   39 +-
 tools/testing/radix-tree/regression1.c             |    4 +-
 tools/testing/radix-tree/regression2.c             |   10 +-
 tools/testing/radix-tree/regression3.c             |   28 +-
 tools/testing/radix-tree/tag_check.c               |   22 +-
 tools/testing/radix-tree/test.c                    |   28 +-
 tools/testing/radix-tree/test.h                    |    2 +
 56 files changed, 1703 insertions(+), 2077 deletions(-)
 create mode 100644 tools/include/linux/spinlock.h
 create mode 100644 tools/testing/radix-tree/idr-test.c
 delete mode 100644 tools/testing/radix-tree/linux/bitops.h
 delete mode 100644 tools/testing/radix-tree/linux/bitops/__ffs.h
 delete mode 100644 tools/testing/radix-tree/linux/bitops/ffs.h
 delete mode 100644 tools/testing/radix-tree/linux/bitops/ffz.h
 delete mode 100644 tools/testing/radix-tree/linux/bitops/find.h
 delete mode 100644 tools/testing/radix-tree/linux/bitops/fls.h
 delete mode 100644 tools/testing/radix-tree/linux/bitops/fls64.h
 delete mode 100644 tools/testing/radix-tree/linux/bitops/hweight.h
 delete mode 100644 tools/testing/radix-tree/linux/bitops/le.h
 delete mode 100644 tools/testing/radix-tree/linux/bitops/non-atomic.h
 delete mode 100644 tools/testing/radix-tree/linux/export.h
 create mode 100644 tools/testing/radix-tree/linux/idr.h
 delete mode 100644 tools/testing/radix-tree/linux/mempool.h
 delete mode 100644 tools/testing/radix-tree/linux/types.h

^ permalink raw reply	[flat|nested] 3+ messages in thread
* Re: Please pull IDR rewrite
  2017-02-28 21:11 Please pull IDR rewrite Matthew Wilcox
@ 2017-02-28 23:38 ` Linus Torvalds
  2017-03-01  0:06   ` Matthew Wilcox
  0 siblings, 1 reply; 3+ messages in thread
From: Linus Torvalds @ 2017-02-28 23:38 UTC (permalink / raw)
  To: Matthew Wilcox; +Cc: Linux Kernel Mailing List

On Tue, Feb 28, 2017 at 1:11 PM, Matthew Wilcox <willy@infradead.org> wrote:
>
> The most significant part of the following is the patch to rewrite the
> IDR & IDA to be clients of the radix tree.

Could you give a bit more details about what this rewrite brings with
it, for the merge message and peoples edification?

              Linus

^ permalink raw reply	[flat|nested] 3+ messages in thread
* Re: Please pull IDR rewrite
  2017-02-28 23:38 ` Linus Torvalds
@ 2017-03-01  0:06   ` Matthew Wilcox
  0 siblings, 0 replies; 3+ messages in thread
From: Matthew Wilcox @ 2017-03-01  0:06 UTC (permalink / raw)
  To: Linus Torvalds; +Cc: Linux Kernel Mailing List

On Tue, Feb 28, 2017 at 03:38:09PM -0800, Linus Torvalds wrote:
> On Tue, Feb 28, 2017 at 1:11 PM, Matthew Wilcox <willy@infradead.org> wrote:
> >
> > The most significant part of the following is the patch to rewrite the
> > IDR & IDA to be clients of the radix tree.
> 
> Could you give a bit more details about what this rewrite brings with
> it, for the merge message and peoples edification?

Certainly!

The radix tree and the IDR use very similar data structures.  Merging the
two codebases lets us share the memory allocation pools, and results in
a net deletion of 500 lines of code.  It also opens up the possibility
of exposing more of the features of the radix tree to users of the IDR
(and I have some interesting patches along those lines waiting for 4.12).
It also shrinks the size of the 'struct idr' from 40 bytes to 24 which
will shrink a fair few data structures that embed an IDR.

 include/linux/idr.h        |  145 +++---
 include/linux/radix-tree.h |   49 +-
 lib/idr.c                  | 1175 +++++++++-----------------------------------
 lib/radix-tree.c           |  375 ++++++++++----
 4 files changed, 627 insertions(+), 1117 deletions(-)

^ permalink raw reply	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2017-03-01  2:20 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-02-28 21:11 Please pull IDR rewrite Matthew Wilcox
2017-02-28 23:38 ` Linus Torvalds
2017-03-01  0:06   ` Matthew Wilcox

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.