1. 25 Jun, 2006 1 commit
  2. 23 Jun, 2006 3 commits
    • Peter Zijlstra's avatar
      [PATCH] buglet in radix_tree_tag_set · 4c91c364
      Peter Zijlstra authored
      The comment states: 'Setting a tag on a not-present item is a BUG.' Hence
      if 'index' is larger than the maxindex; the item _cannot_ be presen; it
      should also be a BUG.
      
      Also, this allows the following statement (assume a fresh tree):
      
        radix_tree_tag_set(root, 16, 1);
      
      to fail silently, but when preceded by:
      
        radix_tree_insert(root, 32, item);
      
      it would BUG, because the height has been extended by the insert.
      
      In neither case was 16 present.
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Acked-by: default avatarNick Piggin <npiggin@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      4c91c364
    • Nick Piggin's avatar
      [PATCH] radix-tree: small · cfd9b7df
      Nick Piggin authored
      Reduce radix tree node memory usage by about a factor of 4 for small files
      (< 64K).  There are pointer traversal and memory usage costs for large
      files with dense pagecache.
      Signed-off-by: default avatarNick Piggin <npiggin@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      cfd9b7df
    • Nick Piggin's avatar
      [PATCH] radix-tree: direct data · 612d6c19
      Nick Piggin authored
      The ability to have height 0 radix trees (a direct pointer to the data item
      rather than going through a full node->slot) quietly disappeared with
      old-2.6-bkcvs commit ffee171812d51652f9ba284302d9e5c5cc14bdfd.  On 64-bit
      machines this causes nearly 600 bytes to be used for every <= 4K file in
      pagecache.
      
      Re-introduce this feature, root tags stored in spare ->gfp_mask bits.
      
      Simplify radix_tree_delete's complex tag clearing arrangement (which would
      become even more complex) by just falling back to tag clearing functions
      (the pagecache radix-tree never uses this path anyway, so the icache
      savings will mean it's actually a speedup).
      
      On my 4GB G5, this saves 8MB RAM per kernel kernel source+object tree in
      pagecache.
      
      Pagecache lookup, insertion, and removal speed for small files will also be
      improved.
      
      This makes RCU radix tree harder, but it's worth it.
      Signed-off-by: default avatarNick Piggin <npiggin@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      612d6c19
  3. 25 Mar, 2006 1 commit
  4. 16 Feb, 2006 1 commit
    • NeilBrown's avatar
      [PATCH] Fix over-zealous tag clearing in radix_tree_delete · 90f9dd8f
      NeilBrown authored
      If a tag is set for a node being deleted from a radix_tree, then that
      tag gets cleared from the parent of the node, even if it is set for some
      siblings of the node begin deleted.
      
      This patch changes the logic to include a test for any_tag_set similar
      to the logic a little futher down.  Care is taken to ensure that
      'nr_cleared_tags' remains equals to the number of entries in the 'tags'
      array which are set to '0' (which means that this tag is not set in the
      tree below pathp->node, and should be cleared at pathp->node and
      possibly above.
      
      [ Nick says: "Linus FYI, I was able to modify the radix tree test
        harness to catch the bug and can no longer trigger it after the fix.
        Resulting code passes all other harness tests as well of course." ]
      Signed-off-by: default avatarNeil Brown <neilb@suse.de>
      Acked-by: default avatarNick Piggin <npiggin@suse.de>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      90f9dd8f
  5. 08 Jan, 2006 3 commits
  6. 07 Nov, 2005 1 commit
    • Hans Reiser's avatar
      [PATCH] reiser4: add radix_tree_lookup_slot() · a4331366
      Hans Reiser authored
      Reiser4 uses radix trees to solve a trouble reiser4_readdir has serving nfs
      requests.
      
      Unfortunately, radix tree api lacks an operation suitable for modifying
      existing entry.  This patch adds radix_tree_lookup_slot which returns pointer
      to found item within the tree.  That location can be then updated.
      
      Both Nick and Christoph Lameter have patches which need this as well.
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      a4331366
  7. 08 Oct, 2005 1 commit
  8. 10 Sep, 2005 1 commit
  9. 07 Sep, 2005 2 commits
  10. 07 Jul, 2005 1 commit
  11. 16 Apr, 2005 1 commit
    • Linus Torvalds's avatar
      Linux-2.6.12-rc2 · 1da177e4
      Linus Torvalds authored
      Initial git repository build. I'm not bothering with the full history,
      even though we have it. We can create a separate "historical" git
      archive of that later if we want to, and in the meantime it's about
      3.2GB when imported into git - space that would just make the early
      git days unnecessarily complicated, when we don't have a lot of good
      infrastructure for it.
      
      Let it rip!
      1da177e4