Initial commit

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

4 files changed, 717 insertions, 0 deletions

diff --git a/lib/Makemodule.am b/lib/Makemodule.am
new file mode 100644
index 0000000..18ec8c4
--- /dev/null
+++ b/lib/Makemodule.am
@@ -0,0 +1,5 @@
+libfstree_a_SOURCES = lib/fstree/fstree.c lib/fstree/fstree_from_file.c
+libfstree_a_SOURCES += lib/fstree/fstree_sort.c
+libfstree_a_SOURCES += include/fstree.h
+
+noinst_LIBRARIES += libfstree.a
diff --git a/lib/fstree/fstree.c b/lib/fstree/fstree.c
new file mode 100644
index 0000000..2722b4a
--- /dev/null
+++ b/lib/fstree/fstree.c
@@ -0,0 +1,200 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#include "fstree.h"
+
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <errno.h>
+
+static tree_node_t *mknode(tree_node_t *parent, const char *name,
+			   size_t name_len, size_t extra_len,
+			   uint16_t mode, uint32_t uid, uint32_t gid)
+{
+	size_t size = sizeof(tree_node_t) + extra_len;
+	tree_node_t *n;
+
+	switch (mode & S_IFMT) {
+	case S_IFDIR:
+		size += sizeof(*n->data.dir);
+		break;
+	case S_IFREG:
+		size += sizeof(*n->data.file);
+		break;
+	}
+
+	n = calloc(1, size + name_len + 1);
+	if (n == NULL)
+		return NULL;
+
+	if (parent != NULL) {
+		n->next = parent->data.dir->children;
+		parent->data.dir->children = n;
+	}
+
+	n->uid = uid;
+	n->gid = gid;
+	n->mode = mode;
+
+	switch (mode & S_IFMT) {
+	case S_IFDIR:
+		n->data.dir = (dir_info_t *)n->payload;
+		break;
+	case S_IFREG:
+		n->data.file = (file_info_t *)n->payload;
+		break;
+	case S_IFLNK:
+		n->data.slink_target = (char *)n->payload;
+		break;
+	}
+
+	n->name = (char *)n + size;
+	memcpy(n->name, name, name_len);
+	return n;
+}
+
+static void free_recursive(tree_node_t *n)
+{
+	tree_node_t *it;
+
+	if (S_ISDIR(n->mode)) {
+		while (n->data.dir->children != NULL) {
+			it = n->data.dir->children;
+			n->data.dir->children = it->next;
+
+			free_recursive(it);
+		}
+	}
+
+	free(n);
+}
+
+static tree_node_t *child_by_name(tree_node_t *root, const char *name,
+				  size_t len)
+{
+	tree_node_t *n = root->data.dir->children;
+
+	while (n != NULL) {
+		if (strncmp(n->name, name, len) == 0 && n->name[len] == '\0')
+			break;
+
+		n = n->next;
+	}
+
+	return n;
+}
+
+static tree_node_t *get_parent_node(fstree_t *fs, tree_node_t *root,
+				    const char *path)
+{
+	const char *end;
+	tree_node_t *n;
+
+	for (;;) {
+		if (!S_ISDIR(root->mode)) {
+			errno = ENOTDIR;
+			return NULL;
+		}
+
+		end = strchr(path, '/');
+		if (end == NULL)
+			break;
+
+		n = child_by_name(root, path, end - path);
+
+		if (n == NULL) {
+			n = mknode(root, path, end - path, 0,
+				   S_IFDIR | fs->default_mode,
+				   fs->default_uid, fs->default_gid);
+			if (n == NULL)
+				return NULL;
+
+			n->data.dir->created_implicitly = true;
+		}
+
+		root = n;
+		path = end + 1;
+	}
+
+	return root;
+}
+
+tree_node_t *fstree_add(fstree_t *fs, const char *path, uint16_t mode,
+			uint32_t uid, uint32_t gid, size_t extra_len)
+{
+	tree_node_t *child, *parent;
+	const char *name;
+
+	name = strrchr(path, '/');
+	name = (name == NULL ? path : (name + 1));
+
+	parent = get_parent_node(fs, fs->root, path);
+	if (parent == NULL)
+		return NULL;
+
+	child = child_by_name(parent, name, strlen(name));
+	if (child != NULL) {
+		if (S_ISDIR(child->mode) && S_ISDIR(mode) &&
+		    child->data.dir->created_implicitly) {
+			child->data.dir->created_implicitly = false;
+			return child;
+		}
+
+		errno = EEXIST;
+		return NULL;
+	}
+
+	return mknode(parent, name, strlen(name), extra_len, mode, uid, gid);
+}
+
+tree_node_t *fstree_add_file(fstree_t *fs, const char *path, uint16_t mode,
+			     uint32_t uid, uint32_t gid, uint64_t filesz,
+			     const char *input)
+{
+	tree_node_t *node;
+	size_t count, extra;
+	char *ptr;
+
+	count = filesz / fs->block_size;
+	extra = sizeof(uint32_t) * count + strlen(input) + 1;
+
+	mode &= 07777;
+	node = fstree_add(fs, path, S_IFREG | mode, uid, gid, extra);
+
+	if (node != NULL) {
+		ptr = (char *)(node->data.file->blocksizes + count);
+		strcpy(ptr, input);
+
+		node->data.file->input_file = ptr;
+		node->data.file->size = filesz;
+	}
+	return node;
+}
+
+int fstree_init(fstree_t *fs, size_t block_size, uint32_t mtime,
+		uint16_t default_mode, uint32_t default_uid,
+		uint32_t default_gid)
+{
+	memset(fs, 0, sizeof(*fs));
+
+	fs->default_uid = default_uid;
+	fs->default_gid = default_gid;
+	fs->default_mode = default_mode & 07777;
+	fs->default_mtime = mtime;
+	fs->block_size = block_size;
+
+	fs->root = mknode(NULL, "", 0, 0, S_IFDIR | fs->default_mode,
+			  default_uid, default_gid);
+
+	if (fs->root == NULL) {
+		perror("initializing file system tree");
+		return -1;
+	}
+
+	return 0;
+}
+
+void fstree_cleanup(fstree_t *fs)
+{
+	free_recursive(fs->root);
+	memset(fs, 0, sizeof(*fs));
+}
diff --git a/lib/fstree/fstree_from_file.c b/lib/fstree/fstree_from_file.c
new file mode 100644
index 0000000..66d71a2
--- /dev/null
+++ b/lib/fstree/fstree_from_file.c
@@ -0,0 +1,436 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#include "fstree.h"
+
+#include <sys/sysmacros.h>
+#include <sys/types.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <stdio.h>
+#include <ctype.h>
+#include <errno.h>
+
+static int add_dir(fstree_t *fs, const char *filename, size_t line_num,
+		   const char *path, uint16_t mode, uint32_t uid,
+		   uint32_t gid, const char *extra)
+{
+	if (extra != NULL && *extra != '\0') {
+		fprintf(stderr, "%s: %zu: WARNING: ignoring extra arguments\n",
+			filename, line_num);
+	}
+
+	if (fstree_add(fs, path, S_IFDIR | mode, uid, gid, 0) == NULL) {
+		fprintf(stderr, "%s: %zu: mkdir -p %s: %s\n",
+			filename, line_num, path, strerror(errno));
+		return -1;
+	}
+
+	return 0;
+}
+
+static int add_slink(fstree_t *fs, const char *filename, size_t line_num,
+		     const char *path, uint16_t mode, uint32_t uid,
+		     uint32_t gid, const char *extra)
+{
+	tree_node_t *node;
+	(void)mode;
+
+	if (extra == NULL || *extra == '\0') {
+		fprintf(stderr, "%s: %zu: missing symlink target\n",
+			filename, line_num);
+		return -1;
+	}
+
+	node = fstree_add(fs, path, S_IFLNK | 0777, uid, gid,
+			  strlen(extra) + 1);
+
+	if (node == NULL) {
+		fprintf(stderr, "%s: %zu: ln -s %s %s\n",
+			filename, line_num, extra, path);
+		return -1;
+	}
+
+	strcpy(node->data.slink_target, extra);
+	return 0;
+}
+
+static int add_device(fstree_t *fs, const char *filename, size_t line_num,
+		      const char *path, uint16_t mode, uint32_t uid,
+		      uint32_t gid, const char *extra)
+{
+	unsigned int maj = 0, min = 0;
+	tree_node_t *node;
+
+	if (extra == NULL || *extra == '\0') {
+		fprintf(stderr, "%s: %zu: missing device type\n",
+			filename, line_num);
+		return -1;
+	}
+
+	if ((*extra == 'c' || *extra == 'C') && isspace(extra[1])) {
+		mode |= S_IFCHR;
+	} else if ((*extra == 'b' || *extra == 'B') && isspace(extra[1])) {
+		mode |= S_IFBLK;
+	} else {
+		fprintf(stderr, "%s: %zu: unsupported device type",
+			filename, line_num);
+		return -1;
+	}
+
+	++extra;
+	while (isspace(*extra))
+		++extra;
+
+	if (!isdigit(*extra))
+		goto fail_devno;
+
+	while (isdigit(*extra))
+		maj = maj * 10 + *(extra++) - '0';
+
+	if (*(extra++) != ':')
+		goto fail_devno;
+
+	if (!isdigit(*extra))
+		goto fail_devno;
+
+	while (isdigit(*extra))
+		min = min * 10 + *(extra++) - '0';
+
+	while (isspace(*extra))
+		++extra;
+
+	if (*extra != '\0') {
+		fprintf(stderr, "%s: %zu: WARNING: ignoring extra arguments\n",
+			filename, line_num);
+	}
+
+	node = fstree_add(fs, path, mode, uid, gid, 0);
+	if (node == NULL) {
+		fprintf(stderr, "%s: %zu: mknod %s %c %u %u: %s\n",
+			filename, line_num, path, S_ISCHR(mode) ? 'c' : 'b',
+			maj, min, strerror(errno));
+		return -1;
+	}
+
+	node->data.devno = makedev(maj, min);
+	return 0;
+fail_devno:
+	fprintf(stderr, "%s: %zu: error in device number format\n",
+		filename, line_num);
+	return -1;
+}
+
+static int add_pipe(fstree_t *fs, const char *filename, size_t line_num,
+		    const char *path, uint16_t mode, uint32_t uid,
+		    uint32_t gid, const char *extra)
+{
+	if (extra != NULL && *extra != '\0') {
+		fprintf(stderr, "%s: %zu: WARNING: ignoring extra arguments\n",
+			filename, line_num);
+	}
+
+	if (fstree_add(fs, path, S_IFIFO | mode, uid, gid, 0) == NULL) {
+		fprintf(stderr, "%s: %zu: mkfifo %s: %s\n",
+			filename, line_num, path, strerror(errno));
+		return -1;
+	}
+
+	return 0;
+}
+
+static int add_socket(fstree_t *fs, const char *filename, size_t line_num,
+		      const char *path, uint16_t mode, uint32_t uid,
+		      uint32_t gid, const char *extra)
+{
+	if (extra != NULL && *extra != '\0') {
+		fprintf(stderr, "%s: %zu: WARNING: ignoring extra arguments\n",
+			filename, line_num);
+	}
+
+	if (fstree_add(fs, path, S_IFSOCK | mode, uid, gid, 0) == NULL) {
+		fprintf(stderr, "%s: %zu: creating Unix socket %s: %s\n",
+			filename, line_num, path, strerror(errno));
+		return -1;
+	}
+
+	return 0;
+}
+
+static int add_file(fstree_t *fs, const char *filename, size_t line_num,
+		    const char *path, uint16_t mode, uint32_t uid,
+		    uint32_t gid, const char *extra)
+{
+	char *infile = NULL;
+	tree_node_t *node;
+	const char *ptr;
+	struct stat sb;
+	int ret;
+
+	ptr = strrchr(filename, '/');
+
+	if (extra == NULL || *extra == '\0') {
+		if (ptr == NULL) {
+			extra = path;
+		} else {
+			ret = asprintf(&infile, "%.*s/%s",
+				       (int)(filename - ptr), filename, path);
+			if (ret < 0)
+				goto fail_asprintf;
+		}
+	} else if (*extra != '/' && ptr != NULL) {
+		ret = asprintf(&infile, "%.*s/%s",
+			       (int)(filename - ptr), filename, extra);
+		if (ret < 0)
+			goto fail_asprintf;
+	}
+
+	if (infile != NULL)
+		extra = infile;
+
+	if (stat(extra, &sb) != 0) {
+		fprintf(stderr, "%s: %zu: stat %s: %s\n", filename, line_num,
+			extra, strerror(errno));
+		goto fail;
+	}
+
+	node = fstree_add_file(fs, path, mode, uid, gid, sb.st_size, extra);
+
+	if (node == NULL) {
+		fprintf(stderr, "%s: %zu: adding %s as %s: %s\n",
+			filename, line_num, extra, path, strerror(errno));
+		goto fail;
+	}
+
+	free(infile);
+	return 0;
+fail:
+	free(infile);
+	return -1;
+fail_asprintf:
+	fprintf(stderr, "%s: %zu: pasting together file path: %s\n",
+		filename, line_num, strerror(errno));
+	return -1;
+}
+
+static const struct {
+	const char *keyword;
+	int (*callback)(fstree_t *fs, const char *filename, size_t line_num,
+			const char *path, uint16_t mode, uint32_t uid,
+			uint32_t gid, const char *extra);
+} file_list_hooks[] = {
+	{ "dir", add_dir },
+	{ "slink", add_slink },
+	{ "nod", add_device },
+	{ "pipe", add_pipe },
+	{ "pipe", add_socket },
+	{ "file", add_file },
+};
+
+#define NUM_HOOKS (sizeof(file_list_hooks) / sizeof(file_list_hooks[0]))
+
+static void trim_line(char *line)
+{
+	size_t i;
+
+	for (i = 0; isspace(line[i]); ++i)
+		;
+
+	if (line[i] == '#') {
+		line[0] = '\0';
+		return;
+	}
+
+	if (i > 0)
+		memmove(line, line + i, strlen(line + i) + 1);
+
+	i = strlen(line);
+	while (i > 0 && isspace(line[i - 1]))
+		--i;
+
+	line[i] = '\0';
+}
+
+static int handle_line(fstree_t *fs, const char *filename,
+		       size_t line_num, char *line)
+{
+	const char *path, *extra = NULL, *msg = NULL;
+	unsigned int mode = 0, uid = 0, gid = 0, x;
+	char keyword[16];
+	size_t i;
+
+	/* isolate keyword */
+	for (i = 0; isalpha(line[i]); ++i)
+		;
+
+	if (i >= sizeof(keyword) || i == 0 || !isspace(line[i]))
+		goto fail_ent;
+
+	memcpy(keyword, line, i);
+	keyword[i] = '\0';
+
+	while (isspace(line[i]))
+		++i;
+
+	/* isolate path */
+	path = line + i;
+
+	for (; line[i] != '\0'; ++i) {
+		/* TODO: escape sequences to support spaces in path */
+
+		if (isspace(line[i]))
+			break;
+	}
+
+	if (!isspace(line[i]))
+		goto fail_ent;
+
+	line[i++] = '\0';
+	while (isspace(line[i]))
+		++i;
+
+	/* mode */
+	if (!isdigit(line[i]))
+		goto fail_mode;
+
+	for (; isdigit(line[i]); ++i) {
+		if (line[i] > '7')
+			goto fail_mode;
+
+		mode = (mode << 3) | (line[i] - '0');
+
+		if (mode > 07777)
+			goto fail_mode_bits;
+	}
+
+	if (!isspace(line[i]))
+		goto fail_ent;
+
+	while (isspace(line[i]))
+		++i;
+
+	/* uid */
+	if (!isdigit(line[i]))
+		goto fail_uid_gid;
+
+	for (; isdigit(line[i]); ++i) {
+		x = line[i] - '0';
+
+		if (uid > (0xFFFFFFFF - x) / 10)
+			goto fail_ov;
+
+		uid = uid * 10 + x;
+	}
+
+	if (!isspace(line[i]))
+		goto fail_ent;
+
+	while (isspace(line[i]))
+		++i;
+
+	/* gid */
+	if (!isdigit(line[i]))
+		goto fail_uid_gid;
+
+	for (; isdigit(line[i]); ++i) {
+		x = line[i] - '0';
+
+		if (gid > (0xFFFFFFFF - x) / 10)
+			goto fail_ov;
+
+		gid = gid * 10 + x;
+	}
+
+	/* extra */
+	if (isspace(line[i])) {
+		while (isspace(line[i]))
+			++i;
+
+		if (line[i] != '\0')
+			extra = line + i;
+	}
+
+	/* forward to callback */
+	for (i = 0; i < NUM_HOOKS; ++i) {
+		if (strcmp(file_list_hooks[i].keyword, keyword) == 0) {
+			return file_list_hooks[i].callback(fs, filename,
+							   line_num, path,
+							   mode, uid, gid,
+							   extra);
+		}
+	}
+
+	fprintf(stderr, "%s: %zu: unknown entry type '%s'.\n", filename,
+		line_num, keyword);
+	return -1;
+fail_ov:
+	msg = "numeric overflow";
+	goto fail_ent;
+fail_uid_gid:
+	msg = "uid & gid must be decimal numbers";
+	goto out_desc;
+fail_mode:
+	msg = "mode must be an octal number";
+	goto out_desc;
+fail_mode_bits:
+	msg = "you can only set the permission bits in the mode";
+	goto out_desc;
+fail_ent:
+	msg = "error in entry description";
+	goto out_desc;
+out_desc:
+	fprintf(stderr, "%s: %zu: %s.\n", filename, line_num, msg);
+	fputs("expected: <type> <path> <mode> <uid> <gid> [<extra>]\n",
+	      stderr);
+	return -1;
+}
+
+int fstree_from_file(fstree_t *fs, const char *filename)
+{
+	FILE *fp = fopen(filename, "rb");
+	size_t n, line_num = 0;
+	ssize_t ret;
+	char *line;
+
+	if (fp == NULL) {
+		perror(filename);
+		return -1;
+	}
+
+	for (;;) {
+		line = NULL;
+		n = 0;
+		errno = 0;
+
+		ret = getline(&line, &n, fp);
+		++line_num;
+
+		if (ret < 0) {
+			if (errno == 0) {
+				free(line);
+				break;
+			}
+
+			perror(filename);
+			goto fail_line;
+		}
+
+		trim_line(line);
+
+		if (line[0] == '\0') {
+			free(line);
+			continue;
+		}
+
+		if (handle_line(fs, filename, line_num, line))
+			goto fail_line;
+
+		free(line);
+	}
+
+	fclose(fp);
+	return 0;
+fail_line:
+	free(line);
+	fclose(fp);
+	return -1;
+}
diff --git a/lib/fstree/fstree_sort.c b/lib/fstree/fstree_sort.c
new file mode 100644
index 0000000..9f07c92
--- /dev/null
+++ b/lib/fstree/fstree_sort.c
@@ -0,0 +1,76 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#include "fstree.h"
+
+#include <string.h>
+
+static tree_node_t *sort_list(tree_node_t *head)
+{
+	tree_node_t *it, *prev, *lhs, *rhs;
+	size_t i, count = 0;
+
+	for (it = head; it != NULL; it = it->next)
+		++count;
+
+	if (count < 2)
+		return head;
+
+	prev = NULL;
+	it = head;
+
+	for (i = 0; i < count / 2; ++i) {
+		prev = it;
+		it = it->next;
+	}
+
+	prev->next = NULL;
+
+	lhs = sort_list(head);
+	rhs = sort_list(it);
+
+	head = NULL;
+	prev = NULL;
+
+	while (lhs != NULL && rhs != NULL) {
+		if (strcmp(lhs->name, rhs->name) <= 0) {
+			it = lhs;
+			lhs = lhs->next;
+		} else {
+			it = rhs;
+			rhs = rhs->next;
+		}
+
+		it->next = NULL;
+
+		if (prev != NULL) {
+			prev->next = it;
+			prev = it;
+		} else {
+			prev = head = it;
+		}
+	}
+
+	it = (lhs != NULL ? lhs : rhs);
+
+	if (prev != NULL) {
+		prev->next = it;
+	} else {
+		head = it;
+	}
+
+	return head;
+}
+
+static void sort_directory(tree_node_t *n)
+{
+	n->data.dir->children = sort_list(n->data.dir->children);
+
+	for (n = n->data.dir->children; n != NULL; n = n->next) {
+		if (S_ISDIR(n->mode))
+			sort_directory(n);
+	}
+}
+
+void fstree_sort(fstree_t *fs)
+{
+	sort_directory(fs->root);
+}