![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / sys / fs|
Return to alloc.c CVS log | Up to [Research Unix] / researchv10no / sys / fs |
1.1 root 1: #include "sys/param.h"
2: #include "sys/systm.h"
3: #include "sys/filsys.h"
4: #include "sys/fblk.h"
5: #include "sys/buf.h"
6: #include "sys/inode.h"
7: #include "sys/ino.h"
8: #include "sys/user.h"
9:
10: typedef struct fblk *FP;
11:
12: /*
13: * alloc will obtain the next available
14: * free disk block from the free list of
15: * the specified filsys.
16: * The super block has up to NICFREE remembered
17: * free blocks; the last of these is read to
18: * obtain NICFREE more . . .
19: */
20: static daddr_t bitfsalloc(), oldfsalloc(), bigfsalloc();
21:
22: struct buf *
23: alloc(fip, prev)
24: struct inode *fip;
25: daddr_t prev;
26: {
27: daddr_t bno;
28: register struct filsys *fp;
29: register struct buf *bp;
30:
31: fp = getfs(fip);
32: while (fp->s_flock)
33: sleep((caddr_t)&fp->s_flock, PINOD);
34: if(BITFS(fip->i_dev)) /* unfortunately device dependent */
35: if(fp->U.N.S_flag)
36: bno = bigfsalloc(fp, prev);
37: else
38: bno = bitfsalloc(fp, prev);
39: else
40: bno = oldfsalloc(fp, fip->i_dev);
41: if (bno == 0) {
42: /*fp->s_nfree = 0; /* but it would be wrong FIX*/
43: fp->s_tfree = 0;
44: fserr(fip->i_dev, fp, "file system full");
45: tsleep((caddr_t)&u, PRIBIO, 5); /* slow things down */
46: u.u_error = ENOSPC;
47: return (NULL);
48: }
49: bp = getblk(fip->i_dev, bno);
50: clrbuf(bp);
51: fp->s_fmod = 1;
52: fp->s_tfree--;
53: return (bp);
54: }
55:
56: /*
57: * bitmap fs alloc:
58: * given the previous block in the file,
59: * try to pick one in the same cylinder,
60: * preferably in a nice rotational place
61: * if we can't, pick one in the next couple of cylinders
62: * if we can't, just pick any block
63: */
64:
65: static daddr_t
66: bitfsalloc(fp, prev)
67: register struct filsys *fp;
68: daddr_t prev;
69: {
70: register daddr_t bno;
71: register long i;
72: daddr_t cyl, end, best;
73:
74: best = -1;
75: if (fp->s_cylsize == 0) { /* safety for the root. ugh. */
76: fp->s_cylsize = 40;
77: fp->s_aspace = 4; /* good for comets */
78: }
79: if (prev >= fp->s_isize) {
80: bno = prev / fp->s_cylsize;
81: bno *= fp->s_cylsize;
82: if (bno < fp->s_isize)
83: bno = fp->s_isize;
84: cyl = bno + fp->s_cylsize;
85: end = bno + 3 * fp->s_cylsize;
86: if (end > fp->s_fsize)
87: end = fp->s_fsize;
88: if (cyl > fp->s_fsize)
89: cyl = fp->s_fsize;
90: i = bno - fp->s_isize;
91: best = findbit(fp->s_bfree, i, cyl-fp->s_isize, prev-fp->s_isize,
92: fp->s_aspace); /* in same cylinder */
93: if(best == -1)
94: best = findbit(fp->s_bfree, cyl-fp->s_isize,
95: end-fp->s_isize, 0L, 0);
96: }
97: if(best == -1)
98: best = findbit(fp->s_bfree, 0L, fp->s_fsize-fp->s_isize, 0L, 0);
99: if(best == -1)
100: return(0);
101: BITALLOC(fp->s_bfree, best);
102: if (fp->s_valid) {
103: fp->s_valid = 0;
104: update(); /* ugh */
105: }
106: return (best+fp->s_isize);
107: }
108:
109: /*
110: * new-style, multi-segment bitmap
111: * take care not to cross segment boundaries
112: */
113:
114: static daddr_t
115: bigfsalloc(fp, prev)
116: register struct filsys *fp;
117: daddr_t prev;
118: {
119: register int fblk;
120: register long bs;
121: register long best, beg, cyl;
122: int nblk;
123:
124: bs = fp->U.N.S_bsize;
125: if(prev > 0) {
126: beg = prev/fp->s_cylsize;
127: beg *= fp->s_cylsize;
128: if(beg < fp->s_isize)
129: beg = fp->s_isize; /* unnecessary */
130: cyl = beg + fp->s_cylsize;
131: if(cyl > fp->s_fsize)
132: cyl = fp->s_fsize;
133: fblk = beg/bs;
134: if (fblk != (cyl-1)/bs)
135: cyl = (fblk+1)*bs; /* bound to this block */
136: best = findbit(fp->U.N.S_blk[fblk]->b_un.b_words, beg%bs,
137: cyl%bs, prev%bs, fp->s_aspace);
138: if (best != -1)
139: goto done;
140: beg = cyl;
141: cyl = beg + 2 * fp->s_cylsize;
142: if (cyl >= fp->s_fsize)
143: cyl = fp->s_fsize;
144: fblk = beg/bs;
145: if (fblk != (cyl - 1)/bs)
146: cyl = (fblk+1)*bs;
147: best = findbit(fp->U.N.S_blk[fblk]->b_un.b_words, beg%bs,
148: cyl%bs, 0L, 0);
149: if(best != -1)
150: goto done;
151: }
152: /*
153: * find any free bit at all
154: */
155: nblk = (fp->s_fsize + bs - 1) / bs;
156: for (fblk = 0; fblk < nblk; fblk++) {
157: best = findbit(fp->U.N.S_blk[fblk]->b_un.b_words, 0L, bs, 0L, 0);
158: if(best != -1)
159: goto done;
160: }
161: /*
162: * found nothing nowhere
163: */
164: return(0);
165: /*
166: * found bit best in block fblk
167: */
168: done:
169: BITALLOC((fp->U.N.S_blk[fblk]->b_un.b_words), best);
170: if(fp->s_valid) {
171: fp->s_valid = 0;
172: update();
173: }
174: return(best+fblk*bs);
175: }
176:
177: /* find a bit between bot and top, preferably at least space from prev */
178: findbit(ptr, bot, top, prev, space)
179: long *ptr;
180: long bot, top, prev;
181: {
182: register long *p;
183: register int j;
184: register long bno, best;
185:
186: best = -1;
187: j = bot/BITCELL;
188: p = ptr + j;
189: bno = j*BITCELL; /* start on long boundary */
190: for(; bno < top; p++) {
191: if(*p == 0) { /* none free in whole long */
192: bno += BITCELL; /* so onward */
193: continue;
194: }
195: for(j = 0; j < BITCELL; j++, bno++) {
196: if((*p & (1<<j)) == 0)
197: continue;
198: if(bno < bot || bno >= top) /* out of the loop? */
199: continue; /* first and last longs */
200: if(best == -1)
201: best = bno;
202: if(bno - prev >= space)
203: return(bno);
204: }
205: }
206: return(best); /* -1 or whatever we found */
207: }
208:
209: static daddr_t
210: oldfsalloc(fp, dev)
211: register struct filsys *fp;
212: {
213: register daddr_t bno;
214: register struct buf *bp;
215:
216: do {
217: if (fp->s_nfree <= 0)
218: return (0);
219: if (fp->s_nfree > NICFREE) {
220: fserr(dev, fp, "bad free count");
221: return (0);
222: }
223: bno = fp->s_free[--fp->s_nfree];
224: if (bno == 0)
225: return (0);
226: } while (badblock(dev, fp, bno));
227: if (fp->s_nfree <= 0) {
228: fp->s_flock++;
229: bp = bread(dev, bno);
230: if ((bp->b_flags&B_ERROR) == 0) {
231: fp->s_nfree = ((FP)(bp->b_un.b_addr))->df_nfree;
232: bcopy((caddr_t)((FP)(bp->b_un.b_addr))->df_free,
233: (caddr_t)fp->s_free, sizeof(fp->s_free));
234: }
235: brelse(bp);
236: fp->s_flock = 0;
237: wakeup((caddr_t)&fp->s_flock);
238: if (fp->s_nfree <= 0)
239: return (0);
240: }
241: return (bno);
242: }
243:
244: /*
245: * place the specified disk block
246: * back on the free list of the
247: * specified device.
248: */
249: free(fip, bno)
250: struct inode *fip;
251: daddr_t bno;
252: { int bs;
253: register struct filsys *fp;
254: register struct buf *bp;
255:
256: fp = getfs(fip);
257: fp->s_fmod = 1;
258: while (fp->s_flock)
259: sleep((caddr_t)&fp->s_flock, PINOD);
260: if (badblock(fip->i_dev, fp, bno))
261: return;
262: if(BITFS(fip->i_dev)) {
263: /* paranoia suggests checking it's not already free */
264: if(fp->U.N.S_flag) {
265: bs = fp->U.N.S_bsize;
266: BITFREE((fp->U.N.S_blk[bno/bs]->b_un.b_words), bno%bs);
267: }
268: else {
269: bno -= fp->s_isize;
270: BITFREE(fp->s_bfree, bno);
271: }
272: if(fp->s_valid) { /* not any more */
273: fp->s_valid = 0;
274: update(); /* even GROSSER */
275: }
276: }
277: else {
278: if (fp->s_nfree <= 0) {
279: fp->s_nfree = 1;
280: fp->s_free[0] = 0;
281: }
282: if (fp->s_nfree >= NICFREE) {
283: fp->s_flock++;
284: bp = getblk(fip->i_dev, bno);
285: ((FP)(bp->b_un.b_addr))->df_nfree = fp->s_nfree;
286: bcopy((caddr_t)fp->s_free,
287: (caddr_t)((FP)(bp->b_un.b_addr))->df_free,
288: sizeof(fp->s_free));
289: fp->s_nfree = 0;
290: bwrite(bp);
291: fp->s_flock = 0;
292: wakeup((caddr_t)&fp->s_flock);
293: }
294: fp->s_free[fp->s_nfree++] = bno;
295: }
296: fp->s_tfree++;
297: fp->s_fmod = 1;
298: }
299:
300: /*
301: * Check that a block number is in the
302: * range between the I list and the size
303: * of the device.
304: * This is used mainly to check that a
305: * garbage file system has not been mounted.
306: */
307: badblock(dev, fp, bn)
308: dev_t dev;
309: register struct filsys *fp;
310: daddr_t bn;
311: {
312:
313: if (bn < fp->s_isize || bn >= fp->s_fsize) {
314: fserr(dev, fp, "bad block");
315: return(1);
316: }
317: return(0);
318: }
319:
320: /*
321: * allocate an unused disk inode in the specified filesystem
322: * up to NICINOD possible i-numbers are kept in a list
323: * in s_inode; try those first. If the list empties,
324: * scan the i-list and fill it again.
325: * To speed things up, pick up the scan where it last
326: * left off (s_lasti) unless there are believed to be
327: * many free i-nodes with lower numbers (s_nbehind).
328: * s_ilock is there only to avoid having two processes
329: * in the list-filling code.
330: */
331:
332: int dupinod; /* debug */
333:
334: struct inode *
335: ialloc(fip)
336: struct inode *fip;
337: {
338: register struct filsys *fp;
339: register struct buf *bp;
340: register struct inode *ip;
341: register int i;
342: struct dinode *dp;
343: ino_t ino;
344: int first;
345: int inopb;
346: daddr_t adr;
347:
348: fp = getfs(fip);
349: if (fp->s_ninode > NICINOD || fp->s_ninode < 0) {
350: fserr(fip->i_dev, fp, "bad inode count");
351: fp->s_ninode = 0;
352: }
353: loop:
354: if (fp->s_ninode > 0) {
355: ino = fp->s_inode[--fp->s_ninode];
356: if (ifind(fip, ino)) { /* already in use */
357: dupinod++; /* debug */
358: goto loop;
359: }
360: ip = iget(fip, fip->i_dev, ino);
361: if (ip == NULL) /* probably table full */
362: return(NULL);
363: if (ip->i_count == 1 && fsiread(fip, ip) < 0)
364: goto loop;
365: if (ip->i_mode != 0) { /* already allocated */
366: iput(ip);
367: goto loop;
368: }
369: for (i=0; i<NADDR; i++)
370: ip->i_un.i_addr[i] = 0;
371: fp->s_tinode--;
372: fp->s_fmod = 1;
373: return(ip);
374: }
375: /*
376: * nothing left in super-block; restock
377: */
378: while (fp->s_ilock)
379: sleep((caddr_t)&fp->s_ilock, PINOD);
380: if (fp->s_ninode > 0) /* someone beat us to it? */
381: goto loop;
382: fp->s_ilock++;
383: first = 1;
384: inopb = INOPB(fip->i_dev); /* optimization */
385: fromtop:
386: ino = fp->s_lasti;
387: ino = ((ino / inopb) * inopb) + 1; /* round down to start of block */
388: adr = itod(fip->i_dev, ino);
389: if (fp->s_nbehind > 4 * NICINOD
390: || adr <= SUPERB || adr >= fp->s_isize
391: || first == 0) {
392: first = 0;
393: ino = 1;
394: adr = SUPERB + 1;
395: fp->s_nbehind = 0;
396: }
397: for(; adr < fp->s_isize; adr++) {
398: bp = bread(fip->i_dev, adr);
399: if (bp->b_flags & B_ERROR) {
400: brelse(bp);
401: ino += inopb;
402: continue;
403: }
404: dp = bp->b_un.b_dino;
405: for (i=0; i<inopb; i++, ino++, dp++) {
406: if (dp->di_mode != 0 || ifind(fip, ino))
407: continue;
408: fp->s_inode[fp->s_ninode++] = ino;
409: if (fp->s_ninode >= NICINOD)
410: break;
411: }
412: brelse(bp);
413: if (fp->s_ninode >= NICINOD)
414: break;
415: }
416: /*
417: * if we found nothing,
418: * try again from the beginning of the i-list
419: */
420: if (fp->s_ninode <= 0 && first) {
421: first = 0;
422: goto fromtop;
423: }
424: if (fp->s_ninode == NICINOD)
425: fp->s_lasti = ino;
426: else { /* hit the end, but found something */
427: fp->s_lasti = 1;
428: fp->s_nbehind = 0;
429: }
430: fp->s_ilock = 0;
431: wakeup((caddr_t)&fp->s_ilock);
432: if (fp->s_ninode > 0)
433: goto loop;
434: fserr(fip->i_dev, fp, "out of inodes");
435: u.u_error = ENOSPC;
436: return (NULL);
437: }
438:
439: /*
440: * Free the specified inode on the specified device.
441: * The algorithm stores up to NICINOD inodes in the super
442: * block and throws away any more. It keeps track of the
443: * number of inodes thrown away which preceded the current
444: * search point in the file system. This lets us rescan
445: * for more inodes from the beginning only when there
446: * are a reasonable number of inodes back there to reallocate.
447: */
448:
449: ifree(ip)
450: register struct inode *ip;
451: {
452: register struct filsys *fp;
453:
454: fp = getfs(ip);
455: if (fp->s_ninode > NICINOD || fp->s_ninode < 0) {
456: fserr(ip->i_dev, fp, "bad inode count");
457: fp->s_ninode = 0;
458: }
459: fp->s_tinode++;
460: if (fp->s_ilock)
461: return;
462: if (fp->s_ninode >= NICINOD) {
463: if (fp->s_lasti > ip->i_number)
464: fp->s_nbehind++;
465: return;
466: }
467: fp->s_inode[fp->s_ninode++] = ip->i_number;
468: fp->s_fmod = 1;
469: }
470:
471: /*
472: * getfs maps an inode into
473: * a pointer to the incore super
474: * block.
475: *
476: * panic: no fs -- the device is not mounted.
477: * this "cannot happen"
478: */
479: struct filsys *
480: getfs(fip)
481: register struct inode *fip;
482: {
483:
484: if (fip->i_fstyp != 0 || fip->i_un.i_bufp == NULL)
485: panic("no fs");
486: return (fip->i_un.i_bufp->b_un.b_filsys);
487: }
488:
489: /*
490: * Fserr prints the name of a file system
491: * with an error diagnostic, in the form
492: * filsys: error message
493: */
494: fserr(dev, fp, cp)
495: dev_t dev;
496: struct filsys *fp;
497: char *cp;
498: {
499:
500: printf("0%o,0%o %s: %s\n", major(dev), minor(dev), fp->s_fsmnt, cp);
501: }
502:
503: /*
504: * Update is the internal name of 'sync'. It goes through the disk
505: * queues to initiate sandbagged IO; goes through the inodes to write
506: * modified nodes; and it goes through the mount table to initiate modified
507: * super blocks.
508: */
509: update()
510: {
511: register struct inode *ip;
512: static int updlock;
513:
514: if (updlock)
515: return;
516: updlock++;
517: /*
518: * Write back each (modified) inode.
519: */
520: for (ip = inode; ip < inodeNINODE; ip++)
521: if((ip->i_flag&ILOCK)==0 && ip->i_count) {
522: ip->i_flag |= ILOCK;
523: ip->i_count++;
524: iupdat(ip, &time, &time, 0);
525: iput(ip);
526: }
527: updlock = 0;
528: /*
529: * Force stale buffer cache information to be flushed,
530: * for all devices.
531: */
532: bflush(NODEV);
533: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.