1 #include "u.h" 2 #include "../port/lib.h" 3 #include "mem.h" 4 #include "dat.h" 5 #include "fns.h" 6 #include "../port/error.h" 7 8 Ref pidalloc; 9 Ref noteidalloc; 10 11 struct 12 { 13 Lock; 14 Proc *arena; 15 Proc *free; 16 }procalloc; 17 18 struct 19 { 20 Lock; 21 Waitq *free; 22 }waitqalloc; 23 24 typedef struct 25 { 26 Lock; 27 Proc *head; 28 Proc *tail; 29 int n; 30 } Schedq; 31 32 int nrdy; 33 int lastreadied; 34 Schedq runq[Nrq]; 35 36 char *statename[] = 37 { /* BUG: generate automatically */ 38 "Dead", 39 "Moribund", 40 "Ready", 41 "Scheding", 42 "Running", 43 "Queueing", 44 "Wakeme", 45 "Broken", 46 "Stopped", 47 "Rendez", 48 }; 49 50 /* 51 * Always splhi()'ed. 52 */ 53 void 54 schedinit(void) /* never returns */ 55 { 56 Proc *p; 57 58 setlabel(&m->sched); 59 if(u){ 60 m->proc = 0; 61 p = u->p; 62 invalidateu(); /* safety first */ 63 u = 0; 64 if(p->state == Running) 65 ready(p); 66 else 67 if(p->state == Moribund) { 68 p->pid = 0; 69 p->state = Dead; 70 /* 71 * Holding locks from pexit: 72 * procalloc, palloc 73 */ 74 mmurelease(p); 75 simpleputpage(p->upage); 76 p->upage = 0; 77 78 p->qnext = procalloc.free; 79 procalloc.free = p; 80 81 unlock(&palloc); 82 unlock(&procalloc); 83 } 84 p->mach = 0; 85 } 86 sched(); 87 } 88 89 void 90 sched(void) 91 { 92 Proc *p; 93 94 if(u){ 95 splhi(); 96 m->cs++; 97 procsave(u->p); 98 if(setlabel(&u->p->sched)){ /* woke up */ 99 p = u->p; 100 p->state = Running; 101 p->mach = m; 102 m->proc = p; 103 procrestore(p); 104 spllo(); 105 return; 106 } 107 gotolabel(&m->sched); 108 } 109 p = runproc(); 110 mapstack(p); 111 gotolabel(&p->sched); 112 } 113 114 /* 115 * this should be called in clock() to implement round robin 116 */ 117 int 118 anyready(void) 119 { 120 return nrdy; 121 } 122 123 /* 124 * this should be called in non-clock traps to implement preemptive scheduling 125 */ 126 int 127 anyhigher(void) 128 { 129 int x; 130 131 x = lastreadied; 132 lastreadied = 0; 133 return nrdy && x >= u->p->priority; 134 } 135 136 enum 137 { 138 Squantum = (HZ+Nrq-1)/Nrq, 139 }; 140 141 void 142 ready(Proc *p) 143 { 144 int s, pri; 145 Schedq *rq; 146 147 s = splhi(); 148 149 /* history counts */ 150 if(p->state == Running){ 151 p->rt++; 152 pri = ((p->art + (p->rt<<1))>>2)/Squantum; 153 } else { 154 p->art = (p->art + (p->rt<<1))>>2; 155 p->rt = 0; 156 pri = p->art/Squantum; 157 } 158 pri = p->basepri - pri; 159 if(pri < 0) 160 pri = 0; 161 162 /* the only intersection between the classes is at PriNormal */ 163 if(pri < PriNormal && p->basepri > PriNormal) 164 pri = PriNormal; 165 p->priority = pri; 166 rq = &runq[p->priority]; 167 168 lock(runq); 169 p->rnext = 0; 170 if(rq->tail) 171 rq->tail->rnext = p; 172 else 173 rq->head = p; 174 rq->tail = p; 175 rq->n++; 176 nrdy++; 177 p->readytime = m->ticks; 178 p->state = Ready; 179 if(p->priority > lastreadied) 180 lastreadied = p->priority; 181 unlock(runq); 182 splx(s); 183 } 184 185 /* 186 * Always called splhi 187 */ 188 #include "io.h" 189 Proc* 190 runproc(void) 191 { 192 int i; 193 Schedq *rq; 194 Proc *p, *l; 195 static ulong lastfair; 196 197 loop: 198 199 /* 200 * find a process that last ran on this processor (affinity), 201 * or one that hasn't moved in a while (load balancing). 202 */ 203 spllo(); 204 for(;;){ 205 /* 206 * Once a second we look for a long waiting process 207 * in the lowest priority queue to make sure nothing 208 * gets starved out by a malfunctioning high priority 209 * process. 210 */ 211 if(m->machno == 0 && m->ticks - lastfair > HZ){ 212 lastfair = m->ticks; 213 for(rq = runq; rq < &runq[Nrq]; rq++){ 214 p = rq->head; 215 if(p){ 216 i = m->ticks - p->readytime; 217 if(i > HZ){ 218 p->art = 0; 219 p->movetime = 0; 220 goto found; 221 } 222 break; 223 } 224 } 225 } 226 227 /* 228 * get highest priority process that this 229 * processor can run given affinity constraints 230 */ 231 for(rq = &runq[Nrq-1]; rq >= runq; rq--){ 232 if(rq->head == 0) 233 continue; 234 for(p = rq->head; p; p = p->rnext){ 235 if(p->mp == m || m->ticks - p->movetime > HZ/2) 236 goto found; 237 } 238 } 239 } 240 241 242 found: 243 splhi(); 244 lock(runq); 245 246 l = 0; 247 for(p = rq->head; p; p = p->rnext){ 248 if(p->mp == m || m->ticks - p->movetime > HZ/2) 249 break; 250 l = p; 251 } 252 253 /* 254 * p->mach==0 only when process state is saved 255 */ 256 if(p == 0 || p->mach){ 257 unlock(runq); 258 goto loop; 259 } 260 if(p->rnext == 0) 261 rq->tail = l; 262 if(l) 263 l->rnext = p->rnext; 264 else 265 rq->head = p->rnext; 266 rq->n--; 267 nrdy--; 268 if(p->state != Ready) 269 print("runproc %s %d %s\n", p->text, p->pid, statename[p->state]); 270 unlock(runq); 271 272 p->state = Scheding; 273 if(p->mp != m) 274 p->movetime = m->ticks; 275 p->mp = m; 276 return p; 277 } 278 279 int 280 canpage(Proc *p) 281 { 282 int ok = 0; 283 284 splhi(); 285 lock(&runq[0]); 286 /* Only reliable way to see if we are Running */ 287 if(p->mach == 0) { 288 p->newtlb = 1; 289 ok = 1; 290 } 291 unlock(&runq[0]); 292 spllo(); 293 294 return ok; 295 } 296 297 Proc* 298 newproc(void) 299 { 300 Proc *p; 301 302 for(;;) { 303 lock(&procalloc); 304 if(p = procalloc.free){ /* assign = */ 305 procalloc.free = p->qnext; 306 p->state = Scheding; 307 p->psstate = "New"; 308 unlock(&procalloc); 309 p->mach = 0; 310 p->qnext = 0; 311 p->nchild = 0; 312 p->nwait = 0; 313 p->waitq = 0; 314 p->pgrp = 0; 315 p->egrp = 0; 316 p->fgrp = 0; 317 p->pdbg = 0; 318 p->fpstate = FPinit; 319 p->kp = 0; 320 p->procctl = 0; 321 p->notepending = 0; 322 p->mp = 0; 323 p->movetime = 0; 324 memset(p->seg, 0, sizeof p->seg); 325 p->pid = incref(&pidalloc); 326 p->noteid = incref(¬eidalloc); 327 if(p->pid==0 || p->noteid==0) 328 panic("pidalloc"); 329 return p; 330 } 331 unlock(&procalloc); 332 resrcwait("no procs"); 333 } 334 return 0; /* not reached */ 335 } 336 337 void 338 procinit0(void) /* bad planning - clashes with devproc.c */ 339 { 340 Proc *p; 341 int i; 342 343 procalloc.free = xalloc(conf.nproc*sizeof(Proc)); 344 procalloc.arena = procalloc.free; 345 346 p = procalloc.free; 347 for(i=0; i<conf.nproc-1; i++,p++) 348 p->qnext = p+1; 349 p->qnext = 0; 350 } 351 352 void 353 sleep1(Rendez *r, int (*f)(void*), void *arg) 354 { 355 Proc *p; 356 int s; 357 358 /* 359 * spl is to allow lock to be called 360 * at interrupt time. lock is mutual exclusion 361 */ 362 s = splhi(); 363 p = u->p; 364 p->r = r; /* early so postnote knows */ 365 lock(r); 366 367 /* 368 * if condition happened, never mind 369 */ 370 if((*f)(arg)){ 371 p->r = 0; 372 unlock(r); 373 splx(s); 374 return; 375 } 376 377 /* 378 * now we are committed to 379 * change state and call scheduler 380 */ 381 if(r->p){ 382 print("double sleep %d %d\n", r->p->pid, p->pid); 383 dumpstack(); 384 } 385 p->state = Wakeme; 386 r->p = p; 387 unlock(r); 388 } 389 390 void 391 sleep(Rendez *r, int (*f)(void*), void *arg) 392 { 393 Proc *p; 394 int s; 395 396 p = u->p; 397 sleep1(r, f, arg); 398 if(p->notepending == 0) 399 sched(); /* notepending may go true while asleep */ 400 if(p->notepending){ 401 p->notepending = 0; 402 s = splhi(); 403 lock(r); 404 if(r->p == p) 405 r->p = 0; 406 unlock(r); 407 splx(s); 408 error(Eintr); 409 } 410 } 411 412 int 413 tfn(void *arg) 414 { 415 Proc *p; 416 417 p = u->p; 418 return MACHP(0)->ticks >= p->twhen || (*p->tfn)(arg); 419 } 420 421 void 422 tsleep(Rendez *r, int (*fn)(void*), void *arg, int ms) 423 { 424 ulong when; 425 Proc *p, *f, **l; 426 427 p = u->p; 428 when = MS2TK(ms)+MACHP(0)->ticks; 429 430 lock(&talarm); 431 /* take out of list if checkalarm didn't */ 432 if(p->trend) { 433 l = &talarm.list; 434 for(f = *l; f; f = f->tlink) { 435 if(f == p) { 436 *l = p->tlink; 437 break; 438 } 439 l = &f->tlink; 440 } 441 } 442 /* insert in increasing time order */ 443 l = &talarm.list; 444 for(f = *l; f; f = f->tlink) { 445 if(f->twhen >= when) 446 break; 447 l = &f->tlink; 448 } 449 p->trend = r; 450 p->twhen = when; 451 p->tfn = fn; 452 p->tlink = *l; 453 *l = p; 454 unlock(&talarm); 455 456 sleep(r, tfn, arg); 457 p->twhen = 0; 458 } 459 460 /* 461 * Expects that only one process can call wakeup for any given Rendez 462 */ 463 void 464 wakeup(Rendez *r) 465 { 466 Proc *p; 467 int s; 468 469 s = splhi(); 470 lock(r); 471 p = r->p; 472 if(p){ 473 r->p = 0; 474 if(p->state != Wakeme) 475 panic("wakeup: state"); 476 p->r = 0; 477 ready(p); 478 } 479 unlock(r); 480 splx(s); 481 } 482 483 int 484 postnote(Proc *p, int dolock, char *n, int flag) 485 { 486 User *up; 487 KMap *k; 488 int s, ret; 489 Rendez *r; 490 Proc *d, **l; 491 492 if(dolock) 493 qlock(&p->debug); 494 495 if(p->kp) 496 print("sending %s to kproc %d %s\n", n, p->pid, p->text); 497 498 if(p->upage == 0){ 499 if(dolock) 500 qunlock(&p->debug); 501 return 0; 502 } 503 504 SET(k); 505 if(u == 0 || p != u->p){ 506 k = kmap(p->upage); 507 up = (User*)VA(k); 508 }else 509 up = u; 510 USED(k); 511 512 if(flag!=NUser && (up->notify==0 || up->notified)) 513 up->nnote = 0; /* force user's hand */ 514 515 ret = 0; 516 if(up->nnote < NNOTE){ 517 strcpy(up->note[up->nnote].msg, n); 518 up->note[up->nnote++].flag = flag; 519 ret = 1; 520 } 521 p->notepending = 1; 522 if(up != u) 523 kunmap(k); 524 if(dolock) 525 qunlock(&p->debug); 526 527 if(r = p->r){ /* assign = */ 528 /* wake up; can't call wakeup itself because we're racing with it */ 529 for(;;) { 530 s = splhi(); 531 if(canlock(r)) 532 break; 533 splx(s); 534 } 535 if(p->r==r && r->p==p && p->state==Wakeme){ /* check we won the race */ 536 r->p = 0; 537 p->r = 0; 538 ready(p); 539 } 540 unlock(r); 541 splx(s); 542 } 543 544 if(p->state != Rendezvous) 545 return ret; 546 547 /* Try and pull out of a rendezvous */ 548 lock(p->pgrp); 549 if(p->state == Rendezvous) { 550 p->rendval = ~0; 551 l = &REND(p->pgrp, p->rendtag); 552 for(d = *l; d; d = d->rendhash) { 553 if(d == p) { 554 *l = p->rendhash; 555 ready(p); 556 break; 557 } 558 l = &d->rendhash; 559 } 560 } 561 unlock(p->pgrp); 562 return ret; 563 } 564 565 /* 566 * weird thing: keep at most NBROKEN around 567 */ 568 #define NBROKEN 4 569 struct 570 { 571 QLock; 572 int n; 573 Proc *p[NBROKEN]; 574 }broken; 575 576 void 577 addbroken(Proc *p) 578 { 579 qlock(&broken); 580 if(broken.n == NBROKEN) { 581 ready(broken.p[0]); 582 memmove(&broken.p[0], &broken.p[1], sizeof(Proc*)*(NBROKEN-1)); 583 --broken.n; 584 } 585 broken.p[broken.n++] = p; 586 qunlock(&broken); 587 588 p->state = Broken; 589 p->psstate = 0; 590 sched(); 591 } 592 593 void 594 unbreak(Proc *p) 595 { 596 int b; 597 598 qlock(&broken); 599 for(b=0; b < broken.n; b++) 600 if(broken.p[b] == p) { 601 broken.n--; 602 memmove(&broken.p[b], &broken.p[b+1], 603 sizeof(Proc*)*(NBROKEN-(b+1))); 604 ready(p); 605 break; 606 } 607 qunlock(&broken); 608 } 609 610 int 611 freebroken(void) 612 { 613 int i, n; 614 615 qlock(&broken); 616 n = broken.n; 617 for(i=0; i<n; i++) { 618 ready(broken.p[i]); 619 broken.p[i] = 0; 620 } 621 broken.n = 0; 622 qunlock(&broken); 623 return n; 624 } 625 626 void 627 pexit(char *exitstr, int freemem) 628 { 629 int n; 630 long utime, stime; 631 Proc *p, *c; 632 Segment **s, **es; 633 Waitq *wq, *f, *next; 634 635 c = u->p; 636 c->alarm = 0; 637 638 if(c->fgrp) 639 closefgrp(c->fgrp); 640 closepgrp(c->pgrp); 641 close(u->dot); 642 if(c->egrp) 643 closeegrp(c->egrp); 644 645 /* 646 * if not a kernel process and have a parent, 647 * do some housekeeping. 648 */ 649 if(c->kp == 0) { 650 p = c->parent; 651 if(p == 0) { 652 if(exitstr == 0) 653 exitstr = "unknown"; 654 panic("boot process died: %s", exitstr); 655 } 656 657 while(waserror()) 658 ; 659 wq = smalloc(sizeof(Waitq)); 660 poperror(); 661 662 readnum(0, wq->w.pid, NUMSIZE, c->pid, NUMSIZE); 663 utime = c->time[TUser] + c->time[TCUser]; 664 stime = c->time[TSys] + c->time[TCSys]; 665 readnum(0, &wq->w.time[TUser*12], NUMSIZE, 666 TK2MS(utime), NUMSIZE); 667 readnum(0, &wq->w.time[TSys*12], NUMSIZE, 668 TK2MS(stime), NUMSIZE); 669 readnum(0, &wq->w.time[TReal*12], NUMSIZE, 670 TK2MS(MACHP(0)->ticks - c->time[TReal]), NUMSIZE); 671 if(exitstr && exitstr[0]){ 672 n = sprint(wq->w.msg, "%s %d:", c->text, c->pid); 673 strncpy(wq->w.msg+n, exitstr, ERRLEN-n); 674 wq->w.msg[ERRLEN-1] = 0; 675 } 676 else 677 wq->w.msg[0] = '\0'; 678 679 lock(&p->exl); 680 /* My parent still alive, processes are limited to 128 Zombies to 681 * prevent a badly written daemon lots of wait records 682 */ 683 if(p->pid == c->parentpid && p->state != Broken && p->nwait < 128) { 684 p->nchild--; 685 p->time[TCUser] += utime; 686 p->time[TCSys] += stime; 687 688 wq->next = p->waitq; 689 p->waitq = wq; 690 p->nwait++; 691 unlock(&p->exl); 692 693 wakeup(&p->waitr); 694 } 695 else { 696 unlock(&p->exl); 697 free(wq); 698 } 699 } 700 701 if(!freemem) 702 addbroken(c); 703 704 es = &c->seg[NSEG]; 705 for(s = c->seg; s < es; s++) 706 if(*s) 707 putseg(*s); 708 709 lock(&c->exl); /* Prevent my children from leaving waits */ 710 c->pid = 0; 711 unlock(&c->exl); 712 713 for(f = c->waitq; f; f = next) { 714 next = f->next; 715 free(f); 716 } 717 718 /* 719 * sched() cannot wait on these locks 720 */ 721 qlock(&c->debug); 722 /* release debuggers */ 723 if(c->pdbg) { 724 wakeup(&c->pdbg->sleep); 725 c->pdbg = 0; 726 } 727 728 qunlock(&u->p->debug); 729 lock(&procalloc); 730 lock(&palloc); 731 732 c->state = Moribund; 733 sched(); 734 panic("pexit"); 735 } 736 737 int 738 haswaitq(void *x) 739 { 740 Proc *p; 741 742 p = (Proc *)x; 743 return p->waitq != 0; 744 } 745 746 ulong 747 pwait(Waitmsg *w) 748 { 749 Proc *p; 750 ulong cpid; 751 Waitq *wq; 752 753 p = u->p; 754 755 if(!canqlock(&p->qwaitr)) 756 error(Einuse); 757 758 if(waserror()) { 759 qunlock(&p->qwaitr); 760 nexterror(); 761 } 762 763 lock(&p->exl); 764 if(p->nchild == 0 && p->waitq == 0) { 765 unlock(&p->exl); 766 error(Enochild); 767 } 768 unlock(&p->exl); 769 770 sleep(&p->waitr, haswaitq, u->p); 771 772 lock(&p->exl); 773 wq = p->waitq; 774 p->waitq = wq->next; 775 p->nwait--; 776 unlock(&p->exl); 777 778 qunlock(&p->qwaitr); 779 poperror(); 780 781 if(w) 782 memmove(w, &wq->w, sizeof(Waitmsg)); 783 cpid = atoi(wq->w.pid); 784 free(wq); 785 return cpid; 786 } 787 788 Proc* 789 proctab(int i) 790 { 791 return &procalloc.arena[i]; 792 } 793 794 void 795 procdump(void) 796 { 797 int i; 798 char *s; 799 Proc *p; 800 ulong bss; 801 Schedq *rq; 802 803 for(i=0; i<conf.nproc; i++){ 804 p = procalloc.arena+i; 805 if(p->state != Dead){ 806 bss = 0; 807 if(p->seg[BSEG]) 808 bss = p->seg[BSEG]->top; 809 810 s = p->psstate; 811 if(s == 0) 812 s = "kproc"; 813 print("%3d:%10s %10s pc %8lux %8s (%s) ut %ld st %ld r %lux qpc %lux bss %lux\n", 814 p->pid, p->text, p->user, p->pc, 815 s, statename[p->state], p->time[0], 816 p->time[1], p->r, p->qlockpc, bss); 817 } 818 } 819 for(rq = runq; rq < &runq[Nrq]; rq++){ 820 if(rq->head == 0) 821 continue; 822 print("rq%d:", rq-runq); 823 for(p = rq->head; p; p = p->rnext) 824 print(" %d(%d)", p->pid, m->ticks - p->readytime); 825 print("\n"); 826 } 827 print("nrdy %d\n", nrdy); 828 } 829 830 void 831 kproc(char *name, void (*func)(void *), void *arg) 832 { 833 Proc *p; 834 int n; 835 ulong upa; 836 User *up; 837 KMap *k; 838 static Pgrp *kpgrp; 839 char *user; 840 int lastvar; /* used to compute stack address */ 841 842 /* 843 * Kernel stack 844 */ 845 p = newproc(); 846 p->psstate = 0; 847 p->procmode = 0644; 848 p->kp = 1; 849 p->upage = newpage(1, 0, USERADDR|(p->pid&0xFFFF)); 850 k = kmap(p->upage); 851 upa = VA(k); 852 up = (User*)upa; 853 854 /* 855 * Save time: only copy u-> data and useful stack 856 */ 857 memmove(up, u, sizeof(User)); 858 n = USERADDR+BY2PG - (ulong)&lastvar; 859 n = (n+32) & ~(BY2WD-1); /* be safe & word align */ 860 memmove((void*)(upa+BY2PG-n), (void*)(USERADDR+BY2PG-n), n); 861 up->p = p; 862 863 p->basepri = PriKproc; 864 p->priority = p->basepri; 865 866 /* 867 * Refs 868 */ 869 incref(up->dot); 870 kunmap(k); 871 872 /* 873 * Sched 874 */ 875 if(setlabel(&p->sched)){ 876 p->state = Running; 877 p->mach = m; 878 m->proc = p; 879 spllo(); 880 (*func)(arg); 881 pexit(0, 1); 882 } 883 884 user = eve; 885 strcpy(p->user, user); 886 if(kpgrp == 0){ 887 kpgrp = newpgrp(); 888 } 889 p->pgrp = kpgrp; 890 incref(kpgrp); 891 892 strcpy(p->text, name); 893 894 p->nchild = 0; 895 p->parent = 0; 896 memset(p->time, 0, sizeof(p->time)); 897 p->time[TReal] = MACHP(0)->ticks; 898 ready(p); 899 /* 900 * since the bss/data segments are now shareable, 901 * any mmu info about this process is now stale 902 * and has to be discarded. 903 */ 904 flushmmu(); 905 } 906 907 /* 908 * called splhi() by notify(). See comment in notify for the 909 * reasoning. 910 */ 911 void 912 procctl(Proc *p) 913 { 914 char *state; 915 ulong s; 916 917 switch(p->procctl) { 918 case Proc_exitme: 919 spllo(); /* pexit has locks in it */ 920 pexit("Killed", 1); 921 922 case Proc_traceme: 923 if(u->nnote == 0) 924 return; 925 /* No break */ 926 927 case Proc_stopme: 928 p->procctl = 0; 929 state = p->psstate; 930 p->psstate = "Stopped"; 931 /* free a waiting debugger */ 932 s = spllo(); 933 qlock(&p->debug); 934 if(p->pdbg) { 935 wakeup(&p->pdbg->sleep); 936 p->pdbg = 0; 937 } 938 qunlock(&p->debug); 939 splhi(); 940 p->state = Stopped; 941 sched(); 942 p->psstate = state; 943 splx(s); 944 return; 945 } 946 } 947 948 #include "errstr.h" 949 950 void 951 error(char *err) 952 { 953 spllo(); 954 strncpy(u->error, err, ERRLEN); 955 nexterror(); 956 } 957 958 void 959 nexterror(void) 960 { 961 gotolabel(&u->errlab[--u->nerrlab]); 962 } 963 964 void 965 exhausted(char *resource) 966 { 967 char buf[ERRLEN]; 968 969 sprint(buf, "no free %s", resource); 970 error(buf); 971 } 972