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