Index: uspace/lib/ext4/libext4_directory_index.c =================================================================== --- uspace/lib/ext4/libext4_directory_index.c (revision 60b8b993fe5035f23414983af1484acf31c7e717) +++ uspace/lib/ext4/libext4_directory_index.c (revision b53a7335885c21fb5a52af874031e5d7a9db7648) @@ -606,4 +606,137 @@ +static int ext4_directory_dx_split_index(ext4_filesystem_t *fs, + 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) { + EXT4FS_DBG("need to split index block !!!"); + + 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); + + if ((levels > 0) && (root_limit == root_count)) { + EXT4FS_DBG("Directory index is full"); + return ENOSPC; + } + + uint32_t new_fblock; + uint32_t new_iblock; + rc = ext4_directory_append_block(fs, inode_ref, &new_fblock, &new_iblock); + if (rc != EOK) { + return rc; + } + + // New block allocated + block_t * new_block; + rc = block_get(&new_block, 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(fs->superblock); + + if (levels > 0) { + EXT4FS_DBG("split index leaf node"); + 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); + + memcpy((void *) new_entries, (void *) (entries + count_left), + count_right * sizeof(ext4_directory_dx_entry_t)); + + 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; + + } + + ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock); + + return block_put(new_block); + + } else { + EXT4FS_DBG("create second level"); + + 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 access path frame */ + 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; +} + int ext4_directory_dx_add_entry(ext4_filesystem_t *fs, ext4_inode_ref_t *parent, ext4_inode_ref_t *child, const char *name) @@ -658,4 +791,5 @@ } + rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len); if (rc == EOK) { @@ -665,109 +799,7 @@ EXT4FS_DBG("no free space found"); - uint32_t block_size = ext4_superblock_get_block_size(fs->superblock); - - ext4_directory_dx_entry_t *entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries; - uint16_t leaf_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries); - uint16_t leaf_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries); - - ext4_directory_dx_entry_t *root_entries = ((ext4_directory_dx_node_t *) dx_blocks[0].block->data)->entries; - - if (leaf_limit == leaf_count) { - EXT4FS_DBG("need to split index block !!!"); - - unsigned int levels = dx_block - dx_blocks; - - uint16_t root_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)root_entries); - uint16_t root_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)root_entries); - - if ((levels > 0) && (root_limit == root_count)) { - EXT4FS_DBG("Directory index is full"); - rc = ENOSPC; - goto release_target_index; - } - - uint32_t new_fblock; - uint32_t new_iblock; - rc = ext4_directory_append_block(fs, parent, &new_fblock, &new_iblock); - if (rc != EOK) { - goto release_target_index; - } - - // New block allocated - block_t * new_block; - rc = block_get(&new_block, fs->device, new_fblock, BLOCK_FLAGS_NOREAD); - if (rc != EOK) { - goto release_target_index; - } - - // Initialize block - memset(new_block->data, 0, block_size); - - ext4_directory_dx_node_t *new_node = new_block->data; - ext4_directory_dx_entry_t *new_entries = new_node->entries; - - if (levels > 0) { - EXT4FS_DBG("split index"); - 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); - - memcpy((void *) new_entries, (void *) (entries + count_left), - count_right * sizeof(ext4_directory_dx_entry_t)); - - 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->position = new_entries + position_index - count_left; - dx_block->entries = new_entries; - entries = dx_block->entries; - - dx_block->block->dirty = true; - block_put(dx_block->block); - dx_block->block = new_block; - } - - ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock); - - - } else { - EXT4FS_DBG("create second level"); - - 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_limit(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 access path frame */ - dx_block = dx_blocks + 1; - dx_block->position = dx_block->position - entries + new_entries; - dx_block->entries = new_entries; - entries = dx_block->entries; - dx_block->block = new_block; - } + rc = ext4_directory_dx_split_index(fs, parent, dx_blocks, dx_block); + if (rc != EOK) { + goto release_target_index; }