6745471 FileBench needs to be able to randomly select files from a fileset

6745474 FileBench's fileset_pick() routine needs to more efficiently select appropriate files

18 files changed, 2288 insertions, 384 deletions

diff --git a/usr/src/cmd/filebench/Makefile.com b/usr/src/cmd/filebench/Makefile.com
index 80b75065c9..e583cbd054 100644
--- a/usr/src/cmd/filebench/Makefile.com
+++ b/usr/src/cmd/filebench/Makefile.com
@@ -32,6 +32,7 @@ SRCS = \
 	auto_comp.c \
         eventgen.c \
 	fb_random.c \
+	fb_avl.c \
         fileset.c \
         flowop.c \
         flowop_library.c \
diff --git a/usr/src/cmd/filebench/common/fb_avl.c b/usr/src/cmd/filebench/common/fb_avl.c
new file mode 100644
index 0000000000..7ef7431c28
--- /dev/null
+++ b/usr/src/cmd/filebench/common/fb_avl.c
@@ -0,0 +1,1064 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License (the "License").
+ * You may not use this file except in compliance with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+
+/*
+ * AVL - generic AVL tree implementation for FileBench use.
+ * -Adapted from the avl.c open source code used in the Solaris Kernel-
+ *
+ * A complete description of AVL trees can be found in many CS textbooks.
+ *
+ * Here is a very brief overview. An AVL tree is a binary search tree that is
+ * almost perfectly balanced. By "almost" perfectly balanced, we mean that at
+ * any given node, the left and right subtrees are allowed to differ in height
+ * by at most 1 level.
+ *
+ * This relaxation from a perfectly balanced binary tree allows doing
+ * insertion and deletion relatively efficiently. Searching the tree is
+ * still a fast operation, roughly O(log(N)).
+ *
+ * The key to insertion and deletion is a set of tree maniuplations called
+ * rotations, which bring unbalanced subtrees back into the semi-balanced state.
+ *
+ * This implementation of AVL trees has the following peculiarities:
+ *
+ *	- The AVL specific data structures are physically embedded as fields
+ *	  in the "using" data structures.  To maintain generality the code
+ *	  must constantly translate between "avl_node_t *" and containing
+ *	  data structure "void *"s by adding/subracting the avl_offset.
+ *
+ *	- Since the AVL data is always embedded in other structures, there is
+ *	  no locking or memory allocation in the AVL routines. This must be
+ *	  provided for by the enclosing data structure's semantics. Typically,
+ *	  avl_insert()/_add()/_remove()/avl_insert_here() require some kind of
+ *	  exclusive write lock. Other operations require a read lock.
+ *
+ *      - The implementation uses iteration instead of explicit recursion,
+ *	  since it is intended to run on limited size kernel stacks. Since
+ *	  there is no recursion stack present to move "up" in the tree,
+ *	  there is an explicit "parent" link in the avl_node_t.
+ *
+ *      - The left/right children pointers of a node are in an array.
+ *	  In the code, variables (instead of constants) are used to represent
+ *	  left and right indices.  The implementation is written as if it only
+ *	  dealt with left handed manipulations.  By changing the value assigned
+ *	  to "left", the code also works for right handed trees.  The
+ *	  following variables/terms are frequently used:
+ *
+ *		int left;	// 0 when dealing with left children,
+ *				// 1 for dealing with right children
+ *
+ *		int left_heavy;	// -1 when left subtree is taller at some node,
+ *				// +1 when right subtree is taller
+ *
+ *		int right;	// will be the opposite of left (0 or 1)
+ *		int right_heavy;// will be the opposite of left_heavy (-1 or 1)
+ *
+ *		int direction;  // 0 for "<" (ie. left child); 1 for ">" (right)
+ *
+ *	  Though it is a little more confusing to read the code, the approach
+ *	  allows using half as much code (and hence cache footprint) for tree
+ *	  manipulations and eliminates many conditional branches.
+ *
+ *	- The avl_index_t is an opaque "cookie" used to find nodes at or
+ *	  adjacent to where a new value would be inserted in the tree. The value
+ *	  is a modified "avl_node_t *".  The bottom bit (normally 0 for a
+ *	  pointer) is set to indicate if that the new node has a value greater
+ *	  than the value of the indicated "avl_node_t *".
+ */
+
+#include "filebench.h"
+#include "fb_avl.h"
+
+/*
+ * Small arrays to translate between balance (or diff) values and child indeces.
+ *
+ * Code that deals with binary tree data structures will randomly use
+ * left and right children when examining a tree.  C "if()" statements
+ * which evaluate randomly suffer from very poor hardware branch prediction.
+ * In this code we avoid some of the branch mispredictions by using the
+ * following translation arrays. They replace random branches with an
+ * additional memory reference. Since the translation arrays are both very
+ * small the data should remain efficiently in cache.
+ */
+static const int  avl_child2balance[2]	= {-1, 1};
+static const int  avl_balance2child[]	= {0, 0, 1};
+
+
+/*
+ * Walk from one node to the previous valued node (ie. an infix walk
+ * towards the left). At any given node we do one of 2 things:
+ *
+ * - If there is a left child, go to it, then to it's rightmost descendant.
+ *
+ * - otherwise we return thru parent nodes until we've come from a right child.
+ *
+ * Return Value:
+ * NULL - if at the end of the nodes
+ * otherwise next node
+ */
+void *
+avl_walk(avl_tree_t *tree, void	*oldnode, int left)
+{
+	size_t off = tree->avl_offset;
+	avl_node_t *node = AVL_DATA2NODE(oldnode, off);
+	int right = 1 - left;
+	int was_child;
+
+
+	/*
+	 * nowhere to walk to if tree is empty
+	 */
+	if (node == NULL)
+		return (NULL);
+
+	/*
+	 * Visit the previous valued node. There are two possibilities:
+	 *
+	 * If this node has a left child, go down one left, then all
+	 * the way right.
+	 */
+	if (node->avl_child[left] != NULL) {
+		for (node = node->avl_child[left];
+		    node->avl_child[right] != NULL;
+		    node = node->avl_child[right])
+			;
+	/*
+	 * Otherwise, return thru left children as far as we can.
+	 */
+	} else {
+		for (;;) {
+			was_child = AVL_XCHILD(node);
+			node = AVL_XPARENT(node);
+			if (node == NULL)
+				return (NULL);
+			if (was_child == right)
+				break;
+		}
+	}
+
+	return (AVL_NODE2DATA(node, off));
+}
+
+/*
+ * Return the lowest valued node in a tree or NULL.
+ * (leftmost child from root of tree)
+ */
+void *
+avl_first(avl_tree_t *tree)
+{
+	avl_node_t *node;
+	avl_node_t *prev = NULL;
+	size_t off = tree->avl_offset;
+
+	for (node = tree->avl_root; node != NULL; node = node->avl_child[0])
+		prev = node;
+
+	if (prev != NULL)
+		return (AVL_NODE2DATA(prev, off));
+	return (NULL);
+}
+
+/*
+ * Return the highest valued node in a tree or NULL.
+ * (rightmost child from root of tree)
+ */
+void *
+avl_last(avl_tree_t *tree)
+{
+	avl_node_t *node;
+	avl_node_t *prev = NULL;
+	size_t off = tree->avl_offset;
+
+	for (node = tree->avl_root; node != NULL; node = node->avl_child[1])
+		prev = node;
+
+	if (prev != NULL)
+		return (AVL_NODE2DATA(prev, off));
+	return (NULL);
+}
+
+/*
+ * Access the node immediately before or after an insertion point.
+ *
+ * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child
+ *
+ * Return value:
+ *	NULL: no node in the given direction
+ *	"void *"  of the found tree node
+ */
+void *
+avl_nearest(avl_tree_t *tree, avl_index_t where, int direction)
+{
+	int child = AVL_INDEX2CHILD(where);
+	avl_node_t *node = AVL_INDEX2NODE(where);
+	void *data;
+	size_t off = tree->avl_offset;
+
+	if (node == NULL) {
+		if (tree->avl_root != NULL)
+			filebench_log(LOG_ERROR,
+			    "Null Node Pointer Supplied");
+		return (NULL);
+	}
+	data = AVL_NODE2DATA(node, off);
+	if (child != direction)
+		return (data);
+
+	return (avl_walk(tree, data, direction));
+}
+
+
+/*
+ * Search for the node which contains "value".  The algorithm is a
+ * simple binary tree search.
+ *
+ * return value:
+ *	NULL: the value is not in the AVL tree
+ *		*where (if not NULL)  is set to indicate the insertion point
+ *	"void *"  of the found tree node
+ */
+void *
+avl_find(avl_tree_t *tree, void *value, avl_index_t *where)
+{
+	avl_node_t *node;
+	avl_node_t *prev = NULL;
+	int child = 0;
+	int diff;
+	size_t off = tree->avl_offset;
+
+	for (node = tree->avl_root; node != NULL;
+	    node = node->avl_child[child]) {
+
+		prev = node;
+
+		diff = tree->avl_compar(value, AVL_NODE2DATA(node, off));
+		if (!((-1 <= diff) && (diff <= 1))) {
+			filebench_log(LOG_ERROR, "avl compare error");
+			return (NULL);
+		}
+		if (diff == 0) {
+			if (where != NULL)
+				*where = 0;
+
+			return (AVL_NODE2DATA(node, off));
+		}
+		child = avl_balance2child[1 + diff];
+
+	}
+
+	if (where != NULL)
+		*where = AVL_MKINDEX(prev, child);
+
+	return (NULL);
+}
+
+
+/*
+ * Perform a rotation to restore balance at the subtree given by depth.
+ *
+ * This routine is used by both insertion and deletion. The return value
+ * indicates:
+ *	 0 : subtree did not change height
+ *	!0 : subtree was reduced in height
+ *
+ * The code is written as if handling left rotations, right rotations are
+ * symmetric and handled by swapping values of variables right/left[_heavy]
+ *
+ * On input balance is the "new" balance at "node". This value is either
+ * -2 or +2.
+ */
+static int
+avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance)
+{
+	int left = !(balance < 0);	/* when balance = -2, left will be 0 */
+	int right = 1 - left;
+	int left_heavy = balance >> 1;
+	int right_heavy = -left_heavy;
+	avl_node_t *parent = AVL_XPARENT(node);
+	avl_node_t *child = node->avl_child[left];
+	avl_node_t *cright;
+	avl_node_t *gchild;
+	avl_node_t *gright;
+	avl_node_t *gleft;
+	int which_child = AVL_XCHILD(node);
+	int child_bal = AVL_XBALANCE(child);
+
+	/* BEGIN CSTYLED */
+	/*
+	 * case 1 : node is overly left heavy, the left child is balanced or
+	 * also left heavy. This requires the following rotation.
+	 *
+	 *                   (node bal:-2)
+	 *                    /           \
+	 *                   /             \
+	 *              (child bal:0 or -1)
+	 *              /    \
+	 *             /      \
+	 *                     cright
+	 *
+	 * becomes:
+	 *
+	 *              (child bal:1 or 0)
+	 *              /        \
+	 *             /          \
+	 *                        (node bal:-1 or 0)
+	 *                         /     \
+	 *                        /       \
+	 *                     cright
+	 *
+	 * we detect this situation by noting that child's balance is not
+	 * right_heavy.
+	 */
+	/* END CSTYLED */
+	if (child_bal != right_heavy) {
+
+		/*
+		 * compute new balance of nodes
+		 *
+		 * If child used to be left heavy (now balanced) we reduced
+		 * the height of this sub-tree -- used in "return...;" below
+		 */
+		child_bal += right_heavy; /* adjust towards right */
+
+		/*
+		 * move "cright" to be node's left child
+		 */
+		cright = child->avl_child[right];
+		node->avl_child[left] = cright;
+		if (cright != NULL) {
+			AVL_SETPARENT(cright, node);
+			AVL_SETCHILD(cright, left);
+		}
+
+		/*
+		 * move node to be child's right child
+		 */
+		child->avl_child[right] = node;
+		AVL_SETBALANCE(node, -child_bal);
+		AVL_SETCHILD(node, right);
+		AVL_SETPARENT(node, child);
+
+		/*
+		 * update the pointer into this subtree
+		 */
+		AVL_SETBALANCE(child, child_bal);
+		AVL_SETCHILD(child, which_child);
+		AVL_SETPARENT(child, parent);
+		if (parent != NULL)
+			parent->avl_child[which_child] = child;
+		else
+			tree->avl_root = child;
+
+		return (child_bal == 0);
+	}
+
+	/* BEGIN CSTYLED */
+	/*
+	 * case 2 : When node is left heavy, but child is right heavy we use
+	 * a different rotation.
+	 *
+	 *                   (node b:-2)
+	 *                    /   \
+	 *                   /     \
+	 *                  /       \
+	 *             (child b:+1)
+	 *              /     \
+	 *             /       \
+	 *                   (gchild b: != 0)
+	 *                     /  \
+	 *                    /    \
+	 *                 gleft   gright
+	 *
+	 * becomes:
+	 *
+	 *              (gchild b:0)
+	 *              /       \
+	 *             /         \
+	 *            /           \
+	 *        (child b:?)   (node b:?)
+	 *         /  \          /   \
+	 *        /    \        /     \
+	 *            gleft   gright
+	 *
+	 * computing the new balances is more complicated. As an example:
+	 *	 if gchild was right_heavy, then child is now left heavy
+	 *		else it is balanced
+	 */
+	/* END CSTYLED */
+	gchild = child->avl_child[right];
+	gleft = gchild->avl_child[left];
+	gright = gchild->avl_child[right];
+
+	/*
+	 * move gright to left child of node and
+	 *
+	 * move gleft to right child of node
+	 */
+	node->avl_child[left] = gright;
+	if (gright != NULL) {
+		AVL_SETPARENT(gright, node);
+		AVL_SETCHILD(gright, left);
+	}
+
+	child->avl_child[right] = gleft;
+	if (gleft != NULL) {
+		AVL_SETPARENT(gleft, child);
+		AVL_SETCHILD(gleft, right);
+	}
+
+	/*
+	 * move child to left child of gchild and
+	 *
+	 * move node to right child of gchild and
+	 *
+	 * fixup parent of all this to point to gchild
+	 */
+	balance = AVL_XBALANCE(gchild);
+	gchild->avl_child[left] = child;
+	AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0));
+	AVL_SETPARENT(child, gchild);
+	AVL_SETCHILD(child, left);
+
+	gchild->avl_child[right] = node;
+	AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0));
+	AVL_SETPARENT(node, gchild);
+	AVL_SETCHILD(node, right);
+
+	AVL_SETBALANCE(gchild, 0);
+	AVL_SETPARENT(gchild, parent);
+	AVL_SETCHILD(gchild, which_child);
+	if (parent != NULL)
+		parent->avl_child[which_child] = gchild;
+	else
+		tree->avl_root = gchild;
+
+	return (1);	/* the new tree is always shorter */
+}
+
+
+/*
+ * Insert a new node into an AVL tree at the specified (from avl_find()) place.
+ *
+ * Newly inserted nodes are always leaf nodes in the tree, since avl_find()
+ * searches out to the leaf positions.  The avl_index_t indicates the node
+ * which will be the parent of the new node.
+ *
+ * After the node is inserted, a single rotation further up the tree may
+ * be necessary to maintain an acceptable AVL balance.
+ */
+void
+avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where)
+{
+	avl_node_t *node;
+	avl_node_t *parent = AVL_INDEX2NODE(where);
+	int old_balance;
+	int new_balance;
+	int which_child = AVL_INDEX2CHILD(where);
+	size_t off = tree->avl_offset;
+
+	if (tree == NULL) {
+		filebench_log(LOG_ERROR, "No Tree Supplied");
+		return;
+	}
+#ifdef _LP64
+	if (((uintptr_t)new_data & 0x7) != 0) {
+		filebench_log(LOG_ERROR, "Missaligned pointer to new data");
+		return;
+	}
+#endif
+
+	node = AVL_DATA2NODE(new_data, off);
+
+	/*
+	 * First, add the node to the tree at the indicated position.
+	 */
+	++tree->avl_numnodes;
+
+	node->avl_child[0] = NULL;
+	node->avl_child[1] = NULL;
+
+	AVL_SETCHILD(node, which_child);
+	AVL_SETBALANCE(node, 0);
+	AVL_SETPARENT(node, parent);
+	if (parent != NULL) {
+		if (parent->avl_child[which_child] != NULL)
+			filebench_log(LOG_DEBUG_IMPL,
+			    "Overwriting existing pointer");
+
+		parent->avl_child[which_child] = node;
+	} else {
+		if (tree->avl_root != NULL)
+			filebench_log(LOG_DEBUG_IMPL,
+			    "Overwriting existing pointer");
+
+		tree->avl_root = node;
+	}
+	/*
+	 * Now, back up the tree modifying the balance of all nodes above the
+	 * insertion point. If we get to a highly unbalanced ancestor, we
+	 * need to do a rotation.  If we back out of the tree we are done.
+	 * If we brought any subtree into perfect balance (0), we are also done.
+	 */
+	for (;;) {
+		node = parent;
+		if (node == NULL)
+			return;
+
+		/*
+		 * Compute the new balance
+		 */
+		old_balance = AVL_XBALANCE(node);
+		new_balance = old_balance + avl_child2balance[which_child];
+
+		/*
+		 * If we introduced equal balance, then we are done immediately
+		 */
+		if (new_balance == 0) {
+			AVL_SETBALANCE(node, 0);
+			return;
+		}
+
+		/*
+		 * If both old and new are not zero we went
+		 * from -1 to -2 balance, do a rotation.
+		 */
+		if (old_balance != 0)
+			break;
+
+		AVL_SETBALANCE(node, new_balance);
+		parent = AVL_XPARENT(node);
+		which_child = AVL_XCHILD(node);
+	}
+
+	/*
+	 * perform a rotation to fix the tree and return
+	 */
+	(void) avl_rotation(tree, node, new_balance);
+}
+
+/*
+ * Insert "new_data" in "tree" in the given "direction" either after or
+ * before (AVL_AFTER, AVL_BEFORE) the data "here".
+ *
+ * Insertions can only be done at empty leaf points in the tree, therefore
+ * if the given child of the node is already present we move to either
+ * the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since
+ * every other node in the tree is a leaf, this always works.
+ *
+ * To help developers using this interface, we assert that the new node
+ * is correctly ordered at every step of the way in DEBUG kernels.
+ */
+void
+avl_insert_here(
+	avl_tree_t *tree,
+	void *new_data,
+	void *here,
+	int direction)
+{
+	avl_node_t *node;
+	int child = direction;	/* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */
+
+	if ((tree == NULL) || (new_data == NULL) || (here == NULL) ||
+	    !((direction == AVL_BEFORE) || (direction == AVL_AFTER))) {
+		filebench_log(LOG_ERROR,
+		    "avl_insert_here: Bad Parameters Passed");
+		return;
+	}
+
+	/*
+	 * If corresponding child of node is not NULL, go to the neighboring
+	 * node and reverse the insertion direction.
+	 */
+	node = AVL_DATA2NODE(here, tree->avl_offset);
+
+	if (node->avl_child[child] != NULL) {
+		node = node->avl_child[child];
+		child = 1 - child;
+		while (node->avl_child[child] != NULL)
+			node = node->avl_child[child];
+
+	}
+	if (node->avl_child[child] != NULL)
+		filebench_log(LOG_DEBUG_IMPL, "Overwriting existing pointer");
+
+	avl_insert(tree, new_data, AVL_MKINDEX(node, child));
+}
+
+/*
+ * Add a new node to an AVL tree.
+ */
+void
+avl_add(avl_tree_t *tree, void *new_node)
+{
+	avl_index_t where;
+
+	/*
+	 * This is unfortunate. Give up.
+	 */
+	if (avl_find(tree, new_node, &where) != NULL) {
+		filebench_log(LOG_ERROR,
+		    "Attempting to insert already inserted node");
+		return;
+	}
+	avl_insert(tree, new_node, where);
+}
+
+/*
+ * Delete a node from the AVL tree.  Deletion is similar to insertion, but
+ * with 2 complications.
+ *
+ * First, we may be deleting an interior node. Consider the following subtree:
+ *
+ *     d           c            c
+ *    / \         / \          / \
+ *   b   e       b   e        b   e
+ *  / \	        / \          /
+ * a   c       a            a
+ *
+ * When we are deleting node (d), we find and bring up an adjacent valued leaf
+ * node, say (c), to take the interior node's place. In the code this is
+ * handled by temporarily swapping (d) and (c) in the tree and then using
+ * common code to delete (d) from the leaf position.
+ *
+ * Secondly, an interior deletion from a deep tree may require more than one
+ * rotation to fix the balance. This is handled by moving up the tree through
+ * parents and applying rotations as needed. The return value from
+ * avl_rotation() is used to detect when a subtree did not change overall
+ * height due to a rotation.
+ */
+void
+avl_remove(avl_tree_t *tree, void *data)
+{
+	avl_node_t *delete;
+	avl_node_t *parent;
+	avl_node_t *node;
+	avl_node_t tmp;
+	int old_balance;
+	int new_balance;
+	int left;
+	int right;
+	int which_child;
+	size_t off = tree->avl_offset;
+
+	if (tree == NULL) {
+		filebench_log(LOG_ERROR, "No Tree Supplied");
+		return;
+	}
+
+	delete = AVL_DATA2NODE(data, off);
+
+	/*
+	 * Deletion is easiest with a node that has at most 1 child.
+	 * We swap a node with 2 children with a sequentially valued
+	 * neighbor node. That node will have at most 1 child. Note this
+	 * has no effect on the ordering of the remaining nodes.
+	 *
+	 * As an optimization, we choose the greater neighbor if the tree
+	 * is right heavy, otherwise the left neighbor. This reduces the
+	 * number of rotations needed.
+	 */
+	if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) {
+
+		/*
+		 * choose node to swap from whichever side is taller
+		 */
+		old_balance = AVL_XBALANCE(delete);
+		left = avl_balance2child[old_balance + 1];
+		right = 1 - left;
+
+		/*
+		 * get to the previous value'd node
+		 * (down 1 left, as far as possible right)
+		 */
+		for (node = delete->avl_child[left];
+		    node->avl_child[right] != NULL;
+		    node = node->avl_child[right])
+			;
+
+		/*
+		 * create a temp placeholder for 'node'
+		 * move 'node' to delete's spot in the tree
+		 */
+		tmp = *node;
+
+		*node = *delete;
+		if (node->avl_child[left] == node)
+			node->avl_child[left] = &tmp;
+
+		parent = AVL_XPARENT(node);
+		if (parent != NULL)
+			parent->avl_child[AVL_XCHILD(node)] = node;
+		else
+			tree->avl_root = node;
+		AVL_SETPARENT(node->avl_child[left], node);
+		AVL_SETPARENT(node->avl_child[right], node);
+
+		/*
+		 * Put tmp where node used to be (just temporary).
+		 * It always has a parent and at most 1 child.
+		 */
+		delete = &tmp;
+		parent = AVL_XPARENT(delete);
+		parent->avl_child[AVL_XCHILD(delete)] = delete;
+		which_child = (delete->avl_child[1] != 0);
+		if (delete->avl_child[which_child] != NULL)
+			AVL_SETPARENT(delete->avl_child[which_child], delete);
+	}
+
+
+	/*
+	 * Here we know "delete" is at least partially a leaf node. It can
+	 * be easily removed from the tree.
+	 */
+	if (tree->avl_numnodes == 0) {
+		filebench_log(LOG_ERROR,
+		    "Deleting Node from already empty tree");
+		return;
+	}
+
+	--tree->avl_numnodes;
+	parent = AVL_XPARENT(delete);
+	which_child = AVL_XCHILD(delete);
+	if (delete->avl_child[0] != NULL)
+		node = delete->avl_child[0];
+	else
+		node = delete->avl_child[1];
+
+	/*
+	 * Connect parent directly to node (leaving out delete).
+	 */
+	if (node != NULL) {
+		AVL_SETPARENT(node, parent);
+		AVL_SETCHILD(node, which_child);
+	}
+	if (parent == NULL) {
+		tree->avl_root = node;
+		return;
+	}
+	parent->avl_child[which_child] = node;
+
+
+	/*
+	 * Since the subtree is now shorter, begin adjusting parent balances
+	 * and performing any needed rotations.
+	 */
+	do {
+
+		/*
+		 * Move up the tree and adjust the balance
+		 *
+		 * Capture the parent and which_child values for the next
+		 * iteration before any rotations occur.
+		 */
+		node = parent;
+		old_balance = AVL_XBALANCE(node);
+		new_balance = old_balance - avl_child2balance[which_child];
+		parent = AVL_XPARENT(node);
+		which_child = AVL_XCHILD(node);
+
+		/*
+		 * If a node was in perfect balance but isn't anymore then
+		 * we can stop, since the height didn't change above this point
+		 * due to a deletion.
+		 */
+		if (old_balance == 0) {
+			AVL_SETBALANCE(node, new_balance);
+			break;
+		}
+
+		/*
+		 * If the new balance is zero, we don't need to rotate
+		 * else
+		 * need a rotation to fix the balance.
+		 * If the rotation doesn't change the height
+		 * of the sub-tree we have finished adjusting.
+		 */
+		if (new_balance == 0)
+			AVL_SETBALANCE(node, new_balance);
+		else if (!avl_rotation(tree, node, new_balance))
+			break;
+	} while (parent != NULL);
+}
+
+#define	AVL_REINSERT(tree, obj)		\
+	avl_remove((tree), (obj));	\
+	avl_add((tree), (obj))
+
+boolean_t
+avl_update_lt(avl_tree_t *t, void *obj)
+{
+	void *neighbor;
+
+	if (!(((neighbor = AVL_NEXT(t, obj)) == NULL) ||
+	    (t->avl_compar(obj, neighbor) <= 0))) {
+		filebench_log(LOG_ERROR,
+		    "avl_update_lt: Neighbor miss compare");
+		return (B_FALSE);
+	}
+
+	neighbor = AVL_PREV(t, obj);
+	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {
+		AVL_REINSERT(t, obj);
+		return (B_TRUE);
+	}
+
+	return (B_FALSE);
+}
+
+boolean_t
+avl_update_gt(avl_tree_t *t, void *obj)
+{
+	void *neighbor;
+
+	if (!(((neighbor = AVL_PREV(t, obj)) == NULL) ||
+	    (t->avl_compar(obj, neighbor) >= 0))) {
+		filebench_log(LOG_ERROR,
+		    "avl_update_gt: Neighbor miss compare");
+		return (B_FALSE);
+	}
+
+	neighbor = AVL_NEXT(t, obj);
+	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {
+		AVL_REINSERT(t, obj);
+		return (B_TRUE);
+	}
+
+	return (B_FALSE);
+}
+
+boolean_t
+avl_update(avl_tree_t *t, void *obj)
+{
+	void *neighbor;
+
+	neighbor = AVL_PREV(t, obj);
+	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {
+		AVL_REINSERT(t, obj);
+		return (B_TRUE);
+	}
+
+	neighbor = AVL_NEXT(t, obj);
+	if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {
+		AVL_REINSERT(t, obj);
+		return (B_TRUE);
+	}
+
+	return (B_FALSE);
+}
+
+/*
+ * initialize a new AVL tree
+ */
+void
+avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *),
+    size_t size, size_t offset)
+{
+	if ((tree == NULL) || (compar == NULL) || (size == 0) ||
+	    (size < (offset + sizeof (avl_node_t)))) {
+		filebench_log(LOG_ERROR,
+		    "avl_create: Bad Parameters Passed");
+		return;
+	}
+;
+#ifdef _LP64
+	if ((offset & 0x7) != 0) {
+		filebench_log(LOG_ERROR, "Missaligned pointer to new data");
+		return;
+	}
+#endif
+
+	tree->avl_compar = compar;
+	tree->avl_root = NULL;
+	tree->avl_numnodes = 0;
+	tree->avl_size = size;
+	tree->avl_offset = offset;
+}
+
+/*
+ * Delete a tree.
+ */
+/* ARGSUSED */
+void
+avl_destroy(avl_tree_t *tree)
+{
+	if ((tree == NULL) || (tree->avl_numnodes != 0) ||
+	    (tree->avl_root != NULL))
+		filebench_log(LOG_DEBUG_IMPL, "avl_tree: Tree not destroyed");
+}
+
+
+/*
+ * Return the number of nodes in an AVL tree.
+ */
+ulong_t
+avl_numnodes(avl_tree_t *tree)
+{
+	if (tree == NULL) {
+		filebench_log(LOG_ERROR, "avl_numnodes: Null tree pointer");
+		return (0);
+	}
+	return (tree->avl_numnodes);
+}
+
+boolean_t
+avl_is_empty(avl_tree_t *tree)
+{
+	if (tree == NULL) {
+		filebench_log(LOG_ERROR, "avl_is_empty: Null tree pointer");
+		return (0);
+	}
+	return (tree->avl_numnodes == 0);
+}
+
+#define	CHILDBIT	(1L)
+
+/*
+ * Post-order tree walk used to visit all tree nodes and destroy the tree
+ * in post order. This is used for destroying a tree w/o paying any cost
+ * for rebalancing it.
+ *
+ * example:
+ *
+ *	void *cookie = NULL;
+ *	my_data_t *node;
+ *
+ *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
+ *		free(node);
+ *	avl_destroy(tree);
+ *
+ * The cookie is really an avl_node_t to the current node's parent and
+ * an indication of which child you looked at last.
+ *
+ * On input, a cookie value of CHILDBIT indicates the tree is done.
+ */
+void *
+avl_destroy_nodes(avl_tree_t *tree, void **cookie)
+{
+	avl_node_t	*node;
+	avl_node_t	*parent;
+	int		child;
+	void		*first;
+	size_t		off = tree->avl_offset;
+
+	/*
+	 * Initial calls go to the first node or it's right descendant.
+	 */
+	if (*cookie == NULL) {
+		first = avl_first(tree);
+
+		/*
+		 * deal with an empty tree
+		 */
+		if (first == NULL) {
+			*cookie = (void *)CHILDBIT;
+			return (NULL);
+		}
+
+		node = AVL_DATA2NODE(first, off);
+		parent = AVL_XPARENT(node);
+		goto check_right_side;
+	}
+
+	/*
+	 * If there is no parent to return to we are done.
+	 */
+	parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT);
+	if (parent == NULL) {
+		if (tree->avl_root != NULL) {
+			if (tree->avl_numnodes != 1) {
+				filebench_log(LOG_DEBUG_IMPL,
+				    "avl_destroy_nodes:"
+				    " number of nodes wrong");
+			}
+			tree->avl_root = NULL;
+			tree->avl_numnodes = 0;
+		}
+		return (NULL);
+	}
+
+	/*
+	 * Remove the child pointer we just visited from the parent and tree.
+	 */
+	child = (uintptr_t)(*cookie) & CHILDBIT;
+	parent->avl_child[child] = NULL;
+	if (tree->avl_numnodes <= 1)
+		filebench_log(LOG_DEBUG_IMPL,
+		    "avl_destroy_nodes: number of nodes wrong");
+
+	--tree->avl_numnodes;
+
+	/*
+	 * If we just did a right child or there isn't one, go up to parent.
+	 */
+	if (child == 1 || parent->avl_child[1] == NULL) {
+		node = parent;
+		parent = AVL_XPARENT(parent);
+		goto done;
+	}
+
+	/*
+	 * Do parent's right child, then leftmost descendent.
+	 */
+	node = parent->avl_child[1];
+	while (node->avl_child[0] != NULL) {
+		parent = node;
+		node = node->avl_child[0];
+	}
+
+	/*
+	 * If here, we moved to a left child. It may have one
+	 * child on the right (when balance == +1).
+	 */
+check_right_side:
+	if (node->avl_child[1] != NULL) {
+		if (AVL_XBALANCE(node) != 1)
+			filebench_log(LOG_DEBUG_IMPL,
+			    "avl_destroy_nodes: Tree inconsistency");
+		parent = node;
+		node = node->avl_child[1];
+		if (node->avl_child[0] != NULL ||
+		    node->avl_child[1] != NULL)
+			filebench_log(LOG_DEBUG_IMPL,
+			    "avl_destroy_nodes: Destroying non leaf node");
+	} else {
+
+		if (AVL_XBALANCE(node) > 0)
+			filebench_log(LOG_DEBUG_IMPL,
+			    "avl_destroy_nodes: Tree inconsistency");
+	}
+
+done:
+	if (parent == NULL) {
+		*cookie = (void *)CHILDBIT;
+		if (node != tree->avl_root)
+			filebench_log(LOG_DEBUG_IMPL,
+			    "avl_destroy_nodes: Dangling last node");
+	} else {
+		*cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node));
+	}
+
+	return (AVL_NODE2DATA(node, off));
+}
diff --git a/usr/src/cmd/filebench/common/fb_avl.h b/usr/src/cmd/filebench/common/fb_avl.h
new file mode 100644
index 0000000000..fdec8b742f
--- /dev/null
+++ b/usr/src/cmd/filebench/common/fb_avl.h
@@ -0,0 +1,423 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License (the "License").
+ * You may not use this file except in compliance with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#ifndef	FB_AVL_H
+#define	FB_AVL_H
+
+/*
+ * derived from  Solaris' sys/avl.h and sys/avl_impl.h
+ */
+
+#ifdef	__cplusplus
+extern "C" {
+#endif
+
+#include <sys/types.h>
+
+/*
+ * generic AVL tree implementation for FileBench use
+ *
+ * The interfaces provide an efficient way of implementing an ordered set of
+ * data structures.
+ *
+ * AVL trees provide an alternative to using an ordered linked list. Using AVL
+ * trees will usually be faster, however they requires more storage. An ordered
+ * linked list in general requires 2 pointers in each data structure. The
+ * AVL tree implementation uses 3 pointers. The following chart gives the
+ * approximate performance of operations with the different approaches:
+ *
+ *	Operation	 Link List	AVL tree
+ *	---------	 --------	--------
+ *	lookup		   O(n)		O(log(n))
+ *
+ *	insert 1 node	 constant	constant
+ *
+ *	delete 1 node	 constant	between constant and O(log(n))
+ *
+ *	delete all nodes   O(n)		O(n)
+ *
+ *	visit the next
+ *	or prev node	 constant	between constant and O(log(n))
+ *
+ *
+ * There are 5 pieces of information stored for each node in an AVL tree
+ *
+ * 	pointer to less than child
+ * 	pointer to greater than child
+ * 	a pointer to the parent of this node
+ *	an indication  [0/1]  of which child I am of my parent
+ * 	a "balance" (-1, 0, +1)  indicating which child tree is taller
+ *
+ * Since they only need 3 bits, the last two fields are packed into the
+ * bottom bits of the parent pointer on 64 bit machines to save on space.
+ */
+
+#ifndef _LP64
+
+struct avl_node {
+	struct avl_node *avl_child[2];	/* left/right children */
+	struct avl_node *avl_parent;	/* this node's parent */
+	unsigned short avl_child_index;	/* my index in parent's avl_child[] */
+	short avl_balance;		/* balance value: -1, 0, +1 */
+};
+
+#define	AVL_XPARENT(n)		((n)->avl_parent)
+#define	AVL_SETPARENT(n, p)	((n)->avl_parent = (p))
+
+#define	AVL_XCHILD(n)		((n)->avl_child_index)
+#define	AVL_SETCHILD(n, c)	((n)->avl_child_index = (unsigned short)(c))
+
+#define	AVL_XBALANCE(n)		((n)->avl_balance)
+#define	AVL_SETBALANCE(n, b)	((n)->avl_balance = (short)(b))
+
+#else /* _LP64 */
+
+/*
+ * for 64 bit machines, avl_pcb contains parent pointer, balance and child_index
+ * values packed in the following manner:
+ *
+ * |63                                  3|        2        |1          0 |
+ * |-------------------------------------|-----------------|-------------|
+ * |      avl_parent hi order bits       | avl_child_index | avl_balance |
+ * |                                     |                 |     + 1     |
+ * |-------------------------------------|-----------------|-------------|
+ *
+ */
+struct avl_node {
+	struct avl_node *avl_child[2];	/* left/right children nodes */
+	uintptr_t avl_pcb;		/* parent, child_index, balance */
+};
+
+/*
+ * macros to extract/set fields in avl_pcb
+ *
+ * pointer to the parent of the current node is the high order bits
+ */
+#define	AVL_XPARENT(n)		((struct avl_node *)((n)->avl_pcb & ~7))
+#define	AVL_SETPARENT(n, p)						\
+	((n)->avl_pcb = (((n)->avl_pcb & 7) | (uintptr_t)(p)))
+
+/*
+ * index of this node in its parent's avl_child[]: bit #2
+ */
+#define	AVL_XCHILD(n)		(((n)->avl_pcb >> 2) & 1)
+#define	AVL_SETCHILD(n, c)						\
+	((n)->avl_pcb = (uintptr_t)(((n)->avl_pcb & ~4) | ((c) << 2)))
+
+/*
+ * balance indication for a node, lowest 2 bits. A valid balance is
+ * -1, 0, or +1, and is encoded by adding 1 to the value to get the
+ * unsigned values of 0, 1, 2.
+ */
+#define	AVL_XBALANCE(n)		((int)(((n)->avl_pcb & 3) - 1))
+#define	AVL_SETBALANCE(n, b)						\
+	((n)->avl_pcb = (uintptr_t)((((n)->avl_pcb & ~3) | ((b) + 1))))
+
+#endif /* _LP64 */
+
+
+
+/*
+ * switch between a node and data pointer for a given tree
+ * the value of "o" is tree->avl_offset
+ */
+#define	AVL_NODE2DATA(n, o)	((void *)((uintptr_t)(n) - (o)))
+#define	AVL_DATA2NODE(d, o)	((struct avl_node *)((uintptr_t)(d) + (o)))
+
+
+
+/*
+ * macros used to create/access an avl_index_t
+ */
+#define	AVL_INDEX2NODE(x)	((avl_node_t *)((x) & ~1))
+#define	AVL_INDEX2CHILD(x)	((x) & 1)
+#define	AVL_MKINDEX(n, c)	((avl_index_t)(n) | (c))
+
+
+/*
+ * The tree structure. The fields avl_root, avl_compar, and avl_offset come
+ * first since they are needed for avl_find().  We want them to fit into
+ * a single 64 byte cache line to make avl_find() as fast as possible.
+ */
+struct avl_tree {
+	struct avl_node *avl_root;	/* root node in tree */
+	int (*avl_compar)(const void *, const void *);
+	size_t avl_offset;		/* offsetof(type, avl_link_t field) */
+	ulong_t avl_numnodes;		/* number of nodes in the tree */
+	size_t avl_size;		/* sizeof user type struct */
+};
+
+
+/*
+ * This will only by used via AVL_NEXT() or AVL_PREV()
+ */
+extern void *avl_walk(struct avl_tree *, void *, int);
+
+
+/*
+ * The data structure nodes are anchored at an "avl_tree_t" (the equivalent
+ * of a list header) and the individual nodes will have a field of
+ * type "avl_node_t" (corresponding to list pointers).
+ *
+ * The type "avl_index_t" is used to indicate a position in the list for
+ * certain calls.
+ *
+ * The usage scenario is generally:
+ *
+ * 1. Create the list/tree with: avl_create()
+ *
+ * followed by any mixture of:
+ *
+ * 2a. Insert nodes with: avl_add(), or avl_find() and avl_insert()
+ *
+ * 2b. Visited elements with:
+ *	 avl_first() - returns the lowest valued node
+ *	 avl_last() - returns the highest valued node
+ *	 AVL_NEXT() - given a node go to next higher one
+ *	 AVL_PREV() - given a node go to previous lower one
+ *
+ * 2c.  Find the node with the closest value either less than or greater
+ *	than a given value with avl_nearest().
+ *
+ * 2d. Remove individual nodes from the list/tree with avl_remove().
+ *
+ * and finally when the list is being destroyed
+ *
+ * 3. Use avl_destroy_nodes() to quickly process/free up any remaining nodes.
+ *    Note that once you use avl_destroy_nodes(), you can no longer
+ *    use any routine except avl_destroy_nodes() and avl_destoy().
+ *
+ * 4. Use avl_destroy() to destroy the AVL tree itself.
+ *
+ * Any locking for multiple thread access is up to the user to provide, just
+ * as is needed for any linked list implementation.
+ */
+
+
+/*
+ * Type used for the root of the AVL tree.
+ */
+typedef struct avl_tree avl_tree_t;
+
+/*
+ * The data nodes in the AVL tree must have a field of this type.
+ */
+typedef struct avl_node avl_node_t;
+
+/*
+ * An opaque type used to locate a position in the tree where a node
+ * would be inserted.
+ */
+typedef uintptr_t avl_index_t;
+
+
+/*
+ * Direction constants used for avl_nearest().
+ */
+#define	AVL_BEFORE	(0)
+#define	AVL_AFTER	(1)
+
+
+/*
+ * Prototypes
+ *
+ * Where not otherwise mentioned, "void *" arguments are a pointer to the
+ * user data structure which must contain a field of type avl_node_t.
+ *
+ * Also assume the user data structures looks like:
+ *	stuct my_type {
+ *		...
+ *		avl_node_t	my_link;
+ *		...
+ *	};
+ */
+
+/*
+ * Initialize an AVL tree. Arguments are:
+ *
+ * tree   - the tree to be initialized
+ * compar - function to compare two nodes, it must return exactly: -1, 0, or +1
+ *          -1 for <, 0 for ==, and +1 for >
+ * size   - the value of sizeof(struct my_type)
+ * offset - the value of OFFSETOF(struct my_type, my_link)
+ */
+extern void avl_create(avl_tree_t *tree,
+	int (*compar) (const void *, const void *), size_t size, size_t offset);
+
+
+/*
+ * Find a node with a matching value in the tree. Returns the matching node
+ * found. If not found, it returns NULL and then if "where" is not NULL it sets
+ * "where" for use with avl_insert() or avl_nearest().
+ *
+ * node   - node that has the value being looked for
+ * where  - position for use with avl_nearest() or avl_insert(), may be NULL
+ */
+extern void *avl_find(avl_tree_t *tree, void *node, avl_index_t *where);
+
+/*
+ * Insert a node into the tree.
+ *
+ * node   - the node to insert
+ * where  - position as returned from avl_find()
+ */
+extern void avl_insert(avl_tree_t *tree, void *node, avl_index_t where);
+
+/*
+ * Insert "new_data" in "tree" in the given "direction" either after
+ * or before the data "here".
+ *
+ * This might be usefull for avl clients caching recently accessed
+ * data to avoid doing avl_find() again for insertion.
+ *
+ * new_data	- new data to insert
+ * here		- existing node in "tree"
+ * direction	- either AVL_AFTER or AVL_BEFORE the data "here".
+ */
+extern void avl_insert_here(avl_tree_t *tree, void *new_data, void *here,
+    int direction);
+
+
+/*
+ * Return the first or last valued node in the tree. Will return NULL
+ * if the tree is empty.
+ *
+ */
+extern void *avl_first(avl_tree_t *tree);
+extern void *avl_last(avl_tree_t *tree);
+
+
+/*
+ * Return the next or previous valued node in the tree.
+ * AVL_NEXT() will return NULL if at the last node.
+ * AVL_PREV() will return NULL if at the first node.
+ *
+ * node   - the node from which the next or previous node is found
+ */
+#define	AVL_NEXT(tree, node)	avl_walk(tree, node, AVL_AFTER)
+#define	AVL_PREV(tree, node)	avl_walk(tree, node, AVL_BEFORE)
+
+
+/*
+ * Find the node with the nearest value either greater or less than
+ * the value from a previous avl_find(). Returns the node or NULL if
+ * there isn't a matching one.
+ *
+ * where     - position as returned from avl_find()
+ * direction - either AVL_BEFORE or AVL_AFTER
+ *
+ * EXAMPLE get the greatest node that is less than a given value:
+ *
+ *	avl_tree_t *tree;
+ *	struct my_data look_for_value = {....};
+ *	struct my_data *node;
+ *	struct my_data *less;
+ *	avl_index_t where;
+ *
+ *	node = avl_find(tree, &look_for_value, &where);
+ *	if (node != NULL)
+ *		less = AVL_PREV(tree, node);
+ *	else
+ *		less = avl_nearest(tree, where, AVL_BEFORE);
+ */
+extern void *avl_nearest(avl_tree_t *tree, avl_index_t where, int direction);
+
+
+/*
+ * Add a single node to the tree.
+ * The node must not be in the tree, and it must not
+ * compare equal to any other node already in the tree.
+ *
+ * node   - the node to add
+ */
+extern void avl_add(avl_tree_t *tree, void *node);
+
+
+/*
+ * Remove a single node from the tree.  The node must be in the tree.
+ *
+ * node   - the node to remove
+ */
+extern void avl_remove(avl_tree_t *tree, void *node);
+
+/*
+ * Reinsert a node only if its order has changed relative to its nearest
+ * neighbors. To optimize performance avl_update_lt() checks only the previous
+ * node and avl_update_gt() checks only the next node. Use avl_update_lt() and
+ * avl_update_gt() only if you know the direction in which the order of the
+ * node may change.
+ */
+extern boolean_t avl_update(avl_tree_t *, void *);
+extern boolean_t avl_update_lt(avl_tree_t *, void *);
+extern boolean_t avl_update_gt(avl_tree_t *, void *);
+
+/*
+ * Return the number of nodes in the tree
+ */
+extern ulong_t avl_numnodes(avl_tree_t *tree);
+
+/*
+ * Return B_TRUE if there are zero nodes in the tree, B_FALSE otherwise.
+ */
+extern boolean_t avl_is_empty(avl_tree_t *tree);
+
+/*
+ * Used to destroy any remaining nodes in a tree. The cookie argument should
+ * be initialized to NULL before the first call. Returns a node that has been
+ * removed from the tree and may be free()'d. Returns NULL when the tree is
+ * empty.
+ *
+ * Once you call avl_destroy_nodes(), you can only continuing calling it and
+ * finally avl_destroy(). No other AVL routines will be valid.
+ *
+ * cookie - a "void *" used to save state between calls to avl_destroy_nodes()
+ *
+ * EXAMPLE:
+ *	avl_tree_t *tree;
+ *	struct my_data *node;
+ *	void *cookie;
+ *
+ *	cookie = NULL;
+ *	while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
+ *		free(node);
+ *	avl_destroy(tree);
+ */
+extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie);
+
+
+/*
+ * Final destroy of an AVL tree. Arguments are:
+ *
+ * tree   - the empty tree to destroy
+ */
+extern void avl_destroy(avl_tree_t *tree);
+
+
+
+#ifdef	__cplusplus
+}
+#endif
+
+#endif	/* FB_AVL_H */
diff --git a/usr/src/cmd/filebench/common/fb_random.c b/usr/src/cmd/filebench/common/fb_random.c
index 15a66880f8..39872dc8ee 100644
--- a/usr/src/cmd/filebench/common/fb_random.c
+++ b/usr/src/cmd/filebench/common/fb_random.c
@@ -23,8 +23,6 @@
  * Use is subject to license terms.
  */
 
-#pragma ident	"%Z%%M%	%I%	%E% SMI"
-
 #include <stdio.h>
 #include <fcntl.h>
 #include <math.h>
@@ -305,9 +303,13 @@ randdist_init_one(randdist_t *rndp)
 	int		pteidx;
 
 	/* convert parameters to doubles */
-	rndp->rnd_dbl_mean  = (double)avd_get_int(rndp->rnd_mean);
 	rndp->rnd_dbl_gamma = (double)avd_get_int(rndp->rnd_gamma) / 1000.0;
+	if (rndp->rnd_mean != NULL)
+		rndp->rnd_dbl_mean  = (double)avd_get_int(rndp->rnd_mean);
+	else
+		rndp->rnd_dbl_mean = rndp->rnd_dbl_gamma;
 
+	/* de-reference min and round amounts for later use */
 	rndp->rnd_vint_min  = avd_get_int(rndp->rnd_min);
 	rndp->rnd_vint_round  = avd_get_int(rndp->rnd_round);
 
diff --git a/usr/src/cmd/filebench/common/filebench.h b/usr/src/cmd/filebench/common/filebench.h
index 3c2e482bbb..91da9418e3 100644
--- a/usr/src/cmd/filebench/common/filebench.h
+++ b/usr/src/cmd/filebench/common/filebench.h
@@ -117,7 +117,7 @@ void filebench_shutdown(int error);
 #define	MIN(x, y) ((x) < (y) ? (x) : (y))
 #endif
 
-#define	FILEBENCH_VERSION	"1.4.1"
+#define	FILEBENCH_VERSION	"1.4.2"
 #define	FILEBENCHDIR	"/usr/benchmarks/filebench"
 #define	FILEBENCH_PROMPT	"filebench> "
 #define	MAX_LINE_LEN	1024
diff --git a/usr/src/cmd/filebench/common/fileset.c b/usr/src/cmd/filebench/common/fileset.c
index 4521913ec7..86d1e3efd5 100644
--- a/usr/src/cmd/filebench/common/fileset.c
+++ b/usr/src/cmd/filebench/common/fileset.c
@@ -31,6 +31,7 @@
 #include <math.h>
 #include <libgen.h>
 #include <sys/mman.h>
+#include <sys/shm.h>
 
 #include "filebench.h"
 #include "fileset.h"
@@ -260,12 +261,24 @@ fileset_create_subdirs(fileset_t *fileset, char *filesetpath)
 		if (fileset_mkdir(full_path, 0755) == FILEBENCH_ERROR)
 			return (FILEBENCH_ERROR);
 
-		direntry = direntry->fse_dirnext;
+		direntry = direntry->fse_nextoftype;
 	}
 	return (FILEBENCH_OK);
 }
 
 /*
+ * move filesetentry between exist tree and non-exist tree, source_tree
+ * to destination tree.
+ */
+static void
+fileset_move_entry(avl_tree_t *src_tree, avl_tree_t *dst_tree,
+    filesetentry_t *entry)
+{
+	avl_remove(src_tree, entry);
+	avl_add(dst_tree, entry);
+}
+
+/*
  * given a fileset entry, determines if the associated leaf directory
  * needs to be made or not, and if so does the mkdir.
  */
@@ -295,16 +308,13 @@ fileset_alloc_leafdir(filesetentry_t *entry)
 			filebench_log(LOG_ERROR,
 			    "Failed to pre-allocate leaf directory %s: %s",
 			    path, strerror(errno));
-
+			fileset_unbusy(entry, TRUE, FALSE, 0);
 			return (FILEBENCH_ERROR);
 		}
 	}
 
-	(void) ipc_mutex_lock(&fileset->fs_pick_lock);
-	entry->fse_flags |= FSE_EXISTS;
-	fileset->fs_num_act_leafdirs++;
-	(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
-
+	/* unbusy the allocated entry */
+	fileset_unbusy(entry, TRUE, TRUE, 0);
 	return (FILEBENCH_OK);
 }
 
@@ -339,6 +349,7 @@ fileset_alloc_file(filesetentry_t *entry)
 			filebench_log(LOG_INFO,
 			    "Attempted but failed to Re-use file %s",
 			    path);
+			fileset_unbusy(entry, TRUE, FALSE, 0);
 			return (FILEBENCH_ERROR);
 		}
 
@@ -350,17 +361,15 @@ fileset_alloc_file(filesetentry_t *entry)
 				(void) fileset_freemem(fd,
 				    entry->fse_size);
 
-			(void) ipc_mutex_lock(&fileset->fs_pick_lock);
-			entry->fse_flags |= FSE_EXISTS;
-			fileset->fs_num_act_files++;
-			(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
-
 			(void) close(fd);
+
+			/* unbusy the allocated entry */
+			fileset_unbusy(entry, TRUE, TRUE, 0);
 			return (FILEBENCH_OK);
 
 		} else if (sb.st_size > (off64_t)entry->fse_size) {
 			/* reuse, but too large */
-			filebench_log(LOG_INFO,
+			filebench_log(LOG_DEBUG_IMPL,
 			    "Truncating & re-using file %s", path);
 
 #ifdef HAVE_FTRUNCATE64
@@ -373,12 +382,10 @@ fileset_alloc_file(filesetentry_t *entry)
 				(void) fileset_freemem(fd,
 				    entry->fse_size);
 
-			(void) ipc_mutex_lock(&fileset->fs_pick_lock);
-			entry->fse_flags |= FSE_EXISTS;
-			fileset->fs_num_act_files++;
-			(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
-
 			(void) close(fd);
+
+			/* unbusy the allocated entry */
+			fileset_unbusy(entry, TRUE, TRUE, 0);
 			return (FILEBENCH_OK);
 		}
 	} else {
@@ -389,17 +396,17 @@ fileset_alloc_file(filesetentry_t *entry)
 			    "Failed to pre-allocate file %s: %s",
 			    path, strerror(errno));
 
+			/* unbusy the unallocated entry */
+			fileset_unbusy(entry, TRUE, FALSE, 0);
 			return (FILEBENCH_ERROR);
 		}
 	}
 
-	if ((buf = (char *)malloc(FILE_ALLOC_BLOCK)) == NULL)
+	if ((buf = (char *)malloc(FILE_ALLOC_BLOCK)) == NULL) {
+		/* unbusy the unallocated entry */
+		fileset_unbusy(entry, TRUE, FALSE, 0);
 		return (FILEBENCH_ERROR);
-
-	(void) ipc_mutex_lock(&fileset->fs_pick_lock);
-	entry->fse_flags |= FSE_EXISTS;
-	fileset->fs_num_act_files++;
-	(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
+	}
 
 	for (seek = 0; seek < entry->fse_size; ) {
 		off64_t wsize;
@@ -418,6 +425,7 @@ fileset_alloc_file(filesetentry_t *entry)
 			    path, strerror(errno));
 			(void) close(fd);
 			free(buf);
+			fileset_unbusy(entry, TRUE, FALSE, 0);
 			return (FILEBENCH_ERROR);
 		}
 		seek += wsize;
@@ -430,6 +438,9 @@ fileset_alloc_file(filesetentry_t *entry)
 
 	free(buf);
 
+	/* unbusy the allocated entry */
+	fileset_unbusy(entry, TRUE, TRUE, 0);
+
 	filebench_log(LOG_DEBUG_IMPL,
 	    "Pre-allocated file %s size %llu",
 	    path, (u_longlong_t)entry->fse_size);
@@ -505,17 +516,17 @@ fileset_openfile(fileset_t *fileset,
 
 	if ((fd = open64(path, flag | open_attrs, filemode)) < 0) {
 		filebench_log(LOG_ERROR,
-		    "Failed to open file %s: %s",
-		    path, strerror(errno));
+		    "Failed to open file %d, %s, with status %x: %s",
+		    entry->fse_index, path, entry->fse_flags, strerror(errno));
 
-		fileset_unbusy(entry, FALSE, FALSE);
+		fileset_unbusy(entry, FALSE, FALSE, 0);
 		return (FILEBENCH_ERROR);
 	}
 
 	if (flag & O_CREAT)
-		fileset_unbusy(entry, TRUE, TRUE);
+		fileset_unbusy(entry, TRUE, TRUE, 1);
 	else
-		fileset_unbusy(entry, FALSE, FALSE);
+		fileset_unbusy(entry, FALSE, FALSE, 1);
 
 #ifdef sun
 	if (attrs & FLOW_ATTR_DIRECTIO)
@@ -527,14 +538,107 @@ fileset_openfile(fileset_t *fileset,
 	return (fd);
 }
 
+/*
+ * removes all filesetentries from their respective btrees, and puts them
+ * on the free list. The supplied argument indicates which free list to
+ * use.
+ */
+static void
+fileset_pickreset(fileset_t *fileset, int entry_type)
+{
+	filesetentry_t	*entry;
+
+	switch (entry_type & FILESET_PICKMASK) {
+	case FILESET_PICKFILE:
+		entry = (filesetentry_t *)avl_first(&fileset->fs_noex_files);
+
+		/* make sure non-existing files are marked free */
+		while (entry) {
+			entry->fse_flags |= FSE_FREE;
+			entry->fse_open_cnt = 0;
+			fileset_move_entry(&fileset->fs_noex_files,
+			    &fileset->fs_free_files, entry);
+			entry =  AVL_NEXT(&fileset->fs_noex_files, entry);
+		}
+
+		/* free up any existing files */
+		entry = (filesetentry_t *)avl_first(&fileset->fs_exist_files);
+
+		while (entry) {
+			entry->fse_flags |= FSE_FREE;
+			entry->fse_open_cnt = 0;
+			fileset_move_entry(&fileset->fs_exist_files,
+			    &fileset->fs_free_files, entry);
+
+			entry =  AVL_NEXT(&fileset->fs_exist_files, entry);
+		}
+
+		break;
+
+	case FILESET_PICKDIR:
+		/* nothing to reset, as all (sub)dirs always exist */
+		break;
+
+	case FILESET_PICKLEAFDIR:
+		entry = (filesetentry_t *)
+		    avl_first(&fileset->fs_noex_leaf_dirs);
+
+		/* make sure non-existing leaf dirs are marked free */
+		while (entry) {
+			entry->fse_flags |= FSE_FREE;
+			entry->fse_open_cnt = 0;
+			fileset_move_entry(&fileset->fs_noex_leaf_dirs,
+			    &fileset->fs_free_leaf_dirs, entry);
+			entry =  AVL_NEXT(&fileset->fs_noex_leaf_dirs, entry);
+		}
+
+		/* free up any existing leaf dirs */
+		entry = (filesetentry_t *)
+		    avl_first(&fileset->fs_exist_leaf_dirs);
+
+		while (entry) {
+			entry->fse_flags |= FSE_FREE;
+			entry->fse_open_cnt = 0;
+			fileset_move_entry(&fileset->fs_exist_leaf_dirs,
+			    &fileset->fs_free_leaf_dirs, entry);
+
+			entry =  AVL_NEXT(&fileset->fs_exist_leaf_dirs, entry);
+		}
+
+		break;
+	}
+}
+
+/*
+ * find a filesetentry from the fileset using the supplied index
+ */
+static filesetentry_t *
+fileset_find_entry(avl_tree_t *atp, uint_t index)
+{
+	avl_index_t	found_loc;
+	filesetentry_t	desired_fse, *found_fse;
+
+	/* find the file with the desired index, if it is in the tree */
+	desired_fse.fse_index = index;
+	found_fse = avl_find(atp, (void *)(&desired_fse), &found_loc);
+	if (found_fse != NULL)
+		return (found_fse);
+
+	/* if requested node not found, find next higher node */
+	found_fse = avl_nearest(atp, found_loc, AVL_AFTER);
+	if (found_fse != NULL)
+		return (found_fse);
+
+	/* might have hit the end, return lowest available index node */
+	found_fse = avl_first(atp);
+	return (found_fse);
+}
 
 /*
  * Selects a fileset entry from a fileset. If the
  * FILESET_PICKLEAFDIR flag is set it will pick a leaf directory entry,
  * if the FILESET_PICKDIR flag is set it will pick a non leaf directory
- * entry, otherwise a file entry. The FILESET_PICKRESET
- * flag will cause it to reset the free list to the
- * overall list (file or directory). The FILESET_PICKUNIQUE
+ * entry, otherwise a file entry. The FILESET_PICKUNIQUE
  * flag will take an entry off of one of the free (unused)
  * lists (file or directory), otherwise the entry will be
  * picked off of one of the rotor lists (file or directory).
@@ -546,10 +650,12 @@ fileset_openfile(fileset_t *fileset,
  * with its FSE_BUSY flag (in fse_flags) set.
  */
 filesetentry_t *
-fileset_pick(fileset_t *fileset, int flags, int tid)
+fileset_pick(fileset_t *fileset, int flags, int tid, int index)
 {
 	filesetentry_t *entry = NULL;
-	filesetentry_t *first = NULL;
+	filesetentry_t *start_point;
+	avl_tree_t *atp;
+	fbint_t max_entries;
 
 	(void) ipc_mutex_lock(&fileset->fs_pick_lock);
 
@@ -558,185 +664,143 @@ fileset_pick(fileset_t *fileset, int flags, int tid)
 	case FILESET_PICKFILE:
 		if (fileset->fs_filelist == NULL)
 			goto empty;
+
 		while (fileset->fs_idle_files == 0) {
 			(void) pthread_cond_wait(&fileset->fs_idle_files_cv,
 			    &fileset->fs_pick_lock);
 		}
+
+		max_entries = fileset->fs_constentries;
+		if (flags & FILESET_PICKUNIQUE) {
+			atp = &fileset->fs_free_files;
+		} else if (flags & FILESET_PICKNOEXIST) {
+			atp = &fileset->fs_noex_files;
+		} else {
+			atp = &fileset->fs_exist_files;
+		}
 		break;
+
 	case FILESET_PICKDIR:
 		if (fileset->fs_dirlist == NULL)
 			goto empty;
+
 		while (fileset->fs_idle_dirs == 0) {
 			(void) pthread_cond_wait(&fileset->fs_idle_dirs_cv,
 			    &fileset->fs_pick_lock);
 		}
+
+		max_entries = 1;
+		atp = &fileset->fs_dirs;
 		break;
+
 	case FILESET_PICKLEAFDIR:
 		if (fileset->fs_leafdirlist == NULL)
 			goto empty;
+
 		while (fileset->fs_idle_leafdirs == 0) {
 			(void) pthread_cond_wait(&fileset->fs_idle_leafdirs_cv,
 			    &fileset->fs_pick_lock);
 		}
-		break;
-	}
 
-	/* see if asking for impossible */
-	switch (flags & FILESET_PICKMASK) {
-	case FILESET_PICKFILE:
-		if (flags & FILESET_PICKEXISTS) {
-			if (fileset->fs_num_act_files == 0) {
-				(void) ipc_mutex_unlock(
-				    &fileset->fs_pick_lock);
-				return (NULL);
-			}
-		} else if (flags & FILESET_PICKNOEXIST) {
-			if (fileset->fs_num_act_files ==
-			    fileset->fs_realfiles) {
-				(void) ipc_mutex_unlock(
-				    &fileset->fs_pick_lock);
-				return (NULL);
-			}
-		}
-		break;
-	case FILESET_PICKLEAFDIR:
-		if (flags & FILESET_PICKEXISTS) {
-			if (fileset->fs_num_act_leafdirs == 0) {
-				(void) ipc_mutex_unlock(
-				    &fileset->fs_pick_lock);
-				return (NULL);
-			}
+		max_entries = fileset->fs_constleafdirs;
+		if (flags & FILESET_PICKUNIQUE) {
+			atp = &fileset->fs_free_leaf_dirs;
 		} else if (flags & FILESET_PICKNOEXIST) {
-			if (fileset->fs_num_act_leafdirs ==
-			    fileset->fs_realleafdirs) {
-				(void) ipc_mutex_unlock(
-				    &fileset->fs_pick_lock);
-				return (NULL);
-			}
+			atp = &fileset->fs_noex_leaf_dirs;
+		} else {
+			atp = &fileset->fs_exist_leaf_dirs;
 		}
 		break;
-	case FILESET_PICKDIR:
-	default:
-		break;
 	}
 
-	while (entry == NULL) {
+	/* see if asking for impossible */
+	if (avl_is_empty(atp))
+		goto empty;
 
-		if (flags & FILESET_PICKRESET) {
-			switch (flags & FILESET_PICKMASK) {
-			case FILESET_PICKFILE:
-				entry = fileset->fs_filelist;
-				while (entry) {
-					entry->fse_flags |= FSE_FREE;
-					entry = entry->fse_filenext;
-				}
-				fileset->fs_filefree = fileset->fs_filelist;
-				break;
-			case FILESET_PICKDIR:
-				entry = fileset->fs_dirlist;
-				while (entry) {
-					entry->fse_flags |= FSE_FREE;
-					entry = entry->fse_dirnext;
-				}
-				fileset->fs_dirfree = fileset->fs_dirlist;
-				break;
-			case FILESET_PICKLEAFDIR:
-				entry = fileset->fs_leafdirlist;
-				while (entry) {
-					entry->fse_flags |= FSE_FREE;
-					entry = entry->fse_leafdirnext;
-				}
-				fileset->fs_leafdirfree =
-				    fileset->fs_leafdirlist;
-				break;
-			}
-		}
+	if (flags & FILESET_PICKUNIQUE) {
+		uint64_t  index64;
 
-		if (flags & FILESET_PICKUNIQUE) {
-			switch (flags & FILESET_PICKMASK) {
-			case FILESET_PICKFILE:
-				entry = fileset->fs_filefree;
-				if (entry == NULL)
-					goto empty;
-				fileset->fs_filefree = entry->fse_filenext;
-				break;
-			case FILESET_PICKDIR:
-				entry = fileset->fs_dirfree;
-				if (entry == NULL)
-					goto empty;
-				fileset->fs_dirfree = entry->fse_dirnext;
-				break;
-			case FILESET_PICKLEAFDIR:
-				entry = fileset->fs_leafdirfree;
-				if (entry == NULL)
-					goto empty;
-				fileset->fs_leafdirfree =
-				    entry->fse_leafdirnext;
-				break;
-			}
-			entry->fse_flags &= ~FSE_FREE;
+		/*
+		 * pick at random from free list in order to
+		 * distribute initially allocated files more
+		 * randomly on storage media. Use uniform
+		 * random number generator to select index
+		 * if it is not supplied with pick call.
+		 */
+		if (index) {
+			index64 = index;
 		} else {
-			switch (flags & FILESET_PICKMASK) {
-			case FILESET_PICKFILE:
-				if (flags & FILESET_PICKNOEXIST) {
-					entry = fileset->fs_file_ne_rotor;
-					if (entry == NULL)
-						fileset->fs_file_ne_rotor =
-						    entry =
-						    fileset->fs_filelist;
-					fileset->fs_file_ne_rotor =
-					    entry->fse_filenext;
-				} else {
-					entry = fileset->fs_filerotor[tid];
-					if (entry == NULL)
-						fileset->fs_filerotor[tid] =
-						    entry =
-						    fileset->fs_filelist;
-					fileset->fs_filerotor[tid] =
-					    entry->fse_filenext;
-				}
-				break;
-			case FILESET_PICKDIR:
-				entry = fileset->fs_dirrotor;
-				if (entry == NULL)
-					fileset->fs_dirrotor =
-					    entry = fileset->fs_dirlist;
-				fileset->fs_dirrotor = entry->fse_dirnext;
-				break;
-			case FILESET_PICKLEAFDIR:
-				entry = fileset->fs_leafdirrotor;
-				if (entry == NULL)
-					fileset->fs_leafdirrotor =
-					    entry = fileset->fs_leafdirlist;
-				fileset->fs_leafdirrotor =
-				    entry->fse_leafdirnext;
-				break;
-			}
+			if (filebench_randomno64(&index64, max_entries, 1,
+			    NULL) == FILEBENCH_ERROR)
+				return (NULL);
 		}
 
-		if (first == entry)
+		entry = fileset_find_entry(atp, (int)index64);
+
+		if (entry == NULL)
 			goto empty;
 
-		if (first == NULL)
-			first = entry;
+	} else if (flags & FILESET_PICKBYINDEX) {
+		/* pick by supplied index */
+		entry = fileset_find_entry(atp, index);
 
-		/* see if entry in use */
-		if (entry->fse_flags & FSE_BUSY) {
+	} else {
+		/* pick in rotation */
+		switch (flags & FILESET_PICKMASK) {
+		case FILESET_PICKFILE:
+			if (flags & FILESET_PICKNOEXIST) {
+				entry = fileset_find_entry(atp,
+				    fileset->fs_file_nerotor);
+				fileset->fs_file_nerotor =
+				    entry->fse_index + 1;
+			} else {
+				entry = fileset_find_entry(atp,
+				    fileset->fs_file_exrotor[tid]);
+				fileset->fs_file_exrotor[tid] =
+				    entry->fse_index + 1;
+			}
+			break;
 
-			/* it is, so try next */
-			entry = NULL;
-			continue;
+		case FILESET_PICKDIR:
+			entry = fileset_find_entry(atp, fileset->fs_dirrotor);
+			fileset->fs_dirrotor = entry->fse_index + 1;
+			break;
+
+		case FILESET_PICKLEAFDIR:
+			if (flags & FILESET_PICKNOEXIST) {
+				entry = fileset_find_entry(atp,
+				    fileset->fs_leafdir_nerotor);
+				fileset->fs_leafdir_nerotor =
+				    entry->fse_index + 1;
+			} else {
+				entry = fileset_find_entry(atp,
+				    fileset->fs_leafdir_exrotor);
+				fileset->fs_leafdir_exrotor =
+				    entry->fse_index + 1;
+			}
+			break;
 		}
+	}
+
+	if (entry == NULL)
+		goto empty;
 
-		/* If we ask for an existing file, go round again */
-		if ((flags & FILESET_PICKEXISTS) &&
-		    !(entry->fse_flags & FSE_EXISTS))
-			entry = NULL;
+	/* see if entry in use */
+	start_point = entry;
+	while (entry->fse_flags & FSE_BUSY) {
+
+		/* it is, so try next */
+		entry = AVL_NEXT(atp, entry);
+		if (entry == NULL)
+			entry = avl_first(atp);
+
+		/* see if we have wrapped around */
+		if ((entry == NULL) || (entry == start_point)) {
+			filebench_log(LOG_DEBUG_SCRIPT,
+			    "All %d files are busy", avl_numnodes(atp));
+			goto empty;
+		}
 
-		/* If we ask for not an existing file, go round again */
-		if ((flags & FILESET_PICKNOEXIST) &&
-		    (entry->fse_flags & FSE_EXISTS))
-			entry = NULL;
 	}
 
 	/* update file or directory idle counts */
@@ -760,6 +824,7 @@ fileset_pick(fileset_t *fileset, int flags, int tid)
 	return (entry);
 
 empty:
+	filebench_log(LOG_DEBUG_SCRIPT, "No file found");
 	(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
 	return (NULL);
 }
@@ -770,7 +835,8 @@ empty:
  * existant or not, or leaves that designation alone.
  */
 void
-fileset_unbusy(filesetentry_t *entry, int update_exist, int new_exist_val)
+fileset_unbusy(filesetentry_t *entry, int update_exist,
+    int new_exist_val, int open_cnt_incr)
 {
 	fileset_t *fileset = NULL;
 
@@ -784,6 +850,99 @@ fileset_unbusy(filesetentry_t *entry, int update_exist, int new_exist_val)
 
 	(void) ipc_mutex_lock(&fileset->fs_pick_lock);
 
+	/* modify FSE_EXIST flag and actual dirs/files count, if requested */
+	if (update_exist) {
+		if (new_exist_val == TRUE) {
+			if (entry->fse_flags & FSE_FREE) {
+
+				/* asked to set and it was free */
+				entry->fse_flags |= FSE_EXISTS;
+				entry->fse_flags &= (~FSE_FREE);
+				switch (entry->fse_flags & FSE_TYPE_MASK) {
+				case FSE_TYPE_FILE:
+					fileset_move_entry(
+					    &fileset->fs_free_files,
+					    &fileset->fs_exist_files, entry);
+					break;
+
+				case FSE_TYPE_DIR:
+					break;
+
+				case FSE_TYPE_LEAFDIR:
+					fileset_move_entry(
+					    &fileset->fs_free_leaf_dirs,
+					    &fileset->fs_exist_leaf_dirs,
+					    entry);
+					break;
+				}
+
+			} else if (!(entry->fse_flags & FSE_EXISTS)) {
+
+				/* asked to set, and it was clear */
+				entry->fse_flags |= FSE_EXISTS;
+				switch (entry->fse_flags & FSE_TYPE_MASK) {
+				case FSE_TYPE_FILE:
+					fileset_move_entry(
+					    &fileset->fs_noex_files,
+					    &fileset->fs_exist_files, entry);
+					break;
+				case FSE_TYPE_DIR:
+					break;
+				case FSE_TYPE_LEAFDIR:
+					fileset_move_entry(
+					    &fileset->fs_noex_leaf_dirs,
+					    &fileset->fs_exist_leaf_dirs,
+					    entry);
+					break;
+				}
+			}
+		} else {
+			if (entry->fse_flags & FSE_FREE) {
+				/* asked to clear, and it was free */
+				entry->fse_flags &= (~(FSE_FREE | FSE_EXISTS));
+				switch (entry->fse_flags & FSE_TYPE_MASK) {
+				case FSE_TYPE_FILE:
+					fileset_move_entry(
+					    &fileset->fs_free_files,
+					    &fileset->fs_noex_files, entry);
+					break;
+
+				case FSE_TYPE_DIR:
+					break;
+
+				case FSE_TYPE_LEAFDIR:
+					fileset_move_entry(
+					    &fileset->fs_free_leaf_dirs,
+					    &fileset->fs_noex_leaf_dirs,
+					    entry);
+					break;
+				}
+			} else if (entry->fse_flags & FSE_EXISTS) {
+
+				/* asked to clear, and it was set */
+				entry->fse_flags &= (~FSE_EXISTS);
+				switch (entry->fse_flags & FSE_TYPE_MASK) {
+				case FSE_TYPE_FILE:
+					fileset_move_entry(
+					    &fileset->fs_exist_files,
+					    &fileset->fs_noex_files, entry);
+					break;
+				case FSE_TYPE_DIR:
+					break;
+				case FSE_TYPE_LEAFDIR:
+					fileset_move_entry(
+					    &fileset->fs_exist_leaf_dirs,
+					    &fileset->fs_noex_leaf_dirs,
+					    entry);
+					break;
+				}
+			}
+		}
+	}
+
+	/* update open count */
+	entry->fse_open_cnt += open_cnt_incr;
+
 	/* increment idle count, clear FSE_BUSY and signal IF it was busy */
 	if (entry->fse_flags & FSE_BUSY) {
 
@@ -806,6 +965,7 @@ fileset_unbusy(filesetentry_t *entry, int update_exist, int new_exist_val)
 				    &fileset->fs_idle_files_cv);
 			}
 			break;
+
 		case FSE_TYPE_DIR:
 			fileset->fs_idle_dirs++;
 			if (fileset->fs_idle_dirs == 1) {
@@ -813,6 +973,7 @@ fileset_unbusy(filesetentry_t *entry, int update_exist, int new_exist_val)
 				    &fileset->fs_idle_dirs_cv);
 			}
 			break;
+
 		case FSE_TYPE_LEAFDIR:
 			fileset->fs_idle_leafdirs++;
 			if (fileset->fs_idle_leafdirs == 1) {
@@ -823,43 +984,6 @@ fileset_unbusy(filesetentry_t *entry, int update_exist, int new_exist_val)
 		}
 	}
 
-	/* modify FSE_EXIST flag and actual dirs/files count, if requested */
-	if (update_exist) {
-		if (new_exist_val == TRUE) {
-			if (!(entry->fse_flags & FSE_EXISTS)) {
-
-				/* asked to set, and it was clear */
-				entry->fse_flags |= FSE_EXISTS;
-				switch (entry->fse_flags & FSE_TYPE_MASK) {
-				case FSE_TYPE_FILE:
-					fileset->fs_num_act_files++;
-					break;
-				case FSE_TYPE_DIR:
-					break;
-				case FSE_TYPE_LEAFDIR:
-					fileset->fs_num_act_leafdirs++;
-					break;
-				}
-			}
-		} else {
-			if (entry->fse_flags & FSE_EXISTS) {
-
-				/* asked to clear, and it was set */
-				entry->fse_flags &= (~FSE_EXISTS);
-				switch (entry->fse_flags & FSE_TYPE_MASK) {
-				case FSE_TYPE_FILE:
-					fileset->fs_num_act_files--;
-					break;
-				case FSE_TYPE_DIR:
-					break;
-				case FSE_TYPE_LEAFDIR:
-					fileset->fs_num_act_leafdirs--;
-					break;
-				}
-			}
-		}
-	}
-
 	(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
 }
 
@@ -884,7 +1008,6 @@ fileset_create(fileset_t *fileset)
 	filesetentry_t *entry;
 	char path[MAXPATHLEN];
 	struct stat64 sb;
-	int pickflags;
 	hrtime_t start = gethrtime();
 	char *fileset_path;
 	char *fileset_name;
@@ -904,9 +1027,6 @@ fileset_create(fileset_t *fileset)
 		return (FILEBENCH_ERROR);
 	}
 
-	/* declare all files currently non existant (single threaded code) */
-	fileset->fs_num_act_files = 0;
-
 #ifdef HAVE_RAW_SUPPORT
 	/* treat raw device as special case */
 	if (fileset->fs_attrs & FILESET_IS_RAW_DEV)
@@ -962,27 +1082,23 @@ fileset_create(fileset_t *fileset)
 	filebench_log(LOG_VERBOSE, "Creating %s %s...",
 	    fileset_entity_name(fileset), fileset_name);
 
-	if (!avd_get_bool(fileset->fs_prealloc))
-		goto exit;
-
 	randno = ((RAND_MAX * (100
 	    - avd_get_int(fileset->fs_preallocpercent))) / 100);
 
 	/* alloc any files, as required */
-	pickflags = FILESET_PICKUNIQUE | FILESET_PICKRESET;
-	while (entry = fileset_pick(fileset, pickflags, 0)) {
+	fileset_pickreset(fileset, FILESET_PICKFILE);
+	while (entry = fileset_pick(fileset,
+	    FILESET_PICKFREE | FILESET_PICKFILE, 0, 0)) {
 		pthread_t tid;
 		int newrand;
 
-		pickflags = FILESET_PICKUNIQUE;
-
-		/* entry doesn't need to be locked during initialization */
-		fileset_unbusy(entry, FALSE, FALSE);
-
 		newrand = rand();
 
-		if (newrand < randno)
+		if (newrand < randno) {
+			/* unbusy the unallocated entry */
+			fileset_unbusy(entry, TRUE, FALSE, 0);
 			continue;
+		}
 
 		preallocated++;
 
@@ -1041,17 +1157,15 @@ fileset_create(fileset_t *fileset)
 	}
 
 	/* alloc any leaf directories, as required */
-	pickflags =
-	    FILESET_PICKUNIQUE | FILESET_PICKRESET | FILESET_PICKLEAFDIR;
-	while (entry = fileset_pick(fileset, pickflags, 0)) {
-
-		pickflags = FILESET_PICKUNIQUE | FILESET_PICKLEAFDIR;
+	fileset_pickreset(fileset, FILESET_PICKLEAFDIR);
+	while (entry = fileset_pick(fileset,
+	    FILESET_PICKFREE | FILESET_PICKLEAFDIR, 0, 0)) {
 
-		/* entry doesn't need to be locked during initialization */
-		fileset_unbusy(entry, FALSE, FALSE);
-
-		if (rand() < randno)
+		if (rand() < randno) {
+			/* unbusy the unallocated entry */
+			fileset_unbusy(entry, TRUE, FALSE, 0);
 			continue;
+		}
 
 		preallocated++;
 
@@ -1082,11 +1196,14 @@ exit:
 static void
 fileset_insfilelist(fileset_t *fileset, filesetentry_t *entry)
 {
+	entry->fse_flags = FSE_TYPE_FILE | FSE_FREE;
+	avl_add(&fileset->fs_free_files, entry);
+
 	if (fileset->fs_filelist == NULL) {
 		fileset->fs_filelist = entry;
-		entry->fse_filenext = NULL;
+		entry->fse_nextoftype = NULL;
 	} else {
-		entry->fse_filenext = fileset->fs_filelist;
+		entry->fse_nextoftype = fileset->fs_filelist;
 		fileset->fs_filelist = entry;
 	}
 }
@@ -1098,11 +1215,14 @@ fileset_insfilelist(fileset_t *fileset, filesetentry_t *entry)
 static void
 fileset_insdirlist(fileset_t *fileset, filesetentry_t *entry)
 {
+	entry->fse_flags = FSE_TYPE_DIR | FSE_EXISTS;
+	avl_add(&fileset->fs_dirs, entry);
+
 	if (fileset->fs_dirlist == NULL) {
 		fileset->fs_dirlist = entry;
-		entry->fse_dirnext = NULL;
+		entry->fse_nextoftype = NULL;
 	} else {
-		entry->fse_dirnext = fileset->fs_dirlist;
+		entry->fse_nextoftype = fileset->fs_dirlist;
 		fileset->fs_dirlist = entry;
 	}
 }
@@ -1114,16 +1234,36 @@ fileset_insdirlist(fileset_t *fileset, filesetentry_t *entry)
 static void
 fileset_insleafdirlist(fileset_t *fileset, filesetentry_t *entry)
 {
+	entry->fse_flags = FSE_TYPE_LEAFDIR | FSE_FREE;
+	avl_add(&fileset->fs_free_leaf_dirs, entry);
+
 	if (fileset->fs_leafdirlist == NULL) {
 		fileset->fs_leafdirlist = entry;
-		entry->fse_leafdirnext = NULL;
+		entry->fse_nextoftype = NULL;
 	} else {
-		entry->fse_leafdirnext = fileset->fs_leafdirlist;
+		entry->fse_nextoftype = fileset->fs_leafdirlist;
 		fileset->fs_leafdirlist = entry;
 	}
 }
 
 /*
+ * Compares two fileset entries to determine their relative order
+ */
+static int
+fileset_entry_compare(const void *node_1, const void *node_2)
+{
+	if (((filesetentry_t *)node_1)->fse_index <
+	    ((filesetentry_t *)node_2)->fse_index)
+		return (-1);
+
+	if (((filesetentry_t *)node_1)->fse_index ==
+	    ((filesetentry_t *)node_2)->fse_index)
+		return (0);
+
+	return (1);
+}
+
+/*
  * Obtains a filesetentry entity for a file to be placed in a
  * (sub)directory of a fileset. The size of the file may be
  * specified by fileset_meansize, or calculated from a gamma
@@ -1141,6 +1281,7 @@ fileset_populate_file(fileset_t *fileset, filesetentry_t *parent, int serial)
 	char tmpname[16];
 	filesetentry_t *entry;
 	double drand;
+	uint_t index;
 
 	if ((entry = (filesetentry_t *)ipc_malloc(FILEBENCH_FILESETENTRY))
 	    == NULL) {
@@ -1151,12 +1292,12 @@ fileset_populate_file(fileset_t *fileset, filesetentry_t *parent, int serial)
 
 	/* Another currently idle file */
 	(void) ipc_mutex_lock(&fileset->fs_pick_lock);
-	fileset->fs_idle_files++;
+	index = fileset->fs_idle_files++;
 	(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
 
+	entry->fse_index = index;
 	entry->fse_parent = parent;
 	entry->fse_fileset = fileset;
-	entry->fse_flags = FSE_TYPE_FILE | FSE_FREE;
 	fileset_insfilelist(fileset, entry);
 
 	(void) snprintf(tmpname, sizeof (tmpname), "%08d", serial);
@@ -1203,6 +1344,7 @@ fileset_populate_leafdir(fileset_t *fileset, filesetentry_t *parent, int serial)
 {
 	char tmpname[16];
 	filesetentry_t *entry;
+	uint_t index;
 
 	if ((entry = (filesetentry_t *)ipc_malloc(FILEBENCH_FILESETENTRY))
 	    == NULL) {
@@ -1213,12 +1355,12 @@ fileset_populate_leafdir(fileset_t *fileset, filesetentry_t *parent, int serial)
 
 	/* Another currently idle leaf directory */
 	(void) ipc_mutex_lock(&fileset->fs_pick_lock);
-	fileset->fs_idle_leafdirs++;
+	index = fileset->fs_idle_leafdirs++;
 	(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
 
+	entry->fse_index = index;
 	entry->fse_parent = parent;
 	entry->fse_fileset = fileset;
-	entry->fse_flags = FSE_TYPE_LEAFDIR | FSE_FREE;
 	fileset_insleafdirlist(fileset, entry);
 
 	(void) snprintf(tmpname, sizeof (tmpname), "%08d", serial);
@@ -1260,6 +1402,7 @@ fileset_populate_subdir(fileset_t *fileset, filesetentry_t *parent,
 	char tmpname[16];
 	filesetentry_t *entry;
 	int i;
+	uint_t index;
 
 	depth += 1;
 
@@ -1273,7 +1416,7 @@ fileset_populate_subdir(fileset_t *fileset, filesetentry_t *parent,
 
 	/* another idle directory */
 	(void) ipc_mutex_lock(&fileset->fs_pick_lock);
-	fileset->fs_idle_dirs++;
+	index = fileset->fs_idle_dirs++;
 	(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
 
 	(void) snprintf(tmpname, sizeof (tmpname), "%08d", serial);
@@ -1283,9 +1426,9 @@ fileset_populate_subdir(fileset_t *fileset, filesetentry_t *parent,
 		return (FILEBENCH_ERROR);
 	}
 
+	entry->fse_index = index;
 	entry->fse_parent = parent;
 	entry->fse_fileset = fileset;
-	entry->fse_flags = FSE_TYPE_DIR | FSE_FREE;
 	fileset_insdirlist(fileset, entry);
 
 	if (fileset->fs_dirdepthrv) {
@@ -1379,8 +1522,8 @@ fileset_populate_subdir(fileset_t *fileset, filesetentry_t *parent,
 static int
 fileset_populate(fileset_t *fileset)
 {
-	int entries = (int)avd_get_int(fileset->fs_entries);
-	int leafdirs = (int)avd_get_int(fileset->fs_leafdirs);
+	fbint_t entries = avd_get_int(fileset->fs_entries);
+	fbint_t leafdirs = avd_get_int(fileset->fs_leafdirs);
 	int meandirwidth;
 	int ret;
 
@@ -1401,10 +1544,6 @@ fileset_populate(fileset_t *fileset)
 	fileset->fs_constentries = entries;
 	fileset->fs_constleafdirs = leafdirs;
 
-	/* declare all files and leafdirs currently non existant */
-	fileset->fs_num_act_files = 0;
-	fileset->fs_num_act_leafdirs = 0;
-
 	/* initialize idle files and directories condition variables */
 	(void) pthread_cond_init(&fileset->fs_idle_files_cv, ipc_condattr());
 	(void) pthread_cond_init(&fileset->fs_idle_dirs_cv, ipc_condattr());
@@ -1418,8 +1557,26 @@ fileset_populate(fileset_t *fileset)
 	/* initialize locks and other condition variables */
 	(void) pthread_mutex_init(&fileset->fs_pick_lock,
 	    ipc_mutexattr(IPC_MUTEX_NORMAL));
+	(void) pthread_mutex_init(&fileset->fs_histo_lock,
+	    ipc_mutexattr(IPC_MUTEX_NORMAL));
 	(void) pthread_cond_init(&fileset->fs_thrd_wait_cv, ipc_condattr());
 
+	/* Initialize avl btrees */
+	avl_create(&(fileset->fs_free_files), fileset_entry_compare,
+	    sizeof (filesetentry_t), FSE_OFFSETOF(fse_link));
+	avl_create(&(fileset->fs_noex_files), fileset_entry_compare,
+	    sizeof (filesetentry_t), FSE_OFFSETOF(fse_link));
+	avl_create(&(fileset->fs_exist_files), fileset_entry_compare,
+	    sizeof (filesetentry_t), FSE_OFFSETOF(fse_link));
+	avl_create(&(fileset->fs_free_leaf_dirs), fileset_entry_compare,
+	    sizeof (filesetentry_t), FSE_OFFSETOF(fse_link));
+	avl_create(&(fileset->fs_noex_leaf_dirs), fileset_entry_compare,
+	    sizeof (filesetentry_t), FSE_OFFSETOF(fse_link));
+	avl_create(&(fileset->fs_exist_leaf_dirs), fileset_entry_compare,
+	    sizeof (filesetentry_t), FSE_OFFSETOF(fse_link));
+	avl_create(&(fileset->fs_dirs), fileset_entry_compare,
+	    sizeof (filesetentry_t), FSE_OFFSETOF(fse_link));
+
 	/* is dirwidth a random variable? */
 	if (AVD_IS_RANDOM(fileset->fs_dirwidth)) {
 		meandirwidth =
@@ -1505,6 +1662,7 @@ fileset_define(avd_t name)
 
 	fileset->fs_dirgamma = avd_int_alloc(1500);
 	fileset->fs_sizegamma = avd_int_alloc(1500);
+	fileset->fs_histo_id = -1;
 
 	/* Add fileset to global list */
 	if (filebench_shm->shm_filesetlist == NULL) {
@@ -1643,7 +1801,7 @@ fileset_find(char *name)
  * time the command has been executed since the current
  * call to fileset_iter.
  */
-void
+int
 fileset_iter(int (*cmd)(fileset_t *fileset, int first))
 {
 	fileset_t *fileset = filebench_shm->shm_filesetlist;
@@ -1652,12 +1810,17 @@ fileset_iter(int (*cmd)(fileset_t *fileset, int first))
 	(void) ipc_mutex_lock(&filebench_shm->shm_fileset_lock);
 
 	while (fileset) {
-		cmd(fileset, count == 0);
+		if (cmd(fileset, count == 0) == FILEBENCH_ERROR) {
+			(void) ipc_mutex_unlock(
+			    &filebench_shm->shm_fileset_lock);
+			return (FILEBENCH_ERROR);
+		}
 		fileset = fileset->fs_next;
 		count++;
 	}
 
 	(void) ipc_mutex_unlock(&filebench_shm->shm_fileset_lock);
+	return (FILEBENCH_OK);
 }
 
 /*
diff --git a/usr/src/cmd/filebench/common/fileset.h b/usr/src/cmd/filebench/common/fileset.h
index fa08b443c5..1250d50c32 100644
--- a/usr/src/cmd/filebench/common/fileset.h
+++ b/usr/src/cmd/filebench/common/fileset.h
@@ -39,7 +39,6 @@
 #define	off64_t off_t
 #endif /* HAVE_OFF64_T */
 
-
 #include <stdio.h>
 #include <stdlib.h>
 #include <unistd.h>
@@ -50,6 +49,7 @@
 #include <pthread.h>
 
 #include "vars.h"
+#include "fb_avl.h"
 #define	FILE_ALLOC_BLOCK (off64_t)(1024 * 1024)
 
 #ifdef	__cplusplus
@@ -70,18 +70,22 @@ extern "C" {
 #define	FSE_THRD_WAITNG		0x40
 
 typedef struct filesetentry {
-	struct filesetentry	*fse_next;
-	struct filesetentry	*fse_parent;
-	struct filesetentry	*fse_filenext;	/* List of files */
-	struct filesetentry	*fse_dirnext;	/* List of directories */
-	struct filesetentry	*fse_leafdirnext; /* List of leaf dirs */
+	struct filesetentry	*fse_next;	/* master list of entries */
+	struct filesetentry	*fse_parent;	/* link to directory */
+	avl_node_t		fse_link;	/* links in avl btree, prot. */
+						/*    by fs_pick_lock */
+	uint_t			fse_index;	/* file order number */
+	struct filesetentry	*fse_nextoftype; /* List of specific fse */
 	struct fileset		*fse_fileset;	/* Parent fileset */
 	char			*fse_path;
 	int			fse_depth;
 	off64_t			fse_size;
+	int			fse_open_cnt;	/* protected by fs_pick_lock */
 	int			fse_flags;	/* protected by fs_pick_lock */
 } filesetentry_t;
 
+#define	FSE_OFFSETOF(f)	((size_t)(&(((filesetentry_t *)0)->f)))
+
 /* type of fileset entry to obtain */
 #define	FILESET_PICKFILE    0x00 /* Pick a file from the set */
 #define	FILESET_PICKDIR	    0x01 /* Pick a directory */
@@ -90,9 +94,10 @@ typedef struct filesetentry {
 /* other pick flags */
 #define	FILESET_PICKUNIQUE  0x04 /* Pick a unique file or leafdir from the */
 				    /* fileset until empty */
-#define	FILESET_PICKRESET   0x08 /* Reset FILESET_PICKUNIQUE selection list */
 #define	FILESET_PICKEXISTS  0x10 /* Pick an existing file */
 #define	FILESET_PICKNOEXIST 0x20 /* Pick a file that doesn't exist */
+#define	FILESET_PICKBYINDEX 0x40 /* use supplied index number to select file */
+#define	FILESET_PICKFREE    FILESET_PICKUNIQUE
 
 /* fileset attributes */
 #define	FILESET_IS_RAW_DEV  0x01 /* fileset is a raw device */
@@ -134,32 +139,37 @@ typedef struct fileset {
 
 	int64_t		fs_idle_files;	/* number of files NOT busy */
 	pthread_cond_t	fs_idle_files_cv; /* idle files condition variable */
-	fbint_t		fs_num_act_files;   /* total number of files */
-					    /* actually existing in the */
-					    /* host or server's file system */
+
 	int64_t		fs_idle_dirs;	/* number of dirs NOT busy */
 	pthread_cond_t	fs_idle_dirs_cv; /* idle dirs condition variable */
 
 	int64_t		fs_idle_leafdirs; /* number of dirs NOT busy */
 	pthread_cond_t	fs_idle_leafdirs_cv; /* idle dirs condition variable */
-	fbint_t		fs_num_act_leafdirs; /* total number of leaf dirs */
-					    /* actually existing in the */
-					    /* host or server's file system */
+
 	pthread_mutex_t	fs_pick_lock;	/* per fileset "pick" function lock */
 	pthread_cond_t	fs_thrd_wait_cv; /* per fileset file busy wait cv */
+	avl_tree_t	fs_free_files;	/* btree of free files */
+	avl_tree_t	fs_exist_files;	/* btree of files on device */
+	avl_tree_t	fs_noex_files;	/* btree of files NOT on device */
+	avl_tree_t	fs_dirs;	/* btree of internal dirs */
+	avl_tree_t	fs_free_leaf_dirs; /* btree of free leaf dirs */
+	avl_tree_t	fs_exist_leaf_dirs; /* btree of leaf dirs on device */
+	avl_tree_t	fs_noex_leaf_dirs;  /* btree of leaf dirs NOT */
+					    /* currently on device */
 	filesetentry_t	*fs_filelist;	/* List of files */
-	filesetentry_t	*fs_filefree;	/* Ptr to next free file */
-	filesetentry_t	*fs_filerotor[FSE_MAXTID];	/* next file to */
+	uint_t		fs_file_exrotor[FSE_MAXTID];	/* next file to */
 							/* select */
-	filesetentry_t	*fs_file_ne_rotor;	/* next non existent file */
+	uint_t		fs_file_nerotor;	/* next non existent file */
 						/* to select for createfile */
 	filesetentry_t	*fs_dirlist;	/* List of directories */
-	filesetentry_t	*fs_dirfree;	/* List of free directories */
-	filesetentry_t	*fs_dirrotor;	/* Ptr to next directory to select */
+	uint_t		fs_dirrotor;	/* index of next directory to select */
 	filesetentry_t	*fs_leafdirlist; /* List of leaf directories */
-	filesetentry_t	*fs_leafdirfree; /* Ptr to next free leaf directory */
-	filesetentry_t	*fs_leafdirrotor;	/* Ptr to next leaf */
+	uint_t		fs_leafdir_exrotor;	/* Ptr to next existing leaf */
 						/* directory to select */
+	uint_t		fs_leafdir_nerotor;	/* Ptr to next non-existing */
+	int		*fs_filehistop;		/* Ptr to access histogram */
+	int		fs_histo_id;	/* shared memory id for filehisto */
+	pthread_mutex_t	fs_histo_lock;	/* lock for incr of histo */
 } fileset_t;
 
 int fileset_createset(fileset_t *);
@@ -167,13 +177,16 @@ int fileset_openfile(fileset_t *fileset, filesetentry_t *entry,
     int flag, int mode, int attrs);
 fileset_t *fileset_define(avd_t);
 fileset_t *fileset_find(char *name);
-filesetentry_t *fileset_pick(fileset_t *fileset, int flags, int tid);
+filesetentry_t *fileset_pick(fileset_t *fileset, int flags, int tid,
+    int index);
 char *fileset_resolvepath(filesetentry_t *entry);
 void fileset_usage(void);
-void fileset_iter(int (*cmd)(fileset_t *fileset, int first));
+int fileset_iter(int (*cmd)(fileset_t *fileset, int first));
 int fileset_print(fileset_t *fileset, int first);
 void fileset_unbusy(filesetentry_t *entry, int update_exist,
-    int new_exist_val);
+    int new_exist_val, int open_cnt_incr);
+int fileset_dump_histo(fileset_t *fileset, int first);
+void fileset_attach_all_histos(void);
 
 #ifdef	__cplusplus
 }
diff --git a/usr/src/cmd/filebench/common/flowop.h b/usr/src/cmd/filebench/common/flowop.h
index f04e9c55e6..976c3d0505 100644
--- a/usr/src/cmd/filebench/common/flowop.h
+++ b/usr/src/cmd/filebench/common/flowop.h
@@ -26,9 +26,6 @@
 #ifndef	_FB_FLOWOP_H
 #define	_FB_FLOWOP_H
 
-
-#pragma ident	"%Z%%M%	%I%	%E% SMI"
-
 #include "config.h"
 
 #include <stdio.h>
@@ -88,6 +85,7 @@ typedef struct flowop {
 	avd_t		fo_blocking;	/* Attr */
 	avd_t		fo_directio;	/* Attr */
 	avd_t		fo_rotatefd;	/* Attr */
+	avd_t		fo_fileindex;	/* Attr */
 	flowstat_t	fo_stats;	/* Flow statistics */
 	pthread_cond_t	fo_cv;		/* Block/wakeup cv */
 	pthread_mutex_t	fo_lock;	/* Mutex around flowop */
diff --git a/usr/src/cmd/filebench/common/flowop_library.c b/usr/src/cmd/filebench/common/flowop_library.c
index 7727c169a8..b2ad1cf28f 100644
--- a/usr/src/cmd/filebench/common/flowop_library.c
+++ b/usr/src/cmd/filebench/common/flowop_library.c
@@ -310,6 +310,84 @@ flowoplib_fileattrs(flowop_t *flowop)
 }
 
 /*
+ * Obtain a filesetentry for a file. Result placed where filep points.
+ * Supply with a flowop and a flag to indicate whether an existent or
+ * non-existent file is required. Returns FILEBENCH_NORSC if all out
+ * of the appropriate type of directories, FILEBENCH_ERROR if the
+ * flowop does not point to a fileset, and FILEBENCH_OK otherwise.
+ */
+static int
+flowoplib_pickfile(filesetentry_t **filep, flowop_t *flowop, int flags, int tid)
+{
+	fileset_t	*fileset;
+	int		fileindex;
+
+	if ((fileset = flowop->fo_fileset) == NULL) {
+		filebench_log(LOG_ERROR, "flowop NO fileset");
+		return (FILEBENCH_ERROR);
+	}
+
+	if (flowop->fo_fileindex) {
+		fileindex = (int)(avd_get_dbl(flowop->fo_fileindex) *
+		    ((double)(fileset->fs_constentries / 2)));
+		fileindex = fileindex % fileset->fs_constentries;
+		flags |= FILESET_PICKBYINDEX;
+	} else {
+		fileindex = 0;
+	}
+
+	if ((*filep = fileset_pick(fileset, FILESET_PICKFILE | flags,
+	    tid, fileindex)) == NULL) {
+		filebench_log(LOG_DEBUG_SCRIPT,
+		    "flowop %s failed to pick file from fileset %s",
+		    flowop->fo_name,
+		    avd_get_str(fileset->fs_name));
+		return (FILEBENCH_NORSC);
+	}
+
+	return (FILEBENCH_OK);
+}
+
+/*
+ * Obtain a filesetentry for a leaf directory. Result placed where dirp
+ * points. Supply with flowop and a flag to indicate whether an existent
+ * or non-existent leaf directory is required. Returns FILEBENCH_NORSC
+ * if all out of the appropriate type of directories, FILEBENCH_ERROR
+ * if the flowop does not point to a fileset, and FILEBENCH_OK otherwise.
+ */
+static int
+flowoplib_pickleafdir(filesetentry_t **dirp, flowop_t *flowop, int flags)
+{
+	fileset_t	*fileset;
+	int		dirindex;
+
+	if ((fileset = flowop->fo_fileset) == NULL) {
+		filebench_log(LOG_ERROR, "flowop NO fileset");
+		return (FILEBENCH_ERROR);
+	}
+
+	if (flowop->fo_fileindex) {
+		dirindex = (int)(avd_get_dbl(flowop->fo_fileindex) *
+		    ((double)(fileset->fs_constleafdirs / 2)));
+		dirindex = dirindex % fileset->fs_constleafdirs;
+		flags |= FILESET_PICKBYINDEX;
+	} else {
+		dirindex = 0;
+	}
+
+	if ((*dirp = fileset_pick(fileset,
+	    FILESET_PICKLEAFDIR | flags, 0, dirindex)) == NULL) {
+		filebench_log(LOG_DEBUG_SCRIPT,
+		    "flowop %s failed to pick directory from fileset %s",
+		    flowop->fo_name,
+		    avd_get_str(fileset->fs_name));
+		return (FILEBENCH_NORSC);
+	}
+
+	return (FILEBENCH_OK);
+}
+
+/*
  * Searches for a file descriptor. Tries the flowop's
  * fo_fdnumber first and returns with it if it has been
  * explicitly set (greater than 0). It next checks to
@@ -1753,6 +1831,7 @@ flowoplib_openfile_common(threadflow_t *threadflow, flowop_t *flowop, int fd)
 	filesetentry_t *file;
 	char *fileset_name;
 	int tid = 0;
+	int err;
 
 	if (flowop->fo_fileset == NULL) {
 		filebench_log(LOG_ERROR, "flowop NULL file");
@@ -1822,12 +1901,12 @@ flowoplib_openfile_common(threadflow_t *threadflow, flowop_t *flowop, int fd)
 	}
 #endif /* HAVE_RAW_SUPPORT */
 
-	if ((file = fileset_pick(flowop->fo_fileset,
-	    FILESET_PICKEXISTS, tid)) == NULL) {
+	if ((err = flowoplib_pickfile(&file, flowop,
+	    FILESET_PICKEXISTS, tid)) != FILEBENCH_OK) {
 		filebench_log(LOG_DEBUG_SCRIPT,
 		    "flowop %s failed to pick file from %s on fd %d",
 		    flowop->fo_name, fileset_name, fd);
-		return (FILEBENCH_NORSC);
+		return (err);
 	}
 
 	threadflow->tf_fse[fd] = file;
@@ -1853,7 +1932,7 @@ flowoplib_openfile_common(threadflow_t *threadflow, flowop_t *flowop, int fd)
 /*
  * Emulate create of a file. Uses the flowop's fdnumber to select
  * tf_fd and tf_fse array locations to put the created file's file
- * descriptor and filesetentry respectively. Uses fileset_pick()
+ * descriptor and filesetentry respectively. Uses flowoplib_pickfile()
  * to select a specific filesetentry whose file does not currently
  * exist for the file create operation. Then calls
  * fileset_openfile() with the O_CREATE flag set to create the
@@ -1867,6 +1946,7 @@ flowoplib_createfile(threadflow_t *threadflow, flowop_t *flowop)
 {
 	filesetentry_t *file;
 	int fd = flowop->fo_fdnumber;
+	int err;
 
 	if (threadflow->tf_fd[fd] != 0) {
 		filebench_log(LOG_ERROR,
@@ -1890,13 +1970,13 @@ flowoplib_createfile(threadflow_t *threadflow, flowop_t *flowop)
 	}
 #endif /* HAVE_RAW_SUPPORT */
 
-	if ((file = fileset_pick(flowop->fo_fileset,
-	    FILESET_PICKNOEXIST, 0)) == NULL) {
+	if ((err = flowoplib_pickfile(&file, flowop,
+	    FILESET_PICKNOEXIST, 0)) != FILEBENCH_OK) {
 		filebench_log(LOG_DEBUG_SCRIPT,
 		    "flowop %s failed to pick file from fileset %s",
 		    flowop->fo_name,
 		    avd_get_str(flowop->fo_fileset->fs_name));
-		return (FILEBENCH_NORSC);
+		return (err);
 	}
 
 	threadflow->tf_fse[fd] = file;
@@ -1940,19 +2020,13 @@ flowoplib_deletefile(threadflow_t *threadflow, flowop_t *flowop)
 	/* if fd specified, use it to access file */
 	if ((fd > 0) && ((file = threadflow->tf_fse[fd]) != NULL)) {
 
-		/* check whether file still open */
-		if (threadflow->tf_fd[fd] > 0) {
-			filebench_log(LOG_DEBUG_SCRIPT,
-			    "flowop %s deleting still open file at fd = %d",
-			    flowop->fo_name, fd);
-		}
-
 		/* indicate that the file will be deleted */
 		threadflow->tf_fse[fd] = NULL;
 
 		/* if here, we still have a valid file pointer */
 		fileset = file->fse_fileset;
 	} else {
+
 		/* Otherwise, pick arbitrary file */
 		file = NULL;
 		fileset = flowop->fo_fileset;
@@ -1975,12 +2049,14 @@ flowoplib_deletefile(threadflow_t *threadflow, flowop_t *flowop)
 #endif /* HAVE_RAW_SUPPORT */
 
 	if (file == NULL) {
+		int err;
+
 		/* pick arbitrary, existing (allocated) file */
-		if ((file = fileset_pick(fileset, FILESET_PICKEXISTS, 0))
-		    == NULL) {
+		if ((err = flowoplib_pickfile(&file, flowop,
+		    FILESET_PICKEXISTS, 0)) != FILEBENCH_OK) {
 			filebench_log(LOG_DEBUG_SCRIPT,
 			    "flowop %s failed to pick file", flowop->fo_name);
-			return (FILEBENCH_NORSC);
+			return (err);
 		}
 	} else {
 		/* delete specific file. wait for it to be non-busy */
@@ -1997,6 +2073,28 @@ flowoplib_deletefile(threadflow_t *threadflow, flowop_t *flowop)
 		(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
 	}
 
+	/* don't delete if anyone (other than me) has file open */
+	if ((fd > 0) && (threadflow->tf_fd[fd] > 0)) {
+		if (file->fse_open_cnt > 1) {
+			filebench_log(LOG_DEBUG_SCRIPT,
+			    "flowop %s can't delete file opened by other"
+			    " threads at fd = %d", flowop->fo_name, fd);
+			fileset_unbusy(file, FALSE, FALSE, 0);
+			return (FILEBENCH_OK);
+		} else {
+			filebench_log(LOG_DEBUG_SCRIPT,
+			    "flowop %s deleting still open file at fd = %d",
+			    flowop->fo_name, fd);
+		}
+	} else if (file->fse_open_cnt > 0) {
+		filebench_log(LOG_DEBUG_SCRIPT,
+		    "flowop %s can't delete file opened by other"
+		    " threads at fd = %d, open count = %d",
+		    flowop->fo_name, fd, file->fse_open_cnt);
+		fileset_unbusy(file, FALSE, FALSE, 0);
+		return (FILEBENCH_OK);
+	}
+
 	(void) fb_strlcpy(path, avd_get_str(fileset->fs_path), MAXPATHLEN);
 	(void) fb_strlcat(path, "/", MAXPATHLEN);
 	(void) fb_strlcat(path, avd_get_str(fileset->fs_name), MAXPATHLEN);
@@ -2010,7 +2108,7 @@ flowoplib_deletefile(threadflow_t *threadflow, flowop_t *flowop)
 	flowop_endop(threadflow, flowop, 0);
 
 	/* indicate that it is no longer busy and no longer exists */
-	fileset_unbusy(file, TRUE, FALSE);
+	fileset_unbusy(file, TRUE, FALSE, -file->fse_open_cnt);
 
 	filebench_log(LOG_DEBUG_SCRIPT, "deleted file %s", file->fse_path);
 
@@ -2103,6 +2201,7 @@ static int
 flowoplib_closefile(threadflow_t *threadflow, flowop_t *flowop)
 {
 	filesetentry_t *file;
+	fileset_t *fileset;
 	int fd = flowop->fo_fdnumber;
 
 	if (threadflow->tf_fd[fd] == 0) {
@@ -2112,12 +2211,32 @@ flowoplib_closefile(threadflow_t *threadflow, flowop_t *flowop)
 		return (FILEBENCH_ERROR);
 	}
 
+	file = threadflow->tf_fse[fd];
+	fileset = file->fse_fileset;
+
+	/* Wait for it to be non-busy */
+	(void) ipc_mutex_lock(&fileset->fs_pick_lock);
+	while (file->fse_flags & FSE_BUSY) {
+		file->fse_flags |= FSE_THRD_WAITNG;
+		(void) pthread_cond_wait(&fileset->fs_thrd_wait_cv,
+		    &fileset->fs_pick_lock);
+	}
+
+	/* File now available, grab it for closing */
+	file->fse_flags |= FSE_BUSY;
+
+	/* if last open, set declare idle */
+	if (file->fse_open_cnt == 1)
+		fileset->fs_idle_files--;
+
+	(void) ipc_mutex_unlock(&fileset->fs_pick_lock);
+
 	/* Measure time to close */
 	flowop_beginop(threadflow, flowop);
 	(void) close(threadflow->tf_fd[fd]);
 	flowop_endop(threadflow, flowop, 0);
 
-	file = threadflow->tf_fse[fd];
+	fileset_unbusy(file, FALSE, FALSE, -1);
 
 	threadflow->tf_fd[fd] = 0;
 
@@ -2127,35 +2246,6 @@ flowoplib_closefile(threadflow_t *threadflow, flowop_t *flowop)
 }
 
 /*
- * Obtain a filesetentry for a leaf directory. Result placed where dirp
- * points. Supply with flowop and a flag to indicate whether an existent
- * or non-existent leaf directory is required. Returns FILEBENCH_NORSC
- * if all out of the appropriate type of directories, FILEBENCH_ERROR
- * if the flowop does not point to a fileset, and FILEBENCH_OK otherwise.
- */
-static int
-flowoplib_pickleafdir(filesetentry_t **dirp, flowop_t *flowop, int flags)
-{
-	fileset_t	*fileset;
-
-	if ((fileset = flowop->fo_fileset) == NULL) {
-		filebench_log(LOG_ERROR, "flowop NO fileset");
-		return (FILEBENCH_ERROR);
-	}
-
-	if ((*dirp = fileset_pick(fileset,
-	    FILESET_PICKLEAFDIR | flags, 0)) == NULL) {
-		filebench_log(LOG_DEBUG_SCRIPT,
-		    "flowop %s failed to pick directory from fileset %s",
-		    flowop->fo_name,
-		    avd_get_str(fileset->fs_name));
-		return (FILEBENCH_NORSC);
-	}
-
-	return (FILEBENCH_OK);
-}
-
-/*
  * Obtain the full pathname of the directory described by the filesetentry
  * indicated by "dir", and copy it into the character array pointed to by
  * path. Returns FILEBENCH_ERROR on errors, FILEBENCH_OK otherwise.
@@ -2217,7 +2307,7 @@ flowoplib_makedir(threadflow_t *threadflow, flowop_t *flowop)
 	flowop_endop(threadflow, flowop, 0);
 
 	/* indicate that it is no longer busy and now exists */
-	fileset_unbusy(dir, TRUE, TRUE);
+	fileset_unbusy(dir, TRUE, TRUE, 0);
 
 	return (FILEBENCH_OK);
 }
@@ -2249,7 +2339,7 @@ flowoplib_removedir(threadflow_t *threadflow, flowop_t *flowop)
 	flowop_endop(threadflow, flowop, 0);
 
 	/* indicate that it is no longer busy and no longer exists */
-	fileset_unbusy(dir, TRUE, FALSE);
+	fileset_unbusy(dir, TRUE, FALSE, 0);
 
 	return (FILEBENCH_OK);
 }
@@ -2281,13 +2371,12 @@ flowoplib_listdir(threadflow_t *threadflow, flowop_t *flowop)
 		return (FILEBENCH_ERROR);
 	}
 
-	if ((dir = fileset_pick(fileset,
-	    FILESET_PICKDIR, 0)) == NULL) {
+	if ((dir = fileset_pick(fileset, FILESET_PICKDIR, 0, 0)) == NULL) {
 		filebench_log(LOG_DEBUG_SCRIPT,
 		    "flowop %s failed to pick directory from fileset %s",
 		    flowop->fo_name,
 		    avd_get_str(fileset->fs_name));
-		return (FILEBENCH_NORSC);
+		return (FILEBENCH_ERROR);
 	}
 
 	if ((ret = flowoplib_getdirpath(dir, full_path)) != FILEBENCH_OK)
@@ -2315,7 +2404,7 @@ flowoplib_listdir(threadflow_t *threadflow, flowop_t *flowop)
 	flowop_endop(threadflow, flowop, dir_bytes);
 
 	/* indicate that it is no longer busy */
-	fileset_unbusy(dir, FALSE, FALSE);
+	fileset_unbusy(dir, FALSE, FALSE, 0);
 
 	return (FILEBENCH_OK);
 }
@@ -2373,14 +2462,15 @@ flowoplib_statfile(threadflow_t *threadflow, flowop_t *flowop)
 	if (file == NULL) {
 		char path[MAXPATHLEN];
 		char *pathtmp;
+		int err;
 
 		/* pick arbitrary, existing (allocated) file */
-		if ((file = fileset_pick(fileset, FILESET_PICKEXISTS, 0))
-		    == NULL) {
+		if ((err = flowoplib_pickfile(&file, flowop,
+		    FILESET_PICKEXISTS, 0)) != FILEBENCH_OK) {
 			filebench_log(LOG_DEBUG_SCRIPT,
 			    "Statfile flowop %s failed to pick file",
 			    flowop->fo_name);
-			return (FILEBENCH_NORSC);
+			return (err);
 		}
 
 		/* resolve path and do a stat on file */
@@ -2400,7 +2490,7 @@ flowoplib_statfile(threadflow_t *threadflow, flowop_t *flowop)
 			    "statfile flowop %s failed", flowop->fo_name);
 		flowop_endop(threadflow, flowop, 0);
 
-		fileset_unbusy(file, FALSE, FALSE);
+		fileset_unbusy(file, FALSE, FALSE, 0);
 	} else {
 		/* stat specific file */
 		flowop_beginop(threadflow, flowop);
diff --git a/usr/src/cmd/filebench/common/parser_gram.y b/usr/src/cmd/filebench/common/parser_gram.y
index d6424d30ff..e3a3594c5d 100644
--- a/usr/src/cmd/filebench/common/parser_gram.y
+++ b/usr/src/cmd/filebench/common/parser_gram.y
@@ -86,6 +86,7 @@ static cmd_t *alloc_cmd(void);
 static attr_t *alloc_attr(void);
 static attr_t *alloc_lvar_attr(var_t *var);
 static attr_t *get_attr(cmd_t *cmd, int64_t name);
+static attr_t *get_attr_fileset(cmd_t *cmd, int64_t name);
 static attr_t *get_attr_integer(cmd_t *cmd, int64_t name);
 static attr_t *get_attr_bool(cmd_t *cmd, int64_t name);
 static void get_attr_lvars(cmd_t *cmd, flowop_t *flowop);
@@ -185,7 +186,7 @@ static void parser_version(cmd_t *cmd);
 %token FSA_HIGHWATER FSA_DIRECTIO FSA_DIRWIDTH FSA_FD FSA_SRCFD FSA_ROTATEFD
 %token FSA_NAMELENGTH FSA_FILESIZE FSA_ENTRIES FSA_FILESIZEGAMMA FSA_DIRDEPTHRV
 %token FSA_DIRGAMMA FSA_USEISM FSA_TYPE FSA_RANDTABLE FSA_RANDSRC FSA_RANDROUND
-%token FSA_LEAFDIRS
+%token FSA_LEAFDIRS FSA_INDEXED
 %token FSA_RANDSEED FSA_RANDGAMMA FSA_RANDMEAN FSA_RANDMIN FSA_MASTER
 %token FSA_CLIENT
 %token FSS_TYPE FSS_SEED FSS_GAMMA FSS_MEAN FSS_MIN FSS_SRC FSS_ROUND
@@ -1438,6 +1439,8 @@ attrs_define_fileset:
 | FSA_DIRWIDTH { $$ = FSA_DIRWIDTH;}
 | FSA_DIRDEPTHRV { $$ = FSA_DIRDEPTHRV;}
 | FSA_PREALLOC { $$ = FSA_PREALLOC;}
+| FSA_PARALLOC { $$ = FSA_PARALLOC;}
+| FSA_REUSE { $$ = FSA_REUSE;}
 | FSA_FILESIZEGAMMA { $$ = FSA_FILESIZEGAMMA;}
 | FSA_DIRGAMMA { $$ = FSA_DIRGAMMA;}
 | FSA_CACHED { $$ = FSA_CACHED;}
@@ -1509,6 +1512,7 @@ attrs_flowop:
 | FSA_ROTATEFD { $$ = FSA_ROTATEFD;}
 | FSA_DSYNC { $$ = FSA_DSYNC;}
 | FSA_DIRECTIO { $$ = FSA_DIRECTIO;}
+| FSA_INDEXED { $$ = FSA_INDEXED;}
 | FSA_TARGET { $$ = FSA_TARGET;}
 | FSA_ITERS { $$ = FSA_ITERS;}
 | FSA_VALUE { $$ = FSA_VALUE;}
@@ -1619,8 +1623,7 @@ attr_list_value: var_string_list {
 	if (($$ = alloc_attr()) == NULL)
 		YYERROR;
 	$$->attr_param_list = $1;
-} | FSV_STRING
-{
+} | FSV_STRING {
 	if (($$ = alloc_attr()) == NULL)
 		YYERROR;
 	$$->attr_avd = avd_str_alloc($1);
@@ -1893,7 +1896,7 @@ parser_list2string(list_t *list)
 
 	*string = 0;
 
-
+	/*	printf("parser_list2string: called\n"); */
 	/* Format args */
 	for (l = list; l != NULL; l = l->list_next) {
 		char *lstr = avd_get_str(l->list_string);
@@ -1975,6 +1978,7 @@ parser_list2varstring(list_t *list)
 {
 	char *lstr = avd_get_str(list->list_string);
 
+	/*	printf("parser_list2varstring: Called\n"); */
 	/* Special case - variable name */
 	if ((list->list_next == NULL) && (*lstr == '$'))
 		return (var_ref_attr(lstr));
@@ -2244,7 +2248,7 @@ parser_thread_define(cmd_t *cmd, procflow_t *procflow, int procinstances)
 }
 
 /*
- * Files in the attributes for a newly allocated flowop
+ * Fills in the attributes for a newly allocated flowop
  */
 static void
 parser_flowop_get_attrs(cmd_t *cmd, flowop_t *flowop)
@@ -2333,6 +2337,12 @@ parser_flowop_get_attrs(cmd_t *cmd, flowop_t *flowop)
 	} else {
 		flowop->fo_highwater = avd_int_alloc(1);
 	}
+
+	/* find file or leaf directory by index number */
+	if (attr = get_attr_integer(cmd, FSA_INDEXED))
+		flowop->fo_fileindex = attr->attr_avd;
+	else
+		flowop->fo_fileindex = NULL;
 }
 
 /*
@@ -2591,7 +2601,7 @@ parser_fileset_define_common(cmd_t *cmd)
 	avd_t pathname;
 
 	/* Get the name of the file */
-	if (attr = get_attr(cmd, FSA_NAME)) {
+	if (attr = get_attr_fileset(cmd, FSA_NAME)) {
 		name = attr->attr_avd;
 	} else {
 		filebench_log(LOG_ERROR,
@@ -3597,12 +3607,6 @@ parser_randvar_define(cmd_t *cmd)
 	else
 		rndp->rnd_min = avd_int_alloc(0);
 
-	/* Get the mean value of the random distribution */
-	if (attr = get_attr_integer(cmd, FSA_RANDMEAN))
-		rndp->rnd_mean = attr->attr_avd;
-	else
-		rndp->rnd_mean = avd_int_alloc(0);
-
 	/* Get the roundoff value for the random distribution */
 	if (attr = get_attr_integer(cmd, FSA_RANDROUND))
 		rndp->rnd_round = attr->attr_avd;
@@ -3652,6 +3656,15 @@ parser_randvar_define(cmd_t *cmd)
 		rndp->rnd_gamma = attr->attr_avd;
 	else
 		rndp->rnd_gamma = avd_int_alloc(1500);
+
+	/* Get the mean value of the random distribution */
+	if (attr = get_attr_integer(cmd, FSA_RANDMEAN)) {
+		rndp->rnd_mean = attr->attr_avd;
+	} else if ((rndp->rnd_type & RAND_TYPE_MASK) == RAND_TYPE_GAMMA) {
+		rndp->rnd_mean = NULL;
+	} else {
+		rndp->rnd_mean = avd_int_alloc(0);
+	}
 }
 
 /*
@@ -3820,6 +3833,47 @@ alloc_lvar_attr(var_t *var)
 	return (attr);
 }
 
+
+/*
+ * Searches the attribute list for the command for the named attribute type.
+ * The attribute list is created by the parser from the list of attributes
+ * supplied with certain commands, such as the define and flowop commands.
+ * Returns a pointer to the attribute structure if the named attribute is
+ * found, otherwise returns NULL. If the attribute includes a parameter list,
+ * the list is converted to a string and stored in the attr_avd field of
+ * the returned attr_t struct.
+ */
+static attr_t *
+get_attr_fileset(cmd_t *cmd, int64_t name)
+{
+	attr_t *attr;
+	attr_t *rtn = NULL;
+	char *string;
+
+	for (attr = cmd->cmd_attr_list; attr != NULL;
+	    attr = attr->attr_next) {
+		filebench_log(LOG_DEBUG_IMPL,
+		    "attr %d = %d %llx?",
+		    attr->attr_name,
+		    name,
+		    attr->attr_avd);
+
+		if (attr->attr_name == name)
+			rtn = attr;
+	}
+
+	if (rtn == NULL)
+		return (NULL);
+
+	if (rtn->attr_param_list) {
+		filebench_log(LOG_DEBUG_SCRIPT, "attr is param list");
+		rtn->attr_avd = parser_list2varstring(rtn->attr_param_list);
+	}
+
+	return (rtn);
+}
+
+
 /*
  * Searches the attribute list for the command for the named attribute type.
  * The attribute list is created by the parser from the list of attributes
diff --git a/usr/src/cmd/filebench/common/parser_lex.l b/usr/src/cmd/filebench/common/parser_lex.l
index 6ac2645e86..7e22c7895b 100644
--- a/usr/src/cmd/filebench/common/parser_lex.l
+++ b/usr/src/cmd/filebench/common/parser_lex.l
@@ -118,6 +118,7 @@ filename                { return FSA_FILE; }
 filesetname             { return FSA_FILE; }
 instances               { return FSA_INSTANCES;}                  
 iosize                  { return FSA_IOSIZE; }
+indexed                 { return FSA_INDEXED; }
 iters                   { return FSA_ITERS;}
 master			{ return FSA_MASTER; }
 client			{ return FSA_CLIENT; }
diff --git a/usr/src/cmd/filebench/workloads/Makefile b/usr/src/cmd/filebench/workloads/Makefile
index f5dca4ac11..4716784876 100644
--- a/usr/src/cmd/filebench/workloads/Makefile
+++ b/usr/src/cmd/filebench/workloads/Makefile
@@ -58,6 +58,7 @@ WORKLOADS = \
 	multistreamwritedirect.f \
 	oltp.f \
 	openfiles.f \
+	randomfileaccess.f \
 	randomread.f \
 	randomrw.f \
 	randomwrite.f \
diff --git a/usr/src/cmd/filebench/workloads/compflow_demo.f b/usr/src/cmd/filebench/workloads/compflow_demo.f
index 4f2e836264..ec556396ab 100644
--- a/usr/src/cmd/filebench/workloads/compflow_demo.f
+++ b/usr/src/cmd/filebench/workloads/compflow_demo.f
@@ -21,8 +21,6 @@
 #
 # Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 # Use is subject to license terms.
-#
-# ident	"%Z%%M%	%I%	%E% SMI"
 
 set $dir=/tmp
 set $nfiles=700
@@ -31,11 +29,11 @@ set $filesize=128k
 set $nthreads=10
 set $meaniosize=16k
 
-define fileset name=usr1files,path=$dir,size=$filesize,entries=$nfiles,dirwidth=$meandirwidth,prealloc=80, paralloc
+define fileset name=bigfileset,path=$dir,size=$filesize,entries=$nfiles,dirwidth=$meandirwidth,prealloc=80, paralloc
 
-define fileset name=usr2files,path=$dir,size=$filesize,entries=$nfiles,dirwidth=$meandirwidth,prealloc=80, paralloc
+define fileset name=u2fileset,path=$dir,size=$filesize,entries=$nfiles,dirwidth=$meandirwidth,prealloc=80, paralloc
 
-define fileset name=usr3files,path=$dir,size=$filesize,entries=$nfiles,dirwidth=$meandirwidth,prealloc=80, paralloc
+define fileset name=u3fileset,path=$dir,size=$filesize,entries=$nfiles,dirwidth=$meandirwidth,prealloc=80, paralloc
 
 define flowop name=readwrite, $fileset
 {
@@ -59,19 +57,19 @@ define flowop name=dowork, $filesetnm, $rwiters
 
 define process name=filereader1,instances=1
 {
-  thread name=drewthread,memsize=10m,instances=$nthreads
+  thread name=user1,memsize=10m,instances=$nthreads
   {
-    flowop dowork name=dowork1, iters=1, $rwiters=5, $filesetnm=usr1files
+    flowop dowork name=dowork1, iters=1, $rwiters=5, $filesetnm=bigfileset
   }
 
-  thread name=ericthread,memsize=10m,instances=$nthreads
+  thread name=user2,memsize=10m,instances=$nthreads
   {
-    flowop dowork name=dowork2, iters=1, $rwiters=4, $filesetnm=usr2files
+    flowop dowork name=dowork2, iters=1, $rwiters=4, $filesetnm=u2fileset
   }
 
-  thread name=spencerthread,memsize=10m,instances=$nthreads
+  thread name=user3,memsize=10m,instances=$nthreads
   {
-    flowop dowork name=dowork3, iters=1, $rwiters=3, $filesetnm=usr3files
+    flowop dowork name=dowork3, iters=1, $rwiters=3, $filesetnm=u3fileset
   }
 }
 
diff --git a/usr/src/cmd/filebench/workloads/fileserver.f b/usr/src/cmd/filebench/workloads/fileserver.f
index f1ba7ec002..894cc379aa 100644
--- a/usr/src/cmd/filebench/workloads/fileserver.f
+++ b/usr/src/cmd/filebench/workloads/fileserver.f
@@ -22,13 +22,12 @@
 # Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 # Use is subject to license terms.
 #
-# ident	"%Z%%M%	%I%	%E% SMI"
 
 set $dir=/tmp
-set $nfiles=1000
+set $nfiles=10000
 set $meandirwidth=20
 set $filesize=128k
-set $nthreads=100
+set $nthreads=50
 set $meaniosize=16k
 set $fixediosize=1m
 
diff --git a/usr/src/cmd/filebench/workloads/randomfileaccess.f b/usr/src/cmd/filebench/workloads/randomfileaccess.f
new file mode 100644
index 0000000000..494b9f7741
--- /dev/null
+++ b/usr/src/cmd/filebench/workloads/randomfileaccess.f
@@ -0,0 +1,94 @@
+#
+# CDDL HEADER START
+#
+# The contents of this file are subject to the terms of the
+# Common Development and Distribution License (the "License").
+# You may not use this file except in compliance with the License.
+#
+# You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+# or http://www.opensolaris.org/os/licensing.
+# See the License for the specific language governing permissions
+# and limitations under the License.
+#
+# When distributing Covered Code, include this CDDL HEADER in each
+# file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+# If applicable, add the following below this CDDL HEADER, with the
+# fields enclosed by brackets "[]" replaced with your own identifying
+# information: Portions Copyright [yyyy] [name of copyright owner]
+#
+# CDDL HEADER END
+#
+# Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
+# Use is subject to license terms.
+#
+# 
+# 
+
+set $dir=/tmp
+set $cached=false
+set $meandirwidth=20
+set $nthreads=5
+set $nfiles=100000
+set $sync=false
+
+define randvar name=$wrtiosize, min=512, round=512, type=gamma, mean=16k
+
+define randvar name=$rdiosize, type=tabular, min=8k, round=1k, randtable =
+{{85,   8k,  8k},
+ {15,   8k, 64k}
+}
+
+define randvar name=$filesize, type=tabular, min=1k, randtable =
+{{33,   1k,    1k},
+ {21,   1k,    3k},
+ {13,   3k,    5k},
+ {10,   5k,   11k},
+ {08,  11k,   21k},
+ {05,  21k,   43k},
+ {04,  43k,   85k},
+ {03,  85k,  171k},
+ {02, 171k,  341k},
+ {01, 341k, 1707k}
+}
+
+define randvar name=$fileidx, type=gamma, min=0, gamma=100
+
+define fileset name=bigfileset,path=$dir,size=$filesize,entries=$nfiles,dirwidth=$meandirwidth,prealloc=60,cached=$cached
+
+define process name=netclient,instances=1
+{
+  thread name=fileuser,memsize=10m,instances=$nthreads
+  {
+    flowop openfile name=openfile1,filesetname=bigfileset,indexed=$fileidx,fd=1
+    flowop openfile name=openfile2,filesetname=bigfileset,indexed=$fileidx,fd=2
+    flowop openfile name=openfile3,filesetname=bigfileset,indexed=$fileidx,fd=3
+    flowop appendfilerand name=appendfilerand1,iosize=$wrtiosize,fd=1
+    flowop closefile name=closefile1,fd=1
+    flowop readwholefile name=readfile1,iosize=$rdiosize,fd=2
+    flowop readwholefile name=readfile2,iosize=$rdiosize,fd=3
+    flowop closefile name=closefile2,fd=2
+    flowop createfile name=newfile1,filesetname=bigfileset,indexed=$fileidx,fd=1
+    flowop writewholefile name=writefile1,iosize=$wrtiosize,srcfd=1,fd=1
+    flowop closefile name=closefile3,fd=3
+    flowop deletefile name=deletefile1,filesetname=bigfileset,fd=2
+    flowop statfile name=statfile1,filesetname=bigfileset,fd=1
+    flowop closefile name=closefile4,fd=1
+  }
+}
+
+echo  "NetworkServer Version 1.0 personality successfully loaded"
+usage "Usage: set \$dir=<dir>            defaults to $dir"
+usage "       set \$cached=<bool>        defaults to $cached"
+usage "       set \$wrtiosize.type=<type>   defaults to $wrtiosize.type"
+usage "       set \$wrtiosize.randsrc=<src> defaults to $wrtiosize.randsrc"
+usage "       set \$wrtiosize.mean=<mean>   defaults to $wrtiosize.mean"
+usage "       set \$wrtiosize.gamma=<gamma> defaults to $wrtiosize.gamma"
+usage "       set \$rdiosize.type=<type>   defaults to $rdiosize.type"
+usage "       set \$rdiosize.randsrc=<src> defaults to $rdiosize.randsrc"
+usage "       set \$filesize.type=<type>   defaults to $filesize.type"
+usage "       set \$filesize.randsrc=<src> defaults to $filesize.randsrc"
+usage "       set \$nfiles=<value>       defaults to $nfiles"
+usage "       set \$nthreads=<value>     defaults to $nthreads"
+usage "       set \$sync=<bool>          defaults to $sync"
+usage " "
+usage "       run runtime (e.g. run 60)"
diff --git a/usr/src/cmd/filebench/workloads/removedirs.f b/usr/src/cmd/filebench/workloads/removedirs.f
index f64255bc8c..debf062817 100644
--- a/usr/src/cmd/filebench/workloads/removedirs.f
+++ b/usr/src/cmd/filebench/workloads/removedirs.f
@@ -35,7 +35,7 @@ define fileset name=bigfileset,path=$dir,size=0,leafdirs=$ndirs,dirwidth=$meandi
 
 define process name=remdir,instances=1
 {
-  thread name=fileopener,memsize=1m,instances=$nthreads
+  thread name=removedirectory,memsize=1m,instances=$nthreads
   {
     flowop removedir name=dirremover,filesetname=bigfileset
   }
diff --git a/usr/src/cmd/filebench/workloads/videoserver.f b/usr/src/cmd/filebench/workloads/videoserver.f
index 668fd0e81c..9cfea0df92 100644
--- a/usr/src/cmd/filebench/workloads/videoserver.f
+++ b/usr/src/cmd/filebench/workloads/videoserver.f
@@ -35,24 +35,29 @@
 set $dir=/tmp
 set $filesize=10g
 set $nthreads=48
-set $writeiosize=1m
-set $readiosize=256k
 set $numactivevids=32
 set $numpassivevids=194
-set $srvbwrate=96
+set $reuseit=false
+set $readiosize=256k
+set $writeiosize=1m
+#
+set $passvidsname=passivevids
+set $actvidsname=activevids
+#
 set $repintval=10
+set $srvbwrate=96
 
 eventgen rate=$srvbwrate
 
-define fileset name=activevids,path=$dir,size=$filesize,entries=$numactivevids,dirwidth=4,prealloc,paralloc,reuse
-define fileset name=passivevids,path=$dir,size=$filesize,entries=$numpassivevids,dirwidth=20,prealloc,paralloc,reuse,prealloc=50
+define fileset name=$actvidsname,path=$dir,size=$filesize,entries=$numactivevids,dirwidth=4,prealloc,paralloc,reuse=$reuseit
+define fileset name=$passvidsname,path=$dir,size=$filesize,entries=$numpassivevids,dirwidth=20,prealloc=50,paralloc,reuse=$reuseit
 
 define process name=vidwriter,instances=1
 {
   thread name=vidwriter,memsize=10m,instances=1
   {
-    flowop deletefile name=vidremover,filesetname=passivevids
-    flowop createfile name=wrtopen,filesetname=passivevids,fd=1
+    flowop deletefile name=vidremover,filesetname=$passvidsname
+    flowop createfile name=wrtopen,filesetname=$passvidsname,fd=1
     flowop writewholefile name=newvid,iosize=$writeiosize,fd=1,srcfd=1
     flowop closefile name=wrtclose, fd=1
     flowop delay name=replaceinterval, value=$repintval
@@ -63,7 +68,7 @@ define process name=vidreaders,instances=1
 {
   thread name=vidreaders,memsize=10m,instances=$nthreads
   {
-    flowop read name=vidreader,filesetname=activevids,iosize=$readiosize
+    flowop read name=vidreader,filesetname=$actvidsname,iosize=$readiosize
     flowop bwlimit name=serverlimit, target=vidreader
   }
 }
diff --git a/usr/src/cmd/filebench/workloads/webproxy.f b/usr/src/cmd/filebench/workloads/webproxy.f
index 43010e360c..2946d648fa 100644
--- a/usr/src/cmd/filebench/workloads/webproxy.f
+++ b/usr/src/cmd/filebench/workloads/webproxy.f
@@ -19,13 +19,11 @@
 # CDDL HEADER END
 #
 #
-# Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
+# Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 # Use is subject to license terms.
-#
-# ident	"%Z%%M%	%I%	%E% SMI"
 
 set $dir=/tmp
-set $nfiles=1000
+set $nfiles=10000
 set $meandirwidth=1000000
 set $filesize=16k
 set $nthreads=100