1. 24 Aug, 2010 28 commits
  2. 23 Aug, 2010 4 commits
    • Linus Torvalds's avatar
      Merge branch 'radix-tree' of git://git.kernel.org/pub/scm/linux/kernel/git/dgc/xfsdev · 9ee47476
      Linus Torvalds authored
      * 'radix-tree' of git://git.kernel.org/pub/scm/linux/kernel/git/dgc/xfsdev:
        radix-tree: radix_tree_range_tag_if_tagged() can set incorrect tags
        radix-tree: clear all tags in radix_tree_node_rcu_free
      9ee47476
    • Linus Torvalds's avatar
      Linux 2.6.36-rc2 · 76be97c1
      Linus Torvalds authored
      76be97c1
    • Dave Chinner's avatar
      radix-tree: radix_tree_range_tag_if_tagged() can set incorrect tags · 144dcfc0
      Dave Chinner authored
      Commit ebf8aa44 ("radix-tree:
      omplement function radix_tree_range_tag_if_tagged") does not safely
      set tags on on intermediate tree nodes. The code walks down the tree
      setting tags before it has fully resolved the path to the leaf under
      the assumption there will be a leaf slot with the tag set in the
      range it is searching.
      
      Unfortunately, this is not a valid assumption - we can abort after
      setting a tag on an intermediate node if we overrun the number of
      tags we are allowed to set in a batch, or stop scanning because we
      we have passed the last scan index before we reach a leaf slot with
      the tag we are searching for set.
      
      As a result, we can leave the function with tags set on intemediate
      nodes which can be tripped over later by tag-based lookups. The
      result of these stale tags is that lookup may end prematurely or
      livelock because the lookup cannot make progress.
      
      The fix for the problem involves reocrding the traversal path we
      take to the leaf nodes, and only propagating the tags back up the
      tree once the tag is set in the leaf node slot. We are already
      recording the path for efficient traversal, so there is no
      additional overhead to do the intermediately node tag setting in
      this manner.
      
      This fixes a radix tree lookup livelock triggered by the new
      writeback sync livelock avoidance code introduced in commit
      f446daae ("mm: implement writeback
      livelock avoidance using page tagging").
      Signed-off-by: default avatarDave Chinner <dchinner@redhat.com>
      Acked-by: default avatarJan Kara <jack@suse.cz>
      144dcfc0
    • Dave Chinner's avatar
      radix-tree: clear all tags in radix_tree_node_rcu_free · b6dd0865
      Dave Chinner authored
      Commit f446daae ("mm: implement
      writeback livelock avoidance using page tagging") introduced a new
      radix tree tag, increasing the number of tags in each node from 2 to
      3. It did not, however, fix up the code in
      radix_tree_node_rcu_free() that cleans up after radix_tree_shrink()
      and hence could leave stray tags set in the new tag array.
      
      The result is that the livelock avoidance code added in the the
      above commit would hit stale tags when doing tag based lookups,
      resulting in livelocks when trying to traverse the tree.
      
      Fix this problem in radix_tree_node_rcu_free() so it doesn't happen
      again in the future by using a loop to walk all the tags up to
      RADIX_TREE_MAX_TAGS to clear the stray tags radix_tree_shrink()
      leaves behind.
      Signed-off-by: default avatarDave Chinner <dchinner@redhat.com>
      Acked-by: default avatarNick Piggin <npiggin@kernel.dk>
      Acked-by: default avatarJan Kara <jack@suse.cz>
      b6dd0865
  3. 22 Aug, 2010 8 commits