Radix tree multiorder fixes
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v2 Latest29 patches 1 replyIn review
- v130 patches 0 repliesSuperseded
Changes in v2 from the cover letter
- Rename get_sibling_offset() to get_slot_offset()
- Use get_slot_offset() in radix_tree_insert() instead of doing arithmetic
- Use get_slot_offset() in radix_tree_descend()
- Some whitespace fixes
- Fix race in radix_tree_next_chunk() against a multiorder insertion
- Reduce the nuber of ifdefs by introducing iter_shift()
- Fix some minor bugs in radix_tree_dump()
- Merge the commit to fix shrinking bugs with the commit to add a test case for the shrinking code
- Fix a bug in radix_tree_range_tag_if_tagged() if the first index was an alias of a multiorder entry
- Add more test-cases to the test suite
- Make __radix_tree_lookup fit the same pattern as the other tree walkers
Patches in v2 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/29 | radix-tree: Introduce radix_tree_emptyinclude/ kernel/ | +6 | 1 reply | |
| 2/29 | radix tree test suite: Fix buildtools/ tools/ tools/ +1 more | +12 | 0 replies | |
| 3/29 | radix tree test suite: Add tests for radix_tree_locate_item()tools/ tools/ | +44 | 0 replies | |
| 4/29 | radix tree test suite: Allow testing other fan-out valuesinclude/ tools/ tools/ | +3 | 0 replies | |
| 5/29 | radix tree test suite: keep regression test runs shorttools/ | +15 | 0 replies | |
| 6/29 | radix tree test suite: rebuild when headers changetools/ | +1 | 0 replies | |
| 7/29 | radix-tree: remove unused looping macrosinclude/ | +0 | 0 replies | |
| 8/29 | Introduce CONFIG_RADIX_TREE_MULTIORDERlib/ lib/ mm/ +1 more | +23 | 0 replies | |
| 9/29 | radix-tree: Add missing sibling entry functionalitylib/ | +40 | 0 replies | |
| 10/29 | radix-tree: Fix sibling entry insertionlib/ | +2 | 0 replies | |
| 11/29 | radix-tree: Fix deleting a multi-order entry through an aliaslib/ | +1 | 0 replies | |
| 12/29 | radix-tree: Remove restriction on multi-order entrieslib/ | +0 | 0 replies | |
| 13/29 | radix-tree: Introduce radix_tree_load_root()lib/ | +23 | 0 replies | |
| 14/29 | radix-tree: Fix extending the tree for multi-order entries at offset 0lib/ | +17 | 0 replies | |
| 15/29 | radix tree test suite: Start adding multiorder teststools/ tools/ tools/ +2 more | +76 | 0 replies | |
| 16/29 | radix-tree: Fix several shrinking bugs with multiorder entrieslib/ tools/ | +51 | 0 replies | |
| 17/29 | radix-tree: Rewrite __radix_tree_lookuplib/ | +16 | 0 replies | |
| 18/29 | radix-tree: Fix multiorder BUG_ON in radix_tree_insertlib/ tools/ | +22 | 0 replies | |
| 19/29 | radix-tree: add support for multi-order iteratinginclude/ lib/ tools/ +1 more | +102 | 0 replies | |
| 20/29 | radix tree test suite: multi-order iteration testtools/ | +92 | 0 replies | |
| 21/29 | radix-tree: Rewrite radix_tree_tag_setlib/ | +17 | 0 replies | |
| 22/29 | radix-tree: Rewrite radix_tree_tag_clearlib/ | +20 | 0 replies | |
| 23/29 | radix-tree: Rewrite radix_tree_tag_getlib/ | +18 | 0 replies | |
| 24/29 | radix-tree test suite: add multi-order tag testtools/ | +97 | 0 replies | |
| 25/29 | radix-tree: Fix radix_tree_create for sibling entrieslib/ tools/ | +7 | 0 replies | |
| 26/29 | radix-tree: Rewrite radix_tree_locate_itemlib/ tools/ | +63 | 0 replies | |
| 27/29 | radix-tree: Fix radix_tree_range_tag_if_tagged() for multiorder entrieslib/ tools/ tools/ | +67 | 0 replies | |
| 28/29 | radix-tree: Fix radix_tree_dump() for multi-order entrieslib/ tools/ | +30 | 0 replies | |
| 29/29 | radix-tree: Add copyright statementslib/ | +2 | 0 replies |
Reviews trailers per patch
18 of 29 patches have a Reviewed-by or Acked-by.
| Patch | Ross Zwisler | Jan Kara |
|---|---|---|
| 1/29 | R-b | R-b |
| 2/29 | R-b | |
| 3/29 | R-b | |
| 4/29 | ||
| 5/29 | ||
| 6/29 | ||
| 7/29 | ||
| 8/29 | R-b | |
| 9/29 | R-b | |
| 10/29 | R-b | |
| 11/29 | R-b | |
| 12/29 | R-b | |
| 13/29 | R-b | |
| 14/29 | R-b | |
| 15/29 | R-b | |
| 16/29 | R-b | |
| 17/29 | R-b | |
| 18/29 | R-b | |
| 19/29 | ||
| 20/29 | ||
| 21/29 | ||
| 22/29 | ||
| 23/29 | ||
| 24/29 | ||
| 25/29 | R-b | |
| 26/29 | R-b | |
| 27/29 | R-b | |
| 28/29 | ||
| 29/29 | R-b |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.
Cover letter [PATCH v2 00/29] Radix tree multiorder fixes
I must apologise for commit f96d18ff84 which left the impression that the support for multiorder radix tree entries was functional. As soon as Ross tried to use it, it became apparent that my testing was completely inadequate, and it didn't even work a little bit for orders that were not a multiple of shift.
This series of patches is the result of about 6 weeks of redesign, reimplementation, testing, arguing and hair-pulling. The great news is that the test-suite is now far better than it was. That's reflected in the diffstat for the test-suite alone:
12 files changed, 436 insertions(+), 28 deletions(-)
The highlight for users of the tree is that the restriction on the order of inserted entries being >= RADIX_TREE_MAP_SHIFT is now gone; the radix tree now supports any order between 0 and 64.
For those who are interested in how the tree works, patch 9 is probably the most interesting one as it introduces the new machinery for handling sibling entries.
I've tried to be fair in attributing authorship to the person who contributed the majority of the code in each patch; Ross has been an invaluable partner in the development of this support and it's fair to say that each of us has code in every commit.
I should also express my appreciation of the 0day testing. It prompted me that I was bloating the tinyconfig in an unacceptable way, and it bisected to a commit which contained a rather nasty memory-corruption bug.
Changes since v1:
- Rename get_sibling_offset() to get_slot_offset()
- Use get_slot_offset() in radix_tree_insert() instead of doing arithmetic
- Use get_slot_offset() in radix_tree_descend()
- Some whitespace fixes
- Fix race in radix_tree_next_chunk() against a multiorder insertion
- Reduce the nuber of ifdefs by introducing iter_shift()
- Fix some minor bugs in radix_tree_dump()
- Merge the commit to fix shrinking bugs with the commit to add a test case for the shrinking code
- Fix a bug in radix_tree_range_tag_if_tagged() if the first index was an alias of a multiorder entry
- Add more test-cases to the test suite
- Make __radix_tree_lookup fit the same pattern as the other tree walkers
Matthew Wilcox (18):
radix-tree: Introduce radix_tree_empty
radix tree test suite: Fix build
radix tree test suite: Add tests for radix_tree_locate_item() Introduce CONFIG_RADIX_TREE_MULTIORDER
radix-tree: Add missing sibling entry functionality
radix-tree: Fix sibling entry insertion
radix-tree: Fix deleting a multi-order entry through an alias
radix-tree: Remove restriction on multi-order entries
radix-tree: Introduce radix_tree_load_root()
radix-tree: Fix extending the tree for multi-order entries at offset 0 radix tree test suite: Start adding multiorder tests
radix-tree: Fix several shrinking bugs with multiorder entries
radix-tree: Rewrite __radix_tree_lookup
radix-tree: Fix multiorder BUG_ON in radix_tree_insert
radix-tree: Fix radix_tree_create for sibling entries
radix-tree: Rewrite radix_tree_locate_item
radix-tree: Fix radix_tree_range_tag_if_tagged() for multiorder
entries
radix-tree: Add copyright statements
Ross Zwisler (11):
radix tree test suite: Allow testing other fan-out values radix tree test suite: keep regression test runs short radix tree test suite: rebuild when headers change
radix-tree: remove unused looping macros
radix-tree: add support for multi-order iterating radix tree test suite: multi-order iteration test
radix-tree: Rewrite radix_tree_tag_set
radix-tree: Rewrite radix_tree_tag_clear
radix-tree: Rewrite radix_tree_tag_get radix-tree test suite: add multi-order tag test
radix-tree: Fix radix_tree_dump() for multi-order entries
include/linux/radix-tree.h | 106 +++-- kernel/irq/irqdomain.c | 7 +- lib/Kconfig | 3 + lib/radix-tree.c | 611 ++++++++++++++------------ mm/Kconfig | 1 + tools/testing/radix-tree/Makefile | 4 +- tools/testing/radix-tree/generated/autoconf.h | 3 + tools/testing/radix-tree/linux/init.h | 0 tools/testing/radix-tree/linux/kernel.h | 15 +- tools/testing/radix-tree/linux/slab.h | 1 - tools/testing/radix-tree/linux/types.h | 7 +- tools/testing/radix-tree/main.c | 71 ++- tools/testing/radix-tree/multiorder.c | 326 ++++++++++++++ tools/testing/radix-tree/regression2.c | 7 - tools/testing/radix-tree/tag_check.c | 10 + tools/testing/radix-tree/test.c | 13 +- tools/testing/radix-tree/test.h | 7 +- 17 files changed, 845 insertions(+), 347 deletions(-) create mode 100644 tools/testing/radix-tree/generated/autoconf.h create mode 100644 tools/testing/radix-tree/linux/init.h create mode 100644 tools/testing/radix-tree/multiorder.c
Signature · 7 lines
2.8.0.rc3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>