From 3cc581c0295465fd5dc2fc818aa92f48dd87788e Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 17 Jul 2023 19:03:30 -0400
Subject: bftw: Pass the whole bftw_state to bftw_openat()

This required shuffling a lot of code around.  Hopefully the new order
makes more sense.
---
 src/bftw.c | 1263 +++++++++++++++++++++++++++++-------------------------------
 1 file changed, 602 insertions(+), 661 deletions(-)

(limited to 'src/bftw.c')

diff --git a/src/bftw.c b/src/bftw.c
index 553363e..2262591 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -34,6 +34,78 @@
 #include <string.h>
 #include <sys/stat.h>
 
+/** 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;
+		} else {
+			cache->error = errno;
+		}
+	}
+
+	return cache->buf;
+}
+
+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;
+		}
+	} 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);
+		}
+	}
+
+	return ret;
+}
+
+const struct bfs_stat *bftw_cached_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
+	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;
+	}
+}
+
+enum bfs_type bftw_type(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
+	if (flags & BFS_STAT_NOFOLLOW) {
+		if (ftwbuf->type == BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
+			return ftwbuf->type;
+		}
+	} else if (flags & BFS_STAT_TRYFOLLOW) {
+		if (ftwbuf->type != BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW)) {
+			return ftwbuf->type;
+		}
+	} else {
+		if (ftwbuf->type != BFS_LNK) {
+			return ftwbuf->type;
+		} else if (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW) {
+			return BFS_ERROR;
+		}
+	}
+
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, flags);
+	if (statbuf) {
+		return bfs_mode_to_type(statbuf->mode);
+	} else {
+		return BFS_ERROR;
+	}
+}
+
 /**
  * A file.
  */
@@ -277,103 +349,7 @@ static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_fil
 	return file;
 }
 
-/**
- * Open a bftw_file relative to another one.
- *
- * @param cache
- *         The cache to hold the file.
- * @param file
- *         The file to open.
- * @param base
- *         The base directory for the relative path (may be NULL).
- * @param at_fd
- *         The base file descriptor, AT_FDCWD if base == NULL.
- * @param at_path
- *         The relative path to the file.
- * @return
- *         The opened file descriptor, or negative on error.
- */
-static int bftw_file_openat(struct bftw_cache *cache, struct bftw_file *file, struct bftw_file *base, const char *at_path) {
-	bfs_assert(file->fd < 0);
-
-	int at_fd = AT_FDCWD;
-	if (base) {
-		bftw_cache_pin(cache, base);
-		at_fd = base->fd;
-	}
-
-	int flags = O_RDONLY | O_CLOEXEC | O_DIRECTORY;
-	int fd = openat(at_fd, at_path, flags);
-
-	if (fd < 0 && errno == EMFILE) {
-		if (bftw_cache_pop(cache) == 0) {
-			fd = openat(at_fd, at_path, flags);
-		}
-		cache->capacity = 1;
-	}
-
-	if (base) {
-		bftw_cache_unpin(cache, base);
-	}
-
-	if (fd >= 0) {
-		file->fd = fd;
-		bftw_cache_add(cache, file);
-	}
-
-	return file->fd;
-}
-
-/**
- * Open a bftw_file.
- *
- * @param cache
- *         The cache to hold the file.
- * @param file
- *         The file to open.
- * @param path
- *         The full path to the file.
- * @return
- *         The opened file descriptor, or negative on error.
- */
-static int bftw_file_open(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
-	// Find the nearest open ancestor
-	struct bftw_file *base = file;
-	do {
-		base = base->parent;
-	} while (base && base->fd < 0);
-
-	const char *at_path = path;
-	if (base) {
-		at_path += bftw_child_nameoff(base);
-	}
-
-	int fd = bftw_file_openat(cache, file, base, at_path);
-	if (fd >= 0 || errno != ENAMETOOLONG) {
-		return fd;
-	}
-
-	// Handle ENAMETOOLONG by manually traversing the path component-by-component
-	struct bftw_list parents;
-	SLIST_INIT(&parents);
-
-	struct bftw_file *cur;
-	for (cur = file; cur != base; cur = cur->parent) {
-		SLIST_PREPEND(&parents, cur);
-	}
-
-	while ((cur = SLIST_POP(&parents))) {
-		if (!cur->parent || cur->parent->fd >= 0) {
-			bftw_file_openat(cache, cur, cur->parent, cur->name);
-		}
-	}
-
-	return file->fd;
-}
-
-/**
- * Associate an open directory with a bftw_file.
- */
+/** Associate an open directory with a bftw_file. */
 static void bftw_file_set_dir(struct bftw_cache *cache, struct bftw_file *file, struct bfs_dir *dir) {
 	bfs_assert(!file->dir);
 	file->dir = dir;
@@ -384,38 +360,6 @@ static void bftw_file_set_dir(struct bftw_cache *cache, struct bftw_file *file,
 	}
 }
 
-/**
- * Open a bftw_file as a directory.
- *
- * @param cache
- *         The cache to hold the file.
- * @param file
- *         The directory to open.
- * @param path
- *         The full path to the directory.
- * @return
- *         The opened directory, or NULL on error.
- */
-static struct bfs_dir *bftw_file_opendir(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
-	int fd = bftw_file_open(cache, file, path);
-	if (fd < 0) {
-		return NULL;
-	}
-
-	struct bfs_dir *dir = bftw_allocdir(cache);
-	if (!dir) {
-		return NULL;
-	}
-
-	if (bfs_opendir(dir, fd, NULL) != 0) {
-		bftw_freedir(cache, dir);
-		return NULL;
-	}
-
-	bftw_file_set_dir(cache, file, dir);
-	return dir;
-}
-
 /** Free a bftw_file. */
 static void bftw_file_free(struct bftw_cache *cache, struct bftw_file *file) {
 	bfs_assert(file->refcount == 0);
@@ -480,9 +424,7 @@ struct bftw_state {
 	struct BFTW ftwbuf;
 };
 
-/**
- * Initialize the bftw() state.
- */
+/** Initialize the bftw() state. */
 static int bftw_state_init(struct bftw_state *state, const struct bftw_args *args) {
 	state->callback = args->callback;
 	state->ptr = args->ptr;
@@ -542,676 +484,677 @@ static int bftw_state_init(struct bftw_state *state, const struct bftw_args *arg
 	return 0;
 }
 
-/** Cached 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;
-		} else {
-			cache->error = errno;
-		}
+/** Pop a response from the I/O queue. */
+static int bftw_ioq_pop(struct bftw_state *state, bool block) {
+	struct ioq *ioq = state->ioq;
+	if (!ioq) {
+		return -1;
 	}
 
-	return cache->buf;
-}
+	struct ioq_ent *ent = block ? ioq_pop(ioq) : ioq_trypop(ioq);
+	if (!ent) {
+		return -1;
+	}
 
-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;
+	struct bftw_cache *cache = &state->cache;
+	struct bftw_file *file;
+	struct bfs_dir *dir;
 
-	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;
-		}
-	} 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);
-		}
-	}
+	enum ioq_op op = ent->op;
+	switch (op) {
+	case IOQ_CLOSE:
+		++cache->capacity;
+		break;
 
-	return ret;
-}
+	case IOQ_CLOSEDIR:
+		++cache->capacity;
+		dir = ent->closedir.dir;
+		bftw_freedir(cache, dir);
+		break;
 
-const struct bfs_stat *bftw_cached_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
-	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;
-	}
-}
+	case IOQ_OPENDIR:
+		file = ent->ptr;
+		file->ioqueued = false;
 
-enum bfs_type bftw_type(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
-	if (flags & BFS_STAT_NOFOLLOW) {
-		if (ftwbuf->type == BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
-			return ftwbuf->type;
+		++cache->capacity;
+		if (file->parent) {
+			bftw_cache_unpin(cache, file->parent);
 		}
-	} else if (flags & BFS_STAT_TRYFOLLOW) {
-		if (ftwbuf->type != BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW)) {
-			return ftwbuf->type;
+
+		dir = ent->opendir.dir;
+		if (ent->ret == 0) {
+			bftw_file_set_dir(cache, file, dir);
+		} else {
+			bftw_freedir(cache, dir);
 		}
-	} else {
-		if (ftwbuf->type != BFS_LNK) {
-			return ftwbuf->type;
-		} else if (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW) {
-			return BFS_ERROR;
+
+		if (!(state->flags & BFTW_SORT)) {
+			SLIST_PREPEND(&state->dirs, file);
 		}
+		break;
 	}
 
-	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, flags);
-	if (statbuf) {
-		return bfs_mode_to_type(statbuf->mode);
-	} else {
-		return BFS_ERROR;
-	}
+	ioq_free(ioq, ent);
+	return op;
 }
 
-/**
- * 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;
-	if (dstresize(&state->path, pathlen) != 0) {
-		state->error = errno;
+/** Try to reserve space in the I/O queue. */
+static int bftw_ioq_reserve(struct bftw_state *state) {
+	struct ioq *ioq = state->ioq;
+	if (!ioq) {
 		return -1;
 	}
 
-	// Try to find a common ancestor with the existing path
-	const struct bftw_file *ancestor = state->previous;
-	while (ancestor && ancestor->depth > file->depth) {
-		ancestor = ancestor->parent;
+	if (ioq_capacity(ioq) > 0) {
+		return 0;
 	}
 
-	// Build the path backwards
-	while (file && file != ancestor) {
-		if (file->nameoff > 0) {
-			state->path[file->nameoff - 1] = '/';
-		}
-		memcpy(state->path + file->nameoff, file->name, file->namelen);
-
-		if (ancestor && ancestor->depth == file->depth) {
-			ancestor = ancestor->parent;
-		}
-		file = file->parent;
+	// 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;
+	if (bftw_ioq_pop(state, block) < 0) {
+		return -1;
 	}
 
-	state->previous = state->file;
+	return 0;
+}
 
-	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;
+/** Try to reserve space in the cache. */
+static int bftw_cache_reserve(struct bftw_state *state) {
+	struct bftw_cache *cache = &state->cache;
+	if (cache->capacity > 0) {
+		return 0;
+	}
+
+	while (bftw_ioq_pop(state, true) >= 0) {
+		if (cache->capacity > 0) {
+			return 0;
 		}
 	}
 
-	return 0;
+	return bftw_cache_pop(cache);
 }
 
-/** 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;
+/** Open a bftw_file relative to another one. */
+static int bftw_file_openat(struct bftw_state *state, struct bftw_file *file, struct bftw_file *base, const char *at_path) {
+	bfs_assert(file->fd < 0);
+
+	struct bftw_cache *cache = &state->cache;
+
+	int at_fd = AT_FDCWD;
+	if (base) {
+		bftw_cache_pin(cache, base);
+		at_fd = base->fd;
 	}
 
-	const struct BFTW *ftwbuf = &state->ftwbuf;
-	if (ftwbuf->type == BFS_UNKNOWN) {
-		return true;
+	int flags = O_RDONLY | O_CLOEXEC | O_DIRECTORY;
+	int fd = openat(at_fd, at_path, flags);
+
+	if (fd < 0 && errno == EMFILE) {
+		if (bftw_cache_pop(cache) == 0) {
+			fd = openat(at_fd, at_path, flags);
+		}
+		cache->capacity = 1;
 	}
 
-	if (ftwbuf->type == BFS_LNK && !(ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
-		return true;
+	if (base) {
+		bftw_cache_unpin(cache, base);
 	}
 
-	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
+	if (fd >= 0) {
+		file->fd = fd;
+		bftw_cache_add(cache, file);
 	}
 
-	return false;
+	return file->fd;
 }
 
-/** Initialize bftw_stat cache. */
-static void bftw_stat_init(struct bftw_stat *cache) {
-	cache->buf = NULL;
-	cache->error = 0;
-}
+/** Open a bftw_file. */
+static int bftw_file_open(struct bftw_state *state, struct bftw_file *file, const char *path) {
+	// Find the nearest open ancestor
+	struct bftw_file *base = file;
+	do {
+		base = base->parent;
+	} while (base && base->fd < 0);
 
-/**
- * Open a file if necessary.
- *
- * @param file
- *         The file to open.
- * @param path
- *         The path to that file or one of its descendants.
- * @return
- *         The opened file descriptor, or -1 on error.
- */
-static int bftw_ensure_open(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
-	int ret = file->fd;
+	const char *at_path = path;
+	if (base) {
+		at_path += bftw_child_nameoff(base);
+	}
 
-	if (ret < 0) {
-		char *copy = strndup(path, file->nameoff + file->namelen);
-		if (!copy) {
-			return -1;
-		}
+	int fd = bftw_file_openat(state, file, base, at_path);
+	if (fd >= 0 || errno != ENAMETOOLONG) {
+		return fd;
+	}
 
-		ret = bftw_file_open(cache, file, copy);
-		free(copy);
+	// Handle ENAMETOOLONG by manually traversing the path component-by-component
+	struct bftw_list parents;
+	SLIST_INIT(&parents);
+
+	struct bftw_file *cur;
+	for (cur = file; cur != base; cur = cur->parent) {
+		SLIST_PREPEND(&parents, cur);
 	}
 
-	return ret;
+	while ((cur = SLIST_POP(&parents))) {
+		if (!cur->parent || cur->parent->fd >= 0) {
+			bftw_file_openat(state, cur, cur->parent, cur->name);
+		}
+	}
+
+	return file->fd;
 }
 
-/**
- * Initialize the buffers with data about the current path.
- */
-static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) {
-	struct bftw_file *file = state->file;
-	const struct bfs_dirent *de = state->de;
+/** 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);
 
-	struct BFTW *ftwbuf = &state->ftwbuf;
-	ftwbuf->path = state->path;
-	ftwbuf->root = file ? file->root->name : ftwbuf->path;
-	ftwbuf->depth = 0;
-	ftwbuf->visit = visit;
-	ftwbuf->type = BFS_UNKNOWN;
-	ftwbuf->error = state->direrror;
-	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);
+	struct bftw_cache *cache = &state->cache;
 
-	struct bftw_file *parent = NULL;
-	if (de) {
-		parent = file;
-		ftwbuf->depth = file->depth + 1;
-		ftwbuf->type = de->type;
-		ftwbuf->nameoff = bftw_child_nameoff(file);
-	} else if (file) {
-		parent = file->parent;
-		ftwbuf->depth = file->depth;
-		ftwbuf->type = file->type;
-		ftwbuf->nameoff = file->nameoff;
+	if (bftw_ioq_reserve(state) != 0) {
+		goto append;
 	}
 
-	if (parent) {
-		// Try to ensure the immediate parent is open, to avoid ENAMETOOLONG
-		if (bftw_ensure_open(&state->cache, parent, state->path) >= 0) {
-			ftwbuf->at_fd = parent->fd;
-			ftwbuf->at_path += ftwbuf->nameoff;
-		} else {
-			ftwbuf->error = errno;
+	int dfd = AT_FDCWD;
+	if (file->parent) {
+		dfd = file->parent->fd;
+		if (dfd < 0) {
+			goto append;
 		}
+		bftw_cache_pin(cache, file->parent);
 	}
 
-	if (ftwbuf->depth == 0) {
-		// Compute the name offset for root paths like "foo/bar"
-		ftwbuf->nameoff = xbaseoff(ftwbuf->path);
+	if (bftw_cache_reserve(state) != 0) {
+		goto unpin;
 	}
 
-	if (ftwbuf->error != 0) {
-		ftwbuf->type = BFS_ERROR;
-		return;
+	struct bfs_dir *dir = bftw_allocdir(cache);
+	if (!dir) {
+		goto unpin;
 	}
 
-	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;
+	if (ioq_opendir(state->ioq, dir, dfd, file->name, file) != 0) {
+		goto free;
 	}
 
-	const struct bfs_stat *statbuf = NULL;
-	if (bftw_need_stat(state)) {
-		statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
-		if (statbuf) {
-			ftwbuf->type = bfs_mode_to_type(statbuf->mode);
-		} else {
-			ftwbuf->type = BFS_ERROR;
-			ftwbuf->error = errno;
-			return;
-		}
+	file->ioqueued = true;
+	--cache->capacity;
+
+	if (state->flags & BFTW_SORT) {
+		// When sorting, dirs are always kept in order in state->dirs,
+		// and we wait for the ioq to open them before popping
+		goto append;
+	} else {
+		// When not sorting, dirs are not added to state->dirs until
+		// popped from the ioq
+		return;
 	}
 
-	if (ftwbuf->type == BFS_DIR && (state->flags & BFTW_DETECT_CYCLES)) {
-		for (const struct bftw_file *ancestor = parent; ancestor; ancestor = ancestor->parent) {
-			if (ancestor->dev == statbuf->dev && ancestor->ino == statbuf->ino) {
-				ftwbuf->type = BFS_ERROR;
-				ftwbuf->error = ELOOP;
-				return;
-			}
-		}
+free:
+	bftw_freedir(cache, dir);
+unpin:
+	if (file->parent) {
+		bftw_cache_unpin(cache, file->parent);
 	}
+append:
+	SLIST_APPEND(&state->dirs, file);
 }
 
-/** Check if the current file is a mount point. */
-static bool bftw_is_mount(struct bftw_state *state, const char *name) {
-	const struct bftw_file *file = state->file;
-	if (!file) {
-		return false;
+/** Close a directory, asynchronously if possible. */
+static int bftw_ioq_closedir(struct bftw_state *state, struct bfs_dir *dir) {
+	if (bftw_ioq_reserve(state) == 0) {
+		if (ioq_closedir(state->ioq, dir, NULL) == 0) {
+			return 0;
+		}
 	}
 
-	const struct bftw_file *parent = name ? file : file->parent;
-	if (!parent) {
-		return false;
+	struct bftw_cache *cache = &state->cache;
+	int ret = bfs_closedir(dir);
+	bftw_freedir(cache, dir);
+	++cache->capacity;
+	return ret;
+}
+
+/** Close a file descriptor, asynchronously if possible. */
+static int bftw_ioq_close(struct bftw_state *state, int fd) {
+	if (bftw_ioq_reserve(state) == 0) {
+		if (ioq_close(state->ioq, fd, NULL) == 0) {
+			return 0;
+		}
 	}
 
-	const struct BFTW *ftwbuf = &state->ftwbuf;
-	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
-	return statbuf && statbuf->dev != parent->dev;
+	struct bftw_cache *cache = &state->cache;
+	int ret = xclose(fd);
+	++cache->capacity;
+	return ret;
 }
 
-/**
- * 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)) {
-		return BFTW_PRUNE;
-	}
+/** Close a file, asynchronously if possible. */
+static int bftw_close(struct bftw_state *state, struct bftw_file *file) {
+	bfs_assert(file->fd >= 0);
+	bfs_assert(file->pincount == 0);
 
-	if (bftw_build_path(state, name) != 0) {
-		return BFTW_STOP;
-	}
+	struct bfs_dir *dir = file->dir;
+	int fd = file->fd;
 
-	const struct BFTW *ftwbuf = &state->ftwbuf;
-	bftw_init_ftwbuf(state, visit);
+	bftw_lru_remove(&state->cache, file);
+	file->dir = NULL;
+	file->fd = -1;
 
-	// Never give the callback BFS_ERROR unless BFTW_RECOVER is specified
-	if (ftwbuf->type == BFS_ERROR && !(state->flags & BFTW_RECOVER)) {
-		state->error = ftwbuf->error;
-		return BFTW_STOP;
+	if (dir) {
+		return bftw_ioq_closedir(state, dir);
+	} else {
+		return bftw_ioq_close(state, fd);
 	}
+}
 
-	if ((state->flags & BFTW_SKIP_MOUNTS) && bftw_is_mount(state, name)) {
-		return BFTW_PRUNE;
+/** Free an open directory. */
+static int bftw_unwrapdir(struct bftw_state *state, struct bftw_file *file) {
+	struct bfs_dir *dir = file->dir;
+	if (!dir) {
+		return 0;
 	}
 
-	enum bftw_action 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;
-		}
-		fallthru;
-	case BFTW_PRUNE:
-	case BFTW_STOP:
-		return ret;
+	struct bftw_cache *cache = &state->cache;
 
-	default:
-		state->error = EINVAL;
-		return BFTW_STOP;
+	// Try to keep an open fd if any children exist
+	bool reffed = file->refcount > 1;
+	// Keep the fd the same if it's pinned
+	bool pinned = file->pincount > 0;
+
+#if BFS_USE_UNWRAPDIR
+	if (reffed || pinned) {
+		bfs_unwrapdir(dir);
+		bftw_freedir(cache, dir);
+		file->dir = NULL;
+		return 0;
 	}
-}
+#else
+	if (pinned) {
+		return -1;
+	}
+#endif
 
-/** Pop a response from the I/O queue. */
-static int bftw_ioq_pop(struct bftw_state *state, bool block) {
-	struct ioq *ioq = state->ioq;
-	if (!ioq) {
+	if (!reffed) {
+		return bftw_close(state, file);
+	}
+
+	if (bftw_cache_reserve(state) != 0) {
 		return -1;
 	}
 
-	struct ioq_ent *ent = block ? ioq_pop(ioq) : ioq_trypop(ioq);
-	if (!ent) {
+	int fd = dup_cloexec(file->fd);
+	if (fd < 0) {
 		return -1;
 	}
+	--cache->capacity;
 
-	struct bftw_cache *cache = &state->cache;
-	struct bftw_file *file;
-	struct bfs_dir *dir;
+	file->dir = NULL;
+	file->fd = fd;
+	return bftw_ioq_closedir(state, dir);
+}
 
-	enum ioq_op op = ent->op;
-	switch (op) {
-	case IOQ_CLOSE:
-		++cache->capacity;
-		break;
+/** Pop a directory to read from the queue. */
+static bool bftw_pop_dir(struct bftw_state *state) {
+	bfs_assert(!state->file);
 
-	case IOQ_CLOSEDIR:
-		++cache->capacity;
-		dir = ent->closedir.dir;
-		bftw_freedir(cache, dir);
-		break;
+	struct bftw_file *dir = state->dirs.head;
+	bool have_files = state->files.head;
 
-	case IOQ_OPENDIR:
-		file = ent->ptr;
-		file->ioqueued = false;
+	if (state->flags & BFTW_SORT) {
+		// Keep strict breadth-first order when sorting
+		if (state->strategy != BFTW_DFS && have_files) {
+			return false;
+		}
+	} else {
+		while (!dir || !dir->dir) {
+			// Block if we have no other files/dirs to visit, or no room in the cache
+			bool have_room = state->cache.capacity > 0;
+			bool block = !(dir || have_files) || !have_room;
 
-		++cache->capacity;
-		if (file->parent) {
-			bftw_cache_unpin(cache, file->parent);
+			if (bftw_ioq_pop(state, block) < 0) {
+				break;
+			}
+			dir = state->dirs.head;
 		}
+	}
 
-		dir = ent->opendir.dir;
-		if (ent->ret == 0) {
-			bftw_file_set_dir(cache, file, dir);
-		} else {
-			bftw_freedir(cache, dir);
-		}
+	if (!dir) {
+		return false;
+	}
 
-		if (!(state->flags & BFTW_SORT)) {
-			SLIST_PREPEND(&state->dirs, file);
-		}
-		break;
+	SLIST_POP(&state->dirs);
+	state->file = dir;
+
+	while (dir->ioqueued) {
+		bftw_ioq_pop(state, true);
 	}
 
-	ioq_free(ioq, ent);
-	return op;
+	return true;
 }
 
-/** Try to reserve space in the I/O queue. */
-static int bftw_ioq_reserve(struct bftw_state *state) {
-	struct ioq *ioq = state->ioq;
-	if (!ioq) {
+/** Pop a file to visit from the queue. */
+static bool bftw_pop_file(struct bftw_state *state) {
+	bfs_assert(!state->file);
+	return (state->file = SLIST_POP(&state->files));
+}
+
+/** 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;
+	if (dstresize(&state->path, pathlen) != 0) {
+		state->error = errno;
 		return -1;
 	}
 
-	if (ioq_capacity(ioq) > 0) {
-		return 0;
+	// Try to find a common ancestor with the existing path
+	const struct bftw_file *ancestor = state->previous;
+	while (ancestor && ancestor->depth > file->depth) {
+		ancestor = ancestor->parent;
 	}
 
-	// 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;
-	if (bftw_ioq_pop(state, block) < 0) {
-		return -1;
+	// Build the path backwards
+	while (file && file != ancestor) {
+		if (file->nameoff > 0) {
+			state->path[file->nameoff - 1] = '/';
+		}
+		memcpy(state->path + file->nameoff, file->name, file->namelen);
+
+		if (ancestor && ancestor->depth == file->depth) {
+			ancestor = ancestor->parent;
+		}
+		file = file->parent;
+	}
+
+	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;
 }
 
-/** Try to reserve space in the cache. */
-static int bftw_cache_reserve(struct bftw_state *state) {
+/** Open a bftw_file as a directory. */
+static struct bfs_dir *bftw_file_opendir(struct bftw_state *state, struct bftw_file *file, const char *path) {
+	int fd = bftw_file_open(state, file, path);
+	if (fd < 0) {
+		return NULL;
+	}
+
 	struct bftw_cache *cache = &state->cache;
-	if (cache->capacity > 0) {
-		return 0;
+	struct bfs_dir *dir = bftw_allocdir(cache);
+	if (!dir) {
+		return NULL;
 	}
 
-	while (bftw_ioq_pop(state, false) >= 0) {
-		if (cache->capacity > 0) {
-			return 0;
-		}
+	if (bfs_opendir(dir, fd, NULL) != 0) {
+		bftw_freedir(cache, dir);
+		return NULL;
 	}
 
-	return bftw_cache_pop(cache);
+	bftw_file_set_dir(cache, file, dir);
+	return dir;
 }
 
-/** 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);
-
-	struct bftw_cache *cache = &state->cache;
+/** Open the current directory. */
+static int bftw_opendir(struct bftw_state *state) {
+	bfs_assert(!state->dir);
+	bfs_assert(!state->de);
 
-	if (bftw_ioq_reserve(state) != 0) {
-		goto append;
-	}
+	state->direrror = 0;
 
-	int dfd = AT_FDCWD;
-	if (file->parent) {
-		dfd = file->parent->fd;
-		if (dfd < 0) {
-			goto append;
+	struct bftw_file *file = state->file;
+	if (file->dir) {
+		state->dir = file->dir;
+	} else {
+		if (bftw_build_path(state, NULL) != 0) {
+			return -1;
 		}
-		bftw_cache_pin(cache, file->parent);
+		state->dir = bftw_file_opendir(state, file, state->path);
 	}
 
-	if (bftw_cache_reserve(state) != 0) {
-		goto unpin;
+	if (state->dir) {
+		bftw_cache_pin(&state->cache, file);
+	} else {
+		state->direrror = errno;
 	}
 
-	struct bfs_dir *dir = bftw_allocdir(cache);
-	if (!dir) {
-		goto unpin;
-	}
+	return 0;
+}
 
-	if (ioq_opendir(state->ioq, dir, dfd, file->name, file) != 0) {
-		goto free;
+/** Read an entry from the current directory. */
+static int bftw_readdir(struct bftw_state *state) {
+	if (!state->dir) {
+		return -1;
 	}
 
-	file->ioqueued = true;
-	--cache->capacity;
-
-	if (state->flags & BFTW_SORT) {
-		// When sorting, dirs are always kept in order in state->dirs,
-		// and we wait for the ioq to open them before popping
-		goto append;
+	int ret = bfs_readdir(state->dir, &state->de_storage);
+	if (ret > 0) {
+		state->de = &state->de_storage;
+	} else if (ret == 0) {
+		state->de = NULL;
 	} else {
-		// When not sorting, dirs are not added to state->dirs until
-		// popped from the ioq
-		return;
+		state->de = NULL;
+		state->direrror = errno;
 	}
 
-free:
-	bftw_freedir(cache, dir);
-unpin:
-	if (file->parent) {
-		bftw_cache_unpin(cache, file->parent);
-	}
-append:
-	SLIST_APPEND(&state->dirs, file);
+	return ret;
 }
 
-/** Close a directory, asynchronously if possible. */
-static int bftw_ioq_closedir(struct bftw_state *state, struct bfs_dir *dir) {
-	if (bftw_ioq_reserve(state) == 0) {
-		if (ioq_closedir(state->ioq, dir, NULL) == 0) {
-			return 0;
-		}
+/** 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;
 	}
 
-	struct bftw_cache *cache = &state->cache;
-	int ret = bfs_closedir(dir);
-	bftw_freedir(cache, dir);
-	++cache->capacity;
-	return ret;
-}
+	const struct BFTW *ftwbuf = &state->ftwbuf;
+	if (ftwbuf->type == BFS_UNKNOWN) {
+		return true;
+	}
 
-/** Close a file descriptor, asynchronously if possible. */
-static int bftw_ioq_close(struct bftw_state *state, int fd) {
-	if (bftw_ioq_reserve(state) == 0) {
-		if (ioq_close(state->ioq, fd, NULL) == 0) {
-			return 0;
+	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
 	}
 
-	struct bftw_cache *cache = &state->cache;
-	int ret = xclose(fd);
-	++cache->capacity;
-	return ret;
+	return false;
 }
 
-/** Close a file, asynchronously if possible. */
-static int bftw_close(struct bftw_state *state, struct bftw_file *file) {
-	bfs_assert(file->fd >= 0);
-	bfs_assert(file->pincount == 0);
+/** Initialize bftw_stat cache. */
+static void bftw_stat_init(struct bftw_stat *cache) {
+	cache->buf = NULL;
+	cache->error = 0;
+}
 
-	struct bfs_dir *dir = file->dir;
-	int fd = file->fd;
+/** 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;
 
-	bftw_lru_remove(&state->cache, file);
-	file->dir = NULL;
-	file->fd = -1;
+	if (ret < 0) {
+		char *copy = strndup(path, file->nameoff + file->namelen);
+		if (!copy) {
+			return -1;
+		}
 
-	if (dir) {
-		return bftw_ioq_closedir(state, dir);
-	} else {
-		return bftw_ioq_close(state, fd);
+		ret = bftw_file_open(state, file, copy);
+		free(copy);
 	}
+
+	return ret;
 }
 
-/** Free an open directory. */
-static int bftw_unwrapdir(struct bftw_state *state, struct bftw_file *file) {
-	struct bfs_dir *dir = file->dir;
-	if (!dir) {
-		return 0;
+/** Initialize the buffers with data about the current path. */
+static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) {
+	struct bftw_file *file = state->file;
+	const struct bfs_dirent *de = state->de;
+
+	struct BFTW *ftwbuf = &state->ftwbuf;
+	ftwbuf->path = state->path;
+	ftwbuf->root = file ? file->root->name : ftwbuf->path;
+	ftwbuf->depth = 0;
+	ftwbuf->visit = visit;
+	ftwbuf->type = BFS_UNKNOWN;
+	ftwbuf->error = state->direrror;
+	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);
+
+	struct bftw_file *parent = NULL;
+	if (de) {
+		parent = file;
+		ftwbuf->depth = file->depth + 1;
+		ftwbuf->type = de->type;
+		ftwbuf->nameoff = bftw_child_nameoff(file);
+	} else if (file) {
+		parent = file->parent;
+		ftwbuf->depth = file->depth;
+		ftwbuf->type = file->type;
+		ftwbuf->nameoff = file->nameoff;
 	}
 
-	struct bftw_cache *cache = &state->cache;
-
-	// Try to keep an open fd if any children exist
-	bool reffed = file->refcount > 1;
-	// Keep the fd the same if it's pinned
-	bool pinned = file->pincount > 0;
-
-#if BFS_USE_UNWRAPDIR
-	if (reffed || pinned) {
-		bfs_unwrapdir(dir);
-		bftw_freedir(cache, dir);
-		file->dir = NULL;
-		return 0;
-	}
-#else
-	if (pinned) {
-		return -1;
+	if (parent) {
+		// Try to ensure the immediate parent is open, to avoid ENAMETOOLONG
+		if (bftw_ensure_open(state, parent, state->path) >= 0) {
+			ftwbuf->at_fd = parent->fd;
+			ftwbuf->at_path += ftwbuf->nameoff;
+		} else {
+			ftwbuf->error = errno;
+		}
 	}
-#endif
 
-	if (!reffed) {
-		return bftw_close(state, file);
+	if (ftwbuf->depth == 0) {
+		// Compute the name offset for root paths like "foo/bar"
+		ftwbuf->nameoff = xbaseoff(ftwbuf->path);
 	}
 
-	if (bftw_cache_reserve(state) != 0) {
-		return -1;
+	if (ftwbuf->error != 0) {
+		ftwbuf->type = BFS_ERROR;
+		return;
 	}
 
-	int fd = dup_cloexec(file->fd);
-	if (fd < 0) {
-		return -1;
+	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;
 	}
-	--cache->capacity;
-
-	file->dir = NULL;
-	file->fd = fd;
-	return bftw_ioq_closedir(state, dir);
-}
-
-/** Pop a directory to read from the queue. */
-static bool bftw_pop_dir(struct bftw_state *state) {
-	bfs_assert(!state->file);
-
-	struct bftw_file *dir = state->dirs.head;
-	bool have_files = state->files.head;
 
-	if (state->flags & BFTW_SORT) {
-		// Keep strict breadth-first order when sorting
-		if (state->strategy != BFTW_DFS && have_files) {
-			return false;
+	const struct bfs_stat *statbuf = NULL;
+	if (bftw_need_stat(state)) {
+		statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+		if (statbuf) {
+			ftwbuf->type = bfs_mode_to_type(statbuf->mode);
+		} else {
+			ftwbuf->type = BFS_ERROR;
+			ftwbuf->error = errno;
+			return;
 		}
-	} else {
-		while (!dir || !dir->dir) {
-			// Block if we have no other files/dirs to visit, or no room in the cache
-			bool have_room = state->cache.capacity > 0;
-			bool block = !(dir || have_files) || !have_room;
+	}
 
-			if (bftw_ioq_pop(state, block) < 0) {
-				break;
+	if (ftwbuf->type == BFS_DIR && (state->flags & BFTW_DETECT_CYCLES)) {
+		for (const struct bftw_file *ancestor = parent; ancestor; ancestor = ancestor->parent) {
+			if (ancestor->dev == statbuf->dev && ancestor->ino == statbuf->ino) {
+				ftwbuf->type = BFS_ERROR;
+				ftwbuf->error = ELOOP;
+				return;
 			}
-			dir = state->dirs.head;
 		}
 	}
+}
 
-	if (!dir) {
+/** Check if the current file is a mount point. */
+static bool bftw_is_mount(struct bftw_state *state, const char *name) {
+	const struct bftw_file *file = state->file;
+	if (!file) {
 		return false;
 	}
 
-	SLIST_POP(&state->dirs);
-	state->file = dir;
-
-	while (dir->ioqueued) {
-		bftw_ioq_pop(state, true);
+	const struct bftw_file *parent = name ? file : file->parent;
+	if (!parent) {
+		return false;
 	}
 
-	return true;
-}
-
-/** Pop a file to visit from the queue. */
-static bool bftw_pop_file(struct bftw_state *state) {
-	bfs_assert(!state->file);
-	return (state->file = SLIST_POP(&state->files));
+	const struct BFTW *ftwbuf = &state->ftwbuf;
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	return statbuf && statbuf->dev != parent->dev;
 }
 
-/**
- * Open the current directory.
- */
-static int bftw_opendir(struct bftw_state *state) {
-	bfs_assert(!state->dir);
-	bfs_assert(!state->de);
-
-	state->direrror = 0;
-
-	struct bftw_file *file = state->file;
-	if (file->dir) {
-		state->dir = file->dir;
-	} else {
-		if (bftw_build_path(state, NULL) != 0) {
-			return -1;
-		}
-		state->dir = bftw_file_opendir(&state->cache, file, state->path);
+/** 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)) {
+		return BFTW_PRUNE;
 	}
 
-	if (state->dir) {
-		bftw_cache_pin(&state->cache, file);
-	} else {
-		state->direrror = errno;
+	if (bftw_build_path(state, name) != 0) {
+		return BFTW_STOP;
 	}
 
-	return 0;
-}
+	const struct BFTW *ftwbuf = &state->ftwbuf;
+	bftw_init_ftwbuf(state, visit);
 
-/**
- * Read an entry from the current directory.
- */
-static int bftw_readdir(struct bftw_state *state) {
-	if (!state->dir) {
-		return -1;
+	// Never give the callback BFS_ERROR unless BFTW_RECOVER is specified
+	if (ftwbuf->type == BFS_ERROR && !(state->flags & BFTW_RECOVER)) {
+		state->error = ftwbuf->error;
+		return BFTW_STOP;
 	}
 
-	int ret = bfs_readdir(state->dir, &state->de_storage);
-	if (ret > 0) {
-		state->de = &state->de_storage;
-	} else if (ret == 0) {
-		state->de = NULL;
-	} else {
-		state->de = NULL;
-		state->direrror = errno;
+	if ((state->flags & BFTW_SKIP_MOUNTS) && bftw_is_mount(state, name)) {
+		return BFTW_PRUNE;
 	}
 
-	return ret;
+	enum bftw_action 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;
+		}
+		fallthru;
+	case BFTW_PRUNE:
+	case BFTW_STOP:
+		return ret;
+
+	default:
+		state->error = EINVAL;
+		return BFTW_STOP;
+	}
 }
 
 /**
@@ -1230,9 +1173,7 @@ enum bftw_gc_flags {
 	BFTW_VISIT_ALL = BFTW_VISIT_ERROR | BFTW_VISIT_FILE | BFTW_VISIT_PARENTS,
 };
 
-/**
- * Garbage collect the current file and its parents.
- */
+/** Garbage collect the current file and its parents. */
 static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) {
 	int ret = 0;
 
@@ -1286,35 +1227,6 @@ static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) {
 	return ret;
 }
 
-/**
- * Dispose of the bftw() state.
- *
- * @return
- *         The bftw() return value.
- */
-static int bftw_state_destroy(struct bftw_state *state) {
-	dstrfree(state->path);
-
-	struct ioq *ioq = state->ioq;
-	if (ioq) {
-		ioq_cancel(ioq);
-		while (bftw_ioq_pop(state, true) >= 0);
-		state->ioq = NULL;
-	}
-
-	SLIST_EXTEND(&state->files, &state->batch);
-	do {
-		bftw_gc(state, BFTW_VISIT_NONE);
-	} while (bftw_pop_dir(state) || bftw_pop_file(state));
-
-	ioq_destroy(ioq);
-
-	bftw_cache_destroy(&state->cache);
-
-	errno = state->error;
-	return state->error ? -1 : 0;
-}
-
 /** Sort a bftw_list by filename. */
 static void bftw_list_sort(struct bftw_list *list) {
 	if (!list->head || !list->head->next) {
@@ -1436,6 +1348,35 @@ static int bftw_visit(struct bftw_state *state, const char *name) {
 	}
 }
 
+/**
+ * Dispose of the bftw() state.
+ *
+ * @return
+ *         The bftw() return value.
+ */
+static int bftw_state_destroy(struct bftw_state *state) {
+	dstrfree(state->path);
+
+	struct ioq *ioq = state->ioq;
+	if (ioq) {
+		ioq_cancel(ioq);
+		while (bftw_ioq_pop(state, true) >= 0);
+		state->ioq = NULL;
+	}
+
+	SLIST_EXTEND(&state->files, &state->batch);
+	do {
+		bftw_gc(state, BFTW_VISIT_NONE);
+	} while (bftw_pop_dir(state) || bftw_pop_file(state));
+
+	ioq_destroy(ioq);
+
+	bftw_cache_destroy(&state->cache);
+
+	errno = state->error;
+	return state->error ? -1 : 0;
+}
+
 /**
  * bftw() implementation for simple breadth-/depth-first search.
  */
-- 
cgit v1.2.3