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