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 lmfs_blockschange(sp->s_dev, -EXT2_PREALLOC_BLOCKS); 236 group_descriptors_dirty = 1; 237 return block; 238 } 239 } 240 241 bit = setbit(b_bitmap(bp), sp->s_blocks_per_group, word); 242 if (bit == -1) { 243 if (word == 0) { 244 panic("ext2: allocator failed to allocate a bit in bitmap\ 245 with free bits."); 246 } else { 247 word = 0; 248 continue; 249 } 250 } 251 252 block = sp->s_first_data_block + group * sp->s_blocks_per_group + bit; 253 check_block_number(block, sp, gd); 254 255 lmfs_markdirty(bp); 256 put_block(bp, MAP_BLOCK); 257 258 gd->free_blocks_count--; 259 sp->s_free_blocks_count--; 260 lmfs_blockschange(sp->s_dev, -1); 261 group_descriptors_dirty = 1; 262 263 if (update_bsearch && block != -1 && block != NO_BLOCK) { 264 /* We searched from the beginning, update bsearch. */ 265 sp->s_bsearch = block; 266 } 267 268 return block; 269 } 270 271 return block; 272 } 273 274 275 /*===========================================================================* 276 * free_block * 277 *===========================================================================*/ 278 void free_block(struct super_block *sp, bit_t bit_returned) 279 { 280 /* Return a block by turning off its bitmap bit. */ 281 int group; /* group number of bit_returned */ 282 int bit; /* bit_returned number within its group */ 283 struct buf *bp; 284 struct group_desc *gd; 285 286 if (sp->s_rd_only) 287 panic("can't free bit on read-only filesys."); 288 289 if (bit_returned >= sp->s_blocks_count || 290 bit_returned < sp->s_first_data_block) 291 panic("trying to free block %d beyond blocks scope.", 292 bit_returned); 293 294 /* At first search group, to which bit_returned belongs to 295 * and figure out in what word bit is stored. 296 */ 297 group = (bit_returned - sp->s_first_data_block) / sp->s_blocks_per_group; 298 bit = (bit_returned - sp->s_first_data_block) % sp->s_blocks_per_group; 299 300 gd = get_group_desc(group); 301 if (gd == NULL) 302 panic("can't get group_desc to alloc block"); 303 304 /* We might be buggy (No way! :P), so check if we deallocate 305 * data block, but not control (system) block. 306 * This should never happen. 307 */ 308 if (bit_returned == gd->inode_bitmap || bit_returned == gd->block_bitmap 309 || (bit_returned >= gd->inode_table 310 && bit_returned < (gd->inode_table + sp->s_itb_per_group))) { 311 ext2_debug("ext2: freeing non-data block %d\n", bit_returned); 312 panic("trying to deallocate \ 313 system/control block, hardly poke author."); 314 } 315 316 bp = get_block(sp->s_dev, gd->block_bitmap, NORMAL); 317 318 if (unsetbit(b_bitmap(bp), bit)) 319 panic("Tried to free unused block %d", bit_returned); 320 321 lmfs_markdirty(bp); 322 put_block(bp, MAP_BLOCK); 323 324 gd->free_blocks_count++; 325 sp->s_free_blocks_count++; 326 lmfs_blockschange(sp->s_dev, 1); 327 328 group_descriptors_dirty = 1; 329 330 if (bit_returned < sp->s_bsearch) 331 sp->s_bsearch = bit_returned; 332 } 333 334 335 static void check_block_number(block_t block, struct super_block *sp, 336 struct group_desc *gd) 337 { 338 339 /* Check if we allocated a data block, but not control (system) block. 340 * Only major bug can cause us to allocate wrong block. If it happens, 341 * we panic (and don't bloat filesystem's bitmap). 342 */ 343 if (block == gd->inode_bitmap || block == gd->block_bitmap || 344 (block >= gd->inode_table 345 && block < (gd->inode_table + sp->s_itb_per_group))) { 346 ext2_debug("ext2: allocating non-data block %d\n", block); 347 panic("ext2: block allocator tryed to return \ 348 system/control block, poke author.\n"); 349 } 350 351 if (block >= sp->s_blocks_count) { 352 panic("ext2: allocator returned blocknum greater, than \ 353 total number of blocks.\n"); 354 } 355 } 356