bftw: Work around d_type being wrong for bind mounts on Linux

C.f. https://savannah.gnu.org/bugs/?54913
C.f. https://lkml.org/lkml/2019/2/11/2027
Fixes https://github.com/tavianator/bfs/issues/37

8 files changed, 121 insertions, 43 deletions

diff --git a/bftw.c b/bftw.c
index 6795bd0..4f94a55 100644
--- a/bftw.c
+++ b/bftw.c
@@ -769,6 +769,8 @@ struct bftw_state {
 	void *ptr;
 	/** bftw() flags. */
 	enum bftw_flags flags;
+	/** The mount table. */
+	const struct bfs_mtab *mtab;
 
 	/** The appropriate errno value, if any. */
 	int error;
@@ -800,6 +802,7 @@ static int bftw_state_init(struct bftw_state *state, const char *root, const str
 	state->callback = args->callback;
 	state->ptr = args->ptr;
 	state->flags = args->flags;
+	state->mtab = args->mtab;
 
 	state->error = 0;
 
@@ -863,6 +866,41 @@ static int bftw_update_path(struct bftw_state *state) {
 	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) {
+		return true;
+	}
+
+	struct BFTW *ftwbuf = &state->ftwbuf;
+	if (ftwbuf->typeflag == BFTW_UNKNOWN) {
+		return true;
+	}
+
+	if (ftwbuf->typeflag == BFTW_LNK && !(ftwbuf->at_flags & AT_SYMLINK_NOFOLLOW)) {
+		return true;
+	}
+
+	if (ftwbuf->typeflag == BFTW_DIR) {
+		if (state->flags & (BFTW_DETECT_CYCLES | BFTW_XDEV)) {
+			return true;
+		}
+#if __linux__
+	} else if (state->mtab) {
+		// Linux fills in d_type from the underlying inode, even when
+		// the directory entry is a bind mount point.  In that case, we
+		// need to stat() to get the correct type.  We don't need to
+		// check for directories because they can only be mounted over
+		// by other directories.
+		if (bfs_maybe_mount(state->mtab, ftwbuf->path)) {
+			return true;
+		}
+#endif
+	}
+
+	return false;
+}
+
 /**
  * Initialize the buffers with data about the current path.
  */
@@ -875,8 +913,8 @@ static void bftw_prepare_visit(struct bftw_state *state) {
 	ftwbuf->path = dir ? reader->path : state->root;
 	ftwbuf->root = state->root;
 	ftwbuf->depth = 0;
-	ftwbuf->error = reader->error;
 	ftwbuf->visit = state->visit;
+	ftwbuf->error = reader->error;
 	ftwbuf->statbuf = NULL;
 	ftwbuf->at_fd = AT_FDCWD;
 	ftwbuf->at_path = ftwbuf->path;
@@ -922,29 +960,24 @@ static void bftw_prepare_visit(struct bftw_state *state) {
 		ftwbuf->at_flags = 0;
 	}
 
-	bool detect_cycles = (state->flags & BFTW_DETECT_CYCLES) && de;
-
-	bool xdev = state->flags & BFTW_XDEV;
-
-	if ((state->flags & BFTW_STAT)
-	    || ftwbuf->typeflag == BFTW_UNKNOWN
-	    || (ftwbuf->typeflag == BFTW_LNK && follow)
-	    || (ftwbuf->typeflag == BFTW_DIR && (detect_cycles || xdev))) {
+	if (bftw_need_stat(state)) {
 		if (bftw_stat(ftwbuf, &state->statbuf) != 0) {
-			ftwbuf->error = errno;
 			ftwbuf->typeflag = BFTW_ERROR;
+			ftwbuf->error = errno;
 			return;
 		}
+	}
 
-		if (ftwbuf->typeflag == BFTW_DIR && detect_cycles) {
-			dev_t dev = ftwbuf->statbuf->dev;
-			ino_t ino = ftwbuf->statbuf->ino;
-			for (const struct bftw_dir *parent = dir; parent; parent = parent->parent) {
-				if (dev == parent->dev && ino == parent->ino) {
-					ftwbuf->error = ELOOP;
-					ftwbuf->typeflag = BFTW_ERROR;
-					return;
-				}
+	if (ftwbuf->typeflag == BFTW_DIR && (state->flags & BFTW_DETECT_CYCLES)) {
+		const struct bfs_stat *statbuf = ftwbuf->statbuf;
+		for (const struct bftw_dir *parent = dir; parent; parent = parent->parent) {
+			if (parent->depth == ftwbuf->depth) {
+				continue;
+			}
+			if (parent->dev == statbuf->dev && parent->ino == statbuf->ino) {
+				ftwbuf->typeflag = BFTW_ERROR;
+				ftwbuf->error = ELOOP;
+				return;
 			}
 		}
 	}
diff --git a/bftw.h b/bftw.h
index 6d1850f..e822523 100644
--- a/bftw.h
+++ b/bftw.h
@@ -21,6 +21,7 @@
 #ifndef BFS_BFTW_H
 #define BFS_BFTW_H
 
+#include "mtab.h"
 #include "stat.h"
 #include <stddef.h>
 
@@ -159,6 +160,8 @@ struct bftw_args {
 	int nopenfd;
 	/** Flags that control bftw() behaviour. */
 	enum bftw_flags flags;
+	/** The parsed mount table, if available. */
+	const struct bfs_mtab *mtab;
 };
 
 /**
diff --git a/cmdline.h b/cmdline.h
index 06b8725..bb36a8d 100644
--- a/cmdline.h
+++ b/cmdline.h
@@ -75,6 +75,8 @@ struct cmdline {
 
 	/** Table of mounted file systems. */
 	struct bfs_mtab *mtab;
+	/** The error that occurred parsing the mount table, if any. */
+	int mtab_error;
 
 	/** -mindepth option. */
 	int mindepth;
diff --git a/eval.c b/eval.c
index 028b31d..bb89401 100644
--- a/eval.c
+++ b/eval.c
@@ -1400,19 +1400,26 @@ int eval_cmdline(const struct cmdline *cmdline) {
 		.ptr = &args,
 		.nopenfd = infer_fdlimit(cmdline),
 		.flags = cmdline->flags,
+		.mtab = cmdline->mtab,
 	};
 
 	for (struct root *root = cmdline->roots; root && !args.quit; root = root->next) {
 		if (cmdline->debug & DEBUG_SEARCH) {
 			fprintf(stderr,
-				"bftw(\"%s\", { "
-				".callback = cmdline_callback, "
-				".ptr = &args, "
-				".nopenfd = %d, "
-				".flags = ",
-				root->path,
-				bftw_args.nopenfd);
+			        "bftw(\"%s\", { "
+			        ".callback = cmdline_callback, "
+			        ".ptr = &args, "
+			        ".nopenfd = %d, "
+			        ".flags = ",
+			        root->path,
+			        bftw_args.nopenfd);
 			dump_bftw_flags(bftw_args.flags);
+			fprintf(stderr, ", .mtab = ");
+			if (bftw_args.mtab) {
+				fprintf(stderr, "cmdline->mtab");
+			} else {
+				fprintf(stderr, "NULL");
+			}
 			fprintf(stderr, " })\n");
 		}
 
diff --git a/mtab.c b/mtab.c
index 0887f49..e2b89c9 100644
--- a/mtab.c
+++ b/mtab.c
@@ -19,6 +19,7 @@
 #include "util.h"
 #include <errno.h>
 #include <fcntl.h>
+#include <stdbool.h>
 #include <stdlib.h>
 #include <string.h>
 #include <sys/stat.h>
@@ -49,13 +50,20 @@
 #endif
 
 struct bfs_mtab {
+	/** A map from device ID to file system type. */
 	struct trie types;
+	/** The names of all the mount points. */
+	struct trie names;
 };
 
 /**
  * Add an entry to the mount table.
  */
-static int bfs_mtab_add(struct bfs_mtab *mtab, dev_t dev, const char *type) {
+static int bfs_mtab_add(struct bfs_mtab *mtab, const char *path, dev_t dev, const char *type) {
+	if (!trie_insert_str(&mtab->names, xbasename(path))) {
+		return -1;
+	}
+
 	struct trie_leaf *leaf = trie_insert_mem(&mtab->types, &dev, sizeof(dev));
 	if (!leaf) {
 		return -1;
@@ -91,6 +99,7 @@ struct bfs_mtab *parse_bfs_mtab() {
 		goto fail_file;
 	}
 	trie_init(&mtab->types);
+	trie_init(&mtab->names);
 
 	struct mntent *mnt;
 	while ((mnt = getmntent(file))) {
@@ -99,7 +108,7 @@ struct bfs_mtab *parse_bfs_mtab() {
 			continue;
 		}
 
-		if (bfs_mtab_add(mtab, sb.dev, mnt->mnt_type) != 0) {
+		if (bfs_mtab_add(mtab, mnt->mnt_dir, sb.dev, mnt->mnt_type) != 0) {
 			goto fail_mtab;
 		}
 	}
@@ -127,6 +136,7 @@ fail:
 		goto fail;
 	}
 	trie_init(&mtab->types);
+	trie_init(&mtab->names);
 
 	for (struct statfs *mnt = mntbuf; mnt < mntbuf + size; ++mnt) {
 		struct bfs_stat sb;
@@ -134,7 +144,7 @@ fail:
 			continue;
 		}
 
-		if (bfs_mtab_add(mtab, sb.dev, mnt->f_fstypename) != 0) {
+		if (bfs_mtab_add(mtab, mnt->f_mntonname, sb.dev, mnt->f_fstypename) != 0) {
 			goto fail_mtab;
 		}
 	}
@@ -158,6 +168,7 @@ fail:
 		goto fail_file;
 	}
 	trie_init(&mtab->types);
+	trie_init(&mtab->names);
 
 	struct mnttab mnt;
 	while (getmntent(file, &mnt) == 0) {
@@ -166,7 +177,7 @@ fail:
 			continue;
 		}
 
-		if (bfs_mtab_add(mtab, sb.dev, mnt.mnt_fstype) != 0) {
+		if (bfs_mtab_add(mtab, mnt.mnt_mountp, sb.dev, mnt.mnt_fstype) != 0) {
 			goto fail_mtab;
 		}
 	}
@@ -197,15 +208,22 @@ const char *bfs_fstype(const struct bfs_mtab *mtab, const struct bfs_stat *statb
 	}
 }
 
+bool bfs_maybe_mount(const struct bfs_mtab *mtab, const char *path) {
+	const char *name = xbasename(path);
+	return trie_find_str(&mtab->names, name);
+}
+
 void free_bfs_mtab(struct bfs_mtab *mtab) {
 	if (mtab) {
+		trie_destroy(&mtab->names);
+
 		struct trie_leaf *leaf;
 		while ((leaf = trie_first_leaf(&mtab->types))) {
 			free((char *)leaf->value);
 			trie_remove_mem(&mtab->types, leaf->key, leaf->length);
 		}
-
 		trie_destroy(&mtab->types);
+
 		free(mtab);
 	}
 }
diff --git a/mtab.h b/mtab.h
index ef22716..a80deb2 100644
--- a/mtab.h
+++ b/mtab.h
@@ -22,6 +22,7 @@
 #define BFS_MTAB_H
 
 #include "stat.h"
+#include <stdbool.h>
 
 /**
  * A file system mount table.
@@ -31,7 +32,8 @@ struct bfs_mtab;
 /**
  * Parse the mount table.
  *
- * @return The parsed mount table, or NULL on error.
+ * @return
+ *         The parsed mount table, or NULL on error.
  */
 struct bfs_mtab *parse_bfs_mtab(void);
 
@@ -42,12 +44,25 @@ struct bfs_mtab *parse_bfs_mtab(void);
  *         The current mount table.
  * @param statbuf
  *         The bfs_stat() buffer for the file in question.
- * @return The type of file system containing this file, "unknown" if not known,
+ * @return
+ *         The type of file system containing this file, "unknown" if not known,
  *         or NULL on error.
  */
 const char *bfs_fstype(const struct bfs_mtab *mtab, const struct bfs_stat *statbuf);
 
 /**
+ * Check if a file could be a mount point.
+ *
+ * @param mtab
+ *         The current mount table.
+ * @param path
+ *         The path to check.
+ * @return
+ *         Whether the named file could be a mount point.
+ */
+bool bfs_maybe_mount(const struct bfs_mtab *mtab, const char *path);
+
+/**
  * Free a mount table.
  */
 void free_bfs_mtab(struct bfs_mtab *mtab);
diff --git a/parse.c b/parse.c
index f58b716..e6716eb 100644
--- a/parse.c
+++ b/parse.c
@@ -1376,11 +1376,8 @@ fail:
 static struct expr *parse_fstype(struct parser_state *state, int arg1, int arg2) {
 	struct cmdline *cmdline = state->cmdline;
 	if (!cmdline->mtab) {
-		cmdline->mtab = parse_bfs_mtab();
-		if (!cmdline->mtab) {
-			parse_error(state, "Couldn't parse the mount table: %m.\n");
-			return NULL;
-		}
+		parse_error(state, "Couldn't parse the mount table: %s.\n", strerror(cmdline->mtab_error));
+		return NULL;
 	}
 
 	struct expr *expr = parse_unary_test(state, eval_fstype);
@@ -3126,6 +3123,7 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
 	cmdline->cout = NULL;
 	cmdline->cerr = NULL;
 	cmdline->mtab = NULL;
+	cmdline->mtab_error = 0;
 	cmdline->mindepth = 0;
 	cmdline->maxdepth = INT_MAX;
 	cmdline->flags = BFTW_RECOVER;
@@ -3162,6 +3160,11 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
 		goto fail;
 	}
 
+	cmdline->mtab = parse_bfs_mtab();
+	if (!cmdline->mtab) {
+		cmdline->mtab_error = errno;
+	}
+
 	bool stderr_tty = cmdline->cerr->colors;
 	bool stdin_tty = isatty(STDIN_FILENO);
 
diff --git a/printf.c b/printf.c
index b13f43f..164717c 100644
--- a/printf.c
+++ b/printf.c
@@ -630,11 +630,8 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 				break;
 			case 'F':
 				if (!cmdline->mtab) {
-					cmdline->mtab = parse_bfs_mtab();
-					if (!cmdline->mtab) {
-						bfs_error(cmdline, "Couldn't parse the mount table: %m.\n");
-						goto directive_error;
-					}
+					bfs_error(cmdline, "Couldn't parse the mount table: %s.\n", strerror(cmdline->mtab_error));
+					goto directive_error;
 				}
 				directive->fn = bfs_printf_F;
 				directive->mtab = cmdline->mtab;