From cdccc69c62579b0c13b35fad0728079652b8f3c9 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Tue, 31 Jan 2023 11:21:30 +0100 Subject: Move library source into src sub-directory Signed-off-by: David Oberhollenzer --- lib/fstree/Makemodule.am | 10 +- lib/fstree/add_by_path.c | 54 ----------- lib/fstree/fstree.c | 135 -------------------------- lib/fstree/get_by_path.c | 76 --------------- lib/fstree/get_path.c | 43 -------- lib/fstree/hardlink.c | 76 --------------- lib/fstree/mknode.c | 101 ------------------- lib/fstree/post_process.c | 221 ------------------------------------------ lib/fstree/src/add_by_path.c | 54 +++++++++++ lib/fstree/src/fstree.c | 135 ++++++++++++++++++++++++++ lib/fstree/src/get_by_path.c | 76 +++++++++++++++ lib/fstree/src/get_path.c | 43 ++++++++ lib/fstree/src/hardlink.c | 76 +++++++++++++++ lib/fstree/src/mknode.c | 101 +++++++++++++++++++ lib/fstree/src/post_process.c | 221 ++++++++++++++++++++++++++++++++++++++++++ 15 files changed, 710 insertions(+), 712 deletions(-) delete mode 100644 lib/fstree/add_by_path.c delete mode 100644 lib/fstree/fstree.c delete mode 100644 lib/fstree/get_by_path.c delete mode 100644 lib/fstree/get_path.c delete mode 100644 lib/fstree/hardlink.c delete mode 100644 lib/fstree/mknode.c delete mode 100644 lib/fstree/post_process.c create mode 100644 lib/fstree/src/add_by_path.c create mode 100644 lib/fstree/src/fstree.c create mode 100644 lib/fstree/src/get_by_path.c create mode 100644 lib/fstree/src/get_path.c create mode 100644 lib/fstree/src/hardlink.c create mode 100644 lib/fstree/src/mknode.c create mode 100644 lib/fstree/src/post_process.c (limited to 'lib/fstree') diff --git a/lib/fstree/Makemodule.am b/lib/fstree/Makemodule.am index 09cd9ac..f740527 100644 --- a/lib/fstree/Makemodule.am +++ b/lib/fstree/Makemodule.am @@ -1,8 +1,6 @@ -libfstree_a_SOURCES = include/fstree.h lib/fstree/fstree.c -libfstree_a_SOURCES += lib/fstree/post_process.c lib/fstree/get_path.c -libfstree_a_SOURCES += lib/fstree/mknode.c lib/fstree/hardlink.c -libfstree_a_SOURCES += lib/fstree/add_by_path.c lib/fstree/get_by_path.c -libfstree_a_CFLAGS = $(AM_CFLAGS) -libfstree_a_CPPFLAGS = $(AM_CPPFLAGS) +libfstree_a_SOURCES = include/fstree.h lib/fstree/src/fstree.c \ + lib/fstree/src/post_process.c lib/fstree/src/get_path.c \ + lib/fstree/src/mknode.c lib/fstree/src/hardlink.c \ + lib/fstree/src/add_by_path.c lib/fstree/src/get_by_path.c noinst_LIBRARIES += libfstree.a diff --git a/lib/fstree/add_by_path.c b/lib/fstree/add_by_path.c deleted file mode 100644 index 0afd898..0000000 --- a/lib/fstree/add_by_path.c +++ /dev/null @@ -1,54 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * add_by_path.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include "fstree.h" - -#include -#include -#include - -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/fstree.c b/lib/fstree/fstree.c deleted file mode 100644 index d44a8ae..0000000 --- a/lib/fstree/fstree.c +++ /dev/null @@ -1,135 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * fstree.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" -#include "fstree.h" - -#include "util/util.h" - -#include -#include -#include - -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/get_by_path.c b/lib/fstree/get_by_path.c deleted file mode 100644 index 8742892..0000000 --- a/lib/fstree/get_by_path.c +++ /dev/null @@ -1,76 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * get_by_path.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include "fstree.h" - -#include -#include - -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/get_path.c b/lib/fstree/get_path.c deleted file mode 100644 index decf92e..0000000 --- a/lib/fstree/get_path.c +++ /dev/null @@ -1,43 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * get_path.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include "fstree.h" - -#include -#include - -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/hardlink.c b/lib/fstree/hardlink.c deleted file mode 100644 index 2165b5f..0000000 --- a/lib/fstree/hardlink.c +++ /dev/null @@ -1,76 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * hardlink.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include "util/util.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; - } - } - - 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/mknode.c b/lib/fstree/mknode.c deleted file mode 100644 index 2faf901..0000000 --- a/lib/fstree/mknode.c +++ /dev/null @@ -1,101 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * mknode.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" -#include "fstree.h" - -#include -#include -#include - -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/post_process.c b/lib/fstree/post_process.c deleted file mode 100644 index 088916b..0000000 --- a/lib/fstree/post_process.c +++ /dev/null @@ -1,221 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * post_process.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" -#include "fstree.h" - -#include -#include -#include -#include -#include - -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; -} 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 + */ +#include "config.h" + +#include "fstree.h" + +#include +#include +#include + +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 + */ +#include "config.h" +#include "fstree.h" + +#include "util/util.h" + +#include +#include +#include + +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 + */ +#include "config.h" + +#include "fstree.h" + +#include +#include + +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 + */ +#include "config.h" + +#include "fstree.h" + +#include +#include + +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 + */ +#include "config.h" + +#include "util/util.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; + } + } + + 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 + */ +#include "config.h" +#include "fstree.h" + +#include +#include +#include + +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 + */ +#include "config.h" +#include "fstree.h" + +#include +#include +#include +#include +#include + +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; +} -- cgit v1.2.3