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

Changeset c0964cd7 in mainline


Ignore:
Timestamp:
2012-02-29T17:56:12Z (10 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master
Children:
6f731f0a
Parents:
e2ec667e
Message:

code for splitting index block if tree is not trivial (one block)

Location:
uspace/lib/ext4
Files:
2 edited

Legend:

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

    re2ec667e rc0964cd7  
    476476}
    477477
     478static void ext4_directory_dx_insert_entry(
     479                ext4_directory_dx_block_t *index_block, uint32_t hash, uint32_t iblock)
     480{
     481        ext4_directory_dx_entry_t *old_index_entry = index_block->position;
     482        ext4_directory_dx_entry_t *new_index_entry = old_index_entry + 1;
     483
     484        ext4_directory_dx_countlimit_t *countlimit =
     485                        (ext4_directory_dx_countlimit_t *)index_block->entries;
     486        uint32_t count = ext4_directory_dx_countlimit_get_count(countlimit);
     487
     488        ext4_directory_dx_entry_t *start_index = index_block->entries;
     489        size_t bytes = (void *)(start_index + count) - (void *)(new_index_entry);
     490
     491        memmove(new_index_entry + 1, new_index_entry, bytes);
     492
     493        ext4_directory_dx_entry_set_block(new_index_entry, iblock);
     494        ext4_directory_dx_entry_set_hash(new_index_entry, hash);
     495
     496        ext4_directory_dx_countlimit_set_count(countlimit, count + 1);
     497
     498        index_block->block->dirty = true;
     499}
     500
    478501static int ext4_directory_dx_split_data(ext4_filesystem_t *fs,
    479502                ext4_inode_ref_t *inode_ref, ext4_hash_info_t *hinfo,
     
    620643        free(entry_buffer);
    621644
    622         ext4_directory_dx_entry_t *old_index_entry = index_block->position;
    623         ext4_directory_dx_entry_t *new_index_entry = old_index_entry + 1;
    624 
    625         ext4_directory_dx_countlimit_t *countlimit =
    626                         (ext4_directory_dx_countlimit_t *)index_block->entries;
    627         uint32_t count = ext4_directory_dx_countlimit_get_count(countlimit);
    628 
    629         ext4_directory_dx_entry_t *start_index = index_block->entries;
    630         size_t bytes = (void *)(start_index + count) - (void *)(new_index_entry);
    631 
    632         memmove(new_index_entry + 1, new_index_entry, bytes);
    633 
    634         ext4_directory_dx_entry_set_block(new_index_entry, new_iblock);
    635         ext4_directory_dx_entry_set_hash(new_index_entry, new_hash + continued);
    636 
    637         ext4_directory_dx_countlimit_set_count(countlimit, count + 1);
    638 
    639         index_block->block->dirty = true;
     645        ext4_directory_dx_insert_entry(index_block, new_hash + continued, new_iblock);
    640646
    641647        *new_data_block = new_data_block_tmp;
     
    759765        uint16_t leaf_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
    760766
    761 //      ext4_directory_dx_entry_t *root_entries = ((ext4_directory_dx_node_t *) dx_blocks[0].block->data)->entries;
     767        ext4_directory_dx_entry_t *root_entries = ((ext4_directory_dx_node_t *) dx_blocks[0].block->data)->entries;
    762768
    763769        if (leaf_limit == leaf_count) {
    764770                EXT4FS_DBG("need to split index block !!!");
    765771
    766 //              unsigned int levels = dx_block - dx_blocks;
    767 //
    768 //              uint16_t root_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)root_entries);
    769 //              uint16_t root_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)root_entries);
    770 //
    771 //              if ((levels > 0) && (root_limit == root_count)) {
    772 //                      EXT4FS_DBG("Directory index is full");
    773 //
    774 //                      // ENOSPC - cleanup !!!
    775 //                      return ENOSPC;
    776 //              }
    777 //
    778 //              uint32_t fblock;
    779 //              rc =  ext4_directory_append_block(fs, parent, &fblock);
    780 //              if (rc != EOK) {
    781 //                      // TODO error
    782 //              }
    783 //
    784 //              // New block allocated
    785 //              block_t * new_block;
    786 //              rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD);
    787 //              if (rc != EOK) {
    788 //                      // TODO error
    789 //              }
    790 //
    791 //              memset(new_block->data, 0, block_size);
    792 //
    793 //              if (levels > 0) {
    794 //                      EXT4FS_DBG("split index");
    795 //              } else {
    796 //                      EXT4FS_DBG("create second level");
    797 //              }
     772                unsigned int levels = dx_block - dx_blocks;
     773
     774                uint16_t root_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)root_entries);
     775                uint16_t root_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)root_entries);
     776
     777                if ((levels > 0) && (root_limit == root_count)) {
     778                        EXT4FS_DBG("Directory index is full");
     779
     780                        // ENOSPC - cleanup !!!
     781                        return ENOSPC;
     782                }
     783
     784                uint32_t new_fblock;
     785                uint32_t new_iblock;
     786                rc =  ext4_directory_append_block(fs, parent, &new_fblock, &new_iblock);
     787                if (rc != EOK) {
     788                        // TODO error
     789                }
     790
     791                // New block allocated
     792                block_t * new_block;
     793                rc = block_get(&new_block, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
     794                if (rc != EOK) {
     795                        // TODO error
     796                }
     797
     798                // Initialize block
     799                memset(new_block->data, 0, block_size);
     800
     801                if (levels > 0) {
     802                        EXT4FS_DBG("split index");
     803                        uint32_t count_left = leaf_count / 2;
     804                        uint32_t count_right = leaf_count - count_left;
     805                        uint32_t hash_right = ext4_directory_dx_entry_get_hash(entries);
     806
     807                        ext4_directory_dx_node_t *new_node = new_block->data;
     808                        ext4_directory_dx_entry_t *new_entries = new_node->entries;
     809
     810                        memcpy((void *) new_entries, (void *) (entries + count_left),
     811                                        count_right * sizeof(ext4_directory_dx_entry_t));
     812
     813                        ext4_directory_dx_countlimit_t *left_countlimit = (ext4_directory_dx_countlimit_t *)entries;
     814                        ext4_directory_dx_countlimit_t *right_countlimit = (ext4_directory_dx_countlimit_t *)new_entries;
     815
     816                        ext4_directory_dx_countlimit_set_count(left_countlimit, count_left);
     817                        ext4_directory_dx_countlimit_set_count(right_countlimit, count_right);
     818
     819                uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t);
     820                uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t);
     821
     822                ext4_directory_dx_countlimit_set_limit(right_countlimit, node_limit);
     823
     824                // Which index block is target for new entry
     825                uint32_t position_index = (dx_block->position - dx_block->entries);
     826                if (position_index >= count_left) {
     827                        dx_block->position = new_entries + position_index - count_left;
     828                        dx_block->entries = new_entries;
     829                        entries = dx_block->entries;
     830
     831                        dx_block->block->dirty = true;
     832                        block_put(dx_block->block);
     833                        dx_block->block = new_block;
     834                }
     835
     836                ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock);
     837
     838
     839                } else {
     840                        EXT4FS_DBG("create second level");
     841                }
    798842        }
    799843
  • uspace/lib/ext4/libext4_directory_index.h

    re2ec667e rc0964cd7  
    6868} ext4_directory_dx_root_t;
    6969
     70typedef struct ext4_fake_directory_entry {
     71        uint32_t inode;
     72        uint16_t entry_length;
     73        uint8_t name_length;
     74        uint8_t inode_type;
     75} ext4_fake_directory_entry_t;
     76
    7077typedef struct ext4_directory_dx_node {
    71         struct fake_directory_entry {
    72                 uint32_t inode;
    73                 uint16_t entry_length;
    74             uint8_t name_length;
    75             uint8_t inode_type;
    76         } fake;
     78        ext4_fake_directory_entry_t fake;
    7779        ext4_directory_dx_entry_t entries[0];
    7880} ext4_directory_dx_node_t;
Note: See TracChangeset for help on using the changeset viewer.