Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1489100 > unrolled thread

[PATCH 0/2] Fix radix_tree_lookup_slot()

Back to article view | Back to linux.kernel

Contents

  [PATCH 0/2] Fix radix_tree_lookup_slot() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-09-22 19:10 +0200
    [PATCH 2/2] radix-tree: Fix optimisation problem Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-09-22 19:10 +0200
      Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-22 20:20 +0200
        RE: [PATCH 2/2] radix-tree: Fix optimisation problem Matthew Wilcox <mawilcox@microsoft.com> - 2016-09-23 22:20 +0200
          Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-24 22:30 +0200
            Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-24 22:50 +0200
            Re: [PATCH 2/2] radix-tree: Fix optimisation problem "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com> - 2016-09-24 23:10 +0200
              Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 01:00 +0200
      Re: [PATCH 2/2] radix-tree: Fix optimisation problem Konstantin Khlebnikov <koct9i@gmail.com> - 2016-09-24 10:40 +0200
      Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-25 01:40 +0200
        Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 02:20 +0200
          Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-25 20:00 +0200
            Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 21:10 +0200
              Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-25 21:50 +0200
              Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 22:00 +0200
                RE: [PATCH 2/2] radix-tree: Fix optimisation problem Matthew Wilcox <mawilcox@microsoft.com> - 2016-09-26 23:30 +0200
                  Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-26 23:50 +0200
    [PATCH 1/2] radix tree test suite: Test radix_tree_replace_slot() for multiorder entries Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-09-22 19:10 +0200

#1489100 — [PATCH 0/2] Fix radix_tree_lookup_slot()

From: Matthew Wilcox <mawilcox@microsoft.com>

Hi Linus,

Please apply for 4.8.  The same bug is also present in 4.7, but is
probably latent.

Matthew Wilcox (2):
  radix tree test suite: Test radix_tree_replace_slot() for multiorder
    entries
  radix-tree: Fix optimisation problem

 lib/radix-tree.c                      |  3 ++-
 tools/testing/radix-tree/Makefile     |  2 +-
 tools/testing/radix-tree/multiorder.c | 16 ++++++++++++----
 3 files changed, 15 insertions(+), 6 deletions(-)

-- 
2.9.3

[toc] | [next] | [standalone]

#1489101 — [PATCH 2/2] radix-tree: Fix optimisation problem

From: Matthew Wilcox <mawilcox@microsoft.com>

When compiling the radix tree with -O2, GCC thinks it can optimise:

	void *entry = parent->slots[offset];
	int siboff = entry - parent->slots;
	void *slot = parent->slots + siboff;

into

	void *slot = entry;

Unfortunately, 'entry' is a tagged pointer, so this optimisation leads
to getting an unaligned pointer back from radix_tree_lookup_slot().
The test suite wasn't being compiled with optimisation, so we hadn't
spotted it before now.  Change the test suite to compile with -O2, and
fix the optimisation problem by passing 'entry' through entry_to_node()
so gcc knows this isn't a plain pointer.
---
 lib/radix-tree.c                  | 3 ++-
 tools/testing/radix-tree/Makefile | 2 +-
 2 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1b7bf73..8bf1f32 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -105,7 +105,8 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent,
 
 #ifdef CONFIG_RADIX_TREE_MULTIORDER
 	if (radix_tree_is_internal_node(entry)) {
-		unsigned long siboff = get_slot_offset(parent, entry);
+		unsigned long siboff = get_slot_offset(parent,
+						(void **)entry_to_node(entry));
 		if (siboff < RADIX_TREE_MAP_SIZE) {
 			offset = siboff;
 			entry = rcu_dereference_raw(parent->slots[offset]);
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 3b53046..9d0919ed 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -1,5 +1,5 @@
 
-CFLAGS += -I. -g -Wall -D_LGPL_SOURCE
+CFLAGS += -I. -g -O2 -Wall -D_LGPL_SOURCE
 LDFLAGS += -lpthread -lurcu
 TARGETS = main
 OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \
-- 
2.9.3

[toc] | [prev] | [next] | [standalone]

#1489279 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

On Thu, Sep 22, 2016 at 11:53 AM, Matthew Wilcox
<mawilcox@linuxonhyperv.com> wrote:
>
>           Change the test suite to compile with -O2, and
> fix the optimisation problem by passing 'entry' through entry_to_node()
> so gcc knows this isn't a plain pointer.

Ugh. I really don't like this patch very much.

Wouldn't it be cleaner to just fix "get_slot_offset()" instead? As it
is, looking at the code, I suspect that it's really hard to convince
people that there isn't some other place this might happen. Because
the "pointer subtraction followed by pointer addition" pattern is all
hidden in these inline functions.

Or at least add a big comment about why this is the only such case.

Because without that, the code now looks very bad.

                   Linus

[toc] | [prev] | [next] | [standalone]

#1490433 — RE: [PATCH 2/2] radix-tree: Fix optimisation problem

[Multipart message — attachments visible in raw view] — view raw

From: linus971@gmail.com [mailto:linus971@gmail.com] On Behalf Of Linus Torvalds
> On Thu, Sep 22, 2016 at 11:53 AM, Matthew Wilcox
> <mawilcox@linuxonhyperv.com> wrote:
> >
> >           Change the test suite to compile with -O2, and
> > fix the optimisation problem by passing 'entry' through entry_to_node()
> > so gcc knows this isn't a plain pointer.
> 
> Ugh. I really don't like this patch very much.
> 
> Wouldn't it be cleaner to just fix "get_slot_offset()" instead? As it
> is, looking at the code, I suspect that it's really hard to convince
> people that there isn't some other place this might happen. Because
> the "pointer subtraction followed by pointer addition" pattern is all
> hidden in these inline functions.
> 
> Or at least add a big comment about why this is the only such case.
> 
> Because without that, the code now looks very bad.

That's fair.  I looked at all the other callers of get_slot_offset, and all the others are using a real slot pointer.  radix_tree_descend() really is the outlier here.  I think the real problem is that the types in the tree are wrong; instead of storing void *, we should be storing uintptr_t.  But fixing that is a little beyond the scope of -rc8.  Here's a slightly better version which asserts that the passed pointer really is a pointer.

(attached as well, I have no idea whether this patch will get mangled)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1b7bf73..368f641 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -91,9 +91,15 @@ static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
 }
 #endif
 
+/*
+ * The slot pointer must be a real pointer as GCC will optimise
+ * through inlined functions and may deduce that
+ * parent->slots + get_slot_offset(parent, slot) == slot
+ */
 static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
 						 void **slot)
 {
+	BUG_ON(radix_tree_exception(slot));
 	return slot - parent->slots;
 }
 
@@ -101,11 +107,12 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent,
 			struct radix_tree_node **nodep, unsigned long index)
 {
 	unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
-	void **entry = rcu_dereference_raw(parent->slots[offset]);
+	void *entry = rcu_dereference_raw(parent->slots[offset]);
 
 #ifdef CONFIG_RADIX_TREE_MULTIORDER
 	if (radix_tree_is_internal_node(entry)) {
-		unsigned long siboff = get_slot_offset(parent, entry);
+		unsigned long siboff = get_slot_offset(parent,
+						(void **)entry_to_node(entry));
 		if (siboff < RADIX_TREE_MAP_SIZE) {
 			offset = siboff;
 			entry = rcu_dereference_raw(parent->slots[offset]);
@@ -113,7 +120,7 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent,
 	}
 #endif
 
-	*nodep = (void *)entry;
+	*nodep = entry;
 	return offset;
 }
 
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 3b53046..9d0919ed 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -1,5 +1,5 @@
 
-CFLAGS += -I. -g -Wall -D_LGPL_SOURCE
+CFLAGS += -I. -g -O2 -Wall -D_LGPL_SOURCE
 LDFLAGS += -lpthread -lurcu
 TARGETS = main
 OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \

[toc] | [prev] | [next] | [standalone]

#1490745 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

On Fri, Sep 23, 2016 at 1:16 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
>
>  #ifdef CONFIG_RADIX_TREE_MULTIORDER
>         if (radix_tree_is_internal_node(entry)) {
> -               unsigned long siboff = get_slot_offset(parent, entry);
> +               unsigned long siboff = get_slot_offset(parent,
> +                                               (void **)entry_to_node(entry));

I feel that it is *this* part that I think needs a huge honking comment.

If you are going to make get_slot_offset() different, then you could
just rewrite get_slot_offset() to do

        unsigned long diff = (unsigned long) slot - (unsigned
long)parent->slots;
        return diff / sizeof(void *);

and add a comment to say "don't do this as a pointer diff, because
'slot' may not be an aligned pointer". No BUG_ON() necessary, because
it "just works".

At that point, gcc should just generate the right code, because it
doesn't see it as a pointer subtraction followed by a pointer
addition.

And yes, that crazy " (void **)entry_to_node(entry)" fixes it *too*,
but it needs a *comment*.

Why is that special, when all the other uses of get_slot_offset()
don't have that? *That* is what should be explained. Not some internal
detail.

That said, if this code isn't even used, as Konstantin says (THP
selects it - doesn't THP use it?), then the fix really should be to
just remove the odd code instead of adding to it.

Looking around for uses that set "order" to anything but zero, I
really don't see it. So maybe we should just do *that* trivial thing
instead, and remove CONFIG_RADIX_TREE_MULTIORDER, since it's appears
to be buggy and always has been.

                  Linus

[toc] | [prev] | [next] | [standalone]

#1490751 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

[Multipart message — attachments visible in raw view] — view raw

On Sat, Sep 24, 2016 at 1:21 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> That said, if this code isn't even used, as Konstantin says (THP
> selects it - doesn't THP use it?), then the fix really should be to
> just remove the odd code instead of adding to it.
>
> Looking around for uses that set "order" to anything but zero, I
> really don't see it. So maybe we should just do *that* trivial thing
> instead, and remove CONFIG_RADIX_TREE_MULTIORDER, since it's appears
> to be buggy and always has been.

IOW, a patch something like this?

NOTE! This is entirely untested. Things still seem to compile with it,
at least with some configurations. That's all I can say.

I do like this part:

   11 files changed, 29 insertions(+), 518 deletions(-)

although admittedly 2/3rds of the deletions were for the multiorder
tests. But even if you ignore the test side, it's just fairly clean
removal of code that is apparently not used, and that was buggy.

               Linus

[toc] | [prev] | [next] | [standalone]

#1490752 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

On Sat, Sep 24, 2016 at 01:21:36PM -0700, Linus Torvalds wrote:
> On Fri, Sep 23, 2016 at 1:16 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> >
> >  #ifdef CONFIG_RADIX_TREE_MULTIORDER
> >         if (radix_tree_is_internal_node(entry)) {
> > -               unsigned long siboff = get_slot_offset(parent, entry);
> > +               unsigned long siboff = get_slot_offset(parent,
> > +                                               (void **)entry_to_node(entry));
> 
> I feel that it is *this* part that I think needs a huge honking comment.
> 
> If you are going to make get_slot_offset() different, then you could
> just rewrite get_slot_offset() to do
> 
>         unsigned long diff = (unsigned long) slot - (unsigned
> long)parent->slots;
>         return diff / sizeof(void *);
> 
> and add a comment to say "don't do this as a pointer diff, because
> 'slot' may not be an aligned pointer". No BUG_ON() necessary, because
> it "just works".
> 
> At that point, gcc should just generate the right code, because it
> doesn't see it as a pointer subtraction followed by a pointer
> addition.
> 
> And yes, that crazy " (void **)entry_to_node(entry)" fixes it *too*,
> but it needs a *comment*.
> 
> Why is that special, when all the other uses of get_slot_offset()
> don't have that? *That* is what should be explained. Not some internal
> detail.
> 
> That said, if this code isn't even used, as Konstantin says (THP
> selects it - doesn't THP use it?), then the fix really should be to
> just remove the odd code instead of adding to it.
> 
> Looking around for uses that set "order" to anything but zero, I
> really don't see it. So maybe we should just do *that* trivial thing
> instead, and remove CONFIG_RADIX_TREE_MULTIORDER, since it's appears
> to be buggy and always has been.

Well, my ext4-with-huge-pages patchset[1] uses multi-order entries.
It also converts shmem-with-huge-pages and hugetlb to them.

I'm okay with converting it to other mechanism, but I need something.
(I looked into Konstantin's RFC patchset[2]. It looks okay, but I don't
feel myself qualified to review it as I don't know much about radix-tree
internals.)

[1] http://lkml.kernel.org/r/20160915115523.29737-1-kirill.shutemov@linux.intel.com
[2] http://lkml.kernel.org/r/147230727479.9957.1087787722571077339.stgit@zurg

-- 
 Kirill A. Shutemov

[toc] | [prev] | [next] | [standalone]

#1490759 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

On Sat, Sep 24, 2016 at 2:04 PM, Kirill A. Shutemov
<kirill.shutemov@linux.intel.com> wrote:
>
> Well, my ext4-with-huge-pages patchset[1] uses multi-order entries.
> It also converts shmem-with-huge-pages and hugetlb to them.

Ok, so that code actually has a chance of being used. I guess we'll
not remove it. But I *would* like this subtle issue to have a comment
around that odd cast/and/mask thing.

            Linus

[toc] | [prev] | [next] | [standalone]

#1490588 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

On Thu, Sep 22, 2016 at 9:53 PM, Matthew Wilcox
<mawilcox@linuxonhyperv.com> wrote:
> From: Matthew Wilcox <mawilcox@microsoft.com>
>
> When compiling the radix tree with -O2, GCC thinks it can optimise:
>
>         void *entry = parent->slots[offset];
>         int siboff = entry - parent->slots;
>         void *slot = parent->slots + siboff;
>
> into
>
>         void *slot = entry;
>
> Unfortunately, 'entry' is a tagged pointer, so this optimisation leads
> to getting an unaligned pointer back from radix_tree_lookup_slot().
> The test suite wasn't being compiled with optimisation, so we hadn't
> spotted it before now.  Change the test suite to compile with -O2, and
> fix the optimisation problem by passing 'entry' through entry_to_node()
> so gcc knows this isn't a plain pointer.
> ---
>  lib/radix-tree.c                  | 3 ++-
>  tools/testing/radix-tree/Makefile | 2 +-
>  2 files changed, 3 insertions(+), 2 deletions(-)
>
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index 1b7bf73..8bf1f32 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -105,7 +105,8 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent,
>
>  #ifdef CONFIG_RADIX_TREE_MULTIORDER
>         if (radix_tree_is_internal_node(entry)) {
> -               unsigned long siboff = get_slot_offset(parent, entry);
> +               unsigned long siboff = get_slot_offset(parent,
> +                                               (void **)entry_to_node(entry));

As I see this is the only place where get_slot_offset used for
unaligned pointer.
Nobody uses "multiorder entries" so this never happens. And I have
plan to kill this code.

>                 if (siboff < RADIX_TREE_MAP_SIZE) {
>                         offset = siboff;
>                         entry = rcu_dereference_raw(parent->slots[offset]);
> diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
> index 3b53046..9d0919ed 100644
> --- a/tools/testing/radix-tree/Makefile
> +++ b/tools/testing/radix-tree/Makefile
> @@ -1,5 +1,5 @@
>
> -CFLAGS += -I. -g -Wall -D_LGPL_SOURCE
> +CFLAGS += -I. -g -O2 -Wall -D_LGPL_SOURCE
>  LDFLAGS += -lpthread -lurcu
>  TARGETS = main
>  OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \
> --
> 2.9.3
>

[toc] | [prev] | [next] | [standalone]

#1490769 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

On 22 September 2016 at 20:53, Matthew Wilcox
<mawilcox@linuxonhyperv.com> wrote:
> From: Matthew Wilcox <mawilcox@microsoft.com>
>
> When compiling the radix tree with -O2, GCC thinks it can optimise:
>
>         void *entry = parent->slots[offset];
>         int siboff = entry - parent->slots;

If entry is a pointer to void, how can you do pointer arithmetic with it?
Also, if you use pointer distances, the use of int is not valid, it
should then be ptrdiff_t siboff.

lint(1) would bite your arse off in both cases.
Sadly only UNIX (Solaris, AIX, ...) use lint(1) as mandatory part of
the build process and make warnings and errors of lint(1) fatal...

Ced
-- 
Cedric Blancher <cedric.blancher@gmail.com>
[https://plus.google.com/u/0/+CedricBlancher/]
Institute Pasteur

[toc] | [prev] | [next] | [standalone]

#1490772 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

On Sat, Sep 24, 2016 at 4:35 PM, Cedric Blancher
<cedric.blancher@gmail.com> wrote:
>>
>>         void *entry = parent->slots[offset];
>>         int siboff = entry - parent->slots;
>
> If entry is a pointer to void, how can you do pointer arithmetic with it?

It's actually void **.

(That said, gcc has an extension that considers "void *" to be a byte
pointer, so you can actually do arithmetic on them, and it acts like
"char *")

> Also, if you use pointer distances, the use of int is not valid, it
> should then be ptrdiff_t siboff.

The use of "int" is perfectly valid, since it's limited by
RADIX_TREE_MAP_SIZE, so it's going to be a small integer.

             Linus

[toc] | [prev] | [next] | [standalone]

#1490943 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

On 25 September 2016 at 02:18, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Sat, Sep 24, 2016 at 4:35 PM, Cedric Blancher
> <cedric.blancher@gmail.com> wrote:
>>>
>>>         void *entry = parent->slots[offset];
>>>         int siboff = entry - parent->slots;
>>
>> If entry is a pointer to void, how can you do pointer arithmetic with it?
>
> It's actually void **.
>
> (That said, gcc has an extension that considers "void *" to be a byte
> pointer, so you can actually do arithmetic on them, and it acts like
> "char *")
>
>> Also, if you use pointer distances, the use of int is not valid, it
>> should then be ptrdiff_t siboff.
>
> The use of "int" is perfectly valid, since it's limited by
> RADIX_TREE_MAP_SIZE, so it's going to be a small integer.

A specific data type would be wise (aka radtr_mapsz_t) to prevent a
disaster as SystemV had early during development. It took AT&T TWO
fucking months to figure out that their avl tree implementation had a
small type problem with int vs long.
Since I'd expect no one cares I'm going to print this email so I can
send the scan as PDF each time you hit that problem in the future with
"told you so"


Ced
-- 
Cedric Blancher <cedric.blancher@gmail.com>
[https://plus.google.com/u/0/+CedricBlancher/]
Institute Pasteur

[toc] | [prev] | [next] | [standalone]

#1490956 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

[Multipart message — attachments visible in raw view] — view raw

On Sun, Sep 25, 2016 at 11:04 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> The more I look at that particular piece of code, the less I like it. It's
> buggy shit. It needs to be rewritten entirely too actually check for sibling
> entries, not that ad-hoc arithmetic crap.

Here's my attempt at cleaning the mess up.

I'm not claiming it's perfect, but I think it's better. It gets rid of
the ad-hoc arithmetic in radix_tree_descend(), and just makes all that
be inside the is_sibling_entry() logic instead. Which got renamed and
made to actually return the main sibling. So now there is at least
only *one* piece of code that does that range comparison, and I don't
think there is any huge need to explain what's going on, because the
"magic" is unconditional.

Willy?

                 Linus

[toc] | [prev] | [next] | [standalone]

#1490961 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

LGTM, except that #define is_sibling_entry should be IS_SIBLING_ENTRY

Ced

On 25 September 2016 at 21:04, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Sun, Sep 25, 2016 at 11:04 AM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
>>
>> The more I look at that particular piece of code, the less I like it. It's
>> buggy shit. It needs to be rewritten entirely too actually check for sibling
>> entries, not that ad-hoc arithmetic crap.
>
> Here's my attempt at cleaning the mess up.
>
> I'm not claiming it's perfect, but I think it's better. It gets rid of
> the ad-hoc arithmetic in radix_tree_descend(), and just makes all that
> be inside the is_sibling_entry() logic instead. Which got renamed and
> made to actually return the main sibling. So now there is at least
> only *one* piece of code that does that range comparison, and I don't
> think there is any huge need to explain what's going on, because the
> "magic" is unconditional.
>
> Willy?
>
>                  Linus



-- 
Cedric Blancher <cedric.blancher@gmail.com>
[https://plus.google.com/u/0/+CedricBlancher/]
Institute Pasteur

[toc] | [prev] | [next] | [standalone]

#1490962 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

[Multipart message — attachments visible in raw view] — view raw

On Sun, Sep 25, 2016 at 12:04 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>        It gets rid of
> the ad-hoc arithmetic in radix_tree_descend(), and just makes all that
> be inside the is_sibling_entry() logic instead. Which got renamed and
> made to actually return the main sibling.

Sadly, it looks like gcc generates bad code for this approach. Looks
like it ends up testing the resulting sibling pointer twice (because
we explicitly disable -fno-delete-null-pointer-checks in the kernel,
and we have no way to say "look, I know this pointer I'm returning is
non-null").

So a smaller patch that keeps the old boolean "is_sibling_entry()" but
then actually *uses* that inside radix_tree_descend() and then tries
to make the nasty cast to "void **" more legible by making it use a
temporary variable seems to be a reasonable balance.

At least I feel like I can still read the code, but admittedly by now
that may be because I've stared at those few lines so much that I feel
like I know what's going on. So maybe the code isn't actually any more
legible after all.

.. and unlike my previous patch, it actually generates better code
than the original (while still passing the fixed test-suite, of
course). The reason seems to be exactly that temporary variable,
allowing us to just do

        entry = rcu_dereference_raw(*sibentry);

rather than doing

        entry = rcu_dereference_raw(parent->slots[offset]);

with the re-computed offset.

So I think I'll commit this unless somebody screams.

                     Linus

[toc] | [prev] | [next] | [standalone]

#1491558 — RE: [PATCH 2/2] radix-tree: Fix optimisation problem

From: linus971@gmail.com [mailto:linus971@gmail.com] On Behalf Of Linus Torvalds
> On Sun, Sep 25, 2016 at 12:04 PM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> >        It gets rid of
> > the ad-hoc arithmetic in radix_tree_descend(), and just makes all that
> > be inside the is_sibling_entry() logic instead. Which got renamed and
> > made to actually return the main sibling.
> 
> Sadly, it looks like gcc generates bad code for this approach. Looks
> like it ends up testing the resulting sibling pointer twice (because
> we explicitly disable -fno-delete-null-pointer-checks in the kernel,
> and we have no way to say "look, I know this pointer I'm returning is
> non-null").
> 
> So a smaller patch that keeps the old boolean "is_sibling_entry()" but
> then actually *uses* that inside radix_tree_descend() and then tries
> to make the nasty cast to "void **" more legible by making it use a
> temporary variable seems to be a reasonable balance.
> 
> At least I feel like I can still read the code, but admittedly by now
> that may be because I've stared at those few lines so much that I feel
> like I know what's going on. So maybe the code isn't actually any more
> legible after all.
> 
> .. and unlike my previous patch, it actually generates better code
> than the original (while still passing the fixed test-suite, of
> course). The reason seems to be exactly that temporary variable,
> allowing us to just do
> 
>         entry = rcu_dereference_raw(*sibentry);
> 
> rather than doing
> 
>         entry = rcu_dereference_raw(parent->slots[offset]);
> 
> with the re-computed offset.
> 
> So I think I'll commit this unless somebody screams.

Acked-by: Matthew Wilcox <mawilcox@microsoft.com>

I don't love it.  But I think it's a reasonable fix for this point in the release cycle, and I have an idea for changing the representation of sibling slots that will make this moot.

(Basically adopting Konstantin's idea for using the *last* entry instead of the *first*, and then using entries of the form (offset << 2 | RADIX_TREE_INTERNAL_NODE), so we can identify sibling entries without knowing the parent pointer, and we can go straight from sibling entry to slot offset as a shift rather than as a pointer subtraction).

[toc] | [prev] | [next] | [standalone]

#1491569 — Re: [PATCH 2/2] radix-tree: Fix optimisation problem

You might also try to use valid, plain ISO C99 instead of perverted
gcc extensions which only cause a lot of trouble in the long run.

Ced

On 26 September 2016 at 23:28, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> From: linus971@gmail.com [mailto:linus971@gmail.com] On Behalf Of Linus Torvalds
>> On Sun, Sep 25, 2016 at 12:04 PM, Linus Torvalds
>> <torvalds@linux-foundation.org> wrote:
>> >        It gets rid of
>> > the ad-hoc arithmetic in radix_tree_descend(), and just makes all that
>> > be inside the is_sibling_entry() logic instead. Which got renamed and
>> > made to actually return the main sibling.
>>
>> Sadly, it looks like gcc generates bad code for this approach. Looks
>> like it ends up testing the resulting sibling pointer twice (because
>> we explicitly disable -fno-delete-null-pointer-checks in the kernel,
>> and we have no way to say "look, I know this pointer I'm returning is
>> non-null").
>>
>> So a smaller patch that keeps the old boolean "is_sibling_entry()" but
>> then actually *uses* that inside radix_tree_descend() and then tries
>> to make the nasty cast to "void **" more legible by making it use a
>> temporary variable seems to be a reasonable balance.
>>
>> At least I feel like I can still read the code, but admittedly by now
>> that may be because I've stared at those few lines so much that I feel
>> like I know what's going on. So maybe the code isn't actually any more
>> legible after all.
>>
>> .. and unlike my previous patch, it actually generates better code
>> than the original (while still passing the fixed test-suite, of
>> course). The reason seems to be exactly that temporary variable,
>> allowing us to just do
>>
>>         entry = rcu_dereference_raw(*sibentry);
>>
>> rather than doing
>>
>>         entry = rcu_dereference_raw(parent->slots[offset]);
>>
>> with the re-computed offset.
>>
>> So I think I'll commit this unless somebody screams.
>
> Acked-by: Matthew Wilcox <mawilcox@microsoft.com>
>
> I don't love it.  But I think it's a reasonable fix for this point in the release cycle, and I have an idea for changing the representation of sibling slots that will make this moot.
>
> (Basically adopting Konstantin's idea for using the *last* entry instead of the *first*, and then using entries of the form (offset << 2 | RADIX_TREE_INTERNAL_NODE), so we can identify sibling entries without knowing the parent pointer, and we can go straight from sibling entry to slot offset as a shift rather than as a pointer subtraction).



-- 
Cedric Blancher <cedric.blancher@gmail.com>
[https://plus.google.com/u/0/+CedricBlancher/]
Institute Pasteur

[toc] | [prev] | [next] | [standalone]

#1489102 — [PATCH 1/2] radix tree test suite: Test radix_tree_replace_slot() for multiorder entries

From: Matthew Wilcox <mawilcox@microsoft.com>

When we replace a multiorder entry, check that all indices reflect the
new value.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 tools/testing/radix-tree/multiorder.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 39d9b95..05d7bc4 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -124,6 +124,8 @@ static void multiorder_check(unsigned long index, int order)
 	unsigned long i;
 	unsigned long min = index & ~((1UL << order) - 1);
 	unsigned long max = min + (1UL << order);
+	void **slot;
+	struct item *item2 = item_create(min);
 	RADIX_TREE(tree, GFP_KERNEL);
 
 	printf("Multiorder index %ld, order %d\n", index, order);
@@ -139,13 +141,19 @@ static void multiorder_check(unsigned long index, int order)
 		item_check_absent(&tree, i);
 	for (i = max; i < 2*max; i++)
 		item_check_absent(&tree, i);
+	for (i = min; i < max; i++)
+		assert(radix_tree_insert(&tree, i, item2) == -EEXIST);
+
+	slot = radix_tree_lookup_slot(&tree, index);
+	free(*slot);
+	radix_tree_replace_slot(slot, item2);
 	for (i = min; i < max; i++) {
-		static void *entry = (void *)
-					(0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY);
-		assert(radix_tree_insert(&tree, i, entry) == -EEXIST);
+		struct item *item = item_lookup(&tree, i);
+		assert(item != 0);
+		assert(item->index == min);
 	}
 
-	assert(item_delete(&tree, index) != 0);
+	assert(item_delete(&tree, min) != 0);
 
 	for (i = 0; i < 2*max; i++)
 		item_check_absent(&tree, i);
-- 
2.9.3

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web