fs/ext2/balloc.c

/* */
This source file includes following definitions.
read_block_bitmap
load_block_bitmap
ext2_free_block
ext2_new_block
ext2_count_free_blocks
   1 /*
   2  *  linux/fs/ext2/balloc.c
   3  *
   4  *  Copyright (C) 1992, 1993  Remy Card (card@masi.ibp.fr)
   5  *
   6  */
   7 
   8 /* balloc.c contains the blocks allocation and deallocation routines */
   9 
  10 /*
  11 
  12    The free blocks are managed by bitmaps.  A file system contains several
  13    blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
  14    block for inodes, N blocks for the inode table and data blocks.
  15 
  16    The file system contains group descriptors which are located after the
  17    super block.  Each descriptor contains the number of the bitmap block and
  18    the free blocks count in the block.  The descriptors are loaded in memory
  19    when a file system is mounted (see ext2_read_super).
  20 
  21 */
  22 
  23 #include <linux/sched.h>
  24 #include <linux/ext2_fs.h>
  25 #include <linux/stat.h>
  26 #include <linux/kernel.h>
  27 #include <linux/string.h>
  28 #include <linux/locks.h>
  29 
  30 #define clear_block(addr,size) \
  31         __asm__("cld\n\t" \
  32                 "rep\n\t" \
  33                 "stosl" \
  34                 : \
  35                 :"a" (0), "c" (size/4), "D" ((long) (addr)) \
  36                 :"cx", "di")
  37 
  38 #define set_bit(nr,addr) ( \
  39 { \
  40         char res; \
  41         __asm__ __volatile__("btsl %1,%2\n\tsetb %0" \
  42                              :"=q" (res) \
  43                              :"r" (nr),"m" (*(addr))); \
  44         res; \
  45 } \
  46 )
  47 
  48 #define clear_bit(nr,addr) ( \
  49 { \
  50         char res; \
  51         __asm__ __volatile__("btrl %1,%2\n\tsetnb %0" \
  52                              :"=q" (res) \
  53                              :"r" (nr),"m" (*(addr))); \
  54         res; \
  55 } \
  56 )
  57 
  58 #define find_first_zero(addr,size) ( \
  59 { \
  60         int __res; \
  61         __asm__("cld\n" \
  62                 "1:\tlodsl\n\t" \
  63                 "notl %%eax\n\t" \
  64                 "bsfl %%eax,%%edx\n\t" \
  65                 "jne 2f\n\t" \
  66                 "addl $32,%%ecx\n\t" \
  67                 "cmpl %%ebx,%%ecx\n\t" \
  68                 "jl 1b\n\t" \
  69                 "xorl %%edx,%%edx\n" \
  70                 "2:\taddl %%edx,%%ecx" \
  71                 :"=c" (__res):"0" (0), "S" (addr), "b" (size) \
  72                 :"ax", "bx", "dx", "si"); \
  73         __res; \
  74 } \
  75 )
  76 
  77 static void read_block_bitmap (struct super_block * sb,
     /*  */
  78                                unsigned int block_group,
  79                                unsigned long bitmap_nr)
  80 {
  81         unsigned long group_desc;
  82         unsigned long desc;
  83         struct ext2_group_desc * gdp;
  84         struct buffer_head * bh;
  85         
  86         group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
  87         desc = block_group % EXT2_DESC_PER_BLOCK(sb);
  88         if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
  89                 printk ("block_group = %d,group_desc = %d,desc = %d\n",
  90                          block_group, group_desc, desc);
  91                 panic ("read_block_bitmap: Group descriptor not loaded");
  92         }
  93         gdp = (struct ext2_group_desc *) sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
  94         bh = bread (sb->s_dev, gdp[desc].bg_block_bitmap, sb->s_blocksize);
  95         if (!bh) {
  96                 printk ("block_group = %d,group_desc = %d,desc = %d,block_bitmap = %d\n",
  97                         block_group, group_desc, desc, gdp[desc].bg_block_bitmap);
  98                 panic ("read_block_bitmap: Cannot read block bitmap");
  99         }
 100         sb->u.ext2_sb.s_block_bitmap_number[bitmap_nr] = block_group;
 101         sb->u.ext2_sb.s_block_bitmap[bitmap_nr] = bh;
 102 }
 103 
 104 /*
 105  * load_block_bitmap loads the block bitmap for a blocks group
 106  *
 107  * It maintains a cache for the last bitmaps loaded.  This cache is managed
 108  * with a LRU algorithm.
 109  *
 110  * Notes:
 111  * 1/ There is one cache per mounted file system.
 112  * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
 113  *    this function reads the bitmap without maintaining a LRU cache.
 114  */
 115 static int load_block_bitmap (struct super_block * sb,
     /*  */
 116                               unsigned int block_group)
 117 {
 118         int i, j;
 119         unsigned long block_bitmap_number;
 120         struct buffer_head * block_bitmap;
 121 
 122         if (block_group >= sb->u.ext2_sb.s_groups_count) {
 123                 printk ("block_group = %d, groups_count = %d\n",
 124                         block_group, sb->u.ext2_sb.s_groups_count);
 125                 panic ("load_block_bitmap: block_group >= groups_count");
 126         }
 127         if (sb->u.ext2_sb.s_loaded_block_bitmaps > 0 &&
 128             sb->u.ext2_sb.s_block_bitmap_number[0] == block_group)
 129                 return 0;
 130 
 131         if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED) {
 132                 if (sb->u.ext2_sb.s_block_bitmap[block_group]) {
 133                         if (sb->u.ext2_sb.s_block_bitmap_number[block_group] != block_group)
 134                                 panic ("load_block_bitmap: block_group != block_bitmap_number");
 135                         else
 136                                 return block_group;
 137                 } else {
 138                         read_block_bitmap (sb, block_group, block_group);
 139                         return block_group;
 140                 }
 141         }
 142 
 143         for (i = 0; i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
 144                     sb->u.ext2_sb.s_block_bitmap_number[i] != block_group; i++)
 145                 ;
 146         if (i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
 147             sb->u.ext2_sb.s_block_bitmap_number[i] == block_group) {
 148                 block_bitmap_number = sb->u.ext2_sb.s_block_bitmap_number[i];
 149                 block_bitmap = sb->u.ext2_sb.s_block_bitmap[i];
 150                 for (j = i; j > 0; j--) {
 151                         sb->u.ext2_sb.s_block_bitmap_number[j] =
 152                                 sb->u.ext2_sb.s_block_bitmap_number[j - 1];
 153                         sb->u.ext2_sb.s_block_bitmap[j] =
 154                                 sb->u.ext2_sb.s_block_bitmap[j - 1];
 155                 }
 156                 sb->u.ext2_sb.s_block_bitmap_number[0] = block_bitmap_number;
 157                 sb->u.ext2_sb.s_block_bitmap[0] = block_bitmap;
 158         } else {
 159                 if (sb->u.ext2_sb.s_loaded_block_bitmaps < EXT2_MAX_GROUP_LOADED)
 160                         sb->u.ext2_sb.s_loaded_block_bitmaps++;
 161                 else
 162                         brelse (sb->u.ext2_sb.s_block_bitmap[EXT2_MAX_GROUP_LOADED - 1]);
 163                 for (j = sb->u.ext2_sb.s_loaded_block_bitmaps - 1; j > 0;  j--) {
 164                         sb->u.ext2_sb.s_block_bitmap_number[j] =
 165                                 sb->u.ext2_sb.s_block_bitmap_number[j - 1];
 166                         sb->u.ext2_sb.s_block_bitmap[j] =
 167                                 sb->u.ext2_sb.s_block_bitmap[j - 1];
 168                 }
 169                 read_block_bitmap (sb, block_group, 0);
 170         }
 171         return 0;
 172 }
 173 
 174 void ext2_free_block (struct super_block * sb, unsigned long block)
     /*  */
 175 {
 176         struct buffer_head * bh;
 177         struct buffer_head * bh2;
 178         unsigned long block_group;
 179         unsigned long bit;
 180         unsigned long group_desc;
 181         unsigned long desc;
 182         int bitmap_nr;
 183         struct ext2_group_desc * gdp;
 184         struct ext2_super_block * es;
 185 
 186         if (!sb) {
 187                 printk ("ext2_free_block: nonexistant device");
 188                 return;
 189         }
 190         lock_super (sb);
 191         if (block < sb->u.ext2_sb.s_first_data_block ||
 192             block >= sb->u.ext2_sb.s_blocks_count) {
 193                 printk ("ext2_free_block: block not in datazone\n");
 194                 unlock_super (sb);
 195                 return;
 196         }
 197         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 198 #ifdef EXT2FS_DEBUG
 199         printk ("ext2_free_block: freeing block %d\n", block);
 200 #endif
 201         bh = get_hash_table (sb->s_dev, block, sb->s_blocksize);
 202         if (bh)
 203                 bh->b_dirt = 0;
 204         brelse (bh);
 205         block_group = (block - sb->u.ext2_sb.s_first_data_block) /
 206                       EXT2_BLOCKS_PER_GROUP(sb);
 207         bit = (block - sb->u.ext2_sb.s_first_data_block) %
 208                 EXT2_BLOCKS_PER_GROUP(sb);
 209         bitmap_nr = load_block_bitmap (sb, block_group);
 210         bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
 211         if (!bh) {
 212                 printk ("block_group = %d\n", block_group);
 213                 panic ("ext2_free_block: Unable to load group bitmap");
 214         }
 215         if (clear_bit (bit, bh->b_data))
 216                 printk ("ext2_free_block (%04x:%d): bit already cleared\n",
 217                         sb->s_dev, block);
 218         else {
 219                 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
 220                 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
 221                 bh2 = sb->u.ext2_sb.s_group_desc[group_desc];
 222                 if (!bh2) {
 223                         printk ("group_desc = %d\n", group_desc);
 224                         panic ("ext2_free_block: Group descriptor not loaded");
 225                 }
 226                 gdp = (struct ext2_group_desc *) bh2->b_data;
 227                 gdp[desc].bg_free_blocks_count ++;
 228                 bh2->b_dirt = 1;
 229         }
 230         bh->b_dirt = 1;
 231         es->s_free_blocks_count ++;
 232         sb->u.ext2_sb.s_sbh->b_dirt = 1;
 233         sb->s_dirt = 1;
 234         unlock_super (sb);
 235         return;
 236 }
 237 
 238 /*
 239  * ext2_new_block does not use a very clever allocation algorithm yet
 240  *
 241  * Currently, the group descriptors are scanned until a free block is found
 242  */
 243 int ext2_new_block (struct super_block * sb, unsigned long block_group)
     /*  */
 244 {
 245         struct buffer_head * bh;
 246         int i, j;
 247         unsigned long group_desc;
 248         unsigned long desc;
 249         int bitmap_nr;
 250         struct ext2_group_desc * gdp;
 251         struct ext2_super_block * es;
 252 
 253         if (!sb) {
 254                 printk ("ext2_new_block: nonexistant device");
 255                 return 0;
 256         }
 257         lock_super (sb);
 258         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 259         if (es->s_free_blocks_count <= es->s_r_blocks_count && !suser()) {
 260                 unlock_super (sb);
 261                 return 0;
 262         }
 263         
 264 repeat:
 265         group_desc = 0;
 266         desc = 0;
 267         gdp = NULL;
 268         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 269                 if (!gdp) {
 270                         if (!sb->u.ext2_sb.s_group_desc[group_desc])
 271                                 panic ("ext2_new_block: Descriptor not loaded");
 272                         gdp = (struct ext2_group_desc *) sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
 273                 }
 274                 if (gdp[desc].bg_free_blocks_count > 0)
 275                         break;
 276                 desc ++;
 277                 if (desc == EXT2_DESC_PER_BLOCK(sb)) {
 278                         group_desc ++;
 279                         desc = 0;
 280                         gdp = NULL;
 281                 }
 282         }
 283         if (i >= sb->u.ext2_sb.s_groups_count) {
 284                 unlock_super (sb);
 285                 return 0;
 286         }
 287 #ifdef EXT2FS_DEBUG
 288         printk ("ext2_new_block: using block group %d(%d,%d,%d)\n", 
 289                 i, group_desc, desc, gdp[desc].bg_free_blocks_count);
 290 #endif
 291         bitmap_nr = load_block_bitmap (sb, i);
 292         bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
 293         if (!bh) {
 294                 printk ("block_group = %d\n", i);
 295                 panic ("ext2_new_block: Unable to load group bitmap");
 296         }
 297         if ((j = find_first_zero (bh->b_data, EXT2_BLOCKS_PER_GROUP(sb))) <
 298             EXT2_BLOCKS_PER_GROUP(sb)) {
 299                 if (set_bit (j, bh->b_data)) {
 300                         printk ("ext2_new_block: bit already set\n");
 301                         goto repeat;
 302                 }
 303                 bh->b_dirt = 1;
 304         } else
 305                 goto repeat;
 306 #ifdef EXT2FS_DEBUG
 307         printk ("ext2_new_block: found bit %d\n", j);
 308 #endif
 309         j += i * EXT2_BLOCKS_PER_GROUP(sb) +
 310                 sb->u.ext2_sb.s_first_data_block;
 311         if (j >= sb->u.ext2_sb.s_blocks_count) {
 312                 printk ("block_group = %d,block=%d\n", i, j);
 313                 printk ("ext2_new_block: block >= blocks count");
 314                 return 0;
 315         }
 316         if (!(bh = getblk (sb->s_dev, j, sb->s_blocksize))) {
 317                 printk ("ext2_new_block: cannot get block");
 318                 unlock_super (sb);
 319                 return 0;
 320         }
 321         clear_block (bh->b_data, sb->s_blocksize);
 322         bh->b_uptodate = 1;
 323         bh->b_dirt = 1;
 324         brelse (bh);
 325 #ifdef EXT2FS_DEBUG
 326         printk("ext2_new_block: allocating block %d\n", j);
 327 #endif
 328         gdp[desc].bg_free_blocks_count --;
 329         sb->u.ext2_sb.s_group_desc[group_desc]->b_dirt = 1;
 330         es->s_free_blocks_count --;
 331         sb->u.ext2_sb.s_sbh->b_dirt = 1;
 332         sb->s_dirt = 1;
 333         unlock_super (sb);
 334         return j;
 335 }
 336 
 337 unsigned long ext2_count_free_blocks (struct super_block *sb)
     /*  */
 338 {
 339         struct ext2_super_block * es;
 340 #ifdef EXT2FS_DEBUG
 341         unsigned long desc_count, bitmap_count, x;
 342         unsigned long group_desc;
 343         unsigned long desc;
 344         int bitmap_nr;
 345         struct ext2_group_desc * gdp;
 346         int i;
 347 
 348         lock_super (sb);
 349         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 350         desc_count = 0;
 351         bitmap_count = 0;
 352         group_desc = 0;
 353         desc = 0;
 354         gdp = NULL;
 355         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 356                 if (!gdp) {
 357                         if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
 358                                 printk ("ext2_count_free_block: Descriptor not loaded\n");
 359                                 break;
 360                         }
 361                         gdp = (struct ext2_group_desc *) sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
 362                 }
 363                 desc_count += gdp[desc].bg_free_blocks_count;
 364                 bitmap_nr = load_block_bitmap (sb, i);
 365                 if (sb->u.ext2_sb.s_block_bitmap[bitmap_nr])
 366                         x = ext2_count_free (sb->u.ext2_sb.s_block_bitmap[bitmap_nr],
 367                                                sb->s_blocksize);
 368                 else {
 369                         x = 0;
 370                         printk ("Cannot load bitmap for group %d\n", i);
 371                 }
 372                 printk ("group %d: stored = %d, counted = %d\n",
 373                         i, gdp[desc].bg_free_blocks_count, x);
 374                 bitmap_count += x;
 375                 desc ++;
 376                 if (desc == EXT2_DESC_PER_BLOCK(sb)) {
 377                         group_desc ++;
 378                         desc = 0;
 379                         gdp = NULL;
 380                 }
 381         }
 382         printk("ext2_count_free_blocks: stored = %d, computed = %d, %d\n",
 383                 es->s_free_blocks_count, desc_count, bitmap_count);
 384         unlock_super (sb);
 385         return bitmap_count;
 386 #else
 387         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 388         return es->s_free_blocks_count;
 389 #endif
 390 }
/* */
root/fs/ext2/balloc.c

DEFINITIONS
