From a559ffac8c65f469adefcd2d4a5c41790d7e6d05 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Mon, 15 Apr 2019 10:21:22 -0400 Subject: [WIP] bftw: Push all files onto the queue before visiting them --- bftw.c | 308 +++++++++++++++++++++++++++-------------------------------------- bftw.h | 2 - eval.c | 6 +- exec.c | 1 + 4 files changed, 131 insertions(+), 186 deletions(-) diff --git a/bftw.c b/bftw.c index aee3689..ca0b06d 100644 --- a/bftw.c +++ b/bftw.c @@ -1,6 +1,6 @@ /**************************************************************************** * bfs * - * Copyright (C) 2015-2018 Tavian Barnes * + * Copyright (C) 2015-2019 Tavian Barnes * * * * Permission to use, copy, modify, and/or distribute this software for any * * purpose with or without fee is hereby granted. * @@ -67,6 +67,8 @@ struct bftw_file { /** An open descriptor to this file, or -1. */ int fd; + /** The type of the file. */ + enum bftw_typeflag typeflag; /** The device number, for cycle detection. */ dev_t dev; /** The inode number, for cycle detection. */ @@ -315,6 +317,7 @@ static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_fil file->refcount = 1; file->fd = -1; + file->typeflag = BFTW_UNKNOWN; file->dev = -1; file->ino = -1; @@ -531,7 +534,7 @@ struct bftw_reader { /** The file object. */ struct bftw_file *file; /** The path to the directory. */ - char *path; + const char *path; /** The open handle to the directory. */ DIR *handle; /** The current directory entry. */ @@ -541,17 +544,12 @@ struct bftw_reader { }; /** Initialize a reader. */ -static int bftw_reader_init(struct bftw_reader *reader) { - reader->path = dstralloc(0); - if (!reader->path) { - return -1; - } - +static void bftw_reader_init(struct bftw_reader *reader) { reader->file = NULL; + reader->path = NULL; reader->handle = NULL; reader->de = NULL; reader->error = 0; - return 0; } /** Read a directory entry. */ @@ -565,20 +563,15 @@ static int bftw_reader_read(struct bftw_reader *reader) { } /** Open a directory for reading. */ -static int bftw_reader_open(struct bftw_reader *reader, struct bftw_cache *cache, struct bftw_file *file) { +static int bftw_reader_open(struct bftw_reader *reader, struct bftw_cache *cache, struct bftw_file *file, const char *path) { assert(!reader->handle); assert(!reader->de); reader->file = file; + reader->path = path; reader->error = 0; - if (bftw_file_path(file, &reader->path) != 0) { - reader->error = errno; - dstresize(&reader->path, 0); - return -1; - } - - reader->handle = bftw_file_opendir(cache, file, reader->path); + reader->handle = bftw_file_opendir(cache, file, path); if (!reader->handle) { reader->error = errno; return -1; @@ -608,8 +601,6 @@ static void bftw_reader_destroy(struct bftw_reader *reader) { if (reader->handle) { bftw_reader_close(reader); } - - dstrfree(reader->path); } /** @@ -749,16 +740,6 @@ static enum bftw_typeflag bftw_dirent_typeflag(const struct dirent *de) { return BFTW_UNKNOWN; } -/** Call stat() and use the results. */ -static int bftw_stat(struct BFTW *ftwbuf, struct bfs_stat *sb) { - int ret = bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, ftwbuf->at_flags, BFS_STAT_BROKEN_OK, sb); - if (ret == 0) { - ftwbuf->statbuf = sb; - ftwbuf->typeflag = bftw_mode_typeflag(sb->mode); - } - return ret; -} - /** * Holds the current state of the bftw() traversal. */ @@ -780,6 +761,10 @@ struct bftw_state { /** The queue of files left to explore. */ struct bftw_queue queue; + /** The current file. */ + struct bftw_file *file; + /** The current path. */ + char *path; /** The reader for the current directory. */ struct bftw_reader reader; /** Whether the current visit is pre- or post-order. */ @@ -818,10 +803,15 @@ static int bftw_state_init(struct bftw_state *state, const char *root, const str bftw_queue_init(&state->queue); - if (bftw_reader_init(&state->reader) != 0) { + state->file = NULL; + + state->path = dstralloc(0); + if (!state->path) { goto err_cache; } + bftw_reader_init(&state->reader); + state->visit = BFTW_PRE; return 0; @@ -832,36 +822,6 @@ err: return -1; } -/** - * Update the path for the current file. - */ -static int bftw_update_path(struct bftw_state *state) { - struct bftw_reader *reader = &state->reader; - struct bftw_file *file = reader->file; - struct dirent *de = reader->de; - - size_t length = file->nameoff + file->namelen; - - if (dstrlen(reader->path) < length) { - errno = reader->error; - return -1; - } - dstresize(&reader->path, length); - - if (de) { - if (reader->path[length - 1] != '/') { - if (dstrapp(&reader->path, '/') != 0) { - return -1; - } - } - if (dstrcat(&reader->path, reader->de->d_name) != 0) { - return -1; - } - } - - return 0; -} - /** Check if a stat() call is needed for this visit. */ static bool bftw_need_stat(struct bftw_state *state) { if (state->flags & BFTW_STAT) { @@ -897,54 +857,57 @@ static bool bftw_need_stat(struct bftw_state *state) { return false; } +/** Call stat() and use the results. */ +static int bftw_stat(struct bftw_state *state) { + struct BFTW *ftwbuf = &state->ftwbuf; + struct bfs_stat *statbuf = &state->statbuf; + struct bftw_file *file = state->file; + + int ret = bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, ftwbuf->at_flags, BFS_STAT_BROKEN_OK, statbuf); + if (ret == 0) { + ftwbuf->statbuf = statbuf; + ftwbuf->typeflag = bftw_mode_typeflag(statbuf->mode); + file->typeflag = ftwbuf->typeflag; + file->dev = statbuf->dev; + file->ino = statbuf->ino; + } else { + ftwbuf->typeflag = BFTW_ERROR; + ftwbuf->error = errno; + } + return ret; +} + /** * Initialize the buffers with data about the current path. */ static void bftw_prepare_visit(struct bftw_state *state) { + struct bftw_file *file = state->file; struct bftw_reader *reader = &state->reader; - struct bftw_file *file = reader->file; - struct dirent *de = reader->de; struct BFTW *ftwbuf = &state->ftwbuf; - ftwbuf->path = file ? reader->path : state->root; + ftwbuf->path = state->path; ftwbuf->root = state->root; - ftwbuf->depth = 0; + ftwbuf->depth = file->depth; ftwbuf->visit = state->visit; + ftwbuf->typeflag = file->typeflag; ftwbuf->error = reader->error; ftwbuf->statbuf = NULL; ftwbuf->at_fd = AT_FDCWD; ftwbuf->at_path = ftwbuf->path; ftwbuf->at_flags = AT_SYMLINK_NOFOLLOW; - if (file) { - ftwbuf->depth = file->depth; - - if (de) { - ftwbuf->nameoff = bftw_child_nameoff(file); - ++ftwbuf->depth; - - ftwbuf->at_fd = file->fd; - ftwbuf->at_path += ftwbuf->nameoff; - } else { - ftwbuf->nameoff = file->nameoff; - bftw_file_base(file, &ftwbuf->at_fd, &ftwbuf->at_path); - } - } - if (ftwbuf->depth == 0) { // Compute the name offset for root paths like "foo/bar" ftwbuf->nameoff = xbasename(ftwbuf->path) - ftwbuf->path; + } else { + ftwbuf->nameoff = file->nameoff; } + bftw_file_base(file, &ftwbuf->at_fd, &ftwbuf->at_path); + if (ftwbuf->error != 0) { ftwbuf->typeflag = BFTW_ERROR; return; - } else if (de) { - ftwbuf->typeflag = bftw_dirent_typeflag(de); - } else if (ftwbuf->depth > 0) { - ftwbuf->typeflag = BFTW_DIR; - } else { - ftwbuf->typeflag = BFTW_UNKNOWN; } int follow_flags = BFTW_LOGICAL; @@ -957,9 +920,7 @@ static void bftw_prepare_visit(struct bftw_state *state) { } if (bftw_need_stat(state)) { - if (bftw_stat(ftwbuf, &state->statbuf) != 0) { - ftwbuf->typeflag = BFTW_ERROR; - ftwbuf->error = errno; + if (bftw_stat(state) != 0) { return; } } @@ -982,29 +943,24 @@ static void bftw_prepare_visit(struct bftw_state *state) { /** * Invoke the callback. */ -static enum bftw_action bftw_visit_path(struct bftw_state *state) { - if (state->reader.file) { - if (bftw_update_path(state) != 0) { - state->error = errno; - return BFTW_STOP; - } - } +static enum bftw_action bftw_visit(struct bftw_state *state) { + const struct bftw_file *file = state->file; + size_t pathlen = file->nameoff + file->namelen; + dstresize(&state->path, pathlen); bftw_prepare_visit(state); - // Never give the callback BFTW_ERROR unless BFTW_RECOVER is specified - if (state->ftwbuf.typeflag == BFTW_ERROR && !(state->flags & BFTW_RECOVER)) { + if (file->typeflag == BFTW_ERROR && !(state->flags & BFTW_RECOVER)) { + // Never give the callback BFTW_ERROR unless BFTW_RECOVER is specified state->error = state->ftwbuf.error; return BFTW_STOP; } - // Defensive copy - struct BFTW ftwbuf = state->ftwbuf; - - enum bftw_action action = state->callback(&ftwbuf, state->ptr); + enum bftw_action action = state->callback(&state->ftwbuf, state->ptr); switch (action) { case BFTW_CONTINUE: - case BFTW_SKIP_SIBLINGS: + break; + case BFTW_SKIP_SUBTREE: case BFTW_STOP: return action; @@ -1013,23 +969,31 @@ static enum bftw_action bftw_visit_path(struct bftw_state *state) { state->error = EINVAL; return BFTW_STOP; } + + if (file->typeflag != BFTW_DIR) { + return BFTW_SKIP_SUBTREE; + } + + if ((state->flags & BFTW_XDEV) && file->parent && file->dev != file->parent->dev) { + return BFTW_SKIP_SUBTREE; + } + + return BFTW_CONTINUE; } /** * Push a new directory onto the queue. */ -static int bftw_push(struct bftw_state *state, const char *name) { - struct bftw_file *parent = state->reader.file; +static int bftw_push(struct bftw_state *state, const char *name, struct dirent *de) { + struct bftw_file *parent = state->file; struct bftw_file *file = bftw_file_new(&state->cache, parent, name); if (!file) { state->error = errno; return -1; } - const struct bfs_stat *statbuf = state->ftwbuf.statbuf; - if (statbuf) { - file->dev = statbuf->dev; - file->ino = statbuf->ino; + if (de) { + file->typeflag = bftw_dirent_typeflag(de); } bftw_queue_push(&state->queue, file); @@ -1037,46 +1001,54 @@ static int bftw_push(struct bftw_state *state, const char *name) { } /** - * Pop a directory from the queue and start reading it. + * Pop a file from the queue. */ -static struct bftw_reader *bftw_pop(struct bftw_state *state) { - struct bftw_reader *reader = &state->reader; - struct bftw_file *file = bftw_queue_pop(&state->queue); - bftw_reader_open(reader, &state->cache, file); - return reader; +static struct bftw_file *bftw_pop(struct bftw_state *state) { + state->file = bftw_queue_pop(&state->queue); + + if (bftw_file_path(state->file, &state->path) == 0) { + return state->file; + } else { + dstresize(&state->path, 0); + return NULL; + } +} + +/** + * Open the current directory. + */ +static struct bftw_reader *bftw_open(struct bftw_state *state) { + bftw_reader_open(&state->reader, &state->cache, state->file, state->path); + return &state->reader; } /** * Finalize and free a file we're done with. */ -static enum bftw_action bftw_release_file(struct bftw_state *state, struct bftw_file *file, bool do_visit) { +static enum bftw_action bftw_release_file(struct bftw_state *state, bool do_visit) { enum bftw_action ret = BFTW_CONTINUE; - if (!(state->flags & BFTW_DEPTH)) { - do_visit = false; - } - state->visit = BFTW_POST; - while (file) { - bftw_file_decref(&state->cache, file); - if (file->refcount > 0) { + while (state->file) { + bftw_file_decref(&state->cache, state->file); + if (state->file->refcount > 0) { break; } if (do_visit) { - state->reader.file = file; - if (bftw_visit_path(state) == BFTW_STOP) { + if (bftw_visit(state) == BFTW_STOP) { ret = BFTW_STOP; do_visit = false; } } - struct bftw_file *parent = file->parent; - bftw_file_free(&state->cache, file); - file = parent; + struct bftw_file *parent = state->file->parent; + bftw_file_free(&state->cache, state->file); + state->file = parent; } + state->file = NULL; state->visit = BFTW_PRE; return ret; } @@ -1094,20 +1066,13 @@ static enum bftw_action bftw_release_reader(struct bftw_state *state, bool do_vi if (reader->error != 0) { if (do_visit) { - if (bftw_visit_path(state) == BFTW_STOP) { - ret = BFTW_STOP; - do_visit = false; - } + ret = bftw_visit(state); } else { state->error = reader->error; } reader->error = 0; } - if (bftw_release_file(state, reader->file, do_visit) == BFTW_STOP) { - ret = BFTW_STOP; - } - reader->file = NULL; return ret; @@ -1126,10 +1091,16 @@ static int bftw_state_destroy(struct bftw_state *state) { } bftw_reader_destroy(reader); + if (state->file) { + bftw_release_file(state, false); + } + + dstrfree(state->path); + struct bftw_queue *queue = &state->queue; while (queue->head) { - struct bftw_file *file = bftw_queue_pop(queue); - bftw_release_file(state, file, false); + state->file = bftw_queue_pop(queue); + bftw_release_file(state, false); } bftw_cache_destroy(&state->cache); @@ -1148,69 +1119,48 @@ int bftw(const char *path, const struct bftw_args *args) { return -1; } - // Handle 'path' itself first - switch (bftw_visit_path(&state)) { - case BFTW_SKIP_SUBTREE: - case BFTW_STOP: - goto done; - default: - break; - } - - if (state.ftwbuf.typeflag != BFTW_DIR) { - goto done; - } - - // Now start the breadth-first search - - if (bftw_push(&state, path) != 0) { + if (bftw_push(&state, path, NULL) != 0) { goto done; } while (state.queue.head) { - struct bftw_reader *reader = bftw_pop(&state); + struct bftw_file *file = bftw_pop(&state); + if (!file) { + goto done; + } + switch (bftw_visit(&state)) { + case BFTW_CONTINUE: + break; + case BFTW_SKIP_SUBTREE: + goto next; + case BFTW_STOP: + goto done; + } + + struct bftw_reader *reader = bftw_open(&state); while (reader->de) { const char *name = reader->de->d_name; if (name[0] == '.' && (name[1] == '\0' || (name[1] == '.' && name[2] == '\0'))) { goto read; } - switch (bftw_visit_path(&state)) { - case BFTW_CONTINUE: - break; - - case BFTW_SKIP_SIBLINGS: - goto next; - - case BFTW_SKIP_SUBTREE: - goto read; - - case BFTW_STOP: + if (bftw_push(&state, name, reader->de) != 0) { goto done; } - if (state.ftwbuf.typeflag == BFTW_DIR) { - const struct bfs_stat *statbuf = state.ftwbuf.statbuf; - if ((args->flags & BFTW_XDEV) - && statbuf - && statbuf->dev != reader->file->dev) { - goto read; - } - - if (bftw_push(&state, name) != 0) { - goto done; - } - } - read: bftw_reader_read(reader); } - next: if (bftw_release_reader(&state, true) == BFTW_STOP) { break; } + + next: + if (bftw_release_file(&state, true) == BFTW_STOP) { + break; + } } done: diff --git a/bftw.h b/bftw.h index e822523..eaeb92e 100644 --- a/bftw.h +++ b/bftw.h @@ -108,8 +108,6 @@ struct BFTW { enum bftw_action { /** Keep walking. */ BFTW_CONTINUE, - /** Skip this path's siblings. */ - BFTW_SKIP_SIBLINGS, /** Skip this path's children. */ BFTW_SKIP_SUBTREE, /** Stop walking. */ diff --git a/eval.c b/eval.c index 341b289..3b054fa 100644 --- a/eval.c +++ b/eval.c @@ -1206,7 +1206,6 @@ static const char *dump_bftw_visit(enum bftw_visit visit) { static const char *dump_bftw_action(enum bftw_action action) { static const char *actions[] = { DUMP_BFTW_MAP(BFTW_CONTINUE), - DUMP_BFTW_MAP(BFTW_SKIP_SIBLINGS), DUMP_BFTW_MAP(BFTW_SKIP_SUBTREE), DUMP_BFTW_MAP(BFTW_STOP), }; @@ -1273,11 +1272,8 @@ static enum bftw_action cmdline_callback(struct BFTW *ftwbuf, void *ptr) { state.action = BFTW_SKIP_SUBTREE; } - // In -depth mode, only handle directories on the BFTW_POST visit enum bftw_visit expected_visit = BFTW_PRE; - if ((cmdline->flags & BFTW_DEPTH) - && ftwbuf->typeflag == BFTW_DIR - && ftwbuf->depth < cmdline->maxdepth) { + if ((cmdline->flags & BFTW_DEPTH) && ftwbuf->depth < cmdline->maxdepth) { expected_visit = BFTW_POST; } diff --git a/exec.c b/exec.c index 3a35063..06703ad 100644 --- a/exec.c +++ b/exec.c @@ -265,6 +265,7 @@ static int bfs_exec_openwd(struct bfs_exec *execbuf, const struct BFTW *ftwbuf) assert(execbuf->wd_fd < 0); assert(!execbuf->wd_path); + assert(ftwbuf->depth == 0 || ftwbuf->at_path == xbasename(ftwbuf->path)); if (ftwbuf->at_fd != AT_FDCWD) { execbuf->wd_fd = ftwbuf->at_fd; if (!(execbuf->flags & BFS_EXEC_MULTI)) { -- cgit v1.2.3