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