1 /* Copyright (c) 1981 Regents of the University of California */ 2 3 static char vers[] = "@(#)lfs_alloc.c 1.2 09/09/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); 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 inode * 54 ialloc(dev, ipref, mode) 55 dev_t dev; 56 ino_t ipref; 57 int mode; 58 { 59 daddr_t ino; 60 register struct fs *fs; 61 register struct inode *ip; 62 int cg; 63 64 fs = getfs(dev); 65 if (fs->fs_nifree == 0) 66 goto noinodes; 67 cg = itog(ipref, fs); 68 ino = hashalloc(dev, fs, cg, (long)ipref, mode, ialloccg); 69 if (ino == 0) 70 goto noinodes; 71 ip = iget(dev, ino); 72 if (ip == NULL) { 73 ifree(dev, ino); 74 return (NULL); 75 } 76 if (ip->i_mode) 77 panic("ialloc: dup alloc"); 78 return (ip); 79 noinodes: 80 fserr(fs, "out of inodes"); 81 uprintf("\n%s: create failed, no inodes free\n", fs->fs_fsmnt); 82 u.u_error = ENOSPC; 83 return (NULL); 84 } 85 86 dipref(dev) 87 dev_t dev; 88 { 89 register struct fs *fs; 90 int cg, minndir, mincg; 91 92 fs = getfs(dev); 93 minndir = fs->fs_cs[0].cs_ndir; 94 mincg = 0; 95 for (cg = 1; cg < fs->fs_ncg; cg++) 96 if (fs->fs_cs[cg].cs_ndir < minndir) { 97 mincg = cg; 98 minndir = fs->fs_cs[cg].cs_ndir; 99 if (minndir == 0) 100 break; 101 } 102 return (fs->fs_ipg * mincg); 103 } 104 105 long 106 hashalloc(dev, fs, cg, pref, size, allocator) 107 dev_t dev; 108 register struct fs *fs; 109 int cg; 110 long pref; 111 int size; /* size for data blocks, mode for inodes */ 112 long (*allocator)(); 113 { 114 long result; 115 int i, icg = cg; 116 117 /* 118 * 1: preferred cylinder group 119 */ 120 result = (*allocator)(dev, fs, cg, pref, size); 121 if (result) 122 return (result); 123 /* 124 * 2: quadratic rehash 125 */ 126 for (i = 1; i < fs->fs_ncg; i *= 2) { 127 cg += i; 128 if (cg >= fs->fs_ncg) 129 cg -= fs->fs_ncg; 130 result = (*allocator)(dev, fs, cg, 0, size); 131 if (result) 132 return (result); 133 } 134 /* 135 * 3: brute force search 136 */ 137 cg = icg; 138 for (i = 0; i < fs->fs_ncg; i++) { 139 result = (*allocator)(dev, fs, cg, 0, size); 140 if (result) 141 return (result); 142 cg++; 143 if (cg == fs->fs_ncg) 144 cg = 0; 145 } 146 return (0); 147 } 148 149 daddr_t 150 alloccg(dev, fs, cg, bpref, size) 151 dev_t dev; 152 struct fs *fs; 153 int cg; 154 daddr_t bpref; 155 int size; 156 { 157 struct buf *bp; 158 struct cg *cgp; 159 int i; 160 161 if (size != BSIZE) 162 panic("alloccg: size != BSIZE is too hard!"); 163 bp = bread(dev, cgtod(cg, fs)); 164 if (bp->b_flags & B_ERROR) 165 return (0); 166 cgp = bp->b_un.b_cg; 167 if (bpref) { 168 bpref %= fs->fs_fpg; 169 if (isblock(cgp->cg_free, bpref/FRAG)) 170 goto gotit; 171 } else 172 bpref = cgp->cg_rotor; 173 for (i = 0; i < cgp->cg_ndblk; i += FRAG) { 174 bpref += FRAG; 175 if (bpref >= cgp->cg_ndblk) 176 bpref = 0; 177 if (isblock(cgp->cg_free, bpref/FRAG)) { 178 cgp->cg_rotor = bpref; 179 goto gotit; 180 } 181 } 182 brelse(bp); 183 return (0); 184 gotit: 185 clrblock(cgp->cg_free, bpref/FRAG); 186 cgp->cg_nbfree--; 187 fs->fs_nbfree--; 188 fs->fs_cs[cg].cs_nbfree--; 189 fs->fs_fmod++; 190 i = bpref * NSPF; 191 cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]--; 192 bdwrite(bp); 193 return (cg * fs->fs_fpg + bpref); 194 } 195 196 long 197 ialloccg(dev, fs, cg, ipref, mode) 198 dev_t dev; 199 struct fs *fs; 200 int cg; 201 daddr_t ipref; 202 int mode; 203 { 204 struct buf *bp; 205 struct cg *cgp; 206 int i; 207 208 bp = bread(dev, cgtod(cg, fs)); 209 if (bp->b_flags & B_ERROR) 210 return (0); 211 cgp = bp->b_un.b_cg; 212 if (cgp->cg_nifree == 0) { 213 brelse(bp); 214 return (0); 215 } 216 if (ipref) { 217 ipref %= fs->fs_ipg; 218 if (isclr(cgp->cg_iused, ipref)) 219 goto gotit; 220 } else 221 ipref = cgp->cg_irotor; 222 for (i = 0; i < fs->fs_ipg; i++) { 223 ipref++; 224 if (ipref >= fs->fs_ipg) 225 ipref = 0; 226 if (isclr(cgp->cg_iused, ipref)) { 227 cgp->cg_irotor = ipref; 228 goto gotit; 229 } 230 } 231 brelse(bp); 232 return (0); 233 gotit: 234 setbit(cgp->cg_iused, ipref); 235 cgp->cg_nifree--; 236 fs->fs_nifree--; 237 fs->fs_cs[cg].cs_nifree--; 238 fs->fs_fmod++; 239 if ((mode & IFMT) == IFDIR) { 240 cgp->cg_ndir++; 241 fs->fs_cs[cg].cs_ndir++; 242 } 243 bdwrite(bp); 244 return (cg * fs->fs_ipg + ipref); 245 } 246 247 fre(dev, bno, size) 248 dev_t dev; 249 daddr_t bno; 250 int size; 251 { 252 register struct fs *fs; 253 register struct cg *cgp; 254 register struct buf *bp; 255 int i; 256 int cg; 257 258 if (size != BSIZE) 259 panic("free: size != BSIZE is too hard!"); 260 fs = getfs(dev); 261 cg = dtog(bno, fs); 262 if (badblock(fs, bno)) 263 return; 264 bp = bread(dev, cgtod(cg, fs)); 265 if (bp->b_flags & B_ERROR) 266 return; 267 cgp = bp->b_un.b_cg; 268 bno %= fs->fs_fpg; 269 if (isblock(cgp->cg_free, bno/FRAG)) 270 panic("free: freeing free block"); 271 setblock(cgp->cg_free, bno/FRAG); 272 cgp->cg_nbfree++; 273 fs->fs_nbfree++; 274 fs->fs_cs[cg].cs_nbfree++; 275 fs->fs_fmod++; 276 i = bno * NSPF; 277 cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]++; 278 bdwrite(bp); 279 } 280 281 ifree(dev, ino, mode) 282 dev_t dev; 283 ino_t ino; 284 int mode; 285 { 286 register struct fs *fs; 287 register struct cg *cgp; 288 register struct buf *bp; 289 int i; 290 int cg; 291 292 fs = getfs(dev); 293 if ((unsigned)ino >= fs->fs_ipg*fs->fs_ncg) 294 panic("ifree: range"); 295 cg = itog(ino, fs); 296 bp = bread(dev, cgtod(cg, fs)); 297 if (bp->b_flags & B_ERROR) 298 return; 299 cgp = bp->b_un.b_cg; 300 ino %= fs->fs_ipg; 301 if (isclr(cgp->cg_iused, ino)) 302 panic("ifree: freeing free inode"); 303 clrbit(cgp->cg_iused, ino); 304 cgp->cg_nifree++; 305 fs->fs_nifree++; 306 fs->fs_cs[cg].cs_nifree++; 307 if ((mode & IFMT) == IFDIR) { 308 cgp->cg_ndir--; 309 fs->fs_cs[cg].cs_ndir--; 310 } 311 fs->fs_fmod++; 312 bdwrite(bp); 313 } 314 315 badblock(fs, bn) 316 register struct fs *fs; 317 daddr_t bn; 318 { 319 320 if ((unsigned)bn >= fs->fs_size || bn < cgdmin(dtog(bn, fs), fs)) { 321 fserr(fs, "bad block"); 322 return (1); 323 } 324 return (0); 325 } 326 327 /* 328 * getfs maps a device number into 329 * a pointer to the incore super 330 * block. The algorithm is a linear 331 * search through the mount table. 332 * A consistency check of the 333 * in core free-block and i-node 334 * counts is performed. 335 * 336 * panic: no fs -- the device is not mounted. 337 * this "cannot happen" 338 */ 339 struct fs * 340 getfs(dev) 341 dev_t dev; 342 { 343 register struct mount *mp; 344 register struct fs *fs; 345 346 for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) 347 if (mp->m_bufp != NULL && mp->m_dev == dev) { 348 fs = mp->m_bufp->b_un.b_fs; 349 if (fs->fs_magic != FS_MAGIC) 350 panic("getfs: bad magic"); 351 return (fs); 352 } 353 panic("getfs: no fs"); 354 return (NULL); 355 } 356 357 /* 358 * Fserr prints the name of a file system 359 * with an error diagnostic, in the form 360 * fs: error message 361 */ 362 fserr(fs, cp) 363 struct fs *fs; 364 char *cp; 365 { 366 367 printf("%s: %s\n", fs->fs_fsmnt, cp); 368 } 369 370 /* 371 * Getfsx returns the index in the file system 372 * table of the specified device. The swap device 373 * is also assigned a pseudo-index. The index may 374 * be used as a compressed indication of the location 375 * of a block, recording 376 * <getfsx(dev),blkno> 377 * rather than 378 * <dev, blkno> 379 * provided the information need remain valid only 380 * as long as the file system is mounted. 381 */ 382 getfsx(dev) 383 dev_t dev; 384 { 385 register struct mount *mp; 386 387 if (dev == swapdev) 388 return (MSWAPX); 389 for(mp = &mount[0]; mp < &mount[NMOUNT]; mp++) 390 if (mp->m_dev == dev) 391 return (mp - &mount[0]); 392 return (-1); 393 } 394 395 /* 396 * Update is the internal name of 'sync'. It goes through the disk 397 * queues to initiate sandbagged IO; goes through the inodes to write 398 * modified nodes; and it goes through the mount table to initiate modified 399 * super blocks. 400 */ 401 update() 402 { 403 register struct inode *ip; 404 register struct mount *mp; 405 register struct buf *bp; 406 struct fs *fs; 407 time_t tim; 408 int i; 409 410 if (updlock) 411 return; 412 updlock++; 413 /* 414 * Write back modified superblocks. 415 * Consistency check that the superblock 416 * of each file system is still in the buffer cache. 417 */ 418 for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) 419 if (mp->m_bufp != NULL) { 420 fs = mp->m_bufp->b_un.b_fs; 421 if (fs->fs_fmod == 0) 422 continue; 423 if (fs->fs_ronly != 0) 424 panic("update: rofs mod"); 425 bp = getblk(mp->m_dev, SBLOCK); 426 fs->fs_fmod = 0; 427 fs->fs_time = TIME; 428 if (bp->b_un.b_fs != fs) 429 panic("update: bad b_fs"); 430 bwrite(bp); 431 for (i = 0; i < cssize(fs); i += BSIZE) { 432 bp = getblk(mp->m_dev, csaddr(fs) + i / FSIZE); 433 bcopy(fs->fs_cs + i, bp->b_un.b_addr, BSIZE); 434 bwrite(bp); 435 } 436 } 437 /* 438 * Write back each (modified) inode. 439 */ 440 for (ip = inode; ip < inodeNINODE; ip++) 441 if((ip->i_flag&ILOCK)==0 && ip->i_count) { 442 ip->i_flag |= ILOCK; 443 ip->i_count++; 444 tim = TIME; 445 iupdat(ip, &tim, &tim, 0); 446 iput(ip); 447 } 448 updlock = 0; 449 /* 450 * Force stale buffer cache information to be flushed, 451 * for all devices. 452 */ 453 bflush(NODEV); 454 } 455