src/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 struct ext4_dx_sort_entry {\r
  49     uint32_t hash;\r
  50     uint32_t rec_len;\r
  51     void         *dentry;\r
  52 };\r
  53 \r
  54 static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len,\r
  55     const char *name)\r
  56 {\r
  57     return ext2_htree_hash(name, len, hinfo->seed, hinfo->hash_version,\r
  58             &hinfo->hash, &hinfo->minor_hash);\r
  59 }\r
  60 \r
  61 \r
  62 uint8_t ext4_dir_dx_root_info_get_hash_version(\r
  63         struct ext4_directory_dx_root_info *root_info)\r
  64 {\r
  65     return root_info->hash_version;\r
  66 }\r
  67 \r
  68 \r
  69 void    ext4_dir_dx_root_info_set_hash_version(\r
  70         struct ext4_directory_dx_root_info  *root_info, uint8_t v)\r
  71 {\r
  72     root_info->hash_version = v;\r
  73 }\r
  74 \r
  75 uint8_t ext4_dir_dx_root_info_get_info_length(\r
  76         struct ext4_directory_dx_root_info *root_info)\r
  77 {\r
  78     return root_info->info_length;\r
  79 }\r
  80 void    ext4_dir_dx_root_info_set_info_length(\r
  81         struct ext4_directory_dx_root_info  *root_info, uint8_t len)\r
  82 {\r
  83     root_info->info_length = len;\r
  84 }\r
  85 \r
  86 uint8_t ext4_dir_dx_root_info_get_indirect_levels(\r
  87         struct ext4_directory_dx_root_info *root_info)\r
  88 {\r
  89     return root_info->indirect_levels;\r
  90 }\r
  91 \r
  92 void    ext4_dir_dx_root_info_set_indirect_levels(\r
  93         struct ext4_directory_dx_root_info *root_info, uint8_t lvl)\r
  94 {\r
  95     root_info->indirect_levels = lvl;\r
  96 }\r
  97 \r
  98 \r
  99 \r
 100 uint16_t ext4_dir_dx_countlimit_get_limit(\r
 101         struct ext4_directory_dx_countlimit *climit)\r
 102 {\r
 103     return to_le16(climit->limit);\r
 104 }\r
 105 void    ext4_dir_dx_countlimit_set_limit(\r
 106         struct ext4_directory_dx_countlimit *climit, uint16_t limit)\r
 107 {\r
 108     climit->limit = to_le16(limit);\r
 109 }\r
 110 \r
 111 uint16_t ext4_dir_dx_countlimit_get_count(\r
 112         struct ext4_directory_dx_countlimit *climit)\r
 113 {\r
 114     return to_le16(climit->count);\r
 115 }\r
 116 \r
 117 void    ext4_dir_dx_countlimit_set_count(\r
 118         struct ext4_directory_dx_countlimit *climit, uint16_t count)\r
 119 {\r
 120     climit->count = to_le16(count);\r
 121 }\r
 122 \r
 123 \r
 124 uint32_t ext4_dir_dx_entry_get_hash(\r
 125         struct ext4_directory_dx_entry *entry)\r
 126 {\r
 127     return to_le32(entry->hash);\r
 128 }\r
 129 void ext4_dir_dx_entry_set_hash(\r
 130         struct ext4_directory_dx_entry *entry, uint32_t hash)\r
 131 {\r
 132     entry->hash = to_le32(hash);\r
 133 }\r
 134 \r
 135 uint32_t ext4_dir_dx_entry_get_block(\r
 136         struct ext4_directory_dx_entry *entry)\r
 137 {\r
 138     return to_le32(entry->block);\r
 139 }\r
 140 void    ext4_dir_dx_entry_set_block(\r
 141         struct ext4_directory_dx_entry *entry, uint32_t block)\r
 142 {\r
 143     entry->block = to_le32(block);\r
 144 }\r
 145 /****************************************************************************/\r
 146 \r
 147 int     ext4_dir_dx_init(struct ext4_inode_ref *dir)\r
 148 {\r
 149     /* Load block 0, where will be index root located */\r
 150     uint32_t fblock;\r
 151     int rc = ext4_fs_get_inode_data_block_index(dir, 0,\r
 152             &fblock);\r
 153     if (rc != EOK)\r
 154         return rc;\r
 155 \r
 156     struct ext4_block block;\r
 157     rc = ext4_block_get(dir->fs->bdev, &block, fblock);\r
 158     if (rc != EOK)\r
 159         return rc;\r
 160 \r
 161     /* Initialize pointers to data structures */\r
 162     struct ext4_directory_dx_root *root = (void *)block.data;\r
 163     struct ext4_directory_dx_root_info *info = &(root->info);\r
 164 \r
 165     /* Initialize root info structure */\r
 166     uint8_t hash_version = ext4_get8(&dir->fs->sb, default_hash_version);\r
 167 \r
 168 \r
 169     ext4_dir_dx_root_info_set_hash_version(info, hash_version);\r
 170     ext4_dir_dx_root_info_set_indirect_levels(info, 0);\r
 171     ext4_dir_dx_root_info_set_info_length(info, 8);\r
 172 \r
 173     /* Set limit and current number of entries */\r
 174     struct ext4_directory_dx_countlimit *countlimit =\r
 175             (struct ext4_directory_dx_countlimit *) &root->entries;\r
 176 \r
 177     ext4_dir_dx_countlimit_set_count(countlimit, 1);\r
 178 \r
 179     uint32_t block_size =\r
 180             ext4_sb_get_block_size(&dir->fs->sb);\r
 181     uint32_t entry_space =\r
 182             block_size - 2 * sizeof(struct ext4_directory_dx_dot_entry) -\r
 183             sizeof(struct ext4_directory_dx_root_info);\r
 184     uint16_t root_limit = entry_space / sizeof(struct ext4_directory_dx_entry);\r
 185     ext4_dir_dx_countlimit_set_limit(countlimit, root_limit);\r
 186 \r
 187     /* Append new block, where will be new entries inserted in the future */\r
 188     uint32_t iblock;\r
 189     rc = ext4_fs_append_inode_block(dir, &fblock, &iblock);\r
 190     if (rc != EOK) {\r
 191         ext4_block_set(dir->fs->bdev, &block);\r
 192         return rc;\r
 193     }\r
 194 \r
 195     struct ext4_block new_block;\r
 196 \r
 197     rc = ext4_block_get(dir->fs->bdev, &new_block, fblock);\r
 198     if (rc != EOK) {\r
 199         ext4_block_set(dir->fs->bdev, &block);\r
 200         return rc;\r
 201     }\r
 202 \r
 203     /* Fill the whole block with empty entry */\r
 204     struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;\r
 205 \r
 206     ext4_dir_entry_ll_set_entry_length(block_entry, block_size);\r
 207     ext4_dir_entry_ll_set_inode(block_entry, 0);\r
 208 \r
 209     new_block.dirty = true;\r
 210     rc = ext4_block_set(dir->fs->bdev, &new_block);\r
 211     if (rc != EOK) {\r
 212         ext4_block_set(dir->fs->bdev, &block);\r
 213         return rc;\r
 214     }\r
 215 \r
 216     /* Connect new block to the only entry in index */\r
 217     struct ext4_directory_dx_entry *entry = root->entries;\r
 218     ext4_dir_dx_entry_set_block(entry, iblock);\r
 219 \r
 220     block.dirty = true;\r
 221 \r
 222     return ext4_block_set(dir->fs->bdev, &block);\r
 223 }\r
 224 \r
 225 static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo,\r
 226         struct ext4_block *root_block, struct ext4_sblock *sb, size_t name_len,\r
 227         const char *name)\r
 228 {\r
 229     struct ext4_directory_dx_root *root =\r
 230             (struct ext4_directory_dx_root *) root_block->data;\r
 231 \r
 232     if ((root->info.hash_version != EXT2_HTREE_LEGACY) &&\r
 233             (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&\r
 234             (root->info.hash_version != EXT2_HTREE_TEA))\r
 235         return EXT4_ERR_BAD_DX_DIR;\r
 236 \r
 237     /* Check unused flags */\r
 238     if (root->info.unused_flags != 0)\r
 239         return EXT4_ERR_BAD_DX_DIR;\r
 240 \r
 241     /* Check indirect levels */\r
 242     if (root->info.indirect_levels > 1)\r
 243         return EXT4_ERR_BAD_DX_DIR;\r
 244 \r
 245     /* Check if node limit is correct */\r
 246     uint32_t block_size = ext4_sb_get_block_size(sb);\r
 247     uint32_t entry_space = block_size;\r
 248     entry_space -= 2 * sizeof(struct ext4_directory_dx_dot_entry);\r
 249     entry_space -= sizeof(struct ext4_directory_dx_root_info);\r
 250     entry_space = entry_space / sizeof(struct ext4_directory_dx_entry);\r
 251 \r
 252     uint16_t limit = ext4_dir_dx_countlimit_get_limit(\r
 253             (struct ext4_directory_dx_countlimit *) &root->entries);\r
 254     if (limit != entry_space)\r
 255         return EXT4_ERR_BAD_DX_DIR;\r
 256 \r
 257     /* Check hash version and modify if necessary */\r
 258     hinfo->hash_version =\r
 259             ext4_dir_dx_root_info_get_hash_version(&root->info);\r
 260     if ((hinfo->hash_version <= EXT2_HTREE_TEA) &&\r
 261             (ext4_sb_check_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {\r
 262         /* Use unsigned hash */\r
 263         hinfo->hash_version += 3;\r
 264     }\r
 265 \r
 266     /* Load hash seed from superblock */\r
 267 \r
 268     hinfo->seed = ext4_get8(sb, hash_seed);\r
 269 \r
 270     /* Compute hash value of name */\r
 271     if (name)\r
 272         return ext4_dir_dx_hash_string(hinfo, name_len, name);\r
 273 \r
 274     return EOK;\r
 275 }\r
 276 \r
 277 \r
 278 static int ext4_dir_dx_get_leaf(struct ext4_hash_info *hinfo,\r
 279         struct ext4_inode_ref *inode_ref, struct ext4_block *root_block,\r
 280         struct ext4_directory_dx_block **dx_block,\r
 281         struct ext4_directory_dx_block *dx_blocks)\r
 282 {\r
 283     struct ext4_directory_dx_block *tmp_dx_block = dx_blocks;\r
 284     struct ext4_directory_dx_root *root =\r
 285             (struct ext4_directory_dx_root *) root_block->data;\r
 286     struct ext4_directory_dx_entry *entries =\r
 287             (struct ext4_directory_dx_entry *) &root->entries;\r
 288 \r
 289     uint16_t limit = ext4_dir_dx_countlimit_get_limit(\r
 290             (struct ext4_directory_dx_countlimit *) entries);\r
 291     uint8_t indirect_level =\r
 292             ext4_dir_dx_root_info_get_indirect_levels(&root->info);\r
 293 \r
 294     struct ext4_block *tmp_block = root_block;\r
 295     struct ext4_directory_dx_entry *p;\r
 296     struct ext4_directory_dx_entry *q;\r
 297     struct ext4_directory_dx_entry *m;\r
 298     struct ext4_directory_dx_entry *at;\r
 299 \r
 300     /* Walk through the index tree */\r
 301     while (true) {\r
 302         uint16_t count = ext4_dir_dx_countlimit_get_count(\r
 303                 (struct ext4_directory_dx_countlimit *) entries);\r
 304         if ((count == 0) || (count > limit))\r
 305             return EXT4_ERR_BAD_DX_DIR;\r
 306 \r
 307         /* Do binary search in every node */\r
 308         p = entries + 1;\r
 309         q = entries + count - 1;\r
 310 \r
 311         while (p <= q) {\r
 312             m = p + (q - p) / 2;\r
 313             if (ext4_dir_dx_entry_get_hash(m) > hinfo->hash)\r
 314                 q = m - 1;\r
 315             else\r
 316                 p = m + 1;\r
 317         }\r
 318 \r
 319         at = p - 1;\r
 320 \r
 321         /* Write results */\r
 322 \r
 323         memcpy(&tmp_dx_block->block, tmp_block, sizeof(struct ext4_block));\r
 324         tmp_dx_block->entries = entries;\r
 325         tmp_dx_block->position = at;\r
 326 \r
 327         /* Is algorithm in the leaf? */\r
 328         if (indirect_level == 0) {\r
 329             *dx_block = tmp_dx_block;\r
 330             return EOK;\r
 331         }\r
 332 \r
 333         /* Goto child node */\r
 334         uint32_t next_block = ext4_dir_dx_entry_get_block(at);\r
 335 \r
 336         indirect_level--;\r
 337 \r
 338         uint32_t fblock;\r
 339         int rc = ext4_fs_get_inode_data_block_index(inode_ref,\r
 340                 next_block, &fblock);\r
 341         if (rc != EOK)\r
 342             return rc;\r
 343 \r
 344         rc = ext4_block_get(inode_ref->fs->bdev, tmp_block, fblock);\r
 345         if (rc != EOK)\r
 346             return rc;\r
 347 \r
 348         entries = ((struct ext4_directory_dx_node *) tmp_block->data)->entries;\r
 349         limit = ext4_dir_dx_countlimit_get_limit(\r
 350                 (struct ext4_directory_dx_countlimit *) entries);\r
 351 \r
 352         uint16_t entry_space =\r
 353                 ext4_sb_get_block_size(&inode_ref->fs->sb) -\r
 354                 sizeof(struct ext4_directory_dx_dot_entry);\r
 355 \r
 356         entry_space = entry_space / sizeof(struct ext4_directory_dx_entry);\r
 357 \r
 358         if (limit != entry_space) {\r
 359             ext4_block_set(inode_ref->fs->bdev, tmp_block);\r
 360             return EXT4_ERR_BAD_DX_DIR;\r
 361         }\r
 362 \r
 363         ++tmp_dx_block;\r
 364     }\r
 365 \r
 366     /* Unreachable */\r
 367     return EOK;\r
 368 }\r
 369 \r
 370 static int ext4_dir_dx_next_block(struct ext4_inode_ref *inode_ref,\r
 371         uint32_t hash, struct ext4_directory_dx_block *dx_block,\r
 372         struct ext4_directory_dx_block *dx_blocks)\r
 373 {\r
 374     uint32_t num_handles = 0;\r
 375     struct ext4_directory_dx_block *p = dx_block;\r
 376 \r
 377     /* Try to find data block with next bunch of entries */\r
 378     while (true) {\r
 379         p->position++;\r
 380         uint16_t count = ext4_dir_dx_countlimit_get_count(\r
 381                 (struct ext4_directory_dx_countlimit *) p->entries);\r
 382 \r
 383         if (p->position < p->entries + count)\r
 384             break;\r
 385 \r
 386         if (p == dx_blocks)\r
 387             return EOK;\r
 388 \r
 389         num_handles++;\r
 390         p--;\r
 391     }\r
 392 \r
 393     /* Check hash collision (if not occured - no next block cannot be used)*/\r
 394     uint32_t current_hash = ext4_dir_dx_entry_get_hash(p->position);\r
 395     if ((hash & 1) == 0) {\r
 396         if ((current_hash & ~1) != hash)\r
 397             return 0;\r
 398     }\r
 399 \r
 400     /* Fill new path */\r
 401     while (num_handles--) {\r
 402         uint32_t block_idx =\r
 403                 ext4_dir_dx_entry_get_block(p->position);\r
 404         uint32_t block_addr;\r
 405 \r
 406         int rc = ext4_fs_get_inode_data_block_index(inode_ref,\r
 407                 block_idx, &block_addr);\r
 408         if (rc != EOK)\r
 409             return rc;\r
 410 \r
 411 \r
 412         struct ext4_block block;\r
 413         rc = ext4_block_get(inode_ref->fs->bdev, &block, block_addr);\r
 414         if (rc != EOK)\r
 415             return rc;\r
 416 \r
 417         p++;\r
 418 \r
 419         /* Don't forget to put old block (prevent memory leak) */\r
 420         ext4_block_set(inode_ref->fs->bdev, &p->block);\r
 421 \r
 422 \r
 423 \r
 424         memcpy(&p->block, &p->block, sizeof(block));\r
 425         p->entries = ((struct ext4_directory_dx_node *) block.data)->entries;\r
 426         p->position = p->entries;\r
 427     }\r
 428 \r
 429     return ENOENT;\r
 430 }\r
 431 \r
 432 \r
 433 \r
 434 int     ext4_dir_dx_find_entry(struct ext4_directory_search_result * result,\r
 435         struct ext4_inode_ref *inode_ref, size_t name_len, const char *name)\r
 436 {\r
 437     /* Load direct block 0 (index root) */\r
 438     uint32_t root_block_addr;\r
 439     int rc = ext4_fs_get_inode_data_block_index(inode_ref, 0,\r
 440             &root_block_addr);\r
 441     if (rc != EOK)\r
 442         return rc;\r
 443 \r
 444     struct ext4_fs *fs = inode_ref->fs;\r
 445 \r
 446     struct ext4_block root_block;\r
 447     rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);\r
 448     if (rc != EOK)\r
 449         return rc;\r
 450 \r
 451     /* Initialize hash info (compute hash value) */\r
 452     struct ext4_hash_info hinfo;\r
 453     rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb,\r
 454             name_len, name);\r
 455     if (rc != EOK) {\r
 456         ext4_block_set(fs->bdev, &root_block);\r
 457         return EXT4_ERR_BAD_DX_DIR;\r
 458     }\r
 459 \r
 460     /*\r
 461      * Hardcoded number 2 means maximum height of index tree,\r
 462      * specified in the Linux driver.\r
 463      */\r
 464     struct ext4_directory_dx_block dx_blocks[2];\r
 465     struct ext4_directory_dx_block *dx_block;\r
 466     struct ext4_directory_dx_block *tmp;\r
 467 \r
 468     rc = ext4_dir_dx_get_leaf(&hinfo, inode_ref, &root_block,\r
 469             &dx_block, dx_blocks);\r
 470     if (rc != EOK) {\r
 471         ext4_block_set(fs->bdev, &root_block);\r
 472         return EXT4_ERR_BAD_DX_DIR;\r
 473     }\r
 474 \r
 475     do {\r
 476         /* Load leaf block */\r
 477         uint32_t leaf_block_idx =\r
 478                 ext4_dir_dx_entry_get_block(dx_block->position);\r
 479         uint32_t leaf_block_addr;\r
 480 \r
 481         rc = ext4_fs_get_inode_data_block_index(inode_ref,\r
 482                 leaf_block_idx, &leaf_block_addr);\r
 483         if (rc != EOK)\r
 484             goto cleanup;\r
 485 \r
 486         struct ext4_block leaf_block;\r
 487         rc = ext4_block_get(fs->bdev, &leaf_block, leaf_block_addr);\r
 488         if (rc != EOK)\r
 489             goto cleanup;\r
 490 \r
 491         /* Linear search inside block */\r
 492         struct ext4_directory_entry_ll *res_dentry;\r
 493         rc = ext4_dir_find_in_block(&leaf_block, &fs->sb,\r
 494                 name_len, name, &res_dentry);\r
 495 \r
 496         /* Found => return it */\r
 497         if (rc == EOK) {\r
 498             result->block = leaf_block;\r
 499             result->dentry = res_dentry;\r
 500             goto cleanup;\r
 501         }\r
 502 \r
 503         /* Not found, leave untouched */\r
 504         ext4_block_set(fs->bdev, &leaf_block);\r
 505 \r
 506         if (rc != ENOENT)\r
 507             goto cleanup;\r
 508 \r
 509         /* check if the next block could be checked */\r
 510         rc = ext4_dir_dx_next_block(inode_ref, hinfo.hash,\r
 511                 dx_block, &dx_blocks[0]);\r
 512         if (rc < 0)\r
 513             goto cleanup;\r
 514     } while (rc == ENOENT);\r
 515 \r
 516     /* Entry not found */\r
 517     rc = ENOENT;\r
 518 \r
 519     cleanup:\r
 520     /* The whole path must be released (preventing memory leak) */\r
 521     tmp = dx_blocks;\r
 522 \r
 523     while (tmp <= dx_block) {\r
 524         ext4_block_set(fs->bdev, &tmp->block);\r
 525         ++tmp;\r
 526     }\r
 527 \r
 528     return rc;\r
 529 }\r
 530 \r
 531 static int ext4_dir_dx_entry_comparator(const void *arg1, const void *arg2)\r
 532 {\r
 533     struct ext4_dx_sort_entry *entry1 = (void *)arg1;\r
 534     struct ext4_dx_sort_entry *entry2 = (void *)arg2;\r
 535 \r
 536     if (entry1->hash == entry2->hash)\r
 537         return 0;\r
 538 \r
 539     if (entry1->hash < entry2->hash)\r
 540         return -1;\r
 541     else\r
 542         return 1;\r
 543 }\r
 544 \r
 545 static void ext4_dir_dx_insert_entry(\r
 546         struct ext4_directory_dx_block *index_block, uint32_t hash,\r
 547         uint32_t iblock)\r
 548 {\r
 549     struct ext4_directory_dx_entry *old_index_entry = index_block->position;\r
 550     struct ext4_directory_dx_entry *new_index_entry = old_index_entry + 1;\r
 551 \r
 552     struct ext4_directory_dx_countlimit *countlimit =\r
 553             (struct ext4_directory_dx_countlimit *) index_block->entries;\r
 554     uint32_t count = ext4_dir_dx_countlimit_get_count(countlimit);\r
 555 \r
 556     struct ext4_directory_dx_entry *start_index = index_block->entries;\r
 557     size_t bytes = (void *) (start_index + count) - (void *) (new_index_entry);\r
 558 \r
 559     memmove(new_index_entry + 1, new_index_entry, bytes);\r
 560 \r
 561     ext4_dir_dx_entry_set_block(new_index_entry, iblock);\r
 562     ext4_dir_dx_entry_set_hash(new_index_entry, hash);\r
 563 \r
 564     ext4_dir_dx_countlimit_set_count(countlimit, count + 1);\r
 565 \r
 566     index_block->block.dirty = true;\r
 567 }\r
 568 \r
 569 static int ext4_dir_dx_split_data(struct ext4_inode_ref *inode_ref,\r
 570         struct ext4_hash_info *hinfo, struct ext4_block *old_data_block,\r
 571         struct ext4_directory_dx_block *index_block,\r
 572         struct ext4_block *new_data_block)\r
 573 {\r
 574     int rc = EOK;\r
 575 \r
 576     /* Allocate buffer for directory entries */\r
 577     uint32_t block_size =\r
 578             ext4_sb_get_block_size(&inode_ref->fs->sb);\r
 579 \r
 580     void *entry_buffer = malloc(block_size);\r
 581     if (entry_buffer == NULL)\r
 582         return ENOMEM;\r
 583 \r
 584     /* dot entry has the smallest size available */\r
 585     uint32_t max_entry_count =\r
 586             block_size / sizeof(struct ext4_directory_dx_dot_entry);\r
 587 \r
 588     /* Allocate sort entry */\r
 589     struct ext4_dx_sort_entry *sort_array =\r
 590             malloc(max_entry_count * sizeof(struct ext4_dx_sort_entry));\r
 591 \r
 592     if (sort_array == NULL) {\r
 593         free(entry_buffer);\r
 594         return ENOMEM;\r
 595     }\r
 596 \r
 597     uint32_t idx = 0;\r
 598     uint32_t real_size = 0;\r
 599 \r
 600     /* Initialize hinfo */\r
 601     struct ext4_hash_info tmp_hinfo;\r
 602     memcpy(&tmp_hinfo, hinfo, sizeof(struct ext4_hash_info));\r
 603 \r
 604     /* Load all valid entries to the buffer */\r
 605     struct ext4_directory_entry_ll *dentry = (void *)old_data_block->data;\r
 606     void *entry_buffer_ptr = entry_buffer;\r
 607     while ((void *)dentry < (void *)(old_data_block->data + block_size)) {\r
 608         /* Read only valid entries */\r
 609         if (ext4_dir_entry_ll_get_inode(dentry) != 0) {\r
 610             uint8_t len = ext4_dir_entry_ll_get_name_length(\r
 611                     &inode_ref->fs->sb, dentry);\r
 612 \r
 613             rc = ext4_dir_dx_hash_string(&tmp_hinfo, len, (char*)dentry->name);\r
 614             if(rc != EOK) {\r
 615                 free(sort_array);\r
 616                 free(entry_buffer);\r
 617                 return rc;\r
 618             }\r
 619 \r
 620             uint32_t rec_len = 8 + len;\r
 621 \r
 622             if ((rec_len % 4) != 0)\r
 623                 rec_len += 4 - (rec_len % 4);\r
 624 \r
 625             memcpy(entry_buffer_ptr, dentry, rec_len);\r
 626 \r
 627             sort_array[idx].dentry = entry_buffer_ptr;\r
 628             sort_array[idx].rec_len = rec_len;\r
 629             sort_array[idx].hash = tmp_hinfo.hash;\r
 630 \r
 631             entry_buffer_ptr += rec_len;\r
 632             real_size += rec_len;\r
 633             idx++;\r
 634         }\r
 635 \r
 636         dentry = (void *) dentry +\r
 637                 ext4_dir_entry_ll_get_entry_length(dentry);\r
 638     }\r
 639 \r
 640     /* Sort all entries */\r
 641     qsort(sort_array, idx, sizeof(struct ext4_dx_sort_entry),\r
 642             ext4_dir_dx_entry_comparator);\r
 643 \r
 644     /* Allocate new block for store the second part of entries */\r
 645     uint32_t new_fblock;\r
 646     uint32_t new_iblock;\r
 647     rc = ext4_fs_append_inode_block(inode_ref, &new_fblock,\r
 648             &new_iblock);\r
 649     if (rc != EOK) {\r
 650         free(sort_array);\r
 651         free(entry_buffer);\r
 652         return rc;\r
 653     }\r
 654 \r
 655     /* Load new block */\r
 656     struct ext4_block new_data_block_tmp;\r
 657     rc = ext4_block_get(inode_ref->fs->bdev, &new_data_block_tmp,\r
 658             new_fblock);\r
 659     if (rc != EOK) {\r
 660         free(sort_array);\r
 661         free(entry_buffer);\r
 662         return rc;\r
 663     }\r
 664 \r
 665     /*\r
 666      * Distribute entries to two blocks (by size)\r
 667      * - compute the half\r
 668      */\r
 669     uint32_t new_hash = 0;\r
 670     uint32_t current_size = 0;\r
 671     uint32_t mid = 0;\r
 672     uint32_t i;\r
 673     for ( i = 0; i < idx; ++i) {\r
 674         if ((current_size + sort_array[i].rec_len) > (real_size / 2)) {\r
 675             new_hash = sort_array[i].hash;\r
 676             mid = i;\r
 677             break;\r
 678         }\r
 679 \r
 680         current_size += sort_array[i].rec_len;\r
 681     }\r
 682 \r
 683     /* Check hash collision */\r
 684     uint32_t continued = 0;\r
 685     if (new_hash == sort_array[mid-1].hash)\r
 686         continued = 1;\r
 687 \r
 688     uint32_t offset = 0;\r
 689     void *ptr;\r
 690 \r
 691     /* First part - to the old block */\r
 692     for (i = 0; i < mid; ++i) {\r
 693         ptr = old_data_block->data + offset;\r
 694         memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);\r
 695 \r
 696         struct ext4_directory_entry_ll *tmp = ptr;\r
 697         if (i < (mid - 1))\r
 698             ext4_dir_entry_ll_set_entry_length(tmp,\r
 699                     sort_array[i].rec_len);\r
 700         else\r
 701             ext4_dir_entry_ll_set_entry_length(tmp,\r
 702                     block_size - offset);\r
 703 \r
 704         offset += sort_array[i].rec_len;\r
 705     }\r
 706 \r
 707     /* Second part - to the new block */\r
 708     offset = 0;\r
 709     for (i = mid; i < idx; ++i) {\r
 710         ptr = new_data_block_tmp.data + offset;\r
 711         memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);\r
 712 \r
 713         struct ext4_directory_entry_ll *tmp = ptr;\r
 714         if (i < (idx - 1))\r
 715             ext4_dir_entry_ll_set_entry_length(tmp,\r
 716                     sort_array[i].rec_len);\r
 717         else\r
 718             ext4_dir_entry_ll_set_entry_length(tmp,\r
 719                     block_size - offset);\r
 720 \r
 721         offset += sort_array[i].rec_len;\r
 722     }\r
 723 \r
 724     /* Do some steps to finish operation */\r
 725     old_data_block->dirty = true;\r
 726     new_data_block_tmp.dirty = true;\r
 727 \r
 728     free(sort_array);\r
 729     free(entry_buffer);\r
 730 \r
 731     ext4_dir_dx_insert_entry(index_block, new_hash + continued,\r
 732             new_iblock);\r
 733 \r
 734     *new_data_block = new_data_block_tmp;\r
 735 \r
 736     return EOK;\r
 737 }\r
 738 \r
 739 /** Split index node and maybe some parent nodes in the tree hierarchy.\r
 740  *\r
 741  * @param inode_ref Directory i-node\r
 742  * @param dx_blocks Array with path from root to leaf node\r
 743  * @param dx_block  Leaf block to be split if needed\r
 744  *\r
 745  * @return Error code\r
 746  *\r
 747  */\r
 748 static int ext4_dir_dx_split_index(struct ext4_inode_ref *inode_ref,\r
 749         struct  ext4_directory_dx_block *dx_blocks,\r
 750         struct ext4_directory_dx_block *dx_block)\r
 751 {\r
 752     struct ext4_directory_dx_entry *entries;\r
 753     if (dx_block == dx_blocks)\r
 754         entries =\r
 755                 ((struct  ext4_directory_dx_root *) dx_block->block.data)->entries;\r
 756     else\r
 757         entries =\r
 758                 ((struct ext4_directory_dx_node *) dx_block->block.data)->entries;\r
 759 \r
 760     struct ext4_directory_dx_countlimit *countlimit =\r
 761             (struct ext4_directory_dx_countlimit *) entries;\r
 762 \r
 763     uint16_t leaf_limit =\r
 764             ext4_dir_dx_countlimit_get_limit(countlimit);\r
 765     uint16_t leaf_count =\r
 766             ext4_dir_dx_countlimit_get_count(countlimit);\r
 767 \r
 768     /* Check if is necessary to split index block */\r
 769     if (leaf_limit == leaf_count) {\r
 770         size_t levels = dx_block - dx_blocks;\r
 771 \r
 772         struct ext4_directory_dx_entry *root_entries =\r
 773                 ((struct ext4_directory_dx_root *) dx_blocks[0].block.data)->entries;\r
 774 \r
 775         struct ext4_directory_dx_countlimit *root_countlimit =\r
 776                 (struct ext4_directory_dx_countlimit *) root_entries;\r
 777         uint16_t root_limit =\r
 778                 ext4_dir_dx_countlimit_get_limit(root_countlimit);\r
 779         uint16_t root_count =\r
 780                 ext4_dir_dx_countlimit_get_count(root_countlimit);\r
 781 \r
 782         /* Linux limitation */\r
 783         if ((levels > 0) && (root_limit == root_count))\r
 784             return ENOSPC;\r
 785 \r
 786         /* Add new block to directory */\r
 787         uint32_t new_fblock;\r
 788         uint32_t new_iblock;\r
 789         int rc = ext4_fs_append_inode_block(inode_ref,\r
 790                 &new_fblock, &new_iblock);\r
 791         if (rc != EOK)\r
 792             return rc;\r
 793 \r
 794         /* load new block */\r
 795         struct ext4_block new_block;\r
 796         rc = ext4_block_get(inode_ref->fs->bdev, &new_block,\r
 797                 new_fblock);\r
 798         if (rc != EOK)\r
 799             return rc;\r
 800 \r
 801         struct ext4_directory_dx_node  *new_node        = (void *)new_block.data;\r
 802         struct ext4_directory_dx_entry *new_entries = new_node->entries;\r
 803 \r
 804         uint32_t block_size =\r
 805                 ext4_sb_get_block_size(&inode_ref->fs->sb);\r
 806 \r
 807         /* Split leaf node */\r
 808         if (levels > 0) {\r
 809             uint32_t count_left = leaf_count / 2;\r
 810             uint32_t count_right = leaf_count - count_left;\r
 811             uint32_t hash_right =\r
 812                     ext4_dir_dx_entry_get_hash(entries + count_left);\r
 813 \r
 814             /* Copy data to new node */\r
 815             memcpy((void *) new_entries, (void *) (entries + count_left),\r
 816                     count_right * sizeof(struct ext4_directory_dx_entry));\r
 817 \r
 818             /* Initialize new node */\r
 819             struct ext4_directory_dx_countlimit *left_countlimit =\r
 820                     (struct ext4_directory_dx_countlimit *) entries;\r
 821             struct ext4_directory_dx_countlimit *right_countlimit =\r
 822                     (struct ext4_directory_dx_countlimit *) new_entries;\r
 823 \r
 824             ext4_dir_dx_countlimit_set_count(left_countlimit, count_left);\r
 825             ext4_dir_dx_countlimit_set_count(right_countlimit, count_right);\r
 826 \r
 827             uint32_t entry_space =\r
 828                     block_size - sizeof(struct ext4_fake_directory_entry);\r
 829             uint32_t node_limit =\r
 830                     entry_space / sizeof(struct ext4_directory_dx_entry);\r
 831             ext4_dir_dx_countlimit_set_limit(right_countlimit, node_limit);\r
 832 \r
 833             /* Which index block is target for new entry */\r
 834             uint32_t position_index = (dx_block->position - dx_block->entries);\r
 835             if (position_index >= count_left) {\r
 836                 dx_block->block.dirty = true;\r
 837 \r
 838                 struct ext4_block block_tmp = dx_block->block;\r
 839 \r
 840 \r
 841                 dx_block->block = new_block;\r
 842 \r
 843                 dx_block->position =\r
 844                         new_entries + position_index - count_left;\r
 845                 dx_block->entries = new_entries;\r
 846 \r
 847                 new_block = block_tmp;\r
 848             }\r
 849 \r
 850             /* Finally insert new entry */\r
 851             ext4_dir_dx_insert_entry(dx_blocks, hash_right, new_iblock);\r
 852 \r
 853             return ext4_block_set(inode_ref->fs->bdev, &new_block);\r
 854         } else {\r
 855             /* Create second level index */\r
 856 \r
 857             /* Copy data from root to child block */\r
 858             memcpy((void *) new_entries, (void *) entries,\r
 859                     leaf_count * sizeof(struct ext4_directory_dx_entry));\r
 860 \r
 861             struct ext4_directory_dx_countlimit *new_countlimit =\r
 862                     (struct ext4_directory_dx_countlimit *) new_entries;\r
 863 \r
 864             uint32_t entry_space =\r
 865                     block_size - sizeof(struct ext4_fake_directory_entry);\r
 866             uint32_t node_limit =\r
 867                     entry_space / sizeof(struct ext4_directory_dx_entry);\r
 868             ext4_dir_dx_countlimit_set_limit(new_countlimit, node_limit);\r
 869 \r
 870             /* Set values in root node */\r
 871             struct ext4_directory_dx_countlimit *new_root_countlimit =\r
 872                     (struct ext4_directory_dx_countlimit *) entries;\r
 873 \r
 874             ext4_dir_dx_countlimit_set_count(new_root_countlimit, 1);\r
 875             ext4_dir_dx_entry_set_block(entries, new_iblock);\r
 876 \r
 877             ((struct ext4_directory_dx_root *)\r
 878                     dx_blocks[0].block.data)->info.indirect_levels = 1;\r
 879 \r
 880             /* Add new entry to the path */\r
 881             dx_block = dx_blocks + 1;\r
 882             dx_block->position = dx_block->position - entries + new_entries;\r
 883             dx_block->entries = new_entries;\r
 884             dx_block->block = new_block;\r
 885         }\r
 886     }\r
 887 \r
 888     return EOK;\r
 889 }\r
 890 \r
 891 int     ext4_dir_dx_add_entry(struct ext4_inode_ref *parent,\r
 892         struct ext4_inode_ref *child, const char *name)\r
 893 {\r
 894     int rc2 = EOK;\r
 895 \r
 896     /* Get direct block 0 (index root) */\r
 897     uint32_t root_block_addr;\r
 898     int rc = ext4_fs_get_inode_data_block_index(parent, 0,\r
 899             &root_block_addr);\r
 900     if (rc != EOK)\r
 901         return rc;\r
 902 \r
 903     struct ext4_fs *fs = parent->fs;\r
 904     struct ext4_block root_block;\r
 905 \r
 906     rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);\r
 907     if (rc != EOK)\r
 908         return rc;\r
 909 \r
 910     /* Initialize hinfo structure (mainly compute hash) */\r
 911     uint32_t name_len = strlen(name);\r
 912     struct ext4_hash_info hinfo;\r
 913     rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb,\r
 914             name_len, name);\r
 915     if (rc != EOK) {\r
 916         ext4_block_set(fs->bdev, &root_block);\r
 917         return EXT4_ERR_BAD_DX_DIR;\r
 918     }\r
 919 \r
 920     /*\r
 921      * Hardcoded number 2 means maximum height of index\r
 922      * tree defined in Linux.\r
 923      */\r
 924     struct ext4_directory_dx_block dx_blocks[2];\r
 925     struct ext4_directory_dx_block *dx_block;\r
 926     struct ext4_directory_dx_block *dx_it;\r
 927 \r
 928     rc = ext4_dir_dx_get_leaf(&hinfo, parent, &root_block,\r
 929             &dx_block, dx_blocks);\r
 930     if (rc != EOK) {\r
 931         rc = EXT4_ERR_BAD_DX_DIR;\r
 932         goto release_index;\r
 933     }\r
 934 \r
 935     /* Try to insert to existing data block */\r
 936     uint32_t leaf_block_idx =\r
 937             ext4_dir_dx_entry_get_block(dx_block->position);\r
 938     uint32_t leaf_block_addr;\r
 939     rc = ext4_fs_get_inode_data_block_index(parent, leaf_block_idx,\r
 940             &leaf_block_addr);\r
 941     if (rc != EOK)\r
 942         goto release_index;\r
 943 \r
 944     struct ext4_block target_block;\r
 945     rc = ext4_block_get(fs->bdev, &target_block, leaf_block_addr);\r
 946     if (rc != EOK)\r
 947         goto release_index;\r
 948 \r
 949     /* Check if insert operation passed */\r
 950     rc = ext4_dir_try_insert_entry(&fs->sb, &target_block, child,\r
 951             name, name_len);\r
 952     if (rc == EOK)\r
 953         goto release_target_index;\r
 954 \r
 955     /*\r
 956      * Check if there is needed to split index node\r
 957      * (and recursively also parent nodes)\r
 958      */\r
 959     rc = ext4_dir_dx_split_index(parent, dx_blocks, dx_block);\r
 960     if (rc != EOK)\r
 961         goto release_target_index;\r
 962 \r
 963     /* Split entries to two blocks (includes sorting by hash value) */\r
 964     struct ext4_block new_block;\r
 965     rc = ext4_dir_dx_split_data(parent, &hinfo, &target_block,\r
 966             dx_block, &new_block);\r
 967     if (rc != EOK) {\r
 968         rc2 = rc;\r
 969         goto release_target_index;\r
 970     }\r
 971 \r
 972     /* Where to save new entry */\r
 973     uint32_t new_block_hash =\r
 974             ext4_dir_dx_entry_get_hash(dx_block->position + 1);\r
 975     if (hinfo.hash >= new_block_hash)\r
 976         rc = ext4_dir_try_insert_entry(&fs->sb, &new_block,\r
 977                 child, name, name_len);\r
 978     else\r
 979         rc = ext4_dir_try_insert_entry(&fs->sb, &target_block,\r
 980                 child, name, name_len);\r
 981 \r
 982     /* Cleanup */\r
 983     rc = ext4_block_set(fs->bdev, &new_block);\r
 984     if (rc != EOK)\r
 985         return rc;\r
 986 \r
 987     /* Cleanup operations */\r
 988 \r
 989     release_target_index:\r
 990     rc2 = rc;\r
 991 \r
 992     rc = ext4_block_set(fs->bdev, &target_block);\r
 993     if (rc != EOK)\r
 994         return rc;\r
 995 \r
 996     release_index:\r
 997     if (rc != EOK)\r
 998         rc2 = rc;\r
 999 \r
1000     dx_it = dx_blocks;\r
1001 \r
1002     while (dx_it <= dx_block) {\r
1003         rc = ext4_block_set(fs->bdev, &dx_it->block);\r
1004         if (rc != EOK)\r
1005             return rc;\r
1006 \r
1007         dx_it++;\r
1008     }\r
1009 \r
1010     return rc2;\r
1011 }\r
1012 \r
1013 /**\r
1014  * @}\r
1015  */\r
1016 \r