Changeset ee3b6150 in mainline


Ignore:
Timestamp:
2012-04-23T16:01:14Z (13 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
bc03679
Parents:
6773ff3
Message:

I-node allocator comments, hash comments, part of the extent comments

Location:
uspace/lib/ext4
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/ext4/libext4_extent.c

    r6773ff3 ree3b6150  
    523523}
    524524
    525 // TODO comments
    526 
    527 // Recursive release
     525/** Recursively release the whole branch of the extent tree.
     526 *
     527 * For each entry of the node release the subbranch and finally release
     528 * the node. In the leaf node all extents will be released.
     529 *
     530 * @param inode_ref             i-node where the branch is released
     531 * @param index                 index in the non-leaf node to be released
     532 *                                              with the whole subtree
     533 * @return                              error code
     534 */
    528535static int ext4_extent_release_branch(ext4_inode_ref_t *inode_ref,
    529536                ext4_extent_index_t *index)
    … …  
    534541
    535542        uint32_t fblock = ext4_extent_index_get_leaf(index);
    536 
    537 //      EXT4FS_DBG("fblock = \%u", fblock);
    538543
    539544        rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NOREAD);
    … …  
    547552        if (ext4_extent_header_get_depth(header)) {
    548553
     554                // The node is non-leaf, do recursion
     555
    549556                ext4_extent_index_t *idx = EXT4_EXTENT_FIRST_INDEX(header);
    550557
     558                // Release all subbranches
    551559                for (uint32_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i, ++idx) {
    552560                        rc = ext4_extent_release_branch(inode_ref, idx);
    … …  
    557565                }
    558566        } else {
     567
     568                // Leaf node reached
    559569                ext4_extent_t *ext = EXT4_EXTENT_FIRST(header);
     570
     571                // Release all extents and stop recursion
    560572
    561573                for (uint32_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i, ++ext) {
    … …  
    568580        }
    569581
     582        // Release data block where the node was stored
     583
    570584        rc = block_put(block);
    571585        if (rc != EOK) {
    … …  
    579593}
    580594
     595/** Release all data blocks starting from specified logical block.
     596 *
     597 * @param inode_ref             i-node to release blocks from
     598 * @param iblock_from   first logical block to release
     599 */
    581600int ext4_extent_release_blocks_from(ext4_inode_ref_t *inode_ref,
    582601                uint32_t iblock_from)
    … …  
    609628                        ext4_extent_get_start(path_ptr->extent);
    610629
     630        // Release all blocks
    611631        rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count);
    612632        if (rc != EOK) {
    … …  
    614634        }
    615635
     636        // Correct counter
    616637        block_count -= delete_count;
    617638        ext4_extent_set_block_count(path_ptr->extent, block_count);
    618639
     640        // Initialize the following loop
    619641        uint16_t entries = ext4_extent_header_get_entries_count(path_ptr->header);
    620642        ext4_extent_t *tmp_ext = path_ptr->extent + 1;
    … …  
    658680        --path_ptr;
    659681
    660         // release all successors in all levels
    661         while(path_ptr >= path) {
     682        // release all successors in all tree levels
     683        while (path_ptr >= path) {
    662684                entries = ext4_extent_header_get_entries_count(path_ptr->header);
    663685                ext4_extent_index_t *index = path_ptr->index + 1;
    … …  
    665687                                EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;
    666688
     689                // Correct entry because of changes in the previous iteration
    667690                if (check_tree) {
    668691                        entries--;
    669692                        ext4_extent_header_set_entries_count(path_ptr->header, entries);
    670                 }
    671 
     693                } else {
     694                        // TODO check this condition
     695                        break;
     696                }
     697
     698                // Iterate over all entries and release the whole subtrees
    672699                while (index < stop) {
    673700                        rc = ext4_extent_release_branch(inode_ref, index);
    … …  
    682709                path_ptr->block->dirty = true;
    683710
     711                // Free the node if it is empty
    684712                if ((entries == 0) && (path_ptr != path)) {
    685713                        rc = ext4_balloc_free_block(inode_ref, path_ptr->block->lba);
    … …  
    687715                                goto cleanup;
    688716                        }
     717
     718                        // Mark parent to be checked
    689719                        check_tree = true;
    690720                } else {
    … …  
    711741}
    712742
     743/** TODO
     744 *
     745 */
    713746static int ext4_extent_append_extent(ext4_inode_ref_t *inode_ref,
    714747                ext4_extent_path_t *path, ext4_extent_path_t **last_path_item,

  • uspace/lib/ext4/libext4_hash.c

    r6773ff3 ree3b6150  
    227227}
    228228
     229
     230/** Compute hash value of the string.
     231 *
     232 * @param hinfo         hash info structure with information about
     233 *                                      the algorithm, hash seed and with the place
     234 *                                      for the output hash value
     235 * @param len           length of the name
     236 * @param name          name to be hashed
     237 * @return                      error code
     238 */
    229239int ext4_hash_string(ext4_hash_info_t *hinfo, int len, const char *name)
    230240{

  • uspace/lib/ext4/libext4_ialloc.c

    r6773ff3 ree3b6150  
    4040#include "libext4.h"
    4141
     42
     43/** Convert i-node number to relative index in block group.
     44 *
     45 * @param sb    superblock
     46 * @param inode i-node number to be converted
     47 * @return              index of the i-node in the block group
     48 */
    4249static uint32_t ext4_ialloc_inode2index_in_group(ext4_superblock_t *sb,
    4350                uint32_t inode)
    … …  
    4754}
    4855
     56/** Convert relative index of i-node to absolute i-node number.
     57 *
     58 * @param sb    superblock
     59 * @param inode index to be converted
     60 * @return              absolute number of the i-node
     61 */
    4962static uint32_t ext4_ialloc_index_in_group2inode(ext4_superblock_t *sb,
    5063                uint32_t index, uint32_t bgid)
    … …  
    5467}
    5568
     69/** Compute block group number from the i-node number.
     70 *
     71 * @param sb            superblock
     72 * @param inode         i-node number to be found the block group for
     73 * @return                      block group number computed from i-node number
     74 */
    5675static uint32_t ext4_ialloc_get_bgid_of_inode(ext4_superblock_t *sb,
    5776                uint32_t inode)
    … …  
    6382
    6483
     84/** Free i-node number and modify filesystem data structers.
     85 *
     86 * @param fs            filesystem, where the i-node is located
     87 * @param index         index of i-node to be release
     88 * @param is_dir        flag us for information whether i-node is directory or not
     89 */
    6590int ext4_ialloc_free_inode(ext4_filesystem_t *fs, uint32_t index, bool is_dir)
    6691{
    … …  
    6994        ext4_superblock_t *sb = fs->superblock;
    7095
     96        // Compute index of block group and load it
    7197        uint32_t block_group = ext4_ialloc_get_bgid_of_inode(sb, index);
    7298
    … …  
    77103        }
    78104
     105        // Load i-node bitmap
    79106        uint32_t bitmap_block_addr = ext4_block_group_get_inode_bitmap(
    80107                        bg_ref->block_group, sb);
    … …  
    85112        }
    86113
     114        // Free i-node in the bitmap
    87115        uint32_t index_in_group = ext4_ialloc_inode2index_in_group(sb, index);
    88116        ext4_bitmap_free_bit(bitmap_block->data, index_in_group);
    89117        bitmap_block->dirty = true;
    90118
     119        // Put back the block with bitmap
    91120        rc = block_put(bitmap_block);
    92121        if (rc != EOK) {
    … …  
    96125        }
    97126
    98         // if inode is directory, decrement used directories count
     127        // If released i-node is a directory, decrement used directories count
    99128        if (is_dir) {
    100129                uint32_t bg_used_dirs = ext4_block_group_get_used_dirs_count(
    … …  
    112141                        sb, free_inodes);
    113142
     143        // Set unused i-nodes count if supported
    114144        if (ext4_block_group_has_flag(bg_ref->block_group, EXT4_BLOCK_GROUP_INODE_UNINIT)) {
    115145                uint32_t unused_inodes = ext4_block_group_get_itable_unused(
    … …  
    121151        bg_ref->dirty = true;
    122152
     153        // Put back the modified block group
    123154        rc = ext4_filesystem_put_block_group_ref(bg_ref);
    124155        if (rc != EOK) {
    … …  
    134165}
    135166
     167/** I-node allocation algorithm.
     168 *
     169 * This is more simple algorithm, than Orlov allocator used in the Linux kernel
     170 *
     171 * @param fs            filesystem to allocate i-node on
     172 * @param index         output value - allocated i-node number
     173 * @param is_dir        flag if allocated i-node will be file or directory
     174 * @return                      error code
     175 */
    136176int ext4_ialloc_alloc_inode(ext4_filesystem_t *fs, uint32_t *index, bool is_dir)
    137177{
    … …  
    145185        uint32_t avg_free_inodes = sb_free_inodes / bg_count;
    146186
     187        // Try to find free i-node in all block groups
    147188        while (bgid < bg_count) {
    148189
     190                // Load block group to check
    149191                ext4_block_group_ref_t *bg_ref;
    150192                rc = ext4_filesystem_get_block_group_ref(fs, bgid, &bg_ref);
    … …  
    152194                        return rc;
    153195                }
     196
    154197                ext4_block_group_t *bg = bg_ref->block_group;
    155198
     199                // Read necessary values for algorithm
    156200                uint32_t free_blocks = ext4_block_group_get_free_blocks_count(bg, sb);
    157201                uint32_t free_inodes = ext4_block_group_get_free_inodes_count(bg, sb);
    158202                uint32_t used_dirs = ext4_block_group_get_used_dirs_count(bg, sb);
    159203
     204                // Check if this block group is good candidate for allocation
    160205                if ((free_inodes >= avg_free_inodes) && (free_blocks > 0)) {
    161206
     207                        // Load block with bitmap
    162208                        uint32_t bitmap_block_addr =  ext4_block_group_get_inode_bitmap(
    163209                                        bg_ref->block_group, sb);
    … …  
    170216                        }
    171217
    172                         // Alloc bit
     218                        // Try to allocate i-node in the bitmap
    173219                        uint32_t inodes_in_group = ext4_superblock_get_inodes_in_group(sb, bgid);
    174220                        uint32_t index_in_group;
    … …  
    176222                                        bitmap_block->data, 0, &index_in_group, inodes_in_group);
    177223
    178                         // Block group is full (inodes)
     224                        // Block group has not any free i-node
    179225                        if (rc == ENOSPC) {
    180226                                block_put(bitmap_block);
    … …  
    183229                        }
    184230
     231                        // Free i-node found, save the bitmap
    185232                        bitmap_block->dirty = true;
    186233
    … …  
    194241                        ext4_block_group_set_free_inodes_count(bg, sb, free_inodes);
    195242
     243                        // Decrement unused i-nodes counter if supported
    196244                        if (ext4_block_group_has_flag(bg, EXT4_BLOCK_GROUP_INODE_UNINIT)) {
    197245                                uint16_t unused_inodes = ext4_block_group_get_itable_unused(bg, sb);
    … …  
    200248                        }
    201249
     250                        // Increment used directories counter
    202251                        if (is_dir) {
    203252                                used_dirs++;
    … …  
    205254                        }
    206255
     256                        // Save modified block group
    207257                        bg_ref->dirty = true;
    208258
    … …  
    213263                        }
    214264
     265                        // Update superblock
    215266                        sb_free_inodes--;
    216267                        ext4_superblock_set_free_inodes_count(sb, sb_free_inodes);
    217268
     269                        // Compute the absolute i-nodex number
    218270                        *index = ext4_ialloc_index_in_group2inode(sb, index_in_group, bgid);
    219271
    … …  
    222274                }
    223275
    224                 // Not modified
     276                // Block group not modified, put it and jump to the next block group
    225277                ext4_filesystem_put_block_group_ref(bg_ref);
    226278                ++bgid;
Note: See TracChangeset for help on using the changeset viewer.