/Teaching/System Level Programming/Assignments/A5
Pull from upstream before solving this task.
A5: Dynamic Memory Implementation
- Create your own implementation of
malloc( ... )
/free( ... )
/calloc(...)
to allocate/deallocate memory on the heap. - Create your own implementation of
operator new
/operator delete
using your ownmalloc( ... )
/free( ... )
to create new instances during runtime. - 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 do not feel very comfortable with
C
/C++
or would just like some extra advice, attend the A5 extended question hour (03.05.). - New and delete will only give you points once your
malloc( ... )
implementation has basic functionality.
However, the task of theoperator new
is much, much simpler than themalloc( ... )
task. - If you plan on attending the “Operating Systems” course, I would 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.
Malloc, Calloc and Free functions (21p + 2p bonus):
Non-functional requirements:
-
- Your implementation should be in
C++
for reasons of portability (you can reuse yourmalloc( ... )
after some small changes for the OS course). - Organize the heap with respect to performance and memory usage overhead (fragmentation).
- 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 use
sbrk( 0 )
more than once in your program. (You can assume you are the only one callingsbrk( ... )
). - 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.
- Hint: Does
- Reduce the heap size whenever it makes sense, for example when all the malloc’d data has been freed.
- This will have some similarities with your solution to the “Reduce the number of syscalls made”-problem, just in the opposite direction.
- Note: This is not necessarily standard
malloc( ... )
behaviour.
- Your
malloc
-functions should not be too slow. For example, try to avoid iterating over the same list multiple times. - You may implement free chunk merging as a bonus task (bonus points!).
- Your implementation must not contain a main function in any file, except for the testcases in the tests directory.
- Your implementation should be in
Functional requirements:
-
- 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
). - 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( ... )
. - The interface of your implementation is required to conform to the POSIX standard (see
man malloc
). - Do not use
mmap( ... )
, you can ignoreMMAP_THRESHOLD
. - You do not need to worry about aligning the memory your
malloc( ... )
returns. - You do not need to implement overflow-detection for
calloc(...)
.
- Implement the methods
Tips:
-
- 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 (4p):
Non-functional requirements:
-
- Your implementation should be in
C++
- 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. - Your implementation must not contain a main function in any file, except for the testcases in the tests directory.
- Your implementation should be in
Functional requirements:
-
- 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
- We will overload the global
new
/delete
operators, so you can use it just as you would use the standardoperator new
inC++
.
- Use
Tips:
- 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 extended question hour (03.05.) if you do not feel comfortable with
C
/C++
or do not know where to start. There you will see some basics on how you can debug, write tests and maybe some small tips for starting out. You can of course also ask me to cover any additional topics that you would like.
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 “tinytest 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.
- 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.
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 your A5/malloc.cpp
, A5/memory.h
and A5/new.cpp
files.
You can modify the other files and add new ones as you like, but your malloc/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.
Any C
/ 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, type make
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
Lorenz Schumm, schumm@student.tugraz.at