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