Printer-Friendly
Version
|
M3: A pager
Use your memory manager from M2 to write a simple VM fault handler that
supports on-demand memory mapping of an application and an
allocate-on-demand memory heap.
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.
- At this point, you do not need to support
the
brk system call to expand the
region. You can choose a fixed (large-ish) virtual
memory range. You can add a brk()
system call in a later milestone.
- 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.
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.
Assessment
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 if 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).
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.
Last modified:
17 Aug 2018.
|