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

1 files changed, 420 insertions, 257 deletions

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);
 }
 
 /*