Changeset d76973c in mainline for uspace/lib/ext4/libext4_balloc.c

Timestamp:

2015-04-25T21:20:11Z (9 years ago)

Author:

Maurizio Lombardi <m.lombardi85@…>

Branches:

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

Children:

60c409c

Parents:

7f29575

Message:

libext4: introduce support for flexible block groups.

With FLEX_BG, several block groups are tied together as one single group,
the first group of the flex_bg contains the block/inode bitmaps and the inode tables of all the other groups.
This improves metadata locality and frees up a lot of contiguous free space for extents.

• modified ext4_balloc_free_blocks() so it can free extents spanning 2 or more block groups
• with FLEX_BG the inode table, the bitmap and inode blocks of a group can reside on a different group.
  • the ext4_balloc_get_first_data_block_in_group() function has been modified to return a correct result in such a case.
  • improve the ext4_filesystem_init_block_bitmap() for the flex_bg case.
• added the ext4_filesystem_blockaddr2group() function that given a block number returns the id of the group it belongs to.
• added the ext4_filesystem_bg_get_itable_size() functions that given a group id number returns the size in blocks of its inode table.

File:

• uspace/lib/ext4/libext4_balloc.c (modified) (9 diffs)

uspace/lib/ext4/libext4_balloc.c

@@ -135 +135 @@
 }
 
-/** Free continuous set of blocks.
- *
- * @param inode_ref Inode, where the blocks are allocated
- * @param first     First block to release
- * @param count     Number of blocks to release
- *
- */
-int ext4_balloc_free_blocks(ext4_inode_ref_t *inode_ref,
+static int ext4_balloc_free_blocks_internal(ext4_inode_ref_t *inode_ref,
     uint32_t first, uint32_t count)
 {
         ext4_filesystem_t *fs = inode_ref->fs;
         ext4_superblock_t *sb = fs->superblock;
-        
+
         /* Compute indexes */
         uint32_t block_group_first =
@@ -153 +146 @@
         uint32_t block_group_last =
             ext4_balloc_get_bgid_of_block(sb, first + count - 1);
-        
+
         assert(block_group_first == block_group_last);
-        
+
         /* Load block group reference */
         ext4_block_group_ref_t *bg_ref;
@@ -161 +154 @@
         if (rc != EOK)
                 return rc;
-        
+
         uint32_t index_in_group_first =
             ext4_filesystem_blockaddr2_index_in_group(sb, first);
-        
+
         /* Load block with bitmap */
         uint32_t bitmap_block_addr =
             ext4_block_group_get_block_bitmap(bg_ref->block_group, sb);
-        
+
         block_t *bitmap_block;
         rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0);
@@ -175 +168 @@
                 return rc;
         }
-        
+
         /* Modify bitmap */
         ext4_bitmap_free_bits(bitmap_block->data, index_in_group_first, count);
         bitmap_block->dirty = true;
-        
+
         /* Release block with bitmap */
         rc = block_put(bitmap_block);
@@ -187 +180 @@
                 return rc;
         }
-        
+
         uint32_t block_size = ext4_superblock_get_block_size(sb);
-        
+
         /* Update superblock free blocks count */
         uint32_t sb_free_blocks =
@@ -195 +188 @@
         sb_free_blocks += count;
         ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
-        
+
         /* Update inode blocks count */
         uint64_t ino_blocks =
@@ -202 +195 @@
         ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
         inode_ref->dirty = true;
-        
+
         /* Update block group free blocks count */
         uint32_t free_blocks =
@@ -210 +203 @@
             sb, free_blocks);
         bg_ref->dirty = true;
-        
+
         /* Release block group reference */
         return ext4_filesystem_put_block_group_ref(bg_ref);
 }
 
+/** Free continuous set of blocks.
+ *
+ * @param inode_ref Inode, where the blocks are allocated
+ * @param first     First block to release
+ * @param count     Number of blocks to release
+ *
+ */
+int ext4_balloc_free_blocks(ext4_inode_ref_t *inode_ref,
+    uint32_t first, uint32_t count)
+{
+        int r;
+        uint32_t gid;
+        uint64_t limit;
+        ext4_filesystem_t *fs = inode_ref->fs;
+        ext4_superblock_t *sb = fs->superblock;
+
+        while (count) {
+                gid = ext4_filesystem_blockaddr2group(sb, first);
+                limit = ext4_filesystem_index_in_group2blockaddr(sb, 0,
+                    gid + 1);
+
+                if ((first + count) >= limit) {
+                        /* This extent spans over 2 or more block groups,
+                         * we'll break it into smaller parts.
+                         */
+                        uint32_t s = limit - first;
+
+                        r = ext4_balloc_free_blocks_internal(inode_ref,
+                            first, s);
+                        if (r != EOK)
+                                return r;
+
+                        first = limit;
+                        count -= s;
+                } else {
+                        return ext4_balloc_free_blocks_internal(inode_ref,
+                            first, count);
+                }
+        }
+
+        return EOK;
+}
+
 /** Compute first block for data in block group.
  *
@@ -227 +263 @@
     ext4_block_group_ref_t *bg_ref)
 {
-        uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
-        uint32_t inode_table_first_block =
-            ext4_block_group_get_inode_table_first_block(bg_ref->block_group, sb);
-        uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
-        uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
-        uint32_t block_size = ext4_superblock_get_block_size(sb);
-        uint32_t inode_table_bytes;
-        
-        if (bg_ref->index < block_group_count - 1) {
-                inode_table_bytes = inodes_per_group * inode_table_item_size;
-        } else {
-                /* Last block group could be smaller */
-                uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
-                inode_table_bytes =
-                    (inodes_count_total - ((block_group_count - 1) * inodes_per_group)) *
-                    inode_table_item_size;
-        }
-        
-        uint32_t inode_table_blocks = inode_table_bytes / block_size;
-        
-        if (inode_table_bytes % block_size)
-                inode_table_blocks++;
-        
-        return inode_table_first_block + inode_table_blocks;
+        uint32_t r;
+        uint64_t itable = ext4_block_group_get_inode_table_first_block(
+            bg_ref->block_group, sb);
+        uint32_t itable_sz = ext4_filesystem_bg_get_itable_size(sb, bg_ref);
+
+        if (!ext4_superblock_has_feature_incompatible(sb,
+            EXT4_FEATURE_INCOMPAT_FLEX_BG)) {
+                /* If we are not using FLEX_BG, the first data block
+                 * is always after the inode table.
+                 */
+                r = itable + itable_sz;
+                return ext4_filesystem_blockaddr2_index_in_group(sb, r);
+        }
+
+        uint64_t bbmap = ext4_block_group_get_block_bitmap(bg_ref->block_group,
+            sb);
+        uint64_t ibmap = ext4_block_group_get_inode_bitmap(bg_ref->block_group,
+            sb);
+
+        r = ext4_filesystem_bg_get_backup_blocks(bg_ref);
+
+        if (ext4_filesystem_blockaddr2group(sb, bbmap) == bg_ref->index)
+                bbmap = ext4_filesystem_blockaddr2_index_in_group(sb, bbmap);
+        else
+                bbmap = -1; /* Invalid */
+
+        if (ext4_filesystem_blockaddr2group(sb, ibmap) == bg_ref->index)
+                ibmap = ext4_filesystem_blockaddr2_index_in_group(sb, ibmap);
+        else
+                ibmap = -1;
+
+        while (1) {
+                uint64_t r_abs = ext4_filesystem_index_in_group2blockaddr(sb,
+                        r, bg_ref->index);
+
+                if (r == bbmap || r == ibmap)
+                        r++;
+                else if (r_abs >= itable && r_abs < itable_sz) {
+                        r = ext4_filesystem_blockaddr2_index_in_group(sb,
+                            itable + itable_sz);
+                } else
+                        break;
+        }
+
+        return r;
 }