From fa7f378bf627ddcfd7a93a000149e4d8c3810bf5 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Tue, 30 Apr 2019 01:24:16 +0200 Subject: Initial commit Signed-off-by: David Oberhollenzer --- lib/Makemodule.am | 5 + lib/fstree/fstree.c | 200 +++++++++++++++++++ lib/fstree/fstree_from_file.c | 436 ++++++++++++++++++++++++++++++++++++++++++ lib/fstree/fstree_sort.c | 76 ++++++++ 4 files changed, 717 insertions(+) create mode 100644 lib/Makemodule.am create mode 100644 lib/fstree/fstree.c create mode 100644 lib/fstree/fstree_from_file.c create mode 100644 lib/fstree/fstree_sort.c (limited to 'lib') diff --git a/lib/Makemodule.am b/lib/Makemodule.am new file mode 100644 index 0000000..18ec8c4 --- /dev/null +++ b/lib/Makemodule.am @@ -0,0 +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 += include/fstree.h + +noinst_LIBRARIES += libfstree.a diff --git a/lib/fstree/fstree.c b/lib/fstree/fstree.c new file mode 100644 index 0000000..2722b4a --- /dev/null +++ b/lib/fstree/fstree.c @@ -0,0 +1,200 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +#include "fstree.h" + +#include +#include +#include +#include + +static tree_node_t *mknode(tree_node_t *parent, const char *name, + size_t name_len, size_t extra_len, + uint16_t mode, uint32_t uid, uint32_t gid) +{ + size_t size = sizeof(tree_node_t) + extra_len; + tree_node_t *n; + + switch (mode & S_IFMT) { + case S_IFDIR: + size += sizeof(*n->data.dir); + break; + case S_IFREG: + size += sizeof(*n->data.file); + break; + } + + n = calloc(1, size + name_len + 1); + if (n == NULL) + return NULL; + + if (parent != NULL) { + n->next = parent->data.dir->children; + parent->data.dir->children = n; + } + + n->uid = uid; + n->gid = gid; + n->mode = mode; + + switch (mode & S_IFMT) { + case S_IFDIR: + n->data.dir = (dir_info_t *)n->payload; + break; + case S_IFREG: + n->data.file = (file_info_t *)n->payload; + break; + case S_IFLNK: + n->data.slink_target = (char *)n->payload; + break; + } + + n->name = (char *)n + size; + memcpy(n->name, name, name_len); + return n; +} + +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); +} + +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; +} + +static tree_node_t *get_parent_node(fstree_t *fs, tree_node_t *root, + const char *path) +{ + const char *end; + tree_node_t *n; + + for (;;) { + if (!S_ISDIR(root->mode)) { + errno = ENOTDIR; + return NULL; + } + + end = strchr(path, '/'); + if (end == NULL) + break; + + n = child_by_name(root, path, end - path); + + if (n == NULL) { + n = mknode(root, path, end - path, 0, + S_IFDIR | fs->default_mode, + fs->default_uid, fs->default_gid); + if (n == NULL) + return NULL; + + n->data.dir->created_implicitly = true; + } + + root = n; + path = end + 1; + } + + return root; +} + +tree_node_t *fstree_add(fstree_t *fs, const char *path, uint16_t mode, + uint32_t uid, uint32_t gid, size_t extra_len) +{ + tree_node_t *child, *parent; + const char *name; + + name = strrchr(path, '/'); + name = (name == NULL ? path : (name + 1)); + + parent = get_parent_node(fs, fs->root, path); + if (parent == NULL) + return NULL; + + child = child_by_name(parent, name, strlen(name)); + if (child != NULL) { + if (S_ISDIR(child->mode) && S_ISDIR(mode) && + child->data.dir->created_implicitly) { + child->data.dir->created_implicitly = false; + return child; + } + + errno = EEXIST; + return NULL; + } + + return mknode(parent, name, strlen(name), extra_len, mode, uid, gid); +} + +tree_node_t *fstree_add_file(fstree_t *fs, const char *path, uint16_t mode, + uint32_t uid, uint32_t gid, uint64_t filesz, + const char *input) +{ + tree_node_t *node; + size_t count, extra; + char *ptr; + + count = filesz / fs->block_size; + extra = sizeof(uint32_t) * count + strlen(input) + 1; + + mode &= 07777; + node = fstree_add(fs, path, S_IFREG | mode, uid, gid, extra); + + if (node != NULL) { + ptr = (char *)(node->data.file->blocksizes + count); + strcpy(ptr, input); + + node->data.file->input_file = ptr; + node->data.file->size = filesz; + } + return node; +} + +int fstree_init(fstree_t *fs, size_t block_size, uint32_t mtime, + uint16_t default_mode, uint32_t default_uid, + uint32_t default_gid) +{ + memset(fs, 0, sizeof(*fs)); + + fs->default_uid = default_uid; + fs->default_gid = default_gid; + fs->default_mode = default_mode & 07777; + fs->default_mtime = mtime; + fs->block_size = block_size; + + fs->root = mknode(NULL, "", 0, 0, S_IFDIR | fs->default_mode, + default_uid, default_gid); + + if (fs->root == NULL) { + perror("initializing file system tree"); + return -1; + } + + return 0; +} + +void fstree_cleanup(fstree_t *fs) +{ + free_recursive(fs->root); + memset(fs, 0, sizeof(*fs)); +} diff --git a/lib/fstree/fstree_from_file.c b/lib/fstree/fstree_from_file.c new file mode 100644 index 0000000..66d71a2 --- /dev/null +++ b/lib/fstree/fstree_from_file.c @@ -0,0 +1,436 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +#include "fstree.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +static int add_dir(fstree_t *fs, const char *filename, size_t line_num, + const char *path, uint16_t mode, uint32_t uid, + uint32_t gid, const char *extra) +{ + if (extra != NULL && *extra != '\0') { + fprintf(stderr, "%s: %zu: WARNING: ignoring extra arguments\n", + filename, line_num); + } + + if (fstree_add(fs, path, S_IFDIR | mode, uid, gid, 0) == NULL) { + fprintf(stderr, "%s: %zu: mkdir -p %s: %s\n", + filename, line_num, path, strerror(errno)); + return -1; + } + + return 0; +} + +static int add_slink(fstree_t *fs, const char *filename, size_t line_num, + const char *path, uint16_t mode, uint32_t uid, + uint32_t gid, const char *extra) +{ + tree_node_t *node; + (void)mode; + + if (extra == NULL || *extra == '\0') { + fprintf(stderr, "%s: %zu: missing symlink target\n", + filename, line_num); + return -1; + } + + node = fstree_add(fs, path, S_IFLNK | 0777, uid, gid, + strlen(extra) + 1); + + if (node == NULL) { + fprintf(stderr, "%s: %zu: ln -s %s %s\n", + filename, line_num, extra, path); + return -1; + } + + strcpy(node->data.slink_target, extra); + return 0; +} + +static int add_device(fstree_t *fs, const char *filename, size_t line_num, + const char *path, uint16_t mode, uint32_t uid, + uint32_t gid, const char *extra) +{ + unsigned int maj = 0, min = 0; + tree_node_t *node; + + if (extra == NULL || *extra == '\0') { + fprintf(stderr, "%s: %zu: missing device type\n", + filename, line_num); + return -1; + } + + if ((*extra == 'c' || *extra == 'C') && isspace(extra[1])) { + mode |= S_IFCHR; + } else if ((*extra == 'b' || *extra == 'B') && isspace(extra[1])) { + mode |= S_IFBLK; + } else { + fprintf(stderr, "%s: %zu: unsupported device type", + filename, line_num); + return -1; + } + + ++extra; + while (isspace(*extra)) + ++extra; + + if (!isdigit(*extra)) + goto fail_devno; + + while (isdigit(*extra)) + maj = maj * 10 + *(extra++) - '0'; + + if (*(extra++) != ':') + goto fail_devno; + + if (!isdigit(*extra)) + goto fail_devno; + + while (isdigit(*extra)) + min = min * 10 + *(extra++) - '0'; + + while (isspace(*extra)) + ++extra; + + if (*extra != '\0') { + fprintf(stderr, "%s: %zu: WARNING: ignoring extra arguments\n", + filename, line_num); + } + + node = fstree_add(fs, path, mode, uid, gid, 0); + if (node == NULL) { + fprintf(stderr, "%s: %zu: mknod %s %c %u %u: %s\n", + filename, line_num, path, S_ISCHR(mode) ? 'c' : 'b', + maj, min, strerror(errno)); + return -1; + } + + node->data.devno = makedev(maj, min); + return 0; +fail_devno: + fprintf(stderr, "%s: %zu: error in device number format\n", + filename, line_num); + return -1; +} + +static int add_pipe(fstree_t *fs, const char *filename, size_t line_num, + const char *path, uint16_t mode, uint32_t uid, + uint32_t gid, const char *extra) +{ + if (extra != NULL && *extra != '\0') { + fprintf(stderr, "%s: %zu: WARNING: ignoring extra arguments\n", + filename, line_num); + } + + if (fstree_add(fs, path, S_IFIFO | mode, uid, gid, 0) == NULL) { + fprintf(stderr, "%s: %zu: mkfifo %s: %s\n", + filename, line_num, path, strerror(errno)); + return -1; + } + + return 0; +} + +static int add_socket(fstree_t *fs, const char *filename, size_t line_num, + const char *path, uint16_t mode, uint32_t uid, + uint32_t gid, const char *extra) +{ + if (extra != NULL && *extra != '\0') { + fprintf(stderr, "%s: %zu: WARNING: ignoring extra arguments\n", + filename, line_num); + } + + if (fstree_add(fs, path, S_IFSOCK | mode, uid, gid, 0) == NULL) { + fprintf(stderr, "%s: %zu: creating Unix socket %s: %s\n", + filename, line_num, path, strerror(errno)); + return -1; + } + + return 0; +} + +static int add_file(fstree_t *fs, const char *filename, size_t line_num, + const char *path, uint16_t mode, uint32_t uid, + uint32_t gid, const char *extra) +{ + char *infile = NULL; + tree_node_t *node; + const char *ptr; + struct stat sb; + int ret; + + ptr = strrchr(filename, '/'); + + if (extra == NULL || *extra == '\0') { + if (ptr == NULL) { + extra = path; + } else { + ret = asprintf(&infile, "%.*s/%s", + (int)(filename - ptr), filename, path); + if (ret < 0) + goto fail_asprintf; + } + } else if (*extra != '/' && ptr != NULL) { + ret = asprintf(&infile, "%.*s/%s", + (int)(filename - ptr), filename, extra); + if (ret < 0) + goto fail_asprintf; + } + + if (infile != NULL) + extra = infile; + + if (stat(extra, &sb) != 0) { + fprintf(stderr, "%s: %zu: stat %s: %s\n", filename, line_num, + extra, strerror(errno)); + goto fail; + } + + node = fstree_add_file(fs, path, mode, uid, gid, sb.st_size, extra); + + if (node == NULL) { + fprintf(stderr, "%s: %zu: adding %s as %s: %s\n", + filename, line_num, extra, path, strerror(errno)); + goto fail; + } + + free(infile); + return 0; +fail: + free(infile); + return -1; +fail_asprintf: + fprintf(stderr, "%s: %zu: pasting together file path: %s\n", + filename, line_num, strerror(errno)); + return -1; +} + +static const struct { + const char *keyword; + int (*callback)(fstree_t *fs, const char *filename, size_t line_num, + const char *path, uint16_t mode, uint32_t uid, + uint32_t gid, const char *extra); +} file_list_hooks[] = { + { "dir", add_dir }, + { "slink", add_slink }, + { "nod", add_device }, + { "pipe", add_pipe }, + { "pipe", add_socket }, + { "file", add_file }, +}; + +#define NUM_HOOKS (sizeof(file_list_hooks) / sizeof(file_list_hooks[0])) + +static void trim_line(char *line) +{ + size_t i; + + for (i = 0; isspace(line[i]); ++i) + ; + + if (line[i] == '#') { + line[0] = '\0'; + return; + } + + if (i > 0) + memmove(line, line + i, strlen(line + i) + 1); + + i = strlen(line); + while (i > 0 && isspace(line[i - 1])) + --i; + + line[i] = '\0'; +} + +static int handle_line(fstree_t *fs, const char *filename, + size_t line_num, char *line) +{ + const char *path, *extra = NULL, *msg = NULL; + unsigned int mode = 0, uid = 0, gid = 0, x; + char keyword[16]; + size_t i; + + /* isolate keyword */ + for (i = 0; isalpha(line[i]); ++i) + ; + + if (i >= sizeof(keyword) || i == 0 || !isspace(line[i])) + goto fail_ent; + + memcpy(keyword, line, i); + keyword[i] = '\0'; + + while (isspace(line[i])) + ++i; + + /* isolate path */ + path = line + i; + + for (; line[i] != '\0'; ++i) { + /* TODO: escape sequences to support spaces in path */ + + if (isspace(line[i])) + break; + } + + if (!isspace(line[i])) + goto fail_ent; + + line[i++] = '\0'; + while (isspace(line[i])) + ++i; + + /* mode */ + if (!isdigit(line[i])) + goto fail_mode; + + for (; isdigit(line[i]); ++i) { + if (line[i] > '7') + goto fail_mode; + + mode = (mode << 3) | (line[i] - '0'); + + if (mode > 07777) + goto fail_mode_bits; + } + + if (!isspace(line[i])) + goto fail_ent; + + while (isspace(line[i])) + ++i; + + /* uid */ + if (!isdigit(line[i])) + goto fail_uid_gid; + + for (; isdigit(line[i]); ++i) { + x = line[i] - '0'; + + if (uid > (0xFFFFFFFF - x) / 10) + goto fail_ov; + + uid = uid * 10 + x; + } + + if (!isspace(line[i])) + goto fail_ent; + + while (isspace(line[i])) + ++i; + + /* gid */ + if (!isdigit(line[i])) + goto fail_uid_gid; + + for (; isdigit(line[i]); ++i) { + x = line[i] - '0'; + + if (gid > (0xFFFFFFFF - x) / 10) + goto fail_ov; + + gid = gid * 10 + x; + } + + /* extra */ + if (isspace(line[i])) { + while (isspace(line[i])) + ++i; + + if (line[i] != '\0') + extra = line + i; + } + + /* forward to callback */ + for (i = 0; i < NUM_HOOKS; ++i) { + if (strcmp(file_list_hooks[i].keyword, keyword) == 0) { + return file_list_hooks[i].callback(fs, filename, + line_num, path, + mode, uid, gid, + extra); + } + } + + fprintf(stderr, "%s: %zu: unknown entry type '%s'.\n", filename, + line_num, keyword); + return -1; +fail_ov: + msg = "numeric overflow"; + goto fail_ent; +fail_uid_gid: + msg = "uid & gid must be decimal numbers"; + goto out_desc; +fail_mode: + msg = "mode must be an octal number"; + goto out_desc; +fail_mode_bits: + msg = "you can only set the permission bits in the mode"; + goto out_desc; +fail_ent: + msg = "error in entry description"; + goto out_desc; +out_desc: + fprintf(stderr, "%s: %zu: %s.\n", filename, line_num, msg); + fputs("expected: []\n", + stderr); + return -1; +} + +int fstree_from_file(fstree_t *fs, const char *filename) +{ + FILE *fp = fopen(filename, "rb"); + size_t n, line_num = 0; + ssize_t ret; + char *line; + + if (fp == NULL) { + perror(filename); + return -1; + } + + for (;;) { + line = NULL; + n = 0; + errno = 0; + + ret = getline(&line, &n, fp); + ++line_num; + + if (ret < 0) { + if (errno == 0) { + free(line); + break; + } + + perror(filename); + goto fail_line; + } + + trim_line(line); + + if (line[0] == '\0') { + free(line); + continue; + } + + if (handle_line(fs, filename, line_num, line)) + goto fail_line; + + free(line); + } + + fclose(fp); + return 0; +fail_line: + free(line); + fclose(fp); + return -1; +} diff --git a/lib/fstree/fstree_sort.c b/lib/fstree/fstree_sort.c new file mode 100644 index 0000000..9f07c92 --- /dev/null +++ b/lib/fstree/fstree_sort.c @@ -0,0 +1,76 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +#include "fstree.h" + +#include + +static tree_node_t *sort_list(tree_node_t *head) +{ + tree_node_t *it, *prev, *lhs, *rhs; + size_t i, count = 0; + + for (it = head; it != NULL; it = it->next) + ++count; + + if (count < 2) + return head; + + prev = NULL; + it = head; + + for (i = 0; i < count / 2; ++i) { + prev = it; + it = it->next; + } + + prev->next = NULL; + + lhs = sort_list(head); + rhs = sort_list(it); + + head = NULL; + prev = NULL; + + while (lhs != NULL && rhs != NULL) { + if (strcmp(lhs->name, rhs->name) <= 0) { + it = lhs; + lhs = lhs->next; + } else { + it = rhs; + rhs = rhs->next; + } + + it->next = NULL; + + if (prev != NULL) { + prev->next = it; + prev = it; + } else { + prev = head = it; + } + } + + it = (lhs != NULL ? lhs : rhs); + + if (prev != NULL) { + prev->next = it; + } else { + head = it; + } + + return head; +} + +static void sort_directory(tree_node_t *n) +{ + n->data.dir->children = sort_list(n->data.dir->children); + + for (n = n->data.dir->children; n != NULL; n = n->next) { + if (S_ISDIR(n->mode)) + sort_directory(n); + } +} + +void fstree_sort(fstree_t *fs) +{ + sort_directory(fs->root); +} -- cgit v1.2.3