1 #include "types.h" 2 #include "defs.h" 3 #include "param.h" 4 #include "memlayout.h" 5 #include "mmu.h" 6 #include "x86.h" 7 #include "proc.h" 8 #include "spinlock.h" 9 10 struct { 11 struct spinlock lock; 12 struct proc proc[NPROC]; 13 } ptable; 14 15 static struct proc *initproc; 16 17 int nextpid = 1; 18 extern void forkret(void); 19 extern void trapret(void); 20 21 static void wakeup1(void *chan); 22 23 void 24 pinit(void) 25 { 26 initlock(&ptable.lock, "ptable"); 27 } 28 29 //PAGEBREAK: 32 30 // Look in the process table for an UNUSED proc. 31 // If found, change state to EMBRYO and initialize 32 // state required to run in the kernel. 33 // Otherwise return 0. 34 // Must hold ptable.lock. 35 static struct proc* 36 allocproc(void) 37 { 38 struct proc *p; 39 char *sp; 40 41 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) 42 if(p->state == UNUSED) 43 goto found; 44 return 0; 45 46 found: 47 p->state = EMBRYO; 48 p->pid = nextpid++; 49 50 // Allocate kernel stack. 51 if((p->kstack = kalloc()) == 0){ 52 p->state = UNUSED; 53 return 0; 54 } 55 sp = p->kstack + KSTACKSIZE; 56 57 // Leave room for trap frame. 58 sp -= sizeof *p->tf; 59 p->tf = (struct trapframe*)sp; 60 61 // Set up new context to start executing at forkret, 62 // which returns to trapret. 63 sp -= 4; 64 *(uint*)sp = (uint)trapret; 65 66 sp -= sizeof *p->context; 67 p->context = (struct context*)sp; 68 memset(p->context, 0, sizeof *p->context); 69 p->context->eip = (uint)forkret; 70 71 return p; 72 } 73 74 //PAGEBREAK: 32 75 // Set up first user process. 76 void 77 userinit(void) 78 { 79 struct proc *p; 80 extern char _binary_initcode_start[], _binary_initcode_size[]; 81 82 acquire(&ptable.lock); 83 84 p = allocproc(); 85 86 // release the lock in case namei() sleeps. 87 // the lock isn't needed because no other 88 // thread will look at an EMBRYO proc. 89 release(&ptable.lock); 90 91 initproc = p; 92 if((p->pgdir = setupkvm()) == 0) 93 panic("userinit: out of memory?"); 94 inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size); 95 p->sz = PGSIZE; 96 memset(p->tf, 0, sizeof(*p->tf)); 97 p->tf->cs = (SEG_UCODE << 3) | DPL_USER; 98 p->tf->ds = (SEG_UDATA << 3) | DPL_USER; 99 p->tf->es = p->tf->ds; 100 p->tf->ss = p->tf->ds; 101 p->tf->eflags = FL_IF; 102 p->tf->esp = PGSIZE; 103 p->tf->eip = 0; // beginning of initcode.S 104 105 safestrcpy(p->name, "initcode", sizeof(p->name)); 106 p->cwd = namei("/"); 107 108 // this assignment to p->state lets other cores 109 // run this process. the acquire forces the above 110 // writes to be visible, and the lock is also needed 111 // because the assignment might not be atomic. 112 acquire(&ptable.lock); 113 114 p->state = RUNNABLE; 115 116 release(&ptable.lock); 117 } 118 119 // Grow current process's memory by n bytes. 120 // Return 0 on success, -1 on failure. 121 int 122 growproc(int n) 123 { 124 uint sz; 125 126 sz = proc->sz; 127 if(n > 0){ 128 if((sz = allocuvm(proc->pgdir, sz, sz + n)) == 0) 129 return -1; 130 } else if(n < 0){ 131 if((sz = deallocuvm(proc->pgdir, sz, sz + n)) == 0) 132 return -1; 133 } 134 proc->sz = sz; 135 switchuvm(proc); 136 return 0; 137 } 138 139 // Create a new process copying p as the parent. 140 // Sets up stack to return as if from system call. 141 // Caller must set state of returned proc to RUNNABLE. 142 int 143 fork(void) 144 { 145 int i, pid; 146 struct proc *np; 147 148 acquire(&ptable.lock); 149 150 // Allocate process. 151 if((np = allocproc()) == 0){ 152 release(&ptable.lock); 153 return -1; 154 } 155 156 release(&ptable.lock); 157 158 // Copy process state from p. 159 if((np->pgdir = copyuvm(proc->pgdir, proc->sz)) == 0){ 160 kfree(np->kstack); 161 np->kstack = 0; 162 np->state = UNUSED; 163 release(&ptable.lock); 164 return -1; 165 } 166 np->sz = proc->sz; 167 np->parent = proc; 168 *np->tf = *proc->tf; 169 170 // Clear %eax so that fork returns 0 in the child. 171 np->tf->eax = 0; 172 173 for(i = 0; i < NOFILE; i++) 174 if(proc->ofile[i]) 175 np->ofile[i] = filedup(proc->ofile[i]); 176 np->cwd = idup(proc->cwd); 177 178 safestrcpy(np->name, proc->name, sizeof(proc->name)); 179 180 pid = np->pid; 181 182 acquire(&ptable.lock); 183 184 np->state = RUNNABLE; 185 186 release(&ptable.lock); 187 188 return pid; 189 } 190 191 // Exit the current process. Does not return. 192 // An exited process remains in the zombie state 193 // until its parent calls wait() to find out it exited. 194 void 195 exit(void) 196 { 197 struct proc *p; 198 int fd; 199 200 if(proc == initproc) 201 panic("init exiting"); 202 203 // Close all open files. 204 for(fd = 0; fd < NOFILE; fd++){ 205 if(proc->ofile[fd]){ 206 fileclose(proc->ofile[fd]); 207 proc->ofile[fd] = 0; 208 } 209 } 210 211 begin_op(); 212 iput(proc->cwd); 213 end_op(); 214 proc->cwd = 0; 215 216 acquire(&ptable.lock); 217 218 // Parent might be sleeping in wait(). 219 wakeup1(proc->parent); 220 221 // Pass abandoned children to init. 222 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ 223 if(p->parent == proc){ 224 p->parent = initproc; 225 if(p->state == ZOMBIE) 226 wakeup1(initproc); 227 } 228 } 229 230 // Jump into the scheduler, never to return. 231 proc->state = ZOMBIE; 232 sched(); 233 panic("zombie exit"); 234 } 235 236 // Wait for a child process to exit and return its pid. 237 // Return -1 if this process has no children. 238 int 239 wait(void) 240 { 241 struct proc *p; 242 int havekids, pid; 243 244 acquire(&ptable.lock); 245 for(;;){ 246 // Scan through table looking for exited children. 247 havekids = 0; 248 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ 249 if(p->parent != proc) 250 continue; 251 havekids = 1; 252 if(p->state == ZOMBIE){ 253 // Found one. 254 pid = p->pid; 255 kfree(p->kstack); 256 p->kstack = 0; 257 freevm(p->pgdir); 258 p->pid = 0; 259 p->parent = 0; 260 p->name[0] = 0; 261 p->killed = 0; 262 p->state = UNUSED; 263 release(&ptable.lock); 264 return pid; 265 } 266 } 267 268 // No point waiting if we don't have any children. 269 if(!havekids || proc->killed){ 270 release(&ptable.lock); 271 return -1; 272 } 273 274 // Wait for children to exit. (See wakeup1 call in proc_exit.) 275 sleep(proc, &ptable.lock); //DOC: wait-sleep 276 } 277 } 278 279 //PAGEBREAK: 42 280 // Per-CPU process scheduler. 281 // Each CPU calls scheduler() after setting itself up. 282 // Scheduler never returns. It loops, doing: 283 // - choose a process to run 284 // - swtch to start running that process 285 // - eventually that process transfers control 286 // via swtch back to the scheduler. 287 void 288 scheduler(void) 289 { 290 struct proc *p; 291 292 for(;;){ 293 // Enable interrupts on this processor. 294 sti(); 295 296 // Loop over process table looking for process to run. 297 acquire(&ptable.lock); 298 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ 299 if(p->state != RUNNABLE) 300 continue; 301 302 // Switch to chosen process. It is the process's job 303 // to release ptable.lock and then reacquire it 304 // before jumping back to us. 305 proc = p; 306 switchuvm(p); 307 p->state = RUNNING; 308 swtch(&cpu->scheduler, p->context); 309 switchkvm(); 310 311 // Process is done running for now. 312 // It should have changed its p->state before coming back. 313 proc = 0; 314 } 315 release(&ptable.lock); 316 317 } 318 } 319 320 // Enter scheduler. Must hold only ptable.lock 321 // and have changed proc->state. Saves and restores 322 // intena because intena is a property of this 323 // kernel thread, not this CPU. It should 324 // be proc->intena and proc->ncli, but that would 325 // break in the few places where a lock is held but 326 // there's no process. 327 void 328 sched(void) 329 { 330 int intena; 331 332 if(!holding(&ptable.lock)) 333 panic("sched ptable.lock"); 334 if(cpu->ncli != 1) 335 panic("sched locks"); 336 if(proc->state == RUNNING) 337 panic("sched running"); 338 if(readeflags()&FL_IF) 339 panic("sched interruptible"); 340 intena = cpu->intena; 341 swtch(&proc->context, cpu->scheduler); 342 cpu->intena = intena; 343 } 344 345 // Give up the CPU for one scheduling round. 346 void 347 yield(void) 348 { 349 acquire(&ptable.lock); //DOC: yieldlock 350 proc->state = RUNNABLE; 351 sched(); 352 release(&ptable.lock); 353 } 354 355 // A fork child's very first scheduling by scheduler() 356 // will swtch here. "Return" to user space. 357 void 358 forkret(void) 359 { 360 static int first = 1; 361 // Still holding ptable.lock from scheduler. 362 release(&ptable.lock); 363 364 if (first) { 365 // Some initialization functions must be run in the context 366 // of a regular process (e.g., they call sleep), and thus cannot 367 // be run from main(). 368 first = 0; 369 iinit(ROOTDEV); 370 initlog(ROOTDEV); 371 } 372 373 // Return to "caller", actually trapret (see allocproc). 374 } 375 376 // Atomically release lock and sleep on chan. 377 // Reacquires lock when awakened. 378 void 379 sleep(void *chan, struct spinlock *lk) 380 { 381 if(proc == 0) 382 panic("sleep"); 383 384 if(lk == 0) 385 panic("sleep without lk"); 386 387 // Must acquire ptable.lock in order to 388 // change p->state and then call sched. 389 // Once we hold ptable.lock, we can be 390 // guaranteed that we won't miss any wakeup 391 // (wakeup runs with ptable.lock locked), 392 // so it's okay to release lk. 393 if(lk != &ptable.lock){ //DOC: sleeplock0 394 acquire(&ptable.lock); //DOC: sleeplock1 395 release(lk); 396 } 397 398 // Go to sleep. 399 proc->chan = chan; 400 proc->state = SLEEPING; 401 sched(); 402 403 // Tidy up. 404 proc->chan = 0; 405 406 // Reacquire original lock. 407 if(lk != &ptable.lock){ //DOC: sleeplock2 408 release(&ptable.lock); 409 acquire(lk); 410 } 411 } 412 413 //PAGEBREAK! 414 // Wake up all processes sleeping on chan. 415 // The ptable lock must be held. 416 static void 417 wakeup1(void *chan) 418 { 419 struct proc *p; 420 421 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) 422 if(p->state == SLEEPING && p->chan == chan) 423 p->state = RUNNABLE; 424 } 425 426 // Wake up all processes sleeping on chan. 427 void 428 wakeup(void *chan) 429 { 430 acquire(&ptable.lock); 431 wakeup1(chan); 432 release(&ptable.lock); 433 } 434 435 // Kill the process with the given pid. 436 // Process won't exit until it returns 437 // to user space (see trap in trap.c). 438 int 439 kill(int pid) 440 { 441 struct proc *p; 442 443 acquire(&ptable.lock); 444 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ 445 if(p->pid == pid){ 446 p->killed = 1; 447 // Wake process from sleep if necessary. 448 if(p->state == SLEEPING) 449 p->state = RUNNABLE; 450 release(&ptable.lock); 451 return 0; 452 } 453 } 454 release(&ptable.lock); 455 return -1; 456 } 457 458 //PAGEBREAK: 36 459 // Print a process listing to console. For debugging. 460 // Runs when user types ^P on console. 461 // No lock to avoid wedging a stuck machine further. 462 void 463 procdump(void) 464 { 465 static char *states[] = { 466 [UNUSED] "unused", 467 [EMBRYO] "embryo", 468 [SLEEPING] "sleep ", 469 [RUNNABLE] "runble", 470 [RUNNING] "run ", 471 [ZOMBIE] "zombie" 472 }; 473 int i; 474 struct proc *p; 475 char *state; 476 uint pc[10]; 477 478 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ 479 if(p->state == UNUSED) 480 continue; 481 if(p->state >= 0 && p->state < NELEM(states) && states[p->state]) 482 state = states[p->state]; 483 else 484 state = "???"; 485 cprintf("%d %s %s", p->pid, state, p->name); 486 if(p->state == SLEEPING){ 487 getcallerpcs((uint*)p->context->ebp+2, pc); 488 for(i=0; i<10 && pc[i] != 0; i++) 489 cprintf(" %p", pc[i]); 490 } 491 cprintf("\n"); 492 } 493 } 494