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 */
b_init(hfsvol * vol)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 */
b_showstats(const bcache * cache)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 */
b_dumpcache(const bcache * cache)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
fillchain(hfsvol * vol,bucket ** bptr,unsigned int * count)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
compare(const bucket ** b1,const bucket ** b2)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
dobuckets(hfsvol * vol,bucket ** chain,unsigned int len,int (* func)(hfsvol *,bucket **,unsigned int *))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 */
b_finish(hfsvol * vol)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
findbucket(bcache * cache,unsigned long bnum,bucket *** hslot)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
reuse(bcache * cache,bucket * b,unsigned long bnum)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
cplace(bcache * cache,bucket * b)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
hplace(bucket ** hslot,bucket * b)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
getbucket(bcache * cache,unsigned long bnum,int fill)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 */
b_readpb(hfsvol * vol,unsigned long bnum,block * bp,unsigned int blen)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 */
b_readlb(hfsvol * vol,unsigned long bnum,block * bp)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 */
b_readab(hfsvol * vol,unsigned int anum,unsigned int index,block * bp)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 */
b_size(hfsvol * vol)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 }
613