Introduction
A basic feature of any programming library is a heap manager that handles the
allocation and freeing of memory resources. The memory manager is invoked every
time you allocate room for a class or object, and then when you no longer need
those resources. The heap manager is not a feature of the operating system, it
is rather provided by the maintainers of the programming language you are using.
Specifically, for C, one implementation of a heap manager comes from the
standard libc
library, and handles the calls to malloc
and free
. The heap
manager presents the users with a library that wraps around many system calls
that the operating system provides.
In this lab assignment, we will implement a basic heap manager for the C library in the xv6 operating system. However, note that the heap manager we will be designing is not built-into the operating system. Rather it lives entirely in user-space and is only accessible through a user-level API.
Learning Objectives
At the end of this lab assignment, you should be able to:
- Implement a basic memory manager for users of the xv6 operating system.
- Use the
sbrk
system call to reserve memory from the operating system. - Manage free memory and provide users with chunks of memory based on API requests.
Overview and Some Reading
We will implement the Rose-Hulman memory manager in the xv6 operating system by
providing support for two main function calls: rhmalloc
and rhfree
that
allocate memory on the heap, and free allocated memory, respectively. First, it
is a good idea to gain some familiarity with the standard libc
memory API,
specifically, malloc
and free
, by reading this
section from our textbook.
Furthermore, managing memory requires us to maintain a free list that tracks the free chunks of memory that can be allocated based on user requests. This section of our textbook provides a great deal of information about strategies to maintain a free list in a heap management system.
Briefly, our heap manager first allocates a large chunk (or slab) of memory from
the operating system by asking for it using the sbrk
system call. That chunk
of memory is now owned by the heap manager and can then be distributed to users
based on incoming requests. When a user makes a request for memory using the
rhmalloc
function, the memory manager will try to accommodate the request by
splitting the list of available memory and giving the user ownership over a
chunk of the requested size. Once the user is done with that chunk of memory,
they will use the rhfree
function call to give back ownership of the memory
area to the memory manager that merges it with its list of free memory chunks.
Note that throughout this lab, we will make several simplifying assumptions that
will make our lives easier and makes the process of implementing a memory
manager more enjoyable.
Getting the Source Code
To obtain the source code for this lab, follow the instructions below.
1. Commit and push your changes to your current branch
First, make sure all your changes to your current branch are pushed to your
repo. Recall that you can use git branch
to check which branch you are
currently on.
Follow the standard git add
, git commit
, and git push
workflow to push
your changes to your own private repo.
If at any point, you get permission issues, this most likely means that you are
trying to push to the class repo, which you do not have access for. To push to
your own main
branch, you can use:
$ git push origin main
2. Fetch the changes from our repo
From your Linux terminal, fetch our changes using:
$ git fetch upstream
Then, make sure you can see this lab’s branch, namely upstream/heapmm
.
$ git branch -a
* clab_solution
main
remotes/origin/clab_solution
remotes/origin/main
remotes/upstream/clab
remotes/upstream/heapmm
remotes/upstream/main
You might see more branches locally (under origin
) depending on what you have
done, but you should be good if remotes/upstream/heapmm
shows up.
3. Get the code in a new branch
Next, let’s checkout the heapmm
branch and create a new local branch for its
solution.
$ git checkout -b heapmm_solution upstream/heapmm
branch 'heapmm_solution' set up to track 'upstream/heapmm'.
Switched to a new branch 'heapmm_solution'
4. Push the changes to your repo
Finally, push your changes to your own repo to make sure the code is there and you can start editing.
$ git push --set-upstream origin heapmm_solution
Enumerating objects: 119, done.
Counting objects: 100% (119/119), done.
Delta compression using up to 56 threads
Compressing objects: 100% (64/64), done.
Writing objects: 100% (111/111), 42.50 KiB | 42.50 MiB/s, done.
Total 111 (delta 42), reused 111 (delta 42), pack-reused 0
remote: Resolving deltas: 100% (42/42), completed with 8 local objects.
remote:
remote: Create a pull request for 'heapmm_solution' on GitHub by visiting:
remote: https://github.com/user/csse332-labs-noureddi/pull/new/heapmm_solution
remote:
To github.com:user/csse332-labs-noureddi.git
* [new branch] heapmm_solution -> heapmm_solution
branch 'heapmm_solution' set up to track 'origin/heapmm_solution'.
Structures and Definitions
To get you started, we have provided you with some definitions and structures
that are going to be helpful for you in implementing our Rose-Hulman heap
manager. Let’s go through them one by one so we can understand what is going on.
We will start with the definitions in user/rhmalloc.h
and then move to the
helper functions in user/rhmalloc.c
.
Alignment
First, we have defined the maximum heap size to be 1MB of memory. In other
words, we only have 1MB of memory to allocate to the users’ requests. Normally,
the heap grows dynamically as we need more memory, but in this lab, we will make
the simplifying assumption that our heap never exceeds 1MB. If a user requests
an area that is larger than 1MB, our memory manager will simply refuse to
allocate memory and return an invalid pointer. Therefore, the MAX_HEAP_SIZE
macro is defined as 1024 x 1024 bytes as follows:
#define MAX_HEAP_SIZE 1024*1024
Next, we need to make sure that our chunks are properly aligned in memory. In
other words, we want all of our allocated and free memory chunks to be in
multiples of ALIGNMENT
bytes (for reasons that will become clearer later on in
the course). Therefore we define the ALIGNMENT
macro as the size of an
unsigned long
integer:
#define ALIGNMENT sizeof(unsigned long)
In addition, we define the macro ALIGN
that takes as input a size
in bytes,
and adjusts it so that it is a multiple of ALIGNMENT
bytes:
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))
For practical purposes, anytime a user wants to allocate s
bytes, we must
align those bytes to the closest multiple of ALIGNMENT
bytes by using the
ALIGN
macro as follows:
unsigned size_to_allocate = ALIGN(s);
The Metadata
Next, in order to keep track of our memory blocks, we must maintain a set of information about each block (like whether it is allocated or not, its size, etc.). We therefore define the struct metadata as follows:
struct __attribute__((aligned(8))) metadata {
unsigned size; /* The size of the block. */
unsigned in_use:1; /* Flag to indicate if the block is in use.*/
struct metadata *next; /* The next pointer in the linked list. */
struct metadata *prev; /* The prev pointer in the linked list. */
};
and then we define a new type based on this union to make it easier to code using:
typedef union metadata metadata_t;
The members of struct metadata
are explained in the comments above. The
__attribute__((aligned(8)))
modified makes sure that our structure’s size
(when queried with sizeof
) is always a multiple of 8 bytes; we rely on nifty
compiler tricks to make that happen!
Note that each block’s metadata contains two pointers, prev
and next
. This
indicates that the blocks are maintained in a simple doubly linked
list. For simplicity, we
assume that the blocks are sorted by increasing memory order. In other words,
the next
block always points to an address that is higher in memory, and the
prev
block always points to an address that is lower in memory.
Finally, note that in our Rose-Hulman memory manager, we keep track of both free and used blocks. Unlike more sophisticated memory managers who only keep track of a free list, we find it simpler to implement for our educational purposes to keep track of all of our blocks, regardless of whether they are free or in-use.
Globals and Helper Functions
Next, let’s take a look at the user/rhmalloc.c
file. The static global
variable heap_mem_start
is used by our memory manager to keep track of the
start of the region of memory to allocate. It is initialized to 0 (i.e.,
NULL
).
Second, the static metadata variable freelist
refers to the head of the list
of the doubly linked list of blocks to be allocated. Similar to
heap_mem_start
, it is initialized to 0 and should be re-initialized when the
heap manager is first called upon. Additionally, the function freelist_head
simply returns a pointer to the head of the list, i.e., it simply returns
freelist
. In a similar fashion, the function heap_start
returns the
heap_mem_start
pointer.
Implementation and Testing
The main trick we’ll play on our users is that we will embed a metadata
structure into the top of every memory region we return to them. For example,
if the user asks for 8 bytes, then what we actually allocate is 8 +
sizeof(struct metadata)
bytes, we place the struct metadata
at the top of
that memory region, and then return to the user a pointer to the first byte
after the metadata structure.
Our user therefore will never be aware of the presence of the struct metadata
at the top of their allocated memory region, we keep it hidden from them so we
can recover it when we need it.
A couple of questions you would need to ask yourself and answer throughout the lab:
- After we create a memory region for the user, how do we return to the user the address of the first byte after the metadata?
- Given a pointer from the user, how do we recover the metadata for the memory region?
- When deciding if we have enough memory, what is the size we need to check for?
Use these questions and their answers as guidelines for you throughout this lab.
Initialization
First thing we would like to implement is the initialization code in
rhmalloc_init
. This function should only be called once at the start to
communicate with the operating system kernel and reserve a large piece of memory
of size MAX_HEAP_SIZE
. It is also responsible for initializing
heap_mem_start
and the free list.
We have provided you with the starting code for this function. Here is how it
goes. First, we call heap_mem_start = sbrk(0);
to ask the operating system to
tell if it were to allocate any memory for us, where would the starting address
of that piece of memory be.
Next, we actually ask the OS to reserve a large slab of memory of size
MAX_HEAP_SIZE
for us using:
p = sbrk(MAX_HEAP_SIZE);
if(p == (char *)-1) {
fprintf(2, "sbrk failed:exiting....\n");
exit(1);
}
At that point in time, if the sbrk
system call succeeds, we will know for sure
that p == heap_mem_start
and that they both point to an area of memory that is
of size MAX_HEAP_SIZE
.
Your job in rhmalloc_init
is the implement the code that properly initializes
freelist
. Note that initially, we only have a single free block, so our doubly
linked list contains a single node only (in other words, the next
and prev
pointers are invalid). Here are a few hints to help you implement this function:
- Note that each block contains its own metadata at the top of the block. In
other words, the first
sizeof(metadata_t)
bytes of each block are reserved for that block’s metadata. This should help you obtainfreelist
fromp
. - Note that the
size
variable in each block refers to the usable size of that block, i.e., its size without its metadata. - All blocks start off not being in use.
Freeing everything
Next, let’s take a look at the rhfree_all
function. This function is tasked
with freeing everything and returning the previously allocated slab of memory
back to the operating system. We have implemented that function for you.
In short, calling the system call sbrk
with a negative number x
shrinks
a process’s memory region by x
bytes. That is why we make the call
sbrk(-MAX_HEAP_SIZE)
.
The next two lines simply reset freelist
and heap_mem_start
to 0.
Implementing rhmalloc
Now let’s start with implementing rhmalloc
. We have provided you with the
first two lines that call rhmalloc_init
in case freelist
has not been
initialized yet.
When a user requests x
bytes, the memory manager will search for a free block
that can fit those x
bytes plus the metadata required to maintain the
information about that block. Then, if the found block is much larger that x
bytes, the memory manager will split that block into two contiguous blocks, one
that is return to the user and one that contains the free bytes remaining from
the split operation. For example, ignoring the metadata bytes, if the memory
area initially consists of a single block of size 4 bytes, and the user requests
1 bytes, then the memory manager will split the 4 bytes block into two blocks:
one of size 1 byte that is returned to the user and another of size 3 bytes that
is still marked as free and can be used to allocate memory for other users.
Now you should implement the process by which our memory manager will allocate a
block of size
bytes to whoever called rhmalloc
. Here are a few hints:
- Note that we always allocate things in multiples of
ALIGNMENT
bytes. Therefore, as discussed earlier, you should use theALIGN
macro to figure out how many bytes to allocate for that user. - Next, your code must search the
freelist
for the first block that can fit the user’s requested size. Once you find such a block, two cases might arise:-
The found block can only fit the user’s request, then your search is done and you should update the block’s metadata and return to the user a pointer to the start of the usable section of the block (In other words, the user should not be aware of the presence of the
metadata_t
struct in the block).For example, if the free block you found is of size 24 bytes and the user requests 16 bytes, then it doesn’t make sense to split the block since it cannot fit any other request from the user. So we can bite the bullet and allocate to the full 24 bytes to the user even though they only needed 16 bytes.
-
The found block is larger than the user’s request, then we must split that block into two blocks, one that is returned to the user and another that is free and contains the remaining bytes. Then, if another request comes in, the memory manager will use the second block to service that user’s request.
-
Testing
Once you complete your implementation of rhmalloc
, you can use the
test_basic_alloc
test in user/lab01test.c
to verify that your code works
correctly. To do so, first compile your code using
$ make qemu
and then run the test with the parameter 1 to only run the test_basic_alloc
test case using
$ lab01test 1
test_basic_alloc(57): OK.
test_basic_alloc(61): OK.
test_basic_alloc(62): OK.
test_basic_alloc(63): OK.
test_basic_alloc(64): OK.
test_basic_alloc(68): OK.
test_basic_alloc(69): OK.
test_basic_alloc(70): OK.
test_basic_alloc(71): OK.
test_basic_alloc(72): OK.
test_basic_alloc(77): OK.
test_basic_alloc(81): OK.
test_basic_alloc(82): OK.
test_basic_alloc(83): OK.
test_basic_alloc(84): OK.
test_basic_alloc(87): OK.
test_basic_alloc(88): OK.
test_basic_alloc(90): OK.
test_basic_alloc(91): OK.
Again, just like in the previous lab, the number between parenthesis tells you which test case passed or failed.
Implementing rhfree
Next, let us implement rhfree
. Given a pointer ptr
, rhfree
will find the
memory block that ptr
belongs to and then mark that pointer as free by
updating the metadata of that specific block. And that is the basic operating of
the rhfree
call.
Testing basic rhfree
Once you have implemented the basic idea behind rhfree
, you can double check
the correctness of your code by running the test_basic_free
test case from
user/lab01test.c
as follows:
$ lab01test 2
test_basic_free(114): OK.
test_basic_free(115): OK.
test_basic_free(116): OK.
test_basic_free(117): OK.
test_basic_free(120): OK.
test_basic_free(128): OK.
test_basic_free(129): OK.
test_basic_free(132): OK.
test_basic_free(133): OK.
test_basic_free(134): OK.
test_basic_free(139): OK.
test_basic_free(140): OK.
test_basic_free(142): OK.
test_basic_free(143): OK.
test_basic_free(145): OK.
test_basic_free(150): OK.
test_basic_free(154): OK.
test_basic_free(155): OK.
Implementing coalescing
One disadvantage of implementing rhfree
in the basic way discussed above is
that if the users request to allocate a lot of tiny sized blocks and then free
them. The memory manager’s free list will end of a lot of tiny free blocks. And
if a user comes in with a request for a large piece of memory, then the memory
manager would not be able to service that request since it does not have a
contiguous large block of free memory.
Here is an example to make it clearer. Ignoring metadata, let’s assume initially
we have a single free block of size 4 bytes. Then a user makes 4 requests for 4
blocks of size 1 byte each, and then frees those blocks. Using our basic
rhfree
implementation, the memory manager will now contain a list of four free
blocks, each of size 1 byte.
If a user now comes in and asks for a block of 2 bytes of memory, the memory manger would not be able to service that request since it only has 4 blocks of size 1 byte each, but no blocks of size 2 bytes or more. This is bad because even though we actually have 4 bytes of free memory, we cannot service the user’s request because those 4 bytes are not in a single block.
To solve this problem, every time a user frees a pointer, we must check whether we can merge, or coalesce, any free blocks in our free list. Since we do this every time we free a pointer, we only need to check for adjacent blocks (i.e., we do not need to scan the entire free list, only the block adjacent to the block we have just freed).
Implementation and testing
To implement coalescing, when a user calls rhfree
, you must check if the freed
block is adjacent to another free block, and then merge those two blocks
together (while preserving the ordering of the pointers in the list). Note that
there are two cases we must take care of:
-
The freed block is the first in a pair of blocks that must be merged, then the resulting block will have the same address as that of the freed block, and the second block in the pair will no longer be addressable.
For example, if we have two blocks (
a -> b
) that are both free and each of size 1 byte, then we must merge those two into a single block with addressa
of size 2 bytes. -
The freed block is the second in a pair of blocks that must be merged, then the results block will have the address of the first block in the pair and the free block will no longer be addressable.
For example, if we free a block
a
and then find a blockc
that is also free, and such thatc
directly precedesa
in the free list, then we must merge those two blocks into a single blockc
that is of sizesize(c) + size(a)
.
To check the implementation of case 1 above, run the test_coalesce_basic1
test
from the user/lab01test.c
as follows:
$ lab01test 3
test_coalesce_basic1(176): OK.
test_coalesce_basic1(177): OK.
test_coalesce_basic1(178): OK.
test_coalesce_basic1(181): OK.
test_coalesce_basic1(182): OK.
test_coalesce_basic1(183): OK.
To check the implementation of case 2 above, run the test_coalesce_basic2
test
from the user/lab01test.c
as follows:
$ lab01test 4
test_coalesce_basic2(204): OK.
test_coalesce_basic2(205): OK.
test_coalesce_basic2(206): OK.
test_coalesce_basic2(209): OK.
test_coalesce_basic2(210): OK.
test_coalesce_basic2(211): OK.
To check the combination of both cases, run the test_coalesce3
test from the
user/lab01test.c
as follows:
$ lab01test 5
test_coalesce3(233): OK.
test_coalesce3(234): OK.
test_coalesce3(235): OK.
test_coalesce3(238): OK.
test_coalesce3(239): OK.
test_coalesce3(240): OK.
test_coalesce3(244): OK.
test_coalesce3(245): OK.
test_coalesce3(246): OK.
test_coalesce3(247): OK.
test_coalesce3(248): OK.
Running the test cases
If you were careful when implementing rhmalloc
and rhfree
above, the
remainder of the test cases should pass automatically. Here is a description of
the remaining ones.
Test force alignment
This tests that your code aligns correctly. By aligned here we mean evenly divisible by the size of the archiecture - because in this system pointers are 8-bytes, our struct must start at an address that is divisible by 8. Similarly, because we have no idea what our user might want to store in their allocated space, we must also always give them an address that is divisible by 8.
To run this test case, run lab01test
with the argument 6 as follows:
$ lab01test 6
test_force_alignment(261): OK.
test_force_alignment(268): OK.
test_force_alignment(271): OK.
test_force_alignment(273): OK.
test_force_alignment(275): OK.
test_force_alignment(276): OK.
Test too small blocks
This test ensures that you never have an entry in the free list that is too
small to actually contain data. This can happen when a new rhmalloc
requests a
size that is very slightly smaller than an available block in the free list. The
normal thing to do would be to split the block, but if it is just slightly
smaller there isn’t enough space to actually add a new entry. In this case the
block should not be split, and instead the slightly larger block should be fully
allocated to the request (and, as with alignment the stored size should reflect
the true allocation not the requested allocation).
In this system, the minimum size needed to allocate a viable block is the size of a aligned metadata block + 8 bytes.
To run this test case, run lab01test
with the argument 7 as follows:
$ lab01test 7
test_too_small_blocks(295): OK.
test_too_small_blocks(306): OK.
test_too_small_blocks(315): OK.
test_too_small_blocks(316): OK.
test_too_small_blocks(326): OK.
test_too_small_blocks(332): OK.
test_too_small_blocks(333): OK.
test_too_small_blocks(344): OK.
test_too_small_blocks(348): OK.
test_too_small_blocks(350): OK.
test_too_small_blocks(351): OK.
test_too_small_blocks(352): OK.
Test gracefully run out of memory
Running out of memory should not be a problem for a memory manager. Functions
that call rhmalloc
are supposed to check to see if the result pointer was 0
(which indicates an allocation failure). So your memory manager should behave
correctly (i.e., return 0
) rather than crashing or infinite looping when a
malloc cannot be fulfilled because the slab is fully in use.
To run this test case, run lab01test
with the argument 8 as follows:
$ lab01test 8
test_gracefully_run_out_of_memory(364): OK.
Test stress big heap
This test allocates a bunch of very big memory regions and then frees them in a random order. If you’ve coded the previous parts correctly, this should work on the first try. One thing that can sometimes cause an issue is incorrect coalescing - after the big chunks have all been freed, the code allocates a really big chunk. This will fail unless all the previous regions have been correctly coalesced.
To run this test case, run lab01test
with the argument 9 as follows:
$ lab01test 9
test_stress_big_heap_chunks(384): OK.
test_stress_big_heap_chunks(384): OK.
test_stress_big_heap_chunks(384): OK.
test_stress_big_heap_chunks(384): OK.
test_stress_big_heap_chunks(384): OK.
test_stress_big_heap_chunks(384): OK.
test_stress_big_heap_chunks(384): OK.
test_stress_big_heap_chunks(390): OK.
test_stress_big_heap_chunks(401): OK.
Test stress overlapping
This test randomly allocates and deallocates regions. While doing allocations, it checks to ensure that the newly created region does not overlap with an existing allocation region. If you’ve coded the previous parts correctly, this should work on the first try.
To run this test case, run lab01test
with the argument 10 as follows:
$ lab01test 10
There will be no printout in case the test is successful.
Running the full grading script
Once you are done implementing all the above programs, run the grading script using
$ make grade
from your Linux terminal (not your xv6 terminal window).
Submitting your code
From the Linux terminal, issue the command (make sure you are in the xv6-riscv
directory in your repository):
./create_submission.sh <username>
and replace <username>
with your RHIT username (without the <
and >
). For
example, for me, that would be:
./create_submission.sh noureddi
If you get a message saying that you don’t have permission to run
./create_submission.sh
, then issue the following command first
chmod +x ./create_submission.sh
Here’s the output as it shows up on my end:
Cleaning up xv6 directory...
Process started: writing temporaries to /tmp/dab9bfedf8d508c2a1c3f1c95e6ba1fc.txt
Found the following modified files:
./user/rhmalloc.c
Creating the submission zip file.
adding: user/rhmalloc.c (deflated 54%)
Done...
################################################################
submission_noureddi.zip has been created.
Please submit THIS FILE AND THIS FILE ONLY to Gradescope.
################################################################
This will generate a single file called submission-username.zip
(for me, it
would be submission-noureddi.zip
). That is all you need to upload to
Gradescope.
Submission Checklist
- My code compiles and generates the right executables.
- I ran
make grade
to double check the test cases for all of my code. - I ran the submission script to generate my
zip
file. - I submitted the
zip
file to Gradescope.
If you notice any typos or inaccuracies, please open a GitHub issue on this repository.