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

Groups > linux.kernel > #1491569

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

Show all headers | View raw

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

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

Thread

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

csiph-web