lwext4/ext4_dir.c

   1 /*
   2  * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
   3  *
   4  *
   5  * HelenOS:
   6  * Copyright (c) 2012 Martin Sucha
   7  * Copyright (c) 2012 Frantisek Princ
   8  * All rights reserved.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  *
  14  * - Redistributions of source code must retain the above copyright
  15  *   notice, this list of conditions and the following disclaimer.
  16  * - Redistributions in binary form must reproduce the above copyright
  17  *   notice, this list of conditions and the following disclaimer in the
  18  *   documentation and/or other materials provided with the distribution.
  19  * - The name of the author may not be used to endorse or promote products
  20  *   derived from this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  23  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  24  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  25  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  27  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  31  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 /** @addtogroup lwext4
  35  * @{
  36  */
  37 /**
  38  * @file  ext4_dir.h
  39  * @brief Directory handle procedures.
  40  */
  41
  42 #include "ext4_config.h"
  43 #include "ext4_dir.h"
  44 #include "ext4_dir_idx.h"
  45 #include "ext4_crc32c.h"
  46 #include "ext4_inode.h"
  47 #include "ext4_fs.h"
  48
  49 #include <string.h>
  50
  51 /****************************************************************************/
  52
  53 /* Walk through a dirent block to find a checksum "dirent" at the tail */
  54 static struct ext4_dir_entry_tail *
  55 ext4_dir_get_tail(struct ext4_inode_ref *inode_ref,
  56                 struct ext4_dir_entry_ll *de)
  57 {
  58         struct ext4_dir_entry_tail *t;
  59         struct ext4_sblock *sb = &inode_ref->fs->sb;
  60
  61         t = EXT4_DIRENT_TAIL(de, ext4_sb_get_block_size(sb));
  62
  63         if (t->reserved_zero1 ||
  64             to_le16(t->rec_len) != sizeof(struct ext4_dir_entry_tail) ||
  65             t->reserved_zero2 ||
  66             t->reserved_ft != EXT4_DIRENTRY_DIR_CSUM)
  67                 return NULL;
  68
  69         return t;
  70 }
  71
  72 #if CONFIG_META_CSUM_ENABLE
  73 static uint32_t ext4_dir_checksum(struct ext4_inode_ref *inode_ref,
  74                                struct ext4_dir_entry_ll *dirent, int size)
  75 {
  76         uint32_t checksum;
  77         struct ext4_sblock *sb = &inode_ref->fs->sb;
  78         uint32_t ino_index = to_le32(inode_ref->index);
  79         uint32_t ino_gen =
  80                 to_le32(ext4_inode_get_generation(inode_ref->inode));
  81
  82         /* First calculate crc32 checksum against fs uuid */
  83         checksum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid, sizeof(sb->uuid));
  84         /* Then calculate crc32 checksum against inode number
  85          * and inode generation */
  86         checksum = ext4_crc32c(checksum, &ino_index,
  87                              sizeof(ino_index));
  88         checksum = ext4_crc32c(checksum, &ino_gen,
  89                              sizeof(ino_gen));
  90         /* Finally calculate crc32 checksum against directory entries */
  91         checksum = ext4_crc32c(checksum, dirent, size);
  92         return checksum;
  93 }
  94 #else
  95 #define ext4_dir_checksum(...) 0
  96 #endif
  97
  98 bool
  99 ext4_dir_checksum_verify(struct ext4_inode_ref *inode_ref,
 100                          struct ext4_dir_entry_ll *dirent)
 101 {
 102 #ifdef CONFIG_META_CSUM_ENABLE
 103         struct ext4_dir_entry_tail *t;
 104         struct ext4_sblock *sb = &inode_ref->fs->sb;
 105
 106         /* Compute the checksum only if the filesystem supports it */
 107         if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
 108                 t = ext4_dir_get_tail(inode_ref, dirent);
 109                 if (!t) {
 110                         /* There is no space to hold the checksum */
 111                         return false;
 112                 }
 113
 114                 if (t->checksum != to_le32(ext4_dir_checksum(inode_ref, dirent,
 115                                         (char *)t - (char *)dirent)))
 116                         return false;
 117
 118         }
 119 #endif
 120         return true;
 121 }
 122
 123 /* checksumming functions */
 124 void initialize_dir_tail(struct ext4_dir_entry_tail *t)
 125 {
 126         memset(t, 0, sizeof(struct ext4_dir_entry_tail));
 127         t->rec_len = to_le16(sizeof(struct ext4_dir_entry_tail));
 128         t->reserved_ft = EXT4_DIRENTRY_DIR_CSUM;
 129 }
 130
 131 void ext4_dir_set_checksum(struct ext4_inode_ref *inode_ref,
 132                            struct ext4_dir_entry_ll *dirent)
 133 {
 134         struct ext4_dir_entry_tail *t;
 135         struct ext4_sblock *sb = &inode_ref->fs->sb;
 136
 137         /* Compute the checksum only if the filesystem supports it */
 138         if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
 139                 t = ext4_dir_get_tail(inode_ref, dirent);
 140                 if (!t) {
 141                         /* There is no space to hold the checksum */
 142                         return;
 143                 }
 144
 145                 t->checksum = to_le32(ext4_dir_checksum(inode_ref, dirent,
 146                                         (char *)t - (char *)dirent));
 147         }
 148 }
 149
 150 /**@brief Do some checks before returning iterator.
 151  * @param it Iterator to be checked
 152  * @param block_size Size of data block
 153  * @return Error code
 154  */
 155 static int ext4_dir_iterator_set(struct ext4_dir_iterator *it,
 156                                  uint32_t block_size)
 157 {
 158         it->current = NULL;
 159
 160         uint32_t offset_in_block = it->current_offset % block_size;
 161
 162         /* Ensure proper alignment */
 163         if ((offset_in_block % 4) != 0)
 164                 return EIO;
 165
 166         /* Ensure that the core of the entry does not overflow the block */
 167         if (offset_in_block > block_size - 8)
 168                 return EIO;
 169
 170         struct ext4_dir_entry_ll *entry =
 171             (void *)(it->current_block.data + offset_in_block);
 172
 173         /* Ensure that the whole entry does not overflow the block */
 174         uint16_t length = ext4_dir_entry_ll_get_entry_length(entry);
 175         if (offset_in_block + length > block_size)
 176                 return EIO;
 177
 178         /* Ensure the name length is not too large */
 179         if (ext4_dir_entry_ll_get_name_length(&it->inode_ref->fs->sb, entry) >
 180             length - 8)
 181                 return EIO;
 182
 183         /* Everything OK - "publish" the entry */
 184         it->current = entry;
 185         return EOK;
 186 }
 187
 188 /**@brief Seek to next valid directory entry.
 189  *        Here can be jumped to the next data block.
 190  * @param it  Initialized iterator
 191  * @param pos Position of the next entry
 192  * @return Error code
 193  */
 194 static int ext4_dir_iterator_seek(struct ext4_dir_iterator *it,
 195                                   uint64_t pos)
 196 {
 197         uint64_t size =
 198             ext4_inode_get_size(&it->inode_ref->fs->sb, it->inode_ref->inode);
 199
 200         /* The iterator is not valid until we seek to the desired position */
 201         it->current = NULL;
 202
 203         /* Are we at the end? */
 204         if (pos >= size) {
 205                 if (it->current_block.lb_id) {
 206
 207                         int rc = ext4_block_set(it->inode_ref->fs->bdev,
 208                                                 &it->current_block);
 209                         it->current_block.lb_id = 0;
 210
 211                         if (rc != EOK)
 212                                 return rc;
 213                 }
 214
 215                 it->current_offset = pos;
 216                 return EOK;
 217         }
 218
 219         /* Compute next block address */
 220         uint32_t block_size = ext4_sb_get_block_size(&it->inode_ref->fs->sb);
 221         uint64_t current_block_idx = it->current_offset / block_size;
 222         uint32_t next_block_idx = pos / block_size;
 223
 224         /*
 225          * If we don't have a block or are moving across block boundary,
 226          * we need to get another block
 227          */
 228         if ((it->current_block.lb_id == 0) ||
 229             (current_block_idx != next_block_idx)) {
 230                 if (it->current_block.lb_id) {
 231                         int rc = ext4_block_set(it->inode_ref->fs->bdev,
 232                                                 &it->current_block);
 233                         it->current_block.lb_id = 0;
 234
 235                         if (rc != EOK)
 236                                 return rc;
 237                 }
 238
 239                 ext4_fsblk_t next_block_phys_idx;
 240                 int rc = ext4_fs_get_inode_data_block_index(
 241                     it->inode_ref, next_block_idx,
 242                     &next_block_phys_idx,
 243                     false);
 244                 if (rc != EOK)
 245                         return rc;
 246
 247                 rc = ext4_block_get(it->inode_ref->fs->bdev, &it->current_block,
 248                                     next_block_phys_idx);
 249                 if (rc != EOK) {
 250                         it->current_block.lb_id = 0;
 251                         return rc;
 252                 }
 253         }
 254
 255         it->current_offset = pos;
 256
 257         return ext4_dir_iterator_set(it, block_size);
 258 }
 259
 260 int ext4_dir_iterator_init(struct ext4_dir_iterator *it,
 261                            struct ext4_inode_ref *inode_ref, uint64_t pos)
 262 {
 263         it->inode_ref = inode_ref;
 264         it->current = 0;
 265         it->current_offset = 0;
 266         it->current_block.lb_id = 0;
 267
 268         return ext4_dir_iterator_seek(it, pos);
 269 }
 270
 271 int ext4_dir_iterator_next(struct ext4_dir_iterator *it)
 272 {
 273         int r = EOK;
 274         uint16_t skip;
 275
 276         while (r == EOK) {
 277                 skip = ext4_dir_entry_ll_get_entry_length(it->current);
 278                 r = ext4_dir_iterator_seek(it, it->current_offset + skip);
 279
 280                 if (!it->current)
 281                         break;
 282                 /*Skip NULL referenced entry*/
 283                 if (ext4_dir_entry_ll_get_inode(it->current) != 0)
 284                         break;
 285         }
 286
 287         return r;
 288 }
 289
 290 int ext4_dir_iterator_fini(struct ext4_dir_iterator *it)
 291 {
 292         it->current = 0;
 293
 294         if (it->current_block.lb_id)
 295                 return ext4_block_set(it->inode_ref->fs->bdev,
 296                                       &it->current_block);
 297
 298         return EOK;
 299 }
 300
 301 void ext4_dir_write_entry(struct ext4_sblock *sb,
 302                           struct ext4_dir_entry_ll *entry,
 303                           uint16_t entry_len, struct ext4_inode_ref *child,
 304                           const char *name, size_t name_len)
 305 {
 306         /* Check maximum entry length */
 307         ext4_assert(entry_len <= ext4_sb_get_block_size(sb));
 308
 309         /* Set type of entry */
 310         switch (ext4_inode_type(sb, child->inode)) {
 311         case EXT4_INODE_MODE_DIRECTORY:
 312                 ext4_dir_entry_ll_set_inode_type(sb, entry,
 313                                                  EXT4_DIRENTRY_DIR);
 314                 break;
 315         case EXT4_INODE_MODE_FILE:
 316                 ext4_dir_entry_ll_set_inode_type(
 317                     sb, entry, EXT4_DIRENTRY_REG_FILE);
 318                 break;
 319         case EXT4_INODE_MODE_SOFTLINK:
 320                 ext4_dir_entry_ll_set_inode_type(
 321                     sb, entry, EXT4_DIRENTRY_SYMLINK);
 322                 break;
 323         default:
 324                 /* FIXME: right now we only support 3 inode type. */
 325                 ext4_assert(0);
 326         }
 327
 328         /* Set basic attributes */
 329         ext4_dir_entry_ll_set_inode(entry, child->index);
 330         ext4_dir_entry_ll_set_entry_length(entry, entry_len);
 331         ext4_dir_entry_ll_set_name_length(sb, entry, name_len);
 332
 333         /* Write name */
 334         memcpy(entry->name, name, name_len);
 335 }
 336
 337 int ext4_dir_add_entry(struct ext4_inode_ref *parent, const char *name,
 338                        uint32_t name_len, struct ext4_inode_ref *child)
 339 {
 340         struct ext4_fs *fs = parent->fs;
 341
 342 #if CONFIG_DIR_INDEX_ENABLE
 343         /* Index adding (if allowed) */
 344         if ((ext4_sb_feature_com(&fs->sb, EXT4_FCOM_DIR_INDEX)) &&
 345             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
 346                 int rc = ext4_dir_dx_add_entry(parent, child, name);
 347
 348                 /* Check if index is not corrupted */
 349                 if (rc != EXT4_ERR_BAD_DX_DIR) {
 350                         if (rc != EOK)
 351                                 return rc;
 352
 353                         return EOK;
 354                 }
 355
 356                 /* Needed to clear dir index flag if corrupted */
 357                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
 358                 parent->dirty = true;
 359         }
 360 #endif
 361
 362         /* Linear algorithm */
 363         uint32_t iblock = 0;
 364         ext4_fsblk_t fblock = 0;
 365         uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 366         uint32_t inode_size = ext4_inode_get_size(&fs->sb, parent->inode);
 367         uint32_t total_blocks = inode_size / block_size;
 368
 369         /* Find block, where is space for new entry and try to add */
 370         bool success = false;
 371         for (iblock = 0; iblock < total_blocks; ++iblock) {
 372                 int rc =
 373                     ext4_fs_get_inode_data_block_index(parent,
 374                                     iblock, &fblock,
 375                                     false);
 376                 if (rc != EOK)
 377                         return rc;
 378
 379                 struct ext4_block block;
 380                 rc = ext4_block_get(fs->bdev, &block, fblock);
 381                 if (rc != EOK)
 382                         return rc;
 383
 384                 if (!ext4_dir_checksum_verify(
 385                                 parent,
 386                                 (struct ext4_dir_entry_ll *)
 387                                         block.data)) {
 388                         ext4_dbg(DEBUG_DIR,
 389                                  DBG_WARN "Leaf block checksum failed."
 390                                  "Inode: %" PRIu32", "
 391                                  "Block: %" PRIu32"\n",
 392                                  parent->index,
 393                                  iblock);
 394                 }
 395
 396                 /* If adding is successful, function can finish */
 397                 rc = ext4_dir_try_insert_entry(&fs->sb, parent, &block, child, name,
 398                                                name_len);
 399                 if (rc == EOK)
 400                         success = true;
 401
 402                 rc = ext4_block_set(fs->bdev, &block);
 403                 if (rc != EOK)
 404                         return rc;
 405
 406                 if (success)
 407                         return EOK;
 408         }
 409
 410         /* No free block found - needed to allocate next data block */
 411
 412         iblock = 0;
 413         fblock = 0;
 414         int rc = ext4_fs_append_inode_block(parent, &fblock, &iblock);
 415         if (rc != EOK)
 416                 return rc;
 417
 418         /* Load new block */
 419         struct ext4_block new_block;
 420
 421         rc = ext4_block_get(fs->bdev, &new_block, fblock);
 422         if (rc != EOK)
 423                 return rc;
 424
 425         /* Fill block with zeroes */
 426         memset(new_block.data, 0, block_size);
 427         struct ext4_dir_entry_ll *block_entry = (void *)new_block.data;
 428
 429         /* Save new block */
 430         if (ext4_sb_feature_ro_com(&fs->sb, EXT4_FRO_COM_METADATA_CSUM)) {
 431                 ext4_dir_write_entry(&fs->sb, block_entry,
 432                                 block_size - sizeof(struct ext4_dir_entry_tail),
 433                                 child,
 434                                 name, name_len);
 435                 initialize_dir_tail(EXT4_DIRENT_TAIL(new_block.data,
 436                                         ext4_sb_get_block_size(&fs->sb)));
 437         } else
 438                 ext4_dir_write_entry(&fs->sb, block_entry, block_size, child, name,
 439                                      name_len);
 440
 441         ext4_dir_set_checksum(parent,
 442                         (struct ext4_dir_entry_ll *)new_block.data);
 443         new_block.dirty = true;
 444         rc = ext4_block_set(fs->bdev, &new_block);
 445
 446         return rc;
 447 }
 448
 449 int ext4_dir_find_entry(struct ext4_dir_search_result *result,
 450                         struct ext4_inode_ref *parent, const char *name,
 451                         uint32_t name_len)
 452 {
 453         struct ext4_sblock *sb = &parent->fs->sb;
 454
 455 #if CONFIG_DIR_INDEX_ENABLE
 456         /* Index search */
 457         if ((ext4_sb_feature_com(sb, EXT4_FCOM_DIR_INDEX)) &&
 458             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
 459                 int rc = ext4_dir_dx_find_entry(result, parent, name_len, name);
 460
 461                 /* Check if index is not corrupted */
 462                 if (rc != EXT4_ERR_BAD_DX_DIR) {
 463                         if (rc != EOK)
 464                                 return rc;
 465
 466                         return EOK;
 467                 }
 468
 469                 /* Needed to clear dir index flag if corrupted */
 470                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
 471                 parent->dirty = true;
 472         }
 473 #endif
 474
 475         /* Linear algorithm */
 476
 477         uint32_t iblock;
 478         ext4_fsblk_t fblock;
 479         uint32_t block_size = ext4_sb_get_block_size(sb);
 480         uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
 481         uint32_t total_blocks = inode_size / block_size;
 482
 483         /* Walk through all data blocks */
 484         for (iblock = 0; iblock < total_blocks; ++iblock) {
 485                 /* Load block address */
 486                 int rc =
 487                     ext4_fs_get_inode_data_block_index(parent,
 488                                     iblock, &fblock,
 489                                     false);
 490                 if (rc != EOK)
 491                         return rc;
 492
 493                 /* Load data block */
 494                 struct ext4_block block;
 495                 rc = ext4_block_get(parent->fs->bdev, &block, fblock);
 496                 if (rc != EOK)
 497                         return rc;
 498
 499                 if (!ext4_dir_checksum_verify(
 500                                 parent,
 501                                 (struct ext4_dir_entry_ll *)
 502                                         block.data)) {
 503                         ext4_dbg(DEBUG_DIR,
 504                                  DBG_WARN "Leaf block checksum failed."
 505                                  "Inode: %" PRIu32", "
 506                                  "Block: %" PRIu32"\n",
 507                                  parent->index,
 508                                  iblock);
 509                 }
 510
 511                 /* Try to find entry in block */
 512                 struct ext4_dir_entry_ll *res_entry;
 513                 rc = ext4_dir_find_in_block(&block, sb, name_len, name,
 514                                             &res_entry);
 515                 if (rc == EOK) {
 516                         result->block = block;
 517                         result->dentry = res_entry;
 518                         return EOK;
 519                 }
 520
 521                 /* Entry not found - put block and continue to the next block */
 522
 523                 rc = ext4_block_set(parent->fs->bdev, &block);
 524                 if (rc != EOK)
 525                         return rc;
 526         }
 527
 528         /* Entry was not found */
 529
 530         result->block.lb_id = 0;
 531         result->dentry = NULL;
 532
 533         return ENOENT;
 534 }
 535
 536 int ext4_dir_remove_entry(struct ext4_inode_ref *parent, const char *name,
 537                           uint32_t name_len)
 538 {
 539         /* Check if removing from directory */
 540         if (!ext4_inode_is_type(&parent->fs->sb, parent->inode,
 541                                 EXT4_INODE_MODE_DIRECTORY))
 542                 return ENOTDIR;
 543
 544         /* Try to find entry */
 545         struct ext4_dir_search_result result;
 546         int rc = ext4_dir_find_entry(&result, parent, name, name_len);
 547         if (rc != EOK)
 548                 return rc;
 549
 550         /* Invalidate entry */
 551         ext4_dir_entry_ll_set_inode(result.dentry, 0);
 552
 553         /* Store entry position in block */
 554         uint32_t pos = (uint8_t *)result.dentry - result.block.data;
 555
 556         /*
 557          * If entry is not the first in block, it must be merged
 558          * with previous entry
 559          */
 560         if (pos != 0) {
 561                 uint32_t offset = 0;
 562
 563                 /* Start from the first entry in block */
 564                 struct ext4_dir_entry_ll *tmp_dentry =
 565                     (void *)result.block.data;
 566                 uint16_t tmp_dentry_length =
 567                     ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 568
 569                 /* Find direct predecessor of removed entry */
 570                 while ((offset + tmp_dentry_length) < pos) {
 571                         offset +=
 572                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 573                         tmp_dentry = (void *)(result.block.data + offset);
 574                         tmp_dentry_length =
 575                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 576                 }
 577
 578                 ext4_assert(tmp_dentry_length + offset == pos);
 579
 580                 /* Add to removed entry length to predecessor's length */
 581                 uint16_t del_entry_length =
 582                     ext4_dir_entry_ll_get_entry_length(result.dentry);
 583                 ext4_dir_entry_ll_set_entry_length(
 584                     tmp_dentry, tmp_dentry_length + del_entry_length);
 585         }
 586
 587         ext4_dir_set_checksum(parent,
 588                         (struct ext4_dir_entry_ll *)result.block.data);
 589         result.block.dirty = true;
 590
 591         return ext4_dir_destroy_result(parent, &result);
 592 }
 593
 594 int ext4_dir_try_insert_entry(struct ext4_sblock *sb,
 595                               struct ext4_inode_ref *inode_ref,
 596                               struct ext4_block *target_block,
 597                               struct ext4_inode_ref *child, const char *name,
 598                               uint32_t name_len)
 599 {
 600         /* Compute required length entry and align it to 4 bytes */
 601         uint32_t block_size = ext4_sb_get_block_size(sb);
 602         uint16_t required_len =
 603             sizeof(struct ext4_fake_dir_entry) + name_len;
 604
 605         if ((required_len % 4) != 0)
 606                 required_len += 4 - (required_len % 4);
 607
 608         /* Initialize pointers, stop means to upper bound */
 609         struct ext4_dir_entry_ll *dentry = (void *)target_block->data;
 610         struct ext4_dir_entry_ll *stop =
 611             (void *)(target_block->data + block_size);
 612
 613         /*
 614          * Walk through the block and check for invalid entries
 615          * or entries with free space for new entry
 616          */
 617         while (dentry < stop) {
 618                 uint32_t inode = ext4_dir_entry_ll_get_inode(dentry);
 619                 uint16_t rec_len = ext4_dir_entry_ll_get_entry_length(dentry);
 620                 uint8_t inode_type = ext4_dir_entry_ll_get_inode_type(sb, dentry);
 621
 622                 /* If invalid and large enough entry, use it */
 623                 if ((inode == 0) &&
 624                     (inode_type != EXT4_DIRENTRY_DIR_CSUM) &&
 625                     (rec_len >= required_len)) {
 626                         ext4_dir_write_entry(sb, dentry, rec_len, child, name,
 627                                              name_len);
 628                         ext4_dir_set_checksum(inode_ref,
 629                                                 (struct ext4_dir_entry_ll *)
 630                                                 target_block->data);
 631                         target_block->dirty = true;
 632
 633                         return EOK;
 634                 }
 635
 636                 /* Valid entry, try to split it */
 637                 if (inode != 0) {
 638                         uint16_t used_name_len =
 639                             ext4_dir_entry_ll_get_name_length(sb, dentry);
 640
 641                         uint16_t used_space =
 642                             sizeof(struct ext4_fake_dir_entry) +
 643                             used_name_len;
 644
 645                         if ((used_name_len % 4) != 0)
 646                                 used_space += 4 - (used_name_len % 4);
 647
 648                         uint16_t free_space = rec_len - used_space;
 649
 650                         /* There is free space for new entry */
 651                         if (free_space >= required_len) {
 652                                 /* Cut tail of current entry */
 653                                 ext4_dir_entry_ll_set_entry_length(dentry,
 654                                                                    used_space);
 655                                 struct ext4_dir_entry_ll *new_entry =
 656                                     (void *)((uint8_t *)dentry + used_space);
 657                                 ext4_dir_write_entry(sb, new_entry, free_space,
 658                                                      child, name, name_len);
 659
 660                                 ext4_dir_set_checksum(inode_ref,
 661                                                 (struct ext4_dir_entry_ll *)
 662                                                 target_block->data);
 663                                 target_block->dirty = true;
 664                                 return EOK;
 665                         }
 666                 }
 667
 668                 /* Jump to the next entry */
 669                 dentry = (void *)((uint8_t *)dentry + rec_len);
 670         }
 671
 672         /* No free space found for new entry */
 673         return ENOSPC;
 674 }
 675
 676 int ext4_dir_find_in_block(struct ext4_block *block, struct ext4_sblock *sb,
 677                            size_t name_len, const char *name,
 678                            struct ext4_dir_entry_ll **res_entry)
 679 {
 680         /* Start from the first entry in block */
 681         struct ext4_dir_entry_ll *dentry =
 682             (struct ext4_dir_entry_ll *)block->data;
 683
 684         /* Set upper bound for cycling */
 685         uint8_t *addr_limit = block->data + ext4_sb_get_block_size(sb);
 686
 687         /* Walk through the block and check entries */
 688         while ((uint8_t *)dentry < addr_limit) {
 689                 /* Termination condition */
 690                 if ((uint8_t *)dentry + name_len > addr_limit)
 691                         break;
 692
 693                 /* Valid entry - check it */
 694                 if (ext4_dir_entry_ll_get_inode(dentry) != 0) {
 695                         /* For more efficient compare only lengths firstly*/
 696                         if (ext4_dir_entry_ll_get_name_length(sb, dentry) ==
 697                             name_len) {
 698                                 /* Compare names */
 699                                 if (memcmp((uint8_t *)name, dentry->name,
 700                                            name_len) == 0) {
 701                                         *res_entry = dentry;
 702                                         return EOK;
 703                                 }
 704                         }
 705                 }
 706
 707                 uint16_t dentry_len =
 708                     ext4_dir_entry_ll_get_entry_length(dentry);
 709
 710                 /* Corrupted entry */
 711                 if (dentry_len == 0)
 712                         return EINVAL;
 713
 714                 /* Jump to next entry */
 715                 dentry = (struct ext4_dir_entry_ll *)((uint8_t *)dentry +
 716                                                             dentry_len);
 717         }
 718
 719         /* Entry not found */
 720         return ENOENT;
 721 }
 722
 723 int ext4_dir_destroy_result(struct ext4_inode_ref *parent,
 724                             struct ext4_dir_search_result *result)
 725 {
 726         if (result->block.lb_id)
 727                 return ext4_block_set(parent->fs->bdev, &result->block);
 728
 729         return EOK;
 730 }
 731
 732 /**
 733  * @}
 734  */