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