linux-kernel - Re: [PATCH 1/3] radix-tree: 'slot' can be NULL in radix_tree_next

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, 8 Aug 2016 22:21:39 +0300
From:	Konstantin Khlebnikov <koct9i@...il.com>
To:	Ross Zwisler <ross.zwisler@...ux.intel.com>
Cc:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	linux-nvdimm@...ts.01.org,
	Andrey Ryabinin <aryabinin@...tuozzo.com>,
	Dmitry Vyukov <dvyukov@...gle.com>
Subject: Re: [PATCH 1/3] radix-tree: 'slot' can be NULL in radix_tree_next_slot()

On Mon, Aug 8, 2016 at 9:57 PM, Ross Zwisler
<ross.zwisler@...ux.intel.com> wrote:
> There are four cases I can see where we could end up with a NULL 'slot' in
> radix_tree_next_slot().  Yet radix_tree_next_slot() never actually checks
> whether 'slot' is NULL.  It just happens that for the cases where 'slot' is
> NULL, some other combination of factors prevents us from dereferencing it.
>
> It would be very easy for someone to unwittingly change one of these
> factors without realizing that we are implicitly depending on it to save us
> from a NULL pointer dereference.
>
> So, explicitly account for the fact that that 'slot' can be NULL in
> radix_tree_next_slot() and save ourselves from future crashes and debugging
> efforts.
>
> Here are details on the four cases:
>
> 1) radix_tree_iter_retry() via a non-tagged iteration like
> radix_tree_for_each_slot().  In this case we currently aren't seeing a bug
> because radix_tree_iter_retry() sets
>
>         iter->next_index = iter->index;
>
> which means that in in the else case in radix_tree_next_slot(), 'count' is
> zero, so we skip over the while() loop and effectively just return NULL
> without ever dereferencing 'slot'.
>
> 2) radix_tree_iter_retry() via tagged iteration like
> radix_tree_for_each_tagged().  This case was giving us NULL pointer
> dereferences in testing, and was fixed with this commit:
>
> commit 3cb9185c6730 ("radix-tree: fix radix_tree_iter_retry() for tagged
> iterators.")
>
> This fix doesn't explicitly check for 'slot' being NULL, though, it works
> around the NULL pointer dereference by instead zeroing iter->tags in
> radix_tree_iter_retry(), which makes us bail out of the if() case in
> radix_tree_next_slot() before we dereference 'slot'.
>
> 3) radix_tree_iter_next() via via a non-tagged iteration like
> radix_tree_for_each_slot().  This currently happens in shmem_tag_pins()
> and shmem_partial_swap_usage().
>
> As with non-tagged iteration, 'count' in the else case of
> radix_tree_next_slot() is zero, so we skip over the while() loop and
> effectively just return NULL without ever dereferencing 'slot'.
>
> 4) radix_tree_iter_next() via tagged iteration like
> radix_tree_for_each_tagged().  This happens in shmem_wait_for_pins().
>
> radix_tree_iter_next() zeros out iter->tags, so we end up exiting
> radix_tree_next_slot() here:
>
>         if (flags & RADIX_TREE_ITER_TAGGED) {
>                 void *canon = slot;
>
>                 iter->tags >>= 1;
>                 if (unlikely(!iter->tags))
>                         return NULL;
>
> Signed-off-by: Ross Zwisler <ross.zwisler@...ux.intel.com>
> ---
>  include/linux/radix-tree.h | 3 +++
>  1 file changed, 3 insertions(+)
>
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index 4c45105..1bf16ed 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -465,6 +465,9 @@ static inline struct radix_tree_node *entry_to_node(void *ptr)
>  static __always_inline void **
>  radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
>  {
> +       if (unlikely(!slot))
> +               return NULL;
> +
>         if (flags & RADIX_TREE_ITER_TAGGED) {
>                 void *canon = slot;
>

NAK. This is fast path and it's already bloated.
I want to revert most changes here and rework "multiorder" entries.

Here you can find almost ready patchset for that
https://github.com/koct9i/linux/commits/radix-tree

> --
> 2.9.0
>