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

Changeset 728d771 in mainline


Ignore:
Timestamp:
2012-04-22T13:11:29Z (10 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master
Children:
6773ff3
Parents:
cb7056a
Message:

next part of comments on extent code

File:
1 edited

Legend:

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

    rcb7056a r728d771  
    4141#include "libext4.h"
    4242
    43 /** Get logical number of the block covered extent.
     43/** Get logical number of the block covered by extent.
    4444 *
    4545 * @param extent        extent to load number from
     
    5353/** Set logical number of the first block covered by extent.
    5454 *
    55  * @param extent        extent to load number from
     55 * @param extent        extent to set number to
    5656 * @param iblock        logical number of the first block covered by extent
    5757 */
     
    103103}
    104104
    105 // TODO start comments here
    106 
     105/** Get logical number of the block covered by extent index.
     106 *
     107 * @param index         extent index to load number from
     108 * @return                      logical number of the first block covered by extent index
     109 */
    107110uint32_t ext4_extent_index_get_first_block(ext4_extent_index_t *index)
    108111{
     
    110113}
    111114
     115/** Set logical number of the block covered by extent index.
     116 *
     117 * @param index         extent index to set number to
     118 * @param iblock        logical number of the first block covered by extent index
     119 */
    112120void ext4_extent_index_set_first_block(ext4_extent_index_t *index,
    113                 uint32_t first)
    114 {
    115         index->first_block = host2uint32_t_le(first);
    116 }
    117 
     121                uint32_t iblock)
     122{
     123        index->first_block = host2uint32_t_le(iblock);
     124}
     125
     126/** Get physical number of block where the child node is located.
     127 *
     128 * @param index         extent index to load number from
     129 * @return                      physical number of the block with child node
     130 */
    118131uint64_t ext4_extent_index_get_leaf(ext4_extent_index_t *index)
    119132{
     
    122135}
    123136
    124 void ext4_extent_index_set_leaf(ext4_extent_index_t *index, uint64_t leaf)
    125 {
    126         index->leaf_lo = host2uint32_t_le((leaf << 32) >> 32);
    127         index->leaf_hi = host2uint16_t_le((uint16_t)(leaf >> 32));
    128 }
    129 
     137/** Set physical number of block where the child node is located.
     138 *
     139 * @param index         extent index to set number to
     140 * @param fblock        physical number of the block with child node
     141 */
     142void ext4_extent_index_set_leaf(ext4_extent_index_t *index, uint64_t fblock)
     143{
     144        index->leaf_lo = host2uint32_t_le((fblock << 32) >> 32);
     145        index->leaf_hi = host2uint16_t_le((uint16_t)(fblock >> 32));
     146}
     147
     148/** Get magic value from extent header.
     149 *
     150 * @param header        extent header to load value from
     151 * @return                      magic value of extent header
     152 */
    130153uint16_t ext4_extent_header_get_magic(ext4_extent_header_t *header)
    131154{
     
    133156}
    134157
     158/** Set magic value to extent header.
     159 *
     160 * @param header        extent header to set value to
     161 * @param magic         magic value of extent header
     162 */
    135163void ext4_extent_header_set_magic(ext4_extent_header_t *header, uint16_t magic)
    136164{
     
    138166}
    139167
     168/** Get number of entries from extent header
     169 *
     170 * @param header        extent header to get value from
     171 * @return                      number of entries covered by extent header
     172 */
    140173uint16_t ext4_extent_header_get_entries_count(ext4_extent_header_t *header)
    141174{
     
    143176}
    144177
     178/** Set number of entries to extent header
     179 *
     180 * @param header        extent header to set value to
     181 * @param count         number of entries covered by extent header
     182 */
    145183void ext4_extent_header_set_entries_count(ext4_extent_header_t *header,
    146184                uint16_t count)
     
    149187}
    150188
     189/** Get maximum number of entries from extent header
     190 *
     191 * @param header        extent header to get value from
     192 * @return                      maximum number of entries covered by extent header
     193 */
    151194uint16_t ext4_extent_header_get_max_entries_count(ext4_extent_header_t *header)
    152195{
     
    154197}
    155198
     199/** Set maximum number of entries to extent header
     200 *
     201 * @param header        extent header to set value to
     202 * @param max_count maximum number of entries covered by extent header
     203 */
    156204void ext4_extent_header_set_max_entries_count(ext4_extent_header_t *header,
    157205                uint16_t max_count)
     
    160208}
    161209
     210/** Get depth of extent subtree.
     211 *
     212 * @param header        extent header to get value from
     213 * @return                      depth of extent subtree
     214 */
    162215uint16_t ext4_extent_header_get_depth(ext4_extent_header_t *header)
    163216{
     
    165218}
    166219
     220/** Set depth of extent subtree.
     221 *
     222 * @param header        extent header to set value to
     223 * @param depth         depth of extent subtree
     224 */
    167225void ext4_extent_header_set_depth(ext4_extent_header_t *header, uint16_t depth)
    168226{
     
    170228}
    171229
     230/** Get generation from extent header
     231 *
     232 * @param header        extent header to get value from
     233 * @return                      generation
     234 */
    172235uint32_t ext4_extent_header_get_generation(ext4_extent_header_t *header)
    173236{
     
    175238}
    176239
     240/** Set generation to extent header
     241 *
     242 * @param header                extent header to set value to
     243 * @param generation    generation
     244 */
    177245void ext4_extent_header_set_generation(ext4_extent_header_t *header,
    178246                uint32_t generation)
     
    181249}
    182250
    183 /**
    184  * Binary search in extent index node
     251/** Binary search in extent index node.
     252 *
     253 * @param header        extent header of index node
     254 * @param index         output value - found index will be set here
     255 * @param iblock        logical block number to find in index node
    185256 */
    186257static void ext4_extent_binsearch_idx(ext4_extent_header_t *header,
     
    191262        uint16_t entries_count = ext4_extent_header_get_entries_count(header);
    192263
     264        // Check trivial situation
    193265        if (entries_count == 1) {
    194266                *index = EXT4_EXTENT_FIRST_INDEX(header);
     
    196268        }
    197269
     270        // Initialize bounds
    198271        l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
    199272        r = l + entries_count - 1;
    200273
     274        // Do binary search
    201275        while (l <= r) {
    202276                m = l + (r - l) / 2;
     
    209283        }
    210284
     285        // Set output value
    211286        *index = l - 1;
    212287}
    213288
    214 /**
    215  * Binary search in extent leaf node
     289/** Binary search in extent leaf node.
     290 * @param header        extent header of leaf node
     291 * @param extent        output value - found extent will be set here,
     292 *                                      or NULL if node is empty
     293 * @param iblock        logical block number to find in leaf node
     294 *
    216295 */
    217296static void ext4_extent_binsearch(ext4_extent_header_t *header,
     
    224303        if (entries_count == 0) {
    225304                // this leaf is empty
    226 //              EXT4FS_DBG("EMPTY LEAF");
    227305                *extent = NULL;
    228306                return;
    229307        }
    230308
     309        // Check trivial situation
    231310        if (entries_count == 1) {
    232311                *extent = EXT4_EXTENT_FIRST(header);
     
    234313        }
    235314
     315        // Initialize bounds
    236316        l = EXT4_EXTENT_FIRST(header) + 1;
    237317        r = l + entries_count - 1;
    238318
     319        // Do binary search
    239320        while (l < r) {
    240321                m = l + (r - l) / 2;
     
    247328        }
    248329
     330        // Set output value
    249331        *extent = l - 1;
    250332}
    251333
    252 // Reading routine without saving blocks to path - for saving memory during finding block
    253 int ext4_extent_find_block(ext4_inode_ref_t *inode_ref, uint32_t iblock, uint32_t *fblock)
     334/** Find physical block in the extent tree by logical block number.
     335 *
     336 * There is no need to save path in the tree during this algorithm.
     337 *
     338 * @param inode_ref             i-node to load block from
     339 * @param iblock                logical block number to find
     340 * @param fblock                output value for physical block number
     341 * @return                              error code
     342 */
     343int ext4_extent_find_block(ext4_inode_ref_t *inode_ref,
     344                uint32_t iblock, uint32_t *fblock)
    254345{
    255346        int rc;
    256347
     348        // Compute bound defined by i-node size
    257349        uint64_t inode_size = ext4_inode_get_size(
    258350                        inode_ref->fs->superblock, inode_ref->inode);
     
    263355        uint32_t last_idx = (inode_size - 1) / block_size;
    264356
     357        // Check if requested iblock is not over size of i-node
    265358        if (iblock > last_idx) {
    266359                *fblock = 0;
     
    270363        block_t* block = NULL;
    271364
     365        // Walk through extent tree
    272366        ext4_extent_header_t *header = ext4_inode_get_extent_header(inode_ref->inode);
    273367        while (ext4_extent_header_get_depth(header) != 0) {
    274368
     369                // Search index in node
    275370                ext4_extent_index_t *index;
    276371                ext4_extent_binsearch_idx(header, &index, iblock);
    277372
     373                // Load child node and set values for the next iteration
    278374                uint64_t child = ext4_extent_index_get_leaf(index);
    279375
     
    290386        }
    291387
    292 
     388        // Search extent in the leaf block
    293389        ext4_extent_t* extent = NULL;
    294390        ext4_extent_binsearch(header, &extent, iblock);
    295391
     392        // Prevent empty leaf
    296393        if (extent == NULL) {
    297394                *fblock = 0;
    298395        } else {
     396
     397                // Compute requested physical block address
    299398                uint32_t phys_block;
    300399                phys_block = ext4_extent_get_start(extent) + iblock;
     
    304403        }
    305404
     405        // Cleanup
    306406        if (block != NULL) {
    307407                block_put(block);
     
    311411}
    312412
     413
     414/** Find extent for specified iblock.
     415 *
     416 * This function is used for finding block in the extent tree with
     417 * saving the path through the tree for possible future modifications.
     418 *
     419 * @param inode_ref             i-node to read extent tree from
     420 * @param iblock                iblock to find extent for
     421 * @param ret_path              output value for loaded path from extent tree
     422 * @return                              error code
     423 */
    313424static int ext4_extent_find_extent(ext4_inode_ref_t *inode_ref,
    314425                uint32_t iblock, ext4_extent_path_t **ret_path)
     
    329440        }
    330441
     442        // Initialize structure for algorithm start
    331443        tmp_path[0].block = inode_ref->block;
    332444        tmp_path[0].header = eh;
    333445
     446        // Walk through the extent tree
    334447        uint16_t pos = 0;
    335448        while (ext4_extent_header_get_depth(eh) != 0) {
    336449
     450                // Search index in index node by iblock
    337451                ext4_extent_binsearch_idx(tmp_path[pos].header, &tmp_path[pos].index, iblock);
    338452
     
    342456                assert(tmp_path[pos].index != NULL);
    343457
     458                // Load information for the next iteration
    344459                uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index);
    345460
     
    362477        tmp_path[pos].index = NULL;
    363478
    364     /* find extent */
     479    // Find extent in the leaf node
    365480        ext4_extent_binsearch(tmp_path[pos].header, &tmp_path[pos].extent, iblock);
    366481
     
    382497
    383498        return rc;
    384 
    385 }
    386 
    387 static int ext4_extent_release(ext4_inode_ref_t *inode_ref, ext4_extent_t* extent)
     499}
     500
     501/** Release extent and all data blocks covered by the extent.
     502 *
     503 * @param inode_ref             i-node to release extent and block from
     504 * @param extent                extent to release
     505 * @return                              error code
     506 */
     507static int ext4_extent_release(
     508                ext4_inode_ref_t *inode_ref, ext4_extent_t *extent)
    388509{
    389510        int rc;
    390511
     512        // Compute number of the first physical block to release
    391513        uint64_t start = ext4_extent_get_start(extent);
    392514        uint16_t block_count = ext4_extent_get_block_count(extent);
     
    394516        rc = ext4_balloc_free_blocks(inode_ref, start, block_count);
    395517        if (rc != EOK) {
    396                 EXT4FS_DBG("ERROR");
     518                EXT4FS_DBG("Error in releasing data blocks");
    397519                return rc;
    398520        }
     
    400522        return EOK;
    401523}
     524
     525// TODO comments
    402526
    403527// Recursive release
Note: See TracChangeset for help on using the changeset viewer.