Primary header file infrastructure and A-list implementation for the
authorMatthew Dillon <dillon@dragonflybsd.org>
Wed, 10 Oct 2007 19:37:25 +0000 (19:37 +0000)
committerMatthew Dillon <dillon@dragonflybsd.org>
Wed, 10 Oct 2007 19:37:25 +0000 (19:37 +0000)
HAMMER VFS.

sys/vfs/hammer/Makefile [new file with mode: 0644]
sys/vfs/hammer/hammer.h [new file with mode: 0644]
sys/vfs/hammer/hammer.txt [new file with mode: 0644]
sys/vfs/hammer/hammer_alist.c [new file with mode: 0644]
sys/vfs/hammer/hammer_btree.h [new file with mode: 0644]
sys/vfs/hammer/hammer_mount.h [new file with mode: 0644]
sys/vfs/hammer/hammerfs.h [new file with mode: 0644]

diff --git a/sys/vfs/hammer/Makefile b/sys/vfs/hammer/Makefile
new file mode 100644 (file)
index 0000000..d4a2e5d
--- /dev/null
@@ -0,0 +1,8 @@
+#
+# $DragonFly: src/sys/vfs/hammer/Makefile,v 1.1 2007/10/10 19:37:25 dillon Exp $
+
+KMOD=  hammer
+SRCS=  hammer_vfsops.c hammer_vnops.c hammer_inode.c hammer_btree.c
+NOMAN=
+
+.include <bsd.kmod.mk>
diff --git a/sys/vfs/hammer/hammer.h b/sys/vfs/hammer/hammer.h
new file mode 100644 (file)
index 0000000..4599e46
--- /dev/null
@@ -0,0 +1,150 @@
+/*
+ * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
+ * 
+ * This code is derived from software contributed to The DragonFly Project
+ * by Matthew Dillon <dillon@backplane.com>
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * 
+ * $DragonFly: src/sys/vfs/hammer/hammer.h,v 1.1 2007/10/10 19:37:25 dillon Exp $
+ */
+/*
+ * This header file contains structures used internally by the HAMMERFS
+ * implementation.  See hammerfs.h for on-disk structures.
+ */
+
+#include <sys/tree.h>
+#include <sys/malloc.h>
+#include "hammerfs.h"
+#include "hammer_mount.h"
+
+#if defined(_KERNEL) || defined(_KERNEL_STRUCTURES)
+
+MALLOC_DECLARE(M_HAMMER);
+
+/*
+ * Key structure used for custom RB tree inode lookups.  This prototypes
+ * the function hammer_ino_rb_tree_RB_LOOKUP_INFO(root, info).
+ */
+typedef struct hammer_inode_info {
+       u_int64_t       obj_id;         /* (key) object identifier */
+       hammer_tid_t    obj_asof;       /* (key) snapshot transid or 0 */
+} *hammer_inode_info_t;
+
+/*
+ * Key and caching structure used for HAMMER B-Tree lookups.
+ */
+struct hammer_btree_info {
+       struct hammer_base_elm key;
+};
+
+/*
+ * Structures used to internally represent an inode
+ */
+struct hammer_ino_rb_tree;
+struct hammer_inode;
+RB_HEAD(hammer_ino_rb_tree, hammer_inode);
+RB_PROTOTYPEX(hammer_ino_rb_tree, INFO, hammer_inode, rb_node,
+            hammer_ino_rb_compare, hammer_inode_info_t);
+
+struct hammer_inode {
+       RB_ENTRY(hammer_inode) rb_node;
+       u_int64_t       obj_id;         /* (key) object identifier */
+       hammer_tid_t    obj_asof;       /* (key) snapshot transid or 0 */
+       struct hammer_mount *hmp;
+};
+
+/*
+ * Structures used to internally represent a volume and a cluster
+ */
+
+struct hammer_volume;
+struct hammer_cluster;
+RB_HEAD(hammer_vol_rb_tree, hammer_volume);
+RB_HEAD(hammer_clu_rb_tree, hammer_cluster);
+
+RB_PROTOTYPE2(hammer_vol_rb_tree, hammer_volume, rb_node,
+             hammer_vol_rb_compare, int32_t);
+RB_PROTOTYPE2(hammer_clu_rb_tree, hammer_cluster, rb_node,
+             hammer_clu_rb_compare, int32_t);
+
+struct hammer_volume {
+       RB_ENTRY(hammer_volume) rb_node;
+       struct hammer_clu_rb_tree rb_clus_root;
+       struct hammer_volume_ondisk *ondisk;
+       int32_t vol_no;
+       int32_t vol_clsize;
+       int64_t cluster_base;   /* base offset of cluster 0 */
+       char *vol_name;
+       struct vnode *devvp;
+       struct hammer_mount *hmp;
+};
+
+struct hammer_cluster {
+       RB_ENTRY(hammer_cluster) rb_node;
+       struct hammer_cluster_ondisk *ondisk;
+       struct hammer_volume *volume;
+       int32_t clu_no;
+};
+
+/*
+ * Internal hammer mount data structure
+ */
+struct hammer_mount {
+       struct mount *mp;
+       struct vnode *rootvp;
+       struct hammer_ino_rb_tree rb_inos_root;
+       struct hammer_vol_rb_tree rb_vols_root;
+       struct hammer_volume *rootvol;
+       struct hammer_cluster *rootcl;
+       uuid_t  fsid;
+};
+
+
+#endif
+
+#if defined(_KERNEL)
+
+extern struct vop_ops hammer_vnode_vops;
+int    hammer_vop_inactive(struct vop_inactive_args *);
+int    hammer_vop_reclaim(struct vop_reclaim_args *);
+int    hammer_vfs_vget(struct mount *mp, ino_t ino, struct  vnode **vpp);
+
+int    hammer_unload_inode(struct hammer_inode *inode, void *data __unused);
+int    hammer_unload_volume(struct hammer_volume *volume, void *data __unused);
+int    hammer_load_volume(struct hammer_mount *hmp, const char *volname);
+struct hammer_cluster *hammer_load_cluster(struct hammer_mount *hmp,
+                               struct hammer_volume *volume, int clu_no,
+                               int *errorp);
+
+int    hammer_btree_lookup(struct hammer_mount *hmp,
+                               struct hammer_btree_info *info);
+
+
+#endif
+
diff --git a/sys/vfs/hammer/hammer.txt b/sys/vfs/hammer/hammer.txt
new file mode 100644 (file)
index 0000000..61dc9dc
--- /dev/null
@@ -0,0 +1,158 @@
+$DragonFly: src/sys/vfs/hammer/Attic/hammer.txt,v 1.1 2007/10/10 19:37:25 dillon Exp $
+
+                              Hammer Filesystem
+
+(I) General Storage Abstraction
+
+    HAMMER uses a basic 16K filesystem buffer for all I/O.  Buffers are
+    collected into clusters, cluster are collected into volumes, and a
+    single HAMMER filesystem may span multiple volumes.
+
+    HAMMER maintains a small hinted radix tree for block management in
+    each layer.  A small radix tree in the volume header manages cluster
+    allocations within a volume, one in the cluster header manages buffer
+    allocations within a cluster, and most buffers (pure data buffers
+    excepted) will embed a small tree to manage item allocations within
+    the buffer.
+
+    Volumes are typically specified as disk partitions, with one volume
+    designated as the root volume containing the root cluster.  The root
+    cluster does not need to be contained in volume 0 nor does it have to
+    be located at any particular offset.
+
+    Data can be migrated on a cluster-by-cluster or volume-by-volume basis
+    and any given volume may be expanded or contracted while the filesystem
+    is live.   Whole volumes can be added and (with appropriate data
+    migration) removed.
+
+    HAMMER's storage management limits it to 32768 volumes, 32768 clusters
+    per volume, and 32768 16K filesystem buffers per cluster.   A volume
+    is thus limited to 16TB and a HAMMER filesystem as a whole is limited
+    to 524288TB.  HAMMER's on-disk structures are designed to allow future
+    expansion through expansion of these limits.  In particular, the volume
+    id is intended to be expanded to a full 32 bits in the future and using
+    a larger buffer size will also greatly increase the cluster and volume
+    size limitations by increasing the number of elements the buffer-
+    restricted radix trees can manage.
+
+    HAMMER breaks all of its information down into objects and records.
+    Records have a creation and deletion transaction id which allows HAMMER
+    to maintain a historical store.  Information is only physically deleted
+    based on the data retention policy.  Those portions of the data retention
+    policy affecting near-term modifications may be acted upon by the live
+    filesystem but all historical vacuuming is handled by a helper process.
+
+    All information in a HAMMER filesystem is CRCd to detect corruption.
+
+(II) Filesystem Object Topology
+
+    The objects and records making up a HAMMER filesystem is organized into
+    a single, unified B-Tree.  Each cluster maintains a B-Tree of the
+    records contained in that cluster and a unified B-Tree is constructed by
+    linking clusters together.  HAMMER issues PUSH and PULL operations
+    internally to open up space for new records and to balance the global
+    B-Tree.  These operations may have the side effect of allocating
+    new clusters or freeing clusters which become unused.
+
+    B-Tree operations tend to be limited to a single cluster.  That is,
+    the B-Tree insertion and deletion algorithm is not extended to the
+    whole unified tree.  If insufficient space exists in a cluster HAMMER
+    will allocate a new cluster, PUSH a portion of the existing
+    cluster's record store to the new cluster, and link the existing
+    cluster's B-Tree to the new one.
+
+    Because B-Tree operations tend to be restricted and because HAMMER tries
+    to avoid balancing clusters in the critical path, HAMMER employs a
+    background process to keep the topology as a whole in balance.  One
+    side effect of this is that HAMMER is fairly loose when it comes to
+    inserting new clusters into the topology.
+
+    HAMMER objects revolve around the concept of an object identifier.
+    The obj_id is a 64 bit quantity which uniquely identifies a filesystem
+    object for the entire life of the filesystem.  This uniqueness allows
+    backups and mirrors to retain varying amounts of filesystem history by
+    removing any possibility of conflict through identifier reuse.  HAMMER
+    typically iterates object identifiers sequentially and expects to never
+    run out.  At a creation rate of 100,000 objects per second it would
+    take HAMMER around 6 million years to run out of identifier space.
+    The characteristics of the HAMMER obj_id also allow HAMMER to operate
+    in a multi-master clustered environment.
+
+    A filesystem object is made up of records.  Each record references a
+    variable-length store of related data, a 64 bit key, and a creation
+    and deletion transaction id which is indexed along with the key.
+
+    HAMMER utilizes a 64 bit key to index all records.  Regular files use
+    the base data offset of the record as the key while directories use a
+    namekey hash as the key and store one directory entry per record.  For
+    all intents and purposes a directory can store an unlimited number of
+    files. 
+
+    HAMMER is also capable of associating any number of out-of-band
+    attributes with a filesystem object using a separate key space.  This
+    key space may be used for extended attributes, ACLs, and anything else
+    the user desires.
+
+(III) Access to historical information
+
+    A HAMMER filesystem can be mounted with an as-of date to access a
+    snapshot of the system.  Snapshots do not have to be explicitly taken
+    but are instead based on the retention policy you specify for any
+    given HAMMER filesystem.  It is also possible to access individual files
+    or directories (and their contents) using an as-of extension on the
+    file name.
+
+    HAMMER uses the transaction ids stored in records to present a snapshot
+    view of the filesystem as-of any time in the past, with a granularity
+    based on the retention policy chosen by the system administrator. 
+    feature also effectively implements file versioning.
+
+(IV) Mirrors and Backups
+
+    HAMMER is organized in a way that allows an information stream to be
+    generated for mirroring and backup purposes.  This stream includes all
+    historical information available in the source.  No queueing is required
+    so there is no limit to the number of mirrors or backups you can have
+    and no limit to how long any given mirror or backup can be taken offline.
+    Resynchronization of the stream is not considered to be an expensive
+    operation.
+
+    Mirrors and backups are maintained logically, not physically, and may
+    have their own, independant retention polcies.  For example, your live
+    filesystem could have a fairly rough retention policy, even none at all,
+    then be streamed to an on-site backup and from there to an off-site
+    backup, each with different retention policies.
+
+(V) Transactions and Recovery
+
+    HAMMER implement an instant-mount capability and will recover information
+    on a cluster-by-cluster basis as it is being accessed.
+
+    HAMMER numbers each record it lays down and stores a synchronization
+    point in the cluster header.  Clusters are synchronously marked 'open'
+    when undergoing modification.  If HAMMER encounters a cluster which is
+    unexpectedly marked open it will perform a recovery operation on the
+    cluster and throw away any records beyond the synchronization point.
+
+    HAMMER supports a userland transactional facility.  Userland can query
+    the current (filesystem wide) transaction id, issue numerous operations
+    and on recovery can tell HAMMER to revert all records with a greater
+    transaction id for any particular set of files.  Multiple userland
+    applications can use this feature simultaniously as long as the files
+    they are accessing do not overlap.  It is also possible for userland
+    to set up an ordering dependancy and maintain completely asynchronous
+    operation while still being able to guarentee recovery to a fairly
+    recent transaction id.
+
+(VI) Database files
+
+    HAMMER uses 64 bit keys internally and makes key-based files directly
+    available to userland.  Key-based files are not regular files and do not
+    operate using a normal data offset space.
+
+    You cannot copy a database file using a regular file copier.  The
+    file type will not be S_IFREG but instead will be S_IFDB.   The file
+    must be opened with O_DATABASE.  Reads which normally seek the file
+    forward will instead iterate through the records and lseek/qseek can
+    be used to acquire or set the key prior to the read/write operation.
+
diff --git a/sys/vfs/hammer/hammer_alist.c b/sys/vfs/hammer/hammer_alist.c
new file mode 100644 (file)
index 0000000..d469c1b
--- /dev/null
@@ -0,0 +1,1185 @@
+/*
+ * HAMMER_ALIST.C -
+ *
+ * Bitmap allocator/deallocator, using a radix tree with hinting.
+ * Unlimited-size allocations, power-of-2 only, power-of-2 aligned results
+ * only.  This module has been separated from the generic kernel module and
+ * written specifically for embedding in HAMMER storage structures.
+ * 
+ * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
+ * 
+ * This code is derived from software contributed to The DragonFly Project
+ * by Matthew Dillon <dillon@backplane.com>
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * 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.1 2007/10/10 19:37:25 dillon Exp $
+ */
+/*
+ * This module implements a generic allocator through the use of a hinted
+ * radix tree.  All allocations must be in powers of 2 and will return
+ * similarly aligned results.  The radix tree typically recurses within
+ * a memory buffer and then continues its recursion by chaining to other
+ * memory buffers, creating a seemless whole capable of managing any amount
+ * of storage.
+ *
+ * The radix tree is layed out recursively using a linear array.  Each meta
+ * node is immediately followed (layed out sequentially in memory) by
+ * HAMMER_ALIST_META_RADIX lower level nodes.  This is a recursive structure
+ * but one that can be easily scanned through a very simple 'skip'
+ * calculation.
+ *
+ * The radix tree supports an early-termination optimization which
+ * effectively allows us to efficiently mix large and small allocations
+ * with a single abstraction.  The address space can be partitioned
+ * arbitrarily without adding much in the way of additional meta-storage
+ * for the allocator.
+ *
+ * This code can be compiled stand-alone for debugging.
+ */
+
+#ifdef _KERNEL
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/lock.h>
+#include <sys/kernel.h>
+#include <sys/malloc.h>
+#include <vm/vm.h>
+#include <vm/vm_object.h>
+#include <vm/vm_kern.h>
+#include <vm/vm_extern.h>
+#include <vm/vm_page.h>
+
+#include "hammerfs.h"
+
+#else
+
+#ifndef ALIST_NO_DEBUG
+#define ALIST_DEBUG
+#endif
+
+#include <sys/types.h>
+#include <stdio.h>
+#include <assert.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdarg.h>
+
+#define kmalloc(a,b,c) malloc(a)
+#define kfree(a,b)     free(a)
+#define kprintf                printf
+#define KKASSERT(exp)  assert(exp)
+struct malloc_type;
+
+#include "hammerfs.h"
+
+void panic(const char *ctl, ...);
+
+#endif
+
+/*
+ * static support functions
+ */
+
+static int32_t hammer_alst_leaf_alloc_fwd(hammer_almeta_t *scan,
+                                       int32_t blk, int count);
+static int32_t hammer_alst_meta_alloc_fwd(hammer_almeta_t *scan,
+                                       int32_t blk, int32_t count,
+                                       int32_t radix, int skip);
+static int32_t hammer_alst_leaf_alloc_rev(hammer_almeta_t *scan,
+                                       int32_t blk, int count);
+static int32_t hammer_alst_meta_alloc_rev(hammer_almeta_t *scan,
+                                       int32_t blk, int32_t count,
+                                       int32_t radix, int skip);
+static void hammer_alst_leaf_free(hammer_almeta_t *scan,
+                                       int32_t relblk, int count);
+static void hammer_alst_meta_free(hammer_almeta_t *scan,
+                                       int32_t freeBlk, int32_t count, 
+                                       int32_t radix, int skip, int32_t blk);
+static int32_t hammer_alst_radix_init(hammer_almeta_t *scan,
+                                       int32_t radix, int skip, int32_t count);
+#ifdef ALIST_DEBUG
+static void    hammer_alst_radix_print(hammer_almeta_t *scan,
+                                       int32_t blk,
+                                       int32_t radix, int skip, int tab);
+#endif
+
+/*
+ * Initialize an alist for use.  The alist will initially be marked
+ * all-allocated so the caller must free the portion it wishes to manage.
+ */
+void
+hammer_alist_template(hammer_alist_t bl, int blocks, int maxmeta)
+{
+       int radix;
+       int skip = 0;
+
+       /*
+        * Calculate radix and skip field used for scanning.
+        */
+       radix = HAMMER_ALIST_BMAP_RADIX;
+
+       while (radix < blocks) {
+               radix *= HAMMER_ALIST_META_RADIX;
+               skip = (skip + 1) * HAMMER_ALIST_META_RADIX;
+       }
+
+       bzero(bl, sizeof(*bl));
+
+       bl->bl_blocks = blocks;
+       bl->bl_radix = radix;
+       bl->bl_skip = skip;
+       bl->bl_rootblks = 1 +
+           hammer_alst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks);
+       KKASSERT(bl->bl_rootblks <= maxmeta);
+
+#if defined(ALIST_DEBUG)
+       kprintf(
+               "ALIST representing %d blocks (%d MB of swap)"
+               ", requiring %dK (%d bytes) of ram\n",
+               bl->bl_blocks,
+               bl->bl_blocks * 4 / 1024,
+               (bl->bl_rootblks * sizeof(hammer_almeta_t) + 1023) / 1024,
+               (bl->bl_rootblks * sizeof(hammer_almeta_t))
+       );
+       kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
+#endif
+}
+
+void
+hammer_alist_init(hammer_alist_t bl, hammer_almeta_t *meta)
+{
+       hammer_alst_radix_init(meta, bl->bl_radix, bl->bl_skip, bl->bl_blocks);
+}
+
+#if !defined(_KERNEL) && defined(ALIST_DEBUG)
+
+/*
+ * hammer_alist_create()       (userland only)
+ *
+ *     create a alist capable of handling up to the specified number of
+ *     blocks.  blocks must be greater then 0
+ *
+ *     The smallest alist consists of a single leaf node capable of 
+ *     managing HAMMER_ALIST_BMAP_RADIX blocks.
+ */
+
+hammer_alist_t 
+hammer_alist_create(int32_t blocks, struct malloc_type *mtype,
+                   hammer_almeta_t **metap)
+{
+       hammer_alist_t bl;
+       hammer_almeta_t *meta;
+       int radix;
+       int skip = 0;
+       int rootblks;
+       size_t metasize;
+
+       /*
+        * Calculate radix and skip field used for scanning.
+        */
+       radix = HAMMER_ALIST_BMAP_RADIX;
+
+       while (radix < blocks) {
+               radix *= HAMMER_ALIST_META_RADIX;
+               skip = (skip + 1) * HAMMER_ALIST_META_RADIX;
+       }
+
+       rootblks = 1 + hammer_alst_radix_init(NULL, radix, skip, blocks);
+       metasize = sizeof(struct hammer_almeta) * rootblks;
+       bl = kmalloc(sizeof(struct hammer_alist), mtype, M_WAITOK);
+       meta = kmalloc(metasize, mtype, M_WAITOK);
+
+       bzero(bl, sizeof(*bl));
+       bzero(meta, metasize);
+
+       bl->bl_blocks = blocks;
+       bl->bl_radix = radix;
+       bl->bl_skip = skip;
+       bl->bl_rootblks = rootblks;
+
+#if defined(ALIST_DEBUG)
+       kprintf(
+               "ALIST representing %d blocks (%d MB of swap)"
+               ", requiring %dK (%d bytes) of ram\n",
+               bl->bl_blocks,
+               bl->bl_blocks * 4 / 1024,
+               (bl->bl_rootblks * sizeof(hammer_almeta_t) + 1023) / 1024,
+               (bl->bl_rootblks * sizeof(hammer_almeta_t))
+       );
+       kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
+#endif
+       hammer_alst_radix_init(meta, bl->bl_radix, bl->bl_skip, blocks);
+
+       *metap = meta;
+       return(bl);
+}
+
+void
+hammer_alist_destroy(hammer_alist_t bl, struct malloc_type *mtype)
+{
+       kfree(bl, mtype);
+}
+
+#endif
+
+/*
+ * hammer_alist_alloc()
+ *
+ *     Reserve space in the block bitmap.  Return the base of a contiguous
+ *     region or HAMMER_ALIST_BLOCK_NONE if space could not be allocated.
+ */
+
+int32_t 
+hammer_alist_alloc(hammer_alist_t bl, hammer_almeta_t *meta, int32_t count)
+{
+       int32_t blk = HAMMER_ALIST_BLOCK_NONE;
+
+       KKASSERT((count | (count - 1)) == (count << 1) - 1);
+
+       if (bl && count < bl->bl_radix) {
+               if (bl->bl_radix == HAMMER_ALIST_BMAP_RADIX) {
+                       blk = hammer_alst_leaf_alloc_fwd(meta, 0, count);
+               } else {
+                       blk = hammer_alst_meta_alloc_fwd(
+                                   meta, 0, count, bl->bl_radix, bl->bl_skip);
+               }
+               if (blk != HAMMER_ALIST_BLOCK_NONE)
+                       bl->bl_free -= count;
+       }
+       return(blk);
+}
+
+int32_t 
+hammer_alist_alloc_rev(hammer_alist_t bl, hammer_almeta_t *meta, int32_t count)
+{
+       int32_t blk = HAMMER_ALIST_BLOCK_NONE;
+
+       KKASSERT((count | (count - 1)) == (count << 1) - 1);
+
+       if (bl && count < bl->bl_radix) {
+               if (bl->bl_radix == HAMMER_ALIST_BMAP_RADIX) {
+                       blk = hammer_alst_leaf_alloc_rev(meta, 0, count);
+               } else {
+                       blk = hammer_alst_meta_alloc_rev(
+                                   meta, 0, count, bl->bl_radix, bl->bl_skip);
+               }
+               if (blk != HAMMER_ALIST_BLOCK_NONE)
+                       bl->bl_free -= 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 bl, hammer_almeta_t *meta,
+                       int32_t count, int32_t start, int flags)
+
+{
+}
+
+#endif
+
+/*
+ * alist_free()
+ *
+ *     Free up space in the block bitmap.  Return the base of a contiguous
+ *     region.  Panic if an inconsistancy is found.
+ *
+ *     Unlike allocations, there are no alignment requirements for blkno or
+ *     count when freeing blocks.
+ */
+
+void 
+hammer_alist_free(hammer_alist_t bl, hammer_almeta_t *meta,
+                 int32_t blkno, int32_t count)
+{
+       if (bl) {
+               KKASSERT(blkno + count <= bl->bl_blocks);
+               if (bl->bl_radix == HAMMER_ALIST_BMAP_RADIX)
+                       hammer_alst_leaf_free(meta, blkno, count);
+               else
+                       hammer_alst_meta_free(meta, blkno, count,
+                                             bl->bl_radix, bl->bl_skip, 0);
+               bl->bl_free += count;
+       }
+}
+
+#ifdef ALIST_DEBUG
+
+/*
+ * alist_print()    - dump radix tree
+ */
+
+void
+hammer_alist_print(hammer_alist_t bl, hammer_almeta_t *meta)
+{
+       kprintf("ALIST {\n");
+       hammer_alst_radix_print(meta, 0, bl->bl_radix, bl->bl_skip, 4);
+       kprintf("}\n");
+}
+
+#endif
+
+/************************************************************************
+ *                       ALLOCATION SUPPORT FUNCTIONS                  *
+ ************************************************************************
+ *
+ *     These support functions do all the actual work.  They may seem 
+ *     rather longish, but that's because I've commented them up.  The
+ *     actual code is straight forward.
+ *
+ */
+
+/*
+ * hammer_alist_leaf_alloc_fwd()
+ *
+ *     Allocate at a leaf in the radix tree (a bitmap).
+ *
+ *     This is the core of the allocator and is optimized for the 1 block
+ *     and the HAMMER_ALIST_BMAP_RADIX block allocation cases.  Other cases
+ *     are somewhat slower.  The 1 block allocation case is log2 and extremely
+ *     quick.
+ */
+
+static int32_t
+hammer_alst_leaf_alloc_fwd(hammer_almeta_t *scan, int32_t blk, int count)
+{
+       u_int32_t orig = scan->bm_bitmap;
+
+       /*
+        * Optimize bitmap all-allocated case.  Also, count = 1
+        * case assumes at least 1 bit is free in the bitmap, so
+        * we have to take care of this case here.
+        */
+       if (orig == 0) {
+               scan->bm_bighint = 0;
+               return(HAMMER_ALIST_BLOCK_NONE);
+       }
+
+       /*
+        * Optimized code to allocate one bit out of the bitmap
+        */
+       if (count == 1) {
+               u_int32_t mask;
+               int j = HAMMER_ALIST_BMAP_RADIX/2;
+               int r = 0;
+
+               mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2);
+
+               while (j) {
+                       if ((orig & mask) == 0) {
+                           r += j;
+                           orig >>= j;
+                       }
+                       j >>= 1;
+                       mask >>= j;
+               }
+               scan->bm_bitmap &= ~(1 << r);
+               return(blk + r);
+       }
+
+       /*
+        * non-optimized code to allocate N bits out of the bitmap.
+        * The more bits, the faster the code runs.  It will run
+        * the slowest allocating 2 bits, but since there aren't any
+        * memory ops in the core loop (or shouldn't be, anyway),
+        * you probably won't notice the difference.
+        *
+        * Similar to the blist case, the alist code also requires
+        * allocations to be power-of-2 sized and aligned to the
+        * size of the allocation, which simplifies the algorithm.
+        */
+       {
+               int j;
+               int n = HAMMER_ALIST_BMAP_RADIX - count;
+               u_int32_t mask;
+
+               mask = (u_int32_t)-1 >> n;
+
+               for (j = 0; j <= n; j += count) {
+                       if ((orig & mask) == mask) {
+                               scan->bm_bitmap &= ~mask;
+                               return(blk + j);
+                       }
+                       mask = mask << count;
+               }
+       }
+
+       /*
+        * We couldn't allocate count in this subtree, update bighint.
+        */
+       scan->bm_bighint = count - 1;
+       return(HAMMER_ALIST_BLOCK_NONE);
+}
+
+/*
+ * 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)
+{
+       u_int32_t orig = scan->bm_bitmap;
+
+       /*
+        * Optimize bitmap all-allocated case.  Also, count = 1
+        * case assumes at least 1 bit is free in the bitmap, so
+        * we have to take care of this case here.
+        */
+       if (orig == 0) {
+               scan->bm_bighint = 0;
+               return(HAMMER_ALIST_BLOCK_NONE);
+       }
+
+       /*
+        * Optimized code to allocate one bit out of the bitmap
+        */
+       if (count == 1) {
+               u_int32_t mask;
+               int j = HAMMER_ALIST_BMAP_RADIX/2;
+               int r = HAMMER_ALIST_BMAP_RADIX - 1;
+
+               mask = ~((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2));
+
+               while (j) {
+                       if ((orig & mask) == 0) {
+                           r -= j;
+                           orig <<= j;
+                       }
+                       j >>= 1;
+                       mask <<= j;
+               }
+               scan->bm_bitmap &= ~(1 << r);
+               return(blk + r);
+       }
+
+       /*
+        * non-optimized code to allocate N bits out of the bitmap.
+        * The more bits, the faster the code runs.  It will run
+        * the slowest allocating 2 bits, but since there aren't any
+        * memory ops in the core loop (or shouldn't be, anyway),
+        * you probably won't notice the difference.
+        *
+        * Similar to the blist case, the alist code also requires
+        * allocations to be power-of-2 sized and aligned to the
+        * size of the allocation, which simplifies the algorithm.
+        *
+        * initial mask if count == 2:  1100....0000
+        */
+       {
+               int j;
+               int n = HAMMER_ALIST_BMAP_RADIX - count;
+               u_int32_t mask;
+
+               mask = ((u_int32_t)-1 >> n) << n;
+
+               for (j = n; j >= 0; j -= count) {
+                       if ((orig & mask) == mask) {
+                               scan->bm_bitmap &= ~mask;
+                               return(blk + j);
+                       }
+                       mask = mask >> count;
+               }
+       }
+
+       /*
+        * We couldn't allocate count in this subtree, update bighint.
+        */
+       scan->bm_bighint = count - 1;
+       return(HAMMER_ALIST_BLOCK_NONE);
+}
+
+/*
+ * hammer_alist_meta_alloc_fwd()
+ *
+ *     Allocate at a meta in the radix tree.
+ *
+ *     Attempt to allocate at a meta node.  If we can't, we update
+ *     bighint and return a failure.  Updating bighint optimize future
+ *     calls that hit this node.  We have to check for our collapse cases
+ *     and we have a few optimizations strewn in as well.
+ */
+static int32_t
+hammer_alst_meta_alloc_fwd(hammer_almeta_t *scan, int32_t blk, int32_t count,
+                          int32_t radix, int skip
+) {
+       int i;
+       u_int32_t mask;
+       u_int32_t pmask;
+       int next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
+
+       /*
+        * ALL-ALLOCATED special case
+        */
+       if (scan->bm_bitmap == 0)  {
+               scan->bm_bighint = 0;
+               return(HAMMER_ALIST_BLOCK_NONE);
+       }
+
+       radix /= HAMMER_ALIST_META_RADIX;
+
+       /*
+        * Radix now represents each bitmap entry for this meta node.  If
+        * the number of blocks being allocated can be fully represented,
+        * we allocate directly out of this meta node.
+        *
+        * Meta node bitmaps use 2 bits per block.
+        *
+        *      00      ALL-ALLOCATED
+        *      01      PARTIALLY-FREE/PARTIALLY-ALLOCATED
+        *      10      (RESERVED)
+        *      11      ALL-FREE
+        */
+       if (count >= radix) {
+               int n = count / radix * 2;      /* number of bits */
+               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) {
+                               scan->bm_bitmap &= ~mask;
+                               return(blk + j * radix);
+                       }
+                       mask <<= n;
+               }
+               if (scan->bm_bighint >= count)
+                       scan->bm_bighint = count >> 1;
+               return(HAMMER_ALIST_BLOCK_NONE);
+       }
+
+       /*
+        * If not we have to recurse.
+        */
+       mask = 0x00000003;
+       pmask = 0x00000001;
+       for (i = 1; i <= skip; i += next_skip) {
+               if (scan[i].bm_bighint == (int32_t)-1) {
+                       /* 
+                        * Terminator
+                        */
+                       break;
+               }
+               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) {
+                       /*
+                        * count fits in object
+                        */
+                       int32_t r;
+                       if (next_skip == 1) {
+                               r = hammer_alst_leaf_alloc_fwd(
+                                       &scan[i], blk, count);
+                       } else {
+                               r = hammer_alst_meta_alloc_fwd(
+                                       &scan[i], blk, count,
+                                       radix, next_skip - 1);
+                       }
+                       if (r != HAMMER_ALIST_BLOCK_NONE) {
+                               if (scan[i].bm_bitmap == 0) {
+                                       scan->bm_bitmap &= ~mask;
+                               } else {
+                                       scan->bm_bitmap &= ~mask;
+                                       scan->bm_bitmap |= pmask;
+                               }
+                               return(r);
+                       }
+               } else if (count > radix) {
+                       /*
+                        * count does not fit in object even if it were
+                        * completely free.
+                        */
+                       break;
+               }
+               blk += radix;
+               mask <<= 2;
+               pmask <<= 2;
+       }
+
+       /*
+        * We couldn't allocate count in this subtree, update bighint.
+        */
+       if (scan->bm_bighint >= count)
+               scan->bm_bighint = count >> 1;
+       return(HAMMER_ALIST_BLOCK_NONE);
+}
+
+/*
+ * This version allocates blocks in the reverse direction.
+ */
+static int32_t
+hammer_alst_meta_alloc_rev(hammer_almeta_t *scan, int32_t blk, int32_t count,
+                          int32_t radix, int skip
+) {
+       int i;
+       int j;
+       u_int32_t mask;
+       u_int32_t pmask;
+       int next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
+
+       /*
+        * ALL-ALLOCATED special case
+        */
+       if (scan->bm_bitmap == 0)  {
+               scan->bm_bighint = 0;
+               return(HAMMER_ALIST_BLOCK_NONE);
+       }
+
+       radix /= HAMMER_ALIST_META_RADIX;
+
+       /*
+        * Radix now represents each bitmap entry for this meta node.  If
+        * the number of blocks being allocated can be fully represented,
+        * we allocate directly out of this meta node.
+        *
+        * Meta node bitmaps use 2 bits per block.
+        *
+        *      00      ALL-ALLOCATED
+        *      01      PARTIALLY-FREE/PARTIALLY-ALLOCATED
+        *      10      (RESERVED)
+        *      11      ALL-FREE
+        */
+       if (count >= radix) {
+               int n = count / radix * 2;      /* number of bits */
+               int j;
+
+               /*
+                * Initial mask if e.g. n == 2:  1100....0000
+                */
+               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) {
+                               scan->bm_bitmap &= ~mask;
+                               return(blk + j * radix);
+                       }
+                       mask >>= n;
+               }
+               if (scan->bm_bighint >= count)
+                       scan->bm_bighint = count >> 1;
+               return(HAMMER_ALIST_BLOCK_NONE);
+       }
+
+       /*
+        * If not we have to recurse.  Since we are going in the reverse
+        * direction we need an extra loop to determine if there is a
+        * terminator, then run backwards.
+        *
+        * This is a little weird but we do not want to overflow the
+        * mask/pmask in the loop.
+        */
+       j = 0;
+       for (i = 1; i <= skip; i += next_skip) {
+               if (scan[i].bm_bighint == (int32_t)-1)
+                       break;
+               blk += radix;
+               j += 2;
+       }
+       blk -= radix;
+       j -= 2;
+       mask = 0x00000003 << j;
+       pmask = 0x00000001 << j;
+       i -= next_skip;
+
+       while (i >= 1) {
+               /*
+                * Initialize the bitmap in the child 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;
+               }
+
+               /*
+                * Handle various count cases.  Bighint may be too large but
+                * is never too small.
+                */
+               if (count <= scan[i].bm_bighint) {
+                       /*
+                        * count fits in object
+                        */
+                       int32_t r;
+                       if (next_skip == 1) {
+                               r = hammer_alst_leaf_alloc_rev(
+                                       &scan[i], blk, count);
+                       } else {
+                               r = hammer_alst_meta_alloc_rev(
+                                       &scan[i], blk, count,
+                                       radix, next_skip - 1);
+                       }
+                       if (r != HAMMER_ALIST_BLOCK_NONE) {
+                               if (scan[i].bm_bitmap == 0) {
+                                       scan->bm_bitmap &= ~mask;
+                               } else {
+                                       scan->bm_bitmap &= ~mask;
+                                       scan->bm_bitmap |= pmask;
+                               }
+                               return(r);
+                       }
+               } else if (count > radix) {
+                       /*
+                        * count does not fit in object even if it were
+                        * completely free.
+                        */
+                       break;
+               }
+               blk -= radix;
+               mask >>= 2;
+               pmask >>= 2;
+               i -= next_skip;
+       }
+
+       /*
+        * We couldn't allocate count in this subtree, update bighint.
+        */
+       if (scan->bm_bighint >= count)
+               scan->bm_bighint = count >> 1;
+       return(HAMMER_ALIST_BLOCK_NONE);
+}
+
+/*
+ * BLST_LEAF_FREE()
+ *
+ *     Free allocated blocks from leaf bitmap.  The allocation code is
+ *     restricted to powers of 2, the freeing code is not.
+ */
+static void
+hammer_alst_leaf_free(
+       hammer_almeta_t *scan,
+       int32_t blk,
+       int count
+) {
+       /*
+        * free some data in this bitmap
+        *
+        * e.g.
+        *      0000111111111110000
+        *          \_________/\__/
+        *              v        n
+        */
+       int n = blk & (HAMMER_ALIST_BMAP_RADIX - 1);
+       u_int32_t mask;
+
+       mask = ((u_int32_t)-1 << n) &
+           ((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - count - n));
+
+       if (scan->bm_bitmap & mask)
+               panic("hammer_alst_radix_free: freeing free block");
+       scan->bm_bitmap |= mask;
+
+       /*
+        * We could probably do a better job here.  We are required to make
+        * bighint at least as large as the biggest contiguous block of 
+        * data.  If we just shoehorn it, a little extra overhead will
+        * be incured on the next allocation (but only that one typically).
+        */
+       scan->bm_bighint = HAMMER_ALIST_BMAP_RADIX;
+}
+
+/*
+ * BLST_META_FREE()
+ *
+ *     Free allocated blocks from radix tree meta info.
+ *
+ *     This support routine frees a range of blocks from the bitmap.
+ *     The range must be entirely enclosed by this radix node.  If a
+ *     meta node, we break the range down recursively to free blocks
+ *     in subnodes (which means that this code can free an arbitrary
+ *     range whereas the allocation code cannot allocate an arbitrary
+ *     range).
+ */
+
+static void 
+hammer_alst_meta_free(
+       hammer_almeta_t *scan, 
+       int32_t freeBlk,
+       int32_t count,
+       int32_t radix, 
+       int skip,
+       int32_t blk
+) {
+       int next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
+       u_int32_t mask;
+       u_int32_t pmask;
+       int i;
+
+       /*
+        * Break the free down into its components.  Because it is so easy
+        * to implement, frees are not limited to power-of-2 sizes.
+        *
+        * Each block in a meta-node bitmap takes two bits.
+        */
+       radix /= HAMMER_ALIST_META_RADIX;
+
+       i = (freeBlk - blk) / radix;
+       blk += i * radix;
+       mask = 0x00000003 << (i * 2);
+       pmask = 0x00000001 << (i * 2);
+
+       i = i * next_skip + 1;
+
+       while (i <= skip && blk < freeBlk + count) {
+               int32_t v;
+
+               v = blk + radix - freeBlk;
+               if (v > count)
+                       v = count;
+
+               if (scan->bm_bighint == (int32_t)-1)
+                       panic("hammer_alst_meta_free: freeing unexpected range");
+
+               if (freeBlk == blk && count >= radix) {
+                       /*
+                        * All-free case, no need to update sub-tree
+                        */
+                       scan->bm_bitmap |= mask;
+                       scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
+                       /*XXX*/
+               } else {
+                       /*
+                        * Recursion case
+                        */
+                       if (next_skip == 1)
+                               hammer_alst_leaf_free(&scan[i], freeBlk, v);
+                       else
+                               hammer_alst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk);
+                       if (scan[i].bm_bitmap == (u_int32_t)-1)
+                               scan->bm_bitmap |= mask;
+                       else
+                               scan->bm_bitmap |= pmask;
+                       if (scan->bm_bighint < scan[i].bm_bighint)
+                           scan->bm_bighint = scan[i].bm_bighint;
+               }
+               mask <<= 2;
+               pmask <<= 2;
+               count -= v;
+               freeBlk += v;
+               blk += radix;
+               i += next_skip;
+       }
+}
+
+/*
+ * BLST_RADIX_INIT()
+ *
+ *     Initialize our meta structures and bitmaps and calculate the exact
+ *     amount of space required to manage 'count' blocks - this space may
+ *     be considerably less then the calculated radix due to the large
+ *     RADIX values we use.
+ */
+
+static int32_t 
+hammer_alst_radix_init(hammer_almeta_t *scan, int32_t radix,
+                      int skip, int32_t count)
+{
+       int i;
+       int next_skip;
+       int32_t memindex = 0;
+       u_int32_t mask;
+       u_int32_t pmask;
+
+       /*
+        * Leaf node
+        */
+       if (radix == HAMMER_ALIST_BMAP_RADIX) {
+               if (scan) {
+                       scan->bm_bighint = 0;
+                       scan->bm_bitmap = 0;
+               }
+               return(memindex);
+       }
+
+       /*
+        * Meta node.  If allocating the entire object we can special
+        * case it.  However, we need to figure out how much memory
+        * is required to manage 'count' blocks, so we continue on anyway.
+        */
+
+       if (scan) {
+               scan->bm_bighint = 0;
+               scan->bm_bitmap = 0;
+       }
+
+       radix /= HAMMER_ALIST_META_RADIX;
+       next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
+       mask = 0x00000003;
+       pmask = 0x00000001;
+
+       for (i = 1; i <= skip; i += next_skip) {
+               if (count >= radix) {
+                       /*
+                        * Allocate the entire object
+                        */
+                       memindex = i + hammer_alst_radix_init(
+                           ((scan) ? &scan[i] : NULL),
+                           radix,
+                           next_skip - 1,
+                           radix
+                       );
+                       count -= radix;
+                       /* already marked as wholely allocated */
+               } else if (count > 0) {
+                       /*
+                        * Allocate a partial object
+                        */
+                       memindex = i + hammer_alst_radix_init(
+                           ((scan) ? &scan[i] : NULL),
+                           radix,
+                           next_skip - 1,
+                           count
+                       );
+                       count = 0;
+
+                       /*
+                        * Mark as partially allocated
+                        */
+                       if (scan)
+                               scan->bm_bitmap |= pmask;
+               } else {
+                       /*
+                        * Add terminator and break out
+                        */
+                       if (scan)
+                               scan[i].bm_bighint = (int32_t)-1;
+                       /* already marked as wholely allocated */
+                       break;
+               }
+               mask <<= 2;
+               pmask <<= 2;
+       }
+       if (memindex < i)
+               memindex = i;
+       return(memindex);
+}
+
+#ifdef ALIST_DEBUG
+
+static void    
+hammer_alst_radix_print(hammer_almeta_t *scan, int32_t blk,
+                       int32_t radix, int skip, int tab)
+{
+       int i;
+       int next_skip;
+       int lastState = 0;
+       u_int32_t mask;
+
+       if (radix == HAMMER_ALIST_BMAP_RADIX) {
+               kprintf(
+                   "%*.*s(%04x,%d): bitmap %08x big=%d\n", 
+                   tab, tab, "",
+                   blk, radix,
+                   scan->bm_bitmap,
+                   scan->bm_bighint
+               );
+               return;
+       }
+
+       if (scan->bm_bitmap == 0) {
+               kprintf(
+                   "%*.*s(%04x,%d) ALL ALLOCATED\n",
+                   tab, tab, "",
+                   blk,
+                   radix
+               );
+               return;
+       }
+       if (scan->bm_bitmap == (u_int32_t)-1) {
+               kprintf(
+                   "%*.*s(%04x,%d) ALL FREE\n",
+                   tab, tab, "",
+                   blk,
+                   radix
+               );
+               return;
+       }
+
+       kprintf(
+           "%*.*s(%04x,%d): subtree (%d) bitmap=%08x big=%d {\n",
+           tab, tab, "",
+           blk, radix,
+           radix,
+           scan->bm_bitmap,
+           scan->bm_bighint
+       );
+
+       radix /= HAMMER_ALIST_META_RADIX;
+       next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
+       tab += 4;
+       mask = 0x00000003;
+
+       for (i = 1; i <= skip; i += next_skip) {
+               if (scan[i].bm_bighint == (int32_t)-1) {
+                       kprintf(
+                           "%*.*s(%04x,%d): Terminator\n",
+                           tab, tab, "",
+                           blk, radix
+                       );
+                       lastState = 0;
+                       break;
+               }
+               if ((scan->bm_bitmap & mask) == mask) {
+                       kprintf(
+                           "%*.*s(%04x,%d): ALL FREE\n",
+                           tab, tab, "",
+                           blk, radix
+                       );
+               } else if ((scan->bm_bitmap & mask) == 0) {
+                       kprintf(
+                           "%*.*s(%04x,%d): ALL ALLOCATED\n",
+                           tab, tab, "",
+                           blk, radix
+                       );
+               } else {
+                       hammer_alst_radix_print(
+                           &scan[i],
+                           blk,
+                           radix,
+                           next_skip - 1,
+                           tab
+                       );
+               }
+               blk += radix;
+               mask <<= 2;
+       }
+       tab -= 4;
+
+       kprintf(
+           "%*.*s}\n",
+           tab, tab, ""
+       );
+}
+
+#endif
+
+#ifdef ALIST_DEBUG
+
+int
+main(int ac, char **av)
+{
+       int size = 1024;
+       int i;
+       hammer_alist_t bl;
+       hammer_almeta_t *meta = NULL;
+
+       for (i = 1; i < ac; ++i) {
+               const char *ptr = av[i];
+               if (*ptr != '-') {
+                       size = strtol(ptr, NULL, 0);
+                       continue;
+               }
+               ptr += 2;
+               fprintf(stderr, "Bad option: %s\n", ptr - 2);
+               exit(1);
+       }
+       bl = hammer_alist_create(size, NULL, &meta);
+       hammer_alist_free(bl, meta, 0, size);
+
+       for (;;) {
+               char buf[1024];
+               int32_t da = 0;
+               int32_t count = 0;
+               int32_t blk;
+
+               kprintf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix);
+               fflush(stdout);
+               if (fgets(buf, sizeof(buf), stdin) == NULL)
+                       break;
+               switch(buf[0]) {
+               case 'p':
+                       hammer_alist_print(bl, meta);
+                       break;
+               case 'a':
+                       if (sscanf(buf + 1, "%d", &count) == 1) {
+                               blk = hammer_alist_alloc(bl, meta, count);
+                               kprintf("    R=%04x\n", blk);
+                       } else {
+                               kprintf("?\n");
+                       }
+                       break;
+               case 'r':
+                       if (sscanf(buf + 1, "%d", &count) == 1) {
+                               blk = hammer_alist_alloc_rev(bl, meta, count);
+                               kprintf("    R=%04x\n", blk);
+                       } else {
+                               kprintf("?\n");
+                       }
+                       break;
+               case 'f':
+                       if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
+                               hammer_alist_free(bl, meta, da, count);
+                       } else {
+                               kprintf("?\n");
+                       }
+                       break;
+               case '?':
+               case 'h':
+                       puts(
+                           "p          -print\n"
+                           "a %d       -allocate\n"
+                           "r %d       -allocate reverse\n"
+                           "f %x %d    -free\n"
+                           "h/?        -help"
+                       );
+                       break;
+               default:
+                       kprintf("?\n");
+                       break;
+               }
+       }
+       return(0);
+}
+
+void
+panic(const char *ctl, ...)
+{
+       __va_list va;
+
+       __va_start(va, ctl);
+       vfprintf(stderr, ctl, va);
+       fprintf(stderr, "\n");
+       __va_end(va);
+       exit(1);
+}
+
+#endif
+
diff --git a/sys/vfs/hammer/hammer_btree.h b/sys/vfs/hammer/hammer_btree.h
new file mode 100644 (file)
index 0000000..4da07e4
--- /dev/null
@@ -0,0 +1,143 @@
+/*
+ * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
+ * 
+ * This code is derived from software contributed to The DragonFly Project
+ * by Matthew Dillon <dillon@backplane.com>
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * 
+ * $DragonFly: src/sys/vfs/hammer/hammer_btree.h,v 1.1 2007/10/10 19:37:25 dillon Exp $
+ */
+
+/*
+ * HAMMER B-Tree index
+ *
+ * rec_type is the record type for a leaf node or an extended record type
+ * for internal btree nodes and cluster references.
+ *
+ * A B-Tree diving down into a new cluster will have two B-Tree elements
+ * indicating the full sub-range stored in that cluster.  These elements
+ * will match the elements stored in the cluster header.
+ */
+
+/*
+ * Common base for all B-Tree element types (40 bytes)
+ */
+struct hammer_base_elm {
+       int64_t obj_id;         /* 00 object record is associated with */
+       int64_t key;            /* 08 indexing key (offset or namekey) */
+
+       hammer_tid_t create_tid; /* 10 transaction id for record creation */
+       hammer_tid_t delete_tid; /* 18 transaction id for record update/del */
+
+       u_int16_t rec_type;     /* 20 */
+       u_int16_t obj_type;     /* 22 (only if rec_type is an inode) */
+       u_int32_t reserved01;   /* 24 */
+                               /* 28 */
+};
+
+/*
+ * Internal B-Tree element (40 + 16 = 56 bytes)
+ */
+struct hammer_internal_elm {
+       struct hammer_base_elm base;
+       int32_t subtree_offset;
+       u_int32_t reserved01;
+       u_int32_t reserved02;
+       u_int32_t reserved03;
+
+};
+
+/*
+ * Leaf B-Tree element (40 + 16 = 56 bytes)
+ */
+struct hammer_leaf_elm {
+       struct hammer_base_elm base;
+       int32_t rec_offset;
+       int32_t data_offset;
+       int32_t data_len;
+       u_int32_t data_crc;
+};
+
+/*
+ * Leaf Cluster-reference B-Tree element (40 + 16 = 56 bytes)
+ */
+struct hammer_cluster_elm {
+       struct hammer_base_elm base;
+       u_int64_t clu_id;               /* cluster id (sanity check) */
+       u_int32_t vol_no;
+       u_int32_t cluster_no;
+};
+
+/*
+ * Rollup btree element types - 56 byte structure
+ */
+union hammer_btree_elm {
+       struct hammer_base_elm base;
+       struct hammer_internal_elm internal;
+       struct hammer_leaf_elm leaf;
+       struct hammer_cluster_elm cluster;
+};
+
+/*
+ * B-Tree node (normal or meta) - 56 + 56 * 8 = 504 bytes
+ *
+ * 32 B-Tree nodes fit in a 16K filesystem buffer.  Remember, the filesystem
+ * buffer has a 128 byte header so (16384 - 128) / 32 = 508, but we want
+ * our structures to be 8-byte aligned so we use 504.
+ */
+#define HAMMER_BTREE_ELMS      8
+
+struct hammer_btree_node {
+       /*
+        * B-Tree node header (56 bytes)
+        */
+       int32_t         count;  /* number of elements in B-Tree node */
+       u_int32_t       parent; /* parent B-Tree node in current cluster */
+       u_int32_t       reserved[12];
+
+       /*
+        * 8 elements making up the B-Tree node 56x8 = 448 bytes
+        */
+       union hammer_btree_elm elms[HAMMER_BTREE_ELMS];
+};
+
+/*
+ * B-Tree filesystem buffer
+ */
+#define HAMMER_BTREE_NODES             \
+        ((HAMMER_BUFSIZE - sizeof(struct hammer_fsbuf_head)) / \
+        sizeof(struct hammer_btree_node))
+
+struct hammer_fsbuf_btree {
+        struct hammer_fsbuf_head        head;
+       char                            unused[128];
+        struct hammer_btree_node       nodes[HAMMER_BTREE_NODES];
+};
+
+
diff --git a/sys/vfs/hammer/hammer_mount.h b/sys/vfs/hammer/hammer_mount.h
new file mode 100644 (file)
index 0000000..d9b5682
--- /dev/null
@@ -0,0 +1,52 @@
+/*
+ * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
+ * 
+ * This code is derived from software contributed to The DragonFly Project
+ * by Matthew Dillon <dillon@backplane.com>
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * 
+ * $DragonFly: src/sys/vfs/hammer/hammer_mount.h,v 1.1 2007/10/10 19:37:25 dillon Exp $
+ */
+
+#ifndef _SYS_TYPES_H_
+#include <sys/types.h>
+#endif
+#ifndef _SYS_MOUNT_H_
+#include <sys/mount.h>
+#endif
+
+/*
+ * This structure is passed from userland to the kernel during the mount
+ * system call.
+ */
+struct hammer_mount_info {
+       const char **volumes;   /* array of pointers to device names */
+       int nvolumes;           /* number of devices */
+};
+
diff --git a/sys/vfs/hammer/hammerfs.h b/sys/vfs/hammer/hammerfs.h
new file mode 100644 (file)
index 0000000..abc3f86
--- /dev/null
@@ -0,0 +1,501 @@
+/*
+ * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
+ * 
+ * This code is derived from software contributed to The DragonFly Project
+ * by Matthew Dillon <dillon@backplane.com>
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * 
+ * $DragonFly: src/sys/vfs/hammer/Attic/hammerfs.h,v 1.1 2007/10/10 19:37:25 dillon Exp $
+ */
+
+#ifndef _SYS_UUID_H_
+#include <sys/uuid.h>
+#endif
+
+/*
+ * The structures below represent the on-disk format for a HAMMER
+ * filesystem.  Note that all fields for on-disk structures are naturally
+ * aligned.  The host endian format is used - compatibility is possible
+ * if the implementation detects reversed endian and adjusts data accordingly.
+ *
+ * Most of HAMMER revolves around the concept of an object identifier.  An
+ * obj_id is a 64 bit quantity which uniquely identifies a filesystem object
+ * FOR THE ENTIRE LIFE OF THE FILESYSTEM.  This uniqueness allows backups
+ * and mirrors to retain varying amounts of filesystem history by removing
+ * any possibility of conflict through identifier reuse.
+ *
+ * A HAMMER filesystem may spam multiple volumes.
+ *
+ * A HAMMER filesystem uses a 16K filesystem buffer size.  All filesystem
+ * I/O is done in multiples of 16K.
+ */
+#define HAMMER_BUFSIZE 16384
+#define HAMMER_BUFMASK (HAMMER_BUFSIZE - 1)
+
+/*
+ * Hammer transction ids are 64 bit unsigned integers and are usually
+ * synchronized with the time of day in nanoseconds.
+ */
+typedef u_int64_t hammer_tid_t;
+
+/*
+ * Storage allocations are managed in powers of 2 with a hinted radix tree
+ * based in volume and cluster headers.  The tree is not necessarily
+ * contained within the header and may recurse into other storage elements.
+ *
+ * The allocator's basic storage element is the hammer_almeta structure
+ * which is laid out recursively in a buffer.  Allocations are driven using
+ * a template called hammer_alist which is constructed in memory and NOT
+ * stored in the filesystem.
+ */
+struct hammer_almeta {
+       u_int32_t       bm_bitmap;
+       int32_t         bm_bighint;
+};
+
+#define HAMMER_ALMETA_SIZE     8
+
+struct hammer_alist {
+       int32_t bl_blocks;      /* area of coverage */
+       int32_t bl_radix;       /* coverage radix */
+       int32_t bl_skip;        /* starting skip for linear layout */
+       int32_t bl_free;        /* number of free blocks */
+       int32_t bl_rootblks;    /* meta-blocks allocated for tree */
+};
+
+typedef struct hammer_almeta   hammer_almeta_t;
+typedef struct hammer_alist    *hammer_alist_t;
+
+#define HAMMER_ALIST_META_RADIX        (sizeof(u_int32_t) * 4)   /* 16 */
+#define HAMMER_ALIST_BMAP_RADIX        (sizeof(u_int32_t) * 8)   /* 32 */
+#define HAMMER_ALIST_BLOCK_NONE        ((int32_t)-1)
+#define HAMMER_ALIST_FORWARDS  0x0001
+#define HAMMER_ALIST_BACKWARDS 0x0002
+
+/*
+ * Most HAMMER data structures are embedded in 16K filesystem buffers.
+ * All filesystem buffers except those designated as pure-data buffers
+ * contain this 128-byte header.
+ *
+ * This structure contains an embedded A-List used to manage space within
+ * the filesystem buffer.  It is not used by volume or cluster header
+ * buffers, or by pure-data buffers.  The granularity is variable and
+ * depends on the type of filesystem buffer.  BLKSIZE is just a minimum.
+ */
+
+#define HAMMER_FSBUF_HEAD_SIZE 128
+#define HAMMER_FSBUF_MAXBLKS   256
+#define HAMMER_FSBUF_METAELMS  10      /* 10 elements needed for 256 blks */
+
+struct hammer_fsbuf_head {
+       u_int64_t buf_type;
+       u_int32_t buf_crc;
+       u_int32_t buf_reserved07;
+       u_int32_t reserved[8];
+       struct hammer_almeta buf_almeta[HAMMER_FSBUF_METAELMS];
+};
+
+typedef struct hammer_fsbuf_head *hammer_fsbuf_head_t;
+
+#define HAMMER_FSBUF_VOLUME    0xC8414D4DC5523031ULL   /* HAMMER01 */
+#define HAMMER_FSBUF_CLUSTER   0xC8414D52C34C5553ULL   /* HAMRCLUS */
+#define HAMMER_FSBUF_RECORDS   0xC8414D52D2454353ULL   /* HAMRRECS */
+#define HAMMER_FSBUF_BTREE     0xC8414D52C2545245ULL   /* HAMRBTRE */
+#define HAMMER_FSBUF_DATA      0xC8414D52C4415441ULL   /* HAMRDATA */
+
+#define HAMMER_FSBUF_VOLUME_REV        0x313052C54D4D41C8ULL   /* (reverse endian) */
+
+/*
+ * The B-Tree structures need hammer_fsbuf_head.
+ */
+#include "hammer_btree.h"
+
+/*
+ * HAMMER Volume header
+ *
+ * A HAMMER filesystem is built from any number of block devices,  Each block
+ * device contains a volume header followed by however many clusters
+ * fit in the volume.  Clusters cannot be migrated but the data they contain
+ * can, so HAMMER can use a truncated cluster for any extra space at the
+ * end of the volume.
+ *
+ * The volume containing the root cluster is designated as the master volume.
+ * The root cluster designation can be moved to any volume.
+ *
+ * The volume header takes up an entire 16K filesystem buffer and includes
+ * an A-list to manage the clusters contained within the volume (up to 32768).
+ * With 512M clusters a volume will be limited to 16TB.
+ */
+#define HAMMER_VOL_MAXCLUSTERS 32768
+#define HAMMER_VOL_METAELMS    1094
+
+struct hammer_volume_ondisk {
+       struct hammer_fsbuf_head head;
+       int64_t vol_beg;        /* byte offset of first cluster in volume */
+       int64_t vol_end;        /* byte offset of volume EOF */
+       int64_t vol_locked;     /* reserved clusters are >= this offset */
+
+       uuid_t    vol_fsid;     /* identify filesystem */
+       uuid_t    vol_fstype;   /* identify filesystem type */
+       char      vol_name[64]; /* Name of volume */
+
+       int32_t vol_no;         /* volume number within filesystem */
+       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_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;
+       u_int32_t vol_reserved06;
+       u_int32_t vol_reserved07;
+
+       /*
+        * These fields are initialized and space is reserved in every
+        * volume making up a HAMMER filesytem, but only the master volume
+        * contains valid data.
+        */
+       int32_t vol0_rootcluster;       /* root cluster no (index) in rootvol */
+       u_int32_t vol0_reserved02;
+       u_int32_t vol0_reserved03;
+       hammer_tid_t vol0_nexttid;      /* next TID */
+       u_int64_t vol0_recid;           /* fs-wide record id allocator */
+
+       char    reserved[1024];
+
+       hammer_almeta_t vol_almeta[HAMMER_VOL_METAELMS];
+       u_int32_t       vol0_bitmap[1024];
+};
+
+#define HAMMER_VOLF_VALID      0x0001  /* valid entry */
+#define HAMMER_VOLF_OPEN       0x0002  /* volume is open */
+
+/*
+ * HAMMER Cluster header
+ *
+ * The cluster header contains all the information required to identify a
+ * cluster, locate critical information areas within the cluster, and
+ * to manage space within the cluster.
+ *
+ * A Cluster contains pure data, incremental data, b-tree nodes, and records.
+ */
+#define HAMMER_CLU_MAXBUFFERS  32768
+#define HAMMER_CLU_METAELMS    1094
+
+struct hammer_cluster_ondisk {
+       struct hammer_fsbuf_head head;
+       uuid_t  vol_fsid;       /* identify filesystem - sanity check */
+       uuid_t  vol_fstype;     /* identify filesystem type - sanity check */
+
+       u_int64_t clu_gen;      /* identify generation number of cluster */
+       u_int64_t clu_unused01;
+
+       hammer_tid_t clu_id;    /* unique cluster self identification */
+       int32_t vol_no;         /* cluster contained in volume (sanity) */
+       u_int32_t clu_flags;    /* cluster flags */
+
+       int32_t clu_start;      /* start of data (byte offset) */
+       int32_t clu_limit;      /* end of data (byte offset) */
+       int32_t clu_no;         /* cluster index in volume (sanity) */
+       u_int32_t clu_reserved03;
+
+       u_int32_t clu_reserved04;
+       u_int32_t clu_reserved05;
+       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) */
+       u_int32_t idx_reserved03;
+
+       /* 
+        * Specify the range of information stored in this cluster.  These
+        * structures match the B-Tree elements in our parent cluster
+        * (if any) that point to us.  Note that clu_objend is
+        * range-inclusive, not range-exclusive so e.g. 0-1023 instead
+        * of 0-1024.
+        */
+       int64_t clu_parent;             /* parent vol & cluster */
+       struct hammer_base_elm clu_objstart;
+       struct hammer_base_elm clu_objend;
+
+       /*
+        * The root node of the cluster's B-Tree is embedded in the
+        * cluster header.  The node is 504 bytes.
+        */
+       struct hammer_btree_node clu_btree_root;
+
+       /*
+        * HAMMER needs a separate bitmap to indicate which buffers are
+        * managed (contain a hammer_fsbuf_head).  Any buffers not so
+        * designated are either unused or contain pure data.
+        *
+        * synchronized_rec_id is the synchronization point for the
+        * cluster.  Any records with a greater or equal rec_id found
+        * when recovering a cluster are likely incomplete and will be
+        * ignored.
+        */
+       u_int64_t synchronized_rec_id;
+       u_int32_t managed_buffers_bitmap[HAMMER_CLU_MAXBUFFERS/32];
+
+       char    reserved[1024];
+       hammer_almeta_t clu_almeta[HAMMER_CLU_METAELMS];
+};
+
+/*
+ * HAMMER records are 96 byte entities encoded into 16K filesystem buffers.
+ * Each record has a 64 byte header and a 32 byte extension.  170 records
+ * fit into each buffer.  Storage is managed by the buffer's A-List.
+ *
+ * Each record may have an explicit data reference to a block of data up
+ * to 2^31-1 bytes in size within the current cluster.  Note that multiple
+ * records may share the same or overlapping data references.
+ */
+
+/*
+ * All HAMMER records have a common 64-byte base and a 32-byte extension.
+ *
+ * Many HAMMER record types reference out-of-band data within the cluster.
+ * This data can also be stored in-band in the record itself if it is small
+ * enough.  Either way, (data_offset, data_len) points to it.
+ *
+ * Key comparison order:  obj_id, rec_type, key, create_tid
+ */
+struct hammer_base_record {
+       int64_t obj_id;         /* 00 object record is associated with */
+       int64_t key;            /* 08 indexing key (offset or namekey) */
+
+       hammer_tid_t create_tid;/* 10 transaction id for record creation */
+       hammer_tid_t delete_tid;/* 18 transaction id for record update/delete */
+
+       u_int16_t rec_type;     /* 20 type of record */
+       u_int16_t obj_type;     /* 22 type of object (if inode) */
+       u_int32_t data_offset;  /* 24 intra-cluster data reference */
+                               /*    An offset of 0 indicates zero-fill */
+       int32_t data_len;       /* 28 size of data (remainder zero-fill) */
+       u_int32_t data_crc;     /* 2C data sanity check */
+       u_int64_t rec_id;       /* 30 record id (iterator for recovery) */
+       u_int64_t reserved07;   /* 38 */
+                               /* 40 */
+};
+
+#define HAMMER_RECTYPE_UNKNOWN         0
+#define HAMMER_RECTYPE_INODE           1       /* inode in obj_id space */
+#define HAMMER_RECTYPE_SLAVE           2       /* slave inode */
+#define HAMMER_RECTYPE_OBJZONE         3       /* subdivide obj_id space */
+#define HAMMER_RECTYPE_DATA_CREATE     0x10
+#define HAMMER_RECTYPE_DATA_ZEROFILL   0x11
+#define HAMMER_RECTYPE_DATA_DELETE     0x12
+#define HAMMER_RECTYPE_DATA_UPDATE     0x13
+#define HAMMER_RECTYPE_DIR_CREATE      0x20
+#define HAMMER_RECTYPE_DIR_DELETE      0x22
+#define HAMMER_RECTYPE_DIR_UPDATE      0x23
+#define HAMMER_RECTYPE_DB_CREATE       0x30
+#define HAMMER_RECTYPE_DB_DELETE       0x32
+#define HAMMER_RECTYPE_DB_UPDATE       0x33
+#define HAMMER_RECTYPE_EXT_CREATE      0x40    /* ext attributes */
+#define HAMMER_RECTYPE_EXT_DELETE      0x42
+#define HAMMER_RECTYPE_EXT_UPDATE      0x43
+
+#define HAMMER_OBJTYPE_DIRECTORY       1
+#define HAMMER_OBJTYPE_REGFILE         2
+#define HAMMER_OBJTYPE_DBFILE          3
+#define HAMMER_OBJTYPE_FIFO            4
+#define HAMMER_OBJTYPE_DEVNODE         5
+#define HAMMER_OBJTYPE_SOFTLINK                6
+
+/*
+ * Generic full-sized record
+ */
+struct hammer_generic_record {
+       struct hammer_base_record base;
+       char filler[32];
+};
+
+/*
+ * A HAMMER inode record.
+ *
+ * This forms the basis for a filesystem object.  obj_id is the inode number,
+ * key1 represents the pseudo filesystem id for security partitioning
+ * (preventing cross-links and/or restricting a NFS export and specifying the
+ * security policy), and key2 represents the data retention policy id.
+ *
+ * Inode numbers are 64 bit quantities which uniquely identify a filesystem
+ * object for the ENTIRE life of the filesystem, even after the object has
+ * been deleted.  For all intents and purposes inode numbers are simply 
+ * allocated by incrementing a sequence space.
+ *
+ * There is an important distinction between the data stored in the inode
+ * record and the record's data reference.  The record references a
+ * hammer_inode_data structure but the filesystem object size and hard link
+ * count is stored in the inode record itself.  This allows multiple inodes
+ * to share the same hammer_inode_data structure.  This is possible because
+ * any modifications will lay out new data.  The HAMMER implementation need
+ * not use the data-sharing ability when laying down new records.
+ *
+ * A HAMMER inode is subject to the same historical storage requirements
+ * as any other record.  In particular any change in filesystem or hard link
+ * count will lay down a new inode record when the filesystem is synced to
+ * disk.  This can lead to a lot of junk records which get cleaned up by
+ * the data retention policy.
+ *
+ * The ino_atime and ino_mtime fields are a special case.  Modifications to
+ * these fields do NOT lay down a new record by default, though the values
+ * are effectively frozen for snapshots which access historical versions
+ * of the inode record due to other operations.  This means that atime will
+ * not necessarily be accurate in snapshots, backups, or mirrors.  mtime
+ * will be accurate in backups and mirrors since it can be regenerated from
+ * the mirroring stream.
+ *
+ * Because nlinks is historically retained the hardlink count will be
+ * accurate when accessing a HAMMER filesystem snapshot.
+ */
+struct hammer_inode_record {
+       struct hammer_base_record base;
+       u_int64_t ino_atime;    /* last access time (not historical) */
+       u_int64_t ino_mtime;    /* last modified time (not historical) */
+       u_int64_t ino_size;     /* filesystem object size */
+       u_int64_t ino_nlinks;   /* hard links */
+};
+
+/*
+ * Data records specify the entire contents of a regular file object,
+ * including attributes.  Small amounts of data can theoretically be
+ * embedded in the record itself but the use of this ability verses using
+ * an out-of-band data reference depends on the implementation.
+ */
+struct hammer_data_record {
+       struct hammer_base_record base;
+       char filler[32];
+};
+
+/*
+ * A directory entry specifies the HAMMER filesystem object id, a copy of
+ * the file type, and file name (either embedded or as out-of-band data).
+ * If the file name is short enough to fit into den_name[] (including a
+ * terminating nul) then it will be embedded in the record, otherwise it
+ * is stored out-of-band.  The base record's data reference always points
+ * to the nul-terminated filename regardless.
+ *
+ * Directory entries are indexed with a 128 bit namekey rather then an
+ * offset.  A portion of the namekey is an iterator or randomizer to deal
+ * with collisions.
+ */
+struct hammer_entry_record {
+       struct hammer_base_record base;
+       u_int64_t obj_id;               /* object being referenced */
+       u_int64_t reserved01;
+       u_int8_t  den_type;             /* cached file type */
+       char      den_name[15];         /* short file names fit in record */
+};
+
+/*
+ * Hammer rollup record
+ */
+union hammer_record {
+       struct hammer_base_record       base;
+       struct hammer_generic_record    generic;
+       struct hammer_inode_record      inode;
+       struct hammer_data_record       data;
+       struct hammer_entry_record      entry;
+};
+
+typedef union hammer_record *hammer_record_t;
+
+/*
+ * Filesystem buffer for records
+ */
+#define HAMMER_RECORD_NODES    \
+       ((HAMMER_BUFSIZE - sizeof(struct hammer_fsbuf_head)) / \
+       sizeof(union hammer_record))
+
+struct hammer_fsbuf_recs {
+       struct hammer_fsbuf_head        head;
+       char                            unused[32];
+       union hammer_record             recs[HAMMER_RECORD_NODES];
+};
+
+/*
+ * Filesystem buffer for piecemeal data.  Note that this does not apply
+ * to dedicated pure-data buffers as such buffers do not have a header.
+ */
+
+#define HAMMER_DATA_SIZE       (HAMMER_BUFSIZE - sizeof(struct hammer_fsbuf_head))
+#define HAMMER_DATA_BLKSIZE    64
+#define HAMMER_DATA_NODES      (HAMMER_DATA_SIZE / HAMMER_DATA_BLKSIZE)
+
+struct hammer_fsbuf_data {
+       struct hammer_fsbuf_head head;
+       u_int8_t                data[HAMMER_DATA_NODES][HAMMER_DATA_BLKSIZE];
+};
+
+
+/*
+ * HAMMER UNIX Attribute data
+ *
+ * The data reference in a HAMMER inode record points to this structure.  Any
+ * modifications to the contents of this structure will result in a record
+ * replacement operation.
+ *
+ * state_sum allows a filesystem object to be validated to a degree by
+ * generating a checksum of all of its pieces (in no particular order) and
+ * checking it against this field.
+ */
+struct hammer_inode_data {
+       u_int16_t version;      /* inode data version */
+       u_int16_t mode;         /* basic unix permissions */
+       u_int32_t uflags;       /* chflags */
+       u_int64_t reserved01;
+       u_int64_t reserved02;
+       u_int64_t state_sum;    /* cumulative checksum */
+       uuid_t  uid;
+       uuid_t  gid;
+};
+
+#define HAMMER_INODE_DATA_VERSION      1
+
+/*
+ * Function library support available to kernel and userland
+ */
+void hammer_alist_template(hammer_alist_t, int blocks, int maxmeta);
+void hammer_alist_init(hammer_alist_t bl, hammer_almeta_t *meta);
+int32_t hammer_alist_alloc(hammer_alist_t bl, hammer_almeta_t *meta,
+                       int32_t count);
+int32_t hammer_alist_alloc_rev(hammer_alist_t bl, hammer_almeta_t *meta,
+                       int32_t count);
+#if 0
+int32_t hammer_alist_alloc_from(hammer_alist_t bl, hammer_almeta_t *meta,
+                       int32_t count, int32_t start, int flags);
+#endif
+void hammer_alist_free(hammer_alist_t bl, hammer_almeta_t *meta,
+                       int32_t blkno, int32_t count);
+