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

Changeset ccac91e in mainline


Ignore:
Timestamp:
2012-02-25T16:25:14Z (10 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master
Children:
89a30bd
Parents:
ac92b85
Message:

splitting data block during adding dentry through index (not tested yet)

File:
1 edited

Legend:

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

    rac92b85 rccac91e  
    295295
    296296        if (dentry_len == 0) {
    297                 // TODO error
     297                // Error
    298298                return -1;
    299299        }
     
    455455typedef struct ext4_dx_sort_entry {
    456456        uint32_t hash;
     457        uint32_t rec_len;
    457458        ext4_directory_entry_ll_t *dentry;
    458459} ext4_dx_sort_entry_t;
     
    477478static int ext4_directory_dx_split_data(ext4_filesystem_t *fs,
    478479                ext4_inode_ref_t *inode_ref, ext4_hash_info_t *hinfo,
    479                 block_t *data_block, ext4_directory_dx_block_t *index_block)
     480                block_t *old_data_block, ext4_directory_dx_block_t *index_block, block_t **new_data_block)
    480481{
    481482        int rc;
     
    488489
    489490        // Copy data to buffer
    490         memcpy(entry_buffer, index_block->block->data, block_size);
     491        memcpy(entry_buffer, old_data_block->data, block_size);
    491492
    492493        ext4_directory_dx_countlimit_t *countlimit =
     
    499500        }
    500501
    501         ext4_directory_entry_ll_t *dentry = data_block->data;
     502        ext4_directory_entry_ll_t *dentry = old_data_block->data;
    502503
    503504        int idx = 0;
    504         while ((void *)dentry < data_block->data + block_size) {
     505        uint32_t real_size = 0;
     506        void *entry_buffer_ptr = entry_buffer;
     507        while ((void *)dentry < old_data_block->data + block_size) {
    505508                char *name = (char *)dentry->name;
    506509                uint8_t len = ext4_directory_entry_ll_get_name_length(fs->superblock, dentry);
    507510                uint32_t hash = ext4_hash_string(hinfo, len, name);
    508511
    509                 sort_array[idx].dentry = dentry;
     512                uint32_t rec_len = 8 + len;
     513
     514                if ((rec_len % 4) != 0) {
     515                        rec_len += 4 - (rec_len % 4);
     516                }
     517
     518                memcpy(entry_buffer_ptr, dentry, rec_len);
     519
     520                sort_array[idx].dentry = entry_buffer_ptr;
     521                sort_array[idx].rec_len = rec_len;
    510522                sort_array[idx].hash = hash;
     523
     524                entry_buffer_ptr += rec_len;
     525                real_size += rec_len;
    511526
    512527                idx++;
     
    515530
    516531        qsort(sort_array, entry_count, sizeof(ext4_dx_sort_entry_t), dx_entry_comparator, NULL);
    517 
    518         // TODO split to two groups (by size, NOT by count)
    519532
    520533        uint32_t new_fblock;
     
    526539        }
    527540
    528         // TODO load new_block
    529 
    530         // TODO write splitted entries to two blocks
     541        // Load new block
     542        block_t *new_data_block_tmp;
     543        rc = block_get(&new_data_block_tmp, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
     544        if (rc != EOK) {
     545                free(sort_array);
     546                free(entry_buffer);
     547                return rc;
     548        }
     549
     550        // Distribute entries to splitted blocks (by size)
     551
     552        uint32_t new_hash = 0;
     553        uint32_t current_size = 0;
     554        int mid = 0;
     555        for (int i = 0; i < idx; ++i) {
     556                if (current_size > real_size / 2) {
     557                        new_hash = sort_array[i].hash;
     558                        mid = i;
     559                        break;
     560                }
     561
     562                current_size += sort_array[i].rec_len;
     563        }
     564
     565        uint32_t offset = 0;
     566        void *ptr;
     567
     568        // First part - to the old block
     569        for (int i = 0; i < mid; ++i) {
     570                ptr = old_data_block->data + offset;
     571                memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
     572
     573                ext4_directory_entry_ll_t *tmp = ptr;
     574                if (i < (mid - 1)) {
     575                        ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);
     576                } else {
     577                        ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset);
     578                }
     579
     580                offset += sort_array[i].rec_len;
     581        }
     582
     583        // Second part - to the new block
     584        offset = 0;
     585        for (int i = mid; i < idx; ++i) {
     586                ptr = new_data_block_tmp->data + offset;
     587                memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
     588
     589                ext4_directory_entry_ll_t *tmp = ptr;
     590                if (i < (idx - 1)) {
     591                        ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);
     592                } else {
     593                        ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset);
     594                }
     595
     596                offset += sort_array[i].rec_len;
     597        }
     598
     599        old_data_block->dirty = true;
     600        new_data_block_tmp->dirty = true;
     601
     602        free(sort_array);
     603        free(entry_buffer);
    531604
    532605        // TODO add new entry to index block
     606        index_block->position++;
     607
     608        ext4_directory_dx_entry_set_block(index_block->position, new_fblock);
     609        ext4_directory_dx_entry_set_hash(index_block->position, new_hash);
     610
     611        index_block->block->dirty = true;
     612
     613        *new_data_block = new_data_block_tmp;
    533614
    534615        return EOK;
     
    581662
    582663
    583         block_t *target;
    584         rc = block_get(&target, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
     664        block_t *target_block;
     665        rc = block_get(&target_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
    585666        if (rc != EOK) {
    586667                return EXT4_ERR_BAD_DX_DIR;
     
    590671        uint16_t required_len = 8 + name_size + (4 - name_size % 4);
    591672
    592         ext4_directory_entry_ll_t *de = target->data;
    593         ext4_directory_entry_ll_t *stop = target->data + block_size;
     673        ext4_directory_entry_ll_t *de = target_block->data;
     674        ext4_directory_entry_ll_t *stop = target_block->data + block_size;
    594675
    595676        while (de < stop) {
     
    601682                        ext4_directory_write_entry(fs->superblock, de, de_rec_len,
    602683                                child, name, name_size);
    603                                 target->dirty = true;
    604                                 rc = block_put(target);
     684                                target_block->dirty = true;
     685                                rc = block_put(target_block);
    605686                                if (rc != EOK) {
    606687                                        return EXT4_ERR_BAD_DX_DIR;
     
    628709                                ext4_directory_write_entry(fs->superblock, new_entry,
    629710                                        free_space, child, name, name_size);
    630                                 target->dirty = true;
    631                                 rc = block_put(target);
     711                                target_block->dirty = true;
     712                                rc = block_put(target_block);
    632713                                if (rc != EOK) {
    633714                                        return EXT4_ERR_BAD_DX_DIR;
     
    687768        }
    688769
    689         rc = ext4_directory_dx_split_data(fs, parent, &hinfo, target, dx_block);
     770        block_t *new_block;
     771        rc = ext4_directory_dx_split_data(fs, parent, &hinfo, target_block, dx_block, &new_block);
    690772        if (rc != EOK) {
    691773                // TODO error
    692774        }
     775
     776        // TODO Where to save new entry
    693777
    694778
Note: See TracChangeset for help on using the changeset viewer.