Changeset d76973c in mainline


Ignore:
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.
Location:
uspace/lib/ext4
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/ext4/libext4_balloc.c

    r7f29575 rd76973c  
    135135}
    136136
    137 /** Free continuous set of blocks.
    138  *
    139  * @param inode_ref Inode, where the blocks are allocated
    140  * @param first     First block to release
    141  * @param count     Number of blocks to release
    142  *
    143  */
    144 int ext4_balloc_free_blocks(ext4_inode_ref_t *inode_ref,
     137static int ext4_balloc_free_blocks_internal(ext4_inode_ref_t *inode_ref,
    145138    uint32_t first, uint32_t count)
    146139{
    147140        ext4_filesystem_t *fs = inode_ref->fs;
    148141        ext4_superblock_t *sb = fs->superblock;
    149        
     142
    150143        /* Compute indexes */
    151144        uint32_t block_group_first =
    … …  
    153146        uint32_t block_group_last =
    154147            ext4_balloc_get_bgid_of_block(sb, first + count - 1);
    155        
     148
    156149        assert(block_group_first == block_group_last);
    157        
     150
    158151        /* Load block group reference */
    159152        ext4_block_group_ref_t *bg_ref;
    … …  
    161154        if (rc != EOK)
    162155                return rc;
    163        
     156
    164157        uint32_t index_in_group_first =
    165158            ext4_filesystem_blockaddr2_index_in_group(sb, first);
    166        
     159
    167160        /* Load block with bitmap */
    168161        uint32_t bitmap_block_addr =
    169162            ext4_block_group_get_block_bitmap(bg_ref->block_group, sb);
    170        
     163
    171164        block_t *bitmap_block;
    172165        rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0);
    … …  
    175168                return rc;
    176169        }
    177        
     170
    178171        /* Modify bitmap */
    179172        ext4_bitmap_free_bits(bitmap_block->data, index_in_group_first, count);
    180173        bitmap_block->dirty = true;
    181        
     174
    182175        /* Release block with bitmap */
    183176        rc = block_put(bitmap_block);
    … …  
    187180                return rc;
    188181        }
    189        
     182
    190183        uint32_t block_size = ext4_superblock_get_block_size(sb);
    191        
     184
    192185        /* Update superblock free blocks count */
    193186        uint32_t sb_free_blocks =
    … …  
    195188        sb_free_blocks += count;
    196189        ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
    197        
     190
    198191        /* Update inode blocks count */
    199192        uint64_t ino_blocks =
    … …  
    202195        ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
    203196        inode_ref->dirty = true;
    204        
     197
    205198        /* Update block group free blocks count */
    206199        uint32_t free_blocks =
    … …  
    210203            sb, free_blocks);
    211204        bg_ref->dirty = true;
    212        
     205
    213206        /* Release block group reference */
    214207        return ext4_filesystem_put_block_group_ref(bg_ref);
    215208}
    216209
     210/** Free continuous set of blocks.
     211 *
     212 * @param inode_ref Inode, where the blocks are allocated
     213 * @param first     First block to release
     214 * @param count     Number of blocks to release
     215 *
     216 */
     217int ext4_balloc_free_blocks(ext4_inode_ref_t *inode_ref,
     218    uint32_t first, uint32_t count)
     219{
     220        int r;
     221        uint32_t gid;
     222        uint64_t limit;
     223        ext4_filesystem_t *fs = inode_ref->fs;
     224        ext4_superblock_t *sb = fs->superblock;
     225
     226        while (count) {
     227                gid = ext4_filesystem_blockaddr2group(sb, first);
     228                limit = ext4_filesystem_index_in_group2blockaddr(sb, 0,
     229                    gid + 1);
     230
     231                if ((first + count) >= limit) {
     232                        /* This extent spans over 2 or more block groups,
     233                         * we'll break it into smaller parts.
     234                         */
     235                        uint32_t s = limit - first;
     236
     237                        r = ext4_balloc_free_blocks_internal(inode_ref,
     238                            first, s);
     239                        if (r != EOK)
     240                                return r;
     241
     242                        first = limit;
     243                        count -= s;
     244                } else {
     245                        return ext4_balloc_free_blocks_internal(inode_ref,
     246                            first, count);
     247                }
     248        }
     249
     250        return EOK;
     251}
     252
    217253/** Compute first block for data in block group.
    218254 *
    … …  
    227263    ext4_block_group_ref_t *bg_ref)
    228264{
    229         uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
    230         uint32_t inode_table_first_block =
    231             ext4_block_group_get_inode_table_first_block(bg_ref->block_group, sb);
    232         uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
    233         uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
    234         uint32_t block_size = ext4_superblock_get_block_size(sb);
    235         uint32_t inode_table_bytes;
    236        
    237         if (bg_ref->index < block_group_count - 1) {
    238                 inode_table_bytes = inodes_per_group * inode_table_item_size;
    239         } else {
    240                 /* Last block group could be smaller */
    241                 uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
    242                 inode_table_bytes =
    243                     (inodes_count_total - ((block_group_count - 1) * inodes_per_group)) *
    244                     inode_table_item_size;
    245         }
    246        
    247         uint32_t inode_table_blocks = inode_table_bytes / block_size;
    248        
    249         if (inode_table_bytes % block_size)
    250                 inode_table_blocks++;
    251        
    252         return inode_table_first_block + inode_table_blocks;
     265        uint32_t r;
     266        uint64_t itable = ext4_block_group_get_inode_table_first_block(
     267            bg_ref->block_group, sb);
     268        uint32_t itable_sz = ext4_filesystem_bg_get_itable_size(sb, bg_ref);
     269
     270        if (!ext4_superblock_has_feature_incompatible(sb,
     271            EXT4_FEATURE_INCOMPAT_FLEX_BG)) {
     272                /* If we are not using FLEX_BG, the first data block
     273                 * is always after the inode table.
     274                 */
     275                r = itable + itable_sz;
     276                return ext4_filesystem_blockaddr2_index_in_group(sb, r);
     277        }
     278
     279        uint64_t bbmap = ext4_block_group_get_block_bitmap(bg_ref->block_group,
     280            sb);
     281        uint64_t ibmap = ext4_block_group_get_inode_bitmap(bg_ref->block_group,
     282            sb);
     283
     284        r = ext4_filesystem_bg_get_backup_blocks(bg_ref);
     285
     286        if (ext4_filesystem_blockaddr2group(sb, bbmap) == bg_ref->index)
     287                bbmap = ext4_filesystem_blockaddr2_index_in_group(sb, bbmap);
     288        else
     289                bbmap = -1; /* Invalid */
     290
     291        if (ext4_filesystem_blockaddr2group(sb, ibmap) == bg_ref->index)
     292                ibmap = ext4_filesystem_blockaddr2_index_in_group(sb, ibmap);
     293        else
     294                ibmap = -1;
     295
     296        while (1) {
     297                uint64_t r_abs = ext4_filesystem_index_in_group2blockaddr(sb,
     298                        r, bg_ref->index);
     299
     300                if (r == bbmap || r == ibmap)
     301                        r++;
     302                else if (r_abs >= itable && r_abs < itable_sz) {
     303                        r = ext4_filesystem_blockaddr2_index_in_group(sb,
     304                            itable + itable_sz);
     305                } else
     306                        break;
     307        }
     308
     309        return r;
    253310}
    254311

  • uspace/lib/ext4/libext4_filesystem.c

    r7f29575 rd76973c  
    251251}
    252252
     253/** Convert the absolute block number to group number
     254 *
     255 * @param sb    Pointer to the superblock
     256 * @param b     Absolute block number
     257 *
     258 * @return      Group number
     259 */
     260uint32_t ext4_filesystem_blockaddr2group(ext4_superblock_t *sb, uint64_t b)
     261{
     262        uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb);
     263
     264        return b / blocks_per_group;
     265}
     266
    253267/** Initialize block bitmap in block group.
    254268 *
    … …  
    260274static int ext4_filesystem_init_block_bitmap(ext4_block_group_ref_t *bg_ref)
    261275{
     276        uint64_t itb;
     277        uint32_t sz;
     278        uint32_t i;
     279
    262280        /* Load bitmap */
    263         uint32_t bitmap_block_addr = ext4_block_group_get_block_bitmap(
     281        ext4_superblock_t *sb = bg_ref->fs->superblock;
     282        uint64_t bitmap_block_addr = ext4_block_group_get_block_bitmap(
     283            bg_ref->block_group, bg_ref->fs->superblock);
     284        uint64_t bitmap_inode_addr = ext4_block_group_get_inode_bitmap(
    264285            bg_ref->block_group, bg_ref->fs->superblock);
    265286       
    … …  
    273294       
    274295        /* Initialize all bitmap bits to zero */
    275         uint32_t block_size = ext4_superblock_get_block_size(bg_ref->fs->superblock);
     296        uint32_t block_size = ext4_superblock_get_block_size(sb);
    276297        memset(bitmap, 0, block_size);
    277298       
    278         /* Determine first block and first data block in group */
    279         uint32_t first_idx = 0;
    280        
    281         uint32_t first_data = ext4_balloc_get_first_data_block_in_group(
    282             bg_ref->fs->superblock, bg_ref);
    283         uint32_t first_data_idx = ext4_filesystem_blockaddr2_index_in_group(
    284             bg_ref->fs->superblock, first_data);
    285        
     299        /* Determine the number of reserved blocks in the group */
     300        uint32_t reserved_cnt = ext4_filesystem_bg_get_backup_blocks(bg_ref);
     301
    286302        /* Set bits from to first block to first data block - 1 to one (allocated) */
    287         for (uint32_t block = first_idx; block < first_data_idx; ++block)
     303        for (uint32_t block = 0; block < reserved_cnt; ++block)
    288304                ext4_bitmap_set_bit(bitmap, block);
    289        
     305
     306        uint32_t bitmap_block_gid = ext4_filesystem_blockaddr2group(sb,
     307            bitmap_block_addr);
     308        if (bitmap_block_gid == bg_ref->index) {
     309                ext4_bitmap_set_bit(bitmap,
     310                    ext4_filesystem_blockaddr2_index_in_group(sb, bitmap_block_addr));
     311        }
     312
     313        uint32_t bitmap_inode_gid = ext4_filesystem_blockaddr2group(sb,
     314            bitmap_inode_addr);
     315        if (bitmap_inode_gid == bg_ref->index) {
     316                ext4_bitmap_set_bit(bitmap,
     317                    ext4_filesystem_blockaddr2_index_in_group(sb, bitmap_inode_addr));
     318        }
     319
     320        itb = ext4_block_group_get_inode_table_first_block(bg_ref->block_group,
     321            sb);
     322        sz = ext4_filesystem_bg_get_itable_size(sb, bg_ref);
     323
     324        for (i = 0; i < sz; ++i, ++itb) {
     325                uint32_t gid = ext4_filesystem_blockaddr2group(sb, itb);
     326                if (gid == bg_ref->index) {
     327                        ext4_bitmap_set_bit(bitmap,
     328                            ext4_filesystem_blockaddr2_index_in_group(sb, itb));
     329                }
     330        }
     331
    290332        bitmap_block->dirty = true;
    291333       
    … …  
    524566}
    525567
     568/** Get the size of the block group's inode table
     569 *
     570 * @param sb     Pointer to the superblock
     571 * @param bg_ref Pointer to the block group reference
     572 *
     573 * @return       Size of the inode table in blocks.
     574 */
     575uint32_t ext4_filesystem_bg_get_itable_size(ext4_superblock_t *sb,
     576    ext4_block_group_ref_t *bg_ref)
     577{
     578        uint32_t itable_size;
     579        uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
     580        uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
     581        uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
     582        uint32_t block_size = ext4_superblock_get_block_size(sb);
     583
     584        if (bg_ref->index < block_group_count - 1) {
     585                itable_size = inodes_per_group * inode_table_item_size;
     586        } else {
     587                /* Last block group could be smaller */
     588                uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
     589                itable_size =
     590                    (inodes_count_total - ((block_group_count - 1) * inodes_per_group)) *
     591                    inode_table_item_size;
     592        }
     593
     594        return ROUND_UP(itable_size, block_size) / block_size;
     595}
     596
    526597/* Check if n is a power of p */
    527598static bool is_power_of(uint32_t n, unsigned p)
    … …  
    548619 * @return      Number of blocks
    549620 */
    550 uint32_t ext4_block_group_get_backup_blocks(ext4_block_group_ref_t *bg)
     621uint32_t ext4_filesystem_bg_get_backup_blocks(ext4_block_group_ref_t *bg)
    551622{
    552623        uint32_t const idx = bg->index;

  • uspace/lib/ext4/libext4_filesystem.h

    r7f29575 rd76973c  
    4747extern uint32_t ext4_filesystem_index_in_group2blockaddr(ext4_superblock_t *,
    4848    uint32_t, uint32_t);
     49extern uint32_t ext4_filesystem_blockaddr2group(ext4_superblock_t *, uint64_t);
    4950extern int ext4_filesystem_get_block_group_ref(ext4_filesystem_t *, uint32_t,
    5051    ext4_block_group_ref_t **);
    … …  
    6465extern int ext4_filesystem_append_inode_block(ext4_inode_ref_t *, uint32_t *,
    6566    uint32_t *);
    66 uint32_t ext4_block_group_get_backup_blocks(ext4_block_group_ref_t *bg);
     67uint32_t ext4_filesystem_bg_get_backup_blocks(ext4_block_group_ref_t *bg);
     68uint32_t ext4_filesystem_bg_get_itable_size(ext4_superblock_t *sb,
     69    ext4_block_group_ref_t *bg_ref);
    6770
    6871#endif

  • uspace/lib/ext4/libext4_types.h

    r7f29575 rd76973c  
    214214        (EXT4_FEATURE_INCOMPAT_FILETYPE | \
    215215        EXT4_FEATURE_INCOMPAT_EXTENTS | \
    216         EXT4_FEATURE_INCOMPAT_64BIT)
     216        EXT4_FEATURE_INCOMPAT_64BIT | \
     217        EXT4_FEATURE_INCOMPAT_FLEX_BG)
    217218
    218219#define EXT4_FEATURE_RO_COMPAT_SUPP \
Note: See TracChangeset for help on using the changeset viewer.