1. Introduction

The demand paging project is organized into two parts (lab3=part1 and lab4=part2) where the main simplification introduced in Part 1 is not having per-process private heaps. The description below covers both Part 1 and Part 2, with the simplifications pertaining to Part 1 specified separately. Further specifics pertaining to Part 2 will be discussed after Part 1 has been completed.

It is assumed that you have read the Intel manuals (especially volume III, chapters 2, 3 and 5) and are comfortable with Intel specific details.

2. Goals

The ultimate goal of this project is to provide the facilities to implement the system calls listed below. This includes kernel data structures, virtual memory initialization, and additional interrupt handling.

3. System Calls

3.1 For Part 1 (Lab 3)

SYSCALL  srpolicy (int policy)

SYSCALL xmmap (int virtpage, int npages, unsigned int flags, bsd_t source)

Much like its UNIX counterpart (see man mmap), xmmap will map a source "file" ("backing store" here) of size npages pages to the virtual page virtpage. A process may call this multiple times to map data structures, code, etc. The only flags that we will support in this implementation are: MAP_SHARED and MAP_PRIVATE. MAP_PRIVATE will have to be implemented using copy-on-write.

Numerical values for the flags:

• MAP_SHARED: 1
• MAP_PRIVATE: 2

SYSCALL xmunmap (int virtpage)

This call, like munmap, should remove a virtual memory mapping. See "man munmap" for the details of the UNIX call.

3.2 For Part 2 (Lab 4)

SYSCALL vcreate (int *procaddr, int ssize, int hsize_in_pages, int priority, char *name, int nargs, long args)

This call will create a new XINU process. The difference from create() is that the process's heap will be private and exists in its virtual memory. The size of the heap (in number of **pages**, not bytes)  is specified by the user by hsize_in_pages parameter.

create() should be left (mostly) unmodified. Processes created with create should not have a private heap but should still be able to use xmmap().

WORD *vgetmem (int nbytes)

Much like getmem(), vgetmem() will allocate the desired amount of memory, if possible. The difference is that vgetmem() will get the memory from a process' private heap located in virtual memory. A call to getmem() will continue to allocate memory from the regular XINU kernel heap.

SYSCALL vfreemem (block_ptr, int size_in_bytes)

You will implement a corresponding vfreemem() call for the vgetmem (bytes) call. It will take two parameters, and will return OK or SYSERR. The two parameters are similar to those of the freemem() call in the original XINU. The type of the first argument block_ptr will depend on your own implementation.

4. Overall Organization

4.1 Memory and Backing Store

4.1.1 Backing Stores

1. bsd_t The backing store descriptor type is used to reference a backing store. The type declaration for it is in h/paging.h. This type is merely unsigned int.

   For practical reasons, each student is limited to 8 mappings at a time. You will use the IDs zero through seven to identify them. To maintain uniqueness, the given calls will transform the store ID based on the last four digits of your student ID. You must enter these last four digits in the appropriate place in h/paging.h.

2. int get_bs (bsd_t store, unsigned int npages) This call requests from the page server a new backing store with id store of size npages (in pages, not bytes). If the page server is able to create the new backing store, then the size of the new backing store is returned. If a backing store with this ID already exists, then the size of this existing backing store is returned. This size is in pages. If a size of 0 is requested, or the page server flags an error, SYSERR is returned.
3. int release_bs (bsd_t store) This call requests that the page server release the backing store with ID store.
4. SYSCALL read_bs (char *dst, bsd_t store, int pagenum) This copies the pagenumth page from the backing store referenced by store to dst. It returns OK on success, SYSERR otherwise. The first page of a backing store is page zero.
5. SYSCALL write_bs (char *src, bsd_t store, int pagenum) This copies a page pointed to by src to the pagenumth page of the backing store referenced by store. It returns OK on success, SYSERR otherwise.

With the basic support provided by the page server, there is the potential for kernel and application to have conflicting usage of backend stores: on one end the kernel needs to allocate a backend store for each private mapping, and on the other hand, the application code needs to allocate a backend store before performing memory mapped access on it. The solution to this problem is to implement a better API for backend stores, with some internal book-keeping, in order to ease the collaboration of kernel and application code. Implementing this API is part of this assignment; the API is as follows:

1. bsd_t allocate_bs(unsigned int npages): allocates a free backend store; returns a bs number if successful or -1 if they are all occupied
2. bsd_t deallocate_bs(bsd_t store): deallocate the backend store if it is not being used and return the bs number; return -1 otherwise
3. bsd_t open_bs(bsd_t store): return the store number if the backend is allocated and increase the use count; return -1 otherwise
4. bsd_t close_bs(bsd_t store): return the store number if successful and increase use count; return -1 otherwise

Clearly, there will be some book-keeping involved. The net benefit will be to offer a clean support for the shared and private mappings.

4.1.2 Memory Layout

As you can see, the version of XINU we will be using will compile to about 100K, or 25 pages. The PC has an area of memory from page 160 through the end of page 405 that cannot be used (this is referred to as the "HOLE" in initialize.c). We will place the free frames into pages 1024 through 4095, giving 3072 frames.

The frames will be used to store resident pages, page directories, and page tables. The remaining free memory below page 1024 is used for XINU's kernel heap (organized as a free list). getmem() and getstk() will obtain memory from this area (from the bottom and top respectively).

All memory below page 4096 will be "global." That is, it is usable and visible by all processes and accessible by simply using actual physical addresses. As a result, the first four page tables for every process will be the same, and thus should be shared.

Memory at page 4096 and above constitute a process' virtual memory. This address space is private and visible only to the process which owns it. Note that the process' private heap is located somewhere in this area.

4.1.3 Page Tables and Page Directories

4.2 Support Data Structures

4.2.1 Finding the Backing Store for a Virtual Address

To find this, you need to keep track of which backing store the process was allocated when it was created using vcreate (vcreate needs to call get_bs to allocate a backing store for the virtual heap). Finding the offset (i.e., the particular page within the store to write/read from) can be computed using the virtual page number. You may need to declare a new kernel data structure which maps virtual address spaces to backing store descriptors. We will call this: the backing store map. It should be a tuple, such as:

You should write a function that performs the lookup:

The function xmmap() will add a mapping to this table. xmunmap() will remove a mapping from this table.

4.2.2 Inverted Page Table

Of course, if we use an array of size NFRAMES, the frame number is implicit and we can just index into the array. With this structure, we can easily find the pid and virtual page number of the page held within any frame i. From that, we can easily find the backing store (using the backing store map), and compute which page within the backing store corresponds to the page in frame i.

You may also want to use this table to hold other information for page replacement (e.g., any data needed by the page replacement policy).

4.2.3 Part I Simplification

For Part I of the project, the virtual address is not private to a particular process. All the processes will share the same paging directory and page tables. Hence, the function f (pid, vaddr) described in Section 4.2.1 will degenerate to just f (vaddr) and the inverted page table need not contain the pid information.

4.3 Process Considerations

4.3.1 Process Creation

A mapping must be created for the new process' private heap, if created with vcreate().

4.3.2 Process Destruction

1. All frames which currently hold any of its pages should be written to the backing store and be freed.
2. All of its mappings should be removed from the backing store map.
3. The backing stores for its heap should be released (remember backing stores allocated by a process should persist unless the process explicitly releases them).
4. The frame used for the process' page directory and page tables should be released.

4.3.3 Context Switching

Think carefully about where exactly you execute this switch if you put it in resched(): should it be before or after the actual context switch (call to ctxsw)?

Note: For Part I of the project the infrastructure explained in 4.3.1 and 4.3.2 is not needed. The global page directory that will be shared by all the processes can be created as part of the null process.

4.3.4 System Initialization

The following should occur at system initialization:

1. Set the DS and SS segment limits to their highest values. This will allow processes to use memory up to the 4 GB limit, without generating general protection faults. Make sure the initial stack pointer (initsp) is set to
   1. a real physical address
   2. an address that corresponds to memory available to the kernel
   Please confer i386.c.
2. Initialize all necessary data structures.
3. Create the page tables which will map pages 0 through 4095 to the physical 16 MB. These will be called the global page tables.
4. Allocate and initialize a page directory for the NULL process.
5. Set the PDBR register to the page directory for the NULL process.
6. Install the page fault interrupt service routine.
7. Enable paging.

4.4 The Interrupt Service Routine (ISR)

Execution then jumps to the ISR. We do not use a common dispatcher for this ISR. To specify the page fault ISR in the interrupt vector, we must use

set evec(int interrupt, (void (*isr)(void)))

Your ISR should be a routine written in assembly (you *cannot* write the entire code in C). The first and last things the ISR should do are save and restore all general purpose registers respectively. It must also, at some point, remove the error code from the top of the stack. Like other ISRs, it should use iret (see Intel Volume II), not ret, to return once finished.

4.5 Page Faults and Replacement Policies

4.5.1 Page Faults

1. Get the faulted address a.
2. Let vp be the virtual page number of the page containing  the faulted address.
3. Let pd point to the current page directory.
4. Check that a is a legal address (i.e., that it has been mapped). If it is not, print an error message and kill the process.
5. Let p be the upper ten bits of a. [What does p represent?]
6. Let q be the bits [21:12] of a. [What does q represent?]
7. Let pt point to the p_th page table. If the p_th page table does not exist, obtain a frame for it and initialize it.
8. To page in the faulted page, do the following:
   1. Using the backing store map, find the store s and page offset o which correspond to vp.
   2. In the inverted page table, increment the reference count of the frame which holds pt. This indicates that one more of pt's entries is marked "present."
   3. Obtain a free frame, f .
   4. Copy the page o of store s to f .
   5. Update pt to mark the appropriate entry as present, and set any other fields. Also set the address portion within the entry to point to frame f.

4.5.2 Obtaining a Free Frame

The function to find a free page should do the following:

1. Search the inverted page table for an empty frame. If one exists, stop.
2. Else, pick a page to replace (using the current replacement policy).
3. Using the inverted page table, get vp, the virtual page number of the page to be replaced.
4. Let a be vp*4096 (the first virtual address on page vp).
5. Let p be the high 10 bits of a. Let q be bits [21:12] of a.
6. Let pid be the process id of the process owning vp.
7. Let pd point to the page directory of process pid.
8. Let pt point to the pid's p_th page table.
9. Mark the appropriate entry of pt as not present.
10. If the page being removed belongs to the current process, invalidate the TLB entry for the page vp, using the invlpg instruction (see Intel Volumes II and III for more details on this instruction).
11. In the inverted page table, decrement the reference count of the frame occupied by pt. If the reference count has reached zero, you should mark the appropriate entry in pd as "not present." This conserves frames by keeping only page tables which are necessary.
12. If the dirty bit for page vp was set in its page table, you must do the following:
1. Using the backing store map, find the store and page offset within the store, given pid and a. If the lookup fails, something is wrong. Print an error message and kill the process with id pid.
2. Write the page back to the backing store.

4.5.3 Page Replacement Policies

5. Required API Calls

None of XINU's other existing system call interfaces should be modified.

6. Details on the Intel Architecture and XINU

The following might also be useful for you to know:

1. We are using the Intel Pentium chip, not the Pentium Pro or Pentium II. Some details of those chips do not apply.
2. XINU uses the flat memory model, i.e., physical address = linear addresses.
3. The segments are set in i386.c in the function setsegs().
4. Pages are 4k (4096 bytes) in size.
5. The backend machines have 16 MB (4096 pages) of real memory.
6. Example code is given for getting and setting the control registers (see asm_ex.c). Another useful function, dump32.c, for dumping a binary number with labeled bits is also given.

7. Given Code

8. Debugging

If it helps, you can uncomment the #define's in evec.c to get a stack trace and register dump. Using this and nm on the file xinu.elf can help you locate where your program crashed. The most difficult problem to diagnose is when the machine simply reboots itself. This is usually the result of having a bad stack pointer. In such a case, the machine cannot give a trap. It is better to test your code unit-wise, and save working copies (to which you can revert back).

9. Instrumentation hooks

void hook_ptable_create(unsigned int pagenum)

where:

• pagenum is the number of the page table being created

This hook should be called when your implementation is creating a page table.
Example implementation for your usage:

kprintf("\n=== Created page table %d\n", p);

void hook_ptable_delete(unsigned int pagenum)

where:

• pagenum is the number of the page table being deleted

This hook should be called when your implementation is deleting a page table.
Example implementation for your usage:

kprintf("\n=== Deleted page table %d\n", p);

void hook_pfault(char *addr)

where:

• addr is the address that for which the page fault was generated

This hook should be called whenever the page fault handler is called.
Example implementation for your usage:

kprintf("\n=== Page fault for address %d\n", addr);

void hook_pswap_out(unsigned int pagenum, int framenb)

where:

• pagenum is the number of the page being swapped out
• framenum is the number of the frame that contains the page being swapped out

This hook should be called when your implementation is replacing (swapping out) a frame.
Example implementation for your usage:

kprintf("\n=== Replacing frame number %d, virtual page %d", framenum, pagenum);

#ifdef LOGGING_ON
kprintf.......
#endif

int get_faults()

Your implementation should maintain a count of the number of times the page fault handler has been called. get_faults() will return this number.
Important: put get_faults() in another file than sys/hooks.c. As explained below, your hooks will be replaced by ours for the grading (by replacing the sys/hooks.c file), hence the requirement to put get_faults() in another file.

10. What to Turn In

As usual, you will do an electronic turn-in. Towards the end of each part, you will receive instructions on how to carry out performance evaluation and how to submit them. In Part I, performance evaluation will center on correctness and dynamic paging performance under FIFO and MYPOLICY when using Xinu's core process model (create()).

1. Goto paging/compile directory and do "make clean".
2. Go to the parent directory of your paging directory.
3. Enter the following command:

   To turn in part1:

   turnin -c cs503 -p lab3 paging-fall2009

FAQ and PSO questions from previous semesters:
(Note: Since these questions are from previous semesters, and the XINU version-- among other things-- may have changed, please exercise caution while interpreting the following questions.)

We have listed the most important questions asked in previous semesters here. They are not in any order of importance. The questions on xmmap() did baffle quite a few, though.

*** An IMPORTANT directive:

        When using get_bs (store, pages), please do not make the pages parameter take values greater than 200. This might cause unnecessary congestion in the page server resulting in its crash (which happens often nonetheless!). Therefore,  please use get_bs (store, 200) or less.
 

(1) How can I get notes on GCM?

    Read the class slides for a high level description of GCM. Please note that the class notes and the answer to question (2) below describe all you need to implement. You will find other variations in the GCM descriptions in the literature-- do not worry about implementing any of them.

***(2) In what order should we go through the list of frames for testing and setting bits in GCM replacement policy? Fifo order, or from the start of the array, or some other order?

   You should start from the frame next to where you last stopped. You may have to maintain a pointer to frame (last_stopped) where you stopped last. For the next round, start from the next frame (next to last_stopped), and traverse the list of frames in a round-robin fashion. Update the pointer to frame (last_stopped) accordingly when you stop again.

(3) Should I integrate this lab with the previous labs?

    No, you need not.

(4) How do I compute the virtual page number from a virtual address?

    The most significant 20 bits of a virtual address form the virtual page number.

(5) Where is the mapping < pid, vpage, npages, store> maintained?

    This mapping is maintained inside the kernel. Since the "store"  can take only 8 values at most (because there are only 8 backing stores possible for any user), and no store can be mapped to more than one range of virtual memory at any time, the table that contains these mappings will contain only 8 entries. This table is placed in the kernel data segment (in the first 25 pages of the physical memory). You need not take any extra care about placing this table. Just create an array of 8 entries of the type of the mapping and that's all. It is pretty similar to semaph[] and proctab[].

(6) When can srpolicy() be called?

    This system call will NOT be called at arbitrary places inside your code to force changing from one replacement policy to another. For simplicity, you can assume that the default policy is fifo and if srpolicy(GCM) is called, it will be the first statement in the program. Therefore, you need not worry about switching from one replacement policy to another midway through execution.

(7) h/paging.h contains two structures pd_t and pt_t which contain a lot of bit fields. Initially which fields should be set in a page directory and a page table?

   For page directories, set the following bits, and make the other bits zero: pd_write always and pd_pres whenever the corresponding page tables are present in the main memory.

    For the four global page tables, set the following bits: pt_pres and pt_write. You can make others zero.

    (This answer should be fairly obvious if you have read the Intel manuals carefully. We are mentioning that just in case. Don't read too much into this answer and confuse yourself.)

(8) Where do we place the page tables and page directories?

    The page tables and page directories are to be placed in the following memory range: If your memory is divided into 4096 pages, then they should be placed in the range 1024-4096. They should be placed on page boundaries only, i.e., the starting address of any page table or page directory should be divisible by the size of the pages NBPG.

***(9) What is the use of xmmap()?  

  Though xmmap() is given in the first page of your handout, it is not the most important system call that you will implement. Also, it is not main part of the project. And it is not the only way by which you can access virtual memory and test your implementation.

    Then, how else can a process try to use virtual memory? I will give you one example

    main()
    {
            vcreate(process A,,, hsize_in_pages = 100, ,,,);        /* process A is created with a virtual heap of 100 pages */

    }

/* This virtual heap will be present in a backing store that is exclusive for this process alone. (No backing store will be shared across processes. Neither will the same backing store be mapped to multiple memory ranges.) */

/* This virtual heap present in a backing store will be mapped from in the address ranges 4096th page to 4196th page of this process. So, the backing store mapping table you maintain will contain an entry < process A's pid, 4096, 100, backing store number > */

 process A()
 {
    int *x;
    int temp;
     x = vgetmem(1000);  /* allocates some memory in the virtual heap which is in virtual memory */
    /* the following statement will cause a page fault. The page fault handling routine will read in the required page from backing store into the main memory, set the proper page tables and the page directory entries and re-execute the statement. */
    *x = 100;
    x++;
    *x = 200;
    temp = *x;  /* You are reading back from virtual heap to check if the previous write was successful */
    /* temp should have a value of 200 now */
    vfreemem(--x, 1000); /* frees the allocation in the virtual heap */
}

In the previous example, you accessed virtual memory, notice that the access creates a page fault and  will handle the page fault.  This example some fair idea about how to use your virtual memory and how to test your implementation of virtual memory.

Then, why do we need xmmap() and what does it do? xmmap() is very similar to mmap() of UNIX. It treats the backing stores as "files". One potential usage of xmmap() is as follows:

Process A:
            char *x;
            char temp;
            get_bs(4, 100);
            xmmap(7000, 4, 100);    /* This call simply creates an entry in the backing store mapping */
            x = 7000*4096;
            *x = 'Y';                          /* write into virtual memory, will create a fault and system should proceed as in the previous example */
            temp = *x;                        /* read back and check */
            xmunmap(...);

/* This can be thought of as you creating a file, whose name is "4". It is a big empty file of size 100 pages. You store a character 'A' as the first character in the file. But, instead of using file I/O operations, since you have mapped the file to a memory location, you modify the file by means of a memory modification !! */

Let us say there is another process B which executes the following code, a while after the previous code was executed (assume that  'Process A' has not executed release_bs(4))

    Process B:

            char *x;
            char temp_b;
            xmmap(6000, 4, 100);
            x = 6000 * 4096;
            temp_b = *x:   /* Surprise: Now, temp_b will get the value 'Y' written by the process A to this backing store '4' */

These examples should make the usage of xmmap() more clear. Think about it.
 

(10) Page fault handling routine (page fault ISR): What should be done here?

        Most of the students have had trouble writing this correctly. So I am giving a pseudo code for the implementation (which is easier if you do it in assembly)

                    clear all interrupts
                    Store error code in a global variable  /* if you use any temp register to do this, then make sure that you restore that value too */
                    save all registers
                    call C function to handle the interrupt and do all the required processing
                    restore all registers
                    remove error code from stack
                    restore interrupts
                    iret

If you have not written in assembly language before, look at some code written in assembly in XINU itself. Or disassemble some simple C code and check the assembly code. Not everything has to be implemented in assembly. It is very difficult. So, include a call to a C function which will handle everything.

(11) Are read_bs and write_bs blocking calls, and can they be used inside our interrupt handling routine?

        They are, but can be used inside the page fault handling routine. In fact, you cannot escape that.

(12) How do I test my replacement policies?

        The specifications say that the free memory in the main memory from the 1024th page to the 4096th page accounts for 3072 free frames. The above request asks you not to have more that 200 pages in a single backing store. There are 8 backing stores available for you. So, totally, you can have 1600 pages of virtual memory for different processes. This entire 1600 pages can be easily accommodated in our 3072 free frames. Thus, there will be no need for any page replacement at all! Then, how do we check our page replacement policy?

        There is a constant called NFRAMES in h/paging.h which has a value of 3072. Make sure that your entire code depends on this constant (not its value) as a measure of the available free frames. If this constant has a value of 3072, then we will have the problem stated above. But, if we change the value of the constant to (say) 400, then the number of free frames initially available is only 400, i.e., your main memory looks as if it only has 1024+NFRAMES = 1024+400 = 1424 frames of memory. Thus, you have ample scope to test your replacement policy by changing the NFRAMES constant.
 

***(13) Important clarifications about xmmap()

        There was some confusion about the course of action to be taken inside any xmmap (start_vpage, bs_store, npages) call  in the following cases:

 Case 1:    bs_store has already been mapped by a process.
 Case 2:    The range [start_vpage - start_vpage+npages] intersects with another mapping by the current process.

 Return SYSERR in both these cases.