From e7e19cd9d8cc0f54ca463c4aebf7c4ef5e4f84f8 Mon Sep 17 00:00:00 2001 From: Zhihao Cheng Date: Mon, 11 Nov 2024 16:36:32 +0800 Subject: ubifs-utils: Split common source files from mkfs.ubifs Split common source files into common dir from mkfs.ubifs, this is a preparation for importing libubifs(from linux kernel) to replace current UBIFS libs. Signed-off-by: Zhihao Cheng Signed-off-by: David Oberhollenzer --- ubifs-utils/Makemodule.am | 57 +- ubifs-utils/common/README | 9 + ubifs-utils/common/compr.c | 284 ++++++++++ ubifs-utils/common/compr.h | 47 ++ ubifs-utils/common/crc16.c | 56 ++ ubifs-utils/common/crc16.h | 27 + ubifs-utils/common/crypto.c | 368 +++++++++++++ ubifs-utils/common/crypto.h | 58 ++ ubifs-utils/common/defs.h | 90 ++++ ubifs-utils/common/devtable.c | 535 +++++++++++++++++++ ubifs-utils/common/fscrypt.c | 282 ++++++++++ ubifs-utils/common/fscrypt.h | 171 ++++++ ubifs-utils/common/hashtable/hashtable.c | 277 ++++++++++ ubifs-utils/common/hashtable/hashtable.h | 199 +++++++ ubifs-utils/common/hashtable/hashtable_itr.c | 176 ++++++ ubifs-utils/common/hashtable/hashtable_itr.h | 112 ++++ ubifs-utils/common/hashtable/hashtable_private.h | 85 +++ ubifs-utils/common/key.h | 222 ++++++++ ubifs-utils/common/lpt.c | 590 +++++++++++++++++++++ ubifs-utils/common/lpt.h | 28 + ubifs-utils/common/sign.c | 410 ++++++++++++++ ubifs-utils/common/sign.h | 80 +++ ubifs-utils/common/ubifs.h | 471 ++++++++++++++++ ubifs-utils/mkfs.ubifs/README | 9 - ubifs-utils/mkfs.ubifs/compr.c | 284 ---------- ubifs-utils/mkfs.ubifs/compr.h | 47 -- ubifs-utils/mkfs.ubifs/crc16.c | 56 -- ubifs-utils/mkfs.ubifs/crc16.h | 27 - ubifs-utils/mkfs.ubifs/crypto.c | 368 ------------- ubifs-utils/mkfs.ubifs/crypto.h | 58 -- ubifs-utils/mkfs.ubifs/defs.h | 90 ---- ubifs-utils/mkfs.ubifs/devtable.c | 535 ------------------- ubifs-utils/mkfs.ubifs/fscrypt.c | 282 ---------- ubifs-utils/mkfs.ubifs/fscrypt.h | 171 ------ ubifs-utils/mkfs.ubifs/hashtable/hashtable.c | 277 ---------- ubifs-utils/mkfs.ubifs/hashtable/hashtable.h | 199 ------- ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.c | 176 ------ ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.h | 112 ---- .../mkfs.ubifs/hashtable/hashtable_private.h | 85 --- ubifs-utils/mkfs.ubifs/key.h | 222 -------- ubifs-utils/mkfs.ubifs/lpt.c | 590 --------------------- ubifs-utils/mkfs.ubifs/lpt.h | 28 - ubifs-utils/mkfs.ubifs/sign.c | 410 -------------- ubifs-utils/mkfs.ubifs/sign.h | 80 --- ubifs-utils/mkfs.ubifs/ubifs.h | 471 ---------------- 45 files changed, 4607 insertions(+), 4604 deletions(-) create mode 100644 ubifs-utils/common/README create mode 100644 ubifs-utils/common/compr.c create mode 100644 ubifs-utils/common/compr.h create mode 100644 ubifs-utils/common/crc16.c create mode 100644 ubifs-utils/common/crc16.h create mode 100644 ubifs-utils/common/crypto.c create mode 100644 ubifs-utils/common/crypto.h create mode 100644 ubifs-utils/common/defs.h create mode 100644 ubifs-utils/common/devtable.c create mode 100644 ubifs-utils/common/fscrypt.c create mode 100644 ubifs-utils/common/fscrypt.h create mode 100644 ubifs-utils/common/hashtable/hashtable.c create mode 100644 ubifs-utils/common/hashtable/hashtable.h create mode 100644 ubifs-utils/common/hashtable/hashtable_itr.c create mode 100644 ubifs-utils/common/hashtable/hashtable_itr.h create mode 100644 ubifs-utils/common/hashtable/hashtable_private.h create mode 100644 ubifs-utils/common/key.h create mode 100644 ubifs-utils/common/lpt.c create mode 100644 ubifs-utils/common/lpt.h create mode 100644 ubifs-utils/common/sign.c create mode 100644 ubifs-utils/common/sign.h create mode 100644 ubifs-utils/common/ubifs.h delete mode 100644 ubifs-utils/mkfs.ubifs/README delete mode 100644 ubifs-utils/mkfs.ubifs/compr.c delete mode 100644 ubifs-utils/mkfs.ubifs/compr.h delete mode 100644 ubifs-utils/mkfs.ubifs/crc16.c delete mode 100644 ubifs-utils/mkfs.ubifs/crc16.h delete mode 100644 ubifs-utils/mkfs.ubifs/crypto.c delete mode 100644 ubifs-utils/mkfs.ubifs/crypto.h delete mode 100644 ubifs-utils/mkfs.ubifs/defs.h delete mode 100644 ubifs-utils/mkfs.ubifs/devtable.c delete mode 100644 ubifs-utils/mkfs.ubifs/fscrypt.c delete mode 100644 ubifs-utils/mkfs.ubifs/fscrypt.h delete mode 100644 ubifs-utils/mkfs.ubifs/hashtable/hashtable.c delete mode 100644 ubifs-utils/mkfs.ubifs/hashtable/hashtable.h delete mode 100644 ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.c delete mode 100644 ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.h delete mode 100644 ubifs-utils/mkfs.ubifs/hashtable/hashtable_private.h delete mode 100644 ubifs-utils/mkfs.ubifs/key.h delete mode 100644 ubifs-utils/mkfs.ubifs/lpt.c delete mode 100644 ubifs-utils/mkfs.ubifs/lpt.h delete mode 100644 ubifs-utils/mkfs.ubifs/sign.c delete mode 100644 ubifs-utils/mkfs.ubifs/sign.h delete mode 100644 ubifs-utils/mkfs.ubifs/ubifs.h diff --git a/ubifs-utils/Makemodule.am b/ubifs-utils/Makemodule.am index 6814d47..4a617c1 100644 --- a/ubifs-utils/Makemodule.am +++ b/ubifs-utils/Makemodule.am @@ -1,37 +1,40 @@ -mkfs_ubifs_SOURCES = \ - ubifs-utils/mkfs.ubifs/mkfs.ubifs.c \ - ubifs-utils/mkfs.ubifs/defs.h \ - ubifs-utils/mkfs.ubifs/lpt.h \ - ubifs-utils/mkfs.ubifs/mkfs.ubifs.h \ - ubifs-utils/mkfs.ubifs/crc16.h \ - ubifs-utils/mkfs.ubifs/key.h \ - ubifs-utils/mkfs.ubifs/compr.h \ - ubifs-utils/mkfs.ubifs/ubifs.h \ - ubifs-utils/mkfs.ubifs/sign.h \ - ubifs-utils/mkfs.ubifs/crc16.c \ - ubifs-utils/mkfs.ubifs/lpt.c \ - ubifs-utils/mkfs.ubifs/compr.c \ - ubifs-utils/mkfs.ubifs/hashtable/hashtable.h \ - ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.h \ - ubifs-utils/mkfs.ubifs/hashtable/hashtable_private.h \ - ubifs-utils/mkfs.ubifs/hashtable/hashtable.c \ - ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.c \ - ubifs-utils/mkfs.ubifs/devtable.c \ +common_SOURCES = \ + ubifs-utils/common/defs.h \ + ubifs-utils/common/crc16.h \ + ubifs-utils/common/crc16.c \ + ubifs-utils/common/compr.h \ + ubifs-utils/common/compr.c \ + ubifs-utils/common/hashtable/hashtable.h \ + ubifs-utils/common/hashtable/hashtable_itr.h \ + ubifs-utils/common/hashtable/hashtable_private.h \ + ubifs-utils/common/hashtable/hashtable.c \ + ubifs-utils/common/hashtable/hashtable_itr.c \ + ubifs-utils/common/devtable.c \ + ubifs-utils/common/ubifs.h \ + ubifs-utils/common/key.h \ + ubifs-utils/common/lpt.h \ + ubifs-utils/common/lpt.c \ + ubifs-utils/common/sign.h \ include/mtd/ubifs-media.h if WITH_CRYPTO -mkfs_ubifs_SOURCES += ubifs-utils/mkfs.ubifs/crypto.c \ - ubifs-utils/mkfs.ubifs/crypto.h \ - ubifs-utils/mkfs.ubifs/fscrypt.c \ - ubifs-utils/mkfs.ubifs/fscrypt.h \ - ubifs-utils/mkfs.ubifs/sign.c +common_SOURCES += ubifs-utils/common/crypto.c \ + ubifs-utils/common/crypto.h \ + ubifs-utils/common/fscrypt.c \ + ubifs-utils/common/fscrypt.h \ + ubifs-utils/common/sign.c endif +mkfs_ubifs_SOURCES = \ + $(common_SOURCES) \ + ubifs-utils/mkfs.ubifs/mkfs.ubifs.h \ + ubifs-utils/mkfs.ubifs/mkfs.ubifs.c + mkfs_ubifs_LDADD = libmtd.a libubi.a $(ZLIB_LIBS) $(LZO_LIBS) $(ZSTD_LIBS) $(UUID_LIBS) $(LIBSELINUX_LIBS) $(OPENSSL_LIBS) -lm -mkfs_ubifs_CPPFLAGS = $(AM_CPPFLAGS) $(ZLIB_CFLAGS) $(LZO_CFLAGS) $(ZSTD_CFLAGS) $(UUID_CFLAGS) $(LIBSELINUX_CFLAGS)\ - -I$(top_srcdir)/ubi-utils/include -I$(top_srcdir)/ubifs-utils/mkfs.ubifs/ +mkfs_ubifs_CPPFLAGS = $(AM_CPPFLAGS) $(ZLIB_CFLAGS) $(LZO_CFLAGS) $(ZSTD_CFLAGS) $(UUID_CFLAGS) $(LIBSELINUX_CFLAGS) \ + -I$(top_srcdir)/ubi-utils/include -I$(top_srcdir)/ubifs-utils/mkfs.ubifs/ -I$(top_srcdir)/ubifs-utils/common -EXTRA_DIST += ubifs-utils/mkfs.ubifs/README +EXTRA_DIST += ubifs-utils/common/README dist_sbin_SCRIPTS = ubifs-utils/mount.ubifs diff --git a/ubifs-utils/common/README b/ubifs-utils/common/README new file mode 100644 index 0000000..8c10fd4 --- /dev/null +++ b/ubifs-utils/common/README @@ -0,0 +1,9 @@ +Common Library + +* crc16.h and crc16.c were copied from the linux kernel. +* crc32.h and crc32.c were copied from mtd-utils and amended. +* ubifs.h is a selection of definitions from fs/ubifs/ubifs.h from the linux kernel. +* key.h is copied from fs/ubifs/key.h from the linux kernel. +* defs.h is a bunch of definitions to smooth things over. +* lpt.c is a selection of functions copied from fs/ubifs/lpt.c from the linux kernel, and amended. +* hashtable/* was downloaded from http://www.cl.cam.ac.uk/~cwc22/hashtable/ diff --git a/ubifs-utils/common/compr.c b/ubifs-utils/common/compr.c new file mode 100644 index 0000000..e4324f3 --- /dev/null +++ b/ubifs-utils/common/compr.c @@ -0,0 +1,284 @@ +/* + * 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 +#include +#include +#include +#ifdef WITH_LZO +#include +#endif +#include +#ifdef WITH_ZSTD +#include +#endif + +#ifdef WITH_ZLIB +#define crc32 __zlib_crc32 +#include +#undef crc32 +#endif + +#include "compr.h" +#include "mkfs.ubifs.h" + +static void *lzo_mem; +static unsigned long long errcnt = 0; +#ifdef WITH_LZO +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 = MKFS_UBIFS_COMPR_LZO; + return 0; + +select_zlib: + *out_len = zlib_len; + *type = MKFS_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 MKFS_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 MKFS_UBIFS_COMPR_LZO: + ret = lzo_compress(in_buf, in_len, out_buf, out_len); + break; +#endif +#ifdef WITH_ZLIB + case MKFS_UBIFS_COMPR_ZLIB: + ret = zlib_deflate(in_buf, in_len, out_buf, out_len); + break; +#endif +#ifdef WITH_ZSTD + case MKFS_UBIFS_COMPR_ZSTD: + ret = zstd_compress(in_buf, in_len, out_buf, out_len); + break; +#endif + case MKFS_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 MKFS_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..d58c7c7 --- /dev/null +++ b/ubifs-utils/common/compr.h @@ -0,0 +1,47 @@ +/* + * 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 + +enum compression_type +{ + MKFS_UBIFS_COMPR_NONE, + MKFS_UBIFS_COMPR_LZO, + MKFS_UBIFS_COMPR_ZLIB, + MKFS_UBIFS_COMPR_ZSTD, +}; + +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 + * + * This code was taken from the linux kernel. The license is GPL Version 2. + */ + +#ifndef __CRC16_H__ +#define __CRC16_H__ + +#include +#include + +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..19c445e --- /dev/null +++ b/ubifs-utils/common/crypto.c @@ -0,0 +1,368 @@ +/* + * 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 + */ + +#define PROGRAM_NAME "mkfs.ubifs" +#include +#include +#include +#include + +#include "fscrypt.h" +#include "common.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 + */ + +#ifndef UBIFS_CRYPTO_H +#define UBIFS_CRYPTO_H + +#include +#include +#include +#include + + +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..8db5277 --- /dev/null +++ b/ubifs-utils/common/defs.h @@ -0,0 +1,90 @@ +/* + * 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__ + +#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 unlikely(x) (x) + +struct qstr +{ + char *name; + size_t len; +}; + +/** + * 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; +} + +#define do_div(n,base) ({ \ +int __res; \ +__res = ((unsigned long) n) % (unsigned) base; \ +n = ((unsigned long) n) / (unsigned) base; \ +__res; }) + +#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..aa815fb --- /dev/null +++ b/ubifs-utils/common/devtable.c @@ -0,0 +1,535 @@ +/* + * 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 + */ + +/* + * This file implemented device table support. Device table entries take the + * form of: + * + * /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 "mkfs.ubifs.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 err_msg("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 err_msg("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_err_msg("sscanf failed"); + + dbg_msg(3, "name %s, type %c, mode %o, uid %u, gid %u, major %u, " + "minor %u, start %u, inc %u, cnt %u", + buf, type, mode, uid, gid, major, minor, start, + increment, count); + + len = strnlen(buf, 1024); + if (len == 0) + return err_msg("empty path"); + if (len == 1024) + return err_msg("too long path"); + + if (buf[0] != '/') + return err_msg("device table entries require absolute paths"); + if (strstr(buf, "//")) + return err_msg("'//' cannot be used in the path"); + if (len > 1 && buf[len - 1] == '/') + return err_msg("do not put '/' at the end"); + + if (strstr(buf, "/./") || strstr(buf, "/../") || + !strcmp(buf + len - 2, "/.") || !strcmp(buf + len - 3, "/..")) + return err_msg("'.' 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 err_msg("link permission must be 0777"); + break; + default: + return err_msg("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) { + dbg_msg(3, "inserting '%s' into path hash table", path); + ph_elt = malloc(sizeof(struct path_htbl_element)); + if (!ph_elt) { + err_msg("cannot allocate %zd bytes of memory", + sizeof(struct path_htbl_element)); + goto out_free; + } + + if (!hashtable_insert(path_htbl, path, ph_elt)) { + err_msg("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) { + err_msg("cannot create name hash table"); + goto out_free; + } + } + + if (increment != 0 && count == 0) { + err_msg("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) { + err_msg("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); + + dbg_msg(3, "inserting '%s' into name hash table (major %d, minor %d)", + name, major(nh_elt->dev), minor(nh_elt->dev)); + + if (hashtable_search(ph_elt->name_htbl, name)) { + err_msg("'%s' is referred twice", buf); + goto out_free; + } + + nh_elt->name = name; + if (!hashtable_insert(ph_elt->name_htbl, name, nh_elt)) { + err_msg("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) { + err_msg("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) { + err_msg("cannot allocate %d bytes of memory", len); + goto out_free; + } + + sprintf(nm, "%s%d", name, i); + nh_elt->name = nm; + + dbg_msg(3, "inserting '%s' into name hash table (major %d, minor %d)", + nm, major(nh_elt->dev), minor(nh_elt->dev)); + + if (hashtable_search(ph_elt->name_htbl, nm)) { + err_msg("'%s' is referred twice", buf); + free (nm); + goto out_free; + } + + if (!hashtable_insert(ph_elt->name_htbl, nm, nh_elt)) { + err_msg("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; + + dbg_msg(1, "parsing device table file '%s'", tbl_file); + + path_htbl = create_hashtable(128, &r5_hash, &is_equivalent); + if (!path_htbl) + return err_msg("cannot create path hash table"); + + f = fopen(tbl_file, "r"); + if (!f) + return sys_err_msg("cannot open '%s'", tbl_file); + + if (fstat(fileno(f), &st) < 0) { + sys_err_msg("cannot stat '%s'", tbl_file); + goto out_close; + } + + if (st.st_size < 10) { + sys_err_msg("'%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)) { + err_msg("cannot parse '%s'", line); + goto out_close; + } + } + + free(line); + line = NULL; + } + + dbg_msg(1, "finished parsing"); + fclose(f); + return 0; + +out_close: + fclose(f); + 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 err_msg("%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 err_msg("%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); + + dbg_msg(3, "set UID %d, GID %d, mode %o for %s/%s as device table says", + 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/fscrypt.c b/ubifs-utils/common/fscrypt.c new file mode 100644 index 0000000..b75bdf7 --- /dev/null +++ b/ubifs-utils/common/fscrypt.c @@ -0,0 +1,282 @@ +/* + * 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 + * David Oberhollenzer + */ + +#define PROGRAM_NAME "mkfs.ubifs" +#include "fscrypt.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) { + err_msg("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, 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 err_msg("could not compute subkey"); + } + + ret = fscrypt_cipher->encrypt_fname(inbuf, cryptlen, + crypt_key, *outbuf); + if (ret < 0) { + free(inbuf); + free(*outbuf); + return err_msg("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 err_msg("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 err_msg("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]) { + err_msg("key descriptor '%s' is too short", desc); + return -1; + } + if (!isxdigit(desc[i * 2]) || !isxdigit(desc[i * 2 + 1])) { + err_msg("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]) { + err_msg("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) { + err_msg("loading key from '%s': file is empty", key_file); + goto fail; + } + if (keysize < fsc->key_length) { + err_msg("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..ff3d326 --- /dev/null +++ b/ubifs-utils/common/fscrypt.h @@ -0,0 +1,171 @@ +/* + * 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 + * David Oberhollenzer + */ + +#ifndef FSCRYPT_H +#define FSCRYPT_H + + +#include "mkfs.ubifs.h" +#include +#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]; +} __attribute__((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]; +} __attribute__((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, 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, 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..c1f99ed --- /dev/null +++ b/ubifs-utils/common/hashtable/hashtable.c @@ -0,0 +1,277 @@ +/* Copyright (C) 2004 Christopher Clark */ + +#define PROGRAM_NAME "hashtable" + +#include "common.h" +#include "hashtable.h" +#include "hashtable_private.h" +#include +#include +#include +#include + +/* +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 */ + +#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 */ + +#include "hashtable.h" +#include "hashtable_private.h" +#include "hashtable_itr.h" +#include /* 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 */ + +#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 */ + +#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/key.h b/ubifs-utils/common/key.h new file mode 100644 index 0000000..2de530b --- /dev/null +++ b/ubifs-utils/common/key.h @@ -0,0 +1,222 @@ +/* + * This file is part of UBIFS. + * + * Copyright (C) 2006-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 + * + * Authors: Artem Bityutskiy (Битюцкий Артём) + * Adrian Hunter + */ + +/* + * This header contains various key-related definitions and helper function. + * UBIFS allows several key schemes, so we access key fields only via these + * helpers. At the moment only one key scheme is supported. + * + * Simple key scheme + * ~~~~~~~~~~~~~~~~~ + * + * Keys are 64-bits long. First 32-bits are inode number (parent inode number + * in case of direntry key). Next 3 bits are node type. The last 29 bits are + * 4KiB offset in case of inode node, and direntry hash in case of a direntry + * node. We use "r5" hash borrowed from reiserfs. + */ + +#ifndef __UBIFS_KEY_H__ +#define __UBIFS_KEY_H__ + +#include + +/** + * key_mask_hash - mask a valid hash value. + * @val: value to be masked + * + * We use hash values as offset in directories, so values %0 and %1 are + * reserved for "." and "..". %2 is reserved for "end of readdir" marker. This + * function makes sure the reserved values are not used. + */ +static inline uint32_t key_mask_hash(uint32_t hash) +{ + hash &= UBIFS_S_KEY_HASH_MASK; + if (unlikely(hash <= 2)) + hash += 3; + return hash; +} + +/** + * key_r5_hash - R5 hash function (borrowed from reiserfs). + * @s: direntry name + * @len: name length + */ +static inline uint32_t key_r5_hash(const char *s, int len) +{ + uint32_t a = 0; + const signed char *str = (const signed char *)s; + + while (len--) { + a += *str << 4; + a += *str >> 4; + a *= 11; + str++; + } + + return key_mask_hash(a); +} + +/** + * key_test_hash - testing hash function. + * @str: direntry name + * @len: name length + */ +static inline uint32_t key_test_hash(const char *str, int len) +{ + uint32_t a = 0; + + len = min_t(uint32_t, len, 4); + memcpy(&a, str, len); + return key_mask_hash(a); +} + +/** + * ino_key_init - initialize inode key. + * @c: UBIFS file-system description object + * @key: key to initialize + * @inum: inode number + */ +static inline void ino_key_init(union ubifs_key *key, ino_t inum) +{ + key->u32[0] = inum; + key->u32[1] = UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS; +} + +/** + * dent_key_init - initialize directory entry key. + * @c: UBIFS file-system description object + * @key: key to initialize + * @inum: parent inode number + * @nm: direntry name and length + */ +static inline void dent_key_init(const struct ubifs_info *c, + union ubifs_key *key, ino_t inum, + const void *name, int name_len) +{ + uint32_t hash = c->key_hash(name, name_len); + + assert(!(hash & ~UBIFS_S_KEY_HASH_MASK)); + key->u32[0] = inum; + key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS); +} + +/** + * xent_key_init - initialize extended attribute entry key. + * @c: UBIFS file-system description object + * @key: key to initialize + * @inum: host inode number + * @nm: extended attribute entry name and length + */ +static inline void xent_key_init(const struct ubifs_info *c, + union ubifs_key *key, ino_t inum, + const struct qstr *nm) +{ + uint32_t hash = c->key_hash(nm->name, nm->len); + + assert(!(hash & ~UBIFS_S_KEY_HASH_MASK)); + key->u32[0] = inum; + key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS); +} + +/** + * data_key_init - initialize data key. + * @c: UBIFS file-system description object + * @key: key to initialize + * @inum: inode number + * @block: block number + */ +static inline void data_key_init(union ubifs_key *key, ino_t inum, + unsigned int block) +{ + assert(!(block & ~UBIFS_S_KEY_BLOCK_MASK)); + key->u32[0] = inum; + key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS); +} + +/** + * key_write - transform a key from in-memory format. + * @c: UBIFS file-system description object + * @from: the key to transform + * @to: the key to store the result + */ +static inline void key_write(const union ubifs_key *from, void *to) +{ + __le32 x[2]; + + x[0] = cpu_to_le32(from->u32[0]); + x[1] = cpu_to_le32(from->u32[1]); + + memcpy(to, &x, 8); + memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8); +} + +/** + * key_write_idx - transform a key from in-memory format for the index. + * @c: UBIFS file-system description object + * @from: the key to transform + * @to: the key to store the result + */ +static inline void key_write_idx(const union ubifs_key *from, void *to) +{ + __le32 x[2]; + + x[0] = cpu_to_le32(from->u32[0]); + x[1] = cpu_to_le32(from->u32[1]); + + memcpy(to, &x, 8); +} + +/** + * keys_cmp - compare keys. + * @c: UBIFS file-system description object + * @key1: the first key to compare + * @key2: the second key to compare + * + * This function compares 2 keys and returns %-1 if @key1 is less than + * @key2, 0 if the keys are equivalent and %1 if @key1 is greater than @key2. + */ +static inline int keys_cmp(const union ubifs_key *key1, + const union ubifs_key *key2) +{ + if (key1->u32[0] < key2->u32[0]) + return -1; + if (key1->u32[0] > key2->u32[0]) + return 1; + if (key1->u32[1] < key2->u32[1]) + return -1; + if (key1->u32[1] > key2->u32[1]) + return 1; + + return 0; +} + +/** + * key_type - get key type. + * @c: UBIFS file-system description object + * @key: key to get type of + */ +static inline int key_type(const union ubifs_key *key) +{ + return key->u32[1] >> UBIFS_S_KEY_BLOCK_BITS; +} + +#endif /* !__UBIFS_KEY_H__ */ diff --git a/ubifs-utils/common/lpt.c b/ubifs-utils/common/lpt.c new file mode 100644 index 0000000..7ee739a --- /dev/null +++ b/ubifs-utils/common/lpt.c @@ -0,0 +1,590 @@ +/* + * This file is part of UBIFS. + * + * Copyright (C) 2006, 2007 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 + * + * Authors: Adrian Hunter + * Artem Bityutskiy + */ + +#include "mkfs.ubifs.h" + +#ifdef WITH_CRYPTO +#include +#endif + +/** + * do_calc_lpt_geom - calculate sizes for the LPT area. + * @c: the UBIFS file-system description object + * + * Calculate the sizes of LPT bit fields, nodes, and tree, based on the + * properties of the flash and whether LPT is "big" (c->big_lpt). + */ +static void do_calc_lpt_geom(struct ubifs_info *c) +{ + int n, bits, per_leb_wastage; + long long sz, tot_wastage; + + c->pnode_cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; + + n = (c->pnode_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; + c->nnode_cnt = n; + while (n > 1) { + n = (n + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; + c->nnode_cnt += n; + } + + c->lpt_hght = 1; + n = UBIFS_LPT_FANOUT; + while (n < c->pnode_cnt) { + c->lpt_hght += 1; + n <<= UBIFS_LPT_FANOUT_SHIFT; + } + + c->space_bits = fls(c->leb_size) - 3; + c->lpt_lnum_bits = fls(c->lpt_lebs); + c->lpt_offs_bits = fls(c->leb_size - 1); + c->lpt_spc_bits = fls(c->leb_size); + + n = (c->max_leb_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; + c->pcnt_bits = fls(n - 1); + + c->lnum_bits = fls(c->max_leb_cnt - 1); + + bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + + (c->big_lpt ? c->pcnt_bits : 0) + + (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT; + c->pnode_sz = (bits + 7) / 8; + + bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + + (c->big_lpt ? c->pcnt_bits : 0) + + (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT; + c->nnode_sz = (bits + 7) / 8; + + bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + + c->lpt_lebs * c->lpt_spc_bits * 2; + c->ltab_sz = (bits + 7) / 8; + + bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + + c->lnum_bits * c->lsave_cnt; + c->lsave_sz = (bits + 7) / 8; + + /* Calculate the minimum LPT size */ + c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz; + c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz; + c->lpt_sz += c->ltab_sz; + c->lpt_sz += c->lsave_sz; + + /* Add wastage */ + sz = c->lpt_sz; + per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz); + sz += per_leb_wastage; + tot_wastage = per_leb_wastage; + while (sz > c->leb_size) { + sz += per_leb_wastage; + sz -= c->leb_size; + tot_wastage += per_leb_wastage; + } + tot_wastage += ALIGN(sz, c->min_io_size) - sz; + c->lpt_sz += tot_wastage; +} + +/** + * calc_dflt_lpt_geom - calculate default LPT geometry. + * @c: the UBIFS file-system description object + * @main_lebs: number of main area LEBs is passed and returned here + * @big_lpt: whether the LPT area is "big" is returned here + * + * The size of the LPT area depends on parameters that themselves are dependent + * on the size of the LPT area. This function, successively recalculates the LPT + * area geometry until the parameters and resultant geometry are consistent. + * + * This function returns %0 on success and a negative error code on failure. + */ +int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt) +{ + int i, lebs_needed; + long long sz; + + /* Start by assuming the minimum number of LPT LEBs */ + c->lpt_lebs = UBIFS_MIN_LPT_LEBS; + c->main_lebs = *main_lebs - c->lpt_lebs; + if (c->main_lebs <= 0) + return -EINVAL; + + /* And assume we will use the small LPT model */ + c->big_lpt = 0; + + /* + * Calculate the geometry based on assumptions above and then see if it + * makes sense + */ + do_calc_lpt_geom(c); + + /* Small LPT model must have lpt_sz < leb_size */ + if (c->lpt_sz > c->leb_size) { + /* Nope, so try again using big LPT model */ + c->big_lpt = 1; + do_calc_lpt_geom(c); + } + + /* Now check there are enough LPT LEBs */ + for (i = 0; i < 64 ; i++) { + sz = c->lpt_sz * 4; /* Allow 4 times the size */ + sz += c->leb_size - 1; + do_div(sz, c->leb_size); + lebs_needed = sz; + if (lebs_needed > c->lpt_lebs) { + /* Not enough LPT LEBs so try again with more */ + c->lpt_lebs = lebs_needed; + c->main_lebs = *main_lebs - c->lpt_lebs; + if (c->main_lebs <= 0) + return -EINVAL; + do_calc_lpt_geom(c); + continue; + } + if (c->ltab_sz > c->leb_size) { + err_msg("LPT ltab too big"); + return -EINVAL; + } + *main_lebs = c->main_lebs; + *big_lpt = c->big_lpt; + return 0; + } + return -EINVAL; +} + +/** + * pack_bits - pack bit fields end-to-end. + * @addr: address at which to pack (passed and next address returned) + * @pos: bit position at which to pack (passed and next position returned) + * @val: value to pack + * @nrbits: number of bits of value to pack (1-32) + */ +static void pack_bits(uint8_t **addr, int *pos, uint32_t val, int nrbits) +{ + uint8_t *p = *addr; + int b = *pos; + + if (b) { + *p |= ((uint8_t)val) << b; + nrbits += b; + if (nrbits > 8) { + *++p = (uint8_t)(val >>= (8 - b)); + if (nrbits > 16) { + *++p = (uint8_t)(val >>= 8); + if (nrbits > 24) { + *++p = (uint8_t)(val >>= 8); + if (nrbits > 32) + *++p = (uint8_t)(val >>= 8); + } + } + } + } else { + *p = (uint8_t)val; + if (nrbits > 8) { + *++p = (uint8_t)(val >>= 8); + if (nrbits > 16) { + *++p = (uint8_t)(val >>= 8); + if (nrbits > 24) + *++p = (uint8_t)(val >>= 8); + } + } + } + b = nrbits & 7; + if (b == 0) + p++; + *addr = p; + *pos = b; +} + +/** + * pack_pnode - pack all the bit fields of a pnode. + * @c: UBIFS file-system description object + * @buf: buffer into which to pack + * @pnode: pnode to pack + */ +static void pack_pnode(struct ubifs_info *c, void *buf, + struct ubifs_pnode *pnode) +{ + uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; + int i, pos = 0; + uint16_t crc; + + pack_bits(&addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS); + if (c->big_lpt) + pack_bits(&addr, &pos, pnode->num, c->pcnt_bits); + for (i = 0; i < UBIFS_LPT_FANOUT; i++) { + pack_bits(&addr, &pos, pnode->lprops[i].free >> 3, + c->space_bits); + pack_bits(&addr, &pos, pnode->lprops[i].dirty >> 3, + c->space_bits); + if (pnode->lprops[i].flags & LPROPS_INDEX) + pack_bits(&addr, &pos, 1, 1); + else + pack_bits(&addr, &pos, 0, 1); + } + crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, + c->pnode_sz - UBIFS_LPT_CRC_BYTES); + addr = buf; + pos = 0; + pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); +} + +/** + * pack_nnode - pack all the bit fields of a nnode. + * @c: UBIFS file-system description object + * @buf: buffer into which to pack + * @nnode: nnode to pack + */ +static void pack_nnode(struct ubifs_info *c, void *buf, + struct ubifs_nnode *nnode) +{ + uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; + int i, pos = 0; + uint16_t crc; + + pack_bits(&addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS); + if (c->big_lpt) + pack_bits(&addr, &pos, nnode->num, c->pcnt_bits); + for (i = 0; i < UBIFS_LPT_FANOUT; i++) { + int lnum = nnode->nbranch[i].lnum; + + if (lnum == 0) + lnum = c->lpt_last + 1; + pack_bits(&addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits); + pack_bits(&addr, &pos, nnode->nbranch[i].offs, + c->lpt_offs_bits); + } + crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, + c->nnode_sz - UBIFS_LPT_CRC_BYTES); + addr = buf; + pos = 0; + pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); +} + +/** + * pack_ltab - pack the LPT's own lprops table. + * @c: UBIFS file-system description object + * @buf: buffer into which to pack + * @ltab: LPT's own lprops table to pack + */ +static void pack_ltab(struct ubifs_info *c, void *buf, + struct ubifs_lpt_lprops *ltab) +{ + uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; + int i, pos = 0; + uint16_t crc; + + pack_bits(&addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS); + for (i = 0; i < c->lpt_lebs; i++) { + pack_bits(&addr, &pos, ltab[i].free, c->lpt_spc_bits); + pack_bits(&addr, &pos, ltab[i].dirty, c->lpt_spc_bits); + } + crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, + c->ltab_sz - UBIFS_LPT_CRC_BYTES); + addr = buf; + pos = 0; + pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); +} + +/** + * pack_lsave - pack the LPT's save table. + * @c: UBIFS file-system description object + * @buf: buffer into which to pack + * @lsave: LPT's save table to pack + */ +static void pack_lsave(struct ubifs_info *c, void *buf, int *lsave) +{ + uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; + int i, pos = 0; + uint16_t crc; + + pack_bits(&addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS); + for (i = 0; i < c->lsave_cnt; i++) + pack_bits(&addr, &pos, lsave[i], c->lnum_bits); + crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, + c->lsave_sz - UBIFS_LPT_CRC_BYTES); + addr = buf; + pos = 0; + pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); +} + +/** + * set_ltab - set LPT LEB properties. + * @c: UBIFS file-system description object + * @lnum: LEB number + * @free: amount of free space + * @dirty: amount of dirty space + */ +static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty) +{ + dbg_msg(3, "LEB %d free %d dirty %d to %d %d", + lnum, c->ltab[lnum - c->lpt_first].free, + c->ltab[lnum - c->lpt_first].dirty, free, dirty); + c->ltab[lnum - c->lpt_first].free = free; + c->ltab[lnum - c->lpt_first].dirty = dirty; +} + +/** + * calc_nnode_num - calculate nnode number. + * @row: the row in the tree (root is zero) + * @col: the column in the row (leftmost is zero) + * + * The nnode number is a number that uniquely identifies a nnode and can be used + * easily to traverse the tree from the root to that nnode. + * + * This function calculates and returns the nnode number for the nnode at @row + * and @col. + */ +static int calc_nnode_num(int row, int col) +{ + int num, bits; + + num = 1; + while (row--) { + bits = (col & (UBIFS_LPT_FANOUT - 1)); + col >>= UBIFS_LPT_FANOUT_SHIFT; + num <<= UBIFS_LPT_FANOUT_SHIFT; + num |= bits; + } + return num; +} + +/** + * create_lpt - create LPT. + * @c: UBIFS file-system description object + * + * This function returns %0 on success and a negative error code on failure. + */ +int create_lpt(struct ubifs_info *c) +{ + int lnum, err = 0, i, j, cnt, len, alen, row; + int blnum, boffs, bsz, bcnt; + struct ubifs_pnode *pnode = NULL; + struct ubifs_nnode *nnode = NULL; + void *buf = NULL, *p; + int *lsave = NULL; + unsigned int md_len; + + pnode = malloc(sizeof(struct ubifs_pnode)); + nnode = malloc(sizeof(struct ubifs_nnode)); + buf = malloc(c->leb_size); + lsave = malloc(sizeof(int) * c->lsave_cnt); + if (!pnode || !nnode || !buf || !lsave) { + err = -ENOMEM; + goto out; + } + memset(pnode, 0 , sizeof(struct ubifs_pnode)); + memset(nnode, 0 , sizeof(struct ubifs_nnode)); + + hash_digest_init(); + + c->lscan_lnum = c->main_first; + + lnum = c->lpt_first; + p = buf; + len = 0; + /* Number of leaf nodes (pnodes) */ + cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) >> UBIFS_LPT_FANOUT_SHIFT; + //printf("pnode_cnt=%d\n",cnt); + + /* + * To calculate the internal node branches, we keep information about + * the level below. + */ + blnum = lnum; /* LEB number of level below */ + boffs = 0; /* Offset of level below */ + bcnt = cnt; /* Number of nodes in level below */ + bsz = c->pnode_sz; /* Size of nodes in level below */ + + /* Add pnodes */ + for (i = 0; i < cnt; i++) { + if (len + c->pnode_sz > c->leb_size) { + alen = ALIGN(len, c->min_io_size); + set_ltab(c, lnum, c->leb_size - alen, alen - len); + memset(p, 0xff, alen - len); + err = write_leb(lnum++, alen, buf); + if (err) + goto out; + p = buf; + len = 0; + } + /* Fill in the pnode */ + for (j = 0; j < UBIFS_LPT_FANOUT; j++) { + int k = (i << UBIFS_LPT_FANOUT_SHIFT) + j; + + if (k < c->main_lebs) + pnode->lprops[j] = c->lpt[k]; + else { + pnode->lprops[j].free = c->leb_size; + pnode->lprops[j].dirty = 0; + pnode->lprops[j].flags = 0; + } + } + pack_pnode(c, p, pnode); + + hash_digest_update(p, c->pnode_sz); + + p += c->pnode_sz; + len += c->pnode_sz; + /* + * pnodes are simply numbered left to right starting at zero, + * which means the pnode number can be used easily to traverse + * down the tree to the corresponding pnode. + */ + pnode->num += 1; + } + + hash_digest_final(c->lpt_hash, &md_len); + + row = c->lpt_hght - 1; + /* Add all nnodes, one level at a time */ + while (1) { + /* Number of internal nodes (nnodes) at next level */ + cnt = (cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; + if (cnt == 0) + cnt = 1; + for (i = 0; i < cnt; i++) { + if (len + c->nnode_sz > c->leb_size) { + alen = ALIGN(len, c->min_io_size); + set_ltab(c, lnum, c->leb_size - alen, + alen - len); + memset(p, 0xff, alen - len); + err = write_leb(lnum++, alen, buf); + if (err) + goto out; + p = buf; + len = 0; + } + /* The root is on row zero */ + if (row == 0) { + c->lpt_lnum = lnum; + c->lpt_offs = len; + } + /* Set branches to the level below */ + for (j = 0; j < UBIFS_LPT_FANOUT; j++) { + if (bcnt) { + if (boffs + bsz > c->leb_size) { + blnum += 1; + boffs = 0; + } + nnode->nbranch[j].lnum = blnum; + nnode->nbranch[j].offs = boffs; + boffs += bsz; + bcnt--; + } else { + nnode->nbranch[j].lnum = 0; + nnode->nbranch[j].offs = 0; + } + } + nnode->num = calc_nnode_num(row, i); + pack_nnode(c, p, nnode); + p += c->nnode_sz; + len += c->nnode_sz; + } + /* Row zero is the top row */ + if (row == 0) + break; + /* Update the information about the level below */ + bcnt = cnt; + bsz = c->nnode_sz; + row -= 1; + } + + if (c->big_lpt) { + /* Need to add LPT's save table */ + if (len + c->lsave_sz > c->leb_size) { + alen = ALIGN(len, c->min_io_size); + set_ltab(c, lnum, c->leb_size - alen, alen - len); + memset(p, 0xff, alen - len); + err = write_leb(lnum++, alen, buf); + if (err) + goto out; + p = buf; + len = 0; + } + + c->lsave_lnum = lnum; + c->lsave_offs = len; + + for (i = 0; i < c->lsave_cnt; i++) + lsave[i] = c->main_first + i; + + pack_lsave(c, p, lsave); + p += c->lsave_sz; + len += c->lsave_sz; + } + + /* Need to add LPT's own LEB properties table */ + if (len + c->ltab_sz > c->leb_size) { + alen = ALIGN(len, c->min_io_size); + set_ltab(c, lnum, c->leb_size - alen, alen - len); + memset(p, 0xff, alen - len); + err = write_leb(lnum++, alen, buf); + if (err) + goto out; + p = buf; + len = 0; + } + + c->ltab_lnum = lnum; + c->ltab_offs = len; + + /* Update ltab before packing it */ + len += c->ltab_sz; + alen = ALIGN(len, c->min_io_size); + set_ltab(c, lnum, c->leb_size - alen, alen - len); + + pack_ltab(c, p, c->ltab); + p += c->ltab_sz; + + /* Write remaining buffer */ + memset(p, 0xff, alen - len); + err = write_leb(lnum, alen, buf); + if (err) + goto out; + + c->nhead_lnum = lnum; + c->nhead_offs = ALIGN(len, c->min_io_size); + + dbg_msg(1, "lpt_sz: %lld", c->lpt_sz); + dbg_msg(1, "space_bits: %d", c->space_bits); + dbg_msg(1, "lpt_lnum_bits: %d", c->lpt_lnum_bits); + dbg_msg(1, "lpt_offs_bits: %d", c->lpt_offs_bits); + dbg_msg(1, "lpt_spc_bits: %d", c->lpt_spc_bits); + dbg_msg(1, "pcnt_bits: %d", c->pcnt_bits); + dbg_msg(1, "lnum_bits: %d", c->lnum_bits); + dbg_msg(1, "pnode_sz: %d", c->pnode_sz); + dbg_msg(1, "nnode_sz: %d", c->nnode_sz); + dbg_msg(1, "ltab_sz: %d", c->ltab_sz); + dbg_msg(1, "lsave_sz: %d", c->lsave_sz); + dbg_msg(1, "lsave_cnt: %d", c->lsave_cnt); + dbg_msg(1, "lpt_hght: %d", c->lpt_hght); + dbg_msg(1, "big_lpt: %d", c->big_lpt); + dbg_msg(1, "LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs); + dbg_msg(1, "LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs); + dbg_msg(1, "LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs); + if (c->big_lpt) + dbg_msg(1, "LPT lsave is at %d:%d", + c->lsave_lnum, c->lsave_offs); +out: + free(lsave); + free(buf); + free(nnode); + free(pnode); + return err; +} diff --git a/ubifs-utils/common/lpt.h b/ubifs-utils/common/lpt.h new file mode 100644 index 0000000..4cde59d --- /dev/null +++ b/ubifs-utils/common/lpt.h @@ -0,0 +1,28 @@ +/* + * 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 + */ + +#ifndef __UBIFS_LPT_H__ +#define __UBIFS_LPT_H__ + +int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt); +int create_lpt(struct ubifs_info *c); + +#endif diff --git a/ubifs-utils/common/sign.c b/ubifs-utils/common/sign.c new file mode 100644 index 0000000..7f284f8 --- /dev/null +++ b/ubifs-utils/common/sign.c @@ -0,0 +1,410 @@ +/* + * 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 "mkfs.ubifs.h" +#include "common.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +static struct ubifs_info *c = &info_; + +EVP_MD_CTX *hash_md; +const EVP_MD *md; + +int authenticated(void) +{ + return c->hash_algo_name != NULL; +} + +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 + +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__); \ + err_msg(fmt, ## __VA_ARGS__); \ + -1; \ +}) + +static const char *key_pass; + +static int pem_pw_cb(char *buf, int len, __attribute__((unused)) int w, + __attribute__((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)) + err_msg("%s: Read wanted retry", x509_name); + if (n >= 0) + err_msg("%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 sign_superblock_node(void *node) +{ + EVP_PKEY *private_key; + CMS_ContentInfo *cms = NULL; + X509 *cert = NULL; + BIO *bd, *bm; + void *obuf; + long len; + int ret; + void *pret; + struct ubifs_sig_node *sig = node + UBIFS_SB_NODE_SZ; + + if (!authenticated()) + return 0; + + ERR_load_crypto_strings(); + ERR_clear_error(); + + key_pass = getenv("MKFS_UBIFS_SIGN_PIN"); + + bm = BIO_new_mem_buf(node, UBIFS_SB_NODE_SZ); + + private_key = read_private_key(c->auth_key_filename, &cert); + if (!private_key) + return -1; + + if (!cert) { + if (!c->auth_cert_filename) + return err_msg("authentication certificate not provided (--auth-cert)"); + cert = read_x509(c->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 err_msg("CMS_sign failed"); + + pret = CMS_add1_signer(cms, cert, private_key, md, + CMS_NOCERTS | CMS_BINARY | + CMS_NOSMIMECAP | CMS_NOATTR); + if (!pret) + return err_msg("CMS_add1_signer failed"); + + ret = CMS_final(cms, bm, NULL, CMS_NOCERTS | CMS_BINARY); + if (!ret) + return err_msg("CMS_final failed"); + + bd = BIO_new(BIO_s_mem()); + + ret = i2d_CMS_bio_stream(bd, cms, NULL, 0); + if (!ret) + return err_msg("i2d_CMS_bio_stream failed"); + + len = BIO_get_mem_data(bd, &obuf); + + sig->type = UBIFS_SIGNATURE_TYPE_PKCS7; + sig->len = cpu_to_le32(len); + sig->ch.node_type = UBIFS_SIG_NODE; + + memcpy(sig + 1, obuf, len); + + BIO_free(bd); + BIO_free(bm); + + return 0; +} + +/** + * ubifs_node_calc_hash - calculate the hash of a UBIFS node + * @c: UBIFS file-system description object + * @node: the node to calculate a hash for + * @hash: the returned hash + */ +void ubifs_node_calc_hash(const void *node, uint8_t *hash) +{ + const struct ubifs_ch *ch = node; + unsigned int md_len; + + if (!authenticated()) + return; + + EVP_DigestInit_ex(hash_md, md, NULL); + EVP_DigestUpdate(hash_md, node, le32_to_cpu(ch->len)); + EVP_DigestFinal_ex(hash_md, hash, &md_len); +} + +/** + * mst_node_calc_hash - calculate the hash of a UBIFS master node + * @c: UBIFS file-system description object + * @node: the node to calculate a hash for + * @hash: the returned hash + */ +void mst_node_calc_hash(const void *node, uint8_t *hash) +{ + unsigned int md_len; + + if (!authenticated()) + return; + + EVP_DigestInit_ex(hash_md, md, NULL); + EVP_DigestUpdate(hash_md, node + sizeof(struct ubifs_ch), + UBIFS_MST_NODE_SZ - sizeof(struct ubifs_ch)); + EVP_DigestFinal_ex(hash_md, hash, &md_len); +} + +void hash_digest_init(void) +{ + if (!authenticated()) + return; + + EVP_DigestInit_ex(hash_md, md, NULL); +} + +void hash_digest_update(const void *buf, int len) +{ + if (!authenticated()) + return; + + EVP_DigestUpdate(hash_md, buf, len); +} + +void hash_digest_final(void *hash, unsigned int *len) +{ + if (!authenticated()) + return; + + EVP_DigestFinal_ex(hash_md, hash, len); +} + +int init_authentication(void) +{ + int hash_algo; + + if (!c->auth_key_filename && !c->auth_cert_filename && !c->hash_algo_name) + return 0; + + if (!c->auth_key_filename) + return err_msg("authentication key not given (--auth-key)"); + + if (!c->hash_algo_name) + return err_msg("Hash algorithm not given (--hash-algo)"); + + OPENSSL_config(NULL); + + OpenSSL_add_all_algorithms(); + ERR_load_crypto_strings(); + + md = EVP_get_digestbyname(c->hash_algo_name); + if (!md) + return err_msg("Unknown message digest %s", c->hash_algo_name); + + hash_md = EVP_MD_CTX_create(); + c->hash_len = EVP_MD_size(md); + + hash_algo = match_string(hash_algo_name, HASH_ALGO__LAST, c->hash_algo_name); + if (hash_algo < 0) + return err_msg("Unsupported message digest %s", c->hash_algo_name); + + c->hash_algo = hash_algo; + + return 0; +} diff --git a/ubifs-utils/common/sign.h b/ubifs-utils/common/sign.h new file mode 100644 index 0000000..fe9fdd8 --- /dev/null +++ b/ubifs-utils/common/sign.h @@ -0,0 +1,80 @@ +/* + * 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__ + +#ifdef WITH_CRYPTO +#include + +void ubifs_node_calc_hash(const void *node, uint8_t *hash); +void mst_node_calc_hash(const void *node, uint8_t *hash); +void hash_digest_init(void); +void hash_digest_update(const void *buf, int len); +void hash_digest_final(void *hash, unsigned int *len); +int init_authentication(void); +int sign_superblock_node(void *node); +int authenticated(void); + +extern EVP_MD_CTX *hash_md; +extern const EVP_MD *md; + +#else +static inline void ubifs_node_calc_hash(__attribute__((unused)) const void *node, + __attribute__((unused)) uint8_t *hash) +{ +} + +static inline void mst_node_calc_hash(__attribute__((unused)) const void *node, + __attribute__((unused)) uint8_t *hash) +{ +} + +static inline void hash_digest_init(void) +{ +} + +static inline void hash_digest_update(__attribute__((unused)) const void *buf, + __attribute__((unused)) int len) +{ +} + +static inline void hash_digest_final(__attribute__((unused)) void *hash, + __attribute__((unused)) unsigned int *len) +{ +} + +static inline int init_authentication(void) +{ + return 0; +} + +static inline int sign_superblock_node(__attribute__((unused)) void *node) +{ + return 0; +} + +static inline int authenticated(void) +{ + return 0; +} + +#endif + +#endif /* __UBIFS_SIGN_H__ */ diff --git a/ubifs-utils/common/ubifs.h b/ubifs-utils/common/ubifs.h new file mode 100644 index 0000000..55937ce --- /dev/null +++ b/ubifs-utils/common/ubifs.h @@ -0,0 +1,471 @@ +/* + * This file is part of UBIFS. + * + * 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_H__ +#define __UBIFS_H__ + +/* Maximum logical eraseblock size in bytes */ +#define UBIFS_MAX_LEB_SZ (2*1024*1024) + +/* Minimum amount of data UBIFS writes to the flash */ +#define MIN_WRITE_SZ (UBIFS_DATA_NODE_SZ + 8) + +/* Largest key size supported in this implementation */ +#define CUR_MAX_KEY_LEN UBIFS_SK_LEN + +/* + * There is no notion of truncation key because truncation nodes do not exist + * in TNC. However, when replaying, it is handy to introduce fake "truncation" + * keys for truncation nodes because the code becomes simpler. So we define + * %UBIFS_TRUN_KEY type. + */ +#define UBIFS_TRUN_KEY UBIFS_KEY_TYPES_CNT + +/* + * How much a directory entry/extended attribute entry adds to the parent/host + * inode. + */ +#define CALC_DENT_SIZE(name_len) ALIGN(UBIFS_DENT_NODE_SZ + (name_len) + 1, 8) + +/* How much an extended attribute adds to the host inode */ +#define CALC_XATTR_BYTES(data_len) ALIGN(UBIFS_INO_NODE_SZ + (data_len) + 1, 8) + +/* The below union makes it easier to deal with keys */ +union ubifs_key +{ + uint8_t u8[CUR_MAX_KEY_LEN]; + uint32_t u32[CUR_MAX_KEY_LEN/4]; + uint64_t u64[CUR_MAX_KEY_LEN/8]; + __le32 j32[CUR_MAX_KEY_LEN/4]; +}; + +/* + * LEB properties flags. + * + * LPROPS_UNCAT: not categorized + * LPROPS_DIRTY: dirty > 0, not index + * LPROPS_DIRTY_IDX: dirty + free > UBIFS_CH_SZ and index + * LPROPS_FREE: free > 0, not empty, not index + * LPROPS_HEAP_CNT: number of heaps used for storing categorized LEBs + * LPROPS_EMPTY: LEB is empty, not taken + * LPROPS_FREEABLE: free + dirty == leb_size, not index, not taken + * LPROPS_FRDI_IDX: free + dirty == leb_size and index, may be taken + * LPROPS_CAT_MASK: mask for the LEB categories above + * LPROPS_TAKEN: LEB was taken (this flag is not saved on the media) + * LPROPS_INDEX: LEB contains indexing nodes (this flag also exists on flash) + */ +enum { + LPROPS_UNCAT = 0, + LPROPS_DIRTY = 1, + LPROPS_DIRTY_IDX = 2, + LPROPS_FREE = 3, + LPROPS_HEAP_CNT = 3, + LPROPS_EMPTY = 4, + LPROPS_FREEABLE = 5, + LPROPS_FRDI_IDX = 6, + LPROPS_CAT_MASK = 15, + LPROPS_TAKEN = 16, + LPROPS_INDEX = 32, +}; + +/** + * struct ubifs_lprops - logical eraseblock properties. + * @free: amount of free space in bytes + * @dirty: amount of dirty space in bytes + * @flags: LEB properties flags (see above) + */ +struct ubifs_lprops +{ + int free; + int dirty; + int flags; +}; + +/** + * struct ubifs_lpt_lprops - LPT logical eraseblock properties. + * @free: amount of free space in bytes + * @dirty: amount of dirty space in bytes + */ +struct ubifs_lpt_lprops +{ + int free; + int dirty; +}; + +struct ubifs_nnode; + +/** + * struct ubifs_cnode - LEB Properties Tree common node. + * @parent: parent nnode + * @cnext: next cnode to commit + * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE) + * @iip: index in parent + * @level: level in the tree (zero for pnodes, greater than zero for nnodes) + * @num: node number + */ +struct ubifs_cnode +{ + struct ubifs_nnode *parent; + struct ubifs_cnode *cnext; + unsigned long flags; + int iip; + int level; + int num; +}; + +/** + * struct ubifs_pnode - LEB Properties Tree leaf node. + * @parent: parent nnode + * @cnext: next cnode to commit + * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE) + * @iip: index in parent + * @level: level in the tree (always zero for pnodes) + * @num: node number + * @lprops: LEB properties array + */ +struct ubifs_pnode +{ + struct ubifs_nnode *parent; + struct ubifs_cnode *cnext; + unsigned long flags; + int iip; + int level; + int num; + struct ubifs_lprops lprops[UBIFS_LPT_FANOUT]; +}; + +/** + * struct ubifs_nbranch - LEB Properties Tree internal node branch. + * @lnum: LEB number of child + * @offs: offset of child + * @nnode: nnode child + * @pnode: pnode child + * @cnode: cnode child + */ +struct ubifs_nbranch +{ + int lnum; + int offs; + union + { + struct ubifs_nnode *nnode; + struct ubifs_pnode *pnode; + struct ubifs_cnode *cnode; + }; +}; + +/** + * struct ubifs_nnode - LEB Properties Tree internal node. + * @parent: parent nnode + * @cnext: next cnode to commit + * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE) + * @iip: index in parent + * @level: level in the tree (always greater than zero for nnodes) + * @num: node number + * @nbranch: branches to child nodes + */ +struct ubifs_nnode +{ + struct ubifs_nnode *parent; + struct ubifs_cnode *cnext; + unsigned long flags; + int iip; + int level; + int num; + struct ubifs_nbranch nbranch[UBIFS_LPT_FANOUT]; +}; + +/** + * struct ubifs_lp_stats - statistics of eraseblocks in the main area. + * @empty_lebs: number of empty LEBs + * @taken_empty_lebs: number of taken LEBs + * @idx_lebs: number of indexing LEBs + * @total_free: total free space in bytes + * @total_dirty: total dirty space in bytes + * @total_used: total used space in bytes (includes only data LEBs) + * @total_dead: total dead space in bytes (includes only data LEBs) + * @total_dark: total dark space in bytes (includes only data LEBs) + */ +struct ubifs_lp_stats { + int empty_lebs; + int taken_empty_lebs; + int idx_lebs; + long long total_free; + long long total_dirty; + long long total_used; + long long total_dead; + long long total_dark; +}; + +/** + * struct ubifs_zbranch - key/coordinate/length branch stored in znodes. + * @key: key + * @znode: znode address in memory + * @lnum: LEB number of the indexing node + * @offs: offset of the indexing node within @lnum + * @len: target node length + */ +struct ubifs_zbranch +{ + union ubifs_key key; + struct ubifs_znode *znode; + int lnum; + int offs; + int len; +}; + +/** + * struct ubifs_znode - in-memory representation of an indexing node. + * @parent: parent znode or NULL if it is the root + * @cnext: next znode to commit + * @flags: flags + * @time: last access time (seconds) + * @level: level of the entry in the TNC tree + * @child_cnt: count of child znodes + * @iip: index in parent's zbranch array + * @alt: lower bound of key range has altered i.e. child inserted at slot 0 + * @zbranch: array of znode branches (@c->fanout elements) + */ +struct ubifs_znode +{ + struct ubifs_znode *parent; + struct ubifs_znode *cnext; + unsigned long flags; + unsigned long time; + int level; + int child_cnt; + int iip; + int alt; +#ifdef CONFIG_UBIFS_FS_DEBUG + int lnum, offs, len; +#endif + struct ubifs_zbranch zbranch[]; +}; + +/** + * struct ubifs_info - UBIFS file-system description data structure + * (per-superblock). + * + * @highest_inum: highest used inode number + * @max_sqnum: current global sequence number + * + * @jhead_cnt: count of journal heads + * @max_bud_bytes: maximum number of bytes allowed in buds + * + * @zroot: zbranch which points to the root index node and znode + * @ihead_lnum: LEB number of index head + * @ihead_offs: offset of index head + * + * @log_lebs: number of logical eraseblocks in the log + * @lpt_lebs: number of LEBs used for lprops table + * @lpt_first: first LEB of the lprops table area + * @lpt_last: last LEB of the lprops table area + * @main_lebs: count of LEBs in the main area + * @main_first: first LEB of the main area + * @default_compr: default compression type + * @favor_lzo: favor LZO compression method + * @favor_percent: lzo vs. zlib threshold used in case favor LZO + * + * @key_hash_type: type of the key hash + * @key_hash: direntry key hash function + * @key_fmt: key format + * @key_len: key length + * @fanout: fanout of the index tree (number of links per indexing node) + * + * @min_io_size: minimal input/output unit size + * @leb_size: logical eraseblock size in bytes + * @leb_cnt: count of logical eraseblocks + * @max_leb_cnt: maximum count of logical eraseblocks + * + * @old_idx_sz: size of index on flash + * @lst: lprops statistics + * + * @dead_wm: LEB dead space watermark + * @dark_wm: LEB dark space watermark + * + * @di: UBI device information + * @vi: UBI volume information + * + * @gc_lnum: LEB number used for garbage collection + * @rp_size: reserved pool size + * + * @space_bits: number of bits needed to record free or dirty space + * @lpt_lnum_bits: number of bits needed to record a LEB number in the LPT + * @lpt_offs_bits: number of bits needed to record an offset in the LPT + * @lpt_spc_bits: number of bits needed to space in the LPT + * @pcnt_bits: number of bits needed to record pnode or nnode number + * @lnum_bits: number of bits needed to record LEB number + * @nnode_sz: size of on-flash nnode + * @pnode_sz: size of on-flash pnode + * @ltab_sz: size of on-flash LPT lprops table + * @lsave_sz: size of on-flash LPT save table + * @pnode_cnt: number of pnodes + * @nnode_cnt: number of nnodes + * @lpt_hght: height of the LPT + * + * @lpt_lnum: LEB number of the root nnode of the LPT + * @lpt_offs: offset of the root nnode of the LPT + * @nhead_lnum: LEB number of LPT head + * @nhead_offs: offset of LPT head + * @big_lpt: flag that LPT is too big to write whole during commit + * @space_fixup: flag indicating that free space in LEBs needs to be cleaned up + * @double_hash: flag indicating that we can do lookups by hash + * @lpt_sz: LPT size + * + * @ltab_lnum: LEB number of LPT's own lprops table + * @ltab_offs: offset of LPT's own lprops table + * @lpt: lprops table + * @ltab: LPT's own lprops table + * @lsave_cnt: number of LEB numbers in LPT's save table + * @lsave_lnum: LEB number of LPT's save table + * @lsave_offs: offset of LPT's save table + * @lsave: LPT's save table + * @lscan_lnum: LEB number of last LPT scan + * + * @hash_algo_name: the name of the hashing algorithm to use + * @hash_algo: The hash algo number (from include/linux/hash_info.h) + * @auth_key_filename: authentication key file name + * @x509_filename: x509 certificate file name for authentication + * @hash_len: the length of the hash + * @root_idx_hash: The hash of the root index node + * @lpt_hash: The hash of the LPT + * @mst_hash: The hash of the master node + */ +struct ubifs_info +{ + ino_t highest_inum; + unsigned long long max_sqnum; + + int jhead_cnt; + long long max_bud_bytes; + + struct ubifs_zbranch zroot; + int ihead_lnum; + int ihead_offs; + + int log_lebs; + int lpt_lebs; + int lpt_first; + int lpt_last; + int orph_lebs; + int main_lebs; + int main_first; + int default_compr; + int favor_lzo; + int favor_percent; + + uint8_t key_hash_type; + uint32_t (*key_hash)(const char *str, int len); + int key_fmt; + int key_len; + int fanout; + + int min_io_size; + int leb_size; + int leb_cnt; + int max_leb_cnt; + + unsigned long long old_idx_sz; + struct ubifs_lp_stats lst; + + int dead_wm; + int dark_wm; + + struct ubi_dev_info di; + struct ubi_vol_info vi; + + int gc_lnum; + long long rp_size; + + int space_bits; + int lpt_lnum_bits; + int lpt_offs_bits; + int lpt_spc_bits; + int pcnt_bits; + int lnum_bits; + int nnode_sz; + int pnode_sz; + int ltab_sz; + int lsave_sz; + int pnode_cnt; + int nnode_cnt; + int lpt_hght; + + int lpt_lnum; + int lpt_offs; + int nhead_lnum; + int nhead_offs; + int big_lpt; + int space_fixup; + int double_hash; + int encrypted; + long long lpt_sz; + + int ltab_lnum; + int ltab_offs; + struct ubifs_lprops *lpt; + struct ubifs_lpt_lprops *ltab; + int lsave_cnt; + int lsave_lnum; + int lsave_offs; + int *lsave; + int lscan_lnum; + + char *hash_algo_name; + int hash_algo; + char *auth_key_filename; + char *auth_cert_filename; + int hash_len; + uint8_t root_idx_hash[UBIFS_MAX_HASH_LEN]; + uint8_t lpt_hash[UBIFS_MAX_HASH_LEN]; + uint8_t mst_hash[UBIFS_MAX_HASH_LEN]; +}; + +/** + * ubifs_idx_node_sz - return index node size. + * @c: the UBIFS file-system description object + * @child_cnt: number of children of this index node + */ +static inline int ubifs_idx_node_sz(const struct ubifs_info *c, int child_cnt) +{ + return UBIFS_IDX_NODE_SZ + (UBIFS_BRANCH_SZ + c->key_len + c->hash_len) + * child_cnt; +} + +/** + * ubifs_idx_branch - return pointer to an index branch. + * @c: the UBIFS file-system description object + * @idx: index node + * @bnum: branch number + */ +static inline +struct ubifs_branch *ubifs_idx_branch(const struct ubifs_info *c, + const struct ubifs_idx_node *idx, + int bnum) +{ + return (struct ubifs_branch *)((void *)idx->branches + + (UBIFS_BRANCH_SZ + c->key_len + c->hash_len) * bnum); +} + +#endif /* __UBIFS_H__ */ diff --git a/ubifs-utils/mkfs.ubifs/README b/ubifs-utils/mkfs.ubifs/README deleted file mode 100644 index 7e19939..0000000 --- a/ubifs-utils/mkfs.ubifs/README +++ /dev/null @@ -1,9 +0,0 @@ -UBIFS File System - Make File System program - -* crc16.h and crc16.c were copied from the linux kernel. -* crc32.h and crc32.c were copied from mtd-utils and amended. -* ubifs.h is a selection of definitions from fs/ubifs/ubifs.h from the linux kernel. -* key.h is copied from fs/ubifs/key.h from the linux kernel. -* defs.h is a bunch of definitions to smooth things over. -* lpt.c is a selection of functions copied from fs/ubifs/lpt.c from the linux kernel, and amended. -* hashtable/* was downloaded from http://www.cl.cam.ac.uk/~cwc22/hashtable/ diff --git a/ubifs-utils/mkfs.ubifs/compr.c b/ubifs-utils/mkfs.ubifs/compr.c deleted file mode 100644 index e4324f3..0000000 --- a/ubifs-utils/mkfs.ubifs/compr.c +++ /dev/null @@ -1,284 +0,0 @@ -/* - * 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 -#include -#include -#include -#ifdef WITH_LZO -#include -#endif -#include -#ifdef WITH_ZSTD -#include -#endif - -#ifdef WITH_ZLIB -#define crc32 __zlib_crc32 -#include -#undef crc32 -#endif - -#include "compr.h" -#include "mkfs.ubifs.h" - -static void *lzo_mem; -static unsigned long long errcnt = 0; -#ifdef WITH_LZO -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 = MKFS_UBIFS_COMPR_LZO; - return 0; - -select_zlib: - *out_len = zlib_len; - *type = MKFS_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 MKFS_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 MKFS_UBIFS_COMPR_LZO: - ret = lzo_compress(in_buf, in_len, out_buf, out_len); - break; -#endif -#ifdef WITH_ZLIB - case MKFS_UBIFS_COMPR_ZLIB: - ret = zlib_deflate(in_buf, in_len, out_buf, out_len); - break; -#endif -#ifdef WITH_ZSTD - case MKFS_UBIFS_COMPR_ZSTD: - ret = zstd_compress(in_buf, in_len, out_buf, out_len); - break; -#endif - case MKFS_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 MKFS_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/mkfs.ubifs/compr.h b/ubifs-utils/mkfs.ubifs/compr.h deleted file mode 100644 index d58c7c7..0000000 --- a/ubifs-utils/mkfs.ubifs/compr.h +++ /dev/null @@ -1,47 +0,0 @@ -/* - * 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 - -enum compression_type -{ - MKFS_UBIFS_COMPR_NONE, - MKFS_UBIFS_COMPR_LZO, - MKFS_UBIFS_COMPR_ZLIB, - MKFS_UBIFS_COMPR_ZSTD, -}; - -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/mkfs.ubifs/crc16.c b/ubifs-utils/mkfs.ubifs/crc16.c deleted file mode 100644 index a19512e..0000000 --- a/ubifs-utils/mkfs.ubifs/crc16.c +++ /dev/null @@ -1,56 +0,0 @@ -/* - * 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/mkfs.ubifs/crc16.h b/ubifs-utils/mkfs.ubifs/crc16.h deleted file mode 100644 index 539d21a..0000000 --- a/ubifs-utils/mkfs.ubifs/crc16.h +++ /dev/null @@ -1,27 +0,0 @@ -/* - * Implements the standard CRC-16: - * Width 16 - * Poly 0x8005 (x^16 + x^15 + x^2 + 1) - * Init 0 - * - * Copyright (c) 2005 Ben Gardner - * - * This code was taken from the linux kernel. The license is GPL Version 2. - */ - -#ifndef __CRC16_H__ -#define __CRC16_H__ - -#include -#include - -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/mkfs.ubifs/crypto.c b/ubifs-utils/mkfs.ubifs/crypto.c deleted file mode 100644 index 19c445e..0000000 --- a/ubifs-utils/mkfs.ubifs/crypto.c +++ /dev/null @@ -1,368 +0,0 @@ -/* - * 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 - */ - -#define PROGRAM_NAME "mkfs.ubifs" -#include -#include -#include -#include - -#include "fscrypt.h" -#include "common.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/mkfs.ubifs/crypto.h b/ubifs-utils/mkfs.ubifs/crypto.h deleted file mode 100644 index b6ffad1..0000000 --- a/ubifs-utils/mkfs.ubifs/crypto.h +++ /dev/null @@ -1,58 +0,0 @@ -/* - * 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 - */ - -#ifndef UBIFS_CRYPTO_H -#define UBIFS_CRYPTO_H - -#include -#include -#include -#include - - -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/mkfs.ubifs/defs.h b/ubifs-utils/mkfs.ubifs/defs.h deleted file mode 100644 index 8db5277..0000000 --- a/ubifs-utils/mkfs.ubifs/defs.h +++ /dev/null @@ -1,90 +0,0 @@ -/* - * 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__ - -#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 unlikely(x) (x) - -struct qstr -{ - char *name; - size_t len; -}; - -/** - * 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; -} - -#define do_div(n,base) ({ \ -int __res; \ -__res = ((unsigned long) n) % (unsigned) base; \ -n = ((unsigned long) n) / (unsigned) base; \ -__res; }) - -#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/mkfs.ubifs/devtable.c b/ubifs-utils/mkfs.ubifs/devtable.c deleted file mode 100644 index aa815fb..0000000 --- a/ubifs-utils/mkfs.ubifs/devtable.c +++ /dev/null @@ -1,535 +0,0 @@ -/* - * 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 - */ - -/* - * This file implemented device table support. Device table entries take the - * form of: - * - * /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 "mkfs.ubifs.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 err_msg("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 err_msg("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_err_msg("sscanf failed"); - - dbg_msg(3, "name %s, type %c, mode %o, uid %u, gid %u, major %u, " - "minor %u, start %u, inc %u, cnt %u", - buf, type, mode, uid, gid, major, minor, start, - increment, count); - - len = strnlen(buf, 1024); - if (len == 0) - return err_msg("empty path"); - if (len == 1024) - return err_msg("too long path"); - - if (buf[0] != '/') - return err_msg("device table entries require absolute paths"); - if (strstr(buf, "//")) - return err_msg("'//' cannot be used in the path"); - if (len > 1 && buf[len - 1] == '/') - return err_msg("do not put '/' at the end"); - - if (strstr(buf, "/./") || strstr(buf, "/../") || - !strcmp(buf + len - 2, "/.") || !strcmp(buf + len - 3, "/..")) - return err_msg("'.' 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 err_msg("link permission must be 0777"); - break; - default: - return err_msg("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) { - dbg_msg(3, "inserting '%s' into path hash table", path); - ph_elt = malloc(sizeof(struct path_htbl_element)); - if (!ph_elt) { - err_msg("cannot allocate %zd bytes of memory", - sizeof(struct path_htbl_element)); - goto out_free; - } - - if (!hashtable_insert(path_htbl, path, ph_elt)) { - err_msg("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) { - err_msg("cannot create name hash table"); - goto out_free; - } - } - - if (increment != 0 && count == 0) { - err_msg("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) { - err_msg("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); - - dbg_msg(3, "inserting '%s' into name hash table (major %d, minor %d)", - name, major(nh_elt->dev), minor(nh_elt->dev)); - - if (hashtable_search(ph_elt->name_htbl, name)) { - err_msg("'%s' is referred twice", buf); - goto out_free; - } - - nh_elt->name = name; - if (!hashtable_insert(ph_elt->name_htbl, name, nh_elt)) { - err_msg("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) { - err_msg("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) { - err_msg("cannot allocate %d bytes of memory", len); - goto out_free; - } - - sprintf(nm, "%s%d", name, i); - nh_elt->name = nm; - - dbg_msg(3, "inserting '%s' into name hash table (major %d, minor %d)", - nm, major(nh_elt->dev), minor(nh_elt->dev)); - - if (hashtable_search(ph_elt->name_htbl, nm)) { - err_msg("'%s' is referred twice", buf); - free (nm); - goto out_free; - } - - if (!hashtable_insert(ph_elt->name_htbl, nm, nh_elt)) { - err_msg("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; - - dbg_msg(1, "parsing device table file '%s'", tbl_file); - - path_htbl = create_hashtable(128, &r5_hash, &is_equivalent); - if (!path_htbl) - return err_msg("cannot create path hash table"); - - f = fopen(tbl_file, "r"); - if (!f) - return sys_err_msg("cannot open '%s'", tbl_file); - - if (fstat(fileno(f), &st) < 0) { - sys_err_msg("cannot stat '%s'", tbl_file); - goto out_close; - } - - if (st.st_size < 10) { - sys_err_msg("'%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)) { - err_msg("cannot parse '%s'", line); - goto out_close; - } - } - - free(line); - line = NULL; - } - - dbg_msg(1, "finished parsing"); - fclose(f); - return 0; - -out_close: - fclose(f); - 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 err_msg("%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 err_msg("%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); - - dbg_msg(3, "set UID %d, GID %d, mode %o for %s/%s as device table says", - 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/mkfs.ubifs/fscrypt.c b/ubifs-utils/mkfs.ubifs/fscrypt.c deleted file mode 100644 index b75bdf7..0000000 --- a/ubifs-utils/mkfs.ubifs/fscrypt.c +++ /dev/null @@ -1,282 +0,0 @@ -/* - * 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 - * David Oberhollenzer - */ - -#define PROGRAM_NAME "mkfs.ubifs" -#include "fscrypt.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) { - err_msg("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, 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 err_msg("could not compute subkey"); - } - - ret = fscrypt_cipher->encrypt_fname(inbuf, cryptlen, - crypt_key, *outbuf); - if (ret < 0) { - free(inbuf); - free(*outbuf); - return err_msg("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 err_msg("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 err_msg("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]) { - err_msg("key descriptor '%s' is too short", desc); - return -1; - } - if (!isxdigit(desc[i * 2]) || !isxdigit(desc[i * 2 + 1])) { - err_msg("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]) { - err_msg("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) { - err_msg("loading key from '%s': file is empty", key_file); - goto fail; - } - if (keysize < fsc->key_length) { - err_msg("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/mkfs.ubifs/fscrypt.h b/ubifs-utils/mkfs.ubifs/fscrypt.h deleted file mode 100644 index ff3d326..0000000 --- a/ubifs-utils/mkfs.ubifs/fscrypt.h +++ /dev/null @@ -1,171 +0,0 @@ -/* - * 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 - * David Oberhollenzer - */ - -#ifndef FSCRYPT_H -#define FSCRYPT_H - - -#include "mkfs.ubifs.h" -#include -#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]; -} __attribute__((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]; -} __attribute__((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, 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, 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/mkfs.ubifs/hashtable/hashtable.c b/ubifs-utils/mkfs.ubifs/hashtable/hashtable.c deleted file mode 100644 index c1f99ed..0000000 --- a/ubifs-utils/mkfs.ubifs/hashtable/hashtable.c +++ /dev/null @@ -1,277 +0,0 @@ -/* Copyright (C) 2004 Christopher Clark */ - -#define PROGRAM_NAME "hashtable" - -#include "common.h" -#include "hashtable.h" -#include "hashtable_private.h" -#include -#include -#include -#include - -/* -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/mkfs.ubifs/hashtable/hashtable.h b/ubifs-utils/mkfs.ubifs/hashtable/hashtable.h deleted file mode 100644 index c0b0acd..0000000 --- a/ubifs-utils/mkfs.ubifs/hashtable/hashtable.h +++ /dev/null @@ -1,199 +0,0 @@ -/* Copyright (C) 2002 Christopher Clark */ - -#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/mkfs.ubifs/hashtable/hashtable_itr.c b/ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.c deleted file mode 100644 index d102453..0000000 --- a/ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.c +++ /dev/null @@ -1,176 +0,0 @@ -/* Copyright (C) 2002, 2004 Christopher Clark */ - -#include "hashtable.h" -#include "hashtable_private.h" -#include "hashtable_itr.h" -#include /* 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/mkfs.ubifs/hashtable/hashtable_itr.h b/ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.h deleted file mode 100644 index 5c94a04..0000000 --- a/ubifs-utils/mkfs.ubifs/hashtable/hashtable_itr.h +++ /dev/null @@ -1,112 +0,0 @@ -/* Copyright (C) 2002, 2004 Christopher Clark */ - -#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/mkfs.ubifs/hashtable/hashtable_private.h b/ubifs-utils/mkfs.ubifs/hashtable/hashtable_private.h deleted file mode 100644 index 3a558e6..0000000 --- a/ubifs-utils/mkfs.ubifs/hashtable/hashtable_private.h +++ /dev/null @@ -1,85 +0,0 @@ -/* Copyright (C) 2002, 2004 Christopher Clark */ - -#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/mkfs.ubifs/key.h b/ubifs-utils/mkfs.ubifs/key.h deleted file mode 100644 index 2de530b..0000000 --- a/ubifs-utils/mkfs.ubifs/key.h +++ /dev/null @@ -1,222 +0,0 @@ -/* - * This file is part of UBIFS. - * - * Copyright (C) 2006-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 - * - * Authors: Artem Bityutskiy (Битюцкий Артём) - * Adrian Hunter - */ - -/* - * This header contains various key-related definitions and helper function. - * UBIFS allows several key schemes, so we access key fields only via these - * helpers. At the moment only one key scheme is supported. - * - * Simple key scheme - * ~~~~~~~~~~~~~~~~~ - * - * Keys are 64-bits long. First 32-bits are inode number (parent inode number - * in case of direntry key). Next 3 bits are node type. The last 29 bits are - * 4KiB offset in case of inode node, and direntry hash in case of a direntry - * node. We use "r5" hash borrowed from reiserfs. - */ - -#ifndef __UBIFS_KEY_H__ -#define __UBIFS_KEY_H__ - -#include - -/** - * key_mask_hash - mask a valid hash value. - * @val: value to be masked - * - * We use hash values as offset in directories, so values %0 and %1 are - * reserved for "." and "..". %2 is reserved for "end of readdir" marker. This - * function makes sure the reserved values are not used. - */ -static inline uint32_t key_mask_hash(uint32_t hash) -{ - hash &= UBIFS_S_KEY_HASH_MASK; - if (unlikely(hash <= 2)) - hash += 3; - return hash; -} - -/** - * key_r5_hash - R5 hash function (borrowed from reiserfs). - * @s: direntry name - * @len: name length - */ -static inline uint32_t key_r5_hash(const char *s, int len) -{ - uint32_t a = 0; - const signed char *str = (const signed char *)s; - - while (len--) { - a += *str << 4; - a += *str >> 4; - a *= 11; - str++; - } - - return key_mask_hash(a); -} - -/** - * key_test_hash - testing hash function. - * @str: direntry name - * @len: name length - */ -static inline uint32_t key_test_hash(const char *str, int len) -{ - uint32_t a = 0; - - len = min_t(uint32_t, len, 4); - memcpy(&a, str, len); - return key_mask_hash(a); -} - -/** - * ino_key_init - initialize inode key. - * @c: UBIFS file-system description object - * @key: key to initialize - * @inum: inode number - */ -static inline void ino_key_init(union ubifs_key *key, ino_t inum) -{ - key->u32[0] = inum; - key->u32[1] = UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS; -} - -/** - * dent_key_init - initialize directory entry key. - * @c: UBIFS file-system description object - * @key: key to initialize - * @inum: parent inode number - * @nm: direntry name and length - */ -static inline void dent_key_init(const struct ubifs_info *c, - union ubifs_key *key, ino_t inum, - const void *name, int name_len) -{ - uint32_t hash = c->key_hash(name, name_len); - - assert(!(hash & ~UBIFS_S_KEY_HASH_MASK)); - key->u32[0] = inum; - key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS); -} - -/** - * xent_key_init - initialize extended attribute entry key. - * @c: UBIFS file-system description object - * @key: key to initialize - * @inum: host inode number - * @nm: extended attribute entry name and length - */ -static inline void xent_key_init(const struct ubifs_info *c, - union ubifs_key *key, ino_t inum, - const struct qstr *nm) -{ - uint32_t hash = c->key_hash(nm->name, nm->len); - - assert(!(hash & ~UBIFS_S_KEY_HASH_MASK)); - key->u32[0] = inum; - key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS); -} - -/** - * data_key_init - initialize data key. - * @c: UBIFS file-system description object - * @key: key to initialize - * @inum: inode number - * @block: block number - */ -static inline void data_key_init(union ubifs_key *key, ino_t inum, - unsigned int block) -{ - assert(!(block & ~UBIFS_S_KEY_BLOCK_MASK)); - key->u32[0] = inum; - key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS); -} - -/** - * key_write - transform a key from in-memory format. - * @c: UBIFS file-system description object - * @from: the key to transform - * @to: the key to store the result - */ -static inline void key_write(const union ubifs_key *from, void *to) -{ - __le32 x[2]; - - x[0] = cpu_to_le32(from->u32[0]); - x[1] = cpu_to_le32(from->u32[1]); - - memcpy(to, &x, 8); - memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8); -} - -/** - * key_write_idx - transform a key from in-memory format for the index. - * @c: UBIFS file-system description object - * @from: the key to transform - * @to: the key to store the result - */ -static inline void key_write_idx(const union ubifs_key *from, void *to) -{ - __le32 x[2]; - - x[0] = cpu_to_le32(from->u32[0]); - x[1] = cpu_to_le32(from->u32[1]); - - memcpy(to, &x, 8); -} - -/** - * keys_cmp - compare keys. - * @c: UBIFS file-system description object - * @key1: the first key to compare - * @key2: the second key to compare - * - * This function compares 2 keys and returns %-1 if @key1 is less than - * @key2, 0 if the keys are equivalent and %1 if @key1 is greater than @key2. - */ -static inline int keys_cmp(const union ubifs_key *key1, - const union ubifs_key *key2) -{ - if (key1->u32[0] < key2->u32[0]) - return -1; - if (key1->u32[0] > key2->u32[0]) - return 1; - if (key1->u32[1] < key2->u32[1]) - return -1; - if (key1->u32[1] > key2->u32[1]) - return 1; - - return 0; -} - -/** - * key_type - get key type. - * @c: UBIFS file-system description object - * @key: key to get type of - */ -static inline int key_type(const union ubifs_key *key) -{ - return key->u32[1] >> UBIFS_S_KEY_BLOCK_BITS; -} - -#endif /* !__UBIFS_KEY_H__ */ diff --git a/ubifs-utils/mkfs.ubifs/lpt.c b/ubifs-utils/mkfs.ubifs/lpt.c deleted file mode 100644 index 7ee739a..0000000 --- a/ubifs-utils/mkfs.ubifs/lpt.c +++ /dev/null @@ -1,590 +0,0 @@ -/* - * This file is part of UBIFS. - * - * Copyright (C) 2006, 2007 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 - * - * Authors: Adrian Hunter - * Artem Bityutskiy - */ - -#include "mkfs.ubifs.h" - -#ifdef WITH_CRYPTO -#include -#endif - -/** - * do_calc_lpt_geom - calculate sizes for the LPT area. - * @c: the UBIFS file-system description object - * - * Calculate the sizes of LPT bit fields, nodes, and tree, based on the - * properties of the flash and whether LPT is "big" (c->big_lpt). - */ -static void do_calc_lpt_geom(struct ubifs_info *c) -{ - int n, bits, per_leb_wastage; - long long sz, tot_wastage; - - c->pnode_cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - - n = (c->pnode_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - c->nnode_cnt = n; - while (n > 1) { - n = (n + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - c->nnode_cnt += n; - } - - c->lpt_hght = 1; - n = UBIFS_LPT_FANOUT; - while (n < c->pnode_cnt) { - c->lpt_hght += 1; - n <<= UBIFS_LPT_FANOUT_SHIFT; - } - - c->space_bits = fls(c->leb_size) - 3; - c->lpt_lnum_bits = fls(c->lpt_lebs); - c->lpt_offs_bits = fls(c->leb_size - 1); - c->lpt_spc_bits = fls(c->leb_size); - - n = (c->max_leb_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - c->pcnt_bits = fls(n - 1); - - c->lnum_bits = fls(c->max_leb_cnt - 1); - - bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + - (c->big_lpt ? c->pcnt_bits : 0) + - (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT; - c->pnode_sz = (bits + 7) / 8; - - bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + - (c->big_lpt ? c->pcnt_bits : 0) + - (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT; - c->nnode_sz = (bits + 7) / 8; - - bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + - c->lpt_lebs * c->lpt_spc_bits * 2; - c->ltab_sz = (bits + 7) / 8; - - bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + - c->lnum_bits * c->lsave_cnt; - c->lsave_sz = (bits + 7) / 8; - - /* Calculate the minimum LPT size */ - c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz; - c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz; - c->lpt_sz += c->ltab_sz; - c->lpt_sz += c->lsave_sz; - - /* Add wastage */ - sz = c->lpt_sz; - per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz); - sz += per_leb_wastage; - tot_wastage = per_leb_wastage; - while (sz > c->leb_size) { - sz += per_leb_wastage; - sz -= c->leb_size; - tot_wastage += per_leb_wastage; - } - tot_wastage += ALIGN(sz, c->min_io_size) - sz; - c->lpt_sz += tot_wastage; -} - -/** - * calc_dflt_lpt_geom - calculate default LPT geometry. - * @c: the UBIFS file-system description object - * @main_lebs: number of main area LEBs is passed and returned here - * @big_lpt: whether the LPT area is "big" is returned here - * - * The size of the LPT area depends on parameters that themselves are dependent - * on the size of the LPT area. This function, successively recalculates the LPT - * area geometry until the parameters and resultant geometry are consistent. - * - * This function returns %0 on success and a negative error code on failure. - */ -int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt) -{ - int i, lebs_needed; - long long sz; - - /* Start by assuming the minimum number of LPT LEBs */ - c->lpt_lebs = UBIFS_MIN_LPT_LEBS; - c->main_lebs = *main_lebs - c->lpt_lebs; - if (c->main_lebs <= 0) - return -EINVAL; - - /* And assume we will use the small LPT model */ - c->big_lpt = 0; - - /* - * Calculate the geometry based on assumptions above and then see if it - * makes sense - */ - do_calc_lpt_geom(c); - - /* Small LPT model must have lpt_sz < leb_size */ - if (c->lpt_sz > c->leb_size) { - /* Nope, so try again using big LPT model */ - c->big_lpt = 1; - do_calc_lpt_geom(c); - } - - /* Now check there are enough LPT LEBs */ - for (i = 0; i < 64 ; i++) { - sz = c->lpt_sz * 4; /* Allow 4 times the size */ - sz += c->leb_size - 1; - do_div(sz, c->leb_size); - lebs_needed = sz; - if (lebs_needed > c->lpt_lebs) { - /* Not enough LPT LEBs so try again with more */ - c->lpt_lebs = lebs_needed; - c->main_lebs = *main_lebs - c->lpt_lebs; - if (c->main_lebs <= 0) - return -EINVAL; - do_calc_lpt_geom(c); - continue; - } - if (c->ltab_sz > c->leb_size) { - err_msg("LPT ltab too big"); - return -EINVAL; - } - *main_lebs = c->main_lebs; - *big_lpt = c->big_lpt; - return 0; - } - return -EINVAL; -} - -/** - * pack_bits - pack bit fields end-to-end. - * @addr: address at which to pack (passed and next address returned) - * @pos: bit position at which to pack (passed and next position returned) - * @val: value to pack - * @nrbits: number of bits of value to pack (1-32) - */ -static void pack_bits(uint8_t **addr, int *pos, uint32_t val, int nrbits) -{ - uint8_t *p = *addr; - int b = *pos; - - if (b) { - *p |= ((uint8_t)val) << b; - nrbits += b; - if (nrbits > 8) { - *++p = (uint8_t)(val >>= (8 - b)); - if (nrbits > 16) { - *++p = (uint8_t)(val >>= 8); - if (nrbits > 24) { - *++p = (uint8_t)(val >>= 8); - if (nrbits > 32) - *++p = (uint8_t)(val >>= 8); - } - } - } - } else { - *p = (uint8_t)val; - if (nrbits > 8) { - *++p = (uint8_t)(val >>= 8); - if (nrbits > 16) { - *++p = (uint8_t)(val >>= 8); - if (nrbits > 24) - *++p = (uint8_t)(val >>= 8); - } - } - } - b = nrbits & 7; - if (b == 0) - p++; - *addr = p; - *pos = b; -} - -/** - * pack_pnode - pack all the bit fields of a pnode. - * @c: UBIFS file-system description object - * @buf: buffer into which to pack - * @pnode: pnode to pack - */ -static void pack_pnode(struct ubifs_info *c, void *buf, - struct ubifs_pnode *pnode) -{ - uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; - int i, pos = 0; - uint16_t crc; - - pack_bits(&addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS); - if (c->big_lpt) - pack_bits(&addr, &pos, pnode->num, c->pcnt_bits); - for (i = 0; i < UBIFS_LPT_FANOUT; i++) { - pack_bits(&addr, &pos, pnode->lprops[i].free >> 3, - c->space_bits); - pack_bits(&addr, &pos, pnode->lprops[i].dirty >> 3, - c->space_bits); - if (pnode->lprops[i].flags & LPROPS_INDEX) - pack_bits(&addr, &pos, 1, 1); - else - pack_bits(&addr, &pos, 0, 1); - } - crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, - c->pnode_sz - UBIFS_LPT_CRC_BYTES); - addr = buf; - pos = 0; - pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); -} - -/** - * pack_nnode - pack all the bit fields of a nnode. - * @c: UBIFS file-system description object - * @buf: buffer into which to pack - * @nnode: nnode to pack - */ -static void pack_nnode(struct ubifs_info *c, void *buf, - struct ubifs_nnode *nnode) -{ - uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; - int i, pos = 0; - uint16_t crc; - - pack_bits(&addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS); - if (c->big_lpt) - pack_bits(&addr, &pos, nnode->num, c->pcnt_bits); - for (i = 0; i < UBIFS_LPT_FANOUT; i++) { - int lnum = nnode->nbranch[i].lnum; - - if (lnum == 0) - lnum = c->lpt_last + 1; - pack_bits(&addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits); - pack_bits(&addr, &pos, nnode->nbranch[i].offs, - c->lpt_offs_bits); - } - crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, - c->nnode_sz - UBIFS_LPT_CRC_BYTES); - addr = buf; - pos = 0; - pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); -} - -/** - * pack_ltab - pack the LPT's own lprops table. - * @c: UBIFS file-system description object - * @buf: buffer into which to pack - * @ltab: LPT's own lprops table to pack - */ -static void pack_ltab(struct ubifs_info *c, void *buf, - struct ubifs_lpt_lprops *ltab) -{ - uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; - int i, pos = 0; - uint16_t crc; - - pack_bits(&addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS); - for (i = 0; i < c->lpt_lebs; i++) { - pack_bits(&addr, &pos, ltab[i].free, c->lpt_spc_bits); - pack_bits(&addr, &pos, ltab[i].dirty, c->lpt_spc_bits); - } - crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, - c->ltab_sz - UBIFS_LPT_CRC_BYTES); - addr = buf; - pos = 0; - pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); -} - -/** - * pack_lsave - pack the LPT's save table. - * @c: UBIFS file-system description object - * @buf: buffer into which to pack - * @lsave: LPT's save table to pack - */ -static void pack_lsave(struct ubifs_info *c, void *buf, int *lsave) -{ - uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; - int i, pos = 0; - uint16_t crc; - - pack_bits(&addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS); - for (i = 0; i < c->lsave_cnt; i++) - pack_bits(&addr, &pos, lsave[i], c->lnum_bits); - crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, - c->lsave_sz - UBIFS_LPT_CRC_BYTES); - addr = buf; - pos = 0; - pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); -} - -/** - * set_ltab - set LPT LEB properties. - * @c: UBIFS file-system description object - * @lnum: LEB number - * @free: amount of free space - * @dirty: amount of dirty space - */ -static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty) -{ - dbg_msg(3, "LEB %d free %d dirty %d to %d %d", - lnum, c->ltab[lnum - c->lpt_first].free, - c->ltab[lnum - c->lpt_first].dirty, free, dirty); - c->ltab[lnum - c->lpt_first].free = free; - c->ltab[lnum - c->lpt_first].dirty = dirty; -} - -/** - * calc_nnode_num - calculate nnode number. - * @row: the row in the tree (root is zero) - * @col: the column in the row (leftmost is zero) - * - * The nnode number is a number that uniquely identifies a nnode and can be used - * easily to traverse the tree from the root to that nnode. - * - * This function calculates and returns the nnode number for the nnode at @row - * and @col. - */ -static int calc_nnode_num(int row, int col) -{ - int num, bits; - - num = 1; - while (row--) { - bits = (col & (UBIFS_LPT_FANOUT - 1)); - col >>= UBIFS_LPT_FANOUT_SHIFT; - num <<= UBIFS_LPT_FANOUT_SHIFT; - num |= bits; - } - return num; -} - -/** - * create_lpt - create LPT. - * @c: UBIFS file-system description object - * - * This function returns %0 on success and a negative error code on failure. - */ -int create_lpt(struct ubifs_info *c) -{ - int lnum, err = 0, i, j, cnt, len, alen, row; - int blnum, boffs, bsz, bcnt; - struct ubifs_pnode *pnode = NULL; - struct ubifs_nnode *nnode = NULL; - void *buf = NULL, *p; - int *lsave = NULL; - unsigned int md_len; - - pnode = malloc(sizeof(struct ubifs_pnode)); - nnode = malloc(sizeof(struct ubifs_nnode)); - buf = malloc(c->leb_size); - lsave = malloc(sizeof(int) * c->lsave_cnt); - if (!pnode || !nnode || !buf || !lsave) { - err = -ENOMEM; - goto out; - } - memset(pnode, 0 , sizeof(struct ubifs_pnode)); - memset(nnode, 0 , sizeof(struct ubifs_nnode)); - - hash_digest_init(); - - c->lscan_lnum = c->main_first; - - lnum = c->lpt_first; - p = buf; - len = 0; - /* Number of leaf nodes (pnodes) */ - cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) >> UBIFS_LPT_FANOUT_SHIFT; - //printf("pnode_cnt=%d\n",cnt); - - /* - * To calculate the internal node branches, we keep information about - * the level below. - */ - blnum = lnum; /* LEB number of level below */ - boffs = 0; /* Offset of level below */ - bcnt = cnt; /* Number of nodes in level below */ - bsz = c->pnode_sz; /* Size of nodes in level below */ - - /* Add pnodes */ - for (i = 0; i < cnt; i++) { - if (len + c->pnode_sz > c->leb_size) { - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, alen - len); - memset(p, 0xff, alen - len); - err = write_leb(lnum++, alen, buf); - if (err) - goto out; - p = buf; - len = 0; - } - /* Fill in the pnode */ - for (j = 0; j < UBIFS_LPT_FANOUT; j++) { - int k = (i << UBIFS_LPT_FANOUT_SHIFT) + j; - - if (k < c->main_lebs) - pnode->lprops[j] = c->lpt[k]; - else { - pnode->lprops[j].free = c->leb_size; - pnode->lprops[j].dirty = 0; - pnode->lprops[j].flags = 0; - } - } - pack_pnode(c, p, pnode); - - hash_digest_update(p, c->pnode_sz); - - p += c->pnode_sz; - len += c->pnode_sz; - /* - * pnodes are simply numbered left to right starting at zero, - * which means the pnode number can be used easily to traverse - * down the tree to the corresponding pnode. - */ - pnode->num += 1; - } - - hash_digest_final(c->lpt_hash, &md_len); - - row = c->lpt_hght - 1; - /* Add all nnodes, one level at a time */ - while (1) { - /* Number of internal nodes (nnodes) at next level */ - cnt = (cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - if (cnt == 0) - cnt = 1; - for (i = 0; i < cnt; i++) { - if (len + c->nnode_sz > c->leb_size) { - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, - alen - len); - memset(p, 0xff, alen - len); - err = write_leb(lnum++, alen, buf); - if (err) - goto out; - p = buf; - len = 0; - } - /* The root is on row zero */ - if (row == 0) { - c->lpt_lnum = lnum; - c->lpt_offs = len; - } - /* Set branches to the level below */ - for (j = 0; j < UBIFS_LPT_FANOUT; j++) { - if (bcnt) { - if (boffs + bsz > c->leb_size) { - blnum += 1; - boffs = 0; - } - nnode->nbranch[j].lnum = blnum; - nnode->nbranch[j].offs = boffs; - boffs += bsz; - bcnt--; - } else { - nnode->nbranch[j].lnum = 0; - nnode->nbranch[j].offs = 0; - } - } - nnode->num = calc_nnode_num(row, i); - pack_nnode(c, p, nnode); - p += c->nnode_sz; - len += c->nnode_sz; - } - /* Row zero is the top row */ - if (row == 0) - break; - /* Update the information about the level below */ - bcnt = cnt; - bsz = c->nnode_sz; - row -= 1; - } - - if (c->big_lpt) { - /* Need to add LPT's save table */ - if (len + c->lsave_sz > c->leb_size) { - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, alen - len); - memset(p, 0xff, alen - len); - err = write_leb(lnum++, alen, buf); - if (err) - goto out; - p = buf; - len = 0; - } - - c->lsave_lnum = lnum; - c->lsave_offs = len; - - for (i = 0; i < c->lsave_cnt; i++) - lsave[i] = c->main_first + i; - - pack_lsave(c, p, lsave); - p += c->lsave_sz; - len += c->lsave_sz; - } - - /* Need to add LPT's own LEB properties table */ - if (len + c->ltab_sz > c->leb_size) { - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, alen - len); - memset(p, 0xff, alen - len); - err = write_leb(lnum++, alen, buf); - if (err) - goto out; - p = buf; - len = 0; - } - - c->ltab_lnum = lnum; - c->ltab_offs = len; - - /* Update ltab before packing it */ - len += c->ltab_sz; - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, alen - len); - - pack_ltab(c, p, c->ltab); - p += c->ltab_sz; - - /* Write remaining buffer */ - memset(p, 0xff, alen - len); - err = write_leb(lnum, alen, buf); - if (err) - goto out; - - c->nhead_lnum = lnum; - c->nhead_offs = ALIGN(len, c->min_io_size); - - dbg_msg(1, "lpt_sz: %lld", c->lpt_sz); - dbg_msg(1, "space_bits: %d", c->space_bits); - dbg_msg(1, "lpt_lnum_bits: %d", c->lpt_lnum_bits); - dbg_msg(1, "lpt_offs_bits: %d", c->lpt_offs_bits); - dbg_msg(1, "lpt_spc_bits: %d", c->lpt_spc_bits); - dbg_msg(1, "pcnt_bits: %d", c->pcnt_bits); - dbg_msg(1, "lnum_bits: %d", c->lnum_bits); - dbg_msg(1, "pnode_sz: %d", c->pnode_sz); - dbg_msg(1, "nnode_sz: %d", c->nnode_sz); - dbg_msg(1, "ltab_sz: %d", c->ltab_sz); - dbg_msg(1, "lsave_sz: %d", c->lsave_sz); - dbg_msg(1, "lsave_cnt: %d", c->lsave_cnt); - dbg_msg(1, "lpt_hght: %d", c->lpt_hght); - dbg_msg(1, "big_lpt: %d", c->big_lpt); - dbg_msg(1, "LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs); - dbg_msg(1, "LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs); - dbg_msg(1, "LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs); - if (c->big_lpt) - dbg_msg(1, "LPT lsave is at %d:%d", - c->lsave_lnum, c->lsave_offs); -out: - free(lsave); - free(buf); - free(nnode); - free(pnode); - return err; -} diff --git a/ubifs-utils/mkfs.ubifs/lpt.h b/ubifs-utils/mkfs.ubifs/lpt.h deleted file mode 100644 index 4cde59d..0000000 --- a/ubifs-utils/mkfs.ubifs/lpt.h +++ /dev/null @@ -1,28 +0,0 @@ -/* - * 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 - */ - -#ifndef __UBIFS_LPT_H__ -#define __UBIFS_LPT_H__ - -int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt); -int create_lpt(struct ubifs_info *c); - -#endif diff --git a/ubifs-utils/mkfs.ubifs/sign.c b/ubifs-utils/mkfs.ubifs/sign.c deleted file mode 100644 index 7f284f8..0000000 --- a/ubifs-utils/mkfs.ubifs/sign.c +++ /dev/null @@ -1,410 +0,0 @@ -/* - * 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 "mkfs.ubifs.h" -#include "common.h" - -#include -#include -#include -#include -#include -#include -#include -#include -#include - -static struct ubifs_info *c = &info_; - -EVP_MD_CTX *hash_md; -const EVP_MD *md; - -int authenticated(void) -{ - return c->hash_algo_name != NULL; -} - -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 - -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__); \ - err_msg(fmt, ## __VA_ARGS__); \ - -1; \ -}) - -static const char *key_pass; - -static int pem_pw_cb(char *buf, int len, __attribute__((unused)) int w, - __attribute__((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)) - err_msg("%s: Read wanted retry", x509_name); - if (n >= 0) - err_msg("%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 sign_superblock_node(void *node) -{ - EVP_PKEY *private_key; - CMS_ContentInfo *cms = NULL; - X509 *cert = NULL; - BIO *bd, *bm; - void *obuf; - long len; - int ret; - void *pret; - struct ubifs_sig_node *sig = node + UBIFS_SB_NODE_SZ; - - if (!authenticated()) - return 0; - - ERR_load_crypto_strings(); - ERR_clear_error(); - - key_pass = getenv("MKFS_UBIFS_SIGN_PIN"); - - bm = BIO_new_mem_buf(node, UBIFS_SB_NODE_SZ); - - private_key = read_private_key(c->auth_key_filename, &cert); - if (!private_key) - return -1; - - if (!cert) { - if (!c->auth_cert_filename) - return err_msg("authentication certificate not provided (--auth-cert)"); - cert = read_x509(c->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 err_msg("CMS_sign failed"); - - pret = CMS_add1_signer(cms, cert, private_key, md, - CMS_NOCERTS | CMS_BINARY | - CMS_NOSMIMECAP | CMS_NOATTR); - if (!pret) - return err_msg("CMS_add1_signer failed"); - - ret = CMS_final(cms, bm, NULL, CMS_NOCERTS | CMS_BINARY); - if (!ret) - return err_msg("CMS_final failed"); - - bd = BIO_new(BIO_s_mem()); - - ret = i2d_CMS_bio_stream(bd, cms, NULL, 0); - if (!ret) - return err_msg("i2d_CMS_bio_stream failed"); - - len = BIO_get_mem_data(bd, &obuf); - - sig->type = UBIFS_SIGNATURE_TYPE_PKCS7; - sig->len = cpu_to_le32(len); - sig->ch.node_type = UBIFS_SIG_NODE; - - memcpy(sig + 1, obuf, len); - - BIO_free(bd); - BIO_free(bm); - - return 0; -} - -/** - * ubifs_node_calc_hash - calculate the hash of a UBIFS node - * @c: UBIFS file-system description object - * @node: the node to calculate a hash for - * @hash: the returned hash - */ -void ubifs_node_calc_hash(const void *node, uint8_t *hash) -{ - const struct ubifs_ch *ch = node; - unsigned int md_len; - - if (!authenticated()) - return; - - EVP_DigestInit_ex(hash_md, md, NULL); - EVP_DigestUpdate(hash_md, node, le32_to_cpu(ch->len)); - EVP_DigestFinal_ex(hash_md, hash, &md_len); -} - -/** - * mst_node_calc_hash - calculate the hash of a UBIFS master node - * @c: UBIFS file-system description object - * @node: the node to calculate a hash for - * @hash: the returned hash - */ -void mst_node_calc_hash(const void *node, uint8_t *hash) -{ - unsigned int md_len; - - if (!authenticated()) - return; - - EVP_DigestInit_ex(hash_md, md, NULL); - EVP_DigestUpdate(hash_md, node + sizeof(struct ubifs_ch), - UBIFS_MST_NODE_SZ - sizeof(struct ubifs_ch)); - EVP_DigestFinal_ex(hash_md, hash, &md_len); -} - -void hash_digest_init(void) -{ - if (!authenticated()) - return; - - EVP_DigestInit_ex(hash_md, md, NULL); -} - -void hash_digest_update(const void *buf, int len) -{ - if (!authenticated()) - return; - - EVP_DigestUpdate(hash_md, buf, len); -} - -void hash_digest_final(void *hash, unsigned int *len) -{ - if (!authenticated()) - return; - - EVP_DigestFinal_ex(hash_md, hash, len); -} - -int init_authentication(void) -{ - int hash_algo; - - if (!c->auth_key_filename && !c->auth_cert_filename && !c->hash_algo_name) - return 0; - - if (!c->auth_key_filename) - return err_msg("authentication key not given (--auth-key)"); - - if (!c->hash_algo_name) - return err_msg("Hash algorithm not given (--hash-algo)"); - - OPENSSL_config(NULL); - - OpenSSL_add_all_algorithms(); - ERR_load_crypto_strings(); - - md = EVP_get_digestbyname(c->hash_algo_name); - if (!md) - return err_msg("Unknown message digest %s", c->hash_algo_name); - - hash_md = EVP_MD_CTX_create(); - c->hash_len = EVP_MD_size(md); - - hash_algo = match_string(hash_algo_name, HASH_ALGO__LAST, c->hash_algo_name); - if (hash_algo < 0) - return err_msg("Unsupported message digest %s", c->hash_algo_name); - - c->hash_algo = hash_algo; - - return 0; -} diff --git a/ubifs-utils/mkfs.ubifs/sign.h b/ubifs-utils/mkfs.ubifs/sign.h deleted file mode 100644 index fe9fdd8..0000000 --- a/ubifs-utils/mkfs.ubifs/sign.h +++ /dev/null @@ -1,80 +0,0 @@ -/* - * 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__ - -#ifdef WITH_CRYPTO -#include - -void ubifs_node_calc_hash(const void *node, uint8_t *hash); -void mst_node_calc_hash(const void *node, uint8_t *hash); -void hash_digest_init(void); -void hash_digest_update(const void *buf, int len); -void hash_digest_final(void *hash, unsigned int *len); -int init_authentication(void); -int sign_superblock_node(void *node); -int authenticated(void); - -extern EVP_MD_CTX *hash_md; -extern const EVP_MD *md; - -#else -static inline void ubifs_node_calc_hash(__attribute__((unused)) const void *node, - __attribute__((unused)) uint8_t *hash) -{ -} - -static inline void mst_node_calc_hash(__attribute__((unused)) const void *node, - __attribute__((unused)) uint8_t *hash) -{ -} - -static inline void hash_digest_init(void) -{ -} - -static inline void hash_digest_update(__attribute__((unused)) const void *buf, - __attribute__((unused)) int len) -{ -} - -static inline void hash_digest_final(__attribute__((unused)) void *hash, - __attribute__((unused)) unsigned int *len) -{ -} - -static inline int init_authentication(void) -{ - return 0; -} - -static inline int sign_superblock_node(__attribute__((unused)) void *node) -{ - return 0; -} - -static inline int authenticated(void) -{ - return 0; -} - -#endif - -#endif /* __UBIFS_SIGN_H__ */ diff --git a/ubifs-utils/mkfs.ubifs/ubifs.h b/ubifs-utils/mkfs.ubifs/ubifs.h deleted file mode 100644 index 55937ce..0000000 --- a/ubifs-utils/mkfs.ubifs/ubifs.h +++ /dev/null @@ -1,471 +0,0 @@ -/* - * This file is part of UBIFS. - * - * 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_H__ -#define __UBIFS_H__ - -/* Maximum logical eraseblock size in bytes */ -#define UBIFS_MAX_LEB_SZ (2*1024*1024) - -/* Minimum amount of data UBIFS writes to the flash */ -#define MIN_WRITE_SZ (UBIFS_DATA_NODE_SZ + 8) - -/* Largest key size supported in this implementation */ -#define CUR_MAX_KEY_LEN UBIFS_SK_LEN - -/* - * There is no notion of truncation key because truncation nodes do not exist - * in TNC. However, when replaying, it is handy to introduce fake "truncation" - * keys for truncation nodes because the code becomes simpler. So we define - * %UBIFS_TRUN_KEY type. - */ -#define UBIFS_TRUN_KEY UBIFS_KEY_TYPES_CNT - -/* - * How much a directory entry/extended attribute entry adds to the parent/host - * inode. - */ -#define CALC_DENT_SIZE(name_len) ALIGN(UBIFS_DENT_NODE_SZ + (name_len) + 1, 8) - -/* How much an extended attribute adds to the host inode */ -#define CALC_XATTR_BYTES(data_len) ALIGN(UBIFS_INO_NODE_SZ + (data_len) + 1, 8) - -/* The below union makes it easier to deal with keys */ -union ubifs_key -{ - uint8_t u8[CUR_MAX_KEY_LEN]; - uint32_t u32[CUR_MAX_KEY_LEN/4]; - uint64_t u64[CUR_MAX_KEY_LEN/8]; - __le32 j32[CUR_MAX_KEY_LEN/4]; -}; - -/* - * LEB properties flags. - * - * LPROPS_UNCAT: not categorized - * LPROPS_DIRTY: dirty > 0, not index - * LPROPS_DIRTY_IDX: dirty + free > UBIFS_CH_SZ and index - * LPROPS_FREE: free > 0, not empty, not index - * LPROPS_HEAP_CNT: number of heaps used for storing categorized LEBs - * LPROPS_EMPTY: LEB is empty, not taken - * LPROPS_FREEABLE: free + dirty == leb_size, not index, not taken - * LPROPS_FRDI_IDX: free + dirty == leb_size and index, may be taken - * LPROPS_CAT_MASK: mask for the LEB categories above - * LPROPS_TAKEN: LEB was taken (this flag is not saved on the media) - * LPROPS_INDEX: LEB contains indexing nodes (this flag also exists on flash) - */ -enum { - LPROPS_UNCAT = 0, - LPROPS_DIRTY = 1, - LPROPS_DIRTY_IDX = 2, - LPROPS_FREE = 3, - LPROPS_HEAP_CNT = 3, - LPROPS_EMPTY = 4, - LPROPS_FREEABLE = 5, - LPROPS_FRDI_IDX = 6, - LPROPS_CAT_MASK = 15, - LPROPS_TAKEN = 16, - LPROPS_INDEX = 32, -}; - -/** - * struct ubifs_lprops - logical eraseblock properties. - * @free: amount of free space in bytes - * @dirty: amount of dirty space in bytes - * @flags: LEB properties flags (see above) - */ -struct ubifs_lprops -{ - int free; - int dirty; - int flags; -}; - -/** - * struct ubifs_lpt_lprops - LPT logical eraseblock properties. - * @free: amount of free space in bytes - * @dirty: amount of dirty space in bytes - */ -struct ubifs_lpt_lprops -{ - int free; - int dirty; -}; - -struct ubifs_nnode; - -/** - * struct ubifs_cnode - LEB Properties Tree common node. - * @parent: parent nnode - * @cnext: next cnode to commit - * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE) - * @iip: index in parent - * @level: level in the tree (zero for pnodes, greater than zero for nnodes) - * @num: node number - */ -struct ubifs_cnode -{ - struct ubifs_nnode *parent; - struct ubifs_cnode *cnext; - unsigned long flags; - int iip; - int level; - int num; -}; - -/** - * struct ubifs_pnode - LEB Properties Tree leaf node. - * @parent: parent nnode - * @cnext: next cnode to commit - * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE) - * @iip: index in parent - * @level: level in the tree (always zero for pnodes) - * @num: node number - * @lprops: LEB properties array - */ -struct ubifs_pnode -{ - struct ubifs_nnode *parent; - struct ubifs_cnode *cnext; - unsigned long flags; - int iip; - int level; - int num; - struct ubifs_lprops lprops[UBIFS_LPT_FANOUT]; -}; - -/** - * struct ubifs_nbranch - LEB Properties Tree internal node branch. - * @lnum: LEB number of child - * @offs: offset of child - * @nnode: nnode child - * @pnode: pnode child - * @cnode: cnode child - */ -struct ubifs_nbranch -{ - int lnum; - int offs; - union - { - struct ubifs_nnode *nnode; - struct ubifs_pnode *pnode; - struct ubifs_cnode *cnode; - }; -}; - -/** - * struct ubifs_nnode - LEB Properties Tree internal node. - * @parent: parent nnode - * @cnext: next cnode to commit - * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE) - * @iip: index in parent - * @level: level in the tree (always greater than zero for nnodes) - * @num: node number - * @nbranch: branches to child nodes - */ -struct ubifs_nnode -{ - struct ubifs_nnode *parent; - struct ubifs_cnode *cnext; - unsigned long flags; - int iip; - int level; - int num; - struct ubifs_nbranch nbranch[UBIFS_LPT_FANOUT]; -}; - -/** - * struct ubifs_lp_stats - statistics of eraseblocks in the main area. - * @empty_lebs: number of empty LEBs - * @taken_empty_lebs: number of taken LEBs - * @idx_lebs: number of indexing LEBs - * @total_free: total free space in bytes - * @total_dirty: total dirty space in bytes - * @total_used: total used space in bytes (includes only data LEBs) - * @total_dead: total dead space in bytes (includes only data LEBs) - * @total_dark: total dark space in bytes (includes only data LEBs) - */ -struct ubifs_lp_stats { - int empty_lebs; - int taken_empty_lebs; - int idx_lebs; - long long total_free; - long long total_dirty; - long long total_used; - long long total_dead; - long long total_dark; -}; - -/** - * struct ubifs_zbranch - key/coordinate/length branch stored in znodes. - * @key: key - * @znode: znode address in memory - * @lnum: LEB number of the indexing node - * @offs: offset of the indexing node within @lnum - * @len: target node length - */ -struct ubifs_zbranch -{ - union ubifs_key key; - struct ubifs_znode *znode; - int lnum; - int offs; - int len; -}; - -/** - * struct ubifs_znode - in-memory representation of an indexing node. - * @parent: parent znode or NULL if it is the root - * @cnext: next znode to commit - * @flags: flags - * @time: last access time (seconds) - * @level: level of the entry in the TNC tree - * @child_cnt: count of child znodes - * @iip: index in parent's zbranch array - * @alt: lower bound of key range has altered i.e. child inserted at slot 0 - * @zbranch: array of znode branches (@c->fanout elements) - */ -struct ubifs_znode -{ - struct ubifs_znode *parent; - struct ubifs_znode *cnext; - unsigned long flags; - unsigned long time; - int level; - int child_cnt; - int iip; - int alt; -#ifdef CONFIG_UBIFS_FS_DEBUG - int lnum, offs, len; -#endif - struct ubifs_zbranch zbranch[]; -}; - -/** - * struct ubifs_info - UBIFS file-system description data structure - * (per-superblock). - * - * @highest_inum: highest used inode number - * @max_sqnum: current global sequence number - * - * @jhead_cnt: count of journal heads - * @max_bud_bytes: maximum number of bytes allowed in buds - * - * @zroot: zbranch which points to the root index node and znode - * @ihead_lnum: LEB number of index head - * @ihead_offs: offset of index head - * - * @log_lebs: number of logical eraseblocks in the log - * @lpt_lebs: number of LEBs used for lprops table - * @lpt_first: first LEB of the lprops table area - * @lpt_last: last LEB of the lprops table area - * @main_lebs: count of LEBs in the main area - * @main_first: first LEB of the main area - * @default_compr: default compression type - * @favor_lzo: favor LZO compression method - * @favor_percent: lzo vs. zlib threshold used in case favor LZO - * - * @key_hash_type: type of the key hash - * @key_hash: direntry key hash function - * @key_fmt: key format - * @key_len: key length - * @fanout: fanout of the index tree (number of links per indexing node) - * - * @min_io_size: minimal input/output unit size - * @leb_size: logical eraseblock size in bytes - * @leb_cnt: count of logical eraseblocks - * @max_leb_cnt: maximum count of logical eraseblocks - * - * @old_idx_sz: size of index on flash - * @lst: lprops statistics - * - * @dead_wm: LEB dead space watermark - * @dark_wm: LEB dark space watermark - * - * @di: UBI device information - * @vi: UBI volume information - * - * @gc_lnum: LEB number used for garbage collection - * @rp_size: reserved pool size - * - * @space_bits: number of bits needed to record free or dirty space - * @lpt_lnum_bits: number of bits needed to record a LEB number in the LPT - * @lpt_offs_bits: number of bits needed to record an offset in the LPT - * @lpt_spc_bits: number of bits needed to space in the LPT - * @pcnt_bits: number of bits needed to record pnode or nnode number - * @lnum_bits: number of bits needed to record LEB number - * @nnode_sz: size of on-flash nnode - * @pnode_sz: size of on-flash pnode - * @ltab_sz: size of on-flash LPT lprops table - * @lsave_sz: size of on-flash LPT save table - * @pnode_cnt: number of pnodes - * @nnode_cnt: number of nnodes - * @lpt_hght: height of the LPT - * - * @lpt_lnum: LEB number of the root nnode of the LPT - * @lpt_offs: offset of the root nnode of the LPT - * @nhead_lnum: LEB number of LPT head - * @nhead_offs: offset of LPT head - * @big_lpt: flag that LPT is too big to write whole during commit - * @space_fixup: flag indicating that free space in LEBs needs to be cleaned up - * @double_hash: flag indicating that we can do lookups by hash - * @lpt_sz: LPT size - * - * @ltab_lnum: LEB number of LPT's own lprops table - * @ltab_offs: offset of LPT's own lprops table - * @lpt: lprops table - * @ltab: LPT's own lprops table - * @lsave_cnt: number of LEB numbers in LPT's save table - * @lsave_lnum: LEB number of LPT's save table - * @lsave_offs: offset of LPT's save table - * @lsave: LPT's save table - * @lscan_lnum: LEB number of last LPT scan - * - * @hash_algo_name: the name of the hashing algorithm to use - * @hash_algo: The hash algo number (from include/linux/hash_info.h) - * @auth_key_filename: authentication key file name - * @x509_filename: x509 certificate file name for authentication - * @hash_len: the length of the hash - * @root_idx_hash: The hash of the root index node - * @lpt_hash: The hash of the LPT - * @mst_hash: The hash of the master node - */ -struct ubifs_info -{ - ino_t highest_inum; - unsigned long long max_sqnum; - - int jhead_cnt; - long long max_bud_bytes; - - struct ubifs_zbranch zroot; - int ihead_lnum; - int ihead_offs; - - int log_lebs; - int lpt_lebs; - int lpt_first; - int lpt_last; - int orph_lebs; - int main_lebs; - int main_first; - int default_compr; - int favor_lzo; - int favor_percent; - - uint8_t key_hash_type; - uint32_t (*key_hash)(const char *str, int len); - int key_fmt; - int key_len; - int fanout; - - int min_io_size; - int leb_size; - int leb_cnt; - int max_leb_cnt; - - unsigned long long old_idx_sz; - struct ubifs_lp_stats lst; - - int dead_wm; - int dark_wm; - - struct ubi_dev_info di; - struct ubi_vol_info vi; - - int gc_lnum; - long long rp_size; - - int space_bits; - int lpt_lnum_bits; - int lpt_offs_bits; - int lpt_spc_bits; - int pcnt_bits; - int lnum_bits; - int nnode_sz; - int pnode_sz; - int ltab_sz; - int lsave_sz; - int pnode_cnt; - int nnode_cnt; - int lpt_hght; - - int lpt_lnum; - int lpt_offs; - int nhead_lnum; - int nhead_offs; - int big_lpt; - int space_fixup; - int double_hash; - int encrypted; - long long lpt_sz; - - int ltab_lnum; - int ltab_offs; - struct ubifs_lprops *lpt; - struct ubifs_lpt_lprops *ltab; - int lsave_cnt; - int lsave_lnum; - int lsave_offs; - int *lsave; - int lscan_lnum; - - char *hash_algo_name; - int hash_algo; - char *auth_key_filename; - char *auth_cert_filename; - int hash_len; - uint8_t root_idx_hash[UBIFS_MAX_HASH_LEN]; - uint8_t lpt_hash[UBIFS_MAX_HASH_LEN]; - uint8_t mst_hash[UBIFS_MAX_HASH_LEN]; -}; - -/** - * ubifs_idx_node_sz - return index node size. - * @c: the UBIFS file-system description object - * @child_cnt: number of children of this index node - */ -static inline int ubifs_idx_node_sz(const struct ubifs_info *c, int child_cnt) -{ - return UBIFS_IDX_NODE_SZ + (UBIFS_BRANCH_SZ + c->key_len + c->hash_len) - * child_cnt; -} - -/** - * ubifs_idx_branch - return pointer to an index branch. - * @c: the UBIFS file-system description object - * @idx: index node - * @bnum: branch number - */ -static inline -struct ubifs_branch *ubifs_idx_branch(const struct ubifs_info *c, - const struct ubifs_idx_node *idx, - int bnum) -{ - return (struct ubifs_branch *)((void *)idx->branches + - (UBIFS_BRANCH_SZ + c->key_len + c->hash_len) * bnum); -} - -#endif /* __UBIFS_H__ */ -- cgit v1.2.3