Give the A-list code the ability to do a forward or reverse allocation
authorMatthew Dillon <dillon@dragonflybsd.org>
Tue, 16 Oct 2007 18:16:42 +0000 (18:16 +0000)
committerMatthew Dillon <dillon@dragonflybsd.org>
Tue, 16 Oct 2007 18:16:42 +0000 (18:16 +0000)
as-of a particular block.  This allows us to localize allocations.

Flesh out HAMMER's on-disk structures.

sys/vfs/hammer/hammer_alist.c
sys/vfs/hammer/hammer_alist.h
sys/vfs/hammer/hammer_disk.h

index 5c88447..4682ecc 100644 (file)
@@ -38,7 +38,7 @@
  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.c,v 1.2 2007/10/12 18:57:45 dillon Exp $
+ * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.c,v 1.3 2007/10/16 18:16:42 dillon Exp $
  */
 /*
  * This module implements a generic allocator through the use of a hinted
@@ -113,17 +113,17 @@ void panic(const char *ctl, ...);
  */
 
 static int32_t hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan,
-                                       int32_t blk, int count);
+                                       int32_t blk, int count, int32_t atblk);
 static int32_t hammer_alst_meta_alloc_fwd(hammer_alist_t live,
                                        hammer_almeta_t scan,
                                        int32_t blk, int32_t count,
-                                       int32_t radix, int skip);
+                                       int32_t radix, int skip, int32_t atblk);
 static int32_t hammer_alst_leaf_alloc_rev(hammer_almeta_t scan,
-                                       int32_t blk, int count);
+                                       int32_t blk, int count, int32_t atblk);
 static int32_t hammer_alst_meta_alloc_rev(hammer_alist_t live,
                                        hammer_almeta_t scan,
                                        int32_t blk, int32_t count,
-                                       int32_t radix, int skip);
+                                       int32_t radix, int skip, int32_t atblk);
 static void hammer_alst_leaf_free(hammer_almeta_t scan,
                                        int32_t relblk, int count);
 static void hammer_alst_meta_free(hammer_alist_t live, hammer_almeta_t scan,
@@ -311,11 +311,11 @@ hammer_alist_alloc(hammer_alist_t live, int32_t count)
                        KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
 #endif
                        blk = hammer_alst_leaf_alloc_fwd(
-                                   live->meta + 1, 0, count);
+                                   live->meta + 1, 0, count, 0);
                } else {
                        blk = hammer_alst_meta_alloc_fwd(
                                    live, live->meta + 1,
-                                   0, count, bl->bl_radix, bl->bl_skip);
+                                   0, count, bl->bl_radix, bl->bl_skip, 0);
                }
                if (blk != HAMMER_ALIST_BLOCK_NONE)
                        live->meta->bm_alist_freeblks -= count;
@@ -324,24 +324,30 @@ hammer_alist_alloc(hammer_alist_t live, int32_t count)
 }
 
 int32_t 
-hammer_alist_alloc_rev(hammer_alist_t live, int32_t count)
+hammer_alist_alloc_fwd(hammer_alist_t live, int32_t count, int32_t atblk)
 {
-       hammer_alist_config_t bl = live->config;
        int32_t blk = HAMMER_ALIST_BLOCK_NONE;
+       hammer_alist_config_t bl = live->config;
 
        KKASSERT((count | (count - 1)) == (count << 1) - 1);
 
-       if (bl && count < bl->bl_radix) {
+       if (bl && count <= bl->bl_radix) {
+               /*
+                * When skip is 1 we are at a leaf.  If we are the terminal
+                * allocator we use our native leaf functions and radix will
+                * be HAMMER_ALIST_BMAP_RADIX.  Otherwise we are a meta node
+                * which will chain to another allocator.
+                */
                if (bl->bl_skip == 1 && bl->bl_terminal) {
 #ifndef _KERNEL
                        KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
 #endif
-                       blk = hammer_alst_leaf_alloc_rev(
-                                   live->meta + 1, 0, count);
+                       blk = hammer_alst_leaf_alloc_fwd(
+                                   live->meta + 1, 0, count, atblk);
                } else {
-                       blk = hammer_alst_meta_alloc_rev(
+                       blk = hammer_alst_meta_alloc_fwd(
                                    live, live->meta + 1,
-                                   0, count, bl->bl_radix, bl->bl_skip);
+                                   0, count, bl->bl_radix, bl->bl_skip, atblk);
                }
                if (blk != HAMMER_ALIST_BLOCK_NONE)
                        live->meta->bm_alist_freeblks -= count;
@@ -349,24 +355,31 @@ hammer_alist_alloc_rev(hammer_alist_t live, int32_t count)
        return(blk);
 }
 
-#if 0
-
-/*
- * hammer_alist_alloc_from()
- *
- *     An extended version of hammer_alist_alloc() which locates free space
- *     starting at the specified block either forwards or backwards.
- *     HAMMER_ALIST_BLOCK_NONE is returned if space could not be allocated.
- *
- *     Note: when allocating from a particular point forwards space is never
- *     allocated behind that start point, and similarly when going backwards.
- */
 int32_t 
-hammer_alist_alloc_from(hammer_alist_t live, int32_t count, int32_t start)
+hammer_alist_alloc_rev(hammer_alist_t live, int32_t count, int32_t atblk)
 {
-}
+       hammer_alist_config_t bl = live->config;
+       int32_t blk = HAMMER_ALIST_BLOCK_NONE;
+
+       KKASSERT((count | (count - 1)) == (count << 1) - 1);
 
+       if (bl && count < bl->bl_radix) {
+               if (bl->bl_skip == 1 && bl->bl_terminal) {
+#ifndef _KERNEL
+                       KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
 #endif
+                       blk = hammer_alst_leaf_alloc_rev(
+                                   live->meta + 1, 0, count, atblk);
+               } else {
+                       blk = hammer_alst_meta_alloc_rev(
+                                   live, live->meta + 1,
+                                   0, count, bl->bl_radix, bl->bl_skip, atblk);
+               }
+               if (blk != HAMMER_ALIST_BLOCK_NONE)
+                       live->meta->bm_alist_freeblks -= count;
+       }
+       return(blk);
+}
 
 /*
  * alist_free()
@@ -397,6 +410,18 @@ hammer_alist_free(hammer_alist_t live, int32_t blkno, int32_t count)
        live->meta->bm_alist_freeblks += count;
 }
 
+int
+hammer_alist_isfull(hammer_alist_t live)
+{
+       return(live->meta->bm_alist_freeblks == 0);
+}
+
+int
+hammer_alist_isempty(hammer_alist_t live)
+{
+       return(live->meta->bm_alist_freeblks == live->config->bl_radix);
+}
+
 #ifdef ALIST_DEBUG
 
 /*
@@ -439,9 +464,11 @@ hammer_alist_print(hammer_alist_t live, int tab)
  */
 
 static int32_t
-hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan, int32_t blk, int count)
+hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan, int32_t blk,
+                          int count, int32_t atblk)
 {
        u_int32_t orig = scan->bm_bitmap;
+       int32_t saveblk = blk;
 
        /*
         * Optimize bitmap all-allocated case.  Also, count = 1
@@ -453,8 +480,13 @@ hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan, int32_t blk, int count)
                return(HAMMER_ALIST_BLOCK_NONE);
        }
 
+#if 0
        /*
         * Optimized code to allocate one bit out of the bitmap
+        *
+        * mask iterates e.g. 00001111 00000011 00000001
+        *
+        * mask starts at 00001111
         */
        if (count == 1) {
                u_int32_t mask;
@@ -474,6 +506,7 @@ hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan, int32_t blk, int count)
                scan->bm_bitmap &= ~(1 << r);
                return(blk + r);
        }
+#endif
 
        /*
         * non-optimized code to allocate N bits out of the bitmap.
@@ -494,18 +527,21 @@ hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan, int32_t blk, int count)
                mask = (u_int32_t)-1 >> n;
 
                for (j = 0; j <= n; j += count) {
-                       if ((orig & mask) == mask) {
+                       if ((orig & mask) == mask && blk >= atblk) {
                                scan->bm_bitmap &= ~mask;
-                               return(blk + j);
+                               return(blk);
                        }
                        mask = mask << count;
+                       blk += count;
                }
        }
 
        /*
-        * We couldn't allocate count in this subtree, update bighint.
+        * We couldn't allocate count in this subtree, update bighint if
+        * atblk didn't interfere with the hinting mechanism.
         */
-       scan->bm_bighint = count - 1;
+       if (saveblk >= atblk)
+               scan->bm_bighint = count - 1;
        return(HAMMER_ALIST_BLOCK_NONE);
 }
 
@@ -513,9 +549,11 @@ hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan, int32_t blk, int count)
  * This version allocates blocks in the reverse direction.
  */
 static int32_t
-hammer_alst_leaf_alloc_rev(hammer_almeta_t scan, int32_t blk, int count)
+hammer_alst_leaf_alloc_rev(hammer_almeta_t scan, int32_t blk,
+                          int count, int32_t atblk)
 {
        u_int32_t orig = scan->bm_bitmap;
+       int32_t saveblk;
 
        /*
         * Optimize bitmap all-allocated case.  Also, count = 1
@@ -527,6 +565,7 @@ hammer_alst_leaf_alloc_rev(hammer_almeta_t scan, int32_t blk, int count)
                return(HAMMER_ALIST_BLOCK_NONE);
        }
 
+#if 0
        /*
         * Optimized code to allocate one bit out of the bitmap
         */
@@ -548,6 +587,7 @@ hammer_alst_leaf_alloc_rev(hammer_almeta_t scan, int32_t blk, int count)
                scan->bm_bitmap &= ~(1 << r);
                return(blk + r);
        }
+#endif
 
        /*
         * non-optimized code to allocate N bits out of the bitmap.
@@ -568,20 +608,25 @@ hammer_alst_leaf_alloc_rev(hammer_almeta_t scan, int32_t blk, int count)
                u_int32_t mask;
 
                mask = ((u_int32_t)-1 >> n) << n;
+               blk += n;
+               saveblk = blk;
 
                for (j = n; j >= 0; j -= count) {
-                       if ((orig & mask) == mask) {
+                       if ((orig & mask) == mask && blk <= atblk) {
                                scan->bm_bitmap &= ~mask;
-                               return(blk + j);
+                               return(blk);
                        }
                        mask = mask >> count;
+                       blk -= count;
                }
        }
 
        /*
-        * We couldn't allocate count in this subtree, update bighint.
+        * We couldn't allocate count in this subtree, update bighint if
+        * atblk didn't interfere with it.
         */
-       scan->bm_bighint = count - 1;
+       if (saveblk <= atblk)
+               scan->bm_bighint = count - 1;
        return(HAMMER_ALIST_BLOCK_NONE);
 }
 
@@ -598,13 +643,14 @@ hammer_alst_leaf_alloc_rev(hammer_almeta_t scan, int32_t blk, int count)
 static int32_t
 hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
                           int32_t blk, int32_t count,
-                          int32_t radix, int skip
+                          int32_t radix, int skip, int32_t atblk
 ) {
        hammer_alist_config_t bl;
-       int i;
        u_int32_t mask;
        u_int32_t pmask;
+       int32_t saveblk;
        int next_skip;
+       int i;
 
        /*
         * ALL-ALLOCATED special case
@@ -631,17 +677,20 @@ hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
         */
        if (count >= radix) {
                int n = count / radix * 2;      /* number of bits */
+               int nd2 = n / 2;
                int j;
 
                mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n);
-               for (j = 0; j < HAMMER_ALIST_META_RADIX; j += n / 2) {
-                       if ((scan->bm_bitmap & mask) == mask) {
+               saveblk = blk;
+               for (j = 0; j < HAMMER_ALIST_META_RADIX; j += nd2) {
+                       if ((scan->bm_bitmap & mask) == mask && blk >= atblk) {
                                scan->bm_bitmap &= ~mask;
-                               return(blk + j * radix);
+                               return(blk);
                        }
                        mask <<= n;
+                       blk += radix * nd2;
                }
-               if (scan->bm_bighint >= count)
+               if (scan->bm_bighint >= count && saveblk >= atblk)
                        scan->bm_bighint = count >> 1;
                return(HAMMER_ALIST_BLOCK_NONE);
        }
@@ -650,6 +699,7 @@ hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
         * If the count is too big we couldn't allocate anything from a
         * recursion even if the sub-tree were entirely free.
         */
+       saveblk = blk;
        if (count > radix)
                goto failed;
 
@@ -667,21 +717,22 @@ hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
                for (i = 0; i < HAMMER_ALIST_META_RADIX; ++i) {
                        /*
                         * If the next layer is completely free then call
-                        * its init function to initialize it and mark it
-                        * partially free.
+                        * its init function to initialize it, then free
+                        * all of its blocks before trying to allocate from
+                        * it.
                         *
                         * bl_radix_init returns an error code or 0 on
                         * success.
                         */
-                       if ((scan->bm_bitmap & mask) == mask) {
-                               int32_t v;
-
-                               v = bl->bl_blocks - blk;
-                               if (v > radix)
-                                       v = radix;
-                               if (bl->bl_radix_init(live->info, blk, radix, v) == 0) {
+                       if ((scan->bm_bitmap & mask) == mask &&
+                           blk + radix > atblk) {
+                               if (bl->bl_radix_init(live->info, blk, radix) == 0) {
+                                       int32_t empty;
                                        scan->bm_bitmap &= ~mask;
                                        scan->bm_bitmap |= pmask;
+                                       bl->bl_radix_free(live->info, blk,
+                                                         radix, 0, radix,
+                                                         &empty);
                                }
                        }
 
@@ -691,15 +742,19 @@ hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
                         * it is completely full then clear both bits to
                         * propogate the condition.
                         */
-                       if ((scan->bm_bitmap & mask) == pmask) {
+                       if ((scan->bm_bitmap & mask) == pmask &&
+                           blk + radix > atblk) {
                                int32_t r;
                                int32_t full;
 
                                r = bl->bl_radix_alloc_fwd(live->info, blk,
-                                                          radix, count, &full);
+                                                          radix, count, atblk,
+                                                          &full);
                                if (r != HAMMER_ALIST_BLOCK_NONE) {
-                                       if (full)
+                                       if (full) {
                                                scan->bm_bitmap &= ~mask;
+                                               bl->bl_radix_destroy(live->info, blk, radix);
+                                       }
                                        return(r);
                                }
                        }
@@ -721,12 +776,18 @@ hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
                                 */
                                break;
                        }
+
+                       /*
+                        * Initialize bitmap if allocating from the all-free
+                        * case.
+                        */
                        if ((scan->bm_bitmap & mask) == mask) {
                                scan[i].bm_bitmap = (u_int32_t)-1;
                                scan[i].bm_bighint = radix;
                        }
 
-                       if (count <= scan[i].bm_bighint) {
+                       if (count <= scan[i].bm_bighint &&
+                           blk + radix > atblk) {
                                /*
                                 * count fits in object, recurse into the
                                 * next layer.  If the next_skip is 1 it
@@ -737,12 +798,12 @@ hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
 
                                if (next_skip == 1 && bl->bl_terminal) {
                                        r = hammer_alst_leaf_alloc_fwd(
-                                               &scan[i], blk, count);
+                                               &scan[i], blk, count, atblk);
                                } else {
                                        r = hammer_alst_meta_alloc_fwd(
                                                live, &scan[i],
                                                blk, count,
-                                               radix, next_skip);
+                                               radix, next_skip, atblk);
                                }
                                if (r != HAMMER_ALIST_BLOCK_NONE) {
                                        if (scan[i].bm_bitmap == 0) {
@@ -764,7 +825,7 @@ failed:
        /*
         * We couldn't allocate count in this subtree, update bighint.
         */
-       if (scan->bm_bighint >= count)
+       if (scan->bm_bighint >= count && saveblk >= atblk)
                scan->bm_bighint = count >> 1;
        return(HAMMER_ALIST_BLOCK_NONE);
 }
@@ -775,13 +836,14 @@ failed:
 static int32_t
 hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
                           int32_t blk, int32_t count,
-                          int32_t radix, int skip
+                          int32_t radix, int skip, int32_t atblk
 ) {
        hammer_alist_config_t bl;
        int i;
        int j;
        u_int32_t mask;
        u_int32_t pmask;
+       int32_t saveblk;
        int next_skip;
 
        /*
@@ -809,6 +871,7 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
         */
        if (count >= radix) {
                int n = count / radix * 2;      /* number of bits */
+               int nd2 = n / 2;                /* number of radi */
                int j;
 
                /*
@@ -816,14 +879,17 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
                 */
                mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n) <<
                        (HAMMER_ALIST_BMAP_RADIX - n);
-               for (j = HAMMER_ALIST_META_RADIX - n / 2; j >= 0; j -= n / 2) {
-                       if ((scan->bm_bitmap & mask) == mask) {
+               blk += (HAMMER_ALIST_META_RADIX - nd2) * radix;
+               saveblk = blk;
+               for (j = HAMMER_ALIST_META_RADIX - nd2; j >= 0; j -= nd2) {
+                       if ((scan->bm_bitmap & mask) == mask && blk <= atblk) {
                                scan->bm_bitmap &= ~mask;
-                               return(blk + j * radix);
+                               return(blk);
                        }
                        mask >>= n;
+                       blk -= nd2 * radix;
                }
-               if (scan->bm_bighint >= count)
+               if (scan->bm_bighint >= count && saveblk <= atblk)
                        scan->bm_bighint = count >> 1;
                return(HAMMER_ALIST_BLOCK_NONE);
        }
@@ -832,8 +898,10 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
         * If the count is too big we couldn't allocate anything from a
         * recursion even if the sub-tree were entirely free.
         */
-       if (count > radix)
-               goto failed;
+       if (count > radix) {
+               saveblk = atblk;        /* make it work for the conditional */
+               goto failed;            /* at the failed label */
+       }
 
        if (skip == 1) {
                /*
@@ -843,6 +911,7 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
                mask = 0xC0000000;
                pmask = 0x40000000;
                blk += radix * HAMMER_ALIST_META_RADIX - radix;
+               saveblk = blk;
 
                for (i = 0; i < HAMMER_ALIST_META_RADIX; ++i) {
                        /*
@@ -850,15 +919,14 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
                         * its init function to initialize it and mark it
                         * partially free.
                         */
-                       if ((scan->bm_bitmap & mask) == mask) {
-                               int32_t v;
-
-                               v = bl->bl_blocks - blk;
-                               if (v > radix)
-                                       v = radix;
-                               if (bl->bl_radix_init(live->info, blk, radix, v) == 0) {
+                       if ((scan->bm_bitmap & mask) == mask && blk <= atblk) {
+                               if (bl->bl_radix_init(live->info, blk, radix) == 0) {
+                                       int32_t empty;
                                        scan->bm_bitmap &= ~mask;
                                        scan->bm_bitmap |= pmask;
+                                       bl->bl_radix_free(live->info, blk,
+                                                         radix, 0, radix,
+                                                         &empty);
                                }
                        }
 
@@ -868,15 +936,18 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
                         * it is completely full then clear both bits to
                         * propogate the condition.
                         */
-                       if ((scan->bm_bitmap & mask) == pmask) {
+                       if ((scan->bm_bitmap & mask) == pmask && blk <= atblk) {
                                int32_t r;
                                int32_t full;
 
                                r = bl->bl_radix_alloc_rev(live->info, blk,
-                                                          radix, count, &full);
+                                                          radix, count,
+                                                          atblk, &full);
                                if (r != HAMMER_ALIST_BLOCK_NONE) {
-                                       if (full)
+                                       if (full) {
                                                scan->bm_bitmap &= ~mask;
+                                               bl->bl_radix_destroy(live->info, blk, radix);
+                                       }
                                        return(r);
                                }
                        }
@@ -895,9 +966,11 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
                 */
                next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
                j = 0;
-               for (i = 1; i <= skip; i += next_skip) {
-                       if (scan[i].bm_bighint == (int32_t)-1)
+               for (i = 1; i < skip; i += next_skip) {
+                       if (scan[i].bm_bighint == (int32_t)-1) {
+                               KKASSERT(j != 0);
                                break;
+                       }
                        blk += radix;
                        j += 2;
                }
@@ -906,6 +979,7 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
                mask = 0x00000003 << j;
                pmask = 0x00000001 << j;
                i -= next_skip;
+               saveblk = blk;
 
                while (i >= 1) {
                        /*
@@ -921,19 +995,19 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
                         * Handle various count cases.  Bighint may be too
                         * large but is never too small.
                         */
-                       if (count <= scan[i].bm_bighint) {
+                       if (count <= scan[i].bm_bighint && blk <= atblk) {
                                /*
                                 * count fits in object
                                 */
                                int32_t r;
                                if (next_skip == 1 && bl->bl_terminal) {
                                        r = hammer_alst_leaf_alloc_rev(
-                                               &scan[i], blk, count);
+                                               &scan[i], blk, count, atblk);
                                } else {
                                        r = hammer_alst_meta_alloc_rev(
                                                live, &scan[i],
                                                blk, count,
-                                               radix, next_skip);
+                                               radix, next_skip, atblk);
                                }
                                if (r != HAMMER_ALIST_BLOCK_NONE) {
                                        if (scan[i].bm_bitmap == 0) {
@@ -944,12 +1018,6 @@ hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
                                        }
                                        return(r);
                                }
-                       } else if (count > radix) {
-                               /*
-                                * count does not fit in object even if it were
-                                * completely free.
-                                */
-                               break;
                        }
                        blk -= radix;
                        mask >>= 2;
@@ -964,7 +1032,7 @@ failed:
         * Since we are restricted to powers of 2, the next highest count
         * we might be able to allocate is (count >> 1).
         */
-       if (scan->bm_bighint >= count)
+       if (scan->bm_bighint >= count && saveblk <= atblk)
                scan->bm_bighint = count >> 1;
        return(HAMMER_ALIST_BLOCK_NONE);
 }
@@ -1059,22 +1127,39 @@ hammer_alst_meta_free(hammer_alist_t live, hammer_almeta_t scan,
 
                        if (freeBlk == blk && count >= radix) {
                                /*
-                                * All-free case, no need to update sub-tree
+                                * When the sub-tree becomes entirely free
+                                * we have to destroy it if it was previously
+                                * partially allocated.  If it was previously
+                                * fully allocated it has already been
+                                * destroyed (or never inited in the first
+                                * place).
                                 */
+                               int32_t empty;
+
+                               if ((scan->bm_bitmap & mask) != 0) {
+                                       bl->bl_radix_free(live->info, blk, radix,
+                                                         freeBlk - blk, v, &empty);
+                                       bl->bl_radix_destroy(live->info, blk, radix);
+                               }
                                scan->bm_bitmap |= mask;
                                scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
                                /* XXX bighint not being set properly */
                        } else {
                                /*
-                                * Recursion case
+                                * Recursion case.  If freeing from an 
+                                * all-allocated state init the sub-tree
+                                * first.
                                 */
                                int32_t empty;
 
-                               bl->bl_radix_free(live->info, freeBlk, v,
-                                                 radix, blk, &empty);
+                               if ((scan->bm_bitmap & mask) == 0)
+                                       bl->bl_radix_init(live->info, blk, radix);
+                               bl->bl_radix_free(live->info, blk, radix,
+                                                 freeBlk - blk, v, &empty);
                                if (empty) {
                                        scan->bm_bitmap |= mask;
                                        scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
+                                       bl->bl_radix_destroy(live->info, blk, radix);
                                        /* XXX bighint not being set properly */
                                } else {
                                        scan->bm_bitmap |= pmask;
@@ -1366,62 +1451,76 @@ static int32_t layer_radix = -1;
 
 static
 int
-debug_radix_init(void *info, int32_t blk, int32_t radix, int32_t count)
+debug_radix_init(void *info, int32_t blk, int32_t radix)
 {
        hammer_alist_t layer;
        int layer_no = blk / layer_radix;
 
-       printf("lower layer: init (%04x,%d) for %d blks\n", blk, radix, count);
+       printf("lower layer: init (%04x,%d)\n", blk, radix);
        KKASSERT(layers[layer_no] == NULL);
-       layer = layers[layer_no] = hammer_alist_create(count, 1, NULL); 
-       hammer_alist_free(layer, 0, count);
+       layer = layers[layer_no] = hammer_alist_create(radix, 1, NULL); 
+       return(0);
+}
+
+static
+int
+debug_radix_destroy(void *info, int32_t blk, int32_t radix)
+{
+       hammer_alist_t layer;
+       int layer_no = blk / layer_radix;
+
+       printf("lower layer: destroy (%04x,%d)\n", blk, radix);
+       layer = layers[layer_no];
+       KKASSERT(layer != NULL);
+       hammer_alist_destroy(layer, NULL);
+       layers[layer_no] = NULL;
        return(0);
 }
 
+
 static
 int32_t
 debug_radix_alloc_fwd(void *info, int32_t blk, int32_t radix,
-                     int32_t count, int32_t *fullp)
+                     int32_t count, int32_t atblk, int32_t *fullp)
 {
        hammer_alist_t layer = layers[blk / layer_radix];
+       int32_t r;
 
-       return(hammer_alist_alloc(layer, count));
+       r = hammer_alist_alloc_fwd(layer, count, atblk - blk);
+       *fullp = (layer->meta->bm_alist_freeblks == 0);
+       if (r != HAMMER_ALIST_BLOCK_NONE)
+               r += blk;
+       return(r);
 }
 
 static
 int32_t
 debug_radix_alloc_rev(void *info, int32_t blk, int32_t radix,
-                     int32_t count, int32_t *fullp)
+                     int32_t count, int32_t atblk, int32_t *fullp)
 {
        hammer_alist_t layer = layers[blk / layer_radix];
+       int32_t r;
 
-       blk = hammer_alist_alloc_rev(layer, count);
+       r = hammer_alist_alloc_rev(layer, count, atblk - blk);
        *fullp = (layer->meta->bm_alist_freeblks == 0);
-       if (*fullp) {
-               hammer_alist_destroy(layer, NULL);
-               layers[blk / layer_radix] = NULL;
-       }
-       return(blk);
+       if (r != HAMMER_ALIST_BLOCK_NONE)
+               r += blk;
+       return(r);
 }
 
 static
 void
-debug_radix_free(void *info, int32_t freeBlk, int32_t count,
-                int32_t radix, int32_t blk, int32_t *emptyp)
+debug_radix_free(void *info, int32_t blk, int32_t radix,
+                int32_t base_blk, int32_t count, int32_t *emptyp)
 {
        int layer_no = blk / layer_radix;
        hammer_alist_t layer = layers[layer_no];
 
        if (layer == NULL) {
-               /*
-                * XXX layer_radix isn't correct if the total number
-                * of blocks only partially fills this layer.  Don't
-                * worry about it.
-                */
                layer = hammer_alist_create(layer_radix, 1, NULL); 
                layers[layer_no] = layer;
        }
-       hammer_alist_free(layer, freeBlk - blk, count);
+       hammer_alist_free(layer, base_blk, count);
        *emptyp = (layer->meta->bm_alist_freeblks == layer_radix);
 }
 
@@ -1478,6 +1577,7 @@ main(int ac, char **av)
                size, live->config->bl_radix / layer_radix, layer_radix);
 
        live->config->bl_radix_init = debug_radix_init;
+       live->config->bl_radix_destroy = debug_radix_destroy;
        live->config->bl_radix_alloc_fwd = debug_radix_alloc_fwd;
        live->config->bl_radix_alloc_rev = debug_radix_alloc_rev;
        live->config->bl_radix_free = debug_radix_free;
@@ -1489,6 +1589,7 @@ main(int ac, char **av)
                char buf[1024];
                int32_t da = 0;
                int32_t count = 0;
+               int32_t atblk;
                int32_t blk;
 
                kprintf("%d/%d> ",
@@ -1501,16 +1602,17 @@ main(int ac, char **av)
                        hammer_alist_print(live, 0);
                        break;
                case 'a':
-                       if (sscanf(buf + 1, "%d", &count) == 1) {
-                               blk = hammer_alist_alloc(live, count);
+                       if (sscanf(buf + 1, "%d %d", &count, &atblk) >= 1) {
+                               blk = hammer_alist_alloc_fwd(live, count, atblk);
                                kprintf("    R=%04x\n", blk);
                        } else {
                                kprintf("?\n");
                        }
                        break;
                case 'r':
-                       if (sscanf(buf + 1, "%d", &count) == 1) {
-                               blk = hammer_alist_alloc_rev(live, count);
+                       atblk = HAMMER_ALIST_BLOCK_MAX;
+                       if (sscanf(buf + 1, "%d %d", &count, &atblk) >= 1) {
+                               blk = hammer_alist_alloc_rev(live, count, atblk);
                                kprintf("    R=%04x\n", blk);
                        } else {
                                kprintf("?\n");
index 95fb544..2486fe2 100644 (file)
@@ -31,7 +31,7 @@
  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  * 
- * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.h,v 1.1 2007/10/12 18:57:45 dillon Exp $
+ * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.h,v 1.2 2007/10/16 18:16:42 dillon Exp $
  */
 
 /*
@@ -79,14 +79,16 @@ typedef struct hammer_alist_config {
        int32_t bl_skip;        /* starting skip for linear layout */
        int32_t bl_rootblks;    /* meta-blocks allocated for tree */
        int32_t bl_terminal;    /* terminal alist, else layer recursion */
-       int     (*bl_radix_init)(void *info, int32_t blk, int32_t radix,
-                                       int32_t count);
+       int     (*bl_radix_init)(void *info, int32_t blk, int32_t radix);
+       int     (*bl_radix_destroy)(void *info, int32_t blk, int32_t radix);
        int32_t (*bl_radix_alloc_fwd)(void *info, int32_t blk, int32_t radix,
-                                       int32_t count, int32_t *fullp);
+                                       int32_t count, int32_t atblk,
+                                       int32_t *fullp);
        int32_t (*bl_radix_alloc_rev)(void *info, int32_t blk, int32_t radix,
-                                       int32_t count, int32_t *fullp);
-       void    (*bl_radix_free)(void *info, int32_t freeBlk, int32_t count,
-                                       int32_t radix, int32_t blk,
+                                       int32_t count, int32_t atblk,
+                                       int32_t *fullp);
+       void    (*bl_radix_free)(void *info, int32_t blk, int32_t radix,
+                                       int32_t base_blk, int32_t count,
                                        int32_t *emptyp);
        void    (*bl_radix_print)(void *info, int32_t blk, int32_t radix,
                                        int tab);
@@ -104,6 +106,7 @@ typedef struct hammer_alist_live {
 #define HAMMER_ALIST_META_RADIX        (sizeof(int32_t) * 4)   /* 16 */
 #define HAMMER_ALIST_BMAP_RADIX        (sizeof(int32_t) * 8)   /* 32 */
 #define HAMMER_ALIST_BLOCK_NONE        ((int32_t)-1)
+#define HAMMER_ALIST_BLOCK_MAX ((int32_t)0x7fffffff)
 
 /*
  * Hard-code some pre-calculated constants for managing varying numbers
@@ -116,3 +119,18 @@ typedef struct hammer_alist_live {
 #define HAMMER_ALIST_METAELMS_4K_1LYR  139
 #define HAMMER_ALIST_METAELMS_4K_2LYR  275
 
+/*
+ * Function library support available to kernel and userland
+ */
+void hammer_alist_template(hammer_alist_config_t bl, int32_t blocks,
+                           int32_t base_radix, int32_t maxmeta);
+void hammer_alist_init(hammer_alist_t live);
+int32_t hammer_alist_alloc(hammer_alist_t live, int32_t count);
+int32_t hammer_alist_alloc_fwd(hammer_alist_t live,
+                          int32_t count, int32_t atblk);
+int32_t hammer_alist_alloc_rev(hammer_alist_t live,
+                          int32_t count, int32_t atblk);
+int hammer_alist_isfull(hammer_alist_t live);
+int hammer_alist_isempty(hammer_alist_t live);
+void hammer_alist_free(hammer_alist_t live, int32_t blkno, int32_t count);
+
index b9eb214..21804eb 100644 (file)
@@ -31,7 +31,7 @@
  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  * 
- * $DragonFly: src/sys/vfs/hammer/hammer_disk.h,v 1.1 2007/10/12 18:57:45 dillon Exp $
+ * $DragonFly: src/sys/vfs/hammer/hammer_disk.h,v 1.2 2007/10/16 18:16:42 dillon Exp $
  */
 
 #ifndef _SYS_UUID_H_
@@ -79,6 +79,7 @@ typedef u_int64_t hammer_tid_t;
 
 #define HAMMER_FSBUF_HEAD_SIZE 128
 #define HAMMER_FSBUF_MAXBLKS   256
+#define HAMMER_FSBUF_BLKMASK   (HAMMER_FSBUF_MAXBLKS - 1)
 #define HAMMER_FSBUF_METAELMS  HAMMER_ALIST_METAELMS_256_1LYR  /* 11 */
 
 struct hammer_fsbuf_head {
@@ -148,7 +149,7 @@ typedef struct hammer_fsbuf_head *hammer_fsbuf_head_t;
 
 struct hammer_volume_ondisk {
        struct hammer_fsbuf_head head;
-       int64_t vol_beg;        /* byte offset of first cluster in volume */
+       int64_t vol_beg;        /* byte offset of first cl/supercl in volume */
        int64_t vol_end;        /* byte offset of volume EOF */
        int64_t vol_locked;     /* reserved clusters are >= this offset */
 
@@ -160,12 +161,12 @@ struct hammer_volume_ondisk {
        int32_t vol_count;      /* number of volumes making up FS */
 
        u_int32_t vol_version;  /* version control information */
-       u_int32_t vol_segsize;  /* cluster size power of 2, 512M max */
+       u_int32_t vol_reserved01;
        u_int32_t vol_flags;    /* volume flags */
        u_int32_t vol_rootvol;  /* which volume is the root volume? */
 
        int32_t vol_clsize;     /* cluster size (same for all volumes) */
-       u_int32_t vol_reserved05;
+       int32_t vol_nclusters;
        u_int32_t vol_reserved06;
        u_int32_t vol_reserved07;
 
@@ -189,8 +190,8 @@ struct hammer_volume_ondisk {
         * can handle 32768 clusters).
         */
        union {
-               hammer_almeta_t super[HAMMER_VOL_METAELMS_2LYR];
-               hammer_almeta_t normal[HAMMER_VOL_METAELMS_1LYR];
+               struct hammer_almeta    super[HAMMER_VOL_METAELMS_2LYR];
+               struct hammer_almeta    normal[HAMMER_VOL_METAELMS_1LYR];
        } vol_almeta;
        u_int32_t       vol0_bitmap[1024];
 };
@@ -214,6 +215,7 @@ struct hammer_volume_ondisk {
  * but the layer is only enabled if the volume exceeds 2TB.
  */
 #define HAMMER_SUPERCL_METAELMS                HAMMER_ALIST_METAELMS_32K_1LYR
+#define HAMMER_SCL_MAXCLUSTERS         HAMMER_VOL_MAXCLUSTERS
 
 struct hammer_supercl_ondisk {
        struct hammer_fsbuf_head head;
@@ -221,7 +223,7 @@ struct hammer_supercl_ondisk {
        uuid_t  vol_fstype;     /* identify filesystem type - sanity check */
        int32_t reserved[1024];
 
-       hammer_almeta_t scl_meta[HAMMER_SUPERCL_METAELMS];
+       struct hammer_almeta    scl_meta[HAMMER_SUPERCL_METAELMS];
 };
 
 /*
@@ -258,6 +260,7 @@ struct hammer_supercl_ondisk {
 #define HAMMER_CLU_MAXBUFFERS          4096
 #define HAMMER_CLU_MASTER_METAELMS     HAMMER_ALIST_METAELMS_4K_1LYR
 #define HAMMER_CLU_SLAVE_METAELMS      HAMMER_ALIST_METAELMS_4K_2LYR
+#define HAMMER_CLU_MAXBYTES            (HAMMER_CLU_MAXBUFFERS * HAMMER_BUFSIZE)
 
 struct hammer_cluster_ondisk {
        struct hammer_fsbuf_head head;
@@ -281,9 +284,9 @@ struct hammer_cluster_ondisk {
        u_int32_t clu_reserved06;
        u_int32_t clu_reserved07;
 
-       int32_t idx_data;       /* data append point (byte offset) */
-       int32_t idx_index;      /* index append point (byte offset) */
-       int32_t idx_record;     /* record prepend point (byte offset) */
+       int32_t idx_data;       /* data append point (element no) */
+       int32_t idx_index;      /* index append point (element no) */
+       int32_t idx_record;     /* record prepend point (element no) */
        u_int32_t idx_reserved03;
 
        /* 
@@ -309,10 +312,10 @@ struct hammer_cluster_ondisk {
 
        u_int64_t synchronized_rec_id;
 
-       hammer_almeta_t clu_master_meta[HAMMER_CLU_MASTER_METAELMS];
-       hammer_almeta_t clu_btree_meta[HAMMER_CLU_SLAVE_METAELMS];
-       hammer_almeta_t clu_record_meta[HAMMER_CLU_SLAVE_METAELMS];
-       hammer_almeta_t clu_mdata_meta[HAMMER_CLU_SLAVE_METAELMS];
+       struct hammer_almeta    clu_master_meta[HAMMER_CLU_MASTER_METAELMS];
+       struct hammer_almeta    clu_btree_meta[HAMMER_CLU_SLAVE_METAELMS];
+       struct hammer_almeta    clu_record_meta[HAMMER_CLU_SLAVE_METAELMS];
+       struct hammer_almeta    clu_mdata_meta[HAMMER_CLU_SLAVE_METAELMS];
 };
 
 /*
@@ -510,6 +513,7 @@ struct hammer_fsbuf_recs {
 
 #define HAMMER_DATA_SIZE       (HAMMER_BUFSIZE - sizeof(struct hammer_fsbuf_head))
 #define HAMMER_DATA_BLKSIZE    64
+#define HAMMER_DATA_BLKMASK    (HAMMER_DATA_BLKSIZE-1)
 #define HAMMER_DATA_NODES      (HAMMER_DATA_SIZE / HAMMER_DATA_BLKSIZE)
 
 struct hammer_fsbuf_data {
@@ -517,6 +521,17 @@ struct hammer_fsbuf_data {
        u_int8_t                data[HAMMER_DATA_NODES][HAMMER_DATA_BLKSIZE];
 };
 
+/*
+ * Filesystem buffer rollup
+ */
+union hammer_fsbuf_ondisk {
+       struct hammer_fsbuf_head        head;
+       struct hammer_fsbuf_btree       btree;
+       struct hammer_fsbuf_recs        record;
+       struct hammer_fsbuf_data        data;
+};
+
+typedef union hammer_fsbuf_ondisk *hammer_fsbuf_ondisk_t;
 
 /*
  * HAMMER UNIX Attribute data
@@ -549,17 +564,3 @@ union hammer_data {
        struct hammer_inode_data inode;
 };
 
-
-/*
- * Function library support available to kernel and userland
- */
-void hammer_alist_template(hammer_alist_config_t bl, int32_t blocks,
-                          int32_t base_radix, int32_t maxmeta);
-void hammer_alist_init(hammer_alist_config_t bl, hammer_almeta_t meta);
-int32_t hammer_alist_alloc(hammer_alist_t live, int32_t count);
-int32_t hammer_alist_alloc_rev(hammer_alist_t live, int32_t count);
-#if 0
-int32_t hammer_alist_alloc_from(hammer_alist_t live, int32_t cnt, int32_t beg);
-#endif
-void hammer_alist_free(hammer_alist_t live, int32_t blkno, int32_t count);
-