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, EXT4_DIRENTRY_DIR);
 313                 break;
 314         case EXT4_INODE_MODE_FILE:
 315                 ext4_dir_entry_ll_set_inode_type(sb, entry,
 316                                                  EXT4_DIRENTRY_REG_FILE);
 317                 break;
 318         case EXT4_INODE_MODE_SOFTLINK:
 319                 ext4_dir_entry_ll_set_inode_type(sb, entry,
 320                                                  EXT4_DIRENTRY_SYMLINK);
 321                 break;
 322         default:
 323                 /* FIXME: right now we only support 3 inode type. */
 324                 ext4_assert(0);
 325         }
 326
 327         /* Set basic attributes */
 328         ext4_dir_entry_ll_set_inode(entry, child->index);
 329         ext4_dir_entry_ll_set_entry_length(entry, entry_len);
 330         ext4_dir_entry_ll_set_name_length(sb, entry, name_len);
 331
 332         /* Write name */
 333         memcpy(entry->name, name, name_len);
 334 }
 335
 336 int ext4_dir_add_entry(struct ext4_inode_ref *parent, const char *name,
 337                        uint32_t name_len, struct ext4_inode_ref *child)
 338 {
 339         struct ext4_fs *fs = parent->fs;
 340
 341 #if CONFIG_DIR_INDEX_ENABLE
 342         /* Index adding (if allowed) */
 343         if ((ext4_sb_feature_com(&fs->sb, EXT4_FCOM_DIR_INDEX)) &&
 344             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
 345                 int rc = ext4_dir_dx_add_entry(parent, child, name);
 346
 347                 /* Check if index is not corrupted */
 348                 if (rc != EXT4_ERR_BAD_DX_DIR) {
 349                         if (rc != EOK)
 350                                 return rc;
 351
 352                         return EOK;
 353                 }
 354
 355                 /* Needed to clear dir index flag if corrupted */
 356                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
 357                 parent->dirty = true;
 358         }
 359 #endif
 360
 361         /* Linear algorithm */
 362         uint32_t iblock = 0;
 363         ext4_fsblk_t fblock = 0;
 364         uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 365         uint32_t inode_size = ext4_inode_get_size(&fs->sb, parent->inode);
 366         uint32_t total_blocks = inode_size / block_size;
 367
 368         /* Find block, where is space for new entry and try to add */
 369         bool success = false;
 370         for (iblock = 0; iblock < total_blocks; ++iblock) {
 371                 int rc =
 372                     ext4_fs_get_inode_data_block_index(parent,
 373                                     iblock, &fblock,
 374                                     false);
 375                 if (rc != EOK)
 376                         return rc;
 377
 378                 struct ext4_block block;
 379                 rc = ext4_block_get(fs->bdev, &block, fblock);
 380                 if (rc != EOK)
 381                         return rc;
 382
 383                 if (!ext4_dir_checksum_verify(
 384                                 parent,
 385                                 (struct ext4_dir_entry_ll *)
 386                                         block.data)) {
 387                         ext4_dbg(DEBUG_DIR,
 388                                  DBG_WARN "Leaf block checksum failed."
 389                                  "Inode: %" PRIu32", "
 390                                  "Block: %" PRIu32"\n",
 391                                  parent->index,
 392                                  iblock);
 393                 }
 394
 395                 /* If adding is successful, function can finish */
 396                 rc = ext4_dir_try_insert_entry(&fs->sb, parent, &block, child, name,
 397                                                name_len);
 398                 if (rc == EOK)
 399                         success = true;
 400
 401                 rc = ext4_block_set(fs->bdev, &block);
 402                 if (rc != EOK)
 403                         return rc;
 404
 405                 if (success)
 406                         return EOK;
 407         }
 408
 409         /* No free block found - needed to allocate next data block */
 410
 411         iblock = 0;
 412         fblock = 0;
 413         int rc = ext4_fs_append_inode_block(parent, &fblock, &iblock);
 414         if (rc != EOK)
 415                 return rc;
 416
 417         /* Load new block */
 418         struct ext4_block new_block;
 419
 420         rc = ext4_block_get_noread(fs->bdev, &new_block, fblock);
 421         if (rc != EOK)
 422                 return rc;
 423
 424         /* Fill block with zeroes */
 425         memset(new_block.data, 0, block_size);
 426         struct ext4_dir_entry_ll *block_entry = (void *)new_block.data;
 427
 428         /* Save new block */
 429         if (ext4_sb_feature_ro_com(&fs->sb, EXT4_FRO_COM_METADATA_CSUM)) {
 430                 ext4_dir_write_entry(&fs->sb, block_entry,
 431                                 block_size - sizeof(struct ext4_dir_entry_tail),
 432                                 child,
 433                                 name, name_len);
 434                 initialize_dir_tail(EXT4_DIRENT_TAIL(new_block.data,
 435                                         ext4_sb_get_block_size(&fs->sb)));
 436         } else
 437                 ext4_dir_write_entry(&fs->sb, block_entry, block_size, child, name,
 438                                      name_len);
 439
 440         ext4_dir_set_checksum(parent,
 441                         (struct ext4_dir_entry_ll *)new_block.data);
 442         new_block.dirty = true;
 443         rc = ext4_block_set(fs->bdev, &new_block);
 444
 445         return rc;
 446 }
 447
 448 int ext4_dir_find_entry(struct ext4_dir_search_result *result,
 449                         struct ext4_inode_ref *parent, const char *name,
 450                         uint32_t name_len)
 451 {
 452         struct ext4_sblock *sb = &parent->fs->sb;
 453
 454         /* Entry clear */
 455         result->block.lb_id = 0;
 456         result->dentry = NULL;
 457
 458 #if CONFIG_DIR_INDEX_ENABLE
 459         /* Index search */
 460         if ((ext4_sb_feature_com(sb, EXT4_FCOM_DIR_INDEX)) &&
 461             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
 462                 int rc = ext4_dir_dx_find_entry(result, parent, name_len, name);
 463
 464                 /* Check if index is not corrupted */
 465                 if (rc != EXT4_ERR_BAD_DX_DIR) {
 466                         if (rc != EOK)
 467                                 return rc;
 468
 469                         return EOK;
 470                 }
 471
 472                 /* Needed to clear dir index flag if corrupted */
 473                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
 474                 parent->dirty = true;
 475         }
 476 #endif
 477
 478         /* Linear algorithm */
 479
 480         uint32_t iblock;
 481         ext4_fsblk_t fblock;
 482         uint32_t block_size = ext4_sb_get_block_size(sb);
 483         uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
 484         uint32_t total_blocks = inode_size / block_size;
 485
 486         /* Walk through all data blocks */
 487         for (iblock = 0; iblock < total_blocks; ++iblock) {
 488                 /* Load block address */
 489                 int rc =
 490                     ext4_fs_get_inode_data_block_index(parent,
 491                                     iblock, &fblock,
 492                                     false);
 493                 if (rc != EOK)
 494                         return rc;
 495
 496                 /* Load data block */
 497                 struct ext4_block block;
 498                 rc = ext4_block_get(parent->fs->bdev, &block, fblock);
 499                 if (rc != EOK)
 500                         return rc;
 501
 502                 if (!ext4_dir_checksum_verify(
 503                                 parent,
 504                                 (struct ext4_dir_entry_ll *)
 505                                         block.data)) {
 506                         ext4_dbg(DEBUG_DIR,
 507                                  DBG_WARN "Leaf block checksum failed."
 508                                  "Inode: %" PRIu32", "
 509                                  "Block: %" PRIu32"\n",
 510                                  parent->index,
 511                                  iblock);
 512                 }
 513
 514                 /* Try to find entry in block */
 515                 struct ext4_dir_entry_ll *res_entry;
 516                 rc = ext4_dir_find_in_block(&block, sb, name_len, name,
 517                                             &res_entry);
 518                 if (rc == EOK) {
 519                         result->block = block;
 520                         result->dentry = res_entry;
 521                         return EOK;
 522                 }
 523
 524                 /* Entry not found - put block and continue to the next block */
 525
 526                 rc = ext4_block_set(parent->fs->bdev, &block);
 527                 if (rc != EOK)
 528                         return rc;
 529         }
 530
 531         return ENOENT;
 532 }
 533
 534 int ext4_dir_remove_entry(struct ext4_inode_ref *parent, const char *name,
 535                           uint32_t name_len)
 536 {
 537         /* Check if removing from directory */
 538         if (!ext4_inode_is_type(&parent->fs->sb, parent->inode,
 539                                 EXT4_INODE_MODE_DIRECTORY))
 540                 return ENOTDIR;
 541
 542         /* Try to find entry */
 543         struct ext4_dir_search_result result;
 544         int rc = ext4_dir_find_entry(&result, parent, name, name_len);
 545         if (rc != EOK)
 546                 return rc;
 547
 548         /* Invalidate entry */
 549         ext4_dir_entry_ll_set_inode(result.dentry, 0);
 550
 551         /* Store entry position in block */
 552         uint32_t pos = (uint8_t *)result.dentry - result.block.data;
 553
 554         /*
 555          * If entry is not the first in block, it must be merged
 556          * with previous entry
 557          */
 558         if (pos != 0) {
 559                 uint32_t offset = 0;
 560
 561                 /* Start from the first entry in block */
 562                 struct ext4_dir_entry_ll *tmp_dentry =
 563                     (void *)result.block.data;
 564                 uint16_t tmp_dentry_length =
 565                     ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 566
 567                 /* Find direct predecessor of removed entry */
 568                 while ((offset + tmp_dentry_length) < pos) {
 569                         offset +=
 570                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 571                         tmp_dentry = (void *)(result.block.data + offset);
 572                         tmp_dentry_length =
 573                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 574                 }
 575
 576                 ext4_assert(tmp_dentry_length + offset == pos);
 577
 578                 /* Add to removed entry length to predecessor's length */
 579                 uint16_t del_entry_length =
 580                     ext4_dir_entry_ll_get_entry_length(result.dentry);
 581                 ext4_dir_entry_ll_set_entry_length(
 582                     tmp_dentry, tmp_dentry_length + del_entry_length);
 583         }
 584
 585         ext4_dir_set_checksum(parent,
 586                         (struct ext4_dir_entry_ll *)result.block.data);
 587         result.block.dirty = true;
 588
 589         return ext4_dir_destroy_result(parent, &result);
 590 }
 591
 592 int ext4_dir_try_insert_entry(struct ext4_sblock *sb,
 593                               struct ext4_inode_ref *inode_ref,
 594                               struct ext4_block *target_block,
 595                               struct ext4_inode_ref *child, const char *name,
 596                               uint32_t name_len)
 597 {
 598         /* Compute required length entry and align it to 4 bytes */
 599         uint32_t block_size = ext4_sb_get_block_size(sb);
 600         uint16_t required_len =
 601             sizeof(struct ext4_fake_dir_entry) + name_len;
 602
 603         if ((required_len % 4) != 0)
 604                 required_len += 4 - (required_len % 4);
 605
 606         /* Initialize pointers, stop means to upper bound */
 607         struct ext4_dir_entry_ll *dentry = (void *)target_block->data;
 608         struct ext4_dir_entry_ll *stop =
 609             (void *)(target_block->data + block_size);
 610
 611         /*
 612          * Walk through the block and check for invalid entries
 613          * or entries with free space for new entry
 614          */
 615         while (dentry < stop) {
 616                 uint32_t inode = ext4_dir_entry_ll_get_inode(dentry);
 617                 uint16_t rec_len = ext4_dir_entry_ll_get_entry_length(dentry);
 618                 uint8_t inode_type = ext4_dir_entry_ll_get_inode_type(sb, dentry);
 619
 620                 /* If invalid and large enough entry, use it */
 621                 if ((inode == 0) &&
 622                     (inode_type != EXT4_DIRENTRY_DIR_CSUM) &&
 623                     (rec_len >= required_len)) {
 624                         ext4_dir_write_entry(sb, dentry, rec_len, child, name,
 625                                              name_len);
 626                         ext4_dir_set_checksum(inode_ref,
 627                                                 (struct ext4_dir_entry_ll *)
 628                                                 target_block->data);
 629                         target_block->dirty = true;
 630
 631                         return EOK;
 632                 }
 633
 634                 /* Valid entry, try to split it */
 635                 if (inode != 0) {
 636                         uint16_t used_name_len =
 637                             ext4_dir_entry_ll_get_name_length(sb, dentry);
 638
 639                         uint16_t used_space =
 640                             sizeof(struct ext4_fake_dir_entry) +
 641                             used_name_len;
 642
 643                         if ((used_name_len % 4) != 0)
 644                                 used_space += 4 - (used_name_len % 4);
 645
 646                         uint16_t free_space = rec_len - used_space;
 647
 648                         /* There is free space for new entry */
 649                         if (free_space >= required_len) {
 650                                 /* Cut tail of current entry */
 651                                 ext4_dir_entry_ll_set_entry_length(dentry,
 652                                                                    used_space);
 653                                 struct ext4_dir_entry_ll *new_entry =
 654                                     (void *)((uint8_t *)dentry + used_space);
 655                                 ext4_dir_write_entry(sb, new_entry, free_space,
 656                                                      child, name, name_len);
 657
 658                                 ext4_dir_set_checksum(inode_ref,
 659                                                 (struct ext4_dir_entry_ll *)
 660                                                 target_block->data);
 661                                 target_block->dirty = true;
 662                                 return EOK;
 663                         }
 664                 }
 665
 666                 /* Jump to the next entry */
 667                 dentry = (void *)((uint8_t *)dentry + rec_len);
 668         }
 669
 670         /* No free space found for new entry */
 671         return ENOSPC;
 672 }
 673
 674 int ext4_dir_find_in_block(struct ext4_block *block, struct ext4_sblock *sb,
 675                            size_t name_len, const char *name,
 676                            struct ext4_dir_entry_ll **res_entry)
 677 {
 678         /* Start from the first entry in block */
 679         struct ext4_dir_entry_ll *dentry =
 680             (struct ext4_dir_entry_ll *)block->data;
 681
 682         /* Set upper bound for cycling */
 683         uint8_t *addr_limit = block->data + ext4_sb_get_block_size(sb);
 684
 685         /* Walk through the block and check entries */
 686         while ((uint8_t *)dentry < addr_limit) {
 687                 /* Termination condition */
 688                 if ((uint8_t *)dentry + name_len > addr_limit)
 689                         break;
 690
 691                 /* Valid entry - check it */
 692                 if (ext4_dir_entry_ll_get_inode(dentry) != 0) {
 693                         /* For more efficient compare only lengths firstly*/
 694                         if (ext4_dir_entry_ll_get_name_length(sb, dentry) ==
 695                             name_len) {
 696                                 /* Compare names */
 697                                 if (memcmp((uint8_t *)name, dentry->name,
 698                                            name_len) == 0) {
 699                                         *res_entry = dentry;
 700                                         return EOK;
 701                                 }
 702                         }
 703                 }
 704
 705                 uint16_t dentry_len =
 706                     ext4_dir_entry_ll_get_entry_length(dentry);
 707
 708                 /* Corrupted entry */
 709                 if (dentry_len == 0)
 710                         return EINVAL;
 711
 712                 /* Jump to next entry */
 713                 dentry = (struct ext4_dir_entry_ll *)((uint8_t *)dentry +
 714                                                             dentry_len);
 715         }
 716
 717         /* Entry not found */
 718         return ENOENT;
 719 }
 720
 721 int ext4_dir_destroy_result(struct ext4_inode_ref *parent,
 722                             struct ext4_dir_search_result *result)
 723 {
 724         if (result->block.lb_id)
 725                 return ext4_block_set(parent->fs->bdev, &result->block);
 726
 727         return EOK;
 728 }
 729
 730 /**
 731  * @}
 732  */