Generate a flat inode table from the fstree ahead of time

Instead of allocating inode numbers as we go, generate and populat an
inode table from the fstree ahead of time. This makes processing nodes
a little bit simpler and we will need that table anyway for NFS export
support later on.

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

7 files changed, 88 insertions, 45 deletions

diff --git a/include/fstree.h b/include/fstree.h
index 3c9e2af..284792b 100644
--- a/include/fstree.h
+++ b/include/fstree.h
@@ -130,7 +130,6 @@ struct tree_node_t {
 	   Generated on the fly when writing inodes. */
 	uint64_t inode_ref;
 
-	/* Inode number. Generated on the fly when writing inodes. */
 	uint32_t inode_num;
 
 	/* Type specific data. Pointers are into payload area blow. */
@@ -151,12 +150,16 @@ struct fstree_t {
 	uint32_t default_mode;
 	uint32_t default_mtime;
 	size_t block_size;
+	size_t inode_tbl_size;
 
 	str_table_t xattr_keys;
 	str_table_t xattr_values;
 
 	tree_node_t *root;
 	tree_xattr_t *xattr;
+
+	/* linear array of tree nodes. inode number is array index */
+	tree_node_t **inode_table;
 };
 
 /*
@@ -248,4 +251,7 @@ void fstree_sort(fstree_t *fs);
    Returns 0 on success. Internally prints errors to stderr. */
 int fstree_relabel_selinux(fstree_t *fs, const char *filename);
 
+/* Returns 0 on success. Prints to stderr on failure */
+int fstree_gen_inode_table(fstree_t *fs);
+
 #endif /* FSTREE_H */
diff --git a/lib/Makemodule.am b/lib/Makemodule.am
index 0120347..536cad0 100644
--- a/lib/Makemodule.am
+++ b/lib/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 lib/fstree/fstree_from_dir.c
-libfstree_a_SOURCES += include/fstree.h
+libfstree_a_SOURCES += lib/fstree/gen_inode_table.c include/fstree.h
 libfstree_a_CFLAGS = $(AM_CFLAGS)
 libfstree_a_CPPFLAGS = $(AM_CPPFLAGS)
 
diff --git a/lib/fstree/fstree.c b/lib/fstree/fstree.c
index 0c3f13d..56ca528 100644
--- a/lib/fstree/fstree.c
+++ b/lib/fstree/fstree.c
@@ -352,5 +352,6 @@ void fstree_cleanup(fstree_t *fs)
 	str_table_cleanup(&fs->xattr_keys);
 	str_table_cleanup(&fs->xattr_values);
 	free_recursive(fs->root);
+	free(fs->inode_table);
 	memset(fs, 0, sizeof(*fs));
 }
diff --git a/lib/fstree/gen_inode_table.c b/lib/fstree/gen_inode_table.c
new file mode 100644
index 0000000..2782c6d
--- /dev/null
+++ b/lib/fstree/gen_inode_table.c
@@ -0,0 +1,67 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#include "fstree.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+
+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] = it;
+	}
+}
+
+int fstree_gen_inode_table(fstree_t *fs)
+{
+	size_t inum = 2;
+
+	fs->inode_tbl_size = count_nodes(fs->root) + 2;
+	fs->inode_table = calloc(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] = fs->root;
+	return 0;
+}
diff --git a/mkfs/meta.c b/mkfs/meta.c
index 1510524..9c305b1 100644
--- a/mkfs/meta.c
+++ b/mkfs/meta.c
@@ -64,9 +64,6 @@ static int write_inode(sqfs_info_t *info, meta_writer_t *im, meta_writer_t *dm,
 
 	meta_writer_get_position(im, &block, &offset);
 	node->inode_ref = (block << 16) | offset;
-	node->inode_num = info->inode_counter++;
-
-	info->super.inode_count += 1;
 
 	type = get_type(node);
 
@@ -293,44 +290,13 @@ out_file_blocks:
 	return 0;
 }
 
-static int write_child_inodes(sqfs_info_t *info, meta_writer_t *im,
-			      meta_writer_t *dm, tree_node_t *root)
-{
-	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))
-				continue;
-
-			if (write_child_inodes(info, im, dm, it))
-				return -1;
-		}
-	}
-
-	for (it = root->data.dir->children; it != NULL; it = it->next) {
-		if (write_inode(info, im, dm, it))
-			return -1;
-	}
-
-	return 0;
-}
-
 int sqfs_write_inodes(sqfs_info_t *info)
 {
 	meta_writer_t *im, *dm;
 	uint8_t buffer[1024];
 	uint32_t offset;
 	uint64_t block;
-	size_t diff;
+	size_t i, diff;
 	ssize_t ret;
 	FILE *tmp;
 	int tmpfd;
@@ -351,13 +317,12 @@ int sqfs_write_inodes(sqfs_info_t *info)
 	if (dm == NULL)
 		goto fail_im;
 
-	info->inode_counter = 2;
-
-	if (write_child_inodes(info, im, dm, info->fs.root))
-		goto fail;
-
-	if (write_inode(info, im, dm, info->fs.root))
-		goto fail;
+	for (i = 0; i < info->fs.inode_tbl_size; ++i) {
+		if (info->fs.inode_table[i] != NULL) {
+			if (write_inode(info, im, dm, info->fs.inode_table[i]))
+				goto fail;
+		}
+	}
 
 	if (meta_writer_flush(im))
 		goto fail;
diff --git a/mkfs/mkfs.c b/mkfs/mkfs.c
index a6f19f1..405d6fd 100644
--- a/mkfs/mkfs.c
+++ b/mkfs/mkfs.c
@@ -89,6 +89,11 @@ int main(int argc, char **argv)
 
 	fstree_sort(&info.fs);
 
+	if (fstree_gen_inode_table(&info.fs))
+		goto out_fstree;
+
+	info.super.inode_count = info.fs.inode_tbl_size - 2;
+
 	info.cmp = compressor_create(info.super.compression_id, true,
 				     info.super.block_size,
 				     info.opt.comp_extra);
diff --git a/mkfs/mkfs.h b/mkfs/mkfs.h
index 15d349e..e3e3c5d 100644
--- a/mkfs/mkfs.h
+++ b/mkfs/mkfs.h
@@ -65,7 +65,6 @@ typedef struct {
 	size_t frag_offset;
 
 	id_table_t idtbl;
-	size_t inode_counter;
 
 	compressor_t *cmp;
 } sqfs_info_t;