Move gensquashfs specific code from libfstree to gensquashfs

The "from dir" and from "from file" code, as well as the "sort file"
code is specific to gensquashfs, so move them there and the test
cases as well.

The medium term idea is to reduce libfstree to a stub, merge it into
the generic writer and ultimately hoist that into libsquashfs.

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

5 files changed, 1491 insertions, 0 deletions

diff --git a/bin/gensquashfs/Makemodule.am b/bin/gensquashfs/Makemodule.am
index e7fad8e..c6a98a2 100644
--- a/bin/gensquashfs/Makemodule.am
+++ b/bin/gensquashfs/Makemodule.am
@@ -2,6 +2,9 @@ gensquashfs_SOURCES = bin/gensquashfs/mkfs.c bin/gensquashfs/mkfs.h
 gensquashfs_SOURCES += bin/gensquashfs/options.c bin/gensquashfs/selinux.c
 gensquashfs_SOURCES += bin/gensquashfs/dirscan_xattr.c
 gensquashfs_SOURCES += bin/gensquashfs/filemap_xattr.c
+gensquashfs_SOURCES += bin/gensquashfs/fstree_from_file.c
+gensquashfs_SOURCES += bin/gensquashfs/fstree_from_dir.c
+gensquashfs_SOURCES += bin/gensquashfs/sort_by_file.c
 gensquashfs_LDADD = libcommon.a libsquashfs.la libfstree.a libio.a
 gensquashfs_LDADD += libutil.a libcompat.a $(LZO_LIBS) $(PTHREAD_LIBS)
 gensquashfs_CPPFLAGS = $(AM_CPPFLAGS)
diff --git a/bin/gensquashfs/fstree_from_dir.c b/bin/gensquashfs/fstree_from_dir.c
new file mode 100644
index 0000000..5b3f003
--- /dev/null
+++ b/bin/gensquashfs/fstree_from_dir.c
@@ -0,0 +1,493 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fstree_from_dir.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "mkfs.h"
+
+#include <dirent.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+
+#if defined(_WIN32) || defined(__WINDOWS__)
+#define UNIX_EPOCH_ON_W32 11644473600UL
+#define W32_TICS_PER_SEC 10000000UL
+
+static sqfs_u32 w32time_to_sqfs_time(const FILETIME *ft)
+{
+	sqfs_u64 w32ts;
+
+	w32ts = ft->dwHighDateTime;
+	w32ts <<= 32UL;
+	w32ts |= ft->dwLowDateTime;
+
+	w32ts /= W32_TICS_PER_SEC;
+
+	if (w32ts <= UNIX_EPOCH_ON_W32)
+		return 0;
+
+	w32ts -= UNIX_EPOCH_ON_W32;
+
+	return (w32ts < 0x0FFFFFFFFUL) ? w32ts : 0xFFFFFFFF;
+}
+
+static int add_node(fstree_t *fs, tree_node_t *root,
+		    scan_node_callback cb, void *user,
+		    unsigned int flags,
+		    const LPWIN32_FIND_DATAW entry)
+{
+	tree_node_t *n;
+	DWORD length;
+
+	if (entry->cFileName[0] == '.') {
+		if (entry->cFileName[1] == '\0')
+			return 0;
+
+		if (entry->cFileName[1] == '.' && entry->cFileName[2] == '\0')
+			return 0;
+	}
+
+	length = WideCharToMultiByte(CP_UTF8, 0, entry->cFileName,
+				     -1, NULL, 0, NULL, NULL);
+	if (length <= 0) {
+		w32_perror("converting path to UTF-8");
+		return -1;
+	}
+
+	n = calloc(1, sizeof(*n) + length + 1);
+	if (n == NULL) {
+		fprintf(stderr, "creating tree node: out-of-memory\n");
+		return -1;
+	}
+
+	n->name = (char *)n->payload;
+	WideCharToMultiByte(CP_UTF8, 0, entry->cFileName, -1,
+			    n->name, length + 1, NULL, NULL);
+
+	if (entry->dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) {
+		if (flags & DIR_SCAN_NO_DIR) {
+			free(n);
+			return 0;
+		}
+
+		n->mode = S_IFDIR | 0755;
+	} else {
+		if (flags & DIR_SCAN_NO_FILE) {
+			free(n);
+			return 0;
+		}
+
+		n->mode = S_IFREG | 0644;
+	}
+
+	if (cb != NULL) {
+		int ret = cb(user, fs, n);
+
+		if (ret != 0) {
+			free(n);
+			return ret < 0 ? ret : 0;
+		}
+	}
+
+	if (flags & DIR_SCAN_KEEP_TIME) {
+		n->mod_time = w32time_to_sqfs_time(&(entry->ftLastWriteTime));
+	} else {
+		n->mod_time = fs->defaults.st_mtime;
+	}
+
+	fstree_insert_sorted(root, n);
+	return 0;
+}
+
+static int scan_dir(fstree_t *fs, tree_node_t *root,
+		    const char *path, const WCHAR *wpath,
+		    scan_node_callback cb, void *user,
+		    unsigned int flags)
+{
+	WIN32_FIND_DATAW entry;
+	HANDLE dirhnd;
+
+	dirhnd = FindFirstFileW(wpath, &entry);
+
+	if (dirhnd == INVALID_HANDLE_VALUE)
+		goto fail_perror;
+
+	do {
+		if (add_node(fs, root, cb, user, flags, &entry))
+			goto fail;
+	} while (FindNextFileW(dirhnd, &entry));
+
+	if (GetLastError() != ERROR_NO_MORE_FILES)
+		goto fail_perror;
+
+	FindClose(dirhnd);
+	return 0;
+fail_perror:
+	w32_perror(path);
+fail:
+	if (dirhnd != INVALID_HANDLE_VALUE)
+		FindClose(dirhnd);
+	return -1;
+}
+
+int fstree_from_dir(fstree_t *fs, tree_node_t *root,
+		    const char *path, scan_node_callback cb,
+		    void *user, unsigned int flags)
+{
+	WCHAR *wpath = NULL, *new = NULL;
+	size_t len, newlen;
+	tree_node_t *n;
+
+	/* path -> to_wchar(path) + L"\*" */
+	wpath = path_to_windows(path);
+	if (wpath == NULL) {
+		fprintf(stderr, "%s: allocation failure.\n", path);
+		return -1;
+	}
+
+	for (len = 0; wpath[len] != '\0'; ++len)
+		;
+
+	newlen = len + 1;
+
+	if (len > 0 && wpath[len - 1] != '\\')
+		newlen += 1;
+
+	new = realloc(wpath, sizeof(wpath[0]) * (newlen + 1));
+	if (new == NULL) {
+		fprintf(stderr, "%s: allocation failure.\n", path);
+		goto fail;
+	}
+
+	wpath = new;
+
+	if (len > 0 && wpath[len - 1] != '\\')
+		wpath[len++] = '\\';
+
+	wpath[len++] = '*';
+	wpath[len++] = '\0';
+
+	/* scan directory contents */
+	if (scan_dir(fs, root, path, wpath, cb, user, flags))
+		goto fail;
+
+	free(wpath);
+	wpath = NULL;
+
+	/* recursion step */
+	if (flags & DIR_SCAN_NO_RECURSION)
+		return 0;
+
+	for (n = root->data.dir.children; n != NULL; n = n->next) {
+		if (!S_ISDIR(n->mode))
+			continue;
+
+		if (fstree_from_subdir(fs, n, path, n->name, cb, user, flags))
+			return -1;
+	}
+
+	return 0;
+fail:
+	free(wpath);
+	return -1;
+}
+
+int fstree_from_subdir(fstree_t *fs, tree_node_t *root,
+		       const char *path, const char *subdir,
+		       scan_node_callback cb, void *user,
+		       unsigned int flags)
+{
+	size_t len, plen, slen;
+	WCHAR *wpath = NULL;
+	char *temp = NULL;
+	tree_node_t *n;
+
+	plen = strlen(path);
+	slen = subdir == NULL ? 0 : strlen(subdir);
+
+	if (slen == 0)
+		return fstree_from_dir(fs, root, path, cb, user, flags);
+
+	len = plen + 1 + slen + 2;
+
+	temp = calloc(1, len + 1);
+	if (temp == NULL) {
+		fprintf(stderr, "%s/%s: allocation failure.\n", path, subdir);
+		return -1;
+	}
+
+	memcpy(temp, path, plen);
+	temp[plen] = '/';
+	memcpy(temp + plen + 1, subdir, slen);
+	temp[plen + 1 + slen    ] = '/';
+	temp[plen + 1 + slen + 1] = '*';
+	temp[plen + 1 + slen + 2] = '\0';
+
+	wpath = path_to_windows(temp);
+	if (wpath == NULL) {
+		fprintf(stderr, "%s: allocation failure.\n", temp);
+		goto fail;
+	}
+
+	if (scan_dir(fs, root, temp, wpath, cb, user, flags))
+		goto fail;
+
+	free(wpath);
+	wpath = NULL;
+
+	if (flags & DIR_SCAN_NO_RECURSION) {
+		free(temp);
+		return 0;
+	}
+
+	temp[plen + 1 + slen] = '\0';
+
+	for (n = root->data.dir.children; n != NULL; n = n->next) {
+		if (!S_ISDIR(n->mode))
+			continue;
+
+		if (fstree_from_subdir(fs, n, temp, n->name, cb, user, flags))
+			goto fail;
+	}
+
+	free(temp);
+	return 0;
+fail:
+	free(temp);
+	free(wpath);
+	return -1;
+
+}
+#else
+static void discard_node(tree_node_t *root, tree_node_t *n)
+{
+	tree_node_t *it;
+
+	if (n == root->data.dir.children) {
+		root->data.dir.children = n->next;
+	} else {
+		it = root->data.dir.children;
+
+		while (it != NULL && it->next != n)
+			it = it->next;
+
+		if (it != NULL)
+			it->next = n->next;
+	}
+
+	free(n);
+}
+
+static int populate_dir(int dir_fd, fstree_t *fs, tree_node_t *root,
+			dev_t devstart, scan_node_callback cb,
+			void *user, unsigned int flags)
+{
+	char *extra = NULL;
+	struct dirent *ent;
+	int ret, childfd;
+	struct stat sb;
+	tree_node_t *n;
+	DIR *dir;
+
+	dir = fdopendir(dir_fd);
+	if (dir == NULL) {
+		perror("fdopendir");
+		close(dir_fd);
+		return -1;
+	}
+
+	/* XXX: fdopendir can dup and close dir_fd internally
+	   and still be compliant with the spec. */
+	dir_fd = dirfd(dir);
+
+	for (;;) {
+		errno = 0;
+		ent = readdir(dir);
+
+		if (ent == NULL) {
+			if (errno) {
+				perror("readdir");
+				goto fail;
+			}
+			break;
+		}
+
+		if (!strcmp(ent->d_name, "..") || !strcmp(ent->d_name, "."))
+			continue;
+
+		if (fstatat(dir_fd, ent->d_name, &sb, AT_SYMLINK_NOFOLLOW)) {
+			perror(ent->d_name);
+			goto fail;
+		}
+
+		switch (sb.st_mode & S_IFMT) {
+		case S_IFSOCK:
+			if (flags & DIR_SCAN_NO_SOCK)
+				continue;
+			break;
+		case S_IFLNK:
+			if (flags & DIR_SCAN_NO_SLINK)
+				continue;
+			break;
+		case S_IFREG:
+			if (flags & DIR_SCAN_NO_FILE)
+				continue;
+			break;
+		case S_IFBLK:
+			if (flags & DIR_SCAN_NO_BLK)
+				continue;
+			break;
+		case S_IFCHR:
+			if (flags & DIR_SCAN_NO_CHR)
+				continue;
+			break;
+		case S_IFIFO:
+			if (flags & DIR_SCAN_NO_FIFO)
+				continue;
+			break;
+		default:
+			break;
+		}
+
+		if ((flags & DIR_SCAN_ONE_FILESYSTEM) && sb.st_dev != devstart)
+			continue;
+
+		if (S_ISLNK(sb.st_mode)) {
+			size_t size;
+
+			if ((sizeof(sb.st_size) > sizeof(size_t)) &&
+			    sb.st_size > SIZE_MAX) {
+				errno = EOVERFLOW;
+				goto fail_rdlink;
+			}
+
+			if (SZ_ADD_OV((size_t)sb.st_size, 1, &size)) {
+				errno = EOVERFLOW;
+				goto fail_rdlink;
+			}
+
+			extra = calloc(1, size);
+			if (extra == NULL)
+				goto fail_rdlink;
+
+			if (readlinkat(dir_fd, ent->d_name,
+				       extra, (size_t)sb.st_size) < 0) {
+				goto fail_rdlink;
+			}
+
+			extra[sb.st_size] = '\0';
+		}
+
+		if (!(flags & DIR_SCAN_KEEP_TIME))
+			sb.st_mtime = fs->defaults.st_mtime;
+
+		if (S_ISDIR(sb.st_mode) && (flags & DIR_SCAN_NO_DIR)) {
+			n = fstree_get_node_by_path(fs, root, ent->d_name,
+						    false, false);
+			if (n == NULL)
+				continue;
+
+			ret = 0;
+		} else {
+			n = fstree_mknode(root, ent->d_name,
+					  strlen(ent->d_name), extra, &sb);
+			if (n == NULL) {
+				perror("creating tree node");
+				goto fail;
+			}
+
+			ret = (cb == NULL) ? 0 : cb(user, fs, n);
+		}
+
+		free(extra);
+		extra = NULL;
+
+		if (ret < 0)
+			goto fail;
+
+		if (ret > 0) {
+			discard_node(root, n);
+			continue;
+		}
+
+		if (S_ISDIR(n->mode) && !(flags & DIR_SCAN_NO_RECURSION)) {
+			childfd = openat(dir_fd, n->name, O_DIRECTORY |
+					 O_RDONLY | O_CLOEXEC);
+			if (childfd < 0) {
+				perror(n->name);
+				goto fail;
+			}
+
+			if (populate_dir(childfd, fs, n, devstart,
+					 cb, user, flags)) {
+				goto fail;
+			}
+		}
+	}
+
+	closedir(dir);
+	return 0;
+fail_rdlink:
+	perror("readlink");
+fail:
+	closedir(dir);
+	free(extra);
+	return -1;
+}
+
+int fstree_from_subdir(fstree_t *fs, tree_node_t *root,
+		       const char *path, const char *subdir,
+		       scan_node_callback cb, void *user,
+		       unsigned int flags)
+{
+	struct stat sb;
+	int fd, subfd;
+
+	if (!S_ISDIR(root->mode)) {
+		fprintf(stderr,
+			"scanning %s/%s into %s: target is not a directory\n",
+			path, subdir == NULL ? "" : subdir, root->name);
+		return -1;
+	}
+
+	fd = open(path, O_DIRECTORY | O_RDONLY | O_CLOEXEC);
+	if (fd < 0) {
+		perror(path);
+		return -1;
+	}
+
+	if (subdir != NULL) {
+		subfd = openat(fd, subdir, O_DIRECTORY | O_RDONLY | O_CLOEXEC);
+
+		if (subfd < 0) {
+			fprintf(stderr, "%s/%s: %s\n", path, subdir,
+				strerror(errno));
+			close(fd);
+			return -1;
+		}
+
+		close(fd);
+		fd = subfd;
+	}
+
+	if (fstat(fd, &sb)) {
+		fprintf(stderr, "%s/%s: %s\n", path,
+			subdir == NULL ? "" : subdir,
+			strerror(errno));
+		close(fd);
+		return -1;
+	}
+
+	return populate_dir(fd, fs, root, sb.st_dev, cb, user, flags);
+}
+
+int fstree_from_dir(fstree_t *fs, tree_node_t *root,
+		    const char *path, scan_node_callback cb,
+		    void *user, unsigned int flags)
+{
+	return fstree_from_subdir(fs, root, path, NULL, cb, user, flags);
+}
+#endif
diff --git a/bin/gensquashfs/fstree_from_file.c b/bin/gensquashfs/fstree_from_file.c
new file mode 100644
index 0000000..feacbbc
--- /dev/null
+++ b/bin/gensquashfs/fstree_from_file.c
@@ -0,0 +1,591 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fstree_from_file.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/util.h"
+#include "io/file.h"
+#include "compat.h"
+#include "mkfs.h"
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <errno.h>
+#include <ctype.h>
+
+struct glob_context {
+	const char *filename;
+	size_t line_num;
+
+	struct stat *basic;
+	unsigned int glob_flags;
+
+	char *name_pattern;
+};
+
+enum {
+	GLOB_MODE_FROM_SRC = 0x01,
+	GLOB_UID_FROM_SRC = 0x02,
+	GLOB_GID_FROM_SRC = 0x04,
+	GLOB_FLAG_PATH = 0x08,
+};
+
+static const struct {
+	const char *name;
+	unsigned int clear_flag;
+	unsigned int set_flag;
+} glob_scan_flags[] = {
+	{ "-type b", DIR_SCAN_NO_BLK, 0 },
+	{ "-type c", DIR_SCAN_NO_CHR, 0 },
+	{ "-type d", DIR_SCAN_NO_DIR, 0 },
+	{ "-type p", DIR_SCAN_NO_FIFO, 0 },
+	{ "-type f", DIR_SCAN_NO_FILE, 0 },
+	{ "-type l", DIR_SCAN_NO_SLINK, 0 },
+	{ "-type s", DIR_SCAN_NO_SOCK, 0 },
+	{ "-xdev", 0, DIR_SCAN_ONE_FILESYSTEM },
+	{ "-mount", 0, DIR_SCAN_ONE_FILESYSTEM },
+	{ "-keeptime", 0, DIR_SCAN_KEEP_TIME },
+	{ "-nonrecursive", 0, DIR_SCAN_NO_RECURSION },
+};
+
+static int add_generic(fstree_t *fs, const char *filename, size_t line_num,
+		       const char *path, struct stat *sb,
+		       const char *basepath, unsigned int glob_flags,
+		       const char *extra)
+{
+	(void)basepath;
+	(void)glob_flags;
+
+	if (fstree_add_generic(fs, path, sb, extra) == NULL) {
+		fprintf(stderr, "%s: " PRI_SZ ": %s: %s\n",
+			filename, line_num, path, strerror(errno));
+		return -1;
+	}
+
+	return 0;
+}
+
+static int add_device(fstree_t *fs, const char *filename, size_t line_num,
+		      const char *path, struct stat *sb, const char *basepath,
+		      unsigned int glob_flags, const char *extra)
+{
+	unsigned int maj, min;
+	char c;
+
+	if (sscanf(extra, "%c %u %u", &c, &maj, &min) != 3) {
+		fprintf(stderr, "%s: " PRI_SZ ": "
+			"expected '<c|b> major minor'\n",
+			filename, line_num);
+		return -1;
+	}
+
+	if (c == 'c' || c == 'C') {
+		sb->st_mode |= S_IFCHR;
+	} else if (c == 'b' || c == 'B') {
+		sb->st_mode |= S_IFBLK;
+	} else {
+		fprintf(stderr, "%s: " PRI_SZ ": unknown device type '%c'\n",
+			filename, line_num, c);
+		return -1;
+	}
+
+	sb->st_rdev = makedev(maj, min);
+	return add_generic(fs, filename, line_num, path, sb, basepath,
+			   glob_flags, NULL);
+}
+
+static int add_file(fstree_t *fs, const char *filename, size_t line_num,
+		    const char *path, struct stat *basic, const char *basepath,
+		    unsigned int glob_flags, const char *extra)
+{
+	if (extra == NULL || *extra == '\0')
+		extra = path;
+
+	return add_generic(fs, filename, line_num, path, basic,
+			   basepath, glob_flags, extra);
+}
+
+static int add_hard_link(fstree_t *fs, const char *filename, size_t line_num,
+			 const char *path, struct stat *basic,
+			 const char *basepath, unsigned int glob_flags,
+			 const char *extra)
+{
+	(void)basepath;
+	(void)glob_flags;
+	(void)basic;
+
+	if (fstree_add_hard_link(fs, path, extra) == NULL) {
+		fprintf(stderr, "%s: " PRI_SZ ": %s\n",
+			filename, line_num, strerror(errno));
+		return -1;
+	}
+	return 0;
+}
+
+static int glob_node_callback(void *user, fstree_t *fs, tree_node_t *node)
+{
+	struct glob_context *ctx = user;
+	char *path;
+	int ret;
+	(void)fs;
+
+	if (!(ctx->glob_flags & GLOB_MODE_FROM_SRC)) {
+		node->mode &= ~(07777);
+		node->mode |= ctx->basic->st_mode & 07777;
+	}
+
+	if (!(ctx->glob_flags & GLOB_UID_FROM_SRC))
+		node->uid = ctx->basic->st_uid;
+
+	if (!(ctx->glob_flags & GLOB_GID_FROM_SRC))
+		node->gid = ctx->basic->st_gid;
+
+	if (ctx->name_pattern != NULL) {
+		if (ctx->glob_flags & GLOB_FLAG_PATH) {
+			path = fstree_get_path(node);
+			if (path == NULL) {
+				fprintf(stderr, "%s: " PRI_SZ ": %s\n",
+					ctx->filename, ctx->line_num,
+					strerror(errno));
+				return -1;
+			}
+
+			ret = canonicalize_name(path);
+			assert(ret == 0);
+
+			ret = fnmatch(ctx->name_pattern, path, FNM_PATHNAME);
+			free(path);
+		} else {
+			ret = fnmatch(ctx->name_pattern, node->name, 0);
+		}
+
+		if (ret != 0)
+			return 1;
+	}
+
+	return 0;
+}
+
+static size_t name_string_length(const char *str)
+{
+	size_t len = 0;
+	int start;
+
+	if (*str == '"' || *str == '\'') {
+		start = *str;
+		++len;
+
+		while (str[len] != '\0' && str[len] != start)
+			++len;
+
+		if (str[len] == start)
+			++len;
+	} else {
+		while (str[len] != '\0' && !isspace(str[len]))
+			++len;
+	}
+
+	return len;
+}
+
+static void quote_remove(char *str)
+{
+	char *dst = str;
+	int start = *(str++);
+
+	if (start != '\'' && start != '"')
+		return;
+
+	while (*str != start && *str != '\0')
+		*(dst++) = *(str++);
+
+	*(dst++) = '\0';
+}
+
+static int glob_files(fstree_t *fs, const char *filename, size_t line_num,
+		      const char *path, struct stat *basic,
+		      const char *basepath, unsigned int glob_flags,
+		      const char *extra)
+{
+	unsigned int scan_flags = 0, all_flags;
+	struct glob_context ctx;
+	bool first_clear_flag;
+	size_t i, count, len;
+	tree_node_t *root;
+	int ret;
+
+	memset(&ctx, 0, sizeof(ctx));
+	ctx.filename = filename;
+	ctx.line_num = line_num;
+	ctx.basic = basic;
+	ctx.glob_flags = glob_flags;
+
+	/* fetch the actual target node */
+	root = fstree_get_node_by_path(fs, fs->root, path, true, false);
+	if (root == NULL) {
+		fprintf(stderr, "%s: " PRI_SZ ": %s: %s\n",
+			filename, line_num, path, strerror(errno));
+		return -1;
+	}
+
+	/* process options */
+	first_clear_flag = true;
+
+	all_flags = DIR_SCAN_NO_BLK | DIR_SCAN_NO_CHR | DIR_SCAN_NO_DIR |
+		DIR_SCAN_NO_FIFO | DIR_SCAN_NO_FILE | DIR_SCAN_NO_SLINK |
+		DIR_SCAN_NO_SOCK;
+
+	while (extra != NULL && *extra != '\0') {
+		count = sizeof(glob_scan_flags) / sizeof(glob_scan_flags[0]);
+
+		for (i = 0; i < count; ++i) {
+			len = strlen(glob_scan_flags[i].name);
+			if (strncmp(extra, glob_scan_flags[i].name, len) != 0)
+				continue;
+
+			if (isspace(extra[len])) {
+				extra += len;
+				while (isspace(*extra))
+					++extra;
+				break;
+			}
+		}
+
+		if (i < count) {
+			if (glob_scan_flags[i].clear_flag != 0 &&
+			    first_clear_flag) {
+				scan_flags |= all_flags;
+				first_clear_flag = false;
+			}
+
+			scan_flags &= ~(glob_scan_flags[i].clear_flag);
+			scan_flags |= glob_scan_flags[i].set_flag;
+			continue;
+		}
+
+		if (strncmp(extra, "-name", 5) == 0 && isspace(extra[5])) {
+			for (extra += 5; isspace(*extra); ++extra)
+				;
+
+			len = name_string_length(extra);
+
+			free(ctx.name_pattern);
+			ctx.name_pattern = strndup(extra, len);
+			extra += len;
+
+			while (isspace(*extra))
+				++extra;
+
+			quote_remove(ctx.name_pattern);
+			continue;
+		}
+
+		if (strncmp(extra, "-path", 5) == 0 && isspace(extra[5])) {
+			for (extra += 5; isspace(*extra); ++extra)
+				;
+
+			len = name_string_length(extra);
+
+			free(ctx.name_pattern);
+			ctx.name_pattern = strndup(extra, len);
+			extra += len;
+
+			while (isspace(*extra))
+				++extra;
+
+			quote_remove(ctx.name_pattern);
+			ctx.glob_flags |= GLOB_FLAG_PATH;
+			continue;
+		}
+
+		if (extra[0] == '-') {
+			if (extra[1] == '-' && isspace(extra[2])) {
+				extra += 2;
+				while (isspace(*extra))
+					++extra;
+				break;
+			}
+
+			fprintf(stderr, "%s: " PRI_SZ ": unknown option.\n",
+				filename, line_num);
+			free(ctx.name_pattern);
+			return -1;
+		} else {
+			break;
+		}
+	}
+
+	if (extra != NULL && *extra == '\0')
+		extra = NULL;
+
+	/* do the scan */
+	if (basepath == NULL) {
+		if (extra == NULL) {
+			ret = fstree_from_dir(fs, root, ".", glob_node_callback,
+					      &ctx, scan_flags);
+		} else {
+			ret = fstree_from_dir(fs, root, extra,
+					      glob_node_callback,
+					      &ctx, scan_flags);
+		}
+	} else {
+		ret = fstree_from_subdir(fs, root, basepath, extra,
+					 glob_node_callback, &ctx,
+					 scan_flags);
+	}
+
+	free(ctx.name_pattern);
+	return ret;
+}
+
+static const struct callback_t {
+	const char *keyword;
+	unsigned int mode;
+	bool need_extra;
+	bool is_glob;
+	bool allow_root;
+	int (*callback)(fstree_t *fs, const char *filename, size_t line_num,
+			const char *path, struct stat *sb,
+			const char *basepath, unsigned int glob_flags,
+			const char *extra);
+} file_list_hooks[] = {
+	{ "dir", S_IFDIR, false, false, true, add_generic },
+	{ "slink", S_IFLNK, true, false, false, add_generic },
+	{ "link", 0, true, false, false, add_hard_link },
+	{ "nod", 0, true, false, false, add_device },
+	{ "pipe", S_IFIFO, false, false, false, add_generic },
+	{ "sock", S_IFSOCK, false, false, false, add_generic },
+	{ "file", S_IFREG, false, false, false, add_file },
+	{ "glob", 0, false, true, true, glob_files },
+};
+
+#define NUM_HOOKS (sizeof(file_list_hooks) / sizeof(file_list_hooks[0]))
+
+static char *skip_space(char *str)
+{
+	if (!isspace(*str))
+		return NULL;
+	while (isspace(*str))
+		++str;
+	return str;
+}
+
+static char *read_u32(char *str, sqfs_u32 *out, sqfs_u32 base)
+{
+	*out = 0;
+
+	if (!isdigit(*str))
+		return NULL;
+
+	while (isdigit(*str)) {
+		sqfs_u32 x = *(str++) - '0';
+
+		if (x >= base || (*out) > (0xFFFFFFFF - x) / base)
+			return NULL;
+
+		(*out) = (*out) * base + x;
+	}
+
+	return str;
+}
+
+static char *read_str(char *str, char **out)
+{
+	*out = str;
+
+	if (*str == '"') {
+		char *ptr = str++;
+
+		while (*str != '\0' && *str != '"') {
+			if (str[0] == '\\' &&
+			    (str[1] == '"' || str[1] == '\\')) {
+				*(ptr++) = str[1];
+				str += 2;
+			} else {
+				*(ptr++) = *(str++);
+			}
+		}
+
+		if (str[0] != '"' || !isspace(str[1]))
+			return NULL;
+
+		*ptr = '\0';
+		++str;
+	} else {
+		while (*str != '\0' && !isspace(*str))
+			++str;
+
+		if (!isspace(*str))
+			return NULL;
+
+		*(str++) = '\0';
+	}
+
+	while (isspace(*str))
+		++str;
+
+	return str;
+}
+
+static int handle_line(fstree_t *fs, const char *filename,
+		       size_t line_num, char *line,
+		       const char *basepath)
+{
+	const char *extra = NULL, *msg = NULL;
+	const struct callback_t *cb = NULL;
+	unsigned int glob_flags = 0;
+	sqfs_u32 uid, gid, mode;
+	struct stat sb;
+	char *path;
+
+	for (size_t i = 0; i < NUM_HOOKS; ++i) {
+		size_t len = strlen(file_list_hooks[i].keyword);
+		if (strncmp(file_list_hooks[i].keyword, line, len) != 0)
+			continue;
+
+		if (isspace(line[len])) {
+			cb = file_list_hooks + i;
+			line = skip_space(line + len);
+			break;
+		}
+	}
+
+	if (cb == NULL)
+		goto fail_kw;
+
+	if ((line = read_str(line, &path)) == NULL)
+		goto fail_ent;
+
+	if (canonicalize_name(path))
+		goto fail_ent;
+
+	if (*path == '\0' && !cb->allow_root)
+		goto fail_root;
+
+	if (cb->is_glob && *line == '*') {
+		++line;
+		mode = 0;
+		glob_flags |= GLOB_MODE_FROM_SRC;
+	} else {
+		if ((line = read_u32(line, &mode, 8)) == NULL || mode > 07777)
+			goto fail_mode;
+	}
+
+	if ((line = skip_space(line)) == NULL)
+		goto fail_ent;
+
+	if (cb->is_glob && *line == '*') {
+		++line;
+		uid = 0;
+		glob_flags |= GLOB_UID_FROM_SRC;
+	} else {
+		if ((line = read_u32(line, &uid, 10)) == NULL)
+			goto fail_uid_gid;
+	}
+
+	if ((line = skip_space(line)) == NULL)
+		goto fail_ent;
+
+	if (cb->is_glob && *line == '*') {
+		++line;
+		gid = 0;
+		glob_flags |= GLOB_GID_FROM_SRC;
+	} else {
+		if ((line = read_u32(line, &gid, 10)) == NULL)
+			goto fail_uid_gid;
+	}
+
+	if ((line = skip_space(line)) != NULL && *line != '\0')
+		extra = line;
+
+	if (cb->need_extra && extra == NULL)
+		goto fail_no_extra;
+
+	/* forward to callback */
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mtime = fs->defaults.st_mtime;
+	sb.st_mode = mode | cb->mode;
+	sb.st_uid = uid;
+	sb.st_gid = gid;
+
+	return cb->callback(fs, filename, line_num, path,
+			    &sb, basepath, glob_flags, extra);
+fail_root:
+	fprintf(stderr, "%s: " PRI_SZ ": cannot use / as argument for %s.\n",
+		filename, line_num, cb->keyword);
+	return -1;
+fail_no_extra:
+	fprintf(stderr, "%s: " PRI_SZ ": missing argument for %s.\n",
+		filename, line_num, cb->keyword);
+	return -1;
+fail_uid_gid:
+	msg = "uid & gid must be decimal numbers < 2^32";
+	goto out_desc;
+fail_mode:
+	msg = "mode must be an octal number <= 07777";
+	goto out_desc;
+fail_kw:
+	msg = "unknown entry type";
+	goto out_desc;
+fail_ent:
+	msg = "error in entry description";
+	goto out_desc;
+out_desc:
+	fprintf(stderr, "%s: " PRI_SZ ": %s.\n", filename, line_num, msg);
+	fputs("expected: <type> <path> <mode> <uid> <gid> [<extra>]\n",
+	      stderr);
+	return -1;
+}
+
+int fstree_from_file_stream(fstree_t *fs, istream_t *fp, const char *basepath)
+{
+	const char *filename;
+	size_t line_num = 1;
+	char *line;
+	int ret;
+
+	filename = istream_get_filename(fp);
+
+	for (;;) {
+		ret = istream_get_line(fp, &line, &line_num,
+				       ISTREAM_LINE_LTRIM | ISTREAM_LINE_SKIP_EMPTY);
+		if (ret < 0)
+			return -1;
+		if (ret > 0)
+			break;
+
+		if (line[0] != '#') {
+			if (handle_line(fs, filename, line_num,
+					line, basepath)) {
+				goto fail_line;
+			}
+		}
+
+		free(line);
+		++line_num;
+	}
+
+	return 0;
+fail_line:
+	free(line);
+	return -1;
+}
+
+int fstree_from_file(fstree_t *fs, const char *filename, const char *basepath)
+{
+	istream_t *fp;
+	int ret;
+
+	fp = istream_open_file(filename);
+	if (fp == NULL)
+		return -1;
+
+	ret = fstree_from_file_stream(fs, fp, basepath);
+
+	sqfs_destroy(fp);
+	return ret;
+}
diff --git a/bin/gensquashfs/mkfs.h b/bin/gensquashfs/mkfs.h
index 33ba707..53fb018 100644
--- a/bin/gensquashfs/mkfs.h
+++ b/bin/gensquashfs/mkfs.h
@@ -98,4 +98,40 @@ int selinux_relable_node(void *sehnd, sqfs_xattr_writer_t *xwr,
 
 void selinux_close_context_file(void *sehnd);
 
+/*
+  Parses the file format accepted by gensquashfs and produce a file system
+  tree from it. File input paths are interpreted as relative to the current
+  working directory.
+
+  On failure, an error report with filename and line number is written
+  to stderr.
+
+  Returns 0 on success.
+ */
+int fstree_from_file(fstree_t *fs, const char *filename,
+		     const char *basepath);
+
+int fstree_from_file_stream(fstree_t *fs, istream_t *file,
+			    const char *basepath);
+
+/*
+  Recursively scan a directory to build a file system tree.
+
+  Returns 0 on success, prints to stderr on failure.
+ */
+int fstree_from_dir(fstree_t *fs, tree_node_t *root,
+		    const char *path, scan_node_callback cb, void *user,
+		    unsigned int flags);
+
+/*
+  Same as fstree_from_dir, but scans a sub-directory inside the specified path.
+
+  Returns 0 on success, prints to stderr on failure.
+ */
+int fstree_from_subdir(fstree_t *fs, tree_node_t *root,
+		       const char *path, const char *subdir,
+		       scan_node_callback cb, void *user, unsigned int flags);
+
+int fstree_sort_files(fstree_t *fs, istream_t *sortfile);
+
 #endif /* MKFS_H */
diff --git a/bin/gensquashfs/sort_by_file.c b/bin/gensquashfs/sort_by_file.c
new file mode 100644
index 0000000..a555718
--- /dev/null
+++ b/bin/gensquashfs/sort_by_file.c
@@ -0,0 +1,368 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * sort_by_file.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/util.h"
+#include "fstree.h"
+#include "mkfs.h"
+
+#include "sqfs/block.h"
+
+#include <string.h>
+#include <stdlib.h>
+#include <ctype.h>
+
+static int decode_priority(const char *filename, size_t line_no,
+			   char *line, sqfs_s64 *priority)
+{
+	bool negative = false;
+	size_t i = 0;
+
+	if (line[0] == '-') {
+		negative = true;
+		i = 1;
+	}
+
+	if (!isdigit(line[i]))
+		goto fail_number;
+
+	*priority = 0;
+
+	for (; isdigit(line[i]); ++i) {
+		sqfs_s64 x = line[i] - '0';
+
+		if ((*priority) >= ((0x7FFFFFFFFFFFFFFFL - x) / 10L))
+			goto fail_ov;
+
+		(*priority) = (*priority) * 10 + x;
+	}
+
+	if (!isspace(line[i]))
+		goto fail_filename;
+
+	while (isspace(line[i]))
+		++i;
+
+	if (line[i] == '\0')
+		goto fail_filename;
+
+	if (negative)
+		(*priority) = -(*priority);
+
+	memmove(line, line + i, strlen(line + i) + 1);
+	return 0;
+fail_number:
+	fprintf(stderr, "%s: " PRI_SZ ": Line must start with "
+		"numeric sort priority.\n",
+		filename, line_no);
+	return -1;
+fail_ov:
+	fprintf(stderr, "%s: " PRI_SZ ": Numeric overflow in sort priority.\n",
+		filename, line_no);
+	return -1;
+fail_filename:
+	fprintf(stderr, "%s: " PRI_SZ ": Expacted `<space> <filename>` "
+		"after sort priority.\n",
+		filename, line_no);
+	return -1;
+}
+
+static int decode_filename(const char *filename, size_t line_no, char *buffer)
+{
+	char *src, *dst;
+
+	if (buffer[0] == '"') {
+		src = buffer + 1;
+		dst = buffer;
+
+		for (;;) {
+			if (src[0] == '\0')
+				goto fail_match;
+
+			if (src[0] == '"') {
+				++src;
+				break;
+			}
+
+			if (src[0] == '\\') {
+				switch (src[1]) {
+				case '\\':
+					*(dst++) = '\\';
+					src += 2;
+					break;
+				case '"':
+					*(dst++) = '"';
+					src += 2;
+					break;
+				default:
+					goto fail_escape;
+				}
+			} else {
+				*(dst++) = *(src++);
+			}
+		}
+
+		if (*src != '\0')
+			return -1;
+	}
+
+	if (canonicalize_name(buffer))
+		goto fail_canon;
+	return 0;
+fail_canon:
+	fprintf(stderr, "%s: " PRI_SZ ": Malformed filename.\n",
+		filename, line_no);
+	return -1;
+fail_escape:
+	fprintf(stderr, "%s: " PRI_SZ ": Unknown escape sequence `\\%c` "
+		"in filename.\n", filename, line_no, src[1]);
+	return -1;
+fail_match:
+	fprintf(stderr, "%s: " PRI_SZ ": Unmatched '\"' in filename.\n",
+		filename, line_no);
+	return -1;
+}
+
+static int decode_flags(const char *filename, size_t line_no, bool *do_glob,
+			bool *path_glob, int *flags, char *line)
+{
+	char *start = line;
+
+	*do_glob = false;
+	*path_glob = false;
+	*flags = 0;
+
+	if (*(line++) != '[')
+		return 0;
+
+	for (;;) {
+		while (isspace(*line))
+			++line;
+
+		if (*line == ']') {
+			++line;
+			break;
+		}
+
+		if (strncmp(line, "glob_no_path", 12) == 0) {
+			line += 12;
+			*do_glob = true;
+			*path_glob = false;
+		} else if (strncmp(line, "glob", 4) == 0) {
+			line += 4;
+			*do_glob = true;
+			*path_glob = true;
+		} else if (strncmp(line, "dont_fragment", 13) == 0) {
+			line += 13;
+			(*flags) |= SQFS_BLK_DONT_FRAGMENT;
+		} else if (strncmp(line, "align", 5) == 0) {
+			line += 5;
+			(*flags) |= SQFS_BLK_ALIGN;
+		} else if (strncmp(line, "dont_compress", 13) == 0) {
+			line += 13;
+			(*flags) |= SQFS_BLK_DONT_COMPRESS;
+		} else if (strncmp(line, "dont_deduplicate", 16) == 0) {
+			line += 16;
+			(*flags) |= SQFS_BLK_DONT_DEDUPLICATE;
+		} else if (strncmp(line, "nosparse", 8) == 0) {
+			line += 8;
+			(*flags) |= SQFS_BLK_IGNORE_SPARSE;
+		} else {
+			goto fail_flag;
+		}
+
+		while (isspace(*line))
+			++line;
+
+		if (*line == ']') {
+			++line;
+			break;
+		}
+
+		if (*(line++) != ',')
+			goto fail_sep;
+	}
+
+	if (!isspace(*line))
+		goto fail_fname;
+
+	while (isspace(*line))
+		++line;
+
+	memmove(start, line, strlen(line) + 1);
+	return 0;
+fail_fname:
+	fprintf(stderr, "%s: " PRI_SZ ": Expected `<space> <filename>` "
+		"after flag list.\n", filename, line_no);
+	return -1;
+fail_sep:
+	fprintf(stderr, "%s: " PRI_SZ ": Unexpected '%c' after flag.\n",
+		filename, line_no, *line);
+	return -1;
+fail_flag:
+	fprintf(stderr, "%s: " PRI_SZ ": Unknown flag `%.3s...`.\n",
+		filename, line_no, line);
+	return -1;
+}
+
+static void sort_file_list(fstree_t *fs)
+{
+	file_info_t *out = NULL, *out_last = NULL;
+
+	while (fs->files != NULL) {
+		sqfs_s64 lowest = fs->files->priority;
+		file_info_t *it, *prev;
+
+		for (it = fs->files; it != NULL; it = it->next) {
+			if (it->priority < lowest)
+				lowest = it->priority;
+		}
+
+		it = fs->files;
+		prev = NULL;
+
+		while (it != NULL) {
+			if (it->priority != lowest) {
+				prev = it;
+				it = it->next;
+				continue;
+			}
+
+			if (prev == NULL) {
+				fs->files = it->next;
+			} else {
+				prev->next = it->next;
+			}
+
+			if (out == NULL) {
+				out = it;
+			} else {
+				out_last->next = it;
+			}
+
+			out_last = it;
+			it = it->next;
+			out_last->next = NULL;
+		}
+	}
+
+	fs->files = out;
+}
+
+int fstree_sort_files(fstree_t *fs, istream_t *sortfile)
+{
+	const char *filename;
+	size_t line_num = 1;
+	file_info_t *it;
+
+	for (it = fs->files; it != NULL; it = it->next) {
+		it->priority = 0;
+		it->flags = 0;
+		it->already_matched = false;
+	}
+
+	filename = istream_get_filename(sortfile);
+
+	for (;;) {
+		bool do_glob, path_glob, have_match;
+		char *line = NULL;
+		sqfs_s64 priority;
+		int ret, flags;
+
+		ret = istream_get_line(sortfile, &line, &line_num,
+				       ISTREAM_LINE_LTRIM |
+				       ISTREAM_LINE_RTRIM |
+				       ISTREAM_LINE_SKIP_EMPTY);
+		if (ret != 0) {
+			free(line);
+			if (ret < 0)
+				return -1;
+			break;
+		}
+
+		if (line[0] == '#') {
+			free(line);
+			continue;
+		}
+
+		if (decode_priority(filename, line_num, line, &priority)) {
+			free(line);
+			return -1;
+		}
+
+		if (decode_flags(filename, line_num, &do_glob, &path_glob,
+				 &flags, line)) {
+			free(line);
+			return -1;
+		}
+
+		if (decode_filename(filename, line_num, line)) {
+			free(line);
+			return -1;
+		}
+
+		have_match = false;
+
+		for (it = fs->files; it != NULL; it = it->next) {
+			tree_node_t *node;
+			char *path;
+
+			if (it->already_matched)
+				continue;
+
+			node = container_of(it, tree_node_t, data.file);
+			path = fstree_get_path(node);
+			if (path == NULL) {
+				fprintf(stderr, "%s: " PRI_SZ ": out-of-memory\n",
+					filename, line_num);
+				free(line);
+				return -1;
+			}
+
+			if (canonicalize_name(path)) {
+				fprintf(stderr,
+					"%s: " PRI_SZ ": [BUG] error "
+					"reconstructing node path\n",
+					filename, line_num);
+				free(line);
+				free(path);
+				return -1;
+			}
+
+			if (do_glob) {
+				ret = fnmatch(line, path,
+					      path_glob ? FNM_PATHNAME : 0);
+
+			} else {
+				ret = strcmp(path, line);
+			}
+
+			free(path);
+
+			if (ret == 0) {
+				have_match = true;
+				it->flags = flags;
+				it->priority = priority;
+				it->already_matched = true;
+
+				if (!do_glob)
+					break;
+			}
+		}
+
+		if (!have_match) {
+			fprintf(stderr, "WARNING: %s: " PRI_SZ ": no match "
+				"for '%s'.\n",
+				filename, line_num, line);
+		}
+
+		free(line);
+	}
+
+	sort_file_list(fs);
+	return 0;
+}