| /* |
| * libhfs - library for reading and writing Macintosh HFS volumes |
| * Copyright (C) 1996-1998 Robert Leslie |
| * |
| * This program is free software; you can redistribute it and/or modify |
| * it under the terms of the GNU General Public License as published by |
| * the Free Software Foundation; either version 2 of the License, or |
| * (at your option) any later version. |
| * |
| * This program is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| * GNU General Public License for more details. |
| * |
| * You should have received a copy of the GNU General Public License |
| * along with this program; if not, write to the Free Software |
| * Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, |
| * MA 02110-1301, USA. |
| * |
| * $Id: block.c,v 1.11 1998/11/02 22:08:52 rob Exp $ |
| */ |
| |
| #include "config.h" |
| |
| #include "libhfs.h" |
| #include "volume.h" |
| #include "block.h" |
| #include "os.h" |
| |
| #define INUSE(b) ((b)->flags & HFS_BUCKET_INUSE) |
| #define DIRTY(b) ((b)->flags & HFS_BUCKET_DIRTY) |
| |
| /* |
| * NAME: block->init() |
| * DESCRIPTION: initialize a volume's block cache |
| */ |
| int b_init(hfsvol *vol) |
| { |
| bcache *cache; |
| int i; |
| |
| ASSERT(vol->cache == 0); |
| |
| cache = ALLOC(bcache, 1); |
| if (cache == NULL) |
| ERROR(ENOMEM, NULL); |
| |
| vol->cache = cache; |
| |
| cache->vol = vol; |
| cache->tail = &cache->chain[HFS_CACHESZ - 1]; |
| |
| cache->hits = 0; |
| cache->misses = 0; |
| |
| for (i = 0; i < HFS_CACHESZ; ++i) |
| { |
| bucket *b = &cache->chain[i]; |
| |
| b->flags = 0; |
| b->count = 0; |
| |
| b->bnum = 0; |
| b->data = &cache->pool[i]; |
| |
| b->cnext = b + 1; |
| b->cprev = b - 1; |
| |
| b->hnext = NULL; |
| b->hprev = NULL; |
| } |
| |
| cache->chain[0].cprev = cache->tail; |
| cache->tail->cnext = &cache->chain[0]; |
| |
| for (i = 0; i < HFS_HASHSZ; ++i) |
| cache->hash[i] = NULL; |
| |
| return 0; |
| |
| fail: |
| return -1; |
| } |
| |
| # ifdef DEBUG |
| /* |
| * NAME: block->showstats() |
| * DESCRIPTION: output cache hit/miss ratio |
| */ |
| void b_showstats(const bcache *cache) |
| { |
| fprintf(stderr, "BLOCK: CACHE vol 0x%lx \"%s\" hit/miss ratio = %.3f\n", |
| (unsigned long) cache->vol, cache->vol->mdb.drVN, |
| (float) cache->hits / (float) cache->misses); |
| } |
| |
| /* |
| * NAME: block->dumpcache() |
| * DESCRIPTION: dump the cache tables for a volume |
| */ |
| void b_dumpcache(const bcache *cache) |
| { |
| const bucket *b; |
| int i; |
| |
| fprintf(stderr, "BLOCK CACHE DUMP:\n"); |
| |
| for (i = 0, b = cache->tail->cnext; i < HFS_CACHESZ; ++i, b = b->cnext) |
| { |
| if (INUSE(b)) |
| { |
| fprintf(stderr, "\t %lu", b->bnum); |
| if (DIRTY(b)) |
| fprintf(stderr, "*"); |
| |
| fprintf(stderr, ":%u", b->count); |
| } |
| } |
| |
| fprintf(stderr, "\n"); |
| |
| fprintf(stderr, "BLOCK HASH DUMP:\n"); |
| |
| for (i = 0; i < HFS_HASHSZ; ++i) |
| { |
| int seen = 0; |
| |
| for (b = cache->hash[i]; b; b = b->hnext) |
| { |
| if (! seen) |
| fprintf(stderr, " %d:", i); |
| |
| if (INUSE(b)) |
| { |
| fprintf(stderr, " %lu", b->bnum); |
| if (DIRTY(b)) |
| fprintf(stderr, "*"); |
| |
| fprintf(stderr, ":%u", b->count); |
| } |
| |
| seen = 1; |
| } |
| |
| if (seen) |
| fprintf(stderr, "\n"); |
| } |
| } |
| # endif |
| |
| /* |
| * NAME: fillchain() |
| * DESCRIPTION: fill a chain of bucket buffers with a single read |
| */ |
| static |
| int fillchain(hfsvol *vol, bucket **bptr, unsigned int *count) |
| { |
| bucket *blist[HFS_BLOCKBUFSZ], **start = bptr; |
| unsigned long bnum=-2; // XXX |
| unsigned int len, i; |
| |
| for (len = 0; len < HFS_BLOCKBUFSZ && |
| (unsigned int) (bptr - start) < *count; ++bptr) |
| { |
| if (INUSE(*bptr)) |
| continue; |
| |
| if (len > 0 && (*bptr)->bnum != bnum) |
| break; |
| |
| blist[len++] = *bptr; |
| bnum = (*bptr)->bnum + 1; |
| } |
| |
| *count = bptr - start; |
| |
| if (len == 0) |
| goto done; |
| else if (len == 1) |
| { |
| if (b_readpb(vol, vol->vstart + blist[0]->bnum, |
| blist[0]->data, 1) == -1) |
| goto fail; |
| } |
| else |
| { |
| block buffer[HFS_BLOCKBUFSZ]; |
| |
| if (b_readpb(vol, vol->vstart + blist[0]->bnum, buffer, len) == -1) |
| goto fail; |
| |
| for (i = 0; i < len; ++i) |
| memcpy(blist[i]->data, buffer[i], HFS_BLOCKSZ); |
| } |
| |
| for (i = 0; i < len; ++i) |
| { |
| blist[i]->flags |= HFS_BUCKET_INUSE; |
| blist[i]->flags &= ~HFS_BUCKET_DIRTY; |
| } |
| |
| done: |
| return 0; |
| |
| fail: |
| return -1; |
| } |
| |
| |
| /* |
| * NAME: compare() |
| * DESCRIPTION: comparison function for qsort of cache bucket pointers |
| */ |
| static |
| int compare(const bucket **b1, const bucket **b2) |
| { |
| long diff; |
| |
| diff = (*b1)->bnum - (*b2)->bnum; |
| |
| if (diff < 0) |
| return -1; |
| else if (diff > 0) |
| return 1; |
| else |
| return 0; |
| } |
| |
| /* |
| * NAME: dobuckets() |
| * DESCRIPTION: fill or flush an array of cache buckets to a volume |
| */ |
| static |
| int dobuckets(hfsvol *vol, bucket **chain, unsigned int len, |
| int (*func)(hfsvol *, bucket **, unsigned int *)) |
| { |
| unsigned int count, i; |
| int result = 0; |
| |
| qsort(chain, len, sizeof(*chain), |
| (int (*)(const void *, const void *)) compare); |
| |
| for (i = 0; i < len; i += count) |
| { |
| count = len - i; |
| if (func(vol, chain + i, &count) == -1) |
| result = -1; |
| } |
| |
| return result; |
| } |
| |
| # define fillbuckets(vol, chain, len) dobuckets(vol, chain, len, fillchain) |
| |
| /* |
| * NAME: block->finish() |
| * DESCRIPTION: commit and free a volume's block cache |
| */ |
| int b_finish(hfsvol *vol) |
| { |
| int result = 0; |
| |
| if (vol->cache == NULL) |
| goto done; |
| |
| # ifdef DEBUG |
| b_dumpcache(vol->cache); |
| # endif |
| |
| FREE(vol->cache); |
| vol->cache = NULL; |
| |
| done: |
| return result; |
| } |
| |
| /* |
| * NAME: findbucket() |
| * DESCRIPTION: locate a bucket in the cache, and/or its hash slot |
| */ |
| static |
| bucket *findbucket(bcache *cache, unsigned long bnum, bucket ***hslot) |
| { |
| bucket *b; |
| |
| *hslot = &cache->hash[bnum & (HFS_HASHSZ - 1)]; |
| |
| for (b = **hslot; b; b = b->hnext) |
| { |
| if (INUSE(b) && b->bnum == bnum) |
| break; |
| } |
| |
| return b; |
| } |
| |
| /* |
| * NAME: reuse() |
| * DESCRIPTION: free a bucket for reuse, flushing if necessary |
| */ |
| static |
| int reuse(bcache *cache, bucket *b, unsigned long bnum) |
| { |
| bucket *bptr; |
| int i; |
| |
| # ifdef DEBUG |
| if (INUSE(b)) |
| fprintf(stderr, "BLOCK: CACHE reusing bucket containing " |
| "vol 0x%lx block %lu:%u\n", |
| (unsigned long) cache->vol, b->bnum, b->count); |
| # endif |
| |
| if (INUSE(b) && DIRTY(b)) |
| { |
| /* flush most recently unused buckets */ |
| |
| for (bptr = b, i = 0; i < HFS_BLOCKBUFSZ; ++i) |
| { |
| bptr = bptr->cprev; |
| } |
| } |
| |
| b->flags &= ~HFS_BUCKET_INUSE; |
| b->count = 1; |
| b->bnum = bnum; |
| |
| return 0; |
| } |
| |
| /* |
| * NAME: cplace() |
| * DESCRIPTION: move a bucket to an appropriate place near head of the chain |
| */ |
| static |
| void cplace(bcache *cache, bucket *b) |
| { |
| bucket *p; |
| |
| for (p = cache->tail->cnext; p->count > 1; p = p->cnext) |
| --p->count; |
| |
| b->cnext->cprev = b->cprev; |
| b->cprev->cnext = b->cnext; |
| |
| if (cache->tail == b) |
| cache->tail = b->cprev; |
| |
| b->cprev = p->cprev; |
| b->cnext = p; |
| |
| p->cprev->cnext = b; |
| p->cprev = b; |
| } |
| |
| /* |
| * NAME: hplace() |
| * DESCRIPTION: move a bucket to the head of its hash slot |
| */ |
| static |
| void hplace(bucket **hslot, bucket *b) |
| { |
| if (*hslot != b) |
| { |
| if (b->hprev) |
| *b->hprev = b->hnext; |
| if (b->hnext) |
| b->hnext->hprev = b->hprev; |
| |
| b->hprev = hslot; |
| b->hnext = *hslot; |
| |
| if (*hslot) |
| (*hslot)->hprev = &b->hnext; |
| |
| *hslot = b; |
| } |
| } |
| |
| /* |
| * NAME: getbucket() |
| * DESCRIPTION: fetch a bucket from the cache, or an empty one to be filled |
| */ |
| static |
| bucket *getbucket(bcache *cache, unsigned long bnum, int fill) |
| { |
| bucket **hslot, *b, *p, *bptr, |
| *chain[HFS_BLOCKBUFSZ], **slots[HFS_BLOCKBUFSZ]; |
| |
| b = findbucket(cache, bnum, &hslot); |
| |
| if (b) |
| { |
| /* cache hit; move towards head of cache chain */ |
| |
| ++cache->hits; |
| |
| if (++b->count > b->cprev->count && |
| b != cache->tail->cnext) |
| { |
| p = b->cprev; |
| |
| p->cprev->cnext = b; |
| b->cnext->cprev = p; |
| |
| p->cnext = b->cnext; |
| b->cprev = p->cprev; |
| |
| p->cprev = b; |
| b->cnext = p; |
| |
| if (cache->tail == b) |
| cache->tail = p; |
| } |
| } |
| else |
| { |
| /* cache miss; reuse least-used cache bucket */ |
| |
| ++cache->misses; |
| |
| b = cache->tail; |
| |
| if (reuse(cache, b, bnum) == -1) |
| goto fail; |
| |
| if (fill) |
| { |
| unsigned int len = 0; |
| |
| chain[len] = b; |
| slots[len++] = hslot; |
| |
| for (bptr = b->cprev; |
| len < (HFS_BLOCKBUFSZ >> 1) && ++bnum < cache->vol->vlen; |
| bptr = bptr->cprev) |
| { |
| if (findbucket(cache, bnum, &hslot)) |
| break; |
| |
| if (reuse(cache, bptr, bnum) == -1) |
| goto fail; |
| |
| chain[len] = bptr; |
| slots[len++] = hslot; |
| } |
| |
| if (fillbuckets(cache->vol, chain, len) == -1) |
| goto fail; |
| |
| while (--len) |
| { |
| cplace(cache, chain[len]); |
| hplace(slots[len], chain[len]); |
| } |
| |
| hslot = slots[0]; |
| } |
| |
| /* move bucket to appropriate place in chain */ |
| |
| cplace(cache, b); |
| } |
| |
| /* insert at front of hash chain */ |
| |
| hplace(hslot, b); |
| |
| return b; |
| |
| fail: |
| return NULL; |
| } |
| |
| /* |
| * NAME: block->readpb() |
| * DESCRIPTION: read blocks from the physical medium (bypassing cache) |
| */ |
| int b_readpb(hfsvol *vol, unsigned long bnum, block *bp, unsigned int blen) |
| { |
| unsigned long nblocks; |
| |
| # ifdef DEBUG |
| fprintf(stderr, "BLOCK: READ vol 0x%lx block %lu", |
| (unsigned long) vol, bnum); |
| if (blen > 1) |
| fprintf(stderr, "+%u[..%lu]\n", blen - 1, bnum + blen - 1); |
| else |
| fprintf(stderr, "\n"); |
| # endif |
| |
| nblocks = os_seek(vol->os_fd, bnum, HFS_BLOCKSZ_BITS ); |
| if (nblocks == (unsigned long) -1) |
| goto fail; |
| |
| if (nblocks != bnum) |
| ERROR(EIO, "block seek failed for read"); |
| |
| nblocks = os_read(vol->os_fd, bp, blen, HFS_BLOCKSZ_BITS); |
| if (nblocks == (unsigned long) -1) |
| goto fail; |
| |
| if (nblocks != blen) |
| ERROR(EIO, "incomplete block read"); |
| |
| return 0; |
| |
| fail: |
| return -1; |
| } |
| |
| |
| /* |
| * NAME: block->readlb() |
| * DESCRIPTION: read a logical block from a volume (or from the cache) |
| */ |
| int b_readlb(hfsvol *vol, unsigned long bnum, block *bp) |
| { |
| if (vol->vlen > 0 && bnum >= vol->vlen) |
| ERROR(EIO, "read nonexistent logical block"); |
| |
| if (vol->cache) |
| { |
| bucket *b; |
| |
| b = getbucket(vol->cache, bnum, 1); |
| if (b == NULL) |
| goto fail; |
| |
| memcpy(bp, b->data, HFS_BLOCKSZ); |
| } |
| else |
| { |
| if (b_readpb(vol, vol->vstart + bnum, bp, 1) == -1) |
| goto fail; |
| } |
| |
| return 0; |
| |
| fail: |
| return -1; |
| } |
| |
| /* |
| * NAME: block->readab() |
| * DESCRIPTION: read a block from an allocation block from a volume |
| */ |
| int b_readab(hfsvol *vol, unsigned int anum, unsigned int index, block *bp) |
| { |
| /* verify the allocation block exists and is marked as in-use */ |
| |
| if (anum >= vol->mdb.drNmAlBlks) |
| ERROR(EIO, "read nonexistent allocation block"); |
| else if (vol->vbm && ! BMTST(vol->vbm, anum)) |
| ERROR(EIO, "read unallocated block"); |
| |
| return b_readlb(vol, vol->mdb.drAlBlSt + anum * vol->lpa + index, bp); |
| |
| fail: |
| return -1; |
| } |
| |
| |
| /* |
| * NAME: block->size() |
| * DESCRIPTION: return the number of physical blocks on a volume's medium |
| */ |
| unsigned long b_size(hfsvol *vol) |
| { |
| unsigned long low, high, mid; |
| block b; |
| |
| high = os_seek(vol->os_fd, -1, HFS_BLOCKSZ_BITS); |
| |
| if (high != (unsigned long) -1 && high > 0) |
| return high; |
| |
| /* manual size detection: first check there is at least 1 block in medium */ |
| |
| if (b_readpb(vol, 0, &b, 1) == -1) |
| ERROR(EIO, "size of medium indeterminable or empty"); |
| |
| for (low = 0, high = 2880; |
| high > 0 && b_readpb(vol, high - 1, &b, 1) != -1; |
| high <<= 1) |
| low = high - 1; |
| |
| if (high == 0) |
| ERROR(EIO, "size of medium indeterminable or too large"); |
| |
| /* common case: 1440K floppy */ |
| |
| if (low == 2879 && b_readpb(vol, 2880, &b, 1) == -1) |
| return 2880; |
| |
| /* binary search for other sizes */ |
| |
| while (low < high - 1) |
| { |
| mid = (low + high) >> 1; |
| |
| if (b_readpb(vol, mid, &b, 1) == -1) |
| high = mid; |
| else |
| low = mid; |
| } |
| |
| return low + 1; |
| |
| fail: |
| return 0; |
| } |