summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bftw.c88
-rw-r--r--bftw.h14
-rw-r--r--parse.c15
-rwxr-xr-xtests.sh27
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 <dirent.h>
#include <errno.h>
#include <fcntl.h>
+#include <limits.h>
#include <stdbool.h>
+#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
@@ -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);
}
@@ -586,6 +591,15 @@ static int bftw_path_concat(struct bftw_state *state, const char *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.
*/
static void bftw_init_buffers(struct bftw_state *state, const struct dirent *de) {
@@ -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;
+ }
+ }
}
}
}
@@ -673,10 +697,30 @@ 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"
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-01 00:25:39 +0000