Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1312293 > unrolled thread
| Started by | Matthew Wilcox <matthew.r.wilcox@intel.com> |
|---|---|
| First post | 2016-01-19 15:30 +0100 |
| Last post | 2016-01-27 04:30 +0100 |
| Articles | 4 — 3 participants |
Back to article view | Back to linux.kernel
[PATCH 0/8] Support multi-order entries in the radix tree Matthew Wilcox <matthew.r.wilcox@intel.com> - 2016-01-19 15:30 +0100
Re: [PATCH 0/8] Support multi-order entries in the radix tree Andrew Morton <akpm@linux-foundation.org> - 2016-01-22 01:30 +0100
Re: [PATCH 2/8] radix tree test harness Andrew Morton <akpm@linux-foundation.org> - 2016-01-27 00:50 +0100
Re: [PATCH 2/8] radix tree test harness Matthew Wilcox <willy@linux.intel.com> - 2016-01-27 04:30 +0100
| From | Matthew Wilcox <matthew.r.wilcox@intel.com> |
|---|---|
| Date | 2016-01-19 15:30 +0100 |
| Subject | [PATCH 0/8] Support multi-order entries in the radix tree |
| Message-ID | <qSFse-Eb-9@gated-at.bofh.it> |
From: Matthew Wilcox <willy@linux.intel.com> In order to support huge pages in the page cache, Kirill has proposed simply creating 512 entries. I think this runs into problems with fsync() tracking dirty bits in the radix tree. Ross inserts a special entry to represent the PMD at the index for the start of the PMD, but this requires probing the tree twice; once for the PTE and once for the PMD. When we add PUD entries, that will become three times. The approach in this patch set is to modify the radix tree to support multi-order entries. Pointers to internal radix tree nodes mostly do not have the 'indirect' bit set. I change that so they always have that bit set; then any pointer without the indirect bit set is a multi-order entry. If the order of the entry is a multiple of the fanout of the tree, then all is well. If not, it is necessary to insert alias nodes into the tree that point to the canonical entry. At this point, I have not added support for entries which are smaller than the last-level fanout of the tree (and I put a BUG_ON in to prevent that usage). Adding support would be a simple matter of one last pointer-chase when we get to the bottom of the tree, but I am not aware of any reason to add support for smaller multi-order entries at this point, so I haven't. Note that no actual users are modified at this point. I think it'd be mostly a matter of deleting code from the DAX fsync support at this point, but with that code in flux, I'm a little reluctant to add more churn to it. I'm also not entriely sure where Kirill is on the page-cache modifications; he seems to have his hands full fixing up the MM right now. Before diving into the important modifications, I add Andrew Morton's radix tree test harness to the tree in patches 1 & 2. It was absolutely invaluable in catching some of my bugs. Patches 3 & 4 are minor tweaks. Patches 5-7 are the interesting ones. Patch 8 we might want to leave out entirely or shift over to the test harness. I found it useful during debugging and others might too. Matthew Wilcox (8): radix-tree: Add an explicit include of bitops.h radix tree test harness radix-tree: Cleanups radix_tree: Convert some variables to unsigned types radix_tree: Tag all internal tree nodes as indirect pointers radix_tree: Loop based on shift count, not height radix_tree: Add support for multi-order entries radix_tree: Add radix_tree_dump include/linux/radix-tree.h | 12 +- lib/radix-tree.c | 231 ++++++++++---- mm/filemap.c | 2 +- tools/testing/radix-tree/.gitignore | 2 + tools/testing/radix-tree/Makefile | 20 ++ tools/testing/radix-tree/find_next_bit.c | 57 ++++ tools/testing/radix-tree/linux.c | 60 ++++ tools/testing/radix-tree/linux/bitops.h | 150 ++++++++++ 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 | 111 +++++++ tools/testing/radix-tree/linux/bug.h | 1 + tools/testing/radix-tree/linux/cpu.h | 35 +++ tools/testing/radix-tree/linux/export.h | 2 + tools/testing/radix-tree/linux/gfp.h | 8 + tools/testing/radix-tree/linux/init.h | 0 tools/testing/radix-tree/linux/kernel.h | 34 +++ tools/testing/radix-tree/linux/kmemleak.h | 1 + tools/testing/radix-tree/linux/mempool.h | 17 ++ tools/testing/radix-tree/linux/notifier.h | 8 + tools/testing/radix-tree/linux/percpu.h | 7 + tools/testing/radix-tree/linux/preempt.h | 5 + tools/testing/radix-tree/linux/radix-tree.h | 1 + tools/testing/radix-tree/linux/rcupdate.h | 9 + tools/testing/radix-tree/linux/slab.h | 28 ++ tools/testing/radix-tree/linux/string.h | 0 tools/testing/radix-tree/linux/types.h | 28 ++ tools/testing/radix-tree/main.c | 271 +++++++++++++++++ tools/testing/radix-tree/rcupdate.c | 86 ++++++ tools/testing/radix-tree/regression.h | 7 + tools/testing/radix-tree/regression1.c | 221 ++++++++++++++ tools/testing/radix-tree/regression2.c | 126 ++++++++ tools/testing/radix-tree/tag_check.c | 332 +++++++++++++++++++++ tools/testing/radix-tree/test.c | 219 ++++++++++++++ tools/testing/radix-tree/test.h | 40 +++ 41 files changed, 2294 insertions(+), 65 deletions(-) create mode 100644 tools/testing/radix-tree/.gitignore create mode 100644 tools/testing/radix-tree/Makefile create mode 100644 tools/testing/radix-tree/find_next_bit.c create mode 100644 tools/testing/radix-tree/linux.c create mode 100644 tools/testing/radix-tree/linux/bitops.h create mode 100644 tools/testing/radix-tree/linux/bitops/__ffs.h create mode 100644 tools/testing/radix-tree/linux/bitops/ffs.h create mode 100644 tools/testing/radix-tree/linux/bitops/ffz.h create mode 100644 tools/testing/radix-tree/linux/bitops/find.h create mode 100644 tools/testing/radix-tree/linux/bitops/fls.h create mode 100644 tools/testing/radix-tree/linux/bitops/fls64.h create mode 100644 tools/testing/radix-tree/linux/bitops/hweight.h create mode 100644 tools/testing/radix-tree/linux/bitops/le.h create mode 100644 tools/testing/radix-tree/linux/bitops/non-atomic.h create mode 100644 tools/testing/radix-tree/linux/bug.h create mode 100644 tools/testing/radix-tree/linux/cpu.h create mode 100644 tools/testing/radix-tree/linux/export.h create mode 100644 tools/testing/radix-tree/linux/gfp.h create mode 100644 tools/testing/radix-tree/linux/init.h create mode 100644 tools/testing/radix-tree/linux/kernel.h create mode 100644 tools/testing/radix-tree/linux/kmemleak.h create mode 100644 tools/testing/radix-tree/linux/mempool.h create mode 100644 tools/testing/radix-tree/linux/notifier.h create mode 100644 tools/testing/radix-tree/linux/percpu.h create mode 100644 tools/testing/radix-tree/linux/preempt.h create mode 120000 tools/testing/radix-tree/linux/radix-tree.h create mode 100644 tools/testing/radix-tree/linux/rcupdate.h create mode 100644 tools/testing/radix-tree/linux/slab.h create mode 100644 tools/testing/radix-tree/linux/string.h create mode 100644 tools/testing/radix-tree/linux/types.h create mode 100644 tools/testing/radix-tree/main.c create mode 100644 tools/testing/radix-tree/rcupdate.c create mode 100644 tools/testing/radix-tree/regression.h create mode 100644 tools/testing/radix-tree/regression1.c create mode 100644 tools/testing/radix-tree/regression2.c create mode 100644 tools/testing/radix-tree/tag_check.c create mode 100644 tools/testing/radix-tree/test.c create mode 100644 tools/testing/radix-tree/test.h -- 2.7.0.rc3
[toc] | [next] | [standalone]
| From | Andrew Morton <akpm@linux-foundation.org> |
|---|---|
| Date | 2016-01-22 01:30 +0100 |
| Message-ID | <qTxLY-4qP-15@gated-at.bofh.it> |
| In reply to | #1312293 |
On Tue, 19 Jan 2016 09:25:25 -0500 Matthew Wilcox <matthew.r.wilcox@intel.com> wrote: > Before diving into the important modifications, I add Andrew Morton's > radix tree test harness to the tree in patches 1 & 2. It was absolutely > invaluable in catching some of my bugs. (cc Shuah for tools/testing/selftests) Cool, thanks for doing that. I think a lot of this came from Nick Piggin a long time ago, but I was bad about attributing it. I wonder how good the coverage is - I don't think it's been seriously updated since 2010 and presumably it isn't hitting on later-added features. Doesn't matter - someone will add things later if needed. And when I bug them to update the test harness ;) I don't think it will link on my system - I have no liburcu by default. I wonder if this will break lots of people's "make kselftest". I'll get all this into -next tomorrow. Hopefully Ross will have time to go through it sometime (non-urgently - it's 4.6 stuff).
[toc] | [prev] | [next] | [standalone]
| From | Andrew Morton <akpm@linux-foundation.org> |
|---|---|
| Date | 2016-01-27 00:50 +0100 |
| Subject | Re: [PATCH 2/8] radix tree test harness |
| Message-ID | <qVlwZ-3bN-5@gated-at.bofh.it> |
| In reply to | #1312293 |
On Tue, 19 Jan 2016 09:25:27 -0500 Matthew Wilcox <matthew.r.wilcox@intel.com> wrote: > From: Matthew Wilcox <willy@linux.intel.com> > > This code is mostly from Andrew Morton; tarball downloaded > from http://ozlabs.org/~akpm/rtth.tar.gz with sha1sum > 0ce679db9ec047296b5d1ff7a1dfaa03a7bef1bd > > Some small modifications were necessary to the test harness to fix the > build with the current Linux source code. > > I also made minor modifications to automatically test the radix-tree.c > and radix-tree.h files that are in the current source tree, as opposed > to a copied and slightly modified version. I am sure more could be > done to tidy up the harness, as well as adding more tests. > > ... > > diff --git a/tools/testing/radix-tree/linux/radix-tree.h b/tools/testing/radix-tree/linux/radix-tree.h > new file mode 120000 > index 0000000..1e6f41f > --- /dev/null > +++ b/tools/testing/radix-tree/linux/radix-tree.h > @@ -0,0 +1 @@ > +../../../../include/linux/radix-tree.h > \ No newline at end of file glumpf. My tools have always had trouble with symlinks - patch(1) seems to handle them OK but diff(1) screws things up. I've had one go at using git to replace patch/diff but it was a fail. Am presently too lazy to have attempt #2 so I think I'll just do --- /dev/null +++ a/tools/testing/radix-tree/linux/radix-tree.h @@ -0,0 +1 @@ +#include "../../../../include/linux/radix-tree.h"
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <willy@linux.intel.com> |
|---|---|
| Date | 2016-01-27 04:30 +0100 |
| Subject | Re: [PATCH 2/8] radix tree test harness |
| Message-ID | <qVoXU-5Jw-7@gated-at.bofh.it> |
| In reply to | #1318479 |
On Tue, Jan 26, 2016 at 03:44:38PM -0800, Andrew Morton wrote: > > diff --git a/tools/testing/radix-tree/linux/radix-tree.h b/tools/testing/radix-tree/linux/radix-tree.h > > new file mode 120000 > > index 0000000..1e6f41f > > --- /dev/null > > +++ b/tools/testing/radix-tree/linux/radix-tree.h > > @@ -0,0 +1 @@ > > +../../../../include/linux/radix-tree.h > > \ No newline at end of file > > glumpf. My tools have always had trouble with symlinks - patch(1) > seems to handle them OK but diff(1) screws things up. I've had one go > at using git to replace patch/diff but it was a fail. > > Am presently too lazy to have attempt #2 so I think I'll just do > > --- /dev/null > +++ a/tools/testing/radix-tree/linux/radix-tree.h > @@ -0,0 +1 @@ > +#include "../../../../include/linux/radix-tree.h" Fine by me; I wasn't sure whether to do it as an include or a symlink. I could have gone either way.
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web