lwext4/ext4_dir_idx.c

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