1 /* This files manages inodes allocation and deallocation. 2 * 3 * The entry points into this file are: 4 * alloc_inode: allocate a new, unused inode. 5 * free_inode: mark an inode as available for a new file. 6 * 7 * Created (alloc_inode/free_inode/wipe_inode are from MFS): 8 * June 2010 (Evgeniy Ivanov) 9 */ 10 11 #include "fs.h" 12 #include <string.h> 13 #include <stdlib.h> 14 #include <minix/com.h> 15 #include <minix/u64.h> 16 #include "buf.h" 17 #include "inode.h" 18 #include "super.h" 19 #include "const.h" 20 21 22 static bit_t alloc_inode_bit(struct super_block *sp, struct inode 23 *parent, int is_dir); 24 static void free_inode_bit(struct super_block *sp, bit_t bit_returned, 25 int is_dir); 26 static void wipe_inode(struct inode *rip); 27 28 29 /*===========================================================================* 30 * alloc_inode * 31 *===========================================================================*/ 32 struct inode *alloc_inode(struct inode *parent, mode_t bits) 33 { 34 /* Allocate a free inode on parent's dev, and return a pointer to it. */ 35 36 register struct inode *rip; 37 register struct super_block *sp; 38 int inumb; 39 bit_t b; 40 static int print_oos_msg = 1; 41 42 sp = get_super(parent->i_dev); /* get pointer to super_block */ 43 if (sp->s_rd_only) { /* can't allocate an inode on a read only device. */ 44 err_code = EROFS; 45 return(NULL); 46 } 47 48 /* Acquire an inode from the bit map. */ 49 b = alloc_inode_bit(sp, parent, (bits & I_TYPE) == I_DIRECTORY); 50 if (b == NO_BIT) { 51 err_code = ENOSPC; 52 if (print_oos_msg) 53 ext2_debug("Out of i-nodes on device %d/%d\n", 54 major(sp->s_dev), minor(sp->s_dev)); 55 print_oos_msg = 0; /* Don't repeat message */ 56 return(NULL); 57 } 58 print_oos_msg = 1; 59 60 inumb = (int) b; /* be careful not to pass unshort as param */ 61 62 /* Try to acquire a slot in the inode table. */ 63 if ((rip = get_inode(NO_DEV, inumb)) == NULL) { 64 /* No inode table slots available. Free the inode just allocated. */ 65 free_inode_bit(sp, b, (bits & I_TYPE) == I_DIRECTORY); 66 } else { 67 /* An inode slot is available. Put the inode just allocated into it. */ 68 rip->i_mode = bits; /* set up RWX bits */ 69 rip->i_links_count = NO_LINK; /* initial no links */ 70 rip->i_uid = caller_uid; /* file's uid is owner's */ 71 rip->i_gid = caller_gid; /* ditto group id */ 72 rip->i_dev = parent->i_dev; /* mark which device it is on */ 73 rip->i_sp = sp; /* pointer to super block */ 74 75 /* Fields not cleared already are cleared in wipe_inode(). They have 76 * been put there because truncate() needs to clear the same fields if 77 * the file happens to be open while being truncated. It saves space 78 * not to repeat the code twice. 79 */ 80 wipe_inode(rip); 81 } 82 83 return(rip); 84 } 85 86 87 /*===========================================================================* 88 * free_inode * 89 *===========================================================================*/ 90 void free_inode( 91 register struct inode *rip /* inode to free */ 92 ) 93 { 94 /* Return an inode to the pool of unallocated inodes. */ 95 register struct super_block *sp; 96 dev_t dev = rip->i_dev; 97 bit_t b = rip->i_num; 98 u16_t mode = rip->i_mode; 99 100 /* Locate the appropriate super_block. */ 101 sp = get_super(dev); 102 103 if (b <= NO_ENTRY || b > sp->s_inodes_count) 104 return; 105 free_inode_bit(sp, b, (mode & I_TYPE) == I_DIRECTORY); 106 107 rip->i_mode = I_NOT_ALLOC; /* clear I_TYPE field */ 108 } 109 110 111 static int find_group_dir(struct super_block *sp); 112 static int find_group_hashalloc(struct super_block *sp, struct inode 113 *parent); 114 static int find_group_any(struct super_block *sp); 115 static int find_group_orlov(struct super_block *sp, struct inode 116 *parent); 117 118 119 /*===========================================================================* 120 * alloc_inode_bit * 121 *===========================================================================*/ 122 static bit_t alloc_inode_bit(sp, parent, is_dir) 123 struct super_block *sp; /* the filesystem to allocate from */ 124 struct inode *parent; /* parent of newly allocated inode */ 125 int is_dir; /* inode will be a directory if it is TRUE */ 126 { 127 int group; 128 ino_t inumber = NO_BIT; 129 bit_t bit; 130 struct buf *bp; 131 struct group_desc *gd; 132 133 if (sp->s_rd_only) 134 panic("can't alloc inode on read-only filesys."); 135 136 if (opt.mfsalloc) { 137 group = find_group_any(sp); 138 } else { 139 if (is_dir) { 140 if (opt.use_orlov) { 141 group = find_group_orlov(sp, parent); 142 } else { 143 group = find_group_dir(sp); 144 } 145 } else { 146 group = find_group_hashalloc(sp, parent); 147 } 148 } 149 /* Check if we have a group where to allocate an inode */ 150 if (group == -1) 151 return(NO_BIT); /* no bit could be allocated */ 152 153 gd = get_group_desc(group); 154 if (gd == NULL) 155 panic("can't get group_desc to alloc block"); 156 157 /* find_group_* should always return either a group with 158 * a free inode slot or -1, which we checked earlier. 159 */ 160 ASSERT(gd->free_inodes_count); 161 162 bp = get_block(sp->s_dev, gd->inode_bitmap, NORMAL); 163 bit = setbit(b_bitmap(bp), sp->s_inodes_per_group, 0); 164 ASSERT(bit != -1); /* group definitly contains free inode */ 165 166 inumber = group * sp->s_inodes_per_group + bit + 1; 167 168 /* Extra checks before real allocation. 169 * Only major bug can cause problems. Since setbit changed 170 * bp->b_bitmap there is no way to recover from this bug. 171 * Should never happen. 172 */ 173 if (inumber > sp->s_inodes_count) { 174 panic("ext2: allocator returned inum greater, than\ 175 total number of inodes.\n"); 176 } 177 178 if (inumber < EXT2_FIRST_INO(sp)) { 179 panic("ext2: allocator tryed to use reserved inode.\n"); 180 } 181 182 lmfs_markdirty(bp); 183 put_block(bp, MAP_BLOCK); 184 185 gd->free_inodes_count--; 186 sp->s_free_inodes_count--; 187 if (is_dir) { 188 gd->used_dirs_count++; 189 sp->s_dirs_counter++; 190 } 191 192 group_descriptors_dirty = 1; 193 194 /* Almost the same as previous 'group' ASSERT */ 195 ASSERT(inumber != NO_BIT); 196 return inumber; 197 } 198 199 200 /*===========================================================================* 201 * free_inode_bit * 202 *===========================================================================*/ 203 static void free_inode_bit(struct super_block *sp, bit_t bit_returned, 204 int is_dir) 205 { 206 /* Return an inode by turning off its bitmap bit. */ 207 int group; /* group number of bit_returned */ 208 int bit; /* bit_returned number within its group */ 209 struct buf *bp; 210 struct group_desc *gd; 211 212 if (sp->s_rd_only) 213 panic("can't free bit on read-only filesys."); 214 215 /* At first search group, to which bit_returned belongs to 216 * and figure out in what word bit is stored. 217 */ 218 if (bit_returned > sp->s_inodes_count || 219 bit_returned < EXT2_FIRST_INO(sp)) 220 panic("trying to free inode %d beyond inodes scope.", bit_returned); 221 222 group = (bit_returned - 1) / sp->s_inodes_per_group; 223 bit = (bit_returned - 1) % sp->s_inodes_per_group; /* index in bitmap */ 224 225 gd = get_group_desc(group); 226 if (gd == NULL) 227 panic("can't get group_desc to alloc block"); 228 229 bp = get_block(sp->s_dev, gd->inode_bitmap, NORMAL); 230 231 if (unsetbit(b_bitmap(bp), bit)) 232 panic("Tried to free unused inode %d", bit_returned); 233 234 lmfs_markdirty(bp); 235 put_block(bp, MAP_BLOCK); 236 237 gd->free_inodes_count++; 238 sp->s_free_inodes_count++; 239 240 if (is_dir) { 241 gd->used_dirs_count--; 242 sp->s_dirs_counter--; 243 } 244 245 group_descriptors_dirty = 1; 246 247 if (group < sp->s_igsearch) 248 sp->s_igsearch = group; 249 } 250 251 252 /* it's implemented very close to the linux' find_group_dir() */ 253 static int find_group_dir(struct super_block *sp) 254 { 255 int avefreei = sp->s_free_inodes_count / sp->s_groups_count; 256 struct group_desc *gd, *best_gd = NULL; 257 int group, best_group = -1; 258 259 for (group = 0; group < sp->s_groups_count; ++group) { 260 gd = get_group_desc(group); 261 if (gd == NULL) 262 panic("can't get group_desc to alloc inode"); 263 if (gd->free_inodes_count == 0) 264 continue; 265 if (gd->free_inodes_count < avefreei) 266 continue; 267 if (!best_gd || 268 gd->free_blocks_count > best_gd->free_blocks_count) { 269 best_gd = gd; 270 best_group = group; 271 } 272 } 273 274 return best_group; /* group or -1 */ 275 } 276 277 278 /* Analog of ffs_hashalloc() from *BSD. 279 * 1) Check parent's for free inodes and blocks. 280 * 2) Quadradically rehash on the group number. 281 * 3) Make a linear search for free inode. 282 */ 283 static int find_group_hashalloc(struct super_block *sp, struct inode *parent) 284 { 285 int ngroups = sp->s_groups_count; 286 struct group_desc *gd; 287 int group, i; 288 int parent_group = (parent->i_num - 1) / sp->s_inodes_per_group; 289 290 /* Try to place new inode in its parent group */ 291 gd = get_group_desc(parent_group); 292 if (gd == NULL) 293 panic("can't get group_desc to alloc inode"); 294 if (gd->free_inodes_count && gd->free_blocks_count) 295 return parent_group; 296 297 /* We can't allocate inode in the parent's group. 298 * Now we will try to place it in another blockgroup. 299 * The main idea is still to keep files from the same 300 * directory together and use different blockgroups for 301 * files from another directory, which lives in the same 302 * blockgroup as our parent. 303 * Thus we will spread things on the disk. 304 */ 305 group = (parent_group + parent->i_num) % ngroups; 306 307 /* Make quadratic probing to find a group with free inodes and blocks. */ 308 for (i = 1; i < ngroups; i <<= 1) { 309 group += i; 310 if (group >= ngroups) 311 group -= ngroups; 312 gd = get_group_desc(group); 313 if (gd == NULL) 314 panic("can't get group_desc to alloc inode"); 315 if (gd->free_inodes_count && gd->free_blocks_count) 316 return group; 317 } 318 319 /* Still no group for new inode, try linear search. 320 * Also check parent again (but for free inodes only). 321 */ 322 group = parent_group; 323 for (i = 0; i < ngroups; i++, group++) { 324 if (group >= ngroups) 325 group = 0; 326 gd = get_group_desc(group); 327 if (gd == NULL) 328 panic("can't get group_desc to alloc inode"); 329 if (gd->free_inodes_count) 330 return group; 331 } 332 333 return -1; 334 } 335 336 337 /* Find first group which has free inode slot. 338 * This is similar to what MFS does. 339 */ 340 static int find_group_any(struct super_block *sp) 341 { 342 int ngroups = sp->s_groups_count; 343 struct group_desc *gd; 344 int group = sp->s_igsearch; 345 346 for (; group < ngroups; group++) { 347 gd = get_group_desc(group); 348 if (gd == NULL) 349 panic("can't get group_desc to alloc inode"); 350 if (gd->free_inodes_count) { 351 sp->s_igsearch = group; 352 return group; 353 } 354 } 355 356 return -1; 357 } 358 359 360 /* We try to spread first-level directories (i.e. directories in the root 361 * or in the directory marked as TOPDIR). 362 * If there are blockgroups with counts for blocks and inodes less than average 363 * we return a group with lowest directory count. Otherwise we either 364 * return a group with good free inodes and blocks counts or just a group 365 * with free inode. 366 * 367 * For other directories we try to find a 'good' group, we consider a group as 368 * a 'good' if it has enough blocks and inodes (greater than min_blocks and 369 * min_inodes). 370 * 371 */ 372 static int find_group_orlov(struct super_block *sp, struct inode *parent) 373 { 374 int avefreei = sp->s_free_inodes_count / sp->s_groups_count; 375 int avefreeb = sp->s_free_blocks_count / sp->s_groups_count; 376 377 int group = -1; 378 int fallback_group = -1; /* Group with at least 1 free inode */ 379 struct group_desc *gd; 380 int i; 381 382 if (parent->i_num == ROOT_INODE || 383 parent->i_flags & EXT2_TOPDIR_FL) { 384 int best_group = -1; 385 int best_avefree_group = -1; /* Best value of avefreei/avefreeb */ 386 int best_ndir = sp->s_inodes_per_group; 387 388 group = (unsigned int)random(); 389 for (i = 0; i < sp->s_groups_count; i++, group++) { 390 if (group >= sp->s_groups_count) 391 group = 0; 392 gd = get_group_desc(group); 393 if (gd == NULL) 394 panic("can't get group_desc to alloc inode"); 395 if (gd->free_inodes_count == 0) 396 continue; 397 398 fallback_group = group; 399 400 if (gd->free_inodes_count < avefreei || 401 gd->free_blocks_count < avefreeb) 402 continue; 403 404 best_avefree_group = group; 405 406 if (gd->used_dirs_count >= best_ndir) 407 continue; 408 best_ndir = gd->used_dirs_count; 409 best_group = group; 410 } 411 if (best_group >= 0) 412 return best_group; 413 if (best_avefree_group >= 0) 414 return best_avefree_group; 415 return fallback_group; 416 } else { 417 int parent_group = (parent->i_num - 1) / sp->s_inodes_per_group; 418 /* 2 is kind of random thing for now, 419 * but performance results are still good. 420 */ 421 int min_blocks = avefreeb / 2; 422 int min_inodes = avefreei / 2; 423 424 group = parent_group; 425 for (i = 0; i < sp->s_groups_count; i++, group++) { 426 if (group >= sp->s_groups_count) 427 group = 0; 428 gd = get_group_desc(group); 429 if (gd == NULL) 430 panic("can't get group_desc to alloc inode"); 431 if (gd->free_inodes_count == 0) 432 continue; 433 434 fallback_group = group; 435 436 if (gd->free_inodes_count >= min_inodes && 437 gd->free_blocks_count >= min_blocks) 438 return group; 439 } 440 return fallback_group; 441 } 442 443 return -1; 444 } 445 446 447 /*===========================================================================* 448 * wipe_inode * 449 *===========================================================================*/ 450 static void wipe_inode( 451 register struct inode *rip /* the inode to be erased */ 452 ) 453 { 454 /* Erase some fields in the inode. This function is called from alloc_inode() 455 * when a new inode is to be allocated, and from truncate(), when an existing 456 * inode is to be truncated. 457 */ 458 459 register int i; 460 461 rip->i_size = 0; 462 rip->i_update = ATIME | CTIME | MTIME; /* update all times later */ 463 rip->i_blocks = 0; 464 rip->i_flags = 0; 465 rip->i_generation = 0; 466 rip->i_file_acl = 0; 467 rip->i_dir_acl = 0; 468 rip->i_faddr = 0; 469 470 for (i = 0; i < EXT2_N_BLOCKS; i++) 471 rip->i_block[i] = NO_BLOCK; 472 rip->i_block[0] = NO_BLOCK; 473 474 rip->i_dirt = IN_DIRTY; 475 } 476