1 #include <u.h>
2 #include <libc.h>
3 #include <auth.h>
4 #include <fcall.h>
5 #include <thread.h>
6 #include <9p.h>
7 #include "flashfs.h"
8
9 enum
10 {
11 debug = 0,
12 diags = 1,
13 };
14
15 typedef struct Gen Gen;
16 typedef struct Sect Sect;
17
18 struct Gen
19 {
20 int gnum;
21 int count;
22 int low;
23 int high;
24 Sect* head;
25 Sect* tail;
26 Sect* dup;
27 Sect** vect;
28 };
29
30 struct Sect
31 {
32 int sect;
33 ulong seq;
34 int coff;
35 int toff;
36 int sum;
37 ulong time;
38 Sect* next;
39 };
40
41 static Gen gens[2];
42 static Sect* freehead;
43 static Sect* freetail;
44 static int nfree;
45 static int nbad;
46 static ulong ltime;
47 static int cursect;
48
49 /*
50 * If we have a delta then file times are in the future.
51 * But they drift back to reality.
52 */
53 ulong
now(void)54 now(void)
55 {
56 ulong cur, drift;
57 static ulong last;
58
59 cur = time(0);
60 if(cur < last)
61 delta += last - cur;
62 else if(delta != 0 && last != 0) {
63 drift = (cur - last + 1) / 2;
64 if(drift > delta)
65 delta = 0;
66 else
67 delta -= drift;
68 }
69 last = cur;
70 return cur + delta;
71 }
72
73 static void
damaged(char * mesg)74 damaged(char *mesg)
75 {
76 sysfatal("damaged filesystem: %s", mesg);
77 }
78
79 static void
lddisc(char * mesg)80 lddisc(char *mesg)
81 {
82 if(debug)
83 fprint(2, "discard %s\n", mesg);
84 else
85 USED(mesg);
86 }
87
88 static Sect *
getsect(void)89 getsect(void)
90 {
91 Sect *t;
92
93 t = freehead;
94 freehead = t->next;
95 if(freehead == nil)
96 freetail = nil;
97 nfree--;
98 return t;
99 }
100
101 static void
newsect(Gen * g,Sect * s)102 newsect(Gen *g, Sect *s)
103 {
104 int m, n, err;
105 uchar hdr[2*3];
106
107 if(debug)
108 fprint(2, "new %d %ld\n", g->gnum, s->seq);
109 if(g->tail == nil)
110 g->head = s;
111 else
112 g->tail->next = s;
113 g->tail = s;
114 s->next = nil;
115 m = putc3(&hdr[0], g->gnum);
116 n = putc3(&hdr[m], s->seq);
117 s->toff = MAGSIZE + m + n;
118 s->coff = s->toff + 4;
119 s->time = NOTIME;
120 s->sum = 0;
121 err = 1;
122 for(;;) {
123 if(writedata(err, s->sect, hdr, m + n, MAGSIZE)
124 && writedata(err, s->sect, magic, MAGSIZE, 0))
125 break;
126 clearsect(s->sect);
127 err = 0;
128 }
129 }
130
131 static Sect *
newsum(Gen * g,ulong seq)132 newsum(Gen *g, ulong seq)
133 {
134 Sect *t;
135
136 if(nfree == 0)
137 damaged("no free sector for summary");
138 t = getsect();
139 t->seq = seq;
140 newsect(g, t);
141 return t;
142 }
143
144 static void
freesect(Sect * s)145 freesect(Sect *s)
146 {
147 clearsect(s->sect);
148 if(freetail == nil)
149 freehead = s;
150 else
151 freetail->next = s;
152 freetail = s;
153 s->next = nil;
154 nfree++;
155 }
156
157 static void
dupsect(Sect * s,int renum)158 dupsect(Sect *s, int renum)
159 {
160 Sect *t;
161 Renum r;
162 uchar *b;
163 int err, n;
164 ulong doff, off;
165
166 if(nfree == 0)
167 damaged("no free for copy");
168 t = getsect();
169 b = sectbuff;
170 off = s->coff;
171 readdata(s->sect, b, off, 0);
172 doff = s->toff;
173 if(s->time == NOTIME)
174 doff += 4;
175 // Window 5
176 err = 1;
177 for(;;) {
178 if(writedata(err, t->sect, b + 1, s->toff - 1, 1)
179 && writedata(err, t->sect, b + doff, off - doff, doff)
180 && writedata(err, t->sect, b, 1, 0))
181 break;
182 clearsect(t->sect);
183 err = 0;
184 }
185 if(renum) {
186 r.old = s->sect;
187 r.new = t->sect;
188 erenum(&r);
189 }
190 n = s->sect;
191 s->sect = t->sect;
192 t->sect = n;
193 freesect(t);
194 if(cursect >= 0)
195 readdata(cursect, b, sectsize, 0);
196 }
197
198 static void
gswap(void)199 gswap(void)
200 {
201 Gen t;
202
203 t = gens[0];
204 gens[0] = gens[1];
205 gens[1] = t;
206 }
207
208 static void
checkdata(void)209 checkdata(void)
210 {
211 Gen *g;
212
213 g = &gens[0];
214 if(g->dup != nil) { // Window 5 damage
215 if(diags)
216 fprint(2, "%s: window 5 damage\n", argv0);
217 freesect(g->dup);
218 g->dup = nil;
219 }
220 }
221
222 static void
checksweep(void)223 checksweep(void)
224 {
225 Gen *g;
226 Jrec j;
227 uchar *b;
228 int n, op;
229 Sect *s, *t, *u;
230 long off, seq, soff;
231
232 g = &gens[1];
233 if(g->dup != nil) { // Window 5 damage
234 if(diags)
235 fprint(2, "%s: window 5 damage\n", argv0);
236 freesect(g->dup);
237 g->dup = nil;
238 }
239
240 s = g->head;
241 if(s != g->tail) {
242 while(s->next != g->tail)
243 s = s->next;
244 }
245
246 b = sectbuff;
247 op = -1;
248 seq = -1;
249 soff = 0;
250 u = nil;
251 t = s;
252 for(;;) {
253 readdata(t->sect, b, sectsize, 0);
254 off = t->toff + 4;
255 for(;;) {
256 n = convM2J(&j, &b[off]);
257 if(n < 0) {
258 if(j.type != 0xFF) {
259 if(debug)
260 fprint(2, "s[%d] @ %d %ld\n", j.type, t->sect, off);
261 damaged("bad Jrec");
262 }
263 break;
264 }
265 switch(j.type) {
266 case FT_SUMMARY:
267 case FT_SUMBEG:
268 seq = j.seq;
269 case FT_SUMEND:
270 op = j.type;
271 soff = off;
272 u = t;
273 break;
274 case FT_WRITE:
275 case FT_AWRITE:
276 off += j.size;
277 }
278 off += n;
279 }
280 t = t->next;
281 if(t == nil)
282 break;
283 }
284
285 if(op == FT_SUMBEG) { // Window 1 damage
286 if(diags)
287 fprint(2, "%s: window 1 damage\n", argv0);
288 if(u != s) {
289 freesect(u);
290 s->next = nil;
291 g->tail = s;
292 }
293 s->coff = soff;
294 dupsect(s, 0);
295 seq--;
296 }
297
298 if(seq >= 0) {
299 g = &gens[0];
300 if(seq > g->low)
301 damaged("high sweep");
302 if(seq == g->low) { // Window 2 damage
303 if(diags)
304 fprint(2, "%s: window 2 damage\n", argv0);
305 s = g->head;
306 g->head = s->next;
307 freesect(s);
308 if(g->head == nil) {
309 g->tail = nil;
310 g->gnum += 2;
311 newsum(g, 0);
312 gswap();
313 }
314 }
315 }
316 }
317
318 void
load1(Sect * s,int parity)319 load1(Sect *s, int parity)
320 {
321 int n;
322 Jrec j;
323 uchar *b;
324 char *err;
325 Extent *x;
326 Entry *d, *e;
327 ulong ctime, off, mtime;
328
329 if(s->sect < 0 && readonly) // readonly damaged
330 return;
331
332 b = sectbuff;
333 readdata(s->sect, b, sectsize, 0);
334 s->sum = 0;
335 off = s->toff;
336 ctime = get4(&b[off]);
337 off += 4;
338
339 for(;;) {
340 n = convM2J(&j, &b[off]);
341 if(n < 0) {
342 if(j.type != 0xFF) {
343 if(debug)
344 fprint(2, "l[%d] @ %d %ld\n", j.type, s->sect, off);
345 damaged("bad Jrec");
346 }
347 s->coff = off;
348 break;
349 }
350 off += n;
351 if(debug)
352 fprint(2, "get %J\n", &j);
353 switch(j.type) {
354 case FT_create:
355 ctime += j.mtime;
356 create:
357 d = elookup(j.parent);
358 if(d == nil) {
359 lddisc("parent");
360 break;
361 }
362 d->ref++;
363 e = ecreate(d, j.name, j.fnum, j.mode, ctime, &err);
364 if(e == nil) {
365 d->ref--;
366 lddisc("create");
367 break;
368 }
369 e->ref--;
370 if(j.type == FT_trunc)
371 e->mode = j.mode;
372 break;
373 case FT_chmod:
374 e = elookup(j.fnum);
375 if(e == nil) {
376 lddisc("lookup");
377 break;
378 }
379 echmod(e, j.mode, j.mnum);
380 break;
381 case FT_REMOVE:
382 e = elookup(j.fnum);
383 if(e == nil) {
384 lddisc("lookup");
385 break;
386 }
387 if(eremove(e) != nil) {
388 lddisc("remove");
389 break;
390 }
391 break;
392 case FT_AWRITE:
393 mtime = 0;
394 goto write;
395 case FT_WRITE:
396 ctime += j.mtime;
397 mtime = ctime;
398 write:
399 x = emalloc9p(sizeof(Extent));
400 x->sect = s->sect;
401 x->addr = off;
402 x->off = j.offset;
403 x->size = j.size;
404 off += j.size;
405 e = elookup(j.fnum);
406 if(e == nil) {
407 lddisc("lookup");
408 break;
409 }
410 ewrite(e, x, parity, mtime);
411 break;
412 case FT_trunc:
413 ctime += j.mtime;
414 e = elookup(j.tnum);
415 if(e == nil) {
416 if(debug)
417 fprint(2, "-> create\n");
418 goto create;
419 }
420 etrunc(e, j.fnum, ctime);
421 break;
422 case FT_SUMMARY:
423 case FT_SUMBEG:
424 case FT_SUMEND:
425 s->sum += n;
426 break;
427 default:
428 damaged("load1 botch");
429 }
430 }
431
432 if(s->sum > Nsum)
433 s->sum = Nsum;
434
435 s->time = ctime;
436 if(ctime != NOTIME && ctime > ltime)
437 ltime = ctime;
438 }
439
440 void
load0(int parity)441 load0(int parity)
442 {
443 Sect *s;
444
445 if(debug)
446 fprint(2, "load %d\n", parity);
447 for(s = gens[parity].head; s != nil; s = s->next)
448 load1(s, parity);
449 }
450
451 void
loadfs(int ro)452 loadfs(int ro)
453 {
454 Gen *g;
455 Sect *s;
456 ulong u, v;
457 int i, j, n;
458 uchar hdr[MAXHDR];
459
460 readonly = ro;
461 fmtinstall('J', Jconv);
462
463 for(i = 0; i < 2; i++) {
464 g = &gens[i];
465 g->gnum = -1;
466 g->low = nsects;
467 g->high = -1;
468 g->count = 0;
469 g->head = nil;
470 g->tail = nil;
471 }
472
473 for(i = 0; i < nsects; i++) {
474 readdata(i, hdr, MAXHDR, 0);
475 if(memcmp(hdr, magic, MAGSIZE) == 0) {
476 n = MAGSIZE + getc3(&hdr[MAGSIZE], &u);
477 getc3(&hdr[n], &v);
478 if(debug)
479 fprint(2, "%d: %ld %ld\n", i, u, v);
480 for(j = 0; j < 2; j++) {
481 g = &gens[j];
482 if(g->gnum == u) {
483 g->count++;
484 if(v < g->low)
485 g->low = v;
486 if(v > g->high)
487 g->high = v;
488 break;
489 }
490 else if(g->gnum < 0) {
491 g->gnum = u;
492 g->count = 1;
493 g->low = v;
494 g->high = v;
495 break;
496 }
497 }
498 if(j == 2)
499 damaged("unexpected generation");
500 }
501 else if(hdr[0] == 0xFF) {
502 nfree++;
503 s = emalloc9p(sizeof(Sect));
504 s->sect = i;
505 s->next = freehead;
506 freehead = s;
507 if(freetail == nil)
508 freetail = s;
509 }
510 else
511 nbad++;
512 }
513
514 if(nbad > 0)
515 damaged("bad sectors");
516
517 if(gens[0].gnum < 0)
518 damaged("no data");
519
520 if(gens[1].gnum < 0) { // Window 3 death
521 if(diags)
522 fprint(2, "%s: window 3 damage\n", argv0);
523 g = &gens[1];
524 g->gnum = gens[0].gnum + 1;
525 g->low = 0;
526 g->high = 0;
527 g->count = 1;
528 if(!readonly)
529 newsum(g, 0);
530 }
531
532 if(gens[0].gnum > gens[1].gnum)
533 gswap();
534
535 for(i = 0; i < 2; i++) {
536 g = &gens[i];
537 n = g->count;
538 if(n <= g->high - g->low)
539 damaged("missing sectors");
540 g->vect = emalloc9p(n * sizeof(Sect *));
541 for(j = 0; j < n; j++) {
542 s = emalloc9p(sizeof(Sect));
543 s->sect = -1;
544 g->vect[j] = s;
545 }
546 }
547
548 if(debug) {
549 for(j = 0; j < 2; j++) {
550 g = &gens[j];
551 print("%d\t%d\t%d-%d\n", g->gnum, g->count, g->low, g->high);
552 }
553 }
554
555 for(i = 0; i < nsects; i++) {
556 readdata(i, hdr, MAXHDR, 0);
557 if(memcmp(hdr, magic, MAGSIZE) == 0) {
558 n = MAGSIZE + getc3(&hdr[MAGSIZE], &u);
559 n += getc3(&hdr[n], &v);
560 g = nil;
561 for(j = 0; j < 2; j++) {
562 g = &gens[j];
563 if(g->gnum == u)
564 break;
565 }
566 if(j == 2)
567 damaged("generation botch");
568 s = g->vect[v - g->low];
569 s->seq = v;
570 s->toff = n;
571 if(s->sect < 0)
572 s->sect = i;
573 else if(v == g->high && g->dup == nil) {
574 s = emalloc9p(sizeof(Sect));
575 s->sect = i;
576 g->dup = s;
577 }
578 else
579 damaged("dup block");
580 }
581 }
582
583 for(j = 0; j < 2; j++) {
584 g = &gens[j];
585 for(i = 0; i < g->count; i++) {
586 s = g->vect[i];
587 if(g->tail == nil)
588 g->head = s;
589 else
590 g->tail->next = s;
591 g->tail = s;
592 s->next = nil;
593 }
594 free(g->vect);
595 }
596
597 cursect = -1;
598
599 if(!readonly) {
600 checkdata();
601 checksweep();
602 }
603
604 load0(1);
605 load0(0);
606
607 if(ltime != 0) {
608 u = now();
609 if(u < ltime) {
610 delta = ltime - u;
611 if(diags)
612 fprint(2, "%s: check clock: delta = %lud\n", argv0, delta);
613 }
614 }
615
616 limit = 80 * nsects * sectsize / 100;
617 maxwrite = sectsize - MAXHDR - Nwrite - Nsum;
618 if(maxwrite > WRSIZE)
619 maxwrite = WRSIZE;
620 }
621
622 static int
sputw(Sect * s,Jrec * j,int mtime,Extent * x,void * a)623 sputw(Sect *s, Jrec *j, int mtime, Extent *x, void *a)
624 {
625 ulong t;
626 int err, n, r;
627 uchar buff[Nmax], type[1];
628
629 if(debug)
630 fprint(2, "put %J\n", j);
631
632 if(mtime) {
633 t = j->mtime;
634 if(s->time == NOTIME) {
635 put4(buff, t);
636 if(!writedata(1, s->sect, buff, 4, s->toff)) {
637 dupsect(s, 1);
638 writedata(0, s->sect, buff, 4, s->toff);
639 }
640 s->time = t;
641 j->mtime = 0;
642 }
643 else {
644 j->mtime = t - s->time;
645 s->time = t;
646 }
647 }
648
649 n = convJ2M(j, buff);
650 if(n < 0)
651 damaged("convJ2M");
652
653 // Window 4
654 err = 2;
655 for(;;) {
656 err--;
657 if(!err)
658 dupsect(s, 1); // Window 4 damage
659 t = s->coff + 1;
660 if(!writedata(err, s->sect, buff, n, t))
661 continue;
662
663 t += n;
664 r = n;
665 if(x != nil) {
666 x->sect = s->sect;
667 x->addr = t;
668 if(!writedata(err, s->sect, a, j->size, t))
669 continue;
670 t += j->size;
671 r += j->size;
672 }
673
674 type[0] = j->type;
675 if(!writedata(err, s->sect, type, 1, s->coff))
676 continue;
677 r++;
678 break;
679 }
680 s->coff = t;
681 return r;
682 }
683
684 static void
summarize(void)685 summarize(void)
686 {
687 Gen *g;
688 uchar *b;
689 Entry *e;
690 Extent *x;
691 Jrec j, sum;
692 Sect *s, *t;
693 ulong off, ctime;
694 int n, bytes, more, mtime, sumd;
695
696 g = &gens[eparity];
697 s = g->head;
698 g->head = s->next;
699 if(g->head == nil)
700 g->tail = nil;
701 g = &gens[eparity^1];
702 t = g->tail;
703 b = sectbuff;
704 x = nil;
705
706 if(debug)
707 fprint(2, "summarize\n");
708
709 for(;;) { // Window 1
710 readdata(s->sect, b, sectsize, 0);
711 off = s->toff;
712 ctime = get4(&b[off]);
713 off += 4;
714 sumd = 0;
715
716 cursect = s->sect;
717 while(b[off] != 0xFF) {
718 n = convM2J(&j, &b[off]);
719 if(n < 0)
720 damaged("bad Jrec");
721 if(debug)
722 fprint(2, "read %J\n", &j);
723 off += n;
724 bytes = n;
725 mtime = 0;
726 switch(j.type) {
727 case FT_create:
728 ctime += j.mtime;
729 mtime = 1;
730 create:
731 e = elookup(j.fnum);
732 if(e == nil)
733 continue;
734 break;
735 case FT_chmod:
736 e = elookup(j.fnum);
737 if(e == nil || j.mnum != e->mnum)
738 continue;
739 break;
740 case FT_REMOVE:
741 e = elookup(j.fnum);
742 if(e == nil)
743 continue;
744 break;
745 case FT_trunc:
746 ctime += j.mtime;
747 mtime = 1;
748 e = elookup(j.tnum);
749 if(e == nil) {
750 if(debug)
751 fprint(2, "-> create\n");
752 j.type = FT_create;
753 goto create;
754 }
755 break;
756 case FT_AWRITE:
757 goto write;
758 case FT_WRITE:
759 ctime += j.mtime;
760 mtime = 1;
761 write:
762 e = elookup(j.fnum);
763 if(e == nil) {
764 off += j.size;
765 continue;
766 }
767 x = esum(e, s->sect, off, &more);
768 if(x == nil) {
769 damaged("missing extent");
770 off += j.size;
771 continue;
772 }
773 if(more) {
774 j.type = FT_AWRITE;
775 mtime = 0;
776 }
777 bytes += j.size;
778 break;
779 case FT_SUMMARY:
780 case FT_SUMBEG:
781 case FT_SUMEND:
782 continue;
783 default:
784 damaged("summarize botch");
785 }
786
787 if(!sumd) {
788 if(t->coff + Nsumbeg >= sectsize - 1)
789 t = newsum(g, t->seq + 1);
790 sum.type = FT_SUMBEG;
791 sum.seq = s->seq;
792 if(debug)
793 fprint(2, "+ %J\n", &sum);
794 t->sum += sputw(t, &sum, 0, nil, nil);
795 if(t->sum >= Nsum)
796 t->sum = Nsum;
797 sumd = 1;
798 }
799
800 if(t->coff + bytes >= sectsize - Nsum + t->sum - 1)
801 t = newsum(g, t->seq + 1);
802
803 if(mtime)
804 j.mtime = ctime;
805
806 switch(j.type) {
807 case FT_AWRITE:
808 case FT_WRITE:
809 sputw(t, &j, mtime, x, &b[off]);
810 off += j.size;
811 break;
812 default:
813 sputw(t, &j, mtime, nil, nil);
814 }
815 }
816 cursect = -1;
817
818 if(t->coff + Nsumbeg >= sectsize - 1)
819 t = newsum(g, t->seq + 1);
820 if(sumd)
821 sum.type = FT_SUMEND;
822 else {
823 sum.type = FT_SUMMARY;
824 sum.seq = s->seq;
825 }
826 if(debug)
827 fprint(2, "+ %J\n", &sum);
828 t->sum += sputw(t, &sum, 0, nil, nil);
829 if(t->sum >= Nsum)
830 t->sum = Nsum;
831
832 // Window 2
833 freesect(s);
834 g = &gens[eparity];
835 s = g->head;
836 if(s == nil) {
837 // Window 3
838 g->gnum += 2;
839 newsum(g, 0);
840 eparity ^= 1;
841 return;
842 }
843
844 if(nfree >= Nfree)
845 return;
846
847 g->head = s->next;
848 if(g->head == nil)
849 g->tail = nil;
850 g = &gens[eparity^1];
851 }
852 }
853
854 char *
need(int bytes)855 need(int bytes)
856 {
857 Gen *g;
858 int sums;
859 Sect *s, *t;
860
861 sums = 0;
862 for(;;) {
863 s = gens[eparity].tail;
864 if(s->coff + bytes < sectsize - Nsum + s->sum - 1)
865 return nil;
866
867 if(nfree >= Nfree)
868 break;
869
870 if(sums == 2) {
871 readonly = 1;
872 return "generation full";
873 }
874
875 summarize();
876 sums++;
877 }
878
879 g = &gens[eparity];
880 t = getsect();
881 t->seq = g->tail->seq + 1;
882 newsect(g, t);
883 return nil;
884 }
885
886 void
putw(Jrec * j,int mtime,Extent * x,void * a)887 putw(Jrec *j, int mtime, Extent *x, void *a)
888 {
889 sputw(gens[eparity].tail, j, mtime, x, a);
890 }
891
892 void
put(Jrec * j,int mtime)893 put(Jrec *j, int mtime)
894 {
895 sputw(gens[eparity].tail, j, mtime, nil, nil);
896 }
897