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

Changeset 2f2feadb in mainline


Ignore:
Timestamp:
2012-03-06T09:54:08Z (10 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master
Children:
a872fc09
Parents:
60b8b99
Message:

refactored code of index node splitting

File:
1 edited

Legend:

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

    r60b8b99 r2f2feadb  
    606606
    607607
     608static int ext4_directory_dx_split_index(ext4_filesystem_t *fs,
     609                ext4_inode_ref_t *inode_ref, ext4_directory_dx_block_t *dx_blocks,
     610                ext4_directory_dx_block_t *dx_block)
     611{
     612        int rc;
     613
     614        ext4_directory_dx_entry_t *entries;
     615        if (dx_block == dx_blocks) {
     616                entries = ((ext4_directory_dx_root_t *) dx_block->block->data)->entries;
     617        } else {
     618                entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries;
     619        }
     620
     621        ext4_directory_dx_countlimit_t *countlimit =
     622                        (ext4_directory_dx_countlimit_t *)entries;
     623        uint16_t leaf_limit = ext4_directory_dx_countlimit_get_limit(countlimit);
     624        uint16_t leaf_count = ext4_directory_dx_countlimit_get_count(countlimit);
     625
     626        // Check if is necessary to split index block
     627        if (leaf_limit == leaf_count) {
     628                EXT4FS_DBG("need to split index block !!!");
     629
     630                unsigned int levels = dx_block - dx_blocks;
     631
     632                ext4_directory_dx_entry_t *root_entries =
     633                                        ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->entries;
     634
     635                ext4_directory_dx_countlimit_t *root_countlimit =
     636                                (ext4_directory_dx_countlimit_t *)root_entries;
     637                uint16_t root_limit =
     638                                ext4_directory_dx_countlimit_get_limit(root_countlimit);
     639                uint16_t root_count =
     640                                ext4_directory_dx_countlimit_get_count(root_countlimit);
     641
     642                if ((levels > 0) && (root_limit == root_count)) {
     643                        EXT4FS_DBG("Directory index is full");
     644                        return ENOSPC;
     645                }
     646
     647                uint32_t new_fblock;
     648                uint32_t new_iblock;
     649                rc =  ext4_directory_append_block(fs, inode_ref, &new_fblock, &new_iblock);
     650                if (rc != EOK) {
     651                        return rc;
     652                }
     653
     654                // New block allocated
     655                block_t * new_block;
     656                rc = block_get(&new_block, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
     657                if (rc != EOK) {
     658                        return rc;
     659                }
     660
     661                ext4_directory_dx_node_t *new_node = new_block->data;
     662                ext4_directory_dx_entry_t *new_entries = new_node->entries;
     663
     664                uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
     665
     666                if (levels > 0) {
     667                        EXT4FS_DBG("split index leaf node");
     668                        uint32_t count_left = leaf_count / 2;
     669                        uint32_t count_right = leaf_count - count_left;
     670                        uint32_t hash_right =
     671                                        ext4_directory_dx_entry_get_hash(entries + count_left);
     672
     673                        memcpy((void *) new_entries, (void *) (entries + count_left),
     674                                        count_right * sizeof(ext4_directory_dx_entry_t));
     675
     676                        ext4_directory_dx_countlimit_t *left_countlimit =
     677                                        (ext4_directory_dx_countlimit_t *)entries;
     678                        ext4_directory_dx_countlimit_t *right_countlimit =
     679                                        (ext4_directory_dx_countlimit_t *)new_entries;
     680
     681                        ext4_directory_dx_countlimit_set_count(left_countlimit, count_left);
     682                        ext4_directory_dx_countlimit_set_count(right_countlimit, count_right);
     683
     684                        uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t);
     685                        uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t);
     686                        ext4_directory_dx_countlimit_set_limit(right_countlimit, node_limit);
     687
     688                        // Which index block is target for new entry
     689                        uint32_t position_index = (dx_block->position - dx_block->entries);
     690                        if (position_index >= count_left) {
     691
     692                                dx_block->block->dirty = true;
     693
     694                                block_t *block_tmp = dx_block->block;
     695                                dx_block->block = new_block;
     696                                dx_block->position = new_entries + position_index - count_left;
     697                                dx_block->entries = new_entries;
     698
     699                                new_block = block_tmp;
     700
     701                        }
     702
     703                        ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock);
     704
     705                        return block_put(new_block);
     706
     707                } else {
     708                        EXT4FS_DBG("create second level");
     709
     710                        memcpy((void *) new_entries, (void *) entries,
     711                                        leaf_count * sizeof(ext4_directory_dx_entry_t));
     712
     713                        ext4_directory_dx_countlimit_t *new_countlimit =
     714                                        (ext4_directory_dx_countlimit_t *)new_entries;
     715
     716                        uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t);
     717                        uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t);
     718                        ext4_directory_dx_countlimit_set_limit(new_countlimit, node_limit);
     719
     720                        // Set values in root node
     721                        ext4_directory_dx_countlimit_t *new_root_countlimit =
     722                                        (ext4_directory_dx_countlimit_t *)entries;
     723
     724                        ext4_directory_dx_countlimit_set_count(new_root_countlimit, 1);
     725                        ext4_directory_dx_entry_set_block(entries, new_iblock);
     726
     727                        ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->info.indirect_levels = 1;
     728
     729                        /* Add new access path frame */
     730                        dx_block = dx_blocks + 1;
     731                        dx_block->position = dx_block->position - entries + new_entries;
     732                        dx_block->entries = new_entries;
     733                        dx_block->block = new_block;
     734                }
     735
     736        }
     737
     738        return EOK;
     739}
     740
    608741int ext4_directory_dx_add_entry(ext4_filesystem_t *fs,
    609742                ext4_inode_ref_t *parent, ext4_inode_ref_t *child, const char *name)
     
    658791        }
    659792
     793
    660794        rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len);
    661795        if (rc == EOK) {
     
    665799    EXT4FS_DBG("no free space found");
    666800
    667     uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
    668 
    669         ext4_directory_dx_entry_t *entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries;
    670         uint16_t leaf_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
    671         uint16_t leaf_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
    672 
    673         ext4_directory_dx_entry_t *root_entries = ((ext4_directory_dx_node_t *) dx_blocks[0].block->data)->entries;
    674 
    675         if (leaf_limit == leaf_count) {
    676                 EXT4FS_DBG("need to split index block !!!");
    677 
    678                 unsigned int levels = dx_block - dx_blocks;
    679 
    680                 uint16_t root_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)root_entries);
    681                 uint16_t root_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)root_entries);
    682 
    683                 if ((levels > 0) && (root_limit == root_count)) {
    684                         EXT4FS_DBG("Directory index is full");
    685                         rc = ENOSPC;
    686                         goto release_target_index;
    687                 }
    688 
    689                 uint32_t new_fblock;
    690                 uint32_t new_iblock;
    691                 rc =  ext4_directory_append_block(fs, parent, &new_fblock, &new_iblock);
    692                 if (rc != EOK) {
    693                         goto release_target_index;
    694                 }
    695 
    696                 // New block allocated
    697                 block_t * new_block;
    698                 rc = block_get(&new_block, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
    699                 if (rc != EOK) {
    700                         goto release_target_index;
    701                 }
    702 
    703                 // Initialize block
    704                 memset(new_block->data, 0, block_size);
    705 
    706                 ext4_directory_dx_node_t *new_node = new_block->data;
    707                 ext4_directory_dx_entry_t *new_entries = new_node->entries;
    708 
    709                 if (levels > 0) {
    710                         EXT4FS_DBG("split index");
    711                         uint32_t count_left = leaf_count / 2;
    712                         uint32_t count_right = leaf_count - count_left;
    713                         uint32_t hash_right = ext4_directory_dx_entry_get_hash(entries);
    714 
    715                         memcpy((void *) new_entries, (void *) (entries + count_left),
    716                                         count_right * sizeof(ext4_directory_dx_entry_t));
    717 
    718                         ext4_directory_dx_countlimit_t *left_countlimit = (ext4_directory_dx_countlimit_t *)entries;
    719                         ext4_directory_dx_countlimit_t *right_countlimit = (ext4_directory_dx_countlimit_t *)new_entries;
    720 
    721                         ext4_directory_dx_countlimit_set_count(left_countlimit, count_left);
    722                         ext4_directory_dx_countlimit_set_count(right_countlimit, count_right);
    723 
    724                 uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t);
    725                 uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t);
    726                 ext4_directory_dx_countlimit_set_limit(right_countlimit, node_limit);
    727 
    728                 // Which index block is target for new entry
    729                 uint32_t position_index = (dx_block->position - dx_block->entries);
    730                 if (position_index >= count_left) {
    731                         dx_block->position = new_entries + position_index - count_left;
    732                         dx_block->entries = new_entries;
    733                         entries = dx_block->entries;
    734 
    735                         dx_block->block->dirty = true;
    736                         block_put(dx_block->block);
    737                         dx_block->block = new_block;
    738                 }
    739 
    740                 ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock);
    741 
    742 
    743                 } else {
    744                         EXT4FS_DBG("create second level");
    745 
    746                         memcpy((void *) new_entries, (void *) entries,
    747                                         leaf_count * sizeof(ext4_directory_dx_entry_t));
    748 
    749                         ext4_directory_dx_countlimit_t *new_countlimit =
    750                                         (ext4_directory_dx_countlimit_t *)new_entries;
    751 
    752                 uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t);
    753                 uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t);
    754                 ext4_directory_dx_countlimit_set_limit(new_countlimit, node_limit);
    755 
    756             // Set values in root node
    757                 ext4_directory_dx_countlimit_t *new_root_countlimit =
    758                                 (ext4_directory_dx_countlimit_t *)entries;
    759 
    760                 ext4_directory_dx_countlimit_set_limit(new_root_countlimit, 1);
    761                 ext4_directory_dx_entry_set_block(entries, new_iblock);
    762 
    763                 ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->info.indirect_levels = 1;
    764 
    765             /* Add new access path frame */
    766                 dx_block = dx_blocks + 1;
    767                 dx_block->position = dx_block->position - entries + new_entries;
    768                 dx_block->entries = new_entries;
    769                 entries = dx_block->entries;
    770             dx_block->block = new_block;
    771                 }
     801        rc = ext4_directory_dx_split_index(fs, parent, dx_blocks, dx_block);
     802        if (rc != EOK) {
     803                goto release_target_index;
    772804        }
    773805
Note: See TracChangeset for help on using the changeset viewer.