qemu/roms/openbios/fs/hfs/block.c

   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 }