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