root/kernel/proc.c

DEFINITIONS

1. proc_mapstacks
2. procinit
3. cpuid
4. mycpu
5. myproc
6. allocpid
7. allocproc
8. freeproc
9. proc_pagetable
10. proc_freepagetable
11. userinit
12. growproc
13. kfork
14. reparent
15. kexit
16. kwait
17. scheduler
18. sched
19. yield
20. forkret
21. sleep
22. wakeup
23. kkill
24. setkilled
25. killed
26. either_copyout
27. either_copyin
28. procdump

   1 #include "types.h"
   2 #include "param.h"
   3 #include "memlayout.h"
   4 #include "riscv.h"
   5 #include "spinlock.h"
   6 #include "proc.h"
   7 #include "defs.h"
   8 
   9 struct cpu cpus[NCPU];
  10 
  11 struct proc proc[NPROC];
  12 
  13 struct proc *initproc;
  14 
  15 int nextpid = 1;
  16 struct spinlock pid_lock;
  17 
  18 extern void forkret(void);
  19 static void freeproc(struct proc *p);
  20 
  21 extern char trampoline[]; // trampoline.S
  22 
  23 // helps ensure that wakeups of wait()ing
  24 // parents are not lost. helps obey the
  25 // memory model when using p->parent.
  26 // must be acquired before any p->lock.
  27 struct spinlock wait_lock;
  28 
  29 // Allocate a page for each process's kernel stack.
  30 // Map it high in memory, followed by an invalid
  31 // guard page.
  32 void
  33 proc_mapstacks(pagetable_t kpgtbl)
  34 {
  35   struct proc *p;
  36   
  37   for(p = proc; p < &proc[NPROC]; p++) {
  38     char *pa = kalloc();
  39     if(pa == 0)
  40       panic("kalloc");
  41     uint64 va = KSTACK((int) (p - proc));
  42     kvmmap(kpgtbl, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
  43   }
  44 }
  45 
  46 // initialize the proc table.
  47 void
  48 procinit(void)
  49 {
  50   struct proc *p;
  51   
  52   initlock(&pid_lock, "nextpid");
  53   initlock(&wait_lock, "wait_lock");
  54   for(p = proc; p < &proc[NPROC]; p++) {
  55       initlock(&p->lock, "proc");
  56       p->state = UNUSED;
  57       p->kstack = KSTACK((int) (p - proc));
  58   }
  59 }
  60 
  61 // Must be called with interrupts disabled,
  62 // to prevent race with process being moved
  63 // to a different CPU.
  64 int
  65 cpuid()
  66 {
  67   int id = r_tp();
  68   return id;
  69 }
  70 
  71 // Return this CPU's cpu struct.
  72 // Interrupts must be disabled.
  73 struct cpu*
  74 mycpu(void)
  75 {
  76   int id = cpuid();
  77   struct cpu *c = &cpus[id];
  78   return c;
  79 }
  80 
  81 // Return the current struct proc *, or zero if none.
  82 struct proc*
  83 myproc(void)
  84 {
  85   push_off();
  86   struct cpu *c = mycpu();
  87   struct proc *p = c->proc;
  88   pop_off();
  89   return p;
  90 }
  91 
  92 int
  93 allocpid()
  94 {
  95   int pid;
  96   
  97   acquire(&pid_lock);
  98   pid = nextpid;
  99   nextpid = nextpid + 1;
 100   release(&pid_lock);
 101 
 102   return pid;
 103 }
 104 
 105 // Look in the process table for an UNUSED proc.
 106 // If found, initialize state required to run in the kernel,
 107 // and return with p->lock held.
 108 // If there are no free procs, or a memory allocation fails, return 0.
 109 static struct proc*
 110 allocproc(void)
 111 {
 112   struct proc *p;
 113 
 114   for(p = proc; p < &proc[NPROC]; p++) {
 115     acquire(&p->lock);
 116     if(p->state == UNUSED) {
 117       goto found;
 118     } else {
 119       release(&p->lock);
 120     }
 121   }
 122   return 0;
 123 
 124 found:
 125   p->pid = allocpid();
 126   p->state = USED;
 127 
 128   // Allocate a trapframe page.
 129   if((p->trapframe = (struct trapframe *)kalloc()) == 0){
 130     freeproc(p);
 131     release(&p->lock);
 132     return 0;
 133   }
 134 
 135   // An empty user page table.
 136   p->pagetable = proc_pagetable(p);
 137   if(p->pagetable == 0){
 138     freeproc(p);
 139     release(&p->lock);
 140     return 0;
 141   }
 142 
 143   // Set up new context to start executing at forkret,
 144   // which returns to user space.
 145   memset(&p->context, 0, sizeof(p->context));
 146   p->context.ra = (uint64)forkret;
 147   p->context.sp = p->kstack + PGSIZE;
 148 
 149   return p;
 150 }
 151 
 152 // free a proc structure and the data hanging from it,
 153 // including user pages.
 154 // p->lock must be held.
 155 static void
 156 freeproc(struct proc *p)
 157 {
 158   if(p->trapframe)
 159     kfree((void*)p->trapframe);
 160   p->trapframe = 0;
 161   if(p->pagetable)
 162     proc_freepagetable(p->pagetable, p->sz);
 163   p->pagetable = 0;
 164   p->sz = 0;
 165   p->pid = 0;
 166   p->parent = 0;
 167   p->name[0] = 0;
 168   p->chan = 0;
 169   p->killed = 0;
 170   p->xstate = 0;
 171   p->state = UNUSED;
 172 }
 173 
 174 // Create a user page table for a given process, with no user memory,
 175 // but with trampoline and trapframe pages.
 176 pagetable_t
 177 proc_pagetable(struct proc *p)
 178 {
 179   pagetable_t pagetable;
 180 
 181   // An empty page table.
 182   pagetable = uvmcreate();
 183   if(pagetable == 0)
 184     return 0;
 185 
 186   // map the trampoline code (for system call return)
 187   // at the highest user virtual address.
 188   // only the supervisor uses it, on the way
 189   // to/from user space, so not PTE_U.
 190   if(mappages(pagetable, TRAMPOLINE, PGSIZE,
 191               (uint64)trampoline, PTE_R | PTE_X) < 0){
 192     uvmfree(pagetable, 0);
 193     return 0;
 194   }
 195 
 196   // map the trapframe page just below the trampoline page, for
 197   // trampoline.S.
 198   if(mappages(pagetable, TRAPFRAME, PGSIZE,
 199               (uint64)(p->trapframe), PTE_R | PTE_W) < 0){
 200     uvmunmap(pagetable, TRAMPOLINE, 1, 0);
 201     uvmfree(pagetable, 0);
 202     return 0;
 203   }
 204 
 205   return pagetable;
 206 }
 207 
 208 // Free a process's page table, and free the
 209 // physical memory it refers to.
 210 void
 211 proc_freepagetable(pagetable_t pagetable, uint64 sz)
 212 {
 213   uvmunmap(pagetable, TRAMPOLINE, 1, 0);
 214   uvmunmap(pagetable, TRAPFRAME, 1, 0);
 215   uvmfree(pagetable, sz);
 216 }
 217 
 218 // Set up first user process.
 219 void
 220 userinit(void)
 221 {
 222   struct proc *p;
 223 
 224   p = allocproc();
 225   initproc = p;
 226   
 227   p->cwd = namei("/");
 228 
 229   p->state = RUNNABLE;
 230 
 231   release(&p->lock);
 232 }
 233 
 234 // Shrink user memory by n bytes.
 235 // Return 0 on success, -1 on failure.
 236 int
 237 growproc(int n)
 238 {
 239   uint64 sz;
 240   struct proc *p = myproc();
 241 
 242   sz = p->sz;
 243   if(n > 0){
 244     if((sz = uvmalloc(p->pagetable, sz, sz + n, PTE_W)) == 0) {
 245       return -1;
 246     }
 247   } else if(n < 0){
 248     sz = uvmdealloc(p->pagetable, sz, sz + n);
 249   }
 250   p->sz = sz;
 251   return 0;
 252 }
 253 
 254 // Create a new process, copying the parent.
 255 // Sets up child kernel stack to return as if from fork() system call.
 256 int
 257 kfork(void)
 258 {
 259   int i, pid;
 260   struct proc *np;
 261   struct proc *p = myproc();
 262 
 263   // Allocate process.
 264   if((np = allocproc()) == 0){
 265     return -1;
 266   }
 267 
 268   // Copy user memory from parent to child.
 269   if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
 270     freeproc(np);
 271     release(&np->lock);
 272     return -1;
 273   }
 274   np->sz = p->sz;
 275 
 276   // copy saved user registers.
 277   *(np->trapframe) = *(p->trapframe);
 278 
 279   // Cause fork to return 0 in the child.
 280   np->trapframe->a0 = 0;
 281 
 282   // increment reference counts on open file descriptors.
 283   for(i = 0; i < NOFILE; i++)
 284     if(p->ofile[i])
 285       np->ofile[i] = filedup(p->ofile[i]);
 286   np->cwd = idup(p->cwd);
 287 
 288   safestrcpy(np->name, p->name, sizeof(p->name));
 289 
 290   pid = np->pid;
 291 
 292   release(&np->lock);
 293 
 294   acquire(&wait_lock);
 295   np->parent = p;
 296   release(&wait_lock);
 297 
 298   acquire(&np->lock);
 299   np->state = RUNNABLE;
 300   release(&np->lock);
 301 
 302   return pid;
 303 }
 304 
 305 // Pass p's abandoned children to init.
 306 // Caller must hold wait_lock.
 307 void
 308 reparent(struct proc *p)
 309 {
 310   struct proc *pp;
 311 
 312   for(pp = proc; pp < &proc[NPROC]; pp++){
 313     if(pp->parent == p){
 314       pp->parent = initproc;
 315       wakeup(initproc);
 316     }
 317   }
 318 }
 319 
 320 // Exit the current process.  Does not return.
 321 // An exited process remains in the zombie state
 322 // until its parent calls wait().
 323 void
 324 kexit(int status)
 325 {
 326   struct proc *p = myproc();
 327 
 328   if(p == initproc)
 329     panic("init exiting");
 330 
 331   // Close all open files.
 332   for(int fd = 0; fd < NOFILE; fd++){
 333     if(p->ofile[fd]){
 334       struct file *f = p->ofile[fd];
 335       fileclose(f);
 336       p->ofile[fd] = 0;
 337     }
 338   }
 339 
 340   begin_op();
 341   iput(p->cwd);
 342   end_op();
 343   p->cwd = 0;
 344 
 345   acquire(&wait_lock);
 346 
 347   // Give any children to init.
 348   reparent(p);
 349 
 350   // Parent might be sleeping in wait().
 351   wakeup(p->parent);
 352   
 353   acquire(&p->lock);
 354 
 355   p->xstate = status;
 356   p->state = ZOMBIE;
 357 
 358   release(&wait_lock);
 359 
 360   // Jump into the scheduler, never to return.
 361   sched();
 362   panic("zombie exit");
 363 }
 364 
 365 // Wait for a child process to exit and return its pid.
 366 // Return -1 if this process has no children.
 367 int
 368 kwait(uint64 addr)
 369 {
 370   struct proc *pp;
 371   int havekids, pid;
 372   struct proc *p = myproc();
 373 
 374   acquire(&wait_lock);
 375 
 376   for(;;){
 377     // Scan through table looking for exited children.
 378     havekids = 0;
 379     for(pp = proc; pp < &proc[NPROC]; pp++){
 380       if(pp->parent == p){
 381         // make sure the child isn't still in exit() or swtch().
 382         acquire(&pp->lock);
 383 
 384         havekids = 1;
 385         if(pp->state == ZOMBIE){
 386           // Found one.
 387           pid = pp->pid;
 388           if(addr != 0 && copyout(p->pagetable, addr, (char *)&pp->xstate,
 389                                   sizeof(pp->xstate)) < 0) {
 390             release(&pp->lock);
 391             release(&wait_lock);
 392             return -1;
 393           }
 394           freeproc(pp);
 395           release(&pp->lock);
 396           release(&wait_lock);
 397           return pid;
 398         }
 399         release(&pp->lock);
 400       }
 401     }
 402 
 403     // No point waiting if we don't have any children.
 404     if(!havekids || killed(p)){
 405       release(&wait_lock);
 406       return -1;
 407     }
 408     
 409     // Wait for a child to exit.
 410     sleep(p, &wait_lock);  //DOC: wait-sleep
 411   }
 412 }
 413 
 414 // Per-CPU process scheduler.
 415 // Each CPU calls scheduler() after setting itself up.
 416 // Scheduler never returns.  It loops, doing:
 417 //  - choose a process to run.
 418 //  - swtch to start running that process.
 419 //  - eventually that process transfers control
 420 //    via swtch back to the scheduler.
 421 void
 422 scheduler(void)
 423 {
 424   struct proc *p;
 425   struct cpu *c = mycpu();
 426 
 427   c->proc = 0;
 428   for(;;){
 429     // The most recent process to run may have had interrupts
 430     // turned off; enable them to avoid a deadlock if all
 431     // processes are waiting. Then turn them back off
 432     // to avoid a possible race between an interrupt
 433     // and wfi.
 434     intr_on();
 435     intr_off();
 436 
 437     int found = 0;
 438     for(p = proc; p < &proc[NPROC]; p++) {
 439       acquire(&p->lock);
 440       if(p->state == RUNNABLE) {
 441         // Switch to chosen process.  It is the process's job
 442         // to release its lock and then reacquire it
 443         // before jumping back to us.
 444         p->state = RUNNING;
 445         c->proc = p;
 446         swtch(&c->context, &p->context);
 447 
 448         // Process is done running for now.
 449         // It should have changed its p->state before coming back.
 450         c->proc = 0;
 451         found = 1;
 452       }
 453       release(&p->lock);
 454     }
 455     if(found == 0) {
 456       // nothing to run; stop running on this core until an interrupt.
 457       asm volatile("wfi");
 458     }
 459   }
 460 }
 461 
 462 // Switch to scheduler.  Must hold only p->lock
 463 // and have changed proc->state. Saves and restores
 464 // intena because intena is a property of this
 465 // kernel thread, not this CPU. It should
 466 // be proc->intena and proc->noff, but that would
 467 // break in the few places where a lock is held but
 468 // there's no process.
 469 void
 470 sched(void)
 471 {
 472   int intena;
 473   struct proc *p = myproc();
 474 
 475   if(!holding(&p->lock))
 476     panic("sched p->lock");
 477   if(mycpu()->noff != 1)
 478     panic("sched locks");
 479   if(p->state == RUNNING)
 480     panic("sched RUNNING");
 481   if(intr_get())
 482     panic("sched interruptible");
 483 
 484   intena = mycpu()->intena;
 485   swtch(&p->context, &mycpu()->context);
 486   mycpu()->intena = intena;
 487 }
 488 
 489 // Give up the CPU for one scheduling round.
 490 void
 491 yield(void)
 492 {
 493   struct proc *p = myproc();
 494   acquire(&p->lock);
 495   p->state = RUNNABLE;
 496   sched();
 497   release(&p->lock);
 498 }
 499 
 500 // A fork child's very first scheduling by scheduler()
 501 // will swtch to forkret.
 502 void
 503 forkret(void)
 504 {
 505   extern char userret[];
 506   static int first = 1;
 507   struct proc *p = myproc();
 508 
 509   // Still holding p->lock from scheduler.
 510   release(&p->lock);
 511 
 512   if (first) {
 513     // File system initialization must be run in the context of a
 514     // regular process (e.g., because it calls sleep), and thus cannot
 515     // be run from main().
 516     fsinit(ROOTDEV);
 517 
 518     first = 0;
 519     // ensure other cores see first=0.
 520     __sync_synchronize();
 521 
 522     // We can invoke kexec() now that file system is initialized.
 523     // Put the return value (argc) of kexec into a0.
 524     p->trapframe->a0 = kexec("/init", (char *[]){ "/init", 0 });
 525     if (p->trapframe->a0 == -1) {
 526       panic("exec");
 527     }
 528   }
 529 
 530   // return to user space, mimicing usertrap()'s return.
 531   prepare_return();
 532   uint64 satp = MAKE_SATP(p->pagetable);
 533   uint64 trampoline_userret = TRAMPOLINE + (userret - trampoline);
 534   ((void (*)(uint64))trampoline_userret)(satp);
 535 }
 536 
 537 // Sleep on channel chan, releasing condition lock lk.
 538 // Re-acquires lk when awakened.
 539 void
 540 sleep(void *chan, struct spinlock *lk)
 541 {
 542   struct proc *p = myproc();
 543   
 544   // Must acquire p->lock in order to
 545   // change p->state and then call sched.
 546   // Once we hold p->lock, we can be
 547   // guaranteed that we won't miss any wakeup
 548   // (wakeup locks p->lock),
 549   // so it's okay to release lk.
 550 
 551   acquire(&p->lock);  //DOC: sleeplock1
 552   release(lk);
 553 
 554   // Go to sleep.
 555   p->chan = chan;
 556   p->state = SLEEPING;
 557 
 558   sched();
 559 
 560   // Tidy up.
 561   p->chan = 0;
 562 
 563   // Reacquire original lock.
 564   release(&p->lock);
 565   acquire(lk);
 566 }
 567 
 568 // Wake up all processes sleeping on channel chan.
 569 // Caller should hold the condition lock.
 570 void
 571 wakeup(void *chan)
 572 {
 573   struct proc *p;
 574 
 575   for(p = proc; p < &proc[NPROC]; p++) {
 576     if(p != myproc()){
 577       acquire(&p->lock);
 578       if(p->state == SLEEPING && p->chan == chan) {
 579         p->state = RUNNABLE;
 580       }
 581       release(&p->lock);
 582     }
 583   }
 584 }
 585 
 586 // Kill the process with the given pid.
 587 // The victim won't exit until it tries to return
 588 // to user space (see usertrap() in trap.c).
 589 int
 590 kkill(int pid)
 591 {
 592   struct proc *p;
 593 
 594   for(p = proc; p < &proc[NPROC]; p++){
 595     acquire(&p->lock);
 596     if(p->pid == pid){
 597       p->killed = 1;
 598       if(p->state == SLEEPING){
 599         // Wake process from sleep().
 600         p->state = RUNNABLE;
 601       }
 602       release(&p->lock);
 603       return 0;
 604     }
 605     release(&p->lock);
 606   }
 607   return -1;
 608 }
 609 
 610 void
 611 setkilled(struct proc *p)
 612 {
 613   acquire(&p->lock);
 614   p->killed = 1;
 615   release(&p->lock);
 616 }
 617 
 618 int
 619 killed(struct proc *p)
 620 {
 621   int k;
 622   
 623   acquire(&p->lock);
 624   k = p->killed;
 625   release(&p->lock);
 626   return k;
 627 }
 628 
 629 // Copy to either a user address, or kernel address,
 630 // depending on usr_dst.
 631 // Returns 0 on success, -1 on error.
 632 int
 633 either_copyout(int user_dst, uint64 dst, void *src, uint64 len)
 634 {
 635   struct proc *p = myproc();
 636   if(user_dst){
 637     return copyout(p->pagetable, dst, src, len);
 638   } else {
 639     memmove((char *)dst, src, len);
 640     return 0;
 641   }
 642 }
 643 
 644 // Copy from either a user address, or kernel address,
 645 // depending on usr_src.
 646 // Returns 0 on success, -1 on error.
 647 int
 648 either_copyin(void *dst, int user_src, uint64 src, uint64 len)
 649 {
 650   struct proc *p = myproc();
 651   if(user_src){
 652     return copyin(p->pagetable, dst, src, len);
 653   } else {
 654     memmove(dst, (char*)src, len);
 655     return 0;
 656   }
 657 }
 658 
 659 // Print a process listing to console.  For debugging.
 660 // Runs when user types ^P on console.
 661 // No lock to avoid wedging a stuck machine further.
 662 void
 663 procdump(void)
 664 {
 665   static char *states[] = {
 666   [UNUSED]    "unused",
 667   [USED]      "used",
 668   [SLEEPING]  "sleep ",
 669   [RUNNABLE]  "runble",
 670   [RUNNING]   "run   ",
 671   [ZOMBIE]    "zombie"
 672   };
 673   struct proc *p;
 674   char *state;
 675 
 676   printf("\n");
 677   for(p = proc; p < &proc[NPROC]; p++){
 678     if(p->state == UNUSED)
 679       continue;
 680     if(p->state >= 0 && p->state < NELEM(states) && states[p->state])
 681       state = states[p->state];
 682     else
 683       state = "???";
 684     printf("%d %s %s", p->pid, state, p->name);
 685     printf("\n");
 686   }
 687 }