Changeset 2674db6 in mainline


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

New block allocation algorithm (from ext2)

Location:
uspace/lib/ext4
Files:
2 added
5 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/ext4/Makefile

    ra9bbce7d r2674db6  
    3333
    3434SOURCES = \
     35        libext4_balloc.c \
    3536        libext4_bitmap.c \
    3637        libext4_block_group.c \

  • uspace/lib/ext4/libext4.h

    ra9bbce7d r2674db6  
    3434#define LIBEXT4_LIBEXT4_H_
    3535
     36#include "libext4_balloc.h"
    3637#include "libext4_bitmap.h"
    3738#include "libext4_block_group.h"

  • uspace/lib/ext4/libext4_bitmap.c

    ra9bbce7d r2674db6  
    3333/**
    3434 * @file        libext4_bitmap.c
    35  * @brief       Ext4 bitmap (block & inode) operations.
     35 * @brief       Ext4 bitmap operations.
    3636 */
    3737
    … …  
    4141#include "libext4.h"
    4242
    43 static void ext4_bitmap_free_bit(uint8_t *bitmap, uint32_t index)
     43void ext4_bitmap_free_bit(uint8_t *bitmap, uint32_t index)
    4444{
    45         // Block numbers are 1-based
    4645        uint32_t byte_index = index / 8;
    4746        uint32_t bit_index = index % 8;
    4847
    49 //      EXT4FS_DBG("freeing block \%u, byte \%u and bit \%u", index, byte_index, bit_index);
     48        uint8_t *target = bitmap + byte_index;
     49
     50        *target &= ~ (1 << bit_index);
     51}
     52
     53void ext4_bitmap_set_bit(uint8_t *bitmap, uint32_t index)
     54{
     55        uint32_t byte_index = index / 8;
     56        uint32_t bit_index = index % 8;
    5057
    5158        uint8_t *target = bitmap + byte_index;
    52         uint8_t old_value = *target;
    5359
    54         uint8_t new_value = old_value & (~ (1 << bit_index));
    55 
    56         *target = new_value;
     60        *target |= 1 << bit_index;
    5761}
    5862
    59 static int ext4_bitmap_find_free_bit_and_set(uint8_t *bitmap, uint32_t *index, uint32_t size)
     63bool ext4_bitmap_is_free_bit(uint8_t *bitmap, uint32_t index)
    6064{
    61         uint8_t *pos = bitmap;
     65        uint32_t byte_index = index / 8;
     66        uint32_t bit_index = index % 8;
     67
     68        uint8_t *target = bitmap + byte_index;
     69
     70        if (*target & (1 << bit_index)) {
     71                return false;
     72        } else {
     73                return true;
     74        }
     75
     76}
     77
     78int ext4_bitmap_find_free_byte_and_set_bit(uint8_t *bitmap, uint32_t start, uint32_t *index, uint32_t size)
     79{
     80        uint8_t *pos = bitmap + (start / 8) + 1;
     81
     82        while (pos < bitmap + size) {
     83                if (*pos == 0) {
     84                        *pos |= 1;
     85
     86                        *index = (pos - bitmap) * 8;
     87                        return EOK;
     88                }
     89
     90                ++pos;
     91        }
     92
     93        return ENOSPC;
     94
     95}
     96
     97int ext4_bitmap_find_free_bit_and_set(uint8_t *bitmap, uint32_t start, uint32_t *index, uint32_t size)
     98{
     99        uint8_t *pos = bitmap + (start / 8);
    62100        int i;
    63         uint32_t idx = 0;
    64101        uint8_t value, new_value;
    65102
    … …  
    71108
    72109                ++pos;
    73                 idx += 8;
     110        }
     111
     112        // Check the byte containing start
     113        if (pos == bitmap + (start / 8)) {
     114                for (i = start % 8; i < 8; ++i) {
     115                        value = *pos;
     116                        if ((value & (1 << i)) == 0) {
     117                                // free bit found
     118                                new_value = value | (1 << i);
     119                                *pos = new_value;
     120                                *index = (pos - bitmap) * 8 + i;
     121                                return EOK;
     122                        }
     123                }
    74124        }
    75125
    76126        if (pos < bitmap + size) {
    77 
    78 //              EXT4FS_DBG("byte found \%u", (uint32_t)(pos - bitmap));
    79127
    80128                for(i = 0; i < 8; ++i) {
    … …  
    83131                        if ((value & (1 << i)) == 0) {
    84132                                // free bit found
    85 //                              EXT4FS_DBG("bit found \%u", i);
    86133                                new_value = value | (1 << i);
    87134                                *pos = new_value;
    88                                 *index = idx + i;
     135                                *index = (pos - bitmap) * 8 + i;
    89136                                return EOK;
    90137                        }
    … …  
    95142}
    96143
    97 int ext4_bitmap_free_block(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t block_index)
    98 {
    99         int rc;
    100         uint32_t blocks_per_group;
    101         uint32_t block_group;
    102         uint32_t index_in_group;
    103         uint32_t bitmap_block;
    104         uint32_t block_size;
    105         ext4_block_group_ref_t *bg_ref;
    106         block_t *block;
    107 
    108         block_size = ext4_superblock_get_block_size(fs->superblock);
    109 
    110         blocks_per_group = ext4_superblock_get_blocks_per_group(fs->superblock);
    111         block_group = ((block_index - 1) / blocks_per_group);
    112         index_in_group = (block_index - 1) % blocks_per_group;
    113 
    114         rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
    115         if (rc != EOK) {
    116                 return rc;
    117         }
    118 
    119         bitmap_block = ext4_block_group_get_block_bitmap(bg_ref->block_group);
    120 
    121         rc = block_get(&block, fs->device, bitmap_block, 0);
    122         if (rc != EOK) {
    123                 return rc;
    124         }
    125 
    126         ext4_bitmap_free_bit(block->data, index_in_group);
    127 
    128         block->dirty = true;
    129         rc = block_put(block);
    130         if (rc != EOK) {
    131                 return rc;
    132         }
    133 
    134         uint64_t ino_blocks = ext4_inode_get_blocks_count(fs->superblock, inode_ref->inode);
    135         ino_blocks -= block_size / EXT4_INODE_BLOCK_SIZE;
    136         ext4_inode_set_blocks_count(fs->superblock, inode_ref->inode, ino_blocks);
    137         inode_ref->dirty = true;
    138 
    139         uint32_t free_blocks = ext4_block_group_get_free_blocks_count(bg_ref->block_group);
    140         free_blocks++;
    141         ext4_block_group_set_free_blocks_count(bg_ref->block_group, free_blocks);
    142         bg_ref->dirty = true;
    143 
    144         // TODO change free blocks count in superblock
    145 
    146         rc = ext4_filesystem_put_block_group_ref(bg_ref);
    147         if (rc != EOK) {
    148                 EXT4FS_DBG("error in saving bg_ref \%d", rc);
    149                 // TODO error
    150                 return rc;
    151         }
    152 
    153 //      EXT4FS_DBG("block \%u released", block_index);
    154 
    155         return EOK;
    156 }
    157 
    158 int ext4_bitmap_alloc_block(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t *fblock)
    159 {
    160         int rc;
    161         uint32_t inodes_per_group, block_group, blocks_per_group;
    162         ext4_block_group_ref_t *bg_ref;
    163         uint32_t bitmap_block;
    164         block_t *block;
    165         uint32_t rel_block_idx = 0;
    166         uint32_t block_size;
    167 
    168         inodes_per_group = ext4_superblock_get_inodes_per_group(fs->superblock);
    169         block_group = (inode_ref->index - 1) / inodes_per_group;
    170 
    171         block_size = ext4_superblock_get_block_size(fs->superblock);
    172 
    173         rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
    174         if (rc != EOK) {
    175                 return rc;
    176         }
    177 
    178         bitmap_block = ext4_block_group_get_block_bitmap(bg_ref->block_group);
    179 
    180         rc = block_get(&block, fs->device, bitmap_block, 0);
    181         if (rc != EOK) {
    182                 ext4_filesystem_put_block_group_ref(bg_ref);
    183                 return rc;
    184         }
    185 
    186         rc = ext4_bitmap_find_free_bit_and_set(block->data, &rel_block_idx, block_size);
    187         if (rc != EOK) {
    188                 EXT4FS_DBG("no free block found");
    189                 // TODO if ENOSPC - try next block groups
    190         }
    191 
    192         block->dirty = true;
    193 
    194         rc = block_put(block);
    195         if (rc != EOK) {
    196                 // TODO error
    197                 EXT4FS_DBG("error in saving bitmap \%d", rc);
    198         }
    199 
    200         // TODO decrement superblock free blocks count
    201         //uint32_t sb_free_blocks = ext4_superblock_get_free_blocks_count(sb);
    202         //sb_free_blocks--;
    203         //ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
    204 
    205         uint64_t ino_blocks = ext4_inode_get_blocks_count(fs->superblock, inode_ref->inode);
    206         ino_blocks += block_size / EXT4_INODE_BLOCK_SIZE;
    207         ext4_inode_set_blocks_count(fs->superblock, inode_ref->inode, ino_blocks);
    208         inode_ref->dirty = true;
    209 
    210         uint32_t bg_free_blocks = ext4_block_group_get_free_blocks_count(bg_ref->block_group);
    211         bg_free_blocks--;
    212         ext4_block_group_set_free_blocks_count(bg_ref->block_group, bg_free_blocks);
    213         bg_ref->dirty = true;
    214 
    215         ext4_filesystem_put_block_group_ref(bg_ref);
    216 
    217         blocks_per_group = ext4_superblock_get_blocks_per_group(fs->superblock);
    218 
    219 //      EXT4FS_DBG("block \%u allocated", blocks_per_group * block_group + rel_block_idx + 1);
    220 
    221         *fblock = blocks_per_group * block_group + rel_block_idx + 1;
    222         return EOK;
    223 
    224 }
    225 
    226144/**
    227145 * @}

  • uspace/lib/ext4/libext4_bitmap.h

    ra9bbce7d r2674db6  
    3535
    3636#include <sys/types.h>
    37 #include "libext4_filesystem.h"
    3837
    39 extern int ext4_bitmap_free_block(ext4_filesystem_t *,
    40                 ext4_inode_ref_t *, uint32_t);
    41 extern int ext4_bitmap_alloc_block(ext4_filesystem_t *,
    42                 ext4_inode_ref_t *, uint32_t *);
     38extern void ext4_bitmap_free_bit(uint8_t *, uint32_t);
     39extern void ext4_bitmap_set_bit(uint8_t *, uint32_t);
     40extern bool ext4_bitmap_is_free_bit(uint8_t *, uint32_t);
     41extern int ext4_bitmap_find_free_byte_and_set_bit(uint8_t *, uint32_t,
     42                uint32_t *, uint32_t);
     43extern int ext4_bitmap_find_free_bit_and_set(uint8_t *, uint32_t,
     44                uint32_t *, uint32_t);
     45
    4346#endif
    4447

  • uspace/lib/ext4/libext4_filesystem.c

    ra9bbce7d r2674db6  
    7272
    7373        /* Initialize block caching */
    74         rc = block_cache_init(service_id, block_size, 0, CACHE_MODE_WT);
     74        // TODO set cache MODE to write through (now writeback for faster testing)
     75        rc = block_cache_init(service_id, block_size, 0, CACHE_MODE_WB);
    7576        if (rc != EOK) {
    7677                block_fini(fs->device);
    … …  
    465466                                if (rc != EOK) {
    466467                                        // TODO error
     468                                        EXT4FS_DBG("allocation error");
    467469                                }
    468470
Note: See TracChangeset for help on using the changeset viewer.