FreeBSD/Linux Kernel Cross Reference
sys/port/devtinyfs.c
1 /*
2 * a pity the code isn't also tiny...
3 */
4 #include "u.h"
5 #include "../port/lib.h"
6 #include "../port/error.h"
7 #include "mem.h"
8 #include "dat.h"
9 #include "fns.h"
10
11 enum{
12 Qdir,
13 Qmedium,
14
15 Maxfs= 10, /* max file systems */
16
17 Blen= 48, /* block length */
18 Nlen= 28, /* name length */
19 Dlen= Blen - 4,
20
21 Tagdir= 'd',
22 Tagdata= 'D',
23 Tagend= 'e',
24 Tagfree= 'f',
25
26 Notapin= 0xffff,
27 Notabno= 0xffff,
28
29 Fcreating= 1,
30 Frmonclose= 2
31 };
32
33 /* representation of a Tdir on medium */
34 typedef struct Mdir Mdir;
35 struct Mdir {
36 uchar type;
37 uchar bno[2];
38 uchar pin[2];
39 char name[Nlen];
40 char pad[Blen - Nlen - 6];
41 uchar sum;
42 };
43
44 /* representation of a Tdata/Tend on medium */
45 typedef struct Mdata Mdata;
46 struct Mdata {
47 uchar type;
48 uchar bno[2];
49 uchar data[Dlen];
50 uchar sum;
51 };
52
53 typedef struct Tfile Tfile;
54 struct Tfile {
55 int r;
56 char name[NAMELEN];
57 ushort bno;
58 ushort dbno;
59 ushort pin;
60 uchar flag;
61 ulong length;
62
63 /* hint to avoid egregious reading */
64 ushort fbno;
65 ulong finger;
66 };
67
68 typedef struct Tfs Tfs;
69 struct Tfs {
70 QLock ql;
71 int r;
72 Chan *c;
73 uchar *map;
74 int nblocks;
75 Tfile *f;
76 int nf;
77 int fsize;
78 };
79
80 struct {
81 Tfs fs[Maxfs];
82 } tinyfs;
83
84 #define GETS(x) ((x)[0]|((x)[1]<<8))
85 #define PUTS(x, v) {(x)[0] = (v);(x)[1] = ((v)>>8);}
86
87 #define GETL(x) (GETS(x)|(GETS(x+2)<<16))
88 #define PUTL(x, v) {PUTS(x, v);PUTS(x+2, (v)>>16)};
89
90 static uchar
91 checksum(uchar *p)
92 {
93 uchar *e;
94 uchar s;
95
96 s = 0;
97 for(e = p + Blen; p < e; p++)
98 s += *p;
99 return s;
100 }
101
102 static void
103 mapclr(Tfs *fs, ulong bno)
104 {
105 fs->map[bno>>3] &= ~(1<<(bno&7));
106 }
107
108 static void
109 mapset(Tfs *fs, ulong bno)
110 {
111 fs->map[bno>>3] |= 1<<(bno&7);
112 }
113
114 static int
115 isalloced(Tfs *fs, ulong bno)
116 {
117 return fs->map[bno>>3] & (1<<(bno&7));
118 }
119
120 static int
121 mapalloc(Tfs *fs)
122 {
123 int i, j, lim;
124 uchar x;
125
126 lim = (fs->nblocks + 8 - 1)/8;
127 for(i = 0; i < lim; i++){
128 x = fs->map[i];
129 if(x == 0xff)
130 continue;
131 for(j = 0; j < 8; j++)
132 if((x & (1<<j)) == 0){
133 fs->map[i] = x|(1<<j);
134 return i*8 + j;
135 }
136 }
137
138 return Notabno;
139 }
140
141 static Mdir*
142 validdir(Tfs *fs, uchar *p)
143 {
144 Mdir *md;
145 ulong x;
146
147 if(checksum(p) != 0)
148 return 0;
149 if(p[0] != Tagdir)
150 return 0;
151 md = (Mdir*)p;
152 x = GETS(md->bno);
153 if(x >= fs->nblocks)
154 return 0;
155 return md;
156 }
157
158 static Mdata*
159 validdata(Tfs *fs, uchar *p, int *lenp)
160 {
161 Mdata *md;
162 ulong x;
163
164 if(checksum(p) != 0)
165 return 0;
166 md = (Mdata*)p;
167 switch(md->type){
168 case Tagdata:
169 x = GETS(md->bno);
170 if(x >= fs->nblocks)
171 return 0;
172 if(lenp)
173 *lenp = Dlen;
174 break;
175 case Tagend:
176 x = GETS(md->bno);
177 if(x > Dlen)
178 return 0;
179 if(lenp)
180 *lenp = x;
181 break;
182 default:
183 return 0;
184 }
185 return md;
186 }
187
188 static Mdata*
189 readdata(Tfs *fs, ulong bno, uchar *buf, int *lenp)
190 {
191 if(bno >= fs->nblocks)
192 return 0;
193 if(devtab[fs->c->type]->read(fs->c, buf, Blen, Blen*bno) != Blen)
194 error(Eio);
195 return validdata(fs, buf, lenp);
196 }
197
198 static void
199 writedata(Tfs *fs, ulong bno, ulong next, uchar *buf, int len, int last)
200 {
201 Mdata md;
202
203 if(bno >= fs->nblocks)
204 error(Eio);
205 if(len > Dlen)
206 len = Dlen;
207 if(len < 0)
208 error(Eio);
209 memset(&md, 0, sizeof(md));
210 if(last){
211 md.type = Tagend;
212 PUTS(md.bno, len);
213 } else {
214 md.type = Tagdata;
215 PUTS(md.bno, next);
216 }
217 memmove(md.data, buf, len);
218 md.sum = 0 - checksum((uchar*)&md);
219
220 if(devtab[fs->c->type]->write(fs->c, &md, Blen, Blen*bno) != Blen)
221 error(Eio);
222 }
223
224 static void
225 writedir(Tfs *fs, Tfile *f)
226 {
227 Mdir *md;
228 uchar buf[Blen];
229
230 if(f->bno == Notabno)
231 return;
232
233 md = (Mdir*)buf;
234 memset(buf, 0, Blen);
235 md->type = Tagdir;
236 strncpy(md->name, f->name, sizeof(md->name)-1);
237 PUTS(md->bno, f->dbno);
238 PUTS(md->pin, f->pin);
239 md->sum = 0 - checksum(buf);
240
241 if(devtab[fs->c->type]->write(fs->c, buf, Blen, Blen*f->bno) != Blen)
242 error(Eio);
243 }
244
245 static void
246 freeblocks(Tfs *fs, ulong bno, ulong bend)
247 {
248 uchar buf[Blen];
249 Mdata *md;
250
251 if(waserror())
252 return;
253
254 while(bno != bend && bno != Notabno){
255 mapclr(fs, bno);
256 if(devtab[fs->c->type]->read(fs->c, buf, Blen, Blen*bno) != Blen)
257 break;
258 md = validdata(fs, buf, 0);
259 if(md == 0)
260 break;
261 if(md->type == Tagend)
262 break;
263 bno = GETS(md->bno);
264 }
265
266 poperror();
267 }
268
269 static void
270 freefile(Tfs *fs, Tfile *f, ulong bend)
271 {
272 uchar buf[Blen];
273
274 /* remove blocks from map */
275 freeblocks(fs, f->dbno, bend);
276
277 /* change file type to free on medium */
278 if(f->bno != Notabno){
279 memset(buf, 0x55, Blen);
280 devtab[fs->c->type]->write(fs->c, buf, Blen, Blen*f->bno);
281 mapclr(fs, f->bno);
282 }
283
284 /* forget we ever knew about it */
285 memset(f, 0, sizeof(*f));
286 }
287
288 static void
289 expand(Tfs *fs)
290 {
291 Tfile *f;
292
293 fs->fsize += 8;
294 f = malloc(fs->fsize*sizeof(*f));
295
296 if(fs->f){
297 memmove(f, fs->f, fs->nf*sizeof(*f));
298 free(fs->f);
299 }
300 fs->f = f;
301 }
302
303 static Tfile*
304 newfile(Tfs *fs, char *name)
305 {
306 int i;
307 volatile struct {
308 Tfile *f;
309 Tfs *fs;
310 } rock;
311
312 /* find free entry in file table */
313 rock.f = 0;
314 rock.fs = fs;
315 for(;;) {
316 for(i = 0; i < rock.fs->fsize; i++){
317 rock.f = &rock.fs->f[i];
318 if(rock.f->name[0] == 0){
319 strncpy(rock.f->name, name, sizeof(rock.f->name)-1);
320 break;
321 }
322 }
323
324 if(i < rock.fs->fsize){
325 if(i >= rock.fs->nf)
326 rock.fs->nf = i+1;
327 break;
328 }
329
330 expand(rock.fs);
331 }
332
333 rock.f->flag = Fcreating;
334 rock.f->dbno = Notabno;
335 rock.f->bno = mapalloc(rock.fs);
336 rock.f->fbno = Notabno;
337 rock.f->r = 1;
338 rock.f->pin = Notapin; // what is a pin??
339
340 /* write directory block */
341 if(waserror()){
342 freefile(rock.fs, rock.f, Notabno);
343 nexterror();
344 }
345 if(rock.f->bno == Notabno)
346 error("out of space");
347 writedir(rock.fs, rock.f);
348 poperror();
349
350 return rock.f;
351 }
352
353 /*
354 * Read the whole medium and build a file table and used
355 * block bitmap. Inconsistent files are purged. The medium
356 * had better be small or this could take a while.
357 */
358 static void
359 tfsinit(Tfs *fs)
360 {
361 char dbuf[DIRLEN];
362 Dir d;
363 uchar buf[Blen];
364 ulong x, bno;
365 int n, done;
366 Tfile *f;
367 Mdir *mdir;
368 Mdata *mdata;
369
370 devtab[fs->c->type]->stat(fs->c, dbuf);
371 convM2D(dbuf, &d);
372 fs->nblocks = d.length/Blen;
373 if(fs->nblocks < 3)
374 error("tinyfs medium too small");
375
376 /* bitmap for block usage */
377 x = (fs->nblocks + 8 - 1)/8;
378 fs->map = malloc(x);
379 memset(fs->map, 0x0, x);
380 for(bno = fs->nblocks; bno < x*8; bno++)
381 mapset(fs, bno);
382
383 /* find files */
384 for(bno = 0; bno < fs->nblocks; bno++){
385 n = devtab[fs->c->type]->read(fs->c, buf, Blen, Blen*bno);
386 if(n != Blen)
387 break;
388
389 mdir = validdir(fs, buf);
390 if(mdir == 0)
391 continue;
392
393 if(fs->nf >= fs->fsize)
394 expand(fs);
395
396 f = &fs->f[fs->nf++];
397
398 x = GETS(mdir->bno);
399 mapset(fs, bno);
400 strncpy(f->name, mdir->name, sizeof(f->name));
401 f->pin = GETS(mdir->pin);
402 f->bno = bno;
403 f->dbno = x;
404 f->fbno = Notabno;
405 }
406
407 /* follow files */
408 for(f = fs->f; f < &(fs->f[fs->nf]); f++){
409 bno = f->dbno;
410 for(done = 0; !done;) {
411 if(isalloced(fs, bno)){
412 freefile(fs, f, bno);
413 break;
414 }
415 n = devtab[fs->c->type]->read(fs->c, buf, Blen, Blen*bno);
416 if(n != Blen){
417 freefile(fs, f, bno);
418 break;
419 }
420 mdata = validdata(fs, buf, 0);
421 if(mdata == 0){
422 freefile(fs, f, bno);
423 break;
424 }
425 mapset(fs, bno);
426 switch(mdata->type){
427 case Tagdata:
428 bno = GETS(mdata->bno);
429 f->length += Dlen;
430 break;
431 case Tagend:
432 f->length += GETS(mdata->bno);
433 done = 1;
434 break;
435 }
436 if(done)
437 f->flag &= ~Fcreating;
438 }
439 }
440 }
441
442 /*
443 * single directory
444 */
445 static int
446 tinyfsgen(Chan *c, Dirtab *tab, int ntab, int i, Dir *dp)
447 {
448 Tfs *fs;
449 Tfile *f;
450 Qid qid;
451
452 USED(ntab);
453 USED(tab);
454
455 qid.vers = 0;
456 fs = &tinyfs.fs[c->dev];
457 if(i >= fs->nf)
458 return -1;
459 if(i == DEVDOTDOT){
460 qid.path = CHDIR;
461 devdir(c, qid, ".", 0, eve, 0555, dp);
462 return 1;
463 }
464 f = &fs->f[i];
465 if(f->name[0] == 0)
466 return 0;
467 qid.path = i;
468 devdir(c, qid, f->name, f->length, eve, 0775, dp);
469 return 1;
470 }
471
472 static void
473 tinyfsinit(void)
474 {
475 if(Nlen > NAMELEN)
476 panic("tinyfsinit");
477 }
478
479 /*
480 * specifier is an open file descriptor
481 */
482 static Chan*
483 tinyfsattach(char *spec)
484 {
485 Tfs *fs;
486 Chan *c;
487 volatile struct { Chan *cc; } rock;
488 int i;
489 char buf[NAMELEN*2];
490
491 snprint(buf, sizeof(buf), "/dev/%s", spec);
492 rock.cc = namec(buf, Aopen, ORDWR, 0);
493
494 if(waserror()){
495 cclose(rock.cc);
496 nexterror();
497 }
498
499 fs = 0;
500 for(i = 0; i < Maxfs; i++){
501 fs = &tinyfs.fs[i];
502 qlock(&fs->ql);
503 if(fs->r && eqchan(rock.cc, fs->c, 1))
504 break;
505 qunlock(&fs->ql);
506 }
507 if(i < Maxfs){
508 fs->r++;
509 qunlock(&fs->ql);
510 cclose(rock.cc);
511 } else {
512 for(fs = tinyfs.fs; fs < &tinyfs.fs[Maxfs]; fs++){
513 qlock(&fs->ql);
514 if(fs->r == 0)
515 break;
516 qunlock(&fs->ql);
517 }
518 if(fs == &tinyfs.fs[Maxfs])
519 error("too many tinyfs's");
520 fs->c = rock.cc;
521 fs->r = 1;
522 fs->f = 0;
523 fs->nf = 0;
524 fs->fsize = 0;
525 tfsinit(fs);
526 qunlock(&fs->ql);
527 }
528 poperror();
529
530 c = devattach('F', spec);
531 c->dev = fs - tinyfs.fs;
532 c->qid.path = CHDIR;
533 c->qid.vers = 0;
534
535 return c;
536 }
537
538 static Chan*
539 tinyfsclone(Chan *c, Chan *nc)
540 {
541 Tfs *fs;
542
543 fs = &tinyfs.fs[c->dev];
544
545 qlock(&fs->ql);
546 fs->r++;
547 qunlock(&fs->ql);
548
549 return devclone(c, nc);
550 }
551
552 static int
553 tinyfswalk(Chan *c, char *name)
554 {
555 int n;
556 Tfs *fs;
557
558 fs = &tinyfs.fs[c->dev];
559
560 qlock(&fs->ql);
561 n = devwalk(c, name, 0, 0, tinyfsgen);
562 if(n != 0 && c->qid.path != CHDIR){
563 fs = &tinyfs.fs[c->dev];
564 fs->f[c->qid.path].r++;
565 }
566 qunlock(&fs->ql);
567 return n;
568 }
569
570 static void
571 tinyfsstat(Chan *c, char *db)
572 {
573 devstat(c, db, 0, 0, tinyfsgen);
574 }
575
576 static Chan*
577 tinyfsopen(Chan *c, int omode)
578 {
579 Tfile *f;
580 volatile struct { Tfs *fs; } rock;
581
582 rock.fs = &tinyfs.fs[c->dev];
583
584 if(c->qid.path & CHDIR){
585 if(omode != OREAD)
586 error(Eperm);
587 } else {
588 qlock(&rock.fs->ql);
589 if(waserror()){
590 qunlock(&rock.fs->ql);
591 nexterror();
592 }
593 switch(omode){
594 case OTRUNC|ORDWR:
595 case OTRUNC|OWRITE:
596 f = newfile(rock.fs, rock.fs->f[c->qid.path].name);
597 rock.fs->f[c->qid.path].r--;
598 c->qid.path = f - rock.fs->f;
599 break;
600 case OREAD:
601 case OEXEC:
602 break;
603 default:
604 error(Eperm);
605 }
606 qunlock(&rock.fs->ql);
607 poperror();
608 }
609
610 return devopen(c, omode, 0, 0, tinyfsgen);
611 }
612
613 static void
614 tinyfscreate(Chan *c, char *name, int omode, ulong perm)
615 {
616 volatile struct { Tfs *fs; } rock;
617 Tfile *f;
618
619 USED(perm);
620
621 rock.fs = &tinyfs.fs[c->dev];
622
623 qlock(&rock.fs->ql);
624 if(waserror()){
625 qunlock(&rock.fs->ql);
626 nexterror();
627 }
628 f = newfile(rock.fs, name);
629 qunlock(&rock.fs->ql);
630 poperror();
631
632 c->qid.path = f - rock.fs->f;
633 c->qid.vers = 0;
634 c->mode = openmode(omode);
635 }
636
637 static void
638 tinyfsremove(Chan *c)
639 {
640 Tfs *fs;
641 Tfile *f;
642
643 if(c->qid.path == CHDIR)
644 error(Eperm);
645 fs = &tinyfs.fs[c->dev];
646 f = &fs->f[c->qid.path];
647 qlock(&fs->ql);
648 freefile(fs, f, Notabno);
649 qunlock(&fs->ql);
650 }
651
652 static void
653 tinyfsclose(Chan *c)
654 {
655 volatile struct { Tfs *fs; } rock;
656 Tfile *f, *nf;
657 int i;
658
659 rock.fs = &tinyfs.fs[c->dev];
660
661 qlock(&rock.fs->ql);
662
663 /* dereference file and remove old versions */
664 if(!waserror()){
665 if(c->qid.path != CHDIR){
666 f = &rock.fs->f[c->qid.path];
667 f->r--;
668 if(f->r == 0){
669 if(f->flag & Frmonclose)
670 freefile(rock.fs, f, Notabno);
671 else if(f->flag & Fcreating){
672 /* remove all other files with this name */
673 for(i = 0; i < rock.fs->fsize; i++){
674 nf = &rock.fs->f[i];
675 if(f == nf)
676 continue;
677 if(strcmp(nf->name, f->name) == 0){
678 if(nf->r)
679 nf->flag |= Frmonclose;
680 else
681 freefile(rock.fs, nf, Notabno);
682 }
683 }
684 f->flag &= ~Fcreating;
685 }
686 }
687 }
688 poperror();
689 }
690
691 /* dereference rock.fs and remove on zero refs */
692 rock.fs->r--;
693 if(rock.fs->r == 0){
694 if(rock.fs->f)
695 free(rock.fs->f);
696 rock.fs->f = 0;
697 rock.fs->nf = 0;
698 rock.fs->fsize = 0;
699 if(rock.fs->map)
700 free(rock.fs->map);
701 rock.fs->map = 0;
702 cclose(rock.fs->c);
703 rock.fs->c = 0;
704 }
705 qunlock(&rock.fs->ql);
706 }
707
708 static long
709 tinyfsread(Chan *c, void *a, long n, vlong offset)
710 {
711 volatile struct { Tfs *fs; } rock;
712 Tfile *f;
713 int sofar, i, off;
714 ulong bno;
715 Mdata *md;
716 uchar buf[Blen];
717 uchar *p;
718
719 if(c->qid.path & CHDIR)
720 return devdirread(c, a, n, 0, 0, tinyfsgen);
721
722 p = a;
723 rock.fs = &tinyfs.fs[c->dev];
724 f = &rock.fs->f[c->qid.path];
725 if(offset >= f->length)
726 return 0;
727
728 qlock(&rock.fs->ql);
729 if(waserror()){
730 qunlock(&rock.fs->ql);
731 nexterror();
732 }
733 if(n + offset >= f->length)
734 n = f->length - offset;
735
736 /* walk to starting data block */
737 if(0 && f->finger <= offset && f->fbno != Notabno){
738 sofar = f->finger;
739 bno = f->fbno;
740 } else {
741 sofar = 0;
742 bno = f->dbno;
743 }
744 for(; sofar + Dlen <= offset; sofar += Dlen){
745 md = readdata(rock.fs, bno, buf, 0);
746 if(md == 0)
747 error(Eio);
748 bno = GETS(md->bno);
749 }
750
751 /* read data */
752 off = offset%Dlen;
753 offset -= off;
754 for(sofar = 0; sofar < n; sofar += i){
755 md = readdata(rock.fs, bno, buf, &i);
756 if(md == 0)
757 error(Eio);
758
759 /* update finger for successful read */
760 f->finger = offset;
761 f->fbno = bno;
762 offset += Dlen;
763
764 i -= off;
765 if(i > n - sofar)
766 i = n - sofar;
767 memmove(p, md->data+off, i);
768 p += i;
769 bno = GETS(md->bno);
770 off = 0;
771 }
772 qunlock(&rock.fs->ql);
773 poperror();
774
775 return sofar;
776 }
777
778 /*
779 * if we get a write error in this routine, blocks will
780 * be lost. They should be recovered next fsinit.
781 */
782 static long
783 tinyfswrite(Chan *c, void *a, long n, vlong offset)
784 {
785 Tfile *f;
786 int last, next, i, finger, off, used;
787 ulong bno, fbno;
788 Mdata *md;
789 uchar buf[Blen];
790 uchar *p;
791 volatile struct {
792 Tfs *fs;
793 ulong dbno;
794 } rock;
795
796 if(c->qid.path & CHDIR)
797 error(Eperm);
798
799 if(n == 0)
800 return 0;
801
802 p = a;
803 rock.fs = &tinyfs.fs[c->dev];
804 f = &rock.fs->f[c->qid.path];
805
806 qlock(&rock.fs->ql);
807 rock.dbno = Notabno;
808 if(waserror()){
809 freeblocks(rock.fs, rock.dbno, Notabno);
810 qunlock(&rock.fs->ql);
811 nexterror();
812 }
813
814 /* files are append only, anything else is illegal */
815 if(offset != f->length)
816 error("append only");
817
818 /* write blocks backwards */
819 p += n;
820 last = offset + n;
821 fbno = Notabno;
822 finger = 0;
823 off = offset; /* so we have something signed to compare against */
824 for(next = ((last-1)/Dlen)*Dlen; next >= off; next -= Dlen){
825 bno = mapalloc(rock.fs);
826 if(bno == Notabno)
827 error("out of space");
828 i = last - next;
829 p -= i;
830 if(last == n+offset){
831 writedata(rock.fs, bno, rock.dbno, p, i, 1);
832 finger = next; /* remember for later */
833 fbno = bno;
834 } else {
835 writedata(rock.fs, bno, rock.dbno, p, i, 0);
836 }
837 rock.dbno = bno;
838 last = next;
839 }
840
841 /* walk to last data block */
842 md = (Mdata*)buf;
843 if(0 && f->finger < offset && f->fbno != Notabno){
844 next = f->finger;
845 bno = f->fbno;
846 } else {
847 next = 0;
848 bno = f->dbno;
849 }
850
851 used = 0;
852 while(bno != Notabno){
853 md = readdata(rock.fs, bno, buf, &used);
854 if(md == 0)
855 error(Eio);
856 if(md->type == Tagend){
857 if(next + Dlen < offset)
858 panic("devtinyfs1");
859 break;
860 }
861 next += Dlen;
862 if(next > offset)
863 panic("devtinyfs1");
864 bno = GETS(md->bno);
865 }
866
867 /* point to new blocks */
868 if(offset == 0){
869 /* first block in a file */
870 f->dbno = rock.dbno;
871 writedir(rock.fs, f);
872 } else {
873 /* updating a current block */
874 i = last - offset;
875 if(i > 0){
876 p -= i;
877 memmove(md->data + used, p, i);
878 used += i;
879 }
880 writedata(rock.fs, bno, rock.dbno, md->data, used, last == n+offset);
881 }
882 f->length += n;
883
884 /* update finger */
885 if(fbno != Notabno){
886 f->finger = finger;
887 f->fbno = fbno;
888 }
889 poperror();
890 qunlock(&rock.fs->ql);
891
892 return n;
893 }
894
895 Dev tinyfsdevtab = {
896 'F',
897 "tinyfs",
898
899 devreset,
900 tinyfsinit,
901 tinyfsattach,
902 tinyfsclone,
903 tinyfswalk,
904 tinyfsstat,
905 tinyfsopen,
906 tinyfscreate,
907 tinyfsclose,
908 tinyfsread,
909 devbread,
910 tinyfswrite,
911 devbwrite,
912 tinyfsremove,
913 devwstat,
914 };
Cache object: 51e00c4726318c0bc5ba4f7966e46692
|