linux-kernel - RE: [PATCH 2/2] radix-tree: Fix optimisation problem

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 26 Sep 2016 21:28:00 +0000
From:   Matthew Wilcox <mawilcox@...rosoft.com>
To:     Linus Torvalds <torvalds@...ux-foundation.org>,
        Cedric Blancher <cedric.blancher@...il.com>
CC:     Ross Zwisler <ross.zwisler@...ux.intel.com>,
        Matthew Wilcox <mawilcox@...uxonhyperv.com>,
        Konstantin Khlebnikov <koct9i@...il.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        "Kirill A. Shutemov" <kirill.shutemov@...ux.intel.com>,
        linux-fsdevel <linux-fsdevel@...r.kernel.org>,
        Linux MM <linux-mm@...ck.org>,
        "Linux Kernel Mailing List" <linux-kernel@...r.kernel.org>
Subject: RE: [PATCH 2/2] radix-tree: Fix optimisation problem

From: linus971@...il.com [mailto:linus971@...il.com] On Behalf Of Linus Torvalds
> On Sun, Sep 25, 2016 at 12:04 PM, Linus Torvalds
> <torvalds@...ux-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@...rosoft.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).