Add basic support for handling and serializing hard links

In libfstree, add a function to add a hard link to the fstree. The
hard links stores the target in the data.target field, canonicalizes
the target and sets a sentinel mode. A second function is used to
resolve link, i.e. replacing it with a direct pointer, setting another
sentinel mode and increasing the targets link count.

The post process function tries to resolve unresolved hard links and
only allocates inode numbers for nodes that aren't hard links. If the
target node of a hard link does not have an inode number yet, the two
need to be swapped, since this is also the order in which they are
serialized.

The serialization function in libcommon simply has to skip hard link
nodes and when writing directory entries, use the inode num/ref of
the target node.

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

7 files changed, 221 insertions, 22 deletions

diff --git a/include/fstree.h b/include/fstree.h
index aff3952..7f81cf5 100644
--- a/include/fstree.h
+++ b/include/fstree.h
@@ -17,6 +17,9 @@
 #include "sqfs/predef.h"
 #include "compat.h"
 
+#define FSTREE_MODE_HARD_LINK (0)
+#define FSTREE_MODE_HARD_LINK_RESOLVED (1)
+
 typedef struct tree_node_t tree_node_t;
 typedef struct file_info_t file_info_t;
 typedef struct dir_info_t dir_info_t;
@@ -40,6 +43,9 @@ struct dir_info_t {
 
 	/* Set to true for implicitly generated directories.  */
 	bool created_implicitly;
+
+	/* Used by recursive tree walking code to avoid hard link loops */
+	bool visited;
 };
 
 /* A node in a file system tree */
@@ -68,12 +74,13 @@ struct tree_node_t {
 	   Generated on the fly when writing inodes. */
 	sqfs_u64 inode_ref;
 
-	/* Type specific data. Pointers are into payload area blow. */
+	/* Type specific data. "target" pointer is into payload area below. */
 	union {
 		dir_info_t dir;
 		file_info_t file;
 		char *target;
 		sqfs_u64 devno;
+		tree_node_t *target_node;
 	} data;
 
 	sqfs_u8 payload[];
@@ -156,13 +163,15 @@ int fstree_from_file(fstree_t *fs, const char *filename, FILE *fp);
 /*
   This function performs all the necessary post processing steps on the file
   system tree, i.e. recursively sorting all directory entries by name,
-  allocating inode numbers and stringing all files nodes together into a
-  linked list.
+  allocating inode numbers, resolving hard links and stringing all files nodes
+  together into a linked list.
 
   The total inode count is stored in unique_inode_count. The head of the file
   list is pointed to by fs->files.
+
+  Returns 0 on success, prints to stderr on failure.
  */
-void fstree_post_process(fstree_t *fs);
+int fstree_post_process(fstree_t *fs);
 
 /*
   Generate a string holding the full path of a node. Returned
@@ -205,4 +214,17 @@ int canonicalize_name(char *filename);
  */
 bool is_filename_sane(const char *name, bool check_os_specific);
 
+/*
+  Add a hard link node. Returns NULL on failure and sets errno.
+ */
+tree_node_t *fstree_add_hard_link(fstree_t *fs, const char *path,
+				  const char *target);
+
+/*
+  Resolve a hard link node and replace it with a direct pointer to the target.
+
+  Returns 0 on success. On failure, errno is set.
+ */
+int fstree_resolve_hard_link(fstree_t *fs, tree_node_t *node);
+
 #endif /* FSTREE_H */
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;
 }
diff --git a/mkfs/mkfs.c b/mkfs/mkfs.c
index 89215c6..213fb36 100644
--- a/mkfs/mkfs.c
+++ b/mkfs/mkfs.c
@@ -232,7 +232,8 @@ int main(int argc, char **argv)
 		sehnd = NULL;
 	}
 
-	fstree_post_process(&sqfs.fs);
+	if (fstree_post_process(&sqfs.fs))
+		goto out;
 
 	if (pack_files(sqfs.data, &sqfs.fs, &sqfs.stats, &opt))
 		goto out;
diff --git a/tar/tar2sqfs.c b/tar/tar2sqfs.c
index a13b84e..63933eb 100644
--- a/tar/tar2sqfs.c
+++ b/tar/tar2sqfs.c
@@ -551,7 +551,8 @@ int main(int argc, char **argv)
 	if (process_tar_ball())
 		goto out;
 
-	fstree_post_process(&sqfs.fs);
+	if (fstree_post_process(&sqfs.fs))
+		goto out;
 
 	if (sqfs_writer_finish(&sqfs, &cfg))
 		goto out;