From 336a05a544ea8773653faa9a9d5078afaa839ff2 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Thu, 19 Sep 2019 18:28:48 +0200 Subject: Move "optimize unpack order" to from fstree to rdsquashfs Signed-off-by: David Oberhollenzer --- include/fstree.h | 7 --- lib/fstree/Makemodule.am | 1 - lib/fstree/optimize_unpack_order.c | 119 ------------------------------------- unpack/Makemodule.am | 2 +- unpack/optimize_unpack_order.c | 119 +++++++++++++++++++++++++++++++++++++ unpack/rdsquashfs.h | 2 + 6 files changed, 122 insertions(+), 128 deletions(-) delete mode 100644 lib/fstree/optimize_unpack_order.c create mode 100644 unpack/optimize_unpack_order.c diff --git a/include/fstree.h b/include/fstree.h index 05e1ebe..426964d 100644 --- a/include/fstree.h +++ b/include/fstree.h @@ -292,13 +292,6 @@ void tree_node_sort_recursive(tree_node_t *root); /* resolve a path to a tree node. Returns NULL on failure and sets errno */ tree_node_t *fstree_node_from_path(fstree_t *fs, const char *path); -/* - Optimize the order of the fstree file list for unpacking as to avoid - unpacking fragment blocks more than once and to improve locality when - fetching data from disk. - */ -file_info_t *optimize_unpack_order(fstree_t *fs); - /* Convert back to forward slashed, remove all preceeding and trailing slashes, collapse all sequences of slashes, remove all path components that are '.' diff --git a/lib/fstree/Makemodule.am b/lib/fstree/Makemodule.am index c3c56fb..00150fd 100644 --- a/lib/fstree/Makemodule.am +++ b/lib/fstree/Makemodule.am @@ -5,7 +5,6 @@ libfstree_a_SOURCES += lib/fstree/node_stat.c lib/fstree/mknode.c libfstree_a_SOURCES += lib/fstree/add_by_path.c lib/fstree/xattr.c libfstree_a_SOURCES += lib/fstree/node_from_path.c include/fstree.h libfstree_a_SOURCES += lib/fstree/gen_file_list.c -libfstree_a_SOURCES += lib/fstree/optimize_unpack_order.c libfstree_a_SOURCES += lib/fstree/canonicalize_name.c libfstree_a_SOURCES += lib/fstree/source_date_epoch.c libfstree_a_CFLAGS = $(AM_CFLAGS) $(LIBSELINUX_CFLAGS) diff --git a/lib/fstree/optimize_unpack_order.c b/lib/fstree/optimize_unpack_order.c deleted file mode 100644 index 972d4b3..0000000 --- a/lib/fstree/optimize_unpack_order.c +++ /dev/null @@ -1,119 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * optimize_unpack_order.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" -#include "fstree.h" - -static bool has_fragment(const fstree_t *fs, const file_info_t *file) -{ - if (file->size % fs->block_size == 0) - return false; - - return file->fragment_offset < fs->block_size && - (file->fragment != 0xFFFFFFFF); -} - -static int compare_files(const fstree_t *fs, const file_info_t *lhs, - const file_info_t *rhs) -{ - /* NOOP < everything else */ - if (lhs->input_file == NULL) - return rhs->input_file == NULL ? 0 : -1; - - if (rhs->input_file == NULL) - return 1; - - /* Files with fragments come first, ordered by ID. - In case of tie, files without data blocks come first, - and the others are ordered by start block. */ - if (has_fragment(fs, lhs)) { - if (!(has_fragment(fs, rhs))) - return -1; - - if (lhs->fragment < rhs->fragment) - return -1; - if (lhs->fragment > rhs->fragment) - return 1; - - if (lhs->size < fs->block_size) - return (rhs->size < fs->block_size) ? 0 : -1; - if (rhs->size < fs->block_size) - return 1; - goto order_by_start; - } - - if (has_fragment(fs, rhs)) - return 1; - - /* order the rest by start block */ -order_by_start: - return lhs->startblock < rhs->startblock ? -1 : - lhs->startblock > rhs->startblock ? 1 : 0; -} - -/* TODO: unify ad-hoc merge sort with the one in fstree_sort */ -static file_info_t *merge(const fstree_t *fs, file_info_t *lhs, - file_info_t *rhs) -{ - file_info_t *it; - file_info_t *head = NULL; - file_info_t **next_ptr = &head; - - while (lhs != NULL && rhs != NULL) { - if (compare_files(fs, lhs, rhs) <= 0) { - it = lhs; - lhs = lhs->next; - } else { - it = rhs; - rhs = rhs->next; - } - - *next_ptr = it; - next_ptr = &it->next; - } - - it = (lhs != NULL ? lhs : rhs); - *next_ptr = it; - return head; -} - -static file_info_t *list_sort(const fstree_t *fs, file_info_t *head) -{ - file_info_t *it, *half, *prev; - - it = half = prev = head; - while (it != NULL) { - prev = half; - half = half->next; - it = it->next; - if (it != NULL) { - it = it->next; - } - } - - // half refers to the (count/2)'th element ROUNDED UP. - // It will be null therefore only in the empty and the - // single element list - if (half == NULL) { - return head; - } - - prev->next = NULL; - - return merge(fs, list_sort(fs, head), list_sort(fs, half)); -} - -file_info_t *optimize_unpack_order(fstree_t *fs) -{ - file_info_t *file_list; - - file_list = list_sort(fs, fs->files); - while (file_list != NULL && file_list->input_file == NULL) - file_list = file_list->next; - - fs->files = NULL; - return file_list; -} diff --git a/unpack/Makemodule.am b/unpack/Makemodule.am index b60292d..964cc05 100644 --- a/unpack/Makemodule.am +++ b/unpack/Makemodule.am @@ -1,7 +1,7 @@ rdsquashfs_SOURCES = unpack/rdsquashfs.c unpack/rdsquashfs.h rdsquashfs_SOURCES += unpack/list_files.c unpack/options.c rdsquashfs_SOURCES += unpack/restore_fstree.c unpack/describe.c -rdsquashfs_SOURCES += unpack/fill_files.c +rdsquashfs_SOURCES += unpack/fill_files.c unpack/optimize_unpack_order.c rdsquashfs_LDADD = libsqfshelper.a libsquashfs.la libfstree.a libutil.la bin_PROGRAMS += rdsquashfs diff --git a/unpack/optimize_unpack_order.c b/unpack/optimize_unpack_order.c new file mode 100644 index 0000000..a76dd51 --- /dev/null +++ b/unpack/optimize_unpack_order.c @@ -0,0 +1,119 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * optimize_unpack_order.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" +#include "rdsquashfs.h" + +static bool has_fragment(const fstree_t *fs, const file_info_t *file) +{ + if (file->size % fs->block_size == 0) + return false; + + return file->fragment_offset < fs->block_size && + (file->fragment != 0xFFFFFFFF); +} + +static int compare_files(const fstree_t *fs, const file_info_t *lhs, + const file_info_t *rhs) +{ + /* NOOP < everything else */ + if (lhs->input_file == NULL) + return rhs->input_file == NULL ? 0 : -1; + + if (rhs->input_file == NULL) + return 1; + + /* Files with fragments come first, ordered by ID. + In case of tie, files without data blocks come first, + and the others are ordered by start block. */ + if (has_fragment(fs, lhs)) { + if (!(has_fragment(fs, rhs))) + return -1; + + if (lhs->fragment < rhs->fragment) + return -1; + if (lhs->fragment > rhs->fragment) + return 1; + + if (lhs->size < fs->block_size) + return (rhs->size < fs->block_size) ? 0 : -1; + if (rhs->size < fs->block_size) + return 1; + goto order_by_start; + } + + if (has_fragment(fs, rhs)) + return 1; + + /* order the rest by start block */ +order_by_start: + return lhs->startblock < rhs->startblock ? -1 : + lhs->startblock > rhs->startblock ? 1 : 0; +} + +/* TODO: unify ad-hoc merge sort with the one in fstree_sort */ +static file_info_t *merge(const fstree_t *fs, file_info_t *lhs, + file_info_t *rhs) +{ + file_info_t *it; + file_info_t *head = NULL; + file_info_t **next_ptr = &head; + + while (lhs != NULL && rhs != NULL) { + if (compare_files(fs, lhs, rhs) <= 0) { + it = lhs; + lhs = lhs->next; + } else { + it = rhs; + rhs = rhs->next; + } + + *next_ptr = it; + next_ptr = &it->next; + } + + it = (lhs != NULL ? lhs : rhs); + *next_ptr = it; + return head; +} + +static file_info_t *list_sort(const fstree_t *fs, file_info_t *head) +{ + file_info_t *it, *half, *prev; + + it = half = prev = head; + while (it != NULL) { + prev = half; + half = half->next; + it = it->next; + if (it != NULL) { + it = it->next; + } + } + + // half refers to the (count/2)'th element ROUNDED UP. + // It will be null therefore only in the empty and the + // single element list + if (half == NULL) { + return head; + } + + prev->next = NULL; + + return merge(fs, list_sort(fs, head), list_sort(fs, half)); +} + +file_info_t *optimize_unpack_order(fstree_t *fs) +{ + file_info_t *file_list; + + file_list = list_sort(fs, fs->files); + while (file_list != NULL && file_list->input_file == NULL) + file_list = file_list->next; + + fs->files = NULL; + return file_list; +} diff --git a/unpack/rdsquashfs.h b/unpack/rdsquashfs.h index b5570dd..065f4aa 100644 --- a/unpack/rdsquashfs.h +++ b/unpack/rdsquashfs.h @@ -74,4 +74,6 @@ int describe_tree(tree_node_t *root, const char *unpack_root); void process_command_line(options_t *opt, int argc, char **argv); +file_info_t *optimize_unpack_order(fstree_t *fs); + #endif /* RDSQUASHFS_H */ -- cgit v1.2.3