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