From e8df57b5a49a70e2daa5bb6c00b8e0e06c51306a Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Thu, 6 Apr 2023 14:55:25 -0400
Subject: ioq: Implement an async I/O queue

---
 src/ioq.h | 94 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)
 create mode 100644 src/ioq.h

(limited to 'src/ioq.h')

diff --git a/src/ioq.h b/src/ioq.h
new file mode 100644
index 0000000..9492034
--- /dev/null
+++ b/src/ioq.h
@@ -0,0 +1,94 @@
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+
+/**
+ * Asynchronous I/O queues.
+ */
+
+#ifndef BFS_IOQ_H
+#define BFS_IOQ_H
+
+#include <stddef.h>
+
+/**
+ * An queue of asynchronous I/O operations.
+ */
+struct ioq;
+
+/**
+ * An I/O queue response.
+ */
+struct ioq_res {
+	/** The opened directory. */
+	struct bfs_dir *dir;
+	/** The error code, if the operation failed. */
+	int error;
+
+	/** Arbitrary user data. */
+	void *ptr;
+};
+
+/**
+ * Create an I/O queue.
+ *
+ * @param depth
+ *         The maximum depth of the queue.
+ * @param threads
+ *         The maximum number of background threads.
+ * @return
+ *         The new I/O queue, or NULL on failure.
+ */
+struct ioq *ioq_create(size_t depth, size_t threads);
+
+/**
+ * Asynchronous bfs_opendir().
+ *
+ * @param ioq
+ *         The I/O queue.
+ * @param dfd
+ *         The base file descriptor.
+ * @param path
+ *         The path to open, relative to dfd.
+ * @param ptr
+ *         An arbitrary pointer to associate with the request.
+ * @return
+ *         0 on success, or -1 on failure.
+ */
+int ioq_opendir(struct ioq *ioq, int dfd, const char *path, void *ptr);
+
+/**
+ * Pop a response from the queue.
+ *
+ * @param ioq
+ *         The I/O queue.
+ * @return
+ *         The next response, or NULL.
+ */
+struct ioq_res *ioq_pop(struct ioq *ioq);
+
+/**
+ * Pop a response from the queue, without blocking.
+ *
+ * @param ioq
+ *         The I/O queue.
+ * @return
+ *         The next response, or NULL.
+ */
+struct ioq_res *ioq_trypop(struct ioq *ioq);
+
+/**
+ * Free a response.
+ *
+ * @param ioq
+ *         The I/O queue.
+ * @param res
+ *         The response to free.
+ */
+void ioq_free(struct ioq *ioq, struct ioq_res *res);
+
+/**
+ * Stop and destroy an I/O queue.
+ */
+void ioq_destroy(struct ioq *ioq);
+
+#endif // BFS_IOQ_H
-- 
cgit v1.2.3


From 90ded13e589b0089167ef25ca3d26be599dfec9b Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 19 Jun 2023 12:11:36 -0400
Subject: alloc: New header for memory allocation utilities

---
 Makefile      |   3 +-
 src/alloc.c   |  50 ++++++++++++++++++++
 src/alloc.h   | 149 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/bfstd.c   |  13 -----
 src/bfstd.h   |  12 -----
 src/bftw.c    |   5 +-
 src/color.c   |   5 +-
 src/config.h  |  50 --------------------
 src/ctx.c     |  31 ++----------
 src/dstring.c |   3 +-
 src/exec.c    |  26 ++++------
 src/ioq.c     |  26 ++++------
 src/ioq.h     |   4 +-
 src/main.c    |   1 +
 src/mtab.c    |   5 +-
 src/parse.c   |  28 ++---------
 src/pwcache.c |   5 +-
 src/trie.c    |   7 ++-
 src/xregex.c  |   3 +-
 src/xspawn.c  |   3 +-
 tests/alloc.c |  24 ++++++++++
 tests/bfstd.c |  13 +----
 22 files changed, 271 insertions(+), 195 deletions(-)
 create mode 100644 src/alloc.c
 create mode 100644 src/alloc.h
 create mode 100644 tests/alloc.c

(limited to 'src/ioq.h')

diff --git a/Makefile b/Makefile
index fb28e29..d38f581 100644
--- a/Makefile
+++ b/Makefile
@@ -217,6 +217,7 @@ $(OBJ)/FLAGS: $(OBJ)/FLAGS.new
 
 # All object files except the entry point
 LIBBFS := \
+    $(OBJ)/src/alloc.o \
     $(OBJ)/src/bar.o \
     $(OBJ)/src/bfstd.o \
     $(OBJ)/src/bftw.o \
@@ -246,7 +247,7 @@ LIBBFS := \
 $(BIN)/bfs: $(OBJ)/src/main.o $(LIBBFS)
 
 # Standalone unit tests
-UNITS := bfstd bit trie xtimegm
+UNITS := alloc bfstd bit trie xtimegm
 UNIT_TESTS := $(UNITS:%=$(BIN)/tests/%)
 UNIT_CHECKS := $(UNITS:%=check-%)
 
diff --git a/src/alloc.c b/src/alloc.c
new file mode 100644
index 0000000..0003108
--- /dev/null
+++ b/src/alloc.c
@@ -0,0 +1,50 @@
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+
+#include "alloc.h"
+#include "bit.h"
+#include "diag.h"
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+/** Portable aligned_alloc()/posix_memalign(). */
+static void *xmemalign(size_t align, size_t size) {
+	bfs_assert(has_single_bit(align));
+	bfs_assert(align >= sizeof(void *));
+	bfs_assert((size & (align - 1)) == 0);
+
+#if __APPLE__
+	void *ptr = NULL;
+	errno = posix_memalign(&ptr, align, size);
+	return ptr;
+#else
+	return aligned_alloc(align, size);
+#endif
+}
+
+void *alloc(size_t align, size_t size) {
+	bfs_assert(has_single_bit(align));
+	bfs_assert((size & (align - 1)) == 0);
+
+	if (align <= alignof(max_align_t)) {
+		return malloc(size);
+	} else {
+		return xmemalign(align, size);
+	}
+}
+
+void *zalloc(size_t align, size_t size) {
+	bfs_assert(has_single_bit(align));
+	bfs_assert((size & (align - 1)) == 0);
+
+	if (align <= alignof(max_align_t)) {
+		return calloc(1, size);
+	}
+
+	void *ret = xmemalign(align, size);
+	if (ret) {
+		memset(ret, 0, size);
+	}
+	return ret;
+}
diff --git a/src/alloc.h b/src/alloc.h
new file mode 100644
index 0000000..899a4ec
--- /dev/null
+++ b/src/alloc.h
@@ -0,0 +1,149 @@
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+
+/**
+ * Memory allocation.
+ */
+
+#ifndef BFS_ALLOC_H
+#define BFS_ALLOC_H
+
+#include "config.h"
+#include <stddef.h>
+
+/** Round down to a multiple of an alignment. */
+static inline size_t align_floor(size_t align, size_t size) {
+	return size & ~(align - 1);
+}
+
+/** Round up to a multiple of an alignment. */
+static inline size_t align_ceil(size_t align, size_t size) {
+	return align_floor(align, size + align - 1);
+}
+
+/**
+ * Saturating array size.
+ *
+ * @param align
+ *         Array element alignment.
+ * @param size
+ *         Array element size.
+ * @param count
+ *         Array element count.
+ * @return
+ *         size * count, saturating to the maximum aligned value on overflow.
+ */
+static inline size_t array_size(size_t align, size_t size, size_t count) {
+	size_t ret = size * count;
+	return ret / size == count ? ret : ~(align - 1);
+}
+
+/** Saturating array sizeof. */
+#define sizeof_array(type, count) \
+	array_size(alignof(type), sizeof(type), count)
+
+/** Size of a struct/union field. */
+#define sizeof_member(type, member) \
+	sizeof(((type *)NULL)->member)
+
+/**
+ * Saturating flexible struct size.
+ *
+ * @param align
+ *         Struct alignment.
+ * @param min
+ *         Minimum struct size.
+ * @param offset
+ *         Flexible array member offset.
+ * @param size
+ *         Flexible array element size.
+ * @param count
+ *         Flexible array element count.
+ * @return
+ *         The size of the struct with count flexible array elements.  Saturates
+ *         to the maximum aligned value on overflow.
+ */
+static inline size_t flex_size(size_t align, size_t min, size_t offset, size_t size, size_t count) {
+	size_t ret = size * count;
+	size_t overflow = ret / size != count;
+
+	size_t extra = offset + align - 1;
+	ret += extra;
+	overflow |= ret < extra;
+	ret |= -overflow;
+	ret = align_floor(align, ret);
+
+	// Make sure flex_sizeof(type, member, 0) >= sizeof(type), even if the
+	// type has more padding than necessary for alignment
+	if (min > align_ceil(align, offset)) {
+		ret = ret < min ? min : ret;
+	}
+
+	return ret;
+}
+
+/**
+ * Computes the size of a flexible struct.
+ *
+ * @param type
+ *         The type of the struct containing the flexible array.
+ * @param member
+ *         The name of the flexible array member.
+ * @param count
+ *         The length of the flexible array.
+ * @return
+ *         The size of the struct with count flexible array elements.  Saturates
+ *         to the maximum aligned value on overflow.
+ */
+#define sizeof_flex(type, member, count) \
+	flex_size(alignof(type), sizeof(type), offsetof(type, member), sizeof_member(type, member[0]), count)
+
+/**
+ * General memory allocator.
+ *
+ * @param align
+ *         The required alignment.
+ * @param size
+ *         The size of the allocation.
+ * @return
+ *         The allocated memory, or NULL on failure.
+ */
+void *alloc(size_t align, size_t size);
+
+/**
+ * Zero-initialized memory allocator.
+ *
+ * @param align
+ *         The required alignment.
+ * @param size
+ *         The size of the allocation.
+ * @return
+ *         The allocated memory, or NULL on failure.
+ */
+void *zalloc(size_t align, size_t size);
+
+/** Allocate memory for the given type. */
+#define ALLOC(type) \
+	(type *)alloc(alignof(type), sizeof(type))
+
+/** Allocate zeroed memory for the given type. */
+#define ZALLOC(type) \
+	(type *)zalloc(alignof(type), sizeof(type))
+
+/** Allocate memory for an array. */
+#define ALLOC_ARRAY(type, count) \
+	(type *)alloc(alignof(type), sizeof_array(type, count));
+
+/** Allocate zeroed memory for an array. */
+#define ZALLOC_ARRAY(type, count) \
+	(type *)zalloc(alignof(type), sizeof_array(type, count));
+
+/** Allocate memory for a flexible struct. */
+#define ALLOC_FLEX(type, member, count) \
+	(type *)alloc(alignof(type), sizeof_flex(type, member, count))
+
+/** Allocate zeroed memory for a flexible struct. */
+#define ZALLOC_FLEX(type, member, count) \
+	(type *)zalloc(alignof(type), sizeof_flex(type, member, count))
+
+#endif // BFS_ALLOC_H
diff --git a/src/bfstd.c b/src/bfstd.c
index 856c76c..0e8ba5f 100644
--- a/src/bfstd.c
+++ b/src/bfstd.c
@@ -143,19 +143,6 @@ char *xgetdelim(FILE *file, char delim) {
 	}
 }
 
-void *xmemalign(size_t align, size_t size) {
-	bfs_assert(has_single_bit(align));
-	bfs_assert((size & (align - 1)) == 0);
-
-#if __APPLE__
-	void *ptr = NULL;
-	errno = posix_memalign(&ptr, align, size);
-	return ptr;
-#else
-	return aligned_alloc(align, size);
-#endif
-}
-
 /** Compile and execute a regular expression for xrpmatch(). */
 static int xrpregex(nl_item item, const char *response) {
 	const char *pattern = nl_langinfo(item);
diff --git a/src/bfstd.h b/src/bfstd.h
index 6f2e21e..cafe28f 100644
--- a/src/bfstd.h
+++ b/src/bfstd.h
@@ -105,18 +105,6 @@ char *xgetdelim(FILE *file, char delim);
 
 // #include <stdlib.h>
 
-/**
- * Portable version of aligned_alloc()/posix_memalign().
- *
- * @param align
- *         The allocation's alignment.
- * @param size
- *         The allocation's size.
- * @return
- *         The allocation, or NULL on failure.
- */
-void *xmemalign(size_t align, size_t size);
-
 /**
  * Process a yes/no prompt.
  *
diff --git a/src/bftw.c b/src/bftw.c
index e711963..7ab14c7 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -17,6 +17,7 @@
  */
 
 #include "bftw.h"
+#include "alloc.h"
 #include "bfstd.h"
 #include "config.h"
 #include "diag.h"
@@ -241,9 +242,7 @@ static void bftw_cache_destroy(struct bftw_cache *cache) {
 /** 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 = flex_sizeof(struct bftw_file, name, namelen + 1);
-
-	struct bftw_file *file = malloc(size);
+	struct bftw_file *file = ALLOC_FLEX(struct bftw_file, name, namelen + 1);
 	if (!file) {
 		return NULL;
 	}
diff --git a/src/color.c b/src/color.c
index 1edd8b5..b54ad53 100644
--- a/src/color.c
+++ b/src/color.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "color.h"
+#include "alloc.h"
 #include "bfstd.h"
 #include "bftw.h"
 #include "config.h"
@@ -404,7 +405,7 @@ static void parse_gnu_ls_colors(struct colors *colors, const char *ls_colors) {
 }
 
 struct colors *parse_colors(void) {
-	struct colors *colors = malloc(sizeof(struct colors));
+	struct colors *colors = ALLOC(struct colors);
 	if (!colors) {
 		return NULL;
 	}
@@ -497,7 +498,7 @@ void free_colors(struct colors *colors) {
 }
 
 CFILE *cfwrap(FILE *file, const struct colors *colors, bool close) {
-	CFILE *cfile = malloc(sizeof(*cfile));
+	CFILE *cfile = ALLOC(CFILE);
 	if (!cfile) {
 		return NULL;
 	}
diff --git a/src/config.h b/src/config.h
index 73348ac..1671a0d 100644
--- a/src/config.h
+++ b/src/config.h
@@ -141,56 +141,6 @@
  */
 #define countof(array) (sizeof(array) / sizeof(0[array]))
 
-/**
- * Round down to a multiple of an alignment.
- */
-static inline size_t align_floor(size_t align, size_t size) {
-	return size & ~(align - 1);
-}
-
-/**
- * Round up to a multiple of an alignment.
- */
-static inline size_t align_ceil(size_t align, size_t size) {
-	return align_floor(align, size + align - 1);
-}
-
-/**
- * Computes the size of a struct containing a flexible array member of the given
- * length.
- *
- * @param type
- *         The type of the struct containing the flexible array.
- * @param member
- *         The name of the flexible array member.
- * @param count
- *         The length of the flexible array.
- */
-#define flex_sizeof(type, member, count) \
-	flex_sizeof_impl(alignof(type), sizeof(type), offsetof(type, member), sizeof(((type *)NULL)->member[0]), count)
-
-static inline size_t flex_sizeof_impl(size_t align, size_t min, size_t offset, size_t size, size_t count) {
-	size_t ret = size * count;
-	size_t overflow = ret / size != count;
-
-	ret += offset;
-	overflow |= ret < offset;
-
-	size_t mask = align - 1;
-	ret += mask;
-	overflow |= ret < mask;
-	ret |= -overflow;
-	ret &= ~mask;
-
-	// Make sure flex_sizeof(type, member, 0) >= sizeof(type), even if the
-	// type has more padding than necessary for alignment
-	if (min > align_ceil(align, offset) && ret < min) {
-		ret = min;
-	}
-
-	return ret;
-}
-
 /**
  * False sharing/destructive interference/largest cache line size.
  */
diff --git a/src/ctx.c b/src/ctx.c
index e8ce0e8..a940bed 100644
--- a/src/ctx.c
+++ b/src/ctx.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "ctx.h"
+#include "alloc.h"
 #include "color.h"
 #include "darray.h"
 #include "diag.h"
@@ -42,43 +43,17 @@ const char *debug_flag_name(enum debug_flags flag) {
 }
 
 struct bfs_ctx *bfs_ctx_new(void) {
-	struct bfs_ctx *ctx = malloc(sizeof(*ctx));
+	struct bfs_ctx *ctx = ZALLOC(struct bfs_ctx);
 	if (!ctx) {
 		return NULL;
 	}
 
-	ctx->argv = NULL;
-	ctx->paths = NULL;
-	ctx->expr = NULL;
-	ctx->exclude = NULL;
-
-	ctx->mindepth = 0;
 	ctx->maxdepth = INT_MAX;
 	ctx->flags = BFTW_RECOVER;
 	ctx->strategy = BFTW_BFS;
-	ctx->threads = 0;
 	ctx->optlevel = 3;
-	ctx->debug = 0;
-	ctx->ignore_races = false;
-	ctx->posixly_correct = false;
-	ctx->status = false;
-	ctx->unique = false;
-	ctx->warn = false;
-	ctx->xargs_safe = false;
-
-	ctx->colors = NULL;
-	ctx->colors_error = 0;
-	ctx->cout = NULL;
-	ctx->cerr = NULL;
-
-	ctx->users = NULL;
-	ctx->groups = NULL;
-
-	ctx->mtab = NULL;
-	ctx->mtab_error = 0;
 
 	trie_init(&ctx->files);
-	ctx->nfiles = 0;
 
 	struct rlimit rl;
 	if (getrlimit(RLIMIT_NOFILE, &rl) != 0) {
@@ -155,7 +130,7 @@ CFILE *bfs_ctx_dedup(struct bfs_ctx *ctx, CFILE *cfile, const char *path) {
 		return ctx_file->cfile;
 	}
 
-	leaf->value = ctx_file = malloc(sizeof(*ctx_file));
+	leaf->value = ctx_file = ALLOC(struct bfs_ctx_file);
 	if (!ctx_file) {
 		trie_remove(&ctx->files, leaf);
 		return NULL;
diff --git a/src/dstring.c b/src/dstring.c
index 2c9869d..7ca74d0 100644
--- a/src/dstring.c
+++ b/src/dstring.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "dstring.h"
+#include "alloc.h"
 #include "diag.h"
 #include <stdarg.h>
 #include <stdio.h>
@@ -24,7 +25,7 @@ static struct dstring *dstrheader(const char *dstr) {
 
 /** Get the correct size for a dstring with the given capacity. */
 static size_t dstrsize(size_t capacity) {
-	return flex_sizeof(struct dstring, data, capacity + 1);
+	return sizeof_flex(struct dstring, data, capacity + 1);
 }
 
 /** Allocate a dstring with the given contents. */
diff --git a/src/exec.c b/src/exec.c
index 5912ad6..ea7f897 100644
--- a/src/exec.c
+++ b/src/exec.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "exec.h"
+#include "alloc.h"
 #include "bfstd.h"
 #include "bftw.h"
 #include "ctx.h"
@@ -124,26 +125,16 @@ static void bfs_exec_parse_error(const struct bfs_ctx *ctx, const struct bfs_exe
 }
 
 struct bfs_exec *bfs_exec_parse(const struct bfs_ctx *ctx, char **argv, enum bfs_exec_flags flags) {
-	struct bfs_exec *execbuf = malloc(sizeof(*execbuf));
+	struct bfs_exec *execbuf = ZALLOC(struct bfs_exec);
 	if (!execbuf) {
-		bfs_perror(ctx, "malloc()");
+		bfs_perror(ctx, "zalloc()");
 		goto fail;
 	}
 
 	execbuf->flags = flags;
 	execbuf->ctx = ctx;
 	execbuf->tmpl_argv = argv + 1;
-	execbuf->tmpl_argc = 0;
-	execbuf->argv = NULL;
-	execbuf->argc = 0;
-	execbuf->argv_cap = 0;
-	execbuf->arg_size = 0;
-	execbuf->arg_max = 0;
-	execbuf->arg_min = 0;
 	execbuf->wd_fd = -1;
-	execbuf->wd_path = NULL;
-	execbuf->wd_len = 0;
-	execbuf->ret = 0;
 
 	while (true) {
 		const char *arg = execbuf->tmpl_argv[execbuf->tmpl_argc];
@@ -176,9 +167,9 @@ struct bfs_exec *bfs_exec_parse(const struct bfs_ctx *ctx, char **argv, enum bfs
 	}
 
 	execbuf->argv_cap = execbuf->tmpl_argc + 1;
-	execbuf->argv = malloc(execbuf->argv_cap*sizeof(*execbuf->argv));
+	execbuf->argv = ALLOC_ARRAY(char *, execbuf->argv_cap);
 	if (!execbuf->argv) {
-		bfs_perror(ctx, "malloc()");
+		bfs_perror(ctx, "alloc()");
 		goto fail;
 	}
 
@@ -224,9 +215,8 @@ static char *bfs_exec_format_path(const struct bfs_exec *execbuf, const struct B
 		return NULL;
 	}
 
-	strcpy(path, "./");
-	strcpy(path + 2, name);
-
+	char *cur = stpcpy(path, "./");
+	cur = stpcpy(cur, name);
 	return path;
 }
 
@@ -612,7 +602,7 @@ static int bfs_exec_push(struct bfs_exec *execbuf, char *arg) {
 
 	if (execbuf->argc + 1 >= execbuf->argv_cap) {
 		size_t cap = 2*execbuf->argv_cap;
-		char **argv = realloc(execbuf->argv, cap*sizeof(*argv));
+		char **argv = realloc(execbuf->argv, sizeof_array(char *, cap));
 		if (!argv) {
 			return -1;
 		}
diff --git a/src/ioq.c b/src/ioq.c
index 5550c91..3e304ce 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "ioq.h"
+#include "alloc.h"
 #include "atomic.h"
 #include "bfstd.h"
 #include "bit.h"
@@ -114,7 +115,7 @@ static struct ioqq *ioqq_create(size_t size) {
 	// Circular buffer size must be a power of two
 	size = bit_ceil(size);
 
-	struct ioqq *ioqq = xmemalign(alignof(struct ioqq), flex_sizeof(struct ioqq, slots, size));
+	struct ioqq *ioqq = ALLOC_FLEX(struct ioqq, slots, size);
 	if (!ioqq) {
 		return NULL;
 	}
@@ -124,7 +125,7 @@ static struct ioqq *ioqq_create(size_t size) {
 
 	// Use a pool of monitors
 	size_t nmonitors = size < 64 ? size : 64;
-	ioqq->monitors = xmemalign(alignof(struct ioq_monitor), nmonitors * sizeof(struct ioq_monitor));
+	ioqq->monitors = ALLOC_ARRAY(struct ioq_monitor, nmonitors);
 	if (!ioqq->monitors) {
 		ioqq_destroy(ioqq);
 		return NULL;
@@ -273,7 +274,7 @@ struct ioq {
 	/** The number of background threads. */
 	size_t nthreads;
 	/** The background threads themselves. */
-	pthread_t *threads;
+	pthread_t threads[];
 };
 
 /** Background thread entry point. */
@@ -303,18 +304,13 @@ static void *ioq_work(void *ptr) {
 	return NULL;
 }
 
-struct ioq *ioq_create(size_t depth, size_t threads) {
-	struct ioq *ioq = malloc(sizeof(*ioq));
+struct ioq *ioq_create(size_t depth, size_t nthreads) {
+	struct ioq *ioq = ZALLOC_FLEX(struct ioq, threads, nthreads);
 	if (!ioq) {
 		goto fail;
 	}
 
 	ioq->depth = depth;
-	ioq->size = 0;
-
-	ioq->pending = NULL;
-	ioq->ready = NULL;
-	ioq->nthreads = 0;
 
 	ioq->pending = ioqq_create(depth);
 	if (!ioq->pending) {
@@ -326,12 +322,7 @@ struct ioq *ioq_create(size_t depth, size_t threads) {
 		goto fail;
 	}
 
-	ioq->threads = malloc(threads * sizeof(ioq->threads[0]));
-	if (!ioq->threads) {
-		goto fail;
-	}
-
-	for (size_t i = 0; i < threads; ++i) {
+	for (size_t i = 0; i < nthreads; ++i) {
 		errno = pthread_create(&ioq->threads[i], NULL, ioq_work, ioq);
 		if (errno != 0) {
 			goto fail;
@@ -354,7 +345,7 @@ int ioq_opendir(struct ioq *ioq, int dfd, const char *path, void *ptr) {
 		return -1;
 	}
 
-	union ioq_cmd *cmd = malloc(sizeof(*cmd));
+	union ioq_cmd *cmd = ALLOC(union ioq_cmd);
 	if (!cmd) {
 		return -1;
 	}
@@ -412,7 +403,6 @@ void ioq_destroy(struct ioq *ioq) {
 			abort();
 		}
 	}
-	free(ioq->threads);
 
 	ioqq_destroy(ioq->ready);
 	ioqq_destroy(ioq->pending);
diff --git a/src/ioq.h b/src/ioq.h
index 9492034..0af5779 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -33,12 +33,12 @@ struct ioq_res {
  *
  * @param depth
  *         The maximum depth of the queue.
- * @param threads
+ * @param nthreads
  *         The maximum number of background threads.
  * @return
  *         The new I/O queue, or NULL on failure.
  */
-struct ioq *ioq_create(size_t depth, size_t threads);
+struct ioq *ioq_create(size_t depth, size_t nthreads);
 
 /**
  * Asynchronous bfs_opendir().
diff --git a/src/main.c b/src/main.c
index 76dde86..b7a08c1 100644
--- a/src/main.c
+++ b/src/main.c
@@ -20,6 +20,7 @@
  *     - bftw.[ch]     (an extended version of nftw(3))
  *
  * - Utilities:
+ *     - alloc.[ch]    (memory allocation)
  *     - atomic.h      (atomic operations)
  *     - bar.[ch]      (a terminal status bar)
  *     - bit.h         (bit manipulation)
diff --git a/src/mtab.c b/src/mtab.c
index 1d1ad94..e5c25ba 100644
--- a/src/mtab.c
+++ b/src/mtab.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "mtab.h"
+#include "alloc.h"
 #include "bfstd.h"
 #include "config.h"
 #include "darray.h"
@@ -87,15 +88,13 @@ fail:
 }
 
 struct bfs_mtab *bfs_mtab_parse(void) {
-	struct bfs_mtab *mtab = malloc(sizeof(*mtab));
+	struct bfs_mtab *mtab = ZALLOC(struct bfs_mtab);
 	if (!mtab) {
 		return NULL;
 	}
 
-	mtab->entries = NULL;
 	trie_init(&mtab->names);
 	trie_init(&mtab->types);
-	mtab->types_filled = false;
 
 	int error = 0;
 
diff --git a/src/parse.c b/src/parse.c
index 64e08cd..cf4f696 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -9,6 +9,7 @@
  */
 
 #include "parse.h"
+#include "alloc.h"
 #include "bfstd.h"
 #include "bftw.h"
 #include "color.h"
@@ -55,39 +56,16 @@ static char *fake_print_arg = "-print";
 static char *fake_true_arg = "-true";
 
 struct bfs_expr *bfs_expr_new(bfs_eval_fn *eval_fn, size_t argc, char **argv) {
-	struct bfs_expr *expr = malloc(sizeof(*expr));
+	struct bfs_expr *expr = ZALLOC(struct bfs_expr);
 	if (!expr) {
-		perror("malloc()");
+		perror("zalloc()");
 		return NULL;
 	}
 
 	expr->eval_fn = eval_fn;
 	expr->argc = argc;
 	expr->argv = argv;
-	expr->persistent_fds = 0;
-	expr->ephemeral_fds = 0;
-	expr->pure = false;
-	expr->always_true = false;
-	expr->always_false = false;
-	expr->cost = 0.0;
 	expr->probability = 0.5;
-	expr->evaluations = 0;
-	expr->successes = 0;
-	expr->elapsed.tv_sec = 0;
-	expr->elapsed.tv_nsec = 0;
-
-	// Prevent bfs_expr_free() from freeing uninitialized pointers on error paths
-	if (bfs_expr_is_parent(expr)) {
-		expr->lhs = NULL;
-		expr->rhs = NULL;
-	} else if (eval_fn == eval_exec) {
-		expr->exec = NULL;
-	} else if (eval_fn == eval_fprintf) {
-		expr->printf = NULL;
-	} else if (eval_fn == eval_regex) {
-		expr->regex = NULL;
-	}
-
 	return expr;
 }
 
diff --git a/src/pwcache.c b/src/pwcache.c
index f52e4e1..9f32eb0 100644
--- a/src/pwcache.c
+++ b/src/pwcache.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "pwcache.h"
+#include "alloc.h"
 #include "config.h"
 #include "darray.h"
 #include "trie.h"
@@ -71,7 +72,7 @@ struct bfs_users {
 };
 
 struct bfs_users *bfs_users_new(void) {
-	struct bfs_users *users = malloc(sizeof(*users));
+	struct bfs_users *users = ALLOC(struct bfs_users);
 	if (!users) {
 		return NULL;
 	}
@@ -144,7 +145,7 @@ struct bfs_groups {
 };
 
 struct bfs_groups *bfs_groups_new(void) {
-	struct bfs_groups *groups = malloc(sizeof(*groups));
+	struct bfs_groups *groups = ALLOC(struct bfs_groups);
 	if (!groups) {
 		return NULL;
 	}
diff --git a/src/trie.c b/src/trie.c
index 8543eb1..19423cf 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -82,6 +82,7 @@
  */
 
 #include "trie.h"
+#include "alloc.h"
 #include "bit.h"
 #include "config.h"
 #include "diag.h"
@@ -317,7 +318,7 @@ struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key) {
 
 /** Create a new leaf, holding a copy of the given key. */
 static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, size_t length) {
-	struct trie_leaf *leaf = malloc(flex_sizeof(struct trie_leaf, key, length));
+	struct trie_leaf *leaf = ALLOC_FLEX(struct trie_leaf, key, length);
 	if (!leaf) {
 		return NULL;
 	}
@@ -339,12 +340,10 @@ static void trie_leaf_free(struct trie *trie, struct trie_leaf *leaf) {
 
 /** Compute the size of a trie node with a certain number of children. */
 static size_t trie_node_size(unsigned int size) {
-	// Empty nodes aren't supported
-	bfs_assert(size > 0);
 	// Node size must be a power of two
 	bfs_assert(has_single_bit(size));
 
-	return flex_sizeof(struct trie_node, children, size);
+	return sizeof_flex(struct trie_node, children, size);
 }
 
 #if ENDIAN_NATIVE == ENDIAN_LITTLE
diff --git a/src/xregex.c b/src/xregex.c
index 89c2e90..ab5f793 100644
--- a/src/xregex.c
+++ b/src/xregex.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "xregex.h"
+#include "alloc.h"
 #include "config.h"
 #include "diag.h"
 #include "sanity.h"
@@ -115,7 +116,7 @@ static int bfs_onig_initialize(OnigEncoding *enc) {
 #endif
 
 int bfs_regcomp(struct bfs_regex **preg, const char *pattern, enum bfs_regex_type type, enum bfs_regcomp_flags flags) {
-	struct bfs_regex *regex = *preg = malloc(sizeof(*regex));
+	struct bfs_regex *regex = *preg = ALLOC(struct bfs_regex);
 	if (!regex) {
 		return -1;
 	}
diff --git a/src/xspawn.c b/src/xspawn.c
index 740e38e..2cabdcc 100644
--- a/src/xspawn.c
+++ b/src/xspawn.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "xspawn.h"
+#include "alloc.h"
 #include "bfstd.h"
 #include "config.h"
 #include "list.h"
@@ -62,7 +63,7 @@ int bfs_spawn_setflags(struct bfs_spawn *ctx, enum bfs_spawn_flags flags) {
 
 /** Add a spawn action to the chain. */
 static struct bfs_spawn_action *bfs_spawn_add(struct bfs_spawn *ctx, enum bfs_spawn_op op) {
-	struct bfs_spawn_action *action = malloc(sizeof(*action));
+	struct bfs_spawn_action *action = ALLOC(struct bfs_spawn_action);
 	if (!action) {
 		return NULL;
 	}
diff --git a/tests/alloc.c b/tests/alloc.c
new file mode 100644
index 0000000..91b1b43
--- /dev/null
+++ b/tests/alloc.c
@@ -0,0 +1,24 @@
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+
+#include "../src/alloc.h"
+#include "../src/diag.h"
+#include <stdlib.h>
+
+int main(void) {
+	// Check sizeof_flex()
+	struct flexible {
+		alignas(64) int foo;
+		int bar[];
+	};
+	bfs_verify(sizeof_flex(struct flexible, bar, 0) >= sizeof(struct flexible));
+	bfs_verify(sizeof_flex(struct flexible, bar, 16) % alignof(struct flexible) == 0);
+	bfs_verify(sizeof_flex(struct flexible, bar, SIZE_MAX / sizeof(int) + 1)
+	           == align_floor(alignof(struct flexible), SIZE_MAX));
+
+	// Corner case: sizeof(type) > align_ceil(alignof(type), offsetof(type, member))
+	// Doesn't happen in typical ABIs
+	bfs_verify(flex_size(8, 16, 4, 4, 1) == 16);
+
+	return EXIT_SUCCESS;
+}
diff --git a/tests/bfstd.c b/tests/bfstd.c
index 7fea9b5..fa854a8 100644
--- a/tests/bfstd.c
+++ b/tests/bfstd.c
@@ -24,17 +24,6 @@ static void check_base_dir(const char *path, const char *dir, const char *base)
 }
 
 int main(void) {
-	// Check flex_sizeof()
-	struct flexible {
-		alignas(64) int foo;
-		int bar[];
-	};
-	bfs_verify(flex_sizeof(struct flexible, bar, 0) >= sizeof(struct flexible));
-	bfs_verify(flex_sizeof(struct flexible, bar, 16) % alignof(struct flexible) == 0);
-	bfs_verify(flex_sizeof(struct flexible, bar, SIZE_MAX / sizeof(int) + 1)
-	           == align_floor(alignof(struct flexible), SIZE_MAX));
-	bfs_verify(flex_sizeof_impl(8, 16, 4, 4, 1) == 16);
-
 	// From man 3p basename
 	check_base_dir("usr", ".", "usr");
 	check_base_dir("usr/", ".", "usr");
@@ -46,4 +35,6 @@ int main(void) {
 	check_base_dir("/usr/lib", "/usr", "lib");
 	check_base_dir("//usr//lib//", "//usr", "lib");
 	check_base_dir("/home//dwc//test", "/home//dwc", "test");
+
+	return EXIT_SUCCESS;
 }
-- 
cgit v1.2.3


From a1490d98a1aebb3bfbd3873613977d0341ec7f98 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Tue, 20 Jun 2023 12:02:08 -0400
Subject: dir: Arena-allocate directories

---
 src/bftw.c | 37 +++++++++++++++++++++++++++++--------
 src/dir.c  | 44 +++++++++++++++++++++++---------------------
 src/dir.h  | 27 +++++++++++++++++++++++----
 src/eval.c | 34 ++++++++++++++++++++++------------
 src/ioq.c  | 15 ++++++++++-----
 src/ioq.h  |  4 +++-
 6 files changed, 110 insertions(+), 51 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/bftw.c b/src/bftw.c
index d0491e0..69e41a2 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -103,6 +103,8 @@ struct bftw_cache {
 
 	/** bftw_file arena. */
 	struct varena files;
+	/** bfs_dir arena. */
+	struct arena dirs;
 };
 
 /** Initialize a cache. */
@@ -111,6 +113,7 @@ static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
 	cache->target = NULL;
 	cache->capacity = capacity;
 	VARENA_INIT(&cache->files, struct bftw_file, name);
+	bfs_dir_arena(&cache->dirs);
 }
 
 /** Remove a bftw_file from the LRU list. */
@@ -136,6 +139,7 @@ static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) {
 	if (file->dir) {
 		bfs_assert(file->fd == bfs_dirfd(file->dir));
 		bfs_closedir(file->dir);
+		arena_free(&cache->dirs, file->dir);
 		file->dir = NULL;
 	} else {
 		xclose(file->fd);
@@ -157,9 +161,10 @@ static void bftw_file_freedir(struct bftw_cache *cache, struct bftw_file *file)
 	bool pinned = file->pincount > 0;
 
 	if (reffed || pinned) {
-		int fd = bfs_freedir(file->dir, pinned);
+		int fd = bfs_fdclosedir(file->dir, pinned);
 		if (fd >= 0) {
 			file->fd = fd;
+			arena_free(&cache->dirs, file->dir);
 			file->dir = NULL;
 		}
 	} else {
@@ -243,6 +248,7 @@ static void bftw_cache_destroy(struct bftw_cache *cache) {
 	bfs_assert(!cache->target);
 
 	varena_destroy(&cache->files);
+	arena_destroy(&cache->dirs);
 }
 
 /** Create a new bftw_file. */
@@ -410,10 +416,17 @@ static struct bfs_dir *bftw_file_opendir(struct bftw_cache *cache, struct bftw_f
 		return NULL;
 	}
 
-	struct bfs_dir *dir = bfs_opendir(fd, NULL);
-	if (dir) {
-		bftw_file_set_dir(cache, file, dir);
+	struct bfs_dir *dir = arena_alloc(&cache->dirs);
+	if (!dir) {
+		return NULL;
+	}
+
+	if (bfs_opendir(dir, fd, NULL) != 0) {
+		arena_free(&cache->dirs, dir);
+		return NULL;
 	}
+
+	bftw_file_set_dir(cache, file, dir);
 	return dir;
 }
 
@@ -900,14 +913,18 @@ static void bftw_push_dir(struct bftw_state *state, struct bftw_file *file) {
 			goto unpin;
 		}
 	}
-	--cache->capacity;
 
-	if (ioq_opendir(state->ioq, dfd, file->name, file) != 0) {
-		++cache->capacity;
+	struct bfs_dir *dir = arena_alloc(&state->cache.dirs);
+	if (!dir) {
 		goto unpin;
 	}
 
+	if (ioq_opendir(state->ioq, dir, dfd, file->name, file) != 0) {
+		goto free;
+	}
+
 	file->ioqueued = true;
+	--cache->capacity;
 
 	if (state->flags & BFTW_SORT) {
 		goto append;
@@ -915,6 +932,8 @@ static void bftw_push_dir(struct bftw_state *state, struct bftw_file *file) {
 		return;
 	}
 
+free:
+	arena_free(&state->cache.dirs, dir);
 unpin:
 	if (file->parent) {
 		bftw_cache_unpin(cache, file->parent);
@@ -950,7 +969,9 @@ static int bftw_ioq_pop(struct bftw_state *state, bool block) {
 		bftw_cache_unpin(cache, file->parent);
 	}
 
-	if (res->dir) {
+	if (res->error) {
+		arena_free(&state->cache.dirs, res->dir);
+	} else {
 		bftw_file_set_dir(cache, file, res->dir);
 	}
 
diff --git a/src/dir.c b/src/dir.c
index b9fd74d..a24b572 100644
--- a/src/dir.c
+++ b/src/dir.c
@@ -2,6 +2,7 @@
 // SPDX-License-Identifier: 0BSD
 
 #include "dir.h"
+#include "alloc.h"
 #include "bfstd.h"
 #include "config.h"
 #include "diag.h"
@@ -120,26 +121,26 @@ struct bfs_dir {
 #  define DIR_SIZE sizeof(struct bfs_dir)
 #endif
 
-struct bfs_dir *bfs_opendir(int at_fd, const char *at_path) {
-	struct bfs_dir *dir = malloc(DIR_SIZE);
-	if (!dir) {
-		return NULL;
-	}
+struct bfs_dir *bfs_allocdir(void) {
+	return malloc(DIR_SIZE);
+}
+
+void bfs_dir_arena(struct arena *arena) {
+	arena_init(arena, alignof(struct bfs_dir), DIR_SIZE);
+}
 
+int bfs_opendir(struct bfs_dir *dir, int at_fd, const char *at_path) {
 	int fd;
 	if (at_path) {
 		fd = openat(at_fd, at_path, O_RDONLY | O_CLOEXEC | O_DIRECTORY);
+		if (fd < 0) {
+			return -1;
+		}
 	} else if (at_fd >= 0) {
 		fd = at_fd;
 	} else {
-		free(dir);
 		errno = EBADF;
-		return NULL;
-	}
-
-	if (fd < 0) {
-		free(dir);
-		return NULL;
+		return -1;
 	}
 
 #if BFS_GETDENTS
@@ -152,14 +153,13 @@ struct bfs_dir *bfs_opendir(int at_fd, const char *at_path) {
 		if (at_path) {
 			close_quietly(fd);
 		}
-		free(dir);
-		return NULL;
+		return -1;
 	}
 	dir->de = NULL;
 #endif
 
 	dir->eof = false;
-	return dir;
+	return 0;
 }
 
 int bfs_dirfd(const struct bfs_dir *dir) {
@@ -291,17 +291,16 @@ int bfs_closedir(struct bfs_dir *dir) {
 		bfs_verify(errno != EBADF);
 	}
 #endif
-	free(dir);
+
+	sanitize_uninit(dir, DIR_SIZE);
 	return ret;
 }
 
-int bfs_freedir(struct bfs_dir *dir, bool same_fd) {
+int bfs_fdclosedir(struct bfs_dir *dir, bool same_fd) {
 #if BFS_GETDENTS
 	int ret = dir->fd;
-	free(dir);
 #elif __FreeBSD__
 	int ret = fdclosedir(dir->dir);
-	free(dir);
 #else
 	if (same_fd) {
 		errno = ENOTSUP;
@@ -309,10 +308,13 @@ int bfs_freedir(struct bfs_dir *dir, bool same_fd) {
 	}
 
 	int ret = dup_cloexec(dirfd(dir->dir));
-	if (ret >= 0) {
-		bfs_closedir(dir);
+	if (ret < 0) {
+		return -1;
 	}
+
+	bfs_closedir(dir);
 #endif
 
+	sanitize_uninit(dir, DIR_SIZE);
 	return ret;
 }
diff --git a/src/dir.h b/src/dir.h
index 6fe7ae2..16f592e 100644
--- a/src/dir.h
+++ b/src/dir.h
@@ -8,6 +8,7 @@
 #ifndef BFS_DIR_H
 #define BFS_DIR_H
 
+#include "alloc.h"
 #include "config.h"
 #include <sys/types.h>
 
@@ -61,18 +62,36 @@ struct bfs_dirent {
 	const char *name;
 };
 
+/**
+ * Allocate space for a directory.
+ *
+ * @return
+ *         An allocated, unopen directory, or NULL on failure.
+ */
+struct bfs_dir *bfs_allocdir(void);
+
+/**
+ * Initialize an arena for directories.
+ *
+ * @param arena
+ *         The arena to initialize.
+ */
+void bfs_dir_arena(struct arena *arena);
+
 /**
  * Open a directory.
  *
+ * @param dir
+ *         The allocated directory.
  * @param at_fd
  *         The base directory for path resolution.
  * @param at_path
  *         The path of the directory to open, relative to at_fd.  Pass NULL to
  *         open at_fd itself.
  * @return
- *         The opened directory, or NULL on failure.
+ *         0 on success, or -1 on failure.
  */
-struct bfs_dir *bfs_opendir(int at_fd, const char *at_path);
+int bfs_opendir(struct bfs_dir *dir, int at_fd, const char *at_path);
 
 /**
  * Get the file descriptor for a directory.
@@ -110,7 +129,7 @@ int bfs_readdir(struct bfs_dir *dir, struct bfs_dirent *de);
 int bfs_closedir(struct bfs_dir *dir);
 
 /**
- * Free a directory, keeping an open file descriptor to it.
+ * Extract the file descriptor from an open directory.
  *
  * @param dir
  *         The directory to free.
@@ -122,6 +141,6 @@ int bfs_closedir(struct bfs_dir *dir);
  *         On success, a file descriptor for the directory is returned.  On
  *         failure, -1 is returned, and the directory remains open.
  */
-int bfs_freedir(struct bfs_dir *dir, bool same_fd);
+int bfs_fdclosedir(struct bfs_dir *dir, bool same_fd);
 
 #endif // BFS_DIR_H
diff --git a/src/eval.c b/src/eval.c
index f16821e..5f27681 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -421,10 +421,15 @@ bool eval_empty(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct BFTW *ftwbuf = state->ftwbuf;
 
 	if (ftwbuf->type == BFS_DIR) {
-		struct bfs_dir *dir = bfs_opendir(ftwbuf->at_fd, ftwbuf->at_path);
+		struct bfs_dir *dir = bfs_allocdir();
 		if (!dir) {
 			eval_report_error(state);
-			goto done;
+			return ret;
+		}
+
+		if (bfs_opendir(dir, ftwbuf->at_fd, ftwbuf->at_path) != 0) {
+			eval_report_error(state);
+			return ret;
 		}
 
 		int did_read = bfs_readdir(dir, NULL);
@@ -435,6 +440,7 @@ bool eval_empty(const struct bfs_expr *expr, struct bfs_eval *state) {
 		}
 
 		bfs_closedir(dir);
+		free(dir);
 	} else if (ftwbuf->type == BFS_REG) {
 		const struct bfs_stat *statbuf = eval_stat(state);
 		if (statbuf) {
@@ -442,7 +448,6 @@ bool eval_empty(const struct bfs_expr *expr, struct bfs_eval *state) {
 		}
 	}
 
-done:
 	return ret;
 }
 
@@ -1495,20 +1500,25 @@ static int infer_fdlimit(const struct bfs_ctx *ctx, int limit) {
 
 	// Check /proc/self/fd for the current number of open fds, if possible
 	// (we may have inherited more than just the standard ones)
-	struct bfs_dir *dir = bfs_opendir(AT_FDCWD, "/proc/self/fd");
+	struct bfs_dir *dir = bfs_allocdir();
 	if (!dir) {
-		dir = bfs_opendir(AT_FDCWD, "/dev/fd");
+		goto done;
 	}
-	if (dir) {
-		// Account for 'dir' itself
-		nopen = -1;
 
-		while (bfs_readdir(dir, NULL) > 0) {
-			++nopen;
-		}
+	if (bfs_opendir(dir, AT_FDCWD, "/proc/self/fd") != 0
+	    && bfs_opendir(dir, AT_FDCWD, "/dev/fd") != 0) {
+		goto done;
+	}
 
-		bfs_closedir(dir);
+	// Account for 'dir' itself
+	nopen = -1;
+
+	while (bfs_readdir(dir, NULL) > 0) {
+		++nopen;
 	}
+	bfs_closedir(dir);
+done:
+	free(dir);
 
 	int ret = limit - nopen;
 	ret -= ctx->expr->persistent_fds;
diff --git a/src/ioq.c b/src/ioq.c
index 33316fa..47b082a 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -20,9 +20,11 @@
  * An I/O queue request.
  */
 struct ioq_req {
+	/** Directory allocation. */
+	struct bfs_dir *dir;
 	/** Base file descriptor for openat(). */
 	int dfd;
-	/** Relative path to dfd. */
+	/** Path to open, relative to dfd. */
 	const char *path;
 
 	/** Arbitrary user data. */
@@ -295,10 +297,12 @@ static void *ioq_work(void *ptr) {
 
 		struct ioq_res *res = &cmd->res;
 		res->ptr = req.ptr;
-		res->dir = bfs_opendir(req.dfd, req.path);
-		res->error = errno;
-		if (res->dir) {
+		res->dir = req.dir;
+		res->error = 0;
+		if (bfs_opendir(req.dir, req.dfd, req.path) == 0) {
 			bfs_polldir(res->dir);
+		} else {
+			res->error = errno;
 		}
 
 		ioqq_push(ioq->ready, cmd);
@@ -344,7 +348,7 @@ fail:
 	return NULL;
 }
 
-int ioq_opendir(struct ioq *ioq, int dfd, const char *path, void *ptr) {
+int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, void *ptr) {
 	if (ioq->size >= ioq->depth) {
 		return -1;
 	}
@@ -355,6 +359,7 @@ int ioq_opendir(struct ioq *ioq, int dfd, const char *path, void *ptr) {
 	}
 
 	struct ioq_req *req = &cmd->req;
+	req->dir = dir;
 	req->dfd = dfd;
 	req->path = path;
 	req->ptr = ptr;
diff --git a/src/ioq.h b/src/ioq.h
index 0af5779..50e02b1 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -45,6 +45,8 @@ struct ioq *ioq_create(size_t depth, size_t nthreads);
  *
  * @param ioq
  *         The I/O queue.
+ * @param dir
+ *         The allocated directory.
  * @param dfd
  *         The base file descriptor.
  * @param path
@@ -54,7 +56,7 @@ struct ioq *ioq_create(size_t depth, size_t nthreads);
  * @return
  *         0 on success, or -1 on failure.
  */
-int ioq_opendir(struct ioq *ioq, int dfd, const char *path, void *ptr);
+int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, void *ptr);
 
 /**
  * Pop a response from the queue.
-- 
cgit v1.2.3


From abd29143d805fa16c65489d5b1d79428943d0187 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 26 Jun 2023 11:47:41 -0400
Subject: ioq: New ioq_cancel() function

---
 src/bftw.c |  4 ++++
 src/ioq.c  | 27 ++++++++++++++++++++-------
 src/ioq.h  |  5 +++++
 3 files changed, 29 insertions(+), 7 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/bftw.c b/src/bftw.c
index 69e41a2..2bdf12d 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -1147,6 +1147,10 @@ static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) {
 static int bftw_state_destroy(struct bftw_state *state) {
 	dstrfree(state->path);
 
+	if (state->ioq) {
+		ioq_cancel(state->ioq);
+	}
+
 	SLIST_EXTEND(&state->files, &state->batch);
 	do {
 		bftw_gc(state, BFTW_VISIT_NONE);
diff --git a/src/ioq.c b/src/ioq.c
index 617bd5f..457ead7 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -264,6 +264,8 @@ struct ioq {
 	size_t depth;
 	/** The current size of the queue. */
 	size_t size;
+	/** Cancellation flag. */
+	atomic bool cancel;
 
 	/** ioq_cmd command arena. */
 	struct arena cmds;
@@ -289,17 +291,22 @@ static void *ioq_work(void *ptr) {
 			break;
 		}
 
+		bool cancel = load(&ioq->cancel, relaxed);
+
 		struct ioq_req req = cmd->req;
 		sanitize_uninit(cmd);
 
 		struct ioq_res *res = &cmd->res;
 		res->ptr = req.ptr;
 		res->dir = req.dir;
-		res->error = 0;
-		if (bfs_opendir(req.dir, req.dfd, req.path) == 0) {
-			bfs_polldir(res->dir);
-		} else {
+
+		if (cancel) {
+			res->error = EINTR;
+		} else if (bfs_opendir(req.dir, req.dfd, req.path) != 0) {
 			res->error = errno;
+		} else {
+			res->error = 0;
+			bfs_polldir(res->dir);
 		}
 
 		ioqq_push(ioq->ready, cmd);
@@ -394,14 +401,20 @@ void ioq_free(struct ioq *ioq, struct ioq_res *res) {
 	arena_free(&ioq->cmds, (union ioq_cmd *)res);
 }
 
+void ioq_cancel(struct ioq *ioq) {
+	if (!exchange(&ioq->cancel, true, relaxed)) {
+		for (size_t i = 0; i < ioq->nthreads; ++i) {
+			ioqq_push(ioq->pending, &IOQ_STOP);
+		}
+	}
+}
+
 void ioq_destroy(struct ioq *ioq) {
 	if (!ioq) {
 		return;
 	}
 
-	for (size_t i = 0; i < ioq->nthreads; ++i) {
-		ioqq_push(ioq->pending, &IOQ_STOP);
-	}
+	ioq_cancel(ioq);
 
 	for (size_t i = 0; i < ioq->nthreads; ++i) {
 		if (pthread_join(ioq->threads[i], NULL) != 0) {
diff --git a/src/ioq.h b/src/ioq.h
index 50e02b1..064e2e2 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -88,6 +88,11 @@ struct ioq_res *ioq_trypop(struct ioq *ioq);
  */
 void ioq_free(struct ioq *ioq, struct ioq_res *res);
 
+/**
+ * Cancel any pending I/O operations.
+ */
+void ioq_cancel(struct ioq *ioq);
+
 /**
  * Stop and destroy an I/O queue.
  */
-- 
cgit v1.2.3


From 379dee8a47480938c067fca0acd01dea9b5afa33 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Tue, 4 Jul 2023 15:01:18 -0400
Subject: ioq: New ioq_capacity() function

---
 src/ioq.c | 9 +++++++--
 src/ioq.h | 5 +++++
 2 files changed, 12 insertions(+), 2 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/ioq.c b/src/ioq.c
index 10451ac..5673c77 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -355,6 +355,10 @@ fail:
 	return NULL;
 }
 
+size_t ioq_capacity(const struct ioq *ioq) {
+	return ioq->depth - ioq->size;
+}
+
 int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, void *ptr) {
 	if (ioq->size >= ioq->depth) {
 		return -1;
@@ -382,7 +386,6 @@ struct ioq_res *ioq_pop(struct ioq *ioq) {
 	}
 
 	union ioq_cmd *cmd = ioqq_pop(ioq->ready);
-	--ioq->size;
 	return &cmd->res;
 }
 
@@ -396,11 +399,13 @@ struct ioq_res *ioq_trypop(struct ioq *ioq) {
 		return NULL;
 	}
 
-	--ioq->size;
 	return &cmd->res;
 }
 
 void ioq_free(struct ioq *ioq, struct ioq_res *res) {
+	bfs_assert(ioq->size > 0);
+	--ioq->size;
+
 	arena_free(&ioq->cmds, (union ioq_cmd *)res);
 }
 
diff --git a/src/ioq.h b/src/ioq.h
index 064e2e2..9901293 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -40,6 +40,11 @@ struct ioq_res {
  */
 struct ioq *ioq_create(size_t depth, size_t nthreads);
 
+/**
+ * Check the remaining capacity of a queue.
+ */
+size_t ioq_capacity(const struct ioq *ioq);
+
 /**
  * Asynchronous bfs_opendir().
  *
-- 
cgit v1.2.3


From 222ac5ba4fbab0ab880e36423d0f1338e39b02c7 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Tue, 4 Jul 2023 15:17:23 -0400
Subject: ioq: Implement async close() and closedir()

---
 src/bftw.c |  41 ++++++++-------
 src/ioq.c  | 175 ++++++++++++++++++++++++++++++++++++-------------------------
 src/ioq.h  |  81 ++++++++++++++++++++++++----
 3 files changed, 197 insertions(+), 100 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/bftw.c b/src/bftw.c
index ec67817..64f221b 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -901,34 +901,39 @@ static int bftw_ioq_pop(struct bftw_state *state, bool block) {
 		return -1;
 	}
 
-	struct ioq_res *res = block ? ioq_pop(ioq) : ioq_trypop(ioq);
-	if (!res) {
+	struct ioq_ent *ent = block ? ioq_pop(ioq) : ioq_trypop(ioq);
+	if (!ent) {
 		return -1;
 	}
 
 	struct bftw_cache *cache = &state->cache;
-	++cache->capacity;
-
-	struct bftw_file *file = res->ptr;
-	file->ioqueued = false;
+	struct bftw_file *file;
+	struct bfs_dir *dir;
 
-	if (file->parent) {
-		bftw_cache_unpin(cache, file->parent);
-	}
+	enum ioq_op op = ent->op;
+	if (op == IOQ_OPENDIR) {
+		file = ent->ptr;
+		file->ioqueued = false;
 
-	if (res->error) {
-		arena_free(&cache->dirs, res->dir);
-	} else {
-		bftw_file_set_dir(cache, file, res->dir);
-	}
+		++cache->capacity;
+		if (file->parent) {
+			bftw_cache_unpin(cache, file->parent);
+		}
 
-	ioq_free(ioq, res);
+		dir = ent->opendir.dir;
+		if (ent->ret == 0) {
+			bftw_file_set_dir(cache, file, dir);
+		} else {
+			arena_free(&cache->dirs, dir);
+		}
 
-	if (!(state->flags & BFTW_SORT)) {
-		SLIST_PREPEND(&state->dirs, file);
+		if (!(state->flags & BFTW_SORT)) {
+			SLIST_PREPEND(&state->dirs, file);
+		}
 	}
 
-	return 0;
+	ioq_free(ioq, ent);
+	return op;
 }
 
 /** Try to reserve space in the I/O queue. */
diff --git a/src/ioq.c b/src/ioq.c
index 5673c77..0544044 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -16,29 +16,6 @@
 #include <pthread.h>
 #include <stdlib.h>
 
-/**
- * An I/O queue request.
- */
-struct ioq_req {
-	/** Directory allocation. */
-	struct bfs_dir *dir;
-	/** Base file descriptor for openat(). */
-	int dfd;
-	/** Path to open, relative to dfd. */
-	const char *path;
-
-	/** Arbitrary user data. */
-	void *ptr;
-};
-
-/**
- * An I/O queue command.
- */
-union ioq_cmd {
-	struct ioq_req req;
-	struct ioq_res res;
-};
-
 /**
  * A monitor for an I/O queue slot.
  */
@@ -101,7 +78,7 @@ bfs_static_assert(IOQ_STRIDE % 2 == 1);
 
 /** Slot flag bit to indicate waiters. */
 #define IOQ_BLOCKED ((uintptr_t)1)
-bfs_static_assert(alignof(union ioq_cmd) > 1);
+bfs_static_assert(alignof(struct ioq_ent) > 1);
 
 /** Destroy an I/O command queue. */
 static void ioqq_destroy(struct ioqq *ioqq) {
@@ -189,12 +166,12 @@ static void ioqq_wake(struct ioqq *ioqq, size_t i) {
 	cond_broadcast(&monitor->cond);
 }
 
-/** Push a command onto the queue. */
-static void ioqq_push(struct ioqq *ioqq, union ioq_cmd *cmd) {
+/** Push an entry onto the queue. */
+static void ioqq_push(struct ioqq *ioqq, struct ioq_ent *ent) {
 	size_t i = fetch_add(&ioqq->head, IOQ_STRIDE, relaxed);
 	atomic uintptr_t *slot = &ioqq->slots[i & ioqq->slot_mask];
 
-	uintptr_t addr = (uintptr_t)cmd;
+	uintptr_t addr = (uintptr_t)ent;
 	bfs_assert(!(addr & IOQ_BLOCKED));
 
 	uintptr_t prev = load(slot, relaxed);
@@ -212,8 +189,8 @@ static void ioqq_push(struct ioqq *ioqq, union ioq_cmd *cmd) {
 	}
 }
 
-/** Pop a command from a queue. */
-static union ioq_cmd *ioqq_pop(struct ioqq *ioqq) {
+/** Pop an entry from the queue. */
+static struct ioq_ent *ioqq_pop(struct ioqq *ioqq) {
 	size_t i = fetch_add(&ioqq->tail, IOQ_STRIDE, relaxed);
 	atomic uintptr_t *slot = &ioqq->slots[i & ioqq->slot_mask];
 
@@ -232,11 +209,11 @@ static union ioq_cmd *ioqq_pop(struct ioqq *ioqq) {
 	}
 	prev &= ~IOQ_BLOCKED;
 
-	return (union ioq_cmd *)prev;
+	return (struct ioq_ent *)prev;
 }
 
-/** Pop a command from a queue if one is available. */
-static union ioq_cmd *ioqq_trypop(struct ioqq *ioqq) {
+/** Pop an entry from the queue if one is available. */
+static struct ioq_ent *ioqq_trypop(struct ioqq *ioqq) {
 	size_t i = load(&ioqq->tail, relaxed);
 	atomic uintptr_t *slot = &ioqq->slots[i & ioqq->slot_mask];
 
@@ -257,11 +234,11 @@ static union ioq_cmd *ioqq_trypop(struct ioqq *ioqq) {
 	bfs_assert(j == i, "ioqq_trypop() only supports a single consumer");
 	(void)j;
 
-	return (union ioq_cmd *)prev;
+	return (struct ioq_ent *)prev;
 }
 
 /** Sentinel stop command. */
-static union ioq_cmd IOQ_STOP;
+static struct ioq_ent IOQ_STOP;
 
 struct ioq {
 	/** The depth of the queue. */
@@ -271,8 +248,8 @@ struct ioq {
 	/** Cancellation flag. */
 	atomic bool cancel;
 
-	/** ioq_cmd command arena. */
-	struct arena cmds;
+	/** ioq_ent arena. */
+	struct arena ents;
 
 	/** Pending I/O requests. */
 	struct ioqq *pending;
@@ -290,30 +267,50 @@ static void *ioq_work(void *ptr) {
 	struct ioq *ioq = ptr;
 
 	while (true) {
-		union ioq_cmd *cmd = ioqq_pop(ioq->pending);
-		if (cmd == &IOQ_STOP) {
+		struct ioq_ent *ent = ioqq_pop(ioq->pending);
+		if (ent == &IOQ_STOP) {
 			break;
 		}
 
 		bool cancel = load(&ioq->cancel, relaxed);
 
-		struct ioq_req req = cmd->req;
-		sanitize_uninit(cmd);
+		ent->ret = -1;
+
+		switch (ent->op) {
+		case IOQ_CLOSE:
+			// Always close(), even if we're cancelled, just like a real EINTR
+			ent->ret = xclose(ent->close.fd);
+			break;
+
+		case IOQ_OPENDIR:
+			if (!cancel) {
+				struct ioq_opendir *args = &ent->opendir;
+				ent->ret = bfs_opendir(args->dir, args->dfd, args->path);
+				if (ent->ret == 0) {
+					bfs_polldir(args->dir);
+				}
+			}
+			break;
+
+		case IOQ_CLOSEDIR:
+			ent->ret = bfs_closedir(ent->closedir.dir);
+			break;
 
-		struct ioq_res *res = &cmd->res;
-		res->ptr = req.ptr;
-		res->dir = req.dir;
+		default:
+			bfs_bug("Unknown ioq_op %d", (int)ent->op);
+			errno = ENOSYS;
+			break;
+		}
 
 		if (cancel) {
-			res->error = EINTR;
-		} else if (bfs_opendir(req.dir, req.dfd, req.path) != 0) {
-			res->error = errno;
+			ent->error = EINTR;
+		} else if (ent->ret < 0) {
+			ent->error = errno;
 		} else {
-			res->error = 0;
-			bfs_polldir(res->dir);
+			ent->error = 0;
 		}
 
-		ioqq_push(ioq->ready, cmd);
+		ioqq_push(ioq->ready, ent);
 	}
 
 	return NULL;
@@ -326,7 +323,7 @@ struct ioq *ioq_create(size_t depth, size_t nthreads) {
 	}
 
 	ioq->depth = depth;
-	ARENA_INIT(&ioq->cmds, union ioq_cmd);
+	ARENA_INIT(&ioq->ents, struct ioq_ent);
 
 	ioq->pending = ioqq_create(depth);
 	if (!ioq->pending) {
@@ -359,54 +356,88 @@ size_t ioq_capacity(const struct ioq *ioq) {
 	return ioq->depth - ioq->size;
 }
 
-int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, void *ptr) {
+static struct ioq_ent *ioq_request(struct ioq *ioq, enum ioq_op op, void *ptr) {
+	if (load(&ioq->cancel, relaxed)) {
+		errno = EINTR;
+		return NULL;
+	}
+
 	if (ioq->size >= ioq->depth) {
+		errno = EAGAIN;
+		return NULL;
+	}
+
+	struct ioq_ent *ent = arena_alloc(&ioq->ents);
+	if (!ent) {
+		return NULL;
+	}
+
+	ent->op = op;
+	ent->ptr = ptr;
+	++ioq->size;
+	return ent;
+}
+
+int ioq_close(struct ioq *ioq, int fd, void *ptr) {
+	struct ioq_ent *ent = ioq_request(ioq, IOQ_CLOSE, ptr);
+	if (!ent) {
 		return -1;
 	}
 
-	union ioq_cmd *cmd = arena_alloc(&ioq->cmds);
-	if (!cmd) {
+	ent->close.fd = fd;
+
+	ioqq_push(ioq->pending, ent);
+	return 0;
+}
+
+int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, void *ptr) {
+	struct ioq_ent *ent = ioq_request(ioq, IOQ_OPENDIR, ptr);
+	if (!ent) {
 		return -1;
 	}
 
-	struct ioq_req *req = &cmd->req;
-	req->dir = dir;
-	req->dfd = dfd;
-	req->path = path;
-	req->ptr = ptr;
+	struct ioq_opendir *args = &ent->opendir;
+	args->dir = dir;
+	args->dfd = dfd;
+	args->path = path;
 
-	ioqq_push(ioq->pending, cmd);
-	++ioq->size;
+	ioqq_push(ioq->pending, ent);
 	return 0;
 }
 
-struct ioq_res *ioq_pop(struct ioq *ioq) {
-	if (ioq->size == 0) {
-		return NULL;
+int ioq_closedir(struct ioq *ioq, struct bfs_dir *dir, void *ptr) {
+	struct ioq_ent *ent = ioq_request(ioq, IOQ_CLOSEDIR, ptr);
+	if (!ent) {
+		return -1;
 	}
 
-	union ioq_cmd *cmd = ioqq_pop(ioq->ready);
-	return &cmd->res;
+	ent->closedir.dir = dir;
+
+	ioqq_push(ioq->pending, ent);
+	return 0;
 }
 
-struct ioq_res *ioq_trypop(struct ioq *ioq) {
+struct ioq_ent *ioq_pop(struct ioq *ioq) {
 	if (ioq->size == 0) {
 		return NULL;
 	}
 
-	union ioq_cmd *cmd = ioqq_trypop(ioq->ready);
-	if (!cmd) {
+	return ioqq_pop(ioq->ready);
+}
+
+struct ioq_ent *ioq_trypop(struct ioq *ioq) {
+	if (ioq->size == 0) {
 		return NULL;
 	}
 
-	return &cmd->res;
+	return ioqq_trypop(ioq->ready);
 }
 
-void ioq_free(struct ioq *ioq, struct ioq_res *res) {
+void ioq_free(struct ioq *ioq, struct ioq_ent *ent) {
 	bfs_assert(ioq->size > 0);
 	--ioq->size;
 
-	arena_free(&ioq->cmds, (union ioq_cmd *)res);
+	arena_free(&ioq->ents, ent);
 }
 
 void ioq_cancel(struct ioq *ioq) {
@@ -431,7 +462,7 @@ void ioq_destroy(struct ioq *ioq) {
 	ioqq_destroy(ioq->ready);
 	ioqq_destroy(ioq->pending);
 
-	arena_destroy(&ioq->cmds);
+	arena_destroy(&ioq->ents);
 
 	free(ioq);
 }
diff --git a/src/ioq.h b/src/ioq.h
index 9901293..99c18c2 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -16,16 +16,49 @@
 struct ioq;
 
 /**
- * An I/O queue response.
+ * I/O queue operations.
  */
-struct ioq_res {
-	/** The opened directory. */
-	struct bfs_dir *dir;
+enum ioq_op {
+	/** ioq_close(). */
+	IOQ_CLOSE,
+	/** ioq_opendir(). */
+	IOQ_OPENDIR,
+	/** ioq_closedir(). */
+	IOQ_CLOSEDIR,
+};
+
+/**
+ * An I/O queue entry.
+ */
+struct ioq_ent {
+	/** The I/O operation. */
+	enum ioq_op op;
+
+	/** The return value of the operation. */
+	int ret;
 	/** The error code, if the operation failed. */
 	int error;
 
 	/** Arbitrary user data. */
 	void *ptr;
+
+	/** Operation-specific arguments. */
+	union {
+		/** ioq_close() args. */
+		struct ioq_close {
+			int fd;
+		} close;
+		/** ioq_opendir() args. */
+		struct ioq_opendir {
+			struct bfs_dir *dir;
+			int dfd;
+			const char *path;
+		} opendir;
+		/** ioq_closedir() args. */
+		struct ioq_closedir {
+			struct bfs_dir *dir;
+		} closedir;
+	};
 };
 
 /**
@@ -45,6 +78,20 @@ struct ioq *ioq_create(size_t depth, size_t nthreads);
  */
 size_t ioq_capacity(const struct ioq *ioq);
 
+/**
+ * Asynchronous close().
+ *
+ * @param ioq
+ *         The I/O queue.
+ * @param fd
+ *         The fd to close.
+ * @param ptr
+ *         An arbitrary pointer to associate with the request.
+ * @return
+ *         0 on success, or -1 on failure.
+ */
+int ioq_close(struct ioq *ioq, int fd, void *ptr);
+
 /**
  * Asynchronous bfs_opendir().
  *
@@ -63,6 +110,20 @@ size_t ioq_capacity(const struct ioq *ioq);
  */
 int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, void *ptr);
 
+/**
+ * Asynchronous bfs_closedir().
+ *
+ * @param ioq
+ *         The I/O queue.
+ * @param dir
+ *         The directory to close.
+ * @param ptr
+ *         An arbitrary pointer to associate with the request.
+ * @return
+ *         0 on success, or -1 on failure.
+ */
+int ioq_closedir(struct ioq *ioq, struct bfs_dir *dir, void *ptr);
+
 /**
  * Pop a response from the queue.
  *
@@ -71,7 +132,7 @@ int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path,
  * @return
  *         The next response, or NULL.
  */
-struct ioq_res *ioq_pop(struct ioq *ioq);
+struct ioq_ent *ioq_pop(struct ioq *ioq);
 
 /**
  * Pop a response from the queue, without blocking.
@@ -81,17 +142,17 @@ struct ioq_res *ioq_pop(struct ioq *ioq);
  * @return
  *         The next response, or NULL.
  */
-struct ioq_res *ioq_trypop(struct ioq *ioq);
+struct ioq_ent *ioq_trypop(struct ioq *ioq);
 
 /**
- * Free a response.
+ * Free a queue entry.
  *
  * @param ioq
  *         The I/O queue.
- * @param res
- *         The response to free.
+ * @param ent
+ *         The entry to free.
  */
-void ioq_free(struct ioq *ioq, struct ioq_res *res);
+void ioq_free(struct ioq *ioq, struct ioq_ent *ent);
 
 /**
  * Cancel any pending I/O operations.
-- 
cgit v1.2.3


From 214a1f9215d33d4b9f34a3d258da1e1f4e3eb01f Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 16 Oct 2023 16:44:46 -0400
Subject: dir: Add a flags parameter to bfs_opendir()

---
 src/bftw.c |  4 ++--
 src/dir.c  | 31 ++++++++++++++++++++-----------
 src/dir.h  | 12 +++++++++++-
 src/eval.c |  6 +++---
 src/ioq.c  |  7 ++++---
 src/ioq.h  |  6 +++++-
 6 files changed, 45 insertions(+), 21 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/bftw.c b/src/bftw.c
index 06a0085..e2f1a66 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -856,7 +856,7 @@ static int bftw_ioq_opendir(struct bftw_state *state, struct bftw_file *file) {
 		goto unpin;
 	}
 
-	if (ioq_opendir(state->ioq, dir, dfd, file->name, file) != 0) {
+	if (ioq_opendir(state->ioq, dir, dfd, file->name, 0, file) != 0) {
 		goto free;
 	}
 
@@ -1018,7 +1018,7 @@ static struct bfs_dir *bftw_file_opendir(struct bftw_state *state, struct bftw_f
 		return NULL;
 	}
 
-	if (bfs_opendir(dir, fd, NULL) != 0) {
+	if (bfs_opendir(dir, fd, NULL, 0) != 0) {
 		bftw_freedir(cache, dir);
 		return NULL;
 	}
diff --git a/src/dir.c b/src/dir.c
index a7423e9..dee02e5 100644
--- a/src/dir.c
+++ b/src/dir.c
@@ -96,18 +96,26 @@ enum bfs_type bfs_mode_to_type(mode_t mode) {
 	}
 }
 
+/**
+ * Private directory flags.
+ */
+enum {
+	/** We've reached the end of the directory. */
+	BFS_DIR_EOF = BFS_DIR_PRIVATE << 0,
+};
+
 struct bfs_dir {
+	unsigned int flags;
+
 #if BFS_USE_GETDENTS
-	alignas(sys_dirent) int fd;
+	int fd;
 	unsigned short pos;
 	unsigned short size;
-	// sys_dirent buf[];
+	alignas(sys_dirent) char buf[];
 #else
 	DIR *dir;
 	struct dirent *de;
 #endif
-
-	bool eof;
 };
 
 #if BFS_USE_GETDENTS
@@ -125,7 +133,7 @@ void bfs_dir_arena(struct arena *arena) {
 	arena_init(arena, alignof(struct bfs_dir), DIR_SIZE);
 }
 
-int bfs_opendir(struct bfs_dir *dir, int at_fd, const char *at_path) {
+int bfs_opendir(struct bfs_dir *dir, int at_fd, const char *at_path, enum bfs_dir_flags flags) {
 	int fd;
 	if (at_path) {
 		fd = openat(at_fd, at_path, O_RDONLY | O_CLOEXEC | O_DIRECTORY);
@@ -139,6 +147,8 @@ int bfs_opendir(struct bfs_dir *dir, int at_fd, const char *at_path) {
 		return -1;
 	}
 
+	dir->flags = flags;
+
 #if BFS_USE_GETDENTS
 	dir->fd = fd;
 	dir->pos = 0;
@@ -154,7 +164,6 @@ int bfs_opendir(struct bfs_dir *dir, int at_fd, const char *at_path) {
 	dir->de = NULL;
 #endif
 
-	dir->eof = false;
 	return 0;
 }
 
@@ -170,14 +179,14 @@ int bfs_polldir(struct bfs_dir *dir) {
 #if BFS_USE_GETDENTS
 	if (dir->pos < dir->size) {
 		return 1;
-	} else if (dir->eof) {
+	} else if (dir->flags & BFS_DIR_EOF) {
 		return 0;
 	}
 
 	char *buf = (char *)(dir + 1);
 	ssize_t size = bfs_getdents(dir->fd, buf, BUF_SIZE);
 	if (size == 0) {
-		dir->eof = true;
+		dir->flags |= BFS_DIR_EOF;
 		return 0;
 	} else if (size < 0) {
 		return -1;
@@ -194,7 +203,7 @@ int bfs_polldir(struct bfs_dir *dir) {
 		if (size > 0) {
 			dir->size += size;
 		} else if (size == 0) {
-			dir->eof = true;
+			dir->flags |= BFS_DIR_EOF;
 		}
 	}
 
@@ -202,7 +211,7 @@ int bfs_polldir(struct bfs_dir *dir) {
 #else // !BFS_USE_GETDENTS
 	if (dir->de) {
 		return 1;
-	} else if (dir->eof) {
+	} else if (dir->flags & BFS_DIR_EOF) {
 		return 0;
 	}
 
@@ -211,7 +220,7 @@ int bfs_polldir(struct bfs_dir *dir) {
 	if (dir->de) {
 		return 1;
 	} else if (errno == 0) {
-		dir->eof = true;
+		dir->flags |= BFS_DIR_EOF;
 		return 0;
 	} else {
 		return -1;
diff --git a/src/dir.h b/src/dir.h
index 1137ff5..7e0cbba 100644
--- a/src/dir.h
+++ b/src/dir.h
@@ -86,6 +86,14 @@ struct bfs_dir *bfs_allocdir(void);
  */
 void bfs_dir_arena(struct arena *arena);
 
+/**
+ * bfs_opendir() flags.
+ */
+enum bfs_dir_flags {
+	/** @internal Start of private flags. */
+	BFS_DIR_PRIVATE = 1 << 0,
+};
+
 /**
  * Open a directory.
  *
@@ -96,10 +104,12 @@ void bfs_dir_arena(struct arena *arena);
  * @param at_path
  *         The path of the directory to open, relative to at_fd.  Pass NULL to
  *         open at_fd itself.
+ * @param flags
+ *         Flags that control which directory entries are listed.
  * @return
  *         0 on success, or -1 on failure.
  */
-int bfs_opendir(struct bfs_dir *dir, int at_fd, const char *at_path);
+int bfs_opendir(struct bfs_dir *dir, int at_fd, const char *at_path, enum bfs_dir_flags flags);
 
 /**
  * Get the file descriptor for a directory.
diff --git a/src/eval.c b/src/eval.c
index e0dd97b..adf7a0b 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -427,7 +427,7 @@ bool eval_empty(const struct bfs_expr *expr, struct bfs_eval *state) {
 			return ret;
 		}
 
-		if (bfs_opendir(dir, ftwbuf->at_fd, ftwbuf->at_path) != 0) {
+		if (bfs_opendir(dir, ftwbuf->at_fd, ftwbuf->at_path, 0) != 0) {
 			eval_report_error(state);
 			return ret;
 		}
@@ -1517,8 +1517,8 @@ static int infer_fdlimit(const struct bfs_ctx *ctx, int limit) {
 		goto done;
 	}
 
-	if (bfs_opendir(dir, AT_FDCWD, "/proc/self/fd") != 0
-	    && bfs_opendir(dir, AT_FDCWD, "/dev/fd") != 0) {
+	if (bfs_opendir(dir, AT_FDCWD, "/proc/self/fd", 0) != 0
+	    && bfs_opendir(dir, AT_FDCWD, "/dev/fd", 0) != 0) {
 		goto done;
 	}
 
diff --git a/src/ioq.c b/src/ioq.c
index 04b9c0d..8c1bdbe 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -348,7 +348,7 @@ static void ioq_handle(struct ioq *ioq, struct ioq_ent *ent) {
 		break;
 
 	case IOQ_OPENDIR:
-		ret = bfs_opendir(ent->opendir.dir, ent->opendir.dfd, ent->opendir.path);
+		ret = bfs_opendir(ent->opendir.dir, ent->opendir.dfd, ent->opendir.path, ent->opendir.flags);
 		if (ret == 0) {
 			bfs_polldir(ent->opendir.dir);
 		}
@@ -505,7 +505,7 @@ static void ioq_ring_reap(struct ioq_ring_state *state) {
 				continue;
 			}
 
-			ent->ret = bfs_opendir(ent->opendir.dir, fd, NULL);
+			ent->ret = bfs_opendir(ent->opendir.dir, fd, NULL, ent->opendir.flags);
 			if (ent->ret == 0) {
 				// TODO: io_uring_prep_getdents()
 				bfs_polldir(ent->opendir.dir);
@@ -659,7 +659,7 @@ int ioq_close(struct ioq *ioq, int fd, void *ptr) {
 	return 0;
 }
 
-int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, void *ptr) {
+int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, enum bfs_dir_flags flags, void *ptr) {
 	struct ioq_ent *ent = ioq_request(ioq, IOQ_OPENDIR, ptr);
 	if (!ent) {
 		return -1;
@@ -669,6 +669,7 @@ int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path,
 	args->dir = dir;
 	args->dfd = dfd;
 	args->path = path;
+	args->flags = flags;
 
 	ioqq_push(ioq->pending, ent);
 	return 0;
diff --git a/src/ioq.h b/src/ioq.h
index 99c18c2..eab89ec 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -8,6 +8,7 @@
 #ifndef BFS_IOQ_H
 #define BFS_IOQ_H
 
+#include "dir.h"
 #include <stddef.h>
 
 /**
@@ -53,6 +54,7 @@ struct ioq_ent {
 			struct bfs_dir *dir;
 			int dfd;
 			const char *path;
+			enum bfs_dir_flags flags;
 		} opendir;
 		/** ioq_closedir() args. */
 		struct ioq_closedir {
@@ -103,12 +105,14 @@ int ioq_close(struct ioq *ioq, int fd, void *ptr);
  *         The base file descriptor.
  * @param path
  *         The path to open, relative to dfd.
+ * @param flags
+ *         Flags that control which directory entries are listed.
  * @param ptr
  *         An arbitrary pointer to associate with the request.
  * @return
  *         0 on success, or -1 on failure.
  */
-int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, void *ptr);
+int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, enum bfs_dir_flags flags, void *ptr);
 
 /**
  * Asynchronous bfs_closedir().
-- 
cgit v1.2.3


From 5fe11b94b38bfb4d43637e05ac24da0d7d72b9ea Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Tue, 7 Nov 2023 16:43:35 -0500
Subject: ioq: Implement a better non-blocking pop

---
 src/bftw.c |   2 +-
 src/ioq.c  | 276 +++++++++++++++++++++++++++++++++++++++++--------------------
 src/ioq.h  |  13 +--
 3 files changed, 189 insertions(+), 102 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/bftw.c b/src/bftw.c
index 5a55037..0b74cd9 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -588,7 +588,7 @@ static int bftw_ioq_pop(struct bftw_state *state, bool block) {
 		return -1;
 	}
 
-	struct ioq_ent *ent = block ? ioq_pop(ioq) : ioq_trypop(ioq);
+	struct ioq_ent *ent = ioq_pop(ioq, block);
 	if (!ent) {
 		return -1;
 	}
diff --git a/src/ioq.c b/src/ioq.c
index 8c1bdbe..244b2cc 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -1,6 +1,127 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+/**
+ * An asynchronous I/O queue implementation.
+ *
+ * struct ioq is composed of two separate queues:
+ *
+ *     struct ioqq *pending; // Pending I/O requests
+ *     struct ioqq *ready;   // Ready I/O responses
+ *
+ * Worker threads pop requests from `pending`, execute them, and push them back
+ * to the `ready` queue.  The main thread pushes requests to `pending` and pops
+ * them from `ready`.
+ *
+ * struct ioqq is a blocking MPMC queue (though it could be SPMC/MPSC for
+ * pending/ready respectively).  It is implemented as a circular buffer:
+ *
+ *     size_t mask;            // (1 << N) - 1
+ *     [padding]
+ *     size_t head;            // Writer index
+ *     [padding]
+ *     size_t tail;            // Reader index
+ *     [padding]
+ *     ioq_slot slots[1 << N]; // Queue contents
+ *
+ * Pushes are implemented with an unconditional
+ *
+ *     fetch_add(&ioqq->head, IOQ_STRIDE)
+ *
+ * which scales better on many architectures than compare-and-swap (see [1] for
+ * details).  Pops are implemented similarly.  We add IOQ_STRIDE rather than 1
+ * so that successive queue elements are on different cache lines, but the
+ * exposition below uses 1 for simplicity.
+ *
+ * Since the fetch-and-adds are unconditional, non-blocking readers can get
+ * ahead of writers:
+ *
+ *     Reader              Writer
+ *     ────────────────    ──────────────────────
+ *     head:     0 → 1
+ *     slots[0]: empty
+ *                         tail:     0     → 1
+ *                         slots[0]: empty → full
+ *     head:     1 → 2
+ *     slots[1]: empty!
+ *
+ * To avoid this, non-blocking reads (ioqq_pop(ioqq, false)) must mark the slots
+ * somehow so that writers can skip them:
+ *
+ *     Reader                     Writer
+ *     ───────────────────────    ───────────────────────
+ *     head:         0 → 1
+ *     slots[0]: empty → skip
+ *                                tail:         0 → 1
+ *                                slots[0]:  skip → empty
+ *                                tail:         1 → 2
+ *                                slots[1]: empty → full
+ *     head:         1 → 2
+ *     slots[1]:  full → empty
+ *
+ * As well, a reader might "lap" a writer (or another reader), so slots need to
+ * count how many times they should be skipped:
+ *
+ *     Reader                        Writer
+ *     ──────────────────────────    ─────────────────────────
+ *     head:          0 → 1
+ *     slots[0]:  empty → skip(1)
+ *     head:          1 → 2
+ *     slots[1]:  empty → skip(1)
+ *     ...
+ *     head:          M → 0
+ *     slots[M]:  empty → skip(1)
+ *     head:          0 → 1
+ *     slots[0]: skip(1 → 2)
+ *                                   tail:           0 → 1
+ *                                   slots[0]:  skip(2 → 1)
+ *                                   tail:           1 → 2
+ *                                   slots[1]: skip(1) → empty
+ *                                   ...
+ *                                   tail:           M → 0
+ *                                   slots[M]: skip(1) → empty
+ *                                   tail:           0 → 1
+ *                                   slots[0]: skip(1) → empty
+ *                                   tail:           1 → 2
+ *                                   slots[1]:   empty → full
+ *     head:          1 → 2
+ *     slots[1]:   full → empty
+ *
+ * As described in [1], this approach is susceptible to livelock if readers stay
+ * ahead of writers.  This is okay for us because we don't retry failed non-
+ * blocking reads.
+ *
+ * The slot representation uses tag bits to hold either a pointer or skip(N):
+ *
+ *     IOQ_SKIP (highest bit)    IOQ_BLOCKED (lowest bit)
+ *        ↓                         ↓
+ *        0 0 0       ...       0 0 0
+ *          └──────────┬──────────┘
+ *                     │
+ *                value bits
+ *
+ * If IOQ_SKIP is unset, the value bits hold a pointer (or zero/NULL for empty).
+ * If IOQ_SKIP is set, the value bits hold a negative skip count.  Writers can
+ * reduce the skip count by adding 1 to the value bits, and when the count hits
+ * zero, the carry will automatically clear IOQ_SKIP:
+ *
+ *     IOQ_SKIP                  IOQ_BLOCKED
+ *        ↓                         ↓
+ *        1 1 1       ...       1 0 0    skip(2)
+ *        1 1 1       ...       1 1 0    skip(1)
+ *        0 0 0       ...       0 0 0    empty
+ *
+ * The IOQ_BLOCKED flag is used to track sleeping waiters, futex-style.  To wait
+ * for a slot to change, waiters call ioq_slot_wait() which sets IOQ_BLOCKED and
+ * goes to sleep.  Whenever a slot is updated, if the old value had IOQ_BLOCKED
+ * set, ioq_slot_wake() must be called to wake up that waiter.
+ *
+ * Blocking/waking uses a pool of monitors (mutex, condition variable pairs).
+ * Slots are assigned round-robin to a monitor from the pool.
+ *
+ * [1]: https://arxiv.org/abs/2201.02179
+ */
+
 #include "ioq.h"
 #include "alloc.h"
 #include "atomic.h"
@@ -51,24 +172,15 @@ static void ioq_monitor_destroy(struct ioq_monitor *monitor) {
 /** A single entry in a command queue. */
 typedef atomic uintptr_t ioq_slot;
 
-/** Slot flag bit to indicate waiters. */
+/** Someone might be waiting on this slot. */
 #define IOQ_BLOCKED ((uintptr_t)1)
-bfs_static_assert(alignof(struct ioq_ent) > 1);
-
-/** Check if a slot has waiters. */
-static bool ioq_slot_blocked(uintptr_t value) {
-	return value & IOQ_BLOCKED;
-}
-
-/** Extract the pointer from a slot. */
-static struct ioq_ent *ioq_slot_ptr(uintptr_t value) {
-	return (struct ioq_ent *)(value & ~IOQ_BLOCKED);
-}
+/** The next push(es) should skip this slot. */
+#define IOQ_SKIP ((uintptr_t)1 << (UINTPTR_WIDTH - 1))
+/** Amount to add for an additional skip. */
+#define IOQ_SKIP_ONE (~IOQ_BLOCKED)
 
-/** Check if a slot is empty. */
-static bool ioq_slot_empty(uintptr_t value) {
-	return !ioq_slot_ptr(value);
-}
+// Need room for two flag bits
+bfs_static_assert(alignof(struct ioq_ent) > 2);
 
 /**
  * An MPMC queue of I/O commands.
@@ -205,80 +317,85 @@ static void ioq_slot_wake(struct ioqq *ioqq, ioq_slot *slot) {
 	cond_broadcast(&monitor->cond);
 }
 
-/** Get the next slot for writing. */
-static ioq_slot *ioqq_write(struct ioqq *ioqq) {
-	size_t i = fetch_add(&ioqq->head, IOQ_STRIDE, relaxed);
-	return &ioqq->slots[i & ioqq->slot_mask];
-}
-
 /** Push an entry into a slot. */
-static void ioq_slot_push(struct ioqq *ioqq, ioq_slot *slot, struct ioq_ent *ent) {
-	uintptr_t addr = (uintptr_t)ent;
-	bfs_assert(!ioq_slot_blocked(addr));
-
+static bool ioq_slot_push(struct ioqq *ioqq, ioq_slot *slot, struct ioq_ent *ent) {
 	uintptr_t prev = load(slot, relaxed);
-	do {
-		while (!ioq_slot_empty(prev)) {
+	while (true) {
+		uintptr_t next;
+		if (prev & IOQ_SKIP) {
+			// skip(1) → empty
+			// skip(n) → skip(n - 1)
+			next = (prev - IOQ_SKIP_ONE) & ~IOQ_BLOCKED;
+		} else if (prev > IOQ_BLOCKED) {
+			// full(ptr) → wait
 			prev = ioq_slot_wait(ioqq, slot, prev);
+			continue;
+		} else {
+			// empty → full(ptr)
+			next = (uintptr_t)ent >> 1;
 		}
-	} while (!compare_exchange_weak(slot, &prev, addr, release, relaxed));
 
-	if (ioq_slot_blocked(prev)) {
+		if (compare_exchange_weak(slot, &prev, next, release, relaxed)) {
+			break;
+		}
+	}
+
+	if (prev & IOQ_BLOCKED) {
 		ioq_slot_wake(ioqq, slot);
 	}
+
+	return !(prev & IOQ_SKIP);
 }
 
 /** Push an entry onto the queue. */
 static void ioqq_push(struct ioqq *ioqq, struct ioq_ent *ent) {
-	ioq_slot *slot = ioqq_write(ioqq);
-	ioq_slot_push(ioqq, slot, ent);
-}
-
-/** Get the next slot for reading. */
-static ioq_slot *ioqq_read(struct ioqq *ioqq) {
-	size_t i = fetch_add(&ioqq->tail, IOQ_STRIDE, relaxed);
-	return &ioqq->slots[i & ioqq->slot_mask];
+	while (true) {
+		size_t i = fetch_add(&ioqq->head, IOQ_STRIDE, relaxed);
+		ioq_slot *slot = &ioqq->slots[i & ioqq->slot_mask];
+		if (ioq_slot_push(ioqq, slot, ent)) {
+			break;
+		}
+	}
 }
 
 /** (Try to) pop an entry from a slot. */
 static struct ioq_ent *ioq_slot_pop(struct ioqq *ioqq, ioq_slot *slot, bool block) {
 	uintptr_t prev = load(slot, relaxed);
-	do {
-		while (ioq_slot_empty(prev)) {
-			if (block) {
-				prev = ioq_slot_wait(ioqq, slot, prev);
-			} else {
-				return NULL;
-			}
+	while (true) {
+		// empty     → skip(1)
+		// skip(n)   → skip(n + 1)
+		// full(ptr) → full(ptr - 1)
+		uintptr_t next = prev + IOQ_SKIP_ONE;
+		// skip(n)   → ~IOQ_BLOCKED
+		// full(ptr) → 0
+		next &= (next & IOQ_SKIP) ? ~IOQ_BLOCKED : 0;
+
+		if (block && next) {
+			prev = ioq_slot_wait(ioqq, slot, prev);
+			continue;
+		}
+
+		if (compare_exchange_weak(slot, &prev, next, acquire, relaxed)) {
+			break;
 		}
-	} while (!compare_exchange_weak(slot, &prev, 0, acquire, relaxed));
+	}
 
-	if (ioq_slot_blocked(prev)) {
+	if (prev & IOQ_BLOCKED) {
 		ioq_slot_wake(ioqq, slot);
 	}
 
-	return ioq_slot_ptr(prev);
+	// empty     → 0
+	// skip(n)   → 0
+	// full(ptr) → ptr
+	prev &= (prev & IOQ_SKIP) ? 0 : ~IOQ_BLOCKED;
+	return (struct ioq_ent *)(prev << 1);
 }
 
 /** Pop an entry from the queue. */
-static struct ioq_ent *ioqq_pop(struct ioqq *ioqq) {
-	ioq_slot *slot = ioqq_read(ioqq);
-	return ioq_slot_pop(ioqq, slot, true);
-}
-
-/** Pop an entry from the queue if one is available. */
-static struct ioq_ent *ioqq_trypop(struct ioqq *ioqq) {
-	size_t i = load(&ioqq->tail, relaxed);
+static struct ioq_ent *ioqq_pop(struct ioqq *ioqq, bool block) {
+	size_t i = fetch_add(&ioqq->tail, IOQ_STRIDE, relaxed);
 	ioq_slot *slot = &ioqq->slots[i & ioqq->slot_mask];
-
-	struct ioq_ent *ret = ioq_slot_pop(ioqq, slot, false);
-	if (ret) {
-		size_t j = exchange(&ioqq->tail, i + IOQ_STRIDE, relaxed);
-		bfs_assert(j == i, "Detected multiple consumers");
-		(void)j;
-	}
-
-	return ret;
+	return ioq_slot_pop(ioqq, slot, block);
 }
 
 /** Sentinel stop command. */
@@ -378,8 +495,6 @@ struct ioq_ring_state {
 	struct ioq *ioq;
 	/** The io_uring. */
 	struct io_uring *ring;
-	/** The current ioq->pending slot. */
-	ioq_slot *slot;
 	/** Number of prepped, unsubmitted SQEs. */
 	size_t prepped;
 	/** Number of submitted, unreaped SQEs. */
@@ -394,20 +509,9 @@ static struct ioq_ent *ioq_ring_pop(struct ioq_ring_state *state) {
 		return NULL;
 	}
 
-	// Advance to the next slot if necessary
-	struct ioq *ioq = state->ioq;
-	if (!state->slot) {
-		state->slot = ioqq_read(ioq->pending);
-	}
-
 	// Block if we have nothing else to do
 	bool block = !state->prepped && !state->submitted;
-	struct ioq_ent *ret = ioq_slot_pop(ioq->pending, state->slot, block);
-
-	if (ret) {
-		// Got an entry, move to the next slot next time
-		state->slot = NULL;
-	}
+	struct ioq_ent *ret = ioqq_pop(state->ioq->pending, block);
 
 	if (ret == &IOQ_STOP) {
 		state->stop = true;
@@ -536,7 +640,7 @@ static void ioq_sync_work(struct ioq_thread *thread) {
 	struct ioq *ioq = thread->parent;
 
 	while (true) {
-		struct ioq_ent *ent = ioqq_pop(ioq->pending);
+		struct ioq_ent *ent = ioqq_pop(ioq->pending, true);
 		if (ent == &IOQ_STOP) {
 			break;
 		}
@@ -687,20 +791,12 @@ int ioq_closedir(struct ioq *ioq, struct bfs_dir *dir, void *ptr) {
 	return 0;
 }
 
-struct ioq_ent *ioq_pop(struct ioq *ioq) {
-	if (ioq->size == 0) {
-		return NULL;
-	}
-
-	return ioqq_pop(ioq->ready);
-}
-
-struct ioq_ent *ioq_trypop(struct ioq *ioq) {
+struct ioq_ent *ioq_pop(struct ioq *ioq, bool block) {
 	if (ioq->size == 0) {
 		return NULL;
 	}
 
-	return ioqq_trypop(ioq->ready);
+	return ioqq_pop(ioq->ready, block);
 }
 
 void ioq_free(struct ioq *ioq, struct ioq_ent *ent) {
diff --git a/src/ioq.h b/src/ioq.h
index eab89ec..87727cb 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -8,6 +8,7 @@
 #ifndef BFS_IOQ_H
 #define BFS_IOQ_H
 
+#include "config.h"
 #include "dir.h"
 #include <stddef.h>
 
@@ -136,17 +137,7 @@ int ioq_closedir(struct ioq *ioq, struct bfs_dir *dir, void *ptr);
  * @return
  *         The next response, or NULL.
  */
-struct ioq_ent *ioq_pop(struct ioq *ioq);
-
-/**
- * Pop a response from the queue, without blocking.
- *
- * @param ioq
- *         The I/O queue.
- * @return
- *         The next response, or NULL.
- */
-struct ioq_ent *ioq_trypop(struct ioq *ioq);
+struct ioq_ent *ioq_pop(struct ioq *ioq, bool block);
 
 /**
  * Free a queue entry.
-- 
cgit v1.2.3


From e766015d60c927aae03b8e43d956c6976c16b2ba Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sat, 13 Jan 2024 15:54:46 -0500
Subject: ioq: Use the negative errno convention

---
 src/bfstd.c |  9 +++++++++
 src/bfstd.h | 10 ++++++++++
 src/bftw.c  |  2 +-
 src/ioq.c   | 32 +++++++++++---------------------
 src/ioq.h   |  6 ++----
 5 files changed, 33 insertions(+), 26 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/bfstd.c b/src/bfstd.c
index 15e8667..0a9b87c 100644
--- a/src/bfstd.c
+++ b/src/bfstd.c
@@ -59,6 +59,15 @@ bool errno_is_like(int category) {
 	return error_is_like(errno, category);
 }
 
+int try(int ret) {
+	if (ret >= 0) {
+		return ret;
+	} else {
+		bfs_assert(errno > 0, "errno should be positive, was %d\n", errno);
+		return -errno;
+	}
+}
+
 char *xdirname(const char *path) {
 	size_t i = xbaseoff(path);
 
diff --git a/src/bfstd.h b/src/bfstd.h
index 8953b9b..d160c88 100644
--- a/src/bfstd.h
+++ b/src/bfstd.h
@@ -63,6 +63,16 @@ bool error_is_like(int error, int category);
  */
 bool errno_is_like(int category);
 
+/**
+ * Apply the "negative errno" convention.
+ *
+ * @param ret
+ *         The return value of the attempted operation.
+ * @return
+ *         ret, if non-negative, otherwise -errno.
+ */
+int try(int ret);
+
 #include <fcntl.h>
 
 #ifndef O_EXEC
diff --git a/src/bftw.c b/src/bftw.c
index 49f07df..952b090 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -621,7 +621,7 @@ static int bftw_ioq_pop(struct bftw_state *state, bool block) {
 		}
 
 		dir = ent->opendir.dir;
-		if (ent->ret == 0) {
+		if (ent->result >= 0) {
 			bftw_file_set_dir(cache, file, dir);
 		} else {
 			bftw_freedir(cache, dir);
diff --git a/src/ioq.c b/src/ioq.c
index 2739338..89ebb3e 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -455,42 +455,35 @@ static bool ioq_check_cancel(struct ioq *ioq, struct ioq_ent *ent) {
 		return false;
 	}
 
-	ent->ret = -1;
-	ent->error = EINTR;
+	ent->result = -EINTR;
 	ioqq_push(ioq->ready, ent);
 	return true;
 }
 
 /** Handle a single request synchronously. */
 static void ioq_handle(struct ioq *ioq, struct ioq_ent *ent) {
-	int ret;
-
 	switch (ent->op) {
 	case IOQ_CLOSE:
-		ret = xclose(ent->close.fd);
+		ent->result = try(xclose(ent->close.fd));
 		break;
 
 	case IOQ_OPENDIR:
-		ret = bfs_opendir(ent->opendir.dir, ent->opendir.dfd, ent->opendir.path, ent->opendir.flags);
-		if (ret == 0) {
+		ent->result = try(bfs_opendir(ent->opendir.dir, ent->opendir.dfd, ent->opendir.path, ent->opendir.flags));
+		if (ent->result >= 0) {
 			bfs_polldir(ent->opendir.dir);
 		}
 		break;
 
 	case IOQ_CLOSEDIR:
-		ret = bfs_closedir(ent->closedir.dir);
+		ent->result = try(bfs_closedir(ent->closedir.dir));
 		break;
 
 	default:
 		bfs_bug("Unknown ioq_op %d", (int)ent->op);
-		ret = -1;
-		errno = ENOSYS;
+		ent->result = -ENOSYS;
 		break;
 	}
 
-	ent->ret = ret;
-	ent->error = ret == 0 ? 0 : errno;
-
 	ioqq_push(ioq->ready, ent);
 }
 
@@ -603,24 +596,21 @@ static void ioq_ring_reap(struct ioq_ring_state *state) {
 		}
 
 		struct ioq_ent *ent = io_uring_cqe_get_data(cqe);
-		ent->ret = cqe->res >= 0 ? cqe->res : -1;
-		ent->error = cqe->res < 0 ? -cqe->res : 0;
+		ent->result = cqe->res;
 		io_uring_cqe_seen(ring, cqe);
 		--state->submitted;
 
-		if (ent->op == IOQ_OPENDIR && ent->ret >= 0) {
-			int fd = ent->ret;
+		if (ent->op == IOQ_OPENDIR && ent->result >= 0) {
+			int fd = ent->result;
 			if (ioq_check_cancel(ioq, ent)) {
 				xclose(fd);
 				continue;
 			}
 
-			ent->ret = bfs_opendir(ent->opendir.dir, fd, NULL, ent->opendir.flags);
-			if (ent->ret == 0) {
+			ent->result = try(bfs_opendir(ent->opendir.dir, fd, NULL, ent->opendir.flags));
+			if (ent->result >= 0) {
 				// TODO: io_uring_prep_getdents()
 				bfs_polldir(ent->opendir.dir);
-			} else {
-				ent->error = errno;
 			}
 		}
 
diff --git a/src/ioq.h b/src/ioq.h
index 87727cb..e1e5052 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -36,10 +36,8 @@ struct ioq_ent {
 	/** The I/O operation. */
 	enum ioq_op op;
 
-	/** The return value of the operation. */
-	int ret;
-	/** The error code, if the operation failed. */
-	int error;
+	/** The return value (on success) or negative error code (on failure). */
+	int result;
 
 	/** Arbitrary user data. */
 	void *ptr;
-- 
cgit v1.2.3


From 18597572f62ab18824df6bab6c30d2b645921969 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Wed, 23 Aug 2023 13:10:10 -0400
Subject: ioq: Implement ioq_stat()

---
 src/bftw.c |   3 ++
 src/ioq.c  | 100 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-------
 src/ioq.h  |  31 +++++++++++++++++++
 3 files changed, 124 insertions(+), 10 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/bftw.c b/src/bftw.c
index 952b090..02dd051 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -631,6 +631,9 @@ static int bftw_ioq_pop(struct bftw_state *state, bool block) {
 			SLIST_APPEND(&state->to_read, file, to_read);
 		}
 		break;
+
+	case IOQ_STAT:
+		break;
 	}
 
 	ioq_free(ioq, ent);
diff --git a/src/ioq.c b/src/ioq.c
index 3d32dfe..3172f0a 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -131,6 +131,7 @@
 #include "diag.h"
 #include "dir.h"
 #include "sanity.h"
+#include "stat.h"
 #include "thread.h"
 #include <assert.h>
 #include <errno.h>
@@ -432,6 +433,10 @@ struct ioq {
 
 	/** ioq_ent arena. */
 	struct arena ents;
+#if BFS_USE_LIBURING && BFS_USE_STATX
+	/** struct statx arena. */
+	struct arena xbufs;
+#endif
 
 	/** Pending I/O requests. */
 	struct ioqq *pending;
@@ -479,6 +484,12 @@ static void ioq_dispatch_sync(struct ioq *ioq, struct ioq_ent *ent) {
 		case IOQ_CLOSEDIR:
 			ent->result = try(bfs_closedir(ent->closedir.dir));
 			return;
+
+		case IOQ_STAT: {
+			struct ioq_stat *args = &ent->stat;
+			ent->result = try(bfs_stat(args->dfd, args->path, args->flags, args->buf));
+			return;
+		}
 	}
 
 	bfs_bug("Unknown ioq_op %d", (int)ent->op);
@@ -549,6 +560,17 @@ static struct io_uring_sqe *ioq_dispatch_async(struct io_uring *ring, struct ioq
 			io_uring_prep_close(sqe, bfs_unwrapdir(ent->closedir.dir));
 #endif
 			return sqe;
+
+		case IOQ_STAT: {
+#if BFS_USE_STATX
+			sqe = io_uring_get_sqe(ring);
+			struct ioq_stat *args = &ent->stat;
+			int flags = bfs_statx_flags(args->flags);
+			unsigned int mask = STATX_BASIC_STATS | STATX_BTIME;
+			io_uring_prep_statx(sqe, args->dfd, args->path, flags, mask, args->xbuf);
+#endif
+			return sqe;
+		}
 	}
 
 	bfs_bug("Unknown ioq_op %d", (int)ent->op);
@@ -597,21 +619,41 @@ static void ioq_reap_cqe(struct ioq_ring_state *state, struct io_uring_cqe *cqe)
 	io_uring_cqe_seen(ring, cqe);
 	--state->submitted;
 
-	if (ent->op == IOQ_OPENDIR && ent->result >= 0) {
-		int fd = ent->result;
-		if (ioq_check_cancel(ioq, ent)) {
-			xclose(fd);
-			return;
+	if (ent->result < 0) {
+		goto push;
+	}
+
+	switch (ent->op) {
+		case IOQ_OPENDIR: {
+			int fd = ent->result;
+			if (ioq_check_cancel(ioq, ent)) {
+				xclose(fd);
+				return;
+			}
+
+			struct ioq_opendir *args = &ent->opendir;
+			ent->result = try(bfs_opendir(args->dir, fd, NULL, args->flags));
+			if (ent->result >= 0) {
+				// TODO: io_uring_prep_getdents()
+				bfs_polldir(args->dir);
+			}
+
+			break;
 		}
 
-		struct ioq_opendir *args = &ent->opendir;
-		ent->result = try(bfs_opendir(args->dir, fd, NULL, args->flags));
-		if (ent->result >= 0) {
-			// TODO: io_uring_prep_getdents()
-			bfs_polldir(args->dir);
+#if BFS_USE_STATX
+		case IOQ_STAT: {
+			struct ioq_stat *args = &ent->stat;
+			ent->result = try(bfs_statx_convert(args->buf, args->xbuf));
+			break;
 		}
+#endif
+
+		default:
+			break;
 	}
 
+push:
 	ioqq_push(ioq->ready, ent);
 }
 
@@ -689,8 +731,13 @@ struct ioq *ioq_create(size_t depth, size_t nthreads) {
 	}
 
 	ioq->depth = depth;
+
 	ARENA_INIT(&ioq->ents, struct ioq_ent);
 
+#if BFS_USE_LIBURING && BFS_USE_STATX
+	ARENA_INIT(&ioq->xbufs, struct statx);
+#endif
+
 	ioq->pending = ioqq_create(depth);
 	if (!ioq->pending) {
 		goto fail;
@@ -807,6 +854,30 @@ int ioq_closedir(struct ioq *ioq, struct bfs_dir *dir, void *ptr) {
 	return 0;
 }
 
+int ioq_stat(struct ioq *ioq, int dfd, const char *path, enum bfs_stat_flags flags, struct bfs_stat *buf, void *ptr) {
+	struct ioq_ent *ent = ioq_request(ioq, IOQ_STAT, ptr);
+	if (!ent) {
+		return -1;
+	}
+
+	struct ioq_stat *args = &ent->stat;
+	args->dfd = dfd;
+	args->path = path;
+	args->flags = flags;
+	args->buf = buf;
+
+#if BFS_USE_LIBURING && BFS_USE_STATX
+	args->xbuf = arena_alloc(&ioq->xbufs);
+	if (!args->xbuf) {
+		ioq_free(ioq, ent);
+		return -1;
+	}
+#endif
+
+	ioqq_push(ioq->pending, ent);
+	return 0;
+}
+
 struct ioq_ent *ioq_pop(struct ioq *ioq, bool block) {
 	if (ioq->size == 0) {
 		return NULL;
@@ -819,6 +890,12 @@ void ioq_free(struct ioq *ioq, struct ioq_ent *ent) {
 	bfs_assert(ioq->size > 0);
 	--ioq->size;
 
+#if BFS_USE_LIBURING && BFS_USE_STATX
+	if (ent->op == IOQ_STAT) {
+		arena_free(&ioq->xbufs, ent->stat.xbuf);
+	}
+#endif
+
 	arena_free(&ioq->ents, ent);
 }
 
@@ -848,6 +925,9 @@ void ioq_destroy(struct ioq *ioq) {
 	ioqq_destroy(ioq->ready);
 	ioqq_destroy(ioq->pending);
 
+#if BFS_USE_LIBURING && BFS_USE_STATX
+	arena_destroy(&ioq->xbufs);
+#endif
 	arena_destroy(&ioq->ents);
 
 	free(ioq);
diff --git a/src/ioq.h b/src/ioq.h
index e1e5052..77aabaa 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -10,6 +10,7 @@
 
 #include "config.h"
 #include "dir.h"
+#include "stat.h"
 #include <stddef.h>
 
 /**
@@ -27,6 +28,8 @@ enum ioq_op {
 	IOQ_OPENDIR,
 	/** ioq_closedir(). */
 	IOQ_CLOSEDIR,
+	/** ioq_stat(). */
+	IOQ_STAT,
 };
 
 /**
@@ -59,6 +62,14 @@ struct ioq_ent {
 		struct ioq_closedir {
 			struct bfs_dir *dir;
 		} closedir;
+		/** ioq_stat() args. */
+		struct ioq_stat {
+			int dfd;
+			const char *path;
+			enum bfs_stat_flags flags;
+			struct bfs_stat *buf;
+			void *xbuf;
+		} stat;
 	};
 };
 
@@ -127,6 +138,26 @@ int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path,
  */
 int ioq_closedir(struct ioq *ioq, struct bfs_dir *dir, void *ptr);
 
+/**
+ * Asynchronous bfs_stat().
+ *
+ * @param ioq
+ *         The I/O queue.
+ * @param dfd
+ *         The base file descriptor.
+ * @param path
+ *         The path to stat, relative to dfd.
+ * @param flags
+ *         Flags that affect the lookup.
+ * @param buf
+ *         A place to store the stat buffer, if successful.
+ * @param ptr
+ *         An arbitrary pointer to associate with the request.
+ * @return
+ *         0 on success, or -1 on failure.
+ */
+int ioq_stat(struct ioq *ioq, int dfd, const char *path, enum bfs_stat_flags flags, struct bfs_stat *buf, void *ptr);
+
 /**
  * Pop a response from the queue.
  *
-- 
cgit v1.2.3


From 2fe4c9922bd02e0ec4bca8151cbff1a0bcf29dcf Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Wed, 14 Feb 2024 11:36:03 -0500
Subject: ioq: Pack ioq_ent args structs

---
 src/ioq.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/ioq.h b/src/ioq.h
index 77aabaa..30e90e0 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -54,8 +54,8 @@ struct ioq_ent {
 		/** ioq_opendir() args. */
 		struct ioq_opendir {
 			struct bfs_dir *dir;
-			int dfd;
 			const char *path;
+			int dfd;
 			enum bfs_dir_flags flags;
 		} opendir;
 		/** ioq_closedir() args. */
@@ -64,11 +64,11 @@ struct ioq_ent {
 		} closedir;
 		/** ioq_stat() args. */
 		struct ioq_stat {
-			int dfd;
 			const char *path;
-			enum bfs_stat_flags flags;
 			struct bfs_stat *buf;
 			void *xbuf;
+			int dfd;
+			enum bfs_stat_flags flags;
 		} stat;
 	};
 };
-- 
cgit v1.2.3


From c749c11b04444ca40941dd2ddc5802faed148f6a Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Fri, 16 Feb 2024 13:44:04 -0500
Subject: ioq: Ensure ioq_ent is sufficiently aligned

The natural alignment of struct ioq_ent is only 2 on m68k, so over-align
it to at least 4 bytes on all platforms.

Link: https://buildd.debian.org/status/fetch.php?pkg=bfs&arch=m68k&ver=3.1-1&stamp=1707699583
---
 src/ioq.c | 2 +-
 src/ioq.h | 9 ++++++++-
 2 files changed, 9 insertions(+), 2 deletions(-)

(limited to 'src/ioq.h')

diff --git a/src/ioq.c b/src/ioq.c
index cf0b927..f23b62f 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -177,7 +177,7 @@ typedef atomic uintptr_t ioq_slot;
 #define IOQ_SKIP_ONE (~IOQ_BLOCKED)
 
 // Need room for two flag bits
-bfs_static_assert(alignof(struct ioq_ent) > 2);
+bfs_static_assert(alignof(struct ioq_ent) >= (1 << 2));
 
 /**
  * An MPMC queue of I/O commands.
diff --git a/src/ioq.h b/src/ioq.h
index 30e90e0..818eea6 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -32,12 +32,19 @@ enum ioq_op {
 	IOQ_STAT,
 };
 
+/**
+ * The I/O queue implementation needs two tag bits in each pointer to a struct
+ * ioq_ent, so we need to ensure at least 4-byte alignment.  The natural
+ * alignment is enough on most architectures, but not m68k, so over-align it.
+ */
+#define IOQ_ENT_ALIGN alignas(4)
+
 /**
  * An I/O queue entry.
  */
 struct ioq_ent {
 	/** The I/O operation. */
-	enum ioq_op op;
+	IOQ_ENT_ALIGN enum ioq_op op;
 
 	/** The return value (on success) or negative error code (on failure). */
 	int result;
-- 
cgit v1.2.3


From c66379749f423413913b406609dfe9311ba6e555 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Thu, 18 Apr 2024 14:53:56 -0400
Subject: Rename config.h to prelude.h

---
 src/alloc.c    |   2 +-
 src/alloc.h    |   2 +-
 src/bar.c      |   2 +-
 src/bfstd.c    |   2 +-
 src/bfstd.h    |   2 +-
 src/bftw.c     |   2 +-
 src/bit.h      |   2 +-
 src/color.c    |   2 +-
 src/color.h    |   2 +-
 src/config.h   | 377 ---------------------------------------------------------
 src/ctx.h      |   2 +-
 src/diag.c     |   2 +-
 src/diag.h     |   2 +-
 src/dir.c      |   2 +-
 src/dstring.c  |   2 +-
 src/dstring.h  |   2 +-
 src/eval.c     |   2 +-
 src/eval.h     |   2 +-
 src/exec.c     |   2 +-
 src/expr.h     |   2 +-
 src/fsade.c    |   2 +-
 src/fsade.h    |   2 +-
 src/ioq.c      |   2 +-
 src/ioq.h      |   2 +-
 src/main.c     |   4 +-
 src/mtab.c     |   2 +-
 src/mtab.h     |   2 +-
 src/opt.c      |   2 +-
 src/parse.c    |   2 +-
 src/prelude.h  | 377 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/printf.c   |   2 +-
 src/pwcache.c  |   2 +-
 src/sanity.h   |   2 +-
 src/stat.c     |   2 +-
 src/stat.h     |   2 +-
 src/thread.c   |   2 +-
 src/thread.h   |   2 +-
 src/trie.c     |   2 +-
 src/xregex.c   |   2 +-
 src/xspawn.c   |   2 +-
 src/xspawn.h   |   2 +-
 src/xtime.c    |   2 +-
 tests/alloc.c  |   2 +-
 tests/bfstd.c  |   2 +-
 tests/bit.c    |   2 +-
 tests/ioq.c    |   2 +-
 tests/main.c   |   2 +-
 tests/tests.h  |   2 +-
 tests/trie.c   |   2 +-
 tests/xspawn.c |   2 +-
 tests/xtime.c  |   2 +-
 tests/xtouch.c |   2 +-
 52 files changed, 428 insertions(+), 428 deletions(-)
 delete mode 100644 src/config.h
 create mode 100644 src/prelude.h

(limited to 'src/ioq.h')

diff --git a/src/alloc.c b/src/alloc.c
index b65d0c5..ec8608f 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -1,9 +1,9 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "alloc.h"
 #include "bit.h"
-#include "config.h"
 #include "diag.h"
 #include "sanity.h"
 #include <errno.h>
diff --git a/src/alloc.h b/src/alloc.h
index ae055bc..095134a 100644
--- a/src/alloc.h
+++ b/src/alloc.h
@@ -8,7 +8,7 @@
 #ifndef BFS_ALLOC_H
 #define BFS_ALLOC_H
 
-#include "config.h"
+#include "prelude.h"
 #include <errno.h>
 #include <stddef.h>
 #include <stdlib.h>
diff --git a/src/bar.c b/src/bar.c
index 8ab4112..184d9a0 100644
--- a/src/bar.c
+++ b/src/bar.c
@@ -1,11 +1,11 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "bar.h"
 #include "atomic.h"
 #include "bfstd.h"
 #include "bit.h"
-#include "config.h"
 #include "dstring.h"
 #include <errno.h>
 #include <fcntl.h>
diff --git a/src/bfstd.c b/src/bfstd.c
index 2499f00..e1b4804 100644
--- a/src/bfstd.c
+++ b/src/bfstd.c
@@ -1,9 +1,9 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "bfstd.h"
 #include "bit.h"
-#include "config.h"
 #include "diag.h"
 #include "sanity.h"
 #include "thread.h"
diff --git a/src/bfstd.h b/src/bfstd.h
index fc22971..42f5d5b 100644
--- a/src/bfstd.h
+++ b/src/bfstd.h
@@ -8,7 +8,7 @@
 #ifndef BFS_BFSTD_H
 #define BFS_BFSTD_H
 
-#include "config.h"
+#include "prelude.h"
 #include "sanity.h"
 #include <stddef.h>
 
diff --git a/src/bftw.c b/src/bftw.c
index 6130c44..c4d3c17 100644
--- a/src/bftw.c
+++ b/src/bftw.c
@@ -18,10 +18,10 @@
  *   various helper functions to take fewer parameters.
  */
 
+#include "prelude.h"
 #include "bftw.h"
 #include "alloc.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include "dir.h"
 #include "dstring.h"
diff --git a/src/bit.h b/src/bit.h
index 69df21e..17cfbcf 100644
--- a/src/bit.h
+++ b/src/bit.h
@@ -8,7 +8,7 @@
 #ifndef BFS_BIT_H
 #define BFS_BIT_H
 
-#include "config.h"
+#include "prelude.h"
 #include <limits.h>
 #include <stdint.h>
 
diff --git a/src/color.c b/src/color.c
index 8c32a68..f004bf2 100644
--- a/src/color.c
+++ b/src/color.c
@@ -1,11 +1,11 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "color.h"
 #include "alloc.h"
 #include "bfstd.h"
 #include "bftw.h"
-#include "config.h"
 #include "diag.h"
 #include "dir.h"
 #include "dstring.h"
diff --git a/src/color.h b/src/color.h
index e3e7973..3278cd6 100644
--- a/src/color.h
+++ b/src/color.h
@@ -8,7 +8,7 @@
 #ifndef BFS_COLOR_H
 #define BFS_COLOR_H
 
-#include "config.h"
+#include "prelude.h"
 #include "dstring.h"
 #include <stdio.h>
 
diff --git a/src/config.h b/src/config.h
deleted file mode 100644
index 2eff1fc..0000000
--- a/src/config.h
+++ /dev/null
@@ -1,377 +0,0 @@
-// Copyright © Tavian Barnes <tavianator@tavianator.com>
-// SPDX-License-Identifier: 0BSD
-
-/**
- * Configuration and feature/platform detection.
- */
-
-#ifndef BFS_CONFIG_H
-#define BFS_CONFIG_H
-
-// Possible __STDC_VERSION__ values
-
-#define C95 199409L
-#define C99 199901L
-#define C11 201112L
-#define C17 201710L
-#define C23 202311L
-
-#include <stddef.h>
-
-#if __STDC_VERSION__ < C23
-#  include <stdalign.h>
-#  include <stdbool.h>
-#  include <stdnoreturn.h>
-#endif
-
-// bfs packaging configuration
-
-#ifndef BFS_COMMAND
-#  define BFS_COMMAND "bfs"
-#endif
-#ifndef BFS_HOMEPAGE
-#  define BFS_HOMEPAGE "https://tavianator.com/projects/bfs.html"
-#endif
-
-// This is a symbol instead of a literal so we don't have to rebuild everything
-// when the version number changes
-extern const char bfs_version[];
-
-// Check for system headers
-
-#ifdef __has_include
-
-#if __has_include(<mntent.h>)
-#  define BFS_HAS_MNTENT_H true
-#endif
-#if __has_include(<paths.h>)
-#  define BFS_HAS_PATHS_H true
-#endif
-#if __has_include(<sys/acl.h>)
-#  define BFS_HAS_SYS_ACL_H true
-#endif
-#if __has_include(<sys/capability.h>)
-#  define BFS_HAS_SYS_CAPABILITY_H true
-#endif
-#if __has_include(<sys/extattr.h>)
-#  define BFS_HAS_SYS_EXTATTR_H true
-#endif
-#if __has_include(<sys/mkdev.h>)
-#  define BFS_HAS_SYS_MKDEV_H true
-#endif
-#if __has_include(<sys/param.h>)
-#  define BFS_HAS_SYS_PARAM_H true
-#endif
-#if __has_include(<sys/sysmacros.h>)
-#  define BFS_HAS_SYS_SYSMACROS_H true
-#endif
-#if __has_include(<sys/xattr.h>)
-#  define BFS_HAS_SYS_XATTR_H true
-#endif
-#if __has_include(<threads.h>)
-#  define BFS_HAS_THREADS_H true
-#endif
-#if __has_include(<util.h>)
-#  define BFS_HAS_UTIL_H true
-#endif
-
-#else // !__has_include
-
-#define BFS_HAS_MNTENT_H __GLIBC__
-#define BFS_HAS_PATHS_H true
-#define BFS_HAS_SYS_ACL_H true
-#define BFS_HAS_SYS_CAPABILITY_H __linux__
-#define BFS_HAS_SYS_EXTATTR_H __FreeBSD__
-#define BFS_HAS_SYS_MKDEV_H false
-#define BFS_HAS_SYS_PARAM_H true
-#define BFS_HAS_SYS_SYSMACROS_H __GLIBC__
-#define BFS_HAS_SYS_XATTR_H __linux__
-#define BFS_HAS_THREADS_H (!__STDC_NO_THREADS__)
-#define BFS_HAS_UTIL_H __NetBSD__
-
-#endif // !__has_include
-
-#ifndef BFS_USE_MNTENT_H
-#  define BFS_USE_MNTENT_H BFS_HAS_MNTENT_H
-#endif
-#ifndef BFS_USE_PATHS_H
-#  define BFS_USE_PATHS_H BFS_HAS_PATHS_H
-#endif
-#ifndef BFS_USE_SYS_ACL_H
-#  define BFS_USE_SYS_ACL_H (BFS_HAS_SYS_ACL_H && !__illumos__ && (!__linux__ || BFS_USE_LIBACL))
-#endif
-#ifndef BFS_USE_SYS_CAPABILITY_H
-#  define BFS_USE_SYS_CAPABILITY_H (BFS_HAS_SYS_CAPABILITY_H && !__FreeBSD__ && (!__linux__ || BFS_USE_LIBCAP))
-#endif
-#ifndef BFS_USE_SYS_EXTATTR_H
-#  define BFS_USE_SYS_EXTATTR_H (BFS_HAS_SYS_EXTATTR_H && !__DragonFly__)
-#endif
-#ifndef BFS_USE_SYS_MKDEV_H
-#  define BFS_USE_SYS_MKDEV_H BFS_HAS_SYS_MKDEV_H
-#endif
-#ifndef BFS_USE_SYS_PARAM_H
-#  define BFS_USE_SYS_PARAM_H BFS_HAS_SYS_PARAM_H
-#endif
-#ifndef BFS_USE_SYS_SYSMACROS_H
-#  define BFS_USE_SYS_SYSMACROS_H BFS_HAS_SYS_SYSMACROS_H
-#endif
-#ifndef BFS_USE_SYS_XATTR_H
-#  define BFS_USE_SYS_XATTR_H BFS_HAS_SYS_XATTR_H
-#endif
-#ifndef BFS_USE_THREADS_H
-#  define BFS_USE_THREADS_H BFS_HAS_THREADS_H
-#endif
-#ifndef BFS_USE_UTIL_H
-#  define BFS_USE_UTIL_H BFS_HAS_UTIL_H
-#endif
-
-// Stub out feature detection on old/incompatible compilers
-
-#ifndef __has_feature
-#  define __has_feature(feat) false
-#endif
-
-#ifndef __has_c_attribute
-#  define __has_c_attribute(attr) false
-#endif
-
-#ifndef __has_attribute
-#  define __has_attribute(attr) false
-#endif
-
-// Platform detection
-
-// Get the definition of BSD if available
-#if BFS_USE_SYS_PARAM_H
-#  include <sys/param.h>
-#endif
-
-#ifndef __GLIBC_PREREQ
-#  define __GLIBC_PREREQ(maj, min) false
-#endif
-
-#ifndef __NetBSD_Prereq__
-#  define __NetBSD_Prereq__(maj, min, patch) false
-#endif
-
-// Fundamental utilities
-
-/**
- * Get the length of an array.
- */
-#define countof(array) (sizeof(array) / sizeof(0[array]))
-
-/**
- * False sharing/destructive interference/largest cache line size.
- */
-#ifdef __GCC_DESTRUCTIVE_SIZE
-#  define FALSE_SHARING_SIZE __GCC_DESTRUCTIVE_SIZE
-#else
-#  define FALSE_SHARING_SIZE 64
-#endif
-
-/**
- * True sharing/constructive interference/smallest cache line size.
- */
-#ifdef __GCC_CONSTRUCTIVE_SIZE
-#  define TRUE_SHARING_SIZE __GCC_CONSTRUCTIVE_SIZE
-#else
-#  define TRUE_SHARING_SIZE 64
-#endif
-
-/**
- * Alignment specifier that avoids false sharing.
- */
-#define cache_align alignas(FALSE_SHARING_SIZE)
-
-#if __COSMOPOLITAN__
-typedef long double max_align_t;
-#endif
-
-// Wrappers for attributes
-
-/**
- * Silence warnings about switch/case fall-throughs.
- */
-#if __has_attribute(fallthrough)
-#  define fallthru __attribute__((fallthrough))
-#else
-#  define fallthru ((void)0)
-#endif
-
-/**
- * Silence warnings about unused declarations.
- */
-#if __has_attribute(unused)
-#  define attr_maybe_unused __attribute__((unused))
-#else
-#  define attr_maybe_unused
-#endif
-
-/**
- * Warn if a value is unused.
- */
-#if __has_attribute(warn_unused_result)
-#  define attr_nodiscard __attribute__((warn_unused_result))
-#else
-#  define attr_nodiscard
-#endif
-
-/**
- * Hint to avoid inlining a function.
- */
-#if __has_attribute(noinline)
-#  define attr_noinline __attribute__((noinline))
-#else
-#  define attr_noinline
-#endif
-
-/**
- * Hint that a function is unlikely to be called.
- */
-#if __has_attribute(cold)
-#  define attr_cold attr_noinline __attribute__((cold))
-#else
-#  define attr_cold attr_noinline
-#endif
-
-/**
- * Adds compiler warnings for bad printf()-style function calls, if supported.
- */
-#if __has_attribute(format)
-#  define attr_printf(fmt, args) __attribute__((format(printf, fmt, args)))
-#else
-#  define attr_printf(fmt, args)
-#endif
-
-/**
- * Annotates allocator-like functions.
- */
-#if __has_attribute(malloc)
-#  if __GNUC__ >= 11 && !__OPTIMIZE__ // malloc(deallocator) disables inlining on GCC
-#    define attr_malloc(...) attr_nodiscard __attribute__((malloc(__VA_ARGS__)))
-#  else
-#    define attr_malloc(...) attr_nodiscard __attribute__((malloc))
-#  endif
-#else
-#  define attr_malloc(...) attr_nodiscard
-#endif
-
-/**
- * Specifies that a function returns allocations with a given alignment.
- */
-#if __has_attribute(alloc_align)
-#  define attr_alloc_align(param) __attribute__((alloc_align(param)))
-#else
-#  define attr_alloc_align(param)
-#endif
-
-/**
- * Specifies that a function returns allocations with a given size.
- */
-#if __has_attribute(alloc_size)
-#  define attr_alloc_size(...) __attribute__((alloc_size(__VA_ARGS__)))
-#else
-#  define attr_alloc_size(...)
-#endif
-
-/**
- * Shorthand for attr_alloc_align() and attr_alloc_size().
- */
-#define attr_aligned_alloc(align, ...) \
-	attr_alloc_align(align) \
-	attr_alloc_size(__VA_ARGS__)
-
-/**
- * Check if function multiversioning via GNU indirect functions (ifunc) is supported.
- */
-#ifndef BFS_USE_TARGET_CLONES
-#  if __has_attribute(target_clones) && (__GLIBC__ || __FreeBSD__)
-#    define BFS_USE_TARGET_CLONES true
-#  endif
-#endif
-
-/**
- * Apply the target_clones attribute, if available.
- */
-#if BFS_USE_TARGET_CLONES
-#  define attr_target_clones(...) __attribute__((target_clones(__VA_ARGS__)))
-#else
-#  define attr_target_clones(...)
-#endif
-
-/**
- * Shorthand for multiple attributes at once. attr(a, b(c), d) is equivalent to
- *
- *     attr_a
- *     attr_b(c)
- *     attr_d
- */
-#define attr(...) \
-	attr__(attr_##__VA_ARGS__, none, none, none, none, none, none, none, none, none, )
-
-/**
- * attr() helper.  For exposition, pretend we support only 2 args, instead of 9.
- * There are a few cases:
- *
- *     attr()
- *         => attr__(attr_, none, none)
- *         => attr_                =>
- *            attr_none            =>
- *            attr_too_many_none() =>
- *
- *     attr(a)
- *         => attr__(attr_a, none, none)
- *         => attr_a               => __attribute__((a))
- *            attr_none            =>
- *            attr_too_many_none() =>
- *
- *     attr(a, b(c))
- *         => attr__(attr_a, b(c), none, none)
- *         => attr_a                   => __attribute__((a))
- *            attr_b(c)                => __attribute__((b(c)))
- *            attr_too_many_none(none) =>
- *
- *     attr(a, b(c), d)
- *         => attr__(attr_a, b(c), d, none, none)
- *         => attr_a                      => __attribute__((a))
- *            attr_b(c)                   => __attribute__((b(c)))
- *            attr_too_many_d(none, none) => error
- *
- * Some attribute names are the same as standard library functions, e.g. printf.
- * Standard libraries are permitted to define these functions as macros, like
- *
- *     #define printf(...) __builtin_printf(__VA_ARGS__)
- *
- * The token paste in
- *
- *     #define attr(...) attr__(attr_##__VA_ARGS__, none, none)
- *
- * is necessary to prevent macro expansion before evaluating attr__().
- * Otherwise, we could get
- *
- *     attr(printf(1, 2))
- *         => attr__(__builtin_printf(1, 2), none, none)
- *         => attr____builtin_printf(1, 2)
- *         => error
- */
-#define attr__(a1, a2, a3, a4, a5, a6, a7, a8, a9, none, ...) \
-	a1 \
-	attr_##a2 \
-	attr_##a3 \
-	attr_##a4 \
-	attr_##a5 \
-	attr_##a6 \
-	attr_##a7 \
-	attr_##a8 \
-	attr_##a9 \
-	attr_too_many_##none(__VA_ARGS__)
-
-// Ignore `attr_none` from expanding 1-9 argument attr(a1, a2, ...)
-#define attr_none
-// Ignore `attr_` from expanding 0-argument attr()
-#define attr_
-// Only trigger an error on more than 9 arguments
-#define attr_too_many_none(...)
-
-#endif // BFS_CONFIG_H
diff --git a/src/ctx.h b/src/ctx.h
index e14db21..fc3020c 100644
--- a/src/ctx.h
+++ b/src/ctx.h
@@ -8,9 +8,9 @@
 #ifndef BFS_CTX_H
 #define BFS_CTX_H
 
+#include "prelude.h"
 #include "alloc.h"
 #include "bftw.h"
-#include "config.h"
 #include "diag.h"
 #include "expr.h"
 #include "trie.h"
diff --git a/src/diag.c b/src/diag.c
index cb27b92..deb6f26 100644
--- a/src/diag.c
+++ b/src/diag.c
@@ -1,11 +1,11 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "diag.h"
 #include "alloc.h"
 #include "bfstd.h"
 #include "color.h"
-#include "config.h"
 #include "ctx.h"
 #include "dstring.h"
 #include "expr.h"
diff --git a/src/diag.h b/src/diag.h
index 4054c48..2b13609 100644
--- a/src/diag.h
+++ b/src/diag.h
@@ -8,7 +8,7 @@
 #ifndef BFS_DIAG_H
 #define BFS_DIAG_H
 
-#include "config.h"
+#include "prelude.h"
 #include <stdarg.h>
 
 /**
diff --git a/src/dir.c b/src/dir.c
index 98518f2..53c9be3 100644
--- a/src/dir.c
+++ b/src/dir.c
@@ -1,10 +1,10 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "dir.h"
 #include "alloc.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include "sanity.h"
 #include "trie.h"
diff --git a/src/dstring.c b/src/dstring.c
index 10b0fad..913dda8 100644
--- a/src/dstring.c
+++ b/src/dstring.c
@@ -1,10 +1,10 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "dstring.h"
 #include "alloc.h"
 #include "bit.h"
-#include "config.h"
 #include "diag.h"
 #include <stdarg.h>
 #include <stddef.h>
diff --git a/src/dstring.h b/src/dstring.h
index 6006199..9ea7eb9 100644
--- a/src/dstring.h
+++ b/src/dstring.h
@@ -8,8 +8,8 @@
 #ifndef BFS_DSTRING_H
 #define BFS_DSTRING_H
 
+#include "prelude.h"
 #include "bfstd.h"
-#include "config.h"
 #include <stdarg.h>
 #include <stddef.h>
 
diff --git a/src/eval.c b/src/eval.c
index d0112c2..b103912 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -5,12 +5,12 @@
  * Implementation of all the primary expressions.
  */
 
+#include "prelude.h"
 #include "eval.h"
 #include "bar.h"
 #include "bfstd.h"
 #include "bftw.h"
 #include "color.h"
-#include "config.h"
 #include "ctx.h"
 #include "diag.h"
 #include "dir.h"
diff --git a/src/eval.h b/src/eval.h
index ae43628..4dd7996 100644
--- a/src/eval.h
+++ b/src/eval.h
@@ -9,7 +9,7 @@
 #ifndef BFS_EVAL_H
 #define BFS_EVAL_H
 
-#include "config.h"
+#include "prelude.h"
 
 struct bfs_ctx;
 struct bfs_expr;
diff --git a/src/exec.c b/src/exec.c
index 60bfd28..e782d49 100644
--- a/src/exec.c
+++ b/src/exec.c
@@ -1,12 +1,12 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "exec.h"
 #include "alloc.h"
 #include "bfstd.h"
 #include "bftw.h"
 #include "color.h"
-#include "config.h"
 #include "ctx.h"
 #include "diag.h"
 #include "dstring.h"
diff --git a/src/expr.h b/src/expr.h
index 75cb5fd..7bcace7 100644
--- a/src/expr.h
+++ b/src/expr.h
@@ -8,8 +8,8 @@
 #ifndef BFS_EXPR_H
 #define BFS_EXPR_H
 
+#include "prelude.h"
 #include "color.h"
-#include "config.h"
 #include "eval.h"
 #include "stat.h"
 #include <sys/types.h>
diff --git a/src/fsade.c b/src/fsade.c
index 0810c7f..34a4d57 100644
--- a/src/fsade.c
+++ b/src/fsade.c
@@ -1,11 +1,11 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "fsade.h"
 #include "atomic.h"
 #include "bfstd.h"
 #include "bftw.h"
-#include "config.h"
 #include "dir.h"
 #include "dstring.h"
 #include "sanity.h"
diff --git a/src/fsade.h b/src/fsade.h
index 1f1dbfc..6300852 100644
--- a/src/fsade.h
+++ b/src/fsade.h
@@ -9,7 +9,7 @@
 #ifndef BFS_FSADE_H
 #define BFS_FSADE_H
 
-#include "config.h"
+#include "prelude.h"
 
 #define BFS_CAN_CHECK_ACL BFS_USE_SYS_ACL_H
 
diff --git a/src/ioq.c b/src/ioq.c
index b936681..189bdac 100644
--- a/src/ioq.c
+++ b/src/ioq.c
@@ -118,12 +118,12 @@
  * [1]: https://arxiv.org/abs/2201.02179
  */
 
+#include "prelude.h"
 #include "ioq.h"
 #include "alloc.h"
 #include "atomic.h"
 #include "bfstd.h"
 #include "bit.h"
-#include "config.h"
 #include "diag.h"
 #include "dir.h"
 #include "stat.h"
diff --git a/src/ioq.h b/src/ioq.h
index 818eea6..d8e1573 100644
--- a/src/ioq.h
+++ b/src/ioq.h
@@ -8,7 +8,7 @@
 #ifndef BFS_IOQ_H
 #define BFS_IOQ_H
 
-#include "config.h"
+#include "prelude.h"
 #include "dir.h"
 #include "stat.h"
 #include <stddef.h>
diff --git a/src/main.c b/src/main.c
index e120f03..9d8b206 100644
--- a/src/main.c
+++ b/src/main.c
@@ -26,7 +26,7 @@
  *     - bit.h         (bit manipulation)
  *     - bfstd.[ch]    (standard library wrappers/polyfills)
  *     - color.[ch]    (for pretty terminal colors)
- *     - config.h      (configuration and feature/platform detection)
+ *     - prelude.h     (configuration and feature/platform detection)
  *     - diag.[ch]     (formats diagnostic messages)
  *     - dir.[ch]      (a directory API facade)
  *     - dstring.[ch]  (a dynamic string library)
@@ -45,8 +45,8 @@
  *     - xtime.[ch]    (date/time handling utilities)
  */
 
+#include "prelude.h"
 #include "bfstd.h"
-#include "config.h"
 #include "ctx.h"
 #include "diag.h"
 #include "eval.h"
diff --git a/src/mtab.c b/src/mtab.c
index 86ae151..7905d14 100644
--- a/src/mtab.c
+++ b/src/mtab.c
@@ -1,10 +1,10 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "mtab.h"
 #include "alloc.h"
 #include "bfstd.h"
-#include "config.h"
 #include "stat.h"
 #include "trie.h"
 #include <errno.h>
diff --git a/src/mtab.h b/src/mtab.h
index d99d78f..67290c2 100644
--- a/src/mtab.h
+++ b/src/mtab.h
@@ -8,7 +8,7 @@
 #ifndef BFS_MTAB_H
 #define BFS_MTAB_H
 
-#include "config.h"
+#include "prelude.h"
 
 struct bfs_stat;
 
diff --git a/src/opt.c b/src/opt.c
index b74b4e1..ffc795b 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -25,11 +25,11 @@
  * effects are reachable at all, skipping the traversal if not.
  */
 
+#include "prelude.h"
 #include "opt.h"
 #include "bftw.h"
 #include "bit.h"
 #include "color.h"
-#include "config.h"
 #include "ctx.h"
 #include "diag.h"
 #include "dir.h"
diff --git a/src/parse.c b/src/parse.c
index a3e32fe..c2ae58f 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -8,12 +8,12 @@
  * flags like always-true options, and skipping over paths wherever they appear.
  */
 
+#include "prelude.h"
 #include "parse.h"
 #include "alloc.h"
 #include "bfstd.h"
 #include "bftw.h"
 #include "color.h"
-#include "config.h"
 #include "ctx.h"
 #include "diag.h"
 #include "dir.h"
diff --git a/src/prelude.h b/src/prelude.h
new file mode 100644
index 0000000..c3a0752
--- /dev/null
+++ b/src/prelude.h
@@ -0,0 +1,377 @@
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+
+/**
+ * Configuration and feature/platform detection.
+ */
+
+#ifndef BFS_PRELUDE_H
+#define BFS_PRELUDE_H
+
+// Possible __STDC_VERSION__ values
+
+#define C95 199409L
+#define C99 199901L
+#define C11 201112L
+#define C17 201710L
+#define C23 202311L
+
+#include <stddef.h>
+
+#if __STDC_VERSION__ < C23
+#  include <stdalign.h>
+#  include <stdbool.h>
+#  include <stdnoreturn.h>
+#endif
+
+// bfs packaging configuration
+
+#ifndef BFS_COMMAND
+#  define BFS_COMMAND "bfs"
+#endif
+#ifndef BFS_HOMEPAGE
+#  define BFS_HOMEPAGE "https://tavianator.com/projects/bfs.html"
+#endif
+
+// This is a symbol instead of a literal so we don't have to rebuild everything
+// when the version number changes
+extern const char bfs_version[];
+
+// Check for system headers
+
+#ifdef __has_include
+
+#if __has_include(<mntent.h>)
+#  define BFS_HAS_MNTENT_H true
+#endif
+#if __has_include(<paths.h>)
+#  define BFS_HAS_PATHS_H true
+#endif
+#if __has_include(<sys/acl.h>)
+#  define BFS_HAS_SYS_ACL_H true
+#endif
+#if __has_include(<sys/capability.h>)
+#  define BFS_HAS_SYS_CAPABILITY_H true
+#endif
+#if __has_include(<sys/extattr.h>)
+#  define BFS_HAS_SYS_EXTATTR_H true
+#endif
+#if __has_include(<sys/mkdev.h>)
+#  define BFS_HAS_SYS_MKDEV_H true
+#endif
+#if __has_include(<sys/param.h>)
+#  define BFS_HAS_SYS_PARAM_H true
+#endif
+#if __has_include(<sys/sysmacros.h>)
+#  define BFS_HAS_SYS_SYSMACROS_H true
+#endif
+#if __has_include(<sys/xattr.h>)
+#  define BFS_HAS_SYS_XATTR_H true
+#endif
+#if __has_include(<threads.h>)
+#  define BFS_HAS_THREADS_H true
+#endif
+#if __has_include(<util.h>)
+#  define BFS_HAS_UTIL_H true
+#endif
+
+#else // !__has_include
+
+#define BFS_HAS_MNTENT_H __GLIBC__
+#define BFS_HAS_PATHS_H true
+#define BFS_HAS_SYS_ACL_H true
+#define BFS_HAS_SYS_CAPABILITY_H __linux__
+#define BFS_HAS_SYS_EXTATTR_H __FreeBSD__
+#define BFS_HAS_SYS_MKDEV_H false
+#define BFS_HAS_SYS_PARAM_H true
+#define BFS_HAS_SYS_SYSMACROS_H __GLIBC__
+#define BFS_HAS_SYS_XATTR_H __linux__
+#define BFS_HAS_THREADS_H (!__STDC_NO_THREADS__)
+#define BFS_HAS_UTIL_H __NetBSD__
+
+#endif // !__has_include
+
+#ifndef BFS_USE_MNTENT_H
+#  define BFS_USE_MNTENT_H BFS_HAS_MNTENT_H
+#endif
+#ifndef BFS_USE_PATHS_H
+#  define BFS_USE_PATHS_H BFS_HAS_PATHS_H
+#endif
+#ifndef BFS_USE_SYS_ACL_H
+#  define BFS_USE_SYS_ACL_H (BFS_HAS_SYS_ACL_H && !__illumos__ && (!__linux__ || BFS_USE_LIBACL))
+#endif
+#ifndef BFS_USE_SYS_CAPABILITY_H
+#  define BFS_USE_SYS_CAPABILITY_H (BFS_HAS_SYS_CAPABILITY_H && !__FreeBSD__ && (!__linux__ || BFS_USE_LIBCAP))
+#endif
+#ifndef BFS_USE_SYS_EXTATTR_H
+#  define BFS_USE_SYS_EXTATTR_H (BFS_HAS_SYS_EXTATTR_H && !__DragonFly__)
+#endif
+#ifndef BFS_USE_SYS_MKDEV_H
+#  define BFS_USE_SYS_MKDEV_H BFS_HAS_SYS_MKDEV_H
+#endif
+#ifndef BFS_USE_SYS_PARAM_H
+#  define BFS_USE_SYS_PARAM_H BFS_HAS_SYS_PARAM_H
+#endif
+#ifndef BFS_USE_SYS_SYSMACROS_H
+#  define BFS_USE_SYS_SYSMACROS_H BFS_HAS_SYS_SYSMACROS_H
+#endif
+#ifndef BFS_USE_SYS_XATTR_H
+#  define BFS_USE_SYS_XATTR_H BFS_HAS_SYS_XATTR_H
+#endif
+#ifndef BFS_USE_THREADS_H
+#  define BFS_USE_THREADS_H BFS_HAS_THREADS_H
+#endif
+#ifndef BFS_USE_UTIL_H
+#  define BFS_USE_UTIL_H BFS_HAS_UTIL_H
+#endif
+
+// Stub out feature detection on old/incompatible compilers
+
+#ifndef __has_feature
+#  define __has_feature(feat) false
+#endif
+
+#ifndef __has_c_attribute
+#  define __has_c_attribute(attr) false
+#endif
+
+#ifndef __has_attribute
+#  define __has_attribute(attr) false
+#endif
+
+// Platform detection
+
+// Get the definition of BSD if available
+#if BFS_USE_SYS_PARAM_H
+#  include <sys/param.h>
+#endif
+
+#ifndef __GLIBC_PREREQ
+#  define __GLIBC_PREREQ(maj, min) false
+#endif
+
+#ifndef __NetBSD_Prereq__
+#  define __NetBSD_Prereq__(maj, min, patch) false
+#endif
+
+// Fundamental utilities
+
+/**
+ * Get the length of an array.
+ */
+#define countof(array) (sizeof(array) / sizeof(0[array]))
+
+/**
+ * False sharing/destructive interference/largest cache line size.
+ */
+#ifdef __GCC_DESTRUCTIVE_SIZE
+#  define FALSE_SHARING_SIZE __GCC_DESTRUCTIVE_SIZE
+#else
+#  define FALSE_SHARING_SIZE 64
+#endif
+
+/**
+ * True sharing/constructive interference/smallest cache line size.
+ */
+#ifdef __GCC_CONSTRUCTIVE_SIZE
+#  define TRUE_SHARING_SIZE __GCC_CONSTRUCTIVE_SIZE
+#else
+#  define TRUE_SHARING_SIZE 64
+#endif
+
+/**
+ * Alignment specifier that avoids false sharing.
+ */
+#define cache_align alignas(FALSE_SHARING_SIZE)
+
+#if __COSMOPOLITAN__
+typedef long double max_align_t;
+#endif
+
+// Wrappers for attributes
+
+/**
+ * Silence warnings about switch/case fall-throughs.
+ */
+#if __has_attribute(fallthrough)
+#  define fallthru __attribute__((fallthrough))
+#else
+#  define fallthru ((void)0)
+#endif
+
+/**
+ * Silence warnings about unused declarations.
+ */
+#if __has_attribute(unused)
+#  define attr_maybe_unused __attribute__((unused))
+#else
+#  define attr_maybe_unused
+#endif
+
+/**
+ * Warn if a value is unused.
+ */
+#if __has_attribute(warn_unused_result)
+#  define attr_nodiscard __attribute__((warn_unused_result))
+#else
+#  define attr_nodiscard
+#endif
+
+/**
+ * Hint to avoid inlining a function.
+ */
+#if __has_attribute(noinline)
+#  define attr_noinline __attribute__((noinline))
+#else
+#  define attr_noinline
+#endif
+
+/**
+ * Hint that a function is unlikely to be called.
+ */
+#if __has_attribute(cold)
+#  define attr_cold attr_noinline __attribute__((cold))
+#else
+#  define attr_cold attr_noinline
+#endif
+
+/**
+ * Adds compiler warnings for bad printf()-style function calls, if supported.
+ */
+#if __has_attribute(format)
+#  define attr_printf(fmt, args) __attribute__((format(printf, fmt, args)))
+#else
+#  define attr_printf(fmt, args)
+#endif
+
+/**
+ * Annotates allocator-like functions.
+ */
+#if __has_attribute(malloc)
+#  if __GNUC__ >= 11 && !__OPTIMIZE__ // malloc(deallocator) disables inlining on GCC
+#    define attr_malloc(...) attr_nodiscard __attribute__((malloc(__VA_ARGS__)))
+#  else
+#    define attr_malloc(...) attr_nodiscard __attribute__((malloc))
+#  endif
+#else
+#  define attr_malloc(...) attr_nodiscard
+#endif
+
+/**
+ * Specifies that a function returns allocations with a given alignment.
+ */
+#if __has_attribute(alloc_align)
+#  define attr_alloc_align(param) __attribute__((alloc_align(param)))
+#else
+#  define attr_alloc_align(param)
+#endif
+
+/**
+ * Specifies that a function returns allocations with a given size.
+ */
+#if __has_attribute(alloc_size)
+#  define attr_alloc_size(...) __attribute__((alloc_size(__VA_ARGS__)))
+#else
+#  define attr_alloc_size(...)
+#endif
+
+/**
+ * Shorthand for attr_alloc_align() and attr_alloc_size().
+ */
+#define attr_aligned_alloc(align, ...) \
+	attr_alloc_align(align) \
+	attr_alloc_size(__VA_ARGS__)
+
+/**
+ * Check if function multiversioning via GNU indirect functions (ifunc) is supported.
+ */
+#ifndef BFS_USE_TARGET_CLONES
+#  if __has_attribute(target_clones) && (__GLIBC__ || __FreeBSD__)
+#    define BFS_USE_TARGET_CLONES true
+#  endif
+#endif
+
+/**
+ * Apply the target_clones attribute, if available.
+ */
+#if BFS_USE_TARGET_CLONES
+#  define attr_target_clones(...) __attribute__((target_clones(__VA_ARGS__)))
+#else
+#  define attr_target_clones(...)
+#endif
+
+/**
+ * Shorthand for multiple attributes at once. attr(a, b(c), d) is equivalent to
+ *
+ *     attr_a
+ *     attr_b(c)
+ *     attr_d
+ */
+#define attr(...) \
+	attr__(attr_##__VA_ARGS__, none, none, none, none, none, none, none, none, none, )
+
+/**
+ * attr() helper.  For exposition, pretend we support only 2 args, instead of 9.
+ * There are a few cases:
+ *
+ *     attr()
+ *         => attr__(attr_, none, none)
+ *         => attr_                =>
+ *            attr_none            =>
+ *            attr_too_many_none() =>
+ *
+ *     attr(a)
+ *         => attr__(attr_a, none, none)
+ *         => attr_a               => __attribute__((a))
+ *            attr_none            =>
+ *            attr_too_many_none() =>
+ *
+ *     attr(a, b(c))
+ *         => attr__(attr_a, b(c), none, none)
+ *         => attr_a                   => __attribute__((a))
+ *            attr_b(c)                => __attribute__((b(c)))
+ *            attr_too_many_none(none) =>
+ *
+ *     attr(a, b(c), d)
+ *         => attr__(attr_a, b(c), d, none, none)
+ *         => attr_a                      => __attribute__((a))
+ *            attr_b(c)                   => __attribute__((b(c)))
+ *            attr_too_many_d(none, none) => error
+ *
+ * Some attribute names are the same as standard library functions, e.g. printf.
+ * Standard libraries are permitted to define these functions as macros, like
+ *
+ *     #define printf(...) __builtin_printf(__VA_ARGS__)
+ *
+ * The token paste in
+ *
+ *     #define attr(...) attr__(attr_##__VA_ARGS__, none, none)
+ *
+ * is necessary to prevent macro expansion before evaluating attr__().
+ * Otherwise, we could get
+ *
+ *     attr(printf(1, 2))
+ *         => attr__(__builtin_printf(1, 2), none, none)
+ *         => attr____builtin_printf(1, 2)
+ *         => error
+ */
+#define attr__(a1, a2, a3, a4, a5, a6, a7, a8, a9, none, ...) \
+	a1 \
+	attr_##a2 \
+	attr_##a3 \
+	attr_##a4 \
+	attr_##a5 \
+	attr_##a6 \
+	attr_##a7 \
+	attr_##a8 \
+	attr_##a9 \
+	attr_too_many_##none(__VA_ARGS__)
+
+// Ignore `attr_none` from expanding 1-9 argument attr(a1, a2, ...)
+#define attr_none
+// Ignore `attr_` from expanding 0-argument attr()
+#define attr_
+// Only trigger an error on more than 9 arguments
+#define attr_too_many_none(...)
+
+#endif // BFS_PRELUDE_H
diff --git a/src/printf.c b/src/printf.c
index 3b8269e..4df399b 100644
--- a/src/printf.c
+++ b/src/printf.c
@@ -1,12 +1,12 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "printf.h"
 #include "alloc.h"
 #include "bfstd.h"
 #include "bftw.h"
 #include "color.h"
-#include "config.h"
 #include "ctx.h"
 #include "diag.h"
 #include "dir.h"
diff --git a/src/pwcache.c b/src/pwcache.c
index 79437d8..af8c237 100644
--- a/src/pwcache.c
+++ b/src/pwcache.c
@@ -1,9 +1,9 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "pwcache.h"
 #include "alloc.h"
-#include "config.h"
 #include "trie.h"
 #include <errno.h>
 #include <grp.h>
diff --git a/src/sanity.h b/src/sanity.h
index 423e6ff..e168b8f 100644
--- a/src/sanity.h
+++ b/src/sanity.h
@@ -8,7 +8,7 @@
 #ifndef BFS_SANITY_H
 #define BFS_SANITY_H
 
-#include "config.h"
+#include "prelude.h"
 #include <stddef.h>
 
 #if __has_feature(address_sanitizer) || defined(__SANITIZE_ADDRESS__)
diff --git a/src/stat.c b/src/stat.c
index 2f2743b..eca5bab 100644
--- a/src/stat.c
+++ b/src/stat.c
@@ -1,10 +1,10 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "stat.h"
 #include "atomic.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include "sanity.h"
 #include <errno.h>
diff --git a/src/stat.h b/src/stat.h
index 856a2ca..1fdd263 100644
--- a/src/stat.h
+++ b/src/stat.h
@@ -12,7 +12,7 @@
 #ifndef BFS_STAT_H
 #define BFS_STAT_H
 
-#include "config.h"
+#include "prelude.h"
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <time.h>
diff --git a/src/thread.c b/src/thread.c
index 200d8c3..3793896 100644
--- a/src/thread.c
+++ b/src/thread.c
@@ -1,9 +1,9 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "thread.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include <errno.h>
 #include <pthread.h>
diff --git a/src/thread.h b/src/thread.h
index 8174fe4..db11bd8 100644
--- a/src/thread.h
+++ b/src/thread.h
@@ -8,7 +8,7 @@
 #ifndef BFS_THREAD_H
 #define BFS_THREAD_H
 
-#include "config.h"
+#include "prelude.h"
 #include <pthread.h>
 
 #if __STDC_VERSION__ < C23 && !defined(thread_local)
diff --git a/src/trie.c b/src/trie.c
index f275064..808953e 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -81,10 +81,10 @@
  * and insert intermediate singleton "jump" nodes when necessary.
  */
 
+#include "prelude.h"
 #include "trie.h"
 #include "alloc.h"
 #include "bit.h"
-#include "config.h"
 #include "diag.h"
 #include "list.h"
 #include <stdint.h>
diff --git a/src/xregex.c b/src/xregex.c
index 3df27f0..c2711bc 100644
--- a/src/xregex.c
+++ b/src/xregex.c
@@ -1,10 +1,10 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "xregex.h"
 #include "alloc.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include "sanity.h"
 #include "thread.h"
diff --git a/src/xspawn.c b/src/xspawn.c
index 347625d..113d7ec 100644
--- a/src/xspawn.c
+++ b/src/xspawn.c
@@ -1,10 +1,10 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "xspawn.h"
 #include "alloc.h"
 #include "bfstd.h"
-#include "config.h"
 #include "list.h"
 #include <errno.h>
 #include <fcntl.h>
diff --git a/src/xspawn.h b/src/xspawn.h
index a20cbd0..6a8f54a 100644
--- a/src/xspawn.h
+++ b/src/xspawn.h
@@ -8,7 +8,7 @@
 #ifndef BFS_XSPAWN_H
 #define BFS_XSPAWN_H
 
-#include "config.h"
+#include "prelude.h"
 #include <sys/resource.h>
 #include <sys/types.h>
 #include <unistd.h>
diff --git a/src/xtime.c b/src/xtime.c
index bcf6dd3..91ed915 100644
--- a/src/xtime.c
+++ b/src/xtime.c
@@ -1,9 +1,9 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "xtime.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include <errno.h>
 #include <limits.h>
diff --git a/tests/alloc.c b/tests/alloc.c
index 54b84ba..6c0defd 100644
--- a/tests/alloc.c
+++ b/tests/alloc.c
@@ -1,9 +1,9 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "tests.h"
 #include "alloc.h"
-#include "config.h"
 #include "diag.h"
 #include <errno.h>
 #include <stdlib.h>
diff --git a/tests/bfstd.c b/tests/bfstd.c
index 5e408ca..07b68b0 100644
--- a/tests/bfstd.c
+++ b/tests/bfstd.c
@@ -1,9 +1,9 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "tests.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include <errno.h>
 #include <langinfo.h>
diff --git a/tests/bit.c b/tests/bit.c
index b444e50..674d1b2 100644
--- a/tests/bit.c
+++ b/tests/bit.c
@@ -1,9 +1,9 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "tests.h"
 #include "bit.h"
-#include "config.h"
 #include "diag.h"
 #include <limits.h>
 #include <stdint.h>
diff --git a/tests/ioq.c b/tests/ioq.c
index a69f2bf..ef5ee3b 100644
--- a/tests/ioq.c
+++ b/tests/ioq.c
@@ -1,10 +1,10 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "tests.h"
 #include "ioq.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include "dir.h"
 #include <errno.h>
diff --git a/tests/main.c b/tests/main.c
index 281c417..429772b 100644
--- a/tests/main.c
+++ b/tests/main.c
@@ -5,10 +5,10 @@
  * Entry point for unit tests.
  */
 
+#include "prelude.h"
 #include "tests.h"
 #include "bfstd.h"
 #include "color.h"
-#include "config.h"
 #include <errno.h>
 #include <locale.h>
 #include <stdio.h>
diff --git a/tests/tests.h b/tests/tests.h
index d61ffd7..9078938 100644
--- a/tests/tests.h
+++ b/tests/tests.h
@@ -8,7 +8,7 @@
 #ifndef BFS_TESTS_H
 #define BFS_TESTS_H
 
-#include "config.h"
+#include "prelude.h"
 #include "diag.h"
 
 /** Unit test function type. */
diff --git a/tests/trie.c b/tests/trie.c
index 2a6eb48..4667322 100644
--- a/tests/trie.c
+++ b/tests/trie.c
@@ -1,9 +1,9 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "tests.h"
 #include "trie.h"
-#include "config.h"
 #include "diag.h"
 #include <stdlib.h>
 #include <string.h>
diff --git a/tests/xspawn.c b/tests/xspawn.c
index fd8362e..7362aa5 100644
--- a/tests/xspawn.c
+++ b/tests/xspawn.c
@@ -1,10 +1,10 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "tests.h"
 #include "alloc.h"
 #include "bfstd.h"
-#include "config.h"
 #include "dstring.h"
 #include "xspawn.h"
 #include <stdlib.h>
diff --git a/tests/xtime.c b/tests/xtime.c
index fd7aa0f..a7c63d2 100644
--- a/tests/xtime.c
+++ b/tests/xtime.c
@@ -1,10 +1,10 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "tests.h"
 #include "xtime.h"
 #include "bfstd.h"
-#include "config.h"
 #include "diag.h"
 #include <errno.h>
 #include <limits.h>
diff --git a/tests/xtouch.c b/tests/xtouch.c
index b1daec7..82d749d 100644
--- a/tests/xtouch.c
+++ b/tests/xtouch.c
@@ -1,8 +1,8 @@
 // Copyright © Tavian Barnes <tavianator@tavianator.com>
 // SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "bfstd.h"
-#include "config.h"
 #include "sanity.h"
 #include "xtime.h"
 #include <errno.h>
-- 
cgit v1.2.3