From cdccc69c62579b0c13b35fad0728079652b8f3c9 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Tue, 31 Jan 2023 11:21:30 +0100 Subject: Move library source into src sub-directory Signed-off-by: David Oberhollenzer --- lib/util/Makemodule.am | 35 ++-- lib/util/alloc.c | 37 ---- lib/util/array.c | 115 ----------- lib/util/base64_decode.c | 103 ---------- lib/util/canonicalize_name.c | 60 ------ lib/util/fast_urem_by_const.h | 77 ------- lib/util/file_cmp.c | 41 ---- lib/util/filename_sane.c | 78 ------- lib/util/hash_table.c | 417 -------------------------------------- lib/util/hex_decode.c | 34 ---- lib/util/is_memory_zero.c | 54 ----- lib/util/mempool.c | 216 -------------------- lib/util/mkdir_p.c | 170 ---------------- lib/util/rbtree.c | 267 ------------------------ lib/util/source_date_epoch.c | 44 ---- lib/util/src/alloc.c | 37 ++++ lib/util/src/array.c | 115 +++++++++++ lib/util/src/base64_decode.c | 103 ++++++++++ lib/util/src/canonicalize_name.c | 60 ++++++ lib/util/src/fast_urem_by_const.h | 77 +++++++ lib/util/src/file_cmp.c | 41 ++++ lib/util/src/filename_sane.c | 78 +++++++ lib/util/src/hash_table.c | 417 ++++++++++++++++++++++++++++++++++++++ lib/util/src/hex_decode.c | 34 ++++ lib/util/src/is_memory_zero.c | 54 +++++ lib/util/src/mempool.c | 216 ++++++++++++++++++++ lib/util/src/mkdir_p.c | 170 ++++++++++++++++ lib/util/src/rbtree.c | 267 ++++++++++++++++++++++++ lib/util/src/source_date_epoch.c | 44 ++++ lib/util/src/str_table.c | 183 +++++++++++++++++ lib/util/src/threadpool.c | 392 +++++++++++++++++++++++++++++++++++ lib/util/src/threadpool_serial.c | 162 +++++++++++++++ lib/util/src/xxhash.c | 112 ++++++++++ lib/util/str_table.c | 183 ----------------- lib/util/threadpool.c | 392 ----------------------------------- lib/util/threadpool_serial.c | 162 --------------- lib/util/xxhash.c | 112 ---------- 37 files changed, 2576 insertions(+), 2583 deletions(-) delete mode 100644 lib/util/alloc.c delete mode 100644 lib/util/array.c delete mode 100644 lib/util/base64_decode.c delete mode 100644 lib/util/canonicalize_name.c delete mode 100644 lib/util/fast_urem_by_const.h delete mode 100644 lib/util/file_cmp.c delete mode 100644 lib/util/filename_sane.c delete mode 100644 lib/util/hash_table.c delete mode 100644 lib/util/hex_decode.c delete mode 100644 lib/util/is_memory_zero.c delete mode 100644 lib/util/mempool.c delete mode 100644 lib/util/mkdir_p.c delete mode 100644 lib/util/rbtree.c delete mode 100644 lib/util/source_date_epoch.c create mode 100644 lib/util/src/alloc.c create mode 100644 lib/util/src/array.c create mode 100644 lib/util/src/base64_decode.c create mode 100644 lib/util/src/canonicalize_name.c create mode 100644 lib/util/src/fast_urem_by_const.h create mode 100644 lib/util/src/file_cmp.c create mode 100644 lib/util/src/filename_sane.c create mode 100644 lib/util/src/hash_table.c create mode 100644 lib/util/src/hex_decode.c create mode 100644 lib/util/src/is_memory_zero.c create mode 100644 lib/util/src/mempool.c create mode 100644 lib/util/src/mkdir_p.c create mode 100644 lib/util/src/rbtree.c create mode 100644 lib/util/src/source_date_epoch.c create mode 100644 lib/util/src/str_table.c create mode 100644 lib/util/src/threadpool.c create mode 100644 lib/util/src/threadpool_serial.c create mode 100644 lib/util/src/xxhash.c delete mode 100644 lib/util/str_table.c delete mode 100644 lib/util/threadpool.c delete mode 100644 lib/util/threadpool_serial.c delete mode 100644 lib/util/xxhash.c (limited to 'lib/util') diff --git a/lib/util/Makemodule.am b/lib/util/Makemodule.am index ec38b7a..35e8078 100644 --- a/lib/util/Makemodule.am +++ b/lib/util/Makemodule.am @@ -1,21 +1,14 @@ -libutil_a_SOURCES = include/util/util.h include/util/str_table.h -libutil_a_SOURCES += include/util/hash_table.h include/util/test.h -libutil_a_SOURCES += lib/util/str_table.c lib/util/alloc.c -libutil_a_SOURCES += lib/util/rbtree.c include/util/rbtree.h -libutil_a_SOURCES += lib/util/array.c include/util/array.h -libutil_a_SOURCES += lib/util/xxhash.c lib/util/hash_table.c -libutil_a_SOURCES += lib/util/fast_urem_by_const.h -libutil_a_SOURCES += include/util/threadpool.h -libutil_a_SOURCES += include/util/w32threadwrap.h -libutil_a_SOURCES += lib/util/threadpool_serial.c -libutil_a_SOURCES += lib/util/is_memory_zero.c -libutil_a_SOURCES += lib/util/mkdir_p.c -libutil_a_SOURCES += lib/util/canonicalize_name.c -libutil_a_SOURCES += lib/util/filename_sane.c -libutil_a_SOURCES += lib/util/source_date_epoch.c -libutil_a_SOURCES += lib/util/file_cmp.c -libutil_a_SOURCES += lib/util/hex_decode.c -libutil_a_SOURCES += lib/util/base64_decode.c +libutil_a_SOURCES = include/util/util.h include/util/str_table.h \ + include/util/hash_table.h include/util/test.h include/util/rbtree.h \ + include/util/array.h include/util/threadpool.h \ + include/util/w32threadwrap.h include/util/mempool.h \ + lib/util/src/str_table.c lib/util/src/alloc.c lib/util/src/rbtree.c \ + lib/util/src/array.c lib/util/src/xxhash.c lib/util/src/hash_table.c \ + lib/util/src/fast_urem_by_const.h lib/util/src/threadpool_serial.c \ + lib/util/src/is_memory_zero.c lib/util/src/mkdir_p.c \ + lib/util/src/canonicalize_name.c lib/util/src/filename_sane.c \ + lib/util/src/source_date_epoch.c lib/util/src/file_cmp.c \ + lib/util/src/hex_decode.c lib/util/src/base64_decode.c libutil_a_CFLAGS = $(AM_CFLAGS) libutil_a_CPPFLAGS = $(AM_CPPFLAGS) @@ -24,18 +17,18 @@ libutil_a_CFLAGS += -DWINVER=0x0600 -D_WIN32_WINNT=0x0600 endif if HAVE_PTHREAD -libutil_a_SOURCES += lib/util/threadpool.c +libutil_a_SOURCES += lib/util/src/threadpool.c libutil_a_CFLAGS += $(PTHREAD_CFLAGS) else if WINDOWS -libutil_a_SOURCES += lib/util/threadpool.c +libutil_a_SOURCES += lib/util/src/threadpool.c else libutil_a_CPPFLAGS += -DNO_THREAD_IMPL endif endif if CUSTOM_ALLOC -libutil_a_SOURCES += lib/util/mempool.c include/util/mempool.h +libutil_a_SOURCES += lib/util/src/mempool.c endif noinst_LIBRARIES += libutil.a diff --git a/lib/util/alloc.c b/lib/util/alloc.c deleted file mode 100644 index 359fef5..0000000 --- a/lib/util/alloc.c +++ /dev/null @@ -1,37 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * alloc.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include "util/util.h" - -#include -#include - -void *alloc_flex(size_t base_size, size_t item_size, size_t nmemb) -{ - size_t size; - - if (SZ_MUL_OV(nmemb, item_size, &size) || - SZ_ADD_OV(base_size, size, &size)) { - errno = EOVERFLOW; - return NULL; - } - - return calloc(1, size); -} - -void *alloc_array(size_t item_size, size_t nmemb) -{ - size_t size; - - if (SZ_MUL_OV(nmemb, item_size, &size)) { - errno = EOVERFLOW; - return NULL; - } - - return calloc(1, size); -} diff --git a/lib/util/array.c b/lib/util/array.c deleted file mode 100644 index 40bac50..0000000 --- a/lib/util/array.c +++ /dev/null @@ -1,115 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * array.c - * - * Copyright (C) 2021 David Oberhollenzer - */ -#include "config.h" -#include "compat.h" -#include "util/array.h" - -#include "sqfs/error.h" - -#include - -int array_init(array_t *array, size_t size, size_t capacity) -{ - size_t total; - - memset(array, 0, sizeof(*array)); - - if (capacity > 0) { - if (SZ_MUL_OV(size, capacity, &total)) - return SQFS_ERROR_OVERFLOW; - - array->data = malloc(total); - if (array->data == NULL) - return SQFS_ERROR_ALLOC; - } - - array->size = size; - array->count = capacity; - return 0; -} - -int array_init_copy(array_t *array, const array_t *src) -{ - int ret; - - ret = array_init(array, src->size, src->used); - if (ret != 0) - return ret; - - memcpy(array->data, src->data, src->used * src->size); - array->used = src->used; - return 0; -} - -void array_cleanup(array_t *array) -{ - free(array->data); - memset(array, 0, sizeof(*array)); -} - -int array_append(array_t *array, const void *data) -{ - size_t new_sz, new_count; - void *new; - - if (array->used == array->count) { - if (array->count == 0) { - new_count = 128; - } else { - if (SZ_MUL_OV(array->count, 2, &new_count)) - return SQFS_ERROR_ALLOC; - } - - if (SZ_MUL_OV(new_count, array->size, &new_sz)) - return SQFS_ERROR_ALLOC; - - new = realloc(array->data, new_sz); - if (new == NULL) - return SQFS_ERROR_ALLOC; - - array->data = new; - array->count = new_count; - } - - memcpy((char *)array->data + array->size * array->used, - data, array->size); - - array->used += 1; - return 0; -} - -int array_set_capacity(array_t *array, size_t capacity) -{ - size_t new_sz, new_count; - void *new; - - if (capacity <= array->count) - return 0; - - if (array->count == 0) { - new_count = 128; - } else { - if (SZ_MUL_OV(array->count, 2, &new_count)) - return SQFS_ERROR_ALLOC; - } - - while (new_count < capacity) { - if (SZ_MUL_OV(new_count, 2, &new_count)) - return SQFS_ERROR_ALLOC; - } - - if (SZ_MUL_OV(new_count, array->size, &new_sz)) - return SQFS_ERROR_ALLOC; - - new = realloc(array->data, new_sz); - if (new == NULL) - return SQFS_ERROR_ALLOC; - - array->data = new; - array->count = new_count; - return 0; -} diff --git a/lib/util/base64_decode.c b/lib/util/base64_decode.c deleted file mode 100644 index b1cf5b6..0000000 --- a/lib/util/base64_decode.c +++ /dev/null @@ -1,103 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * base64_decode.c - * - * Copyright (C) 2022 David Oberhollenzer - */ -#include "config.h" -#include "util/util.h" -#include "util/test.h" - -#include - -static int base64_digit(int c) -{ - if (isupper(c)) - return c - 'A'; - if (islower(c)) - return c - 'a' + 26; - if (isdigit(c)) - return c - '0' + 52; - if (c == '+') - return 62; - if (c == '/' || c == '-') - return 63; - return -1; -} - -int base64_decode(const char *in, size_t in_len, sqfs_u8 *out, size_t *out_len) -{ - int i1, i2, i3, i4; - size_t count = 0; - - while (in_len >= 4) { - i1 = base64_digit(*(in++)); - i2 = base64_digit(*(in++)); - i3 = *(in++); - i4 = *(in++); - in_len -= 4; - - if (i1 < 0 || i2 < 0 || count >= *out_len) - goto fail; - - out[count++] = (i1 << 2) | (i2 >> 4); - - if (i3 == '=' || i3 == '_') { - if ((i4 != '=' && i4 != '_') || in_len > 0) - goto fail; - break; - } - - i3 = base64_digit(i3); - if (i3 < 0 || count >= *out_len) - goto fail; - - out[count++] = ((i2 & 0x0F) << 4) | (i3 >> 2); - - if (i4 == '=' || i4 == '_') { - if (in_len > 0) - goto fail; - break; - } - - i4 = base64_digit(i4); - if (i4 < 0 || count >= *out_len) - goto fail; - - out[count++] = ((i3 & 0x3) << 6) | i4; - } - - /* libarchive has this bizarre bastardization of truncated base64 */ - if (in_len > 0) { - if (in_len == 1) - goto fail; - - i1 = base64_digit(*(in++)); - i2 = base64_digit(*(in++)); - in_len -= 2; - - if (i1 < 0 || i2 < 0 || count >= *out_len) - goto fail; - - out[count++] = (i1 << 2) | (i2 >> 4); - - if (in_len > 0) { - i3 = *(in++); - --in_len; - - if (i3 != '=' && i3 != '_') { - i3 = base64_digit(i3); - if (i3 < 0 || count >= *out_len) - goto fail; - - out[count++] = ((i2 & 0x0F) << 4) | (i3 >> 2); - } - } - } - - *out_len = count; - return 0; -fail: - *out_len = 0; - return -1; -} diff --git a/lib/util/canonicalize_name.c b/lib/util/canonicalize_name.c deleted file mode 100644 index 534e89e..0000000 --- a/lib/util/canonicalize_name.c +++ /dev/null @@ -1,60 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * canonicalize_name.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" -#include "util/util.h" - -static void normalize_slashes(char *filename) -{ - char *dst = filename, *src = filename; - - while (*src == '/') - ++src; - - while (*src != '\0') { - if (*src == '/') { - while (*src == '/') - ++src; - if (*src == '\0') - break; - *(dst++) = '/'; - } else { - *(dst++) = *(src++); - } - } - - *dst = '\0'; -} - -int canonicalize_name(char *filename) -{ - char *dst = filename, *src = filename; - - normalize_slashes(filename); - - while (*src != '\0') { - if (src[0] == '.') { - if (src[1] == '\0') - break; - if (src[1] == '/') { - src += 2; - continue; - } - if (src[1] == '.' && (src[2] == '/' || src[2] == '\0')) - return -1; - } - - while (*src != '\0' && *src != '/') - *(dst++) = *(src++); - - if (*src == '/') - *(dst++) = *(src++); - } - - *dst = '\0'; - normalize_slashes(filename); - return 0; -} diff --git a/lib/util/fast_urem_by_const.h b/lib/util/fast_urem_by_const.h deleted file mode 100644 index 4fb78d3..0000000 --- a/lib/util/fast_urem_by_const.h +++ /dev/null @@ -1,77 +0,0 @@ -/* - * Copyright © 2010 Valve Software - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice (including the next - * paragraph) shall be included in all copies or substantial portions of the - * Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING - * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS - * IN THE SOFTWARE. - */ - -#include "sqfs/predef.h" - -#include -#include - -/* - * Code for fast 32-bit unsigned remainder, based off of "Faster Remainder by - * Direct Computation: Applications to Compilers and Software Libraries," - * available at https://arxiv.org/pdf/1902.01961.pdf. - * - * util_fast_urem32(n, d, REMAINDER_MAGIC(d)) returns the same thing as - * n % d for any unsigned n and d, however it compiles down to only a few - * multiplications, so it should be faster than plain sqfs_u32 modulo if the - * same divisor is used many times. - */ - -#define REMAINDER_MAGIC(divisor) \ - ((sqfs_u64) ~0ull / (divisor) + 1) - -/* - * Get bits 64-96 of a 32x64-bit multiply. If __int128_t is available, we use - * it, which usually compiles down to one instruction on 64-bit architectures. - * Otherwise on 32-bit architectures we usually get four instructions (one - * 32x32->64 multiply, one 32x32->32 multiply, and one 64-bit add). - */ - -static inline sqfs_u32 -_mul32by64_hi(sqfs_u32 a, sqfs_u64 b) -{ -#if defined(__SIZEOF_INT128__) && __SIZEOF_INT128__ == 16 - return ((__uint128_t) b * a) >> 64; -#else - /* - * Let b = b0 + 2^32 * b1. Then a * b = a * b0 + 2^32 * a * b1. We would - * have to do a 96-bit addition to get the full result, except that only - * one term has non-zero lower 32 bits, which means that to get the high 32 - * bits, we only have to add the high 64 bits of each term. Unfortunately, - * we have to do the 64-bit addition in case the low 32 bits overflow. - */ - sqfs_u32 b0 = (sqfs_u32) b; - sqfs_u32 b1 = b >> 32; - return ((((sqfs_u64) a * b0) >> 32) + (sqfs_u64) a * b1) >> 32; -#endif -} - -static inline sqfs_u32 -util_fast_urem32(sqfs_u32 n, sqfs_u32 d, sqfs_u64 magic) -{ - sqfs_u64 lowbits = magic * n; - sqfs_u32 result = _mul32by64_hi(d, lowbits); - assert(result == n % d); - return result; -} - diff --git a/lib/util/file_cmp.c b/lib/util/file_cmp.c deleted file mode 100644 index 2aa0cc2..0000000 --- a/lib/util/file_cmp.c +++ /dev/null @@ -1,41 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * file_cmp.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include "util/util.h" -#include "sqfs/io.h" - -#include - -int check_file_range_equal(sqfs_file_t *file, void *scratch, size_t scratch_sz, - sqfs_u64 loc_a, sqfs_u64 loc_b, sqfs_u64 size) -{ - sqfs_u8 *ptr_a = scratch, *ptr_b = ptr_a + scratch_sz / 2; - int ret; - - while (size > 0) { - size_t diff = scratch_sz / 2; - diff = (sqfs_u64)diff > size ? size : diff; - - ret = file->read_at(file, loc_a, ptr_a, diff); - if (ret != 0) - return ret; - - ret = file->read_at(file, loc_b, ptr_b, diff); - if (ret != 0) - return ret; - - if (memcmp(ptr_a, ptr_b, diff) != 0) - return 1; - - size -= diff; - loc_a += diff; - loc_b += diff; - } - - return 0; -} diff --git a/lib/util/filename_sane.c b/lib/util/filename_sane.c deleted file mode 100644 index b52ce4d..0000000 --- a/lib/util/filename_sane.c +++ /dev/null @@ -1,78 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * filename_sane.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" -#include "util/util.h" - -#include - -#if defined(_WIN32) || defined(__WINDOWS__) || defined(TEST_WIN32) -#ifdef _MSC_VER -#define strncasecmp _strnicmp -#define strcasecmp _stricmp -#endif - -static const char *bad_names[] = { - "CON", "PRN", "AUX", "NUL", - "COM1", "COM2", "COM3", "COM4", "COM5", "COM6", "COM7", "COM8", "COM9", - "LPT1", "LPT2", "LPT3", "LPT4", "LPT5", "LPT6", "LPT7", "LPT8", "LPT9", -}; - -static bool is_allowed_by_os(const char *name) -{ - size_t len, i; - - for (i = 0; i < sizeof(bad_names) / sizeof(bad_names[0]); ++i) { - len = strlen(bad_names[i]); - - if (strncasecmp(name, bad_names[i], len) != 0) - continue; - - if (name[len] == '\0') - return false; - - if (name[len] == '.' && strchr(name + len + 1, '.') == NULL) - return false; - } - - return true; -} -#else -static bool is_allowed_by_os(const char *name) -{ - (void)name; - return true; -} -#endif - -bool is_filename_sane(const char *name, bool check_os_specific) -{ - if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0) - return false; - - if (check_os_specific && !is_allowed_by_os(name)) - return false; - - while (*name != '\0') { - if (*name == '/') - return false; - -#if defined(_WIN32) || defined(__WINDOWS__) || defined(TEST_WIN32) - if (check_os_specific) { - if (*name == '<' || *name == '>' || *name == ':') - return false; - if (*name == '"' || *name == '|' || *name == '?') - return false; - if (*name == '*' || *name == '\\' || *name <= 31) - return false; - } -#endif - - ++name; - } - - return true; -} diff --git a/lib/util/hash_table.c b/lib/util/hash_table.c deleted file mode 100644 index 0010e9f..0000000 --- a/lib/util/hash_table.c +++ /dev/null @@ -1,417 +0,0 @@ -/* - * Copyright © 2009,2012 Intel Corporation - * Copyright © 1988-2004 Keith Packard and Bart Massey. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice (including the next - * paragraph) shall be included in all copies or substantial portions of the - * Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING - * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS - * IN THE SOFTWARE. - * - * Except as contained in this notice, the names of the authors - * or their institutions shall not be used in advertising or - * otherwise to promote the sale, use or other dealings in this - * Software without prior written authorization from the - * authors. - * - * Authors: - * Eric Anholt - * Keith Packard - */ - -/** - * Implements an open-addressing, linear-reprobing hash table. - * - * For more information, see: - * - * http://cgit.freedesktop.org/~anholt/hash_table/tree/README - */ - -#include -#include -#include - -#include "fast_urem_by_const.h" -#include "util/hash_table.h" - -# define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) - -static const sqfs_u32 deleted_key_value; - -/** - * From Knuth -- a good choice for hash/rehash values is p, p-2 where - * p and p-2 are both prime. These tables are sized to have an extra 10% - * free to avoid exponential performance degradation as the hash table fills - */ -static const struct { - sqfs_u32 max_entries, size, rehash; - sqfs_u64 size_magic, rehash_magic; -} hash_sizes[] = { -#define ENTRY(max_entries, size, rehash) \ - { max_entries, size, rehash, \ - REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) } - - ENTRY(2, 5, 3 ), - ENTRY(4, 7, 5 ), - ENTRY(8, 13, 11 ), - ENTRY(16, 19, 17 ), - ENTRY(32, 43, 41 ), - ENTRY(64, 73, 71 ), - ENTRY(128, 151, 149 ), - ENTRY(256, 283, 281 ), - ENTRY(512, 571, 569 ), - ENTRY(1024, 1153, 1151 ), - ENTRY(2048, 2269, 2267 ), - ENTRY(4096, 4519, 4517 ), - ENTRY(8192, 9013, 9011 ), - ENTRY(16384, 18043, 18041 ), - ENTRY(32768, 36109, 36107 ), - ENTRY(65536, 72091, 72089 ), - ENTRY(131072, 144409, 144407 ), - ENTRY(262144, 288361, 288359 ), - ENTRY(524288, 576883, 576881 ), - ENTRY(1048576, 1153459, 1153457 ), - ENTRY(2097152, 2307163, 2307161 ), - ENTRY(4194304, 4613893, 4613891 ), - ENTRY(8388608, 9227641, 9227639 ), - ENTRY(16777216, 18455029, 18455027 ), - ENTRY(33554432, 36911011, 36911009 ), - ENTRY(67108864, 73819861, 73819859 ), - ENTRY(134217728, 147639589, 147639587 ), - ENTRY(268435456, 295279081, 295279079 ), - ENTRY(536870912, 590559793, 590559791 ), - ENTRY(1073741824, 1181116273, 1181116271 ), - ENTRY(2147483648ul, 2362232233ul, 2362232231ul ) -}; - -static inline bool -key_pointer_is_reserved(const struct hash_table *ht, const void *key) -{ - return key == NULL || key == ht->deleted_key; -} - -static int -entry_is_free(const struct hash_entry *entry) -{ - return entry->key == NULL; -} - -static int -entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry) -{ - return entry->key == ht->deleted_key; -} - -static int -entry_is_present(const struct hash_table *ht, struct hash_entry *entry) -{ - return entry->key != NULL && entry->key != ht->deleted_key; -} - -static bool -hash_table_init(struct hash_table *ht, - sqfs_u32 (*key_hash_function)(void *user, const void *key), - bool (*key_equals_function)(void *user, const void *a, - const void *b)) -{ - ht->size_index = 0; - ht->size = hash_sizes[ht->size_index].size; - ht->rehash = hash_sizes[ht->size_index].rehash; - ht->size_magic = hash_sizes[ht->size_index].size_magic; - ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic; - ht->max_entries = hash_sizes[ht->size_index].max_entries; - ht->key_hash_function = key_hash_function; - ht->key_equals_function = key_equals_function; - ht->table = calloc(sizeof(struct hash_entry), ht->size); - ht->entries = 0; - ht->deleted_entries = 0; - ht->deleted_key = &deleted_key_value; - - return ht->table != NULL; -} - -struct hash_table * -hash_table_create(sqfs_u32 (*key_hash_function)(void *user, const void *key), - bool (*key_equals_function)(void *user, const void *a, - const void *b)) -{ - struct hash_table *ht; - - ht = malloc(sizeof(struct hash_table)); - if (ht == NULL) - return NULL; - - if (!hash_table_init(ht, key_hash_function, key_equals_function)) { - free(ht); - return NULL; - } - - return ht; -} - -struct hash_table * -hash_table_clone(struct hash_table *src) -{ - struct hash_table *ht; - - ht = malloc(sizeof(struct hash_table)); - if (ht == NULL) - return NULL; - - memcpy(ht, src, sizeof(struct hash_table)); - - ht->table = calloc(sizeof(struct hash_entry), ht->size); - if (ht->table == NULL) { - free(ht); - return NULL; - } - - memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry)); - - return ht; -} - -/** - * Frees the given hash table. - */ -void -hash_table_destroy(struct hash_table *ht, - void (*delete_function)(struct hash_entry *entry)) -{ - if (!ht) - return; - - if (delete_function) { - hash_table_foreach(ht, entry) { - delete_function(entry); - } - } - free(ht->table); - free(ht); -} - -static struct hash_entry * -hash_table_search(struct hash_table *ht, sqfs_u32 hash, const void *key) -{ - assert(!key_pointer_is_reserved(ht, key)); - - sqfs_u32 size = ht->size; - sqfs_u32 start_hash_address = util_fast_urem32(hash, size, ht->size_magic); - sqfs_u32 double_hash = 1 + util_fast_urem32(hash, ht->rehash, - ht->rehash_magic); - sqfs_u32 hash_address = start_hash_address; - - do { - struct hash_entry *entry = ht->table + hash_address; - - if (entry_is_free(entry)) { - return NULL; - } else if (entry_is_present(ht, entry) && entry->hash == hash) { - if (ht->key_equals_function(ht->user, key, entry->key)) { - return entry; - } - } - - hash_address += double_hash; - if (hash_address >= size) - hash_address -= size; - } while (hash_address != start_hash_address); - - return NULL; -} - -/** - * Finds a hash table entry with the given key and hash of that key. - * - * Returns NULL if no entry is found. Note that the data pointer may be - * modified by the user. - */ -struct hash_entry * -hash_table_search_pre_hashed(struct hash_table *ht, sqfs_u32 hash, - const void *key) -{ - assert(ht->key_hash_function == NULL || - hash == ht->key_hash_function(ht->user, key)); - return hash_table_search(ht, hash, key); -} - -static void -hash_table_insert_rehash(struct hash_table *ht, sqfs_u32 hash, - const void *key, void *data) -{ - sqfs_u32 size = ht->size; - sqfs_u32 start_hash_address = util_fast_urem32(hash, size, ht->size_magic); - sqfs_u32 double_hash = 1 + util_fast_urem32(hash, ht->rehash, - ht->rehash_magic); - sqfs_u32 hash_address = start_hash_address; - do { - struct hash_entry *entry = ht->table + hash_address; - - if (entry->key == NULL) { - entry->hash = hash; - entry->key = key; - entry->data = data; - return; - } - - hash_address += double_hash; - if (hash_address >= size) - hash_address -= size; - } while (true); -} - -static void -hash_table_rehash(struct hash_table *ht, unsigned new_size_index) -{ - struct hash_table old_ht; - struct hash_entry *table; - - if (new_size_index >= ARRAY_SIZE(hash_sizes)) - return; - - table = calloc(sizeof(struct hash_entry), hash_sizes[new_size_index].size); - if (table == NULL) - return; - - old_ht = *ht; - - ht->table = table; - ht->size_index = new_size_index; - ht->size = hash_sizes[ht->size_index].size; - ht->rehash = hash_sizes[ht->size_index].rehash; - ht->size_magic = hash_sizes[ht->size_index].size_magic; - ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic; - ht->max_entries = hash_sizes[ht->size_index].max_entries; - ht->entries = 0; - ht->deleted_entries = 0; - - hash_table_foreach(&old_ht, entry) { - hash_table_insert_rehash(ht, entry->hash, entry->key, entry->data); - } - - ht->entries = old_ht.entries; - - free(old_ht.table); -} - -static struct hash_entry * -hash_table_insert(struct hash_table *ht, sqfs_u32 hash, - const void *key, void *data) -{ - struct hash_entry *available_entry = NULL; - - assert(!key_pointer_is_reserved(ht, key)); - - if (ht->entries >= ht->max_entries) { - hash_table_rehash(ht, ht->size_index + 1); - } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { - hash_table_rehash(ht, ht->size_index); - } - - sqfs_u32 size = ht->size; - sqfs_u32 start_hash_address = util_fast_urem32(hash, size, ht->size_magic); - sqfs_u32 double_hash = 1 + util_fast_urem32(hash, ht->rehash, - ht->rehash_magic); - sqfs_u32 hash_address = start_hash_address; - do { - struct hash_entry *entry = ht->table + hash_address; - - if (!entry_is_present(ht, entry)) { - /* Stash the first available entry we find */ - if (available_entry == NULL) - available_entry = entry; - if (entry_is_free(entry)) - break; - } - - /* Implement replacement when another insert happens - * with a matching key. This is a relatively common - * feature of hash tables, with the alternative - * generally being "insert the new value as well, and - * return it first when the key is searched for". - * - * Note that the hash table doesn't have a delete - * callback. If freeing of old data pointers is - * required to avoid memory leaks, perform a search - * before inserting. - */ - if (!entry_is_deleted(ht, entry) && - entry->hash == hash && - ht->key_equals_function(ht->user, key, entry->key)) { - entry->key = key; - entry->data = data; - return entry; - } - - hash_address += double_hash; - if (hash_address >= size) - hash_address -= size; - } while (hash_address != start_hash_address); - - if (available_entry) { - if (entry_is_deleted(ht, available_entry)) - ht->deleted_entries--; - available_entry->hash = hash; - available_entry->key = key; - available_entry->data = data; - ht->entries++; - return available_entry; - } - - /* We could hit here if a required resize failed. An unchecked-malloc - * application could ignore this result. - */ - return NULL; -} - -/** - * Inserts the key with the given hash into the table. - * - * Note that insertion may rearrange the table on a resize or rehash, - * so previously found hash_entries are no longer valid after this function. - */ -struct hash_entry * -hash_table_insert_pre_hashed(struct hash_table *ht, sqfs_u32 hash, - const void *key, void *data) -{ - assert(ht->key_hash_function == NULL || - hash == ht->key_hash_function(ht->user, key)); - return hash_table_insert(ht, hash, key, data); -} - -/** - * This function is an iterator over the hash table. - * - * Pass in NULL for the first entry, as in the start of a for loop. Note that - * an iteration over the table is O(table_size) not O(entries). - */ -struct hash_entry * -hash_table_next_entry(struct hash_table *ht, - struct hash_entry *entry) -{ - if (entry == NULL) - entry = ht->table; - else - entry = entry + 1; - - for (; entry != ht->table + ht->size; entry++) { - if (entry_is_present(ht, entry)) { - return entry; - } - } - - return NULL; -} diff --git a/lib/util/hex_decode.c b/lib/util/hex_decode.c deleted file mode 100644 index ee4b21c..0000000 --- a/lib/util/hex_decode.c +++ /dev/null @@ -1,34 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * hex_decode.h - * - * Copyright (C) 2022 David Oberhollenzer - */ -#include "util/util.h" - -#include - -static sqfs_u8 xdigit(int in) -{ - if (isupper(in)) - return in - 'A' + 10; - if (islower(in)) - return in - 'a' + 10; - return in - '0'; -} - -int hex_decode(const char *in, size_t in_sz, sqfs_u8 *out, size_t out_sz) -{ - while (out_sz > 0 && in_sz >= 2 && - isxdigit(in[0]) && isxdigit(in[1])) { - sqfs_u8 hi = xdigit(*(in++)); - sqfs_u8 lo = xdigit(*(in++)); - - *(out++) = (hi << 4) | lo; - - in_sz -= 2; - --out_sz; - } - - return (in_sz > 0) ? -1 : 0; -} diff --git a/lib/util/is_memory_zero.c b/lib/util/is_memory_zero.c deleted file mode 100644 index aabd45d..0000000 --- a/lib/util/is_memory_zero.c +++ /dev/null @@ -1,54 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * is_memory_zero.c - * - * Copyright (C) 2021 David Oberhollenzer - */ -#include "config.h" -#include "util/util.h" - -#include - -#define U64THRESHOLD (128) - -static bool test_u8(const unsigned char *blob, size_t size) -{ - while (size--) { - if (*(blob++) != 0) - return false; - } - - return true; -} - -bool is_memory_zero(const void *blob, size_t size) -{ - const sqfs_u64 *u64ptr; - size_t diff; - - if (size < U64THRESHOLD) - return test_u8(blob, size); - - diff = (uintptr_t)blob % sizeof(sqfs_u64); - - if (diff != 0) { - diff = sizeof(sqfs_u64) - diff; - - if (!test_u8(blob, diff)) - return false; - - blob = (const char *)blob + diff; - size -= diff; - } - - u64ptr = blob; - - while (size >= sizeof(sqfs_u64)) { - if (*(u64ptr++) != 0) - return false; - - size -= sizeof(sqfs_u64); - } - - return test_u8((const unsigned char *)u64ptr, size); -} diff --git a/lib/util/mempool.c b/lib/util/mempool.c deleted file mode 100644 index e2ddaf0..0000000 --- a/lib/util/mempool.c +++ /dev/null @@ -1,216 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * mempool.c - * - * Copyright (C) 2021 David Oberhollenzer - */ -#include "util/mempool.h" - -#include -#include -#include -#include - -#if defined(_WIN32) || defined(__WINDOWS__) -#define WIN32_LEAN_AND_MEAN -#include -#else -#include -#endif - -#define DEF_POOL_SIZE (65536) -#define MEM_ALIGN (8) - -typedef struct pool_t { - struct pool_t *next; - - unsigned char *data; - unsigned char *limit; - - unsigned int *bitmap; - - size_t obj_free; - - unsigned int blob[]; -} pool_t; - -struct mem_pool_t { - size_t obj_size; - size_t pool_size; - size_t bitmap_count; - pool_t *pool_list; -}; - -static size_t pool_size_from_bitmap_count(size_t count, size_t obj_size) -{ - size_t size, byte_count, bit_count; - - size = sizeof(pool_t); - if (size % sizeof(unsigned int)) - size += sizeof(unsigned int) - size % sizeof(unsigned int); - - byte_count = count * sizeof(unsigned int); - bit_count = byte_count * CHAR_BIT; - - size += byte_count; - if (size % obj_size) - size += obj_size - size % obj_size; - - size += bit_count * obj_size; - return size; -} - -static pool_t *create_pool(const mem_pool_t *mem) -{ - unsigned char *ptr; - pool_t *pool; - -#if defined(_WIN32) || defined(__WINDOWS__) - pool = VirtualAlloc(NULL, mem->pool_size, MEM_RESERVE | MEM_COMMIT, - PAGE_READWRITE); - - if (pool == NULL) - return NULL; -#else - pool = mmap(NULL, mem->pool_size, PROT_READ | PROT_WRITE, - MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); - - if (pool == MAP_FAILED) - return NULL; -#endif - pool->bitmap = pool->blob; - pool->obj_free = mem->bitmap_count * sizeof(unsigned int) * CHAR_BIT; - - ptr = (unsigned char *)(pool->bitmap + mem->bitmap_count); - - if (((uintptr_t)ptr) % mem->obj_size) { - ptr += mem->obj_size; - ptr -= ((uintptr_t)ptr) % mem->obj_size; - } - - pool->data = ptr; - pool->limit = pool->data + pool->obj_free * mem->obj_size - 1; - - memset(pool->bitmap, 0, mem->bitmap_count * sizeof(unsigned int)); - return pool; -} - -mem_pool_t *mem_pool_create(size_t obj_size) -{ - mem_pool_t *mem = calloc(1, sizeof(*mem)); - size_t count = 1, total; - - if (mem == NULL) - return NULL; - - if (obj_size % MEM_ALIGN) - obj_size += MEM_ALIGN - obj_size % MEM_ALIGN; - - for (;;) { - total = pool_size_from_bitmap_count(count, obj_size); - if (total > DEF_POOL_SIZE) - break; - ++count; - } - - --count; - - mem->obj_size = obj_size; - mem->pool_size = DEF_POOL_SIZE; - mem->bitmap_count = count; - return mem; -} - -void mem_pool_destroy(mem_pool_t *mem) -{ - while (mem->pool_list != NULL) { - pool_t *pool = mem->pool_list; - mem->pool_list = pool->next; - -#if defined(_WIN32) || defined(__WINDOWS__) - VirtualFree(pool, mem->pool_size, MEM_RELEASE); -#else - munmap(pool, mem->pool_size); -#endif - } - - free(mem); -} - -void *mem_pool_allocate(mem_pool_t *mem) -{ - size_t idx, i, j; - void *ptr = NULL; - pool_t *it; -retry_pool: - for (it = mem->pool_list; it != NULL; it = it->next) { - if (it->obj_free > 0) - break; - } - - if (it == NULL) { - it = create_pool(mem); - if (it == NULL) - return NULL; - - it->next = mem->pool_list; - mem->pool_list = it; - } - - for (i = 0; i < mem->bitmap_count; ++i) { - if (it->bitmap[i] < UINT_MAX) - break; - } - - if (i == mem->bitmap_count) { - it->obj_free = 0; - goto retry_pool; - } - - for (j = 0; j < (sizeof(it->bitmap[i]) * CHAR_BIT); ++j) { - if (!(it->bitmap[i] & (1UL << j))) - break; - } - - if (j == (sizeof(it->bitmap[i]) * CHAR_BIT)) { - it->obj_free = 0; - goto retry_pool; - } - - idx = i * sizeof(unsigned int) * CHAR_BIT + j; - ptr = it->data + idx * mem->obj_size; - - it->bitmap[i] |= (1UL << j); - it->obj_free -= 1; - - memset(ptr, 0, mem->obj_size); - return ptr; -} - -void mem_pool_free(mem_pool_t *mem, void *ptr) -{ - size_t idx, i, j; - pool_t *it; - - for (it = mem->pool_list; it != NULL; it = it->next) { - if ((unsigned char *)ptr >= it->data && - (unsigned char *)ptr < it->limit) { - break; - } - } - - assert(it != NULL); - - idx = (size_t)((unsigned char *)ptr - it->data); - - assert((idx % mem->obj_size) == 0); - idx /= mem->obj_size; - - i = idx / (sizeof(unsigned int) * CHAR_BIT); - j = idx % (sizeof(unsigned int) * CHAR_BIT); - - assert((it->bitmap[i] & (1 << j)) != 0); - - it->bitmap[i] &= ~(1 << j); - it->obj_free += 1; -} diff --git a/lib/util/mkdir_p.c b/lib/util/mkdir_p.c deleted file mode 100644 index 993d8ec..0000000 --- a/lib/util/mkdir_p.c +++ /dev/null @@ -1,170 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * mkdir_p.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "util/util.h" - -#include -#include -#include -#include - -#ifdef _WIN32 -/* - Supported paths: - - :\ - - \\\\ - - \\?\:\ - - \\?\UNC\\\ - - Relative path not starting with '\' - */ - -static WCHAR *skip_unc_path(WCHAR *ptr) -{ - /* server */ - if (*ptr == '\0' || *ptr == '\\') - return NULL; - - while (*ptr != '\0' && *ptr != '\\') - ++ptr; - - if (*(ptr++) != '\\') - return NULL; - - /* share */ - if (*ptr == '\0' || *ptr == '\\') - return NULL; - - while (*ptr != '\0' && *ptr != '\\') - ++ptr; - - return (*ptr == '\\') ? (ptr + 1) : ptr; -} - -static WCHAR *skip_prefix(WCHAR *ptr) -{ - if (isalpha(ptr[0]) && ptr[1] == ':' && ptr[2] == '\\') - return ptr + 3; - - if (ptr[0] == '\\' && ptr[1] == '\\') { - if (ptr[2] == '?') { - if (ptr[3] != '\\') - return NULL; - - ptr += 4; - - if ((ptr[0] == 'u' || ptr[0] == 'U') && - (ptr[1] == 'n' || ptr[1] == 'N') && - (ptr[2] == 'c' || ptr[2] == 'C') && - ptr[3] == '\\') { - ptr += 4; - - return skip_unc_path(ptr); - } - - if (isalpha(ptr[0]) && ptr[1] == ':' && ptr[2] == '\\') - return ptr + 3; - - return NULL; - } - - return skip_unc_path(ptr); - } - - if (ptr[0] == '\\') - return NULL; - - return ptr; -} - -int mkdir_p(const char *path) -{ - WCHAR *wpath, *ptr, *end; - DWORD error; - bool done; - - - wpath = path_to_windows(path); - if (wpath == NULL) - return -1; - - ptr = skip_prefix(wpath); - if (ptr == NULL) { - fprintf(stderr, "Illegal or unsupported path: %s\n", path); - goto fail; - } - - while (*ptr != '\0') { - if (*ptr == '\\') { - ++ptr; - continue; - } - - for (end = ptr; *end != '\0' && *end != '\\'; ++end) - ++end; - - if (*end == '\\') { - done = false; - *end = '\0'; - } else { - done = true; - } - - if (!CreateDirectoryW(wpath, NULL)) { - error = GetLastError(); - - if (error != ERROR_ALREADY_EXISTS) { - fprintf(stderr, "Creating %s: %ld\n", - path, error); - goto fail; - } - } - - if (!done) - *end = '\\'; - - ptr = done ? end : (end + 1); - } - - free(wpath); - return 0; -fail: - free(wpath); - return -1; -} -#else -int mkdir_p(const char *path) -{ - size_t i, len; - char *buffer; - - while (path[0] == '/' && path[1] == '/') - ++path; - - if (*path == '\0' || (path[0] == '/' && path[1] == '\0')) - return 0; - - len = strlen(path) + 1; - buffer = alloca(len); - - for (i = 0; i < len; ++i) { - if (i > 0 && (path[i] == '/' || path[i] == '\0')) { - buffer[i] = '\0'; - - if (mkdir(buffer, 0755) != 0) { - if (errno != EEXIST) { - fprintf(stderr, "mkdir %s: %s\n", - buffer, strerror(errno)); - return -1; - } - } - } - - buffer[i] = path[i]; - } - - return 0; -} -#endif diff --git a/lib/util/rbtree.c b/lib/util/rbtree.c deleted file mode 100644 index 8b43e43..0000000 --- a/lib/util/rbtree.c +++ /dev/null @@ -1,267 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * rbtree.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include "sqfs/error.h" -#include "util/rbtree.h" - -#include -#include - -#define IS_RED(n) ((n) && (n)->is_red) - -#ifdef NO_CUSTOM_ALLOC -static void destroy_nodes_dfs(rbtree_node_t *n) -{ - rbtree_node_t *l, *r; - - if (n != NULL) { - l = n->left; - r = n->right; - free(n); - destroy_nodes_dfs(l); - destroy_nodes_dfs(r); - } -} -#else -static void destroy_nodes_dfs(rbtree_node_t *n) -{ - (void)n; -} -#endif - -static void flip_colors(rbtree_node_t *n) -{ - n->is_red = !n->is_red; - n->left->is_red = !n->left->is_red; - n->right->is_red = !n->right->is_red; -} - -static rbtree_node_t *rotate_right(rbtree_node_t *n) -{ - rbtree_node_t *x; - - x = n->left; - n->left = x->right; - x->right = n; - - x->is_red = x->right->is_red; - x->right->is_red = 1; - return x; -} - -static rbtree_node_t *rotate_left(rbtree_node_t *n) -{ - rbtree_node_t *x; - - x = n->right; - n->right = x->left; - x->left = n; - - x->is_red = x->left->is_red; - x->left->is_red = 1; - return x; -} - -static rbtree_node_t *subtree_balance(rbtree_node_t *n) -{ - if (IS_RED(n->right) && !IS_RED(n->left)) - n = rotate_left(n); - - if (IS_RED(n->left) && IS_RED(n->left->left)) - n = rotate_right(n); - - if (IS_RED(n->left) && IS_RED(n->right)) - flip_colors(n); - - return n; -} - -static rbtree_node_t *subtree_insert(rbtree_t *tree, rbtree_node_t *root, - rbtree_node_t *new) -{ - if (root == NULL) - return new; - - if (tree->key_compare(tree->key_context, new->data, root->data) < 0) { - root->left = subtree_insert(tree, root->left, new); - } else { - root->right = subtree_insert(tree, root->right, new); - } - - return subtree_balance(root); -} - -static rbtree_node_t *mknode(rbtree_t *t, const void *key, const void *value) -{ - rbtree_node_t *node; - -#ifdef NO_CUSTOM_ALLOC - node = calloc(1, sizeof(*node) + t->key_size_padded + t->value_size); -#else - node = mem_pool_allocate(t->pool); -#endif - - if (node == NULL) - return NULL; - - node->value_offset = t->key_size_padded; - node->is_red = 1; - - memcpy(node->data, key, t->key_size); - memcpy(node->data + t->key_size_padded, value, t->value_size); - return node; -} - -static rbtree_node_t *copy_node(rbtree_t *nt, const rbtree_t *t, - const rbtree_node_t *n) -{ - rbtree_node_t *out; - -#ifdef NO_CUSTOM_ALLOC - out = calloc(1, sizeof(*out) + t->key_size_padded + t->value_size); -#else - out = mem_pool_allocate(nt->pool); -#endif - - if (out == NULL) - return NULL; - - memcpy(out, n, sizeof(*n) + t->key_size_padded + t->value_size); - out->left = NULL; - out->right = NULL; - - if (n->left != NULL) { - out->left = copy_node(nt, t, n->left); - - if (out->left == NULL) { - destroy_nodes_dfs(out); - return NULL; - } - } - - if (n->right != NULL) { - out->right = copy_node(nt, t, n->right); - - if (out->right == NULL) { - destroy_nodes_dfs(out); - return NULL; - } - } - - return out; -} - -int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize, - int(*key_compare)(const void *, const void *, const void *)) -{ - size_t diff, size; - - memset(tree, 0, sizeof(*tree)); - tree->key_compare = key_compare; - tree->key_size = keysize; - tree->key_size_padded = keysize; - tree->value_size = valuesize; - - /* make sure the value always has pointer alignment */ - diff = keysize % sizeof(void *); - - if (diff != 0) { - diff = sizeof(void *) - diff; - - if (SZ_ADD_OV(tree->key_size_padded, diff, - &tree->key_size_padded)) { - return SQFS_ERROR_OVERFLOW; - } - } - - /* make sure the node can store the offset */ - if (sizeof(size_t) > sizeof(sqfs_u32)) { - if (tree->key_size_padded > 0x0FFFFFFFFUL) - return SQFS_ERROR_OVERFLOW; - } - - /* make sure the nodes fit in memory */ - size = sizeof(rbtree_node_t); - - if (SZ_ADD_OV(size, tree->key_size_padded, &size)) - return SQFS_ERROR_OVERFLOW; - - if (SZ_ADD_OV(size, tree->value_size, &size)) - return SQFS_ERROR_OVERFLOW; - -#ifndef NO_CUSTOM_ALLOC - /* initialize the underlying pool allocator */ - tree->pool = mem_pool_create(size); - if (tree->pool == NULL) - return SQFS_ERROR_ALLOC; -#endif - return 0; -} - -int rbtree_copy(const rbtree_t *tree, rbtree_t *out) -{ - memcpy(out, tree, sizeof(*out)); - out->root = NULL; - -#ifndef NO_CUSTOM_ALLOC - out->pool = mem_pool_create(sizeof(rbtree_node_t) + - tree->key_size_padded + - tree->value_size); - if (out->pool == NULL) - return SQFS_ERROR_ALLOC; -#endif - - if (tree->root != NULL) { - out->root = copy_node(out, tree, tree->root); - - if (out->root == NULL) { - memset(out, 0, sizeof(*out)); - return SQFS_ERROR_ALLOC; - } - } - - return 0; -} - -void rbtree_cleanup(rbtree_t *tree) -{ -#ifdef NO_CUSTOM_ALLOC - destroy_nodes_dfs(tree->root); -#else - mem_pool_destroy(tree->pool); -#endif - memset(tree, 0, sizeof(*tree)); -} - -int rbtree_insert(rbtree_t *tree, const void *key, const void *value) -{ - rbtree_node_t *node = mknode(tree, key, value); - - if (node == NULL) - return SQFS_ERROR_ALLOC; - - tree->root = subtree_insert(tree, tree->root, node); - tree->root->is_red = 0; - return 0; -} - -rbtree_node_t *rbtree_lookup(const rbtree_t *tree, const void *key) -{ - rbtree_node_t *node = tree->root; - int ret; - - while (node != NULL) { - ret = tree->key_compare(tree->key_context, key, node->data); - if (ret == 0) - break; - - node = ret < 0 ? node->left : node->right; - } - - return node; -} diff --git a/lib/util/source_date_epoch.c b/lib/util/source_date_epoch.c deleted file mode 100644 index 26e5530..0000000 --- a/lib/util/source_date_epoch.c +++ /dev/null @@ -1,44 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * source_date_epoch.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "util/util.h" - -#include -#include -#include - -sqfs_u32 get_source_date_epoch(void) -{ - const char *str, *ptr; - sqfs_u32 x, tval = 0; - - str = getenv("SOURCE_DATE_EPOCH"); - - if (str == NULL || *str == '\0') - return 0; - - for (ptr = str; *ptr != '\0'; ++ptr) { - if (!isdigit(*ptr)) - goto fail_nan; - - x = (*ptr) - '0'; - - if (tval > (UINT32_MAX - x) / 10) - goto fail_ov; - - tval = tval * 10 + x; - } - - return tval; -fail_ov: - fprintf(stderr, "WARNING: SOURCE_DATE_EPOCH=%s does not fit into " - "32 bit integer\n", str); - return 0; -fail_nan: - fprintf(stderr, "WARNING: SOURCE_DATE_EPOCH=%s is not a positive " - "number\n", str); - return 0; -} diff --git a/lib/util/src/alloc.c b/lib/util/src/alloc.c new file mode 100644 index 0000000..359fef5 --- /dev/null +++ b/lib/util/src/alloc.c @@ -0,0 +1,37 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * alloc.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" + +#include "util/util.h" + +#include +#include + +void *alloc_flex(size_t base_size, size_t item_size, size_t nmemb) +{ + size_t size; + + if (SZ_MUL_OV(nmemb, item_size, &size) || + SZ_ADD_OV(base_size, size, &size)) { + errno = EOVERFLOW; + return NULL; + } + + return calloc(1, size); +} + +void *alloc_array(size_t item_size, size_t nmemb) +{ + size_t size; + + if (SZ_MUL_OV(nmemb, item_size, &size)) { + errno = EOVERFLOW; + return NULL; + } + + return calloc(1, size); +} diff --git a/lib/util/src/array.c b/lib/util/src/array.c new file mode 100644 index 0000000..40bac50 --- /dev/null +++ b/lib/util/src/array.c @@ -0,0 +1,115 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * array.c + * + * Copyright (C) 2021 David Oberhollenzer + */ +#include "config.h" +#include "compat.h" +#include "util/array.h" + +#include "sqfs/error.h" + +#include + +int array_init(array_t *array, size_t size, size_t capacity) +{ + size_t total; + + memset(array, 0, sizeof(*array)); + + if (capacity > 0) { + if (SZ_MUL_OV(size, capacity, &total)) + return SQFS_ERROR_OVERFLOW; + + array->data = malloc(total); + if (array->data == NULL) + return SQFS_ERROR_ALLOC; + } + + array->size = size; + array->count = capacity; + return 0; +} + +int array_init_copy(array_t *array, const array_t *src) +{ + int ret; + + ret = array_init(array, src->size, src->used); + if (ret != 0) + return ret; + + memcpy(array->data, src->data, src->used * src->size); + array->used = src->used; + return 0; +} + +void array_cleanup(array_t *array) +{ + free(array->data); + memset(array, 0, sizeof(*array)); +} + +int array_append(array_t *array, const void *data) +{ + size_t new_sz, new_count; + void *new; + + if (array->used == array->count) { + if (array->count == 0) { + new_count = 128; + } else { + if (SZ_MUL_OV(array->count, 2, &new_count)) + return SQFS_ERROR_ALLOC; + } + + if (SZ_MUL_OV(new_count, array->size, &new_sz)) + return SQFS_ERROR_ALLOC; + + new = realloc(array->data, new_sz); + if (new == NULL) + return SQFS_ERROR_ALLOC; + + array->data = new; + array->count = new_count; + } + + memcpy((char *)array->data + array->size * array->used, + data, array->size); + + array->used += 1; + return 0; +} + +int array_set_capacity(array_t *array, size_t capacity) +{ + size_t new_sz, new_count; + void *new; + + if (capacity <= array->count) + return 0; + + if (array->count == 0) { + new_count = 128; + } else { + if (SZ_MUL_OV(array->count, 2, &new_count)) + return SQFS_ERROR_ALLOC; + } + + while (new_count < capacity) { + if (SZ_MUL_OV(new_count, 2, &new_count)) + return SQFS_ERROR_ALLOC; + } + + if (SZ_MUL_OV(new_count, array->size, &new_sz)) + return SQFS_ERROR_ALLOC; + + new = realloc(array->data, new_sz); + if (new == NULL) + return SQFS_ERROR_ALLOC; + + array->data = new; + array->count = new_count; + return 0; +} diff --git a/lib/util/src/base64_decode.c b/lib/util/src/base64_decode.c new file mode 100644 index 0000000..b1cf5b6 --- /dev/null +++ b/lib/util/src/base64_decode.c @@ -0,0 +1,103 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * base64_decode.c + * + * Copyright (C) 2022 David Oberhollenzer + */ +#include "config.h" +#include "util/util.h" +#include "util/test.h" + +#include + +static int base64_digit(int c) +{ + if (isupper(c)) + return c - 'A'; + if (islower(c)) + return c - 'a' + 26; + if (isdigit(c)) + return c - '0' + 52; + if (c == '+') + return 62; + if (c == '/' || c == '-') + return 63; + return -1; +} + +int base64_decode(const char *in, size_t in_len, sqfs_u8 *out, size_t *out_len) +{ + int i1, i2, i3, i4; + size_t count = 0; + + while (in_len >= 4) { + i1 = base64_digit(*(in++)); + i2 = base64_digit(*(in++)); + i3 = *(in++); + i4 = *(in++); + in_len -= 4; + + if (i1 < 0 || i2 < 0 || count >= *out_len) + goto fail; + + out[count++] = (i1 << 2) | (i2 >> 4); + + if (i3 == '=' || i3 == '_') { + if ((i4 != '=' && i4 != '_') || in_len > 0) + goto fail; + break; + } + + i3 = base64_digit(i3); + if (i3 < 0 || count >= *out_len) + goto fail; + + out[count++] = ((i2 & 0x0F) << 4) | (i3 >> 2); + + if (i4 == '=' || i4 == '_') { + if (in_len > 0) + goto fail; + break; + } + + i4 = base64_digit(i4); + if (i4 < 0 || count >= *out_len) + goto fail; + + out[count++] = ((i3 & 0x3) << 6) | i4; + } + + /* libarchive has this bizarre bastardization of truncated base64 */ + if (in_len > 0) { + if (in_len == 1) + goto fail; + + i1 = base64_digit(*(in++)); + i2 = base64_digit(*(in++)); + in_len -= 2; + + if (i1 < 0 || i2 < 0 || count >= *out_len) + goto fail; + + out[count++] = (i1 << 2) | (i2 >> 4); + + if (in_len > 0) { + i3 = *(in++); + --in_len; + + if (i3 != '=' && i3 != '_') { + i3 = base64_digit(i3); + if (i3 < 0 || count >= *out_len) + goto fail; + + out[count++] = ((i2 & 0x0F) << 4) | (i3 >> 2); + } + } + } + + *out_len = count; + return 0; +fail: + *out_len = 0; + return -1; +} diff --git a/lib/util/src/canonicalize_name.c b/lib/util/src/canonicalize_name.c new file mode 100644 index 0000000..534e89e --- /dev/null +++ b/lib/util/src/canonicalize_name.c @@ -0,0 +1,60 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * canonicalize_name.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" +#include "util/util.h" + +static void normalize_slashes(char *filename) +{ + char *dst = filename, *src = filename; + + while (*src == '/') + ++src; + + while (*src != '\0') { + if (*src == '/') { + while (*src == '/') + ++src; + if (*src == '\0') + break; + *(dst++) = '/'; + } else { + *(dst++) = *(src++); + } + } + + *dst = '\0'; +} + +int canonicalize_name(char *filename) +{ + char *dst = filename, *src = filename; + + normalize_slashes(filename); + + while (*src != '\0') { + if (src[0] == '.') { + if (src[1] == '\0') + break; + if (src[1] == '/') { + src += 2; + continue; + } + if (src[1] == '.' && (src[2] == '/' || src[2] == '\0')) + return -1; + } + + while (*src != '\0' && *src != '/') + *(dst++) = *(src++); + + if (*src == '/') + *(dst++) = *(src++); + } + + *dst = '\0'; + normalize_slashes(filename); + return 0; +} diff --git a/lib/util/src/fast_urem_by_const.h b/lib/util/src/fast_urem_by_const.h new file mode 100644 index 0000000..4fb78d3 --- /dev/null +++ b/lib/util/src/fast_urem_by_const.h @@ -0,0 +1,77 @@ +/* + * Copyright © 2010 Valve Software + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#include "sqfs/predef.h" + +#include +#include + +/* + * Code for fast 32-bit unsigned remainder, based off of "Faster Remainder by + * Direct Computation: Applications to Compilers and Software Libraries," + * available at https://arxiv.org/pdf/1902.01961.pdf. + * + * util_fast_urem32(n, d, REMAINDER_MAGIC(d)) returns the same thing as + * n % d for any unsigned n and d, however it compiles down to only a few + * multiplications, so it should be faster than plain sqfs_u32 modulo if the + * same divisor is used many times. + */ + +#define REMAINDER_MAGIC(divisor) \ + ((sqfs_u64) ~0ull / (divisor) + 1) + +/* + * Get bits 64-96 of a 32x64-bit multiply. If __int128_t is available, we use + * it, which usually compiles down to one instruction on 64-bit architectures. + * Otherwise on 32-bit architectures we usually get four instructions (one + * 32x32->64 multiply, one 32x32->32 multiply, and one 64-bit add). + */ + +static inline sqfs_u32 +_mul32by64_hi(sqfs_u32 a, sqfs_u64 b) +{ +#if defined(__SIZEOF_INT128__) && __SIZEOF_INT128__ == 16 + return ((__uint128_t) b * a) >> 64; +#else + /* + * Let b = b0 + 2^32 * b1. Then a * b = a * b0 + 2^32 * a * b1. We would + * have to do a 96-bit addition to get the full result, except that only + * one term has non-zero lower 32 bits, which means that to get the high 32 + * bits, we only have to add the high 64 bits of each term. Unfortunately, + * we have to do the 64-bit addition in case the low 32 bits overflow. + */ + sqfs_u32 b0 = (sqfs_u32) b; + sqfs_u32 b1 = b >> 32; + return ((((sqfs_u64) a * b0) >> 32) + (sqfs_u64) a * b1) >> 32; +#endif +} + +static inline sqfs_u32 +util_fast_urem32(sqfs_u32 n, sqfs_u32 d, sqfs_u64 magic) +{ + sqfs_u64 lowbits = magic * n; + sqfs_u32 result = _mul32by64_hi(d, lowbits); + assert(result == n % d); + return result; +} + diff --git a/lib/util/src/file_cmp.c b/lib/util/src/file_cmp.c new file mode 100644 index 0000000..2aa0cc2 --- /dev/null +++ b/lib/util/src/file_cmp.c @@ -0,0 +1,41 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * file_cmp.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" + +#include "util/util.h" +#include "sqfs/io.h" + +#include + +int check_file_range_equal(sqfs_file_t *file, void *scratch, size_t scratch_sz, + sqfs_u64 loc_a, sqfs_u64 loc_b, sqfs_u64 size) +{ + sqfs_u8 *ptr_a = scratch, *ptr_b = ptr_a + scratch_sz / 2; + int ret; + + while (size > 0) { + size_t diff = scratch_sz / 2; + diff = (sqfs_u64)diff > size ? size : diff; + + ret = file->read_at(file, loc_a, ptr_a, diff); + if (ret != 0) + return ret; + + ret = file->read_at(file, loc_b, ptr_b, diff); + if (ret != 0) + return ret; + + if (memcmp(ptr_a, ptr_b, diff) != 0) + return 1; + + size -= diff; + loc_a += diff; + loc_b += diff; + } + + return 0; +} diff --git a/lib/util/src/filename_sane.c b/lib/util/src/filename_sane.c new file mode 100644 index 0000000..b52ce4d --- /dev/null +++ b/lib/util/src/filename_sane.c @@ -0,0 +1,78 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * filename_sane.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" +#include "util/util.h" + +#include + +#if defined(_WIN32) || defined(__WINDOWS__) || defined(TEST_WIN32) +#ifdef _MSC_VER +#define strncasecmp _strnicmp +#define strcasecmp _stricmp +#endif + +static const char *bad_names[] = { + "CON", "PRN", "AUX", "NUL", + "COM1", "COM2", "COM3", "COM4", "COM5", "COM6", "COM7", "COM8", "COM9", + "LPT1", "LPT2", "LPT3", "LPT4", "LPT5", "LPT6", "LPT7", "LPT8", "LPT9", +}; + +static bool is_allowed_by_os(const char *name) +{ + size_t len, i; + + for (i = 0; i < sizeof(bad_names) / sizeof(bad_names[0]); ++i) { + len = strlen(bad_names[i]); + + if (strncasecmp(name, bad_names[i], len) != 0) + continue; + + if (name[len] == '\0') + return false; + + if (name[len] == '.' && strchr(name + len + 1, '.') == NULL) + return false; + } + + return true; +} +#else +static bool is_allowed_by_os(const char *name) +{ + (void)name; + return true; +} +#endif + +bool is_filename_sane(const char *name, bool check_os_specific) +{ + if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0) + return false; + + if (check_os_specific && !is_allowed_by_os(name)) + return false; + + while (*name != '\0') { + if (*name == '/') + return false; + +#if defined(_WIN32) || defined(__WINDOWS__) || defined(TEST_WIN32) + if (check_os_specific) { + if (*name == '<' || *name == '>' || *name == ':') + return false; + if (*name == '"' || *name == '|' || *name == '?') + return false; + if (*name == '*' || *name == '\\' || *name <= 31) + return false; + } +#endif + + ++name; + } + + return true; +} diff --git a/lib/util/src/hash_table.c b/lib/util/src/hash_table.c new file mode 100644 index 0000000..0010e9f --- /dev/null +++ b/lib/util/src/hash_table.c @@ -0,0 +1,417 @@ +/* + * Copyright © 2009,2012 Intel Corporation + * Copyright © 1988-2004 Keith Packard and Bart Massey. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Except as contained in this notice, the names of the authors + * or their institutions shall not be used in advertising or + * otherwise to promote the sale, use or other dealings in this + * Software without prior written authorization from the + * authors. + * + * Authors: + * Eric Anholt + * Keith Packard + */ + +/** + * Implements an open-addressing, linear-reprobing hash table. + * + * For more information, see: + * + * http://cgit.freedesktop.org/~anholt/hash_table/tree/README + */ + +#include +#include +#include + +#include "fast_urem_by_const.h" +#include "util/hash_table.h" + +# define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) + +static const sqfs_u32 deleted_key_value; + +/** + * From Knuth -- a good choice for hash/rehash values is p, p-2 where + * p and p-2 are both prime. These tables are sized to have an extra 10% + * free to avoid exponential performance degradation as the hash table fills + */ +static const struct { + sqfs_u32 max_entries, size, rehash; + sqfs_u64 size_magic, rehash_magic; +} hash_sizes[] = { +#define ENTRY(max_entries, size, rehash) \ + { max_entries, size, rehash, \ + REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) } + + ENTRY(2, 5, 3 ), + ENTRY(4, 7, 5 ), + ENTRY(8, 13, 11 ), + ENTRY(16, 19, 17 ), + ENTRY(32, 43, 41 ), + ENTRY(64, 73, 71 ), + ENTRY(128, 151, 149 ), + ENTRY(256, 283, 281 ), + ENTRY(512, 571, 569 ), + ENTRY(1024, 1153, 1151 ), + ENTRY(2048, 2269, 2267 ), + ENTRY(4096, 4519, 4517 ), + ENTRY(8192, 9013, 9011 ), + ENTRY(16384, 18043, 18041 ), + ENTRY(32768, 36109, 36107 ), + ENTRY(65536, 72091, 72089 ), + ENTRY(131072, 144409, 144407 ), + ENTRY(262144, 288361, 288359 ), + ENTRY(524288, 576883, 576881 ), + ENTRY(1048576, 1153459, 1153457 ), + ENTRY(2097152, 2307163, 2307161 ), + ENTRY(4194304, 4613893, 4613891 ), + ENTRY(8388608, 9227641, 9227639 ), + ENTRY(16777216, 18455029, 18455027 ), + ENTRY(33554432, 36911011, 36911009 ), + ENTRY(67108864, 73819861, 73819859 ), + ENTRY(134217728, 147639589, 147639587 ), + ENTRY(268435456, 295279081, 295279079 ), + ENTRY(536870912, 590559793, 590559791 ), + ENTRY(1073741824, 1181116273, 1181116271 ), + ENTRY(2147483648ul, 2362232233ul, 2362232231ul ) +}; + +static inline bool +key_pointer_is_reserved(const struct hash_table *ht, const void *key) +{ + return key == NULL || key == ht->deleted_key; +} + +static int +entry_is_free(const struct hash_entry *entry) +{ + return entry->key == NULL; +} + +static int +entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry) +{ + return entry->key == ht->deleted_key; +} + +static int +entry_is_present(const struct hash_table *ht, struct hash_entry *entry) +{ + return entry->key != NULL && entry->key != ht->deleted_key; +} + +static bool +hash_table_init(struct hash_table *ht, + sqfs_u32 (*key_hash_function)(void *user, const void *key), + bool (*key_equals_function)(void *user, const void *a, + const void *b)) +{ + ht->size_index = 0; + ht->size = hash_sizes[ht->size_index].size; + ht->rehash = hash_sizes[ht->size_index].rehash; + ht->size_magic = hash_sizes[ht->size_index].size_magic; + ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic; + ht->max_entries = hash_sizes[ht->size_index].max_entries; + ht->key_hash_function = key_hash_function; + ht->key_equals_function = key_equals_function; + ht->table = calloc(sizeof(struct hash_entry), ht->size); + ht->entries = 0; + ht->deleted_entries = 0; + ht->deleted_key = &deleted_key_value; + + return ht->table != NULL; +} + +struct hash_table * +hash_table_create(sqfs_u32 (*key_hash_function)(void *user, const void *key), + bool (*key_equals_function)(void *user, const void *a, + const void *b)) +{ + struct hash_table *ht; + + ht = malloc(sizeof(struct hash_table)); + if (ht == NULL) + return NULL; + + if (!hash_table_init(ht, key_hash_function, key_equals_function)) { + free(ht); + return NULL; + } + + return ht; +} + +struct hash_table * +hash_table_clone(struct hash_table *src) +{ + struct hash_table *ht; + + ht = malloc(sizeof(struct hash_table)); + if (ht == NULL) + return NULL; + + memcpy(ht, src, sizeof(struct hash_table)); + + ht->table = calloc(sizeof(struct hash_entry), ht->size); + if (ht->table == NULL) { + free(ht); + return NULL; + } + + memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry)); + + return ht; +} + +/** + * Frees the given hash table. + */ +void +hash_table_destroy(struct hash_table *ht, + void (*delete_function)(struct hash_entry *entry)) +{ + if (!ht) + return; + + if (delete_function) { + hash_table_foreach(ht, entry) { + delete_function(entry); + } + } + free(ht->table); + free(ht); +} + +static struct hash_entry * +hash_table_search(struct hash_table *ht, sqfs_u32 hash, const void *key) +{ + assert(!key_pointer_is_reserved(ht, key)); + + sqfs_u32 size = ht->size; + sqfs_u32 start_hash_address = util_fast_urem32(hash, size, ht->size_magic); + sqfs_u32 double_hash = 1 + util_fast_urem32(hash, ht->rehash, + ht->rehash_magic); + sqfs_u32 hash_address = start_hash_address; + + do { + struct hash_entry *entry = ht->table + hash_address; + + if (entry_is_free(entry)) { + return NULL; + } else if (entry_is_present(ht, entry) && entry->hash == hash) { + if (ht->key_equals_function(ht->user, key, entry->key)) { + return entry; + } + } + + hash_address += double_hash; + if (hash_address >= size) + hash_address -= size; + } while (hash_address != start_hash_address); + + return NULL; +} + +/** + * Finds a hash table entry with the given key and hash of that key. + * + * Returns NULL if no entry is found. Note that the data pointer may be + * modified by the user. + */ +struct hash_entry * +hash_table_search_pre_hashed(struct hash_table *ht, sqfs_u32 hash, + const void *key) +{ + assert(ht->key_hash_function == NULL || + hash == ht->key_hash_function(ht->user, key)); + return hash_table_search(ht, hash, key); +} + +static void +hash_table_insert_rehash(struct hash_table *ht, sqfs_u32 hash, + const void *key, void *data) +{ + sqfs_u32 size = ht->size; + sqfs_u32 start_hash_address = util_fast_urem32(hash, size, ht->size_magic); + sqfs_u32 double_hash = 1 + util_fast_urem32(hash, ht->rehash, + ht->rehash_magic); + sqfs_u32 hash_address = start_hash_address; + do { + struct hash_entry *entry = ht->table + hash_address; + + if (entry->key == NULL) { + entry->hash = hash; + entry->key = key; + entry->data = data; + return; + } + + hash_address += double_hash; + if (hash_address >= size) + hash_address -= size; + } while (true); +} + +static void +hash_table_rehash(struct hash_table *ht, unsigned new_size_index) +{ + struct hash_table old_ht; + struct hash_entry *table; + + if (new_size_index >= ARRAY_SIZE(hash_sizes)) + return; + + table = calloc(sizeof(struct hash_entry), hash_sizes[new_size_index].size); + if (table == NULL) + return; + + old_ht = *ht; + + ht->table = table; + ht->size_index = new_size_index; + ht->size = hash_sizes[ht->size_index].size; + ht->rehash = hash_sizes[ht->size_index].rehash; + ht->size_magic = hash_sizes[ht->size_index].size_magic; + ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic; + ht->max_entries = hash_sizes[ht->size_index].max_entries; + ht->entries = 0; + ht->deleted_entries = 0; + + hash_table_foreach(&old_ht, entry) { + hash_table_insert_rehash(ht, entry->hash, entry->key, entry->data); + } + + ht->entries = old_ht.entries; + + free(old_ht.table); +} + +static struct hash_entry * +hash_table_insert(struct hash_table *ht, sqfs_u32 hash, + const void *key, void *data) +{ + struct hash_entry *available_entry = NULL; + + assert(!key_pointer_is_reserved(ht, key)); + + if (ht->entries >= ht->max_entries) { + hash_table_rehash(ht, ht->size_index + 1); + } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { + hash_table_rehash(ht, ht->size_index); + } + + sqfs_u32 size = ht->size; + sqfs_u32 start_hash_address = util_fast_urem32(hash, size, ht->size_magic); + sqfs_u32 double_hash = 1 + util_fast_urem32(hash, ht->rehash, + ht->rehash_magic); + sqfs_u32 hash_address = start_hash_address; + do { + struct hash_entry *entry = ht->table + hash_address; + + if (!entry_is_present(ht, entry)) { + /* Stash the first available entry we find */ + if (available_entry == NULL) + available_entry = entry; + if (entry_is_free(entry)) + break; + } + + /* Implement replacement when another insert happens + * with a matching key. This is a relatively common + * feature of hash tables, with the alternative + * generally being "insert the new value as well, and + * return it first when the key is searched for". + * + * Note that the hash table doesn't have a delete + * callback. If freeing of old data pointers is + * required to avoid memory leaks, perform a search + * before inserting. + */ + if (!entry_is_deleted(ht, entry) && + entry->hash == hash && + ht->key_equals_function(ht->user, key, entry->key)) { + entry->key = key; + entry->data = data; + return entry; + } + + hash_address += double_hash; + if (hash_address >= size) + hash_address -= size; + } while (hash_address != start_hash_address); + + if (available_entry) { + if (entry_is_deleted(ht, available_entry)) + ht->deleted_entries--; + available_entry->hash = hash; + available_entry->key = key; + available_entry->data = data; + ht->entries++; + return available_entry; + } + + /* We could hit here if a required resize failed. An unchecked-malloc + * application could ignore this result. + */ + return NULL; +} + +/** + * Inserts the key with the given hash into the table. + * + * Note that insertion may rearrange the table on a resize or rehash, + * so previously found hash_entries are no longer valid after this function. + */ +struct hash_entry * +hash_table_insert_pre_hashed(struct hash_table *ht, sqfs_u32 hash, + const void *key, void *data) +{ + assert(ht->key_hash_function == NULL || + hash == ht->key_hash_function(ht->user, key)); + return hash_table_insert(ht, hash, key, data); +} + +/** + * This function is an iterator over the hash table. + * + * Pass in NULL for the first entry, as in the start of a for loop. Note that + * an iteration over the table is O(table_size) not O(entries). + */ +struct hash_entry * +hash_table_next_entry(struct hash_table *ht, + struct hash_entry *entry) +{ + if (entry == NULL) + entry = ht->table; + else + entry = entry + 1; + + for (; entry != ht->table + ht->size; entry++) { + if (entry_is_present(ht, entry)) { + return entry; + } + } + + return NULL; +} diff --git a/lib/util/src/hex_decode.c b/lib/util/src/hex_decode.c new file mode 100644 index 0000000..ee4b21c --- /dev/null +++ b/lib/util/src/hex_decode.c @@ -0,0 +1,34 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * hex_decode.h + * + * Copyright (C) 2022 David Oberhollenzer + */ +#include "util/util.h" + +#include + +static sqfs_u8 xdigit(int in) +{ + if (isupper(in)) + return in - 'A' + 10; + if (islower(in)) + return in - 'a' + 10; + return in - '0'; +} + +int hex_decode(const char *in, size_t in_sz, sqfs_u8 *out, size_t out_sz) +{ + while (out_sz > 0 && in_sz >= 2 && + isxdigit(in[0]) && isxdigit(in[1])) { + sqfs_u8 hi = xdigit(*(in++)); + sqfs_u8 lo = xdigit(*(in++)); + + *(out++) = (hi << 4) | lo; + + in_sz -= 2; + --out_sz; + } + + return (in_sz > 0) ? -1 : 0; +} diff --git a/lib/util/src/is_memory_zero.c b/lib/util/src/is_memory_zero.c new file mode 100644 index 0000000..aabd45d --- /dev/null +++ b/lib/util/src/is_memory_zero.c @@ -0,0 +1,54 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * is_memory_zero.c + * + * Copyright (C) 2021 David Oberhollenzer + */ +#include "config.h" +#include "util/util.h" + +#include + +#define U64THRESHOLD (128) + +static bool test_u8(const unsigned char *blob, size_t size) +{ + while (size--) { + if (*(blob++) != 0) + return false; + } + + return true; +} + +bool is_memory_zero(const void *blob, size_t size) +{ + const sqfs_u64 *u64ptr; + size_t diff; + + if (size < U64THRESHOLD) + return test_u8(blob, size); + + diff = (uintptr_t)blob % sizeof(sqfs_u64); + + if (diff != 0) { + diff = sizeof(sqfs_u64) - diff; + + if (!test_u8(blob, diff)) + return false; + + blob = (const char *)blob + diff; + size -= diff; + } + + u64ptr = blob; + + while (size >= sizeof(sqfs_u64)) { + if (*(u64ptr++) != 0) + return false; + + size -= sizeof(sqfs_u64); + } + + return test_u8((const unsigned char *)u64ptr, size); +} diff --git a/lib/util/src/mempool.c b/lib/util/src/mempool.c new file mode 100644 index 0000000..e2ddaf0 --- /dev/null +++ b/lib/util/src/mempool.c @@ -0,0 +1,216 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * mempool.c + * + * Copyright (C) 2021 David Oberhollenzer + */ +#include "util/mempool.h" + +#include +#include +#include +#include + +#if defined(_WIN32) || defined(__WINDOWS__) +#define WIN32_LEAN_AND_MEAN +#include +#else +#include +#endif + +#define DEF_POOL_SIZE (65536) +#define MEM_ALIGN (8) + +typedef struct pool_t { + struct pool_t *next; + + unsigned char *data; + unsigned char *limit; + + unsigned int *bitmap; + + size_t obj_free; + + unsigned int blob[]; +} pool_t; + +struct mem_pool_t { + size_t obj_size; + size_t pool_size; + size_t bitmap_count; + pool_t *pool_list; +}; + +static size_t pool_size_from_bitmap_count(size_t count, size_t obj_size) +{ + size_t size, byte_count, bit_count; + + size = sizeof(pool_t); + if (size % sizeof(unsigned int)) + size += sizeof(unsigned int) - size % sizeof(unsigned int); + + byte_count = count * sizeof(unsigned int); + bit_count = byte_count * CHAR_BIT; + + size += byte_count; + if (size % obj_size) + size += obj_size - size % obj_size; + + size += bit_count * obj_size; + return size; +} + +static pool_t *create_pool(const mem_pool_t *mem) +{ + unsigned char *ptr; + pool_t *pool; + +#if defined(_WIN32) || defined(__WINDOWS__) + pool = VirtualAlloc(NULL, mem->pool_size, MEM_RESERVE | MEM_COMMIT, + PAGE_READWRITE); + + if (pool == NULL) + return NULL; +#else + pool = mmap(NULL, mem->pool_size, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); + + if (pool == MAP_FAILED) + return NULL; +#endif + pool->bitmap = pool->blob; + pool->obj_free = mem->bitmap_count * sizeof(unsigned int) * CHAR_BIT; + + ptr = (unsigned char *)(pool->bitmap + mem->bitmap_count); + + if (((uintptr_t)ptr) % mem->obj_size) { + ptr += mem->obj_size; + ptr -= ((uintptr_t)ptr) % mem->obj_size; + } + + pool->data = ptr; + pool->limit = pool->data + pool->obj_free * mem->obj_size - 1; + + memset(pool->bitmap, 0, mem->bitmap_count * sizeof(unsigned int)); + return pool; +} + +mem_pool_t *mem_pool_create(size_t obj_size) +{ + mem_pool_t *mem = calloc(1, sizeof(*mem)); + size_t count = 1, total; + + if (mem == NULL) + return NULL; + + if (obj_size % MEM_ALIGN) + obj_size += MEM_ALIGN - obj_size % MEM_ALIGN; + + for (;;) { + total = pool_size_from_bitmap_count(count, obj_size); + if (total > DEF_POOL_SIZE) + break; + ++count; + } + + --count; + + mem->obj_size = obj_size; + mem->pool_size = DEF_POOL_SIZE; + mem->bitmap_count = count; + return mem; +} + +void mem_pool_destroy(mem_pool_t *mem) +{ + while (mem->pool_list != NULL) { + pool_t *pool = mem->pool_list; + mem->pool_list = pool->next; + +#if defined(_WIN32) || defined(__WINDOWS__) + VirtualFree(pool, mem->pool_size, MEM_RELEASE); +#else + munmap(pool, mem->pool_size); +#endif + } + + free(mem); +} + +void *mem_pool_allocate(mem_pool_t *mem) +{ + size_t idx, i, j; + void *ptr = NULL; + pool_t *it; +retry_pool: + for (it = mem->pool_list; it != NULL; it = it->next) { + if (it->obj_free > 0) + break; + } + + if (it == NULL) { + it = create_pool(mem); + if (it == NULL) + return NULL; + + it->next = mem->pool_list; + mem->pool_list = it; + } + + for (i = 0; i < mem->bitmap_count; ++i) { + if (it->bitmap[i] < UINT_MAX) + break; + } + + if (i == mem->bitmap_count) { + it->obj_free = 0; + goto retry_pool; + } + + for (j = 0; j < (sizeof(it->bitmap[i]) * CHAR_BIT); ++j) { + if (!(it->bitmap[i] & (1UL << j))) + break; + } + + if (j == (sizeof(it->bitmap[i]) * CHAR_BIT)) { + it->obj_free = 0; + goto retry_pool; + } + + idx = i * sizeof(unsigned int) * CHAR_BIT + j; + ptr = it->data + idx * mem->obj_size; + + it->bitmap[i] |= (1UL << j); + it->obj_free -= 1; + + memset(ptr, 0, mem->obj_size); + return ptr; +} + +void mem_pool_free(mem_pool_t *mem, void *ptr) +{ + size_t idx, i, j; + pool_t *it; + + for (it = mem->pool_list; it != NULL; it = it->next) { + if ((unsigned char *)ptr >= it->data && + (unsigned char *)ptr < it->limit) { + break; + } + } + + assert(it != NULL); + + idx = (size_t)((unsigned char *)ptr - it->data); + + assert((idx % mem->obj_size) == 0); + idx /= mem->obj_size; + + i = idx / (sizeof(unsigned int) * CHAR_BIT); + j = idx % (sizeof(unsigned int) * CHAR_BIT); + + assert((it->bitmap[i] & (1 << j)) != 0); + + it->bitmap[i] &= ~(1 << j); + it->obj_free += 1; +} diff --git a/lib/util/src/mkdir_p.c b/lib/util/src/mkdir_p.c new file mode 100644 index 0000000..993d8ec --- /dev/null +++ b/lib/util/src/mkdir_p.c @@ -0,0 +1,170 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * mkdir_p.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "util/util.h" + +#include +#include +#include +#include + +#ifdef _WIN32 +/* + Supported paths: + - :\ + - \\\\ + - \\?\:\ + - \\?\UNC\\\ + - Relative path not starting with '\' + */ + +static WCHAR *skip_unc_path(WCHAR *ptr) +{ + /* server */ + if (*ptr == '\0' || *ptr == '\\') + return NULL; + + while (*ptr != '\0' && *ptr != '\\') + ++ptr; + + if (*(ptr++) != '\\') + return NULL; + + /* share */ + if (*ptr == '\0' || *ptr == '\\') + return NULL; + + while (*ptr != '\0' && *ptr != '\\') + ++ptr; + + return (*ptr == '\\') ? (ptr + 1) : ptr; +} + +static WCHAR *skip_prefix(WCHAR *ptr) +{ + if (isalpha(ptr[0]) && ptr[1] == ':' && ptr[2] == '\\') + return ptr + 3; + + if (ptr[0] == '\\' && ptr[1] == '\\') { + if (ptr[2] == '?') { + if (ptr[3] != '\\') + return NULL; + + ptr += 4; + + if ((ptr[0] == 'u' || ptr[0] == 'U') && + (ptr[1] == 'n' || ptr[1] == 'N') && + (ptr[2] == 'c' || ptr[2] == 'C') && + ptr[3] == '\\') { + ptr += 4; + + return skip_unc_path(ptr); + } + + if (isalpha(ptr[0]) && ptr[1] == ':' && ptr[2] == '\\') + return ptr + 3; + + return NULL; + } + + return skip_unc_path(ptr); + } + + if (ptr[0] == '\\') + return NULL; + + return ptr; +} + +int mkdir_p(const char *path) +{ + WCHAR *wpath, *ptr, *end; + DWORD error; + bool done; + + + wpath = path_to_windows(path); + if (wpath == NULL) + return -1; + + ptr = skip_prefix(wpath); + if (ptr == NULL) { + fprintf(stderr, "Illegal or unsupported path: %s\n", path); + goto fail; + } + + while (*ptr != '\0') { + if (*ptr == '\\') { + ++ptr; + continue; + } + + for (end = ptr; *end != '\0' && *end != '\\'; ++end) + ++end; + + if (*end == '\\') { + done = false; + *end = '\0'; + } else { + done = true; + } + + if (!CreateDirectoryW(wpath, NULL)) { + error = GetLastError(); + + if (error != ERROR_ALREADY_EXISTS) { + fprintf(stderr, "Creating %s: %ld\n", + path, error); + goto fail; + } + } + + if (!done) + *end = '\\'; + + ptr = done ? end : (end + 1); + } + + free(wpath); + return 0; +fail: + free(wpath); + return -1; +} +#else +int mkdir_p(const char *path) +{ + size_t i, len; + char *buffer; + + while (path[0] == '/' && path[1] == '/') + ++path; + + if (*path == '\0' || (path[0] == '/' && path[1] == '\0')) + return 0; + + len = strlen(path) + 1; + buffer = alloca(len); + + for (i = 0; i < len; ++i) { + if (i > 0 && (path[i] == '/' || path[i] == '\0')) { + buffer[i] = '\0'; + + if (mkdir(buffer, 0755) != 0) { + if (errno != EEXIST) { + fprintf(stderr, "mkdir %s: %s\n", + buffer, strerror(errno)); + return -1; + } + } + } + + buffer[i] = path[i]; + } + + return 0; +} +#endif diff --git a/lib/util/src/rbtree.c b/lib/util/src/rbtree.c new file mode 100644 index 0000000..8b43e43 --- /dev/null +++ b/lib/util/src/rbtree.c @@ -0,0 +1,267 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * rbtree.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" + +#include "sqfs/error.h" +#include "util/rbtree.h" + +#include +#include + +#define IS_RED(n) ((n) && (n)->is_red) + +#ifdef NO_CUSTOM_ALLOC +static void destroy_nodes_dfs(rbtree_node_t *n) +{ + rbtree_node_t *l, *r; + + if (n != NULL) { + l = n->left; + r = n->right; + free(n); + destroy_nodes_dfs(l); + destroy_nodes_dfs(r); + } +} +#else +static void destroy_nodes_dfs(rbtree_node_t *n) +{ + (void)n; +} +#endif + +static void flip_colors(rbtree_node_t *n) +{ + n->is_red = !n->is_red; + n->left->is_red = !n->left->is_red; + n->right->is_red = !n->right->is_red; +} + +static rbtree_node_t *rotate_right(rbtree_node_t *n) +{ + rbtree_node_t *x; + + x = n->left; + n->left = x->right; + x->right = n; + + x->is_red = x->right->is_red; + x->right->is_red = 1; + return x; +} + +static rbtree_node_t *rotate_left(rbtree_node_t *n) +{ + rbtree_node_t *x; + + x = n->right; + n->right = x->left; + x->left = n; + + x->is_red = x->left->is_red; + x->left->is_red = 1; + return x; +} + +static rbtree_node_t *subtree_balance(rbtree_node_t *n) +{ + if (IS_RED(n->right) && !IS_RED(n->left)) + n = rotate_left(n); + + if (IS_RED(n->left) && IS_RED(n->left->left)) + n = rotate_right(n); + + if (IS_RED(n->left) && IS_RED(n->right)) + flip_colors(n); + + return n; +} + +static rbtree_node_t *subtree_insert(rbtree_t *tree, rbtree_node_t *root, + rbtree_node_t *new) +{ + if (root == NULL) + return new; + + if (tree->key_compare(tree->key_context, new->data, root->data) < 0) { + root->left = subtree_insert(tree, root->left, new); + } else { + root->right = subtree_insert(tree, root->right, new); + } + + return subtree_balance(root); +} + +static rbtree_node_t *mknode(rbtree_t *t, const void *key, const void *value) +{ + rbtree_node_t *node; + +#ifdef NO_CUSTOM_ALLOC + node = calloc(1, sizeof(*node) + t->key_size_padded + t->value_size); +#else + node = mem_pool_allocate(t->pool); +#endif + + if (node == NULL) + return NULL; + + node->value_offset = t->key_size_padded; + node->is_red = 1; + + memcpy(node->data, key, t->key_size); + memcpy(node->data + t->key_size_padded, value, t->value_size); + return node; +} + +static rbtree_node_t *copy_node(rbtree_t *nt, const rbtree_t *t, + const rbtree_node_t *n) +{ + rbtree_node_t *out; + +#ifdef NO_CUSTOM_ALLOC + out = calloc(1, sizeof(*out) + t->key_size_padded + t->value_size); +#else + out = mem_pool_allocate(nt->pool); +#endif + + if (out == NULL) + return NULL; + + memcpy(out, n, sizeof(*n) + t->key_size_padded + t->value_size); + out->left = NULL; + out->right = NULL; + + if (n->left != NULL) { + out->left = copy_node(nt, t, n->left); + + if (out->left == NULL) { + destroy_nodes_dfs(out); + return NULL; + } + } + + if (n->right != NULL) { + out->right = copy_node(nt, t, n->right); + + if (out->right == NULL) { + destroy_nodes_dfs(out); + return NULL; + } + } + + return out; +} + +int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize, + int(*key_compare)(const void *, const void *, const void *)) +{ + size_t diff, size; + + memset(tree, 0, sizeof(*tree)); + tree->key_compare = key_compare; + tree->key_size = keysize; + tree->key_size_padded = keysize; + tree->value_size = valuesize; + + /* make sure the value always has pointer alignment */ + diff = keysize % sizeof(void *); + + if (diff != 0) { + diff = sizeof(void *) - diff; + + if (SZ_ADD_OV(tree->key_size_padded, diff, + &tree->key_size_padded)) { + return SQFS_ERROR_OVERFLOW; + } + } + + /* make sure the node can store the offset */ + if (sizeof(size_t) > sizeof(sqfs_u32)) { + if (tree->key_size_padded > 0x0FFFFFFFFUL) + return SQFS_ERROR_OVERFLOW; + } + + /* make sure the nodes fit in memory */ + size = sizeof(rbtree_node_t); + + if (SZ_ADD_OV(size, tree->key_size_padded, &size)) + return SQFS_ERROR_OVERFLOW; + + if (SZ_ADD_OV(size, tree->value_size, &size)) + return SQFS_ERROR_OVERFLOW; + +#ifndef NO_CUSTOM_ALLOC + /* initialize the underlying pool allocator */ + tree->pool = mem_pool_create(size); + if (tree->pool == NULL) + return SQFS_ERROR_ALLOC; +#endif + return 0; +} + +int rbtree_copy(const rbtree_t *tree, rbtree_t *out) +{ + memcpy(out, tree, sizeof(*out)); + out->root = NULL; + +#ifndef NO_CUSTOM_ALLOC + out->pool = mem_pool_create(sizeof(rbtree_node_t) + + tree->key_size_padded + + tree->value_size); + if (out->pool == NULL) + return SQFS_ERROR_ALLOC; +#endif + + if (tree->root != NULL) { + out->root = copy_node(out, tree, tree->root); + + if (out->root == NULL) { + memset(out, 0, sizeof(*out)); + return SQFS_ERROR_ALLOC; + } + } + + return 0; +} + +void rbtree_cleanup(rbtree_t *tree) +{ +#ifdef NO_CUSTOM_ALLOC + destroy_nodes_dfs(tree->root); +#else + mem_pool_destroy(tree->pool); +#endif + memset(tree, 0, sizeof(*tree)); +} + +int rbtree_insert(rbtree_t *tree, const void *key, const void *value) +{ + rbtree_node_t *node = mknode(tree, key, value); + + if (node == NULL) + return SQFS_ERROR_ALLOC; + + tree->root = subtree_insert(tree, tree->root, node); + tree->root->is_red = 0; + return 0; +} + +rbtree_node_t *rbtree_lookup(const rbtree_t *tree, const void *key) +{ + rbtree_node_t *node = tree->root; + int ret; + + while (node != NULL) { + ret = tree->key_compare(tree->key_context, key, node->data); + if (ret == 0) + break; + + node = ret < 0 ? node->left : node->right; + } + + return node; +} diff --git a/lib/util/src/source_date_epoch.c b/lib/util/src/source_date_epoch.c new file mode 100644 index 0000000..26e5530 --- /dev/null +++ b/lib/util/src/source_date_epoch.c @@ -0,0 +1,44 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * source_date_epoch.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "util/util.h" + +#include +#include +#include + +sqfs_u32 get_source_date_epoch(void) +{ + const char *str, *ptr; + sqfs_u32 x, tval = 0; + + str = getenv("SOURCE_DATE_EPOCH"); + + if (str == NULL || *str == '\0') + return 0; + + for (ptr = str; *ptr != '\0'; ++ptr) { + if (!isdigit(*ptr)) + goto fail_nan; + + x = (*ptr) - '0'; + + if (tval > (UINT32_MAX - x) / 10) + goto fail_ov; + + tval = tval * 10 + x; + } + + return tval; +fail_ov: + fprintf(stderr, "WARNING: SOURCE_DATE_EPOCH=%s does not fit into " + "32 bit integer\n", str); + return 0; +fail_nan: + fprintf(stderr, "WARNING: SOURCE_DATE_EPOCH=%s is not a positive " + "number\n", str); + return 0; +} diff --git a/lib/util/src/str_table.c b/lib/util/src/str_table.c new file mode 100644 index 0000000..2d3e354 --- /dev/null +++ b/lib/util/src/str_table.c @@ -0,0 +1,183 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * str_table.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" + +#include +#include +#include + +#include "sqfs/error.h" +#include "util/str_table.h" +#include "util/util.h" + +/* R5 hash function (borrowed from reiserfs) */ +static sqfs_u32 strhash(const char *s) +{ + const signed char *str = (const signed char *)s; + sqfs_u32 a = 0; + + while (*str != '\0') { + a += *str << 4; + a += *str >> 4; + a *= 11; + str++; + } + + return a; +} + +static bool key_equals_function(void *user, const void *a, const void *b) +{ + (void)user; + return strcmp(a, b) == 0; +} + +int str_table_init(str_table_t *table) +{ + memset(table, 0, sizeof(*table)); + + if (array_init(&table->bucket_ptrs, sizeof(str_bucket_t *), 0)) + goto fail_arr; + + table->ht = hash_table_create(NULL, key_equals_function); + if (table->ht == NULL) + goto fail_ht; + + return 0; +fail_ht: + array_cleanup(&table->bucket_ptrs); +fail_arr: + memset(table, 0, sizeof(*table)); + return SQFS_ERROR_ALLOC; +} + +int str_table_copy(str_table_t *dst, const str_table_t *src) +{ + str_bucket_t *bucket, **array; + int ret; + + ret = array_init_copy(&dst->bucket_ptrs, &src->bucket_ptrs); + if (ret != 0) + return ret; + + dst->ht = hash_table_clone(src->ht); + if (dst->ht == NULL) { + array_cleanup(&dst->bucket_ptrs); + return SQFS_ERROR_ALLOC; + } + + array = (str_bucket_t **)dst->bucket_ptrs.data; + + hash_table_foreach(dst->ht, ent) { + bucket = alloc_flex(sizeof(*bucket), 1, strlen(ent->key) + 1); + if (bucket == NULL) { + str_table_cleanup(dst); + return SQFS_ERROR_ALLOC; + } + + memcpy(bucket, ent->data, + sizeof(*bucket) + strlen(ent->key) + 1); + + ent->data = bucket; + ent->key = bucket->string; + + array[bucket->index] = bucket; + } + + return 0; +} + +void str_table_cleanup(str_table_t *table) +{ + hash_table_foreach(table->ht, ent) { + free(ent->data); + ent->data = NULL; + ent->key = NULL; + } + + hash_table_destroy(table->ht, NULL); + array_cleanup(&table->bucket_ptrs); + memset(table, 0, sizeof(*table)); +} + +int str_table_get_index(str_table_t *table, const char *str, size_t *idx) +{ + struct hash_entry *ent; + str_bucket_t *new; + sqfs_u32 hash; + + hash = strhash(str); + ent = hash_table_search_pre_hashed(table->ht, hash, str); + + if (ent != NULL) { + *idx = ((str_bucket_t *)ent->data)->index; + return 0; + } + + new = alloc_flex(sizeof(*new), 1, strlen(str) + 1); + if (new == NULL) + return SQFS_ERROR_ALLOC; + + new->index = table->next_index; + strcpy(new->string, str); + + ent = hash_table_insert_pre_hashed(table->ht, hash, str, new); + if (ent == NULL) { + free(new); + return SQFS_ERROR_ALLOC; + } + + ent->key = new->string; + + if (array_append(&table->bucket_ptrs, &new) != 0) { + free(new); + ent->key = NULL; + ent->data = NULL; + return SQFS_ERROR_ALLOC; + } + + *idx = table->next_index++; + return 0; +} + +static str_bucket_t *bucket_by_index(const str_table_t *table, size_t index) +{ + if (index >= table->bucket_ptrs.used) + return NULL; + + return ((str_bucket_t **)table->bucket_ptrs.data)[index]; +} + +const char *str_table_get_string(const str_table_t *table, size_t index) +{ + str_bucket_t *bucket = bucket_by_index(table, index); + + return bucket == NULL ? NULL : bucket->string; +} + +void str_table_add_ref(str_table_t *table, size_t index) +{ + str_bucket_t *bucket = bucket_by_index(table, index); + + if (bucket != NULL && bucket->refcount < ~((size_t)0)) + bucket->refcount += 1; +} + +void str_table_del_ref(str_table_t *table, size_t index) +{ + str_bucket_t *bucket = bucket_by_index(table, index); + + if (bucket != NULL && bucket->refcount > 0) + bucket->refcount -= 1; +} + +size_t str_table_get_ref_count(const str_table_t *table, size_t index) +{ + str_bucket_t *bucket = bucket_by_index(table, index); + + return bucket != NULL ? bucket->refcount : 0; +} diff --git a/lib/util/src/threadpool.c b/lib/util/src/threadpool.c new file mode 100644 index 0000000..c7357cd --- /dev/null +++ b/lib/util/src/threadpool.c @@ -0,0 +1,392 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * threadpool.c + * + * Copyright (C) 2021 David Oberhollenzer + */ +#include "util/threadpool.h" +#include "util/util.h" + +#include +#include + +#if defined(_WIN32) || defined(__WINDOWS__) +#include "util/w32threadwrap.h" + +#define THREAD_FUN(funname, argname) DWORD WINAPI funname(LPVOID argname) +#define THREAD_EXIT_SUCCESS (0) +#else +#include +#include + +#define THREAD_FUN(funname, argname) void *funname(void *argname) +#define THREAD_EXIT_SUCCESS NULL +#endif + +typedef struct thread_pool_impl_t thread_pool_impl_t; + +typedef struct work_item_t { + struct work_item_t *next; + size_t ticket_number; + + void *data; +} work_item_t; + +typedef struct { + pthread_t thread; + thread_pool_impl_t *pool; + + thread_pool_worker_t fun; + void *user; +} worker_t; + +struct thread_pool_impl_t { + thread_pool_t base; + + pthread_mutex_t mtx; + pthread_cond_t queue_cond; + pthread_cond_t done_cond; + + size_t next_ticket; + size_t next_dequeue_ticket; + + size_t item_count; + + work_item_t *queue; + work_item_t *queue_last; + + work_item_t *done; + + work_item_t *safe_done; + work_item_t *safe_done_last; + + work_item_t *recycle; + + int status; + + size_t num_workers; + worker_t workers[]; +}; + +/*****************************************************************************/ + +static void store_completed(thread_pool_impl_t *pool, work_item_t *done, + int status) +{ + work_item_t *it = pool->done, *prev = NULL; + + while (it != NULL) { + if (it->ticket_number >= done->ticket_number) + break; + + prev = it; + it = it->next; + } + + if (prev == NULL) { + done->next = pool->done; + pool->done = done; + } else { + done->next = prev->next; + prev->next = done; + } + + if (status != 0 && pool->status == 0) + pool->status = status; + + pthread_cond_broadcast(&pool->done_cond); +} + +static work_item_t *get_next_work_item(thread_pool_impl_t *pool) +{ + work_item_t *item = NULL; + + while (pool->queue == NULL && pool->status == 0) + pthread_cond_wait(&pool->queue_cond, &pool->mtx); + + if (pool->status == 0) { + item = pool->queue; + pool->queue = item->next; + item->next = NULL; + + if (pool->queue == NULL) + pool->queue_last = NULL; + } + + return item; +} + +static THREAD_FUN(worker_proc, arg) +{ + work_item_t *item = NULL; + worker_t *worker = arg; + int status = 0; + + for (;;) { + pthread_mutex_lock(&worker->pool->mtx); + if (item != NULL) + store_completed(worker->pool, item, status); + + item = get_next_work_item(worker->pool); + pthread_mutex_unlock(&worker->pool->mtx); + + if (item == NULL) + break; + + status = worker->fun(worker->user, item->data); + } + + return THREAD_EXIT_SUCCESS; +} + +/*****************************************************************************/ + +static work_item_t *try_dequeue_done(thread_pool_impl_t *pool) +{ + work_item_t *out; + + if (pool->done == NULL) + return NULL; + + if (pool->done->ticket_number != pool->next_dequeue_ticket) + return NULL; + + out = pool->done; + pool->done = out->next; + out->next = NULL; + pool->next_dequeue_ticket += 1; + return out; +} + +static void free_item_list(work_item_t *list) +{ + while (list != NULL) { + work_item_t *item = list; + list = list->next; + free(item); + } +} + +static void destroy(thread_pool_t *interface) +{ + thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; + size_t i; + + pthread_mutex_lock(&pool->mtx); + pool->status = -1; + pthread_cond_broadcast(&pool->queue_cond); + pthread_mutex_unlock(&pool->mtx); + + for (i = 0; i < pool->num_workers; ++i) + pthread_join(pool->workers[i].thread, NULL); + + pthread_cond_destroy(&pool->done_cond); + pthread_cond_destroy(&pool->queue_cond); + pthread_mutex_destroy(&pool->mtx); + + free_item_list(pool->queue); + free_item_list(pool->done); + free_item_list(pool->recycle); + free_item_list(pool->safe_done); + free(pool); +} + +static size_t get_worker_count(thread_pool_t *interface) +{ + thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; + + return pool->num_workers; +} + +static void set_worker_ptr(thread_pool_t *interface, size_t idx, void *ptr) +{ + thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; + + if (idx >= pool->num_workers) + return; + + pthread_mutex_lock(&pool->mtx); + pool->workers[idx].user = ptr; + pthread_mutex_unlock(&pool->mtx); +} + +static int submit(thread_pool_t *interface, void *ptr) +{ + thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; + work_item_t *item = NULL; + int status; + + if (pool->recycle != NULL) { + item = pool->recycle; + pool->recycle = item->next; + item->next = NULL; + } + + if (item == NULL) { + item = calloc(1, sizeof(*item)); + if (item == NULL) + return -1; + } + + pthread_mutex_lock(&pool->mtx); + status = pool->status; + + if (status == 0) { + item->data = ptr; + item->ticket_number = pool->next_ticket++; + + if (pool->queue_last == NULL) { + pool->queue = item; + } else { + pool->queue_last->next = item; + } + + pool->queue_last = item; + pool->item_count += 1; + } + + for (;;) { + work_item_t *done = try_dequeue_done(pool); + if (done == NULL) + break; + + if (pool->safe_done_last == NULL) { + pool->safe_done = done; + } else { + pool->safe_done_last->next = done; + } + + pool->safe_done_last = done; + } + + pthread_cond_broadcast(&pool->queue_cond); + pthread_mutex_unlock(&pool->mtx); + + if (status != 0) { + memset(item, 0, sizeof(*item)); + item->next = pool->recycle; + pool->recycle = item; + } + + return status; +} + +static void *dequeue(thread_pool_t *interface) +{ + thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; + work_item_t *out = NULL; + void *ptr = NULL; + + if (pool->item_count == 0) + return NULL; + + if (pool->safe_done != NULL) { + out = pool->safe_done; + + pool->safe_done = pool->safe_done->next; + if (pool->safe_done == NULL) + pool->safe_done_last = NULL; + } else { + pthread_mutex_lock(&pool->mtx); + for (;;) { + out = try_dequeue_done(pool); + if (out != NULL) + break; + + pthread_cond_wait(&pool->done_cond, &pool->mtx); + } + pthread_mutex_unlock(&pool->mtx); + } + + ptr = out->data; + + out->ticket_number = 0; + out->data = NULL; + out->next = pool->recycle; + pool->recycle = out; + + pool->item_count -= 1; + return ptr; +} + +static int get_status(thread_pool_t *interface) +{ + thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; + int status; + + pthread_mutex_lock(&pool->mtx); + status = pool->status; + pthread_mutex_unlock(&pool->mtx); + + return status; +} + +thread_pool_t *thread_pool_create(size_t num_jobs, thread_pool_worker_t worker) +{ + thread_pool_impl_t *pool; + thread_pool_t *interface; + sigset_t set, oldset; + size_t i, j; + int ret; + + if (num_jobs < 1) + num_jobs = 1; + + pool = alloc_flex(sizeof(*pool), sizeof(pool->workers[0]), num_jobs); + if (pool == NULL) + return NULL; + + if (pthread_mutex_init(&pool->mtx, NULL) != 0) + goto fail_free; + + if (pthread_cond_init(&pool->queue_cond, NULL) != 0) + goto fail_mtx; + + if (pthread_cond_init(&pool->done_cond, NULL) != 0) + goto fail_qcond; + + sigfillset(&set); + pthread_sigmask(SIG_SETMASK, &set, &oldset); + + pool->num_workers = num_jobs; + + for (i = 0; i < num_jobs; ++i) { + pool->workers[i].fun = worker; + pool->workers[i].pool = pool; + + ret = pthread_create(&pool->workers[i].thread, NULL, + worker_proc, pool->workers + i); + + if (ret != 0) + goto fail; + } + + pthread_sigmask(SIG_SETMASK, &oldset, NULL); + + interface = (thread_pool_t *)pool; + interface->destroy = destroy; + interface->get_worker_count = get_worker_count; + interface->set_worker_ptr = set_worker_ptr; + interface->submit = submit; + interface->dequeue = dequeue; + interface->get_status = get_status; + return interface; +fail: + pthread_mutex_lock(&pool->mtx); + pool->status = -1; + pthread_cond_broadcast(&pool->queue_cond); + pthread_mutex_unlock(&pool->mtx); + + for (j = 0; j < i; ++j) + pthread_join(pool->workers[j].thread, NULL); + + pthread_sigmask(SIG_SETMASK, &oldset, NULL); + pthread_cond_destroy(&pool->done_cond); +fail_qcond: + pthread_cond_destroy(&pool->queue_cond); +fail_mtx: + pthread_mutex_destroy(&pool->mtx); +fail_free: + free(pool); + return NULL; +} diff --git a/lib/util/src/threadpool_serial.c b/lib/util/src/threadpool_serial.c new file mode 100644 index 0000000..fb24ee8 --- /dev/null +++ b/lib/util/src/threadpool_serial.c @@ -0,0 +1,162 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * threadpool_serial.c + * + * Copyright (C) 2021 David Oberhollenzer + */ +#include "util/threadpool.h" +#include "util/util.h" + +#include +#include + +typedef struct work_item_t { + struct work_item_t *next; + void *data; +} work_item_t; + +typedef struct { + thread_pool_t base; + + work_item_t *queue; + work_item_t *queue_last; + + work_item_t *recycle; + + thread_pool_worker_t fun; + void *user; + int status; +} serial_impl_t; + +static void destroy(thread_pool_t *interface) +{ + serial_impl_t *pool = (serial_impl_t *)interface; + + while (pool->queue != NULL) { + work_item_t *item = pool->queue; + pool->queue = item->next; + free(item); + } + + while (pool->recycle != NULL) { + work_item_t *item = pool->recycle; + pool->recycle = item->next; + free(item); + } + + free(pool); +} + +static size_t get_worker_count(thread_pool_t *pool) +{ + (void)pool; + return 1; +} + +static void set_worker_ptr(thread_pool_t *interface, size_t idx, void *ptr) +{ + serial_impl_t *pool = (serial_impl_t *)interface; + + if (idx >= 1) + return; + + pool->user = ptr; +} + +static int submit(thread_pool_t *interface, void *ptr) +{ + serial_impl_t *pool = (serial_impl_t *)interface; + work_item_t *item = NULL; + + if (pool->status != 0) + return pool->status; + + if (pool->recycle != NULL) { + item = pool->recycle; + pool->recycle = item->next; + item->next = NULL; + } + + if (item == NULL) { + item = calloc(1, sizeof(*item)); + if (item == NULL) + return -1; + } + + item->data = ptr; + + if (pool->queue_last == NULL) { + pool->queue = item; + } else { + pool->queue_last->next = item; + } + + pool->queue_last = item; + return 0; +} + +static void *dequeue(thread_pool_t *interface) +{ + serial_impl_t *pool = (serial_impl_t *)interface; + work_item_t *item; + void *ptr; + int ret; + + if (pool->queue == NULL) + return NULL; + + item = pool->queue; + pool->queue = item->next; + + if (pool->queue == NULL) + pool->queue_last = NULL; + + ptr = item->data; + + memset(item, 0, sizeof(*item)); + item->next = pool->recycle; + pool->recycle = item; + + ret = pool->fun(pool->user, ptr); + + if (ret != 0 && pool->status == 0) + pool->status = ret; + + return ptr; +} + +static int get_status(thread_pool_t *interface) +{ + serial_impl_t *pool = (serial_impl_t *)interface; + + return pool->status; +} + +thread_pool_t *thread_pool_create_serial(thread_pool_worker_t worker) +{ + serial_impl_t *pool = calloc(1, sizeof(*pool)); + thread_pool_t *interface = (thread_pool_t *)pool; + + if (pool == NULL) + return NULL; + + pool->fun = worker; + + interface = (thread_pool_t *)pool; + interface->destroy = destroy; + interface->get_worker_count = get_worker_count; + interface->set_worker_ptr = set_worker_ptr; + interface->submit = submit; + interface->dequeue = dequeue; + interface->get_status = get_status; + return interface; + +} + +#ifdef NO_THREAD_IMPL +thread_pool_t *thread_pool_create(size_t num_jobs, thread_pool_worker_t worker) +{ + (void)num_jobs; + return thread_pool_create_serial(worker); +} +#endif diff --git a/lib/util/src/xxhash.c b/lib/util/src/xxhash.c new file mode 100644 index 0000000..60467fb --- /dev/null +++ b/lib/util/src/xxhash.c @@ -0,0 +1,112 @@ +/* + * xxHash - Extremely Fast Hash algorithm + * Copyright (C) 2012-2016, Yann Collet. + * + * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * ---------------------------------------------------------------------------- + * This code has been lifted from Linux (the OS kernel) and adapted for use in + * libsquashfs. For the original, unmodified and complete source, see below. + * + * You can contact the author at: + * - xxHash homepage: http://cyan4973.github.io/xxHash/ + * - xxHash source repository: https://github.com/Cyan4973/xxHash + */ +#include "config.h" +#include "util/util.h" + +#include + +#define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r))) + +static const sqfs_u32 PRIME32_1 = 2654435761U; +static const sqfs_u32 PRIME32_2 = 2246822519U; +static const sqfs_u32 PRIME32_3 = 3266489917U; +static const sqfs_u32 PRIME32_4 = 668265263U; +static const sqfs_u32 PRIME32_5 = 374761393U; + +static sqfs_u32 xxh32_round(sqfs_u32 seed, sqfs_u32 input) +{ + seed += input * PRIME32_2; + seed = xxh_rotl32(seed, 13); + seed *= PRIME32_1; + return seed; +} + +static sqfs_u32 XXH_readLE32(const sqfs_u8 *ptr) +{ + sqfs_u32 value; + memcpy(&value, ptr, sizeof(value)); + return le32toh(value); +} + +sqfs_u32 xxh32(const void *input, const size_t len) +{ + const sqfs_u8 *p = (const sqfs_u8 *)input; + const sqfs_u8 *b_end = p + len; + sqfs_u32 h32; + + if (len >= 16) { + const sqfs_u8 *const limit = b_end - 16; + sqfs_u32 v1 = PRIME32_1 + PRIME32_2; + sqfs_u32 v2 = PRIME32_2; + sqfs_u32 v3 = 0; + sqfs_u32 v4 = PRIME32_1; + + do { + v1 = xxh32_round(v1, XXH_readLE32(p )); + v2 = xxh32_round(v2, XXH_readLE32(p + 4)); + v3 = xxh32_round(v3, XXH_readLE32(p + 8)); + v4 = xxh32_round(v4, XXH_readLE32(p + 12)); + p += 16; + } while (p <= limit); + + h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) + + xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18); + } else { + h32 = PRIME32_5; + } + + h32 += (sqfs_u32)len; + + while (p + 4 <= b_end) { + h32 += XXH_readLE32(p) * PRIME32_3; + h32 = xxh_rotl32(h32, 17) * PRIME32_4; + p += 4; + } + + while (p < b_end) { + h32 += (*p) * PRIME32_5; + h32 = xxh_rotl32(h32, 11) * PRIME32_1; + p++; + } + + h32 ^= h32 >> 15; + h32 *= PRIME32_2; + h32 ^= h32 >> 13; + h32 *= PRIME32_3; + h32 ^= h32 >> 16; + return h32; +} diff --git a/lib/util/str_table.c b/lib/util/str_table.c deleted file mode 100644 index 2d3e354..0000000 --- a/lib/util/str_table.c +++ /dev/null @@ -1,183 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * str_table.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include -#include -#include - -#include "sqfs/error.h" -#include "util/str_table.h" -#include "util/util.h" - -/* R5 hash function (borrowed from reiserfs) */ -static sqfs_u32 strhash(const char *s) -{ - const signed char *str = (const signed char *)s; - sqfs_u32 a = 0; - - while (*str != '\0') { - a += *str << 4; - a += *str >> 4; - a *= 11; - str++; - } - - return a; -} - -static bool key_equals_function(void *user, const void *a, const void *b) -{ - (void)user; - return strcmp(a, b) == 0; -} - -int str_table_init(str_table_t *table) -{ - memset(table, 0, sizeof(*table)); - - if (array_init(&table->bucket_ptrs, sizeof(str_bucket_t *), 0)) - goto fail_arr; - - table->ht = hash_table_create(NULL, key_equals_function); - if (table->ht == NULL) - goto fail_ht; - - return 0; -fail_ht: - array_cleanup(&table->bucket_ptrs); -fail_arr: - memset(table, 0, sizeof(*table)); - return SQFS_ERROR_ALLOC; -} - -int str_table_copy(str_table_t *dst, const str_table_t *src) -{ - str_bucket_t *bucket, **array; - int ret; - - ret = array_init_copy(&dst->bucket_ptrs, &src->bucket_ptrs); - if (ret != 0) - return ret; - - dst->ht = hash_table_clone(src->ht); - if (dst->ht == NULL) { - array_cleanup(&dst->bucket_ptrs); - return SQFS_ERROR_ALLOC; - } - - array = (str_bucket_t **)dst->bucket_ptrs.data; - - hash_table_foreach(dst->ht, ent) { - bucket = alloc_flex(sizeof(*bucket), 1, strlen(ent->key) + 1); - if (bucket == NULL) { - str_table_cleanup(dst); - return SQFS_ERROR_ALLOC; - } - - memcpy(bucket, ent->data, - sizeof(*bucket) + strlen(ent->key) + 1); - - ent->data = bucket; - ent->key = bucket->string; - - array[bucket->index] = bucket; - } - - return 0; -} - -void str_table_cleanup(str_table_t *table) -{ - hash_table_foreach(table->ht, ent) { - free(ent->data); - ent->data = NULL; - ent->key = NULL; - } - - hash_table_destroy(table->ht, NULL); - array_cleanup(&table->bucket_ptrs); - memset(table, 0, sizeof(*table)); -} - -int str_table_get_index(str_table_t *table, const char *str, size_t *idx) -{ - struct hash_entry *ent; - str_bucket_t *new; - sqfs_u32 hash; - - hash = strhash(str); - ent = hash_table_search_pre_hashed(table->ht, hash, str); - - if (ent != NULL) { - *idx = ((str_bucket_t *)ent->data)->index; - return 0; - } - - new = alloc_flex(sizeof(*new), 1, strlen(str) + 1); - if (new == NULL) - return SQFS_ERROR_ALLOC; - - new->index = table->next_index; - strcpy(new->string, str); - - ent = hash_table_insert_pre_hashed(table->ht, hash, str, new); - if (ent == NULL) { - free(new); - return SQFS_ERROR_ALLOC; - } - - ent->key = new->string; - - if (array_append(&table->bucket_ptrs, &new) != 0) { - free(new); - ent->key = NULL; - ent->data = NULL; - return SQFS_ERROR_ALLOC; - } - - *idx = table->next_index++; - return 0; -} - -static str_bucket_t *bucket_by_index(const str_table_t *table, size_t index) -{ - if (index >= table->bucket_ptrs.used) - return NULL; - - return ((str_bucket_t **)table->bucket_ptrs.data)[index]; -} - -const char *str_table_get_string(const str_table_t *table, size_t index) -{ - str_bucket_t *bucket = bucket_by_index(table, index); - - return bucket == NULL ? NULL : bucket->string; -} - -void str_table_add_ref(str_table_t *table, size_t index) -{ - str_bucket_t *bucket = bucket_by_index(table, index); - - if (bucket != NULL && bucket->refcount < ~((size_t)0)) - bucket->refcount += 1; -} - -void str_table_del_ref(str_table_t *table, size_t index) -{ - str_bucket_t *bucket = bucket_by_index(table, index); - - if (bucket != NULL && bucket->refcount > 0) - bucket->refcount -= 1; -} - -size_t str_table_get_ref_count(const str_table_t *table, size_t index) -{ - str_bucket_t *bucket = bucket_by_index(table, index); - - return bucket != NULL ? bucket->refcount : 0; -} diff --git a/lib/util/threadpool.c b/lib/util/threadpool.c deleted file mode 100644 index c7357cd..0000000 --- a/lib/util/threadpool.c +++ /dev/null @@ -1,392 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * threadpool.c - * - * Copyright (C) 2021 David Oberhollenzer - */ -#include "util/threadpool.h" -#include "util/util.h" - -#include -#include - -#if defined(_WIN32) || defined(__WINDOWS__) -#include "util/w32threadwrap.h" - -#define THREAD_FUN(funname, argname) DWORD WINAPI funname(LPVOID argname) -#define THREAD_EXIT_SUCCESS (0) -#else -#include -#include - -#define THREAD_FUN(funname, argname) void *funname(void *argname) -#define THREAD_EXIT_SUCCESS NULL -#endif - -typedef struct thread_pool_impl_t thread_pool_impl_t; - -typedef struct work_item_t { - struct work_item_t *next; - size_t ticket_number; - - void *data; -} work_item_t; - -typedef struct { - pthread_t thread; - thread_pool_impl_t *pool; - - thread_pool_worker_t fun; - void *user; -} worker_t; - -struct thread_pool_impl_t { - thread_pool_t base; - - pthread_mutex_t mtx; - pthread_cond_t queue_cond; - pthread_cond_t done_cond; - - size_t next_ticket; - size_t next_dequeue_ticket; - - size_t item_count; - - work_item_t *queue; - work_item_t *queue_last; - - work_item_t *done; - - work_item_t *safe_done; - work_item_t *safe_done_last; - - work_item_t *recycle; - - int status; - - size_t num_workers; - worker_t workers[]; -}; - -/*****************************************************************************/ - -static void store_completed(thread_pool_impl_t *pool, work_item_t *done, - int status) -{ - work_item_t *it = pool->done, *prev = NULL; - - while (it != NULL) { - if (it->ticket_number >= done->ticket_number) - break; - - prev = it; - it = it->next; - } - - if (prev == NULL) { - done->next = pool->done; - pool->done = done; - } else { - done->next = prev->next; - prev->next = done; - } - - if (status != 0 && pool->status == 0) - pool->status = status; - - pthread_cond_broadcast(&pool->done_cond); -} - -static work_item_t *get_next_work_item(thread_pool_impl_t *pool) -{ - work_item_t *item = NULL; - - while (pool->queue == NULL && pool->status == 0) - pthread_cond_wait(&pool->queue_cond, &pool->mtx); - - if (pool->status == 0) { - item = pool->queue; - pool->queue = item->next; - item->next = NULL; - - if (pool->queue == NULL) - pool->queue_last = NULL; - } - - return item; -} - -static THREAD_FUN(worker_proc, arg) -{ - work_item_t *item = NULL; - worker_t *worker = arg; - int status = 0; - - for (;;) { - pthread_mutex_lock(&worker->pool->mtx); - if (item != NULL) - store_completed(worker->pool, item, status); - - item = get_next_work_item(worker->pool); - pthread_mutex_unlock(&worker->pool->mtx); - - if (item == NULL) - break; - - status = worker->fun(worker->user, item->data); - } - - return THREAD_EXIT_SUCCESS; -} - -/*****************************************************************************/ - -static work_item_t *try_dequeue_done(thread_pool_impl_t *pool) -{ - work_item_t *out; - - if (pool->done == NULL) - return NULL; - - if (pool->done->ticket_number != pool->next_dequeue_ticket) - return NULL; - - out = pool->done; - pool->done = out->next; - out->next = NULL; - pool->next_dequeue_ticket += 1; - return out; -} - -static void free_item_list(work_item_t *list) -{ - while (list != NULL) { - work_item_t *item = list; - list = list->next; - free(item); - } -} - -static void destroy(thread_pool_t *interface) -{ - thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; - size_t i; - - pthread_mutex_lock(&pool->mtx); - pool->status = -1; - pthread_cond_broadcast(&pool->queue_cond); - pthread_mutex_unlock(&pool->mtx); - - for (i = 0; i < pool->num_workers; ++i) - pthread_join(pool->workers[i].thread, NULL); - - pthread_cond_destroy(&pool->done_cond); - pthread_cond_destroy(&pool->queue_cond); - pthread_mutex_destroy(&pool->mtx); - - free_item_list(pool->queue); - free_item_list(pool->done); - free_item_list(pool->recycle); - free_item_list(pool->safe_done); - free(pool); -} - -static size_t get_worker_count(thread_pool_t *interface) -{ - thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; - - return pool->num_workers; -} - -static void set_worker_ptr(thread_pool_t *interface, size_t idx, void *ptr) -{ - thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; - - if (idx >= pool->num_workers) - return; - - pthread_mutex_lock(&pool->mtx); - pool->workers[idx].user = ptr; - pthread_mutex_unlock(&pool->mtx); -} - -static int submit(thread_pool_t *interface, void *ptr) -{ - thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; - work_item_t *item = NULL; - int status; - - if (pool->recycle != NULL) { - item = pool->recycle; - pool->recycle = item->next; - item->next = NULL; - } - - if (item == NULL) { - item = calloc(1, sizeof(*item)); - if (item == NULL) - return -1; - } - - pthread_mutex_lock(&pool->mtx); - status = pool->status; - - if (status == 0) { - item->data = ptr; - item->ticket_number = pool->next_ticket++; - - if (pool->queue_last == NULL) { - pool->queue = item; - } else { - pool->queue_last->next = item; - } - - pool->queue_last = item; - pool->item_count += 1; - } - - for (;;) { - work_item_t *done = try_dequeue_done(pool); - if (done == NULL) - break; - - if (pool->safe_done_last == NULL) { - pool->safe_done = done; - } else { - pool->safe_done_last->next = done; - } - - pool->safe_done_last = done; - } - - pthread_cond_broadcast(&pool->queue_cond); - pthread_mutex_unlock(&pool->mtx); - - if (status != 0) { - memset(item, 0, sizeof(*item)); - item->next = pool->recycle; - pool->recycle = item; - } - - return status; -} - -static void *dequeue(thread_pool_t *interface) -{ - thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; - work_item_t *out = NULL; - void *ptr = NULL; - - if (pool->item_count == 0) - return NULL; - - if (pool->safe_done != NULL) { - out = pool->safe_done; - - pool->safe_done = pool->safe_done->next; - if (pool->safe_done == NULL) - pool->safe_done_last = NULL; - } else { - pthread_mutex_lock(&pool->mtx); - for (;;) { - out = try_dequeue_done(pool); - if (out != NULL) - break; - - pthread_cond_wait(&pool->done_cond, &pool->mtx); - } - pthread_mutex_unlock(&pool->mtx); - } - - ptr = out->data; - - out->ticket_number = 0; - out->data = NULL; - out->next = pool->recycle; - pool->recycle = out; - - pool->item_count -= 1; - return ptr; -} - -static int get_status(thread_pool_t *interface) -{ - thread_pool_impl_t *pool = (thread_pool_impl_t *)interface; - int status; - - pthread_mutex_lock(&pool->mtx); - status = pool->status; - pthread_mutex_unlock(&pool->mtx); - - return status; -} - -thread_pool_t *thread_pool_create(size_t num_jobs, thread_pool_worker_t worker) -{ - thread_pool_impl_t *pool; - thread_pool_t *interface; - sigset_t set, oldset; - size_t i, j; - int ret; - - if (num_jobs < 1) - num_jobs = 1; - - pool = alloc_flex(sizeof(*pool), sizeof(pool->workers[0]), num_jobs); - if (pool == NULL) - return NULL; - - if (pthread_mutex_init(&pool->mtx, NULL) != 0) - goto fail_free; - - if (pthread_cond_init(&pool->queue_cond, NULL) != 0) - goto fail_mtx; - - if (pthread_cond_init(&pool->done_cond, NULL) != 0) - goto fail_qcond; - - sigfillset(&set); - pthread_sigmask(SIG_SETMASK, &set, &oldset); - - pool->num_workers = num_jobs; - - for (i = 0; i < num_jobs; ++i) { - pool->workers[i].fun = worker; - pool->workers[i].pool = pool; - - ret = pthread_create(&pool->workers[i].thread, NULL, - worker_proc, pool->workers + i); - - if (ret != 0) - goto fail; - } - - pthread_sigmask(SIG_SETMASK, &oldset, NULL); - - interface = (thread_pool_t *)pool; - interface->destroy = destroy; - interface->get_worker_count = get_worker_count; - interface->set_worker_ptr = set_worker_ptr; - interface->submit = submit; - interface->dequeue = dequeue; - interface->get_status = get_status; - return interface; -fail: - pthread_mutex_lock(&pool->mtx); - pool->status = -1; - pthread_cond_broadcast(&pool->queue_cond); - pthread_mutex_unlock(&pool->mtx); - - for (j = 0; j < i; ++j) - pthread_join(pool->workers[j].thread, NULL); - - pthread_sigmask(SIG_SETMASK, &oldset, NULL); - pthread_cond_destroy(&pool->done_cond); -fail_qcond: - pthread_cond_destroy(&pool->queue_cond); -fail_mtx: - pthread_mutex_destroy(&pool->mtx); -fail_free: - free(pool); - return NULL; -} diff --git a/lib/util/threadpool_serial.c b/lib/util/threadpool_serial.c deleted file mode 100644 index fb24ee8..0000000 --- a/lib/util/threadpool_serial.c +++ /dev/null @@ -1,162 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * threadpool_serial.c - * - * Copyright (C) 2021 David Oberhollenzer - */ -#include "util/threadpool.h" -#include "util/util.h" - -#include -#include - -typedef struct work_item_t { - struct work_item_t *next; - void *data; -} work_item_t; - -typedef struct { - thread_pool_t base; - - work_item_t *queue; - work_item_t *queue_last; - - work_item_t *recycle; - - thread_pool_worker_t fun; - void *user; - int status; -} serial_impl_t; - -static void destroy(thread_pool_t *interface) -{ - serial_impl_t *pool = (serial_impl_t *)interface; - - while (pool->queue != NULL) { - work_item_t *item = pool->queue; - pool->queue = item->next; - free(item); - } - - while (pool->recycle != NULL) { - work_item_t *item = pool->recycle; - pool->recycle = item->next; - free(item); - } - - free(pool); -} - -static size_t get_worker_count(thread_pool_t *pool) -{ - (void)pool; - return 1; -} - -static void set_worker_ptr(thread_pool_t *interface, size_t idx, void *ptr) -{ - serial_impl_t *pool = (serial_impl_t *)interface; - - if (idx >= 1) - return; - - pool->user = ptr; -} - -static int submit(thread_pool_t *interface, void *ptr) -{ - serial_impl_t *pool = (serial_impl_t *)interface; - work_item_t *item = NULL; - - if (pool->status != 0) - return pool->status; - - if (pool->recycle != NULL) { - item = pool->recycle; - pool->recycle = item->next; - item->next = NULL; - } - - if (item == NULL) { - item = calloc(1, sizeof(*item)); - if (item == NULL) - return -1; - } - - item->data = ptr; - - if (pool->queue_last == NULL) { - pool->queue = item; - } else { - pool->queue_last->next = item; - } - - pool->queue_last = item; - return 0; -} - -static void *dequeue(thread_pool_t *interface) -{ - serial_impl_t *pool = (serial_impl_t *)interface; - work_item_t *item; - void *ptr; - int ret; - - if (pool->queue == NULL) - return NULL; - - item = pool->queue; - pool->queue = item->next; - - if (pool->queue == NULL) - pool->queue_last = NULL; - - ptr = item->data; - - memset(item, 0, sizeof(*item)); - item->next = pool->recycle; - pool->recycle = item; - - ret = pool->fun(pool->user, ptr); - - if (ret != 0 && pool->status == 0) - pool->status = ret; - - return ptr; -} - -static int get_status(thread_pool_t *interface) -{ - serial_impl_t *pool = (serial_impl_t *)interface; - - return pool->status; -} - -thread_pool_t *thread_pool_create_serial(thread_pool_worker_t worker) -{ - serial_impl_t *pool = calloc(1, sizeof(*pool)); - thread_pool_t *interface = (thread_pool_t *)pool; - - if (pool == NULL) - return NULL; - - pool->fun = worker; - - interface = (thread_pool_t *)pool; - interface->destroy = destroy; - interface->get_worker_count = get_worker_count; - interface->set_worker_ptr = set_worker_ptr; - interface->submit = submit; - interface->dequeue = dequeue; - interface->get_status = get_status; - return interface; - -} - -#ifdef NO_THREAD_IMPL -thread_pool_t *thread_pool_create(size_t num_jobs, thread_pool_worker_t worker) -{ - (void)num_jobs; - return thread_pool_create_serial(worker); -} -#endif diff --git a/lib/util/xxhash.c b/lib/util/xxhash.c deleted file mode 100644 index 60467fb..0000000 --- a/lib/util/xxhash.c +++ /dev/null @@ -1,112 +0,0 @@ -/* - * xxHash - Extremely Fast Hash algorithm - * Copyright (C) 2012-2016, Yann Collet. - * - * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following disclaimer - * in the documentation and/or other materials provided with the - * distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * ---------------------------------------------------------------------------- - * This code has been lifted from Linux (the OS kernel) and adapted for use in - * libsquashfs. For the original, unmodified and complete source, see below. - * - * You can contact the author at: - * - xxHash homepage: http://cyan4973.github.io/xxHash/ - * - xxHash source repository: https://github.com/Cyan4973/xxHash - */ -#include "config.h" -#include "util/util.h" - -#include - -#define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r))) - -static const sqfs_u32 PRIME32_1 = 2654435761U; -static const sqfs_u32 PRIME32_2 = 2246822519U; -static const sqfs_u32 PRIME32_3 = 3266489917U; -static const sqfs_u32 PRIME32_4 = 668265263U; -static const sqfs_u32 PRIME32_5 = 374761393U; - -static sqfs_u32 xxh32_round(sqfs_u32 seed, sqfs_u32 input) -{ - seed += input * PRIME32_2; - seed = xxh_rotl32(seed, 13); - seed *= PRIME32_1; - return seed; -} - -static sqfs_u32 XXH_readLE32(const sqfs_u8 *ptr) -{ - sqfs_u32 value; - memcpy(&value, ptr, sizeof(value)); - return le32toh(value); -} - -sqfs_u32 xxh32(const void *input, const size_t len) -{ - const sqfs_u8 *p = (const sqfs_u8 *)input; - const sqfs_u8 *b_end = p + len; - sqfs_u32 h32; - - if (len >= 16) { - const sqfs_u8 *const limit = b_end - 16; - sqfs_u32 v1 = PRIME32_1 + PRIME32_2; - sqfs_u32 v2 = PRIME32_2; - sqfs_u32 v3 = 0; - sqfs_u32 v4 = PRIME32_1; - - do { - v1 = xxh32_round(v1, XXH_readLE32(p )); - v2 = xxh32_round(v2, XXH_readLE32(p + 4)); - v3 = xxh32_round(v3, XXH_readLE32(p + 8)); - v4 = xxh32_round(v4, XXH_readLE32(p + 12)); - p += 16; - } while (p <= limit); - - h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) + - xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18); - } else { - h32 = PRIME32_5; - } - - h32 += (sqfs_u32)len; - - while (p + 4 <= b_end) { - h32 += XXH_readLE32(p) * PRIME32_3; - h32 = xxh_rotl32(h32, 17) * PRIME32_4; - p += 4; - } - - while (p < b_end) { - h32 += (*p) * PRIME32_5; - h32 = xxh_rotl32(h32, 11) * PRIME32_1; - p++; - } - - h32 ^= h32 >> 15; - h32 *= PRIME32_2; - h32 ^= h32 >> 13; - h32 *= PRIME32_3; - h32 ^= h32 >> 16; - return h32; -} -- cgit v1.2.3