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