1implement Styxpersist; 2 3# 4# Copyright © 2004 Vita Nuova Holdings Limited 5# 6 7include "sys.m"; 8 sys: Sys; 9include "draw.m"; 10include "styx.m"; 11 styx: Styx; 12 Tmsg, Rmsg, NOFID, NOTAG: import styx; 13include "rand.m"; 14 rand: Rand; 15include "factotum.m"; 16 factotum: Factotum; 17include "styxpersist.m"; 18 19NOTOPEN, DEAD, AUTH, OPEN: con iota; 20NTAGHASH: con 32; 21MAXBACKOFF: con 30*1000; 22Estale: con "unable to reopen file"; 23Ebadtag: con "bad tag"; 24Epartial: con "operation possibly not completed"; 25Etypemismatch: con "tag type mismatch"; 26Debug: con 0; 27 28Noqid: con Sys->Qid(big 0, 0, 0); 29Nprocs: con 1; 30Erroronpartial: con 1; 31 32Table: adt[T] { 33 items: array of list of (int, T); 34 nilval: T; 35 36 new: fn(nslots: int, nilval: T): ref Table[T]; 37 add: fn(t: self ref Table, id: int, x: T): int; 38 del: fn(t: self ref Table, id: int): int; 39 find: fn(t: self ref Table, id: int): T; 40}; 41 42Fid: adt { 43 fid: int; 44 state: int; 45 omode: int; 46 qid: Sys->Qid; 47 uname: string; 48 aname: string; 49 authed: int; 50 path: list of string; # in reverse order. 51}; 52 53Tag: adt { 54 m: ref Tmsg; 55 seq: int; 56 dead: int; 57 next: cyclic ref Tag; 58}; 59 60Root: adt { 61 refcount: int; 62 attached: chan of int; # [1]; holds attached status: -1 (can't), 0 (haven't), 1 (attached) 63 fid: int; 64 qid: Sys->Qid; 65 uname: string; 66 aname: string; 67}; 68 69keyspec: string; 70 71tags := array[NTAGHASH] of ref Tag; 72fids: ref Table[ref Fid]; 73ntags := 0; 74seqno := 0; 75 76doneversion := 0; 77msize := 0; 78ver: string; 79 80cfd, sfd: ref Sys->FD; 81tmsg: chan of ref Tmsg; # t-messages received from client 82rmsg: chan of ref Rmsg; # r-messages received from server. 83rmsgpid := -1; 84 85token: chan of (int, chan of (ref Fid, ref Root)); # [Nprocs] of (procid, workchan) 86procrmsg: array of chan of ref Rmsg; 87 88init(clientfd: ref Sys->FD, usefac: int, kspec: string): (chan of chan of ref Sys->FD, string) 89{ 90 sys = load Sys Sys->PATH; 91 styx = load Styx Styx->PATH; 92 if(styx == nil) 93 return (nil, sys->sprint("cannot load %q: %r", Styx->PATH)); 94 styx->init(); 95 rand = load Rand Rand->PATH; 96 if (rand == nil) 97 return (nil, sys->sprint("cannot load %q: %r", Rand->PATH)); 98 rand->init(sys->millisec()); 99 if(usefac){ 100 factotum = load Factotum Factotum->PATH; 101 if(factotum == nil) 102 return (nil, sys->sprint("cannot load %q: %r", Rand->PATH)); 103 factotum->init(); 104 } 105 106 keyspec = kspec; 107 connectc := chan of chan of ref Sys->FD; 108 spawn styxpersistproc(clientfd, connectc); 109 return (connectc, nil); 110} 111 112styxpersistproc(clientfd: ref Sys->FD, connectc: chan of chan of ref Sys->FD) 113{ 114 fids = Table[ref Fid].new(11, nil); 115 rmsg = chan of ref Rmsg; 116 tmsg = chan of ref Tmsg; 117 cfd = clientfd; 118 spawn tmsgreader(); 119 connect(connectc); 120 for(;;)alt{ 121 m := <-tmsg => 122 if(m == nil || tagof(m) == tagof(Tmsg.Readerror)) 123 quit(); 124 t := newtag(m); 125 if(t == nil){ 126 sendrmsg(ref Rmsg.Error(m.tag, Ebadtag)); 127 continue; 128 } 129 if((rm := handletmsg(t)) != nil){ 130 sendrmsg(rm); 131 gettag(m.tag, 1); 132 }else{ 133 # XXX could be quicker about this as we don't rewrite messages 134 sendtmsg(m); 135 } 136 m := <-rmsg => 137 if(m == nil || tagof(m) == tagof(Tmsg.Readerror)){ 138 if(Debug) sys->print("**************** reconnect {\n"); 139 do{ 140 connect(connectc); 141 } while(resurrectfids() == 0); 142 resurrecttags(); 143 if(Debug) sys->print("************** done reconnect }\n"); 144 continue; 145 } 146 147 t := gettag(m.tag, 1); 148 if(t == nil){ 149 log(sys->sprint("unexpected tag %d, %s", m.tag, m.text())); 150 continue; 151 } 152 if((e := handlermsg(m, t.m)) != nil) 153 log(e); 154 else{ 155 # XXX could be quicker about this as we don't rewrite messages 156 sendrmsg(m); 157 } 158 } 159} 160 161quit() 162{ 163 log("quitting...\n"); 164 # XXX shutdown properly 165 exit; 166} 167 168log(s: string) 169{ 170 sys->fprint(sys->fildes(2), "styxpersist: %s\n", s); 171} 172 173handletmsg(t: ref Tag): ref Rmsg 174{ 175 fid := NOFID; 176 pick m := t.m { 177 Flush => 178 if(gettag(m.oldtag, 0) == nil) 179 return ref Rmsg.Flush(m.tag); 180 * => 181 fid = tmsgfid(m); 182 } 183 if(fid != NOFID){ 184 f := getfid(fid); 185 if(f.state == DEAD){ 186 if(tagof(t.m) == tagof(Tmsg.Clunk)){ 187 fids.del(f.fid); 188 return ref Rmsg.Clunk(t.m.tag); 189 } 190 return ref Rmsg.Error(t.m.tag, Estale); 191 } 192 } 193 return nil; 194} 195 196handlermsg(rm: ref Rmsg, tm: ref Tmsg): string 197{ 198 if(tagof(rm) == tagof(Rmsg.Error) && 199 tagof(tm) != tagof(Tmsg.Remove) && 200 tagof(tm) != tagof(Tmsg.Clunk)) 201 return nil; 202 if(tagof(rm) != tagof(Rmsg.Error) && rm.mtype() != tm.mtype()+1) 203 return "type mismatch, got "+rm.text()+", reply to "+tm.text(); 204 205 pick m := tm { 206 Auth => 207 fid := newfid(m.afid); # XXX should we be concerned about this failing? 208 fid.state = AUTH; 209 Attach => 210 fid := newfid(m.fid); 211 fid.uname = m.uname; 212 fid.aname = m.aname; 213 if(m.afid != NOFID) 214 fid.authed = 1; 215 Walk => 216 fid := getfid(m.fid); 217 qids: array of Sys->Qid; 218 n := 0; 219 pick r := rm { 220 Walk => 221 qids = r.qids; 222 } 223 if(len qids != len m.names) 224 return nil; 225 if(m.fid != m.newfid){ 226 newfid := newfid(m.newfid); 227 *newfid = *fid; 228 newfid.fid = m.newfid; 229 fid = newfid; 230 } 231 for(i := 0; i < len qids; i++){ 232 if(m.names[i] == ".."){ 233 if(fid.path != nil) 234 fid.path = tl fid.path; 235 }else{ 236 fid.path = m.names[i] :: fid.path; 237 } 238 fid.qid = qids[i]; 239 } 240 Open => 241 fid := getfid(m.fid); 242 fid.state = OPEN; 243 fid.omode = m.mode; 244 pick r := rm { 245 Open => 246 fid.qid = r.qid; 247 } 248 Create => 249 fid := getfid(m.fid); 250 fid.state = OPEN; 251 fid.omode = m.mode; 252 pick r := rm { 253 Create => 254 fid.qid = r.qid; 255 } 256 Clunk or 257 Remove => 258 fids.del(m.fid); 259 Wstat => 260 if(m.stat.name != nil){ 261 fid := getfid(m.fid); 262 fid.path = m.stat.name :: tl fid.path; 263 } 264 } 265 return nil; 266} 267 268# connect to destination with exponential backoff, setting sfd. 269connect(connectc: chan of chan of ref Sys->FD) 270{ 271 reply := chan of ref Sys->FD; 272 sfd = nil; 273 backoff := 0; 274 for(;;){ 275 connectc <-= reply; 276 fd := <-reply; 277 if(fd != nil){ 278 kill(rmsgpid, "kill"); 279 sfd = fd; 280 sync := chan of int; 281 spawn rmsgreader(fd, sync); 282 rmsgpid = <-sync; 283 if(version() != -1) 284 return; 285 sfd = nil; 286 } 287 if(backoff == 0) 288 backoff = 1000 + rand->rand(500) - 250; 289 else if(backoff < MAXBACKOFF) 290 backoff = backoff * 3 / 2; 291 sys->sleep(backoff); 292 } 293} 294 295# first time we use the version offered by the client, 296# and record it; subsequent times we offer the response 297# recorded initially. 298version(): int 299{ 300 if(doneversion) 301 sendtmsg(ref Tmsg.Version(NOTAG, msize, ver)); 302 else{ 303 m := <-tmsg; 304 if(m == nil) 305 quit(); 306 if(m == nil || tagof(m) != tagof(Tmsg.Version)){ 307 log("invalid initial version message: "+m.text()); 308 quit(); 309 } 310 sendtmsg(m); 311 } 312 if((gm := <-rmsg) == nil) 313 return -1; 314 pick m := gm { 315 Readerror => 316 return -1; 317 Version => 318 if(doneversion && (m.msize != msize || m.version != ver)){ 319 log("wrong msize/version on reconnect"); 320 # XXX is there any hope here - we could quit. 321 return -1; 322 } 323 if(!doneversion){ 324 msize = m.msize; 325 ver = m.version; 326 doneversion = 1; 327 sendrmsg(m); 328 } 329 return 0; 330 * => 331 log("invalid reply to Tversion: "+m.text()); 332 return -1; 333 } 334} 335 336resurrecttags() 337{ 338 # make sure that we send the tmsgs in the same order that 339 # they were sent originally. 340 all := array[ntags] of ref Tag; 341 n := 0; 342 for(i := 0; i < len tags; i++){ 343 for(t := tags[i]; t != nil; t = t.next){ 344 fid := tmsgfid(t.m); 345 if(fid != NOFID && (f := getfid(fid)) != nil){ 346 if(f.state == DEAD){ 347 sendrmsg(ref Rmsg.Error(t.m.tag, Estale)); 348 t.dead = 1; 349 continue; 350 } 351 if(Erroronpartial){ 352 partial := 0; 353 pick m := t.m { 354 Create => 355 partial = 1; 356 Remove => 357 partial = 1; 358 Wstat => 359 partial = (m.stat.name != nil && f.path != nil && hd f.path != m.stat.name); 360 Write => 361 partial = (f.qid.qtype & Sys->QTAPPEND); 362 } 363 if(partial) 364 sendrmsg(ref Rmsg.Error(t.m.tag, Epartial)); 365 } 366 } 367 all[n++] = t; 368 } 369 } 370 all = all[0:n]; 371 sort(all); 372 for(i = 0; i < len all; i++){ 373 t := all[i]; 374 pick m := t.m { 375 Flush => 376 ot := gettag(m.oldtag, 0); 377 if(ot == nil || ot.dead){ 378 sendrmsg(ref Rmsg.Flush(t.m.tag)); 379 t.dead = 1; 380 continue; 381 } 382 } 383 sendtmsg(t.m); 384 } 385 tags = array[len tags] of ref Tag; 386 ntags = 0; 387 for(i = 0; i < len all; i++) 388 if(all[i].dead == 0) 389 newtag(all[i].m); 390} 391 392# re-open all the old fids, if possible. 393# use up to Nprocs processes to keep latency down. 394resurrectfids(): int 395{ 396 procrmsg = array[Nprocs] of {* => chan[1] of ref Rmsg}; 397 spawn rmsgmarshal(finish := chan of int); 398 getroot := chan of (int, string, string, chan of ref Root); 399 usedroot := chan of ref Root; 400 spawn fidproc(getroot, usedroot); 401 token = chan[Nprocs] of (int, chan of (ref Fid, ref Root)); 402 for(i := 0; i < Nprocs; i++) 403 token <-= (i, nil); 404 405 for(i = 0; i < len fids.items; i++){ 406 for(fl := fids.items[i]; fl != nil; fl = tl fl){ 407 fid := (hd fl).t1; 408 (procid, workc) := <-token; 409 getroot <-= (1, fid.uname, fid.aname, reply := chan of ref Root); 410 root := <-reply; 411 if(workc == nil){ 412 workc = chan of (ref Fid, ref Root); 413 spawn workproc(procid, workc, usedroot); 414 } 415 workc <-= (fid, root); 416 } 417 } 418 419 for(i = 0; i < Nprocs; i++){ 420 (nil, workc) := <-token; 421 if(workc != nil) 422 workc <-= (nil, nil); 423 } 424 for(i = 0; i < Nprocs; i++){ 425 getroot <-= (0, nil, nil, reply := chan of ref Root); 426 root := <-reply; 427 if(<-root.attached > 0) 428 clunk(0, root.fid); 429 } 430 usedroot <-= nil; 431 return <-finish; 432} 433 434workproc(procid: int, workc: chan of (ref Fid, ref Root), usedroot: chan of ref Root) 435{ 436 while(((fid, root) := <-workc).t0 != nil){ 437 # mark fid as dead only if it's a genuine server error, not if 438 # the server has just hung up. 439 if((err := resurrectfid(procid, fid, root)) != nil && sfd != nil){ 440 log(err); 441 fid.state = DEAD; 442 } 443 usedroot <-= root; 444 token <-= (procid, workc); 445 } 446} 447 448resurrectfid(procid: int, fid: ref Fid, root: ref Root): string 449{ 450 if(fid.state == AUTH) 451 return "auth fid discarded"; 452 attached := <-root.attached; 453 if(attached == -1){ 454 root.attached <-= -1; 455 return "root attach failed"; 456 } 457 if(!attached || root.uname != fid.uname || root.aname != fid.aname){ 458 if(attached) 459 clunk(procid, root.fid); 460 afid := NOFID; 461 if(fid.authed){ 462 afid = fid.fid - 1; # see unusedfid() 463 if((err := auth(procid, afid, root.uname, root.aname)) != nil){ 464 log(err); 465 afid = -1; 466 } 467 } 468 (err, qid) := attach(procid, root.fid, afid, fid.uname, fid.aname); 469 if(afid != NOFID) 470 clunk(procid, afid); 471 if(err != nil){ 472 root.attached <-= -1; 473 return "attach failed: "+err; 474 } 475 root.uname = fid.uname; 476 root.aname = fid.aname; 477 root.qid = qid; 478 } 479 root.attached <-= 1; 480 (err, qid) := walk(procid, root.fid, fid.fid, fid.path, root.qid); 481 if(err != nil) 482 return err; 483 if(fid.state == OPEN && (err = openfid(procid, fid)) != nil){ 484 clunk(procid, fid.fid); 485 return err; 486 } 487 return nil; 488} 489 490openfid(procid: int, fid: ref Fid): string 491{ 492 (err, qid) := open(procid, fid.fid, fid.omode); 493 if(err != nil) 494 return err; 495 if(qid.path != fid.qid.path || qid.qtype != fid.qid.qtype) 496 return "qid mismatch on reopen"; 497 return nil; 498} 499 500# store up to Nprocs separate root fids and dole them out to those that want them. 501fidproc(getroot: chan of (int, string, string, chan of ref Root), usedroot: chan of ref Root) 502{ 503 roots := array[Nprocs] of ref Root; 504 n := 0; 505 maxfid := -1; 506 for(;;)alt{ 507 (match, uname, aname, reply) := <-getroot => 508 for(i := 0; i < n; i++) 509 if(match && roots[i].uname == uname && roots[i].aname == aname) 510 break; 511 if(i == n) 512 for(i = 0; i < n; i++) 513 if(roots[i].refcount == 0) 514 break; 515 if(i == n){ 516 maxfid = unusedfid(maxfid); 517 roots[n] = ref Root(0, chan[1] of int, maxfid, Noqid, uname, aname); 518 roots[n++].attached <-= 0; 519 } 520 roots[i].refcount++; 521 reply <-= roots[i]; 522 r := <-usedroot => 523 if(r == nil) 524 exit; 525 r.refcount--; 526 } 527} 528 529clunk(procid: int, fid: int) 530{ 531 pick m := fcall(ref Tmsg.Clunk(procid, fid)) { 532 Error => 533 if(sfd != nil) 534 log("error on clunk: " + m.ename); 535 } 536} 537 538attach(procid, fid, afid: int, uname, aname: string): (string, Sys->Qid) 539{ 540 pick m := fcall(ref Tmsg.Attach(procid, fid, afid, uname, aname)) { 541 Attach => 542 return (nil, m.qid); 543 Error => 544 return (m.ename, Noqid); 545 } 546 return (nil, Noqid); # not reached 547} 548 549read(procid, fid: int, buf: array of byte): (int, string) 550{ 551 # XXX assume that offsets are ignored of auth fid reads/writes 552 pick m := fcall(ref Tmsg.Read(procid, fid, big 0, len buf)) { 553 Error => 554 return (-1, m.ename); 555 Read => 556 buf[0:] = m.data; 557 return (len m.data, nil); 558 } 559 return (-1, nil); # not reached 560} 561 562write(procid, fid: int, buf: array of byte): (int, string) 563{ 564 # XXX assume that offsets are ignored of auth fid reads/writes 565 pick m := fcall(ref Tmsg.Write(procid, fid, big 0, buf)) { 566 Error => 567 sys->werrstr(m.ename); 568 return (-1, sys->sprint("%r")); 569 Write => 570 return (m.count, nil); 571 } 572 return (-1, nil); # not reached 573} 574 575auth(procid, fid: int, uname, aname: string): string 576{ 577 if(factotum == nil) 578 return "no factotum available"; 579 580 pick m := fcall(ref Tmsg.Auth(procid, fid, uname, aname)) { 581 Error => 582 return m.ename; 583 } 584 585 readc := chan of (array of byte, chan of (int, string)); 586 writec := chan of (array of byte, chan of (int, string)); 587 done := chan of (ref Factotum->Authinfo, string); 588 spawn factotum->genproxy(readc, writec, done, 589 sys->open("/mnt/factotum/rpc", Sys->ORDWR), 590 "proto=p9any role=client "+keyspec); 591 for(;;)alt{ 592 (buf, reply) := <-readc => 593 reply <-= read(procid, fid, buf); 594 (buf, reply) := <-writec => 595 reply <-= write(procid, fid, buf); 596 (authinfo, err) := <-done => 597 if(authinfo == nil){ 598 clunk(procid, fid); 599 return err; 600 } 601 # XXX check that authinfo.cuid == uname? 602 return nil; 603 } 604} 605 606# path is in reverse order; assume fid != newfid on entry. 607walk(procid: int, fid, newfid: int, path: list of string, qid: Sys->Qid): (string, Sys->Qid) 608{ 609 names := array[len path] of string; 610 for(i := len names - 1; i >= 0; i--) 611 (names[i], path) = (hd path, tl path); 612 do{ 613 w := names; 614 if(len w > Styx->MAXWELEM) 615 w = w[0:Styx->MAXWELEM]; 616 names = names[len w:]; 617 pick m := fcall(ref Tmsg.Walk(procid, fid, newfid, w)) { 618 Error => 619 if(newfid == fid) 620 clunk(procid, newfid); 621 return ("walk error: "+m.ename, Noqid); 622 Walk => 623 if(len m.qids != len w){ 624 if(newfid == fid) 625 clunk(procid, newfid); 626 return ("walk: file not found", Noqid); 627 } 628 if(len m.qids > 0) 629 qid = m.qids[len m.qids - 1]; 630 fid = newfid; 631 } 632 }while(len names > 0); 633 return (nil, qid); 634} 635 636open(procid: int, fid: int, mode: int): (string, Sys->Qid) 637{ 638 pick m := fcall(ref Tmsg.Open(procid, fid, mode)) { 639 Error => 640 return ("open: "+m.ename, Noqid); 641 Open => 642 return (nil, m.qid); # XXX what if iounit doesn't match the original? 643 } 644 return (nil, Noqid); # not reached 645} 646 647fcall(m: ref Tmsg): ref Rmsg 648{ 649 sendtmsg(m); 650 pick rm := <-procrmsg[m.tag] { 651 Readerror => 652 procrmsg[m.tag] <-= rm; 653 return ref Rmsg.Error(rm.tag, rm.error); 654 Error => 655 return rm; 656 * => 657 if(rm.mtype() != m.mtype()+1) 658 return ref Rmsg.Error(m.tag, Etypemismatch); 659 return rm; 660 } 661} 662 663# find an unused fid (and make sure that the one before it is unused 664# too, in case we want to use it for an auth fid); 665unusedfid(maxfid: int): int 666{ 667 for(f := maxfid + 1; ; f++) 668 if(fids.find(f) == nil && fids.find(f+1) == nil) 669 return f + 1; 670 abort("no unused fids - i don't believe it"); 671 return 0; 672} 673 674# XXX what about message length limitations? 675sendtmsg(m: ref Tmsg) 676{ 677 if(Debug) sys->print("%s\n", m.text()); 678 d := m.pack(); 679 if(sys->write(sfd, d, len d) != len d) 680 log(sys->sprint("tmsg write failed: %r")); # XXX could signal to redial 681} 682 683sendrmsg(m: ref Rmsg) 684{ 685 d := m.pack(); 686 if(sys->write(cfd, d, len d) != len d){ 687 log(sys->sprint("rmsg write failed: %r")); 688 quit(); 689 } 690} 691 692rmsgmarshal(finish: chan of int) 693{ 694 for(;;)alt{ 695 finish <-= 1 => 696 exit; 697 m := <-rmsg => 698 if(m == nil || tagof(m) == tagof(Rmsg.Readerror)){ 699 sfd = nil; 700 for(i := 0; i < Nprocs; i++) 701 procrmsg[i] <-= ref Rmsg.Readerror(NOTAG, "hung up"); 702 finish <-= 0; 703 exit; 704 } 705 if(m.tag >= Nprocs){ 706 log("invalid reply message"); 707 break; 708 } 709 # XXX if the server replies with a tag that no-one's waiting for. we'll lock up. 710 # (but is it much of a concern, given no flushes, etc?) 711 procrmsg[m.tag] <-= m; 712 } 713} 714 715rmsgreader(fd: ref Sys->FD, sync: chan of int) 716{ 717 sync <-= sys->pctl(0, nil); 718 m: ref Rmsg; 719 do { 720 m = Rmsg.read(fd, msize); 721 if(Debug) sys->print("%s\n", m.text()); 722 rmsg <-= m; 723 } while(m != nil && tagof(m) != tagof(Tmsg.Readerror)); 724} 725 726tmsgreader() 727{ 728 m: ref Tmsg; 729 do{ 730 m = Tmsg.read(cfd, msize); 731 tmsg <-= m; 732 } while(m != nil && tagof(m) != tagof(Tmsg.Readerror)); 733} 734 735abort(s: string) 736{ 737 log(s); 738 raise "abort"; 739} 740 741tmsgfid(t: ref Tmsg): int 742{ 743 fid := NOFID; 744 pick m := t { 745 Attach => 746 fid = m.afid; 747 Walk => 748 fid = m.fid; 749 Open => 750 fid = m.fid; 751 Create => 752 fid = m.fid; 753 Read => 754 fid = m.fid; 755 Write => 756 fid = m.fid; 757 Clunk or 758 Stat or 759 Remove => 760 fid = m.fid; 761 Wstat => 762 fid = m.fid; 763 } 764 return fid; 765} 766 767blankfid: Fid; 768newfid(fid: int): ref Fid 769{ 770 f := ref blankfid; 771 f.fid = fid; 772 if(fids.add(fid, f) == 0){ 773 abort("duplicate fid "+string fid); 774 } 775 return f; 776} 777 778getfid(fid: int): ref Fid 779{ 780 return fids.find(fid); 781} 782 783newtag(m: ref Tmsg): ref Tag 784{ 785 # XXX what happens if the client sends a duplicate tag? 786 t := ref Tag(m, seqno++, 0, nil); 787 slot := t.m.tag & (NTAGHASH - 1); 788 t.next = tags[slot]; 789 tags[slot] = t; 790 ntags++; 791 return t; 792} 793 794gettag(tag: int, destroy: int): ref Tag 795{ 796 slot := tag & (NTAGHASH - 1); 797 prev: ref Tag; 798 for(t := tags[slot]; t != nil; t = t.next){ 799 if(t.m.tag == tag) 800 break; 801 prev = t; 802 } 803 if(t == nil || !destroy) 804 return t; 805 if(prev == nil) 806 tags[slot] = t.next; 807 else 808 prev.next = t.next; 809 ntags--; 810 return t; 811} 812 813Table[T].new(nslots: int, nilval: T): ref Table[T] 814{ 815 if(nslots == 0) 816 nslots = 13; 817 return ref Table[T](array[nslots] of list of (int, T), nilval); 818} 819 820Table[T].add(t: self ref Table[T], id: int, x: T): int 821{ 822 slot := id % len t.items; 823 for(q := t.items[slot]; q != nil; q = tl q) 824 if((hd q).t0 == id) 825 return 0; 826 t.items[slot] = (id, x) :: t.items[slot]; 827 return 1; 828} 829 830Table[T].del(t: self ref Table[T], id: int): int 831{ 832 slot := id % len t.items; 833 834 p: list of (int, T); 835 r := 0; 836 for(q := t.items[slot]; q != nil; q = tl q){ 837 if((hd q).t0 == id){ 838 p = joinip(p, tl q); 839 r = 1; 840 break; 841 } 842 p = hd q :: p; 843 } 844 t.items[slot] = p; 845 return r; 846} 847 848Table[T].find(t: self ref Table[T], id: int): T 849{ 850 for(p := t.items[id % len t.items]; p != nil; p = tl p) 851 if((hd p).t0 == id) 852 return (hd p).t1; 853 return t.nilval; 854} 855 856sort(a: array of ref Tag) 857{ 858 mergesort(a, array[len a] of ref Tag); 859} 860 861mergesort(a, b: array of ref Tag) 862{ 863 r := len a; 864 if (r > 1) { 865 m := (r-1)/2 + 1; 866 mergesort(a[0:m], b[0:m]); 867 mergesort(a[m:], b[m:]); 868 b[0:] = a; 869 for ((i, j, k) := (0, m, 0); i < m && j < r; k++) { 870 if (b[i].seq > b[j].seq) 871 a[k] = b[j++]; 872 else 873 a[k] = b[i++]; 874 } 875 if (i < m) 876 a[k:] = b[i:m]; 877 else if (j < r) 878 a[k:] = b[j:r]; 879 } 880} 881 882kill(pid: int, note: string): int 883{ 884 fd := sys->open("#p/"+string pid+"/ctl", Sys->OWRITE); 885 if(fd == nil || sys->fprint(fd, "%s", note) < 0) 886 return -1; 887 return 0; 888} 889 890# join x to y, leaving result in arbitrary order. 891joinip[T](x, y: list of (int, T)): list of (int, T) 892{ 893 if(len x > len y) 894 (x, y) = (y, x); 895 for(; x != nil; x = tl x) 896 y = hd x :: y; 897 return y; 898} 899