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