diff options
| -rw-r--r-- | include/sqfs/dir.h | 124 | ||||
| -rw-r--r-- | include/sqfs/error.h | 2 | ||||
| -rw-r--r-- | include/sqfs/predef.h | 1 | ||||
| -rw-r--r-- | lib/sqfs/Makemodule.am | 2 | ||||
| -rw-r--r-- | lib/sqfs/read_tree.c | 291 |
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; +} |