HAMMER VFS - Improve initial B-Tree packing

* Detect the case where B-Tree leafs are being laid down sequentially,
  such as when creating a large file.  When linear operation is detected
  split leafs 75:25 instead of 50:50.  This greatly improves fill ratios.

  It should be noted that the HAMMER flush sorts by inode so directory
  entries will also tend to benefit.

* This only effects (improves) the initial B-Tree layout.  The overnight
  hammer cleanup will refactor the B-Tree to a more optimal state
  regardless.

diff --git a/sys/vfs/hammer/hammer.h b/sys/vfs/hammer/hammer.h
index 99a41d4..96a8108 100644 (file)
--- a/sys/vfs/hammer/hammer.h
+++ b/sys/vfs/hammer/hammer.h
@@ -655,6 +655,7 @@ struct hammer_node {
 #define HAMMER_NODE_NEEDSCRC   0x0008
 #define HAMMER_NODE_NEEDSMIRROR        0x0010
 #define HAMMER_NODE_CRCBAD     0x0020
+#define HAMMER_NODE_NONLINEAR  0x0040          /* linear heuristic */
 
 #define HAMMER_NODE_CRCANY     (HAMMER_NODE_CRCGOOD | HAMMER_NODE_CRCBAD)
 

diff --git a/sys/vfs/hammer/hammer_btree.c b/sys/vfs/hammer/hammer_btree.c
index 050d4a2..bfa7e93 100644 (file)
--- a/sys/vfs/hammer/hammer_btree.c
+++ b/sys/vfs/hammer/hammer_btree.c
@@ -1455,16 +1455,31 @@ btree_split_internal(hammer_cursor_t cursor)
        ++hammer_stats_btree_splits;
 
        /* 
-        * We are splitting but elms[split] will be promoted to the parent,
-        * leaving the right hand node with one less element.  If the
-        * insertion point will be on the left-hand side adjust the split
-        * point to give the right hand side one additional node.
+        * Calculate the split point.  If the insertion point is at the
+        * end of the leaf we adjust the split point significantly to the
+        * right to try to optimize node fill and flag it.  If we hit
+        * that same leaf again our heuristic failed and we don't try
+        * to optimize node fill (it could lead to a degenerate case).
         */
        node = cursor->node;
        ondisk = node->ondisk;
-       split = (ondisk->count + 1) / 2;
-       if (cursor->index <= split)
-               --split;
+       KKASSERT(ondisk->count > 4);
+       if (cursor->index == ondisk->count &&
+           (node->flags & HAMMER_NODE_NONLINEAR) == 0) {
+               split = (ondisk->count + 1) * 3 / 4;
+               node->flags |= HAMMER_NODE_NONLINEAR;
+       } else {
+               /*
+                * We are splitting but elms[split] will be promoted to
+                * the parent, leaving the right hand node with one less
+                * element.  If the insertion point will be on the
+                * left-hand side adjust the split point to give the
+                * right hand side one additional node.
+                */
+               split = (ondisk->count + 1) / 2;
+               if (cursor->index <= split)
+                       --split;
+       }
 
        /*
         * If we are at the root of the filesystem, create a new root node
@@ -1695,19 +1710,36 @@ btree_split_leaf(hammer_cursor_t cursor)
                 &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].leaf.base) > 0);
 
        /* 
-        * Calculate the split point.  If the insertion point will be on
-        * the left-hand side adjust the split point to give the right
-        * hand side one additional node.
+        * Calculate the split point.  If the insertion point is at the
+        * end of the leaf we adjust the split point significantly to the
+        * right to try to optimize node fill and flag it.  If we hit
+        * that same leaf again our heuristic failed and we don't try
+        * to optimize node fill (it could lead to a degenerate case).
         *
         * Spikes are made up of two leaf elements which cannot be
         * safely split.
         */
        leaf = cursor->node;
        ondisk = leaf->ondisk;
-       KKASSERT(ondisk->count > 2);
-       split = (ondisk->count + 1) / 2;
-       if (cursor->index <= split)
+       KKASSERT(ondisk->count > 4);
+       if (cursor->index == ondisk->count &&
+           (leaf->flags & HAMMER_NODE_NONLINEAR) == 0) {
+               split = (ondisk->count + 1) * 3 / 4;
+               leaf->flags |= HAMMER_NODE_NONLINEAR;
+       } else {
+               split = (ondisk->count + 1) / 2;
+       }
+
+#if 0
+       /*
+        * If the insertion point is at the split point shift the
+        * split point left so we don't have to worry about
+        */
+       if (cursor->index == split)
                --split;
+#endif
+       KKASSERT(split > 0 && split < ondisk->count);
+
        error = 0;
        hmp = leaf->hmp;
 

diff --git a/sys/vfs/hammer/hammer_inode.c b/sys/vfs/hammer/hammer_inode.c
index 0904eda..c6822dc 100644 (file)
--- a/sys/vfs/hammer/hammer_inode.c
+++ b/sys/vfs/hammer/hammer_inode.c
@@ -1949,8 +1949,13 @@ hammer_flush_inode_core(hammer_inode_t ip, hammer_flush_group_t flg, int flags)
        /*
         * If the flush group reaches the autoflush limit we want to signal
         * the flusher.  This is particularly important for remove()s.
+        *
+        * If the default hammer_limit_reclaim is changed via sysctl
+        * make sure we don't hit a degenerate case where we don't start
+        * a flush but blocked on further inode ops.
         */
-       if (flg->total_count == hammer_autoflush)
+       if (flg->total_count == hammer_autoflush ||
+           flg->total_count >= hammer_limit_reclaim / 4)
                flags |= HAMMER_FLUSH_SIGNAL;
 
 #if 0