Index: uspace/lib/ext4/Makefile =================================================================== --- uspace/lib/ext4/Makefile (revision 7bd2c1960d85ead0ec1655a84c83ec6265e501e7) +++ uspace/lib/ext4/Makefile (revision 8158db78b9315e6037e063697326e42061046800) @@ -37,4 +37,5 @@ libext4_extent.c \ libext4_filesystem.c \ + libext4_hash.c \ libext4_inode.c \ libext4_superblock.c Index: uspace/lib/ext4/libext4.h =================================================================== --- uspace/lib/ext4/libext4.h (revision 7bd2c1960d85ead0ec1655a84c83ec6265e501e7) +++ uspace/lib/ext4/libext4.h (revision 8158db78b9315e6037e063697326e42061046800) @@ -38,4 +38,5 @@ #include "libext4_extent.h" #include "libext4_filesystem.h" +#include "libext4_hash.h" #include "libext4_inode.h" #include "libext4_superblock.h" Index: uspace/lib/ext4/libext4_directory.c =================================================================== --- uspace/lib/ext4/libext4_directory.c (revision 7bd2c1960d85ead0ec1655a84c83ec6265e501e7) +++ uspace/lib/ext4/libext4_directory.c (revision 8158db78b9315e6037e063697326e42061046800) @@ -246,5 +246,5 @@ int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it, - ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, const char *name) + ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t len, const char *name) { int rc; @@ -253,5 +253,5 @@ ext4_directory_dx_root_t *root; uint32_t hash; - ext4_directory_dx_hash_info_t hinfo; + ext4_hash_info_t hinfo; // get direct block 0 (index root) @@ -315,5 +315,5 @@ hinfo.hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info); - if ((hinfo.hash_version <= EXT4_DIRECTORY_DX_HASH_TEA) + if ((hinfo.hash_version <= EXT4_HASH_VERSION_TEA) && (ext4_superblock_has_flag(fs->superblock, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) { // 3 is magic from ext4 linux implementation @@ -324,5 +324,5 @@ hinfo.hash = 0; if (name) { - ext4_directory_hash(&hinfo, name); + ext4_hash_string(&hinfo, len, name); } @@ -387,8 +387,4 @@ } -void ext4_directory_hash(ext4_directory_dx_hash_info_t *hinfo, const char* name) -{ - // TODO -} /** Index: uspace/lib/ext4/libext4_directory.h =================================================================== --- uspace/lib/ext4/libext4_directory.h (revision 7bd2c1960d85ead0ec1655a84c83ec6265e501e7) +++ uspace/lib/ext4/libext4_directory.h (revision 8158db78b9315e6037e063697326e42061046800) @@ -96,22 +96,7 @@ } ext4_directory_dx_root_t; -typedef struct ext4_directory_dx_hash_info { - uint32_t hash; - uint32_t minor_hash; - uint32_t hash_version; - uint32_t *seed; -} ext4_directory_dx_hash_info_t; - #define EXT4_ERR_BAD_DX_DIR (-75000) - -#define EXT4_DIRECTORY_DX_HASH_LEGACY 0 -#define EXT4_DIRECTORY_DX_HASH_HALF_MD4 1 -#define EXT4_DIRECTORY_DX_HASH_TEA 2 -#define EXT4_DIRECTORY_DX_HASH_LEGACY_UNSIGNED 3 -#define EXT4_DIRECTORY_DX_HASH_HALF_MD4_UNSIGNED 4 -#define EXT4_DIRECTORY_DX_HASH_TEA_UNSIGNED 5 - -#define EXT4_DIRECTORY_HTREE_EOF 0x7fffffff +#define EXT4_DIRECTORY_HTREE_EOF (uint32_t)0x7fffffff @@ -138,7 +123,5 @@ extern int ext4_directory_iterator_fini(ext4_directory_iterator_t *); extern int ext4_directory_dx_find_entry(ext4_directory_iterator_t *, - ext4_filesystem_t *, ext4_inode_ref_t *, const char *); - -extern void ext4_directory_hash(ext4_directory_dx_hash_info_t *, const char* name); + ext4_filesystem_t *, ext4_inode_ref_t *, size_t, const char *); #endif Index: uspace/lib/ext4/libext4_hash.c =================================================================== --- uspace/lib/ext4/libext4_hash.c (revision 8158db78b9315e6037e063697326e42061046800) +++ uspace/lib/ext4/libext4_hash.c (revision 8158db78b9315e6037e063697326e42061046800) @@ -0,0 +1,323 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +/** + * @file libext4_hash.c + * @brief TODO + */ + +#include +#include + +#include "libext4_directory.h" +#include "libext4_hash.h" + +#define TEA_DELTA 0x9E3779B9 + + +/* F, G and H are basic MD4 functions: selection, majority, parity */ +#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) +#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) +#define H(x, y, z) ((x) ^ (y) ^ (z)) + +/* + * The generic round function. The application is so specific that + * we don't bother protecting all the arguments with parens, as is generally + * good macro practice, in favor of extra legibility. + * Rotation is separate from addition to prevent recomputation + */ +#define ROUND(f, a, b, c, d, x, s) \ + (a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s))) +#define K1 0 +#define K2 013240474631UL +#define K3 015666365641UL + + +static void tea_transform(uint32_t buf[4],uint32_t const in[]) +{ + uint32_t sum = 0; + uint32_t b0 = buf[0], b1 = buf[1]; + uint32_t a = in[0], b = in[1], c = in[2], d = in[3]; + int n = 16; + + do { + sum += TEA_DELTA; + b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); + b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); + } while (--n); + + buf[0] += b0; + buf[1] += b1; +} + + +static void half_md4_transform(uint32_t buf[4], const uint32_t in[8]) +{ + uint32_t a = buf[0], b = buf[1], c = buf[2], d = buf[3]; + + /* Round 1 */ + ROUND(F, a, b, c, d, in[0] + K1, 3); + ROUND(F, d, a, b, c, in[1] + K1, 7); + ROUND(F, c, d, a, b, in[2] + K1, 11); + ROUND(F, b, c, d, a, in[3] + K1, 19); + ROUND(F, a, b, c, d, in[4] + K1, 3); + ROUND(F, d, a, b, c, in[5] + K1, 7); + ROUND(F, c, d, a, b, in[6] + K1, 11); + ROUND(F, b, c, d, a, in[7] + K1, 19); + + /* Round 2 */ + ROUND(G, a, b, c, d, in[1] + K2, 3); + ROUND(G, d, a, b, c, in[3] + K2, 5); + ROUND(G, c, d, a, b, in[5] + K2, 9); + ROUND(G, b, c, d, a, in[7] + K2, 13); + ROUND(G, a, b, c, d, in[0] + K2, 3); + ROUND(G, d, a, b, c, in[2] + K2, 5); + ROUND(G, c, d, a, b, in[4] + K2, 9); + ROUND(G, b, c, d, a, in[6] + K2, 13); + + /* Round 3 */ + ROUND(H, a, b, c, d, in[3] + K3, 3); + ROUND(H, d, a, b, c, in[7] + K3, 9); + ROUND(H, c, d, a, b, in[2] + K3, 11); + ROUND(H, b, c, d, a, in[6] + K3, 15); + ROUND(H, a, b, c, d, in[1] + K3, 3); + ROUND(H, d, a, b, c, in[5] + K3, 9); + ROUND(H, c, d, a, b, in[0] + K3, 11); + ROUND(H, b, c, d, a, in[4] + K3, 15); + + buf[0] += a; + buf[1] += b; + buf[2] += c; + buf[3] += d; + +} + +static uint32_t hash_unsigned(const char *name, int len) +{ + uint32_t hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; + const unsigned char *ucp = (const unsigned char *) name; + + while (len--) { + hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373)); + + if (hash & 0x80000000) { + hash -= 0x7fffffff; + } + hash1 = hash0; + hash0 = hash; + } + return hash0 << 1; +} + +static uint32_t hash_signed(const char *name, int len) +{ + uint32_t hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; + const signed char *scp = (const signed char *) name; + + while (len--) { + hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373)); + + if (hash & 0x80000000) { + hash -= 0x7fffffff; + } + hash1 = hash0; + hash0 = hash; + } + return hash0 << 1; +} + +static void str2hashbuf_signed(const char *msg, int len, uint32_t *buf, int num) +{ + uint32_t pad, val; + int i; + const signed char *scp = (const signed char *) msg; + + pad = (uint32_t)len | ((uint32_t)len << 8); + pad |= pad << 16; + + val = pad; + if (len > num*4) { + len = num * 4; + } + + for (i = 0; i < len; i++) { + if ((i % 4) == 0) { + val = pad; + } + val = ((int) scp[i]) + (val << 8); + if ((i % 4) == 3) { + *buf++ = val; + val = pad; + num--; + } + } + + if (--num >= 0) { + *buf++ = val; + } + + while (--num >= 0) { + *buf++ = pad; + } +} + + +static void str2hashbuf_unsigned(const char *msg, int len, uint32_t *buf, int num) +{ + uint32_t pad, val; + int i; + const unsigned char *ucp = (const unsigned char *) msg; + + pad = (uint32_t)len | ((uint32_t)len << 8); + pad |= pad << 16; + + val = pad; + if (len > num*4) { + len = num * 4; + } + + for (i = 0; i < len; i++) { + if ((i % 4) == 0) { + val = pad; + } + val = ((int) ucp[i]) + (val << 8); + if ((i % 4) == 3) { + *buf++ = val; + val = pad; + num--; + } + } + + if (--num >= 0) { + *buf++ = val; + } + + while (--num >= 0) { + *buf++ = pad; + } +} + +int ext4_hash_string(ext4_hash_info_t *hinfo, size_t len, const char *name) +{ + uint32_t hash = 0; + uint32_t minor_hash = 0; + const char *p; + int i; + uint32_t in[8], buf[4]; + bool unsigned_version = false; + + /* Initialize the default seed for the hash checksum functions */ + buf[0] = 0x67452301; + buf[1] = 0xefcdab89; + buf[2] = 0x98badcfe; + buf[3] = 0x10325476; + + /* Check if the seed is all zero's */ + if (hinfo->seed) { + for (i = 0; i < 4; i++) { + if (hinfo->seed[i] != 0) { + break; + } + if (i < 4) { + memcpy(buf, hinfo->seed, sizeof(buf)); + } + } + } + + + switch (hinfo->hash_version) { + case EXT4_HASH_VERSION_LEGACY_UNSIGNED: + hash = hash_unsigned(name, len); + break; + + case EXT4_HASH_VERSION_LEGACY: + hash = hash_signed(name, len); + break; + + + case EXT4_HASH_VERSION_HALF_MD4_UNSIGNED: + unsigned_version = true; + + case EXT4_HASH_VERSION_HALF_MD4: + p = name; + while (len > 0) { + if (unsigned_version) { + str2hashbuf_unsigned(p, len, in, 8); + } else { + str2hashbuf_signed(p, len, in, 8); + } + half_md4_transform(buf, in); + len -= 32; + p += 32; + } + minor_hash = buf[2]; + hash = buf[1]; + break; + + + case EXT4_HASH_VERSION_TEA_UNSIGNED: + unsigned_version = true; + + case EXT4_HASH_VERSION_TEA: + p = name; + while (len > 0) { + if (unsigned_version) { + str2hashbuf_unsigned(p, len, in, 4); + } else { + str2hashbuf_signed(p, len, in, 4); + } + tea_transform(buf, in); + len -= 16; + p += 16; + } + hash = buf[0]; + minor_hash = buf[1]; + break; + + default: + hinfo->hash = 0; + return EINVAL; + } + + hash = hash & ~1; + if (hash == (EXT4_DIRECTORY_HTREE_EOF << 1)) { + hash = (EXT4_DIRECTORY_HTREE_EOF-1) << 1; + } + hinfo->hash = hash; + hinfo->minor_hash = minor_hash; + + return EOK; +} + +/** + * @} + */ Index: uspace/lib/ext4/libext4_hash.h =================================================================== --- uspace/lib/ext4/libext4_hash.h (revision 8158db78b9315e6037e063697326e42061046800) +++ uspace/lib/ext4/libext4_hash.h (revision 8158db78b9315e6037e063697326e42061046800) @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2011 Frantisek Princ + * 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. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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. + */ + +/** @addtogroup libext4 + * @{ + */ + +#ifndef LIBEXT4_LIBEXT4_HASH_H_ +#define LIBEXT4_LIBEXT4_HASH_H_ + +#include + +#define EXT4_HASH_VERSION_LEGACY 0 +#define EXT4_HASH_VERSION_HALF_MD4 1 +#define EXT4_HASH_VERSION_TEA 2 +#define EXT4_HASH_VERSION_LEGACY_UNSIGNED 3 +#define EXT4_HASH_VERSION_HALF_MD4_UNSIGNED 4 +#define EXT4_HASH_VERSION_TEA_UNSIGNED 5 + +typedef struct ext4_hash_info { + uint32_t hash; + uint32_t minor_hash; + uint32_t hash_version; + uint32_t *seed; +} ext4_hash_info_t; + +extern int ext4_hash_string(ext4_hash_info_t *, size_t, const char *); + +#endif + +/** + * @} + */ Index: uspace/srv/fs/ext4fs/ext4fs_ops.c =================================================================== --- uspace/srv/fs/ext4fs/ext4fs_ops.c (revision 7bd2c1960d85ead0ec1655a84c83ec6265e501e7) +++ uspace/srv/fs/ext4fs/ext4fs_ops.c (revision 8158db78b9315e6037e063697326e42061046800) @@ -216,28 +216,4 @@ } - // TODO check super block COMPAT FEATURES - if (ext4_inode_has_flag(eparent->inode_ref->inode, EXT4_INODE_FLAG_INDEX)) { - - rc = ext4_directory_dx_find_entry(&it, fs, eparent->inode_ref, component); - - // Index isn't corrupted - if (rc != EXT4_ERR_BAD_DX_DIR) { - - // TODO check return value - if (rc != EOK) { - return rc; - } - - inode = ext4_directory_entry_ll_get_inode(it.current); - return ext4fs_node_get_core(rfn, eparent->instance, inode); - } - - } - - rc = ext4_directory_iterator_init(&it, fs, eparent->inode_ref, 0); - if (rc != EOK) { - return rc; - } - /* Find length of component in bytes * TODO: check for library function call that does this @@ -246,4 +222,28 @@ while (*(component+component_size) != 0) { component_size++; + } + + // TODO check super block COMPAT FEATURES + if (ext4_inode_has_flag(eparent->inode_ref->inode, EXT4_INODE_FLAG_INDEX)) { + + rc = ext4_directory_dx_find_entry(&it, fs, eparent->inode_ref, component_size, component); + + // Index isn't corrupted + if (rc != EXT4_ERR_BAD_DX_DIR) { + + // TODO check return value + if (rc != EOK) { + return rc; + } + + inode = ext4_directory_entry_ll_get_inode(it.current); + return ext4fs_node_get_core(rfn, eparent->instance, inode); + } + + } + + rc = ext4_directory_iterator_init(&it, fs, eparent->inode_ref, 0); + if (rc != EOK) { + return rc; }