1 /* 2 * Copyright (c) 1982, 1986, 1989 Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)ffs_alloc.c 7.30 (Berkeley) 11/20/91 8 */ 9 10 #include <sys/param.h> 11 #include <sys/systm.h> 12 #include <sys/buf.h> 13 #include <sys/proc.h> 14 #include <sys/vnode.h> 15 #include <sys/kernel.h> 16 #include <sys/syslog.h> 17 18 #include <ufs/ufs/quota.h> 19 #include <ufs/ufs/inode.h> 20 21 #include <ufs/ffs/fs.h> 22 #include <ufs/ffs/ffs_extern.h> 23 24 extern u_long nextgennumber; 25 26 static daddr_t ffs_alloccg __P((struct inode *, int, daddr_t, int)); 27 static daddr_t ffs_alloccgblk __P((struct fs *, struct cg *, daddr_t)); 28 static ino_t ffs_dirpref __P((struct fs *)); 29 static daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 30 static void ffs_fserr __P((struct fs *, u_int, char *)); 31 static u_long ffs_hashalloc 32 __P((struct inode *, int, long, int, u_long (*)())); 33 static ino_t ffs_ialloccg __P((struct inode *, int, daddr_t, int)); 34 static daddr_t ffs_mapsearch __P((struct fs *, struct cg *, daddr_t, int)); 35 36 /* 37 * Allocate a block in the file system. 38 * 39 * The size of the requested block is given, which must be some 40 * multiple of fs_fsize and <= fs_bsize. 41 * A preference may be optionally specified. If a preference is given 42 * the following hierarchy is used to allocate a block: 43 * 1) allocate the requested block. 44 * 2) allocate a rotationally optimal block in the same cylinder. 45 * 3) allocate a block in the same cylinder group. 46 * 4) quadradically rehash into other cylinder groups, until an 47 * available block is located. 48 * If no block preference is given the following heirarchy is used 49 * to allocate a block: 50 * 1) allocate a block in the cylinder group that contains the 51 * inode for the file. 52 * 2) quadradically rehash into other cylinder groups, until an 53 * available block is located. 54 */ 55 ffs_alloc(ip, lbn, bpref, size, bnp) 56 register struct inode *ip; 57 daddr_t lbn, bpref; 58 int size; 59 daddr_t *bnp; 60 { 61 daddr_t bno; 62 register struct fs *fs; 63 register struct buf *bp; 64 int cg, error; 65 struct ucred *cred = curproc->p_ucred; /* XXX */ 66 67 *bnp = 0; 68 fs = ip->i_fs; 69 if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) { 70 printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", 71 ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 72 panic("ffs_alloc: bad size"); 73 } 74 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 75 goto nospace; 76 if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 77 goto nospace; 78 #ifdef QUOTA 79 if (error = chkdq(ip, (long)btodb(size), cred, 0)) 80 return (error); 81 #endif 82 if (bpref >= fs->fs_size) 83 bpref = 0; 84 if (bpref == 0) 85 cg = itog(fs, ip->i_number); 86 else 87 cg = dtog(fs, bpref); 88 bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 89 (u_long (*)())ffs_alloccg); 90 if (bno > 0) { 91 ip->i_blocks += btodb(size); 92 ip->i_flag |= IUPD|ICHG; 93 *bnp = bno; 94 return (0); 95 } 96 #ifdef QUOTA 97 /* 98 * Restore user's disk quota because allocation failed. 99 */ 100 (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 101 #endif 102 nospace: 103 ffs_fserr(fs, cred->cr_uid, "file system full"); 104 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 105 return (ENOSPC); 106 } 107 108 /* 109 * Reallocate a fragment to a bigger size 110 * 111 * The number and size of the old block is given, and a preference 112 * and new size is also specified. The allocator attempts to extend 113 * the original block. Failing that, the regular block allocator is 114 * invoked to get an appropriate block. 115 */ 116 ffs_realloccg(ip, lbprev, bpref, osize, nsize, bpp) 117 register struct inode *ip; 118 off_t lbprev; 119 daddr_t bpref; 120 int osize, nsize; 121 struct buf **bpp; 122 { 123 register struct fs *fs; 124 struct buf *bp, *obp; 125 int cg, request, error; 126 daddr_t bprev, bno; 127 struct ucred *cred = curproc->p_ucred; /* XXX */ 128 129 *bpp = 0; 130 fs = ip->i_fs; 131 if ((unsigned)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 132 (unsigned)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 133 printf( 134 "dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n", 135 ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt); 136 panic("ffs_realloccg: bad size"); 137 } 138 if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 139 goto nospace; 140 if ((bprev = ip->i_db[lbprev]) == 0) { 141 printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n", 142 ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); 143 panic("ffs_realloccg: bad bprev"); 144 } 145 /* 146 * Allocate the extra space in the buffer. 147 */ 148 if (error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp)) { 149 brelse(bp); 150 return (error); 151 } 152 #ifdef QUOTA 153 if (error = chkdq(ip, (long)btodb(nsize - osize), cred, 0)) { 154 brelse(bp); 155 return (error); 156 } 157 #endif 158 /* 159 * Check for extension in the existing location. 160 */ 161 cg = dtog(fs, bprev); 162 if (bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize)) { 163 if (bp->b_blkno != fsbtodb(fs, bno)) 164 panic("bad blockno"); 165 ip->i_blocks += btodb(nsize - osize); 166 ip->i_flag |= IUPD|ICHG; 167 allocbuf(bp, nsize); 168 bp->b_flags |= B_DONE; 169 bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize); 170 *bpp = bp; 171 return (0); 172 } 173 /* 174 * Allocate a new disk location. 175 */ 176 if (bpref >= fs->fs_size) 177 bpref = 0; 178 switch ((int)fs->fs_optim) { 179 case FS_OPTSPACE: 180 /* 181 * Allocate an exact sized fragment. Although this makes 182 * best use of space, we will waste time relocating it if 183 * the file continues to grow. If the fragmentation is 184 * less than half of the minimum free reserve, we choose 185 * to begin optimizing for time. 186 */ 187 request = nsize; 188 if (fs->fs_minfree < 5 || 189 fs->fs_cstotal.cs_nffree > 190 fs->fs_dsize * fs->fs_minfree / (2 * 100)) 191 break; 192 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 193 fs->fs_fsmnt); 194 fs->fs_optim = FS_OPTTIME; 195 break; 196 case FS_OPTTIME: 197 /* 198 * At this point we have discovered a file that is trying to 199 * grow a small fragment to a larger fragment. To save time, 200 * we allocate a full sized block, then free the unused portion. 201 * If the file continues to grow, the `ffs_fragextend' call 202 * above will be able to grow it in place without further 203 * copying. If aberrant programs cause disk fragmentation to 204 * grow within 2% of the free reserve, we choose to begin 205 * optimizing for space. 206 */ 207 request = fs->fs_bsize; 208 if (fs->fs_cstotal.cs_nffree < 209 fs->fs_dsize * (fs->fs_minfree - 2) / 100) 210 break; 211 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 212 fs->fs_fsmnt); 213 fs->fs_optim = FS_OPTSPACE; 214 break; 215 default: 216 printf("dev = 0x%x, optim = %d, fs = %s\n", 217 ip->i_dev, fs->fs_optim, fs->fs_fsmnt); 218 panic("ffs_realloccg: bad optim"); 219 /* NOTREACHED */ 220 } 221 bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 222 (u_long (*)())ffs_alloccg); 223 if (bno > 0) { 224 bp->b_blkno = fsbtodb(fs, bno); 225 (void) vnode_pager_uncache(ITOV(ip)); 226 ffs_blkfree(ip, bprev, (off_t)osize); 227 if (nsize < request) 228 ffs_blkfree(ip, bno + numfrags(fs, nsize), 229 (off_t)(request - nsize)); 230 ip->i_blocks += btodb(nsize - osize); 231 ip->i_flag |= IUPD|ICHG; 232 allocbuf(bp, nsize); 233 bp->b_flags |= B_DONE; 234 bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize); 235 *bpp = bp; 236 return (0); 237 } 238 #ifdef QUOTA 239 /* 240 * Restore user's disk quota because allocation failed. 241 */ 242 (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 243 #endif 244 brelse(bp); 245 nospace: 246 /* 247 * no space available 248 */ 249 ffs_fserr(fs, cred->cr_uid, "file system full"); 250 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 251 return (ENOSPC); 252 } 253 254 /* 255 * Allocate an inode in the file system. 256 * 257 * If allocating a directory, use ffs_dirpref to select the inode. 258 * If allocating in a directory, the following hierarchy is followed: 259 * 1) allocate the preferred inode. 260 * 2) allocate an inode in the same cylinder group. 261 * 3) quadradically rehash into other cylinder groups, until an 262 * available inode is located. 263 * If no inode preference is given the following heirarchy is used 264 * to allocate an inode: 265 * 1) allocate an inode in cylinder group 0. 266 * 2) quadradically rehash into other cylinder groups, until an 267 * available inode is located. 268 */ 269 ffs_valloc(pvp, mode, cred, vpp) 270 register struct vnode *pvp; 271 int mode; 272 struct ucred *cred; 273 struct vnode **vpp; 274 { 275 register struct inode *pip; 276 register struct fs *fs; 277 register struct inode *ip; 278 ino_t ino, ipref; 279 int cg, error; 280 281 *vpp = NULL; 282 pip = VTOI(pvp); 283 fs = pip->i_fs; 284 if (fs->fs_cstotal.cs_nifree == 0) 285 goto noinodes; 286 287 if ((mode & IFMT) == IFDIR) 288 ipref = ffs_dirpref(fs); 289 else 290 ipref = pip->i_number; 291 if (ipref >= fs->fs_ncg * fs->fs_ipg) 292 ipref = 0; 293 cg = itog(fs, ipref); 294 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_ialloccg); 295 if (ino == 0) 296 goto noinodes; 297 error = ffs_vget(pvp->v_mount, ino, vpp); 298 if (error) { 299 ffs_vfree(pvp, ino, mode); 300 return (error); 301 } 302 ip = VTOI(*vpp); 303 if (ip->i_mode) { 304 printf("mode = 0%o, inum = %d, fs = %s\n", 305 ip->i_mode, ip->i_number, fs->fs_fsmnt); 306 panic("ffs_valloc: dup alloc"); 307 } 308 if (ip->i_blocks) { /* XXX */ 309 printf("free inode %s/%d had %d blocks\n", 310 fs->fs_fsmnt, ino, ip->i_blocks); 311 ip->i_blocks = 0; 312 } 313 ip->i_flags = 0; 314 /* 315 * Set up a new generation number for this inode. 316 */ 317 if (++nextgennumber < (u_long)time.tv_sec) 318 nextgennumber = time.tv_sec; 319 ip->i_gen = nextgennumber; 320 return (0); 321 noinodes: 322 ffs_fserr(fs, cred->cr_uid, "out of inodes"); 323 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 324 return (ENOSPC); 325 } 326 327 /* 328 * Find a cylinder to place a directory. 329 * 330 * The policy implemented by this algorithm is to select from 331 * among those cylinder groups with above the average number of 332 * free inodes, the one with the smallest number of directories. 333 */ 334 static ino_t 335 ffs_dirpref(fs) 336 register struct fs *fs; 337 { 338 int cg, minndir, mincg, avgifree; 339 340 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 341 minndir = fs->fs_ipg; 342 mincg = 0; 343 for (cg = 0; cg < fs->fs_ncg; cg++) 344 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 345 fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 346 mincg = cg; 347 minndir = fs->fs_cs(fs, cg).cs_ndir; 348 } 349 return ((ino_t)(fs->fs_ipg * mincg)); 350 } 351 352 /* 353 * Select the desired position for the next block in a file. The file is 354 * logically divided into sections. The first section is composed of the 355 * direct blocks. Each additional section contains fs_maxbpg blocks. 356 * 357 * If no blocks have been allocated in the first section, the policy is to 358 * request a block in the same cylinder group as the inode that describes 359 * the file. If no blocks have been allocated in any other section, the 360 * policy is to place the section in a cylinder group with a greater than 361 * average number of free blocks. An appropriate cylinder group is found 362 * by using a rotor that sweeps the cylinder groups. When a new group of 363 * blocks is needed, the sweep begins in the cylinder group following the 364 * cylinder group from which the previous allocation was made. The sweep 365 * continues until a cylinder group with greater than the average number 366 * of free blocks is found. If the allocation is for the first block in an 367 * indirect block, the information on the previous allocation is unavailable; 368 * here a best guess is made based upon the logical block number being 369 * allocated. 370 * 371 * If a section is already partially allocated, the policy is to 372 * contiguously allocate fs_maxcontig blocks. The end of one of these 373 * contiguous blocks and the beginning of the next is physically separated 374 * so that the disk head will be in transit between them for at least 375 * fs_rotdelay milliseconds. This is to allow time for the processor to 376 * schedule another I/O transfer. 377 */ 378 daddr_t 379 ffs_blkpref(ip, lbn, indx, bap) 380 struct inode *ip; 381 daddr_t lbn; 382 int indx; 383 daddr_t *bap; 384 { 385 register struct fs *fs; 386 register int cg; 387 int avgbfree, startcg; 388 daddr_t nextblk; 389 390 fs = ip->i_fs; 391 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 392 if (lbn < NDADDR) { 393 cg = itog(fs, ip->i_number); 394 return (fs->fs_fpg * cg + fs->fs_frag); 395 } 396 /* 397 * Find a cylinder with greater than average number of 398 * unused data blocks. 399 */ 400 if (indx == 0 || bap[indx - 1] == 0) 401 startcg = itog(fs, ip->i_number) + lbn / fs->fs_maxbpg; 402 else 403 startcg = dtog(fs, bap[indx - 1]) + 1; 404 startcg %= fs->fs_ncg; 405 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 406 for (cg = startcg; cg < fs->fs_ncg; cg++) 407 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 408 fs->fs_cgrotor = cg; 409 return (fs->fs_fpg * cg + fs->fs_frag); 410 } 411 for (cg = 0; cg <= startcg; cg++) 412 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 413 fs->fs_cgrotor = cg; 414 return (fs->fs_fpg * cg + fs->fs_frag); 415 } 416 return (NULL); 417 } 418 /* 419 * One or more previous blocks have been laid out. If less 420 * than fs_maxcontig previous blocks are contiguous, the 421 * next block is requested contiguously, otherwise it is 422 * requested rotationally delayed by fs_rotdelay milliseconds. 423 */ 424 nextblk = bap[indx - 1] + fs->fs_frag; 425 if (indx > fs->fs_maxcontig && 426 bap[indx - fs->fs_maxcontig] + blkstofrags(fs, fs->fs_maxcontig) 427 != nextblk) 428 return (nextblk); 429 if (fs->fs_rotdelay != 0) 430 /* 431 * Here we convert ms of delay to frags as: 432 * (frags) = (ms) * (rev/sec) * (sect/rev) / 433 * ((sect/frag) * (ms/sec)) 434 * then round up to the next block. 435 */ 436 nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 437 (NSPF(fs) * 1000), fs->fs_frag); 438 return (nextblk); 439 } 440 441 /* 442 * Implement the cylinder overflow algorithm. 443 * 444 * The policy implemented by this algorithm is: 445 * 1) allocate the block in its requested cylinder group. 446 * 2) quadradically rehash on the cylinder group number. 447 * 3) brute force search for a free block. 448 */ 449 /*VARARGS5*/ 450 static u_long 451 ffs_hashalloc(ip, cg, pref, size, allocator) 452 struct inode *ip; 453 int cg; 454 long pref; 455 int size; /* size for data blocks, mode for inodes */ 456 u_long (*allocator)(); 457 { 458 register struct fs *fs; 459 long result; 460 int i, icg = cg; 461 462 fs = ip->i_fs; 463 /* 464 * 1: preferred cylinder group 465 */ 466 result = (*allocator)(ip, cg, pref, size); 467 if (result) 468 return (result); 469 /* 470 * 2: quadratic rehash 471 */ 472 for (i = 1; i < fs->fs_ncg; i *= 2) { 473 cg += i; 474 if (cg >= fs->fs_ncg) 475 cg -= fs->fs_ncg; 476 result = (*allocator)(ip, cg, 0, size); 477 if (result) 478 return (result); 479 } 480 /* 481 * 3: brute force search 482 * Note that we start at i == 2, since 0 was checked initially, 483 * and 1 is always checked in the quadratic rehash. 484 */ 485 cg = (icg + 2) % fs->fs_ncg; 486 for (i = 2; i < fs->fs_ncg; i++) { 487 result = (*allocator)(ip, cg, 0, size); 488 if (result) 489 return (result); 490 cg++; 491 if (cg == fs->fs_ncg) 492 cg = 0; 493 } 494 return (NULL); 495 } 496 497 /* 498 * Determine whether a fragment can be extended. 499 * 500 * Check to see if the necessary fragments are available, and 501 * if they are, allocate them. 502 */ 503 static daddr_t 504 ffs_fragextend(ip, cg, bprev, osize, nsize) 505 struct inode *ip; 506 int cg; 507 long bprev; 508 int osize, nsize; 509 { 510 register struct fs *fs; 511 register struct cg *cgp; 512 struct buf *bp; 513 long bno; 514 int frags, bbase; 515 int i, error; 516 517 fs = ip->i_fs; 518 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 519 return (NULL); 520 frags = numfrags(fs, nsize); 521 bbase = fragnum(fs, bprev); 522 if (bbase > fragnum(fs, (bprev + frags - 1))) { 523 /* cannot extend across a block boundary */ 524 return (NULL); 525 } 526 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 527 (int)fs->fs_cgsize, NOCRED, &bp); 528 if (error) { 529 brelse(bp); 530 return (NULL); 531 } 532 cgp = bp->b_un.b_cg; 533 if (!cg_chkmagic(cgp)) { 534 brelse(bp); 535 return (NULL); 536 } 537 cgp->cg_time = time.tv_sec; 538 bno = dtogd(fs, bprev); 539 for (i = numfrags(fs, osize); i < frags; i++) 540 if (isclr(cg_blksfree(cgp), bno + i)) { 541 brelse(bp); 542 return (NULL); 543 } 544 /* 545 * the current fragment can be extended 546 * deduct the count on fragment being extended into 547 * increase the count on the remaining fragment (if any) 548 * allocate the extended piece 549 */ 550 for (i = frags; i < fs->fs_frag - bbase; i++) 551 if (isclr(cg_blksfree(cgp), bno + i)) 552 break; 553 cgp->cg_frsum[i - numfrags(fs, osize)]--; 554 if (i != frags) 555 cgp->cg_frsum[i - frags]++; 556 for (i = numfrags(fs, osize); i < frags; i++) { 557 clrbit(cg_blksfree(cgp), bno + i); 558 cgp->cg_cs.cs_nffree--; 559 fs->fs_cstotal.cs_nffree--; 560 fs->fs_cs(fs, cg).cs_nffree--; 561 } 562 fs->fs_fmod = 1; 563 bdwrite(bp); 564 return (bprev); 565 } 566 567 /* 568 * Determine whether a block can be allocated. 569 * 570 * Check to see if a block of the apprpriate size is available, 571 * and if it is, allocate it. 572 */ 573 static daddr_t 574 ffs_alloccg(ip, cg, bpref, size) 575 struct inode *ip; 576 int cg; 577 daddr_t bpref; 578 int size; 579 { 580 register struct fs *fs; 581 register struct cg *cgp; 582 struct buf *bp; 583 register int i; 584 int error, bno, frags, allocsiz; 585 586 fs = ip->i_fs; 587 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 588 return (NULL); 589 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 590 (int)fs->fs_cgsize, NOCRED, &bp); 591 if (error) { 592 brelse(bp); 593 return (NULL); 594 } 595 cgp = bp->b_un.b_cg; 596 if (!cg_chkmagic(cgp) || 597 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 598 brelse(bp); 599 return (NULL); 600 } 601 cgp->cg_time = time.tv_sec; 602 if (size == fs->fs_bsize) { 603 bno = ffs_alloccgblk(fs, cgp, bpref); 604 bdwrite(bp); 605 return (bno); 606 } 607 /* 608 * check to see if any fragments are already available 609 * allocsiz is the size which will be allocated, hacking 610 * it down to a smaller size if necessary 611 */ 612 frags = numfrags(fs, size); 613 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 614 if (cgp->cg_frsum[allocsiz] != 0) 615 break; 616 if (allocsiz == fs->fs_frag) { 617 /* 618 * no fragments were available, so a block will be 619 * allocated, and hacked up 620 */ 621 if (cgp->cg_cs.cs_nbfree == 0) { 622 brelse(bp); 623 return (NULL); 624 } 625 bno = ffs_alloccgblk(fs, cgp, bpref); 626 bpref = dtogd(fs, bno); 627 for (i = frags; i < fs->fs_frag; i++) 628 setbit(cg_blksfree(cgp), bpref + i); 629 i = fs->fs_frag - frags; 630 cgp->cg_cs.cs_nffree += i; 631 fs->fs_cstotal.cs_nffree += i; 632 fs->fs_cs(fs, cg).cs_nffree += i; 633 fs->fs_fmod = 1; 634 cgp->cg_frsum[i]++; 635 bdwrite(bp); 636 return (bno); 637 } 638 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 639 if (bno < 0) { 640 brelse(bp); 641 return (NULL); 642 } 643 for (i = 0; i < frags; i++) 644 clrbit(cg_blksfree(cgp), bno + i); 645 cgp->cg_cs.cs_nffree -= frags; 646 fs->fs_cstotal.cs_nffree -= frags; 647 fs->fs_cs(fs, cg).cs_nffree -= frags; 648 fs->fs_fmod = 1; 649 cgp->cg_frsum[allocsiz]--; 650 if (frags != allocsiz) 651 cgp->cg_frsum[allocsiz - frags]++; 652 bdwrite(bp); 653 return (cg * fs->fs_fpg + bno); 654 } 655 656 /* 657 * Allocate a block in a cylinder group. 658 * 659 * This algorithm implements the following policy: 660 * 1) allocate the requested block. 661 * 2) allocate a rotationally optimal block in the same cylinder. 662 * 3) allocate the next available block on the block rotor for the 663 * specified cylinder group. 664 * Note that this routine only allocates fs_bsize blocks; these 665 * blocks may be fragmented by the routine that allocates them. 666 */ 667 static daddr_t 668 ffs_alloccgblk(fs, cgp, bpref) 669 register struct fs *fs; 670 register struct cg *cgp; 671 daddr_t bpref; 672 { 673 daddr_t bno; 674 int cylno, pos, delta; 675 short *cylbp; 676 register int i; 677 678 if (bpref == 0) { 679 bpref = cgp->cg_rotor; 680 goto norot; 681 } 682 bpref = blknum(fs, bpref); 683 bpref = dtogd(fs, bpref); 684 /* 685 * if the requested block is available, use it 686 */ 687 if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { 688 bno = bpref; 689 goto gotit; 690 } 691 /* 692 * check for a block available on the same cylinder 693 */ 694 cylno = cbtocylno(fs, bpref); 695 if (cg_blktot(cgp)[cylno] == 0) 696 goto norot; 697 if (fs->fs_cpc == 0) { 698 /* 699 * block layout info is not available, so just have 700 * to take any block in this cylinder. 701 */ 702 bpref = howmany(fs->fs_spc * cylno, NSPF(fs)); 703 goto norot; 704 } 705 /* 706 * check the summary information to see if a block is 707 * available in the requested cylinder starting at the 708 * requested rotational position and proceeding around. 709 */ 710 cylbp = cg_blks(fs, cgp, cylno); 711 pos = cbtorpos(fs, bpref); 712 for (i = pos; i < fs->fs_nrpos; i++) 713 if (cylbp[i] > 0) 714 break; 715 if (i == fs->fs_nrpos) 716 for (i = 0; i < pos; i++) 717 if (cylbp[i] > 0) 718 break; 719 if (cylbp[i] > 0) { 720 /* 721 * found a rotational position, now find the actual 722 * block. A panic if none is actually there. 723 */ 724 pos = cylno % fs->fs_cpc; 725 bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 726 if (fs_postbl(fs, pos)[i] == -1) { 727 printf("pos = %d, i = %d, fs = %s\n", 728 pos, i, fs->fs_fsmnt); 729 panic("ffs_alloccgblk: cyl groups corrupted"); 730 } 731 for (i = fs_postbl(fs, pos)[i];; ) { 732 if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) { 733 bno = blkstofrags(fs, (bno + i)); 734 goto gotit; 735 } 736 delta = fs_rotbl(fs)[i]; 737 if (delta <= 0 || 738 delta + i > fragstoblks(fs, fs->fs_fpg)) 739 break; 740 i += delta; 741 } 742 printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 743 panic("ffs_alloccgblk: can't find blk in cyl"); 744 } 745 norot: 746 /* 747 * no blocks in the requested cylinder, so take next 748 * available one in this cylinder group. 749 */ 750 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 751 if (bno < 0) 752 return (NULL); 753 cgp->cg_rotor = bno; 754 gotit: 755 ffs_clrblock(fs, cg_blksfree(cgp), (long)fragstoblks(fs, bno)); 756 cgp->cg_cs.cs_nbfree--; 757 fs->fs_cstotal.cs_nbfree--; 758 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 759 cylno = cbtocylno(fs, bno); 760 cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 761 cg_blktot(cgp)[cylno]--; 762 fs->fs_fmod = 1; 763 return (cgp->cg_cgx * fs->fs_fpg + bno); 764 } 765 766 /* 767 * Determine whether an inode can be allocated. 768 * 769 * Check to see if an inode is available, and if it is, 770 * allocate it using the following policy: 771 * 1) allocate the requested inode. 772 * 2) allocate the next available inode after the requested 773 * inode in the specified cylinder group. 774 */ 775 static ino_t 776 ffs_ialloccg(ip, cg, ipref, mode) 777 struct inode *ip; 778 int cg; 779 daddr_t ipref; 780 int mode; 781 { 782 register struct fs *fs; 783 register struct cg *cgp; 784 struct buf *bp; 785 int error, start, len, loc, map, i; 786 787 fs = ip->i_fs; 788 if (fs->fs_cs(fs, cg).cs_nifree == 0) 789 return (NULL); 790 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 791 (int)fs->fs_cgsize, NOCRED, &bp); 792 if (error) { 793 brelse(bp); 794 return (NULL); 795 } 796 cgp = bp->b_un.b_cg; 797 if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 798 brelse(bp); 799 return (NULL); 800 } 801 cgp->cg_time = time.tv_sec; 802 if (ipref) { 803 ipref %= fs->fs_ipg; 804 if (isclr(cg_inosused(cgp), ipref)) 805 goto gotit; 806 } 807 start = cgp->cg_irotor / NBBY; 808 len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 809 loc = skpc(0xff, len, &cg_inosused(cgp)[start]); 810 if (loc == 0) { 811 len = start + 1; 812 start = 0; 813 loc = skpc(0xff, len, &cg_inosused(cgp)[0]); 814 if (loc == 0) { 815 printf("cg = %s, irotor = %d, fs = %s\n", 816 cg, cgp->cg_irotor, fs->fs_fsmnt); 817 panic("ffs_ialloccg: map corrupted"); 818 /* NOTREACHED */ 819 } 820 } 821 i = start + len - loc; 822 map = cg_inosused(cgp)[i]; 823 ipref = i * NBBY; 824 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 825 if ((map & i) == 0) { 826 cgp->cg_irotor = ipref; 827 goto gotit; 828 } 829 } 830 printf("fs = %s\n", fs->fs_fsmnt); 831 panic("ffs_ialloccg: block not in map"); 832 /* NOTREACHED */ 833 gotit: 834 setbit(cg_inosused(cgp), ipref); 835 cgp->cg_cs.cs_nifree--; 836 fs->fs_cstotal.cs_nifree--; 837 fs->fs_cs(fs, cg).cs_nifree--; 838 fs->fs_fmod = 1; 839 if ((mode & IFMT) == IFDIR) { 840 cgp->cg_cs.cs_ndir++; 841 fs->fs_cstotal.cs_ndir++; 842 fs->fs_cs(fs, cg).cs_ndir++; 843 } 844 bdwrite(bp); 845 return (cg * fs->fs_ipg + ipref); 846 } 847 848 /* 849 * Free a block or fragment. 850 * 851 * The specified block or fragment is placed back in the 852 * free map. If a fragment is deallocated, a possible 853 * block reassembly is checked. 854 */ 855 ffs_blkfree(ip, bno, size) 856 register struct inode *ip; 857 daddr_t bno; 858 off_t size; 859 { 860 register struct fs *fs; 861 register struct cg *cgp; 862 struct buf *bp; 863 int error, cg, blk, frags, bbase; 864 register int i; 865 struct ucred *cred = curproc->p_ucred; /* XXX */ 866 867 fs = ip->i_fs; 868 if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) { 869 printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", 870 ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 871 panic("blkfree: bad size"); 872 } 873 cg = dtog(fs, bno); 874 if ((unsigned)bno >= fs->fs_size) { 875 printf("bad block %d, ino %d\n", bno, ip->i_number); 876 ffs_fserr(fs, cred->cr_uid, "bad block"); 877 return; 878 } 879 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 880 (int)fs->fs_cgsize, NOCRED, &bp); 881 if (error) { 882 brelse(bp); 883 return; 884 } 885 cgp = bp->b_un.b_cg; 886 if (!cg_chkmagic(cgp)) { 887 brelse(bp); 888 return; 889 } 890 cgp->cg_time = time.tv_sec; 891 bno = dtogd(fs, bno); 892 if (size == fs->fs_bsize) { 893 if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno))) { 894 printf("dev = 0x%x, block = %d, fs = %s\n", 895 ip->i_dev, bno, fs->fs_fsmnt); 896 panic("blkfree: freeing free block"); 897 } 898 ffs_setblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno)); 899 cgp->cg_cs.cs_nbfree++; 900 fs->fs_cstotal.cs_nbfree++; 901 fs->fs_cs(fs, cg).cs_nbfree++; 902 i = cbtocylno(fs, bno); 903 cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 904 cg_blktot(cgp)[i]++; 905 } else { 906 bbase = bno - fragnum(fs, bno); 907 /* 908 * decrement the counts associated with the old frags 909 */ 910 blk = blkmap(fs, cg_blksfree(cgp), bbase); 911 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 912 /* 913 * deallocate the fragment 914 */ 915 frags = numfrags(fs, size); 916 for (i = 0; i < frags; i++) { 917 if (isset(cg_blksfree(cgp), bno + i)) { 918 printf("dev = 0x%x, block = %d, fs = %s\n", 919 ip->i_dev, bno + i, fs->fs_fsmnt); 920 panic("blkfree: freeing free frag"); 921 } 922 setbit(cg_blksfree(cgp), bno + i); 923 } 924 cgp->cg_cs.cs_nffree += i; 925 fs->fs_cstotal.cs_nffree += i; 926 fs->fs_cs(fs, cg).cs_nffree += i; 927 /* 928 * add back in counts associated with the new frags 929 */ 930 blk = blkmap(fs, cg_blksfree(cgp), bbase); 931 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 932 /* 933 * if a complete block has been reassembled, account for it 934 */ 935 if (ffs_isblock(fs, cg_blksfree(cgp), 936 (daddr_t)fragstoblks(fs, bbase))) { 937 cgp->cg_cs.cs_nffree -= fs->fs_frag; 938 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 939 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 940 cgp->cg_cs.cs_nbfree++; 941 fs->fs_cstotal.cs_nbfree++; 942 fs->fs_cs(fs, cg).cs_nbfree++; 943 i = cbtocylno(fs, bbase); 944 cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 945 cg_blktot(cgp)[i]++; 946 } 947 } 948 fs->fs_fmod = 1; 949 bdwrite(bp); 950 } 951 952 /* 953 * Free an inode. 954 * 955 * The specified inode is placed back in the free map. 956 */ 957 void 958 ffs_vfree(pvp, ino, mode) 959 struct vnode *pvp; 960 ino_t ino; 961 int mode; 962 { 963 register struct fs *fs; 964 register struct cg *cgp; 965 register struct inode *pip; 966 struct buf *bp; 967 int error, cg; 968 969 pip = VTOI(pvp); 970 fs = pip->i_fs; 971 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 972 panic("ifree: range: dev = 0x%x, ino = %d, fs = %s\n", 973 pip->i_dev, ino, fs->fs_fsmnt); 974 cg = itog(fs, ino); 975 error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 976 (int)fs->fs_cgsize, NOCRED, &bp); 977 if (error) { 978 brelse(bp); 979 return; 980 } 981 cgp = bp->b_un.b_cg; 982 if (!cg_chkmagic(cgp)) { 983 brelse(bp); 984 return; 985 } 986 cgp->cg_time = time.tv_sec; 987 ino %= fs->fs_ipg; 988 if (isclr(cg_inosused(cgp), ino)) { 989 printf("dev = 0x%x, ino = %d, fs = %s\n", 990 pip->i_dev, ino, fs->fs_fsmnt); 991 if (fs->fs_ronly == 0) 992 panic("ifree: freeing free inode"); 993 } 994 clrbit(cg_inosused(cgp), ino); 995 if (ino < cgp->cg_irotor) 996 cgp->cg_irotor = ino; 997 cgp->cg_cs.cs_nifree++; 998 fs->fs_cstotal.cs_nifree++; 999 fs->fs_cs(fs, cg).cs_nifree++; 1000 if ((mode & IFMT) == IFDIR) { 1001 cgp->cg_cs.cs_ndir--; 1002 fs->fs_cstotal.cs_ndir--; 1003 fs->fs_cs(fs, cg).cs_ndir--; 1004 } 1005 fs->fs_fmod = 1; 1006 bdwrite(bp); 1007 } 1008 1009 /* 1010 * Find a block of the specified size in the specified cylinder group. 1011 * 1012 * It is a panic if a request is made to find a block if none are 1013 * available. 1014 */ 1015 static daddr_t 1016 ffs_mapsearch(fs, cgp, bpref, allocsiz) 1017 register struct fs *fs; 1018 register struct cg *cgp; 1019 daddr_t bpref; 1020 int allocsiz; 1021 { 1022 daddr_t bno; 1023 int start, len, loc, i; 1024 int blk, field, subfield, pos; 1025 1026 /* 1027 * find the fragment by searching through the free block 1028 * map for an appropriate bit pattern 1029 */ 1030 if (bpref) 1031 start = dtogd(fs, bpref) / NBBY; 1032 else 1033 start = cgp->cg_frotor / NBBY; 1034 len = howmany(fs->fs_fpg, NBBY) - start; 1035 loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[start], 1036 (u_char *)fragtbl[fs->fs_frag], 1037 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1038 if (loc == 0) { 1039 len = start + 1; 1040 start = 0; 1041 loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[0], 1042 (u_char *)fragtbl[fs->fs_frag], 1043 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1044 if (loc == 0) { 1045 printf("start = %d, len = %d, fs = %s\n", 1046 start, len, fs->fs_fsmnt); 1047 panic("ffs_alloccg: map corrupted"); 1048 /* NOTREACHED */ 1049 } 1050 } 1051 bno = (start + len - loc) * NBBY; 1052 cgp->cg_frotor = bno; 1053 /* 1054 * found the byte in the map 1055 * sift through the bits to find the selected frag 1056 */ 1057 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 1058 blk = blkmap(fs, cg_blksfree(cgp), bno); 1059 blk <<= 1; 1060 field = around[allocsiz]; 1061 subfield = inside[allocsiz]; 1062 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 1063 if ((blk & field) == subfield) 1064 return (bno + pos); 1065 field <<= 1; 1066 subfield <<= 1; 1067 } 1068 } 1069 printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt); 1070 panic("ffs_alloccg: block not in map"); 1071 return (-1); 1072 } 1073 1074 /* 1075 * Fserr prints the name of a file system with an error diagnostic. 1076 * 1077 * The form of the error message is: 1078 * fs: error message 1079 */ 1080 static void 1081 ffs_fserr(fs, uid, cp) 1082 struct fs *fs; 1083 u_int uid; 1084 char *cp; 1085 { 1086 1087 log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp); 1088 } 1089