![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ffs_alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / bsd / ufs / ffs|
Return to ffs_alloc.c CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / ufs / ffs |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
26: /*
27: * Copyright (c) 1982, 1986, 1989, 1993
28: * The Regents of the University of California. All rights reserved.
29: *
30: * Redistribution and use in source and binary forms, with or without
31: * modification, are permitted provided that the following conditions
32: * are met:
33: * 1. Redistributions of source code must retain the above copyright
34: * notice, this list of conditions and the following disclaimer.
35: * 2. Redistributions in binary form must reproduce the above copyright
36: * notice, this list of conditions and the following disclaimer in the
37: * documentation and/or other materials provided with the distribution.
38: * 3. All advertising materials mentioning features or use of this software
39: * must display the following acknowledgement:
40: * This product includes software developed by the University of
41: * California, Berkeley and its contributors.
42: * 4. Neither the name of the University nor the names of its contributors
43: * may be used to endorse or promote products derived from this software
44: * without specific prior written permission.
45: *
46: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
47: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
49: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
50: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
51: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
52: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
53: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
54: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
55: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
56: * SUCH DAMAGE.
57: *
58: * @(#)ffs_alloc.c 8.18 (Berkeley) 5/26/95
59: */
60: #include <rev_endian_fs.h>
61: #include <vm/vm_pager.h>
62: #include <vm/vnode_pager.h>
63:
64: #include <sys/param.h>
65: #include <sys/systm.h>
66: #include <sys/buf.h>
67: #include <sys/proc.h>
68: #include <sys/vnode.h>
69: #include <sys/mount.h>
70: #include <sys/kernel.h>
71: #include <sys/syslog.h>
72:
73: #include <sys/vm.h>
74:
75: #include <ufs/ufs/quota.h>
76: #include <ufs/ufs/inode.h>
77:
78: #include <ufs/ffs/fs.h>
79: #include <ufs/ffs/ffs_extern.h>
80:
81: #if REV_ENDIAN_FS
82: #include <ufs/ufs/ufs_byte_order.h>
83: #include <architecture/byte_order.h>
84: #endif /* REV_ENDIAN_FS */
85:
86: extern u_long nextgennumber;
87:
88: static ufs_daddr_t ffs_alloccg __P((struct inode *, int, ufs_daddr_t, int));
89: static ufs_daddr_t ffs_alloccgblk __P((struct fs *, struct cg *, ufs_daddr_t));
90: static ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t,
91: int));
92: static ino_t ffs_dirpref __P((struct fs *));
93: static ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int));
94: static void ffs_fserr __P((struct fs *, u_int, char *));
95: static u_long ffs_hashalloc
96: __P((struct inode *, int, long, int, u_int32_t (*)()));
97: static ino_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int));
98: static ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, ufs_daddr_t,
99: int));
100:
101: /*
102: * Allocate a block in the file system.
103: *
104: * The size of the requested block is given, which must be some
105: * multiple of fs_fsize and <= fs_bsize.
106: * A preference may be optionally specified. If a preference is given
107: * the following hierarchy is used to allocate a block:
108: * 1) allocate the requested block.
109: * 2) allocate a rotationally optimal block in the same cylinder.
110: * 3) allocate a block in the same cylinder group.
111: * 4) quadradically rehash into other cylinder groups, until an
112: * available block is located.
113: * If no block preference is given the following heirarchy is used
114: * to allocate a block:
115: * 1) allocate a block in the cylinder group that contains the
116: * inode for the file.
117: * 2) quadradically rehash into other cylinder groups, until an
118: * available block is located.
119: */
120: ffs_alloc(ip, lbn, bpref, size, cred, bnp)
121: register struct inode *ip;
122: ufs_daddr_t lbn, bpref;
123: int size;
124: struct ucred *cred;
125: ufs_daddr_t *bnp;
126: {
127: register struct fs *fs;
128: ufs_daddr_t bno;
129: int cg, error;
130: #if NeXT
131: int devBlockSize=0;
132: #endif /* NeXT */
133: *bnp = 0;
134: fs = ip->i_fs;
135: #if DIAGNOSTIC
136: if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) {
137: printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n",
138: ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt);
139: panic("ffs_alloc: bad size");
140: }
141: if (cred == NOCRED)
142: panic("ffs_alloc: missing credential\n");
143: #endif /* DIAGNOSTIC */
144: if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0)
145: goto nospace;
146: if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0)
147: goto nospace;
148: #ifdef NeXT
149: VOP_DEVBLOCKSIZE(ip->i_devvp,&devBlockSize);
150: #endif /* NeXT */
151: #if QUOTA
152: #ifdef NeXT
153: if (error = chkdq(ip, (long)btodb(size, devBlockSize), cred, 0))
154: #else
155: if (error = chkdq(ip, (long)btodb(size), cred, 0))
156: #endif /* NeXT */
157: return (error);
158: #endif /* QUOTA */
159: if (bpref >= fs->fs_size)
160: bpref = 0;
161: if (bpref == 0)
162: cg = ino_to_cg(fs, ip->i_number);
163: else
164: cg = dtog(fs, bpref);
165: bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size,
166: (u_int32_t (*)())ffs_alloccg);
167: if (bno > 0) {
168: #ifdef NeXT
169: ip->i_blocks += btodb(size, devBlockSize);
170: #else
171: ip->i_blocks += btodb(size);
172: #endif /* NeXT */
173: ip->i_flag |= IN_CHANGE | IN_UPDATE;
174: *bnp = bno;
175: return (0);
176: }
177: #if QUOTA
178: /*
179: * Restore user's disk quota because allocation failed.
180: */
181: #ifdef NeXT
182: (void) chkdq(ip, (long)-btodb(size, devBlockSize), cred, FORCE);
183: #else
184: (void) chkdq(ip, (long)-btodb(size), cred, FORCE);
185: #endif /* NeXT */
186: #endif /* QUOTA */
187: nospace:
188: ffs_fserr(fs, cred->cr_uid, "file system full");
189: uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
190: return (ENOSPC);
191: }
192:
193: /*
194: * Reallocate a fragment to a bigger size
195: *
196: * The number and size of the old block is given, and a preference
197: * and new size is also specified. The allocator attempts to extend
198: * the original block. Failing that, the regular block allocator is
199: * invoked to get an appropriate block.
200: */
201: ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp)
202: register struct inode *ip;
203: ufs_daddr_t lbprev;
204: ufs_daddr_t bpref;
205: int osize, nsize;
206: struct ucred *cred;
207: struct buf **bpp;
208: {
209: register struct fs *fs;
210: struct buf *bp;
211: int cg, request, error;
212: ufs_daddr_t bprev, bno;
213: #ifdef NeXT
214: int devBlockSize=0;
215: #endif
216:
217: *bpp = 0;
218: fs = ip->i_fs;
219: #if DIAGNOSTIC
220: if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 ||
221: (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) {
222: printf(
223: "dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n",
224: ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt);
225: panic("ffs_realloccg: bad size");
226: }
227: if (cred == NOCRED)
228: panic("ffs_realloccg: missing credential\n");
229: #endif /* DIAGNOSTIC */
230: if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0)
231: goto nospace;
232: if ((bprev = ip->i_db[lbprev]) == 0) {
233: printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n",
234: ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt);
235: panic("ffs_realloccg: bad bprev");
236: }
237: /*
238: * Allocate the extra space in the buffer.
239: */
240: if (error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp)) {
241: brelse(bp);
242: return (error);
243: }
244: #ifdef NeXT
245: VOP_DEVBLOCKSIZE(ip->i_devvp,&devBlockSize);
246: #endif /* NeXT */
247:
248: #if QUOTA
249: #ifdef NeXT
250: if (error = chkdq(ip, (long)btodb(nsize - osize, devBlockSize), cred, 0))
251: #else
252: if (error = chkdq(ip, (long)btodb(nsize - osize), cred, 0))
253: #endif /* NeXT */
254: {
255: brelse(bp);
256: return (error);
257: }
258: #endif /* QUOTA */
259: /*
260: * Check for extension in the existing location.
261: */
262: cg = dtog(fs, bprev);
263: if (bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize)) {
264: if (bp->b_blkno != fsbtodb(fs, bno))
265: panic("bad blockno");
266: #ifdef NeXT
267: ip->i_blocks += btodb(nsize - osize, devBlockSize);
268: #else
269: ip->i_blocks += btodb(nsize - osize);
270: #endif /* NeXT */
271: ip->i_flag |= IN_CHANGE | IN_UPDATE;
272: allocbuf(bp, nsize);
273: bp->b_flags |= B_DONE;
274: bzero((char *)bp->b_data + osize, (u_int)nsize - osize);
275: *bpp = bp;
276: return (0);
277: }
278: /*
279: * Allocate a new disk location.
280: */
281: if (bpref >= fs->fs_size)
282: bpref = 0;
283: switch ((int)fs->fs_optim) {
284: case FS_OPTSPACE:
285: /*
286: * Allocate an exact sized fragment. Although this makes
287: * best use of space, we will waste time relocating it if
288: * the file continues to grow. If the fragmentation is
289: * less than half of the minimum free reserve, we choose
290: * to begin optimizing for time.
291: */
292: request = nsize;
293: if (fs->fs_minfree < 5 ||
294: fs->fs_cstotal.cs_nffree >
295: fs->fs_dsize * fs->fs_minfree / (2 * 100))
296: break;
297: log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n",
298: fs->fs_fsmnt);
299: fs->fs_optim = FS_OPTTIME;
300: break;
301: case FS_OPTTIME:
302: /*
303: * At this point we have discovered a file that is trying to
304: * grow a small fragment to a larger fragment. To save time,
305: * we allocate a full sized block, then free the unused portion.
306: * If the file continues to grow, the `ffs_fragextend' call
307: * above will be able to grow it in place without further
308: * copying. If aberrant programs cause disk fragmentation to
309: * grow within 2% of the free reserve, we choose to begin
310: * optimizing for space.
311: */
312: request = fs->fs_bsize;
313: if (fs->fs_cstotal.cs_nffree <
314: fs->fs_dsize * (fs->fs_minfree - 2) / 100)
315: break;
316: log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n",
317: fs->fs_fsmnt);
318: fs->fs_optim = FS_OPTSPACE;
319: break;
320: default:
321: printf("dev = 0x%x, optim = %d, fs = %s\n",
322: ip->i_dev, fs->fs_optim, fs->fs_fsmnt);
323: panic("ffs_realloccg: bad optim");
324: /* NOTREACHED */
325: }
326: bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request,
327: (u_int32_t (*)())ffs_alloccg);
328: if (bno > 0) {
329: bp->b_blkno = fsbtodb(fs, bno);
330: #if MACH
331: if (ITOV(ip)->v_vm_info != 0)
332: (void) vnode_uncache(ITOV(ip));
333: #endif
334: ffs_blkfree(ip, bprev, (long)osize);
335: if (nsize < request)
336: ffs_blkfree(ip, bno + numfrags(fs, nsize),
337: (long)(request - nsize));
338: #ifdef NeXT
339: ip->i_blocks += btodb(nsize - osize, devBlockSize);
340: #else
341: ip->i_blocks += btodb(nsize - osize);
342: #endif /* NeXT */
343: ip->i_flag |= IN_CHANGE | IN_UPDATE;
344: allocbuf(bp, nsize);
345: bp->b_flags |= B_DONE;
346: bzero((char *)bp->b_data + osize, (u_int)nsize - osize);
347: *bpp = bp;
348: return (0);
349: }
350: #if QUOTA
351: /*
352: * Restore user's disk quota because allocation failed.
353: */
354: #ifdef NeXT
355: (void) chkdq(ip, (long)-btodb(nsize - osize, devBlockSize), cred, FORCE);
356: #else
357: (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE);
358: #endif /* NeXT */
359: #endif /* QUOTA */
360: brelse(bp);
361: nospace:
362: /*
363: * no space available
364: */
365: ffs_fserr(fs, cred->cr_uid, "file system full");
366: uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
367: return (ENOSPC);
368: }
369:
370: /*
371: * Reallocate a sequence of blocks into a contiguous sequence of blocks.
372: *
373: * The vnode and an array of buffer pointers for a range of sequential
374: * logical blocks to be made contiguous is given. The allocator attempts
375: * to find a range of sequential blocks starting as close as possible to
376: * an fs_rotdelay offset from the end of the allocation for the logical
377: * block immediately preceeding the current range. If successful, the
378: * physical block numbers in the buffer pointers and in the inode are
379: * changed to reflect the new allocation. If unsuccessful, the allocation
380: * is left unchanged. The success in doing the reallocation is returned.
381: * Note that the error return is not reflected back to the user. Rather
382: * the previous block allocation will be used.
383: */
384: int doasyncfree = 1;
385: int doreallocblks = 1;
386: int prtrealloc = 0;
387:
388: int
389: ffs_reallocblks(ap)
390: struct vop_reallocblks_args /* {
391: struct vnode *a_vp;
392: struct cluster_save *a_buflist;
393: } */ *ap;
394: {
395: struct fs *fs;
396: struct inode *ip;
397: struct vnode *vp;
398: struct buf *sbp, *ebp;
399: ufs_daddr_t *bap, *sbap, *ebap;
400: struct cluster_save *buflist;
401: ufs_daddr_t start_lbn, end_lbn, soff, eoff, newblk, blkno;
402: struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp;
403: int i, len, start_lvl, end_lvl, pref, ssize;
404: #if REV_ENDIAN_FS
405: int rev_endian=0;
406: #endif /* REV_ENDIAN_FS */
407:
408: if (doreallocblks == 0)
409: return (ENOSPC);
410: vp = ap->a_vp;
411: #if REV_ENDIAN_FS
412: rev_endian = vp->v_mount->mnt_flag & MNT_REVEND;
413: #endif /* REV_ENDIAN_FS */
414:
415: ip = VTOI(vp);
416: fs = ip->i_fs;
417: if (fs->fs_contigsumsize <= 0)
418: return (ENOSPC);
419: buflist = ap->a_buflist;
420: len = buflist->bs_nchildren;
421: start_lbn = buflist->bs_children[0]->b_lblkno;
422: end_lbn = start_lbn + len - 1;
423: #if DIAGNOSTIC
424: for (i = 0; i < len; i++)
425: if (!ffs_checkblk(ip,
426: dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
427: panic("ffs_reallocblks: unallocated block 1");
428: for (i = 1; i < len; i++)
429: if (buflist->bs_children[i]->b_lblkno != start_lbn + i)
430: panic("ffs_reallocblks: non-logical cluster");
431: blkno = buflist->bs_children[0]->b_blkno;
432: ssize = fsbtodb(fs, fs->fs_frag);
433: for (i = 1; i < len - 1; i++)
434: if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize))
435: panic("ffs_reallocblks: non-physical cluster %d", i);
436: #endif
437: /*
438: * If the latest allocation is in a new cylinder group, assume that
439: * the filesystem has decided to move and do not force it back to
440: * the previous cylinder group.
441: */
442: if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) !=
443: dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno)))
444: return (ENOSPC);
445: if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
446: ufs_getlbns(vp, end_lbn, end_ap, &end_lvl))
447: return (ENOSPC);
448: /*
449: * Get the starting offset and block map for the first block.
450: */
451: if (start_lvl == 0) {
452: sbap = &ip->i_db[0];
453: soff = start_lbn;
454: } else {
455: idp = &start_ap[start_lvl - 1];
456: if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) {
457: brelse(sbp);
458: return (ENOSPC);
459: }
460: sbap = (ufs_daddr_t *)sbp->b_data;
461: soff = idp->in_off;
462: }
463: /*
464: * Find the preferred location for the cluster.
465: */
466: pref = ffs_blkpref(ip, start_lbn, soff, sbap);
467: /*
468: * If the block range spans two block maps, get the second map.
469: */
470: if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
471: ssize = len;
472: } else {
473: #if DIAGNOSTIC
474: if (start_lvl && start_ap[start_lvl-1].in_lbn == idp->in_lbn)
475: panic("ffs_reallocblk: start == end");
476: #endif
477: ssize = len - (idp->in_off + 1);
478: if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp))
479: goto fail;
480: ebap = (ufs_daddr_t *)ebp->b_data;
481: }
482: /*
483: * Search the block map looking for an allocation of the desired size.
484: */
485: if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref,
486: len, (u_int32_t (*)())ffs_clusteralloc)) == 0)
487: goto fail;
488: /*
489: * We have found a new contiguous block.
490: *
491: * First we have to replace the old block pointers with the new
492: * block pointers in the inode and indirect blocks associated
493: * with the file.
494: */
495: #ifdef DEBUG
496: if (prtrealloc)
497: printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number,
498: start_lbn, end_lbn);
499: #endif
500: blkno = newblk;
501: for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) {
502: if (i == ssize)
503: bap = ebap;
504: #if DIAGNOSTIC
505: if (!ffs_checkblk(ip,
506: dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
507: panic("ffs_reallocblks: unallocated block 2");
508: #if REV_ENDIAN_FS
509: if (rev_endian && !(bap >= &ip->i_db[0] && bap <= &ip->i_db[NDADDR-1])) {
510: if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != NXSwapLong(*bap))
511: panic("ffs_reallocblks: alloc mismatch");
512: } else {
513: #endif /* REV_ENDIAN_FS */
514: if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap)
515: panic("ffs_reallocblks: alloc mismatch");
516: #if REV_ENDIAN_FS
517: }
518: #endif /* REV_ENDIAN_FS */
519: #endif
520: #ifdef DEBUG
521: #if REV_ENDIAN_FS
522: if (rev_endian && !(bap >= &ip->i_db[0] && bap <= &ip->i_db[NDADDR-1])) {
523: if (prtrealloc)
524: printf(" %d,", NXSwapLong(*bap));
525: }else {
526: #endif /* REV_ENDIAN_FS */
527: if (prtrealloc)
528: printf(" %d,", *bap);
529: #if REV_ENDIAN_FS
530: }
531: #endif /* REV_ENDIAN_FS */
532: #endif
533: #if REV_ENDIAN_FS
534: if (rev_endian && !(bap >= &ip->i_db[0] && bap <= &ip->i_db[NDADDR-1])) {
535: /* An indirect block need to swap as
536: * it is going to be written out directly
537: */
538: *bap++ = NXSwapLong(blkno);
539: }
540: else {
541: /* Direct block; going to be written out
542: * by a VOP_UPDATE; which takes care of swapping
543: */
544: #endif /* REV_ENDIAN_FS */
545: *bap++ = blkno;
546: #if REV_ENDIAN_FS
547: }
548: #endif /* REV_ENDIAN_FS */
549:
550: }
551: /*
552: * Next we must write out the modified inode and indirect blocks.
553: * For strict correctness, the writes should be synchronous since
554: * the old block values may have been written to disk. In practise
555: * they are almost never written, but if we are concerned about
556: * strict correctness, the `doasyncfree' flag should be set to zero.
557: *
558: * The test on `doasyncfree' should be changed to test a flag
559: * that shows whether the associated buffers and inodes have
560: * been written. The flag should be set when the cluster is
561: * started and cleared whenever the buffer or inode is flushed.
562: * We can then check below to see if it is set, and do the
563: * synchronous write only when it has been cleared.
564: */
565: if (sbap != &ip->i_db[0]) {
566: if (doasyncfree)
567: bdwrite(sbp);
568: else
569: bwrite(sbp);
570: } else {
571: ip->i_flag |= IN_CHANGE | IN_UPDATE;
572: if (!doasyncfree)
573: VOP_UPDATE(vp, &time, &time, MNT_WAIT);
574: }
575: if (ssize < len)
576: if (doasyncfree)
577: bdwrite(ebp);
578: else
579: bwrite(ebp);
580: /*
581: * Last, free the old blocks and assign the new blocks to the buffers.
582: */
583: #ifdef DEBUG
584: if (prtrealloc)
585: printf("\n\tnew:");
586: #endif
587: for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) {
588: ffs_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno),
589: fs->fs_bsize);
590: buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno);
591: #if DIAGNOSTIC
592: if (!ffs_checkblk(ip,
593: dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
594: panic("ffs_reallocblks: unallocated block 3");
595: if (prtrealloc)
596: printf(" %d,", blkno);
597: #endif
598: }
599: #ifdef DEBUG
600: if (prtrealloc) {
601: prtrealloc--;
602: printf("\n");
603: }
604: #endif
605: return (0);
606:
607: fail:
608: if (ssize < len)
609: brelse(ebp);
610: if (sbap != &ip->i_db[0])
611: brelse(sbp);
612: return (ENOSPC);
613: }
614:
615: /*
616: * Allocate an inode in the file system.
617: *
618: * If allocating a directory, use ffs_dirpref to select the inode.
619: * If allocating in a directory, the following hierarchy is followed:
620: * 1) allocate the preferred inode.
621: * 2) allocate an inode in the same cylinder group.
622: * 3) quadradically rehash into other cylinder groups, until an
623: * available inode is located.
624: * If no inode preference is given the following heirarchy is used
625: * to allocate an inode:
626: * 1) allocate an inode in cylinder group 0.
627: * 2) quadradically rehash into other cylinder groups, until an
628: * available inode is located.
629: */
630: int
631: ffs_valloc(ap)
632: struct vop_valloc_args /* {
633: struct vnode *a_pvp;
634: int a_mode;
635: struct ucred *a_cred;
636: struct vnode **a_vpp;
637: } */ *ap;
638: {
639: register struct vnode *pvp = ap->a_pvp;
640: register struct inode *pip;
641: register struct fs *fs;
642: register struct inode *ip;
643: mode_t mode = ap->a_mode;
644: ino_t ino, ipref;
645: int cg, error;
646:
647: *ap->a_vpp = NULL;
648: pip = VTOI(pvp);
649: fs = pip->i_fs;
650: if (fs->fs_cstotal.cs_nifree == 0)
651: goto noinodes;
652:
653: if ((mode & IFMT) == IFDIR)
654: ipref = ffs_dirpref(fs);
655: else
656: ipref = pip->i_number;
657: if (ipref >= fs->fs_ncg * fs->fs_ipg)
658: ipref = 0;
659: cg = ino_to_cg(fs, ipref);
660: ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_nodealloccg);
661: if (ino == 0)
662: goto noinodes;
663: error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp);
664: if (error) {
665: VOP_VFREE(pvp, ino, mode);
666: return (error);
667: }
668: ip = VTOI(*ap->a_vpp);
669: if (ip->i_mode) {
670: printf("mode = 0%o, inum = %d, fs = %s\n",
671: ip->i_mode, ip->i_number, fs->fs_fsmnt);
672: panic("ffs_valloc: dup alloc");
673: }
674: if (ip->i_blocks) { /* XXX */
675: printf("free inode %s/%d had %d blocks\n",
676: fs->fs_fsmnt, ino, ip->i_blocks);
677: ip->i_blocks = 0;
678: }
679: ip->i_flags = 0;
680: /*
681: * Set up a new generation number for this inode.
682: */
683: if (++nextgennumber < (u_long)time.tv_sec)
684: nextgennumber = time.tv_sec;
685: ip->i_gen = nextgennumber;
686: return (0);
687: noinodes:
688: ffs_fserr(fs, ap->a_cred->cr_uid, "out of inodes");
689: uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt);
690: return (ENOSPC);
691: }
692:
693: /*
694: * Find a cylinder to place a directory.
695: *
696: * The policy implemented by this algorithm is to select from
697: * among those cylinder groups with above the average number of
698: * free inodes, the one with the smallest number of directories.
699: */
700: static ino_t
701: ffs_dirpref(fs)
702: register struct fs *fs;
703: {
704: int cg, minndir, mincg, avgifree;
705:
706: avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg;
707: minndir = fs->fs_ipg;
708: mincg = 0;
709: for (cg = 0; cg < fs->fs_ncg; cg++)
710: if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
711: fs->fs_cs(fs, cg).cs_nifree >= avgifree) {
712: mincg = cg;
713: minndir = fs->fs_cs(fs, cg).cs_ndir;
714: }
715: return ((ino_t)(fs->fs_ipg * mincg));
716: }
717:
718: /*
719: * Select the desired position for the next block in a file. The file is
720: * logically divided into sections. The first section is composed of the
721: * direct blocks. Each additional section contains fs_maxbpg blocks.
722: *
723: * If no blocks have been allocated in the first section, the policy is to
724: * request a block in the same cylinder group as the inode that describes
725: * the file. If no blocks have been allocated in any other section, the
726: * policy is to place the section in a cylinder group with a greater than
727: * average number of free blocks. An appropriate cylinder group is found
728: * by using a rotor that sweeps the cylinder groups. When a new group of
729: * blocks is needed, the sweep begins in the cylinder group following the
730: * cylinder group from which the previous allocation was made. The sweep
731: * continues until a cylinder group with greater than the average number
732: * of free blocks is found. If the allocation is for the first block in an
733: * indirect block, the information on the previous allocation is unavailable;
734: * here a best guess is made based upon the logical block number being
735: * allocated.
736: *
737: * If a section is already partially allocated, the policy is to
738: * contiguously allocate fs_maxcontig blocks. The end of one of these
739: * contiguous blocks and the beginning of the next is physically separated
740: * so that the disk head will be in transit between them for at least
741: * fs_rotdelay milliseconds. This is to allow time for the processor to
742: * schedule another I/O transfer.
743: */
744: ufs_daddr_t
745: ffs_blkpref(ip, lbn, indx, bap)
746: struct inode *ip;
747: ufs_daddr_t lbn;
748: int indx;
749: ufs_daddr_t *bap;
750: {
751: register struct fs *fs;
752: register int cg;
753: int avgbfree, startcg;
754: ufs_daddr_t nextblk;
755: #if REV_ENDIAN_FS
756: daddr_t prev=0;
757: struct vnode *vp=ITOV(ip);
758: struct mount *mp=vp->v_mount;
759: int rev_endian=(mp->mnt_flag & MNT_REVEND);
760: #endif /* REV_ENDIAN_FS */
761:
762: fs = ip->i_fs;
763: #if REV_ENDIAN_FS
764: if (indx && bap) {
765: if (rev_endian) {
766: if (bap != &ip->i_db[0])
767: prev = NXSwapLong(bap[indx - 1]);
768: else
769: prev = bap[indx - 1];
770: } else prev = bap[indx - 1];
771: }
772: if (indx % fs->fs_maxbpg == 0 || prev == 0)
773: #else /* REV_ENDIAN_FS */
774: if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0)
775: #endif /* REV_ENDIAN_FS */
776: {
777: if (lbn < NDADDR) {
778: cg = ino_to_cg(fs, ip->i_number);
779: return (fs->fs_fpg * cg + fs->fs_frag);
780: }
781: /*
782: * Find a cylinder with greater than average number of
783: * unused data blocks.
784: */
785: #if REV_ENDIAN_FS
786: if (indx == 0 || prev == 0)
787: #else /* REV_ENDIAN_FS */
788: if (indx == 0 || bap[indx - 1] == 0)
789: #endif /* REV_ENDIAN_FS */
790: startcg =
791: ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg;
792: else
793: #if REV_ENDIAN_FS
794: startcg = dtog(fs, prev) + 1;
795: #else /* REV_ENDIAN_FS */
796: startcg = dtog(fs, bap[indx - 1]) + 1;
797: #endif /* REV_ENDIAN_FS */
798: startcg %= fs->fs_ncg;
799: avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
800: for (cg = startcg; cg < fs->fs_ncg; cg++)
801: if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
802: fs->fs_cgrotor = cg;
803: return (fs->fs_fpg * cg + fs->fs_frag);
804: }
805: for (cg = 0; cg <= startcg; cg++)
806: if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
807: fs->fs_cgrotor = cg;
808: return (fs->fs_fpg * cg + fs->fs_frag);
809: }
810: return (NULL);
811: }
812: /*
813: * One or more previous blocks have been laid out. If less
814: * than fs_maxcontig previous blocks are contiguous, the
815: * next block is requested contiguously, otherwise it is
816: * requested rotationally delayed by fs_rotdelay milliseconds.
817: */
818: #if REV_ENDIAN_FS
819: if (rev_endian) {
820: nextblk = prev + fs->fs_frag;
821: if (indx < fs->fs_maxcontig) {
822: return (nextblk);
823: }
824: if (bap != &ip->i_db[0])
825: prev = NXSwapLong(bap[indx - fs->fs_maxcontig]);
826: else
827: prev = bap[indx - fs->fs_maxcontig];
828: if (prev + blkstofrags(fs, fs->fs_maxcontig) != nextblk)
829: return (nextblk);
830: } else {
831: #endif /* REV_ENDIAN_FS */
832: nextblk = bap[indx - 1] + fs->fs_frag;
833: if (indx < fs->fs_maxcontig || bap[indx - fs->fs_maxcontig] +
834: blkstofrags(fs, fs->fs_maxcontig) != nextblk)
835: return (nextblk);
836: #if REV_ENDIAN_FS
837: }
838: #endif /* REV_ENDIAN_FS */
839: if (fs->fs_rotdelay != 0)
840: /*
841: * Here we convert ms of delay to frags as:
842: * (frags) = (ms) * (rev/sec) * (sect/rev) /
843: * ((sect/frag) * (ms/sec))
844: * then round up to the next block.
845: */
846: nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect /
847: (NSPF(fs) * 1000), fs->fs_frag);
848: return (nextblk);
849: }
850:
851: /*
852: * Implement the cylinder overflow algorithm.
853: *
854: * The policy implemented by this algorithm is:
855: * 1) allocate the block in its requested cylinder group.
856: * 2) quadradically rehash on the cylinder group number.
857: * 3) brute force search for a free block.
858: */
859: /*VARARGS5*/
860: static u_long
861: ffs_hashalloc(ip, cg, pref, size, allocator)
862: struct inode *ip;
863: int cg;
864: long pref;
865: int size; /* size for data blocks, mode for inodes */
866: u_int32_t (*allocator)();
867: {
868: register struct fs *fs;
869: long result;
870: int i, icg = cg;
871:
872: fs = ip->i_fs;
873: /*
874: * 1: preferred cylinder group
875: */
876: result = (*allocator)(ip, cg, pref, size);
877: if (result)
878: return (result);
879: /*
880: * 2: quadratic rehash
881: */
882: for (i = 1; i < fs->fs_ncg; i *= 2) {
883: cg += i;
884: if (cg >= fs->fs_ncg)
885: cg -= fs->fs_ncg;
886: result = (*allocator)(ip, cg, 0, size);
887: if (result)
888: return (result);
889: }
890: /*
891: * 3: brute force search
892: * Note that we start at i == 2, since 0 was checked initially,
893: * and 1 is always checked in the quadratic rehash.
894: */
895: cg = (icg + 2) % fs->fs_ncg;
896: for (i = 2; i < fs->fs_ncg; i++) {
897: result = (*allocator)(ip, cg, 0, size);
898: if (result)
899: return (result);
900: cg++;
901: if (cg == fs->fs_ncg)
902: cg = 0;
903: }
904: return (NULL);
905: }
906:
907: /*
908: * Determine whether a fragment can be extended.
909: *
910: * Check to see if the necessary fragments are available, and
911: * if they are, allocate them.
912: */
913: static ufs_daddr_t
914: ffs_fragextend(ip, cg, bprev, osize, nsize)
915: struct inode *ip;
916: int cg;
917: long bprev;
918: int osize, nsize;
919: {
920: register struct fs *fs;
921: register struct cg *cgp;
922: struct buf *bp;
923: long bno;
924: int frags, bbase;
925: int i, error;
926: #if REV_ENDIAN_FS
927: struct vnode *vp=ITOV(ip);
928: struct mount *mp=vp->v_mount;
929: int rev_endian=(mp->mnt_flag & MNT_REVEND);
930: #endif /* REV_ENDIAN_FS */
931:
932: fs = ip->i_fs;
933: if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize))
934: return (NULL);
935: frags = numfrags(fs, nsize);
936: bbase = fragnum(fs, bprev);
937: if (bbase > fragnum(fs, (bprev + frags - 1))) {
938: /* cannot extend across a block boundary */
939: return (NULL);
940: }
941: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
942: (int)fs->fs_cgsize, NOCRED, &bp);
943: if (error) {
944: brelse(bp);
945: return (NULL);
946: }
947: cgp = (struct cg *)bp->b_data;
948: #if REV_ENDIAN_FS
949: if (rev_endian) {
950: byte_swap_cgin(cgp, fs);
951: }
952: #endif /* REV_ENDIAN_FS */
953:
954: if (!cg_chkmagic(cgp)) {
955: #if REV_ENDIAN_FS
956: if (rev_endian)
957: byte_swap_cgout(cgp,fs);
958: #endif /* REV_ENDIAN_FS */
959: brelse(bp);
960: return (NULL);
961: }
962: cgp->cg_time = time.tv_sec;
963: bno = dtogd(fs, bprev);
964: for (i = numfrags(fs, osize); i < frags; i++)
965: if (isclr(cg_blksfree(cgp), bno + i)) {
966: #if REV_ENDIAN_FS
967: if (rev_endian)
968: byte_swap_cgout(cgp,fs);
969: #endif /* REV_ENDIAN_FS */
970: brelse(bp);
971: return (NULL);
972: }
973: /*
974: * the current fragment can be extended
975: * deduct the count on fragment being extended into
976: * increase the count on the remaining fragment (if any)
977: * allocate the extended piece
978: */
979: for (i = frags; i < fs->fs_frag - bbase; i++)
980: if (isclr(cg_blksfree(cgp), bno + i))
981: break;
982: cgp->cg_frsum[i - numfrags(fs, osize)]--;
983: if (i != frags)
984: cgp->cg_frsum[i - frags]++;
985: for (i = numfrags(fs, osize); i < frags; i++) {
986: clrbit(cg_blksfree(cgp), bno + i);
987: cgp->cg_cs.cs_nffree--;
988: fs->fs_cstotal.cs_nffree--;
989: fs->fs_cs(fs, cg).cs_nffree--;
990: }
991: fs->fs_fmod = 1;
992: #if REV_ENDIAN_FS
993: if (rev_endian)
994: byte_swap_cgout(cgp,fs);
995: #endif /* REV_ENDIAN_FS */
996: bdwrite(bp);
997: return (bprev);
998: }
999:
1000: /*
1001: * Determine whether a block can be allocated.
1002: *
1003: * Check to see if a block of the appropriate size is available,
1004: * and if it is, allocate it.
1005: */
1006: static ufs_daddr_t
1007: ffs_alloccg(ip, cg, bpref, size)
1008: struct inode *ip;
1009: int cg;
1010: ufs_daddr_t bpref;
1011: int size;
1012: {
1013: register struct fs *fs;
1014: register struct cg *cgp;
1015: struct buf *bp;
1016: register int i;
1017: int error, bno, frags, allocsiz;
1018: #if REV_ENDIAN_FS
1019: struct vnode *vp=ITOV(ip);
1020: struct mount *mp=vp->v_mount;
1021: int rev_endian=(mp->mnt_flag & MNT_REVEND);
1022: #endif /* REV_ENDIAN_FS */
1023:
1024: fs = ip->i_fs;
1025: if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize)
1026: return (NULL);
1027: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
1028: (int)fs->fs_cgsize, NOCRED, &bp);
1029: if (error) {
1030: brelse(bp);
1031: return (NULL);
1032: }
1033: cgp = (struct cg *)bp->b_data;
1034: #if REV_ENDIAN_FS
1035: if (rev_endian)
1036: byte_swap_cgin(cgp,fs);
1037: #endif /* REV_ENDIAN_FS */
1038: if (!cg_chkmagic(cgp) ||
1039: (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) {
1040: #if REV_ENDIAN_FS
1041: if (rev_endian)
1042: byte_swap_cgout(cgp,fs);
1043: #endif /* REV_ENDIAN_FS */
1044: brelse(bp);
1045: return (NULL);
1046: }
1047: cgp->cg_time = time.tv_sec;
1048: if (size == fs->fs_bsize) {
1049: bno = ffs_alloccgblk(fs, cgp, bpref);
1050: #if REV_ENDIAN_FS
1051: if (rev_endian)
1052: byte_swap_cgout(cgp,fs);
1053: #endif /* REV_ENDIAN_FS */
1054: bdwrite(bp);
1055: return (bno);
1056: }
1057: /*
1058: * check to see if any fragments are already available
1059: * allocsiz is the size which will be allocated, hacking
1060: * it down to a smaller size if necessary
1061: */
1062: frags = numfrags(fs, size);
1063: for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++)
1064: if (cgp->cg_frsum[allocsiz] != 0)
1065: break;
1066: if (allocsiz == fs->fs_frag) {
1067: /*
1068: * no fragments were available, so a block will be
1069: * allocated, and hacked up
1070: */
1071: if (cgp->cg_cs.cs_nbfree == 0) {
1072: #if REV_ENDIAN_FS
1073: if (rev_endian)
1074: byte_swap_cgout(cgp,fs);
1075: #endif /* REV_ENDIAN_FS */
1076: brelse(bp);
1077: return (NULL);
1078: }
1079: bno = ffs_alloccgblk(fs, cgp, bpref);
1080: bpref = dtogd(fs, bno);
1081: for (i = frags; i < fs->fs_frag; i++)
1082: setbit(cg_blksfree(cgp), bpref + i);
1083: i = fs->fs_frag - frags;
1084: cgp->cg_cs.cs_nffree += i;
1085: fs->fs_cstotal.cs_nffree += i;
1086: fs->fs_cs(fs, cg).cs_nffree += i;
1087: fs->fs_fmod = 1;
1088: cgp->cg_frsum[i]++;
1089: #if REV_ENDIAN_FS
1090: if (rev_endian)
1091: byte_swap_cgout(cgp,fs);
1092: #endif /* REV_ENDIAN_FS */
1093: bdwrite(bp);
1094: return (bno);
1095: }
1096: bno = ffs_mapsearch(fs, cgp, bpref, allocsiz);
1097: if (bno < 0) {
1098: #if REV_ENDIAN_FS
1099: if (rev_endian)
1100: byte_swap_cgout(cgp,fs);
1101: #endif /* REV_ENDIAN_FS */
1102: brelse(bp);
1103: return (NULL);
1104: }
1105: for (i = 0; i < frags; i++)
1106: clrbit(cg_blksfree(cgp), bno + i);
1107: cgp->cg_cs.cs_nffree -= frags;
1108: fs->fs_cstotal.cs_nffree -= frags;
1109: fs->fs_cs(fs, cg).cs_nffree -= frags;
1110: fs->fs_fmod = 1;
1111: cgp->cg_frsum[allocsiz]--;
1112: if (frags != allocsiz)
1113: cgp->cg_frsum[allocsiz - frags]++;
1114: #if REV_ENDIAN_FS
1115: if (rev_endian)
1116: byte_swap_cgout(cgp,fs);
1117: #endif /* REV_ENDIAN_FS */
1118: bdwrite(bp);
1119: return (cg * fs->fs_fpg + bno);
1120: }
1121:
1122: /*
1123: * Allocate a block in a cylinder group.
1124: *
1125: * This algorithm implements the following policy:
1126: * 1) allocate the requested block.
1127: * 2) allocate a rotationally optimal block in the same cylinder.
1128: * 3) allocate the next available block on the block rotor for the
1129: * specified cylinder group.
1130: * Note that this routine only allocates fs_bsize blocks; these
1131: * blocks may be fragmented by the routine that allocates them.
1132: */
1133: static ufs_daddr_t
1134: ffs_alloccgblk(fs, cgp, bpref)
1135: register struct fs *fs;
1136: register struct cg *cgp;
1137: ufs_daddr_t bpref;
1138: {
1139: ufs_daddr_t bno, blkno;
1140: int cylno, pos, delta;
1141: short *cylbp;
1142: register int i;
1143:
1144: if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) {
1145: bpref = cgp->cg_rotor;
1146: goto norot;
1147: }
1148: bpref = blknum(fs, bpref);
1149: bpref = dtogd(fs, bpref);
1150: /*
1151: * if the requested block is available, use it
1152: */
1153: if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) {
1154: bno = bpref;
1155: goto gotit;
1156: }
1157: if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) {
1158: /*
1159: * Block layout information is not available.
1160: * Leaving bpref unchanged means we take the
1161: * next available free block following the one
1162: * we just allocated. Hopefully this will at
1163: * least hit a track cache on drives of unknown
1164: * geometry (e.g. SCSI).
1165: */
1166: goto norot;
1167: }
1168: /*
1169: * check for a block available on the same cylinder
1170: */
1171: cylno = cbtocylno(fs, bpref);
1172: if (cg_blktot(cgp)[cylno] == 0)
1173: goto norot;
1174: /*
1175: * check the summary information to see if a block is
1176: * available in the requested cylinder starting at the
1177: * requested rotational position and proceeding around.
1178: */
1179: cylbp = cg_blks(fs, cgp, cylno);
1180: pos = cbtorpos(fs, bpref);
1181: for (i = pos; i < fs->fs_nrpos; i++)
1182: if (cylbp[i] > 0)
1183: break;
1184: if (i == fs->fs_nrpos)
1185: for (i = 0; i < pos; i++)
1186: if (cylbp[i] > 0)
1187: break;
1188: if (cylbp[i] > 0) {
1189: /*
1190: * found a rotational position, now find the actual
1191: * block. A panic if none is actually there.
1192: */
1193: pos = cylno % fs->fs_cpc;
1194: bno = (cylno - pos) * fs->fs_spc / NSPB(fs);
1195: if (fs_postbl(fs, pos)[i] == -1) {
1196: printf("pos = %d, i = %d, fs = %s\n",
1197: pos, i, fs->fs_fsmnt);
1198: panic("ffs_alloccgblk: cyl groups corrupted");
1199: }
1200: for (i = fs_postbl(fs, pos)[i];; ) {
1201: if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) {
1202: bno = blkstofrags(fs, (bno + i));
1203: goto gotit;
1204: }
1205: delta = fs_rotbl(fs)[i];
1206: if (delta <= 0 ||
1207: delta + i > fragstoblks(fs, fs->fs_fpg))
1208: break;
1209: i += delta;
1210: }
1211: printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt);
1212: panic("ffs_alloccgblk: can't find blk in cyl");
1213: }
1214: norot:
1215: /*
1216: * no blocks in the requested cylinder, so take next
1217: * available one in this cylinder group.
1218: */
1219: bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag);
1220: if (bno < 0)
1221: return (NULL);
1222: cgp->cg_rotor = bno;
1223: gotit:
1224: blkno = fragstoblks(fs, bno);
1225: ffs_clrblock(fs, cg_blksfree(cgp), (long)blkno);
1226: ffs_clusteracct(fs, cgp, blkno, -1);
1227: cgp->cg_cs.cs_nbfree--;
1228: fs->fs_cstotal.cs_nbfree--;
1229: fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--;
1230: cylno = cbtocylno(fs, bno);
1231: cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--;
1232: cg_blktot(cgp)[cylno]--;
1233: fs->fs_fmod = 1;
1234: return (cgp->cg_cgx * fs->fs_fpg + bno);
1235: }
1236:
1237: /*
1238: * Determine whether a cluster can be allocated.
1239: *
1240: * We do not currently check for optimal rotational layout if there
1241: * are multiple choices in the same cylinder group. Instead we just
1242: * take the first one that we find following bpref.
1243: */
1244: static ufs_daddr_t
1245: ffs_clusteralloc(ip, cg, bpref, len)
1246: struct inode *ip;
1247: int cg;
1248: ufs_daddr_t bpref;
1249: int len;
1250: {
1251: register struct fs *fs;
1252: register struct cg *cgp;
1253: struct buf *bp;
1254: int i, got, run, bno, bit, map;
1255: u_char *mapp;
1256: int32_t *lp;
1257: #if REV_ENDIAN_FS
1258: struct vnode *vp=ITOV(ip);
1259: struct mount *mp=vp->v_mount;
1260: int rev_endian=(mp->mnt_flag & MNT_REVEND);
1261: #endif /* REV_ENDIAN_FS */
1262:
1263: fs = ip->i_fs;
1264: if (fs->fs_maxcluster[cg] < len)
1265: return (NULL);
1266: if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize,
1267: NOCRED, &bp))
1268: goto fail;
1269: cgp = (struct cg *)bp->b_data;
1270: #if REV_ENDIAN_FS
1271: if (rev_endian)
1272: byte_swap_cgin(cgp,fs);
1273: #endif /* REV_ENDIAN_FS */
1274: if (!cg_chkmagic(cgp)) {
1275: #if REV_ENDIAN_FS
1276: if (rev_endian)
1277: byte_swap_cgout(cgp,fs);
1278: #endif /* REV_ENDIAN_FS */
1279: goto fail;
1280: }
1281: /*
1282: * Check to see if a cluster of the needed size (or bigger) is
1283: * available in this cylinder group.
1284: */
1285: lp = &cg_clustersum(cgp)[len];
1286: for (i = len; i <= fs->fs_contigsumsize; i++)
1287: if (*lp++ > 0)
1288: break;
1289: if (i > fs->fs_contigsumsize) {
1290: /*
1291: * This is the first time looking for a cluster in this
1292: * cylinder group. Update the cluster summary information
1293: * to reflect the true maximum sized cluster so that
1294: * future cluster allocation requests can avoid reading
1295: * the cylinder group map only to find no clusters.
1296: */
1297: lp = &cg_clustersum(cgp)[len - 1];
1298: for (i = len - 1; i > 0; i--)
1299: if (*lp-- > 0)
1300: break;
1301: fs->fs_maxcluster[cg] = i;
1302: #if REV_ENDIAN_FS
1303: if (rev_endian)
1304: byte_swap_cgout(cgp,fs);
1305: #endif /* REV_ENDIAN_FS */
1306: goto fail;
1307: }
1308: /*
1309: * Search the cluster map to find a big enough cluster.
1310: * We take the first one that we find, even if it is larger
1311: * than we need as we prefer to get one close to the previous
1312: * block allocation. We do not search before the current
1313: * preference point as we do not want to allocate a block
1314: * that is allocated before the previous one (as we will
1315: * then have to wait for another pass of the elevator
1316: * algorithm before it will be read). We prefer to fail and
1317: * be recalled to try an allocation in the next cylinder group.
1318: */
1319: if (dtog(fs, bpref) != cg)
1320: bpref = 0;
1321: else
1322: bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref)));
1323: mapp = &cg_clustersfree(cgp)[bpref / NBBY];
1324: map = *mapp++;
1325: bit = 1 << (bpref % NBBY);
1326: for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) {
1327: if ((map & bit) == 0) {
1328: run = 0;
1329: } else {
1330: run++;
1331: if (run == len)
1332: break;
1333: }
1334: if ((got & (NBBY - 1)) != (NBBY - 1)) {
1335: bit <<= 1;
1336: } else {
1337: map = *mapp++;
1338: bit = 1;
1339: }
1340: }
1341: if (got == cgp->cg_nclusterblks) {
1342: #if REV_ENDIAN_FS
1343: if (rev_endian)
1344: byte_swap_cgout(cgp,fs);
1345: #endif /* REV_ENDIAN_FS */
1346: goto fail;
1347: }
1348: /*
1349: * Allocate the cluster that we have found.
1350: */
1351: for (i = 1; i <= len; i++)
1352: if (!ffs_isblock(fs, cg_blksfree(cgp), got - run + i))
1353: panic("ffs_clusteralloc: map mismatch");
1354: bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1);
1355: if (dtog(fs, bno) != cg)
1356: panic("ffs_clusteralloc: allocated out of group");
1357: len = blkstofrags(fs, len);
1358: for (i = 0; i < len; i += fs->fs_frag)
1359: if ((got = ffs_alloccgblk(fs, cgp, bno + i)) != bno + i)
1360: panic("ffs_clusteralloc: lost block");
1361: #if REV_ENDIAN_FS
1362: if (rev_endian)
1363: byte_swap_cgout(cgp,fs);
1364: #endif /* REV_ENDIAN_FS */
1365: bdwrite(bp);
1366: return (bno);
1367:
1368: fail:
1369: brelse(bp);
1370: return (0);
1371: }
1372:
1373: /*
1374: * Determine whether an inode can be allocated.
1375: *
1376: * Check to see if an inode is available, and if it is,
1377: * allocate it using the following policy:
1378: * 1) allocate the requested inode.
1379: * 2) allocate the next available inode after the requested
1380: * inode in the specified cylinder group.
1381: */
1382: static ino_t
1383: ffs_nodealloccg(ip, cg, ipref, mode)
1384: struct inode *ip;
1385: int cg;
1386: ufs_daddr_t ipref;
1387: int mode;
1388: {
1389: register struct fs *fs;
1390: register struct cg *cgp;
1391: struct buf *bp;
1392: int error, start, len, loc, map, i;
1393: #if REV_ENDIAN_FS
1394: struct vnode *vp=ITOV(ip);
1395: struct mount *mp=vp->v_mount;
1396: int rev_endian=(mp->mnt_flag & MNT_REVEND);
1397: #endif /* REV_ENDIAN_FS */
1398:
1399: fs = ip->i_fs;
1400: if (fs->fs_cs(fs, cg).cs_nifree == 0)
1401: return (NULL);
1402: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
1403: (int)fs->fs_cgsize, NOCRED, &bp);
1404: if (error) {
1405: brelse(bp);
1406: return (NULL);
1407: }
1408: cgp = (struct cg *)bp->b_data;
1409: #if REV_ENDIAN_FS
1410: if (rev_endian)
1411: byte_swap_cgin(cgp,fs);
1412: #endif /* REV_ENDIAN_FS */
1413: if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) {
1414: #if REV_ENDIAN_FS
1415: if (rev_endian)
1416: byte_swap_cgout(cgp,fs);
1417: #endif /* REV_ENDIAN_FS */
1418: brelse(bp);
1419: return (NULL);
1420: }
1421:
1422: cgp->cg_time = time.tv_sec;
1423: if (ipref) {
1424: ipref %= fs->fs_ipg;
1425: if (isclr(cg_inosused(cgp), ipref))
1426: goto gotit;
1427: }
1428: start = cgp->cg_irotor / NBBY;
1429: len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY);
1430: loc = skpc(0xff, len, &cg_inosused(cgp)[start]);
1431: if (loc == 0) {
1432: len = start + 1;
1433: start = 0;
1434: loc = skpc(0xff, len, &cg_inosused(cgp)[0]);
1435: if (loc == 0) {
1436: printf("cg = %d, irotor = %d, fs = %s\n",
1437: cg, cgp->cg_irotor, fs->fs_fsmnt);
1438: panic("ffs_nodealloccg: map corrupted");
1439: /* NOTREACHED */
1440: }
1441: }
1442: i = start + len - loc;
1443: map = cg_inosused(cgp)[i];
1444: ipref = i * NBBY;
1445: for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) {
1446: if ((map & i) == 0) {
1447: cgp->cg_irotor = ipref;
1448: goto gotit;
1449: }
1450: }
1451: printf("fs = %s\n", fs->fs_fsmnt);
1452: panic("ffs_nodealloccg: block not in map");
1453: /* NOTREACHED */
1454: gotit:
1455: setbit(cg_inosused(cgp), ipref);
1456: cgp->cg_cs.cs_nifree--;
1457: fs->fs_cstotal.cs_nifree--;
1458: fs->fs_cs(fs, cg).cs_nifree--;
1459: fs->fs_fmod = 1;
1460: if ((mode & IFMT) == IFDIR) {
1461: cgp->cg_cs.cs_ndir++;
1462: fs->fs_cstotal.cs_ndir++;
1463: fs->fs_cs(fs, cg).cs_ndir++;
1464: }
1465: #if REV_ENDIAN_FS
1466: if (rev_endian)
1467: byte_swap_cgout(cgp,fs);
1468: #endif /* REV_ENDIAN_FS */
1469: bdwrite(bp);
1470: return (cg * fs->fs_ipg + ipref);
1471: }
1472:
1473: /*
1474: * Free a block or fragment.
1475: *
1476: * The specified block or fragment is placed back in the
1477: * free map. If a fragment is deallocated, a possible
1478: * block reassembly is checked.
1479: */
1480: ffs_blkfree(ip, bno, size)
1481: register struct inode *ip;
1482: ufs_daddr_t bno;
1483: long size;
1484: {
1485: register struct fs *fs;
1486: register struct cg *cgp;
1487: struct buf *bp;
1488: ufs_daddr_t blkno;
1489: int i, error, cg, blk, frags, bbase;
1490: #if REV_ENDIAN_FS
1491: struct vnode *vp=ITOV(ip);
1492: struct mount *mp=vp->v_mount;
1493: int rev_endian=(mp->mnt_flag & MNT_REVEND);
1494: #endif /* REV_ENDIAN_FS */
1495: fs = ip->i_fs;
1496: if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) {
1497: printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n",
1498: ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt);
1499: panic("blkfree: bad size");
1500: }
1501: cg = dtog(fs, bno);
1502: if ((u_int)bno >= fs->fs_size) {
1503: printf("bad block %d, ino %d\n", bno, ip->i_number);
1504: ffs_fserr(fs, ip->i_uid, "bad block");
1505: return;
1506: }
1507: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
1508: (int)fs->fs_cgsize, NOCRED, &bp);
1509: if (error) {
1510: brelse(bp);
1511: return;
1512: }
1513: cgp = (struct cg *)bp->b_data;
1514: #if REV_ENDIAN_FS
1515: if (rev_endian)
1516: byte_swap_cgin(cgp,fs);
1517: #endif /* REV_ENDIAN_FS */
1518: if (!cg_chkmagic(cgp)) {
1519: #if REV_ENDIAN_FS
1520: if (rev_endian)
1521: byte_swap_cgout(cgp,fs);
1522: #endif /* REV_ENDIAN_FS */
1523: brelse(bp);
1524: return;
1525: }
1526: cgp->cg_time = time.tv_sec;
1527: bno = dtogd(fs, bno);
1528: if (size == fs->fs_bsize) {
1529: blkno = fragstoblks(fs, bno);
1530: if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) {
1531: printf("dev = 0x%x, block = %d, fs = %s\n",
1532: ip->i_dev, bno, fs->fs_fsmnt);
1533: panic("blkfree: freeing free block");
1534: }
1535: ffs_setblock(fs, cg_blksfree(cgp), blkno);
1536: ffs_clusteracct(fs, cgp, blkno, 1);
1537: cgp->cg_cs.cs_nbfree++;
1538: fs->fs_cstotal.cs_nbfree++;
1539: fs->fs_cs(fs, cg).cs_nbfree++;
1540: i = cbtocylno(fs, bno);
1541: cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++;
1542: cg_blktot(cgp)[i]++;
1543: } else {
1544: bbase = bno - fragnum(fs, bno);
1545: /*
1546: * decrement the counts associated with the old frags
1547: */
1548: blk = blkmap(fs, cg_blksfree(cgp), bbase);
1549: ffs_fragacct(fs, blk, cgp->cg_frsum, -1);
1550: /*
1551: * deallocate the fragment
1552: */
1553: frags = numfrags(fs, size);
1554: for (i = 0; i < frags; i++) {
1555: if (isset(cg_blksfree(cgp), bno + i)) {
1556: printf("dev = 0x%x, block = %d, fs = %s\n",
1557: ip->i_dev, bno + i, fs->fs_fsmnt);
1558: panic("blkfree: freeing free frag");
1559: }
1560: setbit(cg_blksfree(cgp), bno + i);
1561: }
1562: cgp->cg_cs.cs_nffree += i;
1563: fs->fs_cstotal.cs_nffree += i;
1564: fs->fs_cs(fs, cg).cs_nffree += i;
1565: /*
1566: * add back in counts associated with the new frags
1567: */
1568: blk = blkmap(fs, cg_blksfree(cgp), bbase);
1569: ffs_fragacct(fs, blk, cgp->cg_frsum, 1);
1570: /*
1571: * if a complete block has been reassembled, account for it
1572: */
1573: blkno = fragstoblks(fs, bbase);
1574: if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) {
1575: cgp->cg_cs.cs_nffree -= fs->fs_frag;
1576: fs->fs_cstotal.cs_nffree -= fs->fs_frag;
1577: fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
1578: ffs_clusteracct(fs, cgp, blkno, 1);
1579: cgp->cg_cs.cs_nbfree++;
1580: fs->fs_cstotal.cs_nbfree++;
1581: fs->fs_cs(fs, cg).cs_nbfree++;
1582: i = cbtocylno(fs, bbase);
1583: cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++;
1584: cg_blktot(cgp)[i]++;
1585: }
1586: }
1587: fs->fs_fmod = 1;
1588: #if REV_ENDIAN_FS
1589: if (rev_endian)
1590: byte_swap_cgout(cgp,fs);
1591: #endif /* REV_ENDIAN_FS */
1592: bdwrite(bp);
1593: }
1594:
1595: #if DIAGNOSTIC
1596: /*
1597: * Verify allocation of a block or fragment. Returns true if block or
1598: * fragment is allocated, false if it is free.
1599: */
1600: ffs_checkblk(ip, bno, size)
1601: struct inode *ip;
1602: ufs_daddr_t bno;
1603: long size;
1604: {
1605: struct fs *fs;
1606: struct cg *cgp;
1607: struct buf *bp;
1608: int i, error, frags, free;
1609: #if REV_ENDIAN_FS
1610: struct vnode *vp=ITOV(ip);
1611: struct mount *mp=vp->v_mount;
1612: int rev_endian=(mp->mnt_flag & MNT_REVEND);
1613: #endif /* REV_ENDIAN_FS */
1614:
1615: fs = ip->i_fs;
1616: if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) {
1617: printf("bsize = %d, size = %d, fs = %s\n",
1618: fs->fs_bsize, size, fs->fs_fsmnt);
1619: panic("checkblk: bad size");
1620: }
1621: if ((u_int)bno >= fs->fs_size)
1622: panic("checkblk: bad block %d", bno);
1623: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))),
1624: (int)fs->fs_cgsize, NOCRED, &bp);
1625: if (error) {
1626: brelse(bp);
1627: return;
1628: }
1629: cgp = (struct cg *)bp->b_data;
1630: #if REV_ENDIAN_FS
1631: if (rev_endian)
1632: byte_swap_cgin(cgp,fs);
1633: #endif /* REV_ENDIAN_FS */
1634: if (!cg_chkmagic(cgp)) {
1635: #if REV_ENDIAN_FS
1636: if (rev_endian)
1637: byte_swap_cgout(cgp,fs);
1638: #endif /* REV_ENDIAN_FS */
1639: brelse(bp);
1640: return;
1641: }
1642: bno = dtogd(fs, bno);
1643: if (size == fs->fs_bsize) {
1644: free = ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno));
1645: } else {
1646: frags = numfrags(fs, size);
1647: for (free = 0, i = 0; i < frags; i++)
1648: if (isset(cg_blksfree(cgp), bno + i))
1649: free++;
1650: if (free != 0 && free != frags)
1651: panic("checkblk: partially free fragment");
1652: }
1653: #if REV_ENDIAN_FS
1654: if (rev_endian)
1655: byte_swap_cgout(cgp,fs);
1656: #endif /* REV_ENDIAN_FS */
1657: brelse(bp);
1658: return (!free);
1659: }
1660: #endif /* DIAGNOSTIC */
1661:
1662: /*
1663: * Free an inode.
1664: *
1665: * The specified inode is placed back in the free map.
1666: */
1667: int
1668: ffs_vfree(ap)
1669: struct vop_vfree_args /* {
1670: struct vnode *a_pvp;
1671: ino_t a_ino;
1672: int a_mode;
1673: } */ *ap;
1674: {
1675: register struct fs *fs;
1676: register struct cg *cgp;
1677: register struct inode *pip;
1678: ino_t ino = ap->a_ino;
1679: struct buf *bp;
1680: int error, cg;
1681: #if REV_ENDIAN_FS
1682: struct vnode *vp=ap->a_pvp;
1683: struct mount *mp=vp->v_mount;
1684: int rev_endian=(mp->mnt_flag & MNT_REVEND);
1685: #endif /* REV_ENDIAN_FS */
1686:
1687: pip = VTOI(ap->a_pvp);
1688: fs = pip->i_fs;
1689: if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg)
1690: panic("ifree: range: dev = 0x%x, ino = %d, fs = %s\n",
1691: pip->i_dev, ino, fs->fs_fsmnt);
1692: cg = ino_to_cg(fs, ino);
1693: error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
1694: (int)fs->fs_cgsize, NOCRED, &bp);
1695: if (error) {
1696: brelse(bp);
1697: return (0);
1698: }
1699: cgp = (struct cg *)bp->b_data;
1700: #if REV_ENDIAN_FS
1701: if (rev_endian)
1702: byte_swap_cgin(cgp,fs);
1703: #endif /* REV_ENDIAN_FS */
1704: if (!cg_chkmagic(cgp)) {
1705: #if REV_ENDIAN_FS
1706: if (rev_endian)
1707: byte_swap_cgout(cgp,fs);
1708: #endif /* REV_ENDIAN_FS */
1709: brelse(bp);
1710: return (0);
1711: }
1712: cgp->cg_time = time.tv_sec;
1713: ino %= fs->fs_ipg;
1714: if (isclr(cg_inosused(cgp), ino)) {
1715: printf("dev = 0x%x, ino = %d, fs = %s\n",
1716: pip->i_dev, ino, fs->fs_fsmnt);
1717: if (fs->fs_ronly == 0)
1718: panic("ifree: freeing free inode");
1719: }
1720: clrbit(cg_inosused(cgp), ino);
1721: if (ino < cgp->cg_irotor)
1722: cgp->cg_irotor = ino;
1723: cgp->cg_cs.cs_nifree++;
1724: fs->fs_cstotal.cs_nifree++;
1725: fs->fs_cs(fs, cg).cs_nifree++;
1726: if ((ap->a_mode & IFMT) == IFDIR) {
1727: cgp->cg_cs.cs_ndir--;
1728: fs->fs_cstotal.cs_ndir--;
1729: fs->fs_cs(fs, cg).cs_ndir--;
1730: }
1731: fs->fs_fmod = 1;
1732: #if REV_ENDIAN_FS
1733: if (rev_endian)
1734: byte_swap_cgout(cgp,fs);
1735: #endif /* REV_ENDIAN_FS */
1736: bdwrite(bp);
1737: return (0);
1738: }
1739:
1740: /*
1741: * Find a block of the specified size in the specified cylinder group.
1742: *
1743: * It is a panic if a request is made to find a block if none are
1744: * available.
1745: */
1746: static ufs_daddr_t
1747: ffs_mapsearch(fs, cgp, bpref, allocsiz)
1748: register struct fs *fs;
1749: register struct cg *cgp;
1750: ufs_daddr_t bpref;
1751: int allocsiz;
1752: {
1753: ufs_daddr_t bno;
1754: int start, len, loc, i;
1755: int blk, field, subfield, pos;
1756:
1757: /*
1758: * find the fragment by searching through the free block
1759: * map for an appropriate bit pattern
1760: */
1761: if (bpref)
1762: start = dtogd(fs, bpref) / NBBY;
1763: else
1764: start = cgp->cg_frotor / NBBY;
1765: len = howmany(fs->fs_fpg, NBBY) - start;
1766: loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[start],
1767: (u_char *)fragtbl[fs->fs_frag],
1768: (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
1769: if (loc == 0) {
1770: len = start + 1;
1771: start = 0;
1772: loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[0],
1773: (u_char *)fragtbl[fs->fs_frag],
1774: (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
1775: if (loc == 0) {
1776: printf("start = %d, len = %d, fs = %s\n",
1777: start, len, fs->fs_fsmnt);
1778: panic("ffs_alloccg: map corrupted");
1779: /* NOTREACHED */
1780: }
1781: }
1782: bno = (start + len - loc) * NBBY;
1783: cgp->cg_frotor = bno;
1784: /*
1785: * found the byte in the map
1786: * sift through the bits to find the selected frag
1787: */
1788: for (i = bno + NBBY; bno < i; bno += fs->fs_frag) {
1789: blk = blkmap(fs, cg_blksfree(cgp), bno);
1790: blk <<= 1;
1791: field = around[allocsiz];
1792: subfield = inside[allocsiz];
1793: for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) {
1794: if ((blk & field) == subfield)
1795: return (bno + pos);
1796: field <<= 1;
1797: subfield <<= 1;
1798: }
1799: }
1800: printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt);
1801: panic("ffs_alloccg: block not in map");
1802: return (-1);
1803: }
1804:
1805: /*
1806: * Update the cluster map because of an allocation or free.
1807: *
1808: * Cnt == 1 means free; cnt == -1 means allocating.
1809: */
1810: ffs_clusteracct(fs, cgp, blkno, cnt)
1811: struct fs *fs;
1812: struct cg *cgp;
1813: ufs_daddr_t blkno;
1814: int cnt;
1815: {
1816: int32_t *sump;
1817: int32_t *lp;
1818: u_char *freemapp, *mapp;
1819: int i, start, end, forw, back, map, bit;
1820:
1821: if (fs->fs_contigsumsize <= 0)
1822: return;
1823: freemapp = cg_clustersfree(cgp);
1824: sump = cg_clustersum(cgp);
1825: /*
1826: * Allocate or clear the actual block.
1827: */
1828: if (cnt > 0)
1829: setbit(freemapp, blkno);
1830: else
1831: clrbit(freemapp, blkno);
1832: /*
1833: * Find the size of the cluster going forward.
1834: */
1835: start = blkno + 1;
1836: end = start + fs->fs_contigsumsize;
1837: if (end >= cgp->cg_nclusterblks)
1838: end = cgp->cg_nclusterblks;
1839: mapp = &freemapp[start / NBBY];
1840: map = *mapp++;
1841: bit = 1 << (start % NBBY);
1842: for (i = start; i < end; i++) {
1843: if ((map & bit) == 0)
1844: break;
1845: if ((i & (NBBY - 1)) != (NBBY - 1)) {
1846: bit <<= 1;
1847: } else {
1848: map = *mapp++;
1849: bit = 1;
1850: }
1851: }
1852: forw = i - start;
1853: /*
1854: * Find the size of the cluster going backward.
1855: */
1856: start = blkno - 1;
1857: end = start - fs->fs_contigsumsize;
1858: if (end < 0)
1859: end = -1;
1860: mapp = &freemapp[start / NBBY];
1861: map = *mapp--;
1862: bit = 1 << (start % NBBY);
1863: for (i = start; i > end; i--) {
1864: if ((map & bit) == 0)
1865: break;
1866: if ((i & (NBBY - 1)) != 0) {
1867: bit >>= 1;
1868: } else {
1869: map = *mapp--;
1870: bit = 1 << (NBBY - 1);
1871: }
1872: }
1873: back = start - i;
1874: /*
1875: * Account for old cluster and the possibly new forward and
1876: * back clusters.
1877: */
1878: i = back + forw + 1;
1879: if (i > fs->fs_contigsumsize)
1880: i = fs->fs_contigsumsize;
1881: sump[i] += cnt;
1882: if (back > 0)
1883: sump[back] -= cnt;
1884: if (forw > 0)
1885: sump[forw] -= cnt;
1886: /*
1887: * Update cluster summary information.
1888: */
1889: lp = &sump[fs->fs_contigsumsize];
1890: for (i = fs->fs_contigsumsize; i > 0; i--)
1891: if (*lp-- > 0)
1892: break;
1893: fs->fs_maxcluster[cgp->cg_cgx] = i;
1894: }
1895:
1896: /*
1897: * Fserr prints the name of a file system with an error diagnostic.
1898: *
1899: * The form of the error message is:
1900: * fs: error message
1901: */
1902: static void
1903: ffs_fserr(fs, uid, cp)
1904: struct fs *fs;
1905: u_int uid;
1906: char *cp;
1907: {
1908:
1909: log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp);
1910: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.