diff options
Diffstat (limited to 'ubifs-utils/common')
33 files changed, 4581 insertions, 0 deletions
diff --git a/ubifs-utils/common/README b/ubifs-utils/common/README new file mode 100644 index 0000000..8fe716e --- /dev/null +++ b/ubifs-utils/common/README @@ -0,0 +1,13 @@ +Common Library + +* crc16.h and crc16.c were copied from the linux kernel(https://elixir.bootlin.com/linux/v5.10.232/source/lib/crc16.c). +* defs.h is a bunch of definitions to smooth things over. +* hashtable/* was downloaded from http://www.cl.cam.ac.uk/~cwc22/hashtable/ +* atomic.h was downloaded from https://the-linux-channel.the-toffee-project.org/index.php?page=6-tutorials-linux-user-space-atomic-operations +* bitops.h and bitops.c were copied from the linux kernel(https://elixir.bootlin.com/linux/v5.10.232/source/lib/find_bit.c). +* compiler_attributes.h was copied from the linux kernel(https://elixir.bootlin.com/linux/v5.10.232/source/include/linux/compiler_attributes.h). +* linux_types.h was copied from the linux kernel(https://elixir.bootlin.com/linux/v5.10.232/source/include/linux/types.h overflow.h fscrypt.h). +* linux_err.h was copied from the linux kernel(https://elixir.bootlin.com/linux/v5.10.232/source/include/linux/err.h). +* hexdump.c was copied from the linux kernel(https://elixir.bootlin.com/linux/v5.10.232/source/lib/hexdump.c). +* kmem.h and kmem.c were partial copied from xfsprogs-dev(https://git.kernel.org/pub/scm/fs/xfs/xfsprogs-dev.git/). +* sort.h and sort.c were copied from the linux kernel(https://elixir.bootlin.com/linux/v5.10.232/source/lib/sort.c). diff --git a/ubifs-utils/common/atomic.h b/ubifs-utils/common/atomic.h new file mode 100644 index 0000000..95754b2 --- /dev/null +++ b/ubifs-utils/common/atomic.h @@ -0,0 +1,137 @@ +//Source: http://golubenco.org/atomic-operations.html +#ifndef __ATOMIC_H__ +#define __ATOMIC_H__ + +#define GCC_VERSION (__GNUC__ * 10000 \ + + __GNUC_MINOR__ * 100 \ + + __GNUC_PATCHLEVEL__) + +/* Check GCC version, just to be safe */ +#if GCC_VERSION < 40100 +# error atomic.h works only with GCC newer than version 4.1 +#endif /* GNUC >= 4.1 */ + +/** + * Atomic type. + */ +typedef struct { + volatile long counter; +} atomic_long_t; + +#define ATOMIC_INIT(i) { (i) } + +/** + * Read atomic variable + * @param v pointer of type atomic_long_t + * + * Atomically reads the value of @v. + */ +#define atomic_long_read(v) ((v)->counter) + +/** + * Set atomic variable + * @param v pointer of type atomic_long_t + * @param i required value + */ +#define atomic_long_set(v,i) (((v)->counter) = (i)) + +/** + * Add to the atomic variable + * @param i integer value to add + * @param v pointer of type atomic_long_t + */ +static inline void atomic_long_add( int i, atomic_long_t *v ) +{ + (void)__sync_add_and_fetch(&v->counter, i); +} + +/** + * Subtract the atomic variable + * @param i integer value to subtract + * @param v pointer of type atomic_long_t + * + * Atomically subtracts @i from @v. + */ +static inline void atomic_long_sub( int i, atomic_long_t *v ) +{ + (void)__sync_sub_and_fetch(&v->counter, i); +} + +/** + * Subtract value from variable and test result + * @param i integer value to subtract + * @param v pointer of type atomic_long_t + * + * Atomically subtracts @i from @v and returns + * true if the result is zero, or false for all + * other cases. + */ +static inline int atomic_long_sub_and_test( int i, atomic_long_t *v ) +{ + return !(__sync_sub_and_fetch(&v->counter, i)); +} + +/** + * Increment atomic variable + * @param v pointer of type atomic_long_t + * + * Atomically increments @v by 1. + */ +static inline void atomic_long_inc( atomic_long_t *v ) +{ + (void)__sync_fetch_and_add(&v->counter, 1); +} + +/** + * @brief decrement atomic variable + * @param v: pointer of type atomic_long_t + * + * Atomically decrements @v by 1. Note that the guaranteed + * useful range of an atomic_long_t is only 24 bits. + */ +static inline void atomic_long_dec( atomic_long_t *v ) +{ + (void)__sync_fetch_and_sub(&v->counter, 1); +} + +/** + * @brief Decrement and test + * @param v pointer of type atomic_long_t + * + * Atomically decrements @v by 1 and + * returns true if the result is 0, or false for all other + * cases. + */ +static inline int atomic_long_dec_and_test( atomic_long_t *v ) +{ + return !(__sync_sub_and_fetch(&v->counter, 1)); +} + +/** + * @brief Increment and test + * @param v pointer of type atomic_long_t + * + * Atomically increments @v by 1 + * and returns true if the result is zero, or false for all + * other cases. + */ +static inline int atomic_long_inc_and_test( atomic_long_t *v ) +{ + return !(__sync_add_and_fetch(&v->counter, 1)); +} + +/** + * @brief add and test if negative + * @param v pointer of type atomic_long_t + * @param i integer value to add + * + * Atomically adds @i to @v and returns true + * if the result is negative, or false when + * result is greater than or equal to zero. + */ +static inline int atomic_long_add_negative( int i, atomic_long_t *v ) +{ + return (__sync_add_and_fetch(&v->counter, i) < 0); +} + +#endif diff --git a/ubifs-utils/common/bitops.c b/ubifs-utils/common/bitops.c new file mode 100644 index 0000000..c82f1fa --- /dev/null +++ b/ubifs-utils/common/bitops.c @@ -0,0 +1,37 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Realizations of bit operations. + */ + +#include "bitops.h" +#include "defs.h" + +/* + * This is a common helper function for find_next_bit and + * find_next_zero_bit. The difference is the "invert" argument, which + * is XORed with each fetched word before searching it for one bits. + */ +unsigned long _find_next_bit(const unsigned long *addr, + unsigned long nbits, unsigned long start, unsigned long invert) +{ + unsigned long tmp; + + if (!nbits || start >= nbits) + return nbits; + + tmp = addr[start / BITS_PER_LONG] ^ invert; + + /* Handle 1st word. */ + tmp &= BITMAP_FIRST_WORD_MASK(start); + start = round_down(start, BITS_PER_LONG); + + while (!tmp) { + start += BITS_PER_LONG; + if (start >= nbits) + return nbits; + + tmp = addr[start / BITS_PER_LONG] ^ invert; + } + + return min(start + __ffs(tmp), nbits); +} diff --git a/ubifs-utils/common/bitops.h b/ubifs-utils/common/bitops.h new file mode 100644 index 0000000..3a2d3f8 --- /dev/null +++ b/ubifs-utils/common/bitops.h @@ -0,0 +1,152 @@ +#ifndef __BITOPS_H__ +#define __BITOPS_H__ + +/* + * Non-atomic bitops. + */ + +#include <stdbool.h> + +#define BITS_PER_LONG __LONG_WIDTH__ +#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) +#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_LONG) + +#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1))) + +static inline void __set_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p |= mask; +} + +static inline void set_bit(int nr, volatile unsigned long *addr) +{ + __set_bit(nr, addr); +} + +static inline void __clear_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p &= ~mask; +} + +static inline void clear_bit(int nr, volatile unsigned long *addr) +{ + __clear_bit(nr, addr); +} + +static inline bool test_bit(int nr, const volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + return (*p & mask) != 0; +} + +/* Sets and returns original value of the bit */ +static inline int test_and_set_bit(int nr, volatile unsigned long *addr) +{ + if (test_bit(nr, addr)) + return 1; + set_bit(nr, addr); + return 0; +} + +/** + * fls - find last (most-significant) bit set + * @x: the word to search + * + * This is defined the same way as ffs. + * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. + */ +static inline int fls(int x) +{ + int r = 32; + + if (!x) + return 0; + if (!(x & 0xffff0000u)) { + x <<= 16; + r -= 16; + } + if (!(x & 0xff000000u)) { + x <<= 8; + r -= 8; + } + if (!(x & 0xf0000000u)) { + x <<= 4; + r -= 4; + } + if (!(x & 0xc0000000u)) { + x <<= 2; + r -= 2; + } + if (!(x & 0x80000000u)) { + x <<= 1; + r -= 1; + } + return r; +} + +/** + * __ffs - find first bit in word. + * @word: The word to search + * + * Undefined if no bit exists, so code should check against 0 first. + */ +static inline unsigned long __ffs(unsigned long word) +{ + int num = 0; + +#if BITS_PER_LONG == 64 + if ((word & 0xffffffff) == 0) { + num += 32; + word >>= 32; + } +#endif + if ((word & 0xffff) == 0) { + num += 16; + word >>= 16; + } + if ((word & 0xff) == 0) { + num += 8; + word >>= 8; + } + if ((word & 0xf) == 0) { + num += 4; + word >>= 4; + } + if ((word & 0x3) == 0) { + num += 2; + word >>= 2; + } + if ((word & 0x1) == 0) + num += 1; + return num; +} + +unsigned long _find_next_bit(const unsigned long *addr, + unsigned long nbits, unsigned long start, unsigned long invert); + +/* + * Find the next set bit in a memory region. + */ +static inline unsigned long find_next_bit(const unsigned long *addr, + unsigned long size, unsigned long offset) +{ + return _find_next_bit(addr, size, offset, 0UL); +} + +static inline unsigned long find_next_zero_bit(const unsigned long *addr, + unsigned long size, unsigned long offset) +{ + return _find_next_bit(addr, size, offset, ~0UL); +} + +#endif diff --git a/ubifs-utils/common/compiler_attributes.h b/ubifs-utils/common/compiler_attributes.h new file mode 100644 index 0000000..bb65d3a --- /dev/null +++ b/ubifs-utils/common/compiler_attributes.h @@ -0,0 +1,79 @@ +#ifndef __COMPILER_ATTRIBUTES_H__ +#define __COMPILER_ATTRIBUTES_H__ + +#if __has_attribute(__fallthrough__) +#define fallthrough __attribute__((__fallthrough__)) +#else +#define fallthrough do {} while (0) +#endif + +#define __packed __attribute__((__packed__)) +#define __unused __attribute__((__unused__)) +#define __const __attribute__((__const__)) +#define __must_check __attribute__((__warn_unused_result__)) +#ifndef __force +#define __force +#endif + +/* + * Optional: only supported since clang >= 14.0 + * + * gcc: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-error-function-attribute + */ +#if __has_attribute(__error__) +# define __compiletime_error(msg) __attribute__((__error__(msg))) +#else +# define __compiletime_error(msg) +#endif + +#ifndef __compiletime_error +# define __compiletime_error(message) +#endif + +#ifdef __OPTIMIZE__ +# define __compiletime_assert(condition, msg, prefix, suffix) \ + do { \ + extern void prefix ## suffix(void) __compiletime_error(msg); \ + if (!(condition)) \ + prefix ## suffix(); \ + } while (0) +#else +# define __compiletime_assert(condition, msg, prefix, suffix) do { } while (0) +#endif + +#define _compiletime_assert(condition, msg, prefix, suffix) \ + __compiletime_assert(condition, msg, prefix, suffix) + +/** + * compiletime_assert - break build and emit msg if condition is false + * @condition: a compile-time constant condition to check + * @msg: a message to emit if condition is false + * + * In tradition of POSIX assert, this macro will break the build if the + * supplied condition is *false*, emitting the supplied error message if the + * compiler has support to do so. + */ +#define compiletime_assert(condition, msg) \ + _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__) + +/** + * BUILD_BUG_ON_MSG - break compile if a condition is true & emit supplied + * error message. + * @condition: the condition which the compiler should know is false. + * + * See BUILD_BUG_ON for description. + */ +#define BUILD_BUG_ON_MSG(cond, msg) compiletime_assert(!(cond), msg) + +/** + * BUILD_BUG_ON - break compile if a condition is true. + * @condition: the condition which the compiler should know is false. + * + * If you have some code which relies on certain constants being equal, or + * some other compile-time-evaluated condition, you should use BUILD_BUG_ON to + * detect if someone changes it. + */ +#define BUILD_BUG_ON(condition) \ + BUILD_BUG_ON_MSG(condition, "BUILD_BUG_ON failed: " #condition) + +#endif diff --git a/ubifs-utils/common/compr.c b/ubifs-utils/common/compr.c new file mode 100644 index 0000000..6f90151 --- /dev/null +++ b/ubifs-utils/common/compr.c @@ -0,0 +1,285 @@ +/* + * Copyright (C) 2008 Nokia Corporation. + * Copyright (C) 2008 University of Szeged, Hungary + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: Artem Bityutskiy + * Adrian Hunter + * Zoltan Sogor + */ + +#include <stdlib.h> +#include <stdio.h> +#include <stdint.h> +#include <string.h> +#ifdef WITH_LZO +#include <lzo/lzo1x.h> +#endif +#include <linux/types.h> +#ifdef WITH_ZSTD +#include <zstd.h> +#endif + +#ifdef WITH_ZLIB +#define crc32 __zlib_crc32 +#include <zlib.h> +#undef crc32 +#endif + +#include "compr.h" +#include "ubifs.h" + +static void *lzo_mem; +static unsigned long long errcnt = 0; +#ifdef WITH_LZO +extern struct ubifs_info info_; +static struct ubifs_info *c = &info_; +#endif + +#ifdef WITH_ZLIB +#define DEFLATE_DEF_LEVEL Z_DEFAULT_COMPRESSION +#define DEFLATE_DEF_WINBITS 11 +#define DEFLATE_DEF_MEMLEVEL 8 + +static int zlib_deflate(void *in_buf, size_t in_len, void *out_buf, + size_t *out_len) +{ + z_stream strm; + + strm.zalloc = NULL; + strm.zfree = NULL; + + /* + * Match exactly the zlib parameters used by the Linux kernel crypto + * API. + */ + if (deflateInit2(&strm, DEFLATE_DEF_LEVEL, Z_DEFLATED, + -DEFLATE_DEF_WINBITS, DEFLATE_DEF_MEMLEVEL, + Z_DEFAULT_STRATEGY)) { + errcnt += 1; + return -1; + } + + strm.next_in = in_buf; + strm.avail_in = in_len; + strm.total_in = 0; + + strm.next_out = out_buf; + strm.avail_out = *out_len; + strm.total_out = 0; + + if (deflate(&strm, Z_FINISH) != Z_STREAM_END) { + deflateEnd(&strm); + errcnt += 1; + return -1; + } + + if (deflateEnd(&strm) != Z_OK) { + errcnt += 1; + return -1; + } + + *out_len = strm.total_out; + + return 0; +} +#endif + +#ifdef WITH_LZO +static int lzo_compress(void *in_buf, size_t in_len, void *out_buf, + size_t *out_len) +{ + lzo_uint len; + int ret; + + len = *out_len; + ret = lzo1x_999_compress(in_buf, in_len, out_buf, &len, lzo_mem); + *out_len = len; + + if (ret != LZO_E_OK) { + errcnt += 1; + return -1; + } + + return 0; +} +#endif + +#ifdef WITH_ZSTD +static ZSTD_CCtx *zctx; + +static int zstd_compress(void *in_buf, size_t in_len, void *out_buf, + size_t *out_len) +{ + size_t ret; + + ret = ZSTD_compressCCtx(zctx, out_buf, *out_len, in_buf, in_len, 0); + if (ZSTD_isError(ret)) { + errcnt += 1; + return -1; + } + *out_len = ret; + return 0; +} +#endif + +static int no_compress(void *in_buf, size_t in_len, void *out_buf, + size_t *out_len) +{ + memcpy(out_buf, in_buf, in_len); + *out_len = in_len; + return 0; +} + +static char *zlib_buf; + +#if defined(WITH_LZO) && defined(WITH_ZLIB) +static int favor_lzo_compress(void *in_buf, size_t in_len, void *out_buf, + size_t *out_len, int *type) +{ + int lzo_ret, zlib_ret; + size_t lzo_len, zlib_len; + + lzo_len = zlib_len = *out_len; + lzo_ret = lzo_compress(in_buf, in_len, out_buf, &lzo_len); + zlib_ret = zlib_deflate(in_buf, in_len, zlib_buf, &zlib_len); + + if (lzo_ret && zlib_ret) + /* Both compressors failed */ + return -1; + + if (!lzo_ret && !zlib_ret) { + double percent; + + /* Both compressors succeeded */ + if (lzo_len <= zlib_len ) + goto select_lzo; + + percent = (double)zlib_len / (double)lzo_len; + percent *= 100; + if (percent > 100 - c->favor_percent) + goto select_lzo; + goto select_zlib; + } + + if (lzo_ret) + /* Only zlib compressor succeeded */ + goto select_zlib; + + /* Only LZO compressor succeeded */ + +select_lzo: + *out_len = lzo_len; + *type = UBIFS_COMPR_LZO; + return 0; + +select_zlib: + *out_len = zlib_len; + *type = UBIFS_COMPR_ZLIB; + memcpy(out_buf, zlib_buf, zlib_len); + return 0; +} +#endif + +int compress_data(void *in_buf, size_t in_len, void *out_buf, size_t *out_len, + int type) +{ + int ret; + + if (in_len < UBIFS_MIN_COMPR_LEN) { + no_compress(in_buf, in_len, out_buf, out_len); + return UBIFS_COMPR_NONE; + } + +#if defined(WITH_LZO) && defined(WITH_ZLIB) + if (c->favor_lzo) + ret = favor_lzo_compress(in_buf, in_len, out_buf, out_len, &type); + else { +#else + { +#endif + switch (type) { +#ifdef WITH_LZO + case UBIFS_COMPR_LZO: + ret = lzo_compress(in_buf, in_len, out_buf, out_len); + break; +#endif +#ifdef WITH_ZLIB + case UBIFS_COMPR_ZLIB: + ret = zlib_deflate(in_buf, in_len, out_buf, out_len); + break; +#endif +#ifdef WITH_ZSTD + case UBIFS_COMPR_ZSTD: + ret = zstd_compress(in_buf, in_len, out_buf, out_len); + break; +#endif + case UBIFS_COMPR_NONE: + ret = 1; + break; + default: + errcnt += 1; + ret = 1; + break; + } + } + if (ret || *out_len >= in_len) { + no_compress(in_buf, in_len, out_buf, out_len); + return UBIFS_COMPR_NONE; + } + return type; +} + +int init_compression(void) +{ +#ifndef WITH_LZO + lzo_mem = NULL; +#else + lzo_mem = malloc(LZO1X_999_MEM_COMPRESS); + if (!lzo_mem) + return -1; +#endif + +#ifndef WITH_ZLIB + zlib_buf = NULL; +#else + zlib_buf = malloc(UBIFS_BLOCK_SIZE * WORST_COMPR_FACTOR); + if (!zlib_buf) + goto err; +#endif + +#ifdef WITH_ZSTD + zctx = ZSTD_createCCtx(); + if (!zctx) + goto err; +#endif + + return 0; +err: + free(zlib_buf); + free(lzo_mem); + return -1; +} + +void destroy_compression(void) +{ + free(zlib_buf); + free(lzo_mem); +#ifdef WITH_ZSTD + ZSTD_freeCCtx(zctx); +#endif + if (errcnt) + fprintf(stderr, "%llu compression errors occurred\n", errcnt); +} diff --git a/ubifs-utils/common/compr.h b/ubifs-utils/common/compr.h new file mode 100644 index 0000000..3e8e9b6 --- /dev/null +++ b/ubifs-utils/common/compr.h @@ -0,0 +1,39 @@ +/* + * Copyright (C) 2008 Nokia Corporation. + * Copyright (C) 2008 University of Szeged, Hungary + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: Artem Bityutskiy + * Adrian Hunter + * Zoltan Sogor + */ + +#ifndef __UBIFS_COMPRESS_H__ +#define __UBIFS_COMPRESS_H__ + +/* + * Compressors may end-up with more data in the output buffer than in the input + * buffer. This constant defined the worst case factor, i.e. we assume that the + * output buffer may be at max. WORST_COMPR_FACTOR times larger than input + * buffer. + */ +#define WORST_COMPR_FACTOR 4 + +int compress_data(void *in_buf, size_t in_len, void *out_buf, size_t *out_len, + int type); +int init_compression(void); +void destroy_compression(void); + +#endif diff --git a/ubifs-utils/common/crc16.c b/ubifs-utils/common/crc16.c new file mode 100644 index 0000000..a19512e --- /dev/null +++ b/ubifs-utils/common/crc16.c @@ -0,0 +1,56 @@ +/* + * This code was taken from the linux kernel. The license is GPL Version 2. + */ + +#include "crc16.h" + +/** CRC table for the CRC-16. The poly is 0x8005 (x^16 + x^15 + x^2 + 1) */ +uint16_t const crc16_table[256] = { + 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241, + 0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440, + 0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40, + 0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841, + 0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40, + 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41, + 0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641, + 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040, + 0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240, + 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441, + 0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41, + 0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840, + 0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41, + 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40, + 0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640, + 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041, + 0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240, + 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441, + 0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41, + 0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840, + 0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41, + 0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40, + 0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640, + 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041, + 0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241, + 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440, + 0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40, + 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841, + 0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40, + 0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41, + 0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641, + 0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040 +}; + +/** + * crc16 - compute the CRC-16 for the data buffer + * @crc: previous CRC value + * @buffer: data pointer + * @len: number of bytes in the buffer + * + * Returns the updated CRC value. + */ +uint16_t crc16(uint16_t crc, uint8_t const *buffer, size_t len) +{ + while (len--) + crc = crc16_byte(crc, *buffer++); + return crc; +} diff --git a/ubifs-utils/common/crc16.h b/ubifs-utils/common/crc16.h new file mode 100644 index 0000000..539d21a --- /dev/null +++ b/ubifs-utils/common/crc16.h @@ -0,0 +1,27 @@ +/* + * Implements the standard CRC-16: + * Width 16 + * Poly 0x8005 (x^16 + x^15 + x^2 + 1) + * Init 0 + * + * Copyright (c) 2005 Ben Gardner <bgardner@wabtec.com> + * + * This code was taken from the linux kernel. The license is GPL Version 2. + */ + +#ifndef __CRC16_H__ +#define __CRC16_H__ + +#include <stdlib.h> +#include <stdint.h> + +extern uint16_t const crc16_table[256]; + +extern uint16_t crc16(uint16_t crc, const uint8_t *buffer, size_t len); + +static inline uint16_t crc16_byte(uint16_t crc, const uint8_t data) +{ + return (crc >> 8) ^ crc16_table[(crc ^ data) & 0xff]; +} + +#endif /* __CRC16_H__ */ diff --git a/ubifs-utils/common/crypto.c b/ubifs-utils/common/crypto.c new file mode 100644 index 0000000..e4ef349 --- /dev/null +++ b/ubifs-utils/common/crypto.c @@ -0,0 +1,370 @@ +/* + * Copyright (C) 2017 sigma star gmbh + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: David Oberhollenzer <david.oberhollenzer@sigma-star.at> + */ + +#include <openssl/evp.h> +#include <openssl/err.h> +#include <openssl/rand.h> +#include <string.h> +#include <assert.h> + +#include "linux_types.h" +#include "fscrypt.h" +#include "defs.h" +#include "ubifs.h" + +static int do_hash(const EVP_MD *md, const unsigned char *in, size_t len, unsigned char *out) +{ + unsigned int out_len; + EVP_MD_CTX *mdctx = EVP_MD_CTX_create(); + + if (!mdctx) + return -1; + + if (EVP_DigestInit_ex(mdctx, md, NULL) != 1) + return -1; + + if(EVP_DigestUpdate(mdctx, in, len) != 1) + return -1; + + if(EVP_DigestFinal_ex(mdctx, out, &out_len) != 1) + return -1; + + EVP_MD_CTX_destroy(mdctx); + + return 0; +} + +static int check_iv_key_size(const EVP_CIPHER *cipher, size_t key_len, + size_t iv_len) +{ + if ((size_t)EVP_CIPHER_key_length(cipher) != key_len) { + errmsg("Cipher key length mismatch. Expected %lu, got %d", + (unsigned long)key_len, EVP_CIPHER_key_length(cipher)); + return -1; + } + + if (iv_len && (size_t)EVP_CIPHER_iv_length(cipher) != iv_len) { + errmsg("Cipher IV length mismatch. Expected %lu, got %d", + (unsigned long)iv_len, EVP_CIPHER_key_length(cipher)); + return -1; + } + + return 0; +} + +static ssize_t do_encrypt(const EVP_CIPHER *cipher, + const void *plaintext, size_t size, + const void *key, size_t key_len, + const void *iv, size_t iv_len, + void *ciphertext) +{ + int ciphertext_len, len; + EVP_CIPHER_CTX *ctx; + + if (check_iv_key_size(cipher, key_len, iv_len)) + return -1; + + if (!(ctx = EVP_CIPHER_CTX_new())) + goto fail; + + EVP_CIPHER_CTX_set_padding(ctx, 0); + + if (EVP_EncryptInit_ex(ctx, cipher, NULL, key, iv) != 1) + goto fail_ctx; + + if (EVP_EncryptUpdate(ctx, ciphertext, &len, plaintext, size) != 1) + goto fail_ctx; + + ciphertext_len = len; + + if (cipher == EVP_aes_256_xts()) { + if (EVP_EncryptFinal(ctx, ciphertext + ciphertext_len, &len) != 1) + goto fail_ctx; + + ciphertext_len += len; + } + + EVP_CIPHER_CTX_free(ctx); + return ciphertext_len; +fail_ctx: + ERR_print_errors_fp(stderr); + EVP_CIPHER_CTX_free(ctx); + return -1; +fail: + ERR_print_errors_fp(stderr); + return -1; +} + +static ssize_t gen_essiv_salt(const void *iv, size_t iv_len, const void *key, size_t key_len, void *salt) +{ + size_t ret; + const EVP_CIPHER *cipher; + void *sha256 = xzalloc(EVP_MD_size(EVP_sha256())); + + cipher = EVP_aes_256_ecb(); + if (!cipher) { + errmsg("OpenSSL: Cipher AES-256-ECB is not supported"); + goto fail; + } + + if (do_hash(EVP_sha256(), key, key_len, sha256) != 0) { + errmsg("sha256 failed"); + goto fail; + } + + ret = do_encrypt(cipher, iv, iv_len, sha256, EVP_MD_size(EVP_sha256()), NULL, 0, salt); + if (ret != iv_len) { + errmsg("Unable to compute ESSIV salt, return value %zi instead of %zi", ret, iv_len); + goto fail; + } + + free(sha256); + + return ret; +fail: + free(sha256); + return -1; +} + +static ssize_t encrypt_block(const void *plaintext, size_t size, + const void *key, uint64_t block_index, + void *ciphertext, const EVP_CIPHER *cipher) +{ + size_t key_len, ivsize; + void *tweak; + struct { + uint64_t index; + uint8_t padding[FS_IV_SIZE - sizeof(uint64_t)]; + } iv; + + ivsize = EVP_CIPHER_iv_length(cipher); + key_len = EVP_CIPHER_key_length(cipher); + + iv.index = cpu_to_le64(block_index); + memset(iv.padding, 0, sizeof(iv.padding)); + + if (cipher == EVP_aes_128_cbc()) { + tweak = alloca(ivsize); + if (gen_essiv_salt(&iv, FS_IV_SIZE, key, key_len, tweak) < 0) + return -1; + } else { + tweak = &iv; + } + + return do_encrypt(cipher, plaintext, size, key, key_len, tweak, + ivsize, ciphertext); +} + +static ssize_t encrypt_block_aes128_cbc(const void *plaintext, size_t size, + const void *key, uint64_t block_index, + void *ciphertext) +{ + const EVP_CIPHER *cipher = EVP_aes_128_cbc(); + + if (!cipher) { + errmsg("OpenSSL: Cipher AES-128-CBC is not supported"); + return -1; + } + return encrypt_block(plaintext, size, key, block_index, + ciphertext, cipher); +} + +static ssize_t encrypt_block_aes256_xts(const void *plaintext, size_t size, + const void *key, uint64_t block_index, + void *ciphertext) +{ + const EVP_CIPHER *cipher = EVP_aes_256_xts(); + + if (!cipher) { + errmsg("OpenSSL: Cipher AES-256-XTS is not supported"); + return -1; + } + return encrypt_block(plaintext, size, key, block_index, + ciphertext, cipher); +} + +static void block_swap(uint8_t *ciphertext, size_t i0, size_t i1, + size_t size) +{ + uint8_t temp[size], *p0, *p1; + + p0 = ciphertext + i0 * size; + p1 = ciphertext + i1 * size; + + memcpy(temp, p0, size); + memcpy(p0, p1, size); + memcpy(p1, temp, size); +} + +static ssize_t encrypt_cbc_cts(const void *plaintext, size_t size, + const void *key, void *ciphertext, + const EVP_CIPHER *cipher) +{ + size_t diff, padded_size, count, ivsize; + uint8_t iv[EVP_MAX_IV_LENGTH], *padded; + ssize_t ret, key_len; + + key_len = EVP_CIPHER_key_length(cipher); + ivsize = EVP_CIPHER_iv_length(cipher); + + memset(iv, 0, ivsize); + + diff = size % ivsize; + + if (diff) { + padded_size = size - diff + ivsize; + padded = size > 256 ? malloc(padded_size) : alloca(padded_size); + + memcpy(padded, plaintext, size); + memset(padded + size, 0, padded_size - size); + + ret = do_encrypt(cipher, padded, padded_size, key, key_len, + iv, ivsize, ciphertext); + + if (size > 256) + free(padded); + } else { + ret = do_encrypt(cipher, plaintext, size, key, key_len, + iv, ivsize, ciphertext); + } + + if (ret < 0) + return ret; + + count = ret / ivsize; + + if (count > 1) + block_swap(ciphertext, count - 2, count - 1, ivsize); + + return size; +} + +static ssize_t encrypt_aes128_cbc_cts(const void *plaintext, size_t size, + const void *key, void *ciphertext) +{ + const EVP_CIPHER *cipher = EVP_aes_128_cbc(); + if (!cipher) { + errmsg("OpenSSL: Cipher AES-128-CBC is not supported"); + return -1; + } + + return encrypt_cbc_cts(plaintext, size, key, ciphertext, cipher); +} + +static ssize_t encrypt_aes256_cbc_cts(const void *plaintext, size_t size, + const void *key, void *ciphertext) +{ + const EVP_CIPHER *cipher = EVP_aes_256_cbc(); + if (!cipher) { + errmsg("OpenSSL: Cipher AES-256-CBC is not supported"); + return -1; + } + + return encrypt_cbc_cts(plaintext, size, key, ciphertext, cipher); +} + +ssize_t derive_key_aes(const void *deriving_key, const void *source_key, + size_t source_key_len, void *derived_key) +{ + const EVP_CIPHER *cipher; + size_t aes_key_len; + + cipher = EVP_aes_128_ecb(); + if (!cipher) { + errmsg("OpenSSL: Cipher AES-128-ECB is not supported"); + return -1; + } + aes_key_len = EVP_CIPHER_key_length(cipher); + + return do_encrypt(cipher, source_key, source_key_len, deriving_key, + aes_key_len, NULL, 0, derived_key); +} + +int derive_key_descriptor(const void *source_key, void *descriptor) +{ + int ret = -1; + void *hash1 = xzalloc(EVP_MD_size(EVP_sha512())); + void *hash2 = xzalloc(EVP_MD_size(EVP_sha512())); + + if (do_hash(EVP_sha512(), source_key, FS_MAX_KEY_SIZE, hash1) != 0) + goto out; + + if (do_hash(EVP_sha512(), hash1, EVP_MD_size(EVP_sha512()), hash2) != 0) + goto out; + + memcpy(descriptor, hash2, FS_KEY_DESCRIPTOR_SIZE); + + ret = 0; +out: + free(hash1); + free(hash2); + return ret; +} + +static struct cipher ciphers[] = { + { + .name = "AES-128-CBC", + .key_length = 16, + .encrypt_block = encrypt_block_aes128_cbc, + .encrypt_fname = encrypt_aes128_cbc_cts, + .fscrypt_block_mode = FS_ENCRYPTION_MODE_AES_128_CBC, + .fscrypt_fname_mode = FS_ENCRYPTION_MODE_AES_128_CTS, + }, { + .name = "AES-256-XTS", + .key_length = 64, + .encrypt_block = encrypt_block_aes256_xts, + .encrypt_fname = encrypt_aes256_cbc_cts, + .fscrypt_block_mode = FS_ENCRYPTION_MODE_AES_256_XTS, + .fscrypt_fname_mode = FS_ENCRYPTION_MODE_AES_256_CTS, + } +}; + +int crypto_init(void) +{ + ERR_load_crypto_strings(); + RAND_poll(); + return 0; +} + +void crypto_cleanup(void) +{ + EVP_cleanup(); + ERR_free_strings(); +} + +struct cipher *get_cipher(const char *name) +{ + size_t i; + + for (i = 0; i < sizeof(ciphers) / sizeof(ciphers[0]); ++i) { + if (!strcmp(ciphers[i].name, name)) + return ciphers + i; + } + + return NULL; +} + +void list_ciphers(FILE *fp) +{ + size_t i; + + for (i = 0; i < sizeof(ciphers) / sizeof(ciphers[0]); ++i) { + fprintf(fp, "\t%s\n", ciphers[i].name); + } +} diff --git a/ubifs-utils/common/crypto.h b/ubifs-utils/common/crypto.h new file mode 100644 index 0000000..b6ffad1 --- /dev/null +++ b/ubifs-utils/common/crypto.h @@ -0,0 +1,58 @@ +/* + * Copyright (C) 2017 sigma star gmbh + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: David Oberhollenzer <david.oberhollenzer@sigma-star.at> + */ + +#ifndef UBIFS_CRYPTO_H +#define UBIFS_CRYPTO_H + +#include <sys/types.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> + + +struct cipher { + const char *name; + unsigned int key_length; + + ssize_t (*encrypt_block)(const void *plaintext, size_t size, + const void *key, uint64_t block_index, + void *ciphertext); + + ssize_t (*encrypt_fname)(const void *plaintext, size_t size, + const void *key, void *ciphertext); + + unsigned int fscrypt_block_mode; + unsigned int fscrypt_fname_mode; +}; + +#ifdef WITH_CRYPTO +int crypto_init(void); +void crypto_cleanup(void); +ssize_t derive_key_aes(const void *deriving_key, const void *source_key, + size_t source_key_len, void *derived_key); +int derive_key_descriptor(const void *source_key, void *descriptor); +struct cipher *get_cipher(const char *name); +void list_ciphers(FILE *fp); +#else +static inline int crypto_init(void) { return 0;} +static inline void crypto_cleanup(void) {} +#endif /* WITH_CRYPTO */ + +#endif /* UBIFS_CRYPTO_H */ + diff --git a/ubifs-utils/common/defs.h b/ubifs-utils/common/defs.h new file mode 100644 index 0000000..d5edbf6 --- /dev/null +++ b/ubifs-utils/common/defs.h @@ -0,0 +1,126 @@ +/* + * Greate deal of the code was taken from the kernel UBIFS implementation, and + * this file contains some "glue" definitions. + */ + +#ifndef __UBIFS_DEFS_H__ +#define __UBIFS_DEFS_H__ + +#include <stdlib.h> +#include <stdio.h> +#include <unistd.h> +#include <limits.h> +#include <errno.h> +#include <time.h> +#include <assert.h> +#if HAVE_EXECINFO_H +#include <execinfo.h> +#else +#include "libmissing.h" +#endif +#include "ubifs.h" + +/* common.h requires the PROGRAM_NAME macro */ +extern struct ubifs_info info_; +#define PROGRAM_NAME (info_.program_name) +#include "common.h" + +#define MKFS_PROGRAM_NAME "mkfs.ubifs" +#define FSCK_PROGRAM_NAME "fsck.ubifs" + +enum { MKFS_PROGRAM_TYPE = 0, FSCK_PROGRAM_TYPE }; + +enum { + DUMP_PREFIX_NONE, + DUMP_PREFIX_ADDRESS, + DUMP_PREFIX_OFFSET +}; + +#define pr_debug(fmt, ...) do { if (info_.debug_level >= DEBUG_LEVEL) \ + printf("<DEBUG> %s[%d] (%s): %s: " fmt, PROGRAM_NAME, getpid(), \ + info_.dev_name, __FUNCTION__, ##__VA_ARGS__); \ +} while(0) + +#define pr_notice(fmt, ...) do { if (info_.debug_level >= INFO_LEVEL) \ + printf("<INFO> %s[%d] (%s): %s: " fmt, PROGRAM_NAME, getpid(), \ + info_.dev_name, __FUNCTION__, ##__VA_ARGS__); \ +} while(0) + +#define pr_warn(fmt, ...) do { if (info_.debug_level >= WARN_LEVEL) \ + printf("<WARN> %s[%d] (%s): %s: " fmt, PROGRAM_NAME, getpid(), \ + info_.dev_name, __FUNCTION__, ##__VA_ARGS__); \ +} while(0) + +#define pr_err(fmt, ...) do { if (info_.debug_level >= ERR_LEVEL) \ + printf("<ERROR> %s[%d] (%s): %s: " fmt, PROGRAM_NAME, getpid(), \ + info_.dev_name, __FUNCTION__, ##__VA_ARGS__); \ +} while(0) + +#define pr_cont(fmt, ...) do { if (info_.debug_level >= ERR_LEVEL) \ + printf(fmt, ##__VA_ARGS__); \ +} while(0) + +static inline void dump_stack(void) +{ +#define STACK_SIZE 512 + int j, nptrs; + void *buffer[STACK_SIZE]; + char **strings; + + if (info_.debug_level < ERR_LEVEL) + return; + + nptrs = backtrace(buffer, STACK_SIZE); + strings = backtrace_symbols(buffer, nptrs); + + printf("dump_stack:\n"); + for (j = 0; j < nptrs; j++) + printf("%s\n", strings[j]); + + free(strings); +} + +static inline u32 get_random_u32(void) +{ + srand(time(NULL)); + return rand(); +} + +static inline time_t ktime_get_seconds(void) +{ + return time(NULL); +} + +#define likely(x) (x) +#define unlikely(x) (x) + +#define cond_resched() do {} while(0) + +#define BUG() do { \ + assert(0); \ +} while(0) +#define BUG_ON(cond) do { \ + assert(!cond); \ +} while(0) + +#define smp_wmb() do {} while(0) +#define smp_rmb() do {} while(0) +#define smp_mb__before_atomic() do {} while(0) +#define smp_mb__after_atomic() do {} while(0) + +#define min3(x, y, z) min((typeof(x))min(x, y), z) + +static inline u64 div_u64(u64 dividend, u32 divisor) +{ + return dividend / divisor; +} + +#if INT_MAX != 0x7fffffff +#error : sizeof(int) must be 4 for this program +#endif + +#if (~0ULL) != 0xffffffffffffffffULL +#error : sizeof(long long) must be 8 for this program +#endif + +#endif diff --git a/ubifs-utils/common/devtable.c b/ubifs-utils/common/devtable.c new file mode 100644 index 0000000..2e581ff --- /dev/null +++ b/ubifs-utils/common/devtable.c @@ -0,0 +1,544 @@ +/* + * Copyright (C) 2008 Nokia Corporation. + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Author: Artem Bityutskiy + * + * Part of the device table parsing code was taken from the mkfs.jffs2 utility. + * The original author of that code is Erik Andersen, hence: + * Copyright (C) 2001, 2002 Erik Andersen <andersen@codepoet.org> + */ + +/* + * This file implemented device table support. Device table entries take the + * form of: + * <path> <type> <mode> <uid> <gid> <major> <minor> <start> <inc> <count> + * /dev/mem c 640 0 0 1 1 0 0 - + * + * Type can be one of: + * f A regular file + * d Directory + * c Character special device file + * b Block special device file + * p Fifo (named pipe) + * l Link + * + * Don't bother with hard links (special cases of regular files), or sockets + * (why bother). + * + * Regular files must exist in the target root directory. If a char, block, + * fifo, or directory does not exist, it will be created. + * + * Please, refer the device_table.txt file which can be found at MTD utilities + * for more information about what the device table is. + */ + +#include <string.h> +#include <ctype.h> +#include <sys/stat.h> +#include <sys/types.h> +#include <sys/sysmacros.h> + +#include "devtable.h" +#include "ubifs.h" +#include "defs.h" +#include "hashtable/hashtable.h" +#include "hashtable/hashtable_itr.h" + +/* + * The hash table which contains paths to files/directories/device nodes + * referred to in the device table. For example, if the device table refers + * "/dev/loop0", the @path_htbl will contain "/dev" element. + */ +static struct hashtable *path_htbl; + +/* Hash function used for hash tables */ +static unsigned int r5_hash(void *s) +{ + unsigned int a = 0; + const signed char *str = s; + + while (*str) { + a += *str << 4; + a += *str >> 4; + a *= 11; + str++; + } + + return a; +} + +/* + * Check whether 2 keys of a hash table are equivalent. The keys are path/file + * names, so we simply use 'strcmp()'. + */ +static int is_equivalent(void *k1, void *k2) +{ + return !strcmp(k1, k2); +} + +/** + * separate_last - separate out the last path component + * @buf: the path to split + * @len: length of the @buf string + * @path: the beginning of path is returned here + * @name: the last path component is returned here + * + * This helper function separates out the the last component of the full path + * string. For example, "/dev/loop" would be split on "/dev" and "loop". This + * function allocates memory for @path and @name and return the result there. + * Returns zero in case of success and a negative error code in case of + * failure. + */ +static int separate_last(const char *buf, int len, char **path, char **name) +{ + int path_len = len, name_len; + const char *p = buf + len, *n; + + while (*--p != '/') + path_len -= 1; + + /* Drop the final '/' unless this is the root directory */ + name_len = len - path_len; + n = buf + path_len; + if (path_len > 1) + path_len -= 1; + + *path = malloc(path_len + 1); + if (!*path) + return errmsg("cannot allocate %d bytes of memory", + path_len + 1); + memcpy(*path, buf, path_len); + (*path)[path_len] = '\0'; + + *name = malloc(name_len + 1); + if (!*name) { + free(*path); + return errmsg("cannot allocate %d bytes of memory", + name_len + 1); + } + memcpy(*name, n, name_len + 1); + + return 0; +} + +static int interpret_table_entry(const char *line) +{ + char buf[1024], type, *path = NULL, *name = NULL; + int len; + struct path_htbl_element *ph_elt = NULL; + struct name_htbl_element *nh_elt = NULL; + unsigned int mode = 0755, uid = 0, gid = 0, major = 0, minor = 0; + unsigned int start = 0, increment = 0, count = 0; + + if (sscanf(line, "%1023s %c %o %u %u %u %u %u %u %u", + buf, &type, &mode, &uid, &gid, &major, &minor, + &start, &increment, &count) < 0) + return sys_errmsg("sscanf failed"); + + pr_debug("name %s, type %c, mode %o, uid %u, gid %u, major %u, " + "minor %u, start %u, inc %u, cnt %u\n", + buf, type, mode, uid, gid, major, minor, start, + increment, count); + + len = strnlen(buf, 1024); + if (len == 0) + return errmsg("empty path"); + if (len == 1024) + return errmsg("too long path"); + + if (buf[0] != '/') + return errmsg("device table entries require absolute paths"); + if (strstr(buf, "//")) + return errmsg("'//' cannot be used in the path"); + if (len > 1 && buf[len - 1] == '/') + return errmsg("do not put '/' at the end"); + + if (strstr(buf, "/./") || strstr(buf, "/../") || + !strcmp(buf + len - 2, "/.") || !strcmp(buf + len - 3, "/..")) + return errmsg("'.' and '..' cannot be used in the path"); + + switch (type) { + case 'd': + mode |= S_IFDIR; + break; + case 'f': + mode |= S_IFREG; + break; + case 'p': + mode |= S_IFIFO; + break; + case 'c': + mode |= S_IFCHR; + break; + case 'b': + mode |= S_IFBLK; + break; + case 'l': + mode |= S_IFLNK; + if ((mode & 0777) != 0777) + return errmsg("link permission must be 0777"); + break; + default: + return errmsg("unsupported file type '%c'", type); + } + + if (separate_last(buf, len, &path, &name)) + return -1; + + /* + * Check if this path already exist in the path hash table and add it + * if it is not. + */ + ph_elt = hashtable_search(path_htbl, path); + if (!ph_elt) { + pr_debug("inserting '%s' into path hash table\n", path); + ph_elt = malloc(sizeof(struct path_htbl_element)); + if (!ph_elt) { + errmsg("cannot allocate %zd bytes of memory", + sizeof(struct path_htbl_element)); + goto out_free; + } + + if (!hashtable_insert(path_htbl, path, ph_elt)) { + errmsg("cannot insert into path hash table"); + goto out_free; + } + + ph_elt->path = path; + path = NULL; + ph_elt->name_htbl = create_hashtable(128, &r5_hash, + &is_equivalent); + if (!ph_elt->name_htbl) { + errmsg("cannot create name hash table"); + goto out_free; + } + } + + if (increment != 0 && count == 0) { + errmsg("count cannot be zero if increment is non-zero"); + goto out_free; + } + + /* + * Add the file/directory/device node (last component of the path) to + * the name hashtable. The name hashtable resides in the corresponding + * path hashtable element. + */ + + if (count == 0) { + /* This entry does not require any iterating */ + nh_elt = malloc(sizeof(struct name_htbl_element)); + if (!nh_elt) { + errmsg("cannot allocate %zd bytes of memory", + sizeof(struct name_htbl_element)); + goto out_free; + } + + nh_elt->mode = mode; + nh_elt->uid = uid; + nh_elt->gid = gid; + nh_elt->dev = makedev(major, minor); + + pr_debug("inserting '%s' into name hash table (major %d, minor %d)\n", + name, major(nh_elt->dev), minor(nh_elt->dev)); + + if (hashtable_search(ph_elt->name_htbl, name)) { + errmsg("'%s' is referred twice", buf); + goto out_free; + } + + nh_elt->name = name; + if (!hashtable_insert(ph_elt->name_htbl, name, nh_elt)) { + errmsg("cannot insert into name hash table"); + goto out_free; + } + } else { + int i, num = start + count, len = strlen(name) + 20; + char *nm; + + for (i = start; i < num; i++) { + nh_elt = malloc(sizeof(struct name_htbl_element)); + if (!nh_elt) { + errmsg("cannot allocate %zd bytes of memory", + sizeof(struct name_htbl_element)); + goto out_free; + } + + nh_elt->mode = mode; + nh_elt->uid = uid; + nh_elt->gid = gid; + nh_elt->dev = makedev(major, minor + (i - start) * increment); + + nm = malloc(len); + if (!nm) { + errmsg("cannot allocate %d bytes of memory", len); + goto out_free; + } + + sprintf(nm, "%s%d", name, i); + nh_elt->name = nm; + + pr_debug("inserting '%s' into name hash table (major %d, minor %d)\n", + nm, major(nh_elt->dev), minor(nh_elt->dev)); + + if (hashtable_search(ph_elt->name_htbl, nm)) { + errmsg("'%s' is referred twice", buf); + free (nm); + goto out_free; + } + + if (!hashtable_insert(ph_elt->name_htbl, nm, nh_elt)) { + errmsg("cannot insert into name hash table"); + free (nm); + goto out_free; + } + } + free(name); + name = NULL; + } + + return 0; + +out_free: + free(ph_elt); + free(nh_elt); + free(path); + free(name); + return -1; +} + +/** + * parse_devtable - parse the device table. + * @tbl_file: device table file name + * + * This function parses the device table and prepare the hash table which will + * later be used by mkfs.ubifs to create the specified files/device nodes. + * Returns zero in case of success and a negative error code in case of + * failure. + */ +int parse_devtable(const char *tbl_file) +{ + FILE *f; + char *line = NULL; + struct stat st; + size_t len; + + pr_debug("parsing device table file '%s'\n", tbl_file); + + path_htbl = create_hashtable(128, &r5_hash, &is_equivalent); + if (!path_htbl) + return errmsg("cannot create path hash table"); + + f = fopen(tbl_file, "r"); + if (!f) + return sys_errmsg("cannot open '%s'", tbl_file); + + if (fstat(fileno(f), &st) < 0) { + sys_errmsg("cannot stat '%s'", tbl_file); + goto out_close; + } + + if (st.st_size < 10) { + sys_errmsg("'%s' is too short", tbl_file); + goto out_close; + } + + /* + * The general plan now is to read in one line at a time, check for + * leading comment delimiters ('#'), then try and parse the line as a + * device table + */ + while (getline(&line, &len, f) != -1) { + /* First trim off any white-space */ + len = strlen(line); + + /* Trim trailing white-space */ + while (len > 0 && isspace(line[len - 1])) + line[--len] = '\0'; + /* Trim leading white-space */ + memmove(line, &line[strspn(line, " \n\r\t\v")], len); + + /* How long are we after trimming? */ + len = strlen(line); + + /* If this is not a comment line, try to interpret it */ + if (len && *line != '#') { + if (interpret_table_entry(line)) { + errmsg("cannot parse '%s'", line); + goto out_close; + } + } + + free(line); + line = NULL; + } + + pr_debug("finished parsing\n"); + fclose(f); + return 0; + +out_close: + fclose(f); + free(line); + free_devtable_info(); + return -1; +} + +/** + * devtbl_find_path - find a path in the path hash table. + * @path: UBIFS path to find. + * + * This looks up the path hash table. Returns the path hash table element + * reference if @path was found and %NULL if not. + */ +struct path_htbl_element *devtbl_find_path(const char *path) +{ + if (!path_htbl) + return NULL; + + return hashtable_search(path_htbl, (void *)path); +} + +/** + * devtbl_find_name - find a name in the name hash table. + * @ph_etl: path hash table element to find at + * @name: name to find + * + * This looks up the name hash table. Returns the name hash table element + * reference if @name found and %NULL if not. + */ +struct name_htbl_element *devtbl_find_name(struct path_htbl_element *ph_elt, + const char *name) +{ + if (!path_htbl) + return NULL; + + return hashtable_search(ph_elt->name_htbl, (void *)name); +} + +/** + * override_attributes - override inode attributes. + * @st: struct stat object to containing the attributes to override + * @ph_elt: path hash table element object + * @nh_elt: name hash table element object containing the new values + * + * The device table file may override attributes like UID of files. For + * example, the device table may contain a "/dev" entry, and the UBIFS FS on + * the host may contain "/dev" directory. In this case the attributes of the + * "/dev" directory inode has to be as the device table specifies. + * + * Note, the hash element is removed by this function as well. + */ +int override_attributes(struct stat *st, struct path_htbl_element *ph_elt, + struct name_htbl_element *nh_elt) +{ + if (!path_htbl) + return 0; + + if (S_ISCHR(st->st_mode) || S_ISBLK(st->st_mode) || + S_ISFIFO(st->st_mode)) + return errmsg("%s/%s both exists at UBIFS root at host, " + "and is referred from the device table", + strcmp(ph_elt->path, "/") ? ph_elt->path : "", + nh_elt->name); + + if ((st->st_mode & S_IFMT) != (nh_elt->mode & S_IFMT)) + return errmsg("%s/%s is referred from the device table also exists in " + "the UBIFS root directory at host, but the file type is " + "different", strcmp(ph_elt->path, "/") ? ph_elt->path : "", + nh_elt->name); + + pr_debug("set UID %d, GID %d, mode %o for %s/%s as device table says\n", + nh_elt->uid, nh_elt->gid, nh_elt->mode, ph_elt->path, nh_elt->name); + + st->st_uid = nh_elt->uid; + st->st_gid = nh_elt->gid; + st->st_mode = nh_elt->mode; + + hashtable_remove(ph_elt->name_htbl, (void *)nh_elt->name); + return 0; +} + +/** + * first_name_htbl_element - return first element of the name hash table. + * @ph_elt: the path hash table the name hash table belongs to + * @itr: double pointer to a 'struct hashtable_itr' object where the + * information about further iterations is stored + * + * This function implements name hash table iteration together with + * 'next_name_htbl_element()'. Returns the first name hash table element or + * %NULL if the hash table is empty. + */ +struct name_htbl_element * +first_name_htbl_element(struct path_htbl_element *ph_elt, + struct hashtable_itr **itr) +{ + if (!path_htbl || !ph_elt || hashtable_count(ph_elt->name_htbl) == 0) + return NULL; + + *itr = hashtable_iterator(ph_elt->name_htbl); + return hashtable_iterator_value(*itr); +} + +/** + * first_name_htbl_element - return next element of the name hash table. + * @ph_elt: the path hash table the name hash table belongs to + * @itr: double pointer to a 'struct hashtable_itr' object where the + * information about further iterations is stored + * + * This function implements name hash table iteration together with + * 'first_name_htbl_element()'. Returns the next name hash table element or + * %NULL if there are no more elements. + */ +struct name_htbl_element * +next_name_htbl_element(struct path_htbl_element *ph_elt, + struct hashtable_itr **itr) +{ + if (!path_htbl || !ph_elt || !hashtable_iterator_advance(*itr)) + return NULL; + + return hashtable_iterator_value(*itr); +} + +/** + * free_devtable_info - free device table information. + * + * This function frees the path hash table and the name hash tables. + */ +void free_devtable_info(void) +{ + struct hashtable_itr *ph_itr; + struct path_htbl_element *ph_elt; + + if (!path_htbl) + return; + + if (hashtable_count(path_htbl) > 0) { + ph_itr = hashtable_iterator(path_htbl); + do { + ph_elt = hashtable_iterator_value(ph_itr); + /* + * Note, since we use the same string for the key and + * @name in the name hash table elements, we do not + * have to iterate name hash table because @name memory + * will be freed when freeing the key. + */ + hashtable_destroy(ph_elt->name_htbl, 1); + } while (hashtable_iterator_advance(ph_itr)); + free(ph_itr); + } + hashtable_destroy(path_htbl, 1); +} diff --git a/ubifs-utils/common/devtable.h b/ubifs-utils/common/devtable.h new file mode 100644 index 0000000..97585f2 --- /dev/null +++ b/ubifs-utils/common/devtable.h @@ -0,0 +1,77 @@ +/* + * Copyright (C) 2008 Nokia Corporation. + * Copyright (C) 2008 University of Szeged, Hungary + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: Artem Bityutskiy + * Adrian Hunter + * Zoltan Sogor + */ + +#ifndef __DEVTABLE_H__ +#define __DEVTABLE_H__ + +/** + * struct path_htbl_element - an element of the path hash table. + * @path: the UBIFS path the element describes (the key of the element) + * @name_htbl: one more (nested) hash table containing names of all + * files/directories/device nodes which should be created at this + * path + * + * See device table handling for more information. + */ +struct path_htbl_element { + const char *path; + struct hashtable *name_htbl; +}; + +/** + * struct name_htbl_element - an element in the name hash table + * @name: name of the file/directory/device node (the key of the element) + * @mode: accsess rights and file type + * @uid: user ID + * @gid: group ID + * @major: device node major number + * @minor: device node minor number + * + * This is an element of the name hash table. Name hash table sits in the path + * hash table elements and describes file names which should be created/changed + * at this path. + */ +struct name_htbl_element { + const char *name; + unsigned int mode; + unsigned int uid; + unsigned int gid; + dev_t dev; +}; + +struct hashtable_itr; + +int parse_devtable(const char *tbl_file); +struct path_htbl_element *devtbl_find_path(const char *path); +struct name_htbl_element *devtbl_find_name(struct path_htbl_element *ph_elt, + const char *name); +int override_attributes(struct stat *st, struct path_htbl_element *ph_elt, + struct name_htbl_element *nh_elt); +struct name_htbl_element * +first_name_htbl_element(struct path_htbl_element *ph_elt, + struct hashtable_itr **itr); +struct name_htbl_element * +next_name_htbl_element(struct path_htbl_element *ph_elt, + struct hashtable_itr **itr); +void free_devtable_info(void); + +#endif diff --git a/ubifs-utils/common/fscrypt.c b/ubifs-utils/common/fscrypt.c new file mode 100644 index 0000000..f39faa7 --- /dev/null +++ b/ubifs-utils/common/fscrypt.c @@ -0,0 +1,285 @@ +/* + * Copyright (C) 2017 sigma star gmbh + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: Richard Weinberger <richard@sigma-star.at> + * David Oberhollenzer <david.oberhollenzer@sigma-star.at> + */ + +#include <endian.h> + +#include "linux_types.h" +#include "fscrypt.h" +#include "defs.h" +#include "ubifs.h" + +static __u8 fscrypt_masterkey[FS_MAX_KEY_SIZE]; +static struct cipher *fscrypt_cipher; + + +unsigned char *calc_fscrypt_subkey(struct fscrypt_context *fctx) +{ + int ret; + unsigned char *new_key = xmalloc(FS_MAX_KEY_SIZE); + + ret = derive_key_aes(fctx->nonce, fscrypt_masterkey, fscrypt_cipher->key_length, new_key); + if (ret < 0) { + errmsg("derive_key_aes failed: %i\n", ret); + + free(new_key); + new_key = NULL; + } + + return new_key; +} + +struct fscrypt_context *inherit_fscrypt_context(struct fscrypt_context *fctx) +{ + struct fscrypt_context *new_fctx = NULL; + + if (fctx) { + new_fctx = xmalloc(sizeof(*new_fctx)); + new_fctx->format = fctx->format; + new_fctx->contents_encryption_mode = fctx->contents_encryption_mode; + new_fctx->filenames_encryption_mode = fctx->filenames_encryption_mode; + new_fctx->flags = fctx->flags; + memcpy(new_fctx->master_key_descriptor, fctx->master_key_descriptor, + FS_KEY_DESCRIPTOR_SIZE); + RAND_bytes((void *)&new_fctx->nonce, FS_KEY_DERIVATION_NONCE_SIZE); + } + + return new_fctx; +} + +void free_fscrypt_context(struct fscrypt_context *fctx) +{ + free(fctx); +} + +static void print_fscrypt_master_key_descriptor(__u8 *master_key_descriptor) +{ + int i; + + normsg_cont("fscrypt master key descriptor: 0x"); + for (i = 0; i < FS_KEY_DESCRIPTOR_SIZE; i++) { + printf("%02x", master_key_descriptor[i]); + } + printf("\n"); +} + +unsigned int fscrypt_fname_encrypted_size(struct fscrypt_context *fctx, + unsigned int ilen) +{ + int padding; + + padding = 4 << (fctx->flags & FS_POLICY_FLAGS_PAD_MASK); + ilen = max_t(unsigned int, ilen, FS_CRYPTO_BLOCK_SIZE); + return round_up(ilen, padding); +} + +int encrypt_path(void **outbuf, const void *data, unsigned int data_len, + unsigned int max_namelen, struct fscrypt_context *fctx) +{ + void *inbuf, *crypt_key; + unsigned int padding = 4 << (fctx->flags & FS_POLICY_FLAGS_PAD_MASK); + unsigned int cryptlen; + int ret; + + cryptlen = max_t(unsigned int, data_len, FS_CRYPTO_BLOCK_SIZE); + cryptlen = round_up(cryptlen, padding); + cryptlen = min(cryptlen, max_namelen); + + inbuf = xmalloc(cryptlen); + /* CTS mode needs a block size aligned buffer */ + *outbuf = xmalloc(round_up(cryptlen, FS_CRYPTO_BLOCK_SIZE)); + + memset(inbuf, 0, cryptlen); + memcpy(inbuf, data, data_len); + + crypt_key = calc_fscrypt_subkey(fctx); + if (!crypt_key) { + free(inbuf); + free(*outbuf); + return errmsg("could not compute subkey"); + } + + ret = fscrypt_cipher->encrypt_fname(inbuf, cryptlen, + crypt_key, *outbuf); + if (ret < 0) { + free(inbuf); + free(*outbuf); + return errmsg("could not encrypt filename"); + } + + free(crypt_key); + free(inbuf); + return cryptlen; +} + +int encrypt_data_node(struct fscrypt_context *fctx, unsigned int block_no, + struct ubifs_data_node *dn, size_t length) +{ + void *inbuf, *outbuf, *crypt_key; + size_t ret, pad_len = round_up(length, FS_CRYPTO_BLOCK_SIZE); + + dn->compr_size = cpu_to_le16(length); + + inbuf = xzalloc(pad_len); + outbuf = xzalloc(pad_len); + + memcpy(inbuf, &dn->data, length); + + crypt_key = calc_fscrypt_subkey(fctx); + if (!crypt_key) { + free(inbuf); + free(outbuf); + return errmsg("could not compute subkey"); + } + + ret = fscrypt_cipher->encrypt_block(inbuf, pad_len, + crypt_key, block_no, + outbuf); + if (ret != pad_len) { + free(inbuf); + free(outbuf); + free(crypt_key); + return errmsg("encrypt_block returned %zi " + "instead of %zi", ret, pad_len); + } + + memcpy(&dn->data, outbuf, pad_len); + + free(inbuf); + free(outbuf); + free(crypt_key); + return pad_len; +} + +static int xdigit(int x) +{ + if (isupper(x)) + return x - 'A' + 0x0A; + if (islower(x)) + return x - 'a' + 0x0A; + return x - '0'; +} + +static int parse_key_descriptor(const char *desc, __u8 *dst) +{ + int i, hi, lo; + + if (desc[0] == '0' && (desc[1] == 'x' || desc[1] == 'X')) + desc += 2; + + for (i = 0; i < FS_KEY_DESCRIPTOR_SIZE; ++i) { + if (!desc[i * 2] || !desc[i * 2 + 1]) { + errmsg("key descriptor '%s' is too short", desc); + return -1; + } + if (!isxdigit(desc[i * 2]) || !isxdigit(desc[i * 2 + 1])) { + errmsg("invalid key descriptor '%s'", desc); + return -1; + } + + hi = xdigit(desc[i * 2]); + lo = xdigit(desc[i * 2 + 1]); + + dst[i] = (hi << 4) | lo; + } + + if (desc[i * 2]) { + errmsg("key descriptor '%s' is too long", desc); + return -1; + } + return 0; +} + +static int load_master_key(const char *key_file, struct cipher *fsc) +{ + int kf; + ssize_t keysize; + + kf = open(key_file, O_RDONLY); + if (kf < 0) { + sys_errmsg("open '%s'", key_file); + return -1; + } + + keysize = read(kf, fscrypt_masterkey, FS_MAX_KEY_SIZE); + if (keysize < 0) { + sys_errmsg("read '%s'", key_file); + goto fail; + } + if (keysize == 0) { + errmsg("loading key from '%s': file is empty", key_file); + goto fail; + } + if (keysize < fsc->key_length) { + errmsg("key '%s' is too short (at least %u bytes required)", + key_file, fsc->key_length); + goto fail; + } + + close(kf); + return 0; +fail: + close(kf); + return -1; +} + +struct fscrypt_context *init_fscrypt_context(const char *cipher_name, + unsigned int flags, + const char *key_file, + const char *key_descriptor) +{ + __u8 master_key_descriptor[FS_KEY_DESCRIPTOR_SIZE]; + __u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE]; + struct fscrypt_context *new_fctx; + + fscrypt_cipher = get_cipher(cipher_name); + + if (!fscrypt_cipher) { + fprintf(stderr, "Cannot find cipher '%s'\n" + "Try `%s --help' for more information\n", + cipher_name, PROGRAM_NAME); + return NULL; + } + + if (load_master_key(key_file, fscrypt_cipher)) + return NULL; + + if (!key_descriptor) { + if (derive_key_descriptor(fscrypt_masterkey, master_key_descriptor)) + return NULL; + print_fscrypt_master_key_descriptor(master_key_descriptor); + } else { + if (parse_key_descriptor(key_descriptor, master_key_descriptor)) + return NULL; + } + + RAND_bytes((void *)nonce, FS_KEY_DERIVATION_NONCE_SIZE); + + new_fctx = xmalloc(sizeof(*new_fctx)); + + new_fctx->format = FS_ENCRYPTION_CONTEXT_FORMAT_V1; + new_fctx->contents_encryption_mode = fscrypt_cipher->fscrypt_block_mode; + new_fctx->filenames_encryption_mode = fscrypt_cipher->fscrypt_fname_mode; + new_fctx->flags = flags; + + memcpy(&new_fctx->nonce, nonce, FS_KEY_DERIVATION_NONCE_SIZE); + memcpy(&new_fctx->master_key_descriptor, master_key_descriptor, + FS_KEY_DESCRIPTOR_SIZE); + return new_fctx; +} diff --git a/ubifs-utils/common/fscrypt.h b/ubifs-utils/common/fscrypt.h new file mode 100644 index 0000000..4a073e9 --- /dev/null +++ b/ubifs-utils/common/fscrypt.h @@ -0,0 +1,176 @@ +/* + * Copyright (C) 2017 sigma star gmbh + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: Richard Weinberger <richard@sigma-star.at> + * David Oberhollenzer <david.oberhollenzer@sigma-star.at> + */ + +#ifndef FSCRYPT_H +#define FSCRYPT_H + +#ifdef WITH_CRYPTO +#include <openssl/rand.h> +#endif +#include <assert.h> + +#include "compiler_attributes.h" +#include "ubifs.h" +#include "crypto.h" + +#ifndef FS_KEY_DESCRIPTOR_SIZE +#define FS_KEY_DESCRIPTOR_SIZE 8 +#endif +#define FS_ENCRYPTION_CONTEXT_FORMAT_V1 1 +#define FS_KEY_DERIVATION_NONCE_SIZE 16 + +#ifndef FS_ENCRYPTION_MODE_AES_256_XTS +#define FS_ENCRYPTION_MODE_AES_256_XTS 1 +#endif + +#ifndef FS_ENCRYPTION_MODE_AES_256_CTS +#define FS_ENCRYPTION_MODE_AES_256_CTS 4 +#endif + +#ifndef FS_ENCRYPTION_MODE_AES_128_CBC +#define FS_ENCRYPTION_MODE_AES_128_CBC 5 +#endif + +#ifndef FS_ENCRYPTION_MODE_AES_128_CTS +#define FS_ENCRYPTION_MODE_AES_128_CTS 6 +#endif + +#ifndef FS_POLICY_FLAGS_VALID +#define FS_POLICY_FLAGS_PAD_4 0x00 +#define FS_POLICY_FLAGS_PAD_8 0x01 +#define FS_POLICY_FLAGS_PAD_16 0x02 +#define FS_POLICY_FLAGS_PAD_32 0x03 +#define FS_POLICY_FLAGS_PAD_MASK 0x03 +#define FS_POLICY_FLAGS_VALID 0x03 +#endif + +#define FS_CRYPTO_BLOCK_SIZE 16 + +/** + * Encryption context for inode + * + * Protector format: + * 1 byte: Protector format (1 = this version) + * 1 byte: File contents encryption mode + * 1 byte: File names encryption mode + * 1 byte: Flags + * 8 bytes: Master Key descriptor + * 16 bytes: Encryption Key derivation nonce + */ +struct fscrypt_context { + __u8 format; + __u8 contents_encryption_mode; + __u8 filenames_encryption_mode; + __u8 flags; + __u8 master_key_descriptor[FS_KEY_DESCRIPTOR_SIZE]; + __u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE]; +} __packed; + +/** + * For encrypted symlinks, the ciphertext length is stored at the beginning + * of the string in little-endian format. + */ +struct fscrypt_symlink_data { + __le16 len; + char encrypted_path[1]; +} __packed; + + +#ifndef FS_MAX_KEY_SIZE +#define FS_MAX_KEY_SIZE 64 +#endif + +#ifndef FS_IV_SIZE +#define FS_IV_SIZE 16 +#endif + +#ifdef WITH_CRYPTO +unsigned char *calc_fscrypt_subkey(struct fscrypt_context *fctx); +struct fscrypt_context *inherit_fscrypt_context(struct fscrypt_context *fctx); +void free_fscrypt_context(struct fscrypt_context *fctx); +unsigned int fscrypt_fname_encrypted_size(struct fscrypt_context *fctx, + unsigned int ilen); +int encrypt_path(void **outbuf, const void *data, unsigned int data_len, + unsigned int max_namelen, struct fscrypt_context *fctx); +int encrypt_data_node(struct fscrypt_context *fctx, unsigned int block_no, + struct ubifs_data_node *dn, size_t length); +struct fscrypt_context *init_fscrypt_context(const char *cipher_name, + unsigned int flags, + const char *key_file, + const char *key_descriptor); +#else +static inline struct fscrypt_context *init_fscrypt_context( + const char *cipher_name, + unsigned int flags, + const char *key_file, + const char *key_descriptor) +{ + (void)cipher_name; + (void)flags; + (void)key_file; + (void)key_descriptor; + + assert(0); + return NULL; +} + +static inline void free_fscrypt_context(struct fscrypt_context *fctx) +{ + (void)fctx; + + assert(!fctx); +} + +static inline int encrypt_path(void **outbuf, const void *data, + unsigned int data_len, unsigned int max_namelen, + struct fscrypt_context *fctx) +{ + (void)outbuf; + (void)data; + (void)data_len; + (void)max_namelen; + (void)fctx; + + assert(0); + return -1; +} + +static inline int encrypt_data_node(struct fscrypt_context *fctx, unsigned int block_no, + struct ubifs_data_node *dn, size_t length) +{ + (void)fctx; + (void)block_no; + (void)dn; + (void)length; + + assert(0); + return -1; +} + +static inline struct fscrypt_context *inherit_fscrypt_context(struct fscrypt_context *fctx) +{ + (void)fctx; + + assert(!fctx); + return NULL; +} +#endif /* WITH_CRYPTO */ +#endif /* FSCRYPT_H */ + diff --git a/ubifs-utils/common/hashtable/hashtable.c b/ubifs-utils/common/hashtable/hashtable.c new file mode 100644 index 0000000..af7fed9 --- /dev/null +++ b/ubifs-utils/common/hashtable/hashtable.c @@ -0,0 +1,277 @@ +/* Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <math.h> + +#include "ubifs.h" +#include "defs.h" +#include "hashtable.h" +#include "hashtable_private.h" + +/* +Credit for primes table: Aaron Krowne + http://br.endernet.org/~akrowne/ + http://planetmath.org/encyclopedia/GoodHashTablePrimes.html +*/ +static const unsigned int primes[] = { +53, 97, 193, 389, +769, 1543, 3079, 6151, +12289, 24593, 49157, 98317, +196613, 393241, 786433, 1572869, +3145739, 6291469, 12582917, 25165843, +50331653, 100663319, 201326611, 402653189, +805306457, 1610612741 +}; +const unsigned int prime_table_length = ARRAY_SIZE(primes); +const float max_load_factor = 0.65; + +/*****************************************************************************/ +struct hashtable * +create_hashtable(unsigned int minsize, + unsigned int (*hashf) (void*), + int (*eqf) (void*,void*)) +{ + struct hashtable *h; + unsigned int pindex, size = primes[0]; + /* Check requested hashtable isn't too large */ + if (minsize > (1u << 30)) return NULL; + /* Enforce size as prime */ + for (pindex=0; pindex < prime_table_length; pindex++) { + if (primes[pindex] > minsize) { size = primes[pindex]; break; } + } + h = (struct hashtable *)malloc(sizeof(struct hashtable)); + if (NULL == h) return NULL; /*oom*/ + h->table = (struct entry **)malloc(sizeof(struct entry*) * size); + if (NULL == h->table) { free(h); return NULL; } /*oom*/ + memset(h->table, 0, size * sizeof(struct entry *)); + h->tablelength = size; + h->primeindex = pindex; + h->entrycount = 0; + h->hashfn = hashf; + h->eqfn = eqf; + h->loadlimit = (unsigned int) ceil(size * max_load_factor); + return h; +} + +/*****************************************************************************/ +unsigned int +hash(struct hashtable *h, void *k) +{ + /* Aim to protect against poor hash functions by adding logic here + * - logic taken from java 1.4 hashtable source */ + unsigned int i = h->hashfn(k); + i += ~(i << 9); + i ^= ((i >> 14) | (i << 18)); /* >>> */ + i += (i << 4); + i ^= ((i >> 10) | (i << 22)); /* >>> */ + return i; +} + +/*****************************************************************************/ +static int +hashtable_expand(struct hashtable *h) +{ + /* Double the size of the table to accomodate more entries */ + struct entry **newtable; + struct entry *e; + struct entry **pE; + unsigned int newsize, i, index; + /* Check we're not hitting max capacity */ + if (h->primeindex == (prime_table_length - 1)) return 0; + newsize = primes[++(h->primeindex)]; + + newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize); + if (NULL != newtable) + { + memset(newtable, 0, newsize * sizeof(struct entry *)); + /* This algorithm is not 'stable'. ie. it reverses the list + * when it transfers entries between the tables */ + for (i = 0; i < h->tablelength; i++) { + while (NULL != (e = h->table[i])) { + h->table[i] = e->next; + index = indexFor(newsize,e->h); + e->next = newtable[index]; + newtable[index] = e; + } + } + free(h->table); + h->table = newtable; + } + /* Plan B: realloc instead */ + else + { + newtable = (struct entry **) + realloc(h->table, newsize * sizeof(struct entry *)); + if (NULL == newtable) { (h->primeindex)--; return 0; } + h->table = newtable; + memset(newtable[h->tablelength], 0, newsize - h->tablelength); + for (i = 0; i < h->tablelength; i++) { + for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) { + index = indexFor(newsize,e->h); + if (index == i) + { + pE = &(e->next); + } + else + { + *pE = e->next; + e->next = newtable[index]; + newtable[index] = e; + } + } + } + } + h->tablelength = newsize; + h->loadlimit = (unsigned int) ceil(newsize * max_load_factor); + return -1; +} + +/*****************************************************************************/ +unsigned int +hashtable_count(struct hashtable *h) +{ + return h->entrycount; +} + +/*****************************************************************************/ +int +hashtable_insert(struct hashtable *h, void *k, void *v) +{ + /* This method allows duplicate keys - but they shouldn't be used */ + unsigned int index; + struct entry *e; + if (++(h->entrycount) > h->loadlimit) + { + /* Ignore the return value. If expand fails, we should + * still try cramming just this value into the existing table + * -- we may not have memory for a larger table, but one more + * element may be ok. Next time we insert, we'll try expanding again.*/ + hashtable_expand(h); + } + e = (struct entry *)malloc(sizeof(struct entry)); + if (NULL == e) { --(h->entrycount); return 0; } /*oom*/ + e->h = hash(h,k); + index = indexFor(h->tablelength,e->h); + e->k = k; + e->v = v; + e->next = h->table[index]; + h->table[index] = e; + return -1; +} + +/*****************************************************************************/ +void * /* returns value associated with key */ +hashtable_search(struct hashtable *h, void *k) +{ + struct entry *e; + unsigned int hashvalue, index; + hashvalue = hash(h,k); + index = indexFor(h->tablelength,hashvalue); + e = h->table[index]; + while (NULL != e) + { + /* Check hash value to short circuit heavier comparison */ + if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v; + e = e->next; + } + return NULL; +} + +/*****************************************************************************/ +void * /* returns value associated with key */ +hashtable_remove(struct hashtable *h, void *k) +{ + /* TODO: consider compacting the table when the load factor drops enough, + * or provide a 'compact' method. */ + + struct entry *e; + struct entry **pE; + void *v; + unsigned int hashvalue, index; + + hashvalue = hash(h,k); + index = indexFor(h->tablelength,hash(h,k)); + pE = &(h->table[index]); + e = *pE; + while (NULL != e) + { + /* Check hash value to short circuit heavier comparison */ + if ((hashvalue == e->h) && (h->eqfn(k, e->k))) + { + *pE = e->next; + h->entrycount--; + v = e->v; + freekey(e->k); + free(e); + return v; + } + pE = &(e->next); + e = e->next; + } + return NULL; +} + +/*****************************************************************************/ +/* destroy */ +void +hashtable_destroy(struct hashtable *h, int free_values) +{ + unsigned int i; + struct entry *e, *f; + struct entry **table = h->table; + if (free_values) + { + for (i = 0; i < h->tablelength; i++) + { + e = table[i]; + while (NULL != e) + { f = e; e = e->next; freekey(f->k); free(f->v); free(f); } + } + } + else + { + for (i = 0; i < h->tablelength; i++) + { + e = table[i]; + while (NULL != e) + { f = e; e = e->next; freekey(f->k); free(f); } + } + } + free(h->table); + free(h); +} + +/* + * Copyright (c) 2002, Christopher Clark + * All rights reserved. + * + * 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. + * + * * Neither the name of the original author; nor the names of any contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * + * 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. +*/ diff --git a/ubifs-utils/common/hashtable/hashtable.h b/ubifs-utils/common/hashtable/hashtable.h new file mode 100644 index 0000000..c0b0acd --- /dev/null +++ b/ubifs-utils/common/hashtable/hashtable.h @@ -0,0 +1,199 @@ +/* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */ + +#ifndef __HASHTABLE_CWC22_H__ +#define __HASHTABLE_CWC22_H__ + +struct hashtable; + +/* Example of use: + * + * struct hashtable *h; + * struct some_key *k; + * struct some_value *v; + * + * static unsigned int hash_from_key_fn( void *k ); + * static int keys_equal_fn ( void *key1, void *key2 ); + * + * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn); + * k = (struct some_key *) malloc(sizeof(struct some_key)); + * v = (struct some_value *) malloc(sizeof(struct some_value)); + * + * (initialise k and v to suitable values) + * + * if (! hashtable_insert(h,k,v) ) + * { exit(-1); } + * + * if (NULL == (found = hashtable_search(h,k) )) + * { printf("not found!"); } + * + * if (NULL == (found = hashtable_remove(h,k) )) + * { printf("Not found\n"); } + * + */ + +/* Macros may be used to define type-safe(r) hashtable access functions, with + * methods specialized to take known key and value types as parameters. + * + * Example: + * + * Insert this at the start of your file: + * + * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value); + * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value); + * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value); + * + * This defines the functions 'insert_some', 'search_some' and 'remove_some'. + * These operate just like hashtable_insert etc., with the same parameters, + * but their function signatures have 'struct some_key *' rather than + * 'void *', and hence can generate compile time errors if your program is + * supplying incorrect data as a key (and similarly for value). + * + * Note that the hash and key equality functions passed to create_hashtable + * still take 'void *' parameters instead of 'some key *'. This shouldn't be + * a difficult issue as they're only defined and passed once, and the other + * functions will ensure that only valid keys are supplied to them. + * + * The cost for this checking is increased code size and runtime overhead + * - if performance is important, it may be worth switching back to the + * unsafe methods once your program has been debugged with the safe methods. + * This just requires switching to some simple alternative defines - eg: + * #define insert_some hashtable_insert + * + */ + +/***************************************************************************** + * create_hashtable + + * @name create_hashtable + * @param minsize minimum initial size of hashtable + * @param hashfunction function for hashing keys + * @param key_eq_fn function for determining key equality + * @return newly created hashtable or NULL on failure + */ + +struct hashtable * +create_hashtable(unsigned int minsize, + unsigned int (*hashfunction) (void*), + int (*key_eq_fn) (void*,void*)); + +/***************************************************************************** + * hashtable_insert + + * @name hashtable_insert + * @param h the hashtable to insert into + * @param k the key - hashtable claims ownership and will free on removal + * @param v the value - does not claim ownership + * @return non-zero for successful insertion + * + * This function will cause the table to expand if the insertion would take + * the ratio of entries to table size over the maximum load factor. + * + * This function does not check for repeated insertions with a duplicate key. + * The value returned when using a duplicate key is undefined -- when + * the hashtable changes size, the order of retrieval of duplicate key + * entries is reversed. + * If in doubt, remove before insert. + */ + +int +hashtable_insert(struct hashtable *h, void *k, void *v); + +#define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \ +int fnname (struct hashtable *h, keytype *k, valuetype *v) \ +{ \ + return hashtable_insert(h,k,v); \ +} + +/***************************************************************************** + * hashtable_search + + * @name hashtable_search + * @param h the hashtable to search + * @param k the key to search for - does not claim ownership + * @return the value associated with the key, or NULL if none found + */ + +void * +hashtable_search(struct hashtable *h, void *k); + +#define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \ +valuetype * fnname (struct hashtable *h, keytype *k) \ +{ \ + return (valuetype *) (hashtable_search(h,k)); \ +} + +/***************************************************************************** + * hashtable_remove + + * @name hashtable_remove + * @param h the hashtable to remove the item from + * @param k the key to search for - does not claim ownership + * @return the value associated with the key, or NULL if none found + */ + +void * /* returns value */ +hashtable_remove(struct hashtable *h, void *k); + +#define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \ +valuetype * fnname (struct hashtable *h, keytype *k) \ +{ \ + return (valuetype *) (hashtable_remove(h,k)); \ +} + + +/***************************************************************************** + * hashtable_count + + * @name hashtable_count + * @param h the hashtable + * @return the number of items stored in the hashtable + */ +unsigned int +hashtable_count(struct hashtable *h); + + +/***************************************************************************** + * hashtable_destroy + + * @name hashtable_destroy + * @param h the hashtable + * @param free_values whether to call 'free' on the remaining values + */ + +void +hashtable_destroy(struct hashtable *h, int free_values); + +#endif /* __HASHTABLE_CWC22_H__ */ + +/* + * Copyright (c) 2002, Christopher Clark + * All rights reserved. + * + * 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. + * + * * Neither the name of the original author; nor the names of any contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * + * 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. +*/ diff --git a/ubifs-utils/common/hashtable/hashtable_itr.c b/ubifs-utils/common/hashtable/hashtable_itr.c new file mode 100644 index 0000000..d102453 --- /dev/null +++ b/ubifs-utils/common/hashtable/hashtable_itr.c @@ -0,0 +1,176 @@ +/* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */ + +#include "hashtable.h" +#include "hashtable_private.h" +#include "hashtable_itr.h" +#include <stdlib.h> /* defines NULL */ + +/*****************************************************************************/ +/* hashtable_iterator - iterator constructor */ + +struct hashtable_itr * +hashtable_iterator(struct hashtable *h) +{ + unsigned int i, tablelength; + struct hashtable_itr *itr = (struct hashtable_itr *) + malloc(sizeof(struct hashtable_itr)); + if (NULL == itr) return NULL; + itr->h = h; + itr->e = NULL; + itr->parent = NULL; + tablelength = h->tablelength; + itr->index = tablelength; + if (0 == h->entrycount) return itr; + + for (i = 0; i < tablelength; i++) + { + if (NULL != h->table[i]) + { + itr->e = h->table[i]; + itr->index = i; + break; + } + } + return itr; +} + +/*****************************************************************************/ +/* advance - advance the iterator to the next element + * returns zero if advanced to end of table */ + +int +hashtable_iterator_advance(struct hashtable_itr *itr) +{ + unsigned int j,tablelength; + struct entry **table; + struct entry *next; + if (NULL == itr->e) return 0; /* stupidity check */ + + next = itr->e->next; + if (NULL != next) + { + itr->parent = itr->e; + itr->e = next; + return -1; + } + tablelength = itr->h->tablelength; + itr->parent = NULL; + if (tablelength <= (j = ++(itr->index))) + { + itr->e = NULL; + return 0; + } + table = itr->h->table; + while (NULL == (next = table[j])) + { + if (++j >= tablelength) + { + itr->index = tablelength; + itr->e = NULL; + return 0; + } + } + itr->index = j; + itr->e = next; + return -1; +} + +/*****************************************************************************/ +/* remove - remove the entry at the current iterator position + * and advance the iterator, if there is a successive + * element. + * If you want the value, read it before you remove: + * beware memory leaks if you don't. + * Returns zero if end of iteration. */ + +int +hashtable_iterator_remove(struct hashtable_itr *itr) +{ + struct entry *remember_e, *remember_parent; + int ret; + + /* Do the removal */ + if (NULL == (itr->parent)) + { + /* element is head of a chain */ + itr->h->table[itr->index] = itr->e->next; + } else { + /* element is mid-chain */ + itr->parent->next = itr->e->next; + } + /* itr->e is now outside the hashtable */ + remember_e = itr->e; + itr->h->entrycount--; + freekey(remember_e->k); + + /* Advance the iterator, correcting the parent */ + remember_parent = itr->parent; + ret = hashtable_iterator_advance(itr); + if (itr->parent == remember_e) { itr->parent = remember_parent; } + free(remember_e); + return ret; +} + +/*****************************************************************************/ +int /* returns zero if not found */ +hashtable_iterator_search(struct hashtable_itr *itr, + struct hashtable *h, void *k) +{ + struct entry *e, *parent; + unsigned int hashvalue, index; + + hashvalue = hash(h,k); + index = indexFor(h->tablelength,hashvalue); + + e = h->table[index]; + parent = NULL; + while (NULL != e) + { + /* Check hash value to short circuit heavier comparison */ + if ((hashvalue == e->h) && (h->eqfn(k, e->k))) + { + itr->index = index; + itr->e = e; + itr->parent = parent; + itr->h = h; + return -1; + } + parent = e; + e = e->next; + } + return 0; +} + + +/* + * Copyright (c) 2002, 2004, Christopher Clark + * All rights reserved. + * + * 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. + * + * * Neither the name of the original author; nor the names of any contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * + * 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. +*/ diff --git a/ubifs-utils/common/hashtable/hashtable_itr.h b/ubifs-utils/common/hashtable/hashtable_itr.h new file mode 100644 index 0000000..5c94a04 --- /dev/null +++ b/ubifs-utils/common/hashtable/hashtable_itr.h @@ -0,0 +1,112 @@ +/* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */ + +#ifndef __HASHTABLE_ITR_CWC22__ +#define __HASHTABLE_ITR_CWC22__ +#include "hashtable.h" +#include "hashtable_private.h" /* needed to enable inlining */ + +/*****************************************************************************/ +/* This struct is only concrete here to allow the inlining of two of the + * accessor functions. */ +struct hashtable_itr +{ + struct hashtable *h; + struct entry *e; + struct entry *parent; + unsigned int index; +}; + + +/*****************************************************************************/ +/* hashtable_iterator + */ + +struct hashtable_itr * +hashtable_iterator(struct hashtable *h); + +/*****************************************************************************/ +/* hashtable_iterator_key + * - return the value of the (key,value) pair at the current position */ + +static inline void * +hashtable_iterator_key(struct hashtable_itr *i) +{ + return i->e->k; +} + +/*****************************************************************************/ +/* value - return the value of the (key,value) pair at the current position */ + +static inline void * +hashtable_iterator_value(struct hashtable_itr *i) +{ + return i->e->v; +} + +/*****************************************************************************/ +/* advance - advance the iterator to the next element + * returns zero if advanced to end of table */ + +int +hashtable_iterator_advance(struct hashtable_itr *itr); + +/*****************************************************************************/ +/* remove - remove current element and advance the iterator to the next element + * NB: if you need the value to free it, read it before + * removing. ie: beware memory leaks! + * returns zero if advanced to end of table */ + +int +hashtable_iterator_remove(struct hashtable_itr *itr); + +/*****************************************************************************/ +/* search - overwrite the supplied iterator, to point to the entry + * matching the supplied key. + h points to the hashtable to be searched. + * returns zero if not found. */ +int +hashtable_iterator_search(struct hashtable_itr *itr, + struct hashtable *h, void *k); + +#define DEFINE_HASHTABLE_ITERATOR_SEARCH(fnname, keytype) \ +int fnname (struct hashtable_itr *i, struct hashtable *h, keytype *k) \ +{ \ + return (hashtable_iterator_search(i,h,k)); \ +} + + + +#endif /* __HASHTABLE_ITR_CWC22__*/ + +/* + * Copyright (c) 2002, 2004, Christopher Clark + * All rights reserved. + * + * 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. + * + * * Neither the name of the original author; nor the names of any contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * + * 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. +*/ diff --git a/ubifs-utils/common/hashtable/hashtable_private.h b/ubifs-utils/common/hashtable/hashtable_private.h new file mode 100644 index 0000000..3a558e6 --- /dev/null +++ b/ubifs-utils/common/hashtable/hashtable_private.h @@ -0,0 +1,85 @@ +/* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */ + +#ifndef __HASHTABLE_PRIVATE_CWC22_H__ +#define __HASHTABLE_PRIVATE_CWC22_H__ + +#include "hashtable.h" + +/*****************************************************************************/ +struct entry +{ + void *k, *v; + unsigned int h; + struct entry *next; +}; + +struct hashtable { + unsigned int tablelength; + struct entry **table; + unsigned int entrycount; + unsigned int loadlimit; + unsigned int primeindex; + unsigned int (*hashfn) (void *k); + int (*eqfn) (void *k1, void *k2); +}; + +/*****************************************************************************/ +unsigned int +hash(struct hashtable *h, void *k); + +/*****************************************************************************/ +/* indexFor */ +static inline unsigned int +indexFor(unsigned int tablelength, unsigned int hashvalue) { + return (hashvalue % tablelength); +}; + +/* Only works if tablelength == 2^N */ +/*static inline unsigned int +indexFor(unsigned int tablelength, unsigned int hashvalue) +{ + return (hashvalue & (tablelength - 1u)); +} +*/ + +/*****************************************************************************/ +#define freekey(X) free(X) +/*define freekey(X) ; */ + + +/*****************************************************************************/ + +#endif /* __HASHTABLE_PRIVATE_CWC22_H__*/ + +/* + * Copyright (c) 2002, Christopher Clark + * All rights reserved. + * + * 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. + * + * * Neither the name of the original author; nor the names of any contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * + * 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. +*/ diff --git a/ubifs-utils/common/hexdump.c b/ubifs-utils/common/hexdump.c new file mode 100644 index 0000000..7ac4694 --- /dev/null +++ b/ubifs-utils/common/hexdump.c @@ -0,0 +1,218 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * lib/hexdump.c + */ + +#include <stdio.h> + +#include "linux_types.h" +#include "defs.h" + +#define __get_unaligned_t(type, ptr) ({ \ + const struct { type x; } __packed *__pptr = (typeof(__pptr))(ptr); \ + __pptr->x; \ +}) + +#define get_unaligned(ptr) __get_unaligned_t(typeof(*(ptr)), (ptr)) + +const char hex_asc[] = "0123456789abcdef"; + +#define hex_asc_lo(x) hex_asc[((x) & 0x0f)] +#define hex_asc_hi(x) hex_asc[((x) & 0xf0) >> 4] + +void print_hex_dump(const char *prefix_str, int prefix_type, + int rowsize, int groupsize, + const void *buf, size_t len, bool ascii); +/** + * hex_dump_to_buffer - convert a blob of data to "hex ASCII" in memory + * @buf: data blob to dump + * @len: number of bytes in the @buf + * @rowsize: number of bytes to print per line; must be 16 or 32 + * @groupsize: number of bytes to print at a time (1, 2, 4, 8; default = 1) + * @linebuf: where to put the converted data + * @linebuflen: total size of @linebuf, including space for terminating NUL + * @ascii: include ASCII after the hex output + * + * hex_dump_to_buffer() works on one "line" of output at a time, i.e., + * 16 or 32 bytes of input data converted to hex + ASCII output. + * + * Given a buffer of u8 data, hex_dump_to_buffer() converts the input data + * to a hex + ASCII dump at the supplied memory location. + * The converted output is always NUL-terminated. + * + * E.g.: + * hex_dump_to_buffer(frame->data, frame->len, 16, 1, + * linebuf, sizeof(linebuf), true); + * + * example output buffer: + * 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f @ABCDEFGHIJKLMNO + * + * Return: + * The amount of bytes placed in the buffer without terminating NUL. If the + * output was truncated, then the return value is the number of bytes + * (excluding the terminating NUL) which would have been written to the final + * string if enough space had been available. + */ +static int hex_dump_to_buffer(const void *buf, size_t len, int rowsize, + int groupsize, char *linebuf, size_t linebuflen, + bool ascii) +{ + const u8 *ptr = buf; + int ngroups; + u8 ch; + int j, lx = 0; + int ascii_column; + int ret; + + if (rowsize != 16 && rowsize != 32) + rowsize = 16; + + if (len > rowsize) /* limit to one line at a time */ + len = rowsize; + if (!is_power_of_2(groupsize) || groupsize > 8) + groupsize = 1; + if ((len % groupsize) != 0) /* no mixed size output */ + groupsize = 1; + + ngroups = len / groupsize; + ascii_column = rowsize * 2 + rowsize / groupsize + 1; + + if (!linebuflen) + goto overflow1; + + if (!len) + goto nil; + + if (groupsize == 8) { + const u64 *ptr8 = buf; + + for (j = 0; j < ngroups; j++) { + ret = snprintf(linebuf + lx, linebuflen - lx, + "%s%16.16llx", j ? " " : "", + get_unaligned(ptr8 + j)); + if (ret >= linebuflen - lx) + goto overflow1; + lx += ret; + } + } else if (groupsize == 4) { + const u32 *ptr4 = buf; + + for (j = 0; j < ngroups; j++) { + ret = snprintf(linebuf + lx, linebuflen - lx, + "%s%8.8x", j ? " " : "", + get_unaligned(ptr4 + j)); + if (ret >= linebuflen - lx) + goto overflow1; + lx += ret; + } + } else if (groupsize == 2) { + const u16 *ptr2 = buf; + + for (j = 0; j < ngroups; j++) { + ret = snprintf(linebuf + lx, linebuflen - lx, + "%s%4.4x", j ? " " : "", + get_unaligned(ptr2 + j)); + if (ret >= linebuflen - lx) + goto overflow1; + lx += ret; + } + } else { + for (j = 0; j < len; j++) { + if (linebuflen < lx + 2) + goto overflow2; + ch = ptr[j]; + linebuf[lx++] = hex_asc_hi(ch); + if (linebuflen < lx + 2) + goto overflow2; + linebuf[lx++] = hex_asc_lo(ch); + if (linebuflen < lx + 2) + goto overflow2; + linebuf[lx++] = ' '; + } + if (j) + lx--; + } + if (!ascii) + goto nil; + + while (lx < ascii_column) { + if (linebuflen < lx + 2) + goto overflow2; + linebuf[lx++] = ' '; + } + for (j = 0; j < len; j++) { + if (linebuflen < lx + 2) + goto overflow2; + ch = ptr[j]; + linebuf[lx++] = (isascii(ch) && isprint(ch)) ? ch : '.'; + } +nil: + linebuf[lx] = '\0'; + return lx; +overflow2: + linebuf[lx++] = '\0'; +overflow1: + return ascii ? ascii_column + len : (groupsize * 2 + 1) * ngroups - 1; +} + +/** + * print_hex_dump - print a text hex dump to syslog for a binary blob of data + * @prefix_str: string to prefix each line with; + * caller supplies trailing spaces for alignment if desired + * @prefix_type: controls whether prefix of an offset, address, or none + * is printed (%DUMP_PREFIX_OFFSET, %DUMP_PREFIX_ADDRESS, %DUMP_PREFIX_NONE) + * @rowsize: number of bytes to print per line; must be 16 or 32 + * @groupsize: number of bytes to print at a time (1, 2, 4, 8; default = 1) + * @buf: data blob to dump + * @len: number of bytes in the @buf + * @ascii: include ASCII after the hex output + * + * Given a buffer of u8 data, print_hex_dump() prints a hex + ASCII dump + * to the kernel log at the specified kernel log level, with an optional + * leading prefix. + * + * print_hex_dump() works on one "line" of output at a time, i.e., + * 16 or 32 bytes of input data converted to hex + ASCII output. + * print_hex_dump() iterates over the entire input @buf, breaking it into + * "line size" chunks to format and print. + * + * E.g.: + * print_hex_dump(KERN_DEBUG, "raw data: ", DUMP_PREFIX_ADDRESS, + * 16, 1, frame->data, frame->len, true); + * + * Example output using %DUMP_PREFIX_OFFSET and 1-byte mode: + * 0009ab42: 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f @ABCDEFGHIJKLMNO + * Example output using %DUMP_PREFIX_ADDRESS and 4-byte mode: + * ffffffff88089af0: 73727170 77767574 7b7a7978 7f7e7d7c pqrstuvwxyz{|}~. + */ +void print_hex_dump(const char *prefix_str, int prefix_type, + int rowsize, int groupsize, + const void *buf, size_t len, bool ascii) +{ + const u8 *ptr = buf; + int i, linelen, remaining = len; + char linebuf[32 * 3 + 2 + 32 + 1]; + + if (rowsize != 16 && rowsize != 32) + rowsize = 16; + + for (i = 0; i < len; i += rowsize) { + linelen = min(remaining, rowsize); + remaining -= rowsize; + + hex_dump_to_buffer(ptr + i, linelen, rowsize, groupsize, + linebuf, sizeof(linebuf), ascii); + + switch (prefix_type) { + case DUMP_PREFIX_ADDRESS: + printf("%s%p: %s\n", prefix_str, ptr + i, linebuf); + break; + case DUMP_PREFIX_OFFSET: + printf("%s%.8x: %s\n", prefix_str, i, linebuf); + break; + default: + printf("%s%s\n", prefix_str, linebuf); + break; + } + } +} diff --git a/ubifs-utils/common/kmem.c b/ubifs-utils/common/kmem.c new file mode 100644 index 0000000..e926a13 --- /dev/null +++ b/ubifs-utils/common/kmem.c @@ -0,0 +1,64 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Simple memory interface + */ + +#include "compiler_attributes.h" +#include "linux_types.h" +#include "kmem.h" +#include "defs.h" + +static void *kmem_alloc(size_t size) +{ + void *ptr = malloc(size); + + if (ptr == NULL) + sys_errmsg("malloc failed (%d bytes)", (int)size); + return ptr; +} + +static void *kmem_zalloc(size_t size) +{ + void *ptr = kmem_alloc(size); + + if (!ptr) + return ptr; + + memset(ptr, 0, size); + return ptr; +} + +void *kmalloc(size_t size, gfp_t flags) +{ + if (flags & __GFP_ZERO) + return kmem_zalloc(size); + return kmem_alloc(size); +} + +void *krealloc(void *ptr, size_t new_size, __unused gfp_t flags) +{ + ptr = realloc(ptr, new_size); + if (ptr == NULL) + sys_errmsg("realloc failed (%d bytes)", (int)new_size); + return ptr; +} + +void *kmalloc_array(size_t n, size_t size, gfp_t flags) +{ + size_t bytes; + + if (unlikely(check_mul_overflow(n, size, &bytes))) + return NULL; + return kmalloc(bytes, flags); +} + +void *kmemdup(const void *src, size_t len, gfp_t gfp) +{ + void *p; + + p = kmalloc(len, gfp); + if (p) + memcpy(p, src, len); + + return p; +} diff --git a/ubifs-utils/common/kmem.h b/ubifs-utils/common/kmem.h new file mode 100644 index 0000000..9fe2a36 --- /dev/null +++ b/ubifs-utils/common/kmem.h @@ -0,0 +1,56 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (c) 2008 Silicon Graphics, Inc. + * All Rights Reserved. + */ +#ifndef __KMEM_H__ +#define __KMEM_H__ + +#include <stdlib.h> + +typedef unsigned int gfp_t; + +#define GFP_KERNEL 0 +#define GFP_NOFS 0 +#define __GFP_NOWARN 0 +#define __GFP_ZERO 1 + +#define vmalloc(size) malloc(size) +#define vfree(ptr) free(ptr) + +extern void *kmalloc(size_t, gfp_t); +extern void *krealloc(void *, size_t, __attribute__((unused)) gfp_t); +extern void *kmalloc_array(size_t, size_t, gfp_t); +extern void *kmemdup(const void *src, size_t len, gfp_t gfp); + +static inline void kfree(const void *ptr) +{ + free((void *)ptr); +} + +static inline void kvfree(const void *ptr) +{ + kfree(ptr); +} + +static inline void *kvmalloc(size_t size, gfp_t flags) +{ + return kmalloc(size, flags); +} + +static inline void *kzalloc(size_t size, gfp_t flags) +{ + return kmalloc(size, flags | __GFP_ZERO); +} + +static inline void *__vmalloc(unsigned long size, gfp_t gfp_mask) +{ + return kmalloc(size, gfp_mask); +} + +static inline void *kcalloc(size_t n, size_t size, gfp_t flags) +{ + return kmalloc_array(n, size, flags | __GFP_ZERO); +} + +#endif diff --git a/ubifs-utils/common/linux_err.h b/ubifs-utils/common/linux_err.h new file mode 100644 index 0000000..5c6ddc3 --- /dev/null +++ b/ubifs-utils/common/linux_err.h @@ -0,0 +1,62 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_ERR_H +#define _LINUX_ERR_H + +/* Adapted from include/linux/err.h */ + +#include <stdbool.h> + +/* + * Kernel pointers have redundant information, so we can use a + * scheme where we can return either an error code or a normal + * pointer with the same return value. + * + * This should be a per-architecture thing, to allow different + * error and pointer decisions. + */ +#define MAX_ERRNO 4095 + +#define IS_ERR_VALUE(x) ((unsigned long)(void *)(x) >= (unsigned long)-MAX_ERRNO) + +static inline void * ERR_PTR(long error) +{ + return (void *) error; +} + +static inline long PTR_ERR(const void *ptr) +{ + return (long) ptr; +} + +static inline bool IS_ERR(const void *ptr) +{ + return IS_ERR_VALUE((unsigned long)ptr); +} + +static inline bool IS_ERR_OR_NULL(const void *ptr) +{ + return !ptr || IS_ERR_VALUE((unsigned long)ptr); +} + +/** + * ERR_CAST - Explicitly cast an error-valued pointer to another pointer type + * @ptr: The pointer to cast. + * + * Explicitly cast an error-valued pointer to another pointer type in such a + * way as to make it clear that's what's going on. + */ +static inline void * ERR_CAST(const void *ptr) +{ + /* cast away the const */ + return (void *) ptr; +} + +static inline int PTR_ERR_OR_ZERO(const void *ptr) +{ + if (IS_ERR(ptr)) + return PTR_ERR(ptr); + else + return 0; +} + +#endif /* _LINUX_ERR_H */ diff --git a/ubifs-utils/common/linux_types.h b/ubifs-utils/common/linux_types.h new file mode 100644 index 0000000..ebf9ecd --- /dev/null +++ b/ubifs-utils/common/linux_types.h @@ -0,0 +1,92 @@ +#ifndef __LINUX_TYPES_H__ +#define __LINUX_TYPES_H__ + +#include <linux/types.h> +#include <sys/types.h> +#include <byteswap.h> +#include <stdint.h> +#include <unistd.h> + +#include "compiler_attributes.h" + +typedef __u8 u8; +typedef __u16 u16; +typedef __u32 u32; +typedef __u64 u64; + +typedef __s64 time64_t; + +struct qstr { + const char *name; + size_t len; +}; + +struct fscrypt_name { + struct qstr disk_name; +}; + +#define fname_name(p) ((p)->disk_name.name) +#define fname_len(p) ((p)->disk_name.len) + +#define S_IRUGO (S_IRUSR|S_IRGRP|S_IROTH) +#define S_IXUGO (S_IXUSR|S_IXGRP|S_IXOTH) + +#define t16(x) ({ \ + uint16_t __b = (x); \ + (__LITTLE_ENDIAN==__BYTE_ORDER) ? __b : bswap_16(__b); \ +}) + +#define t32(x) ({ \ + uint32_t __b = (x); \ + (__LITTLE_ENDIAN==__BYTE_ORDER) ? __b : bswap_32(__b); \ +}) + +#define t64(x) ({ \ + uint64_t __b = (x); \ + (__LITTLE_ENDIAN==__BYTE_ORDER) ? __b : bswap_64(__b); \ +}) + +#define cpu_to_le16(x) ((__le16){t16(x)}) +#define cpu_to_le32(x) ((__le32){t32(x)}) +#define cpu_to_le64(x) ((__le64){t64(x)}) + +#define le16_to_cpu(x) (t16((x))) +#define le32_to_cpu(x) (t32((x))) +#define le64_to_cpu(x) (t64((x))) + +#define check_mul_overflow(a, b, d) ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + typeof(d) __d = (d); \ + (void) (&__a == &__b); \ + (void) (&__a == __d); \ + __builtin_mul_overflow(__a, __b, __d); \ +}) + +static inline __must_check size_t array_size(size_t a, size_t b) +{ + size_t bytes; + if (check_mul_overflow(a, b, &bytes)) + return SIZE_MAX; + + return bytes; +} + +static inline int int_log2(unsigned int arg) +{ + int l = 0; + + arg >>= 1; + while (arg) { + l++; + arg >>= 1; + } + return l; +} + +#undef PAGE_SIZE +#define PAGE_SIZE (getpagesize()) +#undef PAGE_SHIFT +#define PAGE_SHIFT (int_log2(PAGE_SIZE)) + +#endif diff --git a/ubifs-utils/common/mutex.h b/ubifs-utils/common/mutex.h new file mode 100644 index 0000000..4bf018b --- /dev/null +++ b/ubifs-utils/common/mutex.h @@ -0,0 +1,18 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __LINUX_MUTEX_H_ +#define __LINUX_MUTEX_H_ + +#include <pthread.h> + +struct mutex { + pthread_mutex_t lock; +}; + +#define mutex_init(x) pthread_mutex_init(&(x)->lock, NULL) + +#define mutex_lock(x) pthread_mutex_lock(&(x)->lock) +#define mutex_lock_nested(x, c) pthread_mutex_lock(&(x)->lock) +#define mutex_unlock(x) pthread_mutex_unlock(&(x)->lock) +#define mutex_is_locked(x) (pthread_mutex_trylock(&(x)->lock) == EBUSY) + +#endif diff --git a/ubifs-utils/common/rwsem.h b/ubifs-utils/common/rwsem.h new file mode 100644 index 0000000..3761724 --- /dev/null +++ b/ubifs-utils/common/rwsem.h @@ -0,0 +1,19 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __LINUX_RWSEM_H_ +#define __LINUX_RWSEM_H_ + +#include <pthread.h> + +struct rw_semaphore { + pthread_mutex_t lock; +}; + +#define init_rwsem(x) pthread_mutex_init(&(x)->lock, NULL) + +#define down_read(x) pthread_mutex_lock(&(x)->lock) +#define down_write(x) pthread_mutex_lock(&(x)->lock) +#define up_read(x) pthread_mutex_unlock(&(x)->lock) +#define up_write(x) pthread_mutex_unlock(&(x)->lock) +#define down_write_trylock(x) (pthread_mutex_trylock(&(x)->lock) == 0) + +#endif diff --git a/ubifs-utils/common/sign.c b/ubifs-utils/common/sign.c new file mode 100644 index 0000000..032a6ac --- /dev/null +++ b/ubifs-utils/common/sign.c @@ -0,0 +1,395 @@ +/* + * Copyright (C) 2018 Pengutronix + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Author: Sascha Hauer + */ + +#include <string.h> +#include <openssl/evp.h> +#include <openssl/opensslv.h> +#include <openssl/bio.h> +#include <openssl/pem.h> +#include <openssl/err.h> +#include <openssl/engine.h> +#include <openssl/cms.h> +#include <openssl/conf.h> +#include <err.h> + +#include "linux_types.h" +#include "sign.h" +#include "ubifs.h" +#include "defs.h" + +extern struct ubifs_info info_; +static struct ubifs_info *c = &info_; + +EVP_MD_CTX *hash_md; +const EVP_MD *md; + +static int match_string(const char * const *array, size_t n, const char *string) +{ + int index; + const char *item; + + for (index = 0; index < n; index++) { + item = array[index]; + if (!item) + break; + if (!strcmp(item, string)) + return index; + } + + return -EINVAL; +} + +#include <linux/hash_info.h> + +const char *const hash_algo_name[HASH_ALGO__LAST] = { + [HASH_ALGO_MD4] = "md4", + [HASH_ALGO_MD5] = "md5", + [HASH_ALGO_SHA1] = "sha1", + [HASH_ALGO_RIPE_MD_160] = "rmd160", + [HASH_ALGO_SHA256] = "sha256", + [HASH_ALGO_SHA384] = "sha384", + [HASH_ALGO_SHA512] = "sha512", + [HASH_ALGO_SHA224] = "sha224", + [HASH_ALGO_RIPE_MD_128] = "rmd128", + [HASH_ALGO_RIPE_MD_256] = "rmd256", + [HASH_ALGO_RIPE_MD_320] = "rmd320", + [HASH_ALGO_WP_256] = "wp256", + [HASH_ALGO_WP_384] = "wp384", + [HASH_ALGO_WP_512] = "wp512", + [HASH_ALGO_TGR_128] = "tgr128", + [HASH_ALGO_TGR_160] = "tgr160", + [HASH_ALGO_TGR_192] = "tgr192", + [HASH_ALGO_SM3_256] = "sm3-256", +}; + +static void display_openssl_errors(int l) +{ + const char *file; + char buf[120]; + int e, line; + + if (ERR_peek_error() == 0) + return; + fprintf(stderr, "At main.c:%d:\n", l); + + while ((e = ERR_get_error_line(&file, &line))) { + ERR_error_string(e, buf); + fprintf(stderr, "- SSL %s: %s:%d\n", buf, file, line); + } +} + +static void drain_openssl_errors(void) +{ + const char *file; + int line; + + if (ERR_peek_error() == 0) + return; + while (ERR_get_error_line(&file, &line)) {} +} + +#define ssl_err_msg(fmt, ...) ({ \ + display_openssl_errors(__LINE__); \ + errmsg(fmt, ## __VA_ARGS__); \ + -1; \ +}) + +static const char *key_pass; + +static int pem_pw_cb(char *buf, int len, __unused int w, __unused void *v) +{ + int pwlen; + + if (!key_pass) + return -1; + + pwlen = strlen(key_pass); + if (pwlen >= len) + return -1; + + strcpy(buf, key_pass); + + /* If it's wrong, don't keep trying it. */ + key_pass = NULL; + + return pwlen; +} + +static EVP_PKEY *read_private_key(const char *private_key_name, X509 **cert) +{ + EVP_PKEY *private_key = NULL; + int err; + + *cert = NULL; + + if (!strncmp(private_key_name, "pkcs11:", 7)) { + ENGINE *e; + struct { + const char *url; + X509 *cert; + } parms = { + .url = private_key_name, + }; + + ENGINE_load_builtin_engines(); + drain_openssl_errors(); + e = ENGINE_by_id("pkcs11"); + if (!e) { + ssl_err_msg("Load PKCS#11 ENGINE"); + return NULL; + } + + if (ENGINE_init(e)) { + drain_openssl_errors(); + } else { + ssl_err_msg("ENGINE_init"); + return NULL; + } + + if (key_pass) + if (!ENGINE_ctrl_cmd_string(e, "PIN", key_pass, 0)) { + ssl_err_msg("Set PKCS#11 PIN"); + return NULL; + } + + private_key = ENGINE_load_private_key(e, private_key_name, + NULL, NULL); + + err = ENGINE_ctrl_cmd(e, "LOAD_CERT_CTRL", 0, &parms, NULL, 0); + if (!err || !parms.cert) { + ssl_err_msg("Load certificate"); + } + *cert = parms.cert; + fprintf(stderr, "Using cert %p\n", *cert); + } else { + BIO *b; + + b = BIO_new_file(private_key_name, "rb"); + if (!b) + goto out; + + private_key = PEM_read_bio_PrivateKey(b, NULL, pem_pw_cb, + NULL); + BIO_free(b); + } +out: + if (!private_key) + ssl_err_msg("failed opening private key %s", private_key_name); + + return private_key; +} + +static X509 *read_x509(const char *x509_name) +{ + unsigned char buf[2]; + X509 *x509 = NULL; + BIO *b; + int n; + + b = BIO_new_file(x509_name, "rb"); + if (!b) + goto out; + + /* Look at the first two bytes of the file to determine the encoding */ + n = BIO_read(b, buf, 2); + if (n != 2) { + if (BIO_should_retry(b)) + errmsg("%s: Read wanted retry", x509_name); + if (n >= 0) + errmsg("%s: Short read", x509_name); + goto out; + } + + if (BIO_reset(b)) + goto out; + + if (buf[0] == 0x30 && buf[1] >= 0x81 && buf[1] <= 0x84) + /* Assume raw DER encoded X.509 */ + x509 = d2i_X509_bio(b, NULL); + else + /* Assume PEM encoded X.509 */ + x509 = PEM_read_bio_X509(b, NULL, NULL, NULL); + + BIO_free(b); + +out: + if (!x509) { + ssl_err_msg("%s", x509_name); + return NULL; + } + + return x509; +} + +int hash_sign_node(const char *auth_key_filename, const char *auth_cert_filename, + void *buf, int *len, void *outbuf) +{ + EVP_PKEY *private_key; + CMS_ContentInfo *cms = NULL; + X509 *cert = NULL; + BIO *bd, *bm; + void *obuf; + int ret; + void *pret; + + ERR_load_crypto_strings(); + ERR_clear_error(); + + key_pass = getenv("MKFS_UBIFS_SIGN_PIN"); + + bm = BIO_new_mem_buf(buf, UBIFS_SB_NODE_SZ); + + private_key = read_private_key(auth_key_filename, &cert); + if (!private_key) + return -1; + + if (!cert) { + if (!auth_cert_filename) + return errmsg("authentication certificate not provided (--auth-cert)"); + cert = read_x509(auth_cert_filename); + } + + if (!cert) + return -1; + + OpenSSL_add_all_digests(); + display_openssl_errors(__LINE__); + + cms = CMS_sign(NULL, NULL, NULL, NULL, + CMS_NOCERTS | CMS_PARTIAL | CMS_BINARY | + CMS_DETACHED | CMS_STREAM); + if (!cms) + return errmsg("CMS_sign failed"); + + pret = CMS_add1_signer(cms, cert, private_key, md, + CMS_NOCERTS | CMS_BINARY | + CMS_NOSMIMECAP | CMS_NOATTR); + if (!pret) + return errmsg("CMS_add1_signer failed"); + + ret = CMS_final(cms, bm, NULL, CMS_NOCERTS | CMS_BINARY); + if (!ret) + return errmsg("CMS_final failed"); + + bd = BIO_new(BIO_s_mem()); + + ret = i2d_CMS_bio_stream(bd, cms, NULL, 0); + if (!ret) + return errmsg("i2d_CMS_bio_stream failed"); + + *len = BIO_get_mem_data(bd, &obuf); + + memcpy(outbuf, obuf, *len); + + BIO_free(bd); + BIO_free(bm); + + return 0; +} + +int hash_digest(const void *buf, unsigned int len, uint8_t *hash) +{ + int err; + unsigned int md_len; + + err = EVP_DigestInit_ex(hash_md, md, NULL); + if (!err) + return errmsg("Init hash digest failed"); + err = EVP_DigestUpdate(hash_md, buf, len); + if (!err) + return errmsg("Update hash digest failed"); + err = EVP_DigestFinal_ex(hash_md, hash, &md_len); + if (!err) + return errmsg("Finalize hash digest failed"); + + return 0; +} + +int hash_digest_init(void) +{ + int err; + + err = EVP_DigestInit_ex(hash_md, md, NULL); + if (!err) + return errmsg("Init hash digest failed"); + + return 0; +} + +int hash_digest_update(const void *buf, int len) +{ + int err; + + err = EVP_DigestUpdate(hash_md, buf, len); + if (!err) + return errmsg("Update hash digest failed"); + + return 0; +} + +int hash_digest_final(void *hash) +{ + int err; + unsigned int md_len; + + err = EVP_DigestFinal_ex(hash_md, hash, &md_len); + if (!err) + return errmsg("Finalize hash digest failed"); + + return 0; +} + +int init_authentication(const char *algo_name, int *hash_len, int *hash_algo) +{ + OPENSSL_config(NULL); + OpenSSL_add_all_algorithms(); + ERR_load_crypto_strings(); + + md = EVP_get_digestbyname(c->hash_algo_name); + if (!md) + return errmsg("Unknown message digest %s", c->hash_algo_name); + + hash_md = EVP_MD_CTX_create(); + if (!hash_md) + return errmsg("Cannot create md ctx"); + + *hash_len = EVP_MD_size(md); + if (*hash_len < 0) { + EVP_MD_CTX_destroy(hash_md); + hash_md = NULL; + return errmsg("Cannot init hash len"); + } + + *hash_algo = match_string(hash_algo_name, HASH_ALGO__LAST, algo_name); + if (*hash_algo < 0) { + EVP_MD_CTX_destroy(hash_md); + hash_md = NULL; + return errmsg("Unsupported message digest %s", algo_name); + } + + return 0; +} + +void exit_authentication(void) +{ + if (hash_md) { + EVP_MD_CTX_destroy(hash_md); + hash_md = NULL; + } +} diff --git a/ubifs-utils/common/sign.h b/ubifs-utils/common/sign.h new file mode 100644 index 0000000..f49c76a --- /dev/null +++ b/ubifs-utils/common/sign.h @@ -0,0 +1,39 @@ +/* + * Copyright (C) 2018 Pengutronix + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Author: Sascha Hauer + */ + +#ifndef __UBIFS_SIGN_H__ +#define __UBIFS_SIGN_H__ + +#include <openssl/evp.h> + +struct shash_desc { + void *ctx; +}; + +int hash_digest(const void *buf, unsigned int len, uint8_t *hash); +int hash_digest_init(void); +int hash_digest_update(const void *buf, int len); +int hash_digest_final(void *hash); +int init_authentication(const char *algo_name, int *hash_len, int *hash_algo); +void exit_authentication(void); +void mst_node_calc_hash(const void *node, uint8_t *hash); +int hash_sign_node(const char *auth_key_filename, const char *auth_cert_filename, + void *buf, int *len, void *outbuf); + +#endif /* __UBIFS_SIGN_H__ */ diff --git a/ubifs-utils/common/sort.c b/ubifs-utils/common/sort.c new file mode 100644 index 0000000..d585836 --- /dev/null +++ b/ubifs-utils/common/sort.c @@ -0,0 +1,274 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * A fast, small, non-recursive O(n log n) sort for the Linux kernel + * + * This performs n*log2(n) + 0.37*n + o(n) comparisons on average, + * and 1.5*n*log2(n) + O(n) in the (very contrived) worst case. + * + * Glibc qsort() manages n*log2(n) - 1.26*n for random inputs (1.63*n + * better) at the expense of stack usage and much larger code to avoid + * quicksort's O(n^2) worst case. + */ + +#include <stdio.h> +#include <stdbool.h> +#include <linux/types.h> + +#include "sort.h" +#include "linux_types.h" + +/** + * is_aligned - is this pointer & size okay for word-wide copying? + * @base: pointer to data + * @size: size of each element + * @align: required alignment (typically 4 or 8) + * + * Returns true if elements can be copied using word loads and stores. + * The size must be a multiple of the alignment. + * + * For some reason, gcc doesn't know to optimize "if (a & mask || b & mask)" + * to "if ((a | b) & mask)", so we do that by hand. + */ +__const __always_inline +static bool is_aligned(const void *base, size_t size, unsigned char align) +{ + unsigned char lsbits = (unsigned char)size; + + (void)base; + return (lsbits & (align - 1)) == 0; +} + +/** + * swap_words_32 - swap two elements in 32-bit chunks + * @a: pointer to the first element to swap + * @b: pointer to the second element to swap + * @n: element size (must be a multiple of 4) + * + * Exchange the two objects in memory. This exploits base+index addressing, + * which basically all CPUs have, to minimize loop overhead computations. + * + * For some reason, on x86 gcc 7.3.0 adds a redundant test of n at the + * bottom of the loop, even though the zero flag is still valid from the + * subtract (since the intervening mov instructions don't alter the flags). + * Gcc 8.1.0 doesn't have that problem. + */ +static void swap_words_32(void *a, void *b, size_t n) +{ + do { + u32 t = *(u32 *)(a + (n -= 4)); + *(u32 *)(a + n) = *(u32 *)(b + n); + *(u32 *)(b + n) = t; + } while (n); +} + +/** + * swap_words_64 - swap two elements in 64-bit chunks + * @a: pointer to the first element to swap + * @b: pointer to the second element to swap + * @n: element size (must be a multiple of 8) + * + * Exchange the two objects in memory. This exploits base+index + * addressing, which basically all CPUs have, to minimize loop overhead + * computations. + * + * We'd like to use 64-bit loads if possible. If they're not, emulating + * one requires base+index+4 addressing which x86 has but most other + * processors do not. + */ +static void swap_words_64(void *a, void *b, size_t n) +{ + do { + u64 t = *(u64 *)(a + (n -= 8)); + *(u64 *)(a + n) = *(u64 *)(b + n); + *(u64 *)(b + n) = t; + } while (n); +} + +/** + * swap_bytes - swap two elements a byte at a time + * @a: pointer to the first element to swap + * @b: pointer to the second element to swap + * @n: element size + * + * This is the fallback if alignment doesn't allow using larger chunks. + */ +static void swap_bytes(void *a, void *b, size_t n) +{ + do { + char t = ((char *)a)[--n]; + ((char *)a)[n] = ((char *)b)[n]; + ((char *)b)[n] = t; + } while (n); +} + +/* + * The values are arbitrary as long as they can't be confused with + * a pointer, but small integers make for the smallest compare + * instructions. + */ +#define SWAP_WORDS_64 (swap_r_func_t)0 +#define SWAP_WORDS_32 (swap_r_func_t)1 +#define SWAP_BYTES (swap_r_func_t)2 +#define SWAP_WRAPPER (swap_r_func_t)3 + +struct wrapper { + cmp_func_t cmp; + swap_func_t swap; +}; + +/* + * The function pointer is last to make tail calls most efficient if the + * compiler decides not to inline this function. + */ +static void do_swap(void *a, void *b, size_t size, swap_r_func_t swap_func, const void *priv) +{ + if (swap_func == SWAP_WRAPPER) { + ((const struct wrapper *)priv)->swap(a, b, (int)size); + return; + } + + if (swap_func == SWAP_WORDS_64) + swap_words_64(a, b, size); + else if (swap_func == SWAP_WORDS_32) + swap_words_32(a, b, size); + else if (swap_func == SWAP_BYTES) + swap_bytes(a, b, size); + else + swap_func(a, b, (int)size, priv); +} + +#define _CMP_WRAPPER ((cmp_r_func_t)0L) + +static int do_cmp(const void *a, const void *b, cmp_r_func_t cmp, const void *priv) +{ + if (cmp == _CMP_WRAPPER) + return ((const struct wrapper *)priv)->cmp(a, b); + return cmp(a, b, priv); +} + +/** + * parent - given the offset of the child, find the offset of the parent. + * @i: the offset of the heap element whose parent is sought. Non-zero. + * @lsbit: a precomputed 1-bit mask, equal to "size & -size" + * @size: size of each element + * + * In terms of array indexes, the parent of element j = @i/@size is simply + * (j-1)/2. But when working in byte offsets, we can't use implicit + * truncation of integer divides. + * + * Fortunately, we only need one bit of the quotient, not the full divide. + * @size has a least significant bit. That bit will be clear if @i is + * an even multiple of @size, and set if it's an odd multiple. + * + * Logically, we're doing "if (i & lsbit) i -= size;", but since the + * branch is unpredictable, it's done with a bit of clever branch-free + * code instead. + */ +__const __always_inline +static size_t parent(size_t i, unsigned int lsbit, size_t size) +{ + i -= size; + i -= size & -(i & lsbit); + return i / 2; +} + +/** + * sort_r - sort an array of elements + * @base: pointer to data to sort + * @num: number of elements + * @size: size of each element + * @cmp_func: pointer to comparison function + * @swap_func: pointer to swap function or NULL + * @priv: third argument passed to comparison function + * + * This function does a heapsort on the given array. You may provide + * a swap_func function if you need to do something more than a memory + * copy (e.g. fix up pointers or auxiliary data), but the built-in swap + * avoids a slow retpoline and so is significantly faster. + * + * Sorting time is O(n log n) both on average and worst-case. While + * quicksort is slightly faster on average, it suffers from exploitable + * O(n*n) worst-case behavior and extra memory requirements that make + * it less suitable for kernel use. + */ +void sort_r(void *base, size_t num, size_t size, + cmp_r_func_t cmp_func, + swap_r_func_t swap_func, + const void *priv) +{ + /* pre-scale counters for performance */ + size_t n = num * size, a = (num/2) * size; + const unsigned int lsbit = size & -size; /* Used to find parent */ + + if (!a) /* num < 2 || size == 0 */ + return; + + /* called from 'sort' without swap function, let's pick the default */ + if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap) + swap_func = NULL; + + if (!swap_func) { + if (is_aligned(base, size, 8)) + swap_func = SWAP_WORDS_64; + else if (is_aligned(base, size, 4)) + swap_func = SWAP_WORDS_32; + else + swap_func = SWAP_BYTES; + } + + /* + * Loop invariants: + * 1. elements [a,n) satisfy the heap property (compare greater than + * all of their children), + * 2. elements [n,num*size) are sorted, and + * 3. a <= b <= c <= d <= n (whenever they are valid). + */ + for (;;) { + size_t b, c, d; + + if (a) /* Building heap: sift down --a */ + a -= size; + else if (n -= size) /* Sorting: Extract root to --n */ + do_swap(base, base + n, size, swap_func, priv); + else /* Sort complete */ + break; + + /* + * Sift element at "a" down into heap. This is the + * "bottom-up" variant, which significantly reduces + * calls to cmp_func(): we find the sift-down path all + * the way to the leaves (one compare per level), then + * backtrack to find where to insert the target element. + * + * Because elements tend to sift down close to the leaves, + * this uses fewer compares than doing two per level + * on the way down. (A bit more than half as many on + * average, 3/4 worst-case.) + */ + for (b = a; c = 2*b + size, (d = c + size) < n;) + b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d; + if (d == n) /* Special case last leaf with no sibling */ + b = c; + + /* Now backtrack from "b" to the correct location for "a" */ + while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0) + b = parent(b, lsbit, size); + c = b; /* Where "a" belongs */ + while (b != a) { /* Shift it into place */ + b = parent(b, lsbit, size); + do_swap(base + b, base + c, size, swap_func, priv); + } + } +} + +void sort(void *base, size_t num, size_t size, + cmp_func_t cmp_func, + swap_func_t swap_func) +{ + struct wrapper w = { + .cmp = cmp_func, + .swap = swap_func, + }; + + return sort_r(base, num, size, _CMP_WRAPPER, SWAP_WRAPPER, &w); +} diff --git a/ubifs-utils/common/sort.h b/ubifs-utils/common/sort.h new file mode 100644 index 0000000..8982942 --- /dev/null +++ b/ubifs-utils/common/sort.h @@ -0,0 +1,20 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_SORT_H +#define _LINUX_SORT_H + +typedef void (*swap_r_func_t)(void *a, void *b, int size, const void *priv); +typedef void (*swap_func_t)(void *a, void *b, int size); + +typedef int (*cmp_r_func_t)(const void *a, const void *b, const void *priv); +typedef int (*cmp_func_t)(const void *a, const void *b); + +void sort_r(void *base, size_t num, size_t size, + cmp_r_func_t cmp_func, + swap_r_func_t swap_func, + const void *priv); + +void sort(void *base, size_t num, size_t size, + cmp_func_t cmp_func, + swap_func_t swap_func); + +#endif diff --git a/ubifs-utils/common/spinlock.h b/ubifs-utils/common/spinlock.h new file mode 100644 index 0000000..b9ed393 --- /dev/null +++ b/ubifs-utils/common/spinlock.h @@ -0,0 +1,14 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __LINUX_SPINLOCK_H_ +#define __LINUX_SPINLOCK_H_ + +#include <pthread.h> + +#define spinlock_t pthread_mutex_t +#define DEFINE_SPINLOCK(x) pthread_mutex_t x = PTHREAD_MUTEX_INITIALIZER +#define spin_lock_init(x) pthread_mutex_init(x, NULL) + +#define spin_lock(x) pthread_mutex_lock(x) +#define spin_unlock(x) pthread_mutex_unlock(x) + +#endif |