4 files changed, 191 insertions, 16 deletions

diff --git a/lib/common/serialize_fstree.c b/lib/common/serialize_fstree.c
index 73f4e67..a5f5d71 100644
--- a/lib/common/serialize_fstree.c
+++ b/lib/common/serialize_fstree.c
@@ -64,7 +64,7 @@ static sqfs_inode_generic_t *write_dir_entries(const char *filename,
 {
 	sqfs_u32 xattr, parent_inode;
 	sqfs_inode_generic_t *inode;
-	tree_node_t *it;
+	tree_node_t *it, *tgt;
 	int ret;
 
 	ret = sqfs_dir_writer_begin(dirw, 0);
@@ -72,8 +72,14 @@ static sqfs_inode_generic_t *write_dir_entries(const char *filename,
 		goto fail;
 
 	for (it = node->data.dir.children; it != NULL; it = it->next) {
-		ret = sqfs_dir_writer_add_entry(dirw, it->name, it->inode_num,
-						it->inode_ref, it->mode);
+		if (it->mode == FSTREE_MODE_HARD_LINK_RESOLVED) {
+			tgt = it->data.target_node;
+		} else {
+			tgt = it;
+		}
+
+		ret = sqfs_dir_writer_add_entry(dirw, it->name, tgt->inode_num,
+						tgt->inode_ref, tgt->mode);
 		if (ret)
 			goto fail;
 	}
@@ -111,6 +117,9 @@ static int serialize_tree_node(const char *filename, sqfs_writer_t *wr,
 	sqfs_u64 block;
 	int ret;
 
+	if (n->mode == FSTREE_MODE_HARD_LINK_RESOLVED)
+		return 0;
+
 	if (S_ISDIR(n->mode)) {
 		inode = write_dir_entries(filename, wr->dirwr, n);
 		ret = SQFS_ERROR_INTERNAL;
diff --git a/lib/fstree/Makemodule.am b/lib/fstree/Makemodule.am
index 751d7dc..56394a6 100644
--- a/lib/fstree/Makemodule.am
+++ b/lib/fstree/Makemodule.am
@@ -1,5 +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 += lib/fstree/fstree_sort.c lib/fstree/hardlink.c
 libfstree_a_SOURCES += lib/fstree/post_process.c lib/fstree/get_path.c
 libfstree_a_SOURCES += lib/fstree/mknode.c
 libfstree_a_SOURCES += lib/fstree/add_by_path.c lib/fstree/get_by_path.c
diff --git a/lib/fstree/hardlink.c b/lib/fstree/hardlink.c
new file mode 100644
index 0000000..8a79d46
--- /dev/null
+++ b/lib/fstree/hardlink.c
@@ -0,0 +1,65 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * hardlink.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.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;
+		}
+	}
+
+	start->mode = FSTREE_MODE_HARD_LINK_RESOLVED;
+	start->data.target_node = node;
+
+	node->link_count += 1;
+	return 0;
+}
diff --git a/lib/fstree/post_process.c b/lib/fstree/post_process.c
index ea52e4f..e6bcb3f 100644
--- a/lib/fstree/post_process.c
+++ b/lib/fstree/post_process.c
@@ -7,33 +7,129 @@
 #include "internal.h"
 
 #include <stdlib.h>
+#include <string.h>
+#include <assert.h>
 #include <stdio.h>
+#include <errno.h>
 
-static void map_child_nodes(fstree_t *fs, tree_node_t *root, size_t *counter)
+static void swap_link_with_target(tree_node_t *node)
+{
+	tree_node_t *tgt, *it;
+
+	tgt = node->data.target_node;
+
+	node->xattr_idx = tgt->xattr_idx;
+	node->uid = tgt->uid;
+	node->gid = tgt->gid;
+	node->inode_num = tgt->inode_num;
+	node->mod_time = tgt->mod_time;
+	node->mode = tgt->mode;
+	node->link_count = tgt->link_count;
+	node->inode_ref = tgt->inode_ref;
+
+	/* FIXME: data pointers now point to foreign node! */
+	node->data = tgt->data;
+
+	tgt->mode = FSTREE_MODE_HARD_LINK_RESOLVED;
+	tgt->data.target_node = node;
+
+	if (S_ISDIR(node->mode)) {
+		for (it = node->data.dir.children; it != NULL; it = it->next)
+			it->parent = node;
+	}
+}
+
+static void hard_link_snap(tree_node_t *n)
+{
+	/* XXX: the hard-link-vs-target swap may create hard links
+	   pointing to hard links, making this necessary */
+	while (n->data.target_node->mode == FSTREE_MODE_HARD_LINK_RESOLVED)
+		n->data.target_node = n->data.target_node->data.target_node;
+}
+
+static int map_child_nodes(fstree_t *fs, tree_node_t *root, size_t *counter)
 {
 	bool has_subdirs = false;
-	tree_node_t *it;
+	tree_node_t *it, *tgt;
 
 	for (it = root->data.dir.children; it != NULL; it = it->next) {
-		if (S_ISDIR(it->mode)) {
-			has_subdirs = true;
-			break;
+		if (it->mode == FSTREE_MODE_HARD_LINK_RESOLVED) {
+			hard_link_snap(it);
+			tgt = it->data.target_node;
+
+			if (tgt->inode_num == 0 && tgt->parent != root)
+				swap_link_with_target(it);
 		}
+
+		if (S_ISDIR(it->mode))
+			has_subdirs = true;
 	}
 
 	if (has_subdirs) {
 		for (it = root->data.dir.children; it != NULL; it = it->next) {
-			if (S_ISDIR(it->mode))
-				map_child_nodes(fs, it, counter);
+			if (S_ISDIR(it->mode)) {
+				if (map_child_nodes(fs, it, counter))
+					return -1;
+			}
 		}
 	}
 
 	for (it = root->data.dir.children; it != NULL; it = it->next) {
-		fs->unique_inode_count += 1;
+		if (it->mode == FSTREE_MODE_HARD_LINK_RESOLVED) {
+			hard_link_snap(it);
+		} else {
+			fs->unique_inode_count += 1;
 
-		it->inode_num = *counter;
-		*counter += 1;
+			it->inode_num = *counter;
+			*counter += 1;
+		}
 	}
+	return 0;
+}
+
+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 void sort_recursive(tree_node_t *n)
@@ -76,16 +172,21 @@ static file_info_t *file_list_dfs(tree_node_t *n)
 	return NULL;
 }
 
-void fstree_post_process(fstree_t *fs)
+int fstree_post_process(fstree_t *fs)
 {
 	size_t inum = 1;
 
 	sort_recursive(fs->root);
 
+	if (resolve_hard_links_dfs(fs, fs->root))
+		return -1;
+
 	fs->unique_inode_count = 0;
-	map_child_nodes(fs, fs->root, &inum);
+	if (map_child_nodes(fs, fs->root, &inum))
+		return -1;
 	fs->root->inode_num = inum;
 	fs->unique_inode_count += 1;
 
 	fs->files = file_list_dfs(fs->root);
+	return 0;
 }