![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to block.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Qemu by Fabrice Bellard] / qemu / roms / openbios / fs / hfs|
Return to block.c CVS log | Up to [Qemu by Fabrice Bellard] / qemu / roms / openbios / fs / hfs |
1.1 root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.