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