/Teaching/System Level Programming/Assignments/A5
Pull from upstream before solving this task.
A5: Dynamic Memory Implementation
In this exercise, you are expected to create your own implementation of dynamic memory to allocate/deallocate memory on the heap. You will write your own implementation of malloc( ... )
, free( ... )
and calloc(...)
as well as operator new
/operator delete
to create instances during runtime.
Learning Objectives
Gain a deeper understanding of low-level applications
Compared to the other exercises, you are free in how you want to solve this assignment, as long as you fulfill the mandatory requirements and don’t change the function signatures provided.
After having practiced reading and understanding man pages in the previous exercises and learning about defined and undefined behaviour, you are now expected to write these existing functions yourself, while providing the same behaviour.
Writing Tests & Debugging
This assignment should not be too difficult to write if you have some experience with C/ C++. Instead, the difficult part lies within writing tests, debugging them, and ensuring that your program does what you say it does. The testsystem only provides some sanity checks for you. The remaining functionality you will have to test and debug yourself, which is a big part of this assignment.The testsystem only tests things explicitly mentioned in this assignment description.
If you plan on attending the “Operating Systems” course, it is highly recommend not to skip this task. You will (hopefully) learn a lot about writing, testing and debugging low-level applications, which is essential to OS.
Support
If you want support, please write a few tests first. We will give feedback on which of your tests you should expand, or which ones you should rework. For the most part, we will not give you detailed feedback on your malloc implementation.
Without your own tests you won’t know which parts of your malloc work correctly and which ones don’t.
Where & How to start
It is recommended to start off with a simple malloc(...)
(and free(...)
) implementation and iteratively add features to it. calloc(...)
, operator new
and operator delete
will only give you points once your malloc(...)
implementation has basic functionality. However, the task of the operator new is much, much simpler than the malloc( ... )
task.
The maximum amount of points that can be reached in this assignment is 27 (25 + 2 bonus points). Even a simple implementation of malloc( ... )
and free( ... )
will lead to some points, provided all the mandatory requirements are fulfilled. Implementing all features in combination may lead to unlocking the 2 additional bonus points.
If you do not feel very comfortable with C/ C++, how to debug efficiently or would just like some extra advice, there will be a presentation for A5 during the lecture. Besides the assignment itself, we will look at how to debug and verify a similar program, using techniques you can then apply to your A5 implementation.
You can also attend the A5 question hours (29.11., 06.12.), where we can again demonstrate debugging etc if there is demand.
Mandatory requirements
Malloc and Free functions:
-
-
- The interface of your implementation is required to conform to the POSIX standard (see
man malloc
).- Make sure you support an arbitrary number of
malloc( ... )
andfree( ... )
calls, and arbitrary sizes passed tomalloc( ... )
.
- Make sure you support an arbitrary number of
- Reduce the heap size whenever it makes sense, for example when all the malloc’d data has been freed.
- Note: This is not necessarily standard
malloc( ... )
behaviour. - You can decide for yourself when exactly you can reduce the heap size, especially if there are still some blocks allocated.
- Note: This is not necessarily standard
- Do not trust user pointers: Make sure your functions never cause a segfault if you could prevent it.
- Implement the two functions
snp::Memory::total_alloc_memory(...)
andsnp::Memory::block_info(...)
snp::Memory::total_alloc_memory(...)
: return how much memory has been allocated in total over the runtime not deducting frees.snp::Memory::block_info(...)
: this function takes a parameterint type
. When type is a nonzero value, return the size of the currently first alloced block. When type is 0, return the starting address of the currently first alloced block. If no alloced block exists, return 0.
Additional requirements
Malloc, Calloc and Free functions:
-
- Reduce the number of syscalls where possible (allocating
100kB
should take more than one but no more than 30 syscalls, regardless of the number ofmalloc( ... )
-calls).- Hint: Does
brk( ... )
andsbrk( ... )
need to be called every time you callmalloc( ... )
? - You are also not allowed to call
sbrk( 0 )
more than once during program execution. You can assumesbrk( ... )
is only called in your malloc/free functions. - Think back to A3, what happens internally when you call
sbrk( ... )
? Does it make sense to callsbrk( 1 )
? What could you do instead? - Use
strace
to examine the syscalls a process makes. - You can assume bigger sizes for each of the
malloc( ... )
-calls for the ’30 syscalls’ requirement, so sizes of much more than 8 bytes. - This requirement only applies to testcases where
malloc( ... )
is called more than once.
- Hint: Does
- Detect memory corruption errors. Bring in your own ideas which errors to detect. At least:
- Buffer overruns/memory corruption
- invalid
free( ... )
/ doublefree( ... )
- Handle out of memory correctly.
- In case you run out of memory:
malloc( ... )
returnsNULL
. - Exit the program with
exit code -1
in case of memory corruption, invalidfree( ... )
, doublefree( ... )
. - Your
malloc
-functions should not be too slow. For example, try to avoid iterating over the same list multiple times. - Organize the heap with respect to performance and memory usage overhead (fragmentation).
- You may also implement free chunk merging.
- Reduce the number of syscalls where possible (allocating
New and Delete operators:
-
- Use
malloc( ... )
andfree( ... )
. - Your implementation should use exceptions in the case of an error.
- See
std::new
for exception usage. - Take care that you throw the same exception as
std::new
.
- See
- Use
Implementation Guidelines
Malloc, Calloc and Free functions:
-
- Implement the methods
snp::Memory::malloc(...)
,snp::Memory::calloc(...)
andsnp::Memory::free(...)
. - Use only the
snp::brk( ... )
/snp::sbrk( ... )
functions for acquiring new memory (seeman brk
). - Your implementation should be in
C++
for reasons of portability (you can reuse yourmalloc( ... )
after some small changes for the OS course). - Do not use
mmap( ... )
, you can ignoreMMAP_THRESHOLD
. - You do not need to worry about aligning the memory your
malloc( ... )
returns. - You do not have to implement the
errno
mechanics. - You do not need to implement overflow-detection for
calloc(...)
. - Your implementation must not contain a main function in any file, except for the testcases in the tests directory.
- Implement the methods
New and Delete operators:
-
- Put your implementation of
new
/delete
in the provided stubs. - Only change the already existing function implementations that have a
TODO
above them. You can add additional functions/variables if you want. - We will overload the global
new
/delete
operators, so you can use it just as you would use the standardoperator new
inC++
. - Your implementation must not contain a main function in any file, except for the testcases in the tests directory.
- Put your implementation of
Tips
Malloc, Calloc and Free functions:
-
- Start with a simple
malloc
-implementation, and iteratively add new features. - You are expected to write your own tests, but they do not need to be complex and will not be graded. However, without your own testcases, you will not know if your
malloc
behaves as expected, and will probably not get the full points for this assignment. - For your
calloc(...)
-function, you can just call yourmalloc(...)
-function. - You can use the
placement new operator
and add your own classes to organize your implementation. This can make debugging easier as well.
Usage of theplacement new operator
will be shown in the lecture and the A5 extended question hour. - If you want to use void pointer arithmetic in
C++
, you can usechar*
instead. - If you want to use
C
-style libraries, you can use<cstring>
and<cstdlib>
for example. - Some libraries are already included in your malloc/new files, which should cover everything you need, however you can use additional ones if you need to.
- Even though you will implement malloc in
C++
, you can write in a very similar manner to theC
code found in the other assignments (you do not need to use classes or otherC++
-specifics). - Do not use a data structure like
std::list
, as they usemalloc( ... )
internally. You can use any datastructure that does not usemalloc( ... )
internally. - If you decide to use a linked list, I recommend using a singly linked list.
- Some of the tests are written in
C
(and you can also decide if you preferC
orC++
for your tests), so you cannot use exceptions.
- Start with a simple
New and Delete operators:
-
- You should write your own tests for
new
/delete
. - You will only get points for this task once you have implemented the basic
malloc(...)
-mechanics. - You will probably find this task much, much easier than
malloc( ... )
.
General Advice:
- Try to test for every requirement found here or on the manpage. If you cannot figure out how to test for a specific requirement, feel free to ask via discord or mail.
- Make sure you have a working debugger, this assignment will be rather difficult without one. I recommend gdb or VSCode (which also uses gdb internally but provides a nice GUI), if you need help setting it up ask in discord or via mail.
- You are not restricted in how you want to solve this assignment, as long as you don’t change the function signatures and everything compiles you should be fine.
- Attend the A5 lecture unit and the A5 question hours (29.11., 06.12.) if you do not feel comfortable with
C
/C++
or do not know where to start. In the lecture unit you will see some basics on how you can debug, write tests and maybe some small tips for starting out. - Any mention of “block size” or similar will not include your metadata. A block allocated with
malloc(64)
has the size 64 for our purposes.
Debugging in VSCode:
You can use whatever debugger you prefer. However, if you’d like an easy start you can try the following (assumes gdb and VSCode is installed):
- Download the vscode.zip file. Extract the two files inside into
yourrepo/A5/.vscode/
(create the folder if it does not exist already). - Open your A5 folder with VSCode. You should now have three choices to run within the debug section (the bug symbol on the left).
- Now add a breakpoint within your
malloc.cpp
ortinytest.c
(click on the left side of the linenumber, you should see a red circle). - If you select “exampletest_1 dbg” and click the green arrow next to it or press F5, you should be all done and ready to debug!
- If you write your own tests, select “current file dbg” and open the test you want to debug (make sure it’s the currently active file), then press F5.
- You can also adapt launch.json to create entries for your own testcases.
- If you do not want VSCode to pause when it hits the main function, open
launch.json
and set"stopAtEntry"
fromtrue
tofalse
for all three configs. - Make sure to read up on how to use VSCodes debug UI and all the features it provides, or attend the extended question hour for some basics.
- If you use this config, you can use
ctrl+shift+p
, choose “Tasks: Run Task” and then “Run tests” to execute all of your testcases at once.
Notes:
Please pull from the upstream git repository.
You will find the files-
A5/malloc.cpp
A5/memory.h
A5/util.cpp
A5/new.cpp
A5/Makefile
which contain stubs for your implementation.
The testsystem only uses yourA5/malloc.cpp
,A5/memory.h
andA5/new.cpp
files.
You can modify the other files and add new ones as you like, but yourmalloc/new
-implementation should be contained in those three files.Do not modify the existing parts of the header file
A5/memory.h
. You can, however, add new methods/attributes/classes.
You will also find two testcases in the tests directory. Note that the two basic tests we provide do not test all the requirements by far.
You are expected to test your dynamic memory implementation by writing your own tests and debugging them.
You can add and push as many new files in the/tests/
folder as you like.
Pushing your tests to git makes it easier for us to help you, since we can see what you have already tested and what you may have missed.
AnyC
/C++
tests you write in your/tests/
folder will be compiled by the provided makefile, so there is no need to compile anything manually.
To compile everything, typemake
in your repository.
You will find the binaries for your tests in the/build/
folder, you can start them using./build/testname
.Everything was tested using Ubuntu 20.04 LTS and
gcc/g++
version 9.4.0.Submission
After finishing your implementation, tag the submission with
A5
and push it to the server.Help
If you have any questions, feel free to ask in Discord. You can also write an email to slp@iaik.tugraz.at if necessary. For questions regarding your specific solution, you can ask the tutor who organizes the assignment. There will be two question hours for this assignment, check the website for the dates.
Assignment Tutors
Tobias Teichmann, tobias.teichmann@student.tugraz.at
Nora Puntigam - You should write your own tests for
- The interface of your implementation is required to conform to the POSIX standard (see
-