From 0f09fc54fdf6d5cd453ea0e9fb363756baf87dae Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Tue, 9 Feb 2016 10:34:36 -0500 Subject: Implement -L/-follow. --- bftw.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++---------------- bftw.h | 14 ++++++++--- parse.c | 15 +++++++++-- tests.sh | 27 +++++++++++++++----- 4 files changed, 110 insertions(+), 34 deletions(-) diff --git a/bftw.c b/bftw.c index e445432..d2a73d6 100644 --- a/bftw.c +++ b/bftw.c @@ -27,7 +27,9 @@ #include #include #include +#include #include +#include #include #include #include @@ -104,6 +106,11 @@ struct dircache_entry { /** Reference count. */ size_t refcount; + /** The device number, for cycle detection. */ + dev_t dev; + /** The inode number, for cycle detection. */ + ino_t ino; + /** The offset of this directory in the full path. */ size_t nameoff; /** The length of the directory's name. */ @@ -438,11 +445,7 @@ static struct dircache_entry *dirqueue_pop(struct dirqueue *queue) { return entry; } -static void ftwbuf_set_error(struct BFTW *ftwbuf, int error) { - ftwbuf->typeflag = BFTW_ERROR; - ftwbuf->error = error; -} - +/** Fill in ftwbuf fields with information from a struct dirent. */ static void ftwbuf_use_dirent(struct BFTW *ftwbuf, const struct dirent *de) { #if defined(_DIRENT_HAVE_D_TYPE) || defined(DT_DIR) switch (de->d_type) { @@ -471,6 +474,7 @@ static void ftwbuf_use_dirent(struct BFTW *ftwbuf, const struct dirent *de) { #endif } +/** Call stat() and use the results. */ static int ftwbuf_stat(struct BFTW *ftwbuf, struct stat *sb, int flags) { int ret = fstatat(ftwbuf->at_fd, ftwbuf->at_path, sb, flags); if (ret != 0) { @@ -534,13 +538,14 @@ struct bftw_state { /** The cache of open directories. */ struct dircache cache; + + /** The queue of directories left to explore. */ + struct dirqueue queue; /** The current dircache entry. */ struct dircache_entry *current; /** The current traversal status. */ enum bftw_status status; - /** The queue of directories left to explore. */ - struct dirqueue queue; /** The current path being explored. */ struct dynstr path; @@ -561,10 +566,10 @@ static void bftw_state_init(struct bftw_state *state, bftw_fn *fn, int nopenfd, state->error = 0; dircache_init(&state->cache, nopenfd); - state->current = NULL; - state->status = BFTW_CURRENT; dirqueue_init(&state->queue); + state->current = NULL; + state->status = BFTW_CURRENT; dynstr_init(&state->path); } @@ -585,6 +590,15 @@ static int bftw_path_concat(struct bftw_state *state, const char *subpath) { return dynstr_concat(&state->path, nameoff, subpath); } +/** + * Record an error. + */ +static void bftw_set_error(struct bftw_state *state, int error) { + state->error = error; + state->ftwbuf.error = error; + state->ftwbuf.typeflag = BFTW_ERROR; +} + /** * Initialize the buffers with data about the current path. */ @@ -620,16 +634,15 @@ static void bftw_init_buffers(struct bftw_state *state, const struct dirent *de) ftwbuf->typeflag = BFTW_UNKNOWN; } - bool follow; - if (state->flags & BFTW_FOLLOW_ROOT) { - follow = !state->current; - } else { - follow = false; - } + bool follow = state->flags & (current ? BFTW_FOLLOW_NONROOT : BFTW_FOLLOW_ROOT); + + bool detect_cycles = (state->flags & BFTW_DETECT_CYCLES) + && state->status == BFTW_CHILD; if ((state->flags & BFTW_STAT) || ftwbuf->typeflag == BFTW_UNKNOWN - || (ftwbuf->typeflag == BFTW_LNK && follow)) { + || (ftwbuf->typeflag == BFTW_LNK && follow) + || (ftwbuf->typeflag == BFTW_DIR && detect_cycles)) { int flags = follow ? 0 : AT_SYMLINK_NOFOLLOW; int ret = ftwbuf_stat(ftwbuf, &state->statbuf, flags); @@ -640,8 +653,19 @@ static void bftw_init_buffers(struct bftw_state *state, const struct dirent *de) } if (ret != 0) { - state->error = errno; - ftwbuf_set_error(ftwbuf, state->error); + bftw_set_error(state, errno); + return; + } + + if (ftwbuf->typeflag == BFTW_DIR && detect_cycles) { + dev_t dev = ftwbuf->statbuf->st_dev; + ino_t ino = ftwbuf->statbuf->st_ino; + for (const struct dircache_entry *entry = current; entry; entry = entry->parent) { + if (dev == entry->dev && ino == entry->ino) { + bftw_set_error(state, ELOOP); + return; + } + } } } } @@ -672,11 +696,31 @@ static int bftw_handle_path(struct bftw_state *state) { } } +/** + * Add a new entry to the cache. + */ +static struct dircache_entry *bftw_add(struct bftw_state *state, const char *name) { + struct dircache_entry *entry = dircache_add(&state->cache, state->current, name); + if (!entry) { + return NULL; + } + + if (state->flags & BFTW_DETECT_CYCLES) { + const struct stat *statbuf = state->ftwbuf.statbuf; + if (statbuf) { + entry->dev = statbuf->st_dev; + entry->ino = statbuf->st_ino; + } + } + + return entry; +} + /** * Push a new entry onto the queue. */ static int bftw_push(struct bftw_state *state, const char *name) { - struct dircache_entry *entry = dircache_add(&state->cache, state->current, name); + struct dircache_entry *entry = bftw_add(state, name); if (!entry) { return -1; } @@ -791,7 +835,7 @@ int bftw(const char *path, bftw_fn *fn, int nopenfd, enum bftw_flags flags, void // Now start the breadth-first search - state.current = dircache_add(&state.cache, NULL, path); + state.current = bftw_add(&state, path); if (!state.current) { goto fail; } @@ -803,10 +847,10 @@ int bftw(const char *path, bftw_fn *fn, int nopenfd, enum bftw_flags flags, void DIR *dir = dircache_entry_open(&state.cache, state.current, state.path.str); if (!dir) { - state.error = errno; + int error = errno; bftw_init_buffers(&state, NULL); - ftwbuf_set_error(&state.ftwbuf, state.error); + bftw_set_error(&state, error); switch (bftw_handle_path(&state)) { case BFTW_CONTINUE: diff --git a/bftw.h b/bftw.h index 4b81123..6f6108b 100644 --- a/bftw.h +++ b/bftw.h @@ -105,13 +105,19 @@ typedef enum bftw_action bftw_fn(struct BFTW *ftwbuf, void *ptr); */ enum bftw_flags { /** stat() each encountered file. */ - BFTW_STAT = 1 << 0, + BFTW_STAT = 1 << 0, /** Attempt to recover from encountered errors. */ - BFTW_RECOVER = 1 << 1, + BFTW_RECOVER = 1 << 1, /** Visit directories in post-order as well as pre-order. */ - BFTW_DEPTH = 1 << 2, + BFTW_DEPTH = 1 << 2, /** If the initial path is a symbolic link, follow it. */ - BFTW_FOLLOW_ROOT = 1 << 3, + BFTW_FOLLOW_ROOT = 1 << 3, + /** Follow non-root symbolic links. */ + BFTW_FOLLOW_NONROOT = 1 << 4, + /** Follow all symbolic links. */ + BFTW_FOLLOW = BFTW_FOLLOW_ROOT | BFTW_FOLLOW_NONROOT, + /** Detect directory cycles. */ + BFTW_DETECT_CYCLES = 1 << 5, }; /** diff --git a/parse.c b/parse.c index 93657c8..4613aed 100644 --- a/parse.c +++ b/parse.c @@ -345,7 +345,7 @@ static struct expr *parse_acnewer(struct parser_state *state, const char *option struct stat sb; - bool follow = state->cl->flags & BFTW_FOLLOW_ROOT; + bool follow = state->cl->flags & BFTW_FOLLOW; int flags = follow ? 0 : AT_SYMLINK_NOFOLLOW; if (fstatat(AT_FDCWD, expr->sdata, &sb, flags) != 0) { @@ -471,18 +471,26 @@ static struct expr *parse_literal(struct parser_state *state) { switch (arg[1]) { case 'P': if (strcmp(arg, "-P") == 0) { - state->cl->flags &= ~BFTW_FOLLOW_ROOT; + state->cl->flags &= ~(BFTW_FOLLOW | BFTW_DETECT_CYCLES); return new_option(state, arg); } break; case 'H': if (strcmp(arg, "-H") == 0) { + state->cl->flags &= ~(BFTW_FOLLOW_NONROOT | BFTW_DETECT_CYCLES); state->cl->flags |= BFTW_FOLLOW_ROOT; return new_option(state, arg); } break; + case 'L': + if (strcmp(arg, "-L") == 0) { + state->cl->flags |= BFTW_FOLLOW | BFTW_DETECT_CYCLES; + return new_option(state, arg); + } + break; + case 'a': if (strcmp(arg, "-amin") == 0) { return parse_acmtime(state, arg, ATIME, MINUTES); @@ -529,6 +537,9 @@ static struct expr *parse_literal(struct parser_state *state) { case 'f': if (strcmp(arg, "-false") == 0) { return &expr_false; + } else if (strcmp(arg, "-follow") == 0) { + state->cl->flags |= BFTW_FOLLOW | BFTW_DETECT_CYCLES; + return new_option(state, arg); } break; diff --git a/tests.sh b/tests.sh index 493bfab..8c8c347 100755 --- a/tests.sh +++ b/tests.sh @@ -33,10 +33,10 @@ function links_structure() { touchp "$1/a" ln -s a "$1/b" ln "$1/a" "$1/c" - mkdir -p "$1/d/e" - ln -s ../../d "$1/d/e/f" - touchp "$1/d/e/g" - ln -s q "$1/d/e/h" + mkdir -p "$1/d/e/f" + ln -s ../../d "$1/d/e/g" + ln -s d/e "$1/h" + ln -s q "$1/d/e/i" } # Checks for any (order-independent) differences between bfs and find @@ -171,10 +171,25 @@ function test_0023() { function test_0024() { links_structure "$1" - find_diff -H "$1/d/e/h" + find_diff -H "$1/d/e/i" } -for i in {1..24}; do +function test_0025() { + links_structure "$1" + find_diff -L "$1" 2>/dev/null +} + +function test_0026() { + links_structure "$1" + find_diff "$1" -follow 2>/dev/null +} + +function test_0027() { + links_structure "$1" + find_diff -L "$1" -depth 2>/dev/null +} + +for i in {1..27}; do dir="$(mktemp -d "${TMPDIR:-/tmp}"/bfs.XXXXXXXXXX)" test="test_$(printf '%04d' $i)" "$test" "$dir" -- cgit v1.2.3