servers/ext2/balloc.c

   1 /* This files manages blocks allocation and deallocation.
   2  *
   3  * The entry points into this file are:
   4  *   discard_preallocated_blocks:       Discard preallocated blocks.
   5  *   alloc_block:       somebody wants to allocate a block; find one.
   6  *   free_block:        indicate that a block is available for new allocation.
   7  *
   8  * Created:
   9  *   June 2010 (Evgeniy Ivanov)
  10  */
  11
  12 #include "fs.h"
  13 #include <string.h>
  14 #include <stdlib.h>
  15 #include <minix/com.h>
  16 #include <minix/u64.h>
  17 #include "buf.h"
  18 #include "inode.h"
  19 #include "super.h"
  20 #include "const.h"
  21
  22
  23 static block_t alloc_block_bit(struct super_block *sp, block_t origin,
  24         struct inode *rip);
  25
  26 /*===========================================================================*
  27  *                      discard_preallocated_blocks                          *
  28  *===========================================================================*/
  29 void discard_preallocated_blocks(struct inode *rip)
  30 {
  31 /* When called for rip, discard (free) blocks preallocated for rip,
  32  * otherwise discard all preallocated blocks.
  33  * Normally it should be called in following situations:
  34  * 1. File is closed.
  35  * 2. File is truncated.
  36  * 3. Non-sequential write.
  37  * 4. inode is "unloaded" from the memory.
  38  * 5. No free blocks left (discard all preallocated blocks).
  39  */
  40   int i;
  41
  42   if (rip) {
  43         rip->i_prealloc_count = rip->i_prealloc_index = 0;
  44         for (i = 0; i < EXT2_PREALLOC_BLOCKS; i++) {
  45                 if (rip->i_prealloc_blocks[i] != NO_BLOCK) {
  46                         free_block(rip->i_sp, rip->i_prealloc_blocks[i]);
  47                         rip->i_prealloc_blocks[i] = NO_BLOCK;
  48                 }
  49         }
  50         return;
  51   }
  52
  53   /* Discard all allocated blocks.
  54    * Probably there are just few blocks on the disc, so forbid preallocation.*/
  55   for(rip = &inode[0]; rip < &inode[NR_INODES]; rip++) {
  56         rip->i_prealloc_count = rip->i_prealloc_index = 0;
  57         rip->i_preallocation = 0; /* forbid preallocation */
  58         for (i = 0; i < EXT2_PREALLOC_BLOCKS; i++) {
  59                 if (rip->i_prealloc_blocks[i] != NO_BLOCK) {
  60                         free_block(rip->i_sp, rip->i_prealloc_blocks[i]);
  61                         rip->i_prealloc_blocks[i] = NO_BLOCK;
  62                 }
  63         }
  64   }
  65 }
  66
  67
  68 /*===========================================================================*
  69  *                              alloc_block                                  *
  70  *===========================================================================*/
  71 block_t alloc_block(struct inode *rip, block_t block)
  72 {
  73 /* Allocate a block for inode. If block is provided, then use it as a goal:
  74  * try to allocate this block or his neghbors.
  75  * If block is not provided then goal is group, where inode lives.
  76  */
  77   block_t goal;
  78   block_t b;
  79   struct super_block *sp = rip->i_sp;
  80
  81   if (sp->s_rd_only)
  82         panic("can't alloc block on read-only filesys.");
  83
  84   /* Check for free blocks. First time discard preallocation,
  85    * next time return NO_BLOCK
  86    */
  87   if (!opt.use_reserved_blocks &&
  88       sp->s_free_blocks_count <= sp->s_r_blocks_count) {
  89         discard_preallocated_blocks(NULL);
  90   } else if (sp->s_free_blocks_count <= EXT2_PREALLOC_BLOCKS) {
  91         discard_preallocated_blocks(NULL);
  92   }
  93
  94   if (!opt.use_reserved_blocks &&
  95       sp->s_free_blocks_count <= sp->s_r_blocks_count) {
  96         return(NO_BLOCK);
  97   } else if (sp->s_free_blocks_count == 0) {
  98         return(NO_BLOCK);
  99   }
 100
 101   if (block != NO_BLOCK) {
 102         goal = block;
 103         if (rip->i_preallocation && rip->i_prealloc_count > 0) {
 104                 /* check if goal is preallocated */
 105                 b = rip->i_prealloc_blocks[rip->i_prealloc_index];
 106                 if (block == b || (block + 1) == b) {
 107                         /* use preallocated block */
 108                         rip->i_prealloc_blocks[rip->i_prealloc_index] = NO_BLOCK;
 109                         rip->i_prealloc_count--;
 110                         rip->i_prealloc_index++;
 111                         if (rip->i_prealloc_index >= EXT2_PREALLOC_BLOCKS) {
 112                                 rip->i_prealloc_index = 0;
 113                                 ASSERT(rip->i_prealloc_count == 0);
 114                         }
 115                         rip->i_bsearch = b;
 116                         return b;
 117                 } else {
 118                         /* probably non-sequential write operation,
 119                          * disable preallocation for this inode.
 120                          */
 121                         rip->i_preallocation = 0;
 122                         discard_preallocated_blocks(rip);
 123                 }
 124         }
 125   } else {
 126           int group = (rip->i_num - 1) / sp->s_inodes_per_group;
 127           goal = sp->s_blocks_per_group*group + sp->s_first_data_block;
 128   }
 129
 130   if (rip->i_preallocation && rip->i_prealloc_count) {
 131         ext2_debug("There're preallocated blocks, but they're\
 132                         neither used or freed!");
 133   }
 134
 135   b = alloc_block_bit(sp, goal, rip);
 136
 137   if (b != NO_BLOCK)
 138         rip->i_bsearch = b;
 139
 140   return b;
 141 }
 142
 143
 144 static void check_block_number(block_t block, struct super_block *sp,
 145         struct group_desc *gd);
 146
 147 /*===========================================================================*
 148  *                              alloc_block_bit                              *
 149  *===========================================================================*/
 150 static block_t alloc_block_bit(sp, goal, rip)
 151 struct super_block *sp;         /* the filesystem to allocate from */
 152 block_t goal;                   /* try to allocate near this block */
 153 struct inode *rip;              /* used for preallocation */
 154 {
 155   block_t block = NO_BLOCK;     /* allocated block */
 156   int word;                     /* word in block bitmap */
 157   bit_t bit = -1;
 158   int group;
 159   char update_bsearch = FALSE;
 160   int i;
 161
 162   if (goal >= sp->s_blocks_count ||
 163       (goal < sp->s_first_data_block && goal != 0)) {
 164         goal = sp->s_bsearch;
 165   }
 166
 167   if (goal <= sp->s_bsearch) {
 168         /* No reason to search in a place with no free blocks */
 169         goal = sp->s_bsearch;
 170         update_bsearch = TRUE;
 171   }
 172
 173   /* Figure out where to start the bit search. */
 174   word = ((goal - sp->s_first_data_block) % sp->s_blocks_per_group)
 175                         / FS_BITCHUNK_BITS;
 176
 177   /* Try to allocate block at any group starting from the goal's group.
 178    * First time goal's group is checked from the word=goal, after all
 179    * groups checked, it's checked again from word=0, that's why "i <=".
 180    */
 181   group = (goal - sp->s_first_data_block) / sp->s_blocks_per_group;
 182   for (i = 0; i <= sp->s_groups_count; i++, group++) {
 183         struct buf *bp;
 184         struct group_desc *gd;
 185
 186         if (group >= sp->s_groups_count)
 187                 group = 0;
 188
 189         gd = get_group_desc(group);
 190         if (gd == NULL)
 191                 panic("can't get group_desc to alloc block");
 192
 193         if (gd->free_blocks_count == 0) {
 194                 word = 0;
 195                 continue;
 196         }
 197
 198         bp = get_block(sp->s_dev, gd->block_bitmap, NORMAL);
 199
 200         if (rip->i_preallocation &&
 201             gd->free_blocks_count >= (EXT2_PREALLOC_BLOCKS * 4) ) {
 202                 /* Try to preallocate blocks */
 203                 if (rip->i_prealloc_count != 0) {
 204                         /* kind of glitch... */
 205                         discard_preallocated_blocks(rip);
 206                         ext2_debug("warning, discarding previously preallocated\
 207                                     blocks! It had to be done by another code.");
 208                 }
 209                 ASSERT(rip->i_prealloc_count == 0);
 210                 /* we preallocate bytes only */
 211                 ASSERT(EXT2_PREALLOC_BLOCKS == sizeof(char)*CHAR_BIT);
 212
 213                 bit = setbyte(b_bitmap(bp), sp->s_blocks_per_group);
 214                 if (bit != -1) {
 215                         block = bit + sp->s_first_data_block +
 216                                         group * sp->s_blocks_per_group;
 217                         check_block_number(block, sp, gd);
 218
 219                         /* We preallocate a byte starting from block.
 220                          * First preallocated block will be returned as
 221                          * normally allocated block.
 222                          */
 223                         for (i = 1; i < EXT2_PREALLOC_BLOCKS; i++) {
 224                                 check_block_number(block + i, sp, gd);
 225                                 rip->i_prealloc_blocks[i-1] = block + i;
 226                         }
 227                         rip->i_prealloc_index = 0;
 228                         rip->i_prealloc_count = EXT2_PREALLOC_BLOCKS - 1;
 229
 230                         lmfs_markdirty(bp);
 231                         put_block(bp, MAP_BLOCK);
 232
 233                         gd->free_blocks_count -= EXT2_PREALLOC_BLOCKS;
 234                         sp->s_free_blocks_count -= EXT2_PREALLOC_BLOCKS;
 235                         group_descriptors_dirty = 1;
 236                         return block;
 237                 }
 238         }
 239
 240         bit = setbit(b_bitmap(bp), sp->s_blocks_per_group, word);
 241         if (bit == -1) {
 242                 if (word == 0) {
 243                         panic("ext2: allocator failed to allocate a bit in bitmap\
 244                                 with free bits.");
 245                 } else {
 246                         word = 0;
 247                         continue;
 248                 }
 249         }
 250
 251         block = sp->s_first_data_block + group * sp->s_blocks_per_group + bit;
 252         check_block_number(block, sp, gd);
 253
 254         lmfs_markdirty(bp);
 255         put_block(bp, MAP_BLOCK);
 256
 257         gd->free_blocks_count--;
 258         sp->s_free_blocks_count--;
 259         group_descriptors_dirty = 1;
 260
 261         if (update_bsearch && block != -1 && block != NO_BLOCK) {
 262                 /* We searched from the beginning, update bsearch. */
 263                 sp->s_bsearch = block;
 264         }
 265
 266         return block;
 267   }
 268
 269   return block;
 270 }
 271
 272
 273 /*===========================================================================*
 274  *                        free_block                                         *
 275  *===========================================================================*/
 276 void free_block(struct super_block *sp, bit_t bit_returned)
 277 {
 278 /* Return a block by turning off its bitmap bit. */
 279   int group;            /* group number of bit_returned */
 280   int bit;              /* bit_returned number within its group */
 281   struct buf *bp;
 282   struct group_desc *gd;
 283
 284   if (sp->s_rd_only)
 285         panic("can't free bit on read-only filesys.");
 286
 287   if (bit_returned >= sp->s_blocks_count ||
 288       bit_returned < sp->s_first_data_block)
 289         panic("trying to free block %d beyond blocks scope.",
 290                 bit_returned);
 291
 292   /* At first search group, to which bit_returned belongs to
 293    * and figure out in what word bit is stored.
 294    */
 295   group = (bit_returned - sp->s_first_data_block) / sp->s_blocks_per_group;
 296   bit = (bit_returned - sp->s_first_data_block) % sp->s_blocks_per_group;
 297
 298   gd = get_group_desc(group);
 299   if (gd == NULL)
 300         panic("can't get group_desc to alloc block");
 301
 302   /* We might be buggy (No way! :P), so check if we deallocate
 303    * data block, but not control (system) block.
 304    * This should never happen.
 305    */
 306   if (bit_returned == gd->inode_bitmap || bit_returned == gd->block_bitmap
 307       || (bit_returned >= gd->inode_table
 308           && bit_returned < (gd->inode_table + sp->s_itb_per_group))) {
 309         ext2_debug("ext2: freeing non-data block %d\n", bit_returned);
 310         panic("trying to deallocate \
 311                 system/control block, hardly poke author.");
 312   }
 313
 314   bp = get_block(sp->s_dev, gd->block_bitmap, NORMAL);
 315
 316   if (unsetbit(b_bitmap(bp), bit))
 317         panic("Tried to free unused block", bit_returned);
 318
 319   lmfs_markdirty(bp);
 320   put_block(bp, MAP_BLOCK);
 321
 322   gd->free_blocks_count++;
 323   sp->s_free_blocks_count++;
 324
 325   group_descriptors_dirty = 1;
 326
 327   if (bit_returned < sp->s_bsearch)
 328         sp->s_bsearch = bit_returned;
 329 }
 330
 331
 332 static void check_block_number(block_t block, struct super_block *sp,
 333                                 struct group_desc *gd)
 334 {
 335
 336   /* Check if we allocated a data block, but not control (system) block.
 337    * Only major bug can cause us to allocate wrong block. If it happens,
 338    * we panic (and don't bloat filesystem's bitmap).
 339    */
 340   if (block == gd->inode_bitmap || block == gd->block_bitmap ||
 341       (block >= gd->inode_table
 342        && block < (gd->inode_table + sp->s_itb_per_group))) {
 343         ext2_debug("ext2: allocating non-data block %d\n", block);
 344         panic("ext2: block allocator tryed to return \
 345                 system/control block, poke author.\n");
 346   }
 347
 348   if (block >= sp->s_blocks_count) {
 349         panic("ext2: allocator returned blocknum greater, than \
 350                         total number of blocks.\n");
 351   }
 352 }