Ignore:
File:
1 edited

Legend:

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

    r38542dc r24df0de6  
    3939#include "libext4.h"
    4040
    41 /** Compute number of block group from block address.
    42  *
    43  * @param sb         Superblock pointer.
    44  * @param block_addr Absolute address of block.
    45  *
    46  * @return Block group index
    47  *
    48  */
    49 static uint32_t ext4_balloc_get_bgid_of_block(ext4_superblock_t *sb,
    50     uint32_t block_addr)
    51 {
    52         uint32_t blocks_per_group =
    53             ext4_superblock_get_blocks_per_group(sb);
    54         uint32_t first_block =
    55             ext4_superblock_get_first_data_block(sb);
    56        
    57         /* First block == 0 or 1 */
    58         if (first_block == 0)
    59                 return block_addr / blocks_per_group;
    60         else
    61                 return (block_addr - 1) / blocks_per_group;
    62 }
    63 
    6441/** Free block.
    6542 *
     
    7653       
    7754        /* Compute indexes */
    78         uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, block_addr);
     55        uint32_t block_group = ext4_filesystem_blockaddr2group(sb, block_addr);
    7956        uint32_t index_in_group =
    8057            ext4_filesystem_blockaddr2_index_in_group(sb, block_addr);
     
    9168        block_t *bitmap_block;
    9269        rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0);
    93         if (rc != EOK)
    94                 return rc;
     70        if (rc != EOK) {
     71                ext4_filesystem_put_block_group_ref(bg_ref);
     72                return rc;
     73        }
    9574       
    9675        /* Modify bitmap */
     
    130109       
    131110        /* Release block group reference */
    132         rc = ext4_filesystem_put_block_group_ref(bg_ref);
    133         if (rc != EOK)
    134                 return rc;
    135        
    136         return EOK;
     111        return ext4_filesystem_put_block_group_ref(bg_ref);
    137112}
    138113
    139 /** Free continuous set of blocks.
    140  *
    141  * @param inode_ref Inode, where the blocks are allocated
    142  * @param first     First block to release
    143  * @param count     Number of blocks to release
    144  *
    145  */
    146 int ext4_balloc_free_blocks(ext4_inode_ref_t *inode_ref,
     114static int ext4_balloc_free_blocks_internal(ext4_inode_ref_t *inode_ref,
    147115    uint32_t first, uint32_t count)
    148116{
    149117        ext4_filesystem_t *fs = inode_ref->fs;
    150118        ext4_superblock_t *sb = fs->superblock;
    151        
     119
    152120        /* Compute indexes */
    153         uint32_t block_group_first =
    154             ext4_balloc_get_bgid_of_block(sb, first);
    155         uint32_t block_group_last =
    156             ext4_balloc_get_bgid_of_block(sb, first + count - 1);
    157        
     121        uint32_t block_group_first = ext4_filesystem_blockaddr2group(sb,
     122            first);
     123        uint32_t block_group_last = ext4_filesystem_blockaddr2group(sb,
     124            first + count - 1);
     125
    158126        assert(block_group_first == block_group_last);
    159        
     127
    160128        /* Load block group reference */
    161129        ext4_block_group_ref_t *bg_ref;
     
    163131        if (rc != EOK)
    164132                return rc;
    165        
     133
    166134        uint32_t index_in_group_first =
    167135            ext4_filesystem_blockaddr2_index_in_group(sb, first);
    168        
     136
    169137        /* Load block with bitmap */
    170138        uint32_t bitmap_block_addr =
    171139            ext4_block_group_get_block_bitmap(bg_ref->block_group, sb);
    172        
     140
    173141        block_t *bitmap_block;
    174142        rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0);
    175         if (rc != EOK)
    176                 return rc;
    177        
     143        if (rc != EOK) {
     144                ext4_filesystem_put_block_group_ref(bg_ref);
     145                return rc;
     146        }
     147
    178148        /* Modify bitmap */
    179149        ext4_bitmap_free_bits(bitmap_block->data, index_in_group_first, count);
    180150        bitmap_block->dirty = true;
    181        
     151
    182152        /* Release block with bitmap */
    183153        rc = block_put(bitmap_block);
     
    187157                return rc;
    188158        }
    189        
     159
    190160        uint32_t block_size = ext4_superblock_get_block_size(sb);
    191        
     161
    192162        /* Update superblock free blocks count */
    193163        uint32_t sb_free_blocks =
     
    195165        sb_free_blocks += count;
    196166        ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
    197        
     167
    198168        /* Update inode blocks count */
    199169        uint64_t ino_blocks =
     
    202172        ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
    203173        inode_ref->dirty = true;
    204        
     174
    205175        /* Update block group free blocks count */
    206176        uint32_t free_blocks =
     
    210180            sb, free_blocks);
    211181        bg_ref->dirty = true;
    212        
     182
    213183        /* Release block group reference */
    214         rc = ext4_filesystem_put_block_group_ref(bg_ref);
    215         if (rc != EOK)
    216                 return rc;
    217        
     184        return ext4_filesystem_put_block_group_ref(bg_ref);
     185}
     186
     187/** Free continuous set of blocks.
     188 *
     189 * @param inode_ref Inode, where the blocks are allocated
     190 * @param first     First block to release
     191 * @param count     Number of blocks to release
     192 *
     193 */
     194int ext4_balloc_free_blocks(ext4_inode_ref_t *inode_ref,
     195    uint32_t first, uint32_t count)
     196{
     197        int r;
     198        uint32_t gid;
     199        uint64_t limit;
     200        ext4_filesystem_t *fs = inode_ref->fs;
     201        ext4_superblock_t *sb = fs->superblock;
     202
     203        while (count) {
     204                gid = ext4_filesystem_blockaddr2group(sb, first);
     205                limit = ext4_filesystem_index_in_group2blockaddr(sb, 0,
     206                    gid + 1);
     207
     208                if ((first + count) >= limit) {
     209                        /* This extent spans over 2 or more block groups,
     210                         * we'll break it into smaller parts.
     211                         */
     212                        uint32_t s = limit - first;
     213
     214                        r = ext4_balloc_free_blocks_internal(inode_ref,
     215                            first, s);
     216                        if (r != EOK)
     217                                return r;
     218
     219                        first = limit;
     220                        count -= s;
     221                } else {
     222                        return ext4_balloc_free_blocks_internal(inode_ref,
     223                            first, count);
     224                }
     225        }
     226
    218227        return EOK;
    219228}
     
    231240    ext4_block_group_ref_t *bg_ref)
    232241{
    233         uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
    234         uint32_t inode_table_first_block =
    235             ext4_block_group_get_inode_table_first_block(bg_ref->block_group, sb);
    236         uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
    237         uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
    238         uint32_t block_size = ext4_superblock_get_block_size(sb);
    239         uint32_t inode_table_bytes;
    240        
    241         if (bg_ref->index < block_group_count - 1) {
    242                 inode_table_bytes = inodes_per_group * inode_table_item_size;
    243         } else {
    244                 /* Last block group could be smaller */
    245                 uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
    246                 inode_table_bytes =
    247                     (inodes_count_total - ((block_group_count - 1) * inodes_per_group)) *
    248                     inode_table_item_size;
    249         }
    250        
    251         uint32_t inode_table_blocks = inode_table_bytes / block_size;
    252        
    253         if (inode_table_bytes % block_size)
    254                 inode_table_blocks++;
    255        
    256         return inode_table_first_block + inode_table_blocks;
     242        uint32_t r;
     243        uint64_t itable = ext4_block_group_get_inode_table_first_block(
     244            bg_ref->block_group, sb);
     245        uint32_t itable_sz = ext4_filesystem_bg_get_itable_size(sb, bg_ref);
     246
     247        if (!ext4_superblock_has_feature_incompatible(sb,
     248            EXT4_FEATURE_INCOMPAT_FLEX_BG)) {
     249                /* If we are not using FLEX_BG, the first data block
     250                 * is always after the inode table.
     251                 */
     252                r = itable + itable_sz;
     253                return ext4_filesystem_blockaddr2_index_in_group(sb, r);
     254        }
     255
     256        uint64_t bbmap = ext4_block_group_get_block_bitmap(bg_ref->block_group,
     257            sb);
     258        uint64_t ibmap = ext4_block_group_get_inode_bitmap(bg_ref->block_group,
     259            sb);
     260
     261        r = ext4_filesystem_index_in_group2blockaddr(sb, 0, bg_ref->index);
     262        r += ext4_filesystem_bg_get_backup_blocks(bg_ref);
     263
     264        if (ext4_filesystem_blockaddr2group(sb, bbmap) != bg_ref->index)
     265                bbmap = -1; /* Invalid */
     266
     267        if (ext4_filesystem_blockaddr2group(sb, ibmap) != bg_ref->index)
     268                ibmap = -1;
     269
     270        while (1) {
     271                if (r == bbmap || r == ibmap)
     272                        r++;
     273                else if (r >= itable && r < (itable + itable_sz))
     274                        r = itable + itable_sz;
     275                else
     276                        break;
     277        }
     278
     279        return r;
    257280}
    258281
     
    264287 *
    265288 */
    266 static uint32_t ext4_balloc_find_goal(ext4_inode_ref_t *inode_ref)
     289static int ext4_balloc_find_goal(ext4_inode_ref_t *inode_ref, uint32_t *goal)
    267290{
    268         uint32_t goal = 0;
    269        
     291        *goal = 0;
    270292        ext4_superblock_t *sb = inode_ref->fs->superblock;
    271        
     293
    272294        uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
    273295        uint32_t block_size = ext4_superblock_get_block_size(sb);
    274296        uint32_t inode_block_count = inode_size / block_size;
    275        
     297
    276298        if (inode_size % block_size != 0)
    277299                inode_block_count++;
    278        
     300
    279301        /* If inode has some blocks, get last block address + 1 */
    280302        if (inode_block_count > 0) {
    281303                int rc = ext4_filesystem_get_inode_data_block_index(inode_ref,
    282                     inode_block_count - 1, &goal);
     304                    inode_block_count - 1, goal);
    283305                if (rc != EOK)
    284                         return 0;
    285                
     306                        return rc;
     307
    286308                if (goal != 0) {
    287                         goal++;
    288                         return goal;
    289                 }
    290                
     309                        (*goal)++;
     310                        return EOK;
     311                }
    291312                /* If goal == 0, sparse file -> continue */
    292313        }
    293        
     314
    294315        /* Identify block group of inode */
    295316        uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
    296317        uint32_t block_group = (inode_ref->index - 1) / inodes_per_group;
    297         block_size = ext4_superblock_get_block_size(sb);
    298        
     318
    299319        /* Load block group reference */
    300320        ext4_block_group_ref_t *bg_ref;
     
    302322            block_group, &bg_ref);
    303323        if (rc != EOK)
    304                 return 0;
    305        
    306         /* Compute indexes */
    307         uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
    308         uint32_t inode_table_first_block =
    309             ext4_block_group_get_inode_table_first_block(bg_ref->block_group, sb);
    310         uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
    311         uint32_t inode_table_bytes;
    312        
    313         /* Check for last block group */
    314         if (block_group < block_group_count - 1) {
    315                 inode_table_bytes = inodes_per_group * inode_table_item_size;
    316         } else {
    317                 /* Last block group could be smaller */
    318                 uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
    319                 inode_table_bytes =
    320                     (inodes_count_total - ((block_group_count - 1) * inodes_per_group)) *
    321                     inode_table_item_size;
    322         }
    323        
    324         uint32_t inode_table_blocks = inode_table_bytes / block_size;
    325        
    326         if (inode_table_bytes % block_size)
    327                 inode_table_blocks++;
    328        
    329         goal = inode_table_first_block + inode_table_blocks;
    330        
    331         ext4_filesystem_put_block_group_ref(bg_ref);
    332        
    333         return goal;
     324                return rc;
     325
     326        *goal = ext4_balloc_get_first_data_block_in_group(sb, bg_ref);
     327
     328        return ext4_filesystem_put_block_group_ref(bg_ref);
    334329}
    335330
     
    349344        block_t *bitmap_block;
    350345        uint32_t rel_block_idx = 0;
     346        uint32_t free_blocks;
     347        uint32_t goal;
    351348       
    352349        /* Find GOAL */
    353         uint32_t goal = ext4_balloc_find_goal(inode_ref);
    354         if (goal == 0) {
    355                 /* no goal found => partition is full */
    356                 return ENOSPC;
    357         }
    358        
     350        int rc = ext4_balloc_find_goal(inode_ref, &goal);
     351        if (rc != EOK)
     352                return rc;
     353
    359354        ext4_superblock_t *sb = inode_ref->fs->superblock;
    360355       
    361356        /* Load block group number for goal and relative index */
    362         uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, goal);
     357        uint32_t block_group = ext4_filesystem_blockaddr2group(sb, goal);
    363358        uint32_t index_in_group =
    364359            ext4_filesystem_blockaddr2_index_in_group(sb, goal);
     
    366361        /* Load block group reference */
    367362        ext4_block_group_ref_t *bg_ref;
    368         int rc = ext4_filesystem_get_block_group_ref(inode_ref->fs,
     363        rc = ext4_filesystem_get_block_group_ref(inode_ref->fs,
    369364            block_group, &bg_ref);
    370365        if (rc != EOK)
    371366                return rc;
     367
     368        free_blocks =
     369            ext4_block_group_get_free_blocks_count(bg_ref->block_group, sb);
     370        if (free_blocks == 0) {
     371                /* This group has no free blocks */
     372                goto goal_failed;
     373        }
    372374       
    373375        /* Compute indexes */
     
    467469       
    468470        /* No free block found yet */
    469         block_put(bitmap_block);
    470         ext4_filesystem_put_block_group_ref(bg_ref);
     471        rc = block_put(bitmap_block);
     472        if (rc != EOK) {
     473                ext4_filesystem_put_block_group_ref(bg_ref);
     474                return rc;
     475        }
     476
     477goal_failed:
     478
     479        rc = ext4_filesystem_put_block_group_ref(bg_ref);
     480        if (rc != EOK)
     481                return rc;
    471482       
    472483        /* Try other block groups */
     
    481492                if (rc != EOK)
    482493                        return rc;
    483                
     494
     495                free_blocks =
     496                     ext4_block_group_get_free_blocks_count(bg_ref->block_group, sb);
     497                if (free_blocks == 0) {
     498                        /* This group has no free blocks */
     499                        goto next_group;
     500                }
     501
    484502                /* Load block with bitmap */
    485503                bitmap_block_addr =
     
    512530                        bitmap_block->dirty = true;
    513531                        rc = block_put(bitmap_block);
    514                         if (rc != EOK)
     532                        if (rc != EOK) {
     533                                ext4_filesystem_put_block_group_ref(bg_ref);
    515534                                return rc;
     535                        }
    516536                       
    517537                        allocated_block =
     
    528548                        bitmap_block->dirty = true;
    529549                        rc = block_put(bitmap_block);
    530                         if (rc != EOK)
     550                        if (rc != EOK) {
     551                                ext4_filesystem_put_block_group_ref(bg_ref);
    531552                                return rc;
     553                        }
    532554                       
    533555                        allocated_block =
     
    538560                }
    539561               
    540                 block_put(bitmap_block);
    541                 ext4_filesystem_put_block_group_ref(bg_ref);
     562                rc = block_put(bitmap_block);
     563                if (rc != EOK) {
     564                        ext4_filesystem_put_block_group_ref(bg_ref);
     565                        return rc;
     566                }
     567
     568next_group:
     569                rc = ext4_filesystem_put_block_group_ref(bg_ref);
     570                if (rc != EOK)
     571                        return rc;
    542572               
    543573                /* Goto next group */
     
    574604        bg_ref->dirty = true;
    575605       
    576         ext4_filesystem_put_block_group_ref(bg_ref);
     606        rc = ext4_filesystem_put_block_group_ref(bg_ref);
    577607       
    578608        *fblock = allocated_block;
    579         return EOK;
     609        return rc;
    580610}
    581611
     
    592622    bool *free)
    593623{
    594         int rc = EOK;
     624        int rc;
    595625       
    596626        ext4_filesystem_t *fs = inode_ref->fs;
     
    598628       
    599629        /* Compute indexes */
    600         uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, fblock);
     630        uint32_t block_group = ext4_filesystem_blockaddr2group(sb, fblock);
    601631        uint32_t index_in_group =
    602632            ext4_filesystem_blockaddr2_index_in_group(sb, fblock);
     
    613643        block_t *bitmap_block;
    614644        rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0);
    615         if (rc != EOK)
    616                 return rc;
     645        if (rc != EOK) {
     646                ext4_filesystem_put_block_group_ref(bg_ref);
     647                return rc;
     648        }
    617649       
    618650        /* Check if block is free */
Note: See TracChangeset for help on using the changeset viewer.