Return to alloc.c CVS log

Up to [Research Unix] / researchv10no / sys / fs

Annotation of researchv10no/sys/fs/alloc.c, revision 1.1

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.