Return to block.c CVS log

Up to [Qemu by Fabrice Bellard] / qemu / roms / openbios / fs / hfs

Annotation of qemu/roms/openbios/fs/hfs/block.c, revision 1.1

1.1     ! root        1: /*
        !             2: * libhfs - library for reading and writing Macintosh HFS volumes
        !             3: * Copyright (C) 1996-1998 Robert Leslie
        !             4: *
        !             5: * This program is free software; you can redistribute it and/or modify
        !             6: * it under the terms of the GNU General Public License as published by
        !             7: * the Free Software Foundation; either version 2 of the License, or
        !             8: * (at your option) any later version.
        !             9: *
        !            10: * This program is distributed in the hope that it will be useful,
        !            11: * but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            12: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            13: * GNU General Public License for more details.
        !            14: *
        !            15: * You should have received a copy of the GNU General Public License
        !            16: * along with this program; if not, write to the Free Software
        !            17: * Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
        !            18: * MA 02110-1301, USA.
        !            19: *
        !            20: * $Id: block.c,v 1.11 1998/11/02 22:08:52 rob Exp $
        !            21: */
        !            22: 
        !            23: #include "config.h"
        !            24: 
        !            25: #include "libhfs.h"
        !            26: #include "volume.h"
        !            27: #include "block.h"
        !            28: #include "os.h"
        !            29: 
        !            30: #define INUSE(b)       ((b)->flags & HFS_BUCKET_INUSE)
        !            31: #define DIRTY(b)       ((b)->flags & HFS_BUCKET_DIRTY)
        !            32: 
        !            33: /*
        !            34:  * NAME:       block->init()
        !            35:  * DESCRIPTION:        initialize a volume's block cache
        !            36:  */
        !            37: int b_init(hfsvol *vol)
        !            38: {
        !            39:   bcache *cache;
        !            40:   int i;
        !            41: 
        !            42:   ASSERT(vol->cache == 0);
        !            43: 
        !            44:   cache = ALLOC(bcache, 1);
        !            45:   if (cache == NULL)
        !            46:     ERROR(ENOMEM, NULL);
        !            47: 
        !            48:   vol->cache = cache;
        !            49: 
        !            50:   cache->vol    = vol;
        !            51:   cache->tail   = &cache->chain[HFS_CACHESZ - 1];
        !            52: 
        !            53:   cache->hits   = 0;
        !            54:   cache->misses = 0;
        !            55: 
        !            56:   for (i = 0; i < HFS_CACHESZ; ++i)
        !            57:     {
        !            58:       bucket *b = &cache->chain[i];
        !            59: 
        !            60:       b->flags = 0;
        !            61:       b->count = 0;
        !            62: 
        !            63:       b->bnum  = 0;
        !            64:       b->data  = &cache->pool[i];
        !            65: 
        !            66:       b->cnext = b + 1;
        !            67:       b->cprev = b - 1;
        !            68: 
        !            69:       b->hnext = NULL;
        !            70:       b->hprev = NULL;
        !            71:     }
        !            72: 
        !            73:   cache->chain[0].cprev = cache->tail;
        !            74:   cache->tail->cnext    = &cache->chain[0];
        !            75: 
        !            76:   for (i = 0; i < HFS_HASHSZ; ++i)
        !            77:     cache->hash[i] = NULL;
        !            78: 
        !            79:   return 0;
        !            80: 
        !            81: fail:
        !            82:   return -1;
        !            83: }
        !            84: 
        !            85: # ifdef DEBUG
        !            86: /*
        !            87:  * NAME:       block->showstats()
        !            88:  * DESCRIPTION:        output cache hit/miss ratio
        !            89:  */
        !            90: void b_showstats(const bcache *cache)
        !            91: {
        !            92:   fprintf(stderr, "BLOCK: CACHE vol 0x%lx \"%s\" hit/miss ratio = %.3f\n",
        !            93:          (unsigned long) cache->vol, cache->vol->mdb.drVN,
        !            94:          (float) cache->hits / (float) cache->misses);
        !            95: }
        !            96: 
        !            97: /*
        !            98:  * NAME:       block->dumpcache()
        !            99:  * DESCRIPTION:        dump the cache tables for a volume
        !           100:  */
        !           101: void b_dumpcache(const bcache *cache)
        !           102: {
        !           103:   const bucket *b;
        !           104:   int i;
        !           105: 
        !           106:   fprintf(stderr, "BLOCK CACHE DUMP:\n");
        !           107: 
        !           108:   for (i = 0, b = cache->tail->cnext; i < HFS_CACHESZ; ++i, b = b->cnext)
        !           109:     {
        !           110:       if (INUSE(b))
        !           111:        {
        !           112:          fprintf(stderr, "\t %lu", b->bnum);
        !           113:          if (DIRTY(b))
        !           114:            fprintf(stderr, "*");
        !           115: 
        !           116:          fprintf(stderr, ":%u", b->count);
        !           117:        }
        !           118:     }
        !           119: 
        !           120:   fprintf(stderr, "\n");
        !           121: 
        !           122:   fprintf(stderr, "BLOCK HASH DUMP:\n");
        !           123: 
        !           124:   for (i = 0; i < HFS_HASHSZ; ++i)
        !           125:     {
        !           126:       int seen = 0;
        !           127: 
        !           128:       for (b = cache->hash[i]; b; b = b->hnext)
        !           129:        {
        !           130:          if (! seen)
        !           131:            fprintf(stderr, "  %d:", i);
        !           132: 
        !           133:          if (INUSE(b))
        !           134:            {
        !           135:              fprintf(stderr, " %lu", b->bnum);
        !           136:              if (DIRTY(b))
        !           137:                fprintf(stderr, "*");
        !           138: 
        !           139:              fprintf(stderr, ":%u", b->count);
        !           140:            }
        !           141: 
        !           142:          seen = 1;
        !           143:        }
        !           144: 
        !           145:       if (seen)
        !           146:        fprintf(stderr, "\n");
        !           147:     }
        !           148: }
        !           149: # endif
        !           150: 
        !           151: /*
        !           152:  * NAME:       fillchain()
        !           153:  * DESCRIPTION:        fill a chain of bucket buffers with a single read
        !           154:  */
        !           155: static
        !           156: int fillchain(hfsvol *vol, bucket **bptr, unsigned int *count)
        !           157: {
        !           158:   bucket *blist[HFS_BLOCKBUFSZ], **start = bptr;
        !           159:   unsigned long bnum=-2;       // XXX
        !           160:   unsigned int len, i;
        !           161: 
        !           162:   for (len = 0; len < HFS_BLOCKBUFSZ &&
        !           163:         (unsigned int) (bptr - start) < *count; ++bptr)
        !           164:     {
        !           165:       if (INUSE(*bptr))
        !           166:        continue;
        !           167: 
        !           168:       if (len > 0 && (*bptr)->bnum != bnum)
        !           169:        break;
        !           170: 
        !           171:       blist[len++] = *bptr;
        !           172:       bnum = (*bptr)->bnum + 1;
        !           173:     }
        !           174: 
        !           175:   *count = bptr - start;
        !           176: 
        !           177:   if (len == 0)
        !           178:     goto done;
        !           179:   else if (len == 1)
        !           180:     {
        !           181:       if (b_readpb(vol, vol->vstart + blist[0]->bnum,
        !           182:                   blist[0]->data, 1) == -1)
        !           183:        goto fail;
        !           184:     }
        !           185:   else
        !           186:     {
        !           187:       block buffer[HFS_BLOCKBUFSZ];
        !           188: 
        !           189:       if (b_readpb(vol, vol->vstart + blist[0]->bnum, buffer, len) == -1)
        !           190:        goto fail;
        !           191: 
        !           192:       for (i = 0; i < len; ++i)
        !           193:        memcpy(blist[i]->data, buffer[i], HFS_BLOCKSZ);
        !           194:     }
        !           195: 
        !           196:   for (i = 0; i < len; ++i)
        !           197:     {
        !           198:       blist[i]->flags |=  HFS_BUCKET_INUSE;
        !           199:       blist[i]->flags &= ~HFS_BUCKET_DIRTY;
        !           200:     }
        !           201: 
        !           202: done:
        !           203:   return 0;
        !           204: 
        !           205: fail:
        !           206:   return -1;
        !           207: }
        !           208: 
        !           209: 
        !           210: /*
        !           211:  * NAME:       compare()
        !           212:  * DESCRIPTION:        comparison function for qsort of cache bucket pointers
        !           213:  */
        !           214: static
        !           215: int compare(const bucket **b1, const bucket **b2)
        !           216: {
        !           217:   long diff;
        !           218: 
        !           219:   diff = (*b1)->bnum - (*b2)->bnum;
        !           220: 
        !           221:   if (diff < 0)
        !           222:     return -1;
        !           223:   else if (diff > 0)
        !           224:     return 1;
        !           225:   else
        !           226:     return 0;
        !           227: }
        !           228: 
        !           229: /*
        !           230:  * NAME:       dobuckets()
        !           231:  * DESCRIPTION:        fill or flush an array of cache buckets to a volume
        !           232:  */
        !           233: static
        !           234: int dobuckets(hfsvol *vol, bucket **chain, unsigned int len,
        !           235:              int (*func)(hfsvol *, bucket **, unsigned int *))
        !           236: {
        !           237:   unsigned int count, i;
        !           238:   int result = 0;
        !           239: 
        !           240:   qsort(chain, len, sizeof(*chain),
        !           241:        (int (*)(const void *, const void *)) compare);
        !           242: 
        !           243:   for (i = 0; i < len; i += count)
        !           244:     {
        !           245:       count = len - i;
        !           246:       if (func(vol, chain + i, &count) == -1)
        !           247:        result = -1;
        !           248:     }
        !           249: 
        !           250:   return result;
        !           251: }
        !           252: 
        !           253: # define fillbuckets(vol, chain, len)  dobuckets(vol, chain, len, fillchain)
        !           254: 
        !           255: /*
        !           256:  * NAME:       block->finish()
        !           257:  * DESCRIPTION:        commit and free a volume's block cache
        !           258:  */
        !           259: int b_finish(hfsvol *vol)
        !           260: {
        !           261:   int result = 0;
        !           262: 
        !           263:   if (vol->cache == NULL)
        !           264:     goto done;
        !           265: 
        !           266: # ifdef DEBUG
        !           267:   b_dumpcache(vol->cache);
        !           268: # endif
        !           269: 
        !           270:   FREE(vol->cache);
        !           271:   vol->cache = NULL;
        !           272: 
        !           273: done:
        !           274:   return result;
        !           275: }
        !           276: 
        !           277: /*
        !           278:  * NAME:       findbucket()
        !           279:  * DESCRIPTION:        locate a bucket in the cache, and/or its hash slot
        !           280:  */
        !           281: static
        !           282: bucket *findbucket(bcache *cache, unsigned long bnum, bucket ***hslot)
        !           283: {
        !           284:   bucket *b;
        !           285: 
        !           286:   *hslot = &cache->hash[bnum & (HFS_HASHSZ - 1)];
        !           287: 
        !           288:   for (b = **hslot; b; b = b->hnext)
        !           289:     {
        !           290:       if (INUSE(b) && b->bnum == bnum)
        !           291:        break;
        !           292:     }
        !           293: 
        !           294:   return b;
        !           295: }
        !           296: 
        !           297: /*
        !           298:  * NAME:       reuse()
        !           299:  * DESCRIPTION:        free a bucket for reuse, flushing if necessary
        !           300:  */
        !           301: static
        !           302: int reuse(bcache *cache, bucket *b, unsigned long bnum)
        !           303: {
        !           304:   bucket *bptr;
        !           305:   int i;
        !           306: 
        !           307: # ifdef DEBUG
        !           308:   if (INUSE(b))
        !           309:     fprintf(stderr, "BLOCK: CACHE reusing bucket containing "
        !           310:            "vol 0x%lx block %lu:%u\n",
        !           311:            (unsigned long) cache->vol, b->bnum, b->count);
        !           312: # endif
        !           313: 
        !           314:   if (INUSE(b) && DIRTY(b))
        !           315:     {
        !           316:       /* flush most recently unused buckets */
        !           317: 
        !           318:       for (bptr = b, i = 0; i < HFS_BLOCKBUFSZ; ++i)
        !           319:        {
        !           320:          bptr = bptr->cprev;
        !           321:        }
        !           322:     }
        !           323: 
        !           324:   b->flags &= ~HFS_BUCKET_INUSE;
        !           325:   b->count  = 1;
        !           326:   b->bnum   = bnum;
        !           327: 
        !           328:   return 0;
        !           329: }
        !           330: 
        !           331: /*
        !           332:  * NAME:       cplace()
        !           333:  * DESCRIPTION:        move a bucket to an appropriate place near head of the chain
        !           334:  */
        !           335: static
        !           336: void cplace(bcache *cache, bucket *b)
        !           337: {
        !           338:   bucket *p;
        !           339: 
        !           340:   for (p = cache->tail->cnext; p->count > 1; p = p->cnext)
        !           341:     --p->count;
        !           342: 
        !           343:   b->cnext->cprev = b->cprev;
        !           344:   b->cprev->cnext = b->cnext;
        !           345: 
        !           346:   if (cache->tail == b)
        !           347:     cache->tail = b->cprev;
        !           348: 
        !           349:   b->cprev = p->cprev;
        !           350:   b->cnext = p;
        !           351: 
        !           352:   p->cprev->cnext = b;
        !           353:   p->cprev = b;
        !           354: }
        !           355: 
        !           356: /*
        !           357:  * NAME:       hplace()
        !           358:  * DESCRIPTION:        move a bucket to the head of its hash slot
        !           359:  */
        !           360: static
        !           361: void hplace(bucket **hslot, bucket *b)
        !           362: {
        !           363:   if (*hslot != b)
        !           364:     {
        !           365:       if (b->hprev)
        !           366:        *b->hprev = b->hnext;
        !           367:       if (b->hnext)
        !           368:        b->hnext->hprev = b->hprev;
        !           369: 
        !           370:       b->hprev = hslot;
        !           371:       b->hnext = *hslot;
        !           372: 
        !           373:       if (*hslot)
        !           374:        (*hslot)->hprev = &b->hnext;
        !           375: 
        !           376:       *hslot = b;
        !           377:     }
        !           378: }
        !           379: 
        !           380: /*
        !           381:  * NAME:       getbucket()
        !           382:  * DESCRIPTION:        fetch a bucket from the cache, or an empty one to be filled
        !           383:  */
        !           384: static
        !           385: bucket *getbucket(bcache *cache, unsigned long bnum, int fill)
        !           386: {
        !           387:   bucket **hslot, *b, *p, *bptr,
        !           388:     *chain[HFS_BLOCKBUFSZ], **slots[HFS_BLOCKBUFSZ];
        !           389: 
        !           390:   b = findbucket(cache, bnum, &hslot);
        !           391: 
        !           392:   if (b)
        !           393:     {
        !           394:       /* cache hit; move towards head of cache chain */
        !           395: 
        !           396:       ++cache->hits;
        !           397: 
        !           398:       if (++b->count > b->cprev->count &&
        !           399:          b != cache->tail->cnext)
        !           400:        {
        !           401:          p = b->cprev;
        !           402: 
        !           403:          p->cprev->cnext = b;
        !           404:          b->cnext->cprev = p;
        !           405: 
        !           406:          p->cnext = b->cnext;
        !           407:          b->cprev = p->cprev;
        !           408: 
        !           409:          p->cprev = b;
        !           410:          b->cnext = p;
        !           411: 
        !           412:          if (cache->tail == b)
        !           413:            cache->tail = p;
        !           414:        }
        !           415:     }
        !           416:   else
        !           417:     {
        !           418:       /* cache miss; reuse least-used cache bucket */
        !           419: 
        !           420:       ++cache->misses;
        !           421: 
        !           422:       b = cache->tail;
        !           423: 
        !           424:       if (reuse(cache, b, bnum) == -1)
        !           425:        goto fail;
        !           426: 
        !           427:       if (fill)
        !           428:        {
        !           429:          unsigned int len = 0;
        !           430: 
        !           431:          chain[len]   = b;
        !           432:          slots[len++] = hslot;
        !           433: 
        !           434:          for (bptr = b->cprev;
        !           435:               len < (HFS_BLOCKBUFSZ >> 1) && ++bnum < cache->vol->vlen;
        !           436:               bptr = bptr->cprev)
        !           437:            {
        !           438:              if (findbucket(cache, bnum, &hslot))
        !           439:                break;
        !           440: 
        !           441:              if (reuse(cache, bptr, bnum) == -1)
        !           442:                goto fail;
        !           443: 
        !           444:              chain[len]   = bptr;
        !           445:              slots[len++] = hslot;
        !           446:            }
        !           447: 
        !           448:          if (fillbuckets(cache->vol, chain, len) == -1)
        !           449:            goto fail;
        !           450: 
        !           451:          while (--len)
        !           452:            {
        !           453:              cplace(cache, chain[len]);
        !           454:              hplace(slots[len], chain[len]);
        !           455:            }
        !           456: 
        !           457:          hslot = slots[0];
        !           458:        }
        !           459: 
        !           460:       /* move bucket to appropriate place in chain */
        !           461: 
        !           462:       cplace(cache, b);
        !           463:     }
        !           464: 
        !           465:   /* insert at front of hash chain */
        !           466: 
        !           467:   hplace(hslot, b);
        !           468: 
        !           469:   return b;
        !           470: 
        !           471: fail:
        !           472:   return NULL;
        !           473: }
        !           474: 
        !           475: /*
        !           476:  * NAME:       block->readpb()
        !           477:  * DESCRIPTION:        read blocks from the physical medium (bypassing cache)
        !           478:  */
        !           479: int b_readpb(hfsvol *vol, unsigned long bnum, block *bp, unsigned int blen)
        !           480: {
        !           481:   unsigned long nblocks;
        !           482: 
        !           483: # ifdef DEBUG
        !           484:   fprintf(stderr, "BLOCK: READ vol 0x%lx block %lu",
        !           485:          (unsigned long) vol, bnum);
        !           486:   if (blen > 1)
        !           487:     fprintf(stderr, "+%u[..%lu]\n", blen - 1, bnum + blen - 1);
        !           488:   else
        !           489:     fprintf(stderr, "\n");
        !           490: # endif
        !           491: 
        !           492:   nblocks = os_seek(vol->os_fd, bnum, HFS_BLOCKSZ_BITS );
        !           493:   if (nblocks == (unsigned long) -1)
        !           494:     goto fail;
        !           495: 
        !           496:   if (nblocks != bnum)
        !           497:     ERROR(EIO, "block seek failed for read");
        !           498: 
        !           499:   nblocks = os_read(vol->os_fd, bp, blen, HFS_BLOCKSZ_BITS);
        !           500:   if (nblocks == (unsigned long) -1)
        !           501:     goto fail;
        !           502: 
        !           503:   if (nblocks != blen)
        !           504:     ERROR(EIO, "incomplete block read");
        !           505: 
        !           506:   return 0;
        !           507: 
        !           508: fail:
        !           509:   return -1;
        !           510: }
        !           511: 
        !           512: 
        !           513: /*
        !           514:  * NAME:       block->readlb()
        !           515:  * DESCRIPTION:        read a logical block from a volume (or from the cache)
        !           516:  */
        !           517: int b_readlb(hfsvol *vol, unsigned long bnum, block *bp)
        !           518: {
        !           519:   if (vol->vlen > 0 && bnum >= vol->vlen)
        !           520:     ERROR(EIO, "read nonexistent logical block");
        !           521: 
        !           522:   if (vol->cache)
        !           523:     {
        !           524:       bucket *b;
        !           525: 
        !           526:       b = getbucket(vol->cache, bnum, 1);
        !           527:       if (b == NULL)
        !           528:        goto fail;
        !           529: 
        !           530:       memcpy(bp, b->data, HFS_BLOCKSZ);
        !           531:     }
        !           532:   else
        !           533:     {
        !           534:       if (b_readpb(vol, vol->vstart + bnum, bp, 1) == -1)
        !           535:        goto fail;
        !           536:     }
        !           537: 
        !           538:   return 0;
        !           539: 
        !           540: fail:
        !           541:   return -1;
        !           542: }
        !           543: 
        !           544: /*
        !           545:  * NAME:       block->readab()
        !           546:  * DESCRIPTION:        read a block from an allocation block from a volume
        !           547:  */
        !           548: int b_readab(hfsvol *vol, unsigned int anum, unsigned int index, block *bp)
        !           549: {
        !           550:   /* verify the allocation block exists and is marked as in-use */
        !           551: 
        !           552:   if (anum >= vol->mdb.drNmAlBlks)
        !           553:     ERROR(EIO, "read nonexistent allocation block");
        !           554:   else if (vol->vbm && ! BMTST(vol->vbm, anum))
        !           555:     ERROR(EIO, "read unallocated block");
        !           556: 
        !           557:   return b_readlb(vol, vol->mdb.drAlBlSt + anum * vol->lpa + index, bp);
        !           558: 
        !           559: fail:
        !           560:   return -1;
        !           561: }
        !           562: 
        !           563: 
        !           564: /*
        !           565:  * NAME:       block->size()
        !           566:  * DESCRIPTION:        return the number of physical blocks on a volume's medium
        !           567:  */
        !           568: unsigned long b_size(hfsvol *vol)
        !           569: {
        !           570:   unsigned long low, high, mid;
        !           571:   block b;
        !           572: 
        !           573:   high = os_seek(vol->os_fd, -1, HFS_BLOCKSZ_BITS);
        !           574: 
        !           575:   if (high != (unsigned long) -1 && high > 0)
        !           576:     return high;
        !           577: 
        !           578:   /* manual size detection: first check there is at least 1 block in medium */
        !           579: 
        !           580:   if (b_readpb(vol, 0, &b, 1) == -1)
        !           581:     ERROR(EIO, "size of medium indeterminable or empty");
        !           582: 
        !           583:   for (low = 0, high = 2880;
        !           584:        high > 0 && b_readpb(vol, high - 1, &b, 1) != -1;
        !           585:        high <<= 1)
        !           586:     low = high - 1;
        !           587: 
        !           588:   if (high == 0)
        !           589:     ERROR(EIO, "size of medium indeterminable or too large");
        !           590: 
        !           591:   /* common case: 1440K floppy */
        !           592: 
        !           593:   if (low == 2879 && b_readpb(vol, 2880, &b, 1) == -1)
        !           594:     return 2880;
        !           595: 
        !           596:   /* binary search for other sizes */
        !           597: 
        !           598:   while (low < high - 1)
        !           599:     {
        !           600:       mid = (low + high) >> 1;
        !           601: 
        !           602:       if (b_readpb(vol, mid, &b, 1) == -1)
        !           603:        high = mid;
        !           604:       else
        !           605:        low = mid;
        !           606:     }
        !           607: 
        !           608:   return low + 1;
        !           609: 
        !           610: fail:
        !           611:   return 0;
        !           612: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.