lkml.org 
[lkml]   [2016]   [Aug]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [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@linux.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@linux.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
>

\
 
 \ /
  Last update: 2016-08-08 22:01    [W:0.103 / U:0.188 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site