Requirement:
system calls
- int clone(void(fcn)(void , void ), void arg1, void arg2, void stack).
This call creates a new kernel thread which shares the calling process's address space.
File descriptors are copied as in fork().
The new process uses stack as its user stack, which is passed two arguments (arg1 and arg2) and uses a fake return PC (0xffffffff); a proper thread will simply call exit() when it is done (and not return).
The stack should be one page in size and page-aligned.
The new thread starts executing at the address specified by fcn.
Return value: as with fork(), the PID of the new thread is returned to the parent (for simplicity, threads each have their own process ID).
- int join(void **stack).
This call waits for a child thread that shares the address space with the calling process to exit.
Return value: the PID of waited-for child or -1 if none. The location of the child's user stack is copied into the argument stack (which can then be freed).
thread library
- int thread_create(void (start_routine)(void , void ), void arg1, void *arg2)
This routine should call malloc() to create a new user stack, use clone() to create the child thread and get it running.
Return value: the newly created PID to the parent and 0 to the child (if successful), -1 otherwise.
- int thread_join()
calls the underlying join() system call, frees the user stack, and then returns.
Return value:the waited-for PID (when successful), -1 otherwise.
- void lock_acquire(lock_t ) & void lock_release(lock_t )
TODO:
- study fork() system call to implement clone() system call
- study wait() system call to implement join() system call
clone() systemcall:
Track the fork() system call:
It creates a new process copying p as the parent.
It sets up stack to return as if from system call.
Caller must set state of returned proc to RUNNABLE.
sysproc.c
10 int
11 sys_fork(void)
12 {
13 return fork();
14 }
where is the fork()?
proc.c
180 int
181 fork(void)
182 {
183 int i, pid;
184 struct proc *np;
185 struct proc *curproc = myproc();
186
187 // Allocate process.
188 if((np = allocproc()) == 0){
189 return -1;
190 }
...what does allocproc() actually do?
Look in the process table for an UNUSED proc.
If found, change state to EMBRYO and initialize state required to run in the kernel. Otherwise return 0.
Let's track down the function allocproc().
It is defined in
proc.c
73 static struct proc*
74 allocproc(void)
75 {
76 struct proc *p;
77 char *sp;
78
79 acquire(&ptable.lock);
80
81 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) //what is process table?
82 if(p->state == UNUSED)
83 goto found;
84
....then, where is the process table initialized?
proc.c
10 struct {
11 struct spinlock lock;
12 struct proc proc[NPROC]; //NRPOC is defined as 64 in param.h
13 } ptable;struct proc is defined in proc.h
38 struct proc {
39 uint sz; // Size of process memory (bytes)
40 pde_t* pgdir; // Page table
41 char *kstack; // Bottom of kernel stack for this process
42 enum procstate state; // Process state
43 int pid; // Process ID
44 struct proc *parent; // Parent process
45 struct trapframe *tf; // Trap frame for current syscall
46 struct context *context; // swtch() here to run process
47 void *chan; // If non-zero, sleeping on chan
48 int killed; // If non-zero, have been killed
49 struct file *ofile[NOFILE]; // Open files
50 struct inode *cwd; // Current directory
51 char name[16]; // Process name (debugging)
52 };we now know that struct ptable initializes 64 struct proc and each initial states are UNUSED.
As defined in the proc.h,
35 enum procstate { UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };In C programming, the default value of an enumeration type E is the value produced by expression (E)0, even if zero doesn't have the corresponding enum member -> Default value of the procstate is UNUSED.
go back to allocproc():
...
94 // Allocate kernel stack.
95 if((p->kstack = kalloc()) == 0){
96 p->state = UNUSED;
97 return 0;
98 }
99 sp = p->kstack + KSTACKSIZE;
100
101 // Leave room for trap frame.
102 sp -= sizeof *p->tf;
103 p->tf = (struct trapframe*)sp;
105 // Set up new context to start executing at forkret,
106 // which returns to trapret.
107 sp -= 4;
108 *(uint*)sp = (uint)trapret;
109
110 sp -= sizeof *p->context;
111 p->context = (struct context*)sp;
112 memset(p->context, 0, sizeof *p->context);
113 p->context->eip = (uint)forkret;
114
115 return p;
116 }
...Kernel Stack?
Each process has two stacks: a user stack and a kernel stack (p->kstack). When the process is executing user instructions, only its user stack is in use, and its kernel stack is empty.
When the process enters the kernel (for a system call or interrupt), the kernel code executes on the process’s kernel stack; while a process is in the kernel, its user stack still contains saved data, but isn’t actively used.
On xv6, for example, the processor will push the program counter, flags, and a few other registers onto a per-process trap-frame in kernel stack; the return-fromtrap will pop these values off the stack and resume execution of the usermode program.
Context? trapret? forkret?
context structure is the kernel context of the running process for context switching. (context switching is done in kernel mode)
The user mode context is saved into the trapframe structure.
context의 eip레지스터(extension instruction pointer; 실행할 함수 주소로 이해하자)를 forkret() 함수 주소로 저장함으로써 생성된 프로세스가 스케쥴링되면 forkret() 함수가 실행된다. 또 eip 레지스터 다음에 trapret 함수의 주소를 저장함으로써 forkret() 함수가 return된 후 바로 trapret() 함수가 실행될 수 있도록 구성한다.
forkret()과 trapret() 함수에 대해서 간단히 설명하면 forkret()은 fork return의 약자로 fork(새로운 프로세스를 생성하는 함수)하여 새로운 프로세스가 생성하는 작업이 끝났으니 ptable lock을 해제한다. trapret()은 trap retrun의 약자로 trap을 통해 kernel에 진입하여 작업을 완료했으니 다시 user mode로 전화하기 위해 kernel stack의 trapframe에 저장되어있던 user mode에서의 register를 복구시킴으로써 user mode로 전환하는 함수이다.
go back to fork():
...
192 // Copy process state from proc.
193 if((np->pgdir = copyuvm(curproc->pgdir, curproc->sz)) == 0){
194 kfree(np->kstack);
195 np->kstack = 0;
196 np->state = UNUSED;
197 return -1;
198 }
199 np->sz = curproc->sz;
200 np->parent = curproc;
201 *np->tf = *curproc->tf;
202
203 // Clear %eax so that fork returns 0 in the child.
204 np->tf->eax = 0;
206 for(i = 0; i < NOFILE; i++)
207 if(curproc->ofile[i])
208 np->ofile[i] = filedup(curproc->ofile[i]);
209 np->cwd = idup(curproc->cwd);
210
211 safestrcpy(np->name, curproc->name, sizeof(curproc->name));
212
213 pid = np->pid;
214
215 acquire(&ptable.lock);
216
217 np->state = RUNNABLE;
218
219 release(&ptable.lock);
220
221 return pid;
222 }
...Copying page table of the parent process, size, trap-frame, open files state, current working directory, name, and pid.
%eax is return register for the each processes. we set that value 0 for child process to return value 0.
Summary of fork():
-
The allocproc function creates a new process data structure, and allocates a new kernel stack.On the kernel stack of a new process, it pushes a trap frame and a context structure. The fork function copies the parent’s trap frame onto the child’s trap frame. As a result, both child and the parent return to the same point in the program, right after the fork system call.
The only difference is that the fork function zeroes out the EAX register in the child’s trap frame, which is the return value from fork, causing the child to return with the value 0. On the other hand, the parent returns with the pid of the child. -
In addition to the trap frame, the child’s kernel stack also has the context data structure. Normally, processes have this context data structure pushed onto the kernel stack when they are being switched out, so that this data structure can be used to restore context when the process has to resume again. For a new process, this context structure is pushed onto the stack by allocproc, so that the scheduler can start scheduling this new process like any other process. The instruction pointer in this (somewhat artificially created) context data structure is set to point to a piece of code called forkret, which is where this process starts executing when the scheduler swaps it in. The function forkret mainly calls trapret (and does a few other things we’ll see later). So, when the child process resumes, it also starts executing the code corresponding to the return from a trap, much like its parent. This is the reason why the child process returns to exactly same instruction after the fork system call, much like the parent, with only a different return value.
Actual implementation of clone() systemcall:
before start:
the trap frame stores context before handling a trap.
the context structure stores context during a context switch.
x86 registers:
1. EAX, EBX, ECX, EDX, ESI, and EDI are general purpose registers used to store variables during computations.
2. The general purpose registers EBP and ESP store the base and top of the current stack frame.
3. The program counter (PC) is also referred to as EIP (instruction pointer).
The ESP register should be pointing to the old stack as before, and EIP should contain the return address from where the process resumes execution.
The EAX register is used to pass and return values.
Pop the arguments from stack by incrementing esp register,
Push the arguments to stack by decrementing esp register.
user stack is single page sized, thus esp should point to stack + PGSIZE.
->because malloc()ed pointer points to lowest address of its allocated memory.
536 int
537 clone(void(*fcn)(void*, void*), void* arg1, void* arg2, void* stack)
538 {
539 int i, pid;
540 struct proc *np;
541 struct proc *curproc = myproc();
542
543 //share address space with parent process
544 np->pgdir = curproc->pgdir;
545
546 np->sz = curproc->sz;
547 np->parent = curproc;
548 *np->tf = *curproc->tf;
549
550 np->tf->eip = (uint)fcn; //instruction pointer, where the kernel should return after trap
551
552 char *sp; //stack pointer; char = 1 byte
553 sp = stack + PGSIZE;
554
555 sp -= 4;
556 *(uint*)sp = *(uint*)arg2; //unsigned int = 4 byte
557 sp -= 4;
558 *(uint*)sp = *(uint*)arg1;
559 np->tf->esp = (uint)sp;sysproc.c
93 int
94 sys_clone(void)
95 {
96 void *fcn, *arg1, *arg2, *stack;
97 if(argptr(0, (char**)(&fcn), sizeof(void(*)(void*, void*))) < 0 ||
98 argptr(1, (char**)(&arg1), sizeof(void*)) < 0 ||
99 argptr(2, (char**)(&arg2), sizeof(void*)) < 0 ||
100 argptr(3, (char**)(&stack), sizeof(PGSIZE)) < 0) {
101 return -1;
102 }
103 return clone((void(*)(void*, void*))fcn, arg1, arg2, stack);
104 }
이부분 해결하기: uses a fake return PC (0xffffffff); a proper thread will simply call exit() when it is done (and not return)..? - 일단 보류
join() systemcall:
Track the wait() system call:
272 int
273 wait(void)
274 {
275 struct proc *p;
276 int havekids, pid;
277 struct proc *curproc = myproc();
278
279 acquire(&ptable.lock);
280 for(;;){
281 // Scan through table looking for exited children.
282 havekids = 0;
283 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
284 if(p->parent != curproc)
285 continue;
286 havekids = 1;
287 if(p->state == ZOMBIE){
288 // Found one.
289 pid = p->pid;
290 kfree(p->kstack);
291 p->kstack = 0;
292 freevm(p->pgdir);
293 p->pid = 0;
294 p->parent = 0;
295 p->name[0] = 0;
296 p->killed = 0;
297 p->state = UNUSED;
298 release(&ptable.lock);
299 return pid;
300 }
301 }
302
303 // No point waiting if we don't have any children.
304 if(!havekids || curproc->killed){
305 release(&ptable.lock);
306 return -1;
307 }
308
309 // Wait for children to exit. (See wakeup1 call in proc_exit.)
310 sleep(curproc, &ptable.lock); //DOC: wait-sleep
311 }
312 }
ZOMBIE State = final state where it has exited but has not yet been cleaned up (in UNIX-based systems, this is called the zombie state)
by calling wait(), cleaning the zombie state.
287: if parent process find a ZOMBIE child process, it cleans up the child process and return.
310: but if not found, parent process goes to sleep and waiting for child process to wake parent up by exit()ing(exit() function calls wakeup1() func).
Actual implementation of join() system call:
588 int
589 join(void)
590 {
591 struct proc *p;
592 int havekids, pid;
593 struct proc *curproc = myproc();
594
595 acquire(&ptable.lock);
596 for(;;){
597 // Scan through table looking for exited children.
598 havekids = 0;
599 for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
600 if(p->parent != curproc)
601 continue;
602 havekids = 1;
603 if(p->state == ZOMBIE){
604 // Found one.
605 pid = p->pid;
606 kfree(p->kstack);
607 p->kstack = 0;
608 //freevm(p->pgdir); //it will free the parent pgdir as well.
609 p->pid = 0;
610 p->parent = 0;
611 p->name[0] = 0;
612 p->killed = 0;
613 p->state = UNUSED;
614 release(&ptable.lock);
615 return pid;
616 }
617 }
618
619 // No point waiting if we don't have any children.
620 if(!havekids || curproc->killed){
621 release(&ptable.lock);
622 return -1;
623 }
624
625 // Wait for children to exit. (See wakeup1 call in proc_exit.)
626 sleep(curproc, &ptable.lock); //DOC: wait-sleep
627 }
628 }608: freeing vm of child zombie thread will leads to freeing vm of parent process.
syscall.c will be written after thread library code.
thread library:
thread_create():
ulib.c
109 int thread_create(void (*start_routine)(void*, void*), void *arg1, void *arg2) {
110 void *stack = malloc(4096); //single PGSIZE stack
111 return clone(start_routine, arg1, arg2, stack);
112 }thread_join():
It should free the user stack.
-> initial user stack pointer(malloc()ed pointer) should be known to free() the allocated user stack memory
proc.h
38 struct proc {
52 void *usp; //user stack pointer
53 };proc.c
536 int
537 clone(void(*fcn)(void*, void*), void* arg1, void* arg2, void* stack)
557 np->usp = stack;now, we are able to know user stack pointer by looking a usp member.
589 int
590 join(void** stack)
591 {
604 if(p->state == ZOMBIE){
607 *stack = p->usp;;
615 p->usp = 0;
...ulib.c
115 int thread_join(void) {
116 void *stack;
117 int r = join(&stack);
118 return r;
119 }sysproc.c
106 int
107 sys_join(void)
108 {
109 void* stack;
110 if(argptr(0, (char**)(&stack), sizeof(void*) < 0)
111 return -1;
112 return join(&stack);
113 }you have to link ulib.o and umalloc.o otherwise you cannnot use malloc & free function in ulib.c.
Makefile
153 _forktest: forktest.o $(ULIB)
154 # forktest has less library code linked in - needs to be small
155 # in order to be able to max out the proc table.
156 $(LD) $(LDFLAGS) -N -e main -Ttext 0x1000 -o _forktest forktest.o ulib.o usys.o u
malloc.o
확인:
1 #include "types.h"
2 #include "user.h"
3
4
5 void thread_func(void* arg1, void* arg2) {
6
7 int pid = getpid();
8 printf(1,"child thread pid is %d\n", pid);
9 printf(1,"arg1 = %d, arg2 = %d\n", (int*)arg1, (int*)arg2);
10 exit();
11 }
12
13 int main(void) {
14 int arg1 = 11;
15 int arg2 = 22;
16 thread_create((void(*)(void*,void*))&thread_func, &arg1, &arg2);
17 thread_join();
18 int pid = getpid();
19 printf(1,"parent pid is %d\n", pid);
20 }
