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

Groups > linux.kernel > #1490769 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

#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] | [next] | [standalone]

#1490772

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

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

[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

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

[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

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

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] | [standalone]

Back to top | Article view | linux.kernel

csiph-web