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:   Sat, 24 Sep 2016 11:36:27 +0300
From:   Konstantin Khlebnikov <koct9i@...il.com>
To:     Matthew Wilcox <mawilcox@...uxonhyperv.com>
Cc:     Linus Torvalds <torvalds@...ux-foundation.org>,
        "Kirill A. Shutemov" <kirill.shutemov@...ux.intel.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Ross Zwisler <ross.zwisler@...ux.intel.com>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        linux-fsdevel <linux-fsdevel@...r.kernel.org>,
        Matthew Wilcox <mawilcox@...rosoft.com>
Subject: Re: [PATCH 2/2] radix-tree: Fix optimisation problem

On Thu, Sep 22, 2016 at 9:53 PM, Matthew Wilcox
<mawilcox@...uxonhyperv.com> wrote:
> From: Matthew Wilcox <mawilcox@...rosoft.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
>