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