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