-/*\r
- * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)\r
- *\r
- *\r
- * HelenOS:\r
- * Copyright (c) 2012 Martin Sucha\r
- * Copyright (c) 2012 Frantisek Princ\r
- * All rights reserved.\r
- *\r
- * Redistribution and use in source and binary forms, with or without\r
- * modification, are permitted provided that the following conditions\r
- * are met:\r
- *\r
- * - Redistributions of source code must retain the above copyright\r
- * notice, this list of conditions and the following disclaimer.\r
- * - Redistributions in binary form must reproduce the above copyright\r
- * notice, this list of conditions and the following disclaimer in the\r
- * documentation and/or other materials provided with the distribution.\r
- * - The name of the author may not be used to endorse or promote products\r
- * derived from this software without specific prior written permission.\r
- *\r
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
- */\r
-\r
-/** @addtogroup lwext4\r
- * @{\r
- */\r
-/**\r
- * @file ext4_dir.h\r
- * @brief Directory handle procedures.\r
- */\r
-\r
-#include <ext4_config.h>\r
-#include <ext4_dir.h>\r
-#include <ext4_dir_idx.h>\r
-#include <ext4_inode.h>\r
-#include <ext4_fs.h>\r
-\r
-#include <string.h>\r
-\r
-uint32_t ext4_dir_entry_ll_get_inode(struct ext4_directory_entry_ll *de)\r
-{\r
- return to_le32(de->inode);\r
-}\r
-\r
-void ext4_dir_entry_ll_set_inode(struct ext4_directory_entry_ll *de,\r
- uint32_t inode)\r
-{\r
- de->inode = to_le32(inode);\r
-}\r
-\r
-\r
-uint16_t ext4_dir_entry_ll_get_entry_length(struct ext4_directory_entry_ll *de)\r
-{\r
- return to_le16(de->entry_length);\r
-}\r
-\r
-void ext4_dir_entry_ll_set_entry_length(struct ext4_directory_entry_ll *de,\r
- uint16_t len)\r
-{\r
- de->entry_length = to_le16(len);\r
-}\r
-\r
-\r
-uint16_t ext4_dir_entry_ll_get_name_length(struct ext4_sblock *sb,\r
- struct ext4_directory_entry_ll *de)\r
-{\r
- uint16_t v = de->name_length;\r
-\r
- if ((ext4_get32(sb, rev_level) == 0) &&\r
- (ext4_get32(sb, minor_rev_level) < 5))\r
- v |= ((uint16_t)de->name_length_high) << 8;\r
-\r
- return v;\r
-}\r
-void ext4_dir_entry_ll_set_name_length(struct ext4_sblock *sb,\r
- struct ext4_directory_entry_ll *de, uint16_t len)\r
-{\r
- de->name_length = (len << 8) >> 8;\r
-\r
- if ((ext4_get32(sb, rev_level) == 0) &&\r
- (ext4_get32(sb, minor_rev_level) < 5))\r
- de->name_length_high = len >> 8;\r
-}\r
-\r
-\r
-\r
-uint8_t ext4_dir_entry_ll_get_inode_type(struct ext4_sblock *sb,\r
- struct ext4_directory_entry_ll *de)\r
-{\r
- if ((ext4_get32(sb, rev_level) > 0) ||\r
- (ext4_get32(sb, minor_rev_level) >= 5))\r
- return de->inode_type;\r
-\r
- return EXT4_DIRECTORY_FILETYPE_UNKNOWN;\r
-}\r
-\r
-\r
-void ext4_dir_entry_ll_set_inode_type(struct ext4_sblock *sb,\r
- struct ext4_directory_entry_ll *de, uint8_t type)\r
-{\r
- if ((ext4_get32(sb, rev_level) > 0) ||\r
- (ext4_get32(sb, minor_rev_level) >= 5))\r
- de->inode_type = type;\r
-}\r
-\r
-/****************************************************************************/\r
-\r
-\r
-static int ext4_dir_iterator_set(struct ext4_directory_iterator *it,\r
- uint32_t block_size)\r
-{\r
- it->current = NULL;\r
-\r
- uint32_t offset_in_block = it->current_offset % block_size;\r
-\r
- /* Ensure proper alignment */\r
- if ((offset_in_block % 4) != 0)\r
- return EIO;\r
-\r
- /* Ensure that the core of the entry does not overflow the block */\r
- if (offset_in_block > block_size - 8)\r
- return EIO;\r
-\r
- struct ext4_directory_entry_ll *entry =\r
- (void *)(it->current_block.data + offset_in_block);\r
-\r
- /* Ensure that the whole entry does not overflow the block */\r
- uint16_t length = ext4_dir_entry_ll_get_entry_length(entry);\r
- if (offset_in_block + length > block_size)\r
- return EIO;\r
-\r
- /* Ensure the name length is not too large */\r
- if (ext4_dir_entry_ll_get_name_length(\r
- &it->inode_ref->fs->sb, entry) > length-8)\r
- return EIO;\r
-\r
- /* Everything OK - "publish" the entry */\r
- it->current = entry;\r
- return EOK;\r
-}\r
-\r
-static int ext4_dir_iterator_seek(struct ext4_directory_iterator *it,\r
- uint64_t pos)\r
-{\r
- uint64_t size = ext4_inode_get_size(&it->inode_ref->fs->sb,\r
- it->inode_ref->inode);\r
-\r
- /* The iterator is not valid until we seek to the desired position */\r
- it->current = NULL;\r
-\r
- /* Are we at the end? */\r
- if (pos >= size) {\r
- if (it->current_block.lb_id) {\r
-\r
- int rc = ext4_block_set(it->inode_ref->fs->bdev,\r
- &it->current_block);\r
- it->current_block.lb_id = 0;\r
-\r
- if (rc != EOK)\r
- return rc;\r
- }\r
-\r
- it->current_offset = pos;\r
- return EOK;\r
- }\r
-\r
- /* Compute next block address */\r
- uint32_t block_size =\r
- ext4_sb_get_block_size(&it->inode_ref->fs->sb);\r
- uint64_t current_block_idx = it->current_offset / block_size;\r
- uint64_t next_block_idx = pos / block_size;\r
-\r
- /*\r
- * If we don't have a block or are moving accross block boundary,\r
- * we need to get another block\r
- */\r
- if ((it->current_block.lb_id == 0) ||\r
- (current_block_idx != next_block_idx)) {\r
- if (it->current_block.lb_id) {\r
- int rc = ext4_block_set(it->inode_ref->fs->bdev, &it->current_block);\r
- it->current_block.lb_id = 0;\r
-\r
- if (rc != EOK)\r
- return rc;\r
- }\r
-\r
- uint32_t next_block_phys_idx;\r
- int rc = ext4_fs_get_inode_data_block_index(it->inode_ref,\r
- next_block_idx, &next_block_phys_idx);\r
- if (rc != EOK)\r
- return rc;\r
-\r
-\r
- rc = ext4_block_get(it->inode_ref->fs->bdev, &it->current_block,\r
- next_block_phys_idx);\r
- if (rc != EOK) {\r
- it->current_block.lb_id = 0;\r
- return rc;\r
- }\r
- }\r
-\r
- it->current_offset = pos;\r
-\r
- return ext4_dir_iterator_set(it, block_size);\r
-}\r
-\r
-\r
-int ext4_dir_iterator_init(struct ext4_directory_iterator *it,\r
- struct ext4_inode_ref *inode_ref, uint64_t pos)\r
-{\r
- it->inode_ref = inode_ref;\r
- it->current = 0;\r
- it->current_offset = 0;\r
- it->current_block.lb_id = 0;\r
-\r
- return ext4_dir_iterator_seek(it, pos);\r
-}\r
-\r
-int ext4_dir_iterator_next(struct ext4_directory_iterator *it)\r
-{\r
- uint16_t skip = ext4_dir_entry_ll_get_entry_length(it->current);\r
-\r
- return ext4_dir_iterator_seek(it, it->current_offset + skip);\r
-}\r
-\r
-int ext4_dir_iterator_fini(struct ext4_directory_iterator *it)\r
-{\r
- it->current = 0;\r
-\r
- if (it->current_block.lb_id)\r
- return ext4_block_set(it->inode_ref->fs->bdev, &it->current_block);\r
-\r
- return EOK;\r
-}\r
-\r
-void ext4_dir_write_entry(struct ext4_sblock *sb,\r
- struct ext4_directory_entry_ll *entry, uint16_t entry_len,\r
- struct ext4_inode_ref *child, const char *name, size_t name_len)\r
-{\r
- /* Check maximum entry length */\r
- uint32_t block_size = ext4_sb_get_block_size(sb);\r
- ext4_assert(entry_len <= block_size);\r
-\r
- /* Set basic attributes */\r
- ext4_dir_entry_ll_set_inode(entry, child->index);\r
- ext4_dir_entry_ll_set_entry_length(entry, entry_len);\r
- ext4_dir_entry_ll_set_name_length(sb, entry, name_len);\r
-\r
- /* Write name */\r
- memcpy(entry->name, name, name_len);\r
-\r
- /* Set type of entry */\r
- if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY))\r
- ext4_dir_entry_ll_set_inode_type(sb, entry,\r
- EXT4_DIRECTORY_FILETYPE_DIR);\r
- else\r
- ext4_dir_entry_ll_set_inode_type(sb, entry,\r
- EXT4_DIRECTORY_FILETYPE_REG_FILE);\r
-}\r
-\r
-int ext4_dir_add_entry(struct ext4_inode_ref *parent, const char *name,\r
- uint32_t name_len, struct ext4_inode_ref *child)\r
-{\r
- struct ext4_fs *fs = parent->fs;\r
-\r
-#if CONFIG_DIR_INDEX_ENABLE\r
- /* Index adding (if allowed) */\r
- if ((ext4_sb_check_feature_compatible(&fs->sb,\r
- EXT4_FEATURE_COMPAT_DIR_INDEX)) &&\r
- (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {\r
- int rc = ext4_dir_dx_add_entry(parent, child, name);\r
-\r
- /* Check if index is not corrupted */\r
- if (rc != EXT4_ERR_BAD_DX_DIR) {\r
- if (rc != EOK)\r
- return rc;\r
-\r
- return EOK;\r
- }\r
-\r
- /* Needed to clear dir index flag if corrupted */\r
- ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);\r
- parent->dirty = true;\r
- }\r
-#endif\r
-\r
- /* Linear algorithm */\r
- uint32_t iblock = 0;\r
- uint32_t fblock = 0;\r
- uint32_t block_size = ext4_sb_get_block_size(&fs->sb);\r
- uint32_t inode_size = ext4_inode_get_size(&fs->sb, parent->inode);\r
- uint32_t total_blocks = inode_size / block_size;\r
-\r
-\r
- /* Find block, where is space for new entry and try to add */\r
- bool success = false;\r
- for (iblock = 0; iblock < total_blocks; ++iblock) {\r
- int rc = ext4_fs_get_inode_data_block_index(parent,\r
- iblock, &fblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
-\r
- struct ext4_block block;\r
- rc = ext4_block_get(fs->bdev, &block, fblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- /* If adding is successful, function can finish */\r
- rc = ext4_dir_try_insert_entry(&fs->sb, &block,\r
- child, name, name_len);\r
- if (rc == EOK)\r
- success = true;\r
-\r
- rc = ext4_block_set(fs->bdev, &block);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- if (success)\r
- return EOK;\r
- }\r
-\r
- /* No free block found - needed to allocate next data block */\r
-\r
- iblock = 0;\r
- fblock = 0;\r
- int rc = ext4_fs_append_inode_block(parent, &fblock, &iblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- /* Load new block */\r
- struct ext4_block new_block;\r
-\r
- rc = ext4_block_get(fs->bdev, &new_block, fblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- /* Fill block with zeroes */\r
- memset(new_block.data, 0, block_size);\r
- struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;\r
- ext4_dir_write_entry(&fs->sb, block_entry, block_size,\r
- child, name, name_len);\r
-\r
- /* Save new block */\r
- new_block.dirty = true;\r
- rc = ext4_block_set(fs->bdev, &new_block);\r
-\r
- return rc;\r
-}\r
-\r
-int ext4_dir_find_entry(struct ext4_directory_search_result *result,\r
- struct ext4_inode_ref *parent, const char *name, uint32_t name_len)\r
-{\r
- struct ext4_sblock *sb = &parent->fs->sb;\r
-\r
-\r
-#if CONFIG_DIR_INDEX_ENABLE\r
- /* Index search */\r
- if ((ext4_sb_check_feature_compatible(sb,\r
- EXT4_FEATURE_COMPAT_DIR_INDEX)) &&\r
- (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {\r
- int rc = ext4_dir_dx_find_entry(result, parent, name_len,\r
- name);\r
-\r
- /* Check if index is not corrupted */\r
- if (rc != EXT4_ERR_BAD_DX_DIR) {\r
- if (rc != EOK)\r
- return rc;\r
-\r
- return EOK;\r
- }\r
-\r
- /* Needed to clear dir index flag if corrupted */\r
- ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);\r
- parent->dirty = true;\r
- }\r
-#endif\r
-\r
- /* Linear algorithm */\r
-\r
- uint32_t iblock;\r
- uint32_t fblock;\r
- uint32_t block_size = ext4_sb_get_block_size(sb);\r
- uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);\r
- uint32_t total_blocks = inode_size / block_size;\r
-\r
- /* Walk through all data blocks */\r
- for (iblock = 0; iblock < total_blocks; ++iblock) {\r
- /* Load block address */\r
- int rc = ext4_fs_get_inode_data_block_index(parent, iblock,\r
- &fblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- /* Load data block */\r
- struct ext4_block block;\r
- rc = ext4_block_get( parent->fs->bdev, &block, fblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- /* Try to find entry in block */\r
- struct ext4_directory_entry_ll *res_entry;\r
- rc = ext4_dir_find_in_block(&block, sb, name_len, name,\r
- &res_entry);\r
- if (rc == EOK) {\r
- result->block = block;\r
- result->dentry = res_entry;\r
- return EOK;\r
- }\r
-\r
- /* Entry not found - put block and continue to the next block */\r
-\r
- rc = ext4_block_set(parent->fs->bdev, &block);\r
- if (rc != EOK)\r
- return rc;\r
- }\r
-\r
- /* Entry was not found */\r
-\r
- result->block.lb_id = 0;\r
- result->dentry = NULL;\r
-\r
- return ENOENT;\r
-}\r
-\r
-int ext4_dir_remove_entry(struct ext4_inode_ref *parent, const char *name,\r
- uint32_t name_len)\r
-{\r
- /* Check if removing from directory */\r
- if (!ext4_inode_is_type(&parent->fs->sb, parent->inode,\r
- EXT4_INODE_MODE_DIRECTORY))\r
- return ENOTDIR;\r
-\r
- /* Try to find entry */\r
- struct ext4_directory_search_result result;\r
- int rc = ext4_dir_find_entry(&result, parent, name, name_len);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- /* Invalidate entry */\r
- ext4_dir_entry_ll_set_inode(result.dentry, 0);\r
-\r
- /* Store entry position in block */\r
- uint32_t pos = (uint8_t *) result.dentry - result.block.data;\r
-\r
- /*\r
- * If entry is not the first in block, it must be merged\r
- * with previous entry\r
- */\r
- if (pos != 0) {\r
- uint32_t offset = 0;\r
-\r
- /* Start from the first entry in block */\r
- struct ext4_directory_entry_ll *tmp_dentry = (void *)result.block.data;\r
- uint16_t tmp_dentry_length =\r
- ext4_dir_entry_ll_get_entry_length(tmp_dentry);\r
-\r
- /* Find direct predecessor of removed entry */\r
- while ((offset + tmp_dentry_length) < pos) {\r
- offset +=\r
- ext4_dir_entry_ll_get_entry_length(tmp_dentry);\r
- tmp_dentry = (void *)(result.block.data + offset);\r
- tmp_dentry_length =\r
- ext4_dir_entry_ll_get_entry_length(tmp_dentry);\r
- }\r
-\r
- ext4_assert(tmp_dentry_length + offset == pos);\r
-\r
- /* Add to removed entry length to predecessor's length */\r
- uint16_t del_entry_length =\r
- ext4_dir_entry_ll_get_entry_length(result.dentry);\r
- ext4_dir_entry_ll_set_entry_length(tmp_dentry,\r
- tmp_dentry_length + del_entry_length);\r
- }\r
-\r
- result.block.dirty = true;\r
-\r
- return ext4_dir_destroy_result(parent, &result);\r
-}\r
-\r
-int ext4_dir_try_insert_entry(struct ext4_sblock *sb,\r
- struct ext4_block *target_block, struct ext4_inode_ref *child,\r
- const char *name, uint32_t name_len)\r
-{\r
- /* Compute required length entry and align it to 4 bytes */\r
- uint32_t block_size = ext4_sb_get_block_size(sb);\r
- uint16_t required_len = sizeof(struct ext4_fake_directory_entry) + name_len;\r
-\r
- if ((required_len % 4) != 0)\r
- required_len += 4 - (required_len % 4);\r
-\r
- /* Initialize pointers, stop means to upper bound */\r
- struct ext4_directory_entry_ll *dentry = (void *)target_block->data;\r
- struct ext4_directory_entry_ll *stop =\r
- (void *)(target_block->data + block_size);\r
-\r
- /*\r
- * Walk through the block and check for invalid entries\r
- * or entries with free space for new entry\r
- */\r
- while (dentry < stop) {\r
- uint32_t inode = ext4_dir_entry_ll_get_inode(dentry);\r
- uint16_t rec_len = ext4_dir_entry_ll_get_entry_length(dentry);\r
-\r
- /* If invalid and large enough entry, use it */\r
- if ((inode == 0) && (rec_len >= required_len)) {\r
- ext4_dir_write_entry(sb, dentry, rec_len, child,\r
- name, name_len);\r
- target_block->dirty = true;\r
-\r
- return EOK;\r
- }\r
-\r
- /* Valid entry, try to split it */\r
- if (inode != 0) {\r
- uint16_t used_name_len =\r
- ext4_dir_entry_ll_get_name_length(sb, dentry);\r
-\r
- uint16_t used_space =\r
- sizeof(struct ext4_fake_directory_entry) + used_name_len;\r
-\r
- if ((used_name_len % 4) != 0)\r
- used_space += 4 - (used_name_len % 4);\r
-\r
- uint16_t free_space = rec_len - used_space;\r
-\r
- /* There is free space for new entry */\r
- if (free_space >= required_len) {\r
- /* Cut tail of current entry */\r
- ext4_dir_entry_ll_set_entry_length(dentry, used_space);\r
- struct ext4_directory_entry_ll *new_entry =\r
- (void *) dentry + used_space;\r
- ext4_dir_write_entry(sb, new_entry,\r
- free_space, child, name, name_len);\r
-\r
- target_block->dirty = true;\r
-\r
- return EOK;\r
- }\r
- }\r
-\r
- /* Jump to the next entry */\r
- dentry = (void *) dentry + rec_len;\r
- }\r
-\r
- /* No free space found for new entry */\r
- return ENOSPC;\r
-}\r
-\r
-\r
-int ext4_dir_find_in_block(struct ext4_block *block, struct ext4_sblock *sb,\r
- size_t name_len, const char *name,\r
- struct ext4_directory_entry_ll **res_entry)\r
-{\r
- /* Start from the first entry in block */\r
- struct ext4_directory_entry_ll *dentry =\r
- (struct ext4_directory_entry_ll *) block->data;\r
-\r
- /* Set upper bound for cycling */\r
- uint8_t *addr_limit = block->data + ext4_sb_get_block_size(sb);\r
-\r
- /* Walk through the block and check entries */\r
- while ((uint8_t *) dentry < addr_limit) {\r
- /* Termination condition */\r
- if ((uint8_t *) dentry + name_len > addr_limit)\r
- break;\r
-\r
- /* Valid entry - check it */\r
- if (dentry->inode != 0) {\r
- /* For more effectivity compare firstly only lengths */\r
- if (ext4_dir_entry_ll_get_name_length(sb, dentry) ==\r
- name_len) {\r
- /* Compare names */\r
- if (memcmp((uint8_t *) name, dentry->name, name_len) == 0) {\r
- *res_entry = dentry;\r
- return EOK;\r
- }\r
- }\r
- }\r
-\r
- uint16_t dentry_len =\r
- ext4_dir_entry_ll_get_entry_length(dentry);\r
-\r
- /* Corrupted entry */\r
- if (dentry_len == 0)\r
- return EINVAL;\r
-\r
- /* Jump to next entry */\r
- dentry = (struct ext4_directory_entry_ll *)\r
- ((uint8_t *) dentry + dentry_len);\r
- }\r
-\r
- /* Entry not found */\r
- return ENOENT;\r
-}\r
-\r
-int ext4_dir_destroy_result(struct ext4_inode_ref *parent,\r
- struct ext4_directory_search_result *result)\r
-{\r
- if (result->block.lb_id)\r
- return ext4_block_set(parent->fs->bdev, &result->block);\r
-\r
- return EOK;\r
-}\r
-\r
-/**\r
- * @}\r
- */\r
+/*
+ * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
+ *
+ *
+ * HelenOS:
+ * Copyright (c) 2012 Martin Sucha
+ * 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 lwext4
+ * @{
+ */
+/**
+ * @file ext4_dir.h
+ * @brief Directory handle procedures.
+ */
+
+#include "ext4_config.h"
+#include "ext4_dir.h"
+#include "ext4_dir_idx.h"
+#include "ext4_inode.h"
+#include "ext4_fs.h"
+
+#include <string.h>
+
+/****************************************************************************/
+
+/**@brief Do some checks before returning iterator.
+ * @param it Iterator to be checked
+ * @param block_size Size of data block
+ * @return Error code
+ */
+static int ext4_dir_iterator_set(struct ext4_directory_iterator *it,
+ uint32_t block_size)
+{
+ it->current = NULL;
+
+ uint32_t offset_in_block = it->current_offset % block_size;
+
+ /* Ensure proper alignment */
+ if ((offset_in_block % 4) != 0)
+ return EIO;
+
+ /* Ensure that the core of the entry does not overflow the block */
+ if (offset_in_block > block_size - 8)
+ return EIO;
+
+ struct ext4_directory_entry_ll *entry =
+ (void *)(it->current_block.data + offset_in_block);
+
+ /* Ensure that the whole entry does not overflow the block */
+ uint16_t length = ext4_dir_entry_ll_get_entry_length(entry);
+ if (offset_in_block + length > block_size)
+ return EIO;
+
+ /* Ensure the name length is not too large */
+ if (ext4_dir_entry_ll_get_name_length(&it->inode_ref->fs->sb, entry) >
+ length - 8)
+ return EIO;
+
+ /* Everything OK - "publish" the entry */
+ it->current = entry;
+ return EOK;
+}
+
+/**@brief Seek to next valid directory entry.
+ * Here can be jumped to the next data block.
+ * @param it Initialized iterator
+ * @param pos Position of the next entry
+ * @return Error code
+ */
+static int ext4_dir_iterator_seek(struct ext4_directory_iterator *it,
+ uint64_t pos)
+{
+ uint64_t size =
+ ext4_inode_get_size(&it->inode_ref->fs->sb, it->inode_ref->inode);
+
+ /* The iterator is not valid until we seek to the desired position */
+ it->current = NULL;
+
+ /* Are we at the end? */
+ if (pos >= size) {
+ if (it->current_block.lb_id) {
+
+ int rc = ext4_block_set(it->inode_ref->fs->bdev,
+ &it->current_block);
+ it->current_block.lb_id = 0;
+
+ if (rc != EOK)
+ return rc;
+ }
+
+ it->current_offset = pos;
+ return EOK;
+ }
+
+ /* Compute next block address */
+ uint32_t block_size = ext4_sb_get_block_size(&it->inode_ref->fs->sb);
+ uint64_t current_block_idx = it->current_offset / block_size;
+ uint64_t next_block_idx = pos / block_size;
+
+ /*
+ * If we don't have a block or are moving across block boundary,
+ * we need to get another block
+ */
+ if ((it->current_block.lb_id == 0) ||
+ (current_block_idx != next_block_idx)) {
+ if (it->current_block.lb_id) {
+ int rc = ext4_block_set(it->inode_ref->fs->bdev,
+ &it->current_block);
+ it->current_block.lb_id = 0;
+
+ if (rc != EOK)
+ return rc;
+ }
+
+ uint32_t next_block_phys_idx;
+ int rc = ext4_fs_get_inode_data_block_index(
+ it->inode_ref, next_block_idx, &next_block_phys_idx);
+ if (rc != EOK)
+ return rc;
+
+ rc = ext4_block_get(it->inode_ref->fs->bdev, &it->current_block,
+ next_block_phys_idx);
+ if (rc != EOK) {
+ it->current_block.lb_id = 0;
+ return rc;
+ }
+ }
+
+ it->current_offset = pos;
+
+ return ext4_dir_iterator_set(it, block_size);
+}
+
+int ext4_dir_iterator_init(struct ext4_directory_iterator *it,
+ struct ext4_inode_ref *inode_ref, uint64_t pos)
+{
+ it->inode_ref = inode_ref;
+ it->current = 0;
+ it->current_offset = 0;
+ it->current_block.lb_id = 0;
+
+ return ext4_dir_iterator_seek(it, pos);
+}
+
+int ext4_dir_iterator_next(struct ext4_directory_iterator *it)
+{
+ int r = EOK;
+ uint16_t skip;
+
+ while (r == EOK) {
+ skip = ext4_dir_entry_ll_get_entry_length(it->current);
+ r = ext4_dir_iterator_seek(it, it->current_offset + skip);
+
+ if (!it->current)
+ break;
+ /*Skip NULL referenced entry*/
+ if (ext4_dir_entry_ll_get_inode(it->current) != 0)
+ break;
+ }
+
+ return r;
+}
+
+int ext4_dir_iterator_fini(struct ext4_directory_iterator *it)
+{
+ it->current = 0;
+
+ if (it->current_block.lb_id)
+ return ext4_block_set(it->inode_ref->fs->bdev,
+ &it->current_block);
+
+ return EOK;
+}
+
+void ext4_dir_write_entry(struct ext4_sblock *sb,
+ struct ext4_directory_entry_ll *entry,
+ uint16_t entry_len, struct ext4_inode_ref *child,
+ const char *name, size_t name_len)
+{
+ /* Check maximum entry length */
+ ext4_assert(entry_len <= ext4_sb_get_block_size(sb));
+
+ /* Set type of entry */
+ switch (ext4_inode_type(sb, child->inode)) {
+ case EXT4_INODE_MODE_DIRECTORY:
+ ext4_dir_entry_ll_set_inode_type(sb, entry,
+ EXT4_DIRENTRY_DIR);
+ break;
+ case EXT4_INODE_MODE_FILE:
+ ext4_dir_entry_ll_set_inode_type(
+ sb, entry, EXT4_DIRENTRY_REG_FILE);
+ break;
+ case EXT4_INODE_MODE_SOFTLINK:
+ ext4_dir_entry_ll_set_inode_type(
+ sb, entry, EXT4_DIRENTRY_SYMLINK);
+ break;
+ default:
+ /* FIXME: right now we only support 3 inode type. */
+ ext4_assert(0);
+ }
+
+ /* Set basic attributes */
+ ext4_dir_entry_ll_set_inode(entry, child->index);
+ ext4_dir_entry_ll_set_entry_length(entry, entry_len);
+ ext4_dir_entry_ll_set_name_length(sb, entry, name_len);
+
+ /* Write name */
+ memcpy(entry->name, name, name_len);
+}
+
+int ext4_dir_add_entry(struct ext4_inode_ref *parent, const char *name,
+ uint32_t name_len, struct ext4_inode_ref *child)
+{
+ struct ext4_fs *fs = parent->fs;
+
+#if CONFIG_DIR_INDEX_ENABLE
+ /* Index adding (if allowed) */
+ if ((ext4_sb_has_feature_compatible(&fs->sb,
+ EXT4_FEATURE_COMPAT_DIR_INDEX)) &&
+ (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
+ int rc = ext4_dir_dx_add_entry(parent, child, name);
+
+ /* Check if index is not corrupted */
+ if (rc != EXT4_ERR_BAD_DX_DIR) {
+ if (rc != EOK)
+ return rc;
+
+ return EOK;
+ }
+
+ /* Needed to clear dir index flag if corrupted */
+ ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
+ parent->dirty = true;
+ }
+#endif
+
+ /* Linear algorithm */
+ uint32_t iblock = 0;
+ uint32_t fblock = 0;
+ uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
+ uint32_t inode_size = ext4_inode_get_size(&fs->sb, parent->inode);
+ uint32_t total_blocks = inode_size / block_size;
+
+ /* Find block, where is space for new entry and try to add */
+ bool success = false;
+ for (iblock = 0; iblock < total_blocks; ++iblock) {
+ int rc =
+ ext4_fs_get_inode_data_block_index(parent, iblock, &fblock);
+ if (rc != EOK)
+ return rc;
+
+ struct ext4_block block;
+ rc = ext4_block_get(fs->bdev, &block, fblock);
+ if (rc != EOK)
+ return rc;
+
+ /* If adding is successful, function can finish */
+ rc = ext4_dir_try_insert_entry(&fs->sb, &block, child, name,
+ name_len);
+ if (rc == EOK)
+ success = true;
+
+ rc = ext4_block_set(fs->bdev, &block);
+ if (rc != EOK)
+ return rc;
+
+ if (success)
+ return EOK;
+ }
+
+ /* No free block found - needed to allocate next data block */
+
+ iblock = 0;
+ fblock = 0;
+ int rc = ext4_fs_append_inode_block(parent, &fblock, &iblock);
+ if (rc != EOK)
+ return rc;
+
+ /* Load new block */
+ struct ext4_block new_block;
+
+ rc = ext4_block_get(fs->bdev, &new_block, fblock);
+ if (rc != EOK)
+ return rc;
+
+ /* Fill block with zeroes */
+ memset(new_block.data, 0, block_size);
+ struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;
+ ext4_dir_write_entry(&fs->sb, block_entry, block_size, child, name,
+ name_len);
+
+ /* Save new block */
+ new_block.dirty = true;
+ rc = ext4_block_set(fs->bdev, &new_block);
+
+ return rc;
+}
+
+int ext4_dir_find_entry(struct ext4_directory_search_result *result,
+ struct ext4_inode_ref *parent, const char *name,
+ uint32_t name_len)
+{
+ struct ext4_sblock *sb = &parent->fs->sb;
+
+#if CONFIG_DIR_INDEX_ENABLE
+ /* Index search */
+ if ((ext4_sb_has_feature_compatible(sb,
+ EXT4_FEATURE_COMPAT_DIR_INDEX)) &&
+ (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
+ int rc = ext4_dir_dx_find_entry(result, parent, name_len, name);
+
+ /* Check if index is not corrupted */
+ if (rc != EXT4_ERR_BAD_DX_DIR) {
+ if (rc != EOK)
+ return rc;
+
+ return EOK;
+ }
+
+ /* Needed to clear dir index flag if corrupted */
+ ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
+ parent->dirty = true;
+ }
+#endif
+
+ /* Linear algorithm */
+
+ uint32_t iblock;
+ uint32_t fblock;
+ uint32_t block_size = ext4_sb_get_block_size(sb);
+ uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
+ uint32_t total_blocks = inode_size / block_size;
+
+ /* Walk through all data blocks */
+ for (iblock = 0; iblock < total_blocks; ++iblock) {
+ /* Load block address */
+ int rc =
+ ext4_fs_get_inode_data_block_index(parent, iblock, &fblock);
+ if (rc != EOK)
+ return rc;
+
+ /* Load data block */
+ struct ext4_block block;
+ rc = ext4_block_get(parent->fs->bdev, &block, fblock);
+ if (rc != EOK)
+ return rc;
+
+ /* Try to find entry in block */
+ struct ext4_directory_entry_ll *res_entry;
+ rc = ext4_dir_find_in_block(&block, sb, name_len, name,
+ &res_entry);
+ if (rc == EOK) {
+ result->block = block;
+ result->dentry = res_entry;
+ return EOK;
+ }
+
+ /* Entry not found - put block and continue to the next block */
+
+ rc = ext4_block_set(parent->fs->bdev, &block);
+ if (rc != EOK)
+ return rc;
+ }
+
+ /* Entry was not found */
+
+ result->block.lb_id = 0;
+ result->dentry = NULL;
+
+ return ENOENT;
+}
+
+int ext4_dir_remove_entry(struct ext4_inode_ref *parent, const char *name,
+ uint32_t name_len)
+{
+ /* Check if removing from directory */
+ if (!ext4_inode_is_type(&parent->fs->sb, parent->inode,
+ EXT4_INODE_MODE_DIRECTORY))
+ return ENOTDIR;
+
+ /* Try to find entry */
+ struct ext4_directory_search_result result;
+ int rc = ext4_dir_find_entry(&result, parent, name, name_len);
+ if (rc != EOK)
+ return rc;
+
+ /* Invalidate entry */
+ ext4_dir_entry_ll_set_inode(result.dentry, 0);
+
+ /* Store entry position in block */
+ uint32_t pos = (uint8_t *)result.dentry - result.block.data;
+
+ /*
+ * If entry is not the first in block, it must be merged
+ * with previous entry
+ */
+ if (pos != 0) {
+ uint32_t offset = 0;
+
+ /* Start from the first entry in block */
+ struct ext4_directory_entry_ll *tmp_dentry =
+ (void *)result.block.data;
+ uint16_t tmp_dentry_length =
+ ext4_dir_entry_ll_get_entry_length(tmp_dentry);
+
+ /* Find direct predecessor of removed entry */
+ while ((offset + tmp_dentry_length) < pos) {
+ offset +=
+ ext4_dir_entry_ll_get_entry_length(tmp_dentry);
+ tmp_dentry = (void *)(result.block.data + offset);
+ tmp_dentry_length =
+ ext4_dir_entry_ll_get_entry_length(tmp_dentry);
+ }
+
+ ext4_assert(tmp_dentry_length + offset == pos);
+
+ /* Add to removed entry length to predecessor's length */
+ uint16_t del_entry_length =
+ ext4_dir_entry_ll_get_entry_length(result.dentry);
+ ext4_dir_entry_ll_set_entry_length(
+ tmp_dentry, tmp_dentry_length + del_entry_length);
+ }
+
+ result.block.dirty = true;
+
+ return ext4_dir_destroy_result(parent, &result);
+}
+
+int ext4_dir_try_insert_entry(struct ext4_sblock *sb,
+ struct ext4_block *target_block,
+ struct ext4_inode_ref *child, const char *name,
+ uint32_t name_len)
+{
+ /* Compute required length entry and align it to 4 bytes */
+ uint32_t block_size = ext4_sb_get_block_size(sb);
+ uint16_t required_len =
+ sizeof(struct ext4_fake_directory_entry) + name_len;
+
+ if ((required_len % 4) != 0)
+ required_len += 4 - (required_len % 4);
+
+ /* Initialize pointers, stop means to upper bound */
+ struct ext4_directory_entry_ll *dentry = (void *)target_block->data;
+ struct ext4_directory_entry_ll *stop =
+ (void *)(target_block->data + block_size);
+
+ /*
+ * Walk through the block and check for invalid entries
+ * or entries with free space for new entry
+ */
+ while (dentry < stop) {
+ uint32_t inode = ext4_dir_entry_ll_get_inode(dentry);
+ uint16_t rec_len = ext4_dir_entry_ll_get_entry_length(dentry);
+
+ /* If invalid and large enough entry, use it */
+ if ((inode == 0) && (rec_len >= required_len)) {
+ ext4_dir_write_entry(sb, dentry, rec_len, child, name,
+ name_len);
+ target_block->dirty = true;
+
+ return EOK;
+ }
+
+ /* Valid entry, try to split it */
+ if (inode != 0) {
+ uint16_t used_name_len =
+ ext4_dir_entry_ll_get_name_length(sb, dentry);
+
+ uint16_t used_space =
+ sizeof(struct ext4_fake_directory_entry) +
+ used_name_len;
+
+ if ((used_name_len % 4) != 0)
+ used_space += 4 - (used_name_len % 4);
+
+ uint16_t free_space = rec_len - used_space;
+
+ /* There is free space for new entry */
+ if (free_space >= required_len) {
+ /* Cut tail of current entry */
+ ext4_dir_entry_ll_set_entry_length(dentry,
+ used_space);
+ struct ext4_directory_entry_ll *new_entry =
+ (void *)((uint8_t *)dentry + used_space);
+ ext4_dir_write_entry(sb, new_entry, free_space,
+ child, name, name_len);
+
+ target_block->dirty = true;
+ return EOK;
+ }
+ }
+
+ /* Jump to the next entry */
+ dentry = (void *)((uint8_t *)dentry + rec_len);
+ }
+
+ /* No free space found for new entry */
+ return ENOSPC;
+}
+
+int ext4_dir_find_in_block(struct ext4_block *block, struct ext4_sblock *sb,
+ size_t name_len, const char *name,
+ struct ext4_directory_entry_ll **res_entry)
+{
+ /* Start from the first entry in block */
+ struct ext4_directory_entry_ll *dentry =
+ (struct ext4_directory_entry_ll *)block->data;
+
+ /* Set upper bound for cycling */
+ uint8_t *addr_limit = block->data + ext4_sb_get_block_size(sb);
+
+ /* Walk through the block and check entries */
+ while ((uint8_t *)dentry < addr_limit) {
+ /* Termination condition */
+ if ((uint8_t *)dentry + name_len > addr_limit)
+ break;
+
+ /* Valid entry - check it */
+ if (ext4_dir_entry_ll_get_inode(dentry) != 0) {
+ /* For more efficient compare only lengths firstly*/
+ if (ext4_dir_entry_ll_get_name_length(sb, dentry) ==
+ name_len) {
+ /* Compare names */
+ if (memcmp((uint8_t *)name, dentry->name,
+ name_len) == 0) {
+ *res_entry = dentry;
+ return EOK;
+ }
+ }
+ }
+
+ uint16_t dentry_len =
+ ext4_dir_entry_ll_get_entry_length(dentry);
+
+ /* Corrupted entry */
+ if (dentry_len == 0)
+ return EINVAL;
+
+ /* Jump to next entry */
+ dentry = (struct ext4_directory_entry_ll *)((uint8_t *)dentry +
+ dentry_len);
+ }
+
+ /* Entry not found */
+ return ENOENT;
+}
+
+int ext4_dir_destroy_result(struct ext4_inode_ref *parent,
+ struct ext4_directory_search_result *result)
+{
+ if (result->block.lb_id)
+ return ext4_block_set(parent->fs->bdev, &result->block);
+
+ return EOK;
+}
+
+/**
+ * @}
+ */
projects / lwext4.git / blobdiff