• Ross Zwisler's avatar
    radix-tree: 'slot' can be NULL in radix_tree_next_slot() · 915045fe
    Ross Zwisler authored
    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.
    
    Add a comment documenting the things that allow 'slot' to be safely passed
    as NULL to radix_tree_next_slot().
    
    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 3cb9185c ("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;
    
    Link: http://lkml.kernel.org/r/20160815194237.25967-2-ross.zwisler@linux.intel.comSigned-off-by: default avatarRoss Zwisler <ross.zwisler@linux.intel.com>
    Cc: Konstantin Khlebnikov <koct9i@gmail.com>
    Cc: Andrey Ryabinin <aryabinin@virtuozzo.com>
    Cc: Dmitry Vyukov <dvyukov@google.com>
    Cc: Shuah Khan <shuahkh@osg.samsung.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    915045fe
radix-tree.h 19.5 KB