Changeset ccac91e in mainline

Timestamp:

2012-02-25T16:25:14Z (12 years ago)

Author:

Frantisek Princ <frantisek.princ@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

89a30bd

Parents:

ac92b85

Message:

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

File:

• uspace/lib/ext4/libext4_directory_index.c (modified) (12 diffs)

uspace/lib/ext4/libext4_directory_index.c

@@ -295 +295 @@
 
         if (dentry_len == 0) {
-                // TODO error
+                // Error
                 return -1;
         }
@@ -455 +455 @@
 typedef struct ext4_dx_sort_entry {
         uint32_t hash;
+        uint32_t rec_len;
         ext4_directory_entry_ll_t *dentry;
 } ext4_dx_sort_entry_t;
@@ -477 +478 @@
 static int ext4_directory_dx_split_data(ext4_filesystem_t *fs,
                 ext4_inode_ref_t *inode_ref, ext4_hash_info_t *hinfo,
-                block_t *data_block, ext4_directory_dx_block_t *index_block)
+                block_t *old_data_block, ext4_directory_dx_block_t *index_block, block_t **new_data_block)
 {
         int rc;
@@ -488 +489 @@
 
         // Copy data to buffer
-        memcpy(entry_buffer, index_block->block->data, block_size);
+        memcpy(entry_buffer, old_data_block->data, block_size);
 
         ext4_directory_dx_countlimit_t *countlimit =
@@ -499 +500 @@
         }
 
-        ext4_directory_entry_ll_t *dentry = data_block->data;
+        ext4_directory_entry_ll_t *dentry = old_data_block->data;
 
         int idx = 0;
-        while ((void *)dentry < data_block->data + block_size) {
+        uint32_t real_size = 0;
+        void *entry_buffer_ptr = entry_buffer;
+        while ((void *)dentry < old_data_block->data + block_size) {
                 char *name = (char *)dentry->name;
                 uint8_t len = ext4_directory_entry_ll_get_name_length(fs->superblock, dentry);
                 uint32_t hash = ext4_hash_string(hinfo, len, name);
 
-                sort_array[idx].dentry = dentry;
+                uint32_t rec_len = 8 + len;
+
+                if ((rec_len % 4) != 0) {
+                        rec_len += 4 - (rec_len % 4);
+                }
+
+                memcpy(entry_buffer_ptr, dentry, rec_len);
+
+                sort_array[idx].dentry = entry_buffer_ptr;
+                sort_array[idx].rec_len = rec_len;
                 sort_array[idx].hash = hash;
+
+                entry_buffer_ptr += rec_len;
+                real_size += rec_len;
 
                 idx++;
@@ -515 +530 @@
 
         qsort(sort_array, entry_count, sizeof(ext4_dx_sort_entry_t), dx_entry_comparator, NULL);
-
-        // TODO split to two groups (by size, NOT by count)
 
         uint32_t new_fblock;
@@ -526 +539 @@
         }
 
-        // TODO load new_block
-
-        // TODO write splitted entries to two blocks
+        // Load new block
+        block_t *new_data_block_tmp;
+        rc = block_get(&new_data_block_tmp, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
+        if (rc != EOK) {
+                free(sort_array);
+                free(entry_buffer);
+                return rc;
+        }
+
+        // Distribute entries to splitted blocks (by size)
+
+        uint32_t new_hash = 0;
+        uint32_t current_size = 0;
+        int mid = 0;
+        for (int i = 0; i < idx; ++i) {
+                if (current_size > real_size / 2) {
+                        new_hash = sort_array[i].hash;
+                        mid = i;
+                        break;
+                }
+
+                current_size += sort_array[i].rec_len;
+        }
+
+        uint32_t offset = 0;
+        void *ptr;
+
+        // First part - to the old block
+        for (int i = 0; i < mid; ++i) {
+                ptr = old_data_block->data + offset;
+                memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
+
+                ext4_directory_entry_ll_t *tmp = ptr;
+                if (i < (mid - 1)) {
+                        ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);
+                } else {
+                        ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset);
+                }
+
+                offset += sort_array[i].rec_len;
+        }
+
+        // Second part - to the new block
+        offset = 0;
+        for (int i = mid; i < idx; ++i) {
+                ptr = new_data_block_tmp->data + offset;
+                memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
+
+                ext4_directory_entry_ll_t *tmp = ptr;
+                if (i < (idx - 1)) {
+                        ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);
+                } else {
+                        ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset);
+                }
+
+                offset += sort_array[i].rec_len;
+        }
+
+        old_data_block->dirty = true;
+        new_data_block_tmp->dirty = true;
+
+        free(sort_array);
+        free(entry_buffer);
 
         // TODO add new entry to index block
+        index_block->position++;
+
+        ext4_directory_dx_entry_set_block(index_block->position, new_fblock);
+        ext4_directory_dx_entry_set_hash(index_block->position, new_hash);
+
+        index_block->block->dirty = true;
+
+        *new_data_block = new_data_block_tmp;
 
         return EOK;
@@ -581 +662 @@
 
 
-        block_t *target;
-        rc = block_get(&target, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
+        block_t *target_block;
+        rc = block_get(&target_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
         if (rc != EOK) {
                 return EXT4_ERR_BAD_DX_DIR;
@@ -590 +671 @@
         uint16_t required_len = 8 + name_size + (4 - name_size % 4);
 
-        ext4_directory_entry_ll_t *de = target->data;
-        ext4_directory_entry_ll_t *stop = target->data + block_size;
+        ext4_directory_entry_ll_t *de = target_block->data;
+        ext4_directory_entry_ll_t *stop = target_block->data + block_size;
 
         while (de < stop) {
@@ -601 +682 @@
                         ext4_directory_write_entry(fs->superblock, de, de_rec_len,
                                 child, name, name_size);
-                                target->dirty = true;
-                                rc = block_put(target);
+                                target_block->dirty = true;
+                                rc = block_put(target_block);
                                 if (rc != EOK) {
                                         return EXT4_ERR_BAD_DX_DIR;
@@ -628 +709 @@
                                 ext4_directory_write_entry(fs->superblock, new_entry,
                                         free_space, child, name, name_size);
-                                target->dirty = true;
-                                rc = block_put(target);
+                                target_block->dirty = true;
+                                rc = block_put(target_block);
                                 if (rc != EOK) {
                                         return EXT4_ERR_BAD_DX_DIR;
@@ -687 +768 @@
         }
 
-        rc = ext4_directory_dx_split_data(fs, parent, &hinfo, target, dx_block);
+        block_t *new_block;
+        rc = ext4_directory_dx_split_data(fs, parent, &hinfo, target_block, dx_block, &new_block);
         if (rc != EOK) {
                 // TODO error
         }
+
+        // TODO Where to save new entry