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