Add a helper utility to compare filesystem trees

The intended use case is to compare two mounted or unpacke squashfs
images, so a repacked test image can be compared against its original
or an image unpacked with unsquashfs can be compared with an image
unpacked by rdsquashfs or sqfs2tar.

Since the tool is only intended to aid development (specifically
automated testing), it is not installed by `make install`.

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

9 files changed, 467 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
index 06eb71e..2fecd17 100644
--- a/.gitignore
+++ b/.gitignore
@@ -24,3 +24,4 @@ sqfs2tar
 tar2sqfs
 test_*
 test-*
+fscompare
diff --git a/Makefile.am b/Makefile.am
index 155ac08..4fb779d 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -4,6 +4,7 @@ AM_CPPFLAGS = -I$(top_srcdir)/include -D_GNU_SOURCE
 AM_CFLAGS = $(WARN_CFLAGS)
 
 noinst_LIBRARIES =
+noinst_PROGRAMS =
 bin_PROGRAMS =
 dist_man1_MANS =
 check_PROGRAMS =
@@ -16,4 +17,5 @@ include lib/Makemodule.am
 include tar/Makemodule.am
 include mkfs/Makemodule.am
 include unpack/Makemodule.am
+include difftool/Makemodule.am
 include tests/Makemodule.am
diff --git a/difftool/Makemodule.am b/difftool/Makemodule.am
new file mode 100644
index 0000000..4a03495
--- /dev/null
+++ b/difftool/Makemodule.am
@@ -0,0 +1,6 @@
+fscompare_SOURCES = difftool/fscompare.c difftool/difftool.h difftool/util.c
+fscompare_SOURCES += difftool/compare_dir.c difftool/node_compare.c
+fscompare_SOURCES += difftool/compare_file.c
+fscompare_LDADD = libfstree.a libutil.a
+
+noinst_PROGRAMS += fscompare
diff --git a/difftool/compare_dir.c b/difftool/compare_dir.c
new file mode 100644
index 0000000..8d4a186
--- /dev/null
+++ b/difftool/compare_dir.c
@@ -0,0 +1,97 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * compare_dir.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "difftool.h"
+
+int compare_dir_entries(tree_node_t *a, tree_node_t *b)
+{
+	tree_node_t *ait = a->data.dir->children, *aprev = NULL;
+	tree_node_t *bit = b->data.dir->children, *bprev = NULL;
+	int ret, result = 0;
+	char *path, arrow;
+
+	while (ait != NULL && bit != NULL) {
+		ret = strcmp(ait->name, bit->name);
+
+		if (ret < 0) {
+			result = 1;
+			path = node_path(ait);
+			if (path == NULL)
+				return -1;
+			fprintf(stdout, "< %s\n", path);
+			free(path);
+
+			if (aprev == NULL) {
+				a->data.dir->children = ait->next;
+				free(ait);
+				ait = a->data.dir->children;
+			} else {
+				aprev->next = ait->next;
+				free(ait);
+				ait = aprev->next;
+			}
+		} else if (ret > 0) {
+			result = 1;
+			path = node_path(bit);
+			if (path == NULL)
+				return -1;
+			fprintf(stdout, "> %s\n", path);
+			free(path);
+
+			if (bprev == NULL) {
+				b->data.dir->children = bit->next;
+				free(bit);
+				bit = b->data.dir->children;
+			} else {
+				bprev->next = bit->next;
+				free(bit);
+				bit = bprev->next;
+			}
+		} else {
+			aprev = ait;
+			ait = ait->next;
+
+			bprev = bit;
+			bit = bit->next;
+		}
+	}
+
+	if (ait != NULL || bit != NULL) {
+		result = 1;
+
+		if (ait != NULL) {
+			if (aprev == NULL) {
+				a->data.dir->children = NULL;
+			} else {
+				aprev->next = NULL;
+			}
+			arrow = '<';
+		} else {
+			if (bprev == NULL) {
+				b->data.dir->children = NULL;
+			} else {
+				bprev->next = NULL;
+			}
+			arrow = '>';
+			ait = bit;
+		}
+
+		while (ait != NULL) {
+			path = node_path(ait);
+			if (path == NULL) {
+				result = -1;
+			} else {
+				fprintf(stdout, "%c %s\n", arrow, path);
+				free(path);
+			}
+			aprev = ait;
+			ait = ait->next;
+			free(aprev);
+		}
+	}
+
+	return result;
+}
diff --git a/difftool/compare_file.c b/difftool/compare_file.c
new file mode 100644
index 0000000..c424220
--- /dev/null
+++ b/difftool/compare_file.c
@@ -0,0 +1,77 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * compare_file.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "difftool.h"
+
+int compare_files(file_info_t *a, file_info_t *b, const char *path)
+{
+	uint64_t offset, size, diff;
+	int ret = 0, afd, bfd;
+	void *aptr, *bptr;
+
+	if (a->size != b->size)
+		return 1;
+
+	if (pushd(first_path))
+		return -1;
+	afd = open(path, O_RDONLY);
+	if (afd < 0) {
+		fprintf(stderr, "%s/%s: %s\n", first_path, path,
+			strerror(errno));
+		return -1;
+	}
+	if (popd())
+		goto fail_afd;
+
+	if (pushd(second_path))
+		goto fail_afd;
+	bfd = open(path, O_RDONLY);
+	if (bfd < 0) {
+		fprintf(stderr, "%s/%s: %s\n", second_path, path,
+			strerror(errno));
+		goto fail_afd;
+	}
+	if (popd())
+		goto fail_bfd;
+
+	size = a->size;
+
+	for (offset = 0; offset < size; offset += diff) {
+		diff = size - offset;
+		if (diff > MAX_WINDOW_SIZE)
+			diff = MAX_WINDOW_SIZE;
+
+		aptr = mmap(NULL, diff, PROT_READ, MAP_SHARED, afd, offset);
+		if (aptr == MAP_FAILED) {
+			fprintf(stderr, "mmap %s/%s: %s\n", first_path, path,
+				strerror(errno));
+			goto fail_bfd;
+		}
+
+		bptr = mmap(NULL, diff, PROT_READ, MAP_SHARED, bfd, offset);
+		if (bptr == MAP_FAILED) {
+			fprintf(stderr, "mmap %s/%s: %s\n", second_path, path,
+				strerror(errno));
+			goto fail_bfd;
+		}
+
+		ret = memcmp(aptr, bptr, diff);
+		munmap(aptr, diff);
+		munmap(bptr, diff);
+
+		if (ret != 0)
+			break;
+	}
+
+	close(afd);
+	close(bfd);
+	return ret;
+fail_bfd:
+	close(bfd);
+fail_afd:
+	close(afd);
+	return -1;
+}
diff --git a/difftool/difftool.h b/difftool/difftool.h
new file mode 100644
index 0000000..0dea6d5
--- /dev/null
+++ b/difftool/difftool.h
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * difftool.h
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef DIFFTOOL_H
+#define DIFFTOOL_H
+
+#include "config.h"
+#include "fstree.h"
+#include "util.h"
+
+#include <sys/mman.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <getopt.h>
+#include <string.h>
+#include <errno.h>
+#include <fcntl.h>
+
+#define MAX_WINDOW_SIZE (1024 * 1024 * 4)
+
+extern const char *first_path;
+extern const char *second_path;
+extern int compare_flags;
+
+enum {
+	COMPARE_NO_PERM = 0x01,
+	COMPARE_NO_OWNER = 0x02,
+};
+
+int compare_dir_entries(tree_node_t *a, tree_node_t *b);
+
+char *node_path(tree_node_t *n);
+
+int compare_files(file_info_t *a, file_info_t *b, const char *path);
+
+int node_compare(tree_node_t *a, tree_node_t *b);
+
+#endif /* DIFFTOOL_H */
diff --git a/difftool/fscompare.c b/difftool/fscompare.c
new file mode 100644
index 0000000..c925adc
--- /dev/null
+++ b/difftool/fscompare.c
@@ -0,0 +1,118 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fscompare.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "difftool.h"
+
+static struct option long_opts[] = {
+	{ "no-owner", no_argument, NULL, 'O' },
+	{ "no-permissions", no_argument, NULL, 'P' },
+	{ "help", no_argument, NULL, 'h' },
+	{ "version", no_argument, NULL, 'V' },
+};
+
+static const char *short_opts = "OPhV";
+
+static const char *usagestr =
+"Usage: fscompare [OPTIONS...] <first> <second>\n"
+"\n"
+"Compare two directories, making sure that each contains the same entries.\n"
+"If an entry is a directory, comparison recurses into the directory.\n"
+"\n"
+"Possible options:\n"
+"\n"
+"  --no-owner, -O              Do not compare file owners.\n"
+"  --no-permissions, -P        Do not compare permission bits.\n"
+"\n"
+"  --help, -h                  Print help text and exit.\n"
+"  --version, -V               Print version information and exit.\n"
+"\n";
+
+const char *first_path;
+const char *second_path;
+int compare_flags = 0;
+
+static void process_options(int argc, char **argv)
+{
+	int i;
+
+	for (;;) {
+		i = getopt_long(argc, argv, short_opts, long_opts, NULL);
+		if (i == -1)
+			break;
+
+		switch (i) {
+		case 'O':
+			compare_flags |= COMPARE_NO_OWNER;
+			break;
+		case 'P':
+			compare_flags |= COMPARE_NO_PERM;
+			break;
+		case 'h':
+			fputs(usagestr, stdout);
+			exit(EXIT_SUCCESS);
+		case 'V':
+			print_version();
+			exit(EXIT_SUCCESS);
+		default:
+			goto fail_arg;
+		}
+	}
+
+	if (optind >= argc) {
+		fputs("Missing arguments: first directory\n", stderr);
+		goto fail_arg;
+	}
+
+	first_path = argv[optind++];
+
+	if (optind >= argc) {
+		fputs("Missing arguments: second directory\n", stderr);
+		goto fail_arg;
+	}
+
+	second_path = argv[optind++];
+
+	if (optind < argc) {
+		fputs("Unknown extra arguments\n", stderr);
+		goto fail_arg;
+	}
+	return;
+fail_arg:
+	fprintf(stderr, "Try `fscompare --help' for more information.\n");
+	exit(EXIT_FAILURE);
+}
+
+int main(int argc, char **argv)
+{
+	int ret = EXIT_FAILURE;
+	fstree_t afs, bfs;
+
+	process_options(argc, argv);
+
+	if (fstree_init(&afs, 512, NULL))
+		return EXIT_FAILURE;
+
+	if (fstree_init(&bfs, 512, NULL))
+		goto out_afs;
+
+	if (fstree_from_dir(&afs, first_path, false))
+		goto out_bfs;
+
+	if (fstree_from_dir(&bfs, second_path, false))
+		goto out_bfs;
+
+	tree_node_sort_recursive(afs.root);
+	tree_node_sort_recursive(bfs.root);
+
+	if (node_compare(afs.root, bfs.root) == 0)
+		ret = EXIT_SUCCESS;
+
+out_bfs:
+	fstree_cleanup(&bfs);
+out_afs:
+	fstree_cleanup(&afs);
+	return ret;
+}
diff --git a/difftool/node_compare.c b/difftool/node_compare.c
new file mode 100644
index 0000000..fae35ab
--- /dev/null
+++ b/difftool/node_compare.c
@@ -0,0 +1,99 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * node_compare.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "difftool.h"
+
+int node_compare(tree_node_t *a, tree_node_t *b)
+{
+	char *path = node_path(a);
+	tree_node_t *ait, *bit;
+	int ret, status = 0;
+
+	if (path == NULL)
+		return -1;
+
+	if ((a->mode & S_IFMT) != (b->mode & S_IFMT)) {
+		fprintf(stdout, "%s has a different type\n", path);
+		free(path);
+		return 1;
+	}
+
+	if (!(compare_flags & COMPARE_NO_PERM)) {
+		if ((a->mode & ~S_IFMT) != (b->mode & ~S_IFMT)) {
+			fprintf(stdout, "%s has different permissions\n",
+				path);
+			status = 1;
+		}
+	}
+
+	if (!(compare_flags & COMPARE_NO_OWNER)) {
+		if (a->uid != b->uid || a->gid != b->gid) {
+			fprintf(stdout, "%s has different ownership\n", path);
+			status = 1;
+		}
+	}
+
+	switch (a->mode & S_IFMT) {
+	case S_IFSOCK:
+	case S_IFIFO:
+		break;
+	case S_IFBLK:
+	case S_IFCHR:
+		if (a->data.devno != b->data.devno) {
+			fprintf(stdout, "%s has different device number\n",
+				path);
+			status = 1;
+		}
+		break;
+	case S_IFLNK:
+		if (strcmp(a->data.slink_target, b->data.slink_target) != 0) {
+			fprintf(stdout, "%s has a different link target\n",
+				path);
+		}
+		break;
+	case S_IFDIR:
+		ret = compare_dir_entries(a, b);
+		if (ret < 0) {
+			status = -1;
+			break;
+		}
+		if (ret > 0)
+			status = 1;
+
+		free(path);
+		path = NULL;
+
+		ait = a->data.dir->children;
+		bit = b->data.dir->children;
+
+		while (ait != NULL && bit != NULL) {
+			ret = node_compare(ait, bit);
+			if (ret < 0)
+				return -1;
+			if (ret > 0)
+				status = 1;
+
+			ait = ait->next;
+			bit = bit->next;
+		}
+		break;
+	case S_IFREG:
+		ret = compare_files(a->data.file, b->data.file, path);
+		if (ret < 0) {
+			status = -1;
+		} else if (ret > 0) {
+			fprintf(stdout, "regular file %s differs\n", path);
+			status = 1;
+		}
+		break;
+	default:
+		fprintf(stdout, "%s has unknown type, ignoring\n", path);
+		break;
+	}
+
+	free(path);
+	return status;
+}
diff --git a/difftool/util.c b/difftool/util.c
new file mode 100644
index 0000000..64ee7d4
--- /dev/null
+++ b/difftool/util.c
@@ -0,0 +1,26 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * util.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "difftool.h"
+
+char *node_path(tree_node_t *n)
+{
+	char *path = fstree_get_path(n);
+
+	if (path == NULL) {
+		perror("get path");
+		return NULL;
+	}
+
+	if (canonicalize_name(path)) {
+		fputs("[BUG] canonicalization of fstree_get_path failed!!\n",
+		      stderr);
+		free(path);
+		return NULL;
+	}
+
+	return path;
+}