lwext4/ext4_dir.c

   1 /*\r
   2  * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)\r
   3  *\r
   4  *\r
   5  * HelenOS:\r
   6  * Copyright (c) 2012 Martin Sucha\r
   7  * Copyright (c) 2012 Frantisek Princ\r
   8  * All rights reserved.\r
   9  *\r
  10  * Redistribution and use in source and binary forms, with or without\r
  11  * modification, are permitted provided that the following conditions\r
  12  * are met:\r
  13  *\r
  14  * - Redistributions of source code must retain the above copyright\r
  15  *   notice, this list of conditions and the following disclaimer.\r
  16  * - Redistributions in binary form must reproduce the above copyright\r
  17  *   notice, this list of conditions and the following disclaimer in the\r
  18  *   documentation and/or other materials provided with the distribution.\r
  19  * - The name of the author may not be used to endorse or promote products\r
  20  *   derived from this software without specific prior written permission.\r
  21  *\r
  22  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
  23  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
  24  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
  25  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
  27  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
  28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
  29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
  30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
  31  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
  32  */\r
  33 \r
  34 /** @addtogroup lwext4\r
  35  * @{\r
  36  */\r
  37 /**\r
  38  * @file  ext4_dir.h\r
  39  * @brief Directory handle procedures.\r
  40  */\r
  41 \r
  42 #include <ext4_config.h>\r
  43 #include <ext4_dir.h>\r
  44 #include <ext4_dir_idx.h>\r
  45 #include <ext4_inode.h>\r
  46 #include <ext4_fs.h>\r
  47 \r
  48 #include <string.h>\r
  49 \r
  50 /****************************************************************************/\r
  51 \r
  52 /**@brief Do some checks before returning iterator.\r
  53  * @param it Iterator to be checked\r
  54  * @param block_size Size of data block\r
  55  * @return Error code\r
  56  */\r
  57 static int ext4_dir_iterator_set(struct ext4_directory_iterator *it,\r
  58                                  uint32_t block_size)\r
  59 {\r
  60     it->current = NULL;\r
  61 \r
  62     uint32_t offset_in_block = it->current_offset % block_size;\r
  63 \r
  64     /* Ensure proper alignment */\r
  65     if ((offset_in_block % 4) != 0)\r
  66         return EIO;\r
  67 \r
  68     /* Ensure that the core of the entry does not overflow the block */\r
  69     if (offset_in_block > block_size - 8)\r
  70         return EIO;\r
  71 \r
  72     struct ext4_directory_entry_ll *entry =\r
  73         (void *)(it->current_block.data + offset_in_block);\r
  74 \r
  75     /* Ensure that the whole entry does not overflow the block */\r
  76     uint16_t length = ext4_dir_entry_ll_get_entry_length(entry);\r
  77     if (offset_in_block + length > block_size)\r
  78         return EIO;\r
  79 \r
  80     /* Ensure the name length is not too large */\r
  81     if (ext4_dir_entry_ll_get_name_length(&it->inode_ref->fs->sb, entry) >\r
  82         length - 8)\r
  83         return EIO;\r
  84 \r
  85     /* Everything OK - "publish" the entry */\r
  86     it->current = entry;\r
  87     return EOK;\r
  88 }\r
  89 \r
  90 /**@brief Seek to next valid directory entry.\r
  91  *        Here can be jumped to the next data block.\r
  92  * @param it  Initialized iterator\r
  93  * @param pos Position of the next entry\r
  94  * @return Error code\r
  95  */\r
  96 static int ext4_dir_iterator_seek(struct ext4_directory_iterator *it,\r
  97                                   uint64_t pos)\r
  98 {\r
  99     uint64_t size =\r
 100         ext4_inode_get_size(&it->inode_ref->fs->sb, it->inode_ref->inode);\r
 101 \r
 102     /* The iterator is not valid until we seek to the desired position */\r
 103     it->current = NULL;\r
 104 \r
 105     /* Are we at the end? */\r
 106     if (pos >= size) {\r
 107         if (it->current_block.lb_id) {\r
 108 \r
 109             int rc =\r
 110                 ext4_block_set(it->inode_ref->fs->bdev, &it->current_block);\r
 111             it->current_block.lb_id = 0;\r
 112 \r
 113             if (rc != EOK)\r
 114                 return rc;\r
 115         }\r
 116 \r
 117         it->current_offset = pos;\r
 118         return EOK;\r
 119     }\r
 120 \r
 121     /* Compute next block address */\r
 122     uint32_t block_size = ext4_sb_get_block_size(&it->inode_ref->fs->sb);\r
 123     uint64_t current_block_idx = it->current_offset / block_size;\r
 124     uint64_t next_block_idx = pos / block_size;\r
 125 \r
 126     /*\r
 127      * If we don't have a block or are moving accross block boundary,\r
 128      * we need to get another block\r
 129      */\r
 130     if ((it->current_block.lb_id == 0) ||\r
 131         (current_block_idx != next_block_idx)) {\r
 132         if (it->current_block.lb_id) {\r
 133             int rc =\r
 134                 ext4_block_set(it->inode_ref->fs->bdev, &it->current_block);\r
 135             it->current_block.lb_id = 0;\r
 136 \r
 137             if (rc != EOK)\r
 138                 return rc;\r
 139         }\r
 140 \r
 141         uint32_t next_block_phys_idx;\r
 142         int rc = ext4_fs_get_inode_data_block_index(\r
 143             it->inode_ref, next_block_idx, &next_block_phys_idx);\r
 144         if (rc != EOK)\r
 145             return rc;\r
 146 \r
 147         rc = ext4_block_get(it->inode_ref->fs->bdev, &it->current_block,\r
 148                             next_block_phys_idx);\r
 149         if (rc != EOK) {\r
 150             it->current_block.lb_id = 0;\r
 151             return rc;\r
 152         }\r
 153     }\r
 154 \r
 155     it->current_offset = pos;\r
 156 \r
 157     return ext4_dir_iterator_set(it, block_size);\r
 158 }\r
 159 \r
 160 int ext4_dir_iterator_init(struct ext4_directory_iterator *it,\r
 161                            struct ext4_inode_ref *inode_ref, uint64_t pos)\r
 162 {\r
 163     it->inode_ref = inode_ref;\r
 164     it->current = 0;\r
 165     it->current_offset = 0;\r
 166     it->current_block.lb_id = 0;\r
 167 \r
 168     return ext4_dir_iterator_seek(it, pos);\r
 169 }\r
 170 \r
 171 int ext4_dir_iterator_next(struct ext4_directory_iterator *it)\r
 172 {\r
 173     int r = EOK;\r
 174     uint16_t skip;\r
 175 \r
 176     while (r == EOK) {\r
 177         skip = ext4_dir_entry_ll_get_entry_length(it->current);\r
 178         r = ext4_dir_iterator_seek(it, it->current_offset + skip);\r
 179 \r
 180         if (!it->current)\r
 181             break;\r
 182         /*Skip NULL referenced entry*/\r
 183         if (it->current->inode != 0)\r
 184             break;\r
 185     }\r
 186 \r
 187     return r;\r
 188 }\r
 189 \r
 190 int ext4_dir_iterator_fini(struct ext4_directory_iterator *it)\r
 191 {\r
 192     it->current = 0;\r
 193 \r
 194     if (it->current_block.lb_id)\r
 195         return ext4_block_set(it->inode_ref->fs->bdev, &it->current_block);\r
 196 \r
 197     return EOK;\r
 198 }\r
 199 \r
 200 void ext4_dir_write_entry(struct ext4_sblock *sb,\r
 201                           struct ext4_directory_entry_ll *entry,\r
 202                           uint16_t entry_len, struct ext4_inode_ref *child,\r
 203                           const char *name, size_t name_len)\r
 204 {\r
 205     /* Check maximum entry length */\r
 206     ext4_assert(entry_len <= ext4_sb_get_block_size(sb));\r
 207 \r
 208     /* Set basic attributes */\r
 209     ext4_dir_entry_ll_set_inode(entry, child->index);\r
 210     ext4_dir_entry_ll_set_entry_length(entry, entry_len);\r
 211     ext4_dir_entry_ll_set_name_length(sb, entry, name_len);\r
 212 \r
 213     /* Write name */\r
 214     memcpy(entry->name, name, name_len);\r
 215 \r
 216     /* Set type of entry */\r
 217     if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY))\r
 218         ext4_dir_entry_ll_set_inode_type(sb, entry,\r
 219                                          EXT4_DIRECTORY_FILETYPE_DIR);\r
 220     else\r
 221         ext4_dir_entry_ll_set_inode_type(sb, entry,\r
 222                                          EXT4_DIRECTORY_FILETYPE_REG_FILE);\r
 223 }\r
 224 \r
 225 int ext4_dir_add_entry(struct ext4_inode_ref *parent, const char *name,\r
 226                        uint32_t name_len, struct ext4_inode_ref *child)\r
 227 {\r
 228     struct ext4_fs *fs = parent->fs;\r
 229 \r
 230 #if CONFIG_DIR_INDEX_ENABLE\r
 231     /* Index adding (if allowed) */\r
 232     if ((ext4_sb_has_feature_compatible(&fs->sb,\r
 233                                         EXT4_FEATURE_COMPAT_DIR_INDEX)) &&\r
 234         (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {\r
 235         int rc = ext4_dir_dx_add_entry(parent, child, name);\r
 236 \r
 237         /* Check if index is not corrupted */\r
 238         if (rc != EXT4_ERR_BAD_DX_DIR) {\r
 239             if (rc != EOK)\r
 240                 return rc;\r
 241 \r
 242             return EOK;\r
 243         }\r
 244 \r
 245         /* Needed to clear dir index flag if corrupted */\r
 246         ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);\r
 247         parent->dirty = true;\r
 248     }\r
 249 #endif\r
 250 \r
 251     /* Linear algorithm */\r
 252     uint32_t iblock = 0;\r
 253     uint32_t fblock = 0;\r
 254     uint32_t block_size = ext4_sb_get_block_size(&fs->sb);\r
 255     uint32_t inode_size = ext4_inode_get_size(&fs->sb, parent->inode);\r
 256     uint32_t total_blocks = inode_size / block_size;\r
 257 \r
 258     /* Find block, where is space for new entry and try to add */\r
 259     bool success = false;\r
 260     for (iblock = 0; iblock < total_blocks; ++iblock) {\r
 261         int rc = ext4_fs_get_inode_data_block_index(parent, iblock, &fblock);\r
 262         if (rc != EOK)\r
 263             return rc;\r
 264 \r
 265         struct ext4_block block;\r
 266         rc = ext4_block_get(fs->bdev, &block, fblock);\r
 267         if (rc != EOK)\r
 268             return rc;\r
 269 \r
 270         /* If adding is successful, function can finish */\r
 271         rc = ext4_dir_try_insert_entry(&fs->sb, &block, child, name, name_len);\r
 272         if (rc == EOK)\r
 273             success = true;\r
 274 \r
 275         rc = ext4_block_set(fs->bdev, &block);\r
 276         if (rc != EOK)\r
 277             return rc;\r
 278 \r
 279         if (success)\r
 280             return EOK;\r
 281     }\r
 282 \r
 283     /* No free block found - needed to allocate next data block */\r
 284 \r
 285     iblock = 0;\r
 286     fblock = 0;\r
 287     int rc = ext4_fs_append_inode_block(parent, &fblock, &iblock);\r
 288     if (rc != EOK)\r
 289         return rc;\r
 290 \r
 291     /* Load new block */\r
 292     struct ext4_block new_block;\r
 293 \r
 294     rc = ext4_block_get(fs->bdev, &new_block, fblock);\r
 295     if (rc != EOK)\r
 296         return rc;\r
 297 \r
 298     /* Fill block with zeroes */\r
 299     memset(new_block.data, 0, block_size);\r
 300     struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;\r
 301     ext4_dir_write_entry(&fs->sb, block_entry, block_size, child, name,\r
 302                          name_len);\r
 303 \r
 304     /* Save new block */\r
 305     new_block.dirty = true;\r
 306     rc = ext4_block_set(fs->bdev, &new_block);\r
 307 \r
 308     return rc;\r
 309 }\r
 310 \r
 311 int ext4_dir_find_entry(struct ext4_directory_search_result *result,\r
 312                         struct ext4_inode_ref *parent, const char *name,\r
 313                         uint32_t name_len)\r
 314 {\r
 315     struct ext4_sblock *sb = &parent->fs->sb;\r
 316 \r
 317 #if CONFIG_DIR_INDEX_ENABLE\r
 318     /* Index search */\r
 319     if ((ext4_sb_has_feature_compatible(sb, EXT4_FEATURE_COMPAT_DIR_INDEX)) &&\r
 320         (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {\r
 321         int rc = ext4_dir_dx_find_entry(result, parent, name_len, name);\r
 322 \r
 323         /* Check if index is not corrupted */\r
 324         if (rc != EXT4_ERR_BAD_DX_DIR) {\r
 325             if (rc != EOK)\r
 326                 return rc;\r
 327 \r
 328             return EOK;\r
 329         }\r
 330 \r
 331         /* Needed to clear dir index flag if corrupted */\r
 332         ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);\r
 333         parent->dirty = true;\r
 334     }\r
 335 #endif\r
 336 \r
 337     /* Linear algorithm */\r
 338 \r
 339     uint32_t iblock;\r
 340     uint32_t fblock;\r
 341     uint32_t block_size = ext4_sb_get_block_size(sb);\r
 342     uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);\r
 343     uint32_t total_blocks = inode_size / block_size;\r
 344 \r
 345     /* Walk through all data blocks */\r
 346     for (iblock = 0; iblock < total_blocks; ++iblock) {\r
 347         /* Load block address */\r
 348         int rc = ext4_fs_get_inode_data_block_index(parent, iblock, &fblock);\r
 349         if (rc != EOK)\r
 350             return rc;\r
 351 \r
 352         /* Load data block */\r
 353         struct ext4_block block;\r
 354         rc = ext4_block_get(parent->fs->bdev, &block, fblock);\r
 355         if (rc != EOK)\r
 356             return rc;\r
 357 \r
 358         /* Try to find entry in block */\r
 359         struct ext4_directory_entry_ll *res_entry;\r
 360         rc = ext4_dir_find_in_block(&block, sb, name_len, name, &res_entry);\r
 361         if (rc == EOK) {\r
 362             result->block = block;\r
 363             result->dentry = res_entry;\r
 364             return EOK;\r
 365         }\r
 366 \r
 367         /* Entry not found - put block and continue to the next block */\r
 368 \r
 369         rc = ext4_block_set(parent->fs->bdev, &block);\r
 370         if (rc != EOK)\r
 371             return rc;\r
 372     }\r
 373 \r
 374     /* Entry was not found */\r
 375 \r
 376     result->block.lb_id = 0;\r
 377     result->dentry = NULL;\r
 378 \r
 379     return ENOENT;\r
 380 }\r
 381 \r
 382 int ext4_dir_remove_entry(struct ext4_inode_ref *parent, const char *name,\r
 383                           uint32_t name_len)\r
 384 {\r
 385     /* Check if removing from directory */\r
 386     if (!ext4_inode_is_type(&parent->fs->sb, parent->inode,\r
 387                             EXT4_INODE_MODE_DIRECTORY))\r
 388         return ENOTDIR;\r
 389 \r
 390     /* Try to find entry */\r
 391     struct ext4_directory_search_result result;\r
 392     int rc = ext4_dir_find_entry(&result, parent, name, name_len);\r
 393     if (rc != EOK)\r
 394         return rc;\r
 395 \r
 396     /* Invalidate entry */\r
 397     ext4_dir_entry_ll_set_inode(result.dentry, 0);\r
 398 \r
 399     /* Store entry position in block */\r
 400     uint32_t pos = (uint8_t *)result.dentry - result.block.data;\r
 401 \r
 402     /*\r
 403      * If entry is not the first in block, it must be merged\r
 404      * with previous entry\r
 405      */\r
 406     if (pos != 0) {\r
 407         uint32_t offset = 0;\r
 408 \r
 409         /* Start from the first entry in block */\r
 410         struct ext4_directory_entry_ll *tmp_dentry = (void *)result.block.data;\r
 411         uint16_t tmp_dentry_length =\r
 412             ext4_dir_entry_ll_get_entry_length(tmp_dentry);\r
 413 \r
 414         /* Find direct predecessor of removed entry */\r
 415         while ((offset + tmp_dentry_length) < pos) {\r
 416             offset += ext4_dir_entry_ll_get_entry_length(tmp_dentry);\r
 417             tmp_dentry = (void *)(result.block.data + offset);\r
 418             tmp_dentry_length = ext4_dir_entry_ll_get_entry_length(tmp_dentry);\r
 419         }\r
 420 \r
 421         ext4_assert(tmp_dentry_length + offset == pos);\r
 422 \r
 423         /* Add to removed entry length to predecessor's length */\r
 424         uint16_t del_entry_length =\r
 425             ext4_dir_entry_ll_get_entry_length(result.dentry);\r
 426         ext4_dir_entry_ll_set_entry_length(tmp_dentry, tmp_dentry_length +\r
 427                                                            del_entry_length);\r
 428     }\r
 429 \r
 430     result.block.dirty = true;\r
 431 \r
 432     return ext4_dir_destroy_result(parent, &result);\r
 433 }\r
 434 \r
 435 int ext4_dir_try_insert_entry(struct ext4_sblock *sb,\r
 436                               struct ext4_block *target_block,\r
 437                               struct ext4_inode_ref *child, const char *name,\r
 438                               uint32_t name_len)\r
 439 {\r
 440     /* Compute required length entry and align it to 4 bytes */\r
 441     uint32_t block_size = ext4_sb_get_block_size(sb);\r
 442     uint16_t required_len = sizeof(struct ext4_fake_directory_entry) + name_len;\r
 443 \r
 444     if ((required_len % 4) != 0)\r
 445         required_len += 4 - (required_len % 4);\r
 446 \r
 447     /* Initialize pointers, stop means to upper bound */\r
 448     struct ext4_directory_entry_ll *dentry = (void *)target_block->data;\r
 449     struct ext4_directory_entry_ll *stop =\r
 450         (void *)(target_block->data + block_size);\r
 451 \r
 452     /*\r
 453      * Walk through the block and check for invalid entries\r
 454      * or entries with free space for new entry\r
 455      */\r
 456     while (dentry < stop) {\r
 457         uint32_t inode = ext4_dir_entry_ll_get_inode(dentry);\r
 458         uint16_t rec_len = ext4_dir_entry_ll_get_entry_length(dentry);\r
 459 \r
 460         /* If invalid and large enough entry, use it */\r
 461         if ((inode == 0) && (rec_len >= required_len)) {\r
 462             ext4_dir_write_entry(sb, dentry, rec_len, child, name, name_len);\r
 463             target_block->dirty = true;\r
 464 \r
 465             return EOK;\r
 466         }\r
 467 \r
 468         /* Valid entry, try to split it */\r
 469         if (inode != 0) {\r
 470             uint16_t used_name_len =\r
 471                 ext4_dir_entry_ll_get_name_length(sb, dentry);\r
 472 \r
 473             uint16_t used_space =\r
 474                 sizeof(struct ext4_fake_directory_entry) + used_name_len;\r
 475 \r
 476             if ((used_name_len % 4) != 0)\r
 477                 used_space += 4 - (used_name_len % 4);\r
 478 \r
 479             uint16_t free_space = rec_len - used_space;\r
 480 \r
 481             /* There is free space for new entry */\r
 482             if (free_space >= required_len) {\r
 483                 /* Cut tail of current entry */\r
 484                 ext4_dir_entry_ll_set_entry_length(dentry, used_space);\r
 485                 struct ext4_directory_entry_ll *new_entry =\r
 486                     (void *)((uint8_t *)dentry + used_space);\r
 487                 ext4_dir_write_entry(sb, new_entry, free_space, child, name,\r
 488                                      name_len);\r
 489 \r
 490                 target_block->dirty = true;\r
 491                 return EOK;\r
 492             }\r
 493         }\r
 494 \r
 495         /* Jump to the next entry */\r
 496         dentry = (void *)((uint8_t *)dentry + rec_len);\r
 497     }\r
 498 \r
 499     /* No free space found for new entry */\r
 500     return ENOSPC;\r
 501 }\r
 502 \r
 503 int ext4_dir_find_in_block(struct ext4_block *block, struct ext4_sblock *sb,\r
 504                            size_t name_len, const char *name,\r
 505                            struct ext4_directory_entry_ll **res_entry)\r
 506 {\r
 507     /* Start from the first entry in block */\r
 508     struct ext4_directory_entry_ll *dentry =\r
 509         (struct ext4_directory_entry_ll *)block->data;\r
 510 \r
 511     /* Set upper bound for cycling */\r
 512     uint8_t *addr_limit = block->data + ext4_sb_get_block_size(sb);\r
 513 \r
 514     /* Walk through the block and check entries */\r
 515     while ((uint8_t *)dentry < addr_limit) {\r
 516         /* Termination condition */\r
 517         if ((uint8_t *)dentry + name_len > addr_limit)\r
 518             break;\r
 519 \r
 520         /* Valid entry - check it */\r
 521         if (dentry->inode != 0) {\r
 522             /* For more effectivity compare firstly only lengths */\r
 523             if (ext4_dir_entry_ll_get_name_length(sb, dentry) == name_len) {\r
 524                 /* Compare names */\r
 525                 if (memcmp((uint8_t *)name, dentry->name, name_len) == 0) {\r
 526                     *res_entry = dentry;\r
 527                     return EOK;\r
 528                 }\r
 529             }\r
 530         }\r
 531 \r
 532         uint16_t dentry_len = ext4_dir_entry_ll_get_entry_length(dentry);\r
 533 \r
 534         /* Corrupted entry */\r
 535         if (dentry_len == 0)\r
 536             return EINVAL;\r
 537 \r
 538         /* Jump to next entry */\r
 539         dentry =\r
 540             (struct ext4_directory_entry_ll *)((uint8_t *)dentry + dentry_len);\r
 541     }\r
 542 \r
 543     /* Entry not found */\r
 544     return ENOENT;\r
 545 }\r
 546 \r
 547 int ext4_dir_destroy_result(struct ext4_inode_ref *parent,\r
 548                             struct ext4_directory_search_result *result)\r
 549 {\r
 550     if (result->block.lb_id)\r
 551         return ext4_block_set(parent->fs->bdev, &result->block);\r
 552 \r
 553     return EOK;\r
 554 }\r
 555 \r
 556 /**\r
 557  * @}\r
 558  */\r