lwext4/ext4_dir_idx.c

   1 /*\r
   2  * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)\r
   3  * All rights reserved.\r
   4  *\r
   5  * Redistribution and use in source and binary forms, with or without\r
   6  * modification, are permitted provided that the following conditions\r
   7  * are met:\r
   8  *\r
   9  * - Redistributions of source code must retain the above copyright\r
  10  *   notice, this list of conditions and the following disclaimer.\r
  11  * - Redistributions in binary form must reproduce the above copyright\r
  12  *   notice, this list of conditions and the following disclaimer in the\r
  13  *   documentation and/or other materials provided with the distribution.\r
  14  * - The name of the author may not be used to endorse or promote products\r
  15  *   derived from this software without specific prior written permission.\r
  16  *\r
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
  27  */\r
  28 \r
  29 /** @addtogroup lwext4\r
  30  * @{\r
  31  */\r
  32 /**\r
  33  * @file  ext4_dir_idx.c\r
  34  * @brief Directory indexing procedures.\r
  35  */\r
  36 \r
  37 #include <ext4_config.h>\r
  38 #include <ext4_dir_idx.h>\r
  39 #include <ext4_dir.h>\r
  40 #include <ext4_blockdev.h>\r
  41 #include <ext4_fs.h>\r
  42 #include <ext4_super.h>\r
  43 #include <ext4_hash.h>\r
  44 \r
  45 #include <string.h>\r
  46 #include <stdlib.h>\r
  47 \r
  48 /**@brief Get hash version used in directory index.\r
  49  * @param root_info Pointer to root info structure of index\r
  50  * @return Hash algorithm version\r
  51  */\r
  52 static inline uint8_t ext4_dir_dx_root_info_get_hash_version(\r
  53     struct ext4_directory_dx_root_info *root_info)\r
  54 {\r
  55     return root_info->hash_version;\r
  56 }\r
  57 \r
  58 /**@brief Set hash version, that will be used in directory index.\r
  59  * @param root_info Pointer to root info structure of index\r
  60  * @param v Hash algorithm version\r
  61  */\r
  62 static inline void ext4_dir_dx_root_info_set_hash_version(\r
  63     struct ext4_directory_dx_root_info *root_info, uint8_t v)\r
  64 {\r
  65     root_info->hash_version = v;\r
  66 }\r
  67 \r
  68 /**@brief Get length of root_info structure in bytes.\r
  69  * @param root_info Pointer to root info structure of index\r
  70  * @return Length of the structure\r
  71  */\r
  72 static inline uint8_t ext4_dir_dx_root_info_get_info_length(\r
  73     struct ext4_directory_dx_root_info *root_info)\r
  74 {\r
  75     return root_info->info_length;\r
  76 }\r
  77 \r
  78 /**@brief Set length of root_info structure in bytes.\r
  79  * @param root_info   Pointer to root info structure of index\r
  80  * @param info_length Length of the structure\r
  81  */\r
  82 static inline void ext4_dir_dx_root_info_set_info_length(\r
  83     struct ext4_directory_dx_root_info *root_info, uint8_t len)\r
  84 {\r
  85     root_info->info_length = len;\r
  86 }\r
  87 \r
  88 /**@brief Get number of indirect levels of HTree.\r
  89  * @param root_info Pointer to root info structure of index\r
  90  * @return Height of HTree (actually only 0 or 1)\r
  91  */\r
  92 static inline uint8_t ext4_dir_dx_root_info_get_indirect_levels(\r
  93     struct ext4_directory_dx_root_info *root_info)\r
  94 {\r
  95     return root_info->indirect_levels;\r
  96 }\r
  97 \r
  98 /**@brief Set number of indirect levels of HTree.\r
  99  * @param root_info Pointer to root info structure of index\r
 100  * @param lvl Height of HTree (actually only 0 or 1)\r
 101  */\r
 102 static inline void ext4_dir_dx_root_info_set_indirect_levels(\r
 103     struct ext4_directory_dx_root_info *root_info, uint8_t lvl)\r
 104 {\r
 105     root_info->indirect_levels = lvl;\r
 106 }\r
 107 \r
 108 /**@brief Get maximum number of index node entries.\r
 109  * @param climit Pointer to counlimit structure\r
 110  * @return Maximum of entries in node\r
 111  */\r
 112 static inline uint16_t\r
 113 ext4_dir_dx_countlimit_get_limit(struct ext4_directory_dx_countlimit *climit)\r
 114 {\r
 115     return to_le16(climit->limit);\r
 116 }\r
 117 \r
 118 /**@brief Set maximum number of index node entries.\r
 119  * @param climit Pointer to counlimit structure\r
 120  * @param limit Maximum of entries in node\r
 121  */\r
 122 static inline void\r
 123 ext4_dir_dx_countlimit_set_limit(struct ext4_directory_dx_countlimit *climit,\r
 124                                  uint16_t limit)\r
 125 {\r
 126     climit->limit = to_le16(limit);\r
 127 }\r
 128 \r
 129 /**@brief Get current number of index node entries.\r
 130  * @param climit Pointer to counlimit structure\r
 131  * @return Number of entries in node\r
 132  */\r
 133 static inline uint16_t\r
 134 ext4_dir_dx_countlimit_get_count(struct ext4_directory_dx_countlimit *climit)\r
 135 {\r
 136     return to_le16(climit->count);\r
 137 }\r
 138 \r
 139 /**@brief Set current number of index node entries.\r
 140  * @param climit Pointer to counlimit structure\r
 141  * @param count Number of entries in node\r
 142  */\r
 143 static inline void\r
 144 ext4_dir_dx_countlimit_set_count(struct ext4_directory_dx_countlimit *climit,\r
 145                                  uint16_t count)\r
 146 {\r
 147     climit->count = to_le16(count);\r
 148 }\r
 149 \r
 150 /**@brief Get hash value of index entry.\r
 151  * @param entry Pointer to index entry\r
 152  * @return Hash value\r
 153  */\r
 154 static inline uint32_t\r
 155 ext4_dir_dx_entry_get_hash(struct ext4_directory_dx_entry *entry)\r
 156 {\r
 157     return to_le32(entry->hash);\r
 158 }\r
 159 \r
 160 /**@brief Set hash value of index entry.\r
 161  * @param entry Pointer to index entry\r
 162  * @param hash  Hash value\r
 163  */\r
 164 static inline void\r
 165 ext4_dir_dx_entry_set_hash(struct ext4_directory_dx_entry *entry, uint32_t hash)\r
 166 {\r
 167     entry->hash = to_le32(hash);\r
 168 }\r
 169 \r
 170 /**@brief Get block address where child node is located.\r
 171  * @param entry Pointer to index entry\r
 172  * @return Block address of child node\r
 173  */\r
 174 static inline uint32_t\r
 175 ext4_dir_dx_entry_get_block(struct ext4_directory_dx_entry *entry)\r
 176 {\r
 177     return to_le32(entry->block);\r
 178 }\r
 179 \r
 180 /**@brief Set block address where child node is located.\r
 181  * @param entry Pointer to index entry\r
 182  * @param block Block address of child node\r
 183  */\r
 184 static inline void\r
 185 ext4_dir_dx_entry_set_block(struct ext4_directory_dx_entry *entry,\r
 186                             uint32_t block)\r
 187 {\r
 188     entry->block = to_le32(block);\r
 189 }\r
 190 \r
 191 /**@brief Sort entry item.*/\r
 192 struct ext4_dx_sort_entry\r
 193 {\r
 194     uint32_t hash;\r
 195     uint32_t rec_len;\r
 196     void *dentry;\r
 197 };\r
 198 \r
 199 static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len,\r
 200                                    const char *name)\r
 201 {\r
 202     return ext2_htree_hash(name, len, hinfo->seed, hinfo->hash_version,\r
 203                            &hinfo->hash, &hinfo->minor_hash);\r
 204 }\r
 205 \r
 206 /****************************************************************************/\r
 207 \r
 208 int ext4_dir_dx_init(struct ext4_inode_ref *dir)\r
 209 {\r
 210     /* Load block 0, where will be index root located */\r
 211     uint32_t fblock;\r
 212     int rc = ext4_fs_get_inode_data_block_index(dir, 0, &fblock);\r
 213     if (rc != EOK)\r
 214         return rc;\r
 215 \r
 216     struct ext4_block block;\r
 217     rc = ext4_block_get(dir->fs->bdev, &block, fblock);\r
 218     if (rc != EOK)\r
 219         return rc;\r
 220 \r
 221     /* Initialize pointers to data structures */\r
 222     struct ext4_directory_dx_root *root = (void *)block.data;\r
 223     struct ext4_directory_dx_root_info *info = &(root->info);\r
 224 \r
 225     /* Initialize root info structure */\r
 226     uint8_t hash_version = ext4_get8(&dir->fs->sb, default_hash_version);\r
 227 \r
 228     ext4_dir_dx_root_info_set_hash_version(info, hash_version);\r
 229     ext4_dir_dx_root_info_set_indirect_levels(info, 0);\r
 230     ext4_dir_dx_root_info_set_info_length(info, 8);\r
 231 \r
 232     /* Set limit and current number of entries */\r
 233     struct ext4_directory_dx_countlimit *countlimit =\r
 234         (struct ext4_directory_dx_countlimit *)&root->entries;\r
 235 \r
 236     ext4_dir_dx_countlimit_set_count(countlimit, 1);\r
 237 \r
 238     uint32_t block_size = ext4_sb_get_block_size(&dir->fs->sb);\r
 239     uint32_t entry_space = block_size -\r
 240                            2 * sizeof(struct ext4_directory_dx_dot_entry) -\r
 241                            sizeof(struct ext4_directory_dx_root_info);\r
 242     uint16_t root_limit = entry_space / sizeof(struct ext4_directory_dx_entry);\r
 243     ext4_dir_dx_countlimit_set_limit(countlimit, root_limit);\r
 244 \r
 245     /* Append new block, where will be new entries inserted in the future */\r
 246     uint32_t iblock;\r
 247     rc = ext4_fs_append_inode_block(dir, &fblock, &iblock);\r
 248     if (rc != EOK) {\r
 249         ext4_block_set(dir->fs->bdev, &block);\r
 250         return rc;\r
 251     }\r
 252 \r
 253     struct ext4_block new_block;\r
 254 \r
 255     rc = ext4_block_get(dir->fs->bdev, &new_block, fblock);\r
 256     if (rc != EOK) {\r
 257         ext4_block_set(dir->fs->bdev, &block);\r
 258         return rc;\r
 259     }\r
 260 \r
 261     /* Fill the whole block with empty entry */\r
 262     struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;\r
 263 \r
 264     ext4_dir_entry_ll_set_entry_length(block_entry, block_size);\r
 265     ext4_dir_entry_ll_set_inode(block_entry, 0);\r
 266 \r
 267     new_block.dirty = true;\r
 268     rc = ext4_block_set(dir->fs->bdev, &new_block);\r
 269     if (rc != EOK) {\r
 270         ext4_block_set(dir->fs->bdev, &block);\r
 271         return rc;\r
 272     }\r
 273 \r
 274     /* Connect new block to the only entry in index */\r
 275     struct ext4_directory_dx_entry *entry = root->entries;\r
 276     ext4_dir_dx_entry_set_block(entry, iblock);\r
 277 \r
 278     block.dirty = true;\r
 279 \r
 280     return ext4_block_set(dir->fs->bdev, &block);\r
 281 }\r
 282 \r
 283 /**@brief Initialize hash info structure necessary for index operations.\r
 284  * @param hinfo      Pointer to hinfo to be initialized\r
 285  * @param root_block Root block (number 0) of index\r
 286  * @param sb         Pointer to superblock\r
 287  * @param name_len   Length of name to be computed hash value from\r
 288  * @param name       Name to be computed hash value from\r
 289  * @return Standard error code\r
 290  */\r
 291 static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo,\r
 292                                struct ext4_block *root_block,\r
 293                                struct ext4_sblock *sb, size_t name_len,\r
 294                                const char *name)\r
 295 {\r
 296     struct ext4_directory_dx_root *root =\r
 297         (struct ext4_directory_dx_root *)root_block->data;\r
 298 \r
 299     if ((root->info.hash_version != EXT2_HTREE_LEGACY) &&\r
 300         (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&\r
 301         (root->info.hash_version != EXT2_HTREE_TEA))\r
 302         return EXT4_ERR_BAD_DX_DIR;\r
 303 \r
 304     /* Check unused flags */\r
 305     if (root->info.unused_flags != 0)\r
 306         return EXT4_ERR_BAD_DX_DIR;\r
 307 \r
 308     /* Check indirect levels */\r
 309     if (root->info.indirect_levels > 1)\r
 310         return EXT4_ERR_BAD_DX_DIR;\r
 311 \r
 312     /* Check if node limit is correct */\r
 313     uint32_t block_size = ext4_sb_get_block_size(sb);\r
 314     uint32_t entry_space = block_size;\r
 315     entry_space -= 2 * sizeof(struct ext4_directory_dx_dot_entry);\r
 316     entry_space -= sizeof(struct ext4_directory_dx_root_info);\r
 317     entry_space = entry_space / sizeof(struct ext4_directory_dx_entry);\r
 318 \r
 319     uint16_t limit = ext4_dir_dx_countlimit_get_limit(\r
 320         (struct ext4_directory_dx_countlimit *)&root->entries);\r
 321     if (limit != entry_space)\r
 322         return EXT4_ERR_BAD_DX_DIR;\r
 323 \r
 324     /* Check hash version and modify if necessary */\r
 325     hinfo->hash_version = ext4_dir_dx_root_info_get_hash_version(&root->info);\r
 326     if ((hinfo->hash_version <= EXT2_HTREE_TEA) &&\r
 327         (ext4_sb_check_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {\r
 328         /* Use unsigned hash */\r
 329         hinfo->hash_version += 3;\r
 330     }\r
 331 \r
 332     /* Load hash seed from superblock */\r
 333 \r
 334     hinfo->seed = ext4_get8(sb, hash_seed);\r
 335 \r
 336     /* Compute hash value of name */\r
 337     if (name)\r
 338         return ext4_dir_dx_hash_string(hinfo, name_len, name);\r
 339 \r
 340     return EOK;\r
 341 }\r
 342 \r
 343 /**@brief Walk through index tree and load leaf with corresponding hash value.\r
 344  * @param hinfo      Initialized hash info structure\r
 345  * @param inode_ref  Current i-node\r
 346  * @param root_block Root block (iblock 0), where is root node located\r
 347  * @param dx_block   Pointer to leaf node in dx_blocks array\r
 348  * @param dx_blocks  Array with the whole path from root to leaf\r
 349  * @return Standard error code\r
 350  */\r
 351 static int ext4_dir_dx_get_leaf(struct ext4_hash_info *hinfo,\r
 352                                 struct ext4_inode_ref *inode_ref,\r
 353                                 struct ext4_block *root_block,\r
 354                                 struct ext4_directory_dx_block **dx_block,\r
 355                                 struct ext4_directory_dx_block *dx_blocks)\r
 356 {\r
 357     struct ext4_directory_dx_block *tmp_dx_block = dx_blocks;\r
 358     struct ext4_directory_dx_root *root =\r
 359         (struct ext4_directory_dx_root *)root_block->data;\r
 360     struct ext4_directory_dx_entry *entries =\r
 361         (struct ext4_directory_dx_entry *)&root->entries;\r
 362 \r
 363     uint16_t limit = ext4_dir_dx_countlimit_get_limit(\r
 364         (struct ext4_directory_dx_countlimit *)entries);\r
 365     uint8_t indirect_level =\r
 366         ext4_dir_dx_root_info_get_indirect_levels(&root->info);\r
 367 \r
 368     struct ext4_block *tmp_block = root_block;\r
 369     struct ext4_directory_dx_entry *p;\r
 370     struct ext4_directory_dx_entry *q;\r
 371     struct ext4_directory_dx_entry *m;\r
 372     struct ext4_directory_dx_entry *at;\r
 373 \r
 374     /* Walk through the index tree */\r
 375     while (true) {\r
 376         uint16_t count = ext4_dir_dx_countlimit_get_count(\r
 377             (struct ext4_directory_dx_countlimit *)entries);\r
 378         if ((count == 0) || (count > limit))\r
 379             return EXT4_ERR_BAD_DX_DIR;\r
 380 \r
 381         /* Do binary search in every node */\r
 382         p = entries + 1;\r
 383         q = entries + count - 1;\r
 384 \r
 385         while (p <= q) {\r
 386             m = p + (q - p) / 2;\r
 387             if (ext4_dir_dx_entry_get_hash(m) > hinfo->hash)\r
 388                 q = m - 1;\r
 389             else\r
 390                 p = m + 1;\r
 391         }\r
 392 \r
 393         at = p - 1;\r
 394 \r
 395         /* Write results */\r
 396 \r
 397         memcpy(&tmp_dx_block->block, tmp_block, sizeof(struct ext4_block));\r
 398         tmp_dx_block->entries = entries;\r
 399         tmp_dx_block->position = at;\r
 400 \r
 401         /* Is algorithm in the leaf? */\r
 402         if (indirect_level == 0) {\r
 403             *dx_block = tmp_dx_block;\r
 404             return EOK;\r
 405         }\r
 406 \r
 407         /* Goto child node */\r
 408         uint32_t next_block = ext4_dir_dx_entry_get_block(at);\r
 409 \r
 410         indirect_level--;\r
 411 \r
 412         uint32_t fblock;\r
 413         int rc =\r
 414             ext4_fs_get_inode_data_block_index(inode_ref, next_block, &fblock);\r
 415         if (rc != EOK)\r
 416             return rc;\r
 417 \r
 418         rc = ext4_block_get(inode_ref->fs->bdev, tmp_block, fblock);\r
 419         if (rc != EOK)\r
 420             return rc;\r
 421 \r
 422         entries = ((struct ext4_directory_dx_node *)tmp_block->data)->entries;\r
 423         limit = ext4_dir_dx_countlimit_get_limit(\r
 424             (struct ext4_directory_dx_countlimit *)entries);\r
 425 \r
 426         uint16_t entry_space = ext4_sb_get_block_size(&inode_ref->fs->sb) -\r
 427                                sizeof(struct ext4_fake_directory_entry);\r
 428 \r
 429         entry_space = entry_space / sizeof(struct ext4_directory_dx_entry);\r
 430 \r
 431         if (limit != entry_space) {\r
 432             ext4_block_set(inode_ref->fs->bdev, tmp_block);\r
 433             return EXT4_ERR_BAD_DX_DIR;\r
 434         }\r
 435 \r
 436         ++tmp_dx_block;\r
 437     }\r
 438 \r
 439     /* Unreachable */\r
 440     return EOK;\r
 441 }\r
 442 \r
 443 /**@brief Check if the the next block would be checked during entry search.\r
 444  * @param inode_ref Directory i-node\r
 445  * @param hash      Hash value to check\r
 446  * @param dx_block  Current block\r
 447  * @param dx_blocks Array with path from root to leaf node\r
 448  * @return Standard Error codee\r
 449  */\r
 450 static int ext4_dir_dx_next_block(struct ext4_inode_ref *inode_ref,\r
 451                                   uint32_t hash,\r
 452                                   struct ext4_directory_dx_block *dx_block,\r
 453                                   struct ext4_directory_dx_block *dx_blocks)\r
 454 {\r
 455     uint32_t num_handles = 0;\r
 456     struct ext4_directory_dx_block *p = dx_block;\r
 457 \r
 458     /* Try to find data block with next bunch of entries */\r
 459     while (true) {\r
 460         p->position++;\r
 461         uint16_t count = ext4_dir_dx_countlimit_get_count(\r
 462             (struct ext4_directory_dx_countlimit *)p->entries);\r
 463 \r
 464         if (p->position < p->entries + count)\r
 465             break;\r
 466 \r
 467         if (p == dx_blocks)\r
 468             return EOK;\r
 469 \r
 470         num_handles++;\r
 471         p--;\r
 472     }\r
 473 \r
 474     /* Check hash collision (if not occured - no next block cannot be used)*/\r
 475     uint32_t current_hash = ext4_dir_dx_entry_get_hash(p->position);\r
 476     if ((hash & 1) == 0) {\r
 477         if ((current_hash & ~1) != hash)\r
 478             return 0;\r
 479     }\r
 480 \r
 481     /* Fill new path */\r
 482     while (num_handles--) {\r
 483         uint32_t block_idx = ext4_dir_dx_entry_get_block(p->position);\r
 484         uint32_t block_addr;\r
 485 \r
 486         int rc = ext4_fs_get_inode_data_block_index(inode_ref, block_idx,\r
 487                                                     &block_addr);\r
 488         if (rc != EOK)\r
 489             return rc;\r
 490 \r
 491         struct ext4_block block;\r
 492         rc = ext4_block_get(inode_ref->fs->bdev, &block, block_addr);\r
 493         if (rc != EOK)\r
 494             return rc;\r
 495 \r
 496         p++;\r
 497 \r
 498         /* Don't forget to put old block (prevent memory leak) */\r
 499         rc = ext4_block_set(inode_ref->fs->bdev, &p->block);\r
 500         if (rc != EOK)\r
 501             return rc;\r
 502 \r
 503         memcpy(&p->block, &p->block, sizeof(block));\r
 504         p->entries = ((struct ext4_directory_dx_node *)block.data)->entries;\r
 505         p->position = p->entries;\r
 506     }\r
 507 \r
 508     return ENOENT;\r
 509 }\r
 510 \r
 511 int ext4_dir_dx_find_entry(struct ext4_directory_search_result *result,\r
 512                            struct ext4_inode_ref *inode_ref, size_t name_len,\r
 513                            const char *name)\r
 514 {\r
 515     /* Load direct block 0 (index root) */\r
 516     uint32_t root_block_addr;\r
 517     int rc2;\r
 518     int rc = ext4_fs_get_inode_data_block_index(inode_ref, 0, &root_block_addr);\r
 519     if (rc != EOK)\r
 520         return rc;\r
 521 \r
 522     struct ext4_fs *fs = inode_ref->fs;\r
 523 \r
 524     struct ext4_block root_block;\r
 525     rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);\r
 526     if (rc != EOK)\r
 527         return rc;\r
 528 \r
 529     /* Initialize hash info (compute hash value) */\r
 530     struct ext4_hash_info hinfo;\r
 531     rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);\r
 532     if (rc != EOK) {\r
 533         ext4_block_set(fs->bdev, &root_block);\r
 534         return EXT4_ERR_BAD_DX_DIR;\r
 535     }\r
 536 \r
 537     /*\r
 538      * Hardcoded number 2 means maximum height of index tree,\r
 539      * specified in the Linux driver.\r
 540      */\r
 541     struct ext4_directory_dx_block dx_blocks[2];\r
 542     struct ext4_directory_dx_block *dx_block;\r
 543     struct ext4_directory_dx_block *tmp;\r
 544 \r
 545     rc = ext4_dir_dx_get_leaf(&hinfo, inode_ref, &root_block, &dx_block,\r
 546                               dx_blocks);\r
 547     if (rc != EOK) {\r
 548         ext4_block_set(fs->bdev, &root_block);\r
 549         return EXT4_ERR_BAD_DX_DIR;\r
 550     }\r
 551 \r
 552     do {\r
 553         /* Load leaf block */\r
 554         uint32_t leaf_block_idx =\r
 555             ext4_dir_dx_entry_get_block(dx_block->position);\r
 556         uint32_t leaf_block_addr;\r
 557 \r
 558         rc = ext4_fs_get_inode_data_block_index(inode_ref, leaf_block_idx,\r
 559                                                 &leaf_block_addr);\r
 560         if (rc != EOK)\r
 561             goto cleanup;\r
 562 \r
 563         struct ext4_block leaf_block;\r
 564         rc = ext4_block_get(fs->bdev, &leaf_block, leaf_block_addr);\r
 565         if (rc != EOK)\r
 566             goto cleanup;\r
 567 \r
 568         /* Linear search inside block */\r
 569         struct ext4_directory_entry_ll *res_dentry;\r
 570         rc = ext4_dir_find_in_block(&leaf_block, &fs->sb, name_len, name,\r
 571                                     &res_dentry);\r
 572 \r
 573         /* Found => return it */\r
 574         if (rc == EOK) {\r
 575             result->block = leaf_block;\r
 576             result->dentry = res_dentry;\r
 577             goto cleanup;\r
 578         }\r
 579 \r
 580         /* Not found, leave untouched */\r
 581         rc2 = ext4_block_set(fs->bdev, &leaf_block);\r
 582         if (rc2 != EOK)\r
 583             goto cleanup;\r
 584 \r
 585         if (rc != ENOENT)\r
 586             goto cleanup;\r
 587 \r
 588         /* check if the next block could be checked */\r
 589         rc = ext4_dir_dx_next_block(inode_ref, hinfo.hash, dx_block,\r
 590                                     &dx_blocks[0]);\r
 591         if (rc < 0)\r
 592             goto cleanup;\r
 593     } while (rc == ENOENT);\r
 594 \r
 595     /* Entry not found */\r
 596     rc = ENOENT;\r
 597 \r
 598 cleanup:\r
 599     /* The whole path must be released (preventing memory leak) */\r
 600     tmp = dx_blocks;\r
 601 \r
 602     while (tmp <= dx_block) {\r
 603         rc2 = ext4_block_set(fs->bdev, &tmp->block);\r
 604         if (rc == EOK && rc2 != EOK)\r
 605             rc = rc2;\r
 606         ++tmp;\r
 607     }\r
 608 \r
 609     return rc;\r
 610 }\r
 611 \r
 612 #if CONFIG_DIR_INDEX_COMB_SORT\r
 613 #define SWAP_ENTRY(se1, se2)                                                   \\r
 614     do {                                                                       \\r
 615         struct ext4_dx_sort_entry tmp = se1;                                   \\r
 616         se1 = se2;                                                             \\r
 617         se2 = tmp;                                                             \\r
 618     \\r
 619 } while (0)\r
 620 \r
 621 static void comb_sort(struct ext4_dx_sort_entry *se, uint32_t count)\r
 622 {\r
 623     struct ext4_dx_sort_entry *p, *q, *top = se + count - 1;\r
 624     bool more;\r
 625     /* Combsort */\r
 626     while (count > 2) {\r
 627         count = (count * 10) / 13;\r
 628         if (count - 9 < 2)\r
 629             count = 11;\r
 630         for (p = top, q = p - count; q >= se; p--, q--)\r
 631             if (p->hash < q->hash)\r
 632                 SWAP_ENTRY(*p, *q);\r
 633     }\r
 634     /* Bubblesort */\r
 635     do {\r
 636         more = 0;\r
 637         q = top;\r
 638         while (q-- > se) {\r
 639             if (q[1].hash >= q[0].hash)\r
 640                 continue;\r
 641             SWAP_ENTRY(*(q + 1), *q);\r
 642             more = 1;\r
 643         }\r
 644     } while (more);\r
 645 }\r
 646 #else\r
 647 \r
 648 /**@brief  Compare function used to pass in quicksort implementation.\r
 649  *         It can compare two entries by hash value.\r
 650  * @param arg1  First entry\r
 651  * @param arg2  Second entry\r
 652  * @param dummy Unused parameter, can be NULL\r
 653  *\r
 654  * @return Classic compare result\r
 655  *         (0: equal, -1: arg1 < arg2, 1: arg1 > arg2)\r
 656  */\r
 657 static int ext4_dir_dx_entry_comparator(const void *arg1, const void *arg2)\r
 658 {\r
 659     struct ext4_dx_sort_entry *entry1 = (void *)arg1;\r
 660     struct ext4_dx_sort_entry *entry2 = (void *)arg2;\r
 661 \r
 662     if (entry1->hash == entry2->hash)\r
 663         return 0;\r
 664 \r
 665     if (entry1->hash < entry2->hash)\r
 666         return -1;\r
 667     else\r
 668         return 1;\r
 669 }\r
 670 #endif\r
 671 \r
 672 /**@brief  Insert new index entry to block.\r
 673  *         Note that space for new entry must be checked by caller.\r
 674  * @param index_block Block where to insert new entry\r
 675  * @param hash        Hash value covered by child node\r
 676  * @param iblock      Logical number of child block\r
 677  *\r
 678  */\r
 679 static void\r
 680 ext4_dir_dx_insert_entry(struct ext4_directory_dx_block *index_block,\r
 681                          uint32_t hash, uint32_t iblock)\r
 682 {\r
 683     struct ext4_directory_dx_entry *old_index_entry = index_block->position;\r
 684     struct ext4_directory_dx_entry *new_index_entry = old_index_entry + 1;\r
 685 \r
 686     struct ext4_directory_dx_countlimit *countlimit =\r
 687         (struct ext4_directory_dx_countlimit *)index_block->entries;\r
 688     uint32_t count = ext4_dir_dx_countlimit_get_count(countlimit);\r
 689 \r
 690     struct ext4_directory_dx_entry *start_index = index_block->entries;\r
 691     size_t bytes =\r
 692         (uint8_t *)(start_index + count) - (uint8_t *)(new_index_entry);\r
 693 \r
 694     memmove(new_index_entry + 1, new_index_entry, bytes);\r
 695 \r
 696     ext4_dir_dx_entry_set_block(new_index_entry, iblock);\r
 697     ext4_dir_dx_entry_set_hash(new_index_entry, hash);\r
 698 \r
 699     ext4_dir_dx_countlimit_set_count(countlimit, count + 1);\r
 700 \r
 701     index_block->block.dirty = true;\r
 702 }\r
 703 \r
 704 /**@brief Split directory entries to two parts preventing node overflow.\r
 705  * @param inode_ref      Directory i-node\r
 706  * @param hinfo          Hash info\r
 707  * @param old_data_block Block with data to be split\r
 708  * @param index_block    Block where index entries are located\r
 709  * @param new_data_block Output value for newly allocated data block\r
 710  */\r
 711 static int ext4_dir_dx_split_data(struct ext4_inode_ref *inode_ref,\r
 712                                   struct ext4_hash_info *hinfo,\r
 713                                   struct ext4_block *old_data_block,\r
 714                                   struct ext4_directory_dx_block *index_block,\r
 715                                   struct ext4_block *new_data_block)\r
 716 {\r
 717     int rc = EOK;\r
 718 \r
 719     /* Allocate buffer for directory entries */\r
 720     uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);\r
 721 \r
 722     uint8_t *entry_buffer = malloc(block_size);\r
 723     if (entry_buffer == NULL)\r
 724         return ENOMEM;\r
 725 \r
 726     /* dot entry has the smallest size available */\r
 727     uint32_t max_entry_count =\r
 728         block_size / sizeof(struct ext4_directory_dx_dot_entry);\r
 729 \r
 730     /* Allocate sort entry */\r
 731     struct ext4_dx_sort_entry *sort_array =\r
 732         malloc(max_entry_count * sizeof(struct ext4_dx_sort_entry));\r
 733 \r
 734     if (sort_array == NULL) {\r
 735         free(entry_buffer);\r
 736         return ENOMEM;\r
 737     }\r
 738 \r
 739     uint32_t idx = 0;\r
 740     uint32_t real_size = 0;\r
 741 \r
 742     /* Initialize hinfo */\r
 743     struct ext4_hash_info tmp_hinfo;\r
 744     memcpy(&tmp_hinfo, hinfo, sizeof(struct ext4_hash_info));\r
 745 \r
 746     /* Load all valid entries to the buffer */\r
 747     struct ext4_directory_entry_ll *dentry = (void *)old_data_block->data;\r
 748     uint8_t *entry_buffer_ptr = entry_buffer;\r
 749     while ((void *)dentry < (void *)(old_data_block->data + block_size)) {\r
 750         /* Read only valid entries */\r
 751         if (ext4_dir_entry_ll_get_inode(dentry) && dentry->name_length) {\r
 752             uint8_t len =\r
 753                 ext4_dir_entry_ll_get_name_length(&inode_ref->fs->sb, dentry);\r
 754 \r
 755             rc = ext4_dir_dx_hash_string(&tmp_hinfo, len, (char *)dentry->name);\r
 756             if (rc != EOK) {\r
 757                 free(sort_array);\r
 758                 free(entry_buffer);\r
 759                 return rc;\r
 760             }\r
 761 \r
 762             uint32_t rec_len = 8 + len;\r
 763 \r
 764             if ((rec_len % 4) != 0)\r
 765                 rec_len += 4 - (rec_len % 4);\r
 766 \r
 767             memcpy(entry_buffer_ptr, dentry, rec_len);\r
 768 \r
 769             sort_array[idx].dentry = entry_buffer_ptr;\r
 770             sort_array[idx].rec_len = rec_len;\r
 771             sort_array[idx].hash = tmp_hinfo.hash;\r
 772 \r
 773             entry_buffer_ptr += rec_len;\r
 774             real_size += rec_len;\r
 775             idx++;\r
 776         }\r
 777 \r
 778         dentry = (void *)((uint8_t *)dentry +\r
 779                           ext4_dir_entry_ll_get_entry_length(dentry));\r
 780     }\r
 781 \r
 782 /* Sort all entries */\r
 783 #if CONFIG_DIR_INDEX_COMB_SORT\r
 784     comb_sort(sort_array, idx);\r
 785 #else\r
 786     qsort(sort_array, idx, sizeof(struct ext4_dx_sort_entry),\r
 787           ext4_dir_dx_entry_comparator);\r
 788 #endif\r
 789     /* Allocate new block for store the second part of entries */\r
 790     uint32_t new_fblock;\r
 791     uint32_t new_iblock;\r
 792     rc = ext4_fs_append_inode_block(inode_ref, &new_fblock, &new_iblock);\r
 793     if (rc != EOK) {\r
 794         free(sort_array);\r
 795         free(entry_buffer);\r
 796         return rc;\r
 797     }\r
 798 \r
 799     /* Load new block */\r
 800     struct ext4_block new_data_block_tmp;\r
 801     rc = ext4_block_get(inode_ref->fs->bdev, &new_data_block_tmp, new_fblock);\r
 802     if (rc != EOK) {\r
 803         free(sort_array);\r
 804         free(entry_buffer);\r
 805         return rc;\r
 806     }\r
 807 \r
 808     /*\r
 809      * Distribute entries to two blocks (by size)\r
 810      * - compute the half\r
 811      */\r
 812     uint32_t new_hash = 0;\r
 813     uint32_t current_size = 0;\r
 814     uint32_t mid = 0;\r
 815     uint32_t i;\r
 816     for (i = 0; i < idx; ++i) {\r
 817         if ((current_size + sort_array[i].rec_len) > (block_size / 2)) {\r
 818             new_hash = sort_array[i].hash;\r
 819             mid = i;\r
 820             break;\r
 821         }\r
 822 \r
 823         current_size += sort_array[i].rec_len;\r
 824     }\r
 825 \r
 826     /* Check hash collision */\r
 827     uint32_t continued = 0;\r
 828     if (new_hash == sort_array[mid - 1].hash)\r
 829         continued = 1;\r
 830 \r
 831     uint32_t offset = 0;\r
 832     void *ptr;\r
 833 \r
 834     /* First part - to the old block */\r
 835     for (i = 0; i < mid; ++i) {\r
 836         ptr = old_data_block->data + offset;\r
 837         memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);\r
 838 \r
 839         struct ext4_directory_entry_ll *tmp = ptr;\r
 840         if (i < (mid - 1))\r
 841             ext4_dir_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);\r
 842         else\r
 843             ext4_dir_entry_ll_set_entry_length(tmp, block_size - offset);\r
 844 \r
 845         offset += sort_array[i].rec_len;\r
 846     }\r
 847 \r
 848     /* Second part - to the new block */\r
 849     offset = 0;\r
 850     for (i = mid; i < idx; ++i) {\r
 851         ptr = new_data_block_tmp.data + offset;\r
 852         memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);\r
 853 \r
 854         struct ext4_directory_entry_ll *tmp = ptr;\r
 855         if (i < (idx - 1))\r
 856             ext4_dir_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);\r
 857         else\r
 858             ext4_dir_entry_ll_set_entry_length(tmp, block_size - offset);\r
 859 \r
 860         offset += sort_array[i].rec_len;\r
 861     }\r
 862 \r
 863     /* Do some steps to finish operation */\r
 864     old_data_block->dirty = true;\r
 865     new_data_block_tmp.dirty = true;\r
 866 \r
 867     free(sort_array);\r
 868     free(entry_buffer);\r
 869 \r
 870     ext4_dir_dx_insert_entry(index_block, new_hash + continued, new_iblock);\r
 871 \r
 872     *new_data_block = new_data_block_tmp;\r
 873 \r
 874     return EOK;\r
 875 }\r
 876 \r
 877 /**@brief  Split index node and maybe some parent nodes in the tree hierarchy.\r
 878  * @param inode_ref Directory i-node\r
 879  * @param dx_blocks Array with path from root to leaf node\r
 880  * @param dx_block  Leaf block to be split if needed\r
 881  * @return Error code\r
 882  */\r
 883 static int\r
 884 ext4_dir_dx_split_index(struct ext4_inode_ref *inode_ref,\r
 885                         struct ext4_directory_dx_block *dx_blocks,\r
 886                         struct ext4_directory_dx_block *dx_block,\r
 887                         struct ext4_directory_dx_block **new_dx_block)\r
 888 {\r
 889     struct ext4_directory_dx_entry *entries;\r
 890 \r
 891     if (dx_block == dx_blocks)\r
 892         entries =\r
 893             ((struct ext4_directory_dx_root *)dx_block->block.data)->entries;\r
 894     else\r
 895         entries =\r
 896             ((struct ext4_directory_dx_node *)dx_block->block.data)->entries;\r
 897 \r
 898     struct ext4_directory_dx_countlimit *countlimit =\r
 899         (struct ext4_directory_dx_countlimit *)entries;\r
 900 \r
 901     uint16_t leaf_limit = ext4_dir_dx_countlimit_get_limit(countlimit);\r
 902     uint16_t leaf_count = ext4_dir_dx_countlimit_get_count(countlimit);\r
 903 \r
 904     /* Check if is necessary to split index block */\r
 905     if (leaf_limit == leaf_count) {\r
 906         size_t levels = dx_block - dx_blocks;\r
 907 \r
 908         struct ext4_directory_dx_entry *root_entries =\r
 909             ((struct ext4_directory_dx_root *)dx_blocks[0].block.data)->entries;\r
 910 \r
 911         struct ext4_directory_dx_countlimit *root_countlimit =\r
 912             (struct ext4_directory_dx_countlimit *)root_entries;\r
 913         uint16_t root_limit = ext4_dir_dx_countlimit_get_limit(root_countlimit);\r
 914         uint16_t root_count = ext4_dir_dx_countlimit_get_count(root_countlimit);\r
 915 \r
 916         /* Linux limitation */\r
 917         if ((levels > 0) && (root_limit == root_count))\r
 918             return ENOSPC;\r
 919 \r
 920         /* Add new block to directory */\r
 921         uint32_t new_fblock;\r
 922         uint32_t new_iblock;\r
 923         int rc =\r
 924             ext4_fs_append_inode_block(inode_ref, &new_fblock, &new_iblock);\r
 925         if (rc != EOK)\r
 926             return rc;\r
 927 \r
 928         /* load new block */\r
 929         struct ext4_block new_block;\r
 930         rc = ext4_block_get(inode_ref->fs->bdev, &new_block, new_fblock);\r
 931         if (rc != EOK)\r
 932             return rc;\r
 933 \r
 934         struct ext4_directory_dx_node *new_node = (void *)new_block.data;\r
 935         struct ext4_directory_dx_entry *new_entries = new_node->entries;\r
 936 \r
 937         memset(&new_node->fake, 0, sizeof(struct ext4_fake_directory_entry));\r
 938 \r
 939         uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);\r
 940 \r
 941         new_node->fake.entry_length = block_size;\r
 942 \r
 943         /* Split leaf node */\r
 944         if (levels > 0) {\r
 945             uint32_t count_left = leaf_count / 2;\r
 946             uint32_t count_right = leaf_count - count_left;\r
 947             uint32_t hash_right =\r
 948                 ext4_dir_dx_entry_get_hash(entries + count_left);\r
 949 \r
 950             /* Copy data to new node */\r
 951             memcpy((void *)new_entries, (void *)(entries + count_left),\r
 952                    count_right * sizeof(struct ext4_directory_dx_entry));\r
 953 \r
 954             /* Initialize new node */\r
 955             struct ext4_directory_dx_countlimit *left_countlimit =\r
 956                 (struct ext4_directory_dx_countlimit *)entries;\r
 957             struct ext4_directory_dx_countlimit *right_countlimit =\r
 958                 (struct ext4_directory_dx_countlimit *)new_entries;\r
 959 \r
 960             ext4_dir_dx_countlimit_set_count(left_countlimit, count_left);\r
 961             ext4_dir_dx_countlimit_set_count(right_countlimit, count_right);\r
 962 \r
 963             uint32_t entry_space =\r
 964                 block_size - sizeof(struct ext4_fake_directory_entry);\r
 965             uint32_t node_limit =\r
 966                 entry_space / sizeof(struct ext4_directory_dx_entry);\r
 967             ext4_dir_dx_countlimit_set_limit(right_countlimit, node_limit);\r
 968 \r
 969             /* Which index block is target for new entry */\r
 970             uint32_t position_index = (dx_block->position - dx_block->entries);\r
 971             if (position_index >= count_left) {\r
 972                 dx_block->block.dirty = true;\r
 973 \r
 974                 struct ext4_block block_tmp = dx_block->block;\r
 975 \r
 976                 dx_block->block = new_block;\r
 977 \r
 978                 dx_block->position = new_entries + position_index - count_left;\r
 979                 dx_block->entries = new_entries;\r
 980 \r
 981                 new_block = block_tmp;\r
 982             }\r
 983 \r
 984             /* Finally insert new entry */\r
 985             ext4_dir_dx_insert_entry(dx_blocks, hash_right, new_iblock);\r
 986             dx_blocks[0].block.dirty = true;\r
 987             dx_blocks[1].block.dirty = true;\r
 988 \r
 989             new_block.dirty = true;\r
 990             return ext4_block_set(inode_ref->fs->bdev, &new_block);\r
 991         } else {\r
 992             /* Create second level index */\r
 993 \r
 994             /* Copy data from root to child block */\r
 995             memcpy((void *)new_entries, (void *)entries,\r
 996                    leaf_count * sizeof(struct ext4_directory_dx_entry));\r
 997 \r
 998             struct ext4_directory_dx_countlimit *new_countlimit =\r
 999                 (struct ext4_directory_dx_countlimit *)new_entries;\r
1000 \r
1001             uint32_t entry_space =\r
1002                 block_size - sizeof(struct ext4_fake_directory_entry);\r
1003             uint32_t node_limit =\r
1004                 entry_space / sizeof(struct ext4_directory_dx_entry);\r
1005             ext4_dir_dx_countlimit_set_limit(new_countlimit, node_limit);\r
1006 \r
1007             /* Set values in root node */\r
1008             struct ext4_directory_dx_countlimit *new_root_countlimit =\r
1009                 (struct ext4_directory_dx_countlimit *)entries;\r
1010 \r
1011             ext4_dir_dx_countlimit_set_count(new_root_countlimit, 1);\r
1012             ext4_dir_dx_entry_set_block(entries, new_iblock);\r
1013 \r
1014             ((struct ext4_directory_dx_root *)dx_blocks[0].block.data)\r
1015                 ->info.indirect_levels = 1;\r
1016 \r
1017             /* Add new entry to the path */\r
1018             dx_block = dx_blocks + 1;\r
1019             dx_block->position = dx_blocks->position - entries + new_entries;\r
1020             dx_block->entries = new_entries;\r
1021             dx_block->block = new_block;\r
1022 \r
1023             *new_dx_block = dx_block;\r
1024 \r
1025             dx_blocks[0].block.dirty = true;\r
1026             dx_blocks[1].block.dirty = true;\r
1027         }\r
1028     }\r
1029 \r
1030     return EOK;\r
1031 }\r
1032 \r
1033 int ext4_dir_dx_add_entry(struct ext4_inode_ref *parent,\r
1034                           struct ext4_inode_ref *child, const char *name)\r
1035 {\r
1036     int rc2 = EOK;\r
1037 \r
1038     /* Get direct block 0 (index root) */\r
1039     uint32_t root_block_addr;\r
1040     int rc = ext4_fs_get_inode_data_block_index(parent, 0, &root_block_addr);\r
1041     if (rc != EOK)\r
1042         return rc;\r
1043 \r
1044     struct ext4_fs *fs = parent->fs;\r
1045     struct ext4_block root_block;\r
1046 \r
1047     rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);\r
1048     if (rc != EOK)\r
1049         return rc;\r
1050 \r
1051     /* Initialize hinfo structure (mainly compute hash) */\r
1052     uint32_t name_len = strlen(name);\r
1053     struct ext4_hash_info hinfo;\r
1054     rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);\r
1055     if (rc != EOK) {\r
1056         ext4_block_set(fs->bdev, &root_block);\r
1057         return EXT4_ERR_BAD_DX_DIR;\r
1058     }\r
1059 \r
1060     /*\r
1061      * Hardcoded number 2 means maximum height of index\r
1062      * tree defined in Linux.\r
1063      */\r
1064     struct ext4_directory_dx_block dx_blocks[2];\r
1065     struct ext4_directory_dx_block *dx_block;\r
1066     struct ext4_directory_dx_block *dx_it;\r
1067 \r
1068     rc =\r
1069         ext4_dir_dx_get_leaf(&hinfo, parent, &root_block, &dx_block, dx_blocks);\r
1070     if (rc != EOK) {\r
1071         rc = EXT4_ERR_BAD_DX_DIR;\r
1072         goto release_index;\r
1073     }\r
1074 \r
1075     /* Try to insert to existing data block */\r
1076     uint32_t leaf_block_idx = ext4_dir_dx_entry_get_block(dx_block->position);\r
1077     uint32_t leaf_block_addr;\r
1078     rc = ext4_fs_get_inode_data_block_index(parent, leaf_block_idx,\r
1079                                             &leaf_block_addr);\r
1080     if (rc != EOK)\r
1081         goto release_index;\r
1082 \r
1083     /*\r
1084      * Check if there is needed to split index node\r
1085      * (and recursively also parent nodes)\r
1086      */\r
1087     rc = ext4_dir_dx_split_index(parent, dx_blocks, dx_block, &dx_block);\r
1088     if (rc != EOK)\r
1089         goto release_target_index;\r
1090 \r
1091     struct ext4_block target_block;\r
1092     rc = ext4_block_get(fs->bdev, &target_block, leaf_block_addr);\r
1093     if (rc != EOK)\r
1094         goto release_index;\r
1095 \r
1096     /* Check if insert operation passed */\r
1097     rc = ext4_dir_try_insert_entry(&fs->sb, &target_block, child, name,\r
1098                                    name_len);\r
1099     if (rc == EOK)\r
1100         goto release_target_index;\r
1101 \r
1102     /* Split entries to two blocks (includes sorting by hash value) */\r
1103     struct ext4_block new_block;\r
1104     rc = ext4_dir_dx_split_data(parent, &hinfo, &target_block, dx_block,\r
1105                                 &new_block);\r
1106     if (rc != EOK) {\r
1107         rc2 = rc;\r
1108         goto release_target_index;\r
1109     }\r
1110 \r
1111     /* Where to save new entry */\r
1112     uint32_t new_block_hash =\r
1113         ext4_dir_dx_entry_get_hash(dx_block->position + 1);\r
1114     if (hinfo.hash >= new_block_hash)\r
1115         rc = ext4_dir_try_insert_entry(&fs->sb, &new_block, child, name,\r
1116                                        name_len);\r
1117     else\r
1118         rc = ext4_dir_try_insert_entry(&fs->sb, &target_block, child, name,\r
1119                                        name_len);\r
1120 \r
1121     /* Cleanup */\r
1122     rc = ext4_block_set(fs->bdev, &new_block);\r
1123     if (rc != EOK)\r
1124         return rc;\r
1125 \r
1126 /* Cleanup operations */\r
1127 \r
1128 release_target_index:\r
1129     rc2 = rc;\r
1130 \r
1131     rc = ext4_block_set(fs->bdev, &target_block);\r
1132     if (rc != EOK)\r
1133         return rc;\r
1134 \r
1135 release_index:\r
1136     if (rc != EOK)\r
1137         rc2 = rc;\r
1138 \r
1139     dx_it = dx_blocks;\r
1140 \r
1141     while (dx_it <= dx_block) {\r
1142         rc = ext4_block_set(fs->bdev, &dx_it->block);\r
1143         if (rc != EOK)\r
1144             return rc;\r
1145 \r
1146         dx_it++;\r
1147     }\r
1148 \r
1149     return rc2;\r
1150 }\r
1151 \r
1152 /**\r
1153  * @}\r
1154  */\r