[PATCH 00/19] Radix tree cleanups

From	Matthew Wilcox <willy@linux.intel.com>
Newsgroups	linux.kernel
Subject	[PATCH 00/19] Radix tree cleanups
Date	2016-04-14 16:40 +0200
Message-ID	<rnQB5-33W-35@gated-at.bofh.it> (permalink)
Organization	linux.* mail to news gateway

Show all headers | View raw

This patch series applies on top of the radix-fixes series I sent
recently.

It aims to improve the radix tree by making the code more understandable
and has the nice side-effect of shrinking the code size on i386-tinyconfig
by about 250 bytes.  The 'height' concept is entirely gone from the code
by patch 7 of the series.  We eliminate most of the tricky arithmetic
on index.  This paves the way towards allowing different shift amounts
at different layers of the tree, something I know various people are
interested in.

It integrates two of the patches from Neil Brown which are pre-requisites
for locking exceptional entries.

We end up deleting almost a hundred lines of code from the kernel
(excluding the test-suite).

Matthew Wilcox (18):
  drivers/hwspinlock: Use correct radix tree API
  radix-tree: Miscellaneous fixes
  radix-tree: Split node->path into offset and height
  radix-tree: Replace node->height with node->shift
  radix-tree: Remove a use of root->height from delete_node
  radix tree test suite: Remove dependencies on height
  radix-tree: Remove root->height
  radix-tree: Rename INDIRECT_PTR to INTERNAL_NODE
  radix-tree: Rename ptr_to_indirect() to node_to_entry()
  radix-tree: Rename indirect_to_ptr() to entry_to_node()
  radix-tree: Rename radix_tree_is_indirect_ptr()
  radix-tree: Change naming conventions in radix_tree_shrink
  radix-tree: Tidy up next_chunk
  radix-tree: Tidy up range_tag_if_tagged
  radix-tree: Tidy up __radix_tree_create()
  radix-tree: Introduce radix_tree_replace_clear_tags()
  radix-tree: Make radix_tree_descend() more useful
  radix-tree: Free up the bottom bit of exceptional entries for reuse

NeilBrown (1):
  dax: move RADIX_DAX_ definitions to dax.c

 drivers/hwspinlock/hwspinlock_core.c  |   2 +-
 fs/dax.c                              |   9 +
 include/linux/radix-tree.h            |  94 +++---
 lib/radix-tree.c                      | 577 +++++++++++++++-------------------
 mm/filemap.c                          |  23 +-
 tools/testing/radix-tree/multiorder.c |  99 +++---
 tools/testing/radix-tree/test.c       |  36 ++-
 tools/testing/radix-tree/test.h       |   4 +-
 8 files changed, 385 insertions(+), 459 deletions(-)

-- 
2.8.0.rc3

Back to linux.kernel | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

[PATCH 00/19] Radix tree cleanups Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:40 +0200
  [PATCH 12/19] radix-tree: Change naming conventions in radix_tree_shrink Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:40 +0200
  [PATCH 16/19] radix-tree: Introduce radix_tree_replace_clear_tags() Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:40 +0200
  [PATCH 17/19] radix-tree: Make radix_tree_descend() more useful Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:40 +0200
  [PATCH 01/19] drivers/hwspinlock: Use correct radix tree API Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:40 +0200
  [PATCH 05/19] radix-tree: Remove a use of root->height from delete_node Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:40 +0200
  [PATCH 18/19] dax: move RADIX_DAX_ definitions to dax.c Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:40 +0200
  [PATCH 11/19] radix-tree: Rename radix_tree_is_indirect_ptr() Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 06/19] radix tree test suite: Remove dependencies on height Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 02/19] radix-tree: Miscellaneous fixes Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 04/19] radix-tree: Replace node->height with node->shift Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 10/19] radix-tree: Rename indirect_to_ptr() to entry_to_node() Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 13/19] radix-tree: Tidy up next_chunk Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 14/19] radix-tree: Tidy up range_tag_if_tagged Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 15/19] radix-tree: Tidy up __radix_tree_create() Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 08/19] radix-tree: Rename INDIRECT_PTR to INTERNAL_NODE Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 03/19] radix-tree: Split node->path into offset and height Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200
  [PATCH 09/19] radix-tree: Rename ptr_to_indirect() to node_to_entry() Matthew Wilcox <willy@linux.intel.com> - 2016-04-14 16:50 +0200

csiph-web