From c1e8ef8975458c1c814e85d1e3abe3b94c1fc65e Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sat, 9 Sep 2023 18:00:03 +0200 Subject: Move directory tree related code from libsquashfs to libcommon Signed-off-by: David Oberhollenzer --- Makefile.am | 2 +- include/common.h | 1 + include/dir_tree.h | 180 ++++++++++++++++++++++ include/sqfs/dir_reader.h | 162 -------------------- lib/common/Makemodule.am | 10 +- lib/common/src/dir_tree.c | 98 ++++++++++++ lib/common/src/read_tree.c | 273 ++++++++++++++++++++++++++++++++++ lib/common/test/get_node_path.c | 133 +++++++++++++++++ lib/sqfs/Makemodule.am | 6 +- lib/sqfs/src/dir_reader/get_path.c | 81 ---------- lib/sqfs/src/dir_reader/read_tree.c | 288 ------------------------------------ lib/sqfs/test/get_node_path.c | 132 ----------------- 12 files changed, 694 insertions(+), 672 deletions(-) create mode 100644 include/dir_tree.h create mode 100644 lib/common/src/dir_tree.c create mode 100644 lib/common/src/read_tree.c create mode 100644 lib/common/test/get_node_path.c delete mode 100644 lib/sqfs/src/dir_reader/get_path.c delete mode 100644 lib/sqfs/src/dir_reader/read_tree.c delete mode 100644 lib/sqfs/test/get_node_path.c diff --git a/Makefile.am b/Makefile.am index 141973e..ab960c5 100644 --- a/Makefile.am +++ b/Makefile.am @@ -40,7 +40,7 @@ include bin/sqfs2tar/Makemodule.am include bin/sqfsdiff/Makemodule.am include bin/tar2sqfs/Makemodule.am -include extras/Makemodule.am +#include extras/Makemodule.am if HAVE_DOXYGEN @DX_RULES@ diff --git a/include/common.h b/include/common.h index bf3f34c..ca95ba6 100644 --- a/include/common.h +++ b/include/common.h @@ -21,6 +21,7 @@ #include "simple_writer.h" #include "compress_cli.h" +#include "dir_tree.h" #include "io/std.h" #include "compat.h" #include "fstree.h" diff --git a/include/dir_tree.h b/include/dir_tree.h new file mode 100644 index 0000000..ee630d5 --- /dev/null +++ b/include/dir_tree.h @@ -0,0 +1,180 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * dir_tree.h + * + * Copyright (C) 2019 David Oberhollenzer + */ +#ifndef DIR_TREE_H +#define DIR_TREE_H + +/** + * @enum SQFS_TREE_FILTER_FLAGS + * + * @brief Filter flags for @ref sqfs_dir_reader_get_full_hierarchy + */ +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, + + SQFS_TREE_ALL_FLAGS = 0x7F, +} 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 + */ + sqfs_u32 uid; + + /** + * @brief Resolved 32 bit group ID from the inode + */ + sqfs_u32 gid; + + /** + * @brief null-terminated entry name. + */ + sqfs_u8 name[]; +}; + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * @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 or NULL. + */ +SQFS_INTERNAL void sqfs_dir_tree_destroy(sqfs_tree_node_t *root); + +/** + * @brief Recursively destroy a tree of @ref sqfs_tree_node_t nodes + * + * @memberof sqfs_tree_node_t + * + * This function can be used to assemble an absolute path from a tree + * node returned by @ref sqfs_dir_reader_get_full_hierarchy. + * + * The function recursively walks up the tree to assemble a path string. It + * returns "/" for the root node and assembles paths beginning with "/" for + * non-root nodes. The resulting path is slash separated, but (except for + * the root) never ends with a slash. + * + * While walking the node list, the function enforces various invariantes. It + * returns @ref SQFS_ERROR_LINK_LOOP if the list of parent pointers is cyclical, + * @ref SQFS_ERROR_CORRUPTED if any node has an empty name, or a name that + * contains '/' or equals ".." or ".". The function + * returns @ref SQFS_ERROR_ARG_INVALID if given NULL node or the root has a name + * set. Additionally, the function can return overflow or allocation failures + * while constructing the path. + * + * The returned string needs to be free'd with @ref sqfs_free. + * + * @param node A pointer to a tree node. + * @param out Returns a pointer to a string on success, set to NULL on failure. + * + * @return Zero on success, an @ref SQFS_ERROR value on failure. + */ +SQFS_INTERNAL int sqfs_tree_node_get_path(const sqfs_tree_node_t *node, + char **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 separate path components. Resolving '.' or '..' is + * not supported. Can be set to NULL to get the root inode. + * @param flags A combination of @ref SQFS_TREE_FILTER_FLAGS flags. + * @param out Returns the top most tree node. + * + * @return Zero on success, an @ref SQFS_ERROR value on failure. + */ +SQFS_INTERNAL int sqfs_dir_reader_get_full_hierarchy(sqfs_dir_reader_t *rd, + const sqfs_id_table_t *idtbl, + const char *path, + sqfs_u32 flags, + sqfs_tree_node_t **out); + +#ifdef __cplusplus +} +#endif + +#endif /* DIR_TREE_H */ diff --git a/include/sqfs/dir_reader.h b/include/sqfs/dir_reader.h index 1489a1f..cb071c2 100644 --- a/include/sqfs/dir_reader.h +++ b/include/sqfs/dir_reader.h @@ -52,102 +52,6 @@ * direct access to the inode referred to by a directory entry. */ -/** - * @enum SQFS_TREE_FILTER_FLAGS - * - * @brief Filter flags for @ref sqfs_dir_reader_get_full_hierarchy - */ -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, - - SQFS_TREE_ALL_FLAGS = 0x7F, -} 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 - */ - sqfs_u32 uid; - - /** - * @brief Resolved 32 bit group ID from the inode - */ - sqfs_u32 gid; - - /** - * @brief null-terminated entry name. - */ - sqfs_u8 name[]; -}; - /** * @enum SQFS_DIR_READER_FLAGS * @@ -348,72 +252,6 @@ 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 separate path components. Resolving '.' or '..' is - * not supported. Can be set to NULL to get the root inode. - * @param flags A combination of @ref SQFS_TREE_FILTER_FLAGS flags. - * @param out Returns the top most tree node. - * - * @return Zero on success, an @ref 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, - sqfs_u32 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 or NULL. - */ -SQFS_API void sqfs_dir_tree_destroy(sqfs_tree_node_t *root); - -/** - * @brief Recursively destroy a tree of @ref sqfs_tree_node_t nodes - * - * @memberof sqfs_tree_node_t - * - * This function can be used to assemble an absolute path from a tree - * node returned by @ref sqfs_dir_reader_get_full_hierarchy. - * - * The function recursively walks up the tree to assemble a path string. It - * returns "/" for the root node and assembles paths beginning with "/" for - * non-root nodes. The resulting path is slash separated, but (except for - * the root) never ends with a slash. - * - * While walking the node list, the function enforces various invariantes. It - * returns @ref SQFS_ERROR_LINK_LOOP if the list of parent pointers is cyclical, - * @ref SQFS_ERROR_CORRUPTED if any node has an empty name, or a name that - * contains '/' or equals ".." or ".". The function - * returns @ref SQFS_ERROR_ARG_INVALID if given NULL node or the root has a name - * set. Additionally, the function can return overflow or allocation failures - * while constructing the path. - * - * The returned string needs to be free'd with @ref sqfs_free. - * - * @param node A pointer to a tree node. - * @param out Returns a pointer to a string on success, set to NULL on failure. - * - * @return Zero on success, an @ref SQFS_ERROR value on failure. - */ -SQFS_API int sqfs_tree_node_get_path(const sqfs_tree_node_t *node, - char **out); - #ifdef __cplusplus } #endif diff --git a/lib/common/Makemodule.am b/lib/common/Makemodule.am index a50ddcb..5549cc3 100644 --- a/lib/common/Makemodule.am +++ b/lib/common/Makemodule.am @@ -1,11 +1,12 @@ libcommon_a_SOURCES = include/common.h include/simple_writer.h \ - include/compress_cli.h \ + include/compress_cli.h include/dir_tree.h \ lib/common/src/hardlink.c lib/common/src/print_version.c \ lib/common/src/compress.c lib/common/src/comp_opt.c \ lib/common/src/parse_size.c lib/common/src/print_size.c \ lib/common/src/writer/init.c lib/common/src/writer/cleanup.c \ lib/common/src/writer/serialize_fstree.c lib/common/src/writer/finish.c\ - lib/common/src/fstree_cli.c lib/common/src/perror.c + lib/common/src/fstree_cli.c lib/common/src/perror.c \ + lib/common/src/dir_tree.c lib/common/src/read_tree.c libcommon_a_CFLAGS = $(AM_CFLAGS) $(LZO_CFLAGS) if WITH_LZO @@ -17,8 +18,11 @@ noinst_LIBRARIES += libcommon.a test_fstree_cli_SOURCES = lib/common/test/fstree_cli.c test_fstree_cli_LDADD = libcommon.a libio.a libutil.a libcompat.a +test_get_node_path_SOURCES = lib/common/test/get_node_path.c +test_get_node_path_LDADD = libcommon.a libsquashfs.la libcompat.a + LIBCOMMON_TESTS = \ - test_fstree_cli + test_fstree_cli test_get_node_path check_PROGRAMS += $(LIBCOMMON_TESTS) TESTS += $(LIBCOMMON_TESTS) diff --git a/lib/common/src/dir_tree.c b/lib/common/src/dir_tree.c new file mode 100644 index 0000000..1d778a2 --- /dev/null +++ b/lib/common/src/dir_tree.c @@ -0,0 +1,98 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * dir_tree.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "common.h" + +#include +#include + +void sqfs_dir_tree_destroy(sqfs_tree_node_t *root) +{ + sqfs_tree_node_t *it; + + if (!root) + return; + + while (root->children != NULL) { + it = root->children; + root->children = it->next; + + sqfs_dir_tree_destroy(it); + } + + free(root->inode); + free(root); +} + +int sqfs_tree_node_get_path(const sqfs_tree_node_t *node, char **out) +{ + const sqfs_tree_node_t *it; + size_t clen, len = 0; + char *str, *ptr; + + *out = NULL; + + if (node == NULL) + return SQFS_ERROR_ARG_INVALID; + + for (it = node; it->parent != NULL; it = it->parent) { + if (it->parent == node) + return SQFS_ERROR_LINK_LOOP; + + /* non-root nodes must have a valid name */ + clen = strlen((const char *)it->name); + + if (clen == 0) + return SQFS_ERROR_CORRUPTED; + + if (strchr((const char *)it->name, '/') != NULL) + return SQFS_ERROR_CORRUPTED; + + if (it->name[0] == '.') { + if (clen == 1 || (clen == 2 && it->name[1] == '.')) + return SQFS_ERROR_CORRUPTED; + } + + /* compute total path length */ + if (SZ_ADD_OV(clen, 1, &clen)) + return SQFS_ERROR_OVERFLOW; + + if (SZ_ADD_OV(len, clen, &len)) + return SQFS_ERROR_OVERFLOW; + } + + /* root node must not have a name */ + if (it->name[0] != '\0') + return SQFS_ERROR_ARG_INVALID; + + /* generate the path */ + if (node->parent == NULL) { + str = strdup("/"); + if (str == NULL) + return SQFS_ERROR_ALLOC; + } else { + if (SZ_ADD_OV(len, 1, &len)) + return SQFS_ERROR_OVERFLOW; + + str = malloc(len); + if (str == NULL) + return SQFS_ERROR_ALLOC; + + ptr = str + len - 1; + *ptr = '\0'; + + for (it = node; it->parent != NULL; it = it->parent) { + len = strlen((const char *)it->name); + ptr -= len; + + memcpy(ptr, (const char *)it->name, len); + *(--ptr) = '/'; + } + } + + *out = str; + return 0; +} diff --git a/lib/common/src/read_tree.c b/lib/common/src/read_tree.c new file mode 100644 index 0000000..5d089e5 --- /dev/null +++ b/lib/common/src/read_tree.c @@ -0,0 +1,273 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * read_tree.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "util/util.h" +#include "common.h" + +#include +#include + +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); + default: + break; + } + + return 0; +} + +static bool would_be_own_parent(sqfs_tree_node_t *parent, sqfs_tree_node_t *n) +{ + sqfs_u32 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_node_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, + SQFS_DIR_OPEN_NO_DOT_ENTRIES); + 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 = root->children->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); +} + +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_node_t *ent; + const char *ptr; + int ret; + + if (flags & ~SQFS_TREE_ALL_FLAGS) + return SQFS_ERROR_UNSUPPORTED; + + 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 == '/') { + while (*path == '/') + ++path; + continue; + } + + ret = sqfs_dir_reader_open_dir(rd, tail->inode, + SQFS_DIR_OPEN_NO_DOT_ENTRIES); + if (ret) + goto fail; + + 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, + SQFS_DIR_OPEN_NO_DOT_ENTRIES); + 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; +} diff --git a/lib/common/test/get_node_path.c b/lib/common/test/get_node_path.c new file mode 100644 index 0000000..b02689f --- /dev/null +++ b/lib/common/test/get_node_path.c @@ -0,0 +1,133 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * get_node_path.c + * + * Copyright (C) 2022 David Oberhollenzer + */ +#include "config.h" +#include "compat.h" +#include "util/test.h" + +#include "sqfs/dir_reader.h" +#include "sqfs/error.h" +#include "dir_tree.h" + +int main(int argc, char **argv) +{ + sqfs_tree_node_t *n0, *n1, *n2; + char *str; + int ret; + (void)argc; + (void)argv; + + n0 = calloc(1, sizeof(*n0) + 16); + TEST_NOT_NULL(n0); + + n1 = calloc(1, sizeof(*n1) + 16); + TEST_NOT_NULL(n1); + + n2 = calloc(1, sizeof(*n2) + 16); + TEST_NOT_NULL(n2); + + /* no parent -> must return "/" */ + ret = sqfs_tree_node_get_path(n0, &str); + TEST_EQUAL_I(ret, 0); + TEST_NOT_NULL(str); + TEST_STR_EQUAL(str, "/"); + sqfs_free(str); + + /* hiearchy levels */ + n1->parent = n0; + n0->children = n1; + strcpy((char *)n1->name, "bar"); + + n2->parent = n1; + n1->children = n2; + strcpy((char *)n2->name, "baz"); + + ret = sqfs_tree_node_get_path(n1, &str); + TEST_EQUAL_I(ret, 0); + TEST_NOT_NULL(str); + TEST_STR_EQUAL(str, "/bar"); + sqfs_free(str); + + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, 0); + TEST_NOT_NULL(str); + TEST_STR_EQUAL(str, "/bar/baz"); + sqfs_free(str); + + /* root node must not have a name */ + strcpy((char *)n0->name, "foo"); + + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, SQFS_ERROR_ARG_INVALID); + TEST_NULL(str); + n0->name[0] = '\0'; + + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, 0); + TEST_NOT_NULL(str); + TEST_STR_EQUAL(str, "/bar/baz"); + sqfs_free(str); + + /* non-root nodes must have names */ + n1->name[0] = '\0'; + + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, SQFS_ERROR_CORRUPTED); + TEST_NULL(str); + n1->name[0] = 'b'; + + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, 0); + TEST_NOT_NULL(str); + TEST_STR_EQUAL(str, "/bar/baz"); + sqfs_free(str); + + /* some names are illegal */ + strcpy((char *)n1->name, ".."); + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, SQFS_ERROR_CORRUPTED); + TEST_NULL(str); + + strcpy((char *)n1->name, "."); + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, SQFS_ERROR_CORRUPTED); + TEST_NULL(str); + + strcpy((char *)n1->name, "a/b"); + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, SQFS_ERROR_CORRUPTED); + TEST_NULL(str); + + strcpy((char *)n1->name, "bar"); + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, 0); + TEST_NOT_NULL(str); + TEST_STR_EQUAL(str, "/bar/baz"); + sqfs_free(str); + + /* link loops must be detected */ + n0->parent = n2; + strcpy((char *)n0->name, "foo"); + + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, SQFS_ERROR_LINK_LOOP); + TEST_NULL(str); + + n0->parent = NULL; + n0->name[0] = '\0'; + + ret = sqfs_tree_node_get_path(n2, &str); + TEST_EQUAL_I(ret, 0); + TEST_NOT_NULL(str); + TEST_STR_EQUAL(str, "/bar/baz"); + sqfs_free(str); + + /* cleanup */ + free(n0); + free(n1); + free(n2); + return EXIT_SUCCESS; +} diff --git a/lib/sqfs/Makemodule.am b/lib/sqfs/Makemodule.am index 3d61cd5..00105e8 100644 --- a/lib/sqfs/Makemodule.am +++ b/lib/sqfs/Makemodule.am @@ -19,7 +19,6 @@ libsquashfs_la_SOURCES = $(LIBSQFS_HEARDS) lib/sqfs/src/id_table.c \ lib/sqfs/src/dir_writer.c lib/sqfs/src/xattr/xattr_reader.c \ lib/sqfs/src/read_table.c lib/sqfs/src/comp/compressor.c \ lib/sqfs/src/comp/internal.h lib/sqfs/src/dir_reader/dir_reader.c \ - lib/sqfs/src/dir_reader/read_tree.c lib/sqfs/src/dir_reader/get_path.c \ lib/sqfs/src/dir_reader/internal.h lib/sqfs/src/inode.c \ lib/sqfs/src/xattr/xattr_writer.c \ lib/sqfs/src/xattr/xattr_writer_flush.c \ @@ -125,9 +124,6 @@ test_xattr_writer_LDADD = libsquashfs.la libcompat.a xattr_benchmark_SOURCES = lib/sqfs/test/xattr_benchmark.c xattr_benchmark_LDADD = libcommon.a libsquashfs.la libcompat.a -test_get_node_path_SOURCES = lib/sqfs/test/get_node_path.c -test_get_node_path_LDADD = libcommon.a libsquashfs.la libcompat.a - test_istream_read_SOURCES = lib/sqfs/test/istream_read.c test_istream_read_LDADD = libio.a libsquashfs.la libutil.a libcompat.a @@ -144,7 +140,7 @@ test_hl_dir_SOURCES = lib/sqfs/test/hl_dir.c test_hl_dir_LDADD = libsquashfs.la libio.a libutil.a libcompat.a LIBSQFS_TESTS = \ - test_abi test_xattr test_table test_xattr_writer test_get_node_path \ + test_abi test_xattr test_table test_xattr_writer \ test_istream_read test_istream_skip test_stream_splice test_rec_dir \ test_hl_dir noinst_PROGRAMS += xattr_benchmark diff --git a/lib/sqfs/src/dir_reader/get_path.c b/lib/sqfs/src/dir_reader/get_path.c deleted file mode 100644 index 847bfd3..0000000 --- a/lib/sqfs/src/dir_reader/get_path.c +++ /dev/null @@ -1,81 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * get_path.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#define SQFS_BUILDING_DLL -#include "internal.h" - -#include -#include - -int sqfs_tree_node_get_path(const sqfs_tree_node_t *node, char **out) -{ - const sqfs_tree_node_t *it; - size_t clen, len = 0; - char *str, *ptr; - - *out = NULL; - - if (node == NULL) - return SQFS_ERROR_ARG_INVALID; - - for (it = node; it->parent != NULL; it = it->parent) { - if (it->parent == node) - return SQFS_ERROR_LINK_LOOP; - - /* non-root nodes must have a valid name */ - clen = strlen((const char *)it->name); - - if (clen == 0) - return SQFS_ERROR_CORRUPTED; - - if (strchr((const char *)it->name, '/') != NULL) - return SQFS_ERROR_CORRUPTED; - - if (it->name[0] == '.') { - if (clen == 1 || (clen == 2 && it->name[1] == '.')) - return SQFS_ERROR_CORRUPTED; - } - - /* compute total path length */ - if (SZ_ADD_OV(clen, 1, &clen)) - return SQFS_ERROR_OVERFLOW; - - if (SZ_ADD_OV(len, clen, &len)) - return SQFS_ERROR_OVERFLOW; - } - - /* root node must not have a name */ - if (it->name[0] != '\0') - return SQFS_ERROR_ARG_INVALID; - - /* generate the path */ - if (node->parent == NULL) { - str = strdup("/"); - if (str == NULL) - return SQFS_ERROR_ALLOC; - } else { - if (SZ_ADD_OV(len, 1, &len)) - return SQFS_ERROR_OVERFLOW; - - str = malloc(len); - if (str == NULL) - return SQFS_ERROR_ALLOC; - - ptr = str + len - 1; - *ptr = '\0'; - - for (it = node; it->parent != NULL; it = it->parent) { - len = strlen((const char *)it->name); - ptr -= len; - - memcpy(ptr, (const char *)it->name, len); - *(--ptr) = '/'; - } - } - - *out = str; - return 0; -} diff --git a/lib/sqfs/src/dir_reader/read_tree.c b/lib/sqfs/src/dir_reader/read_tree.c deleted file mode 100644 index 7d6bf67..0000000 --- a/lib/sqfs/src/dir_reader/read_tree.c +++ /dev/null @@ -1,288 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * read_tree.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#define SQFS_BUILDING_DLL -#include "internal.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); - default: - break; - } - - return 0; -} - -static bool would_be_own_parent(sqfs_tree_node_t *parent, sqfs_tree_node_t *n) -{ - sqfs_u32 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_node_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, - SQFS_DIR_OPEN_NO_DOT_ENTRIES); - 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 = root->children->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; - - if (!root) - return; - - 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_node_t *ent; - const char *ptr; - int ret; - - if (flags & ~SQFS_TREE_ALL_FLAGS) - return SQFS_ERROR_UNSUPPORTED; - - 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 == '/') { - while (*path == '/') - ++path; - continue; - } - - ret = sqfs_dir_reader_open_dir(rd, tail->inode, - SQFS_DIR_OPEN_NO_DOT_ENTRIES); - if (ret) - goto fail; - - 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, - SQFS_DIR_OPEN_NO_DOT_ENTRIES); - 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; -} diff --git a/lib/sqfs/test/get_node_path.c b/lib/sqfs/test/get_node_path.c deleted file mode 100644 index c76cc1c..0000000 --- a/lib/sqfs/test/get_node_path.c +++ /dev/null @@ -1,132 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * get_node_path.c - * - * Copyright (C) 2022 David Oberhollenzer - */ -#include "config.h" -#include "compat.h" -#include "util/test.h" - -#include "sqfs/dir_reader.h" -#include "sqfs/error.h" - -int main(int argc, char **argv) -{ - sqfs_tree_node_t *n0, *n1, *n2; - char *str; - int ret; - (void)argc; - (void)argv; - - n0 = calloc(1, sizeof(*n0) + 16); - TEST_NOT_NULL(n0); - - n1 = calloc(1, sizeof(*n1) + 16); - TEST_NOT_NULL(n1); - - n2 = calloc(1, sizeof(*n2) + 16); - TEST_NOT_NULL(n2); - - /* no parent -> must return "/" */ - ret = sqfs_tree_node_get_path(n0, &str); - TEST_EQUAL_I(ret, 0); - TEST_NOT_NULL(str); - TEST_STR_EQUAL(str, "/"); - sqfs_free(str); - - /* hiearchy levels */ - n1->parent = n0; - n0->children = n1; - strcpy((char *)n1->name, "bar"); - - n2->parent = n1; - n1->children = n2; - strcpy((char *)n2->name, "baz"); - - ret = sqfs_tree_node_get_path(n1, &str); - TEST_EQUAL_I(ret, 0); - TEST_NOT_NULL(str); - TEST_STR_EQUAL(str, "/bar"); - sqfs_free(str); - - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, 0); - TEST_NOT_NULL(str); - TEST_STR_EQUAL(str, "/bar/baz"); - sqfs_free(str); - - /* root node must not have a name */ - strcpy((char *)n0->name, "foo"); - - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, SQFS_ERROR_ARG_INVALID); - TEST_NULL(str); - n0->name[0] = '\0'; - - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, 0); - TEST_NOT_NULL(str); - TEST_STR_EQUAL(str, "/bar/baz"); - sqfs_free(str); - - /* non-root nodes must have names */ - n1->name[0] = '\0'; - - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, SQFS_ERROR_CORRUPTED); - TEST_NULL(str); - n1->name[0] = 'b'; - - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, 0); - TEST_NOT_NULL(str); - TEST_STR_EQUAL(str, "/bar/baz"); - sqfs_free(str); - - /* some names are illegal */ - strcpy((char *)n1->name, ".."); - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, SQFS_ERROR_CORRUPTED); - TEST_NULL(str); - - strcpy((char *)n1->name, "."); - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, SQFS_ERROR_CORRUPTED); - TEST_NULL(str); - - strcpy((char *)n1->name, "a/b"); - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, SQFS_ERROR_CORRUPTED); - TEST_NULL(str); - - strcpy((char *)n1->name, "bar"); - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, 0); - TEST_NOT_NULL(str); - TEST_STR_EQUAL(str, "/bar/baz"); - sqfs_free(str); - - /* link loops must be detected */ - n0->parent = n2; - strcpy((char *)n0->name, "foo"); - - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, SQFS_ERROR_LINK_LOOP); - TEST_NULL(str); - - n0->parent = NULL; - n0->name[0] = '\0'; - - ret = sqfs_tree_node_get_path(n2, &str); - TEST_EQUAL_I(ret, 0); - TEST_NOT_NULL(str); - TEST_STR_EQUAL(str, "/bar/baz"); - sqfs_free(str); - - /* cleanup */ - free(n0); - free(n1); - free(n2); - return EXIT_SUCCESS; -} -- cgit v1.2.3