Troubleshooting Tips for Lab 3.0

Okay so this lab is fairly difficult, but it is also fairly straight forward. Much of the difficulty comes from debugging problems most of us have no experience with.

I have given an overview of the Lab, which I may do an update to if I have time; a thing I am currently fairly short of, and I will now give some tips for debugging I have learned to hopefully help minimize your debugging time. I could give a more in depth overview of coremap, pages table, etc. but the lecture content already does a very good job.

Debugging Tips


Multiple Entries in the TLB

This could be caused by 1 of 2 major reasons. The first of which is a programming error in which you could read an incorrect entry from your page table causing you to write the same entry to the TLB a second time.

A second reason could be that you forgot to to OR in the VALID bit in your TLB entry.

 Asserts failing in subpage_kmalloc()


Check all of your programming. This is most likely cause by a double free! Check all of your logic. Try commenting out frees until your problem goes away. However if you comment out all the frees in your program and this does not fix the problem then it is obviously not a double free.

Another cause could be freeing the wrong memory and reusing it somewhere else. If this memory belongs to one of your kernel structures i.e. a page table or the core map, this could cause major problems and very confusing errors.


These were two time consuming errors so hopefully this will help. If you have any other problems that most importantly you can articulate well, I can try and help.

I have been told that people have commented but they do not seem to be appearing. Checked the spam inbox; nothing. So you are welcome to email me at dixon_171 at hotmail dot com. This is not a primary email so you can feel free to spam it I will just ignore it.

-FlounderingZ

Kernel Space does not go through the TLB

This confused me for a bit but now I have got it all sorted out.

Any virtual address greater than 0x80000000 does NOT go through the TLB. So all you have to do in allock_pages is find an open slot in your coremap and return paddr + 0x80000000. No need to write into your TLB or any processes page tables.

Hope this clears up any confusion between User Mode virtual addresses and Kernel Mode virtual addresses

- FlounderingZ

Coremaps and On-Demand Paging

 

Welcome to part 1 of Assignment #3, ‘the hardest assignment of your university career’ – Guest lecturer on Tuesday (sorry I don’t recall you name).

The entire VM system is fairly complicated but I will try and focus on just what you need for part 1. I may mention some things you will want to think about when designing your components that will not come until later parts so if I don’t explain them that is probably why. I would also like to remind everyone reading this that Prof. Lie has broken down this assignment very well already and his Lecture slides are very informative so please use them to your advantage to fill in any holes I leave.

Also I don’t have an internet connection so I may be guessing at the semantics of some things. Feel free to correct me. Then again, you are free to change anything in the system if you feel your method makes more sense or is more efficient.

Coremaps

A coremap is a mixture between a bitmap and some sort of inverted page table, although it is NOT a replacement for an IPT. I’m sure it could be, but a coremap is an abstraction over managing physical memory whereas an IPT is an abstraction over accessing physical memory.

Please refer to the lecture as it explains exactly what a coremap is (structure wise), I will explain how this construct applies to the assignment and how to use it as an abstraction.

The coremap will be what is doing the heavy lifting for getppages, alloc_kpages, and free_kpages. I will go over what each of these should do.

getppages – This function should simply get the next available physical page and return it. If there are no pages available you could return 0 so that alloc_kpages will attempt to swap or otherwise free a page, or you could do that within this function. This is the main interface to the Coremap. This is where you take in a VPN find an available PFN and pass it back to alloc_kpages. Remember that your Coremap is a hashtable but with some special properties. You CANNOT have more VPN in the hashtable than PFN unless some address spaces are sharing physical memory. This differs from a normal hash table in that chaining as a method of collision resolution becomes complicated. You must point back into your array of nodes rather than pointing to a linked list. What you store in your Coremap is really up to you. You could store ASIDs and PIDs, you could throw pointers to thread structures in there etc. Although I would suggest PIDs over thread pointers since you already build a level of abstraction for finding threads by PID for waitpid.

alloc_kpages – This function is called by kmalloc, please go check out the malloc implementation, see where this is used, etc. This function will be returning a vaddr back to kmalloc. Where does this vaddr come from? Well it will be coming from the coremap but you are also going to want to add all the page information into your page table however you decide to implement that. You may want to build some sort of abstraction over allocating multiple pages at once to store some information about memory allocations and allowing you to free multiple pages at a time. Involved with this you may want to make getppages attempt to get as many pages in a row as possible and if this is less than the total number you need then just try again. I would not suggest swapping things out to make room for a complete piece of memory however, also since swap doesn’t exist yet that causes another problem

free_kpages – This function will be called by kfree. This function will most likely be very simple if you have made some sort of abstraction over memory allocation of multiple pages. This function will be interfacing with the core map because for each page it frees it has to look it up in the coremap and invalidate it in both the coremap as well as in the owner thread’s page table. Copy-on-write semantics may complicate this a little but I think you could just remove the thread from the list of threads sharing that page since the “free” is technically writing changes to the page so it should “copy” it and then “free” it aka don’t do either just delete you reference from the coremap as well as your page table.

 

On-Demand memory allocation

This section of the assignment has a lot to with the implementation of your address space but also involves your coremap. This section will be responsible for defining the as_*** functions and how vm_fault works. For the address space functions you need to understand what each one does.

as_create – This funciton allocates space, in the kernel, for a structure that does the bookkeeping for a single address space. It does NOT allocate space for the stack, the program binary, etc., just the structure that hold information about the address space.

as_prepare_load – this function is called just before the text or data sections are loaded into memory. They will just get the required pages for those sections. You may not need this anymore since you should only be allocating pages in vm_fault and you should be modifying load_elf to do on-demand loading of the program rather than loading everything at once.

as_define_region – This function is called in load_elf and simply sets up the bookkeeping for the data and text regions. You will use this data to recognize different types of page faults.

as_activate – This function activates a given address space as the currently in use one. Currently this just invalidates the entire TLB on a context switch but you can give address spaces unique identifiers and then use these in the TLB to differentiate between which address space is currently in use to save on overhead during a context switch. If you do that then this function will just set a global variable or something to the address space ID you wish to be the one you search in the TLB for.

as_destroy – This will actually do something now!!! Throw some asserts in to ensure that everything is how you expect it to be. You may need to free all the pages inside your page table, or maybe this is done earlier and you should assert that the table is empty. Then free the bookkeeping structure and continue on your way.

vm_fault

This guy is responsible for all the cool stuff. When the hardware decides it cannot find an address if jumps to the TLB exception handler. This calls vm_fault so this is where you should make the magic happen. First decide what kind of fault it is i.e. a read or a write. If it is a read then if you hit a page fault that is bad news and you should probably kill that program. If it is a write and you have a page fault then you should check if is allowed. If the fault is because someone is writing to just below the last page of their stack, give them a new one that is how the stack is supposed to work. If it is someone using the heap they should have used sbrk so again kill the program, or return some sort of error if possible. To check if you have a page fault you will be checking to see if there is an entry in the page table. If not and you have a legal page fault then you will want to get a pages from the coremap, add it to the page table, write the entry into the TLB and restart the instruction. If you do find it in the page table then simply write it into the TLB and restart the instruction. The only way for a load or store instruction to complete is if there is a mapping in the TLB. Our software is simply responsible for adding the required mappings in.

Splitting up the work

This is extra important for this assignment since we are a little short on time. There are 2 good ways in my opinion of breaking up this assignment. The first is to have one partner do part 1 and the other do part 2. This will work well for a group with a good understanding of how the entire VM system works. One person implements getting pages from memory and the other implements when and how a process should get that back. Part 2 is an abstraction built on top of part 1 so to do this simultaneously you will need good communication and a good understanding of the whole system.

A second method of doing this would be pairs programming or very heavy code review. Pairs programming involves programming at the same time together. This is a popular style of programming as you catch bugs before they have a chance to happen. Code review means nothing gets checked into the code repository until someone has reviewed it. This means you can work on this simultaneously but you do not compile and test until you have done code review on each others work.

With good communication between group members this assignment should be difficult be very manageable.

One last thing. The minimum you need to implement to test this will be the coremap, page tables, address space structure, as_* functions and vm_fault, wait that’s everything. You can skip some optimizations like the one involving the program file until after you have tested but almost everything is defendant on the vm.

Also, your vm should be one of the first things you bootstrap.

Questions can be left in the comments

 

- FlounderingZ

How to copy arguments from kernel buffers into a new address space

One of the major complexities to execv is copying the arguments from kernel buffers back into the new user space.

The first question you have to ask is, where do I copy them to? Well the only address you have that is valid in that userspace is the stack pointer.

What you are going to want to do is use the stack to store the arguments and then give the user program a modified stack pointer.

You are going to need to count the total number of strings you bring in as well as the total number of character  (including the null terminators).

Take the total size of what you need to store, (num_strings * size of a char pointer) + (num_of_chars) and subtract this from the stack pointer (stack grows down) . Now that you have reserved the size you need you can write to it. Remember that pointer access to an array grows upwards so write the first pointer of your list to stackptr - total size.

Interestingly you want to give the user program the new stack pointer so it doesn't over write your data and you also need to give it a pointer (in userspace) to the argument list. These are the same thing!

Here is a picture of the stack that should make all of this more clear.

Remember the stack pointer must be aligned to 4 bytes so round up to the next highest multiple of 4.

Wrote this one quick. If you have any questions leave a comment. There may be other ways of doing this but beware DumbVM does some fairly dumb things so make sure you fully understand what is going on because if you are reusing physical memory unintentionally your values may work now but not when you implement paging.

- FlounderingZ

OS161 waitpid

The waitpid system call in OS161 has implications in more places than just the files involved with adding a system call. The design of waitpid will have implications in the way you create and destroy threads, and how you exit threads cleanly.

Let us first go over the high level concepts of what the entire waitpid system will need to do.

PID Management

I will run on the assumption that you have created a way of getting the next available PID in your system along with the getpid system call. I will refer to the getting of the next PID as a function called get_new_pid.

So what does this system of allowing processes to wait on each other need to do.

First of all we need a way of getting the thread structure of a process based on it's PID. We need to do this because the semantics of waitpid state that we need to return some information about the process so the simplest way (although not the only) would be to have public members of the thread structure for waitpid's use. Additionally, the scheduler operates on thread structures and we will most likely need similar information in the scheduler and waitpid mechanisms so the thread structure seems like the simplest option.

So how can we get a thread structure from a pid? Data Structures are your friends! Hash Tables, Linked Lists, Binary Trees, Resizing Arrays, etc. Be creative, use something you are comfortable with and you know will have a stable implementation. For the purposes of this post I will refer to however you created this mechanism as get_thread_by_pid(). Along with this you will have things such as add_thread_by_pid(), remove_thread_by_pid(), etc. These are just standard methods for adding to your chosen data structure and removing

You are going to want to add_thread_by_pid() after get_new_pid() and when a thread is being destroyed you are going to need to remove_thread_by_pid() and allow the pid to be reclaimed.

Once this is implemented you will be able to get a thread structure based on a PID. The semantics of waitpid state that the parent must receive the child's exit code. A way of doing this would be to, during the exit system call, save the exit code into the thread structure and then get_thread_by_pid() and read from the thread structure in the thread that is waiting.

waitpid

Now lets talk about actually implementing waitpid. This call should not be that complicated, most of the code is just book keeping. You could implement this by recreating another piece of code and just sleeping on the address of the child thread and then having the child thread call thread_wakeupone (assuming you implemented something like this) when it exits. You could also choose to use a condition variable instead of recreating the CV code. You would probably want to store the CV object in the thread structure. Also remember that if you want to add something to the thread structure be sure to initialize it in thread_create.

One last thing that you need to worry about is a race condition when the thread exits. You will be trying to get_thread_by_pid at the same time that exorcise is going to be trying to delete that thread structure. One way you can get around this would be to add a new thread state that would represent a thread that has exited but is not yet a zombie because someone has been waiting on it. To do this you would also need to know if someone is waiting on you. You may also want to have a list of who is waiting on you, notify them in a FIFO order etc. You must conform to the semantics detailed in the man pages for OS161 and anything else is just going to be bonus. You would also need to modify thread_exit so that if it has any waiters it won't add the thread to the zombies array, waking all waiters first. This is the part that involves the biggest design decision. I hope that this gives you guidance on what exactly needs to be done but there is no way to be more specific without giving a solution. Just remember that you need to return your exit code to any waiters, handle memory correctly, and eliminate a race condition with exorcise.

This is a preliminary analysis from my standpoint so if there are any specific implementation problems people are having I can try and answer them in the comments.

To those who celebrate a very Happy Thanksgiving and to those who don't enjoy your long weekend! (Although I hope those who celebrate enjoy their weekends as well!)

- FlounderingZ

OS161 Execv Part 2

Continuing from part 1, what exactly do we have left to do and what do we have accomplished?

First of all we have added the syscall to the kernel but it is currently empty. So we have a call to execv(const char *progname, char **args); from the user side which means that the arguments we get on the kernel side are as above.

All we really need to do now is recreate runprogram() with some very small tweaks.

Let us go over what runprogram() does and then we will see what tweaks need to be made.

runprogram

The first thing it does is look for the file name provided. Next we create a new address space and activate it in the TLB (Translation Lookaside Buffer) which is how the hardware caches memory access and is a part of the MIPS ISA (Instruction Set Architechture).

Now that we have our address space set up we can call load_elf which handles the semantics of the ELF format and loading into the correct segment of our address space for us.

Now that we have the binary in memory we can close that file and define our usermode stack.

runprogram() now calls md_usermode which warps it into usermode to start executing at entrypoint which is the location of (most likely) the start symbol in the binary. entrypoint is returned from load_elf, yet another thing we don't have to trouble ourselves with.

So runprogram is done, what is different for execv?

execv

For execv we need to pass the arguments to the program through the exception handler, into the kernel syscall, do some work, pass them to md_usermode.

So getting them through the exception handler is done for you and is detailed in part 1, and passing the to md_usermode is quite obviously trivial.

The question is what work has to be done on them before you pass them to md_usermode?

All you really have to do is count how many arguments you have received in the char **args array and ensure that the last argument in the list is NULL. You can also check that the first argument matches the filename but this is a convention so you shouldn't be strict about it. Once you have counted the number of arguments, you may want to check that each is NULL terminated as well since they are strings, just pass argv and argc into md_usermode.

Remember that you are going to need to copy the arguments into kernel space from userspace and then back out to userspace. You will probably want to put them on the heap, using kmalloc, since the only thing you need to ensure is on the stack when going to usermode are the arguments which are just pointers. By having the memory on the heap we can still access it from usermode.

-FlounderingZ

OS161 Fork - Major Difficulties

A lot of people, including myself, have been having troubles with getting fork() to work as expected. Things like TLB misses on load or write, Bus errors, and other panic codes you never want to see.

What I am going to do is go over are Major Areas that can cause problems that are very difficult to find.

sys_fork

1.  You must copy the address space BEFORE you call thread fork other wise you have a synchronization issue.
2. You must also copy the trapframe BEFORE you call thread fork. The is however another small issue with this. The trapframe must be on the heap not the stack so the space must be allocated using kmalloc

md_forkentry

1. All you have to do is assign the pointer to the address space you passed in, into the thread structure. Don't worry about anything else.
2. You now have to copy the trapframe from the heap onto the stack of the current thread which means this time you DO NOT want to use kmalloc just declare a struct NOT a pointer and copy into that location.
3. Last you will want to increment your epc, set your retrun value to zero and make sure userland will see the return as a success (please see comment at the beginning and code at the end of mips_syscall)

That is it. There are really very few 'tricks' to fork() just a couple of hard to debug memory issues.

Feel free to put comments below I will try and answer them if they are appropriate

- FlounderingZ