From caf350448c0020f95b9bfdd65770d86faf548549 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sun, 15 Dec 2019 19:29:34 +0100 Subject: Remove fstree inode table Signed-off-by: David Oberhollenzer --- include/fstree.h | 14 +++--- lib/common/writer.c | 5 +-- lib/fstree/Makemodule.am | 2 +- lib/fstree/fstree.c | 1 - lib/fstree/gen_inode_numbers.c | 49 +++++++++++++++++++++ lib/fstree/gen_inode_table.c | 74 ------------------------------- tests/Makemodule.am | 8 ++-- tests/gen_inode_numbers.c | 92 +++++++++++++++++++++++++++++++++++++++ tests/gen_inode_table.c | 99 ------------------------------------------ 9 files changed, 156 insertions(+), 188 deletions(-) create mode 100644 lib/fstree/gen_inode_numbers.c delete mode 100644 lib/fstree/gen_inode_table.c create mode 100644 tests/gen_inode_numbers.c delete mode 100644 tests/gen_inode_table.c diff --git a/include/fstree.h b/include/fstree.h index 44428cd..ab44e3e 100644 --- a/include/fstree.h +++ b/include/fstree.h @@ -83,13 +83,10 @@ struct tree_node_t { struct fstree_t { struct stat defaults; size_t block_size; - size_t inode_tbl_size; + size_t unique_inode_count; tree_node_t *root; - /* linear array of tree nodes. inode number is array index */ - tree_node_t **inode_table; - /* linear linked list of all regular files */ file_info_t *files; }; @@ -157,8 +154,13 @@ tree_node_t *fstree_add_generic(fstree_t *fs, const char *path, */ int fstree_from_file(fstree_t *fs, const char *filename, FILE *fp); -/* Returns 0 on success. Prints to stderr on failure */ -int fstree_gen_inode_table(fstree_t *fs); +/* + Allocates inode numbers for all nodes. Directory entries are numbered in + ascending order. + + The total inode count is stored in unique_inode_count. + */ +void fstree_gen_inode_numbers(fstree_t *fs); void fstree_gen_file_list(fstree_t *fs); diff --git a/lib/common/writer.c b/lib/common/writer.c index 0b7f378..087ee3c 100644 --- a/lib/common/writer.c +++ b/lib/common/writer.c @@ -214,10 +214,9 @@ int sqfs_writer_finish(sqfs_writer_t *sqfs, const sqfs_writer_cfg_t *cfg) fputs("Writing inodes and directories...\n", stdout); tree_node_sort_recursive(sqfs->fs.root); - if (fstree_gen_inode_table(&sqfs->fs)) - return -1; + fstree_gen_inode_numbers(&sqfs->fs); - sqfs->super.inode_count = sqfs->fs.inode_tbl_size; + sqfs->super.inode_count = sqfs->fs.unique_inode_count; if (sqfs_serialize_fstree(cfg->filename, sqfs)) return -1; diff --git a/lib/fstree/Makemodule.am b/lib/fstree/Makemodule.am index 6638480..bb17d24 100644 --- a/lib/fstree/Makemodule.am +++ b/lib/fstree/Makemodule.am @@ -1,6 +1,6 @@ libfstree_a_SOURCES = lib/fstree/fstree.c lib/fstree/fstree_from_file.c libfstree_a_SOURCES += lib/fstree/fstree_sort.c -libfstree_a_SOURCES += lib/fstree/gen_inode_table.c lib/fstree/get_path.c +libfstree_a_SOURCES += lib/fstree/gen_inode_numbers.c lib/fstree/get_path.c libfstree_a_SOURCES += lib/fstree/mknode.c libfstree_a_SOURCES += lib/fstree/add_by_path.c libfstree_a_SOURCES += include/fstree.h diff --git a/lib/fstree/fstree.c b/lib/fstree/fstree.c index ad48508..90e14ce 100644 --- a/lib/fstree/fstree.c +++ b/lib/fstree/fstree.c @@ -128,6 +128,5 @@ int fstree_init(fstree_t *fs, char *defaults) void fstree_cleanup(fstree_t *fs) { free_recursive(fs->root); - free(fs->inode_table); memset(fs, 0, sizeof(*fs)); } diff --git a/lib/fstree/gen_inode_numbers.c b/lib/fstree/gen_inode_numbers.c new file mode 100644 index 0000000..35dbc7a --- /dev/null +++ b/lib/fstree/gen_inode_numbers.c @@ -0,0 +1,49 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * gen_inode_numbers.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" + +#include "fstree.h" + +#include +#include + +static void map_child_nodes(fstree_t *fs, tree_node_t *root, size_t *counter) +{ + bool has_subdirs = false; + tree_node_t *it; + + for (it = root->data.dir.children; it != NULL; it = it->next) { + if (S_ISDIR(it->mode)) { + has_subdirs = true; + break; + } + } + + if (has_subdirs) { + for (it = root->data.dir.children; it != NULL; it = it->next) { + if (S_ISDIR(it->mode)) + map_child_nodes(fs, it, counter); + } + } + + for (it = root->data.dir.children; it != NULL; it = it->next) { + fs->unique_inode_count += 1; + + it->inode_num = *counter; + *counter += 1; + } +} + +void fstree_gen_inode_numbers(fstree_t *fs) +{ + size_t inum = 1; + + fs->unique_inode_count = 0; + map_child_nodes(fs, fs->root, &inum); + fs->root->inode_num = inum; + fs->unique_inode_count += 1; +} diff --git a/lib/fstree/gen_inode_table.c b/lib/fstree/gen_inode_table.c deleted file mode 100644 index 006029f..0000000 --- a/lib/fstree/gen_inode_table.c +++ /dev/null @@ -1,74 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * gen_inode_table.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include "fstree.h" - -#include -#include - -static size_t count_nodes(tree_node_t *root) -{ - tree_node_t *n = root->data.dir.children; - size_t count = 1; - - while (n != NULL) { - if (S_ISDIR(n->mode)) { - count += count_nodes(n); - } else { - ++count; - } - n = n->next; - } - - return count; -} - -static void map_child_nodes(fstree_t *fs, tree_node_t *root, size_t *counter) -{ - bool has_subdirs = false; - tree_node_t *it; - - for (it = root->data.dir.children; it != NULL; it = it->next) { - if (S_ISDIR(it->mode)) { - has_subdirs = true; - break; - } - } - - if (has_subdirs) { - for (it = root->data.dir.children; it != NULL; it = it->next) { - if (S_ISDIR(it->mode)) - map_child_nodes(fs, it, counter); - } - } - - for (it = root->data.dir.children; it != NULL; it = it->next) { - it->inode_num = *counter; - *counter += 1; - - fs->inode_table[it->inode_num - 1] = it; - } -} - -int fstree_gen_inode_table(fstree_t *fs) -{ - size_t inum = 1; - - fs->inode_tbl_size = count_nodes(fs->root); - fs->inode_table = calloc(1, sizeof(tree_node_t*) * fs->inode_tbl_size); - - if (fs->inode_table == NULL) { - perror("allocating inode table"); - return -1; - } - - map_child_nodes(fs, fs->root, &inum); - fs->root->inode_num = inum; - fs->inode_table[inum - 1] = fs->root; - return 0; -} diff --git a/tests/Makemodule.am b/tests/Makemodule.am index fc27de0..2fb7654 100644 --- a/tests/Makemodule.am +++ b/tests/Makemodule.am @@ -27,8 +27,8 @@ test_mknode_reg_LDADD = libfstree.a libcompat.a test_mknode_dir_SOURCES = tests/mknode_dir.c test_mknode_dir_LDADD = libfstree.a libcompat.a -test_gen_inode_table_SOURCES = tests/gen_inode_table.c -test_gen_inode_table_LDADD = libfstree.a libcompat.a +test_gen_inode_numbers_SOURCES = tests/gen_inode_numbers.c +test_gen_inode_numbers_LDADD = libfstree.a libcompat.a test_add_by_path_SOURCES = tests/add_by_path.c test_add_by_path_LDADD = libfstree.a libcompat.a @@ -93,7 +93,7 @@ tar_fuzz_SOURCES = tests/tar_fuzz.c tar_fuzz_LDADD = libtar.a libcompat.a check_PROGRAMS += test_mknode_simple test_mknode_slink test_mknode_reg -check_PROGRAMS += test_mknode_dir test_gen_inode_table test_add_by_path +check_PROGRAMS += test_mknode_dir test_gen_inode_numbers test_add_by_path check_PROGRAMS += test_get_path test_fstree_sort test_fstree_from_file check_PROGRAMS += test_fstree_init test_tar_ustar test_tar_pax test_tar_gnu check_PROGRAMS += test_tar_sparse_gnu test_tar_sparse_gnu1 test_tar_sparse_gnu2 @@ -104,7 +104,7 @@ check_SCRIPTS += tests/cantrbry.sh tests/test_tar_sqfs.sh noinst_PROGRAMS += fstree_fuzz tar_fuzz TESTS += test_mknode_simple test_mknode_slink -TESTS += test_mknode_reg test_mknode_dir test_gen_inode_table +TESTS += test_mknode_reg test_mknode_dir test_gen_inode_numbers TESTS += test_add_by_path test_get_path test_fstree_sort test_fstree_from_file TESTS += test_fstree_init test_tar_ustar test_tar_pax TESTS += test_tar_gnu test_tar_sparse_gnu test_tar_sparse_gnu1 diff --git a/tests/gen_inode_numbers.c b/tests/gen_inode_numbers.c new file mode 100644 index 0000000..e16abbe --- /dev/null +++ b/tests/gen_inode_numbers.c @@ -0,0 +1,92 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * gen_inode_table.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" + +#include "fstree.h" + +#include +#include +#include + +static tree_node_t *gen_node(tree_node_t *parent, const char *name) +{ + struct stat sb; + + memset(&sb, 0, sizeof(sb)); + sb.st_mode = S_IFDIR | 0755; + + return fstree_mknode(parent, name, strlen(name), NULL, &sb); +} + +static void check_children_before_root(tree_node_t *root) +{ + tree_node_t *n; + + for (n = root->data.dir.children; n != NULL; n = n->next) + assert(n->inode_num < root->inode_num); + + for (n = root->data.dir.children; n != NULL; n = n->next) + check_children_before_root(n); +} + +static void check_children_continuous(tree_node_t *root) +{ + tree_node_t *n; + + for (n = root->data.dir.children; n != NULL; n = n->next) { + if (n->next != NULL) { + assert(n->next->inode_num == (n->inode_num + 1)); + } + } + + for (n = root->data.dir.children; n != NULL; n = n->next) + check_children_continuous(n); +} + +int main(void) +{ + tree_node_t *a, *b, *c; + fstree_t fs; + + // inode table for the empty tree + assert(fstree_init(&fs, NULL) == 0); + fstree_gen_inode_numbers(&fs); + assert(fs.unique_inode_count == 1); + assert(fs.root->inode_num == 1); + fstree_cleanup(&fs); + + // tree with 2 levels under root, fan out 3 + assert(fstree_init(&fs, NULL) == 0); + + a = gen_node(fs.root, "a"); + b = gen_node(fs.root, "b"); + c = gen_node(fs.root, "c"); + assert(a != NULL); + assert(b != NULL); + assert(c != NULL); + + assert(gen_node(a, "a_a") != NULL); + assert(gen_node(a, "a_b") != NULL); + assert(gen_node(a, "a_c") != NULL); + + assert(gen_node(b, "b_a") != NULL); + assert(gen_node(b, "b_b") != NULL); + assert(gen_node(b, "b_c") != NULL); + + assert(gen_node(c, "c_a") != NULL); + assert(gen_node(c, "c_b") != NULL); + assert(gen_node(c, "c_c") != NULL); + + fstree_gen_inode_numbers(&fs); + assert(fs.unique_inode_count == 13); + + check_children_before_root(fs.root); + check_children_continuous(fs.root); + + fstree_cleanup(&fs); + return EXIT_SUCCESS; +} diff --git a/tests/gen_inode_table.c b/tests/gen_inode_table.c deleted file mode 100644 index d70f463..0000000 --- a/tests/gen_inode_table.c +++ /dev/null @@ -1,99 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * gen_inode_table.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include "fstree.h" - -#include -#include -#include - -static tree_node_t *gen_node(tree_node_t *parent, const char *name) -{ - struct stat sb; - - memset(&sb, 0, sizeof(sb)); - sb.st_mode = S_IFDIR | 0755; - - return fstree_mknode(parent, name, strlen(name), NULL, &sb); -} - -static void check_children_before_root(tree_node_t *root) -{ - tree_node_t *n; - - for (n = root->data.dir.children; n != NULL; n = n->next) - assert(n->inode_num < root->inode_num); - - for (n = root->data.dir.children; n != NULL; n = n->next) - check_children_before_root(n); -} - -static void check_children_continuous(tree_node_t *root) -{ - tree_node_t *n; - - for (n = root->data.dir.children; n != NULL; n = n->next) { - if (n->next != NULL) { - assert(n->next->inode_num == (n->inode_num + 1)); - } - } - - for (n = root->data.dir.children; n != NULL; n = n->next) - check_children_continuous(n); -} - -int main(void) -{ - tree_node_t *a, *b, *c; - unsigned int i; - fstree_t fs; - - // inode table for the empty tree - assert(fstree_init(&fs, NULL) == 0); - assert(fstree_gen_inode_table(&fs) == 0); - assert(fs.inode_tbl_size == 1); - assert(fs.root->inode_num == 1); - assert(fs.inode_table[0] == fs.root); - fstree_cleanup(&fs); - - // tree with 2 levels under root, fan out 3 - assert(fstree_init(&fs, NULL) == 0); - - a = gen_node(fs.root, "a"); - b = gen_node(fs.root, "b"); - c = gen_node(fs.root, "c"); - assert(a != NULL); - assert(b != NULL); - assert(c != NULL); - - assert(gen_node(a, "a_a") != NULL); - assert(gen_node(a, "a_b") != NULL); - assert(gen_node(a, "a_c") != NULL); - - assert(gen_node(b, "b_a") != NULL); - assert(gen_node(b, "b_b") != NULL); - assert(gen_node(b, "b_c") != NULL); - - assert(gen_node(c, "c_a") != NULL); - assert(gen_node(c, "c_b") != NULL); - assert(gen_node(c, "c_c") != NULL); - - assert(fstree_gen_inode_table(&fs) == 0); - assert(fs.inode_tbl_size == 13); - - for (i = 0; i < 13; ++i) { - assert(fs.inode_table[i] != NULL); - assert(fs.inode_table[i]->inode_num == i + 1); - } - - check_children_before_root(fs.root); - check_children_continuous(fs.root); - - fstree_cleanup(&fs); - return EXIT_SUCCESS; -} -- cgit v1.2.3