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_directory_entry_tail *
  55 ext4_dir_get_tail(struct ext4_inode_ref *inode_ref,
  56                 struct ext4_directory_entry_ll *de)
  57 {
  58         struct ext4_directory_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_directory_entry_tail) ||
  65             t->reserved_zero2 ||
  66             t->reserved_ft != EXT4_DIRENTRY_DIR_CSUM)
  67                 return NULL;
  68
  69         return t;
  70 }
  71
  72 static uint32_t ext4_dir_checksum(struct ext4_inode_ref *inode_ref,
  73                                struct ext4_directory_entry_ll *dirent, int size)
  74 {
  75         uint32_t checksum;
  76         struct ext4_sblock *sb = &inode_ref->fs->sb;
  77         uint32_t ino_index = to_le32(inode_ref->index);
  78         uint32_t ino_gen =
  79                 to_le32(ext4_inode_get_generation(inode_ref->inode));
  80
  81         /* First calculate crc32 checksum against fs uuid */
  82         checksum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid, sizeof(sb->uuid));
  83         /* Then calculate crc32 checksum against inode number
  84          * and inode generation */
  85         checksum = ext4_crc32c(checksum, &ino_index,
  86                              sizeof(ino_index));
  87         checksum = ext4_crc32c(checksum, &ino_gen,
  88                              sizeof(ino_gen));
  89         /* Finally calculate crc32 checksum against directory entries */
  90         checksum = ext4_crc32c(checksum, dirent, size);
  91         return checksum;
  92 }
  93
  94 __unused int
  95 ext4_dir_checksum_verify(struct ext4_inode_ref *inode_ref,
  96                          struct ext4_directory_entry_ll *dirent)
  97 {
  98         struct ext4_directory_entry_tail *t;
  99         struct ext4_sblock *sb = &inode_ref->fs->sb;
 100
 101         /* Compute the checksum only if the filesystem supports it */
 102         if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
 103                 t = ext4_dir_get_tail(inode_ref, dirent);
 104                 if (!t) {
 105                         /* There is no space to hold the checksum */
 106                         return 0;
 107                 }
 108
 109                 if (t->checksum != to_le32(ext4_dir_checksum(inode_ref, dirent,
 110                                         (char *)t - (char *)dirent)))
 111                         return 0;
 112
 113         }
 114         return 1;
 115 }
 116
 117 /* checksumming functions */
 118 void initialize_dir_tail(struct ext4_directory_entry_tail *t)
 119 {
 120         memset(t, 0, sizeof(struct ext4_directory_entry_tail));
 121         t->rec_len = to_le16(sizeof(struct ext4_directory_entry_tail));
 122         t->reserved_ft = EXT4_DIRENTRY_DIR_CSUM;
 123 }
 124
 125 void ext4_dir_set_checksum(struct ext4_inode_ref *inode_ref,
 126                            struct ext4_directory_entry_ll *dirent)
 127 {
 128         struct ext4_directory_entry_tail *t;
 129         struct ext4_sblock *sb = &inode_ref->fs->sb;
 130
 131         /* Compute the checksum only if the filesystem supports it */
 132         if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
 133                 t = ext4_dir_get_tail(inode_ref, dirent);
 134                 if (!t) {
 135                         /* There is no space to hold the checksum */
 136                         return;
 137                 }
 138
 139                 t->checksum = to_le32(ext4_dir_checksum(inode_ref, dirent,
 140                                         (char *)t - (char *)dirent));
 141         }
 142 }
 143
 144 /**@brief Do some checks before returning iterator.
 145  * @param it Iterator to be checked
 146  * @param block_size Size of data block
 147  * @return Error code
 148  */
 149 static int ext4_dir_iterator_set(struct ext4_directory_iterator *it,
 150                                  uint32_t block_size)
 151 {
 152         it->current = NULL;
 153
 154         uint32_t offset_in_block = it->current_offset % block_size;
 155
 156         /* Ensure proper alignment */
 157         if ((offset_in_block % 4) != 0)
 158                 return EIO;
 159
 160         /* Ensure that the core of the entry does not overflow the block */
 161         if (offset_in_block > block_size - 8)
 162                 return EIO;
 163
 164         struct ext4_directory_entry_ll *entry =
 165             (void *)(it->current_block.data + offset_in_block);
 166
 167         /* Ensure that the whole entry does not overflow the block */
 168         uint16_t length = ext4_dir_entry_ll_get_entry_length(entry);
 169         if (offset_in_block + length > block_size)
 170                 return EIO;
 171
 172         /* Ensure the name length is not too large */
 173         if (ext4_dir_entry_ll_get_name_length(&it->inode_ref->fs->sb, entry) >
 174             length - 8)
 175                 return EIO;
 176
 177         /* Everything OK - "publish" the entry */
 178         it->current = entry;
 179         return EOK;
 180 }
 181
 182 /**@brief Seek to next valid directory entry.
 183  *        Here can be jumped to the next data block.
 184  * @param it  Initialized iterator
 185  * @param pos Position of the next entry
 186  * @return Error code
 187  */
 188 static int ext4_dir_iterator_seek(struct ext4_directory_iterator *it,
 189                                   uint64_t pos)
 190 {
 191         uint64_t size =
 192             ext4_inode_get_size(&it->inode_ref->fs->sb, it->inode_ref->inode);
 193
 194         /* The iterator is not valid until we seek to the desired position */
 195         it->current = NULL;
 196
 197         /* Are we at the end? */
 198         if (pos >= size) {
 199                 if (it->current_block.lb_id) {
 200
 201                         int rc = ext4_block_set(it->inode_ref->fs->bdev,
 202                                                 &it->current_block);
 203                         it->current_block.lb_id = 0;
 204
 205                         if (rc != EOK)
 206                                 return rc;
 207                 }
 208
 209                 it->current_offset = pos;
 210                 return EOK;
 211         }
 212
 213         /* Compute next block address */
 214         uint32_t block_size = ext4_sb_get_block_size(&it->inode_ref->fs->sb);
 215         uint64_t current_block_idx = it->current_offset / block_size;
 216         uint64_t next_block_idx = pos / block_size;
 217
 218         /*
 219          * If we don't have a block or are moving across block boundary,
 220          * we need to get another block
 221          */
 222         if ((it->current_block.lb_id == 0) ||
 223             (current_block_idx != next_block_idx)) {
 224                 if (it->current_block.lb_id) {
 225                         int rc = ext4_block_set(it->inode_ref->fs->bdev,
 226                                                 &it->current_block);
 227                         it->current_block.lb_id = 0;
 228
 229                         if (rc != EOK)
 230                                 return rc;
 231                 }
 232
 233                 ext4_fsblk_t next_block_phys_idx;
 234                 int rc = ext4_fs_get_inode_data_block_index(
 235                     it->inode_ref, next_block_idx,
 236                     &next_block_phys_idx,
 237                     false);
 238                 if (rc != EOK)
 239                         return rc;
 240
 241                 rc = ext4_block_get(it->inode_ref->fs->bdev, &it->current_block,
 242                                     next_block_phys_idx);
 243                 if (rc != EOK) {
 244                         it->current_block.lb_id = 0;
 245                         return rc;
 246                 }
 247         }
 248
 249         it->current_offset = pos;
 250
 251         return ext4_dir_iterator_set(it, block_size);
 252 }
 253
 254 int ext4_dir_iterator_init(struct ext4_directory_iterator *it,
 255                            struct ext4_inode_ref *inode_ref, uint64_t pos)
 256 {
 257         it->inode_ref = inode_ref;
 258         it->current = 0;
 259         it->current_offset = 0;
 260         it->current_block.lb_id = 0;
 261
 262         return ext4_dir_iterator_seek(it, pos);
 263 }
 264
 265 int ext4_dir_iterator_next(struct ext4_directory_iterator *it)
 266 {
 267         int r = EOK;
 268         uint16_t skip;
 269
 270         while (r == EOK) {
 271                 skip = ext4_dir_entry_ll_get_entry_length(it->current);
 272                 r = ext4_dir_iterator_seek(it, it->current_offset + skip);
 273
 274                 if (!it->current)
 275                         break;
 276                 /*Skip NULL referenced entry*/
 277                 if (ext4_dir_entry_ll_get_inode(it->current) != 0)
 278                         break;
 279         }
 280
 281         return r;
 282 }
 283
 284 int ext4_dir_iterator_fini(struct ext4_directory_iterator *it)
 285 {
 286         it->current = 0;
 287
 288         if (it->current_block.lb_id)
 289                 return ext4_block_set(it->inode_ref->fs->bdev,
 290                                       &it->current_block);
 291
 292         return EOK;
 293 }
 294
 295 void ext4_dir_write_entry(struct ext4_sblock *sb,
 296                           struct ext4_directory_entry_ll *entry,
 297                           uint16_t entry_len, struct ext4_inode_ref *child,
 298                           const char *name, size_t name_len)
 299 {
 300         /* Check maximum entry length */
 301         ext4_assert(entry_len <= ext4_sb_get_block_size(sb));
 302
 303         /* Set type of entry */
 304         switch (ext4_inode_type(sb, child->inode)) {
 305         case EXT4_INODE_MODE_DIRECTORY:
 306                 ext4_dir_entry_ll_set_inode_type(sb, entry,
 307                                                  EXT4_DIRENTRY_DIR);
 308                 break;
 309         case EXT4_INODE_MODE_FILE:
 310                 ext4_dir_entry_ll_set_inode_type(
 311                     sb, entry, EXT4_DIRENTRY_REG_FILE);
 312                 break;
 313         case EXT4_INODE_MODE_SOFTLINK:
 314                 ext4_dir_entry_ll_set_inode_type(
 315                     sb, entry, EXT4_DIRENTRY_SYMLINK);
 316                 break;
 317         default:
 318                 /* FIXME: right now we only support 3 inode type. */
 319                 ext4_assert(0);
 320         }
 321
 322         /* Set basic attributes */
 323         ext4_dir_entry_ll_set_inode(entry, child->index);
 324         ext4_dir_entry_ll_set_entry_length(entry, entry_len);
 325         ext4_dir_entry_ll_set_name_length(sb, entry, name_len);
 326
 327         /* Write name */
 328         memcpy(entry->name, name, name_len);
 329 }
 330
 331 int ext4_dir_add_entry(struct ext4_inode_ref *parent, const char *name,
 332                        uint32_t name_len, struct ext4_inode_ref *child)
 333 {
 334         struct ext4_fs *fs = parent->fs;
 335
 336 #if CONFIG_DIR_INDEX_ENABLE
 337         /* Index adding (if allowed) */
 338         if ((ext4_sb_feature_com(&fs->sb, EXT4_FCOM_DIR_INDEX)) &&
 339             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
 340                 int rc = ext4_dir_dx_add_entry(parent, child, name);
 341
 342                 /* Check if index is not corrupted */
 343                 if (rc != EXT4_ERR_BAD_DX_DIR) {
 344                         if (rc != EOK)
 345                                 return rc;
 346
 347                         return EOK;
 348                 }
 349
 350                 /* Needed to clear dir index flag if corrupted */
 351                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
 352                 parent->dirty = true;
 353         }
 354 #endif
 355
 356         /* Linear algorithm */
 357         uint32_t iblock = 0;
 358         ext4_fsblk_t fblock = 0;
 359         uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 360         uint32_t inode_size = ext4_inode_get_size(&fs->sb, parent->inode);
 361         uint32_t total_blocks = inode_size / block_size;
 362
 363         /* Find block, where is space for new entry and try to add */
 364         bool success = false;
 365         for (iblock = 0; iblock < total_blocks; ++iblock) {
 366                 int rc =
 367                     ext4_fs_get_inode_data_block_index(parent,
 368                                     iblock, &fblock,
 369                                     false);
 370                 if (rc != EOK)
 371                         return rc;
 372
 373                 struct ext4_block block;
 374                 rc = ext4_block_get(fs->bdev, &block, fblock);
 375                 if (rc != EOK)
 376                         return rc;
 377
 378                 /* If adding is successful, function can finish */
 379                 rc = ext4_dir_try_insert_entry(&fs->sb, parent, &block, child, name,
 380                                                name_len);
 381                 if (rc == EOK)
 382                         success = true;
 383
 384                 rc = ext4_block_set(fs->bdev, &block);
 385                 if (rc != EOK)
 386                         return rc;
 387
 388                 if (success)
 389                         return EOK;
 390         }
 391
 392         /* No free block found - needed to allocate next data block */
 393
 394         iblock = 0;
 395         fblock = 0;
 396         int rc = ext4_fs_append_inode_block(parent, &fblock, &iblock);
 397         if (rc != EOK)
 398                 return rc;
 399
 400         /* Load new block */
 401         struct ext4_block new_block;
 402
 403         rc = ext4_block_get(fs->bdev, &new_block, fblock);
 404         if (rc != EOK)
 405                 return rc;
 406
 407         /* Fill block with zeroes */
 408         memset(new_block.data, 0, block_size);
 409         struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;
 410
 411         /* Save new block */
 412         if (ext4_sb_feature_ro_com(&fs->sb, EXT4_FRO_COM_METADATA_CSUM)) {
 413                 ext4_dir_write_entry(&fs->sb, block_entry,
 414                                 block_size - sizeof(struct ext4_directory_entry_tail),
 415                                 child,
 416                                 name, name_len);
 417                 initialize_dir_tail(EXT4_DIRENT_TAIL(new_block.data,
 418                                         ext4_sb_get_block_size(&fs->sb)));
 419         } else
 420                 ext4_dir_write_entry(&fs->sb, block_entry, block_size, child, name,
 421                                      name_len);
 422
 423         ext4_dir_set_checksum(parent,
 424                         (struct ext4_directory_entry_ll *)new_block.data);
 425         new_block.dirty = true;
 426         rc = ext4_block_set(fs->bdev, &new_block);
 427
 428         return rc;
 429 }
 430
 431 int ext4_dir_find_entry(struct ext4_directory_search_result *result,
 432                         struct ext4_inode_ref *parent, const char *name,
 433                         uint32_t name_len)
 434 {
 435         struct ext4_sblock *sb = &parent->fs->sb;
 436
 437 #if CONFIG_DIR_INDEX_ENABLE
 438         /* Index search */
 439         if ((ext4_sb_feature_com(sb, EXT4_FCOM_DIR_INDEX)) &&
 440             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
 441                 int rc = ext4_dir_dx_find_entry(result, parent, name_len, name);
 442
 443                 /* Check if index is not corrupted */
 444                 if (rc != EXT4_ERR_BAD_DX_DIR) {
 445                         if (rc != EOK)
 446                                 return rc;
 447
 448                         return EOK;
 449                 }
 450
 451                 /* Needed to clear dir index flag if corrupted */
 452                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
 453                 parent->dirty = true;
 454         }
 455 #endif
 456
 457         /* Linear algorithm */
 458
 459         uint32_t iblock;
 460         ext4_fsblk_t fblock;
 461         uint32_t block_size = ext4_sb_get_block_size(sb);
 462         uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
 463         uint32_t total_blocks = inode_size / block_size;
 464
 465         /* Walk through all data blocks */
 466         for (iblock = 0; iblock < total_blocks; ++iblock) {
 467                 /* Load block address */
 468                 int rc =
 469                     ext4_fs_get_inode_data_block_index(parent,
 470                                     iblock, &fblock,
 471                                     false);
 472                 if (rc != EOK)
 473                         return rc;
 474
 475                 /* Load data block */
 476                 struct ext4_block block;
 477                 rc = ext4_block_get(parent->fs->bdev, &block, fblock);
 478                 if (rc != EOK)
 479                         return rc;
 480
 481                 /* Try to find entry in block */
 482                 struct ext4_directory_entry_ll *res_entry;
 483                 rc = ext4_dir_find_in_block(&block, sb, name_len, name,
 484                                             &res_entry);
 485                 if (rc == EOK) {
 486                         result->block = block;
 487                         result->dentry = res_entry;
 488                         return EOK;
 489                 }
 490
 491                 /* Entry not found - put block and continue to the next block */
 492
 493                 rc = ext4_block_set(parent->fs->bdev, &block);
 494                 if (rc != EOK)
 495                         return rc;
 496         }
 497
 498         /* Entry was not found */
 499
 500         result->block.lb_id = 0;
 501         result->dentry = NULL;
 502
 503         return ENOENT;
 504 }
 505
 506 int ext4_dir_remove_entry(struct ext4_inode_ref *parent, const char *name,
 507                           uint32_t name_len)
 508 {
 509         /* Check if removing from directory */
 510         if (!ext4_inode_is_type(&parent->fs->sb, parent->inode,
 511                                 EXT4_INODE_MODE_DIRECTORY))
 512                 return ENOTDIR;
 513
 514         /* Try to find entry */
 515         struct ext4_directory_search_result result;
 516         int rc = ext4_dir_find_entry(&result, parent, name, name_len);
 517         if (rc != EOK)
 518                 return rc;
 519
 520         /* Invalidate entry */
 521         ext4_dir_entry_ll_set_inode(result.dentry, 0);
 522
 523         /* Store entry position in block */
 524         uint32_t pos = (uint8_t *)result.dentry - result.block.data;
 525
 526         /*
 527          * If entry is not the first in block, it must be merged
 528          * with previous entry
 529          */
 530         if (pos != 0) {
 531                 uint32_t offset = 0;
 532
 533                 /* Start from the first entry in block */
 534                 struct ext4_directory_entry_ll *tmp_dentry =
 535                     (void *)result.block.data;
 536                 uint16_t tmp_dentry_length =
 537                     ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 538
 539                 /* Find direct predecessor of removed entry */
 540                 while ((offset + tmp_dentry_length) < pos) {
 541                         offset +=
 542                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 543                         tmp_dentry = (void *)(result.block.data + offset);
 544                         tmp_dentry_length =
 545                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 546                 }
 547
 548                 ext4_assert(tmp_dentry_length + offset == pos);
 549
 550                 /* Add to removed entry length to predecessor's length */
 551                 uint16_t del_entry_length =
 552                     ext4_dir_entry_ll_get_entry_length(result.dentry);
 553                 ext4_dir_entry_ll_set_entry_length(
 554                     tmp_dentry, tmp_dentry_length + del_entry_length);
 555         }
 556
 557         ext4_dir_set_checksum(parent,
 558                         (struct ext4_directory_entry_ll *)result.block.data);
 559         result.block.dirty = true;
 560
 561         return ext4_dir_destroy_result(parent, &result);
 562 }
 563
 564 int ext4_dir_try_insert_entry(struct ext4_sblock *sb,
 565                               struct ext4_inode_ref *inode_ref,
 566                               struct ext4_block *target_block,
 567                               struct ext4_inode_ref *child, const char *name,
 568                               uint32_t name_len)
 569 {
 570         /* Compute required length entry and align it to 4 bytes */
 571         uint32_t block_size = ext4_sb_get_block_size(sb);
 572         uint16_t required_len =
 573             sizeof(struct ext4_fake_directory_entry) + name_len;
 574
 575         if ((required_len % 4) != 0)
 576                 required_len += 4 - (required_len % 4);
 577
 578         /* Initialize pointers, stop means to upper bound */
 579         struct ext4_directory_entry_ll *dentry = (void *)target_block->data;
 580         struct ext4_directory_entry_ll *stop =
 581             (void *)(target_block->data + block_size);
 582
 583         /*
 584          * Walk through the block and check for invalid entries
 585          * or entries with free space for new entry
 586          */
 587         while (dentry < stop) {
 588                 uint32_t inode = ext4_dir_entry_ll_get_inode(dentry);
 589                 uint16_t rec_len = ext4_dir_entry_ll_get_entry_length(dentry);
 590                 uint8_t inode_type = ext4_dir_entry_ll_get_inode_type(sb, dentry);
 591
 592                 /* If invalid and large enough entry, use it */
 593                 if ((inode == 0) &&
 594                     (inode_type != EXT4_DIRENTRY_DIR_CSUM) &&
 595                     (rec_len >= required_len)) {
 596                         ext4_dir_write_entry(sb, dentry, rec_len, child, name,
 597                                              name_len);
 598                         ext4_dir_set_checksum(inode_ref,
 599                                                 (struct ext4_directory_entry_ll *)
 600                                                 target_block->data);
 601                         target_block->dirty = true;
 602
 603                         return EOK;
 604                 }
 605
 606                 /* Valid entry, try to split it */
 607                 if (inode != 0) {
 608                         uint16_t used_name_len =
 609                             ext4_dir_entry_ll_get_name_length(sb, dentry);
 610
 611                         uint16_t used_space =
 612                             sizeof(struct ext4_fake_directory_entry) +
 613                             used_name_len;
 614
 615                         if ((used_name_len % 4) != 0)
 616                                 used_space += 4 - (used_name_len % 4);
 617
 618                         uint16_t free_space = rec_len - used_space;
 619
 620                         /* There is free space for new entry */
 621                         if (free_space >= required_len) {
 622                                 /* Cut tail of current entry */
 623                                 ext4_dir_entry_ll_set_entry_length(dentry,
 624                                                                    used_space);
 625                                 struct ext4_directory_entry_ll *new_entry =
 626                                     (void *)((uint8_t *)dentry + used_space);
 627                                 ext4_dir_write_entry(sb, new_entry, free_space,
 628                                                      child, name, name_len);
 629
 630                                 ext4_dir_set_checksum(inode_ref,
 631                                                 (struct ext4_directory_entry_ll *)
 632                                                 target_block->data);
 633                                 target_block->dirty = true;
 634                                 return EOK;
 635                         }
 636                 }
 637
 638                 /* Jump to the next entry */
 639                 dentry = (void *)((uint8_t *)dentry + rec_len);
 640         }
 641
 642         /* No free space found for new entry */
 643         return ENOSPC;
 644 }
 645
 646 int ext4_dir_find_in_block(struct ext4_block *block, struct ext4_sblock *sb,
 647                            size_t name_len, const char *name,
 648                            struct ext4_directory_entry_ll **res_entry)
 649 {
 650         /* Start from the first entry in block */
 651         struct ext4_directory_entry_ll *dentry =
 652             (struct ext4_directory_entry_ll *)block->data;
 653
 654         /* Set upper bound for cycling */
 655         uint8_t *addr_limit = block->data + ext4_sb_get_block_size(sb);
 656
 657         /* Walk through the block and check entries */
 658         while ((uint8_t *)dentry < addr_limit) {
 659                 /* Termination condition */
 660                 if ((uint8_t *)dentry + name_len > addr_limit)
 661                         break;
 662
 663                 /* Valid entry - check it */
 664                 if (ext4_dir_entry_ll_get_inode(dentry) != 0) {
 665                         /* For more efficient compare only lengths firstly*/
 666                         if (ext4_dir_entry_ll_get_name_length(sb, dentry) ==
 667                             name_len) {
 668                                 /* Compare names */
 669                                 if (memcmp((uint8_t *)name, dentry->name,
 670                                            name_len) == 0) {
 671                                         *res_entry = dentry;
 672                                         return EOK;
 673                                 }
 674                         }
 675                 }
 676
 677                 uint16_t dentry_len =
 678                     ext4_dir_entry_ll_get_entry_length(dentry);
 679
 680                 /* Corrupted entry */
 681                 if (dentry_len == 0)
 682                         return EINVAL;
 683
 684                 /* Jump to next entry */
 685                 dentry = (struct ext4_directory_entry_ll *)((uint8_t *)dentry +
 686                                                             dentry_len);
 687         }
 688
 689         /* Entry not found */
 690         return ENOENT;
 691 }
 692
 693 int ext4_dir_destroy_result(struct ext4_inode_ref *parent,
 694                             struct ext4_directory_search_result *result)
 695 {
 696         if (result->block.lb_id)
 697                 return ext4_block_set(parent->fs->bdev, &result->block);
 698
 699         return EOK;
 700 }
 701
 702 /**
 703  * @}
 704  */