/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 (20.11., 27.11.), 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 segfault if you could prevent it.
      • Implement the two functions snp::Memory::total_alloc_memory(...) and snp::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 parameter int 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 of malloc( ... )-calls).
          • Hint: Does  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, so 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.
        • In case you run out of memory: malloc( ... ) returns NULL.
        • Exit the program with exit code -1 in case of memory corruption, invalid free( ... ), double free( ... ).
        • 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.

      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 snp::Memory::malloc(...), snp::Memory::calloc(...) and snp::Memory::free(...).
        • Use only the snp::brk( ... )/snp::sbrk( ... ) functions for acquiring new memory (see man brk).
        • Your implementation should be in C++ for reasons of portability (you can reuse your malloc( ... ) after some small changes for the OS course).
        • 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 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.
        • 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).
        • Do not use a data structure like std::list, as they use malloc( ... ) 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 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 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 or tinytest.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" from true to false 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 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

        Tobias Teichmann, tobias.teichmann@student.tugraz.at
        Nora Puntigam