Commit | Line | Data |
---|---|---|
e3fe2d69 KM |
1 | /* Copyright (c) 1981 Regents of the University of California */ |
2 | ||
b6407c9d | 3 | static char vers[] = "@(#)ffs_alloc.c 1.11 %G%"; |
e3fe2d69 KM |
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 | ||
daaf7bee KM |
17 | extern u_long hashalloc(); |
18 | extern ino_t ialloccg(); | |
743f1ef7 KM |
19 | extern daddr_t alloccg(); |
20 | extern daddr_t alloccgblk(); | |
21 | extern daddr_t fragextend(); | |
22 | extern daddr_t blkpref(); | |
23 | extern daddr_t mapsearch(); | |
1d7a08c5 | 24 | extern int inside[], around[]; |
b6407c9d | 25 | extern unsigned char *fragtbl[]; |
e3fe2d69 KM |
26 | |
27 | struct buf * | |
28 | alloc(dev, ip, bpref, size) | |
29 | dev_t dev; | |
f3c028b7 | 30 | register struct inode *ip; |
e3fe2d69 KM |
31 | daddr_t bpref; |
32 | int size; | |
33 | { | |
34 | daddr_t bno; | |
35 | register struct fs *fs; | |
f3c028b7 | 36 | register struct buf *bp; |
e3fe2d69 KM |
37 | int cg; |
38 | ||
39 | fs = getfs(dev); | |
b6407c9d KM |
40 | if ((unsigned)size > fs->fs_bsize || size % fs->fs_fsize != 0) |
41 | panic("alloc: bad size"); | |
42 | if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) | |
0947395d KM |
43 | goto nospace; |
44 | if (u.u_uid != 0 && | |
b6407c9d KM |
45 | fs->fs_cstotal.cs_nbfree * fs->fs_frag + fs->fs_cstotal.cs_nffree < |
46 | fs->fs_dsize * fs->fs_minfree / 100) | |
e3fe2d69 | 47 | goto nospace; |
260e5e3c KM |
48 | if (bpref >= fs->fs_size) |
49 | bpref = 0; | |
e3fe2d69 KM |
50 | if (bpref == 0) |
51 | cg = itog(ip->i_number, fs); | |
52 | else | |
53 | cg = dtog(bpref, fs); | |
daaf7bee | 54 | bno = (daddr_t)hashalloc(dev, fs, cg, (long)bpref, size, alloccg); |
e3fe2d69 KM |
55 | if (bno == 0) |
56 | goto nospace; | |
b6407c9d | 57 | bp = getblk(dev, fsbtodb(fs, bno), size); |
e3fe2d69 KM |
58 | clrbuf(bp); |
59 | return (bp); | |
60 | nospace: | |
61 | fserr(fs, "file system full"); | |
62 | uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); | |
63 | u.u_error = ENOSPC; | |
64 | return (NULL); | |
65 | } | |
66 | ||
07670f7d | 67 | struct buf * |
daaf7bee | 68 | realloccg(dev, bprev, bpref, osize, nsize) |
07670f7d | 69 | dev_t dev; |
743f1ef7 | 70 | daddr_t bprev, bpref; |
07670f7d KM |
71 | int osize, nsize; |
72 | { | |
73 | daddr_t bno; | |
74 | register struct fs *fs; | |
f3c028b7 KM |
75 | register struct buf *bp, *obp; |
76 | caddr_t cp; | |
07670f7d KM |
77 | int cg; |
78 | ||
79 | fs = getfs(dev); | |
b6407c9d KM |
80 | if ((unsigned)osize > fs->fs_bsize || osize % fs->fs_fsize != 0 || |
81 | (unsigned)nsize > fs->fs_bsize || nsize % fs->fs_fsize != 0) | |
82 | panic("realloccg: bad size"); | |
0947395d | 83 | if (u.u_uid != 0 && |
b6407c9d KM |
84 | fs->fs_cstotal.cs_nbfree * fs->fs_frag + fs->fs_cstotal.cs_nffree < |
85 | fs->fs_dsize * fs->fs_minfree / 100) | |
0947395d | 86 | goto nospace; |
f3c028b7 KM |
87 | if (bprev == 0) |
88 | panic("realloccg: bad bprev"); | |
07670f7d | 89 | else |
f3c028b7 KM |
90 | cg = dtog(bprev, fs); |
91 | bno = fragextend(dev, fs, cg, (long)bprev, osize, nsize); | |
92 | if (bno != 0) { | |
b6407c9d | 93 | bp = bread(dev, fsbtodb(fs, bno), osize); |
f3c028b7 KM |
94 | bp->b_bcount = nsize; |
95 | blkclr(bp->b_un.b_addr + osize, nsize - osize); | |
96 | return (bp); | |
97 | } | |
260e5e3c KM |
98 | if (bpref >= fs->fs_size) |
99 | bpref = 0; | |
daaf7bee | 100 | bno = (daddr_t)hashalloc(dev, fs, cg, (long)bpref, nsize, alloccg); |
f3c028b7 KM |
101 | if (bno != 0) { |
102 | /* | |
103 | * make a new copy | |
104 | */ | |
b6407c9d KM |
105 | obp = bread(dev, fsbtodb(fs, bprev), osize); |
106 | bp = getblk(dev, fsbtodb(fs, bno), nsize); | |
f3c028b7 KM |
107 | cp = bp->b_un.b_addr; |
108 | bp->b_un.b_addr = obp->b_un.b_addr; | |
109 | obp->b_un.b_addr = cp; | |
110 | obp->b_flags |= B_INVAL; | |
111 | brelse(obp); | |
daaf7bee | 112 | fre(dev, bprev, (off_t)osize); |
f3c028b7 KM |
113 | blkclr(bp->b_un.b_addr + osize, nsize - osize); |
114 | return(bp); | |
115 | } | |
0947395d | 116 | nospace: |
f3c028b7 KM |
117 | /* |
118 | * no space available | |
119 | */ | |
07670f7d KM |
120 | fserr(fs, "file system full"); |
121 | uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); | |
122 | u.u_error = ENOSPC; | |
123 | return (NULL); | |
124 | } | |
125 | ||
e3fe2d69 KM |
126 | struct inode * |
127 | ialloc(dev, ipref, mode) | |
128 | dev_t dev; | |
129 | ino_t ipref; | |
130 | int mode; | |
131 | { | |
daaf7bee | 132 | ino_t ino; |
e3fe2d69 KM |
133 | register struct fs *fs; |
134 | register struct inode *ip; | |
135 | int cg; | |
136 | ||
137 | fs = getfs(dev); | |
0947395d | 138 | if (fs->fs_cstotal.cs_nifree == 0) |
e3fe2d69 | 139 | goto noinodes; |
260e5e3c KM |
140 | if (ipref >= fs->fs_ncg * fs->fs_ipg) |
141 | ipref = 0; | |
e3fe2d69 | 142 | cg = itog(ipref, fs); |
daaf7bee | 143 | ino = (ino_t)hashalloc(dev, fs, cg, (long)ipref, mode, ialloccg); |
e3fe2d69 KM |
144 | if (ino == 0) |
145 | goto noinodes; | |
146 | ip = iget(dev, ino); | |
147 | if (ip == NULL) { | |
daaf7bee | 148 | ifree(dev, ino, 0); |
e3fe2d69 KM |
149 | return (NULL); |
150 | } | |
151 | if (ip->i_mode) | |
152 | panic("ialloc: dup alloc"); | |
153 | return (ip); | |
154 | noinodes: | |
155 | fserr(fs, "out of inodes"); | |
156 | uprintf("\n%s: create failed, no inodes free\n", fs->fs_fsmnt); | |
157 | u.u_error = ENOSPC; | |
158 | return (NULL); | |
159 | } | |
160 | ||
743f1ef7 KM |
161 | /* |
162 | * find a cylinder to place a directory | |
163 | */ | |
164 | dirpref(dev) | |
e3fe2d69 KM |
165 | dev_t dev; |
166 | { | |
167 | register struct fs *fs; | |
743f1ef7 | 168 | int cg, minndir, mincg, avgifree; |
e3fe2d69 KM |
169 | |
170 | fs = getfs(dev); | |
0947395d | 171 | avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; |
743f1ef7 | 172 | minndir = fs->fs_ipg; |
e3fe2d69 | 173 | mincg = 0; |
743f1ef7 | 174 | for (cg = 0; cg < fs->fs_ncg; cg++) |
b6407c9d KM |
175 | if (fs->fs_cs(fs, cg).cs_ndir < minndir && |
176 | fs->fs_cs(fs, cg).cs_nifree >= avgifree) { | |
e3fe2d69 | 177 | mincg = cg; |
b6407c9d | 178 | minndir = fs->fs_cs(fs, cg).cs_ndir; |
e3fe2d69 KM |
179 | } |
180 | return (fs->fs_ipg * mincg); | |
181 | } | |
182 | ||
743f1ef7 KM |
183 | /* |
184 | * select a cylinder to place a large block of data | |
185 | */ | |
daaf7bee | 186 | daddr_t |
743f1ef7 KM |
187 | blkpref(dev) |
188 | dev_t dev; | |
189 | { | |
190 | register struct fs *fs; | |
191 | int cg, avgbfree; | |
192 | ||
193 | fs = getfs(dev); | |
0947395d | 194 | avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; |
743f1ef7 | 195 | for (cg = fs->fs_cgrotor + 1; cg < fs->fs_ncg; cg++) |
b6407c9d | 196 | if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { |
743f1ef7 | 197 | fs->fs_cgrotor = cg; |
b6407c9d | 198 | return (fs->fs_fpg * cg + fs->fs_frag); |
743f1ef7 KM |
199 | } |
200 | for (cg = 0; cg <= fs->fs_cgrotor; cg++) | |
b6407c9d | 201 | if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { |
743f1ef7 | 202 | fs->fs_cgrotor = cg; |
b6407c9d | 203 | return (fs->fs_fpg * cg + fs->fs_frag); |
743f1ef7 KM |
204 | } |
205 | return (0); | |
206 | } | |
207 | ||
daaf7bee KM |
208 | /*VARARGS5*/ |
209 | u_long | |
e3fe2d69 KM |
210 | hashalloc(dev, fs, cg, pref, size, allocator) |
211 | dev_t dev; | |
212 | register struct fs *fs; | |
213 | int cg; | |
214 | long pref; | |
215 | int size; /* size for data blocks, mode for inodes */ | |
daaf7bee | 216 | u_long (*allocator)(); |
e3fe2d69 KM |
217 | { |
218 | long result; | |
219 | int i, icg = cg; | |
220 | ||
221 | /* | |
222 | * 1: preferred cylinder group | |
223 | */ | |
224 | result = (*allocator)(dev, fs, cg, pref, size); | |
225 | if (result) | |
226 | return (result); | |
227 | /* | |
228 | * 2: quadratic rehash | |
229 | */ | |
230 | for (i = 1; i < fs->fs_ncg; i *= 2) { | |
231 | cg += i; | |
232 | if (cg >= fs->fs_ncg) | |
233 | cg -= fs->fs_ncg; | |
234 | result = (*allocator)(dev, fs, cg, 0, size); | |
235 | if (result) | |
236 | return (result); | |
237 | } | |
238 | /* | |
239 | * 3: brute force search | |
240 | */ | |
241 | cg = icg; | |
242 | for (i = 0; i < fs->fs_ncg; i++) { | |
243 | result = (*allocator)(dev, fs, cg, 0, size); | |
244 | if (result) | |
245 | return (result); | |
246 | cg++; | |
247 | if (cg == fs->fs_ncg) | |
248 | cg = 0; | |
249 | } | |
250 | return (0); | |
251 | } | |
252 | ||
07670f7d | 253 | daddr_t |
f3c028b7 | 254 | fragextend(dev, fs, cg, bprev, osize, nsize) |
07670f7d KM |
255 | dev_t dev; |
256 | register struct fs *fs; | |
257 | int cg; | |
f3c028b7 | 258 | long bprev; |
07670f7d KM |
259 | int osize, nsize; |
260 | { | |
f3c028b7 KM |
261 | register struct buf *bp; |
262 | register struct cg *cgp; | |
263 | long bno; | |
264 | int frags, bbase; | |
07670f7d KM |
265 | int i; |
266 | ||
b6407c9d KM |
267 | frags = nsize / fs->fs_fsize; |
268 | bbase = bprev % fs->fs_frag; | |
269 | if (bbase > (bprev + frags - 1) % fs->fs_frag) { | |
f3c028b7 KM |
270 | /* cannot extend across a block boundry */ |
271 | return (0); | |
272 | } | |
b6407c9d | 273 | bp = bread(dev, fsbtodb(fs, cgtod(cg, fs)), fs->fs_bsize); |
07670f7d KM |
274 | if (bp->b_flags & B_ERROR) |
275 | return (0); | |
276 | cgp = bp->b_un.b_cg; | |
f3c028b7 | 277 | bno = bprev % fs->fs_fpg; |
b6407c9d | 278 | for (i = osize / fs->fs_fsize; i < frags; i++) { |
f3c028b7 KM |
279 | if (isclr(cgp->cg_free, bno + i)) |
280 | break; | |
281 | } | |
282 | if (i == frags) { | |
283 | /* | |
284 | * the current fragment can be extended | |
285 | * deduct the count on fragment being extended into | |
286 | * increase the count on the remaining fragment (if any) | |
287 | * allocate the extended piece | |
288 | */ | |
b6407c9d | 289 | for (i = frags; i < fs->fs_frag - bbase; i++) |
f3c028b7 | 290 | if (isclr(cgp->cg_free, bno + i)) |
07670f7d | 291 | break; |
b6407c9d | 292 | cgp->cg_frsum[i - osize / fs->fs_fsize]--; |
f3c028b7 KM |
293 | if (i != frags) |
294 | cgp->cg_frsum[i - frags]++; | |
b6407c9d | 295 | for (i = osize / fs->fs_fsize; i < frags; i++) { |
f3c028b7 | 296 | clrbit(cgp->cg_free, bno + i); |
0947395d KM |
297 | cgp->cg_cs.cs_nffree--; |
298 | fs->fs_cstotal.cs_nffree--; | |
b6407c9d | 299 | fs->fs_cs(fs, cg).cs_nffree--; |
07670f7d | 300 | } |
f3c028b7 KM |
301 | fs->fs_fmod++; |
302 | bdwrite(bp); | |
303 | return (bprev); | |
07670f7d | 304 | } |
07670f7d KM |
305 | brelse(bp); |
306 | return (0); | |
07670f7d KM |
307 | } |
308 | ||
e3fe2d69 KM |
309 | daddr_t |
310 | alloccg(dev, fs, cg, bpref, size) | |
311 | dev_t dev; | |
f3c028b7 | 312 | register struct fs *fs; |
e3fe2d69 KM |
313 | int cg; |
314 | daddr_t bpref; | |
315 | int size; | |
316 | { | |
f3c028b7 KM |
317 | register struct buf *bp; |
318 | register struct cg *cgp; | |
319 | int bno, frags; | |
320 | int allocsiz; | |
f3c028b7 | 321 | register int i; |
e3fe2d69 | 322 | |
b6407c9d | 323 | if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) |
0947395d | 324 | return (0); |
b6407c9d | 325 | bp = bread(dev, fsbtodb(fs, cgtod(cg, fs)), fs->fs_bsize); |
e3fe2d69 KM |
326 | if (bp->b_flags & B_ERROR) |
327 | return (0); | |
328 | cgp = bp->b_un.b_cg; | |
b6407c9d | 329 | if (size == fs->fs_bsize) { |
daaf7bee | 330 | bno = alloccgblk(fs, cgp, bpref); |
f3c028b7 KM |
331 | bdwrite(bp); |
332 | return (bno); | |
333 | } | |
334 | /* | |
335 | * check to see if any fragments are already available | |
336 | * allocsiz is the size which will be allocated, hacking | |
337 | * it down to a smaller size if necessary | |
338 | */ | |
b6407c9d KM |
339 | frags = size / fs->fs_fsize; |
340 | for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) | |
f3c028b7 KM |
341 | if (cgp->cg_frsum[allocsiz] != 0) |
342 | break; | |
b6407c9d | 343 | if (allocsiz == fs->fs_frag) { |
f3c028b7 KM |
344 | /* |
345 | * no fragments were available, so a block will be | |
346 | * allocated, and hacked up | |
347 | */ | |
0947395d | 348 | if (cgp->cg_cs.cs_nbfree == 0) { |
f3c028b7 KM |
349 | brelse(bp); |
350 | return (0); | |
351 | } | |
daaf7bee | 352 | bno = alloccgblk(fs, cgp, bpref); |
f3c028b7 | 353 | bpref = bno % fs->fs_fpg; |
b6407c9d | 354 | for (i = frags; i < fs->fs_frag; i++) |
f3c028b7 | 355 | setbit(cgp->cg_free, bpref + i); |
b6407c9d | 356 | i = fs->fs_frag - frags; |
0947395d KM |
357 | cgp->cg_cs.cs_nffree += i; |
358 | fs->fs_cstotal.cs_nffree += i; | |
b6407c9d | 359 | fs->fs_cs(fs, cg).cs_nffree += i; |
f3c028b7 KM |
360 | cgp->cg_frsum[i]++; |
361 | bdwrite(bp); | |
362 | return (bno); | |
363 | } | |
743f1ef7 KM |
364 | bno = mapsearch(fs, cgp, bpref, allocsiz); |
365 | if (bno == 0) | |
366 | return (0); | |
f3c028b7 KM |
367 | for (i = 0; i < frags; i++) |
368 | clrbit(cgp->cg_free, bno + i); | |
0947395d KM |
369 | cgp->cg_cs.cs_nffree -= frags; |
370 | fs->fs_cstotal.cs_nffree -= frags; | |
b6407c9d | 371 | fs->fs_cs(fs, cg).cs_nffree -= frags; |
f3c028b7 KM |
372 | cgp->cg_frsum[allocsiz]--; |
373 | if (frags != allocsiz) | |
374 | cgp->cg_frsum[allocsiz - frags]++; | |
375 | bdwrite(bp); | |
376 | return (cg * fs->fs_fpg + bno); | |
377 | } | |
378 | ||
379 | daddr_t | |
daaf7bee | 380 | alloccgblk(fs, cgp, bpref) |
f3c028b7 KM |
381 | struct fs *fs; |
382 | register struct cg *cgp; | |
383 | daddr_t bpref; | |
384 | { | |
743f1ef7 KM |
385 | daddr_t bno; |
386 | int cylno, pos; | |
387 | short *cylbp; | |
388 | int i, j; | |
f3c028b7 | 389 | |
743f1ef7 KM |
390 | if (bpref == 0) { |
391 | bpref = cgp->cg_rotor; | |
392 | } else { | |
b6407c9d | 393 | bpref &= ~(fs->fs_frag - 1); |
e3fe2d69 | 394 | bpref %= fs->fs_fpg; |
743f1ef7 KM |
395 | /* |
396 | * if the requested block is available, use it | |
397 | */ | |
b6407c9d | 398 | if (isblock(fs, cgp->cg_free, bpref/fs->fs_frag)) { |
743f1ef7 | 399 | bno = bpref; |
e3fe2d69 KM |
400 | goto gotit; |
401 | } | |
743f1ef7 KM |
402 | /* |
403 | * check for a block available on the same cylinder | |
404 | * beginning with one which is rotationally optimal | |
405 | */ | |
b6407c9d | 406 | i = bpref * NSPF(fs); |
743f1ef7 KM |
407 | cylno = i / fs->fs_spc; |
408 | cylbp = cgp->cg_b[cylno]; | |
b6407c9d KM |
409 | pos = (i + (fs->fs_rotdelay == 0) ? 0 : |
410 | 1 + fs->fs_rotdelay * HZ * fs->fs_nsect / | |
411 | (NSPF(fs) * 1000)) % fs->fs_nsect * NRPOS / fs->fs_nsect; | |
743f1ef7 KM |
412 | for (i = pos; i < NRPOS; i++) |
413 | if (cylbp[i] > 0) | |
414 | break; | |
415 | if (i == NRPOS) | |
416 | for (i = 0; i < pos; i++) | |
417 | if (cylbp[i] > 0) | |
418 | break; | |
419 | if (cylbp[i] > 0) { | |
b6407c9d | 420 | bpref = cylno * fs->fs_spc / NSPB(fs); |
743f1ef7 | 421 | for (j = fs->fs_postbl[i]; j > -1; j = fs->fs_rotbl[j]) { |
b6407c9d KM |
422 | if (isblock(fs, cgp->cg_free, bpref + j)) { |
423 | bno = (bpref + j) * fs->fs_frag; | |
743f1ef7 KM |
424 | goto gotit; |
425 | } | |
426 | } | |
427 | panic("alloccgblk: can't find blk in cyl"); | |
428 | } | |
e3fe2d69 | 429 | } |
b6407c9d | 430 | bno = mapsearch(fs, cgp, bpref, fs->fs_frag); |
743f1ef7 KM |
431 | if (bno == 0) |
432 | return (0); | |
433 | cgp->cg_rotor = bno; | |
e3fe2d69 | 434 | gotit: |
b6407c9d | 435 | clrblock(fs, cgp->cg_free, bno/fs->fs_frag); |
0947395d KM |
436 | cgp->cg_cs.cs_nbfree--; |
437 | fs->fs_cstotal.cs_nbfree--; | |
b6407c9d KM |
438 | fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; |
439 | i = bno * NSPF(fs); | |
f3c028b7 | 440 | cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]--; |
e3fe2d69 | 441 | fs->fs_fmod++; |
743f1ef7 | 442 | return (cgp->cg_cgx * fs->fs_fpg + bno); |
e3fe2d69 KM |
443 | } |
444 | ||
daaf7bee | 445 | ino_t |
e3fe2d69 KM |
446 | ialloccg(dev, fs, cg, ipref, mode) |
447 | dev_t dev; | |
f3c028b7 | 448 | register struct fs *fs; |
e3fe2d69 KM |
449 | int cg; |
450 | daddr_t ipref; | |
451 | int mode; | |
452 | { | |
f3c028b7 KM |
453 | register struct buf *bp; |
454 | register struct cg *cgp; | |
e3fe2d69 KM |
455 | int i; |
456 | ||
b6407c9d | 457 | if (fs->fs_cs(fs, cg).cs_nifree == 0) |
0947395d | 458 | return (0); |
b6407c9d | 459 | bp = bread(dev, fsbtodb(fs, cgtod(cg, fs)), fs->fs_bsize); |
e3fe2d69 KM |
460 | if (bp->b_flags & B_ERROR) |
461 | return (0); | |
462 | cgp = bp->b_un.b_cg; | |
e3fe2d69 KM |
463 | if (ipref) { |
464 | ipref %= fs->fs_ipg; | |
465 | if (isclr(cgp->cg_iused, ipref)) | |
466 | goto gotit; | |
467 | } else | |
468 | ipref = cgp->cg_irotor; | |
469 | for (i = 0; i < fs->fs_ipg; i++) { | |
470 | ipref++; | |
471 | if (ipref >= fs->fs_ipg) | |
472 | ipref = 0; | |
473 | if (isclr(cgp->cg_iused, ipref)) { | |
474 | cgp->cg_irotor = ipref; | |
475 | goto gotit; | |
476 | } | |
477 | } | |
478 | brelse(bp); | |
479 | return (0); | |
480 | gotit: | |
481 | setbit(cgp->cg_iused, ipref); | |
0947395d KM |
482 | cgp->cg_cs.cs_nifree--; |
483 | fs->fs_cstotal.cs_nifree--; | |
b6407c9d | 484 | fs->fs_cs(fs, cg).cs_nifree--; |
e3fe2d69 KM |
485 | fs->fs_fmod++; |
486 | if ((mode & IFMT) == IFDIR) { | |
0947395d KM |
487 | cgp->cg_cs.cs_ndir++; |
488 | fs->fs_cstotal.cs_ndir++; | |
b6407c9d | 489 | fs->fs_cs(fs, cg).cs_ndir++; |
e3fe2d69 KM |
490 | } |
491 | bdwrite(bp); | |
492 | return (cg * fs->fs_ipg + ipref); | |
493 | } | |
494 | ||
495 | fre(dev, bno, size) | |
496 | dev_t dev; | |
497 | daddr_t bno; | |
daaf7bee | 498 | off_t size; |
e3fe2d69 KM |
499 | { |
500 | register struct fs *fs; | |
501 | register struct cg *cgp; | |
502 | register struct buf *bp; | |
f3c028b7 KM |
503 | int cg, blk, frags, bbase; |
504 | register int i; | |
e3fe2d69 | 505 | |
e3fe2d69 | 506 | fs = getfs(dev); |
b6407c9d KM |
507 | if ((unsigned)size > fs->fs_bsize || size % fs->fs_fsize != 0) |
508 | panic("free: bad size"); | |
e3fe2d69 KM |
509 | cg = dtog(bno, fs); |
510 | if (badblock(fs, bno)) | |
511 | return; | |
b6407c9d | 512 | bp = bread(dev, fsbtodb(fs, cgtod(cg, fs)), fs->fs_bsize); |
e3fe2d69 KM |
513 | if (bp->b_flags & B_ERROR) |
514 | return; | |
515 | cgp = bp->b_un.b_cg; | |
516 | bno %= fs->fs_fpg; | |
b6407c9d KM |
517 | if (size == fs->fs_bsize) { |
518 | if (isblock(fs, cgp->cg_free, bno/fs->fs_frag)) | |
07670f7d | 519 | panic("free: freeing free block"); |
b6407c9d | 520 | setblock(fs, cgp->cg_free, bno/fs->fs_frag); |
0947395d KM |
521 | cgp->cg_cs.cs_nbfree++; |
522 | fs->fs_cstotal.cs_nbfree++; | |
b6407c9d KM |
523 | fs->fs_cs(fs, cg).cs_nbfree++; |
524 | i = bno * NSPF(fs); | |
07670f7d KM |
525 | cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]++; |
526 | } else { | |
b6407c9d | 527 | bbase = bno - (bno % fs->fs_frag); |
f3c028b7 KM |
528 | /* |
529 | * decrement the counts associated with the old frags | |
530 | */ | |
531 | blk = ((cgp->cg_free[bbase / NBBY] >> (bbase % NBBY)) & | |
b6407c9d KM |
532 | (0xff >> (NBBY - fs->fs_frag))); |
533 | fragacct(fs, blk, cgp->cg_frsum, -1); | |
f3c028b7 KM |
534 | /* |
535 | * deallocate the fragment | |
536 | */ | |
b6407c9d | 537 | frags = size / fs->fs_fsize; |
f3c028b7 | 538 | for (i = 0; i < frags; i++) { |
07670f7d KM |
539 | if (isset(cgp->cg_free, bno + i)) |
540 | panic("free: freeing free frag"); | |
541 | setbit(cgp->cg_free, bno + i); | |
0947395d KM |
542 | cgp->cg_cs.cs_nffree++; |
543 | fs->fs_cstotal.cs_nffree++; | |
b6407c9d | 544 | fs->fs_cs(fs, cg).cs_nffree++; |
07670f7d | 545 | } |
f3c028b7 KM |
546 | /* |
547 | * add back in counts associated with the new frags | |
548 | */ | |
549 | blk = ((cgp->cg_free[bbase / NBBY] >> (bbase % NBBY)) & | |
b6407c9d KM |
550 | (0xff >> (NBBY - fs->fs_frag))); |
551 | fragacct(fs, blk, cgp->cg_frsum, 1); | |
f3c028b7 KM |
552 | /* |
553 | * if a complete block has been reassembled, account for it | |
554 | */ | |
b6407c9d KM |
555 | if (isblock(fs, cgp->cg_free, bbase / fs->fs_frag)) { |
556 | cgp->cg_cs.cs_nffree -= fs->fs_frag; | |
557 | fs->fs_cstotal.cs_nffree -= fs->fs_frag; | |
558 | fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; | |
0947395d KM |
559 | cgp->cg_cs.cs_nbfree++; |
560 | fs->fs_cstotal.cs_nbfree++; | |
b6407c9d KM |
561 | fs->fs_cs(fs, cg).cs_nbfree++; |
562 | i = bbase * NSPF(fs); | |
07670f7d KM |
563 | cgp->cg_b[i / fs->fs_spc] |
564 | [i % fs->fs_nsect * NRPOS / fs->fs_nsect]++; | |
565 | } | |
566 | } | |
e3fe2d69 | 567 | fs->fs_fmod++; |
e3fe2d69 KM |
568 | bdwrite(bp); |
569 | } | |
570 | ||
571 | ifree(dev, ino, mode) | |
572 | dev_t dev; | |
573 | ino_t ino; | |
574 | int mode; | |
575 | { | |
576 | register struct fs *fs; | |
577 | register struct cg *cgp; | |
578 | register struct buf *bp; | |
e3fe2d69 KM |
579 | int cg; |
580 | ||
581 | fs = getfs(dev); | |
582 | if ((unsigned)ino >= fs->fs_ipg*fs->fs_ncg) | |
583 | panic("ifree: range"); | |
584 | cg = itog(ino, fs); | |
b6407c9d | 585 | bp = bread(dev, fsbtodb(fs, cgtod(cg, fs)), fs->fs_bsize); |
e3fe2d69 KM |
586 | if (bp->b_flags & B_ERROR) |
587 | return; | |
588 | cgp = bp->b_un.b_cg; | |
589 | ino %= fs->fs_ipg; | |
590 | if (isclr(cgp->cg_iused, ino)) | |
591 | panic("ifree: freeing free inode"); | |
592 | clrbit(cgp->cg_iused, ino); | |
0947395d KM |
593 | cgp->cg_cs.cs_nifree++; |
594 | fs->fs_cstotal.cs_nifree++; | |
b6407c9d | 595 | fs->fs_cs(fs, cg).cs_nifree++; |
e3fe2d69 | 596 | if ((mode & IFMT) == IFDIR) { |
0947395d KM |
597 | cgp->cg_cs.cs_ndir--; |
598 | fs->fs_cstotal.cs_ndir--; | |
b6407c9d | 599 | fs->fs_cs(fs, cg).cs_ndir--; |
e3fe2d69 KM |
600 | } |
601 | fs->fs_fmod++; | |
602 | bdwrite(bp); | |
603 | } | |
604 | ||
743f1ef7 KM |
605 | /* |
606 | * find a block of the specified size in the specified cylinder group | |
607 | * It is a panic if a request is made to find a block if none are | |
608 | * available. | |
609 | */ | |
610 | daddr_t | |
611 | mapsearch(fs, cgp, bpref, allocsiz) | |
612 | register struct fs *fs; | |
613 | register struct cg *cgp; | |
614 | daddr_t bpref; | |
615 | int allocsiz; | |
616 | { | |
617 | daddr_t bno; | |
618 | int start, len, loc, i; | |
619 | int blk, field, subfield, pos; | |
620 | ||
621 | /* | |
622 | * find the fragment by searching through the free block | |
623 | * map for an appropriate bit pattern | |
624 | */ | |
625 | if (bpref) | |
626 | start = bpref % fs->fs_fpg / NBBY; | |
627 | else | |
628 | start = cgp->cg_frotor / NBBY; | |
629 | len = roundup(fs->fs_fpg - 1, NBBY) / NBBY - start; | |
b6407c9d KM |
630 | loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag], |
631 | 1 << (allocsiz - 1)); | |
743f1ef7 KM |
632 | if (loc == 0) { |
633 | len = start - 1; | |
634 | start = (cgdmin(cgp->cg_cgx, fs) - | |
635 | cgbase(cgp->cg_cgx, fs)) / NBBY; | |
b6407c9d | 636 | loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag], |
743f1ef7 KM |
637 | 1 << (allocsiz - 1)); |
638 | if (loc == 0) { | |
639 | panic("alloccg: map corrupted"); | |
640 | return (0); | |
641 | } | |
642 | } | |
643 | bno = (start + len - loc) * NBBY; | |
644 | cgp->cg_frotor = bno; | |
645 | /* | |
646 | * found the byte in the map | |
647 | * sift through the bits to find the selected frag | |
648 | */ | |
b6407c9d KM |
649 | for (i = 0; i < NBBY; i += fs->fs_frag) { |
650 | blk = (cgp->cg_free[bno / NBBY] >> i) & | |
651 | (0xff >> NBBY - fs->fs_frag); | |
743f1ef7 KM |
652 | blk <<= 1; |
653 | field = around[allocsiz]; | |
654 | subfield = inside[allocsiz]; | |
b6407c9d | 655 | for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { |
743f1ef7 KM |
656 | if ((blk & field) == subfield) { |
657 | return (bno + i + pos); | |
658 | } | |
659 | field <<= 1; | |
660 | subfield <<= 1; | |
661 | } | |
662 | } | |
663 | panic("alloccg: block not in map"); | |
664 | return (0); | |
665 | } | |
666 | ||
f3c028b7 KM |
667 | /* |
668 | * update the frsum fields to reflect addition or deletion | |
669 | * of some frags | |
670 | */ | |
b6407c9d KM |
671 | fragacct(fs, fragmap, fraglist, cnt) |
672 | struct fs *fs; | |
1b940b13 | 673 | int fragmap; |
0947395d | 674 | long fraglist[]; |
f3c028b7 KM |
675 | int cnt; |
676 | { | |
677 | int inblk; | |
678 | register int field, subfield; | |
679 | register int siz, pos; | |
680 | ||
b6407c9d | 681 | inblk = (int)(fragtbl[fs->fs_frag][fragmap]) << 1; |
f3c028b7 | 682 | fragmap <<= 1; |
b6407c9d | 683 | for (siz = 1; siz < fs->fs_frag; siz++) { |
f3c028b7 KM |
684 | if (((1 << siz) & inblk) == 0) |
685 | continue; | |
686 | field = around[siz]; | |
687 | subfield = inside[siz]; | |
b6407c9d | 688 | for (pos = siz; pos <= fs->fs_frag; pos++) { |
f3c028b7 KM |
689 | if ((fragmap & field) == subfield) { |
690 | fraglist[siz] += cnt; | |
691 | pos += siz; | |
692 | field <<= siz; | |
693 | subfield <<= siz; | |
694 | } | |
695 | field <<= 1; | |
696 | subfield <<= 1; | |
697 | } | |
698 | } | |
699 | } | |
700 | ||
e3fe2d69 KM |
701 | badblock(fs, bn) |
702 | register struct fs *fs; | |
703 | daddr_t bn; | |
704 | { | |
705 | ||
706 | if ((unsigned)bn >= fs->fs_size || bn < cgdmin(dtog(bn, fs), fs)) { | |
707 | fserr(fs, "bad block"); | |
708 | return (1); | |
709 | } | |
710 | return (0); | |
711 | } | |
712 | ||
713 | /* | |
714 | * getfs maps a device number into | |
715 | * a pointer to the incore super | |
716 | * block. The algorithm is a linear | |
717 | * search through the mount table. | |
718 | * A consistency check of the | |
719 | * in core free-block and i-node | |
720 | * counts is performed. | |
721 | * | |
722 | * panic: no fs -- the device is not mounted. | |
723 | * this "cannot happen" | |
724 | */ | |
725 | struct fs * | |
726 | getfs(dev) | |
727 | dev_t dev; | |
728 | { | |
729 | register struct mount *mp; | |
730 | register struct fs *fs; | |
731 | ||
732 | for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) | |
733 | if (mp->m_bufp != NULL && mp->m_dev == dev) { | |
734 | fs = mp->m_bufp->b_un.b_fs; | |
735 | if (fs->fs_magic != FS_MAGIC) | |
736 | panic("getfs: bad magic"); | |
737 | return (fs); | |
738 | } | |
739 | panic("getfs: no fs"); | |
740 | return (NULL); | |
741 | } | |
742 | ||
743 | /* | |
744 | * Fserr prints the name of a file system | |
745 | * with an error diagnostic, in the form | |
746 | * fs: error message | |
747 | */ | |
748 | fserr(fs, cp) | |
749 | struct fs *fs; | |
750 | char *cp; | |
751 | { | |
752 | ||
753 | printf("%s: %s\n", fs->fs_fsmnt, cp); | |
754 | } | |
755 | ||
756 | /* | |
757 | * Getfsx returns the index in the file system | |
758 | * table of the specified device. The swap device | |
759 | * is also assigned a pseudo-index. The index may | |
760 | * be used as a compressed indication of the location | |
761 | * of a block, recording | |
762 | * <getfsx(dev),blkno> | |
763 | * rather than | |
764 | * <dev, blkno> | |
765 | * provided the information need remain valid only | |
766 | * as long as the file system is mounted. | |
767 | */ | |
768 | getfsx(dev) | |
769 | dev_t dev; | |
770 | { | |
771 | register struct mount *mp; | |
772 | ||
773 | if (dev == swapdev) | |
774 | return (MSWAPX); | |
775 | for(mp = &mount[0]; mp < &mount[NMOUNT]; mp++) | |
776 | if (mp->m_dev == dev) | |
777 | return (mp - &mount[0]); | |
778 | return (-1); | |
779 | } | |
780 | ||
781 | /* | |
782 | * Update is the internal name of 'sync'. It goes through the disk | |
783 | * queues to initiate sandbagged IO; goes through the inodes to write | |
784 | * modified nodes; and it goes through the mount table to initiate modified | |
785 | * super blocks. | |
786 | */ | |
787 | update() | |
788 | { | |
789 | register struct inode *ip; | |
790 | register struct mount *mp; | |
791 | register struct buf *bp; | |
792 | struct fs *fs; | |
793 | time_t tim; | |
743f1ef7 | 794 | int i, blks; |
e3fe2d69 KM |
795 | |
796 | if (updlock) | |
797 | return; | |
798 | updlock++; | |
799 | /* | |
800 | * Write back modified superblocks. | |
801 | * Consistency check that the superblock | |
802 | * of each file system is still in the buffer cache. | |
803 | */ | |
804 | for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) | |
805 | if (mp->m_bufp != NULL) { | |
806 | fs = mp->m_bufp->b_un.b_fs; | |
807 | if (fs->fs_fmod == 0) | |
808 | continue; | |
809 | if (fs->fs_ronly != 0) | |
810 | panic("update: rofs mod"); | |
b6407c9d | 811 | bp = getblk(mp->m_dev, SBLOCK, MAXBSIZE); |
e3fe2d69 KM |
812 | fs->fs_fmod = 0; |
813 | fs->fs_time = TIME; | |
814 | if (bp->b_un.b_fs != fs) | |
815 | panic("update: bad b_fs"); | |
816 | bwrite(bp); | |
b6407c9d | 817 | blks = howmany(fs->fs_cssize, fs->fs_bsize); |
743f1ef7 | 818 | for (i = 0; i < blks; i++) { |
b6407c9d KM |
819 | bp = getblk(mp->m_dev, |
820 | fsbtodb(fs, fs->fs_csaddr + (i * fs->fs_frag)), | |
821 | fs->fs_bsize); | |
e3fe2d69 KM |
822 | bwrite(bp); |
823 | } | |
824 | } | |
825 | /* | |
826 | * Write back each (modified) inode. | |
827 | */ | |
828 | for (ip = inode; ip < inodeNINODE; ip++) | |
829 | if((ip->i_flag&ILOCK)==0 && ip->i_count) { | |
830 | ip->i_flag |= ILOCK; | |
831 | ip->i_count++; | |
832 | tim = TIME; | |
833 | iupdat(ip, &tim, &tim, 0); | |
834 | iput(ip); | |
835 | } | |
836 | updlock = 0; | |
837 | /* | |
838 | * Force stale buffer cache information to be flushed, | |
839 | * for all devices. | |
840 | */ | |
841 | bflush(NODEV); | |
842 | } | |
b6407c9d KM |
843 | |
844 | /* | |
845 | * block macros | |
846 | */ | |
847 | ||
848 | isblock(fs, cp, h) | |
849 | struct fs *fs; | |
850 | unsigned char *cp; | |
851 | int h; | |
852 | { | |
853 | unsigned char mask; | |
854 | ||
855 | switch (fs->fs_frag) { | |
856 | case 8: | |
857 | return (cp[h] == 0xff); | |
858 | case 4: | |
859 | mask = 0x0f << ((h & 0x1) << 2); | |
860 | return ((cp[h >> 1] & mask) == mask); | |
861 | case 2: | |
862 | mask = 0x03 << ((h & 0x3) << 1); | |
863 | return ((cp[h >> 2] & mask) == mask); | |
864 | case 1: | |
865 | mask = 0x01 << (h & 0x7); | |
866 | return ((cp[h >> 3] & mask) == mask); | |
867 | default: | |
868 | panic("isblock bad fs_frag"); | |
869 | return; | |
870 | } | |
871 | } | |
872 | clrblock(fs, cp, h) | |
873 | struct fs *fs; | |
874 | unsigned char *cp; | |
875 | int h; | |
876 | { | |
877 | switch ((fs)->fs_frag) { | |
878 | case 8: | |
879 | cp[h] = 0; | |
880 | return; | |
881 | case 4: | |
882 | cp[h >> 1] &= ~(0x0f << ((h & 0x1) << 2)); | |
883 | return; | |
884 | case 2: | |
885 | cp[h >> 2] &= ~(0x03 << ((h & 0x3) << 1)); | |
886 | return; | |
887 | case 1: | |
888 | cp[h >> 3] &= ~(0x01 << (h & 0x7)); | |
889 | return; | |
890 | default: | |
891 | panic("clrblock bad fs_frag"); | |
892 | return; | |
893 | } | |
894 | } | |
895 | setblock(fs, cp, h) | |
896 | struct fs *fs; | |
897 | unsigned char *cp; | |
898 | int h; | |
899 | { | |
900 | switch (fs->fs_frag) { | |
901 | case 8: | |
902 | cp[h] = 0xff; | |
903 | return; | |
904 | case 4: | |
905 | cp[h >> 1] |= (0x0f << ((h & 0x1) << 2)); | |
906 | return; | |
907 | case 2: | |
908 | cp[h >> 2] |= (0x03 << ((h & 0x3) << 1)); | |
909 | return; | |
910 | case 1: | |
911 | cp[h >> 3] |= (0x01 << (h & 0x7)); | |
912 | return; | |
913 | default: | |
914 | panic("setblock bad fs_frag"); | |
915 | return; | |
916 | } | |
917 | } |