hammer2 - Track leaf counts for topological collapse
authorMatthew Dillon <dillon@apollo.backplane.com>
Sat, 9 Sep 2017 22:59:25 +0000 (15:59 -0700)
committerMatthew Dillon <dillon@apollo.backplane.com>
Sat, 9 Sep 2017 22:59:25 +0000 (15:59 -0700)
* Track leaf counts through indirect blocks.  This is a prereq to
  being able to efficiently collapse indirect nodes that have become
  too empty to be useful.

* Leaf count is capped at 65535.  Attempting to decrement the count will
  flag the chain to recount (in a later commit).

* Because this count will be used to determine when a collapse is possible,
  we do not track leaf counts through inodes.  That is, an inode counts as
  a leaf.

sbin/hammer2/cmd_debug.c
sys/vfs/hammer2/hammer2.h
sys/vfs/hammer2/hammer2_chain.c
sys/vfs/hammer2/hammer2_disk.h

index 392f854..8577b39 100644 (file)
@@ -474,10 +474,13 @@ show_bref(int fd, int tab, int bi, hammer2_blockref_t *bref, int dofreemap,
                break;
        }
 
-       tabprintf(tab, "%s.%-3d %016jx %016jx/%-2d mir=%016jx mod=%016jx ",
+       tabprintf(tab,
+                 "%s.%-3d %016jx %016jx/%-2d "
+                 "mir=%016jx mod=%016jx leafcnt=%d ",
               type_str, bi, (intmax_t)bref->data_off,
               (intmax_t)bref->key, (intmax_t)bref->keybits,
-              (intmax_t)bref->mirror_tid, (intmax_t)bref->modify_tid);
+              (intmax_t)bref->mirror_tid, (intmax_t)bref->modify_tid,
+              bref->leaf_count);
        tab += SHOW_TAB;
        if (bref->flags)
                printf("flags=%02x ", bref->flags);
index d8e804f..85f2193 100644 (file)
@@ -368,6 +368,7 @@ RB_PROTOTYPE(hammer2_chain_tree, hammer2_chain, rbnode, hammer2_chain_cmp);
 #define HAMMER2_CHAIN_IOINPROG         0x00100000      /* I/O interlock */
 #define HAMMER2_CHAIN_IOSIGNAL         0x00200000      /* I/O interlock */
 #define HAMMER2_CHAIN_PFSBOUNDARY      0x00400000      /* super->pfs inode */
+#define HAMMER2_CHAIN_HINT_LEAF_COUNT  0x00800000      /* redo leaf count */
 
 #define HAMMER2_CHAIN_FLUSH_MASK       (HAMMER2_CHAIN_MODIFIED |       \
                                         HAMMER2_CHAIN_UPDATE |         \
index af115e4..6ecfb48 100644 (file)
@@ -4867,15 +4867,41 @@ hammer2_base_delete(hammer2_chain_t *parent,
        }
        switch(scan->type) {
        case HAMMER2_BREF_TYPE_INODE:
-               parent->bref.embed.stats.inode_count -= 1;
-               /* fall through */
        case HAMMER2_BREF_TYPE_DATA:
+               --parent->bref.embed.stats.inode_count;
+               if (parent->bref.leaf_count == HAMMER2_BLOCKREF_LEAF_MAX) {
+                       atomic_set_int(&chain->flags,
+                                      HAMMER2_CHAIN_HINT_LEAF_COUNT);
+               } else {
+                       if (parent->bref.leaf_count)
+                               --parent->bref.leaf_count;
+               }
+               /* fall through */
        case HAMMER2_BREF_TYPE_INDIRECT:
                parent->bref.embed.stats.data_count -=
                        scan->embed.stats.data_count;
                parent->bref.embed.stats.inode_count -=
                        scan->embed.stats.inode_count;
+               if (scan->type == HAMMER2_BREF_TYPE_INODE)
+                       break;
+               if (parent->bref.leaf_count == HAMMER2_BLOCKREF_LEAF_MAX) {
+                       atomic_set_int(&chain->flags,
+                                      HAMMER2_CHAIN_HINT_LEAF_COUNT);
+               } else {
+                       if (parent->bref.leaf_count <= scan->leaf_count)
+                               parent->bref.leaf_count = 0;
+                       else
+                               parent->bref.leaf_count -= scan->leaf_count;
+               }
                break;
+       case HAMMER2_BREF_TYPE_DIRENT:
+               if (parent->bref.leaf_count == HAMMER2_BLOCKREF_LEAF_MAX) {
+                       atomic_set_int(&chain->flags,
+                                      HAMMER2_CHAIN_HINT_LEAF_COUNT);
+               } else {
+                       if (parent->bref.leaf_count)
+                               --parent->bref.leaf_count;
+               }
        default:
                break;
        }
@@ -4952,14 +4978,28 @@ hammer2_base_insert(hammer2_chain_t *parent,
        }
        switch(elm->type) {
        case HAMMER2_BREF_TYPE_INODE:
-               parent->bref.embed.stats.inode_count += 1;
-               /* fall through */
+               ++parent->bref.embed.stats.inode_count;
        case HAMMER2_BREF_TYPE_DATA:
+               if (parent->bref.leaf_count != HAMMER2_BLOCKREF_LEAF_MAX)
+                       ++parent->bref.leaf_count;
+               /* fall through */
        case HAMMER2_BREF_TYPE_INDIRECT:
                parent->bref.embed.stats.data_count +=
                        elm->embed.stats.data_count;
                parent->bref.embed.stats.inode_count +=
                        elm->embed.stats.inode_count;
+               if (elm->type == HAMMER2_BREF_TYPE_INODE)
+                       break;
+               if (parent->bref.leaf_count + elm->leaf_count <
+                   HAMMER2_BLOCKREF_LEAF_MAX) {
+                       parent->bref.leaf_count += elm->leaf_count;
+               } else {
+                       parent->bref.leaf_count = HAMMER2_BLOCKREF_LEAF_MAX;
+               }
+               break;
+       case HAMMER2_BREF_TYPE_DIRENT:
+               if (parent->bref.leaf_count != HAMMER2_BLOCKREF_LEAF_MAX)
+                       ++parent->bref.leaf_count;
                break;
        default:
                break;
index 763de94..4f90081 100644 (file)
@@ -588,6 +588,15 @@ typedef struct hammer2_dirent_head hammer2_dirent_head_t;
  *      blocks bottom-up, inserting a new root when radix expansion
  *      is required.
  *
+ * leaf_count  - Helps manage leaf collapse calculations when indirect
+ *              blocks become mostly empty.  This value caps out at
+ *              HAMMER2_BLOCKREF_LEAF_MAX (65535).
+ *
+ *              Used by the chain code to determine when to pull leafs up
+ *              from nearly empty indirect blocks.  For the purposes of this
+ *              calculation, BREF_TYPE_INODE is considered a leaf, along
+ *              with DIRENT and DATA.
+ *
  *                                 RESERVED FIELDS
  *
  * A number of blockref fields are reserved and should generally be set to
@@ -604,8 +613,7 @@ struct hammer2_blockref {           /* MUST BE EXACTLY 64 BYTES */
        uint8_t         keybits;        /* #of keybits masked off 0=leaf */
        uint8_t         vradix;         /* virtual data/meta-data size */
        uint8_t         flags;          /* blockref flags */
-       uint8_t         reserved06;
-       uint8_t         reserved07;
+       uint16_t        leaf_count;     /* leaf aggregation count */
        hammer2_key_t   key;            /* key specification */
        hammer2_tid_t   mirror_tid;     /* media flush topology & freemap */
        hammer2_tid_t   modify_tid;     /* clc modify (not propagated) */
@@ -683,6 +691,8 @@ typedef struct hammer2_blockref hammer2_blockref_t;
 #define HAMMER2_BLOCKREF_BYTES         128     /* blockref struct in bytes */
 #define HAMMER2_BLOCKREF_RADIX         7
 
+#define HAMMER2_BLOCKREF_LEAF_MAX      65535
+
 /*
  * On-media and off-media blockref types.
  *