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_noread(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         /* Entry clear */
 456         result->block.lb_id = 0;
 457         result->dentry = NULL;
 458
 459 #if CONFIG_DIR_INDEX_ENABLE
 460         /* Index search */
 461         if ((ext4_sb_feature_com(sb, EXT4_FCOM_DIR_INDEX)) &&
 462             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
 463                 int rc = ext4_dir_dx_find_entry(result, parent, name_len, name);
 464
 465                 /* Check if index is not corrupted */
 466                 if (rc != EXT4_ERR_BAD_DX_DIR) {
 467                         if (rc != EOK)
 468                                 return rc;
 469
 470                         return EOK;
 471                 }
 472
 473                 /* Needed to clear dir index flag if corrupted */
 474                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
 475                 parent->dirty = true;
 476         }
 477 #endif
 478
 479         /* Linear algorithm */
 480
 481         uint32_t iblock;
 482         ext4_fsblk_t fblock;
 483         uint32_t block_size = ext4_sb_get_block_size(sb);
 484         uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
 485         uint32_t total_blocks = inode_size / block_size;
 486
 487         /* Walk through all data blocks */
 488         for (iblock = 0; iblock < total_blocks; ++iblock) {
 489                 /* Load block address */
 490                 int rc =
 491                     ext4_fs_get_inode_data_block_index(parent,
 492                                     iblock, &fblock,
 493                                     false);
 494                 if (rc != EOK)
 495                         return rc;
 496
 497                 /* Load data block */
 498                 struct ext4_block block;
 499                 rc = ext4_block_get(parent->fs->bdev, &block, fblock);
 500                 if (rc != EOK)
 501                         return rc;
 502
 503                 if (!ext4_dir_checksum_verify(
 504                                 parent,
 505                                 (struct ext4_dir_entry_ll *)
 506                                         block.data)) {
 507                         ext4_dbg(DEBUG_DIR,
 508                                  DBG_WARN "Leaf block checksum failed."
 509                                  "Inode: %" PRIu32", "
 510                                  "Block: %" PRIu32"\n",
 511                                  parent->index,
 512                                  iblock);
 513                 }
 514
 515                 /* Try to find entry in block */
 516                 struct ext4_dir_entry_ll *res_entry;
 517                 rc = ext4_dir_find_in_block(&block, sb, name_len, name,
 518                                             &res_entry);
 519                 if (rc == EOK) {
 520                         result->block = block;
 521                         result->dentry = res_entry;
 522                         return EOK;
 523                 }
 524
 525                 /* Entry not found - put block and continue to the next block */
 526
 527                 rc = ext4_block_set(parent->fs->bdev, &block);
 528                 if (rc != EOK)
 529                         return rc;
 530         }
 531
 532         return ENOENT;
 533 }
 534
 535 int ext4_dir_remove_entry(struct ext4_inode_ref *parent, const char *name,
 536                           uint32_t name_len)
 537 {
 538         /* Check if removing from directory */
 539         if (!ext4_inode_is_type(&parent->fs->sb, parent->inode,
 540                                 EXT4_INODE_MODE_DIRECTORY))
 541                 return ENOTDIR;
 542
 543         /* Try to find entry */
 544         struct ext4_dir_search_result result;
 545         int rc = ext4_dir_find_entry(&result, parent, name, name_len);
 546         if (rc != EOK)
 547                 return rc;
 548
 549         /* Invalidate entry */
 550         ext4_dir_entry_ll_set_inode(result.dentry, 0);
 551
 552         /* Store entry position in block */
 553         uint32_t pos = (uint8_t *)result.dentry - result.block.data;
 554
 555         /*
 556          * If entry is not the first in block, it must be merged
 557          * with previous entry
 558          */
 559         if (pos != 0) {
 560                 uint32_t offset = 0;
 561
 562                 /* Start from the first entry in block */
 563                 struct ext4_dir_entry_ll *tmp_dentry =
 564                     (void *)result.block.data;
 565                 uint16_t tmp_dentry_length =
 566                     ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 567
 568                 /* Find direct predecessor of removed entry */
 569                 while ((offset + tmp_dentry_length) < pos) {
 570                         offset +=
 571                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 572                         tmp_dentry = (void *)(result.block.data + offset);
 573                         tmp_dentry_length =
 574                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 575                 }
 576
 577                 ext4_assert(tmp_dentry_length + offset == pos);
 578
 579                 /* Add to removed entry length to predecessor's length */
 580                 uint16_t del_entry_length =
 581                     ext4_dir_entry_ll_get_entry_length(result.dentry);
 582                 ext4_dir_entry_ll_set_entry_length(
 583                     tmp_dentry, tmp_dentry_length + del_entry_length);
 584         }
 585
 586         ext4_dir_set_checksum(parent,
 587                         (struct ext4_dir_entry_ll *)result.block.data);
 588         result.block.dirty = true;
 589
 590         return ext4_dir_destroy_result(parent, &result);
 591 }
 592
 593 int ext4_dir_try_insert_entry(struct ext4_sblock *sb,
 594                               struct ext4_inode_ref *inode_ref,
 595                               struct ext4_block *target_block,
 596                               struct ext4_inode_ref *child, const char *name,
 597                               uint32_t name_len)
 598 {
 599         /* Compute required length entry and align it to 4 bytes */
 600         uint32_t block_size = ext4_sb_get_block_size(sb);
 601         uint16_t required_len =
 602             sizeof(struct ext4_fake_dir_entry) + name_len;
 603
 604         if ((required_len % 4) != 0)
 605                 required_len += 4 - (required_len % 4);
 606
 607         /* Initialize pointers, stop means to upper bound */
 608         struct ext4_dir_entry_ll *dentry = (void *)target_block->data;
 609         struct ext4_dir_entry_ll *stop =
 610             (void *)(target_block->data + block_size);
 611
 612         /*
 613          * Walk through the block and check for invalid entries
 614          * or entries with free space for new entry
 615          */
 616         while (dentry < stop) {
 617                 uint32_t inode = ext4_dir_entry_ll_get_inode(dentry);
 618                 uint16_t rec_len = ext4_dir_entry_ll_get_entry_length(dentry);
 619                 uint8_t inode_type = ext4_dir_entry_ll_get_inode_type(sb, dentry);
 620
 621                 /* If invalid and large enough entry, use it */
 622                 if ((inode == 0) &&
 623                     (inode_type != EXT4_DIRENTRY_DIR_CSUM) &&
 624                     (rec_len >= required_len)) {
 625                         ext4_dir_write_entry(sb, dentry, rec_len, child, name,
 626                                              name_len);
 627                         ext4_dir_set_checksum(inode_ref,
 628                                                 (struct ext4_dir_entry_ll *)
 629                                                 target_block->data);
 630                         target_block->dirty = true;
 631
 632                         return EOK;
 633                 }
 634
 635                 /* Valid entry, try to split it */
 636                 if (inode != 0) {
 637                         uint16_t used_name_len =
 638                             ext4_dir_entry_ll_get_name_length(sb, dentry);
 639
 640                         uint16_t used_space =
 641                             sizeof(struct ext4_fake_dir_entry) +
 642                             used_name_len;
 643
 644                         if ((used_name_len % 4) != 0)
 645                                 used_space += 4 - (used_name_len % 4);
 646
 647                         uint16_t free_space = rec_len - used_space;
 648
 649                         /* There is free space for new entry */
 650                         if (free_space >= required_len) {
 651                                 /* Cut tail of current entry */
 652                                 ext4_dir_entry_ll_set_entry_length(dentry,
 653                                                                    used_space);
 654                                 struct ext4_dir_entry_ll *new_entry =
 655                                     (void *)((uint8_t *)dentry + used_space);
 656                                 ext4_dir_write_entry(sb, new_entry, free_space,
 657                                                      child, name, name_len);
 658
 659                                 ext4_dir_set_checksum(inode_ref,
 660                                                 (struct ext4_dir_entry_ll *)
 661                                                 target_block->data);
 662                                 target_block->dirty = true;
 663                                 return EOK;
 664                         }
 665                 }
 666
 667                 /* Jump to the next entry */
 668                 dentry = (void *)((uint8_t *)dentry + rec_len);
 669         }
 670
 671         /* No free space found for new entry */
 672         return ENOSPC;
 673 }
 674
 675 int ext4_dir_find_in_block(struct ext4_block *block, struct ext4_sblock *sb,
 676                            size_t name_len, const char *name,
 677                            struct ext4_dir_entry_ll **res_entry)
 678 {
 679         /* Start from the first entry in block */
 680         struct ext4_dir_entry_ll *dentry =
 681             (struct ext4_dir_entry_ll *)block->data;
 682
 683         /* Set upper bound for cycling */
 684         uint8_t *addr_limit = block->data + ext4_sb_get_block_size(sb);
 685
 686         /* Walk through the block and check entries */
 687         while ((uint8_t *)dentry < addr_limit) {
 688                 /* Termination condition */
 689                 if ((uint8_t *)dentry + name_len > addr_limit)
 690                         break;
 691
 692                 /* Valid entry - check it */
 693                 if (ext4_dir_entry_ll_get_inode(dentry) != 0) {
 694                         /* For more efficient compare only lengths firstly*/
 695                         if (ext4_dir_entry_ll_get_name_length(sb, dentry) ==
 696                             name_len) {
 697                                 /* Compare names */
 698                                 if (memcmp((uint8_t *)name, dentry->name,
 699                                            name_len) == 0) {
 700                                         *res_entry = dentry;
 701                                         return EOK;
 702                                 }
 703                         }
 704                 }
 705
 706                 uint16_t dentry_len =
 707                     ext4_dir_entry_ll_get_entry_length(dentry);
 708
 709                 /* Corrupted entry */
 710                 if (dentry_len == 0)
 711                         return EINVAL;
 712
 713                 /* Jump to next entry */
 714                 dentry = (struct ext4_dir_entry_ll *)((uint8_t *)dentry +
 715                                                             dentry_len);
 716         }
 717
 718         /* Entry not found */
 719         return ENOENT;
 720 }
 721
 722 int ext4_dir_destroy_result(struct ext4_inode_ref *parent,
 723                             struct ext4_dir_search_result *result)
 724 {
 725         if (result->block.lb_id)
 726                 return ext4_block_set(parent->fs->bdev, &result->block);
 727
 728         return EOK;
 729 }
 730
 731 /**
 732  * @}
 733  */