CS537 P5: xv6 memory mapping

You will implement two additional system calls, getwmapinfo() and getpgdirinfo() for debugging and testing purposes.

Learning objectives:

• Understand how memory mapping works in modern systems.
• Learn about xv6 memory layout.
• Understand the relation between virtual and physical addresses
• Understand the use of the page fault handler for memory management

Administrivia:

• This project can be performed in groups of 2.
• Due Date: July 29th at 11:59PM (slip day policy will apply to both people in the the group)
• The final submission will be tested on lab machinesLinks to an external site., so make sure to test your code on these machines.

---

Details

1) Background

Memory mapping or mmap is a technique used in operating systems to create new mappings in the virtual address space of the calling process.
It has two modes of operation: anonymous and file-backed. Anonymous memory mapping is used to allocate memory without file backing, similar to malloc() and free(), but is more powerful. In fact, in most systems today, malloc() and free() invoke memory mapping system calls such as mmap() and munmap(). File-backed memory mapping is commonly used to map a file or a portion of a file into memory. This is an efficient way to access large files.

In this assignment, you will implement support for anomyous memory mapping in xv6. User processes can request the OS to create/delete memory mappings in its address space using system calls wmap() and wunmap(). Anonymous memory mappings created using this approach offers more control to the users than malloc() through the use of flags. Following are some details about this.

• In malloc, when you allocate some memory, it returns the virtual address of the allocated memory. However, through mmap, you can specify the virtual address where the memory should be, using MAP_FIXED flag.
• It supports demand paging. It means, when you need to allocate n bytes of memory, a virtual memory region of n bytes is reserved, but the actual physical memory pages are not allocated until they are accessed. Later, when the process tries to access that memory for the first time, a page fault occurs. The OS then allocates a physical page of memory and maps it to the corresponding virtual address. This process allows efficient use of memory by allocating pages only as they are needed, thereby reducing the initial memory footprint and avoiding unnecessary memory allocation. In this assignment, demand paging should be enabled by default and can  be disabled using MAP_POPULATE flag.
• When a process with a memory-mapping creates child processes, those child processes have the same mappings as the parent process. If there are any data in those mappings at the time of fork, the child should be able to read the same data after the fork through the mappings.
  • Using the MAP_SHARED flag, these memory regions can be shared, which means parent and child processes all have the same virtual mappings, and those mappings maps the same physical addresses. This allows processes to communicate and share data seamlessly, as any changes made to the memory are visible to all processes.
  • Alternatively, with the MAP_PRIVATE flag, parent and child will still have the same virtual mapping, but each process gets it own physical copy of the memory. At the time of the fork, the parent and child process will see the same data in the mappings, but later they can modify those data independently, so changes are not visible to each other. In original mmap(), an optimization strategy called copy-on-write (CoW) is used wherein the actual copying of physical pages is deferred until a write operation occurs. In this assignment, you don’t need to implement CoW.

 

2) Setup

• Define a macro MAPBASE inside memlayout.h file.

#define MAPBASE 0x60000000         // First mmap virtual address

• • Notice that memlayout.h already has another macro KERNBASE(0x80000000), that is used to separate the user space from the kernel space. The lower part of the virtual address space (0x00000000 to KERNBASE - 1) is used for user space (where user code, data, heap and stack reside), and the upper part (KERNBASE to 0xFFFFFFFF) is used for kernel space (where the OS code and data reside).
  • We will use a predefined starting address (MAPBASE) for mmap regions. This helps to organize and separate the mmap regions from other parts of the process’s memory. By placing MAPBASE near the top of the user address space, it allows the rest of the user space (from 0x00000000 to 0x5FFFFFFF) to be used for other allocations such as stack, heap, and code segments. Here’s a simplified view of how the address space will look like (Figure 2-2 in the xv6 book will give a detailed view):

+--------------------------+ 0xFFFFFFFF (Top of virtual address space)
|        Kernel Space      |
|                          |
|       (Kernel code,      |
|       data, etc.)        |
+--------------------------+ 0x80000000 (KERNBASE)
|      User Space          |
|                          |
|     (Memory mapped       |
|     regions start here)  |
+--------------------------+ 0x60000000 (MAPBASE)
|                          |
|     (User heap, code,    |
|     stack, etc.)         |
|                          |
+--------------------------+ 0x00000000 (Start of user address space)

• • allocuvm() grows process from oldsz to newsz. Do not let a process grow beyond MAPBASE.
• Create a file named wmap.h with the following contents inside your xv6 folder.

// Flags for wmap
#define MAP_PRIVATE 0x0001
#define MAP_SHARED 0x0002
#define MAP_POPULATE 0x0004
#define MAP_FIXED 0x0008

// for `getpgdirinfo`
#define MAX_UPAGE_INFO 32
struct pgdirinfo {
    uint n_upages;           // the number of allocated physical pages in the process's user address space
    uint va[MAX_UPAGE_INFO]; // the virtual addresses of the allocated physical pages in the process's user address space
    uint pa[MAX_UPAGE_INFO]; // the physical addresses of the allocated physical pages in the process's user address space
};

// for `getwmapinfo`
#define MAX_WMMAP_INFO 16
struct wmapinfo {
    int total_mmaps;                    // Total number of wmap regions
    int addr[MAX_WMMAP_INFO];           // Starting address of mapping
    int length[MAX_WMMAP_INFO];         // Size of mapping
    int n_loaded_pages[MAX_WMMAP_INFO]; // Number of pages physically loaded into memory
};

3) System Calls

You have to implement four system calls for this assignment.

3.1. wmap

int wmap(uint addr, int length, int flags)

wmap is similar to mmap(). It creates a new mapping in the virtual address space of the calling process. Creating memory mappings involve 3 steps: 1) allocating region in the virtual address space, 2) allocating physical memory, and 3) creating mappings (page tables) between the allocated virtual address region and the allocated physical pages.

wmap allocates length bytes of memory and returns the virtual address of the allocated memory. The returned address should be page-aligned. You must use virtual addresses only between MAPBASE and KERNBASE-1. If the provided length is not page-aligned, the length should be rounded off to next multiple of pagesize (4096 bytes).
Your implementation of wmap should have demand paging enabled by default, which means that physical memory should not be allocated during the system call. Instead, physical memory should be allocated during page faults. Also, when forking, the child process should have the same mappings as the parent process. You should return -1 for any type of error (e.g., the provided addr or length is not valid).

• length: The length of the mapping in bytes. It must be greater than 0.
• addr: The virtual address that wmap must use for the mapping, if MAP_FIXED flag is on. Otherwise, ignore this value. This address should be page-aligned and within MAPBASE and KERNBASE-1
• flags: enables or disables some features of wmap. Flags can be ORed together (e.g., MAP_PRIVATE | MAP_FIXED | MAP_POPULATE). These flags should be defined as constants in wmap.h header file. You have to implement four flags as explained in the following:
  • MAP_FIXED: If this is set, then the mapping must be placed at exactly addr. If this flag is not used, you can ignore addr. Also, a valid addr is a multiple of page size and within MAPBASE (0x60000000) and KERNBASE-1 (0x80000000-0x1).
  • MAP_POPULATE: Demand paging is enabled by default. If this flag is set, disable demand paging, which means that the physical memory will be allocated immediately during the system call.
  • MAP_SHARED: This flag tells wmap that the mapping is shared. Memory mappings are copied from the parent to the child across the fork system call. If the mapping is MAP_SHARED, then changes made by the child will be visible to the parent and vice versa.
  • MAP_PRIVATE: If this flag is set, then the mapping is not shared. You still need to copy the mappings from parent to child, but these mappings should use different physical pages. In other words, the same virtual addresses are mapped in child, but to a different set of physical pages. Note that between the flags MAP_SHARED and MAP_PRIVATE, one of them must be specified in flags. These two flags cannot be used together.

Enabling demand paging means that you don’t actually allocate any physical pages when wmap is called. You just track the allocated virtual address region using some structure. Later, when the process tries to access that memory, a page fault is generated which is handled by the kernel. In the kernel, you can now allocate a physical page and let the user resume execution.

To set up the page fault handler, you’ll add something like this to the trap() function in trap.c:

case T_PGFLT: // T_PGFLT = 14
    if page fault addr is part of a mapping: // demand paging
        // handle it
    else:
        cprintf("Segmentation Fault\n");
        // kill the process

3.2. wunmap

int wunmap(uint addr);

wunmap removes the memory mapped region that starts at addr in the process virtual address space. addr must be page-aligned and the start address of some existing wmap. It returns 0 if the memory map is removed successfully, otherwise -1 (e.g.: addr is not the start of any memory mapped region).

While removing a memory map, if it is MAP_SHARED and it was inherited from the parent, then be careful not to free the physical pages, because the parent process might still be using it. Note that when a child process calls exit(), the wait() called by the parent process frees the memory (from address 0x0 to KERNBASE) used by the child process by calling freevm(p->pgdir), which will free the shared mmap physical pages. You need to modify the code a little bit to avoid this.

3.3. getpgdirinfo

int getpgdirinfo(struct pgdirinfo *pdinfo);

getpgdirinfo retrieves information about the process address space by populating struct pgdirinfo. It returns 0 in case of successful retrieval of information, otherwise -1. This system call should calculate how many physical pages are currently allocated to the current process and store it in n_upages. It should also populate va[MAX_UPAGE_INFO] and pa[MAX_UPAGE_INFO] with the first 32 virtual page addresses and corresponding physical addresses, ordered by the virtual addresses. (Hint: You should only gather information (either for calculating n_upages or returning va/pa pairs) on pages with PTE_U set (i.e. user pages). The only way to do that is to directly consult the page table for the process.)

3.4. getwmapinfo

int getwmapinfo(struct wmapinfo *wminfo);

getwmapinfo retrieves information about the process address space by populating struct wmapinfo. This system call should calculate the current number of memory mapped regions in the process’s address space and store the result in total_mmaps. It should also populate addr[MAX_WMMAP_INFO] and length[MAX_WMAP_INFO] with the address and length of each memory map. as mentioned earlier, If an mmap’s provided length is not page-aligned, the length should be rounded off to next multiple of pagesize (4096 bytes). You can assume that the number of memory maps for any process will not exceed MAX_UPAGE_INFO. The n_loaded_pages[MAX_WMAP_INFO] should store how many pages have been physically allocated for each wmap. This field should reflect demand paging. For example, the length of a memory mapped region could be 8192 but the number of physical pages allocated for this region (n_loaded_pages) might be 0 because of demand paging.

3.5. Some simplifying assumptions

You can make the following simplifying assumptions:

• All mapped memory is readable/writable.
• The maximum number of memory maps is 16.
• The parent process will always exit after the child process.
• Because of demand paging, there might be some pages that are not yet physically allocated when calling fork(). We’ll make sure to use MAP_POPULATE flag for all mmaps before calling fork(), so you need not worry about this case.

 

4) A simple example of wmap and wunmap

Here, we walk you through a simple end-to-end example of a call to wmap. You may want to take a look at the helper functions referenced in this example – you’ll most likely need to use most of them in your implementation.
Suppose that we make the following call to `wmap`:

uint address = wmap(0x60000000, 8192, MAP_FIXED | MAP_SHARED | MAP_POPULATE);

This is the simplest combination of flags – we’re requesting a shared (MAP_SHARED) mapping having a length of two pages and starting at virtual address 0x60000000 (MAP_FIXED). In xv6, 1 page is 4096 bytes and 4096=0x1000. Let’s assume no memory mappings exist at the virtual address range 0x60000000 to 0x60002000 (8192 = 0x2000). So we can use create the requested memory mapping at virtual address 0x60000000 extending until 0x60002000. You should keep track of these mappings per process so you know what ranges of virtual addresses are free. You can create a struct that stores information relevant to a memory map, and store an array/list of such structs in the Process Control Block (struct proc). You might want to keep this array sorted by virtual address, which will make it easy to verify whether another memory mappings already exists in an address range or not.

So far we only talked about virtual address – there also needs to be some corresponding physical pages that are allocated for this mapped region. Since we use the MAP_POPULATE flag, physical memory needs to be allocated immediately. Physical addresses are managed at the granularity of a page, which is 4096 bytes long in xv6. You’ll just need to call existing functions (i.e., kalloc(), kfree() in kalloc.c) in the kernel to get free physical addresses. kalloc() and kfree() work at the granularity of a page (4096 bytes). So if you need 8192 bytes of physical memory, you need to call kalloc() twice, each time it will give you the starting address of a physical page that is 4096 bytes long. Needless to say that the physical addresses returned by the kernel are not necessarily contiguous in the physical address space.

So in our implementation, we would have to call

char *mem = kalloc();

where mem is the starting physical address of a free page we can use.

Note that we haven’t created mapping (page tables) between virtual addresses and physical adresses. We have just allocated virtual and physical regions/pages. To create such mappings, we need to create and place entries in the page table. The mappages function does exactly that. In this case, the call to mappages would be something like the following:

mappages(page_directory, 0x60000000, 4096, V2P(mem), PTE_W | PTE_U);

The first argument is the page table of the process to place the mapping for. Each process has a page table as defined in struct proc in proc.h. The last argument is the protection bits for this page. PTE_U means the page is user-accessible and PTE_W means it’s writable. There’s no flag for readable, because pages are always readable at least. For this project, you can always pass PTE_W|PTE_U as the last argument.
You should always apply the V2P (converts a virtual to physical address in the kernel) macro to the address that you get from kalloc. This is because of the way xv6 manages physical memory. The address returned by kalloc is not an actual physical address, it’s the virtual address that the kernel uses to access each physical page. Yes, all physical pages are also mapped in the kernel. To get more details on this, refer to the second chapter in the xv6 manual on page tables.

The above mappages() call will create page table mappings between virtual address 0x60000000 and the physical page returned by kalloc().

So, after the call to mappages, did we successfully map 8192 bytes of memory at 0x60000000? No! it maps only a single page. In xv6, we have to map one page at a time, each time requesting a new physical page from kalloc. So we may complete our mapping by doing a second call:

mem = kalloc();
mappages(page_directory, 0x60001000, 4096, V2P(mem), PTE_W | PTE_U);

Notice how we advanced the virtual address by one page (0x60001000 = 0x60000000 + 0x1000). Now you can quickly build up on this example and create mappings in a loop, getting as many pages as necessary from kalloc.

Now let’s see how to remove a mapping. Suppose the user accesses the pages we allocated at 0x60000000 for a while, and does a call to `wunmap`:

wunmap(0x60000000);

First we need to find any metadata that we maintain in the Process Control Block for the mmap starting at 0x60000000. Before removing the metadata of the mmap, we need to keep a note of the length of the mapped region. This will help us determine how many how many page table entries need to be deleted and how many physical pages need to be freed.

Next, the page table must be modified so that the user can no longer access those pages. walkpgdir function can be used for that purpose. A typical call to walkpgdir may look like this:

pte_t *pte = walkpgdir(page_directory, 0x60000000, 0);

It returns the page table entry that maps 0x60000000. We’ll eventually need to do *pte = 0, which will cause any future reference to that virtual address to fail. Before that, we need to free the physical page we received from kalloc. Each pte stores a set of flags (e.g. R/W) and a physical page address, called Page Frame Number or PFN for short. Using a simple mask operation, you can extract the physical address from the pte. Look at the macros defined in mmu.h. The final piece of the code will look like this:

physical_address = PTE_ADDR(*pte);
kfree(P2V(physical_address));
*pte = 0;

We need to apply P2V (converts a physical to virtual address in the kernel) because kfree (and kalloc, as explained before) only work with kernel virtual addresses. Only one page has been freed so far. You’ll need to do the exact same calls, but this time passing a virtual address of 0x60001000 to free the second page:

pte_t *pte = walkpgdir(page_directory, 0x60001000, 0);
physical_address = PTE_ADDR(*pte);
kfree(P2V(physical_address));
*pte = 0;

Memory mappings should be inherited by the child. To do this, you’ll need to modify the fork() system call or the internal logic of copyuvm() to copy the mappings from the parent process to the child across fork().

---

Hints

Like prior projects, start by making small additions to xv6. Make sure you provide the support for a basic allocation, then add more complex functionality. At each step, make sure you have not broken your code that was previously working — if so, stop and take time to see how the introduced changes caused the problem. The best way to achieve this is to use a version control system like git. This way, you can later refer to previous versions of your code if you break something.

Following these steps should help you with your implementation:

1. First of all, make sure you understand how xv6 does memory management. The second chapter of xv6 book gives a good insight of the memory layout in xv6. Furthermore, it references some related source files. Looking at those sources should help you understand how mapping happens. You’ll need to use those routines while implementing wmap. You will appreciate the time you spent on this step later.
2. Try to implement a basic wmap that supports MAP_FIXED|MAP_SHARED|MAP_POPULATE. It should just check if that particular region asked by the user is available or not. If it is, you should map the pages in that range.
3. Implement wunmap. For now, just remove the mappings.
4. Implement getwmapinfo and getpgdirinfo. Most of the tests depend on these two system calls to work.
5. Implement demand paging.
6. Modify your wmap such that it’s able to search for an available region in the process address space. This should make your wmap work without MAP_FIXED.
7. Copy mappings from parent to child across the fork() system call.
8. Implement MAP_PRIVATE. You’ll need to change fork() to behave differently if the mapping is private.

---

Testing and handin instructions

Test cases will be released later.

The handin directory will be  ~cs537-1/handin/LOGIN/p5where LOGIN is your CS login. Similar to P2 and P4, please create a subdirectory called ‘src’: ~cs537-1/handin/LOGIN/p5/src.

Copy all of your xv6 source files (but not .o files, please, or binaries!) into this directory.

Each project partner should turn in their joint code to each of their handin directories. Each person should place a file named partners.txt in their handin/p4 directory, so that we can tell who worked together on this project.  The format of partners.txt should be exactly as follows:

cslogin1 wiscNetid1 Lastname1 Firstname1
cslogin2 wiscNetid2 Lastname2 Firstname2

It does not matter who is 1 and who is 2.  If you worked alone, your partners.txt file should have only one line.  There should be no spaces within your first or last name; just use spaces to separate fields.

To repeat, both project partners should turn in their code and both should have a turnin/p2a/partners.txt file.