/Teaching/System Level Programming/Assignments/A5

Pull from upstream before solving this task.

A5: Dynamic Memory Implementation

  • Create your own implementation of malloc( ... )/free( ... ) 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.

Malloc and Free functions (20p):

Non-functional requirements:

    • Your implementation should be in C++ for reasons of portability (SWEB).
    • Organize the heap with respect to performance and memory usage overhead (fragmentation).
    • Reduce the number of syscalls made (allocating 100kB should take 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( ... )?
      • Use strace to examine the syscalls a process makes.
      • You also are not allowed to usesbrk( 0 ) more than once in your program.
    • Reduce the heap size whenever it makes sense.
      • This will have some similarities with your solution to the “Reduce the number of syscalls made”, just in the opposite direction.
      • Note: This is not necessarily standard malloc( ... ) behaviour.
    • You may implement free chunk merging as a bonus task (bonus points!).
    • You do not need a lot of C++-specific functionality (except for the classes), it should be very similar to the C code used in previous slp assignments.
    • Do not use a data structure like std::list, as they use malloc( ... ) internally. You can use any datastructure that does not usemalloc( ... ) internally.

Functional requirements:

    • You are required to use the brk( ... )/sbrk( ... ) functions defined in 4.3BSD or POSIX prior to 1-2001.
    • You do not need to use mmap( ... ), you can ignore MMAP_THRESHOLD.
    • 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 a null-pointer.
    • In case of detecting an error: Exit the program with exit code -1 in case of memory corruption, invalid free( ... ) or double free( ... ).
    • The interface of your implementation is required to conform to the POSIX standard (see man malloc).
    • Do not use malloc( ... ) in your snp::Memory::malloc( ... ) implementation.
      • You are required to use brk( ... )/sbrk( ... ) for all your dynamic memory needs.

Tips:

    • If you want to use void pointer arithmetic in C++, you can use the char* instead.
    • If you want to use C-style libraries, you can use <cstring> and <cstdlib> for example.

New and Delete operators (5p):

Non-functional requirements:

    • Your implementation should be in C++ for reasons of portability (SWEB).
    • You should write your own tests for new/delete. (However they will not be graded)

Functional requirements:

    • Use your own implementation of malloc( ... ) and free( ... ).
    • Your implementation should use exceptions in the case of an error.
      • See std::new for exception usage.
    • Put your implementation of new/delete in the provided stubs.
    • Only change the already existing functions 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 test it just like the standard operator new in C++.

Notes:

Your implementation must not contain a main function in any file, except for the testcases in the tests directory.
Please pull from the upstream git repository.
Please make sure you have g++ and g++-multilib installed. For example, on Ubuntu you can use sudo apt install g++ g++-multilib.
You will find the files

    • A5/new.cpp
    • A5/malloc.cpp
    • A5/memory.h
    • A5/Makefile

which contain stubs for your implementation.
Do not modify the existing parts of the header file A5/memory.h. You can, however, add new methods/attributes to your class.
You will also find two testcases in the tests directory. Note that passing those tests does not mean you get all the points, you have write tests on your own.
Please use the included makefile. If you want to create your own or use cmake, please check out the flags we used for the compiler, since those flags will also be used on the testsystem.
Any C++ tests you write in your /tests/ folder will be compiled by the provided makefile, so there is no need to compile anything manually.
You will find the binaries for your tests in the /tests/  folder, only the smalltest is copied to the root folder.
You will get some points if your new/delete implementation works, even if your malloc( ... ) is not (yet) correct.

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 bs-helpline@iaik.tugraz.at if necessary. For questions regarding your specific solution, you can ask the tutor who organizes the assignment. There will be a question hour for this assignment, check the website for the date.

Assignment Tutors

Lorenz Schumm schumm@student.tugraz.at