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_crc32c.h"
  44 #include "ext4_hash.h"
  45
  46 #include <string.h>
  47 #include <stdlib.h>
  48
  49 /**@brief Get hash version used in directory index.
  50  * @param root_info Pointer to root info structure of index
  51  * @return Hash algorithm version
  52  */
  53 static inline uint8_t ext4_dir_dx_root_info_get_hash_version(
  54     struct ext4_directory_dx_root_info *root_info)
  55 {
  56         return root_info->hash_version;
  57 }
  58
  59 /**@brief Set hash version, that will be used in directory index.
  60  * @param root_info Pointer to root info structure of index
  61  * @param v Hash algorithm version
  62  */
  63 static inline void ext4_dir_dx_root_info_set_hash_version(
  64     struct ext4_directory_dx_root_info *root_info, uint8_t v)
  65 {
  66         root_info->hash_version = v;
  67 }
  68
  69 /**@brief Get length of root_info structure in bytes.
  70  * @param root_info Pointer to root info structure of index
  71  * @return Length of the structure
  72  */
  73 static inline uint8_t ext4_dir_dx_root_info_get_info_length(
  74     struct ext4_directory_dx_root_info *root_info)
  75 {
  76         return root_info->info_length;
  77 }
  78
  79 /**@brief Set length of root_info structure in bytes.
  80  * @param root_info   Pointer to root info structure of index
  81  * @param info_length Length of the structure
  82  */
  83 static inline void ext4_dir_dx_root_info_set_info_length(
  84     struct ext4_directory_dx_root_info *root_info, uint8_t len)
  85 {
  86         root_info->info_length = len;
  87 }
  88
  89 /**@brief Get number of indirect levels of HTree.
  90  * @param root_info Pointer to root info structure of index
  91  * @return Height of HTree (actually only 0 or 1)
  92  */
  93 static inline uint8_t ext4_dir_dx_root_info_get_indirect_levels(
  94     struct ext4_directory_dx_root_info *root_info)
  95 {
  96         return root_info->indirect_levels;
  97 }
  98
  99 /**@brief Set number of indirect levels of HTree.
 100  * @param root_info Pointer to root info structure of index
 101  * @param lvl Height of HTree (actually only 0 or 1)
 102  */
 103 static inline void ext4_dir_dx_root_info_set_indirect_levels(
 104     struct ext4_directory_dx_root_info *root_info, uint8_t lvl)
 105 {
 106         root_info->indirect_levels = lvl;
 107 }
 108
 109 /**@brief Get maximum number of index node entries.
 110  * @param climit Pointer to counlimit structure
 111  * @return Maximum of entries in node
 112  */
 113 static inline uint16_t
 114 ext4_dir_dx_countlimit_get_limit(struct ext4_directory_dx_countlimit *climit)
 115 {
 116         return to_le16(climit->limit);
 117 }
 118
 119 /**@brief Set maximum number of index node entries.
 120  * @param climit Pointer to counlimit structure
 121  * @param limit Maximum of entries in node
 122  */
 123 static inline void
 124 ext4_dir_dx_countlimit_set_limit(struct ext4_directory_dx_countlimit *climit,
 125                                  uint16_t limit)
 126 {
 127         climit->limit = to_le16(limit);
 128 }
 129
 130 /**@brief Get current number of index node entries.
 131  * @param climit Pointer to counlimit structure
 132  * @return Number of entries in node
 133  */
 134 static inline uint16_t
 135 ext4_dir_dx_countlimit_get_count(struct ext4_directory_dx_countlimit *climit)
 136 {
 137         return to_le16(climit->count);
 138 }
 139
 140 /**@brief Set current number of index node entries.
 141  * @param climit Pointer to counlimit structure
 142  * @param count Number of entries in node
 143  */
 144 static inline void
 145 ext4_dir_dx_countlimit_set_count(struct ext4_directory_dx_countlimit *climit,
 146                                  uint16_t count)
 147 {
 148         climit->count = to_le16(count);
 149 }
 150
 151 /**@brief Get hash value of index entry.
 152  * @param entry Pointer to index entry
 153  * @return Hash value
 154  */
 155 static inline uint32_t
 156 ext4_dir_dx_entry_get_hash(struct ext4_directory_dx_entry *entry)
 157 {
 158         return to_le32(entry->hash);
 159 }
 160
 161 /**@brief Set hash value of index entry.
 162  * @param entry Pointer to index entry
 163  * @param hash  Hash value
 164  */
 165 static inline void
 166 ext4_dir_dx_entry_set_hash(struct ext4_directory_dx_entry *entry, uint32_t hash)
 167 {
 168         entry->hash = to_le32(hash);
 169 }
 170
 171 /**@brief Get block address where child node is located.
 172  * @param entry Pointer to index entry
 173  * @return Block address of child node
 174  */
 175 static inline uint32_t
 176 ext4_dir_dx_entry_get_block(struct ext4_directory_dx_entry *entry)
 177 {
 178         return to_le32(entry->block);
 179 }
 180
 181 /**@brief Set block address where child node is located.
 182  * @param entry Pointer to index entry
 183  * @param block Block address of child node
 184  */
 185 static inline void
 186 ext4_dir_dx_entry_set_block(struct ext4_directory_dx_entry *entry,
 187                             uint32_t block)
 188 {
 189         entry->block = to_le32(block);
 190 }
 191
 192 /**@brief Sort entry item.*/
 193 struct ext4_dx_sort_entry {
 194         uint32_t hash;
 195         uint32_t rec_len;
 196         void *dentry;
 197 };
 198
 199 static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len,
 200                                    const char *name)
 201 {
 202         return ext2_htree_hash(name, len, hinfo->seed, hinfo->hash_version,
 203                                &hinfo->hash, &hinfo->minor_hash);
 204 }
 205
 206 static uint32_t
 207 ext4_dir_dx_checksum(struct ext4_inode_ref *inode_ref,
 208                  void *dirent,
 209                  int count_offset, int count, struct ext4_directory_dx_tail *t)
 210 {
 211         uint32_t orig_checksum, checksum = 0;
 212         struct ext4_sblock *sb = &inode_ref->fs->sb;
 213         int size;
 214
 215         /* Compute the checksum only if the filesystem supports it */
 216         if (ext4_sb_has_feature_read_only(sb,
 217                                 EXT4_FEATURE_RO_COMPAT_METADATA_CSUM)) {
 218                 size = count_offset +
 219                         (count * sizeof(struct ext4_directory_dx_tail));
 220                 orig_checksum = t->checksum;
 221                 t->checksum = 0;
 222                 /* First calculate crc32 checksum against fs uuid */
 223                 checksum = ext4_crc32c(~0, sb->uuid, sizeof(sb->uuid));
 224                 /* Then calculate crc32 checksum against all the dx_entry */
 225                 checksum = ext4_crc32c(checksum, dirent, size);
 226                 /* Finally calculate crc32 checksum for dx_tail */
 227                 checksum = ext4_crc32c(checksum, t,
 228                                 sizeof(struct ext4_directory_dx_tail));
 229                 t->checksum = orig_checksum;
 230         }
 231         return checksum;
 232 }
 233
 234 static struct ext4_directory_dx_countlimit *
 235 ext4_dir_dx_get_countlimit(struct ext4_inode_ref *inode_ref,
 236                         struct ext4_directory_entry_ll *dirent,
 237                         int *offset)
 238 {
 239         struct ext4_directory_entry_ll *dp;
 240         struct ext4_directory_dx_root *root;
 241         struct ext4_sblock *sb = &inode_ref->fs->sb;
 242         int count_offset;
 243
 244         if (ext4_dir_entry_ll_get_entry_length(dirent) ==
 245                         ext4_sb_get_block_size(sb))
 246                 count_offset = 8;
 247         else if (ext4_dir_entry_ll_get_entry_length(dirent) == 12) {
 248                 root = (struct ext4_directory_dx_root *)dirent;
 249                 dp = (struct ext4_directory_entry_ll *)&root->dots[1];
 250                 if (ext4_dir_entry_ll_get_entry_length(dp) !=
 251                     ext4_sb_get_block_size(sb) - 12)
 252                         return NULL;
 253                 if (root->info.reserved_zero ||
 254                     root->info.info_length != sizeof(struct ext4_directory_dx_root_info))
 255                         return NULL;
 256                 count_offset = 32;
 257         } else
 258                 return NULL;
 259
 260         if (offset)
 261                 *offset = count_offset;
 262         return (struct ext4_directory_dx_countlimit *)(((char *)dirent) + count_offset);
 263 }
 264
 265 /*
 266  * BIG FAT NOTES:
 267  *       Currently we do not verify the checksum of HTree node.
 268  */
 269 __unused static int
 270 ext4_dir_dx_checksum_verify(struct ext4_inode_ref *inode_ref,
 271                                 struct ext4_directory_entry_ll *dirent)
 272 {
 273         struct ext4_sblock *sb = &inode_ref->fs->sb;
 274         int count_offset, limit, count;
 275
 276         if (ext4_sb_has_feature_read_only(sb,
 277                                 EXT4_FEATURE_RO_COMPAT_METADATA_CSUM)) {
 278                 struct ext4_directory_dx_countlimit *countlimit =
 279                         ext4_dir_dx_get_countlimit(inode_ref, dirent, &count_offset);
 280                 if (!countlimit) {
 281                         /* Directory seems corrupted. */
 282                         return 1;
 283                 }
 284                 struct ext4_directory_dx_tail *t;
 285                 limit = ext4_dir_dx_countlimit_get_limit(countlimit);
 286                 count = ext4_dir_dx_countlimit_get_count(countlimit);
 287                 if (count_offset + (limit * sizeof(struct ext4_directory_dx_entry)) >
 288                                 ext4_sb_get_block_size(sb) -
 289                                 sizeof(struct ext4_directory_dx_tail)) {
 290                         /* There is no space to hold the checksum */
 291                         return 1;
 292                 }
 293                 t = (struct ext4_directory_dx_tail *)
 294                         (((struct ext4_directory_dx_entry *)countlimit) + limit);
 295
 296                 if (t->checksum != to_le32(ext4_dir_dx_checksum(inode_ref,
 297                                                                 dirent,
 298                                                                 count_offset,
 299                                                                 count, t)))
 300                         return 0;
 301         }
 302         return 1;
 303 }
 304
 305 static void
 306 ext4_dir_set_dx_checksum(struct ext4_inode_ref *inode_ref,
 307                         struct ext4_directory_entry_ll *dirent)
 308 {
 309         int count_offset, limit, count;
 310         struct ext4_sblock *sb = &inode_ref->fs->sb;
 311
 312         if (ext4_sb_has_feature_read_only(sb,
 313                                 EXT4_FEATURE_RO_COMPAT_METADATA_CSUM)) {
 314                 struct ext4_directory_dx_countlimit *countlimit =
 315                         ext4_dir_dx_get_countlimit(inode_ref, dirent, &count_offset);
 316                 if (!countlimit) {
 317                         /* Directory seems corrupted. */
 318                         return;
 319                 }
 320                 struct ext4_directory_dx_tail *t;
 321                 limit = ext4_dir_dx_countlimit_get_limit(countlimit);
 322                 count = ext4_dir_dx_countlimit_get_count(countlimit);
 323                 if (count_offset + (limit * sizeof(struct ext4_directory_dx_entry)) >
 324                                 ext4_sb_get_block_size(sb) -
 325                                 sizeof(struct ext4_directory_dx_tail)) {
 326                         /* There is no space to hold the checksum */
 327                         return;
 328                 }
 329                 t = (struct ext4_directory_dx_tail *)
 330                         (((struct ext4_directory_dx_entry *)countlimit) + limit);
 331
 332                 t->checksum =
 333                         to_le32(ext4_dir_dx_checksum(inode_ref, dirent, count_offset, count, t));
 334         }
 335 }
 336
 337 /****************************************************************************/
 338
 339 int ext4_dir_dx_init(struct ext4_inode_ref *dir)
 340 {
 341         /* Load block 0, where will be index root located */
 342         ext4_fsblk_t fblock;
 343         struct ext4_sblock *sb = &dir->fs->sb;
 344         int rc = ext4_fs_get_inode_data_block_index(dir, 0, &fblock, false);
 345         if (rc != EOK)
 346                 return rc;
 347
 348         struct ext4_block block;
 349         rc = ext4_block_get(dir->fs->bdev, &block, fblock);
 350         if (rc != EOK)
 351                 return rc;
 352
 353         /* Initialize pointers to data structures */
 354         struct ext4_directory_dx_root *root = (void *)block.data;
 355         struct ext4_directory_dx_root_info *info = &(root->info);
 356
 357         /* Initialize root info structure */
 358         uint8_t hash_version = ext4_get8(&dir->fs->sb, default_hash_version);
 359
 360         ext4_dir_dx_root_info_set_hash_version(info, hash_version);
 361         ext4_dir_dx_root_info_set_indirect_levels(info, 0);
 362         ext4_dir_dx_root_info_set_info_length(info, 8);
 363
 364         /* Set limit and current number of entries */
 365         struct ext4_directory_dx_countlimit *countlimit =
 366             (struct ext4_directory_dx_countlimit *)&root->entries;
 367
 368         ext4_dir_dx_countlimit_set_count(countlimit, 1);
 369
 370         uint32_t block_size = ext4_sb_get_block_size(&dir->fs->sb);
 371         uint32_t entry_space = block_size -
 372                                2 * sizeof(struct ext4_directory_dx_dot_entry) -
 373                                sizeof(struct ext4_directory_dx_root_info);
 374         if (ext4_sb_has_feature_read_only(sb,
 375                                           EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
 376                 entry_space -= sizeof(struct ext4_directory_dx_tail);
 377         uint16_t root_limit =
 378             entry_space / sizeof(struct ext4_directory_dx_entry);
 379
 380         ext4_dir_dx_countlimit_set_limit(countlimit, root_limit);
 381
 382         /* Append new block, where will be new entries inserted in the future */
 383         uint32_t iblock;
 384         rc = ext4_fs_append_inode_block(dir, &fblock, &iblock);
 385         if (rc != EOK) {
 386                 ext4_block_set(dir->fs->bdev, &block);
 387                 return rc;
 388         }
 389
 390         struct ext4_block new_block;
 391
 392         rc = ext4_block_get(dir->fs->bdev, &new_block, fblock);
 393         if (rc != EOK) {
 394                 ext4_block_set(dir->fs->bdev, &block);
 395                 return rc;
 396         }
 397
 398         /* Fill the whole block with empty entry */
 399         struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;
 400
 401         if (ext4_sb_has_feature_read_only(sb,
 402                                           EXT4_FEATURE_RO_COMPAT_METADATA_CSUM)) {
 403                 ext4_dir_entry_ll_set_entry_length(block_entry,
 404                                 block_size -
 405                                 sizeof(struct ext4_directory_entry_tail));
 406                 ext4_dir_entry_ll_set_name_length(sb,
 407                                                   block_entry,
 408                                                   0);
 409                 ext4_dir_entry_ll_set_inode_type(sb,
 410                                                  block_entry,
 411                                                  EXT4_DIRENTRY_UNKNOWN);
 412
 413                 initialize_dir_tail(EXT4_DIRENT_TAIL(block_entry,
 414                                         ext4_sb_get_block_size(sb)));
 415                 ext4_dir_set_checksum(dir,
 416                                 (struct ext4_directory_entry_ll *)new_block.data);
 417         } else {
 418                 ext4_dir_entry_ll_set_entry_length(block_entry, block_size);
 419         }
 420
 421         ext4_dir_entry_ll_set_inode(block_entry, 0);
 422
 423         new_block.dirty = true;
 424         rc = ext4_block_set(dir->fs->bdev, &new_block);
 425         if (rc != EOK) {
 426                 ext4_block_set(dir->fs->bdev, &block);
 427                 return rc;
 428         }
 429
 430         /* Connect new block to the only entry in index */
 431         struct ext4_directory_dx_entry *entry = root->entries;
 432         ext4_dir_dx_entry_set_block(entry, iblock);
 433
 434         ext4_dir_set_dx_checksum(dir,
 435                         (struct ext4_directory_entry_ll *)block.data);
 436         block.dirty = true;
 437
 438         return ext4_block_set(dir->fs->bdev, &block);
 439 }
 440
 441 /**@brief Initialize hash info structure necessary for index operations.
 442  * @param hinfo      Pointer to hinfo to be initialized
 443  * @param root_block Root block (number 0) of index
 444  * @param sb         Pointer to superblock
 445  * @param name_len   Length of name to be computed hash value from
 446  * @param name       Name to be computed hash value from
 447  * @return Standard error code
 448  */
 449 static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo,
 450                                struct ext4_block *root_block,
 451                                struct ext4_sblock *sb, size_t name_len,
 452                                const char *name)
 453 {
 454         struct ext4_directory_dx_root *root =
 455             (struct ext4_directory_dx_root *)root_block->data;
 456
 457         if ((root->info.hash_version != EXT2_HTREE_LEGACY) &&
 458             (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&
 459             (root->info.hash_version != EXT2_HTREE_TEA))
 460                 return EXT4_ERR_BAD_DX_DIR;
 461
 462         /* Check unused flags */
 463         if (root->info.unused_flags != 0)
 464                 return EXT4_ERR_BAD_DX_DIR;
 465
 466         /* Check indirect levels */
 467         if (root->info.indirect_levels > 1)
 468                 return EXT4_ERR_BAD_DX_DIR;
 469
 470         /* Check if node limit is correct */
 471         uint32_t block_size = ext4_sb_get_block_size(sb);
 472         uint32_t entry_space = block_size;
 473         entry_space -= 2 * sizeof(struct ext4_directory_dx_dot_entry);
 474         entry_space -= sizeof(struct ext4_directory_dx_root_info);
 475         entry_space = entry_space / sizeof(struct ext4_directory_dx_entry);
 476
 477         uint16_t limit = ext4_dir_dx_countlimit_get_limit(
 478             (struct ext4_directory_dx_countlimit *)&root->entries);
 479         if (limit != entry_space)
 480                 return EXT4_ERR_BAD_DX_DIR;
 481
 482         /* Check hash version and modify if necessary */
 483         hinfo->hash_version =
 484             ext4_dir_dx_root_info_get_hash_version(&root->info);
 485         if ((hinfo->hash_version <= EXT2_HTREE_TEA) &&
 486             (ext4_sb_check_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
 487                 /* Use unsigned hash */
 488                 hinfo->hash_version += 3;
 489         }
 490
 491         /* Load hash seed from superblock */
 492
 493         hinfo->seed = ext4_get8(sb, hash_seed);
 494
 495         /* Compute hash value of name */
 496         if (name)
 497                 return ext4_dir_dx_hash_string(hinfo, name_len, name);
 498
 499         return EOK;
 500 }
 501
 502 /**@brief Walk through index tree and load leaf with corresponding hash value.
 503  * @param hinfo      Initialized hash info structure
 504  * @param inode_ref  Current i-node
 505  * @param root_block Root block (iblock 0), where is root node located
 506  * @param dx_block   Pointer to leaf node in dx_blocks array
 507  * @param dx_blocks  Array with the whole path from root to leaf
 508  * @return Standard error code
 509  */
 510 static int ext4_dir_dx_get_leaf(struct ext4_hash_info *hinfo,
 511                                 struct ext4_inode_ref *inode_ref,
 512                                 struct ext4_block *root_block,
 513                                 struct ext4_directory_dx_block **dx_block,
 514                                 struct ext4_directory_dx_block *dx_blocks)
 515 {
 516         struct ext4_directory_dx_block *tmp_dx_block = dx_blocks;
 517         struct ext4_directory_dx_root *root =
 518             (struct ext4_directory_dx_root *)root_block->data;
 519         struct ext4_directory_dx_entry *entries =
 520             (struct ext4_directory_dx_entry *)&root->entries;
 521
 522         uint16_t limit = ext4_dir_dx_countlimit_get_limit(
 523             (struct ext4_directory_dx_countlimit *)entries);
 524         uint8_t indirect_level =
 525             ext4_dir_dx_root_info_get_indirect_levels(&root->info);
 526
 527         struct ext4_block *tmp_block = root_block;
 528         struct ext4_directory_dx_entry *p;
 529         struct ext4_directory_dx_entry *q;
 530         struct ext4_directory_dx_entry *m;
 531         struct ext4_directory_dx_entry *at;
 532
 533         /* Walk through the index tree */
 534         while (true) {
 535                 uint16_t count = ext4_dir_dx_countlimit_get_count(
 536                     (struct ext4_directory_dx_countlimit *)entries);
 537                 if ((count == 0) || (count > limit))
 538                         return EXT4_ERR_BAD_DX_DIR;
 539
 540                 /* Do binary search in every node */
 541                 p = entries + 1;
 542                 q = entries + count - 1;
 543
 544                 while (p <= q) {
 545                         m = p + (q - p) / 2;
 546                         if (ext4_dir_dx_entry_get_hash(m) > hinfo->hash)
 547                                 q = m - 1;
 548                         else
 549                                 p = m + 1;
 550                 }
 551
 552                 at = p - 1;
 553
 554                 /* Write results */
 555
 556                 memcpy(&tmp_dx_block->block, tmp_block,
 557                        sizeof(struct ext4_block));
 558                 tmp_dx_block->entries = entries;
 559                 tmp_dx_block->position = at;
 560
 561                 /* Is algorithm in the leaf? */
 562                 if (indirect_level == 0) {
 563                         *dx_block = tmp_dx_block;
 564                         return EOK;
 565                 }
 566
 567                 /* Goto child node */
 568                 uint32_t next_block = ext4_dir_dx_entry_get_block(at);
 569
 570                 indirect_level--;
 571
 572                 ext4_fsblk_t fblock;
 573                 int rc = ext4_fs_get_inode_data_block_index(
 574                     inode_ref, next_block, &fblock, false);
 575                 if (rc != EOK)
 576                         return rc;
 577
 578                 rc = ext4_block_get(inode_ref->fs->bdev, tmp_block, fblock);
 579                 if (rc != EOK)
 580                         return rc;
 581
 582                 entries =
 583                     ((struct ext4_directory_dx_node *)tmp_block->data)->entries;
 584                 limit = ext4_dir_dx_countlimit_get_limit(
 585                     (struct ext4_directory_dx_countlimit *)entries);
 586
 587                 uint16_t entry_space =
 588                     ext4_sb_get_block_size(&inode_ref->fs->sb) -
 589                     sizeof(struct ext4_fake_directory_entry);
 590
 591                 entry_space =
 592                     entry_space / sizeof(struct ext4_directory_dx_entry);
 593
 594                 if (limit != entry_space) {
 595                         ext4_block_set(inode_ref->fs->bdev, tmp_block);
 596                         return EXT4_ERR_BAD_DX_DIR;
 597                 }
 598
 599                 ++tmp_dx_block;
 600         }
 601
 602         /* Unreachable */
 603         return EOK;
 604 }
 605
 606 /**@brief Check if the the next block would be checked during entry search.
 607  * @param inode_ref Directory i-node
 608  * @param hash      Hash value to check
 609  * @param dx_block  Current block
 610  * @param dx_blocks Array with path from root to leaf node
 611  * @return Standard Error code
 612  */
 613 static int ext4_dir_dx_next_block(struct ext4_inode_ref *inode_ref,
 614                                   uint32_t hash,
 615                                   struct ext4_directory_dx_block *dx_block,
 616                                   struct ext4_directory_dx_block *dx_blocks)
 617 {
 618         uint32_t num_handles = 0;
 619         struct ext4_directory_dx_block *p = dx_block;
 620
 621         /* Try to find data block with next bunch of entries */
 622         while (true) {
 623                 p->position++;
 624                 uint16_t count = ext4_dir_dx_countlimit_get_count(
 625                     (struct ext4_directory_dx_countlimit *)p->entries);
 626
 627                 if (p->position < p->entries + count)
 628                         break;
 629
 630                 if (p == dx_blocks)
 631                         return EOK;
 632
 633                 num_handles++;
 634                 p--;
 635         }
 636
 637         /* Check hash collision (if not occurred - no next block cannot be
 638          * used)*/
 639         uint32_t current_hash = ext4_dir_dx_entry_get_hash(p->position);
 640         if ((hash & 1) == 0) {
 641                 if ((current_hash & ~1) != hash)
 642                         return 0;
 643         }
 644
 645         /* Fill new path */
 646         while (num_handles--) {
 647                 uint32_t block_idx = ext4_dir_dx_entry_get_block(p->position);
 648                 ext4_fsblk_t block_addr;
 649
 650                 int rc = ext4_fs_get_inode_data_block_index(
 651                     inode_ref, block_idx, &block_addr, false);
 652                 if (rc != EOK)
 653                         return rc;
 654
 655                 struct ext4_block block;
 656                 rc = ext4_block_get(inode_ref->fs->bdev, &block, block_addr);
 657                 if (rc != EOK)
 658                         return rc;
 659
 660                 p++;
 661
 662                 /* Don't forget to put old block (prevent memory leak) */
 663                 rc = ext4_block_set(inode_ref->fs->bdev, &p->block);
 664                 if (rc != EOK)
 665                         return rc;
 666
 667                 memcpy(&p->block, &block, sizeof(block));
 668                 p->entries =
 669                     ((struct ext4_directory_dx_node *)block.data)->entries;
 670                 p->position = p->entries;
 671         }
 672
 673         return ENOENT;
 674 }
 675
 676 int ext4_dir_dx_find_entry(struct ext4_directory_search_result *result,
 677                            struct ext4_inode_ref *inode_ref, size_t name_len,
 678                            const char *name)
 679 {
 680         /* Load direct block 0 (index root) */
 681         ext4_fsblk_t root_block_addr;
 682         int rc2;
 683         int rc =
 684             ext4_fs_get_inode_data_block_index(inode_ref,
 685                             0, &root_block_addr, false);
 686         if (rc != EOK)
 687                 return rc;
 688
 689         struct ext4_fs *fs = inode_ref->fs;
 690
 691         struct ext4_block root_block;
 692         rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);
 693         if (rc != EOK)
 694                 return rc;
 695
 696         /* Initialize hash info (compute hash value) */
 697         struct ext4_hash_info hinfo;
 698         rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);
 699         if (rc != EOK) {
 700                 ext4_block_set(fs->bdev, &root_block);
 701                 return EXT4_ERR_BAD_DX_DIR;
 702         }
 703
 704         /*
 705          * Hardcoded number 2 means maximum height of index tree,
 706          * specified in the Linux driver.
 707          */
 708         struct ext4_directory_dx_block dx_blocks[2];
 709         struct ext4_directory_dx_block *dx_block;
 710         struct ext4_directory_dx_block *tmp;
 711
 712         rc = ext4_dir_dx_get_leaf(&hinfo, inode_ref, &root_block, &dx_block,
 713                                   dx_blocks);
 714         if (rc != EOK) {
 715                 ext4_block_set(fs->bdev, &root_block);
 716                 return EXT4_ERR_BAD_DX_DIR;
 717         }
 718
 719         do {
 720                 /* Load leaf block */
 721                 uint32_t leaf_block_idx =
 722                     ext4_dir_dx_entry_get_block(dx_block->position);
 723                 ext4_fsblk_t leaf_block_addr;
 724
 725                 rc = ext4_fs_get_inode_data_block_index(
 726                     inode_ref, leaf_block_idx, &leaf_block_addr,
 727                     false);
 728                 if (rc != EOK)
 729                         goto cleanup;
 730
 731                 struct ext4_block leaf_block;
 732                 rc = ext4_block_get(fs->bdev, &leaf_block, leaf_block_addr);
 733                 if (rc != EOK)
 734                         goto cleanup;
 735
 736                 /* Linear search inside block */
 737                 struct ext4_directory_entry_ll *res_dentry;
 738                 rc = ext4_dir_find_in_block(&leaf_block, &fs->sb, name_len,
 739                                             name, &res_dentry);
 740
 741                 /* Found => return it */
 742                 if (rc == EOK) {
 743                         result->block = leaf_block;
 744                         result->dentry = res_dentry;
 745                         goto cleanup;
 746                 }
 747
 748                 /* Not found, leave untouched */
 749                 rc2 = ext4_block_set(fs->bdev, &leaf_block);
 750                 if (rc2 != EOK)
 751                         goto cleanup;
 752
 753                 if (rc != ENOENT)
 754                         goto cleanup;
 755
 756                 /* check if the next block could be checked */
 757                 rc = ext4_dir_dx_next_block(inode_ref, hinfo.hash, dx_block,
 758                                             &dx_blocks[0]);
 759                 if (rc < 0)
 760                         goto cleanup;
 761         } while (rc == ENOENT);
 762
 763         /* Entry not found */
 764         rc = ENOENT;
 765
 766 cleanup:
 767         /* The whole path must be released (preventing memory leak) */
 768         tmp = dx_blocks;
 769
 770         while (tmp <= dx_block) {
 771                 rc2 = ext4_block_set(fs->bdev, &tmp->block);
 772                 if (rc == EOK && rc2 != EOK)
 773                         rc = rc2;
 774                 ++tmp;
 775         }
 776
 777         return rc;
 778 }
 779
 780 #if CONFIG_DIR_INDEX_COMB_SORT
 781 #define SWAP_ENTRY(se1, se2)                                                   \
 782         do {                                                                   \
 783                 struct ext4_dx_sort_entry tmp = se1;                           \
 784                 se1 = se2;                                                     \
 785                 se2 = tmp;                                                     \
 786         \
 787 } while (0)
 788
 789 static void comb_sort(struct ext4_dx_sort_entry *se, uint32_t count)
 790 {
 791         struct ext4_dx_sort_entry *p, *q, *top = se + count - 1;
 792         bool more;
 793         /* Combsort */
 794         while (count > 2) {
 795                 count = (count * 10) / 13;
 796                 if (count - 9 < 2)
 797                         count = 11;
 798                 for (p = top, q = p - count; q >= se; p--, q--)
 799                         if (p->hash < q->hash)
 800                                 SWAP_ENTRY(*p, *q);
 801         }
 802         /* Bubblesort */
 803         do {
 804                 more = 0;
 805                 q = top;
 806                 while (q-- > se) {
 807                         if (q[1].hash >= q[0].hash)
 808                                 continue;
 809                         SWAP_ENTRY(*(q + 1), *q);
 810                         more = 1;
 811                 }
 812         } while (more);
 813 }
 814 #else
 815
 816 /**@brief  Compare function used to pass in quicksort implementation.
 817  *         It can compare two entries by hash value.
 818  * @param arg1  First entry
 819  * @param arg2  Second entry
 820  * @param dummy Unused parameter, can be NULL
 821  *
 822  * @return Classic compare result
 823  *         (0: equal, -1: arg1 < arg2, 1: arg1 > arg2)
 824  */
 825 static int ext4_dir_dx_entry_comparator(const void *arg1, const void *arg2)
 826 {
 827         struct ext4_dx_sort_entry *entry1 = (void *)arg1;
 828         struct ext4_dx_sort_entry *entry2 = (void *)arg2;
 829
 830         if (entry1->hash == entry2->hash)
 831                 return 0;
 832
 833         if (entry1->hash < entry2->hash)
 834                 return -1;
 835         else
 836                 return 1;
 837 }
 838 #endif
 839
 840 /**@brief  Insert new index entry to block.
 841  *         Note that space for new entry must be checked by caller.
 842  * @param inode_ref   Directory i-node
 843  * @param index_block Block where to insert new entry
 844  * @param hash        Hash value covered by child node
 845  * @param iblock      Logical number of child block
 846  *
 847  */
 848 static void
 849 ext4_dir_dx_insert_entry(struct ext4_inode_ref *inode_ref,
 850                          struct ext4_directory_dx_block *index_block,
 851                          uint32_t hash, uint32_t iblock)
 852 {
 853         struct ext4_directory_dx_entry *old_index_entry = index_block->position;
 854         struct ext4_directory_dx_entry *new_index_entry = old_index_entry + 1;
 855
 856         struct ext4_directory_dx_countlimit *countlimit =
 857             (struct ext4_directory_dx_countlimit *)index_block->entries;
 858         uint32_t count = ext4_dir_dx_countlimit_get_count(countlimit);
 859
 860         struct ext4_directory_dx_entry *start_index = index_block->entries;
 861         size_t bytes =
 862             (uint8_t *)(start_index + count) - (uint8_t *)(new_index_entry);
 863
 864         memmove(new_index_entry + 1, new_index_entry, bytes);
 865
 866         ext4_dir_dx_entry_set_block(new_index_entry, iblock);
 867         ext4_dir_dx_entry_set_hash(new_index_entry, hash);
 868
 869         ext4_dir_dx_countlimit_set_count(countlimit, count + 1);
 870
 871         ext4_dir_set_dx_checksum(inode_ref,
 872                         (struct ext4_directory_entry_ll *)index_block->block.data);
 873         index_block->block.dirty = true;
 874 }
 875
 876 /**@brief Split directory entries to two parts preventing node overflow.
 877  * @param inode_ref      Directory i-node
 878  * @param hinfo          Hash info
 879  * @param old_data_block Block with data to be split
 880  * @param index_block    Block where index entries are located
 881  * @param new_data_block Output value for newly allocated data block
 882  */
 883 static int ext4_dir_dx_split_data(struct ext4_inode_ref *inode_ref,
 884                                   struct ext4_hash_info *hinfo,
 885                                   struct ext4_block *old_data_block,
 886                                   struct ext4_directory_dx_block *index_block,
 887                                   struct ext4_block *new_data_block)
 888 {
 889         int rc = EOK;
 890
 891         /* Allocate buffer for directory entries */
 892         uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
 893
 894         uint8_t *entry_buffer = malloc(block_size);
 895         if (entry_buffer == NULL)
 896                 return ENOMEM;
 897
 898         /* dot entry has the smallest size available */
 899         uint32_t max_entry_count =
 900             block_size / sizeof(struct ext4_directory_dx_dot_entry);
 901
 902         /* Allocate sort entry */
 903         struct ext4_dx_sort_entry *sort_array =
 904             malloc(max_entry_count * sizeof(struct ext4_dx_sort_entry));
 905
 906         if (sort_array == NULL) {
 907                 free(entry_buffer);
 908                 return ENOMEM;
 909         }
 910
 911         uint32_t idx = 0;
 912         uint32_t real_size = 0;
 913
 914         /* Initialize hinfo */
 915         struct ext4_hash_info tmp_hinfo;
 916         memcpy(&tmp_hinfo, hinfo, sizeof(struct ext4_hash_info));
 917
 918         /* Load all valid entries to the buffer */
 919         struct ext4_directory_entry_ll *dentry = (void *)old_data_block->data;
 920         uint8_t *entry_buffer_ptr = entry_buffer;
 921         while ((void *)dentry < (void *)(old_data_block->data + block_size)) {
 922                 /* Read only valid entries */
 923                 if (ext4_dir_entry_ll_get_inode(dentry) &&
 924                     dentry->name_length) {
 925                         uint8_t len = ext4_dir_entry_ll_get_name_length(
 926                             &inode_ref->fs->sb, dentry);
 927
 928                         rc = ext4_dir_dx_hash_string(&tmp_hinfo, len,
 929                                                      (char *)dentry->name);
 930                         if (rc != EOK) {
 931                                 free(sort_array);
 932                                 free(entry_buffer);
 933                                 return rc;
 934                         }
 935
 936                         uint32_t rec_len = 8 + len;
 937
 938                         if ((rec_len % 4) != 0)
 939                                 rec_len += 4 - (rec_len % 4);
 940
 941                         memcpy(entry_buffer_ptr, dentry, rec_len);
 942
 943                         sort_array[idx].dentry = entry_buffer_ptr;
 944                         sort_array[idx].rec_len = rec_len;
 945                         sort_array[idx].hash = tmp_hinfo.hash;
 946
 947                         entry_buffer_ptr += rec_len;
 948                         real_size += rec_len;
 949                         idx++;
 950                 }
 951
 952                 dentry = (void *)((uint8_t *)dentry +
 953                                   ext4_dir_entry_ll_get_entry_length(dentry));
 954         }
 955
 956 /* Sort all entries */
 957 #if CONFIG_DIR_INDEX_COMB_SORT
 958         comb_sort(sort_array, idx);
 959 #else
 960         qsort(sort_array, idx, sizeof(struct ext4_dx_sort_entry),
 961               ext4_dir_dx_entry_comparator);
 962 #endif
 963         /* Allocate new block for store the second part of entries */
 964         ext4_fsblk_t new_fblock;
 965         uint32_t new_iblock;
 966         rc = ext4_fs_append_inode_block(inode_ref, &new_fblock, &new_iblock);
 967         if (rc != EOK) {
 968                 free(sort_array);
 969                 free(entry_buffer);
 970                 return rc;
 971         }
 972
 973         /* Load new block */
 974         struct ext4_block new_data_block_tmp;
 975         rc = ext4_block_get(inode_ref->fs->bdev, &new_data_block_tmp,
 976                             new_fblock);
 977         if (rc != EOK) {
 978                 free(sort_array);
 979                 free(entry_buffer);
 980                 return rc;
 981         }
 982
 983         /*
 984          * Distribute entries to two blocks (by size)
 985          * - compute the half
 986          */
 987         uint32_t new_hash = 0;
 988         uint32_t current_size = 0;
 989         uint32_t mid = 0;
 990         uint32_t i;
 991         for (i = 0; i < idx; ++i) {
 992                 if ((current_size + sort_array[i].rec_len) > (block_size / 2)) {
 993                         new_hash = sort_array[i].hash;
 994                         mid = i;
 995                         break;
 996                 }
 997
 998                 current_size += sort_array[i].rec_len;
 999         }
1000
1001         /* Check hash collision */
1002         uint32_t continued = 0;
1003         if (new_hash == sort_array[mid - 1].hash)
1004                 continued = 1;
1005
1006         uint32_t offset = 0;
1007         void *ptr;
1008
1009         if (ext4_sb_has_feature_read_only(&inode_ref->fs->sb,
1010                                           EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
1011                 block_size -= sizeof(struct ext4_directory_entry_tail);
1012
1013         /* First part - to the old block */
1014         for (i = 0; i < mid; ++i) {
1015                 ptr = old_data_block->data + offset;
1016                 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
1017
1018                 struct ext4_directory_entry_ll *tmp = ptr;
1019                 if (i < (mid - 1))
1020                         ext4_dir_entry_ll_set_entry_length(
1021                             tmp, sort_array[i].rec_len);
1022                 else
1023                         ext4_dir_entry_ll_set_entry_length(tmp,
1024                                                            block_size - offset);
1025
1026                 offset += sort_array[i].rec_len;
1027         }
1028
1029         /* Second part - to the new block */
1030         offset = 0;
1031         for (i = mid; i < idx; ++i) {
1032                 ptr = new_data_block_tmp.data + offset;
1033                 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
1034
1035                 struct ext4_directory_entry_ll *tmp = ptr;
1036                 if (i < (idx - 1))
1037                         ext4_dir_entry_ll_set_entry_length(
1038                             tmp, sort_array[i].rec_len);
1039                 else
1040                         ext4_dir_entry_ll_set_entry_length(tmp,
1041                                                            block_size - offset);
1042
1043                 offset += sort_array[i].rec_len;
1044         }
1045
1046         block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
1047
1048         /* Do some steps to finish operation */
1049         if (ext4_sb_has_feature_read_only(&inode_ref->fs->sb,
1050                                           EXT4_FEATURE_RO_COMPAT_METADATA_CSUM)) {
1051                 initialize_dir_tail(EXT4_DIRENT_TAIL(old_data_block->data,
1052                                         block_size));
1053                 initialize_dir_tail(EXT4_DIRENT_TAIL(new_data_block_tmp.data,
1054                                         block_size));
1055         }
1056         ext4_dir_set_checksum(inode_ref,
1057                         (struct ext4_directory_entry_ll *)old_data_block->data);
1058         ext4_dir_set_checksum(inode_ref,
1059                         (struct ext4_directory_entry_ll *)new_data_block_tmp.data);
1060         old_data_block->dirty = true;
1061         new_data_block_tmp.dirty = true;
1062
1063         free(sort_array);
1064         free(entry_buffer);
1065
1066         ext4_dir_dx_insert_entry(inode_ref,
1067                         index_block,
1068                         new_hash + continued, new_iblock);
1069
1070         *new_data_block = new_data_block_tmp;
1071
1072         return EOK;
1073 }
1074
1075 /**@brief  Split index node and maybe some parent nodes in the tree hierarchy.
1076  * @param inode_ref Directory i-node
1077  * @param dx_blocks Array with path from root to leaf node
1078  * @param dx_block  Leaf block to be split if needed
1079  * @return Error code
1080  */
1081 static int
1082 ext4_dir_dx_split_index(struct ext4_inode_ref *inode_ref,
1083                         struct ext4_directory_dx_block *dx_blocks,
1084                         struct ext4_directory_dx_block *dx_block,
1085                         struct ext4_directory_dx_block **new_dx_block)
1086 {
1087         struct ext4_sblock *sb = &inode_ref->fs->sb;
1088         struct ext4_directory_dx_entry *entries;
1089
1090         if (dx_block == dx_blocks)
1091                 entries =
1092                     ((struct ext4_directory_dx_root *)dx_block->block.data)
1093                         ->entries;
1094         else
1095                 entries =
1096                     ((struct ext4_directory_dx_node *)dx_block->block.data)
1097                         ->entries;
1098
1099         struct ext4_directory_dx_countlimit *countlimit =
1100             (struct ext4_directory_dx_countlimit *)entries;
1101
1102         uint16_t leaf_limit = ext4_dir_dx_countlimit_get_limit(countlimit);
1103         uint16_t leaf_count = ext4_dir_dx_countlimit_get_count(countlimit);
1104
1105         /* Check if is necessary to split index block */
1106         if (leaf_limit == leaf_count) {
1107                 size_t levels = dx_block - dx_blocks;
1108
1109                 struct ext4_directory_dx_entry *root_entries =
1110                     ((struct ext4_directory_dx_root *)dx_blocks[0].block.data)
1111                         ->entries;
1112
1113                 struct ext4_directory_dx_countlimit *root_countlimit =
1114                     (struct ext4_directory_dx_countlimit *)root_entries;
1115                 uint16_t root_limit =
1116                     ext4_dir_dx_countlimit_get_limit(root_countlimit);
1117                 uint16_t root_count =
1118                     ext4_dir_dx_countlimit_get_count(root_countlimit);
1119
1120                 /* Linux limitation */
1121                 if ((levels > 0) && (root_limit == root_count))
1122                         return ENOSPC;
1123
1124                 /* Add new block to directory */
1125                 ext4_fsblk_t new_fblock;
1126                 uint32_t new_iblock;
1127                 int rc = ext4_fs_append_inode_block(inode_ref, &new_fblock,
1128                                                     &new_iblock);
1129                 if (rc != EOK)
1130                         return rc;
1131
1132                 /* load new block */
1133                 struct ext4_block new_block;
1134                 rc =
1135                     ext4_block_get(inode_ref->fs->bdev, &new_block, new_fblock);
1136                 if (rc != EOK)
1137                         return rc;
1138
1139                 struct ext4_directory_dx_node *new_node =
1140                     (void *)new_block.data;
1141                 struct ext4_directory_dx_entry *new_entries = new_node->entries;
1142
1143                 memset(&new_node->fake, 0,
1144                        sizeof(struct ext4_fake_directory_entry));
1145
1146                 uint32_t block_size =
1147                     ext4_sb_get_block_size(&inode_ref->fs->sb);
1148
1149                 new_node->fake.entry_length = block_size;
1150
1151                 /* Split leaf node */
1152                 if (levels > 0) {
1153                         uint32_t count_left = leaf_count / 2;
1154                         uint32_t count_right = leaf_count - count_left;
1155                         uint32_t hash_right =
1156                             ext4_dir_dx_entry_get_hash(entries + count_left);
1157
1158                         /* Copy data to new node */
1159                         memcpy((void *)new_entries,
1160                                (void *)(entries + count_left),
1161                                count_right *
1162                                    sizeof(struct ext4_directory_dx_entry));
1163
1164                         /* Initialize new node */
1165                         struct ext4_directory_dx_countlimit *left_countlimit =
1166                             (struct ext4_directory_dx_countlimit *)entries;
1167                         struct ext4_directory_dx_countlimit *right_countlimit =
1168                             (struct ext4_directory_dx_countlimit *)new_entries;
1169
1170                         ext4_dir_dx_countlimit_set_count(left_countlimit,
1171                                                          count_left);
1172                         ext4_dir_dx_countlimit_set_count(right_countlimit,
1173                                                          count_right);
1174
1175                         uint32_t entry_space =
1176                             block_size -
1177                             sizeof(struct ext4_fake_directory_entry);
1178                         if (ext4_sb_has_feature_read_only(sb,
1179                                                           EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
1180                                 entry_space -= sizeof(struct ext4_directory_dx_tail);
1181                         uint32_t node_limit =
1182                             entry_space /
1183                             sizeof(struct ext4_directory_dx_entry);
1184
1185                         ext4_dir_dx_countlimit_set_limit(right_countlimit,
1186                                                          node_limit);
1187
1188                         /* Which index block is target for new entry */
1189                         uint32_t position_index =
1190                             (dx_block->position - dx_block->entries);
1191                         if (position_index >= count_left) {
1192                                 ext4_dir_set_dx_checksum(
1193                                                 inode_ref,
1194                                                 (struct ext4_directory_entry_ll *)
1195                                                 dx_block->block.data);
1196                                 dx_block->block.dirty = true;
1197
1198                                 struct ext4_block block_tmp = dx_block->block;
1199
1200                                 dx_block->block = new_block;
1201
1202                                 dx_block->position =
1203                                     new_entries + position_index - count_left;
1204                                 dx_block->entries = new_entries;
1205
1206                                 new_block = block_tmp;
1207                         }
1208
1209                         /* Finally insert new entry */
1210                         ext4_dir_dx_insert_entry(inode_ref,
1211                                                  dx_blocks, hash_right,
1212                                                  new_iblock);
1213                         ext4_dir_set_dx_checksum(inode_ref,
1214                                                 (struct ext4_directory_entry_ll *)
1215                                                         dx_blocks[0].block.data);
1216                         ext4_dir_set_dx_checksum(inode_ref,
1217                                                 (struct ext4_directory_entry_ll *)
1218                                                         dx_blocks[1].block.data);
1219                         dx_blocks[0].block.dirty = true;
1220                         dx_blocks[1].block.dirty = true;
1221
1222                         ext4_dir_set_dx_checksum(inode_ref,
1223                                                 (struct ext4_directory_entry_ll *)
1224                                                         new_block.data);
1225                         new_block.dirty = true;
1226                         return ext4_block_set(inode_ref->fs->bdev, &new_block);
1227                 } else {
1228                         /* Create second level index */
1229
1230                         /* Copy data from root to child block */
1231                         memcpy((void *)new_entries, (void *)entries,
1232                                leaf_count *
1233                                    sizeof(struct ext4_directory_dx_entry));
1234
1235                         struct ext4_directory_dx_countlimit *new_countlimit =
1236                             (struct ext4_directory_dx_countlimit *)new_entries;
1237
1238                         uint32_t entry_space =
1239                             block_size -
1240                             sizeof(struct ext4_fake_directory_entry);
1241                         if (ext4_sb_has_feature_read_only(sb,
1242                                                           EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
1243                                 entry_space -= sizeof(struct ext4_directory_dx_tail);
1244                         uint32_t node_limit =
1245                             entry_space /
1246                             sizeof(struct ext4_directory_dx_entry);
1247                         ext4_dir_dx_countlimit_set_limit(new_countlimit,
1248                                                          node_limit);
1249
1250                         /* Set values in root node */
1251                         struct ext4_directory_dx_countlimit
1252                             *new_root_countlimit =
1253                                 (struct ext4_directory_dx_countlimit *)entries;
1254
1255                         ext4_dir_dx_countlimit_set_count(new_root_countlimit,
1256                                                          1);
1257                         ext4_dir_dx_entry_set_block(entries, new_iblock);
1258
1259                         ((struct ext4_directory_dx_root *)dx_blocks[0]
1260                              .block.data)
1261                             ->info.indirect_levels = 1;
1262
1263                         /* Add new entry to the path */
1264                         dx_block = dx_blocks + 1;
1265                         dx_block->position =
1266                             dx_blocks->position - entries + new_entries;
1267                         dx_block->entries = new_entries;
1268                         dx_block->block = new_block;
1269
1270                         *new_dx_block = dx_block;
1271
1272                         ext4_dir_set_dx_checksum(inode_ref,
1273                                                 (struct ext4_directory_entry_ll *)
1274                                                         dx_blocks[0].block.data);
1275                         ext4_dir_set_dx_checksum(inode_ref,
1276                                                 (struct ext4_directory_entry_ll *)
1277                                                         dx_blocks[1].block.data);
1278                         dx_blocks[0].block.dirty = true;
1279                         dx_blocks[1].block.dirty = true;
1280                 }
1281         }
1282
1283         return EOK;
1284 }
1285
1286 int ext4_dir_dx_add_entry(struct ext4_inode_ref *parent,
1287                           struct ext4_inode_ref *child, const char *name)
1288 {
1289         int rc2 = EOK;
1290
1291         /* Get direct block 0 (index root) */
1292         ext4_fsblk_t root_block_addr;
1293         int rc =
1294             ext4_fs_get_inode_data_block_index(parent,
1295                             0, &root_block_addr,
1296                             false);
1297         if (rc != EOK)
1298                 return rc;
1299
1300         struct ext4_fs *fs = parent->fs;
1301         struct ext4_block root_block;
1302
1303         rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);
1304         if (rc != EOK)
1305                 return rc;
1306
1307         /* Initialize hinfo structure (mainly compute hash) */
1308         uint32_t name_len = strlen(name);
1309         struct ext4_hash_info hinfo;
1310         rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);
1311         if (rc != EOK) {
1312                 ext4_block_set(fs->bdev, &root_block);
1313                 return EXT4_ERR_BAD_DX_DIR;
1314         }
1315
1316         /*
1317          * Hardcoded number 2 means maximum height of index
1318          * tree defined in Linux.
1319          */
1320         struct ext4_directory_dx_block dx_blocks[2];
1321         struct ext4_directory_dx_block *dx_block;
1322         struct ext4_directory_dx_block *dx_it;
1323
1324         rc = ext4_dir_dx_get_leaf(&hinfo, parent, &root_block, &dx_block,
1325                                   dx_blocks);
1326         if (rc != EOK) {
1327                 rc = EXT4_ERR_BAD_DX_DIR;
1328                 goto release_index;
1329         }
1330
1331         /* Try to insert to existing data block */
1332         uint32_t leaf_block_idx =
1333             ext4_dir_dx_entry_get_block(dx_block->position);
1334         ext4_fsblk_t leaf_block_addr;
1335         rc = ext4_fs_get_inode_data_block_index(parent, leaf_block_idx,
1336                                                 &leaf_block_addr,
1337                                                 false);
1338         if (rc != EOK)
1339                 goto release_index;
1340
1341         /*
1342          * Check if there is needed to split index node
1343          * (and recursively also parent nodes)
1344          */
1345         rc = ext4_dir_dx_split_index(parent, dx_blocks, dx_block, &dx_block);
1346         if (rc != EOK)
1347                 goto release_target_index;
1348
1349         struct ext4_block target_block;
1350         rc = ext4_block_get(fs->bdev, &target_block, leaf_block_addr);
1351         if (rc != EOK)
1352                 goto release_index;
1353
1354         /* Check if insert operation passed */
1355         rc = ext4_dir_try_insert_entry(&fs->sb, parent, &target_block, child, name,
1356                                        name_len);
1357         if (rc == EOK)
1358                 goto release_target_index;
1359
1360         /* Split entries to two blocks (includes sorting by hash value) */
1361         struct ext4_block new_block;
1362         rc = ext4_dir_dx_split_data(parent, &hinfo, &target_block, dx_block,
1363                                     &new_block);
1364         if (rc != EOK) {
1365                 rc2 = rc;
1366                 goto release_target_index;
1367         }
1368
1369         /* Where to save new entry */
1370         uint32_t new_block_hash =
1371             ext4_dir_dx_entry_get_hash(dx_block->position + 1);
1372         if (hinfo.hash >= new_block_hash)
1373                 rc = ext4_dir_try_insert_entry(&fs->sb, parent, &new_block, child, name,
1374                                                name_len);
1375         else
1376                 rc = ext4_dir_try_insert_entry(&fs->sb, parent, &target_block, child,
1377                                                name, name_len);
1378
1379         /* Cleanup */
1380         rc = ext4_block_set(fs->bdev, &new_block);
1381         if (rc != EOK)
1382                 return rc;
1383
1384 /* Cleanup operations */
1385
1386 release_target_index:
1387         rc2 = rc;
1388
1389         rc = ext4_block_set(fs->bdev, &target_block);
1390         if (rc != EOK)
1391                 return rc;
1392
1393 release_index:
1394         if (rc != EOK)
1395                 rc2 = rc;
1396
1397         dx_it = dx_blocks;
1398
1399         while (dx_it <= dx_block) {
1400                 rc = ext4_block_set(fs->bdev, &dx_it->block);
1401                 if (rc != EOK)
1402                         return rc;
1403
1404                 dx_it++;
1405         }
1406
1407         return rc2;
1408 }
1409
1410 int ext4_dir_dx_reset_parent_inode(struct ext4_inode_ref *dir,
1411                                    uint32_t parent_inode)
1412 {
1413         /* Load block 0, where will be index root located */
1414         ext4_fsblk_t fblock;
1415         int rc = ext4_fs_get_inode_data_block_index(dir, 0, &fblock, false);
1416         if (rc != EOK)
1417                 return rc;
1418
1419         struct ext4_block block;
1420         rc = ext4_block_get(dir->fs->bdev, &block, fblock);
1421         if (rc != EOK)
1422                 return rc;
1423
1424         /* Initialize pointers to data structures */
1425         struct ext4_directory_dx_root *root = (void *)block.data;
1426
1427         /* Fill the inode field with a new parent ino. */
1428         ext4_dx_dot_entry_set_inode(&root->dots[1], parent_inode);
1429
1430         ext4_dir_set_dx_checksum(dir,
1431                                 (struct ext4_directory_entry_ll *)
1432                                         block.data);
1433         block.dirty = true;
1434
1435         return ext4_block_set(dir->fs->bdev, &block);
1436 }
1437
1438 /**
1439  * @}
1440  */