![[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;
1.1.1.2 ! root 440: if (indx < fs->fs_maxcontig || bap[indx - fs->fs_maxcontig] +
! 441: blkstofrags(fs, fs->fs_maxcontig) != nextblk)
1.1 root 442: return (nextblk);
443: if (fs->fs_rotdelay != 0)
444: /*
445: * Here we convert ms of delay to frags as:
446: * (frags) = (ms) * (rev/sec) * (sect/rev) /
447: * ((sect/frag) * (ms/sec))
448: * then round up to the next block.
449: */
450: nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect /
451: (NSPF(fs) * 1000), fs->fs_frag);
452: return (nextblk);
453: }
454:
455: /*
456: * Implement the cylinder overflow algorithm.
457: *
458: * The policy implemented by this algorithm is:
459: * 1) allocate the block in its requested cylinder group.
460: * 2) quadradically rehash on the cylinder group number.
461: * 3) brute force search for a free block.
462: */
463: /*VARARGS5*/
464: u_long
465: hashalloc(ip, cg, pref, size, allocator)
466: struct inode *ip;
467: int cg;
468: long pref;
469: int size; /* size for data blocks, mode for inodes */
470: u_long (*allocator)();
471: {
472: register struct fs *fs;
473: long result;
474: int i, icg = cg;
475:
476: fs = ip->i_fs;
477: /*
478: * 1: preferred cylinder group
479: */
480: result = (*allocator)(ip, cg, pref, size);
481: if (result)
482: return (result);
483: /*
484: * 2: quadratic rehash
485: */
486: for (i = 1; i < fs->fs_ncg; i *= 2) {
487: cg += i;
488: if (cg >= fs->fs_ncg)
489: cg -= fs->fs_ncg;
490: result = (*allocator)(ip, cg, 0, size);
491: if (result)
492: return (result);
493: }
494: /*
495: * 3: brute force search
496: * Note that we start at i == 2, since 0 was checked initially,
497: * and 1 is always checked in the quadratic rehash.
498: */
499: cg = (icg + 2) % fs->fs_ncg;
500: for (i = 2; i < fs->fs_ncg; i++) {
501: result = (*allocator)(ip, cg, 0, size);
502: if (result)
503: return (result);
504: cg++;
505: if (cg == fs->fs_ncg)
506: cg = 0;
507: }
508: return (NULL);
509: }
510:
511: /*
512: * Determine whether a fragment can be extended.
513: *
514: * Check to see if the necessary fragments are available, and
515: * if they are, allocate them.
516: */
517: daddr_t
518: fragextend(ip, cg, bprev, osize, nsize)
519: struct inode *ip;
520: int cg;
521: long bprev;
522: int osize, nsize;
523: {
524: register struct fs *fs;
525: register struct cg *cgp;
526: struct buf *bp;
527: long bno;
528: int frags, bbase;
529: int i, error;
530:
531: fs = ip->i_fs;
532: if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize))
533: return (NULL);
534: frags = numfrags(fs, nsize);
535: bbase = fragnum(fs, bprev);
536: if (bbase > fragnum(fs, (bprev + frags - 1))) {
537: /* cannot extend across a block boundary */
538: return (NULL);
539: }
540: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
541: (int)fs->fs_cgsize, NOCRED, &bp);
542: if (error) {
543: brelse(bp);
544: return (NULL);
545: }
546: cgp = bp->b_un.b_cg;
547: if (!cg_chkmagic(cgp)) {
548: brelse(bp);
549: return (NULL);
550: }
551: cgp->cg_time = time.tv_sec;
552: bno = dtogd(fs, bprev);
553: for (i = numfrags(fs, osize); i < frags; i++)
554: if (isclr(cg_blksfree(cgp), bno + i)) {
555: brelse(bp);
556: return (NULL);
557: }
558: /*
559: * the current fragment can be extended
560: * deduct the count on fragment being extended into
561: * increase the count on the remaining fragment (if any)
562: * allocate the extended piece
563: */
564: for (i = frags; i < fs->fs_frag - bbase; i++)
565: if (isclr(cg_blksfree(cgp), bno + i))
566: break;
567: cgp->cg_frsum[i - numfrags(fs, osize)]--;
568: if (i != frags)
569: cgp->cg_frsum[i - frags]++;
570: for (i = numfrags(fs, osize); i < frags; i++) {
571: clrbit(cg_blksfree(cgp), bno + i);
572: cgp->cg_cs.cs_nffree--;
573: fs->fs_cstotal.cs_nffree--;
574: fs->fs_cs(fs, cg).cs_nffree--;
575: }
576: fs->fs_fmod++;
577: bdwrite(bp);
578: return (bprev);
579: }
580:
581: /*
582: * Determine whether a block can be allocated.
583: *
584: * Check to see if a block of the apprpriate size is available,
585: * and if it is, allocate it.
586: */
587: daddr_t
588: alloccg(ip, cg, bpref, size)
589: struct inode *ip;
590: int cg;
591: daddr_t bpref;
592: int size;
593: {
594: register struct fs *fs;
595: register struct cg *cgp;
596: struct buf *bp;
597: register int i;
598: int error, bno, frags, allocsiz;
599:
600: fs = ip->i_fs;
601: if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize)
602: return (NULL);
603: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
604: (int)fs->fs_cgsize, NOCRED, &bp);
605: if (error) {
606: brelse(bp);
607: return (NULL);
608: }
609: cgp = bp->b_un.b_cg;
610: if (!cg_chkmagic(cgp) ||
611: (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) {
612: brelse(bp);
613: return (NULL);
614: }
615: cgp->cg_time = time.tv_sec;
616: if (size == fs->fs_bsize) {
617: bno = alloccgblk(fs, cgp, bpref);
618: bdwrite(bp);
619: return (bno);
620: }
621: /*
622: * check to see if any fragments are already available
623: * allocsiz is the size which will be allocated, hacking
624: * it down to a smaller size if necessary
625: */
626: frags = numfrags(fs, size);
627: for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++)
628: if (cgp->cg_frsum[allocsiz] != 0)
629: break;
630: if (allocsiz == fs->fs_frag) {
631: /*
632: * no fragments were available, so a block will be
633: * allocated, and hacked up
634: */
635: if (cgp->cg_cs.cs_nbfree == 0) {
636: brelse(bp);
637: return (NULL);
638: }
639: bno = alloccgblk(fs, cgp, bpref);
640: bpref = dtogd(fs, bno);
641: for (i = frags; i < fs->fs_frag; i++)
642: setbit(cg_blksfree(cgp), bpref + i);
643: i = fs->fs_frag - frags;
644: cgp->cg_cs.cs_nffree += i;
645: fs->fs_cstotal.cs_nffree += i;
646: fs->fs_cs(fs, cg).cs_nffree += i;
647: fs->fs_fmod++;
648: cgp->cg_frsum[i]++;
649: bdwrite(bp);
650: return (bno);
651: }
652: bno = mapsearch(fs, cgp, bpref, allocsiz);
653: if (bno < 0) {
654: brelse(bp);
655: return (NULL);
656: }
657: for (i = 0; i < frags; i++)
658: clrbit(cg_blksfree(cgp), bno + i);
659: cgp->cg_cs.cs_nffree -= frags;
660: fs->fs_cstotal.cs_nffree -= frags;
661: fs->fs_cs(fs, cg).cs_nffree -= frags;
662: fs->fs_fmod++;
663: cgp->cg_frsum[allocsiz]--;
664: if (frags != allocsiz)
665: cgp->cg_frsum[allocsiz - frags]++;
666: bdwrite(bp);
667: return (cg * fs->fs_fpg + bno);
668: }
669:
670: /*
671: * Allocate a block in a cylinder group.
672: *
673: * This algorithm implements the following policy:
674: * 1) allocate the requested block.
675: * 2) allocate a rotationally optimal block in the same cylinder.
676: * 3) allocate the next available block on the block rotor for the
677: * specified cylinder group.
678: * Note that this routine only allocates fs_bsize blocks; these
679: * blocks may be fragmented by the routine that allocates them.
680: */
681: daddr_t
682: alloccgblk(fs, cgp, bpref)
683: register struct fs *fs;
684: register struct cg *cgp;
685: daddr_t bpref;
686: {
687: daddr_t bno;
688: int cylno, pos, delta;
689: short *cylbp;
690: register int i;
691:
692: if (bpref == 0) {
693: bpref = cgp->cg_rotor;
694: goto norot;
695: }
696: bpref = blknum(fs, bpref);
697: bpref = dtogd(fs, bpref);
698: /*
699: * if the requested block is available, use it
700: */
701: if (isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) {
702: bno = bpref;
703: goto gotit;
704: }
705: /*
706: * check for a block available on the same cylinder
707: */
708: cylno = cbtocylno(fs, bpref);
709: if (cg_blktot(cgp)[cylno] == 0)
710: goto norot;
711: if (fs->fs_cpc == 0) {
712: /*
713: * block layout info is not available, so just have
714: * to take any block in this cylinder.
715: */
716: bpref = howmany(fs->fs_spc * cylno, NSPF(fs));
717: goto norot;
718: }
719: /*
720: * check the summary information to see if a block is
721: * available in the requested cylinder starting at the
722: * requested rotational position and proceeding around.
723: */
724: cylbp = cg_blks(fs, cgp, cylno);
725: pos = cbtorpos(fs, bpref);
726: for (i = pos; i < fs->fs_nrpos; i++)
727: if (cylbp[i] > 0)
728: break;
729: if (i == fs->fs_nrpos)
730: for (i = 0; i < pos; i++)
731: if (cylbp[i] > 0)
732: break;
733: if (cylbp[i] > 0) {
734: /*
735: * found a rotational position, now find the actual
736: * block. A panic if none is actually there.
737: */
738: pos = cylno % fs->fs_cpc;
739: bno = (cylno - pos) * fs->fs_spc / NSPB(fs);
740: if (fs_postbl(fs, pos)[i] == -1) {
741: printf("pos = %d, i = %d, fs = %s\n",
742: pos, i, fs->fs_fsmnt);
743: panic("alloccgblk: cyl groups corrupted");
744: }
745: for (i = fs_postbl(fs, pos)[i];; ) {
746: if (isblock(fs, cg_blksfree(cgp), bno + i)) {
747: bno = blkstofrags(fs, (bno + i));
748: goto gotit;
749: }
750: delta = fs_rotbl(fs)[i];
751: if (delta <= 0 ||
752: delta + i > fragstoblks(fs, fs->fs_fpg))
753: break;
754: i += delta;
755: }
756: printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt);
757: panic("alloccgblk: can't find blk in cyl");
758: }
759: norot:
760: /*
761: * no blocks in the requested cylinder, so take next
762: * available one in this cylinder group.
763: */
764: bno = mapsearch(fs, cgp, bpref, (int)fs->fs_frag);
765: if (bno < 0)
766: return (NULL);
767: cgp->cg_rotor = bno;
768: gotit:
769: clrblock(fs, cg_blksfree(cgp), (long)fragstoblks(fs, bno));
770: cgp->cg_cs.cs_nbfree--;
771: fs->fs_cstotal.cs_nbfree--;
772: fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--;
773: cylno = cbtocylno(fs, bno);
774: cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--;
775: cg_blktot(cgp)[cylno]--;
776: fs->fs_fmod++;
777: return (cgp->cg_cgx * fs->fs_fpg + bno);
778: }
779:
780: /*
781: * Determine whether an inode can be allocated.
782: *
783: * Check to see if an inode is available, and if it is,
784: * allocate it using the following policy:
785: * 1) allocate the requested inode.
786: * 2) allocate the next available inode after the requested
787: * inode in the specified cylinder group.
788: */
789: ino_t
790: ialloccg(ip, cg, ipref, mode)
791: struct inode *ip;
792: int cg;
793: daddr_t ipref;
794: int mode;
795: {
796: register struct fs *fs;
797: register struct cg *cgp;
798: struct buf *bp;
799: int error, start, len, loc, map, i;
800:
801: fs = ip->i_fs;
802: if (fs->fs_cs(fs, cg).cs_nifree == 0)
803: return (NULL);
804: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
805: (int)fs->fs_cgsize, NOCRED, &bp);
806: if (error) {
807: brelse(bp);
808: return (NULL);
809: }
810: cgp = bp->b_un.b_cg;
811: if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) {
812: brelse(bp);
813: return (NULL);
814: }
815: cgp->cg_time = time.tv_sec;
816: if (ipref) {
817: ipref %= fs->fs_ipg;
818: if (isclr(cg_inosused(cgp), ipref))
819: goto gotit;
820: }
821: start = cgp->cg_irotor / NBBY;
822: len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY);
823: loc = skpc(0xff, len, &cg_inosused(cgp)[start]);
824: if (loc == 0) {
825: len = start + 1;
826: start = 0;
827: loc = skpc(0xff, len, &cg_inosused(cgp)[0]);
828: if (loc == 0) {
829: printf("cg = %s, irotor = %d, fs = %s\n",
830: cg, cgp->cg_irotor, fs->fs_fsmnt);
831: panic("ialloccg: map corrupted");
832: /* NOTREACHED */
833: }
834: }
835: i = start + len - loc;
836: map = cg_inosused(cgp)[i];
837: ipref = i * NBBY;
838: for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) {
839: if ((map & i) == 0) {
840: cgp->cg_irotor = ipref;
841: goto gotit;
842: }
843: }
844: printf("fs = %s\n", fs->fs_fsmnt);
845: panic("ialloccg: block not in map");
846: /* NOTREACHED */
847: gotit:
848: setbit(cg_inosused(cgp), ipref);
849: cgp->cg_cs.cs_nifree--;
850: fs->fs_cstotal.cs_nifree--;
851: fs->fs_cs(fs, cg).cs_nifree--;
852: fs->fs_fmod++;
853: if ((mode & IFMT) == IFDIR) {
854: cgp->cg_cs.cs_ndir++;
855: fs->fs_cstotal.cs_ndir++;
856: fs->fs_cs(fs, cg).cs_ndir++;
857: }
858: bdwrite(bp);
859: return (cg * fs->fs_ipg + ipref);
860: }
861:
862: /*
863: * Free a block or fragment.
864: *
865: * The specified block or fragment is placed back in the
866: * free map. If a fragment is deallocated, a possible
867: * block reassembly is checked.
868: */
869: blkfree(ip, bno, size)
870: register struct inode *ip;
871: daddr_t bno;
872: off_t size;
873: {
874: register struct fs *fs;
875: register struct cg *cgp;
876: struct buf *bp;
877: int error, cg, blk, frags, bbase;
878: register int i;
879: struct ucred *cred = curproc->p_ucred; /* XXX */
880:
881: fs = ip->i_fs;
882: if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) {
883: printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n",
884: ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt);
885: panic("blkfree: bad size");
886: }
887: cg = dtog(fs, bno);
888: if ((unsigned)bno >= fs->fs_size) {
889: printf("bad block %d, ino %d\n", bno, ip->i_number);
890: fserr(fs, cred->cr_uid, "bad block");
891: return;
892: }
893: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
894: (int)fs->fs_cgsize, NOCRED, &bp);
895: if (error) {
896: brelse(bp);
897: return;
898: }
899: cgp = bp->b_un.b_cg;
900: if (!cg_chkmagic(cgp)) {
901: brelse(bp);
902: return;
903: }
904: cgp->cg_time = time.tv_sec;
905: bno = dtogd(fs, bno);
906: if (size == fs->fs_bsize) {
907: if (isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno))) {
908: printf("dev = 0x%x, block = %d, fs = %s\n",
909: ip->i_dev, bno, fs->fs_fsmnt);
910: panic("blkfree: freeing free block");
911: }
912: setblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno));
913: cgp->cg_cs.cs_nbfree++;
914: fs->fs_cstotal.cs_nbfree++;
915: fs->fs_cs(fs, cg).cs_nbfree++;
916: i = cbtocylno(fs, bno);
917: cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++;
918: cg_blktot(cgp)[i]++;
919: } else {
920: bbase = bno - fragnum(fs, bno);
921: /*
922: * decrement the counts associated with the old frags
923: */
924: blk = blkmap(fs, cg_blksfree(cgp), bbase);
925: fragacct(fs, blk, cgp->cg_frsum, -1);
926: /*
927: * deallocate the fragment
928: */
929: frags = numfrags(fs, size);
930: for (i = 0; i < frags; i++) {
931: if (isset(cg_blksfree(cgp), bno + i)) {
932: printf("dev = 0x%x, block = %d, fs = %s\n",
933: ip->i_dev, bno + i, fs->fs_fsmnt);
934: panic("blkfree: freeing free frag");
935: }
936: setbit(cg_blksfree(cgp), bno + i);
937: }
938: cgp->cg_cs.cs_nffree += i;
939: fs->fs_cstotal.cs_nffree += i;
940: fs->fs_cs(fs, cg).cs_nffree += i;
941: /*
942: * add back in counts associated with the new frags
943: */
944: blk = blkmap(fs, cg_blksfree(cgp), bbase);
945: fragacct(fs, blk, cgp->cg_frsum, 1);
946: /*
947: * if a complete block has been reassembled, account for it
948: */
949: if (isblock(fs, cg_blksfree(cgp),
950: (daddr_t)fragstoblks(fs, bbase))) {
951: cgp->cg_cs.cs_nffree -= fs->fs_frag;
952: fs->fs_cstotal.cs_nffree -= fs->fs_frag;
953: fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
954: cgp->cg_cs.cs_nbfree++;
955: fs->fs_cstotal.cs_nbfree++;
956: fs->fs_cs(fs, cg).cs_nbfree++;
957: i = cbtocylno(fs, bbase);
958: cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++;
959: cg_blktot(cgp)[i]++;
960: }
961: }
962: fs->fs_fmod++;
963: bdwrite(bp);
964: }
965:
966: /*
967: * Free an inode.
968: *
969: * The specified inode is placed back in the free map.
970: */
971: ifree(ip, ino, mode)
972: struct inode *ip;
973: ino_t ino;
974: int mode;
975: {
976: register struct fs *fs;
977: register struct cg *cgp;
978: struct buf *bp;
979: int error, cg;
980:
981: fs = ip->i_fs;
982: if ((unsigned)ino >= fs->fs_ipg*fs->fs_ncg) {
983: printf("dev = 0x%x, ino = %d, fs = %s\n",
984: ip->i_dev, ino, fs->fs_fsmnt);
985: panic("ifree: range");
986: }
987: cg = itog(fs, ino);
988: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
989: (int)fs->fs_cgsize, NOCRED, &bp);
990: if (error) {
991: brelse(bp);
992: return;
993: }
994: cgp = bp->b_un.b_cg;
995: if (!cg_chkmagic(cgp)) {
996: brelse(bp);
997: return;
998: }
999: cgp->cg_time = time.tv_sec;
1000: ino %= fs->fs_ipg;
1001: if (isclr(cg_inosused(cgp), ino)) {
1002: printf("dev = 0x%x, ino = %d, fs = %s\n",
1003: ip->i_dev, ino, fs->fs_fsmnt);
1004: if (fs->fs_ronly == 0)
1005: panic("ifree: freeing free inode");
1006: }
1007: clrbit(cg_inosused(cgp), ino);
1008: if (ino < cgp->cg_irotor)
1009: cgp->cg_irotor = ino;
1010: cgp->cg_cs.cs_nifree++;
1011: fs->fs_cstotal.cs_nifree++;
1012: fs->fs_cs(fs, cg).cs_nifree++;
1013: if ((mode & IFMT) == IFDIR) {
1014: cgp->cg_cs.cs_ndir--;
1015: fs->fs_cstotal.cs_ndir--;
1016: fs->fs_cs(fs, cg).cs_ndir--;
1017: }
1018: fs->fs_fmod++;
1019: bdwrite(bp);
1020: }
1021:
1022: /*
1023: * Find a block of the specified size in the specified cylinder group.
1024: *
1025: * It is a panic if a request is made to find a block if none are
1026: * available.
1027: */
1028: daddr_t
1029: mapsearch(fs, cgp, bpref, allocsiz)
1030: register struct fs *fs;
1031: register struct cg *cgp;
1032: daddr_t bpref;
1033: int allocsiz;
1034: {
1035: daddr_t bno;
1036: int start, len, loc, i;
1037: int blk, field, subfield, pos;
1038:
1039: /*
1040: * find the fragment by searching through the free block
1041: * map for an appropriate bit pattern
1042: */
1043: if (bpref)
1044: start = dtogd(fs, bpref) / NBBY;
1045: else
1046: start = cgp->cg_frotor / NBBY;
1047: len = howmany(fs->fs_fpg, NBBY) - start;
1048: loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[start],
1049: (u_char *)fragtbl[fs->fs_frag],
1050: (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
1051: if (loc == 0) {
1052: len = start + 1;
1053: start = 0;
1054: loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[0],
1055: (u_char *)fragtbl[fs->fs_frag],
1056: (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
1057: if (loc == 0) {
1058: printf("start = %d, len = %d, fs = %s\n",
1059: start, len, fs->fs_fsmnt);
1060: panic("alloccg: map corrupted");
1061: /* NOTREACHED */
1062: }
1063: }
1064: bno = (start + len - loc) * NBBY;
1065: cgp->cg_frotor = bno;
1066: /*
1067: * found the byte in the map
1068: * sift through the bits to find the selected frag
1069: */
1070: for (i = bno + NBBY; bno < i; bno += fs->fs_frag) {
1071: blk = blkmap(fs, cg_blksfree(cgp), bno);
1072: blk <<= 1;
1073: field = around[allocsiz];
1074: subfield = inside[allocsiz];
1075: for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) {
1076: if ((blk & field) == subfield)
1077: return (bno + pos);
1078: field <<= 1;
1079: subfield <<= 1;
1080: }
1081: }
1082: printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt);
1083: panic("alloccg: block not in map");
1084: return (-1);
1085: }
1086:
1087: /*
1088: * Fserr prints the name of a file system with an error diagnostic.
1089: *
1090: * The form of the error message is:
1091: * fs: error message
1092: */
1093: fserr(fs, uid, cp)
1094: struct fs *fs;
1095: uid_t uid;
1096: char *cp;
1097: {
1098:
1099: log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp);
1100: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.