pwcache: Fill the user/group caches lazily

Iterating all the users/groups can be expensive, especially with NSS.
Android has so many that it doesn't even return them all from
get{pw,gr}ent() for performance reasons, leading to incorrect behaviour
of -user/-group/etc.

10 files changed, 237 insertions, 366 deletions

diff --git a/src/ctx.c b/src/ctx.c
index b2f7d56..8d80691 100644
--- a/src/ctx.c
+++ b/src/ctx.c
@@ -84,9 +84,7 @@ struct bfs_ctx *bfs_ctx_new(void) {
 	ctx->cerr = NULL;
 
 	ctx->users = NULL;
-	ctx->users_error = 0;
 	ctx->groups = NULL;
-	ctx->groups_error = 0;
 
 	ctx->mtab = NULL;
 	ctx->mtab_error = 0;
@@ -95,45 +93,27 @@ struct bfs_ctx *bfs_ctx_new(void) {
 	ctx->nfiles = 0;
 
 	struct rlimit rl;
-	if (getrlimit(RLIMIT_NOFILE, &rl) == 0) {
-		ctx->nofile_soft = rl.rlim_cur;
-		ctx->nofile_hard = rl.rlim_max;
-	} else {
-		ctx->nofile_soft = 1024;
-		ctx->nofile_hard = RLIM_INFINITY;
+	if (getrlimit(RLIMIT_NOFILE, &rl) != 0) {
+		goto fail;
 	}
+	ctx->nofile_soft = rl.rlim_cur;
+	ctx->nofile_hard = rl.rlim_max;
 
-	return ctx;
-}
-
-const struct bfs_users *bfs_ctx_users(const struct bfs_ctx *ctx) {
-	struct bfs_ctx *mut = (struct bfs_ctx *)ctx;
-
-	if (mut->users_error) {
-		errno = mut->users_error;
-	} else if (!mut->users) {
-		mut->users = bfs_users_parse();
-		if (!mut->users) {
-			mut->users_error = errno;
-		}
+	ctx->users = bfs_users_new();
+	if (!ctx->users) {
+		goto fail;
 	}
 
-	return mut->users;
-}
-
-const struct bfs_groups *bfs_ctx_groups(const struct bfs_ctx *ctx) {
-	struct bfs_ctx *mut = (struct bfs_ctx *)ctx;
-
-	if (mut->groups_error) {
-		errno = mut->groups_error;
-	} else if (!mut->groups) {
-		mut->groups = bfs_groups_parse();
-		if (!mut->groups) {
-			mut->groups_error = errno;
-		}
+	ctx->groups = bfs_groups_new();
+	if (!ctx->groups) {
+		goto fail;
 	}
 
-	return mut->groups;
+	return ctx;
+
+fail:
+	bfs_ctx_free(ctx);
+	return NULL;
 }
 
 const struct bfs_mtab *bfs_ctx_mtab(const struct bfs_ctx *ctx) {
diff --git a/src/ctx.h b/src/ctx.h
index 6c4ef33..d32db59 100644
--- a/src/ctx.h
+++ b/src/ctx.h
@@ -106,10 +106,8 @@ struct bfs_ctx {
 	/** Colored stderr. */
 	struct CFILE *cerr;
 
-	/** User table. */
+	/** User cache. */
 	struct bfs_users *users;
-	/** The error that occurred parsing the user table, if any. */
-	int users_error;
 	/** Group table. */
 	struct bfs_groups *groups;
 	/** The error that occurred parsing the group table, if any. */
@@ -138,26 +136,6 @@ struct bfs_ctx {
 struct bfs_ctx *bfs_ctx_new(void);
 
 /**
- * Get the users table.
- *
- * @param ctx
- *         The bfs context.
- * @return
- *         The cached users table, or NULL on failure.
- */
-const struct bfs_users *bfs_ctx_users(const struct bfs_ctx *ctx);
-
-/**
- * Get the groups table.
- *
- * @param ctx
- *         The bfs context.
- * @return
- *         The cached groups table, or NULL on failure.
- */
-const struct bfs_groups *bfs_ctx_groups(const struct bfs_ctx *ctx);
-
-/**
  * Get the mount table.
  *
  * @param ctx
diff --git a/src/eval.c b/src/eval.c
index dc46a23..f756617 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -309,13 +309,11 @@ bool eval_nogroup(const struct bfs_expr *expr, struct bfs_eval *state) {
 		return false;
 	}
 
-	const struct bfs_groups *groups = bfs_ctx_groups(state->ctx);
-	if (!groups) {
+	const struct group *grp = bfs_getgrgid(state->ctx->groups, statbuf->gid);
+	if (errno != 0) {
 		eval_report_error(state);
-		return false;
 	}
-
-	return bfs_getgrgid(groups, statbuf->gid) == NULL;
+	return grp == NULL;
 }
 
 /**
@@ -327,13 +325,11 @@ bool eval_nouser(const struct bfs_expr *expr, struct bfs_eval *state) {
 		return false;
 	}
 
-	const struct bfs_users *users = bfs_ctx_users(state->ctx);
-	if (!users) {
+	const struct passwd *pwd = bfs_getpwuid(state->ctx->users, statbuf->uid);
+	if (errno != 0) {
 		eval_report_error(state);
-		return false;
 	}
-
-	return bfs_getpwuid(users, statbuf->uid) == NULL;
+	return pwd == NULL;
 }
 
 /**
@@ -642,8 +638,7 @@ bool eval_perm(const struct bfs_expr *expr, struct bfs_eval *state) {
 bool eval_fls(const struct bfs_expr *expr, struct bfs_eval *state) {
 	CFILE *cfile = expr->cfile;
 	FILE *file = cfile->file;
-	const struct bfs_users *users = bfs_ctx_users(state->ctx);
-	const struct bfs_groups *groups = bfs_ctx_groups(state->ctx);
+	const struct bfs_ctx *ctx = state->ctx;
 	const struct BFTW *ftwbuf = state->ftwbuf;
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
@@ -651,7 +646,7 @@ bool eval_fls(const struct bfs_expr *expr, struct bfs_eval *state) {
 	}
 
 	uintmax_t ino = statbuf->ino;
-	uintmax_t block_size = state->ctx->posixly_correct ? 512 : 1024;
+	uintmax_t block_size = ctx->posixly_correct ? 512 : 1024;
 	uintmax_t blocks = ((uintmax_t)statbuf->blocks*BFS_STAT_BLKSIZE + block_size - 1)/block_size;
 	char mode[11];
 	xstrmode(statbuf->mode, mode);
@@ -662,7 +657,7 @@ bool eval_fls(const struct bfs_expr *expr, struct bfs_eval *state) {
 	}
 
 	uintmax_t uid = statbuf->uid;
-	const struct passwd *pwd = users ? bfs_getpwuid(users, uid) : NULL;
+	const struct passwd *pwd = bfs_getpwuid(ctx->users, uid);
 	if (pwd) {
 		if (fprintf(file, " %-8s", pwd->pw_name) < 0) {
 			goto error;
@@ -674,7 +669,7 @@ bool eval_fls(const struct bfs_expr *expr, struct bfs_eval *state) {
 	}
 
 	uintmax_t gid = statbuf->gid;
-	const struct group *grp = groups ? bfs_getgrgid(groups, gid) : NULL;
+	const struct group *grp = bfs_getgrgid(ctx->groups, gid);
 	if (grp) {
 		if (fprintf(file, " %-8s", grp->gr_name) < 0) {
 			goto error;
diff --git a/src/opt.c b/src/opt.c
index cece337..fa2e66c 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -48,6 +48,7 @@
 #include "expr.h"
 #include "pwcache.h"
 #include <assert.h>
+#include <errno.h>
 #include <limits.h>
 #include <stdarg.h>
 #include <stdbool.h>
@@ -789,12 +790,13 @@ static void infer_icmp_facts(struct opt_state *state, const struct bfs_expr *exp
 static void infer_gid_facts(struct opt_state *state, const struct bfs_expr *expr) {
 	infer_icmp_facts(state, expr, GID_RANGE);
 
-	const struct bfs_groups *groups = bfs_ctx_groups(state->ctx);
 	struct range *range = &state->facts_when_true.ranges[GID_RANGE];
-	if (groups && range->min == range->max) {
+	if (range->min == range->max) {
 		gid_t gid = range->min;
-		bool nogroup = !bfs_getgrgid(groups, gid);
-		constrain_pred(&state->facts_when_true.preds[NOGROUP_PRED], nogroup);
+		bool nogroup = !bfs_getgrgid(state->ctx->groups, gid);
+		if (errno == 0) {
+			constrain_pred(&state->facts_when_true.preds[NOGROUP_PRED], nogroup);
+		}
 	}
 }
 
@@ -802,12 +804,13 @@ static void infer_gid_facts(struct opt_state *state, const struct bfs_expr *expr
 static void infer_uid_facts(struct opt_state *state, const struct bfs_expr *expr) {
 	infer_icmp_facts(state, expr, UID_RANGE);
 
-	const struct bfs_users *users = bfs_ctx_users(state->ctx);
 	struct range *range = &state->facts_when_true.ranges[UID_RANGE];
-	if (users && range->min == range->max) {
+	if (range->min == range->max) {
 		uid_t uid = range->min;
-		bool nouser = !bfs_getpwuid(users, uid);
-		constrain_pred(&state->facts_when_true.preds[NOUSER_PRED], nouser);
+		bool nouser = !bfs_getpwuid(state->ctx->users, uid);
+		if (errno == 0) {
+			constrain_pred(&state->facts_when_true.preds[NOUSER_PRED], nouser);
+		}
 	}
 }
 
diff --git a/src/parse.c b/src/parse.c
index a4cb4fc..45242f0 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -1526,12 +1526,6 @@ static struct bfs_expr *parse_fls(struct parser_state *state, int arg1, int arg2
 	expr_set_always_true(expr);
 	expr->cost = PRINT_COST;
 	expr->reftime = state->now;
-
-	// We'll need these for user/group names, so initialize them now to
-	// avoid EMFILE later
-	bfs_ctx_users(state->ctx);
-	bfs_ctx_groups(state->ctx);
-
 	return expr;
 
 fail:
@@ -1647,13 +1641,7 @@ static struct bfs_expr *parse_group(struct parser_state *state, int arg1, int ar
 		return NULL;
 	}
 
-	const struct bfs_groups *groups = bfs_ctx_groups(state->ctx);
-	if (!groups) {
-		parse_expr_error(state, expr, "Couldn't parse the group table: %m.\n");
-		goto fail;
-	}
-
-	const struct group *grp = bfs_getgrnam(groups, expr->argv[1]);
+	const struct group *grp = bfs_getgrnam(state->ctx->groups, expr->argv[1]);
 	if (grp) {
 		expr->num = grp->gr_gid;
 		expr->int_cmp = BFS_INT_EQUAL;
@@ -1661,13 +1649,15 @@ static struct bfs_expr *parse_group(struct parser_state *state, int arg1, int ar
 		if (!parse_icmp(state, expr, 0)) {
 			goto fail;
 		}
+	} else if (errno) {
+		parse_expr_error(state, expr, "%m.\n");
+		goto fail;
 	} else {
 		parse_expr_error(state, expr, "No such group.\n");
 		goto fail;
 	}
 
 	expr->cost = STAT_COST;
-
 	return expr;
 
 fail:
@@ -1703,13 +1693,7 @@ static struct bfs_expr *parse_user(struct parser_state *state, int arg1, int arg
 		return NULL;
 	}
 
-	const struct bfs_users *users = bfs_ctx_users(state->ctx);
-	if (!users) {
-		parse_expr_error(state, expr, "Couldn't parse the user table: %m.\n");
-		goto fail;
-	}
-
-	const struct passwd *pwd = bfs_getpwnam(users, expr->argv[1]);
+	const struct passwd *pwd = bfs_getpwnam(state->ctx->users, expr->argv[1]);
 	if (pwd) {
 		expr->num = pwd->pw_uid;
 		expr->int_cmp = BFS_INT_EQUAL;
@@ -1717,13 +1701,15 @@ static struct bfs_expr *parse_user(struct parser_state *state, int arg1, int arg
 		if (!parse_icmp(state, expr, 0)) {
 			goto fail;
 		}
+	} else if (errno) {
+		parse_expr_error(state, expr, "%m.\n");
+		goto fail;
 	} else {
 		parse_expr_error(state, expr, "No such user.\n");
 		goto fail;
 	}
 
 	expr->cost = STAT_COST;
-
 	return expr;
 
 fail:
@@ -1785,12 +1771,6 @@ static struct bfs_expr *parse_ls(struct parser_state *state, int arg1, int arg2)
 
 	init_print_expr(state, expr);
 	expr->reftime = state->now;
-
-	// We'll need these for user/group names, so initialize them now to
-	// avoid EMFILE later
-	bfs_ctx_users(state->ctx);
-	bfs_ctx_groups(state->ctx);
-
 	return expr;
 }
 
@@ -2005,16 +1985,18 @@ fail:
  * Parse -nogroup.
  */
 static struct bfs_expr *parse_nogroup(struct parser_state *state, int arg1, int arg2) {
-	if (!bfs_ctx_groups(state->ctx)) {
-		parse_error(state, "Couldn't parse the group table: %m.\n");
+	struct bfs_expr *expr = parse_nullary_test(state, eval_nogroup);
+	if (!expr) {
 		return NULL;
 	}
 
-	struct bfs_expr *expr = parse_nullary_test(state, eval_nogroup);
-	if (expr) {
-		expr->cost = STAT_COST;
-		expr->probability = 0.01;
-	}
+	expr->cost = STAT_COST;
+	expr->probability = 0.01;
+
+	// Who knows how many FDs getgrgid_r() needs?  Probably at least one for
+	// /etc/group
+	expr->ephemeral_fds = 1;
+
 	return expr;
 }
 
@@ -2051,16 +2033,18 @@ static struct bfs_expr *parse_noleaf(struct parser_state *state, int arg1, int a
  * Parse -nouser.
  */
 static struct bfs_expr *parse_nouser(struct parser_state *state, int arg1, int arg2) {
-	if (!bfs_ctx_users(state->ctx)) {
-		parse_error(state, "Couldn't parse the user table: %m.\n");
+	struct bfs_expr *expr = parse_nullary_test(state, eval_nouser);
+	if (!expr) {
 		return NULL;
 	}
 
-	struct bfs_expr *expr = parse_nullary_test(state, eval_nouser);
-	if (expr) {
-		expr->cost = STAT_COST;
-		expr->probability = 0.01;
-	}
+	expr->cost = STAT_COST;
+	expr->probability = 0.01;
+
+	// Who knows how many FDs getpwuid_r() needs?  Probably at least one for
+	// /etc/passwd
+	expr->ephemeral_fds = 1;
+
 	return expr;
 }
 
diff --git a/src/printf.c b/src/printf.c
index 57ff5fd..6a7b9a9 100644
--- a/src/printf.c
+++ b/src/printf.c
@@ -59,7 +59,7 @@ struct bfs_printf {
 	/** Character data associated with this directive. */
 	char c;
 	/** Some data used by the directive. */
-	const void *ptr;
+	void *ptr;
 };
 
 /** Print some text as-is. */
@@ -259,8 +259,8 @@ static int bfs_printf_g(CFILE *cfile, const struct bfs_printf *directive, const
 		return -1;
 	}
 
-	const struct bfs_groups *groups = directive->ptr;
-	const struct group *grp = groups ? bfs_getgrgid(groups, statbuf->gid) : NULL;
+	struct bfs_groups *groups = directive->ptr;
+	const struct group *grp = bfs_getgrgid(groups, statbuf->gid);
 	if (!grp) {
 		return bfs_printf_G(cfile, directive, ftwbuf);
 	}
@@ -469,8 +469,8 @@ static int bfs_printf_u(CFILE *cfile, const struct bfs_printf *directive, const
 		return -1;
 	}
 
-	const struct bfs_users *users = directive->ptr;
-	const struct passwd *pwd = users ? bfs_getpwuid(users, statbuf->uid) : NULL;
+	struct bfs_users *users = directive->ptr;
+	const struct passwd *pwd = bfs_getpwuid(users, statbuf->uid);
 	if (!pwd) {
 		return bfs_printf_U(cfile, directive, ftwbuf);
 	}
@@ -733,24 +733,18 @@ int bfs_printf_parse(const struct bfs_ctx *ctx, struct bfs_expr *expr, const cha
 				directive.fn = bfs_printf_f;
 				break;
 			case 'F':
-				directive.ptr = bfs_ctx_mtab(ctx);
+				directive.fn = bfs_printf_F;
+				directive.ptr = (void *)bfs_ctx_mtab(ctx);
 				if (!directive.ptr) {
 					int error = errno;
 					bfs_expr_error(ctx, expr);
 					bfs_error(ctx, "Couldn't parse the mount table: %s.\n", strerror(error));
 					goto directive_error;
 				}
-				directive.fn = bfs_printf_F;
 				break;
 			case 'g':
-				directive.ptr = bfs_ctx_groups(ctx);
-				if (!directive.ptr) {
-					int error = errno;
-					bfs_expr_error(ctx, expr);
-					bfs_error(ctx, "Couldn't parse the group table: %s.\n", strerror(error));
-					goto directive_error;
-				}
 				directive.fn = bfs_printf_g;
+				directive.ptr = ctx->groups;
 				break;
 			case 'G':
 				directive.fn = bfs_printf_G;
@@ -798,14 +792,8 @@ int bfs_printf_parse(const struct bfs_ctx *ctx, struct bfs_expr *expr, const cha
 				directive.stat_field = BFS_STAT_MTIME;
 				break;
 			case 'u':
-				directive.ptr = bfs_ctx_users(ctx);
-				if (!directive.ptr) {
-					int error = errno;
-					bfs_expr_error(ctx, expr);
-					bfs_error(ctx, "Couldn't parse the user table: %s.\n", strerror(error));
-					goto directive_error;
-				}
 				directive.fn = bfs_printf_u;
+				directive.ptr = ctx->users;
 				break;
 			case 'U':
 				directive.fn = bfs_printf_U;
diff --git a/src/pwcache.c b/src/pwcache.c
index 91435bd..7071f59 100644
--- a/src/pwcache.c
+++ b/src/pwcache.c
@@ -1,6 +1,6 @@
 /****************************************************************************
  * bfs                                                                      *
- * Copyright (C) 2020 Tavian Barnes <tavianator@tavianator.com>             *
+ * Copyright (C) 2020-2022 Tavian Barnes <tavianator@tavianator.com>        *
  *                                                                          *
  * Permission to use, copy, modify, and/or distribute this software for any *
  * purpose with or without fee is hereby granted.                           *
@@ -23,270 +23,200 @@
 #include <stdbool.h>
 #include <stdlib.h>
 #include <string.h>
+#include <unistd.h>
 
-struct bfs_users {
-	/** The array of passwd entries. */
-	struct passwd *entries;
-	/** A map from usernames to entries. */
-	struct trie by_name;
-	/** A map from UIDs to entries. */
-	struct trie by_uid;
-};
+/** Represents cache hits for negative results. */
+static void *MISSING = &MISSING;
 
-struct bfs_users *bfs_users_parse(void) {
-	int error;
+/** Callback type for bfs_getent(). */
+typedef void *bfs_getent_fn(const void *key, void *ent, void *buf, size_t bufsize);
 
-	struct bfs_users *users = malloc(sizeof(*users));
-	if (!users) {
-		return NULL;
+/** Shared scaffolding for get{pw,gr}{nam,?id}_r(). */
+static void *bfs_getent(struct trie_leaf *leaf, bfs_getent_fn *fn, const void *key, size_t entsize, size_t bufsize) {
+	if (leaf->value) {
+		errno = 0;
+		return leaf->value == MISSING ? NULL : leaf->value;
 	}
 
-	users->entries = NULL;
-	trie_init(&users->by_name);
-	trie_init(&users->by_uid);
-
-	setpwent();
-
+	void *buf = NULL;
 	while (true) {
-		errno = 0;
-		struct passwd *ent = getpwent();
-		if (!ent) {
-			if (errno) {
-				error = errno;
-				goto fail_end;
-			} else {
-				break;
-			}
-		}
-
-		if (DARRAY_PUSH(&users->entries, ent) != 0) {
-			error = errno;
-			goto fail_end;
+		void *result = buf;
+		buf = realloc(buf, entsize + bufsize);
+		if (!buf) {
+			free(result);
+			return NULL;
 		}
 
-		ent = users->entries + darray_length(users->entries) - 1;
-		ent->pw_name = strdup(ent->pw_name);
-		ent->pw_dir = strdup(ent->pw_dir);
-		ent->pw_shell = strdup(ent->pw_shell);
-		if (!ent->pw_name || !ent->pw_dir || !ent->pw_shell) {
-			error = ENOMEM;
-			goto fail_end;
+		result = fn(key, buf, (char *)buf + entsize, bufsize);
+		if (result) {
+			leaf->value = result;
+			return result;
+		} else if (errno == 0) {
+			free(buf);
+			leaf->value = MISSING;
+			return NULL;
+		} else if (errno == ERANGE) {
+			bufsize *= 2;
+		} else {
+			free(buf);
+			return NULL;
 		}
 	}
+}
 
-	endpwent();
+struct bfs_users {
+	/** Initial buffer size for getpw*_r(). */
+	size_t bufsize;
+	/** A map from usernames to entries. */
+	struct trie by_name;
+	/** A map from UIDs to entries. */
+	struct trie by_uid;
+};
 
-	for (size_t i = 0; i < darray_length(users->entries); ++i) {
-		struct passwd *entry = &users->entries[i];
-		struct trie_leaf *leaf = trie_insert_str(&users->by_name, entry->pw_name);
-		if (leaf) {
-			if (!leaf->value) {
-				leaf->value = entry;
-			}
-		} else {
-			error = errno;
-			goto fail_free;
-		}
+struct bfs_users *bfs_users_new(void) {
+	struct bfs_users *users = malloc(sizeof(*users));
+	if (!users) {
+		return NULL;
+	}
 
-		leaf = trie_insert_mem(&users->by_uid, &entry->pw_uid, sizeof(entry->pw_uid));
-		if (leaf) {
-			if (!leaf->value) {
-				leaf->value = entry;
-			}
-		} else {
-			error = errno;
-			goto fail_free;
-		}
+	long bufsize = sysconf(_SC_GETPW_R_SIZE_MAX);
+	if (bufsize > 0) {
+		users->bufsize = bufsize;
+	} else {
+		users->bufsize = 1024;
 	}
 
+	trie_init(&users->by_name);
+	trie_init(&users->by_uid);
 	return users;
+}
 
-fail_end:
-	endpwent();
-fail_free:
-	bfs_users_free(users);
-	errno = error;
-	return NULL;
+/** bfs_getent() callback for getpwnam_r(). */
+static void *bfs_getpwnam_impl(const void *key, void *ent, void *buf, size_t bufsize) {
+	struct passwd *result;
+	errno = getpwnam_r(key, ent, buf, bufsize, &result);
+	return result;
 }
 
-const struct passwd *bfs_getpwnam(const struct bfs_users *users, const char *name) {
-	const struct trie_leaf *leaf = trie_find_str(&users->by_name, name);
-	if (leaf) {
-		return leaf->value;
-	} else {
+const struct passwd *bfs_getpwnam(struct bfs_users *users, const char *name) {
+	struct trie_leaf *leaf = trie_insert_str(&users->by_name, name);
+	if (!leaf) {
 		return NULL;
 	}
+
+	return bfs_getent(leaf, bfs_getpwnam_impl, name, sizeof(struct passwd), users->bufsize);
 }
 
-const struct passwd *bfs_getpwuid(const struct bfs_users *users, uid_t uid) {
-	const struct trie_leaf *leaf = trie_find_mem(&users->by_uid, &uid, sizeof(uid));
-	if (leaf) {
-		return leaf->value;
-	} else {
+/** bfs_getent() callback for getpwuid_r(). */
+static void *bfs_getpwuid_impl(const void *key, void *ent, void *buf, size_t bufsize) {
+	struct passwd *result;
+	errno = getpwuid_r(*(const uid_t *)key, ent, buf, bufsize, &result);
+	return result;
+}
+
+const struct passwd *bfs_getpwuid(struct bfs_users *users, uid_t uid) {
+	struct trie_leaf *leaf = trie_insert_mem(&users->by_uid, &uid, sizeof(uid));
+	if (!leaf) {
 		return NULL;
 	}
+
+	return bfs_getent(leaf, bfs_getpwuid_impl, &uid, sizeof(struct passwd), users->bufsize);
 }
 
 void bfs_users_free(struct bfs_users *users) {
 	if (users) {
+		TRIE_FOR_EACH(&users->by_uid, leaf) {
+			if (leaf->value != MISSING) {
+				free(leaf->value);
+			}
+		}
 		trie_destroy(&users->by_uid);
-		trie_destroy(&users->by_name);
 
-		for (size_t i = 0; i < darray_length(users->entries); ++i) {
-			struct passwd *entry = &users->entries[i];
-			free(entry->pw_shell);
-			free(entry->pw_dir);
-			free(entry->pw_name);
+		TRIE_FOR_EACH(&users->by_name, leaf) {
+			if (leaf->value != MISSING) {
+				free(leaf->value);
+			}
 		}
-		darray_free(users->entries);
+		trie_destroy(&users->by_name);
 
 		free(users);
 	}
 }
 
 struct bfs_groups {
-	/** The array of group entries. */
-	struct group *entries;
+	/** Initial buffer size for getgr*_r(). */
+	size_t bufsize;
 	/** A map from group names to entries. */
 	struct trie by_name;
 	/** A map from GIDs to entries. */
 	struct trie by_gid;
 };
 
-/**
- * struct group::gr_mem isn't properly aligned on macOS, so do this to avoid
- * ASAN warnings.
- */
-static char *next_gr_mem(void **gr_mem) {
-	char *mem;
-	memcpy(&mem, *gr_mem, sizeof(mem));
-	*gr_mem = (char *)*gr_mem + sizeof(mem);
-	return mem;
-}
-
-struct bfs_groups *bfs_groups_parse(void) {
-	int error;
-
+struct bfs_groups *bfs_groups_new(void) {
 	struct bfs_groups *groups = malloc(sizeof(*groups));
 	if (!groups) {
 		return NULL;
 	}
 
-	groups->entries = NULL;
-	trie_init(&groups->by_name);
-	trie_init(&groups->by_gid);
-
-	setgrent();
-
-	while (true) {
-		errno = 0;
-		struct group *ent = getgrent();
-		if (!ent) {
-			if (errno) {
-				error = errno;
-				goto fail_end;
-			} else {
-				break;
-			}
-		}
-
-		if (DARRAY_PUSH(&groups->entries, ent) != 0) {
-			error = errno;
-			goto fail_end;
-		}
-		ent = groups->entries + darray_length(groups->entries) - 1;
-
-		void *members = ent->gr_mem;
-		ent->gr_mem = NULL;
-
-		ent->gr_name = strdup(ent->gr_name);
-		if (!ent->gr_name) {
-			error = errno;
-			goto fail_end;
-		}
-
-		for (char *mem = next_gr_mem(&members); mem; mem = next_gr_mem(&members)) {
-			char *dup = strdup(mem);
-			if (!dup) {
-				error = errno;
-				goto fail_end;
-			}
-
-			if (DARRAY_PUSH(&ent->gr_mem, &dup) != 0) {
-				error = errno;
-				free(dup);
-				goto fail_end;
-			}
-		}
-	}
-
-	endgrent();
-
-	for (size_t i = 0; i < darray_length(groups->entries); ++i) {
-		struct group *entry = &groups->entries[i];
-		struct trie_leaf *leaf = trie_insert_str(&groups->by_name, entry->gr_name);
-		if (leaf) {
-			if (!leaf->value) {
-				leaf->value = entry;
-			}
-		} else {
-			error = errno;
-			goto fail_free;
-		}
-
-		leaf = trie_insert_mem(&groups->by_gid, &entry->gr_gid, sizeof(entry->gr_gid));
-		if (leaf) {
-			if (!leaf->value) {
-				leaf->value = entry;
-			}
-		} else {
-			error = errno;
-			goto fail_free;
-		}
+	long bufsize = sysconf(_SC_GETGR_R_SIZE_MAX);
+	if (bufsize > 0) {
+		groups->bufsize = bufsize;
+	} else {
+		groups->bufsize = 1024;
 	}
 
+	trie_init(&groups->by_name);
+	trie_init(&groups->by_gid);
 	return groups;
+}
 
-fail_end:
-	endgrent();
-fail_free:
-	bfs_groups_free(groups);
-	errno = error;
-	return NULL;
+/** bfs_getent() callback for getgrnam_r(). */
+static void *bfs_getgrnam_impl(const void *key, void *ent, void *buf, size_t bufsize) {
+	struct group *result;
+	errno = getgrnam_r(key, ent, buf, bufsize, &result);
+	return result;
 }
 
-const struct group *bfs_getgrnam(const struct bfs_groups *groups, const char *name) {
-	const struct trie_leaf *leaf = trie_find_str(&groups->by_name, name);
-	if (leaf) {
-		return leaf->value;
-	} else {
+const struct group *bfs_getgrnam(struct bfs_groups *groups, const char *name) {
+	struct trie_leaf *leaf = trie_insert_str(&groups->by_name, name);
+	if (!leaf) {
 		return NULL;
 	}
+
+	return bfs_getent(leaf, bfs_getgrnam_impl, name, sizeof(struct group), groups->bufsize);
 }
 
-const struct group *bfs_getgrgid(const struct bfs_groups *groups, gid_t gid) {
-	const struct trie_leaf *leaf = trie_find_mem(&groups->by_gid, &gid, sizeof(gid));
-	if (leaf) {
-		return leaf->value;
-	} else {
+/** bfs_getent() callback for getgrgid_r(). */
+static void *bfs_getgrgid_impl(const void *key, void *ent, void *buf, size_t bufsize) {
+	struct group *result;
+	errno = getgrgid_r(*(const gid_t *)key, ent, buf, bufsize, &result);
+	return result;
+}
+
+const struct group *bfs_getgrgid(struct bfs_groups *groups, gid_t gid) {
+	struct trie_leaf *leaf = trie_insert_mem(&groups->by_gid, &gid, sizeof(gid));
+	if (!leaf) {
 		return NULL;
 	}
+
+	return bfs_getent(leaf, bfs_getgrgid_impl, &gid, sizeof(struct group), groups->bufsize);
 }
 
 void bfs_groups_free(struct bfs_groups *groups) {
 	if (groups) {
+		TRIE_FOR_EACH(&groups->by_gid, leaf) {
+			if (leaf->value != MISSING) {
+				free(leaf->value);
+			}
+		}
 		trie_destroy(&groups->by_gid);
-		trie_destroy(&groups->by_name);
 
-		for (size_t i = 0; i < darray_length(groups->entries); ++i) {
-			struct group *entry = &groups->entries[i];
-			for (size_t j = 0; j < darray_length(entry->gr_mem); ++j) {
-				free(entry->gr_mem[j]);
+		TRIE_FOR_EACH(&groups->by_name, leaf) {
+			if (leaf->value != MISSING) {
+				free(leaf->value);
 			}
-			darray_free(entry->gr_mem);
-			free(entry->gr_name);
 		}
-		darray_free(groups->entries);
+		trie_destroy(&groups->by_name);
 
 		free(groups);
 	}
diff --git a/src/pwcache.h b/src/pwcache.h
index f1a1db3..6ae8bea 100644
--- a/src/pwcache.h
+++ b/src/pwcache.h
@@ -25,92 +25,96 @@
 #include <pwd.h>
 
 /**
- * The user table.
+ * A user cache.
  */
 struct bfs_users;
 
 /**
- * Parse the user table.
+ * Create a user cache.
  *
  * @return
- *         The parsed user table, or NULL on failure.
+ *         A new user cache, or NULL on failure.
  */
-struct bfs_users *bfs_users_parse(void);
+struct bfs_users *bfs_users_new(void);
 
 /**
  * Get a user entry by name.
  *
  * @param users
- *         The user table.
+ *         The user cache.
  * @param name
  *         The username to look up.
  * @return
- *         The matching user, or NULL if not found.
+ *         The matching user, or NULL if not found (errno == 0) or an error
+ *         occurred (errno != 0).
  */
-const struct passwd *bfs_getpwnam(const struct bfs_users *users, const char *name);
+const struct passwd *bfs_getpwnam(struct bfs_users *users, const char *name);
 
 /**
  * Get a user entry by ID.
  *
  * @param users
- *         The user table.
+ *         The user cache.
  * @param uid
  *         The ID to look up.
  * @return
- *         The matching user, or NULL if not found.
+ *         The matching user, or NULL if not found (errno == 0) or an error
+ *         occurred (errno != 0).
  */
-const struct passwd *bfs_getpwuid(const struct bfs_users *users, uid_t uid);
+const struct passwd *bfs_getpwuid(struct bfs_users *users, uid_t uid);
 
 /**
- * Free a user table.
+ * Free a user cache.
  *
  * @param users
- *         The user table to free.
+ *         The user cache to free.
  */
 void bfs_users_free(struct bfs_users *users);
 
 /**
- * The group table.
+ * A group cache.
  */
 struct bfs_groups;
 
 /**
- * Parse the group table.
+ * Create a group cache.
  *
  * @return
- *         The parsed group table, or NULL on failure.
+ *         A new group cache, or NULL on failure.
  */
-struct bfs_groups *bfs_groups_parse(void);
+struct bfs_groups *bfs_groups_new(void);
 
 /**
  * Get a group entry by name.
  *
  * @param groups
- *         The group table.
+ *         The group cache.
  * @param name
  *         The group name to look up.
  * @return
- *         The matching group, or NULL if not found.
+ *         The matching group, or NULL if not found (errno == 0) or an error
+ *         occurred (errno != 0).
  */
-const struct group *bfs_getgrnam(const struct bfs_groups *groups, const char *name);
+const struct group *bfs_getgrnam(struct bfs_groups *groups, const char *name);
 
 /**
  * Get a group entry by ID.
  *
  * @param groups
- *         The group table.
+ *         The group cache.
  * @param uid
  *         The ID to look up.
  * @return
- *         The matching group, or NULL if not found.
+ *         The matching group, or NULL if not found (errno == 0) or an error
+ *         occurred (errno != 0).
  */
-const struct group *bfs_getgrgid(const struct bfs_groups *groups, gid_t gid);
+const struct group *bfs_getgrgid(struct bfs_groups *groups, gid_t gid);
 
 /**
- * Free a group table.
+ * Free a group cache.
  *
  * @param groups
- *         The group table to free.
+ *         The group cache to free.
  */
 void bfs_groups_free(struct bfs_groups *groups);
 
diff --git a/tests/posix/nogroup_ulimit.sh b/tests/posix/nogroup_ulimit.sh
index e7231d9..8f758c4 100644
--- a/tests/posix/nogroup_ulimit.sh
+++ b/tests/posix/nogroup_ulimit.sh
@@ -1,3 +1,8 @@
 closefrom 4
 ulimit -n 16
-bfs_diff deep -nogroup
+
+# -mindepth 18, but POSIX
+path="*/*/*/*/*/*"
+path="$path/$path/$path"
+bfs_diff deep -path "deep/$path" -nogroup
+
diff --git a/tests/posix/nouser_ulimit.sh b/tests/posix/nouser_ulimit.sh
index 1d0dd65..2777589 100644
--- a/tests/posix/nouser_ulimit.sh
+++ b/tests/posix/nouser_ulimit.sh
@@ -1,3 +1,7 @@
 closefrom 4
 ulimit -n 16
-bfs_diff deep -nouser
+
+# -mindepth 18, but POSIX
+path="*/*/*/*/*/*"
+path="$path/$path/$path"
+bfs_diff deep -path "deep/$path" -nouser