Task: 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 do not 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 and 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 will not know which parts of your malloc work correctly and which ones do not.

Where and 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.04., 06.05.), 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 and free calls, and arbitrary sizes passed to malloc.
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.
Do not trust user pointers! Make sure your functions never cause a segmentation fault if you can prevent it.

Utility functions

Implement the two functions slp::Memory::total_used_memory and slp::Memory::free_block_info
- slp::Memory::total_used_memory(...): return the total amount of currently allocated memory.
- slp::Memory::free_block_info(...): this function takes a parameter int type. When type is 1, return the size of the first free block. When type is 2, return the starting address of the first free block. When type is 3, return the number of free blocks. Otherwise return -1! If no free block exists, return 0.

Additional requirements

malloc, calloc and free functions

Reduce the number of syscalls where possible (allocating 100 kB should take more than one but no more than 30 syscalls, regardless of the number of malloc-calls).
- Hint: Do brk and sbrk need to be called every time you call malloc?
- You are also not allowed to call sbrk(0) more than once during program execution. You can assume sbrk is only called in your malloc/free functions.
- Think back to A3! What happens internally when you call sbrk? Does it make sense to call sbrk(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. Sizes of much more than 8 bytes.
- This requirement only applies to testcases where malloc is called more than once.
Detect memory corruption errors. Bring in your own ideas which errors to detect. At least:
- Buffer overruns/memory corruption
- Invalid free/double free
- Handle out of memory correctly.
Exit the program with exit code -1 in case of memory corruption, invalid free or double free.
In case you run out of memory, malloc returns NULL.
Your malloc functions must 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).
Also think about implementing free chunk merging.

new and delete operators

Use malloc and free.
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

Implementation Guidelines

malloc, calloc and free functions

Implement the methods slp::Memory::malloc(...), slp::Memory::calloc(...) and slp::Memory::free(...).
Use only the slp::brk(...)/slp::sbrk(...) functions for acquiring new memory (see man brk).
Do not use mmap(...), you can ignore MMAP_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

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 STUDENT 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 standard operator new in C++.
Your implementation must not contain a main function in any file, except for the testcases in the tests directory.

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 your malloc 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 the placement 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 use char* 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. However, be careful when using standard library functions that may internally call malloc(...) or operator new, as they will then use your implementation and may cause unintended side effects.
Do not use a data structure like std::list or std::vector, as they use malloc internally. You can use any data structure that does not use malloc internally.
Even though you will implement malloc in C++, you can write in a very similar manner to the C code found in the other assignments (you do not need to use classes or other C++-specifics).
Some of the tests are written in C (and you can also decide if you prefer C or C++ for your tests), so you cannot use exceptions.

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.
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.
You are not restricted in how you want to solve this assignment, as long as you do not change the function signatures and everything compiles you should be fine.
Attend the A5 lecture unit and the A5 question hours (29.04., 06.05.) 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 would 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 YOUR_REPO/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 or tinytest.c (click on the left side of the line number, 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 is 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" from true to false for all three configs.
Make sure to read up on how to use VSCode’s 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 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.

Submission

Modify the files in your git repository. You can find this assignment’s files in the A5 directory.

Tag the submission with A5 and push it to the server. You may remove and re-push the A5 tag any time you like before the deadline.

Assignment Tutors

If you have any questions regarding this assignment, go to Discord and read through the SLP channels. The probability that your question was already answered or some discussions will lead you in the right direction is quite high. If not so, just create a new thread with the A5 flair applied.

If you have a more direct question regarding your specific solution, you can also ask the tutors who organize this assignment:

Thomas Halbedl, halbedl@student.tugraz.at
Philip Prohaska, prohaska@student.tugraz.at