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_inode.h"
  46 #include "ext4_fs.h"
  47
  48 #include <string.h>
  49
  50 /****************************************************************************/
  51
  52 /**@brief Do some checks before returning iterator.
  53  * @param it Iterator to be checked
  54  * @param block_size Size of data block
  55  * @return Error code
  56  */
  57 static int ext4_dir_iterator_set(struct ext4_directory_iterator *it,
  58                                  uint32_t block_size)
  59 {
  60         it->current = NULL;
  61
  62         uint32_t offset_in_block = it->current_offset % block_size;
  63
  64         /* Ensure proper alignment */
  65         if ((offset_in_block % 4) != 0)
  66                 return EIO;
  67
  68         /* Ensure that the core of the entry does not overflow the block */
  69         if (offset_in_block > block_size - 8)
  70                 return EIO;
  71
  72         struct ext4_directory_entry_ll *entry =
  73             (void *)(it->current_block.data + offset_in_block);
  74
  75         /* Ensure that the whole entry does not overflow the block */
  76         uint16_t length = ext4_dir_entry_ll_get_entry_length(entry);
  77         if (offset_in_block + length > block_size)
  78                 return EIO;
  79
  80         /* Ensure the name length is not too large */
  81         if (ext4_dir_entry_ll_get_name_length(&it->inode_ref->fs->sb, entry) >
  82             length - 8)
  83                 return EIO;
  84
  85         /* Everything OK - "publish" the entry */
  86         it->current = entry;
  87         return EOK;
  88 }
  89
  90 /**@brief Seek to next valid directory entry.
  91  *        Here can be jumped to the next data block.
  92  * @param it  Initialized iterator
  93  * @param pos Position of the next entry
  94  * @return Error code
  95  */
  96 static int ext4_dir_iterator_seek(struct ext4_directory_iterator *it,
  97                                   uint64_t pos)
  98 {
  99         uint64_t size =
 100             ext4_inode_get_size(&it->inode_ref->fs->sb, it->inode_ref->inode);
 101
 102         /* The iterator is not valid until we seek to the desired position */
 103         it->current = NULL;
 104
 105         /* Are we at the end? */
 106         if (pos >= size) {
 107                 if (it->current_block.lb_id) {
 108
 109                         int rc = ext4_block_set(it->inode_ref->fs->bdev,
 110                                                 &it->current_block);
 111                         it->current_block.lb_id = 0;
 112
 113                         if (rc != EOK)
 114                                 return rc;
 115                 }
 116
 117                 it->current_offset = pos;
 118                 return EOK;
 119         }
 120
 121         /* Compute next block address */
 122         uint32_t block_size = ext4_sb_get_block_size(&it->inode_ref->fs->sb);
 123         uint64_t current_block_idx = it->current_offset / block_size;
 124         uint64_t next_block_idx = pos / block_size;
 125
 126         /*
 127          * If we don't have a block or are moving across block boundary,
 128          * we need to get another block
 129          */
 130         if ((it->current_block.lb_id == 0) ||
 131             (current_block_idx != next_block_idx)) {
 132                 if (it->current_block.lb_id) {
 133                         int rc = ext4_block_set(it->inode_ref->fs->bdev,
 134                                                 &it->current_block);
 135                         it->current_block.lb_id = 0;
 136
 137                         if (rc != EOK)
 138                                 return rc;
 139                 }
 140
 141                 uint32_t next_block_phys_idx;
 142                 int rc = ext4_fs_get_inode_data_block_index(
 143                     it->inode_ref, next_block_idx, &next_block_phys_idx);
 144                 if (rc != EOK)
 145                         return rc;
 146
 147                 rc = ext4_block_get(it->inode_ref->fs->bdev, &it->current_block,
 148                                     next_block_phys_idx);
 149                 if (rc != EOK) {
 150                         it->current_block.lb_id = 0;
 151                         return rc;
 152                 }
 153         }
 154
 155         it->current_offset = pos;
 156
 157         return ext4_dir_iterator_set(it, block_size);
 158 }
 159
 160 int ext4_dir_iterator_init(struct ext4_directory_iterator *it,
 161                            struct ext4_inode_ref *inode_ref, uint64_t pos)
 162 {
 163         it->inode_ref = inode_ref;
 164         it->current = 0;
 165         it->current_offset = 0;
 166         it->current_block.lb_id = 0;
 167
 168         return ext4_dir_iterator_seek(it, pos);
 169 }
 170
 171 int ext4_dir_iterator_next(struct ext4_directory_iterator *it)
 172 {
 173         int r = EOK;
 174         uint16_t skip;
 175
 176         while (r == EOK) {
 177                 skip = ext4_dir_entry_ll_get_entry_length(it->current);
 178                 r = ext4_dir_iterator_seek(it, it->current_offset + skip);
 179
 180                 if (!it->current)
 181                         break;
 182                 /*Skip NULL referenced entry*/
 183                 if (ext4_dir_entry_ll_get_inode(it->current) != 0)
 184                         break;
 185         }
 186
 187         return r;
 188 }
 189
 190 int ext4_dir_iterator_fini(struct ext4_directory_iterator *it)
 191 {
 192         it->current = 0;
 193
 194         if (it->current_block.lb_id)
 195                 return ext4_block_set(it->inode_ref->fs->bdev,
 196                                       &it->current_block);
 197
 198         return EOK;
 199 }
 200
 201 void ext4_dir_write_entry(struct ext4_sblock *sb,
 202                           struct ext4_directory_entry_ll *entry,
 203                           uint16_t entry_len, struct ext4_inode_ref *child,
 204                           const char *name, size_t name_len)
 205 {
 206         /* Check maximum entry length */
 207         ext4_assert(entry_len <= ext4_sb_get_block_size(sb));
 208
 209         /* Set type of entry */
 210         switch (ext4_inode_type(sb, child->inode)) {
 211         case EXT4_INODE_MODE_DIRECTORY:
 212                 ext4_dir_entry_ll_set_inode_type(sb, entry,
 213                                                  EXT4_DIRECTORY_FILETYPE_DIR);
 214                 break;
 215         case EXT4_INODE_MODE_FILE:
 216                 ext4_dir_entry_ll_set_inode_type(
 217                     sb, entry, EXT4_DIRECTORY_FILETYPE_REG_FILE);
 218                 break;
 219         case EXT4_INODE_MODE_SOFTLINK:
 220                 ext4_dir_entry_ll_set_inode_type(
 221                     sb, entry, EXT4_DIRECTORY_FILETYPE_SYMLINK);
 222                 break;
 223         default:
 224                 /* FIXME: right now we only support 3 inode type. */
 225                 ext4_assert(0);
 226         }
 227
 228         /* Set basic attributes */
 229         ext4_dir_entry_ll_set_inode(entry, child->index);
 230         ext4_dir_entry_ll_set_entry_length(entry, entry_len);
 231         ext4_dir_entry_ll_set_name_length(sb, entry, name_len);
 232
 233         /* Write name */
 234         memcpy(entry->name, name, name_len);
 235 }
 236
 237 int ext4_dir_add_entry(struct ext4_inode_ref *parent, const char *name,
 238                        uint32_t name_len, struct ext4_inode_ref *child)
 239 {
 240         struct ext4_fs *fs = parent->fs;
 241
 242 #if CONFIG_DIR_INDEX_ENABLE
 243         /* Index adding (if allowed) */
 244         if ((ext4_sb_has_feature_compatible(&fs->sb,
 245                                             EXT4_FEATURE_COMPAT_DIR_INDEX)) &&
 246             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
 247                 int rc = ext4_dir_dx_add_entry(parent, child, name);
 248
 249                 /* Check if index is not corrupted */
 250                 if (rc != EXT4_ERR_BAD_DX_DIR) {
 251                         if (rc != EOK)
 252                                 return rc;
 253
 254                         return EOK;
 255                 }
 256
 257                 /* Needed to clear dir index flag if corrupted */
 258                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
 259                 parent->dirty = true;
 260         }
 261 #endif
 262
 263         /* Linear algorithm */
 264         uint32_t iblock = 0;
 265         uint32_t fblock = 0;
 266         uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 267         uint32_t inode_size = ext4_inode_get_size(&fs->sb, parent->inode);
 268         uint32_t total_blocks = inode_size / block_size;
 269
 270         /* Find block, where is space for new entry and try to add */
 271         bool success = false;
 272         for (iblock = 0; iblock < total_blocks; ++iblock) {
 273                 int rc =
 274                     ext4_fs_get_inode_data_block_index(parent, iblock, &fblock);
 275                 if (rc != EOK)
 276                         return rc;
 277
 278                 struct ext4_block block;
 279                 rc = ext4_block_get(fs->bdev, &block, fblock);
 280                 if (rc != EOK)
 281                         return rc;
 282
 283                 /* If adding is successful, function can finish */
 284                 rc = ext4_dir_try_insert_entry(&fs->sb, &block, child, name,
 285                                                name_len);
 286                 if (rc == EOK)
 287                         success = true;
 288
 289                 rc = ext4_block_set(fs->bdev, &block);
 290                 if (rc != EOK)
 291                         return rc;
 292
 293                 if (success)
 294                         return EOK;
 295         }
 296
 297         /* No free block found - needed to allocate next data block */
 298
 299         iblock = 0;
 300         fblock = 0;
 301         int rc = ext4_fs_append_inode_block(parent, &fblock, &iblock);
 302         if (rc != EOK)
 303                 return rc;
 304
 305         /* Load new block */
 306         struct ext4_block new_block;
 307
 308         rc = ext4_block_get(fs->bdev, &new_block, fblock);
 309         if (rc != EOK)
 310                 return rc;
 311
 312         /* Fill block with zeroes */
 313         memset(new_block.data, 0, block_size);
 314         struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;
 315         ext4_dir_write_entry(&fs->sb, block_entry, block_size, child, name,
 316                              name_len);
 317
 318         /* Save new block */
 319         new_block.dirty = true;
 320         rc = ext4_block_set(fs->bdev, &new_block);
 321
 322         return rc;
 323 }
 324
 325 int ext4_dir_find_entry(struct ext4_directory_search_result *result,
 326                         struct ext4_inode_ref *parent, const char *name,
 327                         uint32_t name_len)
 328 {
 329         struct ext4_sblock *sb = &parent->fs->sb;
 330
 331 #if CONFIG_DIR_INDEX_ENABLE
 332         /* Index search */
 333         if ((ext4_sb_has_feature_compatible(sb,
 334                                             EXT4_FEATURE_COMPAT_DIR_INDEX)) &&
 335             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
 336                 int rc = ext4_dir_dx_find_entry(result, parent, name_len, name);
 337
 338                 /* Check if index is not corrupted */
 339                 if (rc != EXT4_ERR_BAD_DX_DIR) {
 340                         if (rc != EOK)
 341                                 return rc;
 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
 354         uint32_t iblock;
 355         uint32_t fblock;
 356         uint32_t block_size = ext4_sb_get_block_size(sb);
 357         uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
 358         uint32_t total_blocks = inode_size / block_size;
 359
 360         /* Walk through all data blocks */
 361         for (iblock = 0; iblock < total_blocks; ++iblock) {
 362                 /* Load block address */
 363                 int rc =
 364                     ext4_fs_get_inode_data_block_index(parent, iblock, &fblock);
 365                 if (rc != EOK)
 366                         return rc;
 367
 368                 /* Load data block */
 369                 struct ext4_block block;
 370                 rc = ext4_block_get(parent->fs->bdev, &block, fblock);
 371                 if (rc != EOK)
 372                         return rc;
 373
 374                 /* Try to find entry in block */
 375                 struct ext4_directory_entry_ll *res_entry;
 376                 rc = ext4_dir_find_in_block(&block, sb, name_len, name,
 377                                             &res_entry);
 378                 if (rc == EOK) {
 379                         result->block = block;
 380                         result->dentry = res_entry;
 381                         return EOK;
 382                 }
 383
 384                 /* Entry not found - put block and continue to the next block */
 385
 386                 rc = ext4_block_set(parent->fs->bdev, &block);
 387                 if (rc != EOK)
 388                         return rc;
 389         }
 390
 391         /* Entry was not found */
 392
 393         result->block.lb_id = 0;
 394         result->dentry = NULL;
 395
 396         return ENOENT;
 397 }
 398
 399 int ext4_dir_remove_entry(struct ext4_inode_ref *parent, const char *name,
 400                           uint32_t name_len)
 401 {
 402         /* Check if removing from directory */
 403         if (!ext4_inode_is_type(&parent->fs->sb, parent->inode,
 404                                 EXT4_INODE_MODE_DIRECTORY))
 405                 return ENOTDIR;
 406
 407         /* Try to find entry */
 408         struct ext4_directory_search_result result;
 409         int rc = ext4_dir_find_entry(&result, parent, name, name_len);
 410         if (rc != EOK)
 411                 return rc;
 412
 413         /* Invalidate entry */
 414         ext4_dir_entry_ll_set_inode(result.dentry, 0);
 415
 416         /* Store entry position in block */
 417         uint32_t pos = (uint8_t *)result.dentry - result.block.data;
 418
 419         /*
 420          * If entry is not the first in block, it must be merged
 421          * with previous entry
 422          */
 423         if (pos != 0) {
 424                 uint32_t offset = 0;
 425
 426                 /* Start from the first entry in block */
 427                 struct ext4_directory_entry_ll *tmp_dentry =
 428                     (void *)result.block.data;
 429                 uint16_t tmp_dentry_length =
 430                     ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 431
 432                 /* Find direct predecessor of removed entry */
 433                 while ((offset + tmp_dentry_length) < pos) {
 434                         offset +=
 435                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 436                         tmp_dentry = (void *)(result.block.data + offset);
 437                         tmp_dentry_length =
 438                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);
 439                 }
 440
 441                 ext4_assert(tmp_dentry_length + offset == pos);
 442
 443                 /* Add to removed entry length to predecessor's length */
 444                 uint16_t del_entry_length =
 445                     ext4_dir_entry_ll_get_entry_length(result.dentry);
 446                 ext4_dir_entry_ll_set_entry_length(
 447                     tmp_dentry, tmp_dentry_length + del_entry_length);
 448         }
 449
 450         result.block.dirty = true;
 451
 452         return ext4_dir_destroy_result(parent, &result);
 453 }
 454
 455 int ext4_dir_try_insert_entry(struct ext4_sblock *sb,
 456                               struct ext4_block *target_block,
 457                               struct ext4_inode_ref *child, const char *name,
 458                               uint32_t name_len)
 459 {
 460         /* Compute required length entry and align it to 4 bytes */
 461         uint32_t block_size = ext4_sb_get_block_size(sb);
 462         uint16_t required_len =
 463             sizeof(struct ext4_fake_directory_entry) + name_len;
 464
 465         if ((required_len % 4) != 0)
 466                 required_len += 4 - (required_len % 4);
 467
 468         /* Initialize pointers, stop means to upper bound */
 469         struct ext4_directory_entry_ll *dentry = (void *)target_block->data;
 470         struct ext4_directory_entry_ll *stop =
 471             (void *)(target_block->data + block_size);
 472
 473         /*
 474          * Walk through the block and check for invalid entries
 475          * or entries with free space for new entry
 476          */
 477         while (dentry < stop) {
 478                 uint32_t inode = ext4_dir_entry_ll_get_inode(dentry);
 479                 uint16_t rec_len = ext4_dir_entry_ll_get_entry_length(dentry);
 480
 481                 /* If invalid and large enough entry, use it */
 482                 if ((inode == 0) && (rec_len >= required_len)) {
 483                         ext4_dir_write_entry(sb, dentry, rec_len, child, name,
 484                                              name_len);
 485                         target_block->dirty = true;
 486
 487                         return EOK;
 488                 }
 489
 490                 /* Valid entry, try to split it */
 491                 if (inode != 0) {
 492                         uint16_t used_name_len =
 493                             ext4_dir_entry_ll_get_name_length(sb, dentry);
 494
 495                         uint16_t used_space =
 496                             sizeof(struct ext4_fake_directory_entry) +
 497                             used_name_len;
 498
 499                         if ((used_name_len % 4) != 0)
 500                                 used_space += 4 - (used_name_len % 4);
 501
 502                         uint16_t free_space = rec_len - used_space;
 503
 504                         /* There is free space for new entry */
 505                         if (free_space >= required_len) {
 506                                 /* Cut tail of current entry */
 507                                 ext4_dir_entry_ll_set_entry_length(dentry,
 508                                                                    used_space);
 509                                 struct ext4_directory_entry_ll *new_entry =
 510                                     (void *)((uint8_t *)dentry + used_space);
 511                                 ext4_dir_write_entry(sb, new_entry, free_space,
 512                                                      child, name, name_len);
 513
 514                                 target_block->dirty = true;
 515                                 return EOK;
 516                         }
 517                 }
 518
 519                 /* Jump to the next entry */
 520                 dentry = (void *)((uint8_t *)dentry + rec_len);
 521         }
 522
 523         /* No free space found for new entry */
 524         return ENOSPC;
 525 }
 526
 527 int ext4_dir_find_in_block(struct ext4_block *block, struct ext4_sblock *sb,
 528                            size_t name_len, const char *name,
 529                            struct ext4_directory_entry_ll **res_entry)
 530 {
 531         /* Start from the first entry in block */
 532         struct ext4_directory_entry_ll *dentry =
 533             (struct ext4_directory_entry_ll *)block->data;
 534
 535         /* Set upper bound for cycling */
 536         uint8_t *addr_limit = block->data + ext4_sb_get_block_size(sb);
 537
 538         /* Walk through the block and check entries */
 539         while ((uint8_t *)dentry < addr_limit) {
 540                 /* Termination condition */
 541                 if ((uint8_t *)dentry + name_len > addr_limit)
 542                         break;
 543
 544                 /* Valid entry - check it */
 545                 if (ext4_dir_entry_ll_get_inode(dentry) != 0) {
 546                         /* For more efficient compare only lengths firstly*/
 547                         if (ext4_dir_entry_ll_get_name_length(sb, dentry) ==
 548                             name_len) {
 549                                 /* Compare names */
 550                                 if (memcmp((uint8_t *)name, dentry->name,
 551                                            name_len) == 0) {
 552                                         *res_entry = dentry;
 553                                         return EOK;
 554                                 }
 555                         }
 556                 }
 557
 558                 uint16_t dentry_len =
 559                     ext4_dir_entry_ll_get_entry_length(dentry);
 560
 561                 /* Corrupted entry */
 562                 if (dentry_len == 0)
 563                         return EINVAL;
 564
 565                 /* Jump to next entry */
 566                 dentry = (struct ext4_directory_entry_ll *)((uint8_t *)dentry +
 567                                                             dentry_len);
 568         }
 569
 570         /* Entry not found */
 571         return ENOENT;
 572 }
 573
 574 int ext4_dir_destroy_result(struct ext4_inode_ref *parent,
 575                             struct ext4_directory_search_result *result)
 576 {
 577         if (result->block.lb_id)
 578                 return ext4_block_set(parent->fs->bdev, &result->block);
 579
 580         return EOK;
 581 }
 582
 583 /**
 584  * @}
 585  */