From 1466f1f8571aca423156ee7ef4094a0c082f88d7 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Thu, 19 Dec 2019 16:10:39 +0100 Subject: 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 --- lib/common/serialize_fstree.c | 15 ++++- lib/fstree/Makemodule.am | 2 +- lib/fstree/hardlink.c | 65 ++++++++++++++++++++++ lib/fstree/post_process.c | 125 ++++++++++++++++++++++++++++++++++++++---- 4 files changed, 191 insertions(+), 16 deletions(-) create mode 100644 lib/fstree/hardlink.c (limited to 'lib') 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 + */ +#include "config.h" + +#include "fstree.h" + +#include +#include +#include + +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 +#include +#include #include +#include -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; } -- cgit v1.2.3