Move library source into src sub-directory

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

7 files changed, 706 insertions, 0 deletions

diff --git a/lib/fstree/src/add_by_path.c b/lib/fstree/src/add_by_path.c
new file mode 100644
index 0000000..0afd898
--- /dev/null
+++ b/lib/fstree/src/add_by_path.c
@@ -0,0 +1,54 @@
+/* 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 <string.h>
+#include <assert.h>
+#include <errno.h>
+
+tree_node_t *fstree_add_generic(fstree_t *fs, const char *path,
+				const struct stat *sb, const char *extra)
+{
+	tree_node_t *child, *parent;
+	const char *name;
+
+	if (*path == '\0') {
+		child = fs->root;
+		assert(child != NULL);
+		goto out;
+	}
+
+	parent = fstree_get_node_by_path(fs, fs->root, path, true, true);
+	if (parent == NULL)
+		return NULL;
+
+	name = strrchr(path, '/');
+	name = (name == NULL ? path : (name + 1));
+
+	child = parent->data.dir.children;
+	while (child != NULL && strcmp(child->name, name) != 0)
+		child = child->next;
+out:
+	if (child != NULL) {
+		if (!S_ISDIR(child->mode) || !S_ISDIR(sb->st_mode) ||
+		    !child->data.dir.created_implicitly) {
+			errno = EEXIST;
+			return NULL;
+		}
+
+		child->uid = sb->st_uid;
+		child->gid = sb->st_gid;
+		child->mode = sb->st_mode;
+		child->mod_time = sb->st_mtime;
+		child->data.dir.created_implicitly = false;
+		return child;
+	}
+
+	return fstree_mknode(parent, name, strlen(name), extra, sb);
+}
diff --git a/lib/fstree/src/fstree.c b/lib/fstree/src/fstree.c
new file mode 100644
index 0000000..d44a8ae
--- /dev/null
+++ b/lib/fstree/src/fstree.c
@@ -0,0 +1,135 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * fstree.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "fstree.h"
+
+#include "util/util.h"
+
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+enum {
+	DEF_UID = 0,
+	DEF_GID,
+	DEF_MODE,
+	DEF_MTIME,
+};
+
+static const char *defaults[] = {
+	[DEF_UID] = "uid",
+	[DEF_GID] = "gid",
+	[DEF_MODE] = "mode",
+	[DEF_MTIME] = "mtime",
+	NULL
+};
+
+static int process_defaults(struct stat *sb, char *subopts)
+{
+	char *value;
+	long lval;
+	int i;
+
+	while (*subopts != '\0') {
+		i = getsubopt(&subopts, (char *const *)defaults, &value);
+
+		if (value == NULL) {
+			fprintf(stderr, "Missing value for option %s\n",
+				defaults[i]);
+			return -1;
+		}
+
+		switch (i) {
+		case DEF_UID:
+			lval = strtol(value, NULL, 0);
+			if (lval < 0)
+				goto fail_uv;
+			if (lval > (long)INT32_MAX)
+				goto fail_ov;
+			sb->st_uid = lval;
+			break;
+		case DEF_GID:
+			lval = strtol(value, NULL, 0);
+			if (lval < 0)
+				goto fail_uv;
+			if (lval > (long)INT32_MAX)
+				goto fail_ov;
+			sb->st_gid = lval;
+			break;
+		case DEF_MODE:
+			lval = strtol(value, NULL, 0);
+			if (lval < 0)
+				goto fail_uv;
+			if (lval > 07777)
+				goto fail_ov;
+			sb->st_mode = S_IFDIR | (sqfs_u16)lval;
+			break;
+		case DEF_MTIME:
+			lval = strtol(value, NULL, 0);
+			if (lval < 0)
+				goto fail_uv;
+			if (lval > (long)INT32_MAX)
+				goto fail_ov;
+			sb->st_mtime = lval;
+			break;
+		default:
+			fprintf(stderr, "Unknown option '%s'\n", value);
+			return -1;
+		}
+	}
+	return 0;
+fail_uv:
+	fprintf(stderr, "%s: value must be positive\n", defaults[i]);
+	return -1;
+fail_ov:
+	fprintf(stderr, "%s: value too large\n", defaults[i]);
+	return -1;
+}
+
+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);
+}
+
+int fstree_init(fstree_t *fs, char *defaults)
+{
+	memset(fs, 0, sizeof(*fs));
+	fs->defaults.st_mode = S_IFDIR | 0755;
+	fs->defaults.st_blksize = 512;
+	fs->defaults.st_mtime = get_source_date_epoch();
+
+	if (defaults != NULL && process_defaults(&fs->defaults, defaults) != 0)
+		return -1;
+
+	fs->root = fstree_mknode(NULL, "", 0, NULL, &fs->defaults);
+
+	if (fs->root == NULL) {
+		perror("initializing file system tree");
+		return -1;
+	}
+
+	fs->root->data.dir.created_implicitly = true;
+	return 0;
+}
+
+void fstree_cleanup(fstree_t *fs)
+{
+	free_recursive(fs->root);
+	free(fs->inodes);
+	memset(fs, 0, sizeof(*fs));
+}
diff --git a/lib/fstree/src/get_by_path.c b/lib/fstree/src/get_by_path.c
new file mode 100644
index 0000000..8742892
--- /dev/null
+++ b/lib/fstree/src/get_by_path.c
@@ -0,0 +1,76 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * get_by_path.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "fstree.h"
+
+#include <string.h>
+#include <errno.h>
+
+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;
+}
+
+tree_node_t *fstree_get_node_by_path(fstree_t *fs, tree_node_t *root,
+				     const char *path, bool create_implicitly,
+				     bool stop_at_parent)
+{
+	const char *end;
+	tree_node_t *n;
+	size_t len;
+
+	while (*path != '\0') {
+		while (*path == '/')
+			++path;
+
+		if (!S_ISDIR(root->mode)) {
+			errno = ENOTDIR;
+			return NULL;
+		}
+
+		end = strchr(path, '/');
+		if (end == NULL) {
+			if (stop_at_parent)
+				break;
+
+			len = strlen(path);
+		} else {
+			len = end - path;
+		}
+
+		n = child_by_name(root, path, len);
+
+		if (n == NULL) {
+			if (!create_implicitly) {
+				errno = ENOENT;
+				return NULL;
+			}
+
+			n = fstree_mknode(root, path, len, NULL, &fs->defaults);
+			if (n == NULL)
+				return NULL;
+
+			n->data.dir.created_implicitly = true;
+		}
+
+		root = n;
+		path = path + len;
+	}
+
+	return root;
+}
diff --git a/lib/fstree/src/get_path.c b/lib/fstree/src/get_path.c
new file mode 100644
index 0000000..decf92e
--- /dev/null
+++ b/lib/fstree/src/get_path.c
@@ -0,0 +1,43 @@
+/* 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 <string.h>
+#include <stdlib.h>
+
+char *fstree_get_path(tree_node_t *node)
+{
+	tree_node_t *it;
+	char *str, *ptr;
+	size_t len = 0;
+
+	if (node->parent == NULL)
+		return strdup("/");
+
+	for (it = node; it != NULL && it->parent != NULL; it = it->parent) {
+		len += strlen(it->name) + 1;
+	}
+
+	str = malloc(len + 1);
+	if (str == NULL)
+		return NULL;
+
+	ptr = str + len;
+	*ptr = '\0';
+
+	for (it = node; it != NULL && it->parent != NULL; it = it->parent) {
+		len = strlen(it->name);
+		ptr -= len;
+
+		memcpy(ptr, it->name, len);
+		*(--ptr) = '/';
+	}
+
+	return str;
+}
diff --git a/lib/fstree/src/hardlink.c b/lib/fstree/src/hardlink.c
new file mode 100644
index 0000000..2165b5f
--- /dev/null
+++ b/lib/fstree/src/hardlink.c
@@ -0,0 +1,76 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * hardlink.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/util.h"
+#include "fstree.h"
+
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+
+tree_node_t *fstree_add_hard_link(fstree_t *fs, const char *path,
+				  const char *target)
+{
+	struct stat sb;
+	tree_node_t *n;
+
+	memset(&sb, 0, sizeof(sb));
+	sb.st_mode = S_IFLNK | 0777;
+
+	n = fstree_add_generic(fs, path, &sb, target);
+	if (n != NULL) {
+		if (canonicalize_name(n->data.target)) {
+			free(n);
+			errno = EINVAL;
+			return NULL;
+		}
+
+		n->mode = FSTREE_MODE_HARD_LINK;
+	}
+
+	return n;
+}
+
+int fstree_resolve_hard_link(fstree_t *fs, tree_node_t *node)
+{
+	tree_node_t *start = node;
+
+	while (node->mode == FSTREE_MODE_HARD_LINK ||
+	       node->mode == FSTREE_MODE_HARD_LINK_RESOLVED) {
+		if (node->mode == FSTREE_MODE_HARD_LINK_RESOLVED) {
+			node = node->data.target_node;
+		} else {
+			node = fstree_get_node_by_path(fs, fs->root,
+						       node->data.target,
+						       false, false);
+			if (node == NULL)
+				return -1;
+		}
+
+		if (node == start) {
+			errno = EMLINK;
+			return -1;
+		}
+	}
+
+	if (S_ISDIR(node->mode)) {
+		errno = EPERM;
+		return -1;
+	}
+
+	if (node->link_count == 0xFFFFFFFF) {
+		errno = EMLINK;
+		return -1;
+	}
+
+	start->mode = FSTREE_MODE_HARD_LINK_RESOLVED;
+	start->data.target_node = node;
+
+	node->link_count++;
+	return 0;
+}
diff --git a/lib/fstree/src/mknode.c b/lib/fstree/src/mknode.c
new file mode 100644
index 0000000..2faf901
--- /dev/null
+++ b/lib/fstree/src/mknode.c
@@ -0,0 +1,101 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * mknode.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "fstree.h"
+
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+
+void fstree_insert_sorted(tree_node_t *root, tree_node_t *n)
+{
+	tree_node_t *it = root->data.dir.children, *prev = NULL;
+
+	while (it != NULL && strcmp(it->name, n->name) < 0) {
+		prev = it;
+		it = it->next;
+	}
+
+	n->parent = root;
+	n->next = it;
+
+	if (prev == NULL) {
+		root->data.dir.children = n;
+	} else {
+		prev->next = n;
+	}
+}
+
+tree_node_t *fstree_mknode(tree_node_t *parent, const char *name,
+			   size_t name_len, const char *extra,
+			   const struct stat *sb)
+{
+	tree_node_t *n;
+	size_t size;
+	char *ptr;
+
+	if (S_ISLNK(sb->st_mode) && extra == NULL) {
+		errno = EINVAL;
+		return NULL;
+	}
+
+	size = sizeof(tree_node_t) + name_len + 1;
+	if (extra != NULL)
+		size += strlen(extra) + 1;
+
+	n = calloc(1, size);
+	if (n == NULL)
+		return NULL;
+
+	n->xattr_idx = 0xFFFFFFFF;
+	n->uid = sb->st_uid;
+	n->gid = sb->st_gid;
+	n->mode = sb->st_mode;
+	n->mod_time = sb->st_mtime;
+	n->link_count = 1;
+	n->name = (char *)n->payload;
+	memcpy(n->name, name, name_len);
+
+	if (extra != NULL) {
+		ptr = n->name + name_len + 1;
+		strcpy(ptr, extra);
+	} else {
+		ptr = NULL;
+	}
+
+	switch (sb->st_mode & S_IFMT) {
+	case S_IFREG:
+		n->data.file.input_file = ptr;
+		break;
+	case S_IFLNK:
+		n->mode = S_IFLNK | 0777;
+		n->data.target = ptr;
+		break;
+	case S_IFBLK:
+	case S_IFCHR:
+		n->data.devno = sb->st_rdev;
+		break;
+	case S_IFDIR:
+		n->link_count = 2;
+		break;
+	default:
+		break;
+	}
+
+	if (parent != NULL) {
+		if (parent->link_count == 0xFFFFFFFF) {
+			free(n);
+			errno = EMLINK;
+			return NULL;
+		}
+
+		fstree_insert_sorted(parent, n);
+		parent->link_count++;
+	}
+
+	return n;
+}
diff --git a/lib/fstree/src/post_process.c b/lib/fstree/src/post_process.c
new file mode 100644
index 0000000..088916b
--- /dev/null
+++ b/lib/fstree/src/post_process.c
@@ -0,0 +1,221 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * post_process.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "fstree.h"
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <stdio.h>
+#include <errno.h>
+
+static int alloc_inode_num_dfs(fstree_t *fs, tree_node_t *root)
+{
+	bool has_subdirs = false;
+	tree_node_t *it;
+	size_t inum;
+
+	for (it = root->data.dir.children; it != NULL; it = it->next) {
+		if (S_ISDIR(it->mode)) {
+			has_subdirs = true;
+			break;
+		}
+	}
+
+	if (has_subdirs) {
+		for (it = root->data.dir.children; it != NULL; it = it->next) {
+			if (S_ISDIR(it->mode)) {
+				if (alloc_inode_num_dfs(fs, it))
+					return -1;
+			}
+		}
+	}
+
+	for (it = root->data.dir.children; it != NULL; it = it->next) {
+		if (it->mode != FSTREE_MODE_HARD_LINK_RESOLVED) {
+			if (SZ_ADD_OV(fs->unique_inode_count, 1, &inum))
+				goto fail_ov;
+
+			if ((sizeof(size_t) > sizeof(sqfs_u32)) &&
+			    inum > 0x0FFFFFFFFUL) {
+				goto fail_ov;
+			}
+
+			it->inode_num = (sqfs_u32)inum;
+			fs->unique_inode_count = inum;
+		}
+	}
+
+	return 0;
+fail_ov:
+	fputs("Too many inodes.\n", stderr);
+	return -1;
+}
+
+static int resolve_hard_links_dfs(fstree_t *fs, tree_node_t *n)
+{
+	tree_node_t *it;
+
+	if (n->mode == FSTREE_MODE_HARD_LINK) {
+		if (fstree_resolve_hard_link(fs, n))
+			goto fail_link;
+
+		assert(n->mode == FSTREE_MODE_HARD_LINK_RESOLVED);
+		it = n->data.target_node;
+
+		if (S_ISDIR(it->mode) && it->data.dir.visited)
+			goto fail_link_loop;
+	} else if (S_ISDIR(n->mode)) {
+		n->data.dir.visited = true;
+
+		for (it = n->data.dir.children; it != NULL; it = it->next) {
+			if (resolve_hard_links_dfs(fs, it))
+				return -1;
+		}
+
+		n->data.dir.visited = false;
+	}
+
+	return 0;
+fail_link: {
+	char *path = fstree_get_path(n);
+	fprintf(stderr, "Resolving hard link '%s' -> '%s': %s\n",
+		path == NULL ? n->name : path, n->data.target,
+		strerror(errno));
+	free(path);
+}
+	return -1;
+fail_link_loop: {
+	char *npath = fstree_get_path(n);
+	char *tpath = fstree_get_path(it);
+	fprintf(stderr, "Hard link loop detected in '%s' -> '%s'\n",
+		npath == NULL ? n->name : npath,
+		tpath == NULL ? it->name : tpath);
+	free(npath);
+	free(tpath);
+}
+	return -1;
+}
+
+static file_info_t *file_list_dfs(tree_node_t *n)
+{
+	if (S_ISREG(n->mode)) {
+		n->data.file.next = NULL;
+		return &n->data.file;
+	}
+
+	if (S_ISDIR(n->mode)) {
+		file_info_t *list = NULL, *last = NULL;
+
+		for (n = n->data.dir.children; n != NULL; n = n->next) {
+			if (list == NULL) {
+				list = file_list_dfs(n);
+				if (list == NULL)
+					continue;
+				last = list;
+			} else {
+				last->next = file_list_dfs(n);
+			}
+
+			while (last->next != NULL)
+				last = last->next;
+		}
+
+		return list;
+	}
+
+	return NULL;
+}
+
+static void map_inodes_dfs(fstree_t *fs, tree_node_t *n)
+{
+	if (n->mode == FSTREE_MODE_HARD_LINK_RESOLVED)
+		return;
+
+	fs->inodes[n->inode_num - 1] = n;
+
+	if (S_ISDIR(n->mode)) {
+		for (n = n->data.dir.children; n != NULL; n = n->next)
+			map_inodes_dfs(fs, n);
+	}
+}
+
+static void reorder_hard_links(fstree_t *fs)
+{
+	size_t i, j, tgt_idx;
+	tree_node_t *it, *tgt;
+
+	for (i = 0; i < fs->unique_inode_count; ++i) {
+		if (!S_ISDIR(fs->inodes[i]->mode))
+			continue;
+
+		it = fs->inodes[i]->data.dir.children;
+
+		for (; it != NULL; it = it->next) {
+			if (it->mode != FSTREE_MODE_HARD_LINK_RESOLVED)
+				continue;
+
+			tgt = it->data.target_node;
+			tgt_idx = tgt->inode_num - 1;
+
+			if (tgt_idx <= i)
+				continue;
+
+			/* TODO ? */
+			assert(!S_ISDIR(tgt->mode));
+
+			for (j = tgt_idx; j > i; --j) {
+				fs->inodes[j] = fs->inodes[j - 1];
+				fs->inodes[j]->inode_num += 1;
+			}
+
+			fs->inodes[i] = tgt;
+
+			/* XXX: the possible overflow is checked for
+			   during allocation */
+			tgt->inode_num = (sqfs_u32)(i + 1);
+			++i;
+		}
+	}
+}
+
+int fstree_post_process(fstree_t *fs)
+{
+	size_t inum;
+
+	if (resolve_hard_links_dfs(fs, fs->root))
+		return -1;
+
+	fs->unique_inode_count = 0;
+
+	if (alloc_inode_num_dfs(fs, fs->root))
+		return -1;
+
+	if (SZ_ADD_OV(fs->unique_inode_count, 1, &inum))
+		goto fail_root_ov;
+
+	if ((sizeof(size_t) > sizeof(sqfs_u32)) && inum > 0x0FFFFFFFFUL)
+		goto fail_root_ov;
+
+	fs->root->inode_num = (sqfs_u32)inum;
+	fs->unique_inode_count = inum;
+
+	fs->inodes = calloc(sizeof(fs->inodes[0]), fs->unique_inode_count);
+	if (fs->inodes == NULL) {
+		perror("Allocating inode list");
+		return -1;
+	}
+
+	map_inodes_dfs(fs, fs->root);
+	reorder_hard_links(fs);
+
+	fs->files = file_list_dfs(fs->root);
+	return 0;
+fail_root_ov:
+	fputs("Too many inodes, cannot allocate number for root.\n", stderr);
+	return -1;
+}