Changes in uspace/lib/ext4/src/extent.c [a35b458:5a6cc679] in mainline

File:

• uspace/lib/ext4/src/extent.c (modified) (50 diffs)

uspace/lib/ext4/src/extent.c

@@ -295 +295 @@
         ext4_extent_index_t *l;
         ext4_extent_index_t *m;
-
+        
         uint16_t entries_count =
             ext4_extent_header_get_entries_count(header);
-
+        
         /* Initialize bounds */
         l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
         r = EXT4_EXTENT_FIRST_INDEX(header) + entries_count - 1;
-
+        
         /* Do binary search */
         while (l <= r) {
                 m = l + (r - l) / 2;
                 uint32_t first_block = ext4_extent_index_get_first_block(m);
-
+                
                 if (iblock < first_block)
                         r = m - 1;
@@ -313 +313 @@
                         l = m + 1;
         }
-
+        
         /* Set output value */
         *index = l - 1;
@@ -332 +332 @@
         ext4_extent_t *l;
         ext4_extent_t *m;
-
+        
         uint16_t entries_count =
             ext4_extent_header_get_entries_count(header);
-
+        
         if (entries_count == 0) {
                 /* this leaf is empty */
@@ -341 +341 @@
                 return;
         }
-
+        
         /* Initialize bounds */
         l = EXT4_EXTENT_FIRST(header) + 1;
         r = EXT4_EXTENT_FIRST(header) + entries_count - 1;
-
+        
         /* Do binary search */
         while (l <= r) {
                 m = l + (r - l) / 2;
                 uint32_t first_block = ext4_extent_get_first_block(m);
-
+                
                 if (iblock < first_block)
                         r = m - 1;
@@ -356 +356 @@
                         l = m + 1;
         }
-
+        
         /* Set output value */
         *extent = l - 1;
@@ -379 +379 @@
         uint64_t inode_size =
             ext4_inode_get_size(inode_ref->fs->superblock, inode_ref->inode);
-
+        
         uint32_t block_size =
             ext4_superblock_get_block_size(inode_ref->fs->superblock);
-
+        
         uint32_t last_idx = (inode_size - 1) / block_size;
-
+        
         /* Check if requested iblock is not over size of i-node */
         if (iblock > last_idx) {
@@ -390 +390 @@
                 return EOK;
         }
-
+        
         block_t *block = NULL;
-
+        
         /* Walk through extent tree */
         ext4_extent_header_t *header =
             ext4_inode_get_extent_header(inode_ref->inode);
-
+        
         while (ext4_extent_header_get_depth(header) != 0) {
                 /* Search index in node */
                 ext4_extent_index_t *index;
                 ext4_extent_binsearch_idx(header, &index, iblock);
-
+                
                 /* Load child node and set values for the next iteration */
                 uint64_t child = ext4_extent_index_get_leaf(index);
-
+                
                 if (block != NULL) {
                         rc = block_put(block);
@@ -410 +410 @@
                                 return rc;
                 }
-
+                
                 rc = block_get(&block, inode_ref->fs->device, child,
                     BLOCK_FLAGS_NONE);
                 if (rc != EOK)
                         return rc;
-
+                
                 header = (ext4_extent_header_t *)block->data;
         }
-
+        
         /* Search extent in the leaf block */
         ext4_extent_t* extent = NULL;
         ext4_extent_binsearch(header, &extent, iblock);
-
+        
         /* Prevent empty leaf */
         if (extent == NULL) {
@@ -431 +431 @@
                 uint32_t first = ext4_extent_get_first_block(extent);
                 phys_block = ext4_extent_get_start(extent) + iblock - first;
-
+                
                 *fblock = phys_block;
         }
-
+        
         /* Cleanup */
         if (block != NULL)
                 rc = block_put(block);
-
+        
         return rc;
 }
@@ -459 +459 @@
         ext4_extent_header_t *eh =
             ext4_inode_get_extent_header(inode_ref->inode);
-
+        
         uint16_t depth = ext4_extent_header_get_depth(eh);
-
+        
         ext4_extent_path_t *tmp_path;
-
+        
         /* Added 2 for possible tree growing */
         tmp_path = malloc(sizeof(ext4_extent_path_t) * (depth + 2));
         if (tmp_path == NULL)
                 return ENOMEM;
-
+        
         /* Initialize structure for algorithm start */
         tmp_path[0].block = inode_ref->block;
         tmp_path[0].header = eh;
-
+        
         /* Walk through the extent tree */
         uint16_t pos = 0;
@@ -480 +480 @@
                 ext4_extent_binsearch_idx(tmp_path[pos].header,
                     &tmp_path[pos].index, iblock);
-
+                
                 tmp_path[pos].depth = depth;
                 tmp_path[pos].extent = NULL;
-
+                
                 assert(tmp_path[pos].index != NULL);
-
+                
                 /* Load information for the next iteration */
                 uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index);
-
+                
                 block_t *block;
                 rc = block_get(&block, inode_ref->fs->device, fblock,
@@ -494 +494 @@
                 if (rc != EOK)
                         goto cleanup;
-
+                
                 pos++;
-
+                
                 eh = (ext4_extent_header_t *)block->data;
                 tmp_path[pos].block = block;
                 tmp_path[pos].header = eh;
         }
-
+        
         tmp_path[pos].depth = 0;
         tmp_path[pos].extent = NULL;
         tmp_path[pos].index = NULL;
-
+        
         /* Find extent in the leaf node */
         ext4_extent_binsearch(tmp_path[pos].header, &tmp_path[pos].extent, iblock);
         *ret_path = tmp_path;
-
+        
         return EOK;
-
+        
 cleanup:
         ;
@@ -528 +528 @@
                 }
         }
-
+        
         /* Destroy temporary data structure */
         free(tmp_path);
-
+        
         return rc;
 }
@@ -549 +549 @@
         uint64_t start = ext4_extent_get_start(extent);
         uint16_t block_count = ext4_extent_get_block_count(extent);
-
+        
         return ext4_balloc_free_blocks(inode_ref, start, block_count);
 }
@@ -569 +569 @@
 {
         uint32_t fblock = ext4_extent_index_get_leaf(index);
-
+        
         block_t* block;
         errno_t rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NONE);
         if (rc != EOK)
                 return rc;
-
+        
         ext4_extent_header_t *header = block->data;
-
+        
         if (ext4_extent_header_get_depth(header)) {
                 /* The node is non-leaf, do recursion */
                 ext4_extent_index_t *idx = EXT4_EXTENT_FIRST_INDEX(header);
-
+                
                 /* Release all subbranches */
                 for (uint32_t i = 0;
@@ -592 +592 @@
                 /* Leaf node reached */
                 ext4_extent_t *ext = EXT4_EXTENT_FIRST(header);
-
+                
                 /* Release all extents and stop recursion */
                 for (uint32_t i = 0;
@@ -602 +602 @@
                 }
         }
-
+        
         /* Release data block where the node was stored */
-
+        
         rc = block_put(block);
         if (rc != EOK)
                 return rc;
-
+        
         return ext4_balloc_free_block(inode_ref, fblock);
 }
@@ -626 +626 @@
         if (rc != EOK)
                 return rc;
-
+        
         /* Jump to last item of the path (extent) */
         ext4_extent_path_t *path_ptr = path;
         while (path_ptr->depth != 0)
                 path_ptr++;
-
+        
         assert(path_ptr->extent != NULL);
-
+        
         /* First extent maybe released partially */
         uint32_t first_iblock =
@@ -639 +639 @@
         uint32_t first_fblock =
             ext4_extent_get_start(path_ptr->extent) + iblock_from - first_iblock;
-
+        
         uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);
-
+        
         uint16_t delete_count = block_count -
             (ext4_extent_get_start(path_ptr->extent) - first_fblock);
-
+        
         /* Release all blocks */
         rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count);
         if (rc != EOK)
                 goto cleanup;
-
+        
         /* Correct counter */
         block_count -= delete_count;
         ext4_extent_set_block_count(path_ptr->extent, block_count);
-
+        
         /* Initialize the following loop */
         uint16_t entries =
@@ -659 +659 @@
         ext4_extent_t *tmp_ext = path_ptr->extent + 1;
         ext4_extent_t *stop_ext = EXT4_EXTENT_FIRST(path_ptr->header) + entries;
-
+        
         /* If first extent empty, release it */
         if (block_count == 0)
                 entries--;
-
+        
         /* Release all successors of the first extent in the same node */
         while (tmp_ext < stop_ext) {
                 first_fblock = ext4_extent_get_start(tmp_ext);
                 delete_count = ext4_extent_get_block_count(tmp_ext);
-
+                
                 rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count);
                 if (rc != EOK)
                         goto cleanup;
-
+                
                 entries--;
                 tmp_ext++;
         }
-
+        
         ext4_extent_header_set_entries_count(path_ptr->header, entries);
         path_ptr->block->dirty = true;
-
+        
         /* If leaf node is empty, parent entry must be modified */
         bool remove_parent_record = false;
-
+        
         /* Don't release root block (including inode data) !!! */
         if ((path_ptr != path) && (entries == 0)) {
@@ -688 +688 @@
                 if (rc != EOK)
                         goto cleanup;
-
+                
                 remove_parent_record = true;
         }
-
+        
         /* Jump to the parent */
         --path_ptr;
-
+        
         /* Release all successors in all tree levels */
         while (path_ptr >= path) {
@@ -701 +701 @@
                 ext4_extent_index_t *stop =
                     EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;
-
+                
                 /* Correct entries count because of changes in the previous iteration */
                 if (remove_parent_record)
                         entries--;
-
+                
                 /* Iterate over all entries and release the whole subtrees */
                 while (index < stop) {
@@ -711 +711 @@
                         if (rc != EOK)
                                 goto cleanup;
-
+                        
                         ++index;
                         --entries;
                 }
-
+                
                 ext4_extent_header_set_entries_count(path_ptr->header, entries);
                 path_ptr->block->dirty = true;
-
+                
                 /* Free the node if it is empty */
                 if ((entries == 0) && (path_ptr != path)) {
@@ -724 +724 @@
                         if (rc != EOK)
                                 goto cleanup;
-
+                        
                         /* Mark parent to be checked */
                         remove_parent_record = true;
                 } else
                         remove_parent_record = false;
-
+                
                 --path_ptr;
         }
-
+        
 cleanup:
         ;
@@ -749 +749 @@
                 }
         }
-
+        
         /* Destroy temporary data structure */
         free(path);
-
+        
         return rc;
 }
@@ -771 +771 @@
 {
         ext4_extent_path_t *path_ptr = path + path->depth;
-
+        
         uint32_t block_size =
             ext4_superblock_get_block_size(inode_ref->fs->superblock);
-
+        
         /* Start splitting */
         while (path_ptr > path) {
@@ -781 +781 @@
                 uint16_t limit =
                     ext4_extent_header_get_max_entries_count(path_ptr->header);
-
+                
                 if (entries == limit) {
                         /* Full node - allocate block for new one */
@@ -788 +788 @@
                         if (rc != EOK)
                                 return rc;
-
+                        
                         block_t *block;
                         rc = block_get(&block, inode_ref->fs->device, fblock,
@@ -796 +796 @@
                                 return rc;
                         }
-
+                        
                         /* Put back not modified old block */
                         rc = block_put(path_ptr->block);
@@ -804 +804 @@
                                 return rc;
                         }
-
+                        
                         /* Initialize newly allocated block and remember it */
                         memset(block->data, 0, block_size);
                         path_ptr->block = block;
-
+                        
                         /* Update pointers in extent path structure */
                         path_ptr->header = block->data;
@@ -823 +823 @@
                                     sizeof(ext4_extent_t);
                         }
-
+                        
                         /* Initialize on-disk structure (header) */
                         ext4_extent_header_set_entries_count(path_ptr->header, 1);
@@ -830 +830 @@
                         ext4_extent_header_set_depth(path_ptr->header, path_ptr->depth);
                         ext4_extent_header_set_generation(path_ptr->header, 0);
-
+                        
                         path_ptr->block->dirty = true;
-
+                        
                         /* Jump to the preceeding item */
                         path_ptr--;
@@ -845 +845 @@
                                 ext4_extent_set_first_block(path_ptr->extent, iblock);
                         }
-
+                        
                         ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);
                         path_ptr->block->dirty = true;
-
+                        
                         /* No more splitting needed */
                         return EOK;
                 }
         }
-
+        
         assert(path_ptr == path);
-
+        
         /* Should be the root split too? */
-
+        
         uint16_t entries = ext4_extent_header_get_entries_count(path->header);
         uint16_t limit = ext4_extent_header_get_max_entries_count(path->header);
-
+        
         if (entries == limit) {
                 uint32_t new_fblock;
@@ -866 +866 @@
                 if (rc != EOK)
                         return rc;
-
+                
                 block_t *block;
                 rc = block_get(&block, inode_ref->fs->device, new_fblock,
@@ -872 +872 @@
                 if (rc != EOK)
                         return rc;
-
+                
                 /* Initialize newly allocated block */
                 memset(block->data, 0, block_size);
-
+                
                 /* Move data from root to the new block */
                 memcpy(block->data, inode_ref->inode->blocks,
                     EXT4_INODE_BLOCKS * sizeof(uint32_t));
-
+                
                 /* Data block is initialized */
-
+                
                 block_t *root_block = path->block;
                 uint16_t root_depth = path->depth;
                 ext4_extent_header_t *root_header = path->header;
-
+                
                 /* Make space for tree growing */
                 ext4_extent_path_t *new_root = path;
                 ext4_extent_path_t *old_root = path + 1;
-
+                
                 size_t nbytes = sizeof(ext4_extent_path_t) * (path->depth + 1);
                 memmove(old_root, new_root, nbytes);
                 memset(new_root, 0, sizeof(ext4_extent_path_t));
-
+                
                 /* Update old root structure */
                 old_root->block = block;
                 old_root->header = (ext4_extent_header_t *)block->data;
-
+                
                 /* Add new entry and update limit for entries */
                 if (old_root->depth) {
@@ -913 +913 @@
                         old_root->index = NULL;
                 }
-
+                
                 ext4_extent_header_set_entries_count(old_root->header, entries + 1);
                 ext4_extent_header_set_max_entries_count(old_root->header, limit);
-
+                
                 old_root->block->dirty = true;
-
+                
                 /* Re-initialize new root metadata */
                 new_root->depth = root_depth + 1;
@@ -925 +925 @@
                 new_root->extent = NULL;
                 new_root->index = EXT4_EXTENT_FIRST_INDEX(new_root->header);
-
+                
                 ext4_extent_header_set_depth(new_root->header, new_root->depth);
-
+                
                 /* Create new entry in root */
                 ext4_extent_header_set_entries_count(new_root->header, 1);
                 ext4_extent_index_set_first_block(new_root->index, 0);
                 ext4_extent_index_set_leaf(new_root->index, new_fblock);
-
+                
                 new_root->block->dirty = true;
         } else {
@@ -943 +943 @@
                         ext4_extent_set_first_block(path->extent, iblock);
                 }
-
+                
                 ext4_extent_header_set_entries_count(path->header, entries + 1);
                 path->block->dirty = true;
         }
-
+        
         return EOK;
 }
@@ -970 +970 @@
         uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
         uint32_t block_size = ext4_superblock_get_block_size(sb);
-
+        
         /* Calculate number of new logical block */
         uint32_t new_block_idx = 0;
@@ -976 +976 @@
                 if ((inode_size % block_size) != 0)
                         inode_size += block_size - (inode_size % block_size);
-
+                
                 new_block_idx = inode_size / block_size;
         }
-
+        
         /* Load the nearest leaf (with extent) */
         ext4_extent_path_t *path;
@@ -985 +985 @@
         if (rc != EOK)
                 return rc;
-
+        
         /* Jump to last item of the path (extent) */
         ext4_extent_path_t *path_ptr = path;
         while (path_ptr->depth != 0)
                 path_ptr++;
-
+        
         /* Add new extent to the node if not present */
         if (path_ptr->extent == NULL)
                 goto append_extent;
-
+        
         uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);
         uint16_t block_limit = (1 << 15);
-
+        
         uint32_t phys_block = 0;
         if (block_count < block_limit) {
@@ -1006 +1006 @@
                         if (rc != EOK)
                                 goto finish;
-
+                        
                         /* Initialize extent */
                         ext4_extent_set_first_block(path_ptr->extent, new_block_idx);
                         ext4_extent_set_start(path_ptr->extent, phys_block);
                         ext4_extent_set_block_count(path_ptr->extent, 1);
-
+                        
                         /* Update i-node */
                         if (update_size) {
@@ -1017 +1017 @@
                                 inode_ref->dirty = true;
                         }
-
+                        
                         path_ptr->block->dirty = true;
-
+                        
                         goto finish;
                 } else {
@@ -1025 +1025 @@
                         phys_block = ext4_extent_get_start(path_ptr->extent);
                         phys_block += ext4_extent_get_block_count(path_ptr->extent);
-
+                        
                         /* Check if the following block is free for allocation */
                         bool free;
@@ -1031 +1031 @@
                         if (rc != EOK)
                                 goto finish;
-
+                        
                         if (!free) {
                                 /* Target is not free, new block must be appended to new extent */
                                 goto append_extent;
                         }
-
+                        
                         /* Update extent */
                         ext4_extent_set_block_count(path_ptr->extent, block_count + 1);
-
+                        
                         /* Update i-node */
                         if (update_size) {
@@ -1045 +1045 @@
                                 inode_ref->dirty = true;
                         }
-
+                        
                         path_ptr->block->dirty = true;
-
+                        
                         goto finish;
                 }
         }
-
-
+        
+        
 append_extent:
         /* Append new extent to the tree */
         phys_block = 0;
-
+        
         /* Allocate new data block */
         rc = ext4_balloc_alloc_block(inode_ref, &phys_block);
         if (rc != EOK)
                 goto finish;
-
+        
         /* Append extent for new block (includes tree splitting if needed) */
         rc = ext4_extent_append_extent(inode_ref, path, new_block_idx);
@@ -1068 +1068 @@
                 goto finish;
         }
-
+        
         uint32_t tree_depth = ext4_extent_header_get_depth(path->header);
         path_ptr = path + tree_depth;
-
+        
         /* Initialize newly created extent */
         ext4_extent_set_block_count(path_ptr->extent, 1);
         ext4_extent_set_first_block(path_ptr->extent, new_block_idx);
         ext4_extent_set_start(path_ptr->extent, phys_block);
-
+        
         /* Update i-node */
         if (update_size) {
@@ -1082 +1082 @@
                 inode_ref->dirty = true;
         }
-
+        
         path_ptr->block->dirty = true;
-
+        
 finish:
         ;
@@ -1093 +1093 @@
         *iblock = new_block_idx;
         *fblock = phys_block;
-
+        
         /*
          * Put loaded blocks
@@ -1105 +1105 @@
                 }
         }
-
+        
         /* Destroy temporary data structure */
         free(path);
-
+        
         return rc;
 }