aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2019-09-17 15:49:26 +0200
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2019-09-20 03:18:47 +0200
commit71895fb039d7f19ab277aa6094d9755bb6827565 (patch)
tree9839f987fce8700084743811f70ff678e28e5432
parentab0c4a02ba9d1a836f62a8601699c971b72eec07 (diff)
Add fstree like tree deserialization function to dir reader
Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>
-rw-r--r--include/sqfs/dir.h124
-rw-r--r--include/sqfs/error.h2
-rw-r--r--include/sqfs/predef.h1
-rw-r--r--lib/sqfs/Makemodule.am2
-rw-r--r--lib/sqfs/read_tree.c291
5 files changed, 419 insertions, 1 deletions
diff --git a/include/sqfs/dir.h b/include/sqfs/dir.h
index d8603d7..d57ad73 100644
--- a/include/sqfs/dir.h
+++ b/include/sqfs/dir.h
@@ -192,6 +192,95 @@ struct sqfs_dir_index_t {
uint8_t name[];
};
+typedef enum {
+ /**
+ * @brief Omit device special files from the final tree.
+ */
+ SQFS_TREE_NO_DEVICES = 0x01,
+
+ /**
+ * @brief Omit socket files from the final tree.
+ */
+ SQFS_TREE_NO_SOCKETS = 0x02,
+
+ /**
+ * @brief Omit named pipes from the final tree.
+ */
+ SQFS_TREE_NO_FIFO = 0x04,
+
+ /**
+ * @brief Omit symbolic links from the final tree.
+ */
+ SQFS_TREE_NO_SLINKS = 0x08,
+
+ /**
+ * @brief Omit empty directories from the final tree.
+ *
+ * If a directory is not empty on-disk, but ends up empty after
+ * applying all the other filter rules, it is also omitted.
+ */
+ SQFS_TREE_NO_EMPTY = 0x10,
+
+ /**
+ * @brief Do not recurse into sub directories.
+ *
+ * If the start node is a directory, the tree deserializer will still
+ * recurse into it, but it will not go beyond that.
+ */
+ SQFS_TREE_NO_RECURSE = 0x20,
+
+ /**
+ * @brief Store the list of parent nodes all the way to the target node
+ *
+ * When traversing towards the selected node, also collect the chain
+ * of parent nodes with the subtree stored at the end.
+ */
+ SQFS_TREE_STORE_PARENTS = 0x40,
+} E_SQFS_TREE_FILTER_FLAGS;
+
+/**
+ * @struct sqfs_tree_node_t
+ *
+ * @brief Encapsulates a node in the filesystem tree read by
+ * @ref sqfs_dir_reader_get_full_hierarchy.
+ */
+struct sqfs_tree_node_t {
+ /**
+ * @brief Pointer to parent, NULL for the root node
+ */
+ sqfs_tree_node_t *parent;
+
+ /**
+ * @brief For directories, a linked list of children.
+ */
+ sqfs_tree_node_t *children;
+
+ /**
+ * @brief Linked list next pointer for children list.
+ */
+ sqfs_tree_node_t *next;
+
+ /**
+ * @brief Inode representing this element in the tree.
+ */
+ sqfs_inode_generic_t *inode;
+
+ /**
+ * @brief Resolved 32 bit user ID from the inode
+ */
+ uint32_t uid;
+
+ /**
+ * @brief Resolved 32 bit group ID from the inode
+ */
+ uint32_t gid;
+
+ /**
+ * @brief null-terminated entry name.
+ */
+ uint8_t name[];
+};
+
#ifdef __cplusplus
extern "C" {
#endif
@@ -500,6 +589,41 @@ SQFS_API int sqfs_dir_reader_find_by_path(sqfs_dir_reader_t *rd,
const char *path,
sqfs_inode_generic_t **out);
+/**
+ * @brief High level helper function for deserializing the entire file system
+ * hierarchy into an in-memory tree structure.
+ *
+ * @memberof sqfs_dir_reader_t
+ *
+ * This function internally navigates to a specified inode using
+ * @ref sqfs_dir_reader_find_by_path and starting from that recursively
+ * deserializes the entire hierarchy into a tree structure holding all inodes.
+ *
+ * @param rd A pointer to a directory reader.
+ * @param path A path to resolve into an inode. Forward or backward slashes can
+ * be used to seperate path components. Resolving '.' or '..' is
+ * not supported. Can be set to NULL to get the root inode.
+ * @param flags A combination of @ref E_SQFS_TREE_FILTER_FLAGS flags.
+ * @param out Returns the top most tree node.
+ *
+ * @return Zero on success, an @ref E_SQFS_ERROR value on failure.
+ */
+SQFS_API int sqfs_dir_reader_get_full_hierarchy(sqfs_dir_reader_t *rd,
+ const sqfs_id_table_t *idtbl,
+ const char *path,
+ unsigned int flags,
+ sqfs_tree_node_t **out);
+
+/**
+ * @brief Recursively destroy a tree of @ref sqfs_tree_node_t nodes
+ *
+ * This function can be used to clean up after
+ * @ref sqfs_dir_reader_get_full_hierarchy.
+ *
+ * @param root A pointer to the root node.
+ */
+SQFS_API void sqfs_dir_tree_destroy(sqfs_tree_node_t *root);
+
#ifdef __cplusplus
}
#endif
diff --git a/include/sqfs/error.h b/include/sqfs/error.h
index ddfeadd..31ebb47 100644
--- a/include/sqfs/error.h
+++ b/include/sqfs/error.h
@@ -107,6 +107,8 @@ typedef enum {
SQFS_ERROR_NOT_DIR = -12,
SQFS_ERROR_NO_ENTRY = -13,
+
+ SQFS_ERROR_LINK_LOOP = -14,
} E_SQFS_ERROR;
#endif /* SQFS_ERROR_H */
diff --git a/include/sqfs/predef.h b/include/sqfs/predef.h
index 4041a57..c25a858 100644
--- a/include/sqfs/predef.h
+++ b/include/sqfs/predef.h
@@ -70,6 +70,7 @@ typedef struct sqfs_meta_writer_t sqfs_meta_writer_t;
typedef struct sqfs_xattr_reader_t sqfs_xattr_reader_t;
typedef struct sqfs_file_t sqfs_file_t;
typedef struct sqfs_sparse_map_t sqfs_sparse_map_t;
+typedef struct sqfs_tree_node_t sqfs_tree_node_t;
typedef struct sqfs_fragment_t sqfs_fragment_t;
typedef struct sqfs_dir_header_t sqfs_dir_header_t;
diff --git a/lib/sqfs/Makemodule.am b/lib/sqfs/Makemodule.am
index 807c104..8dbb255 100644
--- a/lib/sqfs/Makemodule.am
+++ b/lib/sqfs/Makemodule.am
@@ -14,7 +14,7 @@ libsquashfs_la_SOURCES += lib/sqfs/read_inode.c lib/sqfs/write_inode.c
libsquashfs_la_SOURCES += lib/sqfs/dir_writer.c lib/sqfs/xattr_reader.c
libsquashfs_la_SOURCES += lib/sqfs/read_table.c lib/sqfs/comp/compressor.c
libsquashfs_la_SOURCES += lib/sqfs/io_stdin.c lib/sqfs/comp/internal.h
-libsquashfs_la_SOURCES += lib/sqfs/dir_reader.c
+libsquashfs_la_SOURCES += lib/sqfs/dir_reader.c lib/sqfs/read_tree.c
libsquashfs_la_SOURCES += lib/sqfs/blk_proc/process_block.c lib/sqfs/io.c
libsquashfs_la_SOURCES += lib/sqfs/blk_proc/internal.h
libsquashfs_la_CPPFLAGS = $(AM_CPPFLAGS)
diff --git a/lib/sqfs/read_tree.c b/lib/sqfs/read_tree.c
new file mode 100644
index 0000000..1cac26a
--- /dev/null
+++ b/lib/sqfs/read_tree.c
@@ -0,0 +1,291 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * read_tree.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#define SQFS_BUILDING_DLL
+#include "config.h"
+
+#include "sqfs/meta_reader.h"
+#include "sqfs/compress.h"
+#include "sqfs/id_table.h"
+#include "sqfs/super.h"
+#include "sqfs/inode.h"
+#include "sqfs/error.h"
+#include "sqfs/dir.h"
+#include "util.h"
+
+#include <string.h>
+#include <stdlib.h>
+
+static int should_skip(int type, unsigned int flags)
+{
+ switch (type) {
+ case SQFS_INODE_BDEV:
+ case SQFS_INODE_CDEV:
+ case SQFS_INODE_EXT_CDEV:
+ case SQFS_INODE_EXT_BDEV:
+ return (flags & SQFS_TREE_NO_DEVICES);
+ case SQFS_INODE_SLINK:
+ case SQFS_INODE_EXT_SLINK:
+ return (flags & SQFS_TREE_NO_SLINKS);
+ case SQFS_INODE_SOCKET:
+ case SQFS_INODE_EXT_SOCKET:
+ return(flags & SQFS_TREE_NO_SOCKETS);
+ case SQFS_INODE_FIFO:
+ case SQFS_INODE_EXT_FIFO:
+ return (flags & SQFS_TREE_NO_FIFO);
+ }
+
+ return 0;
+}
+
+static bool would_be_own_parent(sqfs_tree_node_t *parent, sqfs_tree_node_t *n)
+{
+ uint32_t inum = n->inode->base.inode_number;
+
+ while (parent != NULL) {
+ if (parent->inode->base.inode_number == inum)
+ return true;
+
+ parent = parent->parent;
+ }
+
+ return false;
+}
+
+static sqfs_tree_node_t *create_node(sqfs_inode_generic_t *inode,
+ const char *name)
+{
+ sqfs_tree_node_t *n;
+
+ n = alloc_flex(sizeof(*n), 1, strlen(name) + 1);
+ if (n == NULL)
+ return NULL;
+
+ n->inode = inode;
+ strcpy((char *)n->name, name);
+ return n;
+}
+
+static int fill_dir(sqfs_dir_reader_t *dr, sqfs_tree_node_t *root,
+ unsigned int flags)
+{
+ sqfs_tree_node_t *n, *prev, **tail;
+ sqfs_inode_generic_t *inode;
+ sqfs_dir_entry_t *ent;
+ int err;
+
+ tail = &root->children;
+
+ for (;;) {
+ err = sqfs_dir_reader_read(dr, &ent);
+ if (err > 0)
+ break;
+ if (err < 0)
+ return err;
+
+ if (should_skip(ent->type, flags)) {
+ free(ent);
+ continue;
+ }
+
+ err = sqfs_dir_reader_get_inode(dr, &inode);
+ if (err) {
+ free(ent);
+ return err;
+ }
+
+ n = create_node(inode, (const char *)ent->name);
+ free(ent);
+
+ if (n == NULL) {
+ free(inode);
+ return SQFS_ERROR_ALLOC;
+ }
+
+ if (would_be_own_parent(root, n)) {
+ free(n);
+ free(inode);
+ return SQFS_ERROR_LINK_LOOP;
+ }
+
+ *tail = n;
+ tail = &n->next;
+ n->parent = root;
+ }
+
+ n = root->children;
+ prev = NULL;
+
+ while (n != NULL) {
+ if (n->inode->base.type == SQFS_INODE_DIR ||
+ n->inode->base.type == SQFS_INODE_EXT_DIR) {
+ if (!(flags & SQFS_TREE_NO_RECURSE)) {
+ err = sqfs_dir_reader_open_dir(dr, n->inode);
+ if (err)
+ return err;
+
+ err = fill_dir(dr, n, flags);
+ if (err)
+ return err;
+ }
+
+ if (n->children == NULL &&
+ (flags & SQFS_TREE_NO_EMPTY)) {
+ free(n->inode);
+ if (prev == NULL) {
+ root->children = n->next;
+ free(n);
+ n = root->children;
+ } else {
+ prev->next = n->next;
+ free(n);
+ n = prev->next;
+ }
+ continue;
+ }
+ }
+
+ prev = n;
+ n = n->next;
+ }
+
+ return 0;
+}
+
+static int resolve_ids(sqfs_tree_node_t *root, const sqfs_id_table_t *idtbl)
+{
+ sqfs_tree_node_t *it;
+ int err;
+
+ for (it = root->children; it != NULL; it = it->next)
+ resolve_ids(it, idtbl);
+
+ err = sqfs_id_table_index_to_id(idtbl, root->inode->base.uid_idx,
+ &root->uid);
+ if (err)
+ return err;
+
+ return sqfs_id_table_index_to_id(idtbl, root->inode->base.gid_idx,
+ &root->gid);
+}
+
+void sqfs_dir_tree_destroy(sqfs_tree_node_t *root)
+{
+ sqfs_tree_node_t *it;
+
+ while (root->children != NULL) {
+ it = root->children;
+ root->children = it->next;
+
+ sqfs_dir_tree_destroy(it);
+ }
+
+ free(root->inode);
+ free(root);
+}
+
+int sqfs_dir_reader_get_full_hierarchy(sqfs_dir_reader_t *rd,
+ const sqfs_id_table_t *idtbl,
+ const char *path, unsigned int flags,
+ sqfs_tree_node_t **out)
+{
+ sqfs_tree_node_t *root, *tail, *new;
+ sqfs_inode_generic_t *inode;
+ sqfs_dir_entry_t *ent;
+ const char *ptr;
+ int ret;
+
+ ret = sqfs_dir_reader_get_root_inode(rd, &inode);
+ if (ret)
+ return ret;
+
+ root = tail = create_node(inode, "");
+ if (root == NULL) {
+ free(inode);
+ return SQFS_ERROR_ALLOC;
+ }
+ inode = NULL;
+
+ while (path != NULL && *path != '\0') {
+ if (*path == '/' || *path == '\\') {
+ while (*path == '/' || *path == '\\')
+ ++path;
+ continue;
+ }
+
+ ret = sqfs_dir_reader_open_dir(rd, tail->inode);
+ if (ret)
+ goto fail;
+
+ ptr = strchr(path, '/');
+ if (ptr == NULL)
+ ptr = strchrnul(path, '\\');
+
+ for (;;) {
+ ret = sqfs_dir_reader_read(rd, &ent);
+ if (ret < 0)
+ goto fail;
+ if (ret > 0) {
+ ret = SQFS_ERROR_NO_ENTRY;
+ goto fail;
+ }
+
+ ret = strncmp((const char *)ent->name,
+ path, ptr - path);
+ if (ret == 0 && ent->name[ptr - path] == '\0')
+ break;
+ free(ent);
+ }
+
+ ret = sqfs_dir_reader_get_inode(rd, &inode);
+ if (ret) {
+ free(ent);
+ goto fail;
+ }
+
+ new = create_node(inode, (const char *)ent->name);
+ free(ent);
+
+ if (new == NULL) {
+ free(inode);
+ ret = SQFS_ERROR_ALLOC;
+ goto fail;
+ }
+
+ inode = NULL;
+ path = ptr;
+
+ if (flags & SQFS_TREE_STORE_PARENTS) {
+ tail->children = new;
+ new->parent = tail;
+ tail = new;
+ } else {
+ sqfs_dir_tree_destroy(root);
+ root = tail = new;
+ }
+ }
+
+ if (tail->inode->base.type == SQFS_INODE_DIR ||
+ tail->inode->base.type == SQFS_INODE_EXT_DIR) {
+ ret = sqfs_dir_reader_open_dir(rd, tail->inode);
+ if (ret)
+ goto fail;
+
+ ret = fill_dir(rd, tail, flags);
+ if (ret)
+ goto fail;
+ }
+
+ ret = resolve_ids(root, idtbl);
+ if (ret)
+ goto fail;
+
+ *out = root;
+ return 0;
+fail:
+ sqfs_dir_tree_destroy(root);
+ return ret;
+}