19 files changed, 1670 insertions, 0 deletions

diff --git a/tests/libfstree/Makemodule.am b/tests/libfstree/Makemodule.am
new file mode 100644
index 0000000..4dc6da1
--- /dev/null
+++ b/tests/libfstree/Makemodule.am
@@ -0,0 +1,76 @@
+FSTDATADIR=$(top_srcdir)/tests/libfstree
+
+test_canonicalize_name_SOURCES = tests/libfstree/canonicalize_name.c
+test_canonicalize_name_SOURCES += tests/test.h
+test_canonicalize_name_LDADD = libfstree.a
+
+test_mknode_simple_SOURCES = tests/libfstree/mknode_simple.c tests/test.h
+test_mknode_simple_LDADD = libfstree.a libcompat.a
+
+test_mknode_slink_SOURCES = tests/libfstree/mknode_slink.c tests/test.h
+test_mknode_slink_LDADD = libfstree.a libcompat.a
+
+test_mknode_reg_SOURCES = tests/libfstree/mknode_reg.c tests/test.h
+test_mknode_reg_LDADD = libfstree.a libcompat.a
+
+test_mknode_dir_SOURCES = tests/libfstree/mknode_dir.c tests/test.h
+test_mknode_dir_LDADD = libfstree.a libcompat.a
+
+test_gen_inode_numbers_SOURCES = tests/libfstree/gen_inode_numbers.c
+test_gen_inode_numbers_SOURCES += tests/test.h
+test_gen_inode_numbers_LDADD = libfstree.a libcompat.a
+
+test_add_by_path_SOURCES = tests/libfstree/add_by_path.c tests/test.h
+test_add_by_path_LDADD = libfstree.a libcompat.a
+
+test_get_path_SOURCES = tests/libfstree/get_path.c tests/test.h
+test_get_path_LDADD = libfstree.a libcompat.a
+
+test_fstree_sort_SOURCES = tests/libfstree/fstree_sort.c tests/test.h
+test_fstree_sort_CPPFLAGS = $(AM_CPPFLAGS) -I$(top_srcdir)/lib/fstree
+test_fstree_sort_LDADD = libfstree.a libfstream.a libcompat.a
+
+test_fstree_from_file_SOURCES = tests/libfstree/fstree_from_file.c tests/test.h
+test_fstree_from_file_CPPFLAGS = $(AM_CPPFLAGS)
+test_fstree_from_file_CPPFLAGS += -DTESTPATH=$(FSTDATADIR)/fstree1.txt
+test_fstree_from_file_LDADD = libfstree.a libfstream.a libcompat.a
+
+test_fstree_glob1_SOURCES = tests/libfstree/fstree_glob1.c tests/test.h
+test_fstree_glob1_CPPFLAGS = $(AM_CPPFLAGS) -DTESTPATH=$(FSTDATADIR)
+test_fstree_glob1_LDADD = libfstree.a libfstream.a libcompat.a
+
+test_fstree_from_dir_SOURCES = tests/libfstree/fstree_from_dir.c tests/test.h
+test_fstree_from_dir_CPPFLAGS = $(AM_CPPFLAGS)
+test_fstree_from_dir_CPPFLAGS += -DTESTPATH=$(top_srcdir)/tests/libtar/data
+test_fstree_from_dir_LDADD = libfstree.a libcompat.a
+
+test_fstree_init_SOURCES = tests/libfstree/fstree_init.c tests/test.h
+test_fstree_init_CPPFLAGS = $(AM_CPPFLAGS) -I$(top_srcdir)/lib/fstree
+test_fstree_init_LDADD = libfstree.a libfstream.a libcompat.a
+
+test_filename_sane_SOURCES = tests/libfstree/filename_sane.c
+test_filename_sane_SOURCES += lib/fstree/filename_sane.c
+
+test_filename_sane_w32_SOURCES = tests/libfstree/filename_sane.c
+test_filename_sane_w32_SOURCES += lib/fstree/filename_sane.c
+test_filename_sane_w32_CPPFLAGS = $(AM_CPPFLAGS) -DTEST_WIN32=1
+
+fstree_fuzz_SOURCES = tests/libfstree/fstree_fuzz.c
+fstree_fuzz_LDADD = libfstree.a libfstream.a libcompat.a
+
+FSTREE_TESTS = \
+	test_canonicalize_name test_mknode_simple test_mknode_slink \
+	test_mknode_reg test_mknode_dir test_gen_inode_numbers \
+	test_add_by_path test_get_path test_fstree_sort test_fstree_from_file \
+	test_fstree_init test_filename_sane test_filename_sane_w32 \
+	test_fstree_from_dir test_fstree_glob1
+
+if BUILD_TOOLS
+check_PROGRAMS += $(FSTREE_TESTS)
+noinst_PROGRAMS += fstree_fuzz
+
+TESTS += $(FSTREE_TESTS)
+endif
+
+EXTRA_DIST += $(FSTDATADIR)/fstree1.txt
+EXTRA_DIST += $(FSTDATADIR)/fstree_glob1.txt $(FSTDATADIR)/fstree_glob2.txt
diff --git a/tests/libfstree/add_by_path.c b/tests/libfstree/add_by_path.c
new file mode 100644
index 0000000..94c0dc9
--- /dev/null
+++ b/tests/libfstree/add_by_path.c
@@ -0,0 +1,133 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * add_by_path.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+int main(void)
+{
+	tree_node_t *a, *b;
+	struct stat sb;
+	fstree_t fs;
+	char *opts;
+
+	opts = strdup("mode=0755,uid=21,gid=42");
+	TEST_ASSERT(fstree_init(&fs, opts) == 0);
+	free(opts);
+
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFDIR | 0750;
+	sb.st_uid = 1000;
+	sb.st_gid = 100;
+
+	TEST_EQUAL_UI(fs.root->link_count, 2);
+
+	a = fstree_add_generic(&fs, "dir", &sb, NULL);
+	TEST_NOT_NULL(a);
+	TEST_STR_EQUAL(a->name, "dir");
+	TEST_EQUAL_UI(a->mode, sb.st_mode);
+	TEST_EQUAL_UI(a->uid, sb.st_uid);
+	TEST_EQUAL_UI(a->gid, sb.st_gid);
+	TEST_ASSERT(a->parent == fs.root);
+	TEST_EQUAL_UI(a->link_count, 2);
+	TEST_NULL(a->next);
+	TEST_ASSERT(fs.root->data.dir.children == a);
+	TEST_EQUAL_UI(fs.root->link_count, 3);
+	TEST_ASSERT(!a->data.dir.created_implicitly);
+
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFBLK | 0640;
+	sb.st_rdev = 1234;
+
+	b = fstree_add_generic(&fs, "blkdev", &sb, NULL);
+	TEST_NOT_NULL(b);
+	TEST_ASSERT(b != a);
+	TEST_STR_EQUAL(b->name, "blkdev");
+	TEST_EQUAL_UI(b->mode, sb.st_mode);
+	TEST_EQUAL_UI(b->uid, sb.st_uid);
+	TEST_EQUAL_UI(b->gid, sb.st_gid);
+	TEST_ASSERT(b->parent == fs.root);
+	TEST_EQUAL_UI(b->link_count, 1);
+	TEST_EQUAL_UI(b->data.devno, sb.st_rdev);
+	TEST_ASSERT(b->next == a);
+	TEST_EQUAL_UI(fs.root->link_count, 4);
+	TEST_ASSERT(fs.root->data.dir.children == b);
+
+	TEST_NULL(fstree_add_generic(&fs, "blkdev/foo", &sb, NULL));
+	TEST_EQUAL_UI(errno, ENOTDIR);
+
+	TEST_NULL(fstree_add_generic(&fs, "dir", &sb, NULL));
+	TEST_EQUAL_UI(errno, EEXIST);
+
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFDIR | 0755;
+	TEST_NULL(fstree_add_generic(&fs, "dir", &sb, NULL));
+	TEST_EQUAL_UI(errno, EEXIST);
+
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFCHR | 0444;
+	b = fstree_add_generic(&fs, "dir/chrdev", &sb, NULL);
+	TEST_NOT_NULL(b);
+	TEST_EQUAL_UI(b->mode, sb.st_mode);
+	TEST_EQUAL_UI(b->uid, sb.st_uid);
+	TEST_EQUAL_UI(b->gid, sb.st_gid);
+	TEST_EQUAL_UI(b->link_count, 1);
+	TEST_ASSERT(b->parent == a);
+	TEST_EQUAL_UI(b->data.devno, sb.st_rdev);
+	TEST_NULL(b->next);
+	TEST_ASSERT(a->data.dir.children == b);
+
+	TEST_EQUAL_UI(a->link_count, 3);
+	TEST_EQUAL_UI(fs.root->link_count, 4);
+
+	b = fstree_add_generic(&fs, "dir/foo/chrdev", &sb, NULL);
+	TEST_NOT_NULL(b);
+	TEST_NULL(b->next);
+	TEST_EQUAL_UI(b->mode, sb.st_mode);
+	TEST_EQUAL_UI(b->uid, sb.st_uid);
+	TEST_EQUAL_UI(b->gid, sb.st_gid);
+	TEST_EQUAL_UI(b->link_count, 1);
+	TEST_ASSERT(b->parent != a);
+	TEST_ASSERT(b->parent->parent == a);
+	TEST_EQUAL_UI(b->data.devno, sb.st_rdev);
+	TEST_NULL(b->next);
+
+	TEST_EQUAL_UI(a->link_count, 4);
+	TEST_EQUAL_UI(fs.root->link_count, 4);
+	TEST_ASSERT(a->data.dir.children != b);
+
+	b = b->parent;
+	TEST_ASSERT(b->data.dir.created_implicitly);
+	TEST_EQUAL_UI(b->mode, S_IFDIR | 0755);
+	TEST_EQUAL_UI(b->uid, 21);
+	TEST_EQUAL_UI(b->gid, 42);
+	TEST_EQUAL_UI(b->link_count, 3);
+
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFDIR | 0750;
+	sb.st_uid = 1000;
+	sb.st_gid = 100;
+
+	a = fstree_add_generic(&fs, "dir/foo", &sb, NULL);
+	TEST_NOT_NULL(a);
+	TEST_ASSERT(a == b);
+	TEST_ASSERT(!a->data.dir.created_implicitly);
+	TEST_EQUAL_UI(a->mode, sb.st_mode);
+	TEST_EQUAL_UI(a->uid, sb.st_uid);
+	TEST_EQUAL_UI(a->gid, sb.st_gid);
+	TEST_EQUAL_UI(a->link_count, 3);
+
+	TEST_EQUAL_UI(a->parent->link_count, 4);
+	TEST_EQUAL_UI(fs.root->link_count, 4);
+
+	TEST_NULL(fstree_add_generic(&fs, "dir/foo", &sb, NULL));
+	TEST_EQUAL_UI(errno, EEXIST);
+
+	fstree_cleanup(&fs);
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/canonicalize_name.c b/tests/libfstree/canonicalize_name.c
new file mode 100644
index 0000000..37b07e3
--- /dev/null
+++ b/tests/libfstree/canonicalize_name.c
@@ -0,0 +1,77 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * canonicalize_name.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "fstree.h"
+#include "../test.h"
+
+static const struct {
+	const char *in;
+	const char *out;
+} must_work[] = {
+	{ "", "" },
+	{ "/", "" },
+	{ "\\", "\\" },
+	{ "///", "" },
+	{ "\\\\\\", "\\\\\\" },
+	{ "/\\//\\\\/", "\\/\\\\" },
+	{ "foo/bar/test", "foo/bar/test" },
+	{ "foo\\bar\\test", "foo\\bar\\test" },
+	{ "/foo/bar/test/", "foo/bar/test" },
+	{ "\\foo\\bar\\test\\", "\\foo\\bar\\test\\" },
+	{ "///foo//bar//test///", "foo/bar/test" },
+	{ "./foo/././bar/test/./.", "foo/bar/test" },
+	{ "./foo/././", "foo" },
+	{ ".", "" },
+	{ "./", "" },
+	{ "./.", "" },
+	{ "foo/.../bar", "foo/.../bar" },
+	{ "foo/.test/bar", "foo/.test/bar" },
+};
+
+static const char *must_not_work[] = {
+	"..",
+	"foo/../bar",
+	"../foo/bar",
+	"foo/bar/..",
+	"foo/bar/../",
+};
+
+int main(void)
+{
+	char buffer[512];
+	size_t i;
+
+	for (i = 0; i < sizeof(must_work) / sizeof(must_work[0]); ++i) {
+		strcpy(buffer, must_work[i].in);
+
+		if (canonicalize_name(buffer)) {
+			fprintf(stderr, "Test case rejected: '%s'\n",
+				must_work[i].in);
+			return EXIT_FAILURE;
+		}
+
+		if (strcmp(buffer, must_work[i].out) != 0) {
+			fprintf(stderr, "Expected result: %s\n",
+				must_work[i].out);
+			fprintf(stderr, "Actual result: %s\n", buffer);
+			return EXIT_FAILURE;
+		}
+	}
+
+	for (i = 0; i < sizeof(must_not_work) / sizeof(must_not_work[0]); ++i) {
+		strcpy(buffer, must_not_work[i]);
+
+		if (canonicalize_name(buffer) == 0) {
+			fprintf(stderr, "Test case accepted: '%s'\n",
+				must_not_work[i]);
+			fprintf(stderr, "Transformed into: '%s'\n", buffer);
+			return EXIT_FAILURE;
+		}
+	}
+
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/filename_sane.c b/tests/libfstree/filename_sane.c
new file mode 100644
index 0000000..4d25b33
--- /dev/null
+++ b/tests/libfstree/filename_sane.c
@@ -0,0 +1,93 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * filename_sane.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "fstree.h"
+#include "../test.h"
+
+static const char *must_work[] = {
+	"foobar",
+	"test.txt",
+#if !defined(_WIN32) && !defined(__WINDOWS__) && !defined(TEST_WIN32)
+	"\\foo", "foo\\", "foo\\bar",
+#endif
+	NULL,
+};
+
+static const char *must_not_work[] = {
+	".",
+	"..",
+	"/foo",
+	"foo/",
+	"foo/bar",
+	NULL,
+};
+
+static const char *must_not_work_here[] = {
+#if defined(_WIN32) || defined(__WINDOWS__) || defined(TEST_WIN32)
+	"\\foo", "foo\\", "foo\\bar",
+	"fo<o", "fo>o", "fo:o", "fo\"o",
+	"fo|o", "fo?o", "fo*o", "fo\ro",
+	"CON", "PRN", "AUX", "NUL",
+	"COM1", "COM2", "LPT1", "LPT2",
+	"con", "prn", "aux", "nul",
+	"com1", "com2", "lpt1", "lpt2",
+	"AUX.txt", "aux.txt", "NUL.txt", "nul.txt",
+#endif
+	NULL,
+};
+
+int main(void)
+{
+	size_t i;
+
+	for (i = 0; must_work[i] != NULL; ++i) {
+		if (!is_filename_sane(must_work[i], false)) {
+			fprintf(stderr, "%s was rejected!\n", must_work[i]);
+			return EXIT_FAILURE;
+		}
+
+		if (!is_filename_sane(must_work[i], true)) {
+			fprintf(stderr,
+				"%s was rejected when testing for "
+				"OS specific stuff!\n", must_work[i]);
+			return EXIT_FAILURE;
+		}
+	}
+
+	for (i = 0; must_not_work[i] != NULL; ++i) {
+		if (is_filename_sane(must_not_work[i], false)) {
+			fprintf(stderr, "%s was accepted!\n",
+				must_not_work[i]);
+			return EXIT_FAILURE;
+		}
+
+		if (is_filename_sane(must_not_work[i], true)) {
+			fprintf(stderr,
+				"%s was accepted when testing for "
+				"OS specific stuff!\n", must_not_work[i]);
+			return EXIT_FAILURE;
+		}
+	}
+
+	for (i = 0; must_not_work_here[i] != NULL; ++i) {
+		if (!is_filename_sane(must_not_work_here[i], false)) {
+			fprintf(stderr,
+				"%s was rejected in the generic test!\n",
+				must_not_work_here[i]);
+			return EXIT_FAILURE;
+		}
+
+		if (is_filename_sane(must_not_work_here[i], true)) {
+			fprintf(stderr,
+				"%s was accepted when testing for "
+				"OS specific stuff!\n", must_not_work_here[i]);
+			return EXIT_FAILURE;
+		}
+	}
+
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/fstree1.txt b/tests/libfstree/fstree1.txt
new file mode 100644
index 0000000..090aff9
--- /dev/null
+++ b/tests/libfstree/fstree1.txt
@@ -0,0 +1,9 @@
+# comment line
+slink /slink 0644 2 3 slinktarget
+dir /dir 0755 4 5
+nod /chardev 0600 6 7 c 13 37
+nod /blkdev 0600 8 9 b 42 21
+pipe /pipe 0644 10 11
+dir "/foo bar" 0755 0 0
+dir "/foo bar/ test \"/" 0755 0 0
+  sock  /sock  0555  12  13  
\ No newline at end of file
diff --git a/tests/libfstree/fstree_from_dir.c b/tests/libfstree/fstree_from_dir.c
new file mode 100644
index 0000000..7db1b74
--- /dev/null
+++ b/tests/libfstree/fstree_from_dir.c
@@ -0,0 +1,380 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fstree_from_dir.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+static void check_hierarchy(tree_node_t *root, bool recursive)
+{
+	tree_node_t *n, *m;
+
+	n = root->data.dir.children;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "CREDITS");
+	TEST_ASSERT(S_ISREG(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "file-size");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "12-digit.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "format-acceptance");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu-g.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "link_filled.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "ustar-pre-posix.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "ustar.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "v7.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "large-mtime");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "12-digit.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "long-paths");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "ustar.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "negative-mtime");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "sparse-files");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu-small.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax-gnu0-0.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax-gnu0-1.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax-gnu1-0.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "sqfs.sha512");
+	TEST_ASSERT(S_ISREG(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "user-group-largenum");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "8-digit.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "xattr");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "acl.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "xattr-libarchive.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "xattr-schily-binary.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "xattr-schily.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NULL(n);
+}
+
+int main(void)
+{
+	struct stat sb;
+	tree_node_t *n;
+	fstree_t fs;
+
+	/* recursively scan into root */
+	TEST_ASSERT(fstree_init(&fs, NULL) == 0);
+	TEST_ASSERT(fstree_from_dir(&fs, fs.root, TEST_PATH,
+				    NULL, NULL, 0) == 0);
+
+	fstree_post_process(&fs);
+	check_hierarchy(fs.root, true);
+	fstree_cleanup(&fs);
+
+	/* non-recursively scan into root */
+	TEST_ASSERT(fstree_init(&fs, NULL) == 0);
+	TEST_ASSERT(fstree_from_dir(&fs, fs.root, TEST_PATH, NULL, NULL,
+				    DIR_SCAN_NO_RECURSION) == 0);
+
+	fstree_post_process(&fs);
+	check_hierarchy(fs.root, false);
+	fstree_cleanup(&fs);
+
+	/* recursively scan into a sub-directory of root */
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFDIR | 0755;
+
+	TEST_ASSERT(fstree_init(&fs, NULL) == 0);
+
+	n = fstree_mknode(fs.root, "foodir", 6, NULL, &sb);
+	TEST_NOT_NULL(n);
+	fs.root->data.dir.children = n;
+
+	TEST_ASSERT(fstree_from_dir(&fs, n, TEST_PATH, NULL, NULL, 0) == 0);
+
+	TEST_ASSERT(fs.root->data.dir.children == n);
+	TEST_NULL(n->next);
+
+	fstree_post_process(&fs);
+	check_hierarchy(n, true);
+	fstree_cleanup(&fs);
+
+	/* non-recursively scan into a sub-directory of root */
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFDIR | 0755;
+
+	TEST_ASSERT(fstree_init(&fs, NULL) == 0);
+
+	n = fstree_mknode(fs.root, "foodir", 6, NULL, &sb);
+	TEST_NOT_NULL(n);
+	fs.root->data.dir.children = n;
+
+	TEST_ASSERT(fstree_from_dir(&fs, n, TEST_PATH, NULL, NULL,
+				    DIR_SCAN_NO_RECURSION) == 0);
+
+	TEST_ASSERT(fs.root->data.dir.children == n);
+	TEST_NULL(n->next);
+
+	fstree_post_process(&fs);
+	check_hierarchy(n, false);
+	fstree_cleanup(&fs);
+
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/fstree_from_file.c b/tests/libfstree/fstree_from_file.c
new file mode 100644
index 0000000..c8816e6
--- /dev/null
+++ b/tests/libfstree/fstree_from_file.c
@@ -0,0 +1,89 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fstree_from_file.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+int main(void)
+{
+	tree_node_t *n;
+	fstree_t fs;
+
+	TEST_ASSERT(fstree_init(&fs, NULL) == 0);
+	TEST_ASSERT(fstree_from_file(&fs, TEST_PATH, NULL) == 0);
+
+	fstree_post_process(&fs);
+	n = fs.root->data.dir.children;
+
+	TEST_EQUAL_UI(fs.root->link_count, 9);
+
+	TEST_EQUAL_UI(n->mode, S_IFBLK | 0600);
+	TEST_EQUAL_UI(n->uid, 8);
+	TEST_EQUAL_UI(n->gid, 9);
+	TEST_EQUAL_UI(n->link_count, 1);
+	TEST_STR_EQUAL(n->name, "blkdev");
+	TEST_EQUAL_UI(n->data.devno, makedev(42, 21));
+
+	n = n->next;
+	TEST_EQUAL_UI(n->mode, S_IFCHR | 0600);
+	TEST_EQUAL_UI(n->uid, 6);
+	TEST_EQUAL_UI(n->gid, 7);
+	TEST_EQUAL_UI(n->link_count, 1);
+	TEST_STR_EQUAL(n->name, "chardev");
+	TEST_EQUAL_UI(n->data.devno, makedev(13, 37));
+
+	n = n->next;
+	TEST_EQUAL_UI(n->mode, S_IFDIR | 0755);
+	TEST_EQUAL_UI(n->uid, 4);
+	TEST_EQUAL_UI(n->gid, 5);
+	TEST_EQUAL_UI(n->link_count, 2);
+	TEST_STR_EQUAL(n->name, "dir");
+	TEST_NULL(n->data.dir.children);
+
+	n = n->next;
+	TEST_EQUAL_UI(n->mode, S_IFDIR | 0755);
+	TEST_EQUAL_UI(n->uid, 0);
+	TEST_EQUAL_UI(n->gid, 0);
+	TEST_EQUAL_UI(n->link_count, 3);
+	TEST_STR_EQUAL(n->name, "foo bar");
+	TEST_NOT_NULL(n->data.dir.children);
+
+	TEST_NULL(n->data.dir.children->next);
+	TEST_EQUAL_UI(n->data.dir.children->mode, S_IFDIR | 0755);
+	TEST_EQUAL_UI(n->data.dir.children->uid, 0);
+	TEST_EQUAL_UI(n->data.dir.children->gid, 0);
+	TEST_EQUAL_UI(n->data.dir.children->link_count, 2);
+	TEST_STR_EQUAL(n->data.dir.children->name, " test \"");
+	TEST_NULL(n->data.dir.children->data.dir.children);
+
+	n = n->next;
+	TEST_EQUAL_UI(n->mode, S_IFIFO | 0644);
+	TEST_EQUAL_UI(n->uid, 10);
+	TEST_EQUAL_UI(n->gid, 11);
+	TEST_EQUAL_UI(n->link_count, 1);
+	TEST_STR_EQUAL(n->name, "pipe");
+
+	n = n->next;
+	TEST_EQUAL_UI(n->mode, S_IFLNK | 0777);
+	TEST_EQUAL_UI(n->uid, 2);
+	TEST_EQUAL_UI(n->gid, 3);
+	TEST_EQUAL_UI(n->link_count, 1);
+	TEST_STR_EQUAL(n->name, "slink");
+	TEST_STR_EQUAL(n->data.target, "slinktarget");
+
+	n = n->next;
+	TEST_EQUAL_UI(n->mode, S_IFSOCK | 0555);
+	TEST_EQUAL_UI(n->uid, 12);
+	TEST_EQUAL_UI(n->gid, 13);
+	TEST_EQUAL_UI(n->link_count, 1);
+	TEST_STR_EQUAL(n->name, "sock");
+	TEST_NULL(n->next);
+
+	fstree_cleanup(&fs);
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/fstree_fuzz.c b/tests/libfstree/fstree_fuzz.c
new file mode 100644
index 0000000..ebc8c45
--- /dev/null
+++ b/tests/libfstree/fstree_fuzz.c
@@ -0,0 +1,34 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fstree_fuzz.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+
+int main(int argc, char **argv)
+{
+	int ret = EXIT_FAILURE;
+	fstree_t fs;
+
+	if (argc != 2) {
+		fputs("Usage: fstree_fuzz <input_file>\n", stderr);
+		return EXIT_FAILURE;
+	}
+
+	if (fstree_init(&fs, NULL))
+		return EXIT_FAILURE;
+
+	if (fstree_from_file(&fs, argv[1], NULL))
+		goto out_fs;
+
+	ret = EXIT_SUCCESS;
+out_fs:
+	fstree_cleanup(&fs);
+	return ret;
+}
diff --git a/tests/libfstree/fstree_glob1.c b/tests/libfstree/fstree_glob1.c
new file mode 100644
index 0000000..592180b
--- /dev/null
+++ b/tests/libfstree/fstree_glob1.c
@@ -0,0 +1,224 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fstree_glob1.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+static void check_hierarchy(tree_node_t *root, bool recursive)
+{
+	tree_node_t *n, *m;
+
+	n = root->data.dir.children;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "tarcorpus");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root);
+	TEST_NULL(n->next);
+
+	n = n->data.dir.children;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "file-size");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root->data.dir.children);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "format-acceptance");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root->data.dir.children);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu-g.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "large-mtime");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root->data.dir.children);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "long-paths");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root->data.dir.children);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "negative-mtime");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root->data.dir.children);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "sparse-files");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root->data.dir.children);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu-small.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax-gnu0-0.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax-gnu0-1.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "pax-gnu1-0.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "user-group-largenum");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root->data.dir.children);
+
+	if (recursive) {
+		m = n->data.dir.children;
+		TEST_NOT_NULL(m);
+		TEST_STR_EQUAL(m->name, "gnu.tar");
+		TEST_ASSERT(S_ISREG(m->mode));
+		TEST_ASSERT(m->parent == n);
+
+		m = m->next;
+		TEST_NULL(m);
+	} else {
+		TEST_NULL(n->data.dir.children);
+	}
+
+	n = n->next;
+	TEST_NOT_NULL(n);
+	TEST_STR_EQUAL(n->name, "xattr");
+	TEST_ASSERT(S_ISDIR(n->mode));
+	TEST_ASSERT(n->parent == root->data.dir.children);
+	TEST_NULL(n->data.dir.children);
+
+	n = n->next;
+	TEST_NULL(n);
+}
+
+int main(void)
+{
+	fstree_t fs;
+	int ret;
+
+	/* first test case, directory tree only */
+	ret = fstree_init(&fs, NULL);
+	TEST_EQUAL_I(ret, 0);
+
+	ret = fstree_from_file(&fs, TEST_PATH "/fstree_glob1.txt", TEST_PATH);
+	TEST_EQUAL_I(ret, 0);
+
+	fstree_post_process(&fs);
+	check_hierarchy(fs.root, false);
+	fstree_cleanup(&fs);
+
+	/* first test case, directory tree plus fnmatch()ed files */
+	ret = fstree_init(&fs, NULL);
+	TEST_EQUAL_I(ret, 0);
+
+	ret = fstree_from_file(&fs, TEST_PATH "/fstree_glob2.txt", TEST_PATH);
+	TEST_EQUAL_I(ret, 0);
+
+	fstree_post_process(&fs);
+	check_hierarchy(fs.root, true);
+	fstree_cleanup(&fs);
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/fstree_glob1.txt b/tests/libfstree/fstree_glob1.txt
new file mode 100644
index 0000000..b1df979
--- /dev/null
+++ b/tests/libfstree/fstree_glob1.txt
@@ -0,0 +1,2 @@
+dir /tarcorpus 0755 0 0
+glob /tarcorpus 0755 0 0 -type d -- ../libtar/data
diff --git a/tests/libfstree/fstree_glob2.txt b/tests/libfstree/fstree_glob2.txt
new file mode 100644
index 0000000..3c8019b
--- /dev/null
+++ b/tests/libfstree/fstree_glob2.txt
@@ -0,0 +1,3 @@
+dir /tarcorpus 0755 0 0
+glob /tarcorpus 0755 0 0 -type d ../libtar/data
+glob /tarcorpus 0644 0 0 -type f -name "*gnu*.tar" -- ../libtar/data
diff --git a/tests/libfstree/fstree_init.c b/tests/libfstree/fstree_init.c
new file mode 100644
index 0000000..a101143
--- /dev/null
+++ b/tests/libfstree/fstree_init.c
@@ -0,0 +1,49 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fstree_init.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "internal.h"
+#include "../test.h"
+
+int main(void)
+{
+	fstree_t fs;
+	char *str;
+
+	str = strdup("mtime=1337,uid=1000,gid=100,mode=0321");
+	TEST_NOT_NULL(str);
+	TEST_ASSERT(fstree_init(&fs, str) == 0);
+	free(str);
+	TEST_EQUAL_UI(fs.defaults.st_mtime, 1337);
+	TEST_EQUAL_UI(fs.defaults.st_uid, 1000);
+	TEST_EQUAL_UI(fs.defaults.st_gid, 100);
+	TEST_EQUAL_UI(fs.defaults.st_mode, S_IFDIR | 0321);
+	fstree_cleanup(&fs);
+
+	TEST_ASSERT(fstree_init(&fs, NULL) == 0);
+	if (fs.defaults.st_mtime != 0) {
+		TEST_EQUAL_UI(fs.defaults.st_mtime, get_source_date_epoch());
+	}
+	TEST_EQUAL_UI(fs.defaults.st_uid, 0);
+	TEST_EQUAL_UI(fs.defaults.st_gid, 0);
+	TEST_EQUAL_UI(fs.defaults.st_mode, S_IFDIR | 0755);
+	fstree_cleanup(&fs);
+
+	str = strdup("mode=07777");
+	TEST_NOT_NULL(str);
+	TEST_ASSERT(fstree_init(&fs, str) == 0);
+	free(str);
+	fstree_cleanup(&fs);
+
+	str = strdup("mode=017777");
+	TEST_NOT_NULL(str);
+	TEST_ASSERT(fstree_init(&fs, str) != 0);
+	free(str);
+
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/fstree_sort.c b/tests/libfstree/fstree_sort.c
new file mode 100644
index 0000000..6fc7543
--- /dev/null
+++ b/tests/libfstree/fstree_sort.c
@@ -0,0 +1,101 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fstree_sort.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "internal.h"
+#include "../test.h"
+
+int main(void)
+{
+	tree_node_t *a, *b, *c, *d;
+	struct stat sb;
+	fstree_t fs;
+
+	memset(&fs, 0, sizeof(fs));
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFBLK | 0600;
+	sb.st_rdev = 1337;
+
+	a = fstree_mknode(NULL, "a", 1, NULL, &sb);
+	b = fstree_mknode(NULL, "b", 1, NULL, &sb);
+	c = fstree_mknode(NULL, "c", 1, NULL, &sb);
+	d = fstree_mknode(NULL, "d", 1, NULL, &sb);
+	TEST_ASSERT(a != NULL && b != NULL && c != NULL && d != NULL);
+
+	/* empty list */
+	TEST_NULL(tree_node_list_sort(NULL));
+
+	/* single element */
+	TEST_ASSERT(tree_node_list_sort(a) == a);
+	TEST_NULL(a->next);
+
+	/* two elements, reverse order */
+	b->next = a;
+	TEST_ASSERT(tree_node_list_sort(b) == a);
+	TEST_ASSERT(a->next == b);
+	TEST_NULL(b->next);
+
+	/* two elements, sorted order */
+	TEST_ASSERT(tree_node_list_sort(a) == a);
+	TEST_ASSERT(a->next == b);
+	TEST_NULL(b->next);
+
+	/* three elements, reverse order */
+	c->next = b;
+	b->next = a;
+	a->next = NULL;
+
+	TEST_ASSERT(tree_node_list_sort(c) == a);
+	TEST_ASSERT(a->next == b);
+	TEST_ASSERT(b->next == c);
+	TEST_NULL(c->next);
+
+	/* three elements, ordered */
+	TEST_ASSERT(tree_node_list_sort(a) == a);
+	TEST_ASSERT(a->next == b);
+	TEST_ASSERT(b->next == c);
+	TEST_NULL(c->next);
+
+	/* four elements, reverse order */
+	d->next = c;
+	c->next = b;
+	b->next = a;
+	a->next = NULL;
+
+	TEST_ASSERT(tree_node_list_sort(d) == a);
+	TEST_ASSERT(a->next == b);
+	TEST_ASSERT(b->next == c);
+	TEST_ASSERT(c->next == d);
+	TEST_NULL(d->next);
+
+	/* four elements, sorted order */
+	TEST_ASSERT(tree_node_list_sort(a) == a);
+	TEST_ASSERT(a->next == b);
+	TEST_ASSERT(b->next == c);
+	TEST_ASSERT(c->next == d);
+	TEST_NULL(d->next);
+
+	/* force merge sort to go through LRLR pattern */
+	b->next = a;
+	a->next = d;
+	d->next = c;
+	c->next = NULL;
+
+	TEST_ASSERT(tree_node_list_sort(b) == a);
+	TEST_ASSERT(a->next == b);
+	TEST_ASSERT(b->next == c);
+	TEST_ASSERT(c->next == d);
+	TEST_NULL(d->next);
+
+	/* cleanup and done */
+	free(a);
+	free(b);
+	free(c);
+	free(d);
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/gen_inode_numbers.c b/tests/libfstree/gen_inode_numbers.c
new file mode 100644
index 0000000..8ee2315
--- /dev/null
+++ b/tests/libfstree/gen_inode_numbers.c
@@ -0,0 +1,89 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * gen_inode_table.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+static tree_node_t *gen_node(tree_node_t *parent, const char *name)
+{
+	struct stat sb;
+
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFDIR | 0755;
+
+	return fstree_mknode(parent, name, strlen(name), NULL, &sb);
+}
+
+static void check_children_before_root(tree_node_t *root)
+{
+	tree_node_t *n;
+
+	for (n = root->data.dir.children; n != NULL; n = n->next)
+		TEST_LESS_THAN_UI(n->inode_num, root->inode_num);
+
+	for (n = root->data.dir.children; n != NULL; n = n->next)
+		check_children_before_root(n);
+}
+
+static void check_children_continuous(tree_node_t *root)
+{
+	tree_node_t *n;
+
+	for (n = root->data.dir.children; n != NULL; n = n->next) {
+		if (n->next != NULL) {
+			TEST_EQUAL_UI(n->next->inode_num, (n->inode_num + 1));
+		}
+	}
+
+	for (n = root->data.dir.children; n != NULL; n = n->next)
+		check_children_continuous(n);
+}
+
+int main(void)
+{
+	tree_node_t *a, *b, *c;
+	fstree_t fs;
+
+	// inode table for the empty tree
+	TEST_ASSERT(fstree_init(&fs, NULL) == 0);
+	fstree_post_process(&fs);
+	TEST_EQUAL_UI(fs.unique_inode_count, 1);
+	TEST_EQUAL_UI(fs.root->inode_num, 1);
+	fstree_cleanup(&fs);
+
+	// tree with 2 levels under root, fan out 3
+	TEST_ASSERT(fstree_init(&fs, NULL) == 0);
+
+	a = gen_node(fs.root, "a");
+	b = gen_node(fs.root, "b");
+	c = gen_node(fs.root, "c");
+	TEST_NOT_NULL(a);
+	TEST_NOT_NULL(b);
+	TEST_NOT_NULL(c);
+
+	TEST_NOT_NULL(gen_node(a, "a_a"));
+	TEST_NOT_NULL(gen_node(a, "a_b"));
+	TEST_NOT_NULL(gen_node(a, "a_c"));
+
+	TEST_NOT_NULL(gen_node(b, "b_a"));
+	TEST_NOT_NULL(gen_node(b, "b_b"));
+	TEST_NOT_NULL(gen_node(b, "b_c"));
+
+	TEST_NOT_NULL(gen_node(c, "c_a"));
+	TEST_NOT_NULL(gen_node(c, "c_b"));
+	TEST_NOT_NULL(gen_node(c, "c_c"));
+
+	fstree_post_process(&fs);
+	TEST_EQUAL_UI(fs.unique_inode_count, 13);
+
+	check_children_before_root(fs.root);
+	check_children_continuous(fs.root);
+
+	fstree_cleanup(&fs);
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/get_path.c b/tests/libfstree/get_path.c
new file mode 100644
index 0000000..9bf618b
--- /dev/null
+++ b/tests/libfstree/get_path.c
@@ -0,0 +1,58 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * get_path.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+int main(void)
+{
+	tree_node_t *a, *b, *c, *d;
+	struct stat sb;
+	fstree_t fs;
+	char *str;
+
+	TEST_ASSERT(fstree_init(&fs, NULL) == 0);
+
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFDIR | 0750;
+	sb.st_uid = 1000;
+	sb.st_gid = 100;
+
+	a = fstree_add_generic(&fs, "foo", &sb, NULL);
+	b = fstree_add_generic(&fs, "foo/bar", &sb, NULL);
+	c = fstree_add_generic(&fs, "foo/bar/baz", &sb, NULL);
+	d = fstree_add_generic(&fs, "foo/bar/baz/dir", &sb, NULL);
+
+	str = fstree_get_path(fs.root);
+	TEST_NOT_NULL(str);
+	TEST_STR_EQUAL(str, "/");
+	free(str);
+
+	str = fstree_get_path(a);
+	TEST_NOT_NULL(str);
+	TEST_STR_EQUAL(str, "/foo");
+	free(str);
+
+	str = fstree_get_path(b);
+	TEST_NOT_NULL(str);
+	TEST_STR_EQUAL(str, "/foo/bar");
+	free(str);
+
+	str = fstree_get_path(c);
+	TEST_NOT_NULL(str);
+	TEST_STR_EQUAL(str, "/foo/bar/baz");
+	free(str);
+
+	str = fstree_get_path(d);
+	TEST_NOT_NULL(str);
+	TEST_STR_EQUAL(str, "/foo/bar/baz/dir");
+	free(str);
+
+	fstree_cleanup(&fs);
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/mknode_dir.c b/tests/libfstree/mknode_dir.c
new file mode 100644
index 0000000..be1156f
--- /dev/null
+++ b/tests/libfstree/mknode_dir.c
@@ -0,0 +1,62 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * mknode_dir.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+int main(void)
+{
+	tree_node_t *root, *a, *b;
+	struct stat sb;
+	fstree_t fs;
+
+	memset(&fs, 0, sizeof(fs));
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFDIR | 0654;
+	sb.st_uid = 123;
+	sb.st_gid = 456;
+	sb.st_rdev = 789;
+	sb.st_size = 4096;
+
+	root = fstree_mknode(NULL, "rootdir", 7, NULL, &sb);
+	TEST_EQUAL_UI(root->uid, sb.st_uid);
+	TEST_EQUAL_UI(root->gid, sb.st_gid);
+	TEST_EQUAL_UI(root->mode, sb.st_mode);
+	TEST_EQUAL_UI(root->link_count, 2);
+	TEST_ASSERT(root->name >= (char *)root->payload);
+	TEST_STR_EQUAL(root->name, "rootdir");
+	TEST_NULL(root->data.dir.children);
+	TEST_NULL(root->parent);
+	TEST_NULL(root->next);
+
+	a = fstree_mknode(root, "adir", 4, NULL, &sb);
+	TEST_ASSERT(a->parent == root);
+	TEST_NULL(a->next);
+	TEST_EQUAL_UI(a->link_count, 2);
+	TEST_EQUAL_UI(root->link_count, 3);
+	TEST_ASSERT(root->data.dir.children == a);
+	TEST_NULL(root->parent);
+	TEST_NULL(root->next);
+
+	b = fstree_mknode(root, "bdir", 4, NULL, &sb);
+	TEST_ASSERT(a->parent == root);
+	TEST_ASSERT(b->parent == root);
+	TEST_EQUAL_UI(b->link_count, 2);
+	TEST_ASSERT(root->data.dir.children == b);
+	TEST_EQUAL_UI(root->link_count, 4);
+	TEST_ASSERT(b->next == a);
+	TEST_NULL(a->next);
+	TEST_NULL(root->parent);
+	TEST_NULL(root->next);
+
+	free(root);
+	free(a);
+	free(b);
+
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/mknode_reg.c b/tests/libfstree/mknode_reg.c
new file mode 100644
index 0000000..1f7ec88
--- /dev/null
+++ b/tests/libfstree/mknode_reg.c
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * mknode_reg.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+int main(void)
+{
+	tree_node_t *node;
+	struct stat sb;
+	fstree_t fs;
+
+	memset(&fs, 0, sizeof(fs));
+
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFREG | 0654;
+	sb.st_uid = 123;
+	sb.st_gid = 456;
+	sb.st_rdev = 789;
+	sb.st_size = 4096;
+
+	node = fstree_mknode(NULL, "filename", 8, "input", &sb);
+	TEST_EQUAL_UI(node->uid, sb.st_uid);
+	TEST_EQUAL_UI(node->gid, sb.st_gid);
+	TEST_EQUAL_UI(node->mode, sb.st_mode);
+	TEST_NULL(node->parent);
+	TEST_EQUAL_UI(node->link_count, 1);
+	TEST_ASSERT((char *)node->name >= (char *)node->payload);
+	TEST_ASSERT(node->data.file.input_file >= (char *)node->payload);
+	TEST_ASSERT(node->data.file.input_file >= node->name + 8);
+	TEST_STR_EQUAL(node->name, "filename");
+	TEST_STR_EQUAL(node->data.file.input_file, "input");
+	free(node);
+
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/mknode_simple.c b/tests/libfstree/mknode_simple.c
new file mode 100644
index 0000000..b8505ed
--- /dev/null
+++ b/tests/libfstree/mknode_simple.c
@@ -0,0 +1,97 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * mknode_simple.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+int main(void)
+{
+	tree_node_t *node;
+	struct stat sb;
+	fstree_t fs;
+
+	memset(&fs, 0, sizeof(fs));
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFSOCK | 0654;
+	sb.st_uid = 123;
+	sb.st_gid = 456;
+	sb.st_rdev = 789;
+	sb.st_size = 1337;
+
+	node = fstree_mknode(NULL, "sockfile", 8, NULL, &sb);
+	TEST_ASSERT((char *)node->name >= (char *)node->payload);
+	TEST_STR_EQUAL(node->name, "sockfile");
+	TEST_EQUAL_UI(node->uid, sb.st_uid);
+	TEST_EQUAL_UI(node->gid, sb.st_gid);
+	TEST_EQUAL_UI(node->mode, sb.st_mode);
+	TEST_EQUAL_UI(node->link_count, 1);
+	TEST_NULL(node->parent);
+	TEST_NULL(node->data.target);
+	TEST_EQUAL_UI(node->data.devno, 0);
+	free(node);
+
+	memset(&fs, 0, sizeof(fs));
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFIFO | 0654;
+	sb.st_uid = 123;
+	sb.st_gid = 456;
+	sb.st_rdev = 789;
+	sb.st_size = 1337;
+
+	node = fstree_mknode(NULL, "fifo", 4, NULL, &sb);
+	TEST_ASSERT((char *)node->name >= (char *)node->payload);
+	TEST_STR_EQUAL(node->name, "fifo");
+	TEST_EQUAL_UI(node->uid, sb.st_uid);
+	TEST_EQUAL_UI(node->gid, sb.st_gid);
+	TEST_EQUAL_UI(node->mode, sb.st_mode);
+	TEST_EQUAL_UI(node->link_count, 1);
+	TEST_NULL(node->parent);
+	TEST_NULL(node->data.target);
+	TEST_EQUAL_UI(node->data.devno, 0);
+	free(node);
+
+	memset(&fs, 0, sizeof(fs));
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFBLK | 0654;
+	sb.st_uid = 123;
+	sb.st_gid = 456;
+	sb.st_rdev = 789;
+	sb.st_size = 1337;
+
+	node = fstree_mknode(NULL, "blkdev", 6, NULL, &sb);
+	TEST_ASSERT((char *)node->name >= (char *)node->payload);
+	TEST_STR_EQUAL(node->name, "blkdev");
+	TEST_EQUAL_UI(node->uid, sb.st_uid);
+	TEST_EQUAL_UI(node->gid, sb.st_gid);
+	TEST_EQUAL_UI(node->mode, sb.st_mode);
+	TEST_EQUAL_UI(node->link_count, 1);
+	TEST_EQUAL_UI(node->data.devno, sb.st_rdev);
+	TEST_NULL(node->parent);
+	free(node);
+
+	memset(&fs, 0, sizeof(fs));
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFCHR | 0654;
+	sb.st_uid = 123;
+	sb.st_gid = 456;
+	sb.st_rdev = 789;
+	sb.st_size = 1337;
+
+	node = fstree_mknode(NULL, "chardev", 7, NULL, &sb);
+	TEST_ASSERT((char *)node->name >= (char *)node->payload);
+	TEST_STR_EQUAL(node->name, "chardev");
+	TEST_EQUAL_UI(node->uid, sb.st_uid);
+	TEST_EQUAL_UI(node->gid, sb.st_gid);
+	TEST_EQUAL_UI(node->mode, sb.st_mode);
+	TEST_EQUAL_UI(node->link_count, 1);
+	TEST_EQUAL_UI(node->data.devno, sb.st_rdev);
+	TEST_NULL(node->parent);
+	free(node);
+
+	return EXIT_SUCCESS;
+}
diff --git a/tests/libfstree/mknode_slink.c b/tests/libfstree/mknode_slink.c
new file mode 100644
index 0000000..29f2679
--- /dev/null
+++ b/tests/libfstree/mknode_slink.c
@@ -0,0 +1,53 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * mknode_slink.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+#include "../test.h"
+
+int main(void)
+{
+	tree_node_t *node;
+	struct stat sb;
+	fstree_t fs;
+
+	memset(&fs, 0, sizeof(fs));
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFLNK | 0654;
+	sb.st_uid = 123;
+	sb.st_gid = 456;
+	sb.st_rdev = 789;
+	sb.st_size = 1337;
+
+	node = fstree_mknode(NULL, "symlink", 7, "target", &sb);
+	TEST_EQUAL_UI(node->uid, sb.st_uid);
+	TEST_EQUAL_UI(node->gid, sb.st_gid);
+	TEST_EQUAL_UI(node->mode, S_IFLNK | 0777);
+	TEST_EQUAL_UI(node->link_count, 1);
+	TEST_NULL(node->parent);
+	TEST_ASSERT((char *)node->name >= (char *)node->payload);
+	TEST_ASSERT(node->data.target >= (char *)node->payload);
+	TEST_ASSERT(node->data.target >= node->name + 8);
+	TEST_STR_EQUAL(node->name, "symlink");
+	TEST_STR_EQUAL(node->data.target, "target");
+	free(node);
+
+	node = fstree_mknode(NULL, "symlink", 7, "", &sb);
+	TEST_EQUAL_UI(node->uid, sb.st_uid);
+	TEST_EQUAL_UI(node->gid, sb.st_gid);
+	TEST_EQUAL_UI(node->mode, S_IFLNK | 0777);
+	TEST_EQUAL_UI(node->link_count, 1);
+	TEST_NULL(node->parent);
+	TEST_ASSERT((char *)node->name >= (char *)node->payload);
+	TEST_ASSERT(node->data.target >= (char *)node->payload);
+	TEST_ASSERT(node->data.target >= node->name + 8);
+	TEST_STR_EQUAL(node->name, "symlink");
+	TEST_STR_EQUAL(node->data.target, "");
+	free(node);
+
+	return EXIT_SUCCESS;
+}