Changeset e6f6260 in mainline


Ignore:
Timestamp:
2012-04-19T08:57:01Z (12 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
1d4262e
Parents:
db8fb43
Message:

next part of directory index comments

Location:
uspace
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/ext4/libext4_directory_index.c

    rdb8fb43 re6f6260  
    209209/**************************************************************************/
    210210
    211 /** TODO comment all function
    212  *
     211/** Initialize index structure of new directory.
     212 *
     213 * @param dir   pointer to directory i-node
     214 * @return              error code
    213215 */
    214216int ext4_directory_dx_init(ext4_inode_ref_t *dir)
    … …  
    216218        int rc;
    217219
     220        // Load block 0, where will be index root located
    218221        uint32_t fblock;
    219222        rc = ext4_filesystem_get_inode_data_block_index(dir, 0, &fblock);
    … …  
    228231        }
    229232
    230         EXT4FS_DBG("fblock = \%u", fblock);
    231 
     233        // Initialize pointers to data structures
    232234        ext4_directory_dx_root_t *root = block->data;
    233 
    234         ext4_directory_entry_ll_t *dot = (ext4_directory_entry_ll_t *)&root->dots[0];
    235         ext4_directory_entry_ll_t *dot_dot = (ext4_directory_entry_ll_t *)&root->dots[1];
    236 
    237 
    238         // TODO why the commented lines??
    239         EXT4FS_DBG("dot len = \%u, dotdot len = \%u", ext4_directory_entry_ll_get_entry_length(dot), ext4_directory_entry_ll_get_entry_length(dot_dot));
    240 
    241 //      uint32_t block_size = ext4_superblock_get_block_size(dir->fs->superblock);
    242 //      uint16_t len = block_size - sizeof(ext4_directory_dx_dot_entry_t);
    243 
    244 //      ext4_directory_entry_ll_set_entry_length(dot_dot, len);
    245 
    246235        ext4_directory_dx_root_info_t *info = &(root->info);
    247236
     237        // Initialize root info structure
    248238        uint8_t hash_version =
    249239                        ext4_superblock_get_default_hash_version(dir->fs->superblock);
    … …  
    253243        ext4_directory_dx_root_info_set_info_length(info, 8);
    254244
     245        // Set limit and current number of entries
    255246        ext4_directory_dx_countlimit_t *countlimit =
    256247                        (ext4_directory_dx_countlimit_t *)&root->entries;
    … …  
    263254        ext4_directory_dx_countlimit_set_limit(countlimit, root_limit);
    264255
     256        // Append new block, where will be new entries inserted in the future
    265257        uint32_t iblock;
    266258        rc = ext4_filesystem_append_inode_block(dir, &fblock, &iblock);
    … …  
    277269        }
    278270
     271        // Fill the whole block with empty entry
    279272        ext4_directory_entry_ll_t *block_entry = new_block->data;
    280273        ext4_directory_entry_ll_set_entry_length(block_entry, block_size);
    … …  
    288281        }
    289282
     283        // Connect new block to the only entry in index
    290284        ext4_directory_dx_entry_t *entry = root->entries;
    291285        ext4_directory_dx_entry_set_block(entry, iblock);
    … …  
    301295}
    302296
     297/** Initialize hash info structure necessary for index operations.
     298 *
     299 * @param hinfo                 pointer to hinfo to be initialized
     300 * @param root_block    root block (number 0) of index
     301 * @param sb                    pointer to superblock
     302 * @param name_len              length of name to be computed hash value from
     303 * @param name                  name to be computed hash value from
     304 * @return                              error code
     305 */
    303306static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block,
    304307                ext4_superblock_t *sb, size_t name_len, const char *name)
    … …  
    325328        }
    326329
     330        // Check if node limit is correct
    327331        uint32_t block_size = ext4_superblock_get_block_size(sb);
    328 
    329332        uint32_t entry_space = block_size;
    330333        entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t);
    … …  
    337340        }
    338341
     342    // Check hash version and modify if necessary
    339343        hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info);
    340344        if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA)
    … …  
    344348        }
    345349
     350        // Load hash seed from superblock
    346351        hinfo->seed = ext4_superblock_get_hash_seed(sb);
    347352
     353        // Compute hash value of name
    348354        if (name) {
    349355                ext4_hash_string(hinfo, name_len, name);
    … …  
    353359}
    354360
     361/** Walk through index tree and load leaf with corresponding hash value.
     362 *
     363 * @param hinfo                 initialized hash info structure
     364 * @param inode_ref     current i-node
     365 * @param root_block    root block (iblock 0), where is root node located
     366 * @param dx_block              pointer to leaf node in dx_blocks array
     367 * @param dx_blocks             array with the whole path from root to leaf
     368 * @return                              error code
     369 */
    355370static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo,
    356371                ext4_inode_ref_t *inode_ref, block_t *root_block,
    … …  
    369384        block_t *tmp_block = root_block;
    370385        ext4_directory_dx_entry_t *p, *q, *m, *at;
     386
     387        // Walk through the index tree
    371388        while (true) {
    372389
    … …  
    376393                }
    377394
     395
     396                // Do binary search in every node
    378397                p = entries + 1;
    379398                q = entries + count - 1;
    … …  
    390409                at = p - 1;
    391410
     411                // Write results
    392412                tmp_dx_block->block = tmp_block;
    393413                tmp_dx_block->entries = entries;
    394414                tmp_dx_block->position = at;
    395415
     416                // Is algorithm in the leaf?
    396417        if (indirect_level == 0) {
    397418                *dx_block = tmp_dx_block;
    … …  
    399420        }
    400421
     422        // Goto child node
    401423                uint32_t next_block = ext4_directory_dx_entry_get_block(at);
    402424
    … …  
    437459
    438460
     461/** Check if the the next block would be checked during entry search.
     462 *
     463 * @param inode_ref                     directory i-node
     464 * @param hash                          hash value to check
     465 * @param dx_block                      current block
     466 * @param dx_blocks                     aray with path from root to leaf node
     467 * @return                                      error code
     468 */
    439469static int ext4_directory_dx_next_block(ext4_inode_ref_t *inode_ref, uint32_t hash,
    440                 ext4_directory_dx_block_t *handle, ext4_directory_dx_block_t *handles)
     470                ext4_directory_dx_block_t *dx_block, ext4_directory_dx_block_t *dx_blocks)
    441471{
    442472        int rc;
    443473
    444 
    445474    uint32_t num_handles = 0;
    446     ext4_directory_dx_block_t *p = handle;
    447 
     475    ext4_directory_dx_block_t *p = dx_block;
     476
     477    // TODO comment
    448478    while (1) {
    449479
    … …  
    455485        }
    456486
    457         if (p == handles) {
     487        if (p == dx_blocks) {
    458488                return 0;
    459489        }
    … …  
    463493    }
    464494
     495    // TODO comment
    465496    uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position);
    466 
    467497    if ((hash & 1) == 0) {
    468498        if ((current_hash & ~1) != hash) {
    … …  
    471501    }
    472502
    473 
     503    // TODO comment
    474504    while (num_handles--) {
    475505
    … …  
    499529}
    500530
     531/** Try to find directory entry using directory index.
     532 *
     533 * @param result                output value - if entry will be found,
     534 *                      than will be passed through this parameter
     535 * @param inode_ref             directory i-node
     536 * @param name_len              length of name to be found
     537 * @param name                  name to be found
     538 * @return                              error code
     539 */
    501540int ext4_directory_dx_find_entry(ext4_directory_search_result_t *result,
    502541                ext4_inode_ref_t *inode_ref, size_t name_len, const char *name)
    … …  
    504543        int rc;
    505544
    506         // get direct block 0 (index root)
     545        // Load direct block 0 (index root)
    507546        uint32_t root_block_addr;
    508547        rc = ext4_filesystem_get_inode_data_block_index(inode_ref, 0, &root_block_addr);
    … …  
    519558        }
    520559
     560        // Initialize hash info (compute hash value)
    521561        ext4_hash_info_t hinfo;
    522562        rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_len, name);
    … …  
    526566        }
    527567
    528         // Hardcoded number 2 means maximum height of index tree !!!
     568        // Hardcoded number 2 means maximum height of index tree, specified in linux driver
    529569        ext4_directory_dx_block_t dx_blocks[2];
    530570        ext4_directory_dx_block_t *dx_block, *tmp;
    … …  
    535575        }
    536576
    537 
    538577        do {
    539 
     578                // Load leaf block
    540579                uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position);
    541580                uint32_t leaf_block_addr;
    … …  
    551590                }
    552591
     592                // Linear search inside block
    553593                ext4_directory_entry_ll_t *res_dentry;
    554594                rc = ext4_directory_find_in_block(leaf_block, fs->superblock, name_len, name, &res_dentry);
    … …  
    568608                }
    569609
     610                // check if the next block could be checked
    570611                rc = ext4_directory_dx_next_block(inode_ref, hinfo.hash, dx_block, &dx_blocks[0]);
    571612                if (rc < 0) {
    … …  
    575616        } while (rc == 1);
    576617
     618        // Entry not found
    577619        rc = ENOENT;
    578620
    579621cleanup:
    580622
     623        // The whole path must be released (preventing memory leak)
    581624        tmp = dx_blocks;
    582625        while (tmp <= dx_block) {
    … …  
    587630}
    588631
     632/** Compare function used to pass in quicksort implementation.
     633 *
     634 * It can compare two entries by hash value.
     635 *
     636 * @param arg1          first entry
     637 * @param arg2          second entry
     638 * @param dummy         unused parameter, can be NULL
     639 * @return                      classic compare result (0: equal, -1: arg1 < arg2, 1: arg1 > arg2)
     640 */
    589641static int ext4_directory_dx_entry_comparator(void *arg1, void *arg2, void *dummy)
    590642{
    … …  
    604656}
    605657
     658/** Insert new index entry to block.
     659 *
     660 * Note that space for new entry must be checked by caller.
     661 *
     662 * @param index_block           block where to insert new entry
     663 * @param hash                          hash value covered by child node
     664 * @param iblock                        logical number of child block
     665 *
     666 */
    606667static void ext4_directory_dx_insert_entry(
    607668                ext4_directory_dx_block_t *index_block, uint32_t hash, uint32_t iblock)
    … …  
    627688}
    628689
    629 static int ext4_directory_dx_split_data(ext4_filesystem_t *fs,
    630                 ext4_inode_ref_t *inode_ref, ext4_hash_info_t *hinfo,
    631                 block_t *old_data_block, ext4_directory_dx_block_t *index_block, block_t **new_data_block)
     690/** Split directory entries to two parts preventing node overflow.
     691 *
     692 * @param inode_ref                     directory i-node
     693 * @param hinfo                         hash info
     694 * @param old_data_block        block with data to be split
     695 * @param index_block           block where index entries are located
     696 * @param new_data_block        output value for newly allocated data block
     697 */
     698static int ext4_directory_dx_split_data(ext4_inode_ref_t *inode_ref,
     699                ext4_hash_info_t *hinfo, block_t *old_data_block,
     700                ext4_directory_dx_block_t *index_block, block_t **new_data_block)
    632701{
    633702        int rc = EOK;
    634703
    635704        // Allocate buffer for directory entries
    636         uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
     705        uint32_t block_size =
     706                        ext4_superblock_get_block_size(inode_ref->fs->superblock);
    637707        void *entry_buffer = malloc(block_size);
    638708        if (entry_buffer == NULL) {
    … …  
    665735                if (ext4_directory_entry_ll_get_inode(dentry) != 0) {
    666736
    667                         uint8_t len = ext4_directory_entry_ll_get_name_length(fs->superblock, dentry);
     737                        uint8_t len = ext4_directory_entry_ll_get_name_length(
     738                                        inode_ref->fs->superblock, dentry);
    668739                        ext4_hash_string(&tmp_hinfo, len, (char *)dentry->name);
    669740
    … …  
    688759        }
    689760
     761        // Sort all entries
    690762        qsort(sort_array, idx, sizeof(ext4_dx_sort_entry_t),
    691763                        ext4_directory_dx_entry_comparator, NULL);
    692764
     765        // Allocate new block for store the second part of entries
    693766        uint32_t new_fblock;
    694767        uint32_t new_iblock;
    … …  
    702775        // Load new block
    703776        block_t *new_data_block_tmp;
    704         rc = block_get(&new_data_block_tmp, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
     777        rc = block_get(&new_data_block_tmp, inode_ref->fs->device,
     778                        new_fblock, BLOCK_FLAGS_NOREAD);
    705779        if (rc != EOK) {
    706780                free(sort_array);
    … …  
    709783        }
    710784
    711         // Distribute entries to splitted blocks (by size)
     785        // Distribute entries to two blocks (by size)
     786        // Compute the half
    712787        uint32_t new_hash = 0;
    713788        uint32_t current_size = 0;
    … …  
    723798        }
    724799
     800        // Check hash collision
    725801        uint32_t continued = 0;
    726802        if (new_hash == sort_array[mid-1].hash) {
    … …  
    762838        }
    763839
     840        // Do some steps to finish operation
    764841        old_data_block->dirty = true;
    765842        new_data_block_tmp->dirty = true;
    … …  
    775852}
    776853
    777 
     854/** TODO start comments from here
     855 *
     856 */
    778857static int ext4_directory_dx_split_index(ext4_filesystem_t *fs,
    779858                ext4_inode_ref_t *inode_ref, ext4_directory_dx_block_t *dx_blocks,
    … …  
    9801059
    9811060        block_t *new_block = NULL;
    982         rc = ext4_directory_dx_split_data(fs, parent, &hinfo, target_block, dx_block, &new_block);
     1061        rc = ext4_directory_dx_split_data(parent, &hinfo, target_block, dx_block, &new_block);
    9831062        if (rc != EOK) {
    9841063                rc2 = rc;

  • uspace/srv/fs/ext4fs/ext4fs_ops.c

    rdb8fb43 re6f6260  
    619619                }
    620620
    621                 // Initialize directory index if necessary
     621                // Initialize directory index if supported
    622622                if (ext4_superblock_has_feature_compatible(
    623623                                fs->superblock, EXT4_FEATURE_COMPAT_DIR_INDEX)) {
Note: See TracChangeset for help on using the changeset viewer.