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 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 74 damaged(char *mesg) 75 { 76 sysfatal("damaged filesystem: %s", mesg); 77 } 78 79 static void 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 * 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 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 * 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 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 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 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 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 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 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 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 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 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 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 * 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 887 putw(Jrec *j, int mtime, Extent *x, void *a) 888 { 889 sputw(gens[eparity].tail, j, mtime, x, a); 890 } 891 892 void 893 put(Jrec *j, int mtime) 894 { 895 sputw(gens[eparity].tail, j, mtime, nil, nil); 896 } 897