Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset bae2a79e in mainline


Ignore:
Timestamp:
2012-04-20T09:51:44Z (10 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master
Children:
d37d500e
Parents:
dfac604
Message:

Comments and some simple modifications of code for work with directory entry

Location:
uspace
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • uspace/lib/ext4/libext4_directory.c

    rdfac604 rbae2a79e  
    4242#include "libext4.h"
    4343
    44 static int ext4_directory_iterator_set(ext4_directory_iterator_t *,
    45     uint32_t);
    46 
    47 
     44
     45/** Get i-node number from directory entry.
     46 *
     47 * @param de    directory entry
     48 * @return              i-node number
     49 */
    4850uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *de)
    4951{
     
    5153}
    5254
     55/** Set i-node number to directory entry.
     56 *
     57 * @param de    directory entry
     58 * @param inode i-node number
     59 */
    5360void ext4_directory_entry_ll_set_inode(ext4_directory_entry_ll_t *de,
    5461                uint32_t inode)
     
    5764}
    5865
     66/** Get directory entry length.
     67 *
     68 * @param de    directory entry
     69 * @return              entry length
     70 */
    5971uint16_t ext4_directory_entry_ll_get_entry_length(
    6072                ext4_directory_entry_ll_t *de)
     
    6375}
    6476
     77/** Set directory entry length.
     78 *
     79 * @param de            directory entry
     80 * @param length        entry length
     81 */
     82
    6583void ext4_directory_entry_ll_set_entry_length(ext4_directory_entry_ll_t *de,
    6684                uint16_t length)
     
    6987}
    7088
     89/** Get directory entry name length.
     90 *
     91 * @param sb    superblock
     92 * @param de    directory entry
     93 * @return              entry name length
     94 */
    7195uint16_t ext4_directory_entry_ll_get_name_length(
    7296    ext4_superblock_t *sb, ext4_directory_entry_ll_t *de)
     
    83107}
    84108
     109/** Set directory entry name length.
     110 *
     111 * @param sb            superblock
     112 * @param de            directory entry
     113 * @param length        entry name length
     114 */
    85115void ext4_directory_entry_ll_set_name_length(ext4_superblock_t *sb,
    86116                ext4_directory_entry_ll_t *de, uint16_t length)
     
    95125}
    96126
     127/** Get i-node type of directory entry.
     128 *
     129 * @param sb    superblock
     130 * @param de    directory entry
     131 * @return              i-node type (file, dir, etc.)
     132 */
    97133uint8_t ext4_directory_entry_ll_get_inode_type(
    98134                ext4_superblock_t *sb, ext4_directory_entry_ll_t *de)
     
    108144}
    109145
     146/** Set i-node type of directory entry.
     147 *
     148 * @param sb    superblock
     149 * @param de    directory entry
     150 * @param type  i-node type (file, dir, etc.)
     151 */
    110152void ext4_directory_entry_ll_set_inode_type(
    111153                ext4_superblock_t *sb, ext4_directory_entry_ll_t *de, uint8_t type)
     
    121163}
    122164
     165static int ext4_directory_iterator_seek(
     166                ext4_directory_iterator_t *, aoff64_t);
     167static int ext4_directory_iterator_set(
     168                ext4_directory_iterator_t *, uint32_t);
     169
     170
     171/** Initialize directory iterator.
     172 *
     173 * Set position to the first valid entry from the required position.
     174 *
     175 * @param it                    pointer to iterator to be initialized
     176 * @param inode_ref             directory i-node
     177 * @param pos                   position to start reading entries from
     178 * @return                              error code
     179 */
    123180int ext4_directory_iterator_init(ext4_directory_iterator_t *it,
    124     ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, aoff64_t pos)
     181                ext4_inode_ref_t *inode_ref, aoff64_t pos)
    125182{
    126183        it->inode_ref = inode_ref;
    127         it->fs = fs;
    128184        it->current = NULL;
    129185        it->current_offset = 0;
     
    133189}
    134190
    135 
     191/** Jump to the next valid entry
     192 *
     193 * @param it    initialized iterator
     194 * @return              error code
     195 */
    136196int ext4_directory_iterator_next(ext4_directory_iterator_t *it)
    137197{
     
    145205}
    146206
    147 
     207/** Seek to next valid directory entry.
     208 *
     209 * Here can be jumped to the next data block.
     210 *
     211 * @param it    initialized iterator
     212 * @param pos   position of the next entry
     213 * @return              error code
     214 */
    148215int ext4_directory_iterator_seek(ext4_directory_iterator_t *it, aoff64_t pos)
    149216{
    150217        int rc;
    151218
    152         uint64_t size = ext4_inode_get_size(it->fs->superblock, it->inode_ref->inode);
     219        uint64_t size = ext4_inode_get_size(
     220                        it->inode_ref->fs->superblock, it->inode_ref->inode);
    153221
    154222        /* The iterator is not valid until we seek to the desired position */
     
    169237        }
    170238
    171         uint32_t block_size = ext4_superblock_get_block_size(it->fs->superblock);
     239        // Compute next block address
     240        uint32_t block_size = ext4_superblock_get_block_size(
     241                        it->inode_ref->fs->superblock);
    172242        aoff64_t current_block_idx = it->current_offset / block_size;
    173243        aoff64_t next_block_idx = pos / block_size;
     
    192262                }
    193263
    194                 rc = block_get(&it->current_block, it->fs->device, next_block_phys_idx,
    195                     BLOCK_FLAGS_NONE);
     264                rc = block_get(&it->current_block, it->inode_ref->fs->device,
     265                                next_block_phys_idx, BLOCK_FLAGS_NONE);
    196266                if (rc != EOK) {
    197267                        it->current_block = NULL;
     
    205275}
    206276
     277/** Do some checks before returning iterator.
     278 *
     279 * @param it                    iterator to be checked
     280 * @param block_size    size of data block
     281 * @return                              error code
     282 */
    207283static int ext4_directory_iterator_set(ext4_directory_iterator_t *it,
    208284    uint32_t block_size)
     
    232308
    233309        /* Ensure the name length is not too large */
    234         if (ext4_directory_entry_ll_get_name_length(it->fs->superblock,
     310        if (ext4_directory_entry_ll_get_name_length(it->inode_ref->fs->superblock,
    235311            entry) > length-8) {
    236312                return EIO;
    237313        }
    238314
     315        // Everything OK - "publish" the entry
    239316        it->current = entry;
    240317        return EOK;
     
    242319
    243320
     321/** Uninitialize directory iterator.
     322 *
     323 * Release all allocated structures.
     324 *
     325 * @param it    iterator to be finished
     326 * @return              error code
     327 */
    244328int ext4_directory_iterator_fini(ext4_directory_iterator_t *it)
    245329{
    246330        int rc;
    247331
    248         it->fs = NULL;
    249332        it->inode_ref = NULL;
    250333        it->current = NULL;
     
    260343}
    261344
     345/**     Write directory entry to concrete data block.
     346 *
     347 * @param sb            superblock
     348 * @param entry         pointer to entry to be written
     349 * @param entry_len     lenght of new entry
     350 * @param child         child i-node to be written to new entry
     351 * @param name          name of the new entry
     352 * @param name_len      length of entry name
     353 */
    262354void ext4_directory_write_entry(ext4_superblock_t *sb,
    263355                ext4_directory_entry_ll_t *entry, uint16_t entry_len,
     
    265357{
    266358
    267         EXT4FS_DBG("writing entry \%s, len \%u, addr = \%u", name, entry_len, (uint32_t)entry);
    268 
     359        // Check maximum entry length
     360        uint32_t block_size = ext4_superblock_get_block_size(sb);
     361        assert(entry_len <= block_size);
     362
     363        // Set basic attributes
    269364        ext4_directory_entry_ll_set_inode(entry, child->index);
    270365        ext4_directory_entry_ll_set_entry_length(entry, entry_len);
    271366        ext4_directory_entry_ll_set_name_length(sb, entry, name_len);
    272367
     368        // Write name
     369        memcpy(entry->name, name, name_len);
     370
     371        // Set type of entry
    273372        if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY)) {
    274373                ext4_directory_entry_ll_set_inode_type(
     
    278377                                sb, entry, EXT4_DIRECTORY_FILETYPE_REG_FILE);
    279378        }
    280         memcpy(entry->name, name, name_len);
    281 }
    282 
     379
     380}
     381
     382/** Add new entry to the directory.
     383 *
     384 * @param parent        directory i-node
     385 * @param name          name of new entry
     386 * @param child         i-node to be referenced from new entry
     387 * @return                      error code
     388 */
    283389int ext4_directory_add_entry(ext4_inode_ref_t * parent,
    284390                const char *name, ext4_inode_ref_t *child)
    285391{
    286392        int rc;
    287 
    288         EXT4FS_DBG("adding entry to directory \%u [ino = \%u, name = \%s]", parent->index, child->index, name);
    289393
    290394        ext4_filesystem_t *fs = parent->fs;
     
    294398                        ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) {
    295399
    296                 EXT4FS_DBG("index");
    297 
    298400                rc = ext4_directory_dx_add_entry(parent, child, name);
    299401
     
    308410                }
    309411
    310                 // Needed to clear dir index flag
     412                // Needed to clear dir index flag if corrupted
    311413                ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
    312414                parent->dirty = true;
     
    324426        uint32_t name_len = strlen(name);
    325427
    326         // Find block, where is space for new entry
     428        // Find block, where is space for new entry and try to add
    327429        bool success = false;
    328430        for (iblock = 0; iblock < total_blocks; ++iblock) {
     
    339441                }
    340442
     443                // If adding is successful, function can finish
    341444                rc = ext4_directory_try_insert_entry(fs->superblock, block, child, name, name_len);
    342445                if (rc == EOK) {
     
    354457        }
    355458
    356         // No free block found - needed to allocate next block
     459        // No free block found - needed to allocate next data block
    357460
    358461        iblock = 0;
     
    363466        }
    364467
    365         EXT4FS_DBG("using iblock \%u fblock \%u", iblock, fblock);
    366 
    367468        // Load new block
    368469        block_t *new_block;
     
    387488}
    388489
     490/** Find directory entry with passed name.
     491 *
     492 * @param result        result structure to be returned if entry found
     493 * @param parent        directory i-node
     494 * @param name          name of entry to be found
     495 * @return                      error code
     496 */
    389497int ext4_directory_find_entry(ext4_directory_search_result_t *result,
    390498                ext4_inode_ref_t *parent, const char *name)
     
    410518                }
    411519
     520                // Needed to clear dir index flag if corrupted
     521                ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
     522                parent->dirty = true;
     523
    412524                EXT4FS_DBG("index is corrupted - doing linear search");
    413525        }
     526
     527        // Linear algorithm
    414528
    415529        uint32_t iblock, fblock;
     
    418532        uint32_t total_blocks = inode_size / block_size;
    419533
     534        // Walk through all data blocks
    420535        for (iblock = 0; iblock < total_blocks; ++iblock) {
    421536
     537                // Load block address
    422538                rc = ext4_filesystem_get_inode_data_block_index(parent, iblock, &fblock);
    423539                if (rc != EOK) {
     
    425541                }
    426542
     543                // Load data block
    427544                block_t *block;
    428545                rc = block_get(&block, parent->fs->device, fblock, BLOCK_FLAGS_NONE);
     
    431548                }
    432549
    433                 // find block entry
     550                // Try to find entry in block
    434551                ext4_directory_entry_ll_t *res_entry;
    435552                rc = ext4_directory_find_in_block(block, sb, name_len, name, &res_entry);
     
    440557                }
    441558
     559                // Entry not found - put block and continue to the next block
     560
    442561                rc = block_put(block);
    443562                if (rc != EOK) {
     
    445564                }
    446565        }
     566
     567        // Entry was not found
    447568
    448569        result->block = NULL;
     
    453574
    454575
     576/** Remove directory entry.
     577 *
     578 * @param parent        directory i-node
     579 * @param name          name of the entry to be removed
     580 * @return                      error code
     581 */
    455582int ext4_directory_remove_entry(ext4_inode_ref_t *parent, const char *name)
    456583{
    457584        int rc;
    458585
     586        // Check if removing from directory
    459587        if (!ext4_inode_is_type(parent->fs->superblock, parent->inode,
    460588            EXT4_INODE_MODE_DIRECTORY)) {
     
    462590        }
    463591
     592        // Try to find entry
    464593        ext4_directory_search_result_t result;
    465594        rc  = ext4_directory_find_entry(&result, parent, name);
     
    468597        }
    469598
     599        // Invalidate entry
    470600        ext4_directory_entry_ll_set_inode(result.dentry, 0);
    471601
     602        // Store entry position in block
    472603        uint32_t pos = (void *)result.dentry - result.block->data;
    473604
    474         uint32_t offset = 0;
     605        // If entry is not the first in block, it must be merged
     606        // with previous entry
    475607        if (pos != 0) {
    476608
     609                uint32_t offset = 0;
     610
     611                // Start from the first entry in block
    477612                ext4_directory_entry_ll_t *tmp_dentry = result.block->data;
    478613                uint16_t tmp_dentry_length =
    479614                                ext4_directory_entry_ll_get_entry_length(tmp_dentry);
    480615
     616                // Find direct predecessor of removed entry
    481617                while ((offset + tmp_dentry_length) < pos) {
    482618                        offset += ext4_directory_entry_ll_get_entry_length(tmp_dentry);
     
    488624                assert(tmp_dentry_length + offset == pos);
    489625
     626                // Add to removed entry length to predecessor's length
    490627                uint16_t del_entry_length =
    491628                                ext4_directory_entry_ll_get_entry_length(result.dentry);
     
    500637}
    501638
    502 
     639/** Try to insert entry to concrete data block.
     640 *
     641 * @param sb                    superblock
     642 * @param target_block  block to try to insert entry to
     643 * @param child                 child i-node to be inserted by new entry
     644 * @param name                  name of the new entry
     645 * @param name_len              length of the new entry name
     646 * @return                              error code
     647 */
    503648int ext4_directory_try_insert_entry(ext4_superblock_t *sb,
    504649                block_t *target_block, ext4_inode_ref_t *child,
    505650                const char *name, uint32_t name_len)
    506651{
     652        // Compute required length entry and align it to 4 bytes
    507653        uint32_t block_size = ext4_superblock_get_block_size(sb);
    508654        uint16_t required_len = sizeof(ext4_fake_directory_entry_t) + name_len;
     
    511657        }
    512658
     659        // Initialize pointers, stop means to upper bound
    513660        ext4_directory_entry_ll_t *dentry = target_block->data;
    514661        ext4_directory_entry_ll_t *stop = target_block->data + block_size;
    515662
     663        // Walk through the block and check for invalid entries
     664        // or entries with free space for new entry
    516665        while (dentry < stop) {
    517666
     
    519668                uint16_t rec_len = ext4_directory_entry_ll_get_entry_length(dentry);
    520669
     670                // If invalid and large enough entry, use it
    521671                if ((inode == 0) && (rec_len >= required_len)) {
    522672                        ext4_directory_write_entry(sb, dentry, rec_len, child, name, name_len);
     
    525675                }
    526676
     677                // Valid entry, try to split it
    527678                if (inode != 0) {
    528679                        uint16_t used_name_len =
     
    536687                        uint16_t free_space = rec_len - used_space;
    537688
     689                        // There is free space for new entry
    538690                        if (free_space >= required_len) {
    539691
     
    550702                }
    551703
     704                // Jump to the next entry
    552705                dentry = (void *)dentry + rec_len;
    553706        }
    554707
     708        // No free space found for new entry
     709
    555710        return ENOSPC;
    556711}
    557712
     713/** Try to find entry in block by name.
     714 *
     715 * @param block         block containing entries
     716 * @param sb            superblock
     717 * @param name_len      length of entry name
     718 * @param name          name of entry to be found
     719 * @param res_entry     output pointer to found entry, NULL if not found
     720 * @return                      error code
     721 */
    558722int ext4_directory_find_in_block(block_t *block,
    559723                ext4_superblock_t *sb, size_t name_len, const char *name,
    560724                ext4_directory_entry_ll_t **res_entry)
    561725{
    562 
     726        // Start from the first entry in block
    563727        ext4_directory_entry_ll_t *dentry = (ext4_directory_entry_ll_t *)block->data;
     728        //Set upper bound for cycling
    564729        uint8_t *addr_limit = block->data + ext4_superblock_get_block_size(sb);
    565730
     731        // Walk through the block and check entries
    566732        while ((uint8_t *)dentry < addr_limit) {
    567733
     734                // Termination condition
    568735                if ((uint8_t*) dentry + name_len > addr_limit) {
    569736                        break;
    570737                }
    571738
     739                // Valid entry - check it
    572740                if (dentry->inode != 0) {
     741
     742                        // For more effectivity compare firstly only lengths
    573743                        if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) {
    574744                                // Compare names
     
    580750                }
    581751
    582                 // Goto next entry
    583752                uint16_t dentry_len = ext4_directory_entry_ll_get_entry_length(dentry);
    584753
     754                // Corrupted entry
    585755                if (dentry_len == 0) {
    586756                        return EINVAL;
    587757                }
    588758
     759                // Jump to next entry
    589760                dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len);
    590761        }
    591762
     763        // Entry not found
    592764        return ENOENT;
    593765}
    594766
     767/** Simple function to release allocated data from result.
     768 *
     769 * @param result        search result to destroy
     770 * @return                      error code
     771 */
    595772int ext4_directory_destroy_result(ext4_directory_search_result_t *result)
    596773{
  • uspace/lib/ext4/libext4_directory.h

    rdfac604 rbae2a79e  
    5353
    5454extern int ext4_directory_iterator_init(ext4_directory_iterator_t *,
    55                 ext4_filesystem_t *, ext4_inode_ref_t *, aoff64_t);
     55                ext4_inode_ref_t *, aoff64_t);
    5656extern int ext4_directory_iterator_next(ext4_directory_iterator_t *);
    57 extern int ext4_directory_iterator_seek(ext4_directory_iterator_t *, aoff64_t);
    5857extern int ext4_directory_iterator_fini(ext4_directory_iterator_t *);
    5958
  • uspace/lib/ext4/libext4_types.h

    rdfac604 rbae2a79e  
    386386
    387387typedef struct ext4_directory_iterator {
    388         ext4_filesystem_t *fs;
    389388        ext4_inode_ref_t *inode_ref;
    390389        block_t *current_block;
  • uspace/srv/fs/ext4fs/ext4fs_ops.c

    rdfac604 rbae2a79e  
    746746
    747747        ext4_directory_iterator_t it;
    748         rc = ext4_directory_iterator_init(&it, fs, enode->inode_ref, 0);
     748        rc = ext4_directory_iterator_init(&it, enode->inode_ref, 0);
    749749        if (rc != EOK) {
    750750                return rc;
     
    11121112
    11131113        ext4_directory_iterator_t it;
    1114         rc = ext4_directory_iterator_init(&it, inst->filesystem, inode_ref, pos);
     1114        rc = ext4_directory_iterator_init(&it, inode_ref, pos);
    11151115        if (rc != EOK) {
    11161116                async_answer_0(callid, rc);
Note: See TracChangeset for help on using the changeset viewer.