Source / Include Folder (#88)

Moved Source Files Into `src` Folder

1 files changed, 1494 insertions, 0 deletions

diff --git a/src/bftw.c b/src/bftw.c
new file mode 100644
index 0000000..6f97bf6
--- /dev/null
+++ b/src/bftw.c
@@ -0,0 +1,1494 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2015-2022 Tavian Barnes <tavianator@tavianator.com>        *
+ *                                                                          *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted.                           *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
+ ****************************************************************************/
+
+/**
+ * The bftw() implementation consists of the following components:
+ *
+ * - struct bftw_file: A file that has been encountered during the traversal.
+ *   They have reference-counted links to their parents in the directory tree.
+ *
+ * - 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.
+ *
+ * - struct bftw_queue: The queue of bftw_file's left to explore.  Implemented
+ *   as a simple circular buffer.
+ *
+ * - struct bftw_state: Represents the current state of the traversal, allowing
+ *   various helper functions to take fewer parameters.
+ */
+
+#include "bftw.h"
+#include "dir.h"
+#include "darray.h"
+#include "dstring.h"
+#include "mtab.h"
+#include "stat.h"
+#include "trie.h"
+#include "util.h"
+#include <assert.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+/**
+ * A file.
+ */
+struct bftw_file {
+	/** The parent directory, if any. */
+	struct bftw_file *parent;
+	/** The root under which this file was found. */
+	struct bftw_file *root;
+	/** The next file in the queue, if any. */
+	struct bftw_file *next;
+
+	/** The previous file in the LRU list. */
+	struct bftw_file *lru_prev;
+	/** The next file in the LRU list. */
+	struct bftw_file *lru_next;
+
+	/** This file's depth in the walk. */
+	size_t depth;
+	/** Reference count. */
+	size_t refcount;
+
+	/** An open descriptor to this file, or -1. */
+	int fd;
+
+	/** This file's type, if known. */
+	enum bfs_type type;
+	/** The device number, for cycle detection. */
+	dev_t dev;
+	/** The inode number, for cycle detection. */
+	ino_t ino;
+
+	/** The offset of this file in the full path. */
+	size_t nameoff;
+	/** The length of the file's name. */
+	size_t namelen;
+	/** The file's name. */
+	char name[];
+};
+
+/**
+ * A cache of open directories.
+ */
+struct bftw_cache {
+	/** The head of the LRU list. */
+	struct bftw_file *head;
+	/** The insertion target for the LRU list. */
+	struct bftw_file *target;
+	/** The tail of the LRU list. */
+	struct bftw_file *tail;
+	/** The remaining capacity of the LRU list. */
+	size_t capacity;
+};
+
+/** Initialize a cache. */
+static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
+	cache->head = NULL;
+	cache->target = NULL;
+	cache->tail = NULL;
+	cache->capacity = capacity;
+}
+
+/** Destroy a cache. */
+static void bftw_cache_destroy(struct bftw_cache *cache) {
+	assert(!cache->tail);
+	assert(!cache->target);
+	assert(!cache->head);
+}
+
+/** Add a bftw_file to the cache. */
+static void bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) {
+	assert(cache->capacity > 0);
+	assert(file->fd >= 0);
+	assert(!file->lru_prev);
+	assert(!file->lru_next);
+
+	if (cache->target) {
+		file->lru_prev = cache->target;
+		file->lru_next = cache->target->lru_next;
+	} else {
+		file->lru_next = cache->head;
+	}
+
+	if (file->lru_prev) {
+		file->lru_prev->lru_next = file;
+	} else {
+		cache->head = file;
+	}
+
+	if (file->lru_next) {
+		file->lru_next->lru_prev = file;
+	} else {
+		cache->tail = file;
+	}
+
+	// Prefer to keep the root paths open by keeping them at the head of the list
+	if (file->depth == 0) {
+		cache->target = file;
+	}
+
+	--cache->capacity;
+}
+
+/** Remove a bftw_file from the cache. */
+static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) {
+	if (cache->target == file) {
+		cache->target = file->lru_prev;
+	}
+
+	if (file->lru_prev) {
+		assert(cache->head != file);
+		file->lru_prev->lru_next = file->lru_next;
+	} else {
+		assert(cache->head == file);
+		cache->head = file->lru_next;
+	}
+
+	if (file->lru_next) {
+		assert(cache->tail != file);
+		file->lru_next->lru_prev = file->lru_prev;
+	} else {
+		assert(cache->tail == file);
+		cache->tail = file->lru_prev;
+	}
+
+	file->lru_prev = NULL;
+	file->lru_next = NULL;
+	++cache->capacity;
+}
+
+/** Mark a cache entry as recently used. */
+static void bftw_cache_use(struct bftw_cache *cache, struct bftw_file *file) {
+	bftw_cache_remove(cache, file);
+	bftw_cache_add(cache, file);
+}
+
+/** Close a bftw_file. */
+static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) {
+	assert(file->fd >= 0);
+
+	bftw_cache_remove(cache, file);
+
+	xclose(file->fd);
+	file->fd = -1;
+}
+
+/** Pop a directory from the cache. */
+static void bftw_cache_pop(struct bftw_cache *cache) {
+	assert(cache->tail);
+	bftw_file_close(cache, cache->tail);
+}
+
+/**
+ * Shrink the cache, to recover from EMFILE.
+ *
+ * @param cache
+ *         The cache in question.
+ * @param saved
+ *         A bftw_file that must be preserved.
+ * @return
+ *         0 if successfully shrunk, otherwise -1.
+ */
+static int bftw_cache_shrink(struct bftw_cache *cache, const struct bftw_file *saved) {
+	struct bftw_file *file = cache->tail;
+	if (!file) {
+		return -1;
+	}
+
+	if (file == saved) {
+		file = file->lru_prev;
+		if (!file) {
+			return -1;
+		}
+	}
+
+	bftw_file_close(cache, file);
+	cache->capacity = 0;
+	return 0;
+}
+
+/** Compute the name offset of a child path. */
+static size_t bftw_child_nameoff(const struct bftw_file *parent) {
+	size_t ret = parent->nameoff + parent->namelen;
+	if (parent->name[parent->namelen - 1] != '/') {
+		++ret;
+	}
+	return ret;
+}
+
+/** Create a new bftw_file. */
+static struct bftw_file *bftw_file_new(struct bftw_file *parent, const char *name) {
+	size_t namelen = strlen(name);
+	size_t size = BFS_FLEX_SIZEOF(struct bftw_file, name, namelen + 1);
+
+	struct bftw_file *file = malloc(size);
+	if (!file) {
+		return NULL;
+	}
+
+	file->parent = parent;
+
+	if (parent) {
+		file->root = parent->root;
+		file->depth = parent->depth + 1;
+		file->nameoff = bftw_child_nameoff(parent);
+		++parent->refcount;
+	} else {
+		file->root = file;
+		file->depth = 0;
+		file->nameoff = 0;
+	}
+
+	file->next = NULL;
+
+	file->lru_prev = NULL;
+	file->lru_next = NULL;
+
+	file->refcount = 1;
+	file->fd = -1;
+
+	file->type = BFS_UNKNOWN;
+	file->dev = -1;
+	file->ino = -1;
+
+	file->namelen = namelen;
+	memcpy(file->name, name, namelen + 1);
+
+	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) {
+	assert(file->fd < 0);
+
+	int at_fd = AT_FDCWD;
+	if (base) {
+		bftw_cache_use(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_shrink(cache, base) == 0) {
+			fd = openat(at_fd, at_path, flags);
+		}
+	}
+
+	if (fd >= 0) {
+		if (cache->capacity == 0) {
+			bftw_cache_pop(cache);
+		}
+
+		file->fd = fd;
+		bftw_cache_add(cache, file);
+	}
+
+	return 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
+
+	// Use the ->next linked list to temporarily hold the reversed parent
+	// chain between base and file
+	struct bftw_file *cur;
+	for (cur = file; cur->parent != base; cur = cur->parent) {
+		cur->parent->next = cur;
+	}
+
+	// Open the files in the chain one by one
+	for (base = cur; base; base = base->next) {
+		fd = bftw_file_openat(cache, base, base->parent, base->name);
+		if (fd < 0 || base == file) {
+			break;
+		}
+	}
+
+	// Clear out the linked list
+	for (struct bftw_file *next = cur->next; cur != file; cur = next, next = next->next) {
+		cur->next = NULL;
+	}
+
+	return fd;
+}
+
+/**
+ * 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;
+	}
+
+	return bfs_opendir(fd, NULL);
+}
+
+/** Free a bftw_file. */
+static void bftw_file_free(struct bftw_cache *cache, struct bftw_file *file) {
+	assert(file->refcount == 0);
+
+	if (file->fd >= 0) {
+		bftw_file_close(cache, file);
+	}
+
+	free(file);
+}
+
+/**
+ * A queue of bftw_file's to examine.
+ */
+struct bftw_queue {
+	/** The head of the queue. */
+	struct bftw_file *head;
+	/** The insertion target. */
+	struct bftw_file **target;
+};
+
+/** Initialize a bftw_queue. */
+static void bftw_queue_init(struct bftw_queue *queue) {
+	queue->head = NULL;
+	queue->target = &queue->head;
+}
+
+/** Add a file to a bftw_queue. */
+static void bftw_queue_push(struct bftw_queue *queue, struct bftw_file *file) {
+	assert(file->next == NULL);
+
+	file->next = *queue->target;
+	*queue->target = file;
+	queue->target = &file->next;
+}
+
+/** Pop the next file from the head of the queue. */
+static struct bftw_file *bftw_queue_pop(struct bftw_queue *queue) {
+	struct bftw_file *file = queue->head;
+	queue->head = file->next;
+	file->next = NULL;
+	if (queue->target == &file->next) {
+		queue->target = &queue->head;
+	}
+	return file;
+}
+
+/** The split phase of mergesort. */
+static struct bftw_file **bftw_sort_split(struct bftw_file **head, struct bftw_file **tail) {
+	struct bftw_file **tortoise = head, **hare = head;
+
+	while (*hare != *tail) {
+		tortoise = &(*tortoise)->next;
+		hare = &(*hare)->next;
+		if (*hare != *tail) {
+			hare = &(*hare)->next;
+		}
+	}
+
+	return tortoise;
+}
+
+/** The merge phase of mergesort. */
+static struct bftw_file **bftw_sort_merge(struct bftw_file **head, struct bftw_file **mid, struct bftw_file **tail) {
+	struct bftw_file *left = *head, *right = *mid, *end = *tail;
+	*mid = NULL;
+	*tail = NULL;
+
+	while (left || right) {
+		struct bftw_file *next;
+		if (left && (!right || strcoll(left->name, right->name) <= 0)) {
+			next = left;
+			left = left->next;
+		} else {
+			next = right;
+			right = right->next;
+		}
+
+		*head = next;
+		head = &next->next;
+	}
+
+	*head = end;
+	return head;
+}
+
+/**
+ * Sort a (sub-)list of files.
+ *
+ * @param head
+ *         The head of the (sub-)list to sort.
+ * @param tail
+ *         The tail of the (sub-)list to sort.
+ * @return
+ *         The new tail of the (sub-)list.
+ */
+static struct bftw_file **bftw_sort_files(struct bftw_file **head, struct bftw_file **tail) {
+	struct bftw_file **mid = bftw_sort_split(head, tail);
+	if (*mid == *head || *mid == *tail) {
+		return tail;
+	}
+
+	mid = bftw_sort_files(head, mid);
+	tail = bftw_sort_files(mid, tail);
+
+	return bftw_sort_merge(head, mid, tail);
+}
+
+/**
+ * Holds the current state of the bftw() traversal.
+ */
+struct bftw_state {
+	/** bftw() callback. */
+	bftw_callback *callback;
+	/** bftw() callback data. */
+	void *ptr;
+	/** bftw() flags. */
+	enum bftw_flags flags;
+	/** Search strategy. */
+	enum bftw_strategy strategy;
+	/** The mount table. */
+	const struct bfs_mtab *mtab;
+
+	/** The appropriate errno value, if any. */
+	int error;
+
+	/** The cache of open directories. */
+	struct bftw_cache cache;
+	/** The queue of directories left to explore. */
+	struct bftw_queue queue;
+	/** The start of the current batch of files. */
+	struct bftw_file **batch;
+
+	/** The current path. */
+	char *path;
+	/** The current file. */
+	struct bftw_file *file;
+	/** The previous file. */
+	struct bftw_file *previous;
+
+	/** The currently open directory. */
+	struct bfs_dir *dir;
+	/** The current directory entry. */
+	struct bfs_dirent *de;
+	/** Storage for the directory entry. */
+	struct bfs_dirent de_storage;
+	/** Any error encountered while reading the directory. */
+	int direrror;
+
+	/** Extra data about the current file. */
+	struct BFTW ftwbuf;
+};
+
+/**
+ * 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;
+	state->flags = args->flags;
+	state->strategy = args->strategy;
+	state->mtab = args->mtab;
+
+	state->error = 0;
+
+	if (args->nopenfd < 1) {
+		errno = EMFILE;
+		return -1;
+	}
+
+	state->path = dstralloc(0);
+	if (!state->path) {
+		return -1;
+	}
+
+	bftw_cache_init(&state->cache, args->nopenfd);
+	bftw_queue_init(&state->queue);
+	state->batch = NULL;
+
+	state->file = NULL;
+	state->previous = NULL;
+
+	state->dir = NULL;
+	state->de = NULL;
+	state->direrror = 0;
+
+	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;
+		}
+	}
+
+	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;
+	}
+}
+
+/**
+ * Update the path for the current file.
+ */
+static int bftw_update_path(struct bftw_state *state, const char *name) {
+	const struct bftw_file *file = state->file;
+	size_t length = file ? file->nameoff + file->namelen : 0;
+
+	assert(dstrlen(state->path) >= length);
+	dstresize(&state->path, length);
+
+	if (name) {
+		if (length > 0 && state->path[length - 1] != '/') {
+			if (dstrapp(&state->path, '/') != 0) {
+				return -1;
+			}
+		}
+		if (dstrcat(&state->path, name) != 0) {
+			return -1;
+		}
+	}
+
+	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;
+	}
+
+	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.
+ *
+ * @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;
+
+	if (ret < 0) {
+		char *copy = strndup(path, file->nameoff + file->namelen);
+		if (!copy) {
+			return -1;
+		}
+
+		ret = bftw_file_open(cache, file, copy);
+		free(copy);
+	}
+
+	return ret;
+}
+
+/**
+ * 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;
+	}
+
+	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;
+		}
+	}
+
+	if (ftwbuf->depth == 0) {
+		// Compute the name offset for root paths like "foo/bar"
+		ftwbuf->nameoff = xbasename(ftwbuf->path) - ftwbuf->path;
+	}
+
+	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)) {
+		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;
+		}
+	}
+
+	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;
+			}
+		}
+	}
+}
+
+/** 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;
+	}
+
+	const struct bftw_file *parent = name ? file : file->parent;
+	if (!parent) {
+		return false;
+	}
+
+	const struct BFTW *ftwbuf = &state->ftwbuf;
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	return statbuf && statbuf->dev != parent->dev;
+}
+
+/** Fill file identity information from an ftwbuf. */
+static void bftw_fill_id(struct bftw_file *file, const struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = ftwbuf->stat_cache.buf;
+	if (!statbuf || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
+		statbuf = ftwbuf->lstat_cache.buf;
+	}
+	if (statbuf) {
+		file->dev = statbuf->dev;
+		file->ino = statbuf->ino;
+	}
+}
+
+/**
+ * Visit a path, invoking the callback.
+ */
+static enum bftw_action bftw_visit(struct bftw_state *state, const char *name, enum bftw_visit visit) {
+	if (bftw_update_path(state, name) != 0) {
+		state->error = errno;
+		return BFTW_STOP;
+	}
+
+	const struct BFTW *ftwbuf = &state->ftwbuf;
+	bftw_init_ftwbuf(state, visit);
+
+	// 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 ((state->flags & BFTW_SKIP_MOUNTS) && bftw_is_mount(state, name)) {
+		return BFTW_PRUNE;
+	}
+
+	enum bftw_action ret = state->callback(ftwbuf, state->ptr);
+	switch (ret) {
+	case BFTW_CONTINUE:
+		break;
+	case BFTW_PRUNE:
+	case BFTW_STOP:
+		goto done;
+	default:
+		state->error = EINVAL;
+		return BFTW_STOP;
+	}
+
+	if (visit != BFTW_PRE || ftwbuf->type != BFS_DIR) {
+		ret = BFTW_PRUNE;
+		goto done;
+	}
+
+	if ((state->flags & BFTW_PRUNE_MOUNTS) && bftw_is_mount(state, name)) {
+		ret = BFTW_PRUNE;
+		goto done;
+	}
+
+done:
+	if (state->file && !name) {
+		bftw_fill_id(state->file, ftwbuf);
+	}
+
+	return ret;
+}
+
+/**
+ * Push a new file onto the queue.
+ */
+static int bftw_push(struct bftw_state *state, const char *name, bool fill_id) {
+	struct bftw_file *parent = state->file;
+	struct bftw_file *file = bftw_file_new(parent, name);
+	if (!file) {
+		state->error = errno;
+		return -1;
+	}
+
+	if (state->de) {
+		file->type = state->de->type;
+	}
+
+	if (fill_id) {
+		bftw_fill_id(file, &state->ftwbuf);
+	}
+
+	bftw_queue_push(&state->queue, file);
+
+	return 0;
+}
+
+/**
+ * Build the path to the current file.
+ */
+static int bftw_build_path(struct bftw_state *state) {
+	const struct bftw_file *file = state->file;
+
+	size_t pathlen = file->nameoff + file->namelen;
+	if (dstresize(&state->path, pathlen) != 0) {
+		state->error = errno;
+		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;
+	}
+
+	// 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;
+	return 0;
+}
+
+/**
+ * Pop the next file from the queue.
+ */
+static int bftw_pop(struct bftw_state *state) {
+	if (!state->queue.head) {
+		return 0;
+	}
+
+	state->file = bftw_queue_pop(&state->queue);
+
+	if (bftw_build_path(state) != 0) {
+		return -1;
+	}
+
+	return 1;
+}
+
+/**
+ * Open the current directory.
+ */
+static void bftw_opendir(struct bftw_state *state) {
+	assert(!state->dir);
+	assert(!state->de);
+
+	state->direrror = 0;
+
+	state->dir = bftw_file_opendir(&state->cache, state->file, state->path);
+	if (!state->dir) {
+		state->direrror = errno;
+	}
+}
+
+/**
+ * Read an entry from the current directory.
+ */
+static int bftw_readdir(struct bftw_state *state) {
+	if (!state->dir) {
+		return -1;
+	}
+
+	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;
+	}
+
+	return ret;
+}
+
+/**
+ * Flags controlling which files get visited when done with a directory.
+ */
+enum bftw_gc_flags {
+	/** Don't visit anything. */
+	BFTW_VISIT_NONE = 0,
+	/** Visit the file itself. */
+	BFTW_VISIT_FILE = 1 << 0,
+	/** Visit the file's ancestors. */
+	BFTW_VISIT_PARENTS = 1 << 1,
+	/** Visit both the file and its ancestors. */
+	BFTW_VISIT_ALL = BFTW_VISIT_FILE | BFTW_VISIT_PARENTS,
+};
+
+/**
+ * Close the current directory.
+ */
+static enum bftw_action bftw_closedir(struct bftw_state *state, enum bftw_gc_flags flags) {
+	struct bftw_file *file = state->file;
+	enum bftw_action ret = BFTW_CONTINUE;
+
+	if (state->dir) {
+		assert(file->fd >= 0);
+
+		if (file->refcount > 1) {
+			// Keep the fd around if any subdirectories exist
+			file->fd = bfs_freedir(state->dir);
+		} else {
+			bfs_closedir(state->dir);
+			file->fd = -1;
+		}
+
+		if (file->fd < 0) {
+			bftw_cache_remove(&state->cache, file);
+		}
+	}
+
+	state->de = NULL;
+	state->dir = NULL;
+
+	if (state->direrror != 0) {
+		if (flags & BFTW_VISIT_FILE) {
+			ret = bftw_visit(state, NULL, BFTW_PRE);
+		} else {
+			state->error = state->direrror;
+		}
+		state->direrror = 0;
+	}
+
+	return ret;
+}
+
+/**
+ * Finalize and free a file we're done with.
+ */
+static enum bftw_action bftw_gc_file(struct bftw_state *state, enum bftw_gc_flags flags) {
+	enum bftw_action ret = BFTW_CONTINUE;
+
+	if (!(state->flags & BFTW_POST_ORDER)) {
+		flags = 0;
+	}
+	bool visit = flags & BFTW_VISIT_FILE;
+
+	while (state->file) {
+		struct bftw_file *file = state->file;
+		if (--file->refcount > 0) {
+			state->file = NULL;
+			break;
+		}
+
+		if (visit && bftw_visit(state, NULL, BFTW_POST) == BFTW_STOP) {
+			ret = BFTW_STOP;
+			flags &= ~BFTW_VISIT_PARENTS;
+		}
+		visit = flags & BFTW_VISIT_PARENTS;
+
+		struct bftw_file *parent = file->parent;
+		if (state->previous == file) {
+			state->previous = parent;
+		}
+		bftw_file_free(&state->cache, file);
+		state->file = parent;
+	}
+
+	return ret;
+}
+
+/**
+ * Drain all the entries from a bftw_queue.
+ */
+static void bftw_drain_queue(struct bftw_state *state, struct bftw_queue *queue) {
+	while (queue->head) {
+		state->file = bftw_queue_pop(queue);
+		bftw_gc_file(state, BFTW_VISIT_NONE);
+	}
+}
+
+/**
+ * Dispose of the bftw() state.
+ *
+ * @return
+ *         The bftw() return value.
+ */
+static int bftw_state_destroy(struct bftw_state *state) {
+	dstrfree(state->path);
+
+	bftw_closedir(state, BFTW_VISIT_NONE);
+
+	bftw_gc_file(state, BFTW_VISIT_NONE);
+	bftw_drain_queue(state, &state->queue);
+
+	bftw_cache_destroy(&state->cache);
+
+	errno = state->error;
+	return state->error ? -1 : 0;
+}
+
+/** Start a batch of files. */
+static void bftw_batch_start(struct bftw_state *state) {
+	if (state->strategy == BFTW_DFS) {
+		state->queue.target = &state->queue.head;
+	}
+	state->batch = state->queue.target;
+}
+
+/** Finish adding a batch of files. */
+static void bftw_batch_finish(struct bftw_state *state) {
+	if (state->flags & BFTW_SORT) {
+		state->queue.target = bftw_sort_files(state->batch, state->queue.target);
+	}
+}
+
+/**
+ * Streaming mode: visit files as they are encountered.
+ */
+static int bftw_stream(const struct bftw_args *args) {
+	struct bftw_state state;
+	if (bftw_state_init(&state, args) != 0) {
+		return -1;
+	}
+
+	assert(!(state.flags & (BFTW_SORT | BFTW_BUFFER)));
+
+	bftw_batch_start(&state);
+	for (size_t i = 0; i < args->npaths; ++i) {
+		const char *path = args->paths[i];
+
+		switch (bftw_visit(&state, path, BFTW_PRE)) {
+		case BFTW_CONTINUE:
+			break;
+		case BFTW_PRUNE:
+			continue;
+		case BFTW_STOP:
+			goto done;
+		}
+
+		if (bftw_push(&state, path, true) != 0) {
+			goto done;
+		}
+	}
+	bftw_batch_finish(&state);
+
+	while (bftw_pop(&state) > 0) {
+		bftw_opendir(&state);
+
+		bftw_batch_start(&state);
+		while (bftw_readdir(&state) > 0) {
+			const char *name = state.de->name;
+
+			switch (bftw_visit(&state, name, BFTW_PRE)) {
+			case BFTW_CONTINUE:
+				break;
+			case BFTW_PRUNE:
+				continue;
+			case BFTW_STOP:
+				goto done;
+			}
+
+			if (bftw_push(&state, name, true) != 0) {
+				goto done;
+			}
+		}
+		bftw_batch_finish(&state);
+
+		if (bftw_closedir(&state, BFTW_VISIT_ALL) == BFTW_STOP) {
+			goto done;
+		}
+		if (bftw_gc_file(&state, BFTW_VISIT_ALL) == BFTW_STOP) {
+			goto done;
+		}
+	}
+
+done:
+	return bftw_state_destroy(&state);
+}
+
+/**
+ * Batching mode: queue up all children before visiting them.
+ */
+static int bftw_batch(const struct bftw_args *args) {
+	struct bftw_state state;
+	if (bftw_state_init(&state, args) != 0) {
+		return -1;
+	}
+
+	bftw_batch_start(&state);
+	for (size_t i = 0; i < args->npaths; ++i) {
+		if (bftw_push(&state, args->paths[i], false) != 0) {
+			goto done;
+		}
+	}
+	bftw_batch_finish(&state);
+
+	while (bftw_pop(&state) > 0) {
+		enum bftw_gc_flags gcflags = BFTW_VISIT_ALL;
+
+		switch (bftw_visit(&state, NULL, BFTW_PRE)) {
+		case BFTW_CONTINUE:
+			break;
+		case BFTW_PRUNE:
+			gcflags &= ~BFTW_VISIT_FILE;
+			goto next;
+		case BFTW_STOP:
+			goto done;
+		}
+
+		bftw_opendir(&state);
+
+		bftw_batch_start(&state);
+		while (bftw_readdir(&state) > 0) {
+			if (bftw_push(&state, state.de->name, false) != 0) {
+				goto done;
+			}
+		}
+		bftw_batch_finish(&state);
+
+		if (bftw_closedir(&state, gcflags) == BFTW_STOP) {
+			goto done;
+		}
+
+	next:
+		if (bftw_gc_file(&state, gcflags) == BFTW_STOP) {
+			goto done;
+		}
+	}
+
+done:
+	return bftw_state_destroy(&state);
+}
+
+/** Select bftw_stream() or bftw_batch() appropriately. */
+static int bftw_auto(const struct bftw_args *args) {
+	if (args->flags & (BFTW_SORT | BFTW_BUFFER)) {
+		return bftw_batch(args);
+	} else {
+		return bftw_stream(args);
+	}
+}
+
+/**
+ * Iterative deepening search state.
+ */
+struct bftw_ids_state {
+	/** The wrapped callback. */
+	bftw_callback *delegate;
+	/** The wrapped callback arguments. */
+	void *ptr;
+	/** Which visit this search corresponds to. */
+	enum bftw_visit visit;
+	/** Whether to override the bftw_visit. */
+	bool force_visit;
+	/** The current minimum depth (inclusive). */
+	size_t min_depth;
+	/** The current maximum depth (exclusive). */
+	size_t max_depth;
+	/** The set of pruned paths. */
+	struct trie pruned;
+	/** An error code to report. */
+	int error;
+	/** Whether the bottom has been found. */
+	bool bottom;
+	/** Whether to quit the search. */
+	bool quit;
+};
+
+/** Iterative deepening callback function. */
+static enum bftw_action bftw_ids_callback(const struct BFTW *ftwbuf, void *ptr) {
+	struct bftw_ids_state *state = ptr;
+
+	if (state->force_visit) {
+		struct BFTW *mutbuf = (struct BFTW *)ftwbuf;
+		mutbuf->visit = state->visit;
+	}
+
+	if (ftwbuf->type == BFS_ERROR) {
+		if (ftwbuf->depth + 1 >= state->min_depth) {
+			return state->delegate(ftwbuf, state->ptr);
+		} else {
+			return BFTW_PRUNE;
+		}
+	}
+
+	if (ftwbuf->depth < state->min_depth) {
+		if (trie_find_str(&state->pruned, ftwbuf->path)) {
+			return BFTW_PRUNE;
+		} else {
+			return BFTW_CONTINUE;
+		}
+	} else if (state->visit == BFTW_POST) {
+		if (trie_find_str(&state->pruned, ftwbuf->path)) {
+			return BFTW_PRUNE;
+		}
+	}
+
+	enum bftw_action ret = BFTW_CONTINUE;
+	if (ftwbuf->visit == state->visit) {
+		ret = state->delegate(ftwbuf, state->ptr);
+	}
+
+	switch (ret) {
+	case BFTW_CONTINUE:
+		if (ftwbuf->type == BFS_DIR && ftwbuf->depth + 1 >= state->max_depth) {
+			state->bottom = false;
+			ret = BFTW_PRUNE;
+		}
+		break;
+	case BFTW_PRUNE:
+		if (ftwbuf->type == BFS_DIR) {
+			if (!trie_insert_str(&state->pruned, ftwbuf->path)) {
+				state->error = errno;
+				state->quit = true;
+				ret = BFTW_STOP;
+			}
+		}
+		break;
+	case BFTW_STOP:
+		state->quit = true;
+		break;
+	}
+
+	return ret;
+}
+
+/** Initialize iterative deepening state. */
+static void bftw_ids_init(const struct bftw_args *args, struct bftw_ids_state *state, struct bftw_args *ids_args) {
+	state->delegate = args->callback;
+	state->ptr = args->ptr;
+	state->visit = BFTW_PRE;
+	state->force_visit = false;
+	state->min_depth = 0;
+	state->max_depth = 1;
+	trie_init(&state->pruned);
+	state->error = 0;
+	state->bottom = false;
+	state->quit = false;
+
+	*ids_args = *args;
+	ids_args->callback = bftw_ids_callback;
+	ids_args->ptr = state;
+	ids_args->flags &= ~BFTW_POST_ORDER;
+	ids_args->strategy = BFTW_DFS;
+}
+
+/** Finish an iterative deepening search. */
+static int bftw_ids_finish(struct bftw_ids_state *state) {
+	int ret = 0;
+
+	if (state->error) {
+		ret = -1;
+	} else {
+		state->error = errno;
+	}
+
+	trie_destroy(&state->pruned);
+
+	errno = state->error;
+	return ret;
+}
+
+/**
+ * Iterative deepening bftw() wrapper.
+ */
+static int bftw_ids(const struct bftw_args *args) {
+	struct bftw_ids_state state;
+	struct bftw_args ids_args;
+	bftw_ids_init(args, &state, &ids_args);
+
+	while (!state.quit && !state.bottom) {
+		state.bottom = true;
+
+		if (bftw_auto(&ids_args) != 0) {
+			state.error = errno;
+			state.quit = true;
+		}
+
+		++state.min_depth;
+		++state.max_depth;
+	}
+
+	if (args->flags & BFTW_POST_ORDER) {
+		state.visit = BFTW_POST;
+		state.force_visit = true;
+
+		while (!state.quit && state.min_depth > 0) {
+			--state.max_depth;
+			--state.min_depth;
+
+			if (bftw_auto(&ids_args) != 0) {
+				state.error = errno;
+				state.quit = true;
+			}
+		}
+	}
+
+	return bftw_ids_finish(&state);
+}
+
+/**
+ * Exponential deepening bftw() wrapper.
+ */
+static int bftw_eds(const struct bftw_args *args) {
+	struct bftw_ids_state state;
+	struct bftw_args ids_args;
+	bftw_ids_init(args, &state, &ids_args);
+
+	while (!state.quit && !state.bottom) {
+		state.bottom = true;
+
+		if (bftw_auto(&ids_args) != 0) {
+			state.error = errno;
+			state.quit = true;
+		}
+
+		state.min_depth = state.max_depth;
+		state.max_depth *= 2;
+	}
+
+	if (!state.quit && (args->flags & BFTW_POST_ORDER)) {
+		state.visit = BFTW_POST;
+		state.min_depth = 0;
+		ids_args.flags |= BFTW_POST_ORDER;
+
+		if (bftw_auto(&ids_args) != 0) {
+			state.error = errno;
+		}
+	}
+
+	return bftw_ids_finish(&state);
+}
+
+int bftw(const struct bftw_args *args) {
+	switch (args->strategy) {
+	case BFTW_BFS:
+		return bftw_auto(args);
+	case BFTW_DFS:
+		return bftw_batch(args);
+	case BFTW_IDS:
+		return bftw_ids(args);
+	case BFTW_EDS:
+		return bftw_eds(args);
+	}
+
+	errno = EINVAL;
+	return -1;
+}