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