M3: A virtual memory manager

• Due: Week 4
• Marks: 5 (-1 per week late)
• Design and implement a virtual memory management system to manage mapping and fault handling of processes within your operating system.

Use the provided frame table to implement a virtual memory manager that is responsible for managing the memory mapped into your processes which supports on-demand memory mapping of an application and an allocate-on-demand memory heap.

1. Current Implementation
2. A small malloc() intro
3. Malloc and musl libc peculiarities
4. Aarch64 page tables
5. The Milestone
6. Provided code
7. Design alternatives
8. Assessment
   1. Demonstration
   2. Show Stoppers
   3. Better Solutions

Current Implementation

The current implementation simply pre-maps in the pages for the single binary. Any actual VM page faults will trigger an assert() which halts the system, under the assumption something has gone wrong. The executable itself is mapped in with untracked frames (i.e. we leak them), and finally, the current sos application malloc implementation uses a static array.

A small malloc()intro

malloc is the standard library function to allocate memory in C. In our system, malloc is provided by the musl libc library. malloc manages memory from a bigger memory pool. In the SOS code you are provided, malloc uses memory from a pre-allocated array in the initial data section as the memory pool. This pool is fixed in size, and malloc returns NULL when the pool is exhausted. See the diagram below for an approximate picture of the memory layout. The code musl uses to allocate memory from the static region for SOS is in apps/sos/src/sys/morecore.c

SOS applications use an independent implementation that uses a pre-allocated memory pool in the application's data section (as shown in the middle of the diagram). The code musl libc uses in applications is in projects/aos/libsosapi/src/sys_morecore.c. So just for emphasis, there are two versions of the morecore code in the system.

One of the tasks of this milestone is to leverage virtual memory to create a dynamically allocated memory region for malloc's use, usually termed the heap, as shown at the bottom of the diagram. The dynamic region is allocated on-demand via VM faults, and can be expanded in range dynamically by requesting that SOS increase the brk point.

In this milestone, you will modify the application-level morecore routines in projects/aos/libsosapi/src/sys_morecore.c to use your dynamically-allocated memory region. Again, be sure you're modifying the morecore routines for sos applications, not SOS's own morecore routines.

Malloc and musl libc peculiarities

The malloc implementation in musl libc (i.e. the application C library) has two behaviours for implementing memory allocation of the memory pool:

• Musl expects a brk syscall that has similar semantics to the Linux brk syscall. The current implementation is sys_brk in projects/aos/libsosapi/src/sys_morecore.c and it returns memory from a static array, as described above.

• If malloc is called to allocate more than 112KiB, then musl libc does not allocate from the heap or increase the heap via sys_brk, but instead it uses mmap to create an large anonymous mapping. The sample implementation of this is the sys_mmap2 function in projects/aos/libsosapi/src/sys_morecore.c and it currently steals memory from the top of the static morecore region, and leaks memory on when it's released with munmap

Aarch64 page tables

Aarch64 has a four-level page table structure, where all structures are 4K in size and use 9 bits of the virtual address. The paging structures are as follows:

• Page Global Directory (PGD): the top level paging structure (the root of the virtual address space).
• Page Upper Directory (PUD): the second level paging structure.
• Page Directory (PD): the third level paging structure.
• Page Table (PT): the fourth level paging structure.

For a page to be mapped successfully, all 4 paging structures must exist first. In the provided code (map_frame_impl in mapping.c) this is done lazily, and no record is maintained of the allocated paging structures. When a mapping operation fails due to a missing paging structure, seL4 returns the amount of bits that could not be resolved, which can be retrieved with seL4_MappingFailedLookupLevel().

The Milestone

In this milestone you will:

• Implement a page table to translate virtual memory addresses to frame table entries. You need to consider where you will keep track of cptrs to all levels of the page table and to the frames themselves. Note that you will be creating shadow paging structures, as well as the hardware structures. You must track the intermediate hardware paging objects that map_frame_impl currently throws away, in order to later destroy the address space and free all memory when processes are deleted.

• Using our code as a guide only, create your own version of the map_frame(). Your version (say sos_map_frame()) will need to populate and use your data structures to keep track of address spaces, virtual addresses, frame physical addresses and cptrs. Note: The existing map_frame() is used internally and thus needs to continue to work as before, so be careful if modifying it.

• Design your application-level address space layout and permissions - including the stack, heap and other sections. You may wish to consider a region-like abstraction like OS/161.

• Change the current application-level malloc implementation to use virtual memory by modifying the sys_brk() to use the heap memory region, thus removing the need for a static array (just allow the application to fault in memory within the heap region), as shown at the bottom of the above diagram.

  • You will need to provide a system call interface for sys_brk() using the framework you devised in milestone 2.
  • You are not required to support the mmap syscall for anonymous memory in this project. We don't expect you to support applications calling malloc for sizes over 112KiB (you can gracefully fail those requests in the library). Note: there is a small bonus available for those who do implement mmap/munmap.

• Modify the bootstrap ELF-loading code to use your mapping functions, not the ut table directly. Update the implementation of sos_sys_read/write such that:

  • the amount of data transferred in each system call is not limited by the size of the IPC buffer,
  • data is not unnecessarily copied into or out of any intermediary buffers,
  • the system call operates correctly for buffers that are larger than the size of a page (or physical memory) or that overlap page boundaries, and
  • SOS does not crash due to invalid arguments being passed for system calls.

Provided code

A frame table has been provided to provide allocation and management of 4KiB untyped objects as memory frames for processes within SOS.

You should become familiar the interface in projects/aos/sos/src/frame_table.h and the implementation in projects/aos/sos/src/frame_table.c as you will need to extend this in a later milestone.

The frame table provides mechanisms to allocate and free frames that may be used to map memory into the address spaces of applications, as is already done in elf.c. These frames are all also mapped into the address space of SOS allowing their contents to be read and written.

Rather than providing pointers to each frame, the frame table provides 19-bit frame references that uniquely identify each frame being managed by the frame table.

Make sure to consider the impact of the cache hierarchy when reading data from frames mapped into other virtual address spaces.

Design alternatives

Probably the main thing that you should consider here is the layout of your processes address space. Some things you will want to consider is where you place various parts of memory such as the stack, heap and code segments. You may also have some other regions in your process address space, one of these is the IPC Buffer.

You should also think about if you want to make different ranges of the address space have different permissions, eg: you may want to make code read-only to prevent bugs, or have a guard page at the end of your stack to prevent overflow.

While not needed for this milestone, you should think about what book keeping is required to delete an address space and free all the resources associated with it.

Demonstration

The main demonstration here will be to show a user process running with a high stack pointer (> 0x8000000000). You should also demonstrate a user process using malloc() from a heap.

    #include <utils/page.h>

    #define NPAGES 270
    #define TEST_ADDRESS 0x8000000000

    /* called from pt_test */
    static void
    do_pt_test(char *buf)
    {
        int i;

        /* set */
        for (int i = 0; i < NPAGES; i++) {
          buf[i * PAGE_SIZE_4K] = i;
        }

        /* check */
        for (int i = 0; i < NPAGES; i++) {
          assert(buf[i * PAGE_SIZE_4K] == i);
        }
    }

    static void
    pt_test( void )
    {
        /* need a decent sized stack */
        char buf1[NPAGES * PAGE_SIZE_4K], *buf2 = NULL;

        /* check the stack is above phys mem */
        assert((void *) buf1 > (void *) TEST_ADDRESS);

        /* stack test */
        do_pt_test(buf1);

        /* heap test */
        buf2 = malloc(NPAGES * PAGE_SIZE_4K);
        assert(buf2);
        do_pt_test(buf2);
        free(buf2);
    }

You should also be able to explain to the tutor how your code works and any design decisions you took.

Show Stoppers

• Maximum heap size less than 16 MB
• Maximum stack size Less than 16 MB
• A one-level page table (unless it is a Hashed Page Table)
• Designs that leak the cptrs of frames or seL4-internal page tables.
• Page table look-ups that are not constant time (HPTs can tolerate a small amount of collision chaining).
• Designs that simply map memory on any fault regardless of location in the application virtual address space.
• Designs that allow user applications to map in NULL.
• A stack and heap that can run into each other
• Assuming allocation will never fail (ok to panic, but need to check result of allocation calls)
• A design that pre-maps all pages so that the VM fault handler is not invoked (or even implemented).
• Your implementation of sos_sys_read/write transfers data in the IPC buffer.
• Your implementation of sos_sys_read/write is unable to transfer a buffer that spans more than a single page.

Better Solutions

• As much heap and stack as the address space can provide.
• Designs that probe page table efficiently - minimal control flow checks in the critical path, and minimal levels traversed.
• Designs that don't use SOS's malloc to allocate SOS's page tables (to avoid hitting the fixed size of the memory pool).
• Designs that have a clear SOS-internal abstraction for tracking ranges of virtual memory for applications.
• Solutions that minimise the size of page table entries (e.g. only contain the equivalent of a PTE and a cptr).
• Enforcing read-only permissions as specified in the ELF file or API calls.
• Designs that defer the actual mapping of pages until they are used (mapping on the fault rather than always mapping on the initial request).