• David Howells's avatar
    radix_tree_tag_get() is not as safe as the docs make out [ver #2] · ce82653d
    David Howells authored
    radix_tree_tag_get() is not safe to use concurrently with radix_tree_tag_set()
    or radix_tree_tag_clear().  The problem is that the double tag_get() in
    radix_tree_tag_get():
    
    		if (!tag_get(node, tag, offset))
    			saw_unset_tag = 1;
    		if (height == 1) {
    			int ret = tag_get(node, tag, offset);
    
    may see the value change due to the action of set/clear.  RCU is no protection
    against this as no pointers are being changed, no nodes are being replaced
    according to a COW protocol - set/clear alter the node directly.
    
    The documentation in linux/radix-tree.h, however, says that
    radix_tree_tag_get() is an exception to the rule that "any function modifying
    the tree or tags (...) must exclude other modifications, and exclude any
    functions reading the tree".
    
    The problem is that the next statement in radix_tree_tag_get() checks that the
    tag doesn't vary over time:
    
    			BUG_ON(ret && saw_unset_tag);
    
    This has been seen happening in FS-Cache:
    
    	https://www.redhat.com/archives/linux-cachefs/2010-April/msg00013.html
    
    To this end, remove the BUG_ON() from radix_tree_tag_get() and note in various
    comments that the value of the tag may change whilst the RCU read lock is held,
    and thus that the return value of radix_tree_tag_get() may not be relied upon
    unless radix_tree_tag_set/clear() and radix_tree_delete() are excluded from
    running concurrently with it.
    Reported-by: default avatarRomain DEGEZ <romain.degez@smartjog.com>
    Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
    Acked-by: default avatarNick Piggin <npiggin@suse.de>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    ce82653d
radix-tree.c 32 KB