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

Changeset dfac604 in mainline


Ignore:
Timestamp:
2012-04-20T08:43:47Z (10 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master
Children:
bae2a79e
Parents:
1d4262e
Message:

completed comments for directory index

File:
1 edited

Legend:

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

    r1d4262e rdfac604  
    475475    ext4_directory_dx_block_t *p = dx_block;
    476476
    477     // TODO comment
     477    // Try to find data block with next bunch of entries
    478478    while (1) {
    479479
    480480        p->position++;
    481         uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries);
     481        uint16_t count = ext4_directory_dx_countlimit_get_count(
     482                        (ext4_directory_dx_countlimit_t *)p->entries);
    482483
    483484        if (p->position < p->entries + count) {
     
    493494    }
    494495
    495     // TODO comment
     496    // Check hash collision (if not occured - no next block cannot be used)
    496497    uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position);
    497498    if ((hash & 1) == 0) {
     
    501502    }
    502503
    503     // TODO comment
     504    // Fill new path
    504505    while (num_handles--) {
    505506
     
    519520        p++;
    520521
     522        // Don't forget to put old block (prevent memory leak)
    521523        block_put(p->block);
     524
    522525        p->block = block;
    523526        p->entries = ((ext4_directory_dx_node_t *) block->data)->entries;
     
    852855}
    853856
    854 /** TODO start comments from here
    855  *
    856  */
    857 static int ext4_directory_dx_split_index(ext4_filesystem_t *fs,
    858                 ext4_inode_ref_t *inode_ref, ext4_directory_dx_block_t *dx_blocks,
    859                 ext4_directory_dx_block_t *dx_block)
     857/** Split index node and maybe some parent nodes in the tree hierarchy.
     858 *
     859 * @param inode_ref             directory i-node
     860 * @param dx_blocks             array with path from root to leaf node
     861 * @param dx_block              leaf block to be split if needed
     862 * @return                              error code
     863 */
     864static int ext4_directory_dx_split_index(ext4_inode_ref_t *inode_ref,
     865                ext4_directory_dx_block_t *dx_blocks, ext4_directory_dx_block_t *dx_block)
    860866{
    861867        int rc;
     
    875881        // Check if is necessary to split index block
    876882        if (leaf_limit == leaf_count) {
    877                 EXT4FS_DBG("need to split index block !!!");
    878883
    879884                unsigned int levels = dx_block - dx_blocks;
     
    889894                                ext4_directory_dx_countlimit_get_count(root_countlimit);
    890895
     896                // Linux limitation
    891897                if ((levels > 0) && (root_limit == root_count)) {
    892898                        EXT4FS_DBG("Directory index is full");
     
    894900                }
    895901
     902                // Add new block to directory
    896903                uint32_t new_fblock;
    897904                uint32_t new_iblock;
     
    902909                }
    903910
    904                 // New block allocated
     911                // load new block
    905912                block_t * new_block;
    906                 rc = block_get(&new_block, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
     913                rc = block_get(&new_block, inode_ref->fs->device,
     914                                new_fblock, BLOCK_FLAGS_NOREAD);
    907915                if (rc != EOK) {
    908916                        return rc;
     
    912920                ext4_directory_dx_entry_t *new_entries = new_node->entries;
    913921
    914                 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
    915 
     922                uint32_t block_size = ext4_superblock_get_block_size(
     923                                inode_ref->fs->superblock);
     924
     925                // Split leaf node
    916926                if (levels > 0) {
    917                         EXT4FS_DBG("split index leaf node");
     927
    918928                        uint32_t count_left = leaf_count / 2;
    919929                        uint32_t count_right = leaf_count - count_left;
     
    921931                                        ext4_directory_dx_entry_get_hash(entries + count_left);
    922932
     933                        // Copy data to new node
    923934                        memcpy((void *) new_entries, (void *) (entries + count_left),
    924935                                        count_right * sizeof(ext4_directory_dx_entry_t));
    925936
     937                        // Initialize new node
    926938                        ext4_directory_dx_countlimit_t *left_countlimit =
    927939                                        (ext4_directory_dx_countlimit_t *)entries;
     
    951963                        }
    952964
     965                        // Finally insert new entry
    953966                        ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock);
    954967
     
    956969
    957970                } else {
    958                         EXT4FS_DBG("create second level");
    959 
     971
     972                        // Create second level index
     973
     974                        // Copy data from root to child block
    960975                        memcpy((void *) new_entries, (void *) entries,
    961976                                        leaf_count * sizeof(ext4_directory_dx_entry_t));
     
    977992                        ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->info.indirect_levels = 1;
    978993
    979                         /* Add new access path frame */
     994                        // Add new entry to the path
    980995                        dx_block = dx_blocks + 1;
    981996                        dx_block->position = dx_block->position - entries + new_entries;
     
    9891004}
    9901005
     1006/** Add new entry to indexed directory
     1007 *
     1008 * @param parent        directory i-node
     1009 * @param child         i-node to be referenced from directory entry
     1010 * @param name          name of new directory entry
     1011 * @return                      error code
     1012 */
    9911013int ext4_directory_dx_add_entry(ext4_inode_ref_t *parent,
    9921014                ext4_inode_ref_t *child, const char *name)
     
    10101032        }
    10111033
     1034        // Initialize hinfo structure (mainly compute hash)
    10121035        uint32_t name_len = strlen(name);
    10131036        ext4_hash_info_t hinfo;
     
    10191042        }
    10201043
    1021         // Hardcoded number 2 means maximum height of index tree !!!
     1044        // Hardcoded number 2 means maximum height of index tree defined in linux
    10221045        ext4_directory_dx_block_t dx_blocks[2];
    10231046        ext4_directory_dx_block_t *dx_block, *dx_it;
     
    10451068        }
    10461069
    1047 
     1070        // Check if insert operation passed
    10481071        rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len);
    10491072        if (rc == EOK) {
     
    10511074        }
    10521075
    1053     EXT4FS_DBG("no free space found");
    1054 
    1055         rc = ext4_directory_dx_split_index(fs, parent, dx_blocks, dx_block);
     1076        // Check if there is needed to split index node
     1077        // (and recursively also parent nodes)
     1078        rc = ext4_directory_dx_split_index(parent, dx_blocks, dx_block);
    10561079        if (rc != EOK) {
    10571080                goto release_target_index;
    10581081        }
    10591082
     1083        // Split entries to two blocks (includes sorting by hash value)
    10601084        block_t *new_block = NULL;
    10611085        rc = ext4_directory_dx_split_data(parent, &hinfo, target_block, dx_block, &new_block);
     
    10731097        }
    10741098
    1075 
    1076 
    1077 
     1099        // Cleanup
    10781100        rc = block_put(new_block);
    10791101        if (rc != EOK) {
     
    10811103                return rc;
    10821104        }
     1105
     1106        // Cleanup operations
    10831107
    10841108release_target_index:
Note: See TracChangeset for help on using the changeset viewer.