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