1 files changed, 934 insertions, 264 deletions

diff --git a/src/bftw.c b/src/bftw.c
index e6b8cd5..f822456 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -9,6 +9,8 @@
  *
  * - struct bftw_list: A linked list of bftw_file's.
  *
+ * - struct bftw_queue: A multi-stage queue of bftw_file's.
+ *
  * - struct bftw_cache: An LRU list of bftw_file's with open file descriptors,
  *   used for openat() to minimize the amount of path re-traversals.
  *
@@ -17,9 +19,10 @@
  */
 
 #include "bftw.h"
+
 #include "alloc.h"
+#include "bfs.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include "dir.h"
 #include "dstring.h"
@@ -28,57 +31,138 @@
 #include "mtab.h"
 #include "stat.h"
 #include "trie.h"
+
 #include <errno.h>
 #include <fcntl.h>
 #include <stdlib.h>
 #include <string.h>
 #include <sys/stat.h>
+#include <sys/types.h>
+
+/** Initialize a bftw_stat cache. */
+static void bftw_stat_init(struct bftw_stat *bufs, struct bfs_stat *stat_buf, struct bfs_stat *lstat_buf) {
+	bufs->stat_buf = stat_buf;
+	bufs->lstat_buf = lstat_buf;
+	bufs->stat_err = -1;
+	bufs->lstat_err = -1;
+}
 
-/** Caching bfs_stat(). */
-static const struct bfs_stat *bftw_stat_impl(struct BFTW *ftwbuf, struct bftw_stat *cache, enum bfs_stat_flags flags) {
-	if (!cache->buf) {
-		if (cache->error) {
-			errno = cache->error;
-		} else if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, flags, &cache->storage) == 0) {
-			cache->buf = &cache->storage;
+/** Fill a bftw_stat cache from another one. */
+static void bftw_stat_fill(struct bftw_stat *dest, const struct bftw_stat *src) {
+	if (dest->stat_err < 0 && src->stat_err >= 0) {
+		dest->stat_buf = src->stat_buf;
+		dest->stat_err = src->stat_err;
+	}
+
+	if (dest->lstat_err < 0 && src->lstat_err >= 0) {
+		dest->lstat_buf = src->lstat_buf;
+		dest->lstat_err = src->lstat_err;
+	}
+}
+
+/** Cache a bfs_stat() result. */
+static void bftw_stat_cache(struct bftw_stat *bufs, enum bfs_stat_flags flags, const struct bfs_stat *buf, int err) {
+	if (flags & BFS_STAT_NOFOLLOW) {
+		bufs->lstat_buf = buf;
+		bufs->lstat_err = err;
+		if (err || !S_ISLNK(buf->mode)) {
+			// Non-link, so share stat info
+			bufs->stat_buf = buf;
+			bufs->stat_err = err;
+		}
+	} else if (flags & BFS_STAT_TRYFOLLOW) {
+		if (err) {
+			bufs->stat_err = err;
+		} else if (S_ISLNK(buf->mode)) {
+			bufs->lstat_buf = buf;
+			bufs->lstat_err = err;
+			bufs->stat_err = ENOENT;
 		} else {
-			cache->error = errno;
+			bufs->stat_buf = buf;
+			bufs->stat_err = err;
 		}
+	} else {
+		bufs->stat_buf = buf;
+		bufs->stat_err = err;
+	}
+}
+
+/** Caching bfs_stat(). */
+static const struct bfs_stat *bftw_stat_impl(struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
+	struct bftw_stat *bufs = &ftwbuf->stat_bufs;
+	struct bfs_stat *buf;
+
+	if (flags & BFS_STAT_NOFOLLOW) {
+		buf = (struct bfs_stat *)bufs->lstat_buf;
+		if (bufs->lstat_err == 0) {
+			return buf;
+		} else if (bufs->lstat_err > 0) {
+			errno = bufs->lstat_err;
+			return NULL;
+		}
+	} else {
+		buf = (struct bfs_stat *)bufs->stat_buf;
+		if (bufs->stat_err == 0) {
+			return buf;
+		} else if (bufs->stat_err > 0) {
+			errno = bufs->stat_err;
+			return NULL;
+		}
+	}
+
+	struct bfs_stat *ret;
+	int err;
+	if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, flags, buf) == 0) {
+		ret = buf;
+		err = 0;
+#ifdef S_IFWHT
+	} else if (errno == ENOENT && ftwbuf->type == BFS_WHT) {
+		// This matches the behavior of FTS_WHITEOUT on BSD
+		ret = memset(buf, 0, sizeof(*buf));
+		ret->mode = S_IFWHT;
+		err = 0;
+#endif
+	} else {
+		ret = NULL;
+		err = errno;
 	}
 
-	return cache->buf;
+	bftw_stat_cache(bufs, flags, ret, err);
+	return ret;
 }
 
 const struct bfs_stat *bftw_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
 	struct BFTW *mutbuf = (struct BFTW *)ftwbuf;
 	const struct bfs_stat *ret;
 
-	if (flags & BFS_STAT_NOFOLLOW) {
-		ret = bftw_stat_impl(mutbuf, &mutbuf->lstat_cache, BFS_STAT_NOFOLLOW);
-		if (ret && !S_ISLNK(ret->mode) && !mutbuf->stat_cache.buf) {
-			// Non-link, so share stat info
-			mutbuf->stat_cache.buf = ret;
+	if (flags & BFS_STAT_TRYFOLLOW) {
+		ret = bftw_stat_impl(mutbuf, BFS_STAT_FOLLOW);
+		if (!ret && errno_is_like(ENOENT)) {
+			ret = bftw_stat_impl(mutbuf, BFS_STAT_NOFOLLOW);
 		}
 	} else {
-		ret = bftw_stat_impl(mutbuf, &mutbuf->stat_cache, BFS_STAT_FOLLOW);
-		if (!ret && (flags & BFS_STAT_TRYFOLLOW) && is_nonexistence_error(errno)) {
-			ret = bftw_stat_impl(mutbuf, &mutbuf->lstat_cache, BFS_STAT_NOFOLLOW);
-		}
+		ret = bftw_stat_impl(mutbuf, flags);
 	}
 
 	return ret;
 }
 
 const struct bfs_stat *bftw_cached_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
+	const struct bftw_stat *bufs = &ftwbuf->stat_bufs;
+
 	if (flags & BFS_STAT_NOFOLLOW) {
-		return ftwbuf->lstat_cache.buf;
-	} else if (ftwbuf->stat_cache.buf) {
-		return ftwbuf->stat_cache.buf;
-	} else if ((flags & BFS_STAT_TRYFOLLOW) && is_nonexistence_error(ftwbuf->stat_cache.error)) {
-		return ftwbuf->lstat_cache.buf;
-	} else {
-		return NULL;
+		if (bufs->lstat_err == 0) {
+			return bufs->lstat_buf;
+		}
+	} else if (bufs->stat_err == 0) {
+		return bufs->stat_buf;
+	} else if ((flags & BFS_STAT_TRYFOLLOW) && error_is_like(bufs->stat_err, ENOENT)) {
+		if (bufs->lstat_err == 0) {
+			return bufs->lstat_buf;
+		}
 	}
+
+	return NULL;
 }
 
 enum bfs_type bftw_type(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
@@ -115,12 +199,26 @@ struct bftw_file {
 	/** The root under which this file was found. */
 	struct bftw_file *root;
 
-	/** The next file to open/close/visit. */
+	/**
+	 * List node for:
+	 *
+	 *     bftw_queue::buffer
+	 *     bftw_queue::waiting
+	 *     bftw_file_open()::parents
+	 */
 	struct bftw_file *next;
-	/** The next directory to read. */
-	struct { struct bftw_file *next; } to_read;
 
-	/** LRU list node. */
+	/**
+	 * List node for:
+	 *
+	 *     bftw_queue::ready
+	 *     bftw_state::to_close
+	 */
+	struct { struct bftw_file *next; } ready;
+
+	/**
+	 * List node for bftw_cache.
+	 */
 	struct {
 		struct bftw_file *prev;
 		struct bftw_file *next;
@@ -147,6 +245,9 @@ struct bftw_file {
 	/** The inode number, for cycle detection. */
 	ino_t ino;
 
+	/** Cached bfs_stat() info. */
+	struct bftw_stat stat_bufs;
+
 	/** The offset of this file in the full path. */
 	size_t nameoff;
 	/** The length of the file's name. */
@@ -164,6 +265,283 @@ struct bftw_list {
 };
 
 /**
+ * bftw_queue flags.
+ */
+enum bftw_qflags {
+	/** Track the sync/async service balance. */
+	BFTW_QBALANCE = 1 << 0,
+	/** Buffer files before adding them to the queue. */
+	BFTW_QBUFFER  = 1 << 1,
+	/** Use LIFO (stack/DFS) ordering. */
+	BFTW_QLIFO    = 1 << 2,
+	/** Maintain a strict order. */
+	BFTW_QORDER   = 1 << 3,
+};
+
+/**
+ * A queue of bftw_file's that may be serviced asynchronously.
+ *
+ * A bftw_queue comprises three linked lists each tracking different stages.
+ * When BFTW_QBUFFER is set, files are initially pushed to the buffer:
+ *
+ *              ╔═══╗                 ╔═══╦═══╗
+ *     buffer:  ║ 𝘩 ║                 ║ 𝘩 ║ 𝘪 ║
+ *              ╠═══╬═══╦═══╗         ╠═══╬═══╬═══╗
+ *     waiting: ║ e ║ f ║ g ║      →  ║ e ║ f ║ g ║
+ *              ╠═══╬═══╬═══╬═══╗     ╠═══╬═══╬═══╬═══╗
+ *     ready:   ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║     ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║
+ *              ╚═══╩═══╩═══╩═══╝     ╚═══╩═══╩═══╩═══╝
+ *
+ * When bftw_queue_flush() is called, the files in the buffer are appended to
+ * the waiting list (or prepended, if BFTW_QLIFO is set):
+ *
+ *              ╔═╗
+ *     buffer:  ║ ║
+ *              ╠═╩═╦═══╦═══╦═══╦═══╗
+ *     waiting: ║ e ║ f ║ g ║ h ║ i ║
+ *              ╠═══╬═══╬═══╬═══╬═══╝
+ *     ready:   ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║
+ *              ╚═══╩═══╩═══╩═══╝
+ *
+ * Using the buffer gives a more natural ordering for BFTW_QLIFO, and allows
+ * files to be sorted before adding them to the waiting list.  If BFTW_QBUFFER
+ * is not set, files are pushed directly to the waiting list instead.
+ *
+ * Files on the waiting list are waiting to be "serviced" asynchronously by the
+ * ioq (for example, by an ioq_opendir() or ioq_stat() call).  While they are
+ * being serviced, they are detached from the queue by bftw_queue_detach() and
+ * are not tracked by the queue at all:
+ *
+ *              ╔═╗
+ *     buffer:  ║ ║
+ *              ╠═╩═╦═══╦═══╗       ⎛      ┌───┬───┐ ⎞
+ *     waiting: ║ g ║ h ║ i ║       ⎜ ioq: │ 𝓮 │ 𝓯 │ ⎟
+ *              ╠═══╬═══╬═══╬═══╗   ⎝      └───┴───┘ ⎠
+ *     ready:   ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║
+ *              ╚═══╩═══╩═══╩═══╝
+ *
+ * When their async service is complete, files are reattached to the queue by
+ * bftw_queue_attach(), this time on the ready list:
+ *
+ *              ╔═╗
+ *     buffer:  ║ ║
+ *              ╠═╩═╦═══╦═══╗           ⎛      ┌───┐ ⎞
+ *     waiting: ║ g ║ h ║ i ║           ⎜ ioq: │ 𝓮 │ ⎟
+ *              ╠═══╬═══╬═══╬═══╦═══╗   ⎝      └───┘ ⎠
+ *     ready:   ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║ 𝕗 ║
+ *              ╚═══╩═══╩═══╩═══╩═══╝
+ *
+ * Files are added to the ready list in the order they are finished by the ioq.
+ * bftw_queue_pop() pops a file from the ready list if possible.  Otherwise, it
+ * pops from the waiting list, and the file must be serviced synchronously.
+ *
+ * However, if BFTW_QORDER is set, files must be popped in the exact order they
+ * are added to the waiting list (to maintain sorted order).  In this case,
+ * files are added to the waiting and ready lists at the same time.  The
+ * file->ioqueued flag is set while it is in-service, so that bftw() can wait
+ * for it to be truly ready before using it.
+ *
+ *              ╔═╗
+ *     buffer:  ║ ║
+ *              ╠═╩═╦═══╦═══╗                           ⎛      ┌───┐ ⎞
+ *     waiting: ║ g ║ h ║ i ║                           ⎜ ioq: │ 𝓮 │ ⎟
+ *              ╠═══╬═══╬═══╬═══╦═══╦═══╦═══╦═══╦═══╗   ⎝      └───┘ ⎠
+ *     ready:   ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║ 𝓮 ║ 𝕗 ║ g ║ h ║ i ║
+ *              ╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝
+ *
+ * If BFTW_QBALANCE is set, queue->imbalance tracks the delta between async
+ * service (negative) and synchronous service (positive).  The queue is
+ * considered "balanced" when this number is non-negative.  Only a balanced
+ * queue will perform any async service, ensuring work is fairly distributed
+ * between the main thread and the ioq.
+ *
+ * BFTW_QBALANCE is only set for single-threaded ioqs.  When an ioq has multiple
+ * threads, it is faster to wait for the ioq to complete an operation than it is
+ * to perform it on the main thread.
+ */
+struct bftw_queue {
+	/** Queue flags. */
+	enum bftw_qflags flags;
+	/** A buffer of files to be enqueued together. */
+	struct bftw_list buffer;
+	/** A list of files which are waiting to be serviced. */
+	struct bftw_list waiting;
+	/** A list of already-serviced files. */
+	struct bftw_list ready;
+	/** The current size of the queue. */
+	size_t size;
+	/** The number of files currently in-service. */
+	size_t ioqueued;
+	/** Tracks the imbalance between synchronous and async service. */
+	unsigned long imbalance;
+};
+
+/** Initialize a queue. */
+static void bftw_queue_init(struct bftw_queue *queue, enum bftw_qflags flags) {
+	queue->flags = flags;
+	SLIST_INIT(&queue->buffer);
+	SLIST_INIT(&queue->waiting);
+	SLIST_INIT(&queue->ready);
+	queue->size = 0;
+	queue->ioqueued = 0;
+	queue->imbalance = 0;
+}
+
+/** Add a file to the queue. */
+static void bftw_queue_push(struct bftw_queue *queue, struct bftw_file *file) {
+	if (queue->flags & BFTW_QBUFFER) {
+		SLIST_APPEND(&queue->buffer, file);
+	} else if (queue->flags & BFTW_QLIFO) {
+		SLIST_PREPEND(&queue->waiting, file);
+		if (queue->flags & BFTW_QORDER) {
+			SLIST_PREPEND(&queue->ready, file, ready);
+		}
+	} else {
+		SLIST_APPEND(&queue->waiting, file);
+		if (queue->flags & BFTW_QORDER) {
+			SLIST_APPEND(&queue->ready, file, ready);
+		}
+	}
+
+	++queue->size;
+}
+
+/** Add any buffered files to the queue. */
+static void bftw_queue_flush(struct bftw_queue *queue) {
+	if (!(queue->flags & BFTW_QBUFFER)) {
+		return;
+	}
+
+	if (queue->flags & BFTW_QORDER) {
+		// When sorting, add files to the ready list at the same time
+		// (and in the same order) as they are added to the waiting list
+		struct bftw_file **cursor = (queue->flags & BFTW_QLIFO)
+			? &queue->ready.head
+			: queue->ready.tail;
+		for_slist (struct bftw_file, file, &queue->buffer) {
+			cursor = SLIST_INSERT(&queue->ready, cursor, file, ready);
+		}
+	}
+
+	if (queue->flags & BFTW_QLIFO) {
+		SLIST_EXTEND(&queue->buffer, &queue->waiting);
+	}
+
+	SLIST_EXTEND(&queue->waiting, &queue->buffer);
+}
+
+/** Check if the queue is properly balanced for async work. */
+static bool bftw_queue_balanced(const struct bftw_queue *queue) {
+	if (queue->flags & BFTW_QBALANCE) {
+		return (long)queue->imbalance >= 0;
+	} else {
+		return true;
+	}
+}
+
+/** Update the queue balance for (a)sync service. */
+static void bftw_queue_rebalance(struct bftw_queue *queue, bool async) {
+	if (async) {
+		--queue->imbalance;
+	} else {
+		++queue->imbalance;
+	}
+}
+
+/** Detach the next waiting file. */
+static void bftw_queue_detach(struct bftw_queue *queue, struct bftw_file *file, bool async) {
+	bfs_assert(!file->ioqueued);
+
+	if (file == SLIST_HEAD(&queue->buffer)) {
+		// To maintain order, we can't detach any files until they're
+		// added to the waiting/ready lists
+		bfs_assert(!(queue->flags & BFTW_QORDER));
+		SLIST_POP(&queue->buffer);
+	} else if (file == SLIST_HEAD(&queue->waiting)) {
+		SLIST_POP(&queue->waiting);
+	} else {
+		bfs_bug("Detached file was not buffered or waiting");
+	}
+
+	if (async) {
+		file->ioqueued = true;
+		++queue->ioqueued;
+		bftw_queue_rebalance(queue, true);
+	}
+}
+
+/** Reattach a serviced file to the queue. */
+static void bftw_queue_attach(struct bftw_queue *queue, struct bftw_file *file, bool async) {
+	if (async) {
+		bfs_assert(file->ioqueued);
+		file->ioqueued = false;
+		--queue->ioqueued;
+	} else {
+		bfs_assert(!file->ioqueued);
+	}
+
+	if (!(queue->flags & BFTW_QORDER)) {
+		SLIST_APPEND(&queue->ready, file, ready);
+	}
+}
+
+/** Make a file ready immediately. */
+static void bftw_queue_skip(struct bftw_queue *queue, struct bftw_file *file) {
+	bftw_queue_detach(queue, file, false);
+	bftw_queue_attach(queue, file, false);
+}
+
+/** Get the next waiting file. */
+static struct bftw_file *bftw_queue_waiting(const struct bftw_queue *queue) {
+	if (!(queue->flags & BFTW_QBUFFER)) {
+		return SLIST_HEAD(&queue->waiting);
+	}
+
+	if (queue->flags & BFTW_QORDER) {
+		// Don't detach files until they're on the waiting/ready lists
+		return SLIST_HEAD(&queue->waiting);
+	}
+
+	const struct bftw_list *prefix = &queue->waiting;
+	const struct bftw_list *suffix = &queue->buffer;
+	if (queue->flags & BFTW_QLIFO) {
+		prefix = &queue->buffer;
+		suffix = &queue->waiting;
+	}
+
+	struct bftw_file *file = SLIST_HEAD(prefix);
+	if (!file) {
+		file = SLIST_HEAD(suffix);
+	}
+	return file;
+}
+
+/** Get the next ready file. */
+static struct bftw_file *bftw_queue_ready(const struct bftw_queue *queue) {
+	return SLIST_HEAD(&queue->ready);
+}
+
+/** Pop a file from the queue. */
+static struct bftw_file *bftw_queue_pop(struct bftw_queue *queue) {
+	// Don't pop until we've had a chance to sort the buffer
+	bfs_assert(SLIST_EMPTY(&queue->buffer));
+
+	struct bftw_file *file = SLIST_POP(&queue->ready, ready);
+
+	if (!file || file == SLIST_HEAD(&queue->waiting)) {
+		// If no files are ready, try the waiting list.  Or, if
+		// BFTW_QORDER is set, we may need to pop from both lists.
+		file = SLIST_POP(&queue->waiting);
+	}
+
+	if (file) {
+		--queue->size;
+	}
+
+	return file;
+}
+
+/**
  * A cache of open directories.
  */
 struct bftw_cache {
@@ -178,10 +556,14 @@ struct bftw_cache {
 
 	/** bftw_file arena. */
 	struct varena files;
+
 	/** bfs_dir arena. */
 	struct arena dirs;
 	/** Remaining bfs_dir capacity. */
-	size_t dirlimit;
+	int dir_limit;
+
+	/** bfs_stat arena. */
+	struct arena stat_bufs;
 };
 
 /** Initialize a cache. */
@@ -191,28 +573,35 @@ static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
 	cache->capacity = capacity;
 
 	VARENA_INIT(&cache->files, struct bftw_file, name);
+
 	bfs_dir_arena(&cache->dirs);
 
-	cache->dirlimit = capacity - 1;
-	if (cache->dirlimit > 1024) {
-		cache->dirlimit = 1024;
+	if (cache->capacity > 1024) {
+		cache->dir_limit = 1024;
+	} else {
+		cache->dir_limit = capacity - 1;
 	}
+
+	ARENA_INIT(&cache->stat_bufs, struct bfs_stat);
 }
 
 /** Allocate a directory. */
-static struct bfs_dir *bftw_allocdir(struct bftw_cache *cache) {
-	if (cache->dirlimit == 0) {
+static struct bfs_dir *bftw_allocdir(struct bftw_cache *cache, bool force) {
+	if (!force && cache->dir_limit <= 0) {
 		errno = ENOMEM;
 		return NULL;
 	}
-	--cache->dirlimit;
 
-	return arena_alloc(&cache->dirs);
+	struct bfs_dir *dir = arena_alloc(&cache->dirs);
+	if (dir) {
+		--cache->dir_limit;
+	}
+	return dir;
 }
 
 /** Free a directory. */
 static void bftw_freedir(struct bftw_cache *cache, struct bfs_dir *dir) {
-	++cache->dirlimit;
+	++cache->dir_limit;
 	arena_free(&cache->dirs, dir);
 }
 
@@ -318,12 +707,12 @@ static size_t bftw_child_nameoff(const struct bftw_file *parent) {
 
 /** Destroy a cache. */
 static void bftw_cache_destroy(struct bftw_cache *cache) {
-	bfs_assert(!cache->head);
-	bfs_assert(!cache->tail);
+	bfs_assert(LIST_EMPTY(cache));
 	bfs_assert(!cache->target);
 
-	varena_destroy(&cache->files);
+	arena_destroy(&cache->stat_bufs);
 	arena_destroy(&cache->dirs);
+	varena_destroy(&cache->files);
 }
 
 /** Create a new bftw_file. */
@@ -347,9 +736,9 @@ static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_fil
 		file->nameoff = 0;
 	}
 
-	file->next = NULL;
-	file->to_read.next = NULL;
-	file->lru.prev = file->lru.next = NULL;
+	SLIST_ITEM_INIT(file);
+	SLIST_ITEM_INIT(file, ready);
+	LIST_ITEM_INIT(file, lru);
 
 	file->refcount = 1;
 	file->pincount = 0;
@@ -361,6 +750,8 @@ static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_fil
 	file->dev = -1;
 	file->ino = -1;
 
+	bftw_stat_init(&file->stat_bufs, NULL, NULL);
+
 	file->namelen = namelen;
 	memcpy(file->name, name, namelen + 1);
 
@@ -378,8 +769,21 @@ static void bftw_file_set_dir(struct bftw_cache *cache, struct bftw_file *file,
 		file->fd = bfs_dirfd(dir);
 		bftw_cache_add(cache, file);
 	}
+}
 
-	bftw_cache_pin(cache, file);
+/** Free a file's cached stat() buffers. */
+static void bftw_stat_recycle(struct bftw_cache *cache, struct bftw_file *file) {
+	struct bftw_stat *bufs = &file->stat_bufs;
+
+	struct bfs_stat *stat_buf = (struct bfs_stat *)bufs->stat_buf;
+	struct bfs_stat *lstat_buf = (struct bfs_stat *)bufs->lstat_buf;
+	if (stat_buf) {
+		arena_free(&cache->stat_bufs, stat_buf);
+	} else if (lstat_buf) {
+		arena_free(&cache->stat_bufs, lstat_buf);
+	}
+
+	bftw_stat_init(bufs, NULL, NULL);
 }
 
 /** Free a bftw_file. */
@@ -390,6 +794,8 @@ static void bftw_file_free(struct bftw_cache *cache, struct bftw_file *file) {
 		bftw_file_close(cache, file);
 	}
 
+	bftw_stat_recycle(cache, file);
+
 	varena_free(&cache->files, file, file->namelen + 1);
 }
 
@@ -411,6 +817,8 @@ struct bftw_state {
 	enum bftw_strategy strategy;
 	/** The mount table. */
 	const struct bfs_mtab *mtab;
+	/** bfs_opendir() flags. */
+	enum bfs_dir_flags dir_flags;
 
 	/** The appropriate errno value, if any. */
 	int error;
@@ -423,20 +831,15 @@ struct bftw_state {
 	/** The number of I/O threads. */
 	size_t nthreads;
 
-	/** The queue of directories to open. */
-	struct bftw_list to_open;
-	/** The queue of directories to read. */
-	struct bftw_list to_read;
 	/** The queue of unpinned directories to unwrap. */
 	struct bftw_list to_close;
-
 	/** The queue of files to visit. */
-	struct bftw_list to_visit;
-	/** A batch of files to enqueue. */
-	struct bftw_list batch;
+	struct bftw_queue fileq;
+	/** The queue of directories to open/read. */
+	struct bftw_queue dirq;
 
 	/** The current path. */
-	char *path;
+	dchar *path;
 	/** The current file. */
 	struct bftw_file *file;
 	/** The previous file. */
@@ -453,8 +856,44 @@ struct bftw_state {
 
 	/** Extra data about the current file. */
 	struct BFTW ftwbuf;
+	/** stat() buffer storage. */
+	struct bfs_stat stat_buf;
+	/** lstat() buffer storage. */
+	struct bfs_stat lstat_buf;
 };
 
+/** Check if we have to buffer files before visiting them. */
+static bool bftw_must_buffer(const struct bftw_state *state) {
+	if (state->flags & BFTW_SORT) {
+		// Have to buffer the files to sort them
+		return true;
+	}
+
+	if (state->strategy == BFTW_DFS && state->nthreads == 0) {
+		// Without buffering, we would get a not-quite-depth-first
+		// ordering:
+		//
+		//     a
+		//     b
+		//     a/c
+		//     a/c/d
+		//     b/e
+		//     b/e/f
+		//
+		// This is okay for iterative deepening, since the caller only
+		// sees files at the target depth.  We also deem it okay for
+		// parallel searches, since the order is unpredictable anyway.
+		return true;
+	}
+
+	if ((state->flags & BFTW_STAT) && state->nthreads > 1) {
+		// We will be buffering every file anyway for ioq_stat()
+		return true;
+	}
+
+	return false;
+}
+
 /** Initialize the bftw() state. */
 static int bftw_state_init(struct bftw_state *state, const struct bftw_args *args) {
 	state->paths = args->paths;
@@ -464,35 +903,68 @@ static int bftw_state_init(struct bftw_state *state, const struct bftw_args *arg
 	state->flags = args->flags;
 	state->strategy = args->strategy;
 	state->mtab = args->mtab;
-
-	if ((state->flags & BFTW_SORT) || state->strategy == BFTW_DFS) {
-		state->flags |= BFTW_BUFFER;
-	}
-
+	state->dir_flags = 0;
 	state->error = 0;
 
-	if (args->nopenfd < 1) {
+	if (args->nopenfd < 2) {
 		errno = EMFILE;
 		return -1;
 	}
-	bftw_cache_init(&state->cache, args->nopenfd);
 
-	state->nthreads = args->nthreads;
-	if (state->nthreads > 0) {
-		state->ioq = ioq_create(4096, state->nthreads);
+	size_t nopenfd = args->nopenfd;
+	size_t qdepth = 4096;
+	size_t nthreads = args->nthreads;
+
+#if BFS_WITH_LIBURING
+	// io_uring uses one fd per ring, ioq uses one ring per thread
+	if (nthreads >= nopenfd - 1) {
+		nthreads = nopenfd - 2;
+	}
+	nopenfd -= nthreads;
+#endif
+
+	bftw_cache_init(&state->cache, nopenfd);
+
+	if (nthreads > 0) {
+		state->ioq = ioq_create(qdepth, nthreads);
 		if (!state->ioq) {
 			return -1;
 		}
 	} else {
 		state->ioq = NULL;
 	}
+	state->nthreads = nthreads;
+
+	if (bftw_must_buffer(state)) {
+		state->flags |= BFTW_BUFFER;
+	}
+
+	if (state->flags & BFTW_WHITEOUTS) {
+		state->dir_flags |= BFS_DIR_WHITEOUTS;
+	}
 
-	SLIST_INIT(&state->to_open);
-	SLIST_INIT(&state->to_read);
 	SLIST_INIT(&state->to_close);
 
-	SLIST_INIT(&state->to_visit);
-	SLIST_INIT(&state->batch);
+	enum bftw_qflags qflags = 0;
+	if (state->strategy != BFTW_BFS) {
+		qflags |= BFTW_QBUFFER | BFTW_QLIFO;
+	}
+	if (state->flags & BFTW_BUFFER) {
+		qflags |= BFTW_QBUFFER;
+	}
+	if (state->flags & BFTW_SORT) {
+		qflags |= BFTW_QORDER;
+	} else if (nthreads == 1) {
+		qflags |= BFTW_QBALANCE;
+	}
+	bftw_queue_init(&state->fileq, qflags);
+
+	if (state->strategy == BFTW_BFS || (state->flags & BFTW_BUFFER)) {
+		// In breadth-first mode, or if we're already buffering files,
+		// directories can be queued in FIFO order
+		qflags &= ~(BFTW_QBUFFER | BFTW_QLIFO);
+	}
+	bftw_queue_init(&state->dirq, qflags);
 
 	state->path = NULL;
 	state->file = NULL;
@@ -505,22 +977,47 @@ static int bftw_state_init(struct bftw_state *state, const struct bftw_args *arg
 	return 0;
 }
 
+/** Queue a directory for unwrapping. */
+static void bftw_delayed_unwrap(struct bftw_state *state, struct bftw_file *file) {
+	bfs_assert(file->dir);
+
+	if (!SLIST_ATTACHED(&state->to_close, file, ready)) {
+		SLIST_APPEND(&state->to_close, file, ready);
+	}
+}
+
+/** Unpin a file's parent. */
+static void bftw_unpin_parent(struct bftw_state *state, struct bftw_file *file, bool unwrap) {
+	struct bftw_file *parent = file->parent;
+	if (!parent) {
+		return;
+	}
+
+	bftw_cache_unpin(&state->cache, parent);
+
+	if (unwrap && parent->dir && parent->pincount == 0) {
+		bftw_delayed_unwrap(state, parent);
+	}
+}
+
 /** Pop a response from the I/O queue. */
 static int bftw_ioq_pop(struct bftw_state *state, bool block) {
+	struct bftw_cache *cache = &state->cache;
 	struct ioq *ioq = state->ioq;
 	if (!ioq) {
 		return -1;
 	}
 
-	struct ioq_ent *ent = block ? ioq_pop(ioq) : ioq_trypop(ioq);
+	ioq_submit(ioq);
+	struct ioq_ent *ent = ioq_pop(ioq, block);
 	if (!ent) {
 		return -1;
 	}
 
-	struct bftw_cache *cache = &state->cache;
-	struct bftw_file *file;
-	struct bftw_file *parent;
-	struct bfs_dir *dir;
+	struct bftw_file *file = ent->ptr;
+	if (file) {
+		bftw_unpin_parent(state, file, true);
+	}
 
 	enum ioq_op op = ent->op;
 	switch (op) {
@@ -530,33 +1027,34 @@ static int bftw_ioq_pop(struct bftw_state *state, bool block) {
 
 	case IOQ_CLOSEDIR:
 		++cache->capacity;
-		dir = ent->closedir.dir;
-		bftw_freedir(cache, dir);
+		bftw_freedir(cache, ent->closedir.dir);
 		break;
 
 	case IOQ_OPENDIR:
-		file = ent->ptr;
-		file->ioqueued = false;
-
 		++cache->capacity;
-		parent = file->parent;
-		if (parent) {
-			bftw_cache_unpin(cache, parent);
-			if (parent->pincount == 0 && parent->dir) {
-				SLIST_APPEND(&state->to_close, parent);
-			}
-		}
 
-		dir = ent->opendir.dir;
-		if (ent->ret == 0) {
-			bftw_file_set_dir(cache, file, dir);
+		if (ent->result >= 0) {
+			bftw_file_set_dir(cache, file, ent->opendir.dir);
 		} else {
-			bftw_freedir(cache, dir);
+			bftw_freedir(cache, ent->opendir.dir);
 		}
 
-		if (!(state->flags & BFTW_SORT)) {
-			SLIST_APPEND(&state->to_read, file, to_read);
+		bftw_queue_attach(&state->dirq, file, true);
+		break;
+
+	case IOQ_STAT:
+		if (ent->result >= 0) {
+			bftw_stat_cache(&file->stat_bufs, ent->stat.flags, ent->stat.buf, 0);
+		} else {
+			arena_free(&cache->stat_bufs, ent->stat.buf);
+			bftw_stat_cache(&file->stat_bufs, ent->stat.flags, NULL, -ent->result);
 		}
+
+		bftw_queue_attach(&state->fileq, file, true);
+		break;
+
+	default:
+		bfs_bug("Unexpected ioq op %d", (int)op);
 		break;
 	}
 
@@ -575,9 +1073,9 @@ static int bftw_ioq_reserve(struct bftw_state *state) {
 		return 0;
 	}
 
-	// With more than two threads, it is faster to wait for an I/O operation
-	// to complete than it is to do it ourselves
-	bool block = state->nthreads > 2;
+	// With more than one background thread, it's faster to wait on
+	// background I/O than it is to do it on the main thread
+	bool block = state->nthreads > 1;
 	if (bftw_ioq_pop(state, block) < 0) {
 		return -1;
 	}
@@ -661,7 +1159,7 @@ static int bftw_file_open(struct bftw_state *state, struct bftw_file *file, cons
 	}
 
 	int fd = bftw_file_openat(state, file, base, at_path);
-	if (fd >= 0 || errno != ENAMETOOLONG) {
+	if (fd >= 0 || !errno_is_like(ENAMETOOLONG)) {
 		return fd;
 	}
 
@@ -669,12 +1167,13 @@ static int bftw_file_open(struct bftw_state *state, struct bftw_file *file, cons
 	struct bftw_list parents;
 	SLIST_INIT(&parents);
 
-	struct bftw_file *cur;
-	for (cur = file; cur != base; cur = cur->parent) {
+	// Reverse the chain of parents
+	for (struct bftw_file *cur = file; cur != base; cur = cur->parent) {
 		SLIST_PREPEND(&parents, cur);
 	}
 
-	while ((cur = SLIST_POP(&parents))) {
+	// Open each component relative to its parent
+	drain_slist (struct bftw_file, cur, &parents) {
 		if (!cur->parent || cur->parent->fd >= 0) {
 			bftw_file_openat(state, cur, cur->parent, cur->name);
 		}
@@ -762,8 +1261,12 @@ static int bftw_unwrapdir(struct bftw_state *state, struct bftw_file *file) {
 		return bftw_close(state, file);
 	}
 
-	if (bftw_cache_reserve(state) != 0) {
-		return -1;
+	// Make room for dup()
+	bftw_cache_pin(cache, file);
+	int ret = bftw_cache_reserve(state);
+	bftw_cache_unpin(cache, file);
+	if (ret != 0) {
+		return ret;
 	}
 
 	int fd = dup_cloexec(file->fd);
@@ -777,124 +1280,285 @@ static int bftw_unwrapdir(struct bftw_state *state, struct bftw_file *file) {
 	return bftw_ioq_closedir(state, dir);
 }
 
+/** Try to pin a file's parent. */
+static int bftw_pin_parent(struct bftw_state *state, struct bftw_file *file) {
+	struct bftw_file *parent = file->parent;
+	if (!parent) {
+		return AT_FDCWD;
+	}
+
+	int fd = parent->fd;
+	if (fd < 0) {
+		// Don't confuse failures with AT_FDCWD
+		return (int)AT_FDCWD == -1 ? -2 : -1;
+	}
+
+	bftw_cache_pin(&state->cache, parent);
+	return fd;
+}
+
 /** Open a directory asynchronously. */
 static int bftw_ioq_opendir(struct bftw_state *state, struct bftw_file *file) {
+	struct bftw_cache *cache = &state->cache;
+
 	if (bftw_ioq_reserve(state) != 0) {
 		goto fail;
 	}
 
-	int dfd = AT_FDCWD;
-	struct bftw_cache *cache = &state->cache;
-	struct bftw_file *parent = file->parent;
-	if (parent) {
-		dfd = parent->fd;
-		if (dfd < 0) {
-			goto fail;
-		}
-		bftw_cache_pin(cache, parent);
+	int dfd = bftw_pin_parent(state, file);
+	if (dfd < 0 && dfd != (int)AT_FDCWD) {
+		goto fail;
 	}
 
 	if (bftw_cache_reserve(state) != 0) {
 		goto unpin;
 	}
 
-	struct bfs_dir *dir = bftw_allocdir(cache);
+	struct bfs_dir *dir = bftw_allocdir(cache, false);
 	if (!dir) {
 		goto unpin;
 	}
 
-	if (ioq_opendir(state->ioq, dir, dfd, file->name, file) != 0) {
+	if (ioq_opendir(state->ioq, dir, dfd, file->name, state->dir_flags, file) != 0) {
 		goto free;
 	}
 
-	file->ioqueued = true;
 	--cache->capacity;
 	return 0;
 
 free:
 	bftw_freedir(cache, dir);
 unpin:
-	if (parent) {
-		bftw_cache_unpin(cache, parent);
-	}
+	bftw_unpin_parent(state, file, false);
 fail:
 	return -1;
 }
 
+/** Open a batch of directories asynchronously. */
+static void bftw_ioq_opendirs(struct bftw_state *state) {
+	while (bftw_queue_balanced(&state->dirq)) {
+		struct bftw_file *dir = bftw_queue_waiting(&state->dirq);
+		if (!dir) {
+			break;
+		}
+
+		if (bftw_ioq_opendir(state, dir) == 0) {
+			bftw_queue_detach(&state->dirq, dir, true);
+		} else {
+			break;
+		}
+	}
+}
+
 /** Push a directory onto the queue. */
 static void bftw_push_dir(struct bftw_state *state, struct bftw_file *file) {
 	bfs_assert(file->type == BFS_DIR);
+	bftw_queue_push(&state->dirq, file);
+	bftw_ioq_opendirs(state);
+}
 
-	SLIST_APPEND(&state->to_open, file);
-
-	if (state->flags & BFTW_SORT) {
-		// When sorting, directories are kept in order on the to_read
-		// list; otherwise, they are only added once they are open
-		SLIST_APPEND(&state->to_read, file, to_read);
+/** Pop a file from a queue, then activate it. */
+static bool bftw_pop(struct bftw_state *state, struct bftw_queue *queue) {
+	if (queue->size == 0) {
+		return false;
 	}
 
-	while (state->to_open.head) {
-		if (bftw_ioq_opendir(state, state->to_open.head) == 0) {
-			SLIST_POP(&state->to_open);
-		} else {
+	while (!bftw_queue_ready(queue) && queue->ioqueued > 0) {
+		bool block = true;
+		if (bftw_queue_waiting(queue) && state->nthreads == 1) {
+			// With only one background thread, balance the work
+			// between it and the main thread
+			block = false;
+		}
+
+		if (bftw_ioq_pop(state, block) < 0) {
 			break;
 		}
 	}
+
+	struct bftw_file *file = bftw_queue_pop(queue);
+	if (!file) {
+		return false;
+	}
+
+	while (file->ioqueued) {
+		bftw_ioq_pop(state, true);
+	}
+
+	state->file = file;
+	return true;
 }
 
 /** Pop a directory to read from the queue. */
 static bool bftw_pop_dir(struct bftw_state *state) {
 	bfs_assert(!state->file);
 
-	struct bftw_cache *cache = &state->cache;
-	bool have_files = state->to_visit.head;
-
 	if (state->flags & BFTW_SORT) {
 		// Keep strict breadth-first order when sorting
-		if (state->strategy != BFTW_DFS && have_files) {
+		if (state->strategy == BFTW_BFS && bftw_queue_ready(&state->fileq)) {
 			return false;
 		}
+	} else if (!bftw_queue_ready(&state->dirq)) {
+		// Don't block if we have files ready to visit
+		if (bftw_queue_ready(&state->fileq)) {
+			return false;
+		}
+	}
+
+	return bftw_pop(state, &state->dirq);
+}
+
+/** Figure out bfs_stat() flags. */
+static enum bfs_stat_flags bftw_stat_flags(const struct bftw_state *state, size_t depth) {
+	enum bftw_flags mask = BFTW_FOLLOW_ALL;
+	if (depth == 0) {
+		mask |= BFTW_FOLLOW_ROOTS;
+	}
+
+	if (state->flags & mask) {
+		return BFS_STAT_TRYFOLLOW;
 	} else {
-		while (!state->to_read.head) {
-			// Block if we have no other files/dirs to visit, or no room in the cache
-			bool have_dirs = state->to_open.head;
-			bool have_room = cache->capacity > 0 && cache->dirlimit > 0;
-			bool block = !(have_dirs || have_files) || !have_room;
-
-			if (bftw_ioq_pop(state, block) < 0) {
-				break;
-			}
+		return BFS_STAT_NOFOLLOW;
+	}
+}
+
+/** Check if a stat() call is necessary. */
+static bool bftw_must_stat(const struct bftw_state *state, size_t depth, enum bfs_type type, const char *name) {
+	if (state->flags & BFTW_STAT) {
+		return true;
+	}
+
+	switch (type) {
+	case BFS_UNKNOWN:
+		return true;
+
+	case BFS_DIR:
+		return state->flags & (BFTW_DETECT_CYCLES | BFTW_SKIP_MOUNTS | BFTW_PRUNE_MOUNTS);
+
+	case BFS_LNK:
+		if (!(bftw_stat_flags(state, depth) & BFS_STAT_NOFOLLOW)) {
+			return true;
 		}
+		_fallthrough;
+
+	default:
+#if __linux__
+		if (state->mtab && bfs_might_be_mount(state->mtab, name)) {
+			return true;
+		}
+#endif
+		return false;
 	}
+}
 
-	struct bftw_file *file = SLIST_POP(&state->to_read, to_read);
-	if (!file || file == state->to_open.head) {
-		file = SLIST_POP(&state->to_open);
+/** stat() a file asynchronously. */
+static int bftw_ioq_stat(struct bftw_state *state, struct bftw_file *file) {
+	if (bftw_ioq_reserve(state) != 0) {
+		goto fail;
 	}
-	if (!file) {
+
+	int dfd = bftw_pin_parent(state, file);
+	if (dfd < 0 && dfd != (int)AT_FDCWD) {
+		goto fail;
+	}
+
+	struct bftw_cache *cache = &state->cache;
+	struct bfs_stat *buf = arena_alloc(&cache->stat_bufs);
+	if (!buf) {
+		goto unpin;
+	}
+
+	enum bfs_stat_flags flags = bftw_stat_flags(state, file->depth);
+	if (ioq_stat(state->ioq, dfd, file->name, flags, buf, file) != 0) {
+		goto free;
+	}
+
+	return 0;
+
+free:
+	arena_free(&cache->stat_bufs, buf);
+unpin:
+	bftw_unpin_parent(state, file, false);
+fail:
+	return -1;
+}
+
+/** Check if we should stat() a file asynchronously. */
+static bool bftw_should_ioq_stat(struct bftw_state *state, struct bftw_file *file) {
+	// To avoid surprising users too much, process the roots in order
+	if (file->depth == 0) {
 		return false;
 	}
 
-	while (file->ioqueued) {
-		bftw_ioq_pop(state, true);
+#ifdef S_IFWHT
+	// ioq_stat() does not do whiteout emulation like bftw_stat_impl()
+	if (file->type == BFS_WHT) {
+		return false;
 	}
+#endif
 
-	state->file = file;
-	return true;
+	return bftw_must_stat(state, file->depth, file->type, file->name);
+}
+
+/** Call stat() on files that need it. */
+static void bftw_stat_files(struct bftw_state *state) {
+	while (true) {
+		struct bftw_file *file = bftw_queue_waiting(&state->fileq);
+		if (!file) {
+			break;
+		}
+
+		if (!bftw_should_ioq_stat(state, file)) {
+			bftw_queue_skip(&state->fileq, file);
+			continue;
+		}
+
+		if (!bftw_queue_balanced(&state->fileq)) {
+			break;
+		}
+
+		if (bftw_ioq_stat(state, file) == 0) {
+			bftw_queue_detach(&state->fileq, file, true);
+		} else {
+			break;
+		}
+	}
+}
+
+/** Push a file onto the queue. */
+static void bftw_push_file(struct bftw_state *state, struct bftw_file *file) {
+	bftw_queue_push(&state->fileq, file);
+	bftw_stat_files(state);
 }
 
 /** Pop a file to visit from the queue. */
 static bool bftw_pop_file(struct bftw_state *state) {
 	bfs_assert(!state->file);
-	state->file = SLIST_POP(&state->to_visit);
-	return state->file;
+	return bftw_pop(state, &state->fileq);
+}
+
+/** Add a path component to the path. */
+static void bftw_prepend_path(char *path, size_t nameoff, size_t namelen, const char *name) {
+	if (nameoff > 0) {
+		path[nameoff - 1] = '/';
+	}
+	memcpy(path + nameoff, name, namelen);
 }
 
 /** Build the path to the current file. */
 static int bftw_build_path(struct bftw_state *state, const char *name) {
 	const struct bftw_file *file = state->file;
 
-	size_t pathlen = file ? file->nameoff + file->namelen : 0;
+	size_t nameoff, namelen;
+	if (name) {
+		nameoff = file ? bftw_child_nameoff(file) : 0;
+		namelen = strlen(name);
+	} else {
+		nameoff = file->nameoff;
+		namelen = file->namelen;
+	}
+
+	size_t pathlen = nameoff + namelen;
 	if (dstresize(&state->path, pathlen) != 0) {
 		state->error = errno;
 		return -1;
@@ -907,11 +1571,11 @@ static int bftw_build_path(struct bftw_state *state, const char *name) {
 	}
 
 	// Build the path backwards
+	if (name) {
+		bftw_prepend_path(state->path, nameoff, namelen, name);
+	}
 	while (file && file != ancestor) {
-		if (file->nameoff > 0) {
-			state->path[file->nameoff - 1] = '/';
-		}
-		memcpy(state->path + file->nameoff, file->name, file->namelen);
+		bftw_prepend_path(state->path, file->nameoff, file->namelen, file->name);
 
 		if (ancestor && ancestor->depth == file->depth) {
 			ancestor = ancestor->parent;
@@ -920,20 +1584,6 @@ static int bftw_build_path(struct bftw_state *state, const char *name) {
 	}
 
 	state->previous = state->file;
-
-	if (name) {
-		if (pathlen > 0 && state->path[pathlen - 1] != '/') {
-			if (dstrapp(&state->path, '/') != 0) {
-				state->error = errno;
-				return -1;
-			}
-		}
-		if (dstrcat(&state->path, name) != 0) {
-			state->error = errno;
-			return -1;
-		}
-	}
-
 	return 0;
 }
 
@@ -945,12 +1595,12 @@ static struct bfs_dir *bftw_file_opendir(struct bftw_state *state, struct bftw_f
 	}
 
 	struct bftw_cache *cache = &state->cache;
-	struct bfs_dir *dir = bftw_allocdir(cache);
+	struct bfs_dir *dir = bftw_allocdir(cache, true);
 	if (!dir) {
 		return NULL;
 	}
 
-	if (bfs_opendir(dir, fd, NULL) != 0) {
+	if (bfs_opendir(dir, fd, NULL, state->dir_flags) != 0) {
 		bftw_freedir(cache, dir);
 		return NULL;
 	}
@@ -969,18 +1619,23 @@ static int bftw_opendir(struct bftw_state *state) {
 	struct bftw_file *file = state->file;
 	state->dir = file->dir;
 	if (state->dir) {
-		return 0;
+		goto pin;
 	}
 
 	if (bftw_build_path(state, NULL) != 0) {
 		return -1;
 	}
 
+	bftw_queue_rebalance(&state->dirq, false);
+
 	state->dir = bftw_file_opendir(state, file, state->path);
 	if (!state->dir) {
 		state->direrror = errno;
+		return 0;
 	}
 
+pin:
+	bftw_cache_pin(&state->cache, file);
 	return 0;
 }
 
@@ -1003,47 +1658,6 @@ static int bftw_readdir(struct bftw_state *state) {
 	return ret;
 }
 
-/** Check if a stat() call is needed for this visit. */
-static bool bftw_need_stat(const struct bftw_state *state) {
-	if (state->flags & BFTW_STAT) {
-		return true;
-	}
-
-	const struct BFTW *ftwbuf = &state->ftwbuf;
-	if (ftwbuf->type == BFS_UNKNOWN) {
-		return true;
-	}
-
-	if (ftwbuf->type == BFS_LNK && !(ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
-		return true;
-	}
-
-	if (ftwbuf->type == BFS_DIR) {
-		if (state->flags & (BFTW_DETECT_CYCLES | BFTW_SKIP_MOUNTS | BFTW_PRUNE_MOUNTS)) {
-			return true;
-		}
-#if __linux__
-	} else if (state->mtab) {
-		// Linux fills in d_type from the underlying inode, even when
-		// the directory entry is a bind mount point.  In that case, we
-		// need to stat() to get the correct type.  We don't need to
-		// check for directories because they can only be mounted over
-		// by other directories.
-		if (bfs_might_be_mount(state->mtab, ftwbuf->path)) {
-			return true;
-		}
-#endif
-	}
-
-	return false;
-}
-
-/** Initialize bftw_stat cache. */
-static void bftw_stat_init(struct bftw_stat *cache) {
-	cache->buf = NULL;
-	cache->error = 0;
-}
-
 /** Open a file if necessary. */
 static int bftw_ensure_open(struct bftw_state *state, struct bftw_file *file, const char *path) {
 	int ret = file->fd;
@@ -1073,11 +1687,10 @@ static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) {
 	ftwbuf->visit = visit;
 	ftwbuf->type = BFS_UNKNOWN;
 	ftwbuf->error = state->direrror;
+	ftwbuf->loopoff = 0;
 	ftwbuf->at_fd = AT_FDCWD;
 	ftwbuf->at_path = ftwbuf->path;
-	ftwbuf->stat_flags = BFS_STAT_NOFOLLOW;
-	bftw_stat_init(&ftwbuf->lstat_cache);
-	bftw_stat_init(&ftwbuf->stat_cache);
+	bftw_stat_init(&ftwbuf->stat_bufs, &state->stat_buf, &state->lstat_buf);
 
 	struct bftw_file *parent = NULL;
 	if (de) {
@@ -1090,6 +1703,7 @@ static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) {
 		ftwbuf->depth = file->depth;
 		ftwbuf->type = file->type;
 		ftwbuf->nameoff = file->nameoff;
+		bftw_stat_fill(&ftwbuf->stat_bufs, &file->stat_bufs);
 	}
 
 	if (parent) {
@@ -1107,22 +1721,15 @@ static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) {
 		ftwbuf->nameoff = xbaseoff(ftwbuf->path);
 	}
 
+	ftwbuf->stat_flags = bftw_stat_flags(state, ftwbuf->depth);
+
 	if (ftwbuf->error != 0) {
 		ftwbuf->type = BFS_ERROR;
 		return;
 	}
 
-	int follow_flags = BFTW_FOLLOW_ALL;
-	if (ftwbuf->depth == 0) {
-		follow_flags |= BFTW_FOLLOW_ROOTS;
-	}
-	bool follow = state->flags & follow_flags;
-	if (follow) {
-		ftwbuf->stat_flags = BFS_STAT_TRYFOLLOW;
-	}
-
 	const struct bfs_stat *statbuf = NULL;
-	if (bftw_need_stat(state)) {
+	if (bftw_must_stat(state, ftwbuf->depth, ftwbuf->type, ftwbuf->path + ftwbuf->nameoff)) {
 		statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
 		if (statbuf) {
 			ftwbuf->type = bfs_mode_to_type(statbuf->mode);
@@ -1138,6 +1745,7 @@ static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) {
 			if (ancestor->dev == statbuf->dev && ancestor->ino == statbuf->ino) {
 				ftwbuf->type = BFS_ERROR;
 				ftwbuf->error = ELOOP;
+				ftwbuf->loopoff = ancestor->nameoff + ancestor->namelen;
 				return;
 			}
 		}
@@ -1161,6 +1769,11 @@ static bool bftw_is_mount(struct bftw_state *state, const char *name) {
 	return statbuf && statbuf->dev != parent->dev;
 }
 
+/** Check if bfs_stat() was called from the main thread. */
+static bool bftw_stat_was_sync(const struct bftw_state *state, const struct bfs_stat *buf) {
+	return buf == &state->stat_buf || buf == &state->lstat_buf;
+}
+
 /** Invoke the callback. */
 static enum bftw_action bftw_call_back(struct bftw_state *state, const char *name, enum bftw_visit visit) {
 	if (visit == BFTW_POST && !(state->flags & BFTW_POST_ORDER)) {
@@ -1180,31 +1793,43 @@ static enum bftw_action bftw_call_back(struct bftw_state *state, const char *nam
 		return BFTW_STOP;
 	}
 
+	enum bftw_action ret = BFTW_PRUNE;
 	if ((state->flags & BFTW_SKIP_MOUNTS) && bftw_is_mount(state, name)) {
-		return BFTW_PRUNE;
+		goto done;
 	}
 
-	enum bftw_action ret = state->callback(ftwbuf, state->ptr);
+	ret = state->callback(ftwbuf, state->ptr);
 	switch (ret) {
 	case BFTW_CONTINUE:
-		if (visit != BFTW_PRE) {
-			return BFTW_PRUNE;
-		}
-		if (ftwbuf->type != BFS_DIR) {
-			return BFTW_PRUNE;
-		}
-		if ((state->flags & BFTW_PRUNE_MOUNTS) && bftw_is_mount(state, name)) {
-			return BFTW_PRUNE;
+		if (visit != BFTW_PRE || ftwbuf->type != BFS_DIR) {
+			ret = BFTW_PRUNE;
+		} else if (state->flags & BFTW_PRUNE_MOUNTS) {
+			if (bftw_is_mount(state, name)) {
+				ret = BFTW_PRUNE;
+			}
 		}
-		fallthru;
+		break;
+
 	case BFTW_PRUNE:
 	case BFTW_STOP:
-		return ret;
+		break;
 
 	default:
 		state->error = EINVAL;
 		return BFTW_STOP;
 	}
+
+done:
+	if (state->fileq.flags & BFTW_QBALANCE) {
+		// Detect any main-thread stat() calls to rebalance the queue
+		const struct bfs_stat *buf = bftw_cached_stat(ftwbuf, BFS_STAT_FOLLOW);
+		const struct bfs_stat *lbuf = bftw_cached_stat(ftwbuf, BFS_STAT_NOFOLLOW);
+		if (bftw_stat_was_sync(state, buf) || bftw_stat_was_sync(state, lbuf)) {
+			bftw_queue_rebalance(&state->fileq, false);
+		}
+	}
+
+	return ret;
 }
 
 /**
@@ -1228,9 +1853,13 @@ static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) {
 	int ret = 0;
 
 	struct bftw_file *file = state->file;
-	if (file && file->dir) {
-		bftw_cache_unpin(&state->cache, file);
-		SLIST_APPEND(&state->to_close, file);
+	if (file) {
+		if (state->dir) {
+			bftw_cache_unpin(&state->cache, file);
+		}
+		if (file->dir) {
+			bftw_delayed_unwrap(state, file);
+		}
 	}
 	state->dir = NULL;
 	state->de = NULL;
@@ -1247,8 +1876,8 @@ static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) {
 	}
 	state->direrror = 0;
 
-	while ((file = SLIST_POP(&state->to_close))) {
-		bftw_unwrapdir(state, file);
+	drain_slist (struct bftw_file, dead, &state->to_close, ready) {
+		bftw_unwrapdir(state, dead);
 	}
 
 	enum bftw_gc_flags visit = BFTW_VISIT_FILE;
@@ -1303,7 +1932,7 @@ static void bftw_list_sort(struct bftw_list *list) {
 	bftw_list_sort(&right);
 
 	// Merge
-	while (left.head && right.head) {
+	while (!SLIST_EMPTY(&left) && !SLIST_EMPTY(&right)) {
 		struct bftw_file *lf = left.head;
 		struct bftw_file *rf = right.head;
 
@@ -1319,16 +1948,20 @@ static void bftw_list_sort(struct bftw_list *list) {
 	SLIST_EXTEND(list, &right);
 }
 
-/** Finish adding a batch of files. */
-static void bftw_batch_finish(struct bftw_state *state) {
+/** Flush all the queue buffers. */
+static void bftw_flush(struct bftw_state *state) {
 	if (state->flags & BFTW_SORT) {
-		bftw_list_sort(&state->batch);
+		bftw_list_sort(&state->fileq.buffer);
 	}
+	bftw_queue_flush(&state->fileq);
+	bftw_stat_files(state);
 
-	if (state->strategy != BFTW_BFS) {
-		SLIST_EXTEND(&state->batch, &state->to_visit);
+	bftw_queue_flush(&state->dirq);
+	bftw_ioq_opendirs(state);
+
+	if (state->ioq) {
+		ioq_submit(state->ioq);
 	}
-	SLIST_EXTEND(&state->to_visit, &state->batch);
 }
 
 /** Close the current directory. */
@@ -1337,7 +1970,7 @@ static int bftw_closedir(struct bftw_state *state) {
 		return -1;
 	}
 
-	bftw_batch_finish(state);
+	bftw_flush(state);
 	return 0;
 }
 
@@ -1345,22 +1978,46 @@ static int bftw_closedir(struct bftw_state *state) {
 static void bftw_save_ftwbuf(struct bftw_file *file, const struct BFTW *ftwbuf) {
 	file->type = ftwbuf->type;
 
-	const struct bfs_stat *statbuf = ftwbuf->stat_cache.buf;
-	if (!statbuf || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
-		statbuf = ftwbuf->lstat_cache.buf;
-	}
+	const struct bfs_stat *statbuf = bftw_cached_stat(ftwbuf, ftwbuf->stat_flags);
 	if (statbuf) {
 		file->dev = statbuf->dev;
 		file->ino = statbuf->ino;
 	}
 }
 
+/** Check if we should buffer a file instead of visiting it. */
+static bool bftw_buffer_file(const struct bftw_state *state, const struct bftw_file *file, const char *name) {
+	if (!name) {
+		// Already buffered
+		return false;
+	}
+
+	if (state->flags & BFTW_BUFFER) {
+		return true;
+	}
+
+	// If we need to call stat(), and can do it async, buffer this file
+	if (!state->ioq) {
+		return false;
+	}
+
+	if (!bftw_queue_balanced(&state->fileq)) {
+		// stat() would run synchronously anyway
+		return false;
+	}
+
+	size_t depth = file ? file->depth + 1 : 1;
+	enum bfs_type type = state->de ? state->de->type : BFS_UNKNOWN;
+	return bftw_must_stat(state, depth, type, name);
+}
+
 /** Visit and/or enqueue the current file. */
 static int bftw_visit(struct bftw_state *state, const char *name) {
+	struct bftw_cache *cache = &state->cache;
 	struct bftw_file *file = state->file;
 
-	if (name && (state->flags & BFTW_BUFFER)) {
-		file = bftw_file_new(&state->cache, file, name);
+	if (bftw_buffer_file(state, file, name)) {
+		file = bftw_file_new(cache, file, name);
 		if (!file) {
 			state->error = errno;
 			return -1;
@@ -1370,14 +2027,14 @@ static int bftw_visit(struct bftw_state *state, const char *name) {
 			file->type = state->de->type;
 		}
 
-		SLIST_APPEND(&state->batch, file);
+		bftw_push_file(state, file);
 		return 0;
 	}
 
 	switch (bftw_call_back(state, name, BFTW_PRE)) {
 	case BFTW_CONTINUE:
 		if (name) {
-			file = bftw_file_new(&state->cache, state->file, name);
+			file = bftw_file_new(cache, state->file, name);
 		} else {
 			state->file = NULL;
 		}
@@ -1387,6 +2044,7 @@ static int bftw_visit(struct bftw_state *state, const char *name) {
 		}
 
 		bftw_save_ftwbuf(file, &state->ftwbuf);
+		bftw_stat_recycle(cache, file);
 		bftw_push_dir(state, file);
 		return 0;
 
@@ -1398,10 +2056,22 @@ static int bftw_visit(struct bftw_state *state, const char *name) {
 		}
 
 	default:
+		if (file && !name) {
+			bftw_gc(state, BFTW_VISIT_NONE);
+		}
 		return -1;
 	}
 }
 
+/** Drain a bftw_queue. */
+static void bftw_drain(struct bftw_state *state, struct bftw_queue *queue) {
+	bftw_queue_flush(queue);
+
+	while (bftw_pop(state, queue)) {
+		bftw_gc(state, BFTW_VISIT_NONE);
+	}
+}
+
 /**
  * Dispose of the bftw() state.
  *
@@ -1418,10 +2088,9 @@ static int bftw_state_destroy(struct bftw_state *state) {
 		state->ioq = NULL;
 	}
 
-	SLIST_EXTEND(&state->to_visit, &state->batch);
-	do {
-		bftw_gc(state, BFTW_VISIT_NONE);
-	} while (bftw_pop_dir(state) || bftw_pop_file(state));
+	bftw_gc(state, BFTW_VISIT_NONE);
+	bftw_drain(state, &state->dirq);
+	bftw_drain(state, &state->fileq);
 
 	ioq_destroy(ioq);
 
@@ -1440,7 +2109,7 @@ static int bftw_impl(struct bftw_state *state) {
 			return -1;
 		}
 	}
-	bftw_batch_finish(state);
+	bftw_flush(state);
 
 	while (true) {
 		while (bftw_pop_dir(state)) {
@@ -1461,8 +2130,9 @@ static int bftw_impl(struct bftw_state *state) {
 			break;
 		}
 		if (bftw_visit(state, NULL) != 0) {
-			break;
+			return -1;
 		}
+		bftw_flush(state);
 	}
 
 	return 0;