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/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 ++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 706 insertions(+) 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/src') 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