From 1c184e718f5745cf3a53a3c389814a792e73aa51 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 29 Feb 2020 18:35:55 -0500 Subject: passwd: Cache the user/group tables MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This is a significant optimization for conditions that need these tables: Benchmark #1: ./bfs ~/code/linux -nouser >/dev/null Time (mean ± σ): 232.0 ms ± 2.5 ms [User: 44.3 ms, System: 185.0 ms] Range (min … max): 228.7 ms … 238.7 ms 12 runs Benchmark #2: ./bfs-1.6 ~/code/linux -nouser >/dev/null Time (mean ± σ): 1.050 s ± 0.012 s [User: 544.2 ms, System: 500.0 ms] Range (min … max): 1.025 s … 1.063 s 10 runs Benchmark #3: find ~/code/linux -nouser >/dev/null Time (mean ± σ): 1.040 s ± 0.012 s [User: 533.6 ms, System: 500.6 ms] Range (min … max): 1.017 s … 1.054 s 10 runs Summary './bfs ~/code/linux -nouser >/dev/null' ran 4.48 ± 0.07 times faster than 'find ~/code/linux -nouser >/dev/null' 4.52 ± 0.07 times faster than './bfs-1.6 ~/code/linux -nouser >/dev/null' --- Makefile | 1 + cmdline.h | 9 +++ eval.c | 29 ++----- main.c | 1 + parse.c | 50 ++++++++++-- passwd.c | 272 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ passwd.h | 117 +++++++++++++++++++++++++++ printf.c | 27 +++++-- 8 files changed, 471 insertions(+), 35 deletions(-) create mode 100644 passwd.c create mode 100644 passwd.h diff --git a/Makefile b/Makefile index 8121e2f..5bd8ab8 100644 --- a/Makefile +++ b/Makefile @@ -86,6 +86,7 @@ bfs: \ mtab.o \ opt.o \ parse.o \ + passwd.o \ printf.o \ spawn.o \ stat.o \ diff --git a/cmdline.h b/cmdline.h index 6670696..422fc6c 100644 --- a/cmdline.h +++ b/cmdline.h @@ -63,6 +63,15 @@ struct cmdline { /** Colored stderr. */ CFILE *cerr; + /** User table. */ + 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. */ + int groups_error; + /** Table of mounted file systems. */ struct bfs_mtab *mtab; /** The error that occurred parsing the mount table, if any. */ diff --git a/eval.c b/eval.c index 010fef9..bdf4d99 100644 --- a/eval.c +++ b/eval.c @@ -28,6 +28,7 @@ #include "exec.h" #include "fsade.h" #include "mtab.h" +#include "passwd.h" #include "printf.h" #include "stat.h" #include "time.h" @@ -294,16 +295,7 @@ bool eval_nogroup(const struct expr *expr, struct eval_state *state) { return false; } - errno = 0; - if (getgrgid(statbuf->gid) == NULL) { - if (errno == 0) { - return true; - } else { - eval_report_error(state); - } - } - - return false; + return bfs_getgrgid(state->cmdline->groups, statbuf->gid) == NULL; } /** @@ -315,16 +307,7 @@ bool eval_nouser(const struct expr *expr, struct eval_state *state) { return false; } - errno = 0; - if (getpwuid(statbuf->uid) == NULL) { - if (errno == 0) { - return true; - } else { - eval_report_error(state); - } - } - - return false; + return bfs_getpwuid(state->cmdline->users, statbuf->uid) == NULL; } /** @@ -603,6 +586,8 @@ bool eval_perm(const struct expr *expr, struct eval_state *state) { bool eval_fls(const struct expr *expr, struct eval_state *state) { CFILE *cfile = expr->cfile; FILE *file = cfile->file; + const struct bfs_users *users = state->cmdline->users; + const struct bfs_groups *groups = state->cmdline->groups; const struct BFTW *ftwbuf = state->ftwbuf; const struct bfs_stat *statbuf = eval_stat(state); if (!statbuf) { @@ -620,7 +605,7 @@ bool eval_fls(const struct expr *expr, struct eval_state *state) { } uintmax_t uid = statbuf->uid; - struct passwd *pwd = getpwuid(uid); + const struct passwd *pwd = users ? bfs_getpwuid(users, uid) : NULL; if (pwd) { if (fprintf(file, " %-8s", pwd->pw_name) < 0) { goto error; @@ -632,7 +617,7 @@ bool eval_fls(const struct expr *expr, struct eval_state *state) { } uintmax_t gid = statbuf->gid; - struct group *grp = getgrgid(gid); + const struct group *grp = groups ? bfs_getgrgid(groups, gid) : NULL; if (grp) { if (fprintf(file, " %-8s", grp->gr_name) < 0) { goto error; diff --git a/main.c b/main.c index b8d7bae..442f66a 100644 --- a/main.c +++ b/main.c @@ -40,6 +40,7 @@ * - dstring.[ch] (a dynamic string library) * - fsade.[ch] (a facade over non-standard filesystem features) * - mtab.[ch] (parses the system's mount table) + * - passwd.[ch] (a cache for the user/group tables) * - spawn.[ch] (spawns processes) * - stat.[ch] (wraps stat(), or statx() on Linux) * - time.[ch] (date/time handling utilities) diff --git a/parse.c b/parse.c index 1de065b..891e6e1 100644 --- a/parse.c +++ b/parse.c @@ -31,6 +31,7 @@ #include "expr.h" #include "fsade.h" #include "mtab.h" +#include "passwd.h" #include "printf.h" #include "spawn.h" #include "stat.h" @@ -267,6 +268,9 @@ int free_cmdline(struct cmdline *cmdline) { free_bfs_mtab(cmdline->mtab); + bfs_free_groups(cmdline->groups); + bfs_free_users(cmdline->users); + struct trie_leaf *leaf; while ((leaf = trie_first_leaf(&cmdline->open_files))) { struct open_file *ofile = leaf->value; @@ -1299,7 +1303,6 @@ static struct expr *parse_fls(struct parser_state *state, int arg1, int arg2) { if (expr) { expr_set_always_true(expr); expr->cost = PRINT_COST; - expr->ephemeral_fds = 1; if (expr_open(state, expr, expr->sdata) != 0) { goto fail; } @@ -1414,6 +1417,12 @@ static struct expr *parse_fstype(struct parser_state *state, int arg1, int arg2) * Parse -gid/-group. */ static struct expr *parse_group(struct parser_state *state, int arg1, int arg2) { + struct cmdline *cmdline = state->cmdline; + if (!cmdline->groups) { + parse_error(state, "Couldn't parse the group table: %s.\n", strerror(cmdline->groups_error)); + return NULL; + } + const char *arg = state->argv[0]; struct expr *expr = parse_unary_test(state, eval_gid); @@ -1421,7 +1430,7 @@ static struct expr *parse_group(struct parser_state *state, int arg1, int arg2) return NULL; } - struct group *grp = getgrnam(expr->sdata); + const struct group *grp = bfs_getgrnam(cmdline->groups, expr->sdata); if (grp) { expr->idata = grp->gr_gid; expr->cmp_flag = CMP_EXACT; @@ -1466,6 +1475,12 @@ static struct expr *parse_used(struct parser_state *state, int arg1, int arg2) { * Parse -uid/-user. */ static struct expr *parse_user(struct parser_state *state, int arg1, int arg2) { + struct cmdline *cmdline = state->cmdline; + if (!cmdline->users) { + parse_error(state, "Couldn't parse the user table: %s.\n", strerror(cmdline->users_error)); + return NULL; + } + const char *arg = state->argv[0]; struct expr *expr = parse_unary_test(state, eval_uid); @@ -1473,7 +1488,7 @@ static struct expr *parse_user(struct parser_state *state, int arg1, int arg2) { return NULL; } - struct passwd *pwd = getpwnam(expr->sdata); + const struct passwd *pwd = bfs_getpwnam(cmdline->users, expr->sdata); if (pwd) { expr->idata = pwd->pw_uid; expr->cmp_flag = CMP_EXACT; @@ -1545,7 +1560,6 @@ static struct expr *parse_ls(struct parser_state *state, int arg1, int arg2) { struct expr *expr = parse_nullary_action(state, eval_fls); if (expr) { init_print_expr(state, expr); - expr->ephemeral_fds = 1; expr->reftime = state->now; } return expr; @@ -1743,11 +1757,16 @@ fail: * Parse -nogroup. */ static struct expr *parse_nogroup(struct parser_state *state, int arg1, int arg2) { + struct cmdline *cmdline = state->cmdline; + if (!cmdline->groups) { + parse_error(state, "Couldn't parse the group table: %s.\n", strerror(cmdline->groups_error)); + return NULL; + } + struct expr *expr = parse_nullary_test(state, eval_nogroup); if (expr) { expr->cost = 9000.0; expr->probability = 0.01; - expr->ephemeral_fds = 1; } return expr; } @@ -1775,11 +1794,16 @@ static struct expr *parse_noleaf(struct parser_state *state, int arg1, int arg2) * Parse -nouser. */ static struct expr *parse_nouser(struct parser_state *state, int arg1, int arg2) { + struct cmdline *cmdline = state->cmdline; + if (!cmdline->users) { + parse_error(state, "Couldn't parse the user table: %s.\n", strerror(cmdline->users_error)); + return NULL; + } + struct expr *expr = parse_nullary_test(state, eval_nouser); if (expr) { expr->cost = 9000.0; expr->probability = 0.01; - expr->ephemeral_fds = 1; } return expr; } @@ -3452,6 +3476,10 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) { cmdline->colors = NULL; cmdline->cout = NULL; cmdline->cerr = NULL; + cmdline->users = NULL; + cmdline->users_error = 0; + cmdline->groups = NULL; + cmdline->groups_error = 0; cmdline->mtab = NULL; cmdline->mtab_error = 0; cmdline->mindepth = 0; @@ -3497,6 +3525,16 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) { goto fail; } + cmdline->users = bfs_parse_users(); + if (!cmdline->users) { + cmdline->users_error = errno; + } + + cmdline->groups = bfs_parse_groups(); + if (!cmdline->groups) { + cmdline->groups_error = errno; + } + cmdline->mtab = parse_bfs_mtab(); if (!cmdline->mtab) { cmdline->mtab_error = errno; diff --git a/passwd.c b/passwd.c new file mode 100644 index 0000000..ffb7b8c --- /dev/null +++ b/passwd.c @@ -0,0 +1,272 @@ +/**************************************************************************** + * bfs * + * Copyright (C) 2020 Tavian Barnes * + * * + * Permission to use, copy, modify, and/or distribute this software for any * + * purpose with or without fee is hereby granted. * + * * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * + ****************************************************************************/ + +#include "passwd.h" +#include "darray.h" +#include "trie.h" +#include +#include +#include +#include +#include + +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; +}; + +struct bfs_users *bfs_parse_users(void) { + int error; + + struct bfs_users *users = malloc(sizeof(*users)); + if (!users) { + return NULL; + } + + users->entries = NULL; + trie_init(&users->by_name); + trie_init(&users->by_uid); + + setpwent(); + + 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; + } + + 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; + } + } + + endpwent(); + + 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) { + leaf->value = entry; + } else { + error = errno; + goto fail_free; + } + + leaf = trie_insert_mem(&users->by_uid, &entry->pw_uid, sizeof(entry->pw_uid)); + if (leaf) { + leaf->value = entry; + } else { + error = errno; + goto fail_free; + } + } + + return users; + +fail_end: + endpwent(); +fail_free: + bfs_free_users(users); + errno = error; + return NULL; +} + +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 { + return NULL; + } +} + +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 { + return NULL; + } +} + +void bfs_free_users(struct bfs_users *users) { + if (users) { + 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); + } + darray_free(users->entries); + + free(users); + } +} + +struct bfs_groups { + /** The array of group entries. */ + struct group *entries; + /** A map from group names to entries. */ + struct trie by_name; + /** A map from GIDs to entries. */ + struct trie by_gid; +}; + +struct bfs_groups *bfs_parse_groups(void) { + int error; + + 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; + ent->gr_name = strdup(ent->gr_name); + if (!ent->gr_name) { + error = errno; + goto fail_end; + } + + char **members = ent->gr_mem; + ent->gr_mem = NULL; + for (char **mem = members; *mem; ++mem) { + 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) { + 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) { + leaf->value = entry; + } else { + error = errno; + goto fail_free; + } + } + + return groups; + +fail_end: + endgrent(); +fail_free: + bfs_free_groups(groups); + errno = error; + return NULL; +} + +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 { + return NULL; + } +} + +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 { + return NULL; + } +} + +void bfs_free_groups(struct bfs_groups *groups) { + if (groups) { + 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]); + } + darray_free(entry->gr_mem); + free(entry->gr_name); + } + darray_free(groups->entries); + + free(groups); + } +} diff --git a/passwd.h b/passwd.h new file mode 100644 index 0000000..a0b8c6b --- /dev/null +++ b/passwd.h @@ -0,0 +1,117 @@ +/**************************************************************************** + * bfs * + * Copyright (C) 2020 Tavian Barnes * + * * + * Permission to use, copy, modify, and/or distribute this software for any * + * purpose with or without fee is hereby granted. * + * * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * + ****************************************************************************/ + +/** + * A caching wrapper for /etc/{passwd,group}. + */ + +#ifndef BFS_PASSWD_H +#define BFS_PASSWD_H + +#include +#include + +/** + * The user table. + */ +struct bfs_users; + +/** + * Parse the user table. + * + * @return + * The parsed user table, or NULL on failure. + */ +struct bfs_users *bfs_parse_users(void); + +/** + * Get a user entry by name. + * + * @param users + * The user table. + * @param name + * The username to look up. + * @return + * The matching user, or NULL if not found. + */ +const struct passwd *bfs_getpwnam(const struct bfs_users *users, const char *name); + +/** + * Get a user entry by ID. + * + * @param users + * The user table. + * @param uid + * The ID to look up. + * @return + * The matching user, or NULL if not found. + */ +const struct passwd *bfs_getpwuid(const struct bfs_users *users, uid_t uid); + +/** + * Free a user table. + * + * @param users + * The user table to free. + */ +void bfs_free_users(struct bfs_users *users); + +/** + * The group table. + */ +struct bfs_groups; + +/** + * Parse the group table. + * + * @return + * The parsed group table, or NULL on failure. + */ +struct bfs_groups *bfs_parse_groups(void); + +/** + * Get a group entry by name. + * + * @param groups + * The group table. + * @param name + * The group name to look up. + * @return + * The matching group, or NULL if not found. + */ +const struct group *bfs_getgrnam(const struct bfs_groups *groups, const char *name); + +/** + * Get a group entry by ID. + * + * @param groups + * The group table. + * @param uid + * The ID to look up. + * @return + * The matching group, or NULL if not found. + */ +const struct group *bfs_getgrgid(const struct bfs_groups *groups, gid_t gid); + +/** + * Free a group table. + * + * @param groups + * The group table to free. + */ +void bfs_free_groups(struct bfs_groups *groups); + +#endif // BFS_PASSWD_H diff --git a/printf.c b/printf.c index 4e7af18..7bee795 100644 --- a/printf.c +++ b/printf.c @@ -21,6 +21,7 @@ #include "dstring.h" #include "expr.h" #include "mtab.h" +#include "passwd.h" #include "stat.h" #include "time.h" #include "util.h" @@ -45,8 +46,8 @@ struct bfs_printf { enum bfs_stat_field stat_field; /** Character data associated with this directive. */ char c; - /** The current mount table. */ - const struct bfs_mtab *mtab; + /** Some data used by the directive. */ + const void *ptr; /** The next printf directive in the chain. */ struct bfs_printf *next; }; @@ -217,7 +218,7 @@ static int bfs_printf_F(FILE *file, const struct bfs_printf *directive, const st return -1; } - const char *type = bfs_fstype(directive->mtab, statbuf); + const char *type = bfs_fstype(directive->ptr, statbuf); return fprintf(file, directive->str, type); } @@ -239,7 +240,8 @@ static int bfs_printf_g(FILE *file, const struct bfs_printf *directive, const st return -1; } - struct group *grp = getgrgid(statbuf->gid); + const struct bfs_groups *groups = directive->ptr; + const struct group *grp = groups ? bfs_getgrgid(groups, statbuf->gid) : NULL; if (!grp) { return bfs_printf_G(file, directive, ftwbuf); } @@ -410,7 +412,8 @@ static int bfs_printf_u(FILE *file, const struct bfs_printf *directive, const st return -1; } - struct passwd *pwd = getpwuid(statbuf->uid); + const struct bfs_users *users = directive->ptr; + const struct passwd *pwd = users ? bfs_getpwuid(users, statbuf->uid) : NULL; if (!pwd) { return bfs_printf_U(file, directive, ftwbuf); } @@ -512,7 +515,7 @@ static struct bfs_printf *new_directive(bfs_printf_fn *fn) { } directive->stat_field = 0; directive->c = 0; - directive->mtab = NULL; + directive->ptr = NULL; directive->next = NULL; return directive; @@ -686,10 +689,15 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline) bfs_error(cmdline, "Couldn't parse the mount table: %s.\n", strerror(cmdline->mtab_error)); goto directive_error; } + directive->ptr = cmdline->mtab; directive->fn = bfs_printf_F; - directive->mtab = cmdline->mtab; break; case 'g': + if (!cmdline->groups) { + bfs_error(cmdline, "Couldn't parse the group table: %s.\n", strerror(cmdline->groups_error)); + goto directive_error; + } + directive->ptr = cmdline->groups; directive->fn = bfs_printf_g; break; case 'G': @@ -738,6 +746,11 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline) directive->stat_field = BFS_STAT_MTIME; break; case 'u': + if (!cmdline->users) { + bfs_error(cmdline, "Couldn't parse the user table: %s.\n", strerror(cmdline->users_error)); + goto directive_error; + } + directive->ptr = cmdline->users; directive->fn = bfs_printf_u; break; case 'U': -- cgit v1.2.3