1 /* 2 * Copyright (c) 1982, 1986, 1989, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)ffs_alloc.c 8.7 (Berkeley) 02/14/94 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/mount.h> 16 #include <sys/kernel.h> 17 #include <sys/syslog.h> 18 19 #include <vm/vm.h> 20 21 #include <ufs/ufs/quota.h> 22 #include <ufs/ufs/inode.h> 23 24 #include <ufs/ffs/fs.h> 25 #include <ufs/ffs/ffs_extern.h> 26 27 extern u_long nextgennumber; 28 29 static daddr_t ffs_alloccg __P((struct inode *, int, daddr_t, int)); 30 static daddr_t ffs_alloccgblk __P((struct fs *, struct cg *, daddr_t)); 31 static daddr_t ffs_clusteralloc __P((struct inode *, int, daddr_t, int)); 32 static ino_t ffs_dirpref __P((struct fs *)); 33 static daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 34 static void ffs_fserr __P((struct fs *, u_int, char *)); 35 static u_long ffs_hashalloc 36 __P((struct inode *, int, long, int, u_long (*)())); 37 static ino_t ffs_nodealloccg __P((struct inode *, int, daddr_t, int)); 38 static daddr_t ffs_mapsearch __P((struct fs *, struct cg *, daddr_t, int)); 39 40 /* 41 * Allocate a block in the file system. 42 * 43 * The size of the requested block is given, which must be some 44 * multiple of fs_fsize and <= fs_bsize. 45 * A preference may be optionally specified. If a preference is given 46 * the following hierarchy is used to allocate a block: 47 * 1) allocate the requested block. 48 * 2) allocate a rotationally optimal block in the same cylinder. 49 * 3) allocate a block in the same cylinder group. 50 * 4) quadradically rehash into other cylinder groups, until an 51 * available block is located. 52 * If no block preference is given the following heirarchy is used 53 * to allocate a block: 54 * 1) allocate a block in the cylinder group that contains the 55 * inode for the file. 56 * 2) quadradically rehash into other cylinder groups, until an 57 * available block is located. 58 */ 59 ffs_alloc(ip, lbn, bpref, size, cred, bnp) 60 register struct inode *ip; 61 daddr_t lbn, bpref; 62 int size; 63 struct ucred *cred; 64 daddr_t *bnp; 65 { 66 register struct fs *fs; 67 daddr_t bno; 68 int cg, error; 69 70 *bnp = 0; 71 fs = ip->i_fs; 72 #ifdef DIAGNOSTIC 73 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 74 printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", 75 ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 76 panic("ffs_alloc: bad size"); 77 } 78 if (cred == NOCRED) 79 panic("ffs_alloc: missing credential\n"); 80 #endif /* DIAGNOSTIC */ 81 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 82 goto nospace; 83 if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 84 goto nospace; 85 #ifdef QUOTA 86 if (error = chkdq(ip, (long)btodb(size), cred, 0)) 87 return (error); 88 #endif 89 if (bpref >= fs->fs_size) 90 bpref = 0; 91 if (bpref == 0) 92 cg = ino_to_cg(fs, ip->i_number); 93 else 94 cg = dtog(fs, bpref); 95 bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 96 (u_long (*)())ffs_alloccg); 97 if (bno > 0) { 98 ip->i_blocks += btodb(size); 99 ip->i_flag |= IN_CHANGE | IN_UPDATE; 100 *bnp = bno; 101 return (0); 102 } 103 #ifdef QUOTA 104 /* 105 * Restore user's disk quota because allocation failed. 106 */ 107 (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 108 #endif 109 nospace: 110 ffs_fserr(fs, cred->cr_uid, "file system full"); 111 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 112 return (ENOSPC); 113 } 114 115 /* 116 * Reallocate a fragment to a bigger size 117 * 118 * The number and size of the old block is given, and a preference 119 * and new size is also specified. The allocator attempts to extend 120 * the original block. Failing that, the regular block allocator is 121 * invoked to get an appropriate block. 122 */ 123 ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp) 124 register struct inode *ip; 125 daddr_t lbprev; 126 daddr_t bpref; 127 int osize, nsize; 128 struct ucred *cred; 129 struct buf **bpp; 130 { 131 register struct fs *fs; 132 struct buf *bp; 133 int cg, request, error; 134 daddr_t bprev, bno; 135 136 *bpp = 0; 137 fs = ip->i_fs; 138 #ifdef DIAGNOSTIC 139 if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 140 (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 141 printf( 142 "dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n", 143 ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt); 144 panic("ffs_realloccg: bad size"); 145 } 146 if (cred == NOCRED) 147 panic("ffs_realloccg: missing credential\n"); 148 #endif /* DIAGNOSTIC */ 149 if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 150 goto nospace; 151 if ((bprev = ip->i_db[lbprev]) == 0) { 152 printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n", 153 ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); 154 panic("ffs_realloccg: bad bprev"); 155 } 156 /* 157 * Allocate the extra space in the buffer. 158 */ 159 if (error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp)) { 160 brelse(bp); 161 return (error); 162 } 163 #ifdef QUOTA 164 if (error = chkdq(ip, (long)btodb(nsize - osize), cred, 0)) { 165 brelse(bp); 166 return (error); 167 } 168 #endif 169 /* 170 * Check for extension in the existing location. 171 */ 172 cg = dtog(fs, bprev); 173 if (bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize)) { 174 if (bp->b_blkno != fsbtodb(fs, bno)) 175 panic("bad blockno"); 176 ip->i_blocks += btodb(nsize - osize); 177 ip->i_flag |= IN_CHANGE | IN_UPDATE; 178 allocbuf(bp, nsize); 179 bp->b_flags |= B_DONE; 180 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 181 *bpp = bp; 182 return (0); 183 } 184 /* 185 * Allocate a new disk location. 186 */ 187 if (bpref >= fs->fs_size) 188 bpref = 0; 189 switch ((int)fs->fs_optim) { 190 case FS_OPTSPACE: 191 /* 192 * Allocate an exact sized fragment. Although this makes 193 * best use of space, we will waste time relocating it if 194 * the file continues to grow. If the fragmentation is 195 * less than half of the minimum free reserve, we choose 196 * to begin optimizing for time. 197 */ 198 request = nsize; 199 if (fs->fs_minfree < 5 || 200 fs->fs_cstotal.cs_nffree > 201 fs->fs_dsize * fs->fs_minfree / (2 * 100)) 202 break; 203 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 204 fs->fs_fsmnt); 205 fs->fs_optim = FS_OPTTIME; 206 break; 207 case FS_OPTTIME: 208 /* 209 * At this point we have discovered a file that is trying to 210 * grow a small fragment to a larger fragment. To save time, 211 * we allocate a full sized block, then free the unused portion. 212 * If the file continues to grow, the `ffs_fragextend' call 213 * above will be able to grow it in place without further 214 * copying. If aberrant programs cause disk fragmentation to 215 * grow within 2% of the free reserve, we choose to begin 216 * optimizing for space. 217 */ 218 request = fs->fs_bsize; 219 if (fs->fs_cstotal.cs_nffree < 220 fs->fs_dsize * (fs->fs_minfree - 2) / 100) 221 break; 222 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 223 fs->fs_fsmnt); 224 fs->fs_optim = FS_OPTSPACE; 225 break; 226 default: 227 printf("dev = 0x%x, optim = %d, fs = %s\n", 228 ip->i_dev, fs->fs_optim, fs->fs_fsmnt); 229 panic("ffs_realloccg: bad optim"); 230 /* NOTREACHED */ 231 } 232 bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 233 (u_long (*)())ffs_alloccg); 234 if (bno > 0) { 235 bp->b_blkno = fsbtodb(fs, bno); 236 (void) vnode_pager_uncache(ITOV(ip)); 237 ffs_blkfree(ip, bprev, (long)osize); 238 if (nsize < request) 239 ffs_blkfree(ip, bno + numfrags(fs, nsize), 240 (long)(request - nsize)); 241 ip->i_blocks += btodb(nsize - osize); 242 ip->i_flag |= IN_CHANGE | IN_UPDATE; 243 allocbuf(bp, nsize); 244 bp->b_flags |= B_DONE; 245 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 246 *bpp = bp; 247 return (0); 248 } 249 #ifdef QUOTA 250 /* 251 * Restore user's disk quota because allocation failed. 252 */ 253 (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 254 #endif 255 brelse(bp); 256 nospace: 257 /* 258 * no space available 259 */ 260 ffs_fserr(fs, cred->cr_uid, "file system full"); 261 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 262 return (ENOSPC); 263 } 264 265 /* 266 * Reallocate a sequence of blocks into a contiguous sequence of blocks. 267 * 268 * The vnode and an array of buffer pointers for a range of sequential 269 * logical blocks to be made contiguous is given. The allocator attempts 270 * to find a range of sequential blocks starting as close as possible to 271 * an fs_rotdelay offset from the end of the allocation for the logical 272 * block immediately preceeding the current range. If successful, the 273 * physical block numbers in the buffer pointers and in the inode are 274 * changed to reflect the new allocation. If unsuccessful, the allocation 275 * is left unchanged. The success in doing the reallocation is returned. 276 * Note that the error return is not reflected back to the user. Rather 277 * the previous block allocation will be used. 278 */ 279 int 280 ffs_reallocblks(ap) 281 struct vop_reallocblks_args /* { 282 struct vnode *a_vp; 283 struct cluster_save *a_buflist; 284 } */ *ap; 285 { 286 struct fs *fs; 287 struct inode *ip; 288 struct vnode *vp; 289 struct buf *sbp, *ebp; 290 daddr_t *bap, *sbap, *ebap; 291 struct cluster_save *buflist; 292 daddr_t start_lbn, end_lbn, soff, eoff, newblk, blkno; 293 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 294 int i, len, start_lvl, end_lvl, pref, ssize; 295 296 vp = ap->a_vp; 297 ip = VTOI(vp); 298 fs = ip->i_fs; 299 if (fs->fs_contigsumsize <= 0) 300 return (ENOSPC); 301 buflist = ap->a_buflist; 302 len = buflist->bs_nchildren; 303 start_lbn = buflist->bs_children[0]->b_lblkno; 304 end_lbn = start_lbn + len - 1; 305 #ifdef DIAGNOSTIC 306 for (i = 1; i < len; i++) 307 if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 308 panic("ffs_reallocblks: non-cluster"); 309 #endif 310 /* 311 * If the latest allocation is in a new cylinder group, assume that 312 * the filesystem has decided to move and do not force it back to 313 * the previous cylinder group. 314 */ 315 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 316 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 317 return (ENOSPC); 318 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 319 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 320 return (ENOSPC); 321 /* 322 * Get the starting offset and block map for the first block. 323 */ 324 if (start_lvl == 0) { 325 sbap = &ip->i_db[0]; 326 soff = start_lbn; 327 } else { 328 idp = &start_ap[start_lvl - 1]; 329 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 330 brelse(sbp); 331 return (ENOSPC); 332 } 333 sbap = (daddr_t *)sbp->b_data; 334 soff = idp->in_off; 335 } 336 /* 337 * Find the preferred location for the cluster. 338 */ 339 pref = ffs_blkpref(ip, start_lbn, soff, sbap); 340 /* 341 * If the block range spans two block maps, get the second map. 342 */ 343 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 344 ssize = len; 345 } else { 346 #ifdef DIAGNOSTIC 347 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 348 panic("ffs_reallocblk: start == end"); 349 #endif 350 ssize = len - (idp->in_off + 1); 351 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 352 goto fail; 353 ebap = (daddr_t *)ebp->b_data; 354 } 355 /* 356 * Search the block map looking for an allocation of the desired size. 357 */ 358 if ((newblk = (daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 359 len, (u_long (*)())ffs_clusteralloc)) == 0) 360 goto fail; 361 /* 362 * We have found a new contiguous block. 363 * 364 * First we have to replace the old block pointers with the new 365 * block pointers in the inode and indirect blocks associated 366 * with the file. 367 */ 368 blkno = newblk; 369 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 370 if (i == ssize) 371 bap = ebap; 372 #ifdef DIAGNOSTIC 373 if (buflist->bs_children[i]->b_blkno != fsbtodb(fs, *bap)) 374 panic("ffs_reallocblks: alloc mismatch"); 375 #endif 376 *bap++ = blkno; 377 } 378 /* 379 * Next we must write out the modified inode and indirect blocks. 380 * The writes are synchronous since the old block values may have 381 * been written to disk. 382 * 383 * These writes should be changed to be bdwrites (and the VOP_UPDATE 384 * dropped) when a flag has been added to the buffers and inodes 385 * to detect when they have been written. It should be set when the 386 * cluster is started and cleared whenever the buffer or inode is 387 * flushed. We can then check below to see if it is set, and do 388 * the synchronous write only when it has been cleared. 389 */ 390 if (sbap != &ip->i_db[0]) { 391 bwrite(sbp); 392 } else { 393 ip->i_flag |= IN_CHANGE | IN_UPDATE; 394 VOP_UPDATE(vp, &time, &time, MNT_WAIT); 395 } 396 if (ssize < len) 397 bwrite(ebp); 398 /* 399 * Last, free the old blocks and assign the new blocks to the buffers. 400 */ 401 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 402 ffs_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno), 403 fs->fs_bsize); 404 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 405 } 406 return (0); 407 408 fail: 409 if (ssize < len) 410 brelse(ebp); 411 if (sbap != &ip->i_db[0]) 412 brelse(sbp); 413 return (ENOSPC); 414 } 415 416 /* 417 * Allocate an inode in the file system. 418 * 419 * If allocating a directory, use ffs_dirpref to select the inode. 420 * If allocating in a directory, the following hierarchy is followed: 421 * 1) allocate the preferred inode. 422 * 2) allocate an inode in the same cylinder group. 423 * 3) quadradically rehash into other cylinder groups, until an 424 * available inode is located. 425 * If no inode preference is given the following heirarchy is used 426 * to allocate an inode: 427 * 1) allocate an inode in cylinder group 0. 428 * 2) quadradically rehash into other cylinder groups, until an 429 * available inode is located. 430 */ 431 ffs_valloc(ap) 432 struct vop_valloc_args /* { 433 struct vnode *a_pvp; 434 int a_mode; 435 struct ucred *a_cred; 436 struct vnode **a_vpp; 437 } */ *ap; 438 { 439 register struct vnode *pvp = ap->a_pvp; 440 register struct inode *pip; 441 register struct fs *fs; 442 register struct inode *ip; 443 mode_t mode = ap->a_mode; 444 ino_t ino, ipref; 445 int cg, error; 446 447 *ap->a_vpp = NULL; 448 pip = VTOI(pvp); 449 fs = pip->i_fs; 450 if (fs->fs_cstotal.cs_nifree == 0) 451 goto noinodes; 452 453 if ((mode & IFMT) == IFDIR) 454 ipref = ffs_dirpref(fs); 455 else 456 ipref = pip->i_number; 457 if (ipref >= fs->fs_ncg * fs->fs_ipg) 458 ipref = 0; 459 cg = ino_to_cg(fs, ipref); 460 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_nodealloccg); 461 if (ino == 0) 462 goto noinodes; 463 error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp); 464 if (error) { 465 VOP_VFREE(pvp, ino, mode); 466 return (error); 467 } 468 ip = VTOI(*ap->a_vpp); 469 if (ip->i_mode) { 470 printf("mode = 0%o, inum = %d, fs = %s\n", 471 ip->i_mode, ip->i_number, fs->fs_fsmnt); 472 panic("ffs_valloc: dup alloc"); 473 } 474 if (ip->i_blocks) { /* XXX */ 475 printf("free inode %s/%d had %d blocks\n", 476 fs->fs_fsmnt, ino, ip->i_blocks); 477 ip->i_blocks = 0; 478 } 479 ip->i_flags = 0; 480 /* 481 * Set up a new generation number for this inode. 482 */ 483 if (++nextgennumber < (u_long)time.tv_sec) 484 nextgennumber = time.tv_sec; 485 ip->i_gen = nextgennumber; 486 return (0); 487 noinodes: 488 ffs_fserr(fs, ap->a_cred->cr_uid, "out of inodes"); 489 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 490 return (ENOSPC); 491 } 492 493 /* 494 * Find a cylinder to place a directory. 495 * 496 * The policy implemented by this algorithm is to select from 497 * among those cylinder groups with above the average number of 498 * free inodes, the one with the smallest number of directories. 499 */ 500 static ino_t 501 ffs_dirpref(fs) 502 register struct fs *fs; 503 { 504 int cg, minndir, mincg, avgifree; 505 506 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 507 minndir = fs->fs_ipg; 508 mincg = 0; 509 for (cg = 0; cg < fs->fs_ncg; cg++) 510 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 511 fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 512 mincg = cg; 513 minndir = fs->fs_cs(fs, cg).cs_ndir; 514 } 515 return ((ino_t)(fs->fs_ipg * mincg)); 516 } 517 518 /* 519 * Select the desired position for the next block in a file. The file is 520 * logically divided into sections. The first section is composed of the 521 * direct blocks. Each additional section contains fs_maxbpg blocks. 522 * 523 * If no blocks have been allocated in the first section, the policy is to 524 * request a block in the same cylinder group as the inode that describes 525 * the file. If no blocks have been allocated in any other section, the 526 * policy is to place the section in a cylinder group with a greater than 527 * average number of free blocks. An appropriate cylinder group is found 528 * by using a rotor that sweeps the cylinder groups. When a new group of 529 * blocks is needed, the sweep begins in the cylinder group following the 530 * cylinder group from which the previous allocation was made. The sweep 531 * continues until a cylinder group with greater than the average number 532 * of free blocks is found. If the allocation is for the first block in an 533 * indirect block, the information on the previous allocation is unavailable; 534 * here a best guess is made based upon the logical block number being 535 * allocated. 536 * 537 * If a section is already partially allocated, the policy is to 538 * contiguously allocate fs_maxcontig blocks. The end of one of these 539 * contiguous blocks and the beginning of the next is physically separated 540 * so that the disk head will be in transit between them for at least 541 * fs_rotdelay milliseconds. This is to allow time for the processor to 542 * schedule another I/O transfer. 543 */ 544 daddr_t 545 ffs_blkpref(ip, lbn, indx, bap) 546 struct inode *ip; 547 daddr_t lbn; 548 int indx; 549 daddr_t *bap; 550 { 551 register struct fs *fs; 552 register int cg; 553 int avgbfree, startcg; 554 daddr_t nextblk; 555 556 fs = ip->i_fs; 557 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 558 if (lbn < NDADDR) { 559 cg = ino_to_cg(fs, ip->i_number); 560 return (fs->fs_fpg * cg + fs->fs_frag); 561 } 562 /* 563 * Find a cylinder with greater than average number of 564 * unused data blocks. 565 */ 566 if (indx == 0 || bap[indx - 1] == 0) 567 startcg = 568 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 569 else 570 startcg = dtog(fs, bap[indx - 1]) + 1; 571 startcg %= fs->fs_ncg; 572 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 573 for (cg = startcg; cg < fs->fs_ncg; cg++) 574 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 575 fs->fs_cgrotor = cg; 576 return (fs->fs_fpg * cg + fs->fs_frag); 577 } 578 for (cg = 0; cg <= startcg; cg++) 579 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 580 fs->fs_cgrotor = cg; 581 return (fs->fs_fpg * cg + fs->fs_frag); 582 } 583 return (NULL); 584 } 585 /* 586 * One or more previous blocks have been laid out. If less 587 * than fs_maxcontig previous blocks are contiguous, the 588 * next block is requested contiguously, otherwise it is 589 * requested rotationally delayed by fs_rotdelay milliseconds. 590 */ 591 nextblk = bap[indx - 1] + fs->fs_frag; 592 if (indx < fs->fs_maxcontig || bap[indx - fs->fs_maxcontig] + 593 blkstofrags(fs, fs->fs_maxcontig) != nextblk) 594 return (nextblk); 595 if (fs->fs_rotdelay != 0) 596 /* 597 * Here we convert ms of delay to frags as: 598 * (frags) = (ms) * (rev/sec) * (sect/rev) / 599 * ((sect/frag) * (ms/sec)) 600 * then round up to the next block. 601 */ 602 nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 603 (NSPF(fs) * 1000), fs->fs_frag); 604 return (nextblk); 605 } 606 607 /* 608 * Implement the cylinder overflow algorithm. 609 * 610 * The policy implemented by this algorithm is: 611 * 1) allocate the block in its requested cylinder group. 612 * 2) quadradically rehash on the cylinder group number. 613 * 3) brute force search for a free block. 614 */ 615 /*VARARGS5*/ 616 static u_long 617 ffs_hashalloc(ip, cg, pref, size, allocator) 618 struct inode *ip; 619 int cg; 620 long pref; 621 int size; /* size for data blocks, mode for inodes */ 622 u_long (*allocator)(); 623 { 624 register struct fs *fs; 625 long result; 626 int i, icg = cg; 627 628 fs = ip->i_fs; 629 /* 630 * 1: preferred cylinder group 631 */ 632 result = (*allocator)(ip, cg, pref, size); 633 if (result) 634 return (result); 635 /* 636 * 2: quadratic rehash 637 */ 638 for (i = 1; i < fs->fs_ncg; i *= 2) { 639 cg += i; 640 if (cg >= fs->fs_ncg) 641 cg -= fs->fs_ncg; 642 result = (*allocator)(ip, cg, 0, size); 643 if (result) 644 return (result); 645 } 646 /* 647 * 3: brute force search 648 * Note that we start at i == 2, since 0 was checked initially, 649 * and 1 is always checked in the quadratic rehash. 650 */ 651 cg = (icg + 2) % fs->fs_ncg; 652 for (i = 2; i < fs->fs_ncg; i++) { 653 result = (*allocator)(ip, cg, 0, size); 654 if (result) 655 return (result); 656 cg++; 657 if (cg == fs->fs_ncg) 658 cg = 0; 659 } 660 return (NULL); 661 } 662 663 /* 664 * Determine whether a fragment can be extended. 665 * 666 * Check to see if the necessary fragments are available, and 667 * if they are, allocate them. 668 */ 669 static daddr_t 670 ffs_fragextend(ip, cg, bprev, osize, nsize) 671 struct inode *ip; 672 int cg; 673 long bprev; 674 int osize, nsize; 675 { 676 register struct fs *fs; 677 register struct cg *cgp; 678 struct buf *bp; 679 long bno; 680 int frags, bbase; 681 int i, error; 682 683 fs = ip->i_fs; 684 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 685 return (NULL); 686 frags = numfrags(fs, nsize); 687 bbase = fragnum(fs, bprev); 688 if (bbase > fragnum(fs, (bprev + frags - 1))) { 689 /* cannot extend across a block boundary */ 690 return (NULL); 691 } 692 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 693 (int)fs->fs_cgsize, NOCRED, &bp); 694 if (error) { 695 brelse(bp); 696 return (NULL); 697 } 698 cgp = (struct cg *)bp->b_data; 699 if (!cg_chkmagic(cgp)) { 700 brelse(bp); 701 return (NULL); 702 } 703 cgp->cg_time = time.tv_sec; 704 bno = dtogd(fs, bprev); 705 for (i = numfrags(fs, osize); i < frags; i++) 706 if (isclr(cg_blksfree(cgp), bno + i)) { 707 brelse(bp); 708 return (NULL); 709 } 710 /* 711 * the current fragment can be extended 712 * deduct the count on fragment being extended into 713 * increase the count on the remaining fragment (if any) 714 * allocate the extended piece 715 */ 716 for (i = frags; i < fs->fs_frag - bbase; i++) 717 if (isclr(cg_blksfree(cgp), bno + i)) 718 break; 719 cgp->cg_frsum[i - numfrags(fs, osize)]--; 720 if (i != frags) 721 cgp->cg_frsum[i - frags]++; 722 for (i = numfrags(fs, osize); i < frags; i++) { 723 clrbit(cg_blksfree(cgp), bno + i); 724 cgp->cg_cs.cs_nffree--; 725 fs->fs_cstotal.cs_nffree--; 726 fs->fs_cs(fs, cg).cs_nffree--; 727 } 728 fs->fs_fmod = 1; 729 bdwrite(bp); 730 return (bprev); 731 } 732 733 /* 734 * Determine whether a block can be allocated. 735 * 736 * Check to see if a block of the appropriate size is available, 737 * and if it is, allocate it. 738 */ 739 static daddr_t 740 ffs_alloccg(ip, cg, bpref, size) 741 struct inode *ip; 742 int cg; 743 daddr_t bpref; 744 int size; 745 { 746 register struct fs *fs; 747 register struct cg *cgp; 748 struct buf *bp; 749 register int i; 750 int error, bno, frags, allocsiz; 751 752 fs = ip->i_fs; 753 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 754 return (NULL); 755 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 756 (int)fs->fs_cgsize, NOCRED, &bp); 757 if (error) { 758 brelse(bp); 759 return (NULL); 760 } 761 cgp = (struct cg *)bp->b_data; 762 if (!cg_chkmagic(cgp) || 763 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 764 brelse(bp); 765 return (NULL); 766 } 767 cgp->cg_time = time.tv_sec; 768 if (size == fs->fs_bsize) { 769 bno = ffs_alloccgblk(fs, cgp, bpref); 770 bdwrite(bp); 771 return (bno); 772 } 773 /* 774 * check to see if any fragments are already available 775 * allocsiz is the size which will be allocated, hacking 776 * it down to a smaller size if necessary 777 */ 778 frags = numfrags(fs, size); 779 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 780 if (cgp->cg_frsum[allocsiz] != 0) 781 break; 782 if (allocsiz == fs->fs_frag) { 783 /* 784 * no fragments were available, so a block will be 785 * allocated, and hacked up 786 */ 787 if (cgp->cg_cs.cs_nbfree == 0) { 788 brelse(bp); 789 return (NULL); 790 } 791 bno = ffs_alloccgblk(fs, cgp, bpref); 792 bpref = dtogd(fs, bno); 793 for (i = frags; i < fs->fs_frag; i++) 794 setbit(cg_blksfree(cgp), bpref + i); 795 i = fs->fs_frag - frags; 796 cgp->cg_cs.cs_nffree += i; 797 fs->fs_cstotal.cs_nffree += i; 798 fs->fs_cs(fs, cg).cs_nffree += i; 799 fs->fs_fmod = 1; 800 cgp->cg_frsum[i]++; 801 bdwrite(bp); 802 return (bno); 803 } 804 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 805 if (bno < 0) { 806 brelse(bp); 807 return (NULL); 808 } 809 for (i = 0; i < frags; i++) 810 clrbit(cg_blksfree(cgp), bno + i); 811 cgp->cg_cs.cs_nffree -= frags; 812 fs->fs_cstotal.cs_nffree -= frags; 813 fs->fs_cs(fs, cg).cs_nffree -= frags; 814 fs->fs_fmod = 1; 815 cgp->cg_frsum[allocsiz]--; 816 if (frags != allocsiz) 817 cgp->cg_frsum[allocsiz - frags]++; 818 bdwrite(bp); 819 return (cg * fs->fs_fpg + bno); 820 } 821 822 /* 823 * Allocate a block in a cylinder group. 824 * 825 * This algorithm implements the following policy: 826 * 1) allocate the requested block. 827 * 2) allocate a rotationally optimal block in the same cylinder. 828 * 3) allocate the next available block on the block rotor for the 829 * specified cylinder group. 830 * Note that this routine only allocates fs_bsize blocks; these 831 * blocks may be fragmented by the routine that allocates them. 832 */ 833 static daddr_t 834 ffs_alloccgblk(fs, cgp, bpref) 835 register struct fs *fs; 836 register struct cg *cgp; 837 daddr_t bpref; 838 { 839 daddr_t bno, blkno; 840 int cylno, pos, delta; 841 short *cylbp; 842 register int i; 843 844 if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 845 bpref = cgp->cg_rotor; 846 goto norot; 847 } 848 bpref = blknum(fs, bpref); 849 bpref = dtogd(fs, bpref); 850 /* 851 * if the requested block is available, use it 852 */ 853 if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { 854 bno = bpref; 855 goto gotit; 856 } 857 /* 858 * check for a block available on the same cylinder 859 */ 860 cylno = cbtocylno(fs, bpref); 861 if (cg_blktot(cgp)[cylno] == 0) 862 goto norot; 863 if (fs->fs_cpc == 0) { 864 /* 865 * Block layout information is not available. 866 * Leaving bpref unchanged means we take the 867 * next available free block following the one 868 * we just allocated. Hopefully this will at 869 * least hit a track cache on drives of unknown 870 * geometry (e.g. SCSI). 871 */ 872 goto norot; 873 } 874 /* 875 * check the summary information to see if a block is 876 * available in the requested cylinder starting at the 877 * requested rotational position and proceeding around. 878 */ 879 cylbp = cg_blks(fs, cgp, cylno); 880 pos = cbtorpos(fs, bpref); 881 for (i = pos; i < fs->fs_nrpos; i++) 882 if (cylbp[i] > 0) 883 break; 884 if (i == fs->fs_nrpos) 885 for (i = 0; i < pos; i++) 886 if (cylbp[i] > 0) 887 break; 888 if (cylbp[i] > 0) { 889 /* 890 * found a rotational position, now find the actual 891 * block. A panic if none is actually there. 892 */ 893 pos = cylno % fs->fs_cpc; 894 bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 895 if (fs_postbl(fs, pos)[i] == -1) { 896 printf("pos = %d, i = %d, fs = %s\n", 897 pos, i, fs->fs_fsmnt); 898 panic("ffs_alloccgblk: cyl groups corrupted"); 899 } 900 for (i = fs_postbl(fs, pos)[i];; ) { 901 if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) { 902 bno = blkstofrags(fs, (bno + i)); 903 goto gotit; 904 } 905 delta = fs_rotbl(fs)[i]; 906 if (delta <= 0 || 907 delta + i > fragstoblks(fs, fs->fs_fpg)) 908 break; 909 i += delta; 910 } 911 printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 912 panic("ffs_alloccgblk: can't find blk in cyl"); 913 } 914 norot: 915 /* 916 * no blocks in the requested cylinder, so take next 917 * available one in this cylinder group. 918 */ 919 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 920 if (bno < 0) 921 return (NULL); 922 cgp->cg_rotor = bno; 923 gotit: 924 blkno = fragstoblks(fs, bno); 925 ffs_clrblock(fs, cg_blksfree(cgp), (long)blkno); 926 ffs_clusteracct(fs, cgp, blkno, -1); 927 cgp->cg_cs.cs_nbfree--; 928 fs->fs_cstotal.cs_nbfree--; 929 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 930 cylno = cbtocylno(fs, bno); 931 cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 932 cg_blktot(cgp)[cylno]--; 933 fs->fs_fmod = 1; 934 return (cgp->cg_cgx * fs->fs_fpg + bno); 935 } 936 937 /* 938 * Determine whether a cluster can be allocated. 939 * 940 * We do not currently check for optimal rotational layout if there 941 * are multiple choices in the same cylinder group. Instead we just 942 * take the first one that we find following bpref. 943 */ 944 static daddr_t 945 ffs_clusteralloc(ip, cg, bpref, len) 946 struct inode *ip; 947 int cg; 948 daddr_t bpref; 949 int len; 950 { 951 register struct fs *fs; 952 register struct cg *cgp; 953 struct buf *bp; 954 int i, run, bno, bit, map; 955 u_char *mapp; 956 957 fs = ip->i_fs; 958 if (fs->fs_cs(fs, cg).cs_nbfree < len) 959 return (NULL); 960 if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 961 NOCRED, &bp)) 962 goto fail; 963 cgp = (struct cg *)bp->b_data; 964 if (!cg_chkmagic(cgp)) 965 goto fail; 966 /* 967 * Check to see if a cluster of the needed size (or bigger) is 968 * available in this cylinder group. 969 */ 970 for (i = len; i <= fs->fs_contigsumsize; i++) 971 if (cg_clustersum(cgp)[i] > 0) 972 break; 973 if (i > fs->fs_contigsumsize) 974 goto fail; 975 /* 976 * Search the cluster map to find a big enough cluster. 977 * We take the first one that we find, even if it is larger 978 * than we need as we prefer to get one close to the previous 979 * block allocation. We do not search before the current 980 * preference point as we do not want to allocate a block 981 * that is allocated before the previous one (as we will 982 * then have to wait for another pass of the elevator 983 * algorithm before it will be read). We prefer to fail and 984 * be recalled to try an allocation in the next cylinder group. 985 */ 986 if (dtog(fs, bpref) != cg) 987 bpref = 0; 988 else 989 bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 990 mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 991 map = *mapp++; 992 bit = 1 << (bpref % NBBY); 993 for (run = 0, i = bpref; i < cgp->cg_nclusterblks; i++) { 994 if ((map & bit) == 0) { 995 run = 0; 996 } else { 997 run++; 998 if (run == len) 999 break; 1000 } 1001 if ((i & (NBBY - 1)) != (NBBY - 1)) { 1002 bit <<= 1; 1003 } else { 1004 map = *mapp++; 1005 bit = 1; 1006 } 1007 } 1008 if (i == cgp->cg_nclusterblks) 1009 goto fail; 1010 /* 1011 * Allocate the cluster that we have found. 1012 */ 1013 bno = cg * fs->fs_fpg + blkstofrags(fs, i - run + 1); 1014 len = blkstofrags(fs, len); 1015 for (i = 0; i < len; i += fs->fs_frag) 1016 if (ffs_alloccgblk(fs, cgp, bno + i) != bno + i) 1017 panic("ffs_clusteralloc: lost block"); 1018 brelse(bp); 1019 return (bno); 1020 1021 fail: 1022 brelse(bp); 1023 return (0); 1024 } 1025 1026 /* 1027 * Determine whether an inode can be allocated. 1028 * 1029 * Check to see if an inode is available, and if it is, 1030 * allocate it using the following policy: 1031 * 1) allocate the requested inode. 1032 * 2) allocate the next available inode after the requested 1033 * inode in the specified cylinder group. 1034 */ 1035 static ino_t 1036 ffs_nodealloccg(ip, cg, ipref, mode) 1037 struct inode *ip; 1038 int cg; 1039 daddr_t ipref; 1040 int mode; 1041 { 1042 register struct fs *fs; 1043 register struct cg *cgp; 1044 struct buf *bp; 1045 int error, start, len, loc, map, i; 1046 1047 fs = ip->i_fs; 1048 if (fs->fs_cs(fs, cg).cs_nifree == 0) 1049 return (NULL); 1050 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1051 (int)fs->fs_cgsize, NOCRED, &bp); 1052 if (error) { 1053 brelse(bp); 1054 return (NULL); 1055 } 1056 cgp = (struct cg *)bp->b_data; 1057 if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 1058 brelse(bp); 1059 return (NULL); 1060 } 1061 cgp->cg_time = time.tv_sec; 1062 if (ipref) { 1063 ipref %= fs->fs_ipg; 1064 if (isclr(cg_inosused(cgp), ipref)) 1065 goto gotit; 1066 } 1067 start = cgp->cg_irotor / NBBY; 1068 len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 1069 loc = skpc(0xff, len, &cg_inosused(cgp)[start]); 1070 if (loc == 0) { 1071 len = start + 1; 1072 start = 0; 1073 loc = skpc(0xff, len, &cg_inosused(cgp)[0]); 1074 if (loc == 0) { 1075 printf("cg = %d, irotor = %d, fs = %s\n", 1076 cg, cgp->cg_irotor, fs->fs_fsmnt); 1077 panic("ffs_nodealloccg: map corrupted"); 1078 /* NOTREACHED */ 1079 } 1080 } 1081 i = start + len - loc; 1082 map = cg_inosused(cgp)[i]; 1083 ipref = i * NBBY; 1084 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 1085 if ((map & i) == 0) { 1086 cgp->cg_irotor = ipref; 1087 goto gotit; 1088 } 1089 } 1090 printf("fs = %s\n", fs->fs_fsmnt); 1091 panic("ffs_nodealloccg: block not in map"); 1092 /* NOTREACHED */ 1093 gotit: 1094 setbit(cg_inosused(cgp), ipref); 1095 cgp->cg_cs.cs_nifree--; 1096 fs->fs_cstotal.cs_nifree--; 1097 fs->fs_cs(fs, cg).cs_nifree--; 1098 fs->fs_fmod = 1; 1099 if ((mode & IFMT) == IFDIR) { 1100 cgp->cg_cs.cs_ndir++; 1101 fs->fs_cstotal.cs_ndir++; 1102 fs->fs_cs(fs, cg).cs_ndir++; 1103 } 1104 bdwrite(bp); 1105 return (cg * fs->fs_ipg + ipref); 1106 } 1107 1108 /* 1109 * Free a block or fragment. 1110 * 1111 * The specified block or fragment is placed back in the 1112 * free map. If a fragment is deallocated, a possible 1113 * block reassembly is checked. 1114 */ 1115 ffs_blkfree(ip, bno, size) 1116 register struct inode *ip; 1117 daddr_t bno; 1118 long size; 1119 { 1120 register struct fs *fs; 1121 register struct cg *cgp; 1122 struct buf *bp; 1123 daddr_t blkno; 1124 int i, error, cg, blk, frags, bbase; 1125 1126 fs = ip->i_fs; 1127 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1128 printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", 1129 ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 1130 panic("blkfree: bad size"); 1131 } 1132 cg = dtog(fs, bno); 1133 if ((u_int)bno >= fs->fs_size) { 1134 printf("bad block %d, ino %d\n", bno, ip->i_number); 1135 ffs_fserr(fs, ip->i_uid, "bad block"); 1136 return; 1137 } 1138 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1139 (int)fs->fs_cgsize, NOCRED, &bp); 1140 if (error) { 1141 brelse(bp); 1142 return; 1143 } 1144 cgp = (struct cg *)bp->b_data; 1145 if (!cg_chkmagic(cgp)) { 1146 brelse(bp); 1147 return; 1148 } 1149 cgp->cg_time = time.tv_sec; 1150 bno = dtogd(fs, bno); 1151 if (size == fs->fs_bsize) { 1152 blkno = fragstoblks(fs, bno); 1153 if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 1154 printf("dev = 0x%x, block = %d, fs = %s\n", 1155 ip->i_dev, bno, fs->fs_fsmnt); 1156 panic("blkfree: freeing free block"); 1157 } 1158 ffs_setblock(fs, cg_blksfree(cgp), blkno); 1159 ffs_clusteracct(fs, cgp, blkno, 1); 1160 cgp->cg_cs.cs_nbfree++; 1161 fs->fs_cstotal.cs_nbfree++; 1162 fs->fs_cs(fs, cg).cs_nbfree++; 1163 i = cbtocylno(fs, bno); 1164 cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 1165 cg_blktot(cgp)[i]++; 1166 } else { 1167 bbase = bno - fragnum(fs, bno); 1168 /* 1169 * decrement the counts associated with the old frags 1170 */ 1171 blk = blkmap(fs, cg_blksfree(cgp), bbase); 1172 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 1173 /* 1174 * deallocate the fragment 1175 */ 1176 frags = numfrags(fs, size); 1177 for (i = 0; i < frags; i++) { 1178 if (isset(cg_blksfree(cgp), bno + i)) { 1179 printf("dev = 0x%x, block = %d, fs = %s\n", 1180 ip->i_dev, bno + i, fs->fs_fsmnt); 1181 panic("blkfree: freeing free frag"); 1182 } 1183 setbit(cg_blksfree(cgp), bno + i); 1184 } 1185 cgp->cg_cs.cs_nffree += i; 1186 fs->fs_cstotal.cs_nffree += i; 1187 fs->fs_cs(fs, cg).cs_nffree += i; 1188 /* 1189 * add back in counts associated with the new frags 1190 */ 1191 blk = blkmap(fs, cg_blksfree(cgp), bbase); 1192 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 1193 /* 1194 * if a complete block has been reassembled, account for it 1195 */ 1196 blkno = fragstoblks(fs, bbase); 1197 if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 1198 cgp->cg_cs.cs_nffree -= fs->fs_frag; 1199 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 1200 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 1201 ffs_clusteracct(fs, cgp, blkno, 1); 1202 cgp->cg_cs.cs_nbfree++; 1203 fs->fs_cstotal.cs_nbfree++; 1204 fs->fs_cs(fs, cg).cs_nbfree++; 1205 i = cbtocylno(fs, bbase); 1206 cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 1207 cg_blktot(cgp)[i]++; 1208 } 1209 } 1210 fs->fs_fmod = 1; 1211 bdwrite(bp); 1212 } 1213 1214 /* 1215 * Free an inode. 1216 * 1217 * The specified inode is placed back in the free map. 1218 */ 1219 int 1220 ffs_vfree(ap) 1221 struct vop_vfree_args /* { 1222 struct vnode *a_pvp; 1223 ino_t a_ino; 1224 int a_mode; 1225 } */ *ap; 1226 { 1227 register struct fs *fs; 1228 register struct cg *cgp; 1229 register struct inode *pip; 1230 ino_t ino = ap->a_ino; 1231 struct buf *bp; 1232 int error, cg; 1233 1234 pip = VTOI(ap->a_pvp); 1235 fs = pip->i_fs; 1236 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 1237 panic("ifree: range: dev = 0x%x, ino = %d, fs = %s\n", 1238 pip->i_dev, ino, fs->fs_fsmnt); 1239 cg = ino_to_cg(fs, ino); 1240 error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1241 (int)fs->fs_cgsize, NOCRED, &bp); 1242 if (error) { 1243 brelse(bp); 1244 return (0); 1245 } 1246 cgp = (struct cg *)bp->b_data; 1247 if (!cg_chkmagic(cgp)) { 1248 brelse(bp); 1249 return (0); 1250 } 1251 cgp->cg_time = time.tv_sec; 1252 ino %= fs->fs_ipg; 1253 if (isclr(cg_inosused(cgp), ino)) { 1254 printf("dev = 0x%x, ino = %d, fs = %s\n", 1255 pip->i_dev, ino, fs->fs_fsmnt); 1256 if (fs->fs_ronly == 0) 1257 panic("ifree: freeing free inode"); 1258 } 1259 clrbit(cg_inosused(cgp), ino); 1260 if (ino < cgp->cg_irotor) 1261 cgp->cg_irotor = ino; 1262 cgp->cg_cs.cs_nifree++; 1263 fs->fs_cstotal.cs_nifree++; 1264 fs->fs_cs(fs, cg).cs_nifree++; 1265 if ((ap->a_mode & IFMT) == IFDIR) { 1266 cgp->cg_cs.cs_ndir--; 1267 fs->fs_cstotal.cs_ndir--; 1268 fs->fs_cs(fs, cg).cs_ndir--; 1269 } 1270 fs->fs_fmod = 1; 1271 bdwrite(bp); 1272 return (0); 1273 } 1274 1275 /* 1276 * Find a block of the specified size in the specified cylinder group. 1277 * 1278 * It is a panic if a request is made to find a block if none are 1279 * available. 1280 */ 1281 static daddr_t 1282 ffs_mapsearch(fs, cgp, bpref, allocsiz) 1283 register struct fs *fs; 1284 register struct cg *cgp; 1285 daddr_t bpref; 1286 int allocsiz; 1287 { 1288 daddr_t bno; 1289 int start, len, loc, i; 1290 int blk, field, subfield, pos; 1291 1292 /* 1293 * find the fragment by searching through the free block 1294 * map for an appropriate bit pattern 1295 */ 1296 if (bpref) 1297 start = dtogd(fs, bpref) / NBBY; 1298 else 1299 start = cgp->cg_frotor / NBBY; 1300 len = howmany(fs->fs_fpg, NBBY) - start; 1301 loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[start], 1302 (u_char *)fragtbl[fs->fs_frag], 1303 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1304 if (loc == 0) { 1305 len = start + 1; 1306 start = 0; 1307 loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[0], 1308 (u_char *)fragtbl[fs->fs_frag], 1309 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1310 if (loc == 0) { 1311 printf("start = %d, len = %d, fs = %s\n", 1312 start, len, fs->fs_fsmnt); 1313 panic("ffs_alloccg: map corrupted"); 1314 /* NOTREACHED */ 1315 } 1316 } 1317 bno = (start + len - loc) * NBBY; 1318 cgp->cg_frotor = bno; 1319 /* 1320 * found the byte in the map 1321 * sift through the bits to find the selected frag 1322 */ 1323 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 1324 blk = blkmap(fs, cg_blksfree(cgp), bno); 1325 blk <<= 1; 1326 field = around[allocsiz]; 1327 subfield = inside[allocsiz]; 1328 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 1329 if ((blk & field) == subfield) 1330 return (bno + pos); 1331 field <<= 1; 1332 subfield <<= 1; 1333 } 1334 } 1335 printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt); 1336 panic("ffs_alloccg: block not in map"); 1337 return (-1); 1338 } 1339 1340 /* 1341 * Update the cluster map because of an allocation or free. 1342 * 1343 * Cnt == 1 means free; cnt == -1 means allocating. 1344 */ 1345 ffs_clusteracct(fs, cgp, blkno, cnt) 1346 struct fs *fs; 1347 struct cg *cgp; 1348 daddr_t blkno; 1349 int cnt; 1350 { 1351 long *sump; 1352 u_char *freemapp, *mapp; 1353 int i, start, end, forw, back, map, bit; 1354 1355 if (fs->fs_contigsumsize <= 0) 1356 return; 1357 freemapp = cg_clustersfree(cgp); 1358 sump = cg_clustersum(cgp); 1359 /* 1360 * Allocate or clear the actual block. 1361 */ 1362 if (cnt > 0) 1363 setbit(freemapp, blkno); 1364 else 1365 clrbit(freemapp, blkno); 1366 /* 1367 * Find the size of the cluster going forward. 1368 */ 1369 start = blkno + 1; 1370 end = start + fs->fs_contigsumsize; 1371 if (end >= cgp->cg_nclusterblks) 1372 end = cgp->cg_nclusterblks; 1373 mapp = &freemapp[start / NBBY]; 1374 map = *mapp++; 1375 bit = 1 << (start % NBBY); 1376 for (i = start; i < end; i++) { 1377 if ((map & bit) == 0) 1378 break; 1379 if ((i & (NBBY - 1)) != (NBBY - 1)) { 1380 bit <<= 1; 1381 } else { 1382 map = *mapp++; 1383 bit = 1; 1384 } 1385 } 1386 forw = i - start; 1387 /* 1388 * Find the size of the cluster going backward. 1389 */ 1390 start = blkno - 1; 1391 end = start - fs->fs_contigsumsize; 1392 if (end < 0) 1393 end = -1; 1394 mapp = &freemapp[start / NBBY]; 1395 map = *mapp--; 1396 bit = 1 << (start % NBBY); 1397 for (i = start; i > end; i--) { 1398 if ((map & bit) == 0) 1399 break; 1400 if ((i & (NBBY - 1)) != 0) { 1401 bit >>= 1; 1402 } else { 1403 map = *mapp--; 1404 bit = 1 << (NBBY - 1); 1405 } 1406 } 1407 back = start - i; 1408 /* 1409 * Account for old cluster and the possibly new forward and 1410 * back clusters. 1411 */ 1412 i = back + forw + 1; 1413 if (i > fs->fs_contigsumsize) 1414 i = fs->fs_contigsumsize; 1415 sump[i] += cnt; 1416 if (back > 0) 1417 sump[back] -= cnt; 1418 if (forw > 0) 1419 sump[forw] -= cnt; 1420 } 1421 1422 /* 1423 * Fserr prints the name of a file system with an error diagnostic. 1424 * 1425 * The form of the error message is: 1426 * fs: error message 1427 */ 1428 static void 1429 ffs_fserr(fs, uid, cp) 1430 struct fs *fs; 1431 u_int uid; 1432 char *cp; 1433 { 1434 1435 log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp); 1436 } 1437