/* * Copyright (c) 2012 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 Ext4 directory index operations. */ #include #include #include #include #include #include "libext4.h" /** Type entry to pass to sorting algorithm. * */ typedef struct ext4_dx_sort_entry { uint32_t hash; uint32_t rec_len; void *dentry; } ext4_dx_sort_entry_t; /** Get hash version used in directory index. * * @param root_info pointer to root info structure of index * @return hash algorithm version */ uint8_t ext4_directory_dx_root_info_get_hash_version( ext4_directory_dx_root_info_t *root_info) { return root_info->hash_version; } /** Set hash version, that will be used in directory index. * * @param root_info pointer to root info structure of index * @param version hash algorithm version */ void ext4_directory_dx_root_info_set_hash_version( ext4_directory_dx_root_info_t *root_info, uint8_t version) { root_info->hash_version = version; } /** Get length of root_info structure in bytes. * * @param root_info pointer to root info structure of index * @return length of the structure */ uint8_t ext4_directory_dx_root_info_get_info_length( ext4_directory_dx_root_info_t *root_info) { return root_info->info_length; } /** Set length of root_info structure in bytes. * * @param root_info pointer to root info structure of index * @param info_length length of the structure */ void ext4_directory_dx_root_info_set_info_length( ext4_directory_dx_root_info_t *root_info, uint8_t info_length) { root_info->info_length = info_length; } /** Get number of indirect levels of HTree. * * @param root_info pointer to root info structure of index * @return height of HTree (actually only 0 or 1) */ uint8_t ext4_directory_dx_root_info_get_indirect_levels( ext4_directory_dx_root_info_t *root_info) { return root_info->indirect_levels; } /** Set number of indirect levels of HTree. * * @param root_info pointer to root info structure of index * @param levels height of HTree (actually only 0 or 1) */ void ext4_directory_dx_root_info_set_indirect_levels( ext4_directory_dx_root_info_t *root_info, uint8_t levels) { root_info->indirect_levels = levels; } /** Get maximum number of index node entries. * * @param countlimit pointer to counlimit structure * @return maximum of entries in node */ uint16_t ext4_directory_dx_countlimit_get_limit( ext4_directory_dx_countlimit_t *countlimit) { return uint16_t_le2host(countlimit->limit); } /** Set maximum number of index node entries. * * @param countlimit pointer to counlimit structure * @param limit maximum of entries in node */ void ext4_directory_dx_countlimit_set_limit( ext4_directory_dx_countlimit_t *countlimit, uint16_t limit) { countlimit->limit = host2uint16_t_le(limit); } /** Get current number of index node entries. * * @param countlimit pointer to counlimit structure * @return number of entries in node */ uint16_t ext4_directory_dx_countlimit_get_count( ext4_directory_dx_countlimit_t *countlimit) { return uint16_t_le2host(countlimit->count); } /** Set current number of index node entries. * * @param countlimit pointer to counlimit structure * @param count number of entries in node */ void ext4_directory_dx_countlimit_set_count( ext4_directory_dx_countlimit_t *countlimit, uint16_t count) { countlimit->count = host2uint16_t_le(count); } /** Get hash value of index entry. * * @param entry pointer to index entry * @return hash value */ uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry) { return uint32_t_le2host(entry->hash); } /** Set hash value of index entry. * * @param entry pointer to index entry * @param hash hash value */ void ext4_directory_dx_entry_set_hash(ext4_directory_dx_entry_t *entry, uint32_t hash) { entry->hash = host2uint32_t_le(hash); } /** Get block address where child node is located. * * @param entry pointer to index entry * @return block address of child node */ uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry) { return uint32_t_le2host(entry->block); } /** Set block address where child node is located. * * @param entry pointer to index entry * @param block block address of child node */ void ext4_directory_dx_entry_set_block(ext4_directory_dx_entry_t *entry, uint32_t block) { entry->block = host2uint32_t_le(block); } /**************************************************************************/ /** Initialize index structure of new directory. * * @param dir pointer to directory i-node * @return error code */ int ext4_directory_dx_init(ext4_inode_ref_t *dir) { int rc; // Load block 0, where will be index root located uint32_t fblock; rc = ext4_filesystem_get_inode_data_block_index(dir, 0, &fblock); if (rc != EOK) { return rc; } block_t *block; rc = block_get(&block, dir->fs->device, fblock, BLOCK_FLAGS_NONE); if (rc != EOK) { return rc; } // Initialize pointers to data structures ext4_directory_dx_root_t *root = block->data; ext4_directory_dx_root_info_t *info = &(root->info); // Initialize root info structure uint8_t hash_version = ext4_superblock_get_default_hash_version(dir->fs->superblock); ext4_directory_dx_root_info_set_hash_version(info, hash_version); ext4_directory_dx_root_info_set_indirect_levels(info, 0); ext4_directory_dx_root_info_set_info_length(info, 8); // Set limit and current number of entries ext4_directory_dx_countlimit_t *countlimit = (ext4_directory_dx_countlimit_t *)&root->entries; ext4_directory_dx_countlimit_set_count(countlimit, 1); uint32_t block_size = ext4_superblock_get_block_size(dir->fs->superblock); uint32_t entry_space = block_size - 2 * sizeof(ext4_directory_dx_dot_entry_t) - sizeof(ext4_directory_dx_root_info_t); uint16_t root_limit = entry_space / sizeof(ext4_directory_dx_entry_t); ext4_directory_dx_countlimit_set_limit(countlimit, root_limit); // Append new block, where will be new entries inserted in the future uint32_t iblock; rc = ext4_filesystem_append_inode_block(dir, &fblock, &iblock); if (rc != EOK) { block_put(block); return rc; } block_t *new_block; rc = block_get(&new_block, dir->fs->device, fblock, BLOCK_FLAGS_NOREAD); if (rc != EOK) { block_put(block); return rc; } // Fill the whole block with empty entry ext4_directory_entry_ll_t *block_entry = new_block->data; ext4_directory_entry_ll_set_entry_length(block_entry, block_size); ext4_directory_entry_ll_set_inode(block_entry, 0); new_block->dirty = true; rc = block_put(new_block); if (rc != EOK) { block_put(block); return rc; } // Connect new block to the only entry in index ext4_directory_dx_entry_t *entry = root->entries; ext4_directory_dx_entry_set_block(entry, iblock); block->dirty = true; rc = block_put(block); if (rc != EOK) { return rc; } return EOK; } /** Initialize hash info structure necessary for index operations. * * @param hinfo pointer to hinfo to be initialized * @param root_block root block (number 0) of index * @param sb pointer to superblock * @param name_len length of name to be computed hash value from * @param name name to be computed hash value from * @return error code */ 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) { ext4_directory_dx_root_t *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; } // Check if node limit is correct uint32_t block_size = ext4_superblock_get_block_size(sb); uint32_t 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); uint16_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; } // Check hash version and modify if necessary 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; } // Load hash seed from superblock hinfo->seed = ext4_superblock_get_hash_seed(sb); // Compute hash value of name if (name) { ext4_hash_string(hinfo, name_len, name); } return EOK; } /** Walk through index tree and load leaf with corresponding hash value. * * @param hinfo initialized hash info structure * @param inode_ref current i-node * @param root_block root block (iblock 0), where is root node located * @param dx_block pointer to leaf node in dx_blocks array * @param dx_blocks array with the whole path from root to leaf * @return error code */ static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo, ext4_inode_ref_t *inode_ref, block_t *root_block, ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks) { int rc; ext4_directory_dx_block_t *tmp_dx_block = dx_blocks; ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data; ext4_directory_dx_entry_t *entries = (ext4_directory_dx_entry_t *)&root->entries; uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries); uint8_t indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info); block_t *tmp_block = root_block; ext4_directory_dx_entry_t *p, *q, *m, *at; // Walk through the index tree while (true) { uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries); if ((count == 0) || (count > limit)) { return EXT4_ERR_BAD_DX_DIR; } // Do binary search in every node 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; // Write results tmp_dx_block->block = tmp_block; tmp_dx_block->entries = entries; tmp_dx_block->position = at; // Is algorithm in the leaf? if (indirect_level == 0) { *dx_block = tmp_dx_block; return EOK; } // Goto child node uint32_t next_block = ext4_directory_dx_entry_get_block(at); indirect_level--; uint32_t fblock; rc = ext4_filesystem_get_inode_data_block_index( inode_ref, next_block, &fblock); if (rc != EOK) { return rc; } rc = block_get(&tmp_block, inode_ref->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); uint16_t entry_space = ext4_superblock_get_block_size(inode_ref->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; } /** Check if the the next block would be checked during entry search. * * @param inode_ref directory i-node * @param hash hash value to check * @param dx_block current block * @param dx_blocks aray with path from root to leaf node * @return error code */ static int ext4_directory_dx_next_block(ext4_inode_ref_t *inode_ref, uint32_t hash, ext4_directory_dx_block_t *dx_block, ext4_directory_dx_block_t *dx_blocks) { int rc; uint32_t num_handles = 0; ext4_directory_dx_block_t *p = dx_block; // Try to find data block with next bunch of entries while (1) { p->position++; uint16_t count = ext4_directory_dx_countlimit_get_count( (ext4_directory_dx_countlimit_t *)p->entries); if (p->position < p->entries + count) { break; } if (p == dx_blocks) { return 0; } num_handles++; p--; } // Check hash collision (if not occured - no next block cannot be used) uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position); if ((hash & 1) == 0) { if ((current_hash & ~1) != hash) { return 0; } } // Fill new path while (num_handles--) { uint32_t block_idx = ext4_directory_dx_entry_get_block(p->position); uint32_t block_addr; rc = ext4_filesystem_get_inode_data_block_index(inode_ref, block_idx, &block_addr); if (rc != EOK) { return rc; } block_t *block; rc = block_get(&block, inode_ref->fs->device, block_addr, BLOCK_FLAGS_NONE); if (rc != EOK) { return rc; } p++; // Don't forget to put old block (prevent memory leak) block_put(p->block); p->block = block; p->entries = ((ext4_directory_dx_node_t *) block->data)->entries; p->position = p->entries; } return 1; } /** Try to find directory entry using directory index. * * @param result output value - if entry will be found, * than will be passed through this parameter * @param inode_ref directory i-node * @param name_len length of name to be found * @param name name to be found * @return error code */ int ext4_directory_dx_find_entry(ext4_directory_search_result_t *result, ext4_inode_ref_t *inode_ref, size_t name_len, const char *name) { int rc; // Load direct block 0 (index root) uint32_t root_block_addr; rc = ext4_filesystem_get_inode_data_block_index(inode_ref, 0, &root_block_addr); if (rc != EOK) { return rc; } ext4_filesystem_t *fs = inode_ref->fs; block_t *root_block; rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE); if (rc != EOK) { return rc; } // Initialize hash info (compute hash value) ext4_hash_info_t hinfo; rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_len, name); if (rc != EOK) { block_put(root_block); return EXT4_ERR_BAD_DX_DIR; } // Hardcoded number 2 means maximum height of index tree, specified in linux driver ext4_directory_dx_block_t dx_blocks[2]; ext4_directory_dx_block_t *dx_block, *tmp; rc = ext4_directory_dx_get_leaf(&hinfo, inode_ref, root_block, &dx_block, dx_blocks); if (rc != EOK) { block_put(root_block); return EXT4_ERR_BAD_DX_DIR; } do { // Load leaf block uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position); uint32_t leaf_block_addr; rc = ext4_filesystem_get_inode_data_block_index(inode_ref, leaf_block_idx, &leaf_block_addr); if (rc != EOK) { goto cleanup; } block_t *leaf_block; rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE); if (rc != EOK) { goto cleanup; } // Linear search inside block ext4_directory_entry_ll_t *res_dentry; rc = ext4_directory_find_in_block(leaf_block, fs->superblock, name_len, name, &res_dentry); // Found => return it if (rc == EOK) { result->block = leaf_block; result->dentry = res_dentry; goto cleanup; } // Not found, leave untouched block_put(leaf_block); if (rc != ENOENT) { goto cleanup; } // check if the next block could be checked rc = ext4_directory_dx_next_block(inode_ref, hinfo.hash, dx_block, &dx_blocks[0]); if (rc < 0) { goto cleanup; } } while (rc == 1); // Entry not found rc = ENOENT; cleanup: // The whole path must be released (preventing memory leak) tmp = dx_blocks; while (tmp <= dx_block) { block_put(tmp->block); ++tmp; } return rc; } /** Compare function used to pass in quicksort implementation. * * It can compare two entries by hash value. * * @param arg1 first entry * @param arg2 second entry * @param dummy unused parameter, can be NULL * @return classic compare result (0: equal, -1: arg1 < arg2, 1: arg1 > arg2) */ static int ext4_directory_dx_entry_comparator(void *arg1, void *arg2, void *dummy) { ext4_dx_sort_entry_t *entry1 = arg1; ext4_dx_sort_entry_t *entry2 = arg2; if (entry1->hash == entry2->hash) { return 0; } if (entry1->hash < entry2->hash) { return -1; } else { return 1; } } /** Insert new index entry to block. * * Note that space for new entry must be checked by caller. * * @param index_block block where to insert new entry * @param hash hash value covered by child node * @param iblock logical number of child block * */ static void ext4_directory_dx_insert_entry( ext4_directory_dx_block_t *index_block, uint32_t hash, uint32_t iblock) { ext4_directory_dx_entry_t *old_index_entry = index_block->position; ext4_directory_dx_entry_t *new_index_entry = old_index_entry + 1; ext4_directory_dx_countlimit_t *countlimit = (ext4_directory_dx_countlimit_t *)index_block->entries; uint32_t count = ext4_directory_dx_countlimit_get_count(countlimit); ext4_directory_dx_entry_t *start_index = index_block->entries; size_t bytes = (void *)(start_index + count) - (void *)(new_index_entry); memmove(new_index_entry + 1, new_index_entry, bytes); ext4_directory_dx_entry_set_block(new_index_entry, iblock); ext4_directory_dx_entry_set_hash(new_index_entry, hash); ext4_directory_dx_countlimit_set_count(countlimit, count + 1); index_block->block->dirty = true; } /** Split directory entries to two parts preventing node overflow. * * @param inode_ref directory i-node * @param hinfo hash info * @param old_data_block block with data to be split * @param index_block block where index entries are located * @param new_data_block output value for newly allocated data block */ static int ext4_directory_dx_split_data(ext4_inode_ref_t *inode_ref, ext4_hash_info_t *hinfo, block_t *old_data_block, ext4_directory_dx_block_t *index_block, block_t **new_data_block) { int rc = EOK; // Allocate buffer for directory entries uint32_t block_size = ext4_superblock_get_block_size(inode_ref->fs->superblock); void *entry_buffer = malloc(block_size); if (entry_buffer == NULL) { return ENOMEM; } // dot entry has the smallest size available uint32_t max_entry_count = block_size / sizeof(ext4_directory_dx_dot_entry_t); // Allocate sort entry ext4_dx_sort_entry_t *sort_array = malloc(max_entry_count * sizeof(ext4_dx_sort_entry_t)); if (sort_array == NULL) { free(entry_buffer); return ENOMEM; } uint32_t idx = 0; uint32_t real_size = 0; // Initialize hinfo ext4_hash_info_t tmp_hinfo; memcpy(&tmp_hinfo, hinfo, sizeof(ext4_hash_info_t)); // Load all valid entries to the buffer ext4_directory_entry_ll_t *dentry = old_data_block->data; void *entry_buffer_ptr = entry_buffer; while ((void *)dentry < old_data_block->data + block_size) { // Read only valid entries if (ext4_directory_entry_ll_get_inode(dentry) != 0) { uint8_t len = ext4_directory_entry_ll_get_name_length( inode_ref->fs->superblock, dentry); ext4_hash_string(&tmp_hinfo, len, (char *)dentry->name); uint32_t rec_len = 8 + len; if ((rec_len % 4) != 0) { rec_len += 4 - (rec_len % 4); } memcpy(entry_buffer_ptr, dentry, rec_len); sort_array[idx].dentry = entry_buffer_ptr; sort_array[idx].rec_len = rec_len; sort_array[idx].hash = tmp_hinfo.hash; entry_buffer_ptr += rec_len; real_size += rec_len; idx++; } dentry = (void *)dentry + ext4_directory_entry_ll_get_entry_length(dentry); } // Sort all entries qsort(sort_array, idx, sizeof(ext4_dx_sort_entry_t), ext4_directory_dx_entry_comparator, NULL); // Allocate new block for store the second part of entries uint32_t new_fblock; uint32_t new_iblock; rc = ext4_filesystem_append_inode_block(inode_ref, &new_fblock, &new_iblock); if (rc != EOK) { free(sort_array); free(entry_buffer); return rc; } // Load new block block_t *new_data_block_tmp; rc = block_get(&new_data_block_tmp, inode_ref->fs->device, new_fblock, BLOCK_FLAGS_NOREAD); if (rc != EOK) { free(sort_array); free(entry_buffer); return rc; } // Distribute entries to two blocks (by size) // Compute the half uint32_t new_hash = 0; uint32_t current_size = 0; uint32_t mid = 0; for (uint32_t i = 0; i < idx; ++i) { if ((current_size + sort_array[i].rec_len) > (real_size / 2)) { new_hash = sort_array[i].hash; mid = i; break; } current_size += sort_array[i].rec_len; } // Check hash collision uint32_t continued = 0; if (new_hash == sort_array[mid-1].hash) { continued = 1; } uint32_t offset = 0; void *ptr; // First part - to the old block for (uint32_t i = 0; i < mid; ++i) { ptr = old_data_block->data + offset; memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len); ext4_directory_entry_ll_t *tmp = ptr; if (i < (mid - 1)) { ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len); } else { ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset); } offset += sort_array[i].rec_len; } // Second part - to the new block offset = 0; for (uint32_t i = mid; i < idx; ++i) { ptr = new_data_block_tmp->data + offset; memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len); ext4_directory_entry_ll_t *tmp = ptr; if (i < (idx - 1)) { ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len); } else { ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset); } offset += sort_array[i].rec_len; } // Do some steps to finish operation old_data_block->dirty = true; new_data_block_tmp->dirty = true; free(sort_array); free(entry_buffer); ext4_directory_dx_insert_entry(index_block, new_hash + continued, new_iblock); *new_data_block = new_data_block_tmp; return EOK; } /** Split index node and maybe some parent nodes in the tree hierarchy. * * @param inode_ref directory i-node * @param dx_blocks array with path from root to leaf node * @param dx_block leaf block to be split if needed * @return error code */ static int ext4_directory_dx_split_index(ext4_inode_ref_t *inode_ref, ext4_directory_dx_block_t *dx_blocks, ext4_directory_dx_block_t *dx_block) { int rc; ext4_directory_dx_entry_t *entries; if (dx_block == dx_blocks) { entries = ((ext4_directory_dx_root_t *) dx_block->block->data)->entries; } else { entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries; } ext4_directory_dx_countlimit_t *countlimit = (ext4_directory_dx_countlimit_t *)entries; uint16_t leaf_limit = ext4_directory_dx_countlimit_get_limit(countlimit); uint16_t leaf_count = ext4_directory_dx_countlimit_get_count(countlimit); // Check if is necessary to split index block if (leaf_limit == leaf_count) { unsigned int levels = dx_block - dx_blocks; ext4_directory_dx_entry_t *root_entries = ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->entries; ext4_directory_dx_countlimit_t *root_countlimit = (ext4_directory_dx_countlimit_t *)root_entries; uint16_t root_limit = ext4_directory_dx_countlimit_get_limit(root_countlimit); uint16_t root_count = ext4_directory_dx_countlimit_get_count(root_countlimit); // Linux limitation if ((levels > 0) && (root_limit == root_count)) { EXT4FS_DBG("Directory index is full"); return ENOSPC; } // Add new block to directory uint32_t new_fblock; uint32_t new_iblock; rc = ext4_filesystem_append_inode_block( inode_ref, &new_fblock, &new_iblock); if (rc != EOK) { return rc; } // load new block block_t * new_block; rc = block_get(&new_block, inode_ref->fs->device, new_fblock, BLOCK_FLAGS_NOREAD); if (rc != EOK) { return rc; } ext4_directory_dx_node_t *new_node = new_block->data; ext4_directory_dx_entry_t *new_entries = new_node->entries; uint32_t block_size = ext4_superblock_get_block_size( inode_ref->fs->superblock); // Split leaf node if (levels > 0) { uint32_t count_left = leaf_count / 2; uint32_t count_right = leaf_count - count_left; uint32_t hash_right = ext4_directory_dx_entry_get_hash(entries + count_left); // Copy data to new node memcpy((void *) new_entries, (void *) (entries + count_left), count_right * sizeof(ext4_directory_dx_entry_t)); // Initialize new node ext4_directory_dx_countlimit_t *left_countlimit = (ext4_directory_dx_countlimit_t *)entries; ext4_directory_dx_countlimit_t *right_countlimit = (ext4_directory_dx_countlimit_t *)new_entries; ext4_directory_dx_countlimit_set_count(left_countlimit, count_left); ext4_directory_dx_countlimit_set_count(right_countlimit, count_right); uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t); uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t); ext4_directory_dx_countlimit_set_limit(right_countlimit, node_limit); // Which index block is target for new entry uint32_t position_index = (dx_block->position - dx_block->entries); if (position_index >= count_left) { dx_block->block->dirty = true; block_t *block_tmp = dx_block->block; dx_block->block = new_block; dx_block->position = new_entries + position_index - count_left; dx_block->entries = new_entries; new_block = block_tmp; } // Finally insert new entry ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock); return block_put(new_block); } else { // Create second level index // Copy data from root to child block memcpy((void *) new_entries, (void *) entries, leaf_count * sizeof(ext4_directory_dx_entry_t)); ext4_directory_dx_countlimit_t *new_countlimit = (ext4_directory_dx_countlimit_t *)new_entries; uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t); uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t); ext4_directory_dx_countlimit_set_limit(new_countlimit, node_limit); // Set values in root node ext4_directory_dx_countlimit_t *new_root_countlimit = (ext4_directory_dx_countlimit_t *)entries; ext4_directory_dx_countlimit_set_count(new_root_countlimit, 1); ext4_directory_dx_entry_set_block(entries, new_iblock); ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->info.indirect_levels = 1; // Add new entry to the path dx_block = dx_blocks + 1; dx_block->position = dx_block->position - entries + new_entries; dx_block->entries = new_entries; dx_block->block = new_block; } } return EOK; } /** Add new entry to indexed directory * * @param parent directory i-node * @param child i-node to be referenced from directory entry * @param name name of new directory entry * @return error code */ int ext4_directory_dx_add_entry(ext4_inode_ref_t *parent, ext4_inode_ref_t *child, const char *name) { int rc = EOK; int rc2 = EOK; // get direct block 0 (index root) uint32_t root_block_addr; rc = ext4_filesystem_get_inode_data_block_index(parent, 0, &root_block_addr); if (rc != EOK) { return rc; } ext4_filesystem_t *fs = parent->fs; block_t *root_block; rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE); if (rc != EOK) { return rc; } // Initialize hinfo structure (mainly compute hash) uint32_t name_len = strlen(name); ext4_hash_info_t hinfo; rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_len, name); if (rc != EOK) { block_put(root_block); EXT4FS_DBG("hinfo initialization error"); return EXT4_ERR_BAD_DX_DIR; } // Hardcoded number 2 means maximum height of index tree defined in linux ext4_directory_dx_block_t dx_blocks[2]; ext4_directory_dx_block_t *dx_block, *dx_it; rc = ext4_directory_dx_get_leaf(&hinfo, parent, root_block, &dx_block, dx_blocks); if (rc != EOK) { EXT4FS_DBG("get leaf error"); rc = EXT4_ERR_BAD_DX_DIR; goto release_index; } // Try to insert to existing data block uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position); uint32_t leaf_block_addr; rc = ext4_filesystem_get_inode_data_block_index(parent, leaf_block_idx, &leaf_block_addr); if (rc != EOK) { goto release_index; } block_t *target_block; rc = block_get(&target_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE); if (rc != EOK) { goto release_index; } // Check if insert operation passed rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len); if (rc == EOK) { goto release_target_index; } // Check if there is needed to split index node // (and recursively also parent nodes) rc = ext4_directory_dx_split_index(parent, dx_blocks, dx_block); if (rc != EOK) { goto release_target_index; } // Split entries to two blocks (includes sorting by hash value) block_t *new_block = NULL; rc = ext4_directory_dx_split_data(parent, &hinfo, target_block, dx_block, &new_block); if (rc != EOK) { rc2 = rc; goto release_target_index; } // Where to save new entry uint32_t new_block_hash = ext4_directory_dx_entry_get_hash(dx_block->position + 1); if (hinfo.hash >= new_block_hash) { rc = ext4_directory_try_insert_entry(fs->superblock, new_block, child, name, name_len); } else { rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len); } // Cleanup rc = block_put(new_block); if (rc != EOK) { EXT4FS_DBG("error writing new block"); return rc; } // Cleanup operations release_target_index: rc2 = rc; rc = block_put(target_block); if (rc != EOK) { EXT4FS_DBG("error writing target block"); return rc; } release_index: if (rc != EOK) { rc2 = rc; } dx_it = dx_blocks; while (dx_it <= dx_block) { rc = block_put(dx_it->block); if (rc != EOK) { EXT4FS_DBG("error writing index block"); return rc; } dx_it++; } return rc2; } /** * @} */