OS161 execv Part 1

The function prototype

So the first thing we will do is decipher exactly what the prototype in unistd.h means.

int execv(const char *prog, char *const *args);

The syscall takes a constant character pointer to the program name. This could be a string literal “testbin/progname” or a string you have created. The second argument is more interesting although not complicated. It is simply an array of constant character pointers. A little more in depth this means that the variable args may be changed i.e.

args = new_args_array;

Each pointer in the array of constant character pointers that args points to however cannot be modified i.e.

args[0] = "Hello"; //"Hello" is a const char * but no go.

All of this however is kind of irrelevant because we will be passing these values through a syscall so gcc wont be generating any code and we do not have to respect these rules. The prototype may however give you a useful warning if you try something silly.

 Dropping into the Kernel

This part is all done for you. Here is a checklist of how to add a syscall just in case you forgot

1. Add the value to callno.h in kern/include/kern (already done)
2. Add the user syscall prototype to include/unistd.h (already done)
3. Add the prototype of the kernel version of the syscall to kern/include/syscall.h
4. Add a case to the switch statement in kern/arch/mips/mips/syscall.c
5. Add a call to the kernel version of the syscall to the case you just added. (you may not know all of the semantics you need just yet but just add a //TODO and if you have problems later do a “grep –r ‘TODO’ *” from your top level directoy.)

But what about our arguments?

The comment at the top of kern/arch/mips/mips/syscall.c is very informative on this matter.

When the user call into libc uses the syscall instruction to drop into the kernel.

That instruction jumps to the exception symbol in exception.S in kern/arch/mips/mips. This does some setup, sets up the trapframe and then jumps to mips_trap in kern/arch/mips/mips/trap.c and then it is going to hand off execution to mips_syscall.

During the setup of the trapframe before the call to mips_trap our arguments from userland were saved into the trap frame. The arguments are available at tf->a0, tf->a1, tf->a2, tf->a3, although we only need a0 and a1.

So now we have our arguments… but we haven’t done anything yet, have we? Not really, but maybe there will be a part 2?

- FlounderingZ

OS161 PID Allocation

The quickest way to find a solution to essentially any problem you come across while working on OS161 is to look at the Linux kernel source or other similar resources.
Some useful sites include :

The IBM Technical Library

An IBM article on Linux Process Management 

Some of the Linux kernel read with a text-to-speech synthesizer (including text source) 

Linux Kernel Repository with tagged symbols 

Stack Overflow

How The Linux Kernel Works
Now obviously the Linux Kernel does a lot of optimizations and has many more features than we currently have to deal with in OS161 so I will keep the details light.

For our implementation each process will have a PID. In Linux each process may have many process IDs, thread group IDs, process group IDs, and session IDs, and all of these are included in the task_struct structure. Linux keeps all of these IDs tucked away in hashed doubly linked lists and iterates over them in very weird, very (assumingly) optimized ways.

We do not need a lot of these implementation details. What most of us are looking for is how does Linux keep track of PIDs of any type, how does it reclaim them, etc.

What the Linux kernel does is make an array of bitmaps (explanation to follow) that are the same size as memory pages. It uses these in combination with test and set operations to create a management system that does not use locks, is allocated page-by-page and thus has a low memory over head, and is scalable up to 4 million PIDs (the size of an unsigned int).

So, what is a bitmap. If you have heard of bitfields, same concept. The Linux kernel will initially allocate a single page of memory (probably 4KB) and use each bit to represent a PID. This allows you to determine if PIDs 0-4095 are in use using only 4KB. This is extensible because if the PID is greater than any value on the current page, allocate a new one. If the PID is greater than your defined max_pid, wrap around. To keep track of available PIDs per page, Linux has a counter associated with each page of how many PIDs are available. This is atomically incremented and decremented appropriately. This allows you to quickly identify if there are any PIDs left on a given page.

Once a process has a PID Linux does a few more things with it. It gets attached to the task, added to hashed-doubly-linked lists, etc. Since we do not expose threads to the user, only processes, we don’t have much more to worry about in our allocation scheme. You can even use the existing thread structure and assign the PID to the thread ID. You may need to be able to look up a thread structure (if you use it) by PID for things like parent-child relationships, waiting until a process reaches a certain state. These things can be accomplished other ways but you may want to throw all your processes into a hash table or something.

What should I do for OS161?
For OS161 you are not required to implement exactly what the Linux kernel does but understanding what a large system is useful information. Using this you could decide to make this on a smaller scale. If you only need 4096 PIDs, don’t bother with pages just use a single bit map. Feel free to think of other methods of implementing this, you could create a linked list of reclaimed PIDs and only increment your max PID when this is empty. Remember for an assignment like this simplicity can be your friend as school deadlines are not very flexible.

Hopefully this sheds some lights on the mystery of PID allocation
- FlounderingZ


Edit : Prof. Lie has read this content and feels it lies well within the guidelines of Academic Integrity at U of T. Feel free to share with your friends and check back for more.
Edit 2: Never edit a post after uploading from Windows Live Writer, wow!