libhfs/block.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: block.c,v 1.11 1998/11/02 22:08:52 rob Exp $
 */

# 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:	bcompare()
 * DESCRIPTION:	comparison function for qsort of cache bucket pointers
 */
static
int bcompare(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 *)) bcompare);

  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 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->writeab()
 * DESCRIPTION:	write a block to an allocation block to a volume
 */
int b_writeab(hfsvol *vol,
	      unsigned int anum, unsigned int index, 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 + 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->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;
}