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