ciderpress/diskimg/libhfs/block.c
2007-03-27 17:47:10 +00:00

808 lines
16 KiB
C

/*
* 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., 675 Mass Ave, Cambridge, MA 02139, USA.
*
* $Id$
*/
# ifdef HAVE_CONFIG_H
# include "config.h"
# endif
# include <stdlib.h>
# include <string.h>
# include <errno.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 == 0)
ERROR(ENOMEM, 0);
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 = 0;
b->hprev = 0;
}
cache->chain[0].cprev = cache->tail;
cache->tail->cnext = &cache->chain[0];
for (i = 0; i < HFS_HASHSZ; ++i)
cache->hash[i] = 0;
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;
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: flushchain()
* DESCRIPTION: store a chain of bucket buffers with a single write
*/
static
int flushchain(hfsvol *vol, bucket **bptr, unsigned int *count)
{
bucket *blist[HFS_BLOCKBUFSZ], **start = bptr;
unsigned long bnum;
unsigned int len, i;
for (len = 0; len < HFS_BLOCKBUFSZ &&
(unsigned int) (bptr - start) < *count; ++bptr)
{
if (! INUSE(*bptr) || ! DIRTY(*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_writepb(vol, vol->vstart + blist[0]->bnum,
blist[0]->data, 1) == -1)
goto fail;
}
else
{
block buffer[HFS_BLOCKBUFSZ];
for (i = 0; i < len; ++i)
memcpy(buffer[i], blist[i]->data, HFS_BLOCKSZ);
if (b_writepb(vol, vol->vstart + blist[0]->bnum, buffer, len) == -1)
goto fail;
}
for (i = 0; i < len; ++i)
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)
# define flushbuckets(vol, chain, len) dobuckets(vol, chain, len, flushchain)
/*
* NAME: block->flush()
* DESCRIPTION: commit dirty cache blocks to a volume
*/
int b_flush(hfsvol *vol)
{
bcache *cache = vol->cache;
bucket *chain[HFS_CACHESZ];
int i;
if (cache == 0 || (vol->flags & HFS_VOL_READONLY))
goto done;
for (i = 0; i < HFS_CACHESZ; ++i)
chain[i] = &cache->chain[i];
if (flushbuckets(vol, chain, HFS_CACHESZ) == -1)
goto fail;
done:
# ifdef DEBUG
if (cache)
b_showstats(cache);
# endif
return 0;
fail:
return -1;
}
/*
* NAME: block->finish()
* DESCRIPTION: commit and free a volume's block cache
*/
int b_finish(hfsvol *vol)
{
int result = 0;
if (vol->cache == 0)
goto done;
# ifdef DEBUG
b_dumpcache(vol->cache);
# endif
result = b_flush(vol);
FREE(vol->cache);
vol->cache = 0;
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 *chain[HFS_BLOCKBUFSZ], *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)
{
chain[i] = bptr;
bptr = bptr->cprev;
}
if (flushbuckets(cache->vol, chain, HFS_BLOCKBUFSZ) == -1)
goto fail;
}
b->flags &= ~HFS_BUCKET_INUSE;
b->count = 1;
b->bnum = bnum;
return 0;
fail:
return -1;
}
/*
* 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 0;
}
/*
* 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->priv, bnum);
if (nblocks == (unsigned long) -1)
goto fail;
if (nblocks != bnum)
ERROR(EIO, "block seek failed for read");
nblocks = os_read(&vol->priv, bp, blen);
if (nblocks == (unsigned long) -1)
goto fail;
if (nblocks != blen)
ERROR(EIO, "incomplete block read");
return 0;
fail:
return -1;
}
/*
* NAME: block->writepb()
* DESCRIPTION: write blocks to the physical medium (bypassing cache)
*/
int b_writepb(hfsvol *vol, unsigned long bnum, const block *bp,
unsigned int blen)
{
unsigned long nblocks;
# ifdef DEBUG
fprintf(stderr, "BLOCK: WRITE 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->priv, bnum);
if (nblocks == (unsigned long) -1)
goto fail;
if (nblocks != bnum)
ERROR(EIO, "block seek failed for write");
nblocks = os_write(&vol->priv, bp, blen);
if (nblocks == (unsigned long) -1)
goto fail;
if (nblocks != blen)
ERROR(EIO, "incomplete block write");
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 == 0)
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->writelb()
* DESCRIPTION: write a logical block to a volume (or to the cache)
*/
int b_writelb(hfsvol *vol, unsigned long bnum, const block *bp)
{
if (vol->vlen > 0 && bnum >= vol->vlen)
ERROR(EIO, "write nonexistent logical block");
if (vol->cache)
{
bucket *b;
b = getbucket(vol->cache, bnum, 0);
if (b == 0)
goto fail;
if (! INUSE(b) ||
memcmp(b->data, bp, HFS_BLOCKSZ) != 0)
{
memcpy(b->data, bp, HFS_BLOCKSZ);
b->flags |= HFS_BUCKET_INUSE | HFS_BUCKET_DIRTY;
}
}
else
{
if (b_writepb(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 idx, 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 + idx, bp);
fail:
return -1;
}
/*
* NAME: block->writeab()
* DESCRIPTION: write a block to an allocation block to a volume
*/
int b_writeab(hfsvol *vol,
unsigned int anum, unsigned int idx, const block *bp)
{
/* verify the allocation block exists and is marked as in-use */
if (anum >= vol->mdb.drNmAlBlks)
ERROR(EIO, "write nonexistent allocation block");
else if (vol->vbm && ! BMTST(vol->vbm, anum))
ERROR(EIO, "write unallocated block");
if (v_dirty(vol) == -1)
goto fail;
return b_writelb(vol, vol->mdb.drAlBlSt + anum * vol->lpa + idx, 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->priv, -1);
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;
}