aboutsummaryrefslogtreecommitdiff
path: root/lib/fstree
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2019-04-30 01:24:16 +0200
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2019-04-30 01:31:32 +0200
commitfa7f378bf627ddcfd7a93a000149e4d8c3810bf5 (patch)
treee431943a22bc73395c4cb6a639b4243fc45f7deb /lib/fstree
Initial commit
Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>
Diffstat (limited to 'lib/fstree')
-rw-r--r--lib/fstree/fstree.c200
-rw-r--r--lib/fstree/fstree_from_file.c436
-rw-r--r--lib/fstree/fstree_sort.c76
3 files changed, 712 insertions, 0 deletions
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 <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <errno.h>
+
+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 <sys/sysmacros.h>
+#include <sys/types.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <stdio.h>
+#include <ctype.h>
+#include <errno.h>
+
+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: <type> <path> <mode> <uid> <gid> [<extra>]\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 <string.h>
+
+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);
+}