Index: uspace/lib/ext4/Makefile =================================================================== --- uspace/lib/ext4/Makefile (revision ab779280d0b8fd72a86dda613351189bb8eb38f0) +++ uspace/lib/ext4/Makefile (revision 0dc91833e7a3181f7d4a5b6d4e520601613be39b) @@ -35,4 +35,5 @@ libext4_block_group.c \ libext4_directory.c \ + libext4_directory_index.c \ libext4_extent.c \ libext4_filesystem.c \ Index: uspace/lib/ext4/libext4.h =================================================================== --- uspace/lib/ext4/libext4.h (revision ab779280d0b8fd72a86dda613351189bb8eb38f0) +++ uspace/lib/ext4/libext4.h (revision 0dc91833e7a3181f7d4a5b6d4e520601613be39b) @@ -36,4 +36,5 @@ #include "libext4_block_group.h" #include "libext4_directory.h" +#include "libext4_directory_index.h" #include "libext4_extent.h" #include "libext4_filesystem.h" Index: uspace/lib/ext4/libext4_directory.c =================================================================== --- uspace/lib/ext4/libext4_directory.c (revision ab779280d0b8fd72a86dda613351189bb8eb38f0) +++ uspace/lib/ext4/libext4_directory.c (revision 0dc91833e7a3181f7d4a5b6d4e520601613be39b) @@ -246,333 +246,4 @@ -static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block, - ext4_superblock_t *sb, size_t name_len, const char *name) -{ - uint32_t block_size, entry_space; - uint16_t limit; - ext4_directory_dx_root_t *root; - - root = (ext4_directory_dx_root_t *)root_block->data; - - if (root->info.hash_version != EXT4_HASH_VERSION_TEA && - root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4 && - root->info.hash_version != EXT4_HASH_VERSION_LEGACY) { - return EXT4_ERR_BAD_DX_DIR; - } - - // Check unused flags - if (root->info.unused_flags != 0) { - EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags); - return EXT4_ERR_BAD_DX_DIR; - } - - // Check indirect levels - if (root->info.indirect_levels > 1) { - EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels); - return EXT4_ERR_BAD_DX_DIR; - } - - block_size = ext4_superblock_get_block_size(sb); - - entry_space = block_size; - entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t); - entry_space -= sizeof(ext4_directory_dx_root_info_t); - entry_space = entry_space / sizeof(ext4_directory_dx_entry_t); - - limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries); - if (limit != entry_space) { - return EXT4_ERR_BAD_DX_DIR; - } - - hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info); - if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA) - && (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) { - // 3 is magic from ext4 linux implementation - hinfo->hash_version += 3; - } - - hinfo->seed = ext4_superblock_get_hash_seed(sb); - - if (name) { - ext4_hash_string(hinfo, name_len, name); - } - - return EOK; -} - -static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo, - ext4_filesystem_t *fs, ext4_inode_t *inode, block_t *root_block, - ext4_directory_dx_handle_t **handle, ext4_directory_dx_handle_t *handles) -{ - int rc; - uint16_t count, limit, entry_space; - uint8_t indirect_level; - ext4_directory_dx_root_t *root; - ext4_directory_dx_entry_t *p, *q, *m, *at; - ext4_directory_dx_entry_t *entries; - block_t *tmp_block = root_block; - uint32_t fblock, next_block; - ext4_directory_dx_handle_t *tmp_handle = handles; - - root = (ext4_directory_dx_root_t *)root_block->data; - entries = (ext4_directory_dx_entry_t *)&root->entries; - - limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries); - indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info); - - while (true) { - - count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries); - if ((count == 0) || (count > limit)) { - return EXT4_ERR_BAD_DX_DIR; - } - - p = entries + 1; - q = entries + count - 1; - - while (p <= q) { - m = p + (q - p) / 2; - if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) { - q = m - 1; - } else { - p = m + 1; - } - } - - at = p - 1; - - tmp_handle->block = tmp_block; - tmp_handle->entries = entries; - tmp_handle->position = at; - - if (indirect_level == 0) { - *handle = tmp_handle; - return EOK; - } - - next_block = ext4_directory_dx_entry_get_block(at); - - indirect_level--; - - rc = ext4_filesystem_get_inode_data_block_index(fs, inode, next_block, &fblock); - if (rc != EOK) { - return rc; - } - - rc = block_get(&tmp_block, fs->device, fblock, BLOCK_FLAGS_NONE); - if (rc != EOK) { - return rc; - } - - entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries; - limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries); - - entry_space = ext4_superblock_get_block_size(fs->superblock) - sizeof(ext4_directory_dx_dot_entry_t); - entry_space = entry_space / sizeof(ext4_directory_dx_entry_t); - - - if (limit != entry_space) { - block_put(tmp_block); - return EXT4_ERR_BAD_DX_DIR; - } - - ++tmp_handle; - } - - // Unreachable - return EOK; -} - - -static int ext4_dirextory_dx_find_dir_entry(block_t *block, - ext4_superblock_t *sb, size_t name_len, const char *name, - ext4_directory_entry_ll_t **res_entry, aoff64_t *block_offset) -{ - ext4_directory_entry_ll_t *dentry; - uint16_t dentry_len; - uint8_t *addr_limit; - aoff64_t offset = 0; - - dentry = (ext4_directory_entry_ll_t *)block->data; - addr_limit = block->data + ext4_superblock_get_block_size(sb); - - while ((uint8_t *)dentry < addr_limit) { - - if ((uint8_t*) dentry + name_len > addr_limit) { - break; - } - - if (dentry->inode != 0) { - if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) { - // Compare names - if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) { - *block_offset = offset; - *res_entry = dentry; - return 1; - } - } - } - - - // Goto next entry - dentry_len = ext4_directory_entry_ll_get_entry_length(dentry); - - if (dentry_len == 0) { - // TODO error - return -1; - } - - offset += dentry_len; - dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len); - } - - return 0; -} - -static int ext4_directory_dx_next_block(ext4_filesystem_t *fs, ext4_inode_t *inode, uint32_t hash, - ext4_directory_dx_handle_t *handle, ext4_directory_dx_handle_t *handles) -{ - ext4_directory_dx_handle_t *p; - uint16_t count; - uint32_t num_handles; - uint32_t current_hash; - block_t *block; - uint32_t block_addr, block_idx; - int rc; - - num_handles = 0; - p = handle; - - while (1) { - - p->position++; - count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries); - - if (p->position < p->entries + count) { - break; - } - - if (p == handles) { - return 0; - } - - num_handles++; - p--; - } - - current_hash = ext4_directory_dx_entry_get_hash(p->position); - - if ((hash & 1) == 0) { - if ((current_hash & ~1) != hash) { - return 0; - } - } - - while (num_handles--) { - - block_idx = ext4_directory_dx_entry_get_block(p->position); - rc = ext4_filesystem_get_inode_data_block_index(fs, inode, block_idx, &block_addr); - if (rc != EOK) { - return rc; - } - - rc = block_get(&block, fs->device, block_addr, BLOCK_FLAGS_NONE); - if (rc != EOK) { - return rc; - } - - p++; - - block_put(p->block); - p->block = block; - p->entries = ((ext4_directory_dx_node_t *) block->data)->entries; - p->position = p->entries; - } - - return 1; - -} - -int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it, - ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t len, const char *name) -{ - int rc; - uint32_t root_block_addr, leaf_block_addr, leaf_block_idx; - aoff64_t block_offset; - block_t *root_block, *leaf_block; - ext4_hash_info_t hinfo; - ext4_directory_entry_ll_t *res_dentry; - // TODO better names - ext4_directory_dx_handle_t handles[2], *handle; - - // get direct block 0 (index root) - rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &root_block_addr); - if (rc != EOK) { - return rc; - } - - rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE); - if (rc != EOK) { - it->current_block = NULL; - return rc; - } - - rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, len, name); - if (rc != EOK) { - block_put(root_block); - return EXT4_ERR_BAD_DX_DIR; - } - - rc = ext4_directory_dx_get_leaf(&hinfo, fs, inode_ref->inode, root_block, &handle, handles); - if (rc != EOK) { - block_put(root_block); - return EXT4_ERR_BAD_DX_DIR; - } - - do { - - leaf_block_idx = ext4_directory_dx_entry_get_block(handle->position); - - rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, leaf_block_idx, &leaf_block_addr); - if (rc != EOK) { - return EXT4_ERR_BAD_DX_DIR; - } - - rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE); - if (rc != EOK) { - return EXT4_ERR_BAD_DX_DIR; - } - - rc = ext4_dirextory_dx_find_dir_entry(leaf_block, fs->superblock, len, name, - &res_dentry, &block_offset); - - // Found => return it - if (rc == 1) { - it->fs = fs; - it->inode_ref = inode_ref; - it->current_block = leaf_block; - it->current_offset = block_offset; - it->current = res_dentry; - return EOK; - } - - block_put(leaf_block); - - // ERROR - corrupted index - if (rc == -1) { - // TODO cleanup - return EXT4_ERR_BAD_DX_DIR; - } - - rc = ext4_directory_dx_next_block(fs, inode_ref->inode, hinfo.hash, handle, &handles[0]); - if (rc < 0) { - // TODO cleanup - return EXT4_ERR_BAD_DX_DIR; - } - - } while (rc == 1); - - return ENOENT; -} Index: uspace/lib/ext4/libext4_directory.h =================================================================== --- uspace/lib/ext4/libext4_directory.h (revision ab779280d0b8fd72a86dda613351189bb8eb38f0) +++ uspace/lib/ext4/libext4_directory.h (revision 0dc91833e7a3181f7d4a5b6d4e520601613be39b) @@ -62,61 +62,4 @@ -/* Structures for indexed directory */ - -typedef struct ext4_directory_dx_countlimit { - uint16_t limit; - uint16_t count; -} ext4_directory_dx_countlimit_t; - -typedef struct ext4_directory_dx_dot_entry { - uint32_t inode; - uint16_t entry_length; - uint8_t name_length; - uint8_t inode_type; - uint8_t name[4]; -} ext4_directory_dx_dot_entry_t; - -typedef struct ext4_directory_dx_root_info { - uint32_t reserved_zero; - uint8_t hash_version; - uint8_t info_length; - uint8_t indirect_levels; - uint8_t unused_flags; -} ext4_directory_dx_root_info_t; - -typedef struct ext4_directory_dx_entry { - uint32_t hash; - uint32_t block; -} ext4_directory_dx_entry_t; - -typedef struct ext4_directory_dx_root { - ext4_directory_dx_dot_entry_t dots[2]; - ext4_directory_dx_root_info_t info; - ext4_directory_dx_entry_t entries[0]; -} ext4_directory_dx_root_t; - -typedef struct ext4_directory_dx_node { - struct fake_directory_entry { - uint32_t inode; - uint16_t entry_length; - uint8_t name_length; - uint8_t inode_type; - } fake; - ext4_directory_dx_entry_t entries[0]; -} ext4_directory_dx_node_t; - - -typedef struct ext4_directory_dx_handle { - block_t *block; - ext4_directory_dx_entry_t *entries; - ext4_directory_dx_entry_t *position; -} ext4_directory_dx_handle_t; - - - -#define EXT4_ERR_BAD_DX_DIR (-75000) -#define EXT4_DIRECTORY_HTREE_EOF (uint32_t)0x7fffffff - - extern uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *); extern uint16_t ext4_directory_entry_ll_get_entry_length( @@ -125,14 +68,4 @@ ext4_superblock_t *, ext4_directory_entry_ll_t *); -extern uint8_t ext4_directory_dx_root_info_get_hash_version(ext4_directory_dx_root_info_t *); -extern uint8_t ext4_directory_dx_root_info_get_info_length(ext4_directory_dx_root_info_t *); -extern uint8_t ext4_directory_dx_root_info_get_indirect_levels(ext4_directory_dx_root_info_t *); - -extern uint16_t ext4_directory_dx_countlimit_get_limit(ext4_directory_dx_countlimit_t *); -extern uint16_t ext4_directory_dx_countlimit_get_count(ext4_directory_dx_countlimit_t *); - -extern uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *); -extern uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *); - extern int ext4_directory_iterator_init(ext4_directory_iterator_t *, ext4_filesystem_t *, ext4_inode_ref_t *, aoff64_t); @@ -140,6 +73,4 @@ extern int ext4_directory_iterator_seek(ext4_directory_iterator_t *, aoff64_t pos); 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 *, size_t, const char *); #endif Index: uspace/lib/ext4/libext4_directory_index.c =================================================================== --- uspace/lib/ext4/libext4_directory_index.c (revision 0dc91833e7a3181f7d4a5b6d4e520601613be39b) +++ uspace/lib/ext4/libext4_directory_index.c (revision 0dc91833e7a3181f7d4a5b6d4e520601613be39b) @@ -0,0 +1,374 @@ +/* + * 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_directory_index.c + * @brief TODO + */ + +#include +#include "libext4.h" + +static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block, + ext4_superblock_t *sb, size_t name_len, const char *name) +{ + uint32_t block_size, entry_space; + uint16_t limit; + ext4_directory_dx_root_t *root; + + root = (ext4_directory_dx_root_t *)root_block->data; + + if (root->info.hash_version != EXT4_HASH_VERSION_TEA && + root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4 && + root->info.hash_version != EXT4_HASH_VERSION_LEGACY) { + return EXT4_ERR_BAD_DX_DIR; + } + + // Check unused flags + if (root->info.unused_flags != 0) { + EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags); + return EXT4_ERR_BAD_DX_DIR; + } + + // Check indirect levels + if (root->info.indirect_levels > 1) { + EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels); + return EXT4_ERR_BAD_DX_DIR; + } + + block_size = ext4_superblock_get_block_size(sb); + + entry_space = block_size; + entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t); + entry_space -= sizeof(ext4_directory_dx_root_info_t); + entry_space = entry_space / sizeof(ext4_directory_dx_entry_t); + + limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries); + if (limit != entry_space) { + return EXT4_ERR_BAD_DX_DIR; + } + + hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info); + if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA) + && (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) { + // 3 is magic from ext4 linux implementation + hinfo->hash_version += 3; + } + + hinfo->seed = ext4_superblock_get_hash_seed(sb); + + if (name) { + ext4_hash_string(hinfo, name_len, name); + } + + return EOK; +} + +static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo, + ext4_filesystem_t *fs, ext4_inode_t *inode, block_t *root_block, + ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks) +{ + int rc; + uint16_t count, limit, entry_space; + uint8_t indirect_level; + ext4_directory_dx_root_t *root; + ext4_directory_dx_entry_t *p, *q, *m, *at; + ext4_directory_dx_entry_t *entries; + block_t *tmp_block = root_block; + uint32_t fblock, next_block; + ext4_directory_dx_block_t *tmp_dx_block = dx_blocks; + + root = (ext4_directory_dx_root_t *)root_block->data; + entries = (ext4_directory_dx_entry_t *)&root->entries; + + limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries); + indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info); + + while (true) { + + count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries); + if ((count == 0) || (count > limit)) { + return EXT4_ERR_BAD_DX_DIR; + } + + p = entries + 1; + q = entries + count - 1; + + while (p <= q) { + m = p + (q - p) / 2; + if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) { + q = m - 1; + } else { + p = m + 1; + } + } + + at = p - 1; + + tmp_dx_block->block = tmp_block; + tmp_dx_block->entries = entries; + tmp_dx_block->position = at; + + if (indirect_level == 0) { + *dx_block = tmp_dx_block; + return EOK; + } + + next_block = ext4_directory_dx_entry_get_block(at); + + indirect_level--; + + rc = ext4_filesystem_get_inode_data_block_index(fs, inode, next_block, &fblock); + if (rc != EOK) { + return rc; + } + + rc = block_get(&tmp_block, fs->device, fblock, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries; + limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries); + + entry_space = ext4_superblock_get_block_size(fs->superblock) - sizeof(ext4_directory_dx_dot_entry_t); + entry_space = entry_space / sizeof(ext4_directory_dx_entry_t); + + + if (limit != entry_space) { + block_put(tmp_block); + return EXT4_ERR_BAD_DX_DIR; + } + + ++tmp_dx_block; + } + + // Unreachable + return EOK; +} + + +static int ext4_dirextory_dx_find_dir_entry(block_t *block, + ext4_superblock_t *sb, size_t name_len, const char *name, + ext4_directory_entry_ll_t **res_entry, aoff64_t *block_offset) +{ + ext4_directory_entry_ll_t *dentry; + uint16_t dentry_len; + uint8_t *addr_limit; + aoff64_t offset = 0; + + dentry = (ext4_directory_entry_ll_t *)block->data; + addr_limit = block->data + ext4_superblock_get_block_size(sb); + + while ((uint8_t *)dentry < addr_limit) { + + if ((uint8_t*) dentry + name_len > addr_limit) { + break; + } + + if (dentry->inode != 0) { + if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) { + // Compare names + if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) { + *block_offset = offset; + *res_entry = dentry; + return 1; + } + } + } + + + // Goto next entry + dentry_len = ext4_directory_entry_ll_get_entry_length(dentry); + + if (dentry_len == 0) { + // TODO error + return -1; + } + + offset += dentry_len; + dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len); + } + + return 0; +} + +static int ext4_directory_dx_next_block(ext4_filesystem_t *fs, ext4_inode_t *inode, uint32_t hash, + ext4_directory_dx_block_t *handle, ext4_directory_dx_block_t *handles) +{ + ext4_directory_dx_block_t *p; + uint16_t count; + uint32_t num_handles; + uint32_t current_hash; + block_t *block; + uint32_t block_addr, block_idx; + int rc; + + num_handles = 0; + p = handle; + + while (1) { + + p->position++; + count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries); + + if (p->position < p->entries + count) { + break; + } + + if (p == handles) { + return 0; + } + + num_handles++; + p--; + } + + current_hash = ext4_directory_dx_entry_get_hash(p->position); + + if ((hash & 1) == 0) { + if ((current_hash & ~1) != hash) { + return 0; + } + } + + while (num_handles--) { + + block_idx = ext4_directory_dx_entry_get_block(p->position); + rc = ext4_filesystem_get_inode_data_block_index(fs, inode, block_idx, &block_addr); + if (rc != EOK) { + return rc; + } + + rc = block_get(&block, fs->device, block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return rc; + } + + p++; + + block_put(p->block); + p->block = block; + p->entries = ((ext4_directory_dx_node_t *) block->data)->entries; + p->position = p->entries; + } + + return 1; + +} + +int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it, + ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t len, const char *name) +{ + int rc; + uint32_t root_block_addr, leaf_block_addr, leaf_block_idx; + aoff64_t block_offset; + block_t *root_block, *leaf_block; + ext4_hash_info_t hinfo; + ext4_directory_entry_ll_t *res_dentry; + ext4_directory_dx_block_t dx_blocks[2], *dx_block; + + // get direct block 0 (index root) + rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &root_block_addr); + if (rc != EOK) { + return rc; + } + + rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + it->current_block = NULL; + return rc; + } + + rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, len, name); + if (rc != EOK) { + block_put(root_block); + return EXT4_ERR_BAD_DX_DIR; + } + + rc = ext4_directory_dx_get_leaf(&hinfo, fs, inode_ref->inode, root_block, &dx_block, dx_blocks); + if (rc != EOK) { + block_put(root_block); + return EXT4_ERR_BAD_DX_DIR; + } + + do { + + leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position); + + rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, leaf_block_idx, &leaf_block_addr); + if (rc != EOK) { + return EXT4_ERR_BAD_DX_DIR; + } + + rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE); + if (rc != EOK) { + return EXT4_ERR_BAD_DX_DIR; + } + + rc = ext4_dirextory_dx_find_dir_entry(leaf_block, fs->superblock, len, name, + &res_dentry, &block_offset); + + // Found => return it + if (rc == 1) { + it->fs = fs; + it->inode_ref = inode_ref; + it->current_block = leaf_block; + it->current_offset = block_offset; + it->current = res_dentry; + return EOK; + } + + block_put(leaf_block); + + // ERROR - corrupted index + if (rc == -1) { + // TODO cleanup + return EXT4_ERR_BAD_DX_DIR; + } + + rc = ext4_directory_dx_next_block(fs, inode_ref->inode, hinfo.hash, dx_block, &dx_blocks[0]); + if (rc < 0) { + // TODO cleanup + return EXT4_ERR_BAD_DX_DIR; + } + + } while (rc == 1); + + return ENOENT; +} + + + +/** + * @} + */ Index: uspace/lib/ext4/libext4_directory_index.h =================================================================== --- uspace/lib/ext4/libext4_directory_index.h (revision 0dc91833e7a3181f7d4a5b6d4e520601613be39b) +++ uspace/lib/ext4/libext4_directory_index.h (revision 0dc91833e7a3181f7d4a5b6d4e520601613be39b) @@ -0,0 +1,111 @@ +/* + * 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_DIRECTORY_INDEX_H_ +#define LIBEXT4_LIBEXT4_DIRECTORY_INDEX_H_ + +/* Structures for indexed directory */ + +typedef struct ext4_directory_dx_countlimit { + uint16_t limit; + uint16_t count; +} ext4_directory_dx_countlimit_t; + +typedef struct ext4_directory_dx_dot_entry { + uint32_t inode; + uint16_t entry_length; + uint8_t name_length; + uint8_t inode_type; + uint8_t name[4]; +} ext4_directory_dx_dot_entry_t; + +typedef struct ext4_directory_dx_root_info { + uint32_t reserved_zero; + uint8_t hash_version; + uint8_t info_length; + uint8_t indirect_levels; + uint8_t unused_flags; +} ext4_directory_dx_root_info_t; + +typedef struct ext4_directory_dx_entry { + uint32_t hash; + uint32_t block; +} ext4_directory_dx_entry_t; + +typedef struct ext4_directory_dx_root { + ext4_directory_dx_dot_entry_t dots[2]; + ext4_directory_dx_root_info_t info; + ext4_directory_dx_entry_t entries[0]; +} ext4_directory_dx_root_t; + +typedef struct ext4_directory_dx_node { + struct fake_directory_entry { + uint32_t inode; + uint16_t entry_length; + uint8_t name_length; + uint8_t inode_type; + } fake; + ext4_directory_dx_entry_t entries[0]; +} ext4_directory_dx_node_t; + + +typedef struct ext4_directory_dx_block { + block_t *block; + ext4_directory_dx_entry_t *entries; + ext4_directory_dx_entry_t *position; +} ext4_directory_dx_block_t; + + + +#define EXT4_ERR_BAD_DX_DIR (-75000) +#define EXT4_DIRECTORY_HTREE_EOF (uint32_t)0x7fffffff + + +extern uint8_t ext4_directory_dx_root_info_get_hash_version(ext4_directory_dx_root_info_t *); +extern uint8_t ext4_directory_dx_root_info_get_info_length(ext4_directory_dx_root_info_t *); +extern uint8_t ext4_directory_dx_root_info_get_indirect_levels(ext4_directory_dx_root_info_t *); + +extern uint16_t ext4_directory_dx_countlimit_get_limit(ext4_directory_dx_countlimit_t *); +extern uint16_t ext4_directory_dx_countlimit_get_count(ext4_directory_dx_countlimit_t *); + +extern uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *); +extern uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *); + +extern int ext4_directory_dx_find_entry(ext4_directory_iterator_t *, + 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 ab779280d0b8fd72a86dda613351189bb8eb38f0) +++ uspace/lib/ext4/libext4_hash.c (revision 0dc91833e7a3181f7d4a5b6d4e520601613be39b) @@ -236,10 +236,4 @@ void (*str2hashbuf)(const char *, int, uint32_t *, int) = str2hashbuf_signed; - /* - for (i = 0; i < 8; ++i) { - in[i] = 0; - } - */ - /* Initialize the default seed for the hash checksum functions */ buf[0] = 0x67452301;