1 /* Copyright (c) 1981 Regents of the University of California */ 2 3 static char vers[] = "@(#)lfs_alloc.c 1.3 09/22/81"; 4 5 /* alloc.c 4.8 81/03/08 */ 6 7 #include "../h/param.h" 8 #include "../h/systm.h" 9 #include "../h/mount.h" 10 #include "../h/fs.h" 11 #include "../h/conf.h" 12 #include "../h/buf.h" 13 #include "../h/inode.h" 14 #include "../h/dir.h" 15 #include "../h/user.h" 16 17 long hashalloc(); 18 long alloccg(); 19 long ialloccg(); 20 21 struct buf * 22 alloc(dev, ip, bpref, size) 23 dev_t dev; 24 struct inode *ip; 25 daddr_t bpref; 26 int size; 27 { 28 daddr_t bno; 29 register struct fs *fs; 30 struct buf *bp; 31 int cg; 32 33 fs = getfs(dev); 34 if (fs->fs_nbfree == 0 && size == BSIZE) 35 goto nospace; 36 if (bpref == 0) 37 cg = itog(ip->i_number, fs); 38 else 39 cg = dtog(bpref, fs); 40 bno = hashalloc(dev, fs, cg, (long)bpref, size, alloccg); 41 if (bno == 0) 42 goto nospace; 43 bp = getblk(dev, bno, size); 44 clrbuf(bp); 45 return (bp); 46 nospace: 47 fserr(fs, "file system full"); 48 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 49 u.u_error = ENOSPC; 50 return (NULL); 51 } 52 53 struct buf * 54 realloccg(dev, ip, bpref, osize, nsize) 55 dev_t dev; 56 struct inode *ip; 57 daddr_t bpref; 58 int osize, nsize; 59 { 60 daddr_t bno; 61 register struct fs *fs; 62 struct buf *bp; 63 int cg; 64 65 fs = getfs(dev); 66 if (bpref == 0) 67 cg = itog(ip->i_number, fs); 68 else 69 cg = dtog(bpref, fs); 70 bno = fragalloc(dev, fs, cg, (long)bpref, osize, nsize); 71 if (bno == 0) 72 goto nospace; 73 bp = getblk(dev, bno, osize); 74 bp->b_bcount += nsize - osize; 75 blkclr(bp->b_un.b_addr + osize, nsize - osize); 76 return (bp); 77 nospace: 78 fserr(fs, "file system full"); 79 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 80 u.u_error = ENOSPC; 81 return (NULL); 82 } 83 84 struct inode * 85 ialloc(dev, ipref, mode) 86 dev_t dev; 87 ino_t ipref; 88 int mode; 89 { 90 daddr_t ino; 91 register struct fs *fs; 92 register struct inode *ip; 93 int cg; 94 95 fs = getfs(dev); 96 if (fs->fs_nifree == 0) 97 goto noinodes; 98 cg = itog(ipref, fs); 99 ino = hashalloc(dev, fs, cg, (long)ipref, mode, ialloccg); 100 if (ino == 0) 101 goto noinodes; 102 ip = iget(dev, ino); 103 if (ip == NULL) { 104 ifree(dev, ino); 105 return (NULL); 106 } 107 if (ip->i_mode) 108 panic("ialloc: dup alloc"); 109 return (ip); 110 noinodes: 111 fserr(fs, "out of inodes"); 112 uprintf("\n%s: create failed, no inodes free\n", fs->fs_fsmnt); 113 u.u_error = ENOSPC; 114 return (NULL); 115 } 116 117 dipref(dev) 118 dev_t dev; 119 { 120 register struct fs *fs; 121 int cg, minndir, mincg; 122 123 fs = getfs(dev); 124 minndir = fs->fs_cs[0].cs_ndir; 125 mincg = 0; 126 for (cg = 1; cg < fs->fs_ncg; cg++) 127 if (fs->fs_cs[cg].cs_ndir < minndir) { 128 mincg = cg; 129 minndir = fs->fs_cs[cg].cs_ndir; 130 if (minndir == 0) 131 break; 132 } 133 return (fs->fs_ipg * mincg); 134 } 135 136 long 137 hashalloc(dev, fs, cg, pref, size, allocator) 138 dev_t dev; 139 register struct fs *fs; 140 int cg; 141 long pref; 142 int size; /* size for data blocks, mode for inodes */ 143 long (*allocator)(); 144 { 145 long result; 146 int i, icg = cg; 147 148 /* 149 * 1: preferred cylinder group 150 */ 151 result = (*allocator)(dev, fs, cg, pref, size); 152 if (result) 153 return (result); 154 /* 155 * 2: quadratic rehash 156 */ 157 for (i = 1; i < fs->fs_ncg; i *= 2) { 158 cg += i; 159 if (cg >= fs->fs_ncg) 160 cg -= fs->fs_ncg; 161 result = (*allocator)(dev, fs, cg, 0, size); 162 if (result) 163 return (result); 164 } 165 /* 166 * 3: brute force search 167 */ 168 cg = icg; 169 for (i = 0; i < fs->fs_ncg; i++) { 170 result = (*allocator)(dev, fs, cg, 0, size); 171 if (result) 172 return (result); 173 cg++; 174 if (cg == fs->fs_ncg) 175 cg = 0; 176 } 177 return (0); 178 } 179 180 daddr_t 181 fragalloc(dev, fs, cg, pref, osize, nsize) 182 dev_t dev; 183 register struct fs *fs; 184 int cg; 185 long pref; 186 int osize, nsize; 187 { 188 struct buf *bp; 189 struct cg *cgp; 190 int i; 191 192 if ((unsigned)osize > BSIZE || osize % FSIZE != 0 || 193 (unsigned)nsize > BSIZE || nsize % FSIZE != 0) 194 panic("fragalloc: bad size"); 195 bp = bread(dev, cgtod(cg, fs), BSIZE); 196 if (bp->b_flags & B_ERROR) 197 return (0); 198 cgp = bp->b_un.b_cg; 199 if (pref) { 200 pref %= fs->fs_fpg; 201 for (i = osize / FSIZE; i < nsize / FSIZE; i++) { 202 if (isclr(cgp->cg_free, pref + i)) 203 break; 204 } 205 if (i == nsize / FSIZE) 206 goto extendit; 207 } 208 /* 209 * MUST FIND ALTERNATE LOCATION 210 */ 211 panic("fragalloc: reallocation too hard!"); 212 brelse(bp); 213 return (0); 214 extendit: 215 for (i = osize / FSIZE; i < nsize / FSIZE; i++) { 216 clrbit(cgp->cg_free, pref + i); 217 cgp->cg_nffree--; 218 fs->fs_nffree--; 219 } 220 fs->fs_fmod++; 221 bdwrite(bp); 222 return (cg * fs->fs_fpg + pref); 223 } 224 225 daddr_t 226 alloccg(dev, fs, cg, bpref, size) 227 dev_t dev; 228 struct fs *fs; 229 int cg; 230 daddr_t bpref; 231 int size; 232 { 233 struct buf *bp; 234 struct cg *cgp; 235 int i; 236 237 if ((unsigned)size > BSIZE || size % FSIZE != 0) 238 panic("alloccg: bad size"); 239 bp = bread(dev, cgtod(cg, fs), BSIZE); 240 if (bp->b_flags & B_ERROR) 241 return (0); 242 cgp = bp->b_un.b_cg; 243 if (bpref) { 244 bpref %= fs->fs_fpg; 245 if (isblock(cgp->cg_free, bpref/FRAG)) 246 goto gotit; 247 } else 248 bpref = cgp->cg_rotor; 249 for (i = 0; i < cgp->cg_ndblk; i += FRAG) { 250 bpref += FRAG; 251 if (bpref >= cgp->cg_ndblk) 252 bpref = 0; 253 if (isblock(cgp->cg_free, bpref/FRAG)) { 254 cgp->cg_rotor = bpref; 255 goto gotit; 256 } 257 } 258 brelse(bp); 259 return (0); 260 gotit: 261 if (size == BSIZE) { 262 clrblock(cgp->cg_free, bpref/FRAG); 263 cgp->cg_nbfree--; 264 fs->fs_nbfree--; 265 fs->fs_cs[cg].cs_nbfree--; 266 i = bpref * NSPF; 267 cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]--; 268 } else { 269 cgp->cg_nffree += FRAG; 270 fs->fs_nffree += FRAG; 271 for (i = 0; i < size / FSIZE; i++) { 272 clrbit(cgp->cg_free, bpref + i); 273 cgp->cg_nffree--; 274 fs->fs_nffree--; 275 } 276 cgp->cg_nbfree--; 277 fs->fs_nbfree--; 278 fs->fs_cs[cg].cs_nbfree--; 279 i = bpref * NSPF; 280 cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]--; 281 } 282 fs->fs_fmod++; 283 bdwrite(bp); 284 return (cg * fs->fs_fpg + bpref); 285 } 286 287 long 288 ialloccg(dev, fs, cg, ipref, mode) 289 dev_t dev; 290 struct fs *fs; 291 int cg; 292 daddr_t ipref; 293 int mode; 294 { 295 struct buf *bp; 296 struct cg *cgp; 297 int i; 298 299 bp = bread(dev, cgtod(cg, fs), BSIZE); 300 if (bp->b_flags & B_ERROR) 301 return (0); 302 cgp = bp->b_un.b_cg; 303 if (cgp->cg_nifree == 0) { 304 brelse(bp); 305 return (0); 306 } 307 if (ipref) { 308 ipref %= fs->fs_ipg; 309 if (isclr(cgp->cg_iused, ipref)) 310 goto gotit; 311 } else 312 ipref = cgp->cg_irotor; 313 for (i = 0; i < fs->fs_ipg; i++) { 314 ipref++; 315 if (ipref >= fs->fs_ipg) 316 ipref = 0; 317 if (isclr(cgp->cg_iused, ipref)) { 318 cgp->cg_irotor = ipref; 319 goto gotit; 320 } 321 } 322 brelse(bp); 323 return (0); 324 gotit: 325 setbit(cgp->cg_iused, ipref); 326 cgp->cg_nifree--; 327 fs->fs_nifree--; 328 fs->fs_cs[cg].cs_nifree--; 329 fs->fs_fmod++; 330 if ((mode & IFMT) == IFDIR) { 331 cgp->cg_ndir++; 332 fs->fs_cs[cg].cs_ndir++; 333 } 334 bdwrite(bp); 335 return (cg * fs->fs_ipg + ipref); 336 } 337 338 fre(dev, bno, size) 339 dev_t dev; 340 daddr_t bno; 341 int size; 342 { 343 register struct fs *fs; 344 register struct cg *cgp; 345 register struct buf *bp; 346 int i; 347 int cg; 348 349 if ((unsigned)size > BSIZE || size % FSIZE != 0) 350 panic("free: bad size"); 351 fs = getfs(dev); 352 cg = dtog(bno, fs); 353 if (badblock(fs, bno)) 354 return; 355 bp = bread(dev, cgtod(cg, fs), BSIZE); 356 if (bp->b_flags & B_ERROR) 357 return; 358 cgp = bp->b_un.b_cg; 359 bno %= fs->fs_fpg; 360 if (size == BSIZE) { 361 if (isblock(cgp->cg_free, bno/FRAG)) 362 panic("free: freeing free block"); 363 setblock(cgp->cg_free, bno/FRAG); 364 cgp->cg_nbfree++; 365 fs->fs_nbfree++; 366 fs->fs_cs[cg].cs_nbfree++; 367 i = bno * NSPF; 368 cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]++; 369 } else { 370 for (i = 0; i < size / FSIZE; i++) { 371 if (isset(cgp->cg_free, bno + i)) 372 panic("free: freeing free frag"); 373 setbit(cgp->cg_free, bno + i); 374 cgp->cg_nffree++; 375 fs->fs_nffree++; 376 } 377 if (isblock(cgp->cg_free, (bno - bno % FRAG) / FRAG)) { 378 cgp->cg_nffree -= FRAG; 379 fs->fs_nffree -= FRAG; 380 cgp->cg_nbfree++; 381 fs->fs_nbfree++; 382 fs->fs_cs[cg].cs_nbfree++; 383 i = bno * NSPF; 384 cgp->cg_b[i / fs->fs_spc] 385 [i % fs->fs_nsect * NRPOS / fs->fs_nsect]++; 386 } 387 } 388 fs->fs_fmod++; 389 bdwrite(bp); 390 } 391 392 ifree(dev, ino, mode) 393 dev_t dev; 394 ino_t ino; 395 int mode; 396 { 397 register struct fs *fs; 398 register struct cg *cgp; 399 register struct buf *bp; 400 int i; 401 int cg; 402 403 fs = getfs(dev); 404 if ((unsigned)ino >= fs->fs_ipg*fs->fs_ncg) 405 panic("ifree: range"); 406 cg = itog(ino, fs); 407 bp = bread(dev, cgtod(cg, fs), BSIZE); 408 if (bp->b_flags & B_ERROR) 409 return; 410 cgp = bp->b_un.b_cg; 411 ino %= fs->fs_ipg; 412 if (isclr(cgp->cg_iused, ino)) 413 panic("ifree: freeing free inode"); 414 clrbit(cgp->cg_iused, ino); 415 cgp->cg_nifree++; 416 fs->fs_nifree++; 417 fs->fs_cs[cg].cs_nifree++; 418 if ((mode & IFMT) == IFDIR) { 419 cgp->cg_ndir--; 420 fs->fs_cs[cg].cs_ndir--; 421 } 422 fs->fs_fmod++; 423 bdwrite(bp); 424 } 425 426 badblock(fs, bn) 427 register struct fs *fs; 428 daddr_t bn; 429 { 430 431 if ((unsigned)bn >= fs->fs_size || bn < cgdmin(dtog(bn, fs), fs)) { 432 fserr(fs, "bad block"); 433 return (1); 434 } 435 return (0); 436 } 437 438 /* 439 * getfs maps a device number into 440 * a pointer to the incore super 441 * block. The algorithm is a linear 442 * search through the mount table. 443 * A consistency check of the 444 * in core free-block and i-node 445 * counts is performed. 446 * 447 * panic: no fs -- the device is not mounted. 448 * this "cannot happen" 449 */ 450 struct fs * 451 getfs(dev) 452 dev_t dev; 453 { 454 register struct mount *mp; 455 register struct fs *fs; 456 457 for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) 458 if (mp->m_bufp != NULL && mp->m_dev == dev) { 459 fs = mp->m_bufp->b_un.b_fs; 460 if (fs->fs_magic != FS_MAGIC) 461 panic("getfs: bad magic"); 462 return (fs); 463 } 464 panic("getfs: no fs"); 465 return (NULL); 466 } 467 468 /* 469 * Fserr prints the name of a file system 470 * with an error diagnostic, in the form 471 * fs: error message 472 */ 473 fserr(fs, cp) 474 struct fs *fs; 475 char *cp; 476 { 477 478 printf("%s: %s\n", fs->fs_fsmnt, cp); 479 } 480 481 /* 482 * Getfsx returns the index in the file system 483 * table of the specified device. The swap device 484 * is also assigned a pseudo-index. The index may 485 * be used as a compressed indication of the location 486 * of a block, recording 487 * <getfsx(dev),blkno> 488 * rather than 489 * <dev, blkno> 490 * provided the information need remain valid only 491 * as long as the file system is mounted. 492 */ 493 getfsx(dev) 494 dev_t dev; 495 { 496 register struct mount *mp; 497 498 if (dev == swapdev) 499 return (MSWAPX); 500 for(mp = &mount[0]; mp < &mount[NMOUNT]; mp++) 501 if (mp->m_dev == dev) 502 return (mp - &mount[0]); 503 return (-1); 504 } 505 506 /* 507 * Update is the internal name of 'sync'. It goes through the disk 508 * queues to initiate sandbagged IO; goes through the inodes to write 509 * modified nodes; and it goes through the mount table to initiate modified 510 * super blocks. 511 */ 512 update() 513 { 514 register struct inode *ip; 515 register struct mount *mp; 516 register struct buf *bp; 517 struct fs *fs; 518 time_t tim; 519 int i; 520 521 if (updlock) 522 return; 523 updlock++; 524 /* 525 * Write back modified superblocks. 526 * Consistency check that the superblock 527 * of each file system is still in the buffer cache. 528 */ 529 for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) 530 if (mp->m_bufp != NULL) { 531 fs = mp->m_bufp->b_un.b_fs; 532 if (fs->fs_fmod == 0) 533 continue; 534 if (fs->fs_ronly != 0) 535 panic("update: rofs mod"); 536 bp = getblk(mp->m_dev, SBLOCK, BSIZE); 537 fs->fs_fmod = 0; 538 fs->fs_time = TIME; 539 if (bp->b_un.b_fs != fs) 540 panic("update: bad b_fs"); 541 bwrite(bp); 542 for (i = 0; i < cssize(fs); i += BSIZE) { 543 bp = getblk(mp->m_dev, csaddr(fs) + i / FSIZE, 544 BSIZE); 545 bcopy(fs->fs_cs + i, bp->b_un.b_addr, BSIZE); 546 bwrite(bp); 547 } 548 } 549 /* 550 * Write back each (modified) inode. 551 */ 552 for (ip = inode; ip < inodeNINODE; ip++) 553 if((ip->i_flag&ILOCK)==0 && ip->i_count) { 554 ip->i_flag |= ILOCK; 555 ip->i_count++; 556 tim = TIME; 557 iupdat(ip, &tim, &tim, 0); 558 iput(ip); 559 } 560 updlock = 0; 561 /* 562 * Force stale buffer cache information to be flushed, 563 * for all devices. 564 */ 565 bflush(NODEV); 566 } 567