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


Ignore:
Timestamp:
2011-11-18T15:30:24Z (13 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
d5ba17f
Parents:
e18de3c
Message:

improved block allocator - but has some bugs

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/ext4/libext4_balloc.c

    re18de3c rb12ca16  
    3131 */
    3232
     33/**
     34 * @file        libext4_balloc.c
     35 * @brief       Block allocator.
     36 */
     37
    3338#include <errno.h>
    3439#include <sys/types.h>
    3540#include "libext4.h"
    3641
    37 int ext4_bitmap_free_block(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t block_index)
    38 {
    39         int rc;
    40         uint32_t blocks_per_group;
    41         uint32_t block_group;
    42         uint32_t index_in_group;
    43         uint32_t bitmap_block;
    44         uint32_t block_size;
    45         ext4_block_group_ref_t *bg_ref;
    46         block_t *block;
    47         uint32_t first_block;
    48 
    49         block_size = ext4_superblock_get_block_size(fs->superblock);
    50         blocks_per_group = ext4_superblock_get_blocks_per_group(fs->superblock);
    51         first_block = ext4_superblock_get_first_data_block(fs->superblock);
     42static uint32_t ext4_balloc_blockaddr2_index_in_group(ext4_superblock_t *sb,
     43                uint32_t block_addr)
     44{
     45        uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb);
     46        uint32_t first_block = ext4_superblock_get_first_data_block(sb);
    5247
    5348        // First block == 0 or 1
    5449        if (first_block == 0) {
    55                 block_group = block_index / blocks_per_group;
    56                 index_in_group = block_index % blocks_per_group;
     50                return block_addr % blocks_per_group;
    5751        } else {
    58                 block_group = (block_index - 1) / blocks_per_group;
    59                 index_in_group = (block_index - 1) % blocks_per_group;
    60         }
    61 
     52                return (block_addr - 1) % blocks_per_group;
     53        }
     54}
     55
     56static uint32_t ext4_balloc_index_in_group2blockaddr(ext4_superblock_t *sb,
     57                uint32_t index, uint32_t bgid)
     58{
     59        uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb);
     60
     61        if (ext4_superblock_get_first_data_block(sb) == 0) {
     62                return bgid * blocks_per_group + index;
     63        } else {
     64                return bgid * blocks_per_group + index + 1;
     65        }
     66
     67}
     68
     69static uint32_t ext4_balloc_get_bgid_of_block(ext4_superblock_t *sb,
     70                uint32_t block_addr)
     71{
     72        uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb);
     73        uint32_t first_block = ext4_superblock_get_first_data_block(sb);
     74
     75        // First block == 0 or 1
     76        if (first_block == 0) {
     77                return block_addr / blocks_per_group;
     78        } else {
     79                return (block_addr - 1) / blocks_per_group;
     80        }
     81}
     82
     83
     84int ext4_balloc_free_block(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t block_addr)
     85{
     86        int rc;
     87
     88        uint32_t block_group = ext4_balloc_get_bgid_of_block(fs->superblock, block_addr);
     89        uint32_t index_in_group = ext4_balloc_blockaddr2_index_in_group(fs->superblock, block_addr);
     90
     91        ext4_block_group_ref_t *bg_ref;
    6292        rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
    6393        if (rc != EOK) {
    64                 return rc;
    65         }
    66 
    67         bitmap_block = ext4_block_group_get_block_bitmap(bg_ref->block_group);
    68 
    69         rc = block_get(&block, fs->device, bitmap_block, 0);
    70         if (rc != EOK) {
    71                 return rc;
    72         }
    73 
    74         ext4_bitmap_free_bit(block->data, index_in_group);
    75 
    76         block->dirty = true;
    77         rc = block_put(block);
    78         if (rc != EOK) {
    79                 return rc;
    80         }
     94                EXT4FS_DBG("error in loading bg_ref \%d", rc);
     95                return rc;
     96        }
     97
     98        uint32_t bitmap_block_addr = ext4_block_group_get_block_bitmap(bg_ref->block_group);
     99        block_t *bitmap_block;
     100        rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0);
     101        if (rc != EOK) {
     102                EXT4FS_DBG("error in loading bitmap \%d", rc);
     103                return rc;
     104        }
     105
     106        ext4_bitmap_free_bit(bitmap_block->data, index_in_group);
     107        bitmap_block->dirty = true;
     108
     109        rc = block_put(bitmap_block);
     110        if (rc != EOK) {
     111                // Error in saving bitmap
     112                ext4_filesystem_put_block_group_ref(bg_ref);
     113                EXT4FS_DBG("error in saving bitmap \%d", rc);
     114                return rc;
     115        }
     116
     117        uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
    81118
    82119        uint64_t ino_blocks = ext4_inode_get_blocks_count(fs->superblock, inode_ref->inode);
    … …  
    99136        }
    100137
     138//      EXT4FS_DBG("released block \%u (idx = \%u)", block_addr, index_in_group);
    101139        return EOK;
    102140}
    103141
    104 
    105 static uint32_t ext4_bitmap_find_goal(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref)
    106 {
     142static uint32_t ext4_balloc_get_first_data_block_in_group(
     143                ext4_superblock_t *sb, ext4_block_group_t *bg, uint32_t bgid)
     144{
     145        uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
     146        uint32_t inode_table_first_block = ext4_block_group_get_inode_table_first_block(bg);
     147        uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
     148        uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
     149        uint32_t block_size = ext4_superblock_get_block_size(sb);
     150        uint32_t inode_table_bytes;
     151
     152        if (bgid < block_group_count - 1) {
     153                inode_table_bytes = inodes_per_group * inode_table_item_size;
     154        } else {
     155                // last block group could be smaller
     156                uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
     157                inode_table_bytes =
     158                                (inodes_count_total - ((block_group_count - 1) * inodes_per_group))
     159                                * inode_table_item_size;
     160        }
     161
     162        uint32_t inode_table_blocks = inode_table_bytes / block_size;
     163
     164        if (inode_table_bytes % block_size) {
     165                inode_table_blocks++;
     166        }
     167
     168        return inode_table_first_block + inode_table_blocks;
     169}
     170
     171
     172static uint32_t ext4_balloc_find_goal(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref)
     173{
     174        int rc;
    107175        uint32_t goal = 0;
    108176
    109         int rc;
    110177        uint64_t inode_size = ext4_inode_get_size(fs->superblock, inode_ref->inode);
    111178        uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
    112179        uint32_t inode_block_count = inode_size / block_size;
    113180
    114 
    115181        if (inode_size % block_size != 0) {
    116182                inode_block_count++;
    … …  
    119185        if (inode_block_count > 0) {
    120186                // TODO check retval
    121 //              EXT4FS_DBG("has blocks");
    122187                ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, inode_block_count - 1, &goal);
    123188
    124189                // TODO
    125190                // If goal == 0 -> SPARSE file !!!
     191
    126192                goal++;
     193
     194//              EXT4FS_DBG("goal = \%u, inode_block_count == \%u", goal, inode_block_count);
     195
    127196                return goal;
    128197        }
    129198
    130 //      uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(fs->superblock);
     199//      EXT4FS_DBG("Inode has no blocks");
    131200
    132201        // Identify block group of inode
    … …  
    141210        }
    142211
     212        uint32_t block_group_count = ext4_superblock_get_block_group_count(fs->superblock);
    143213        uint32_t inode_table_first_block = ext4_block_group_get_inode_table_first_block(bg_ref->block_group);
    144214        uint16_t inode_table_item_size = ext4_superblock_get_inode_size(fs->superblock);
    145         uint32_t inode_table_bytes = inodes_per_group * inode_table_item_size;
     215        uint32_t inode_table_bytes;
     216
     217        if (block_group < block_group_count - 1) {
     218                inode_table_bytes = inodes_per_group * inode_table_item_size;
     219        } else {
     220                // last block group could be smaller
     221                uint32_t inodes_count_total = ext4_superblock_get_inodes_count(fs->superblock);
     222                inode_table_bytes =
     223                                (inodes_count_total - ((block_group_count - 1) * inodes_per_group))
     224                                * inode_table_item_size;
     225        }
     226
    146227        uint32_t inode_table_blocks = inode_table_bytes / block_size;
    147228
    … …  
    157238}
    158239
    159 int ext4_bitmap_alloc_block(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t *fblock)
     240int ext4_balloc_alloc_block(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t *fblock)
    160241{
    161242        int rc;
    162         ext4_block_group_ref_t *bg_ref;
     243        uint32_t allocated_block = 0;
     244
    163245        uint32_t bitmap_block;
    164246        block_t *block;
    165247        uint32_t rel_block_idx = 0;
    166         uint32_t index_in_group;
    167         uint32_t tmp;
    168 
    169         uint32_t allocated_block = 0;
    170 
    171         // Determine GOAL
    172         uint32_t goal = ext4_bitmap_find_goal(fs, inode_ref);
    173 
    174         uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
    175 
    176         //if (goal == 0) - unable to determine goal
     248
     249        // Find GOAL
     250        uint32_t goal = ext4_balloc_find_goal(fs, inode_ref);
    177251        if (goal == 0) {
    178252                // TODO
    179253                EXT4FS_DBG("ERRORR (goal == 0)");
    180         }
    181 
    182 //      EXT4FS_DBG("goal = \%u", goal);
    183 
    184         uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(fs->superblock);
    185         uint32_t first_block = ext4_superblock_get_first_data_block(fs->superblock);
    186 
    187         uint32_t block_group;
    188 
    189         // First block == 0 or 1
    190         if (first_block == 0) {
    191                 block_group = goal / blocks_per_group;
    192                 index_in_group = goal % blocks_per_group;
    193         } else {
    194                 block_group = (goal - 1) / blocks_per_group;
    195                 index_in_group = (goal - 1) % blocks_per_group;
    196         }
    197 
    198 
     254                return ENOSPC;
     255        }
     256
     257        // Load block group number for goal and relative index
     258        uint32_t block_group = ext4_balloc_get_bgid_of_block(fs->superblock, goal);
     259        uint32_t index_in_group = ext4_balloc_blockaddr2_index_in_group(fs->superblock, goal);
    199260//      EXT4FS_DBG("block_group = \%u, index_in_group = \%u", block_group, index_in_group);
    200261
     262
     263
     264        ext4_block_group_ref_t *bg_ref;
    201265        rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
    202266        if (rc != EOK) {
    203                 return rc;
     267                EXT4FS_DBG("initial BG ref not loaded");
     268                return rc;
     269        }
     270
     271        uint32_t first_in_group =
     272                        ext4_balloc_get_first_data_block_in_group(fs->superblock,
     273                                        bg_ref->block_group, block_group);
     274
     275        if (index_in_group < first_in_group) {
     276                index_in_group = first_in_group;
    204277        }
    205278
    … …  
    210283        if (rc != EOK) {
    211284                ext4_filesystem_put_block_group_ref(bg_ref);
     285                EXT4FS_DBG("initial bitmap not loaded");
    212286                return rc;
    213287        }
    … …  
    215289//      EXT4FS_DBG("bitmap loaded");
    216290
     291        // Check if goal is free
    217292        if (ext4_bitmap_is_free_bit(block->data, index_in_group)) {
    218 
    219 //              EXT4FS_DBG("goal is free");
    220 
    221293                ext4_bitmap_set_bit(block->data, index_in_group);
    222294                block->dirty = true;
    … …  
    224296                if (rc != EOK) {
    225297                        // TODO error
    226                         EXT4FS_DBG("error in saving bitmap \%d", rc);
     298                        EXT4FS_DBG("goal check: error in saving initial bitmap \%d", rc);
     299                        ext4_filesystem_put_block_group_ref(bg_ref);
     300                        return rc;
    227301                }
    228302
    229303                allocated_block = goal;
    230                 goto end;
    231 
    232         }
    233 
    234 //      EXT4FS_DBG("try 63 blocks after goal");
     304                goto success;
     305
     306        }
     307
     308        uint32_t blocks_in_group = ext4_superblock_get_blocks_in_group(fs->superblock, block_group);
     309
     310//      EXT4FS_DBG("index = \%u (goal = \%u), blocks_in_group = \%u", index_in_group, goal, blocks_in_group);
     311
     312        uint32_t end_idx = (index_in_group + 63) & ~63;
     313        if (end_idx > blocks_in_group) {
     314                end_idx = blocks_in_group;
     315        }
     316
    235317        // Try to find free block near to goal
    236         for (tmp = index_in_group + 1; (tmp < blocks_per_group) && (tmp < ((index_in_group + 63) & ~63)); ++tmp) {
    237 
    238 //              EXT4FS_DBG("trying \%u", tmp);
    239 
    240                 if (ext4_bitmap_is_free_bit(block->data, tmp)) {
    241 
    242 //                      EXT4FS_DBG("block \%u is free -> allocate it", tmp);
    243 
    244                         ext4_bitmap_set_bit(block->data, tmp);
     318        for (uint32_t tmp_idx = index_in_group + 1; tmp_idx < end_idx; ++tmp_idx) {
     319                if (ext4_bitmap_is_free_bit(block->data, tmp_idx)) {
     320
     321                        ext4_bitmap_set_bit(block->data, tmp_idx);
     322                        block->dirty = true;
     323                        rc = block_put(block);
     324                        if (rc != EOK) {
     325                                // TODO error
     326                                EXT4FS_DBG("near blocks: error in saving initial bitmap \%d", rc);
     327                        }
     328
     329                        allocated_block = ext4_balloc_index_in_group2blockaddr(
     330                                        fs->superblock, tmp_idx, block_group);
     331
     332
     333//                      EXT4FS_DBG("block \%u (idx = \%u) allocated, goal = \%u", allocated_block, tmp_idx, goal);
     334
     335                        goto success;
     336                }
     337
     338        }
     339
     340        // Find free BYTE in bitmap
     341//      EXT4FS_DBG("try find free byte in own BG");
     342        rc = ext4_bitmap_find_free_byte_and_set_bit(block->data, index_in_group, &rel_block_idx, blocks_in_group);
     343        if (rc == EOK) {
     344                block->dirty = true;
     345                rc = block_put(block);
     346                if (rc != EOK) {
     347                        // TODO error
     348                        EXT4FS_DBG("free byte: error in saving initial bitmap \%d", rc);
     349                }
     350
     351                allocated_block = ext4_balloc_index_in_group2blockaddr(
     352                                fs->superblock, rel_block_idx, block_group);
     353
     354//              EXT4FS_DBG("block \%u allocated, index = \%u, goal = \%u", allocated_block, rel_block_idx, goal);
     355
     356                goto success;
     357        }
     358
     359        // Find free bit in bitmap
     360        EXT4FS_DBG("find free bit");
     361        rc = ext4_bitmap_find_free_bit_and_set(block->data, index_in_group, &rel_block_idx, blocks_in_group);
     362        if (rc == EOK) {
     363                block->dirty = true;
     364                rc = block_put(block);
     365                if (rc != EOK) {
     366                        // TODO error
     367                        EXT4FS_DBG("free bit: error in saving initial bitmap \%d", rc);
     368                }
     369
     370                allocated_block = ext4_balloc_index_in_group2blockaddr(
     371                                fs->superblock, rel_block_idx, block_group);
     372
     373                EXT4FS_DBG("find free bit: block \%u allocated, index = \%u, goal = \%u", allocated_block, rel_block_idx, goal);
     374
     375                goto success;
     376        }
     377
     378        block_put(block);
     379        ext4_filesystem_put_block_group_ref(bg_ref);
     380
     381        // Try other block groups
     382        uint32_t block_group_count = ext4_superblock_get_block_group_count(fs->superblock);
     383
     384        uint32_t bgid = (block_group + 1) % block_group_count;
     385        uint32_t count = block_group_count;
     386
     387        while (count > 0) {
     388                EXT4FS_DBG("trying group \%u", bgid);
     389
     390                rc = ext4_filesystem_get_block_group_ref(fs, bgid, &bg_ref);
     391                if (rc != EOK) {
     392                        EXT4FS_DBG("errrrrrrrrrrr");
     393                        return rc;
     394                }
     395
     396                // Load bitmap
     397                bitmap_block = ext4_block_group_get_block_bitmap(bg_ref->block_group);
     398
     399                rc = block_get(&block, fs->device, bitmap_block, 0);
     400                if (rc != EOK) {
     401                        ext4_filesystem_put_block_group_ref(bg_ref);
     402                        EXT4FS_DBG("errrrrrrrrrr");
     403                        return rc;
     404                }
     405
     406                first_in_group = ext4_balloc_get_first_data_block_in_group(
     407                                fs->superblock, bg_ref->block_group, bgid);
     408                index_in_group = ext4_balloc_blockaddr2_index_in_group(fs->superblock,
     409                                                first_in_group);
     410                blocks_in_group = ext4_superblock_get_blocks_in_group(fs->superblock, bgid);
     411
     412                if (index_in_group < first_in_group) {
     413                        index_in_group = first_in_group;
     414                }
     415
     416//              EXT4FS_DBG("trying free byte in bg \%u", bgid);
     417                rc = ext4_bitmap_find_free_byte_and_set_bit(block->data, index_in_group, &rel_block_idx, blocks_in_group);
     418                if (rc == EOK) {
    245419                        block->dirty = true;
    246420                        rc = block_put(block);
    … …  
    250424                        }
    251425
    252                         if (first_block == 0) {
    253                                 allocated_block = blocks_per_group * block_group + tmp;
    254                         } else {
    255                                 allocated_block = blocks_per_group * block_group + tmp + 1;
     426                        allocated_block = ext4_balloc_index_in_group2blockaddr(
     427                                        fs->superblock, rel_block_idx, bgid);
     428
     429                        EXT4FS_DBG("byte: block \%u allocated, index = \%u, goal = \%u", allocated_block, rel_block_idx, goal);
     430
     431                        goto success;
     432                }
     433
     434                // Find free bit in bitmap
     435                rc = ext4_bitmap_find_free_bit_and_set(block->data, index_in_group, &rel_block_idx, blocks_in_group);
     436//              EXT4FS_DBG("trying free bit in bg \%u", bgid);
     437                if (rc == EOK) {
     438                        block->dirty = true;
     439                        rc = block_put(block);
     440                        if (rc != EOK) {
     441                                // TODO error
     442                                EXT4FS_DBG("error in saving bitmap \%d", rc);
    256443                        }
    257444
    258                         goto end;
    259                 }
    260         }
    261 
    262 //      EXT4FS_DBG("try find free byte");
    263 
    264         // Find free BYTE in bitmap
    265         rc = ext4_bitmap_find_free_byte_and_set_bit(block->data, index_in_group, &rel_block_idx, block_size);
    266         if (rc == EOK) {
    267                 block->dirty = true;
    268                 rc = block_put(block);
    269                 if (rc != EOK) {
    270                         // TODO error
    271                         EXT4FS_DBG("error in saving bitmap \%d", rc);
    272                 }
    273 
    274                 if (first_block == 0) {
    275                         allocated_block = blocks_per_group * block_group + rel_block_idx;
    276                 } else {
    277                         allocated_block = blocks_per_group * block_group + rel_block_idx + 1;
    278                 }
    279 
    280                 goto end;
    281         }
    282 
    283 //      EXT4FS_DBG("try find free bit");
    284 
    285         // Find free bit in bitmap
    286         rc = ext4_bitmap_find_free_bit_and_set(block->data, index_in_group, &rel_block_idx, block_size);
    287         if (rc == EOK) {
    288                 block->dirty = true;
    289                 rc = block_put(block);
    290                 if (rc != EOK) {
    291                         // TODO error
    292                         EXT4FS_DBG("error in saving bitmap \%d", rc);
    293                 }
    294 
    295                 if (first_block == 0) {
    296                         allocated_block = blocks_per_group * block_group + rel_block_idx;
    297                 } else {
    298                         allocated_block = blocks_per_group * block_group + rel_block_idx + 1;
    299                 }
    300 
    301                 goto end;
    302         }
    303 
    304 
    305         // TODO Try other block groups
    306         EXT4FS_DBG("try other block group");
     445                        allocated_block = ext4_balloc_index_in_group2blockaddr(
     446                                        fs->superblock, rel_block_idx, bgid);
     447
     448                        EXT4FS_DBG("bit: block \%u allocated, index = \%u, goal = \%u", allocated_block, rel_block_idx, goal);
     449
     450                        goto success;
     451                }
     452
     453
     454                // Next group
     455                block_put(block);
     456                ext4_filesystem_put_block_group_ref(bg_ref);
     457                bgid = (bgid + 1) % block_group_count;
     458                count--;
     459        }
     460
     461        EXT4FS_DBG("No free block found");
    307462        return ENOSPC;
    308463
    309 end:
     464success:
    310465
    311466        ;
    312467//      EXT4FS_DBG("returning block \%u", allocated_block);
     468
     469        uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
    313470
    314471        // TODO decrement superblock free blocks count
    … …  
    329486        ext4_filesystem_put_block_group_ref(bg_ref);
    330487
    331 //      EXT4FS_DBG("block \%u allocated", blocks_per_group * block_group + rel_block_idx + 1);
    332 
    333 
     488//      if (goal > 1980)
     489//              EXT4FS_DBG("block \%u allocated", allocated_block);
    334490
    335491        *fblock = allocated_block;
    336492        return EOK;
    337493}
    338 
    339 
    340 /**
    341  * @file        libext4_balloc.c
    342  * @brief       TODO
    343  */
    344 
    345494
    346495
Note: See TracChangeset for help on using the changeset viewer.