Your assignment is to implement a memory manager module and use it to:
- Allocate and free memory regions
- Implement a program that manages a memory map - a binary file that represents the content of the memory
“The essential requirement of memory manager is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when no longer needed.” [https://en.wikipedia.org/wiki/Memory_management].
For more information on memory managers please read: “A memory allocator”, by Doug Lea. “A Malloc Tutorial” by Marwan Burelle, is also a very informative, but it does not use the most eloquent English .
For this assignment you will create a memory manager for a simulated memory of 64 Kb.
- memory addresses and sizes are represented on 2 bytes (16 bits) and are aligned at four bytes. This implies that all memory addresses and sizes are multiples of 4.
- a chunk of memory consists of
- size - the size of the chunk of memory. It is 4 bytes more than the size of the user data space. It occupies the first two bytes of the chunk.
- user data space - used for storage
- size - the size of the chunk of memory. It occupies the last two bytes of the chunk. NOTE: Since all memory chunks are aligned at 4 bytes, the last bit of the size will be used as a status flag to indicate if the chunk is in used or free: 1 represents in use and 0 free.
- there are 18 bins of memory chunks.
- the first 8 bins contain chunks of exact sizes: 8, 12, 16, 20, 24, 28, and 32.
- the last 11 bins contain chunks of variable sizes. The size of a chunk in each bin is bounded above by: 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, and 65536 bytes respectively. Each such bin contains chunks of memory which are larger than the size limit of the previous bin, and less than or equal to their own size limit.
- each bin is implemented as a circular double linked list. The lists for the variable size bins are to be sorted in increasing order of chunk sizes. The links of a free chunk are stored in the first 4 bytes of the user data space, the forward list first and the backward link after it.
- the headers of the bins are stored in the first 72 bytes of the memory. The header of an empty list has circular references to itself.
- initially memory is made of a single chunk of size 65464 bytes
- memory regions are allocated on a best first approach. If no chuck of requested size is available, the smallest chunk, larger than the requested size is divided into a chunk of requested size and a left over chunk that can fit in one of the remaining bins. If the left over chunk does not fit any of the existing bins, then the entire chunk is allocated.
- when a memory region is freed, first it neighbor are checked and if they are free too, the regions are coalesced into a larger region. The resulting region is added to the bin into which it fits.
You must make and justify any important design decisions for your implementation, based on the following important requirements:
- memManager.h is given to supply your module with a common public interface. You must have these functions written to spec. This way we can link your module with our own test program. You may add whatever other functions you need to this module, but it must run under these conditions.
- memManager.c contains your implementation of the memory manager
- We will test your memory manager implementation under the assumption that it can handle any number of entries (as long as memory is available).
- You must implement the memory manager, test it appropriately, and then report your effort in a test report (see below). Test your programs extensively; including automated rules for your tests (we want to run the same tests that you have!).
memMapMgr.c Contains the main memory manager program which works with a given memory map. A memory map is a binary file containing 65,536 bytes. It is an external copy of the internal memory of the memManager module. The program must be able to:
- Create the memory map of a new empty internal memory
- Import a memory map in the internal memory
- Export internal memory to an external memory map
- Allocate memory regions in a memory map
- Free memory regions in a memory map
- Print statistics of a memory map
What mode it runs in is handled from the command line, this program does not take standard input. For sanity and practice, consider using getopt for the command line manipulation.
The possible program invocations are ( indicate a filename):
./memMapMgr -c [memory map] to create an "empty" memory map ./memMapMgr -i [memory map] to import a memory map ./memMapMgr -e [memory map] to export a memory map ./memMapMgr -s [memory map] to print statistics about a memory map ./memMapMgr -a [memory map] - b <size> to allocate a region of <size> bytes in the memory map ./memMapMgr -f [memory map] - p <address> to free a region starting at address <address>
- Please follow Good Programming Style document for guidelines on style. You must not add more global variables in this assignment.
- Function documentation should follow the example provided in the header file memManager.h.
- Some information regarding memory organization and management will be covered in class. You are encouraged to seek out information about these subjects. Make sure to reference any sources you use.
- You should design your data structure carefully.
Your tar file should contain an A2 directory which includes all files related to this assignment. In particular, the A2 directory should contain:
- README a text file explaining the content of each file you have included in the directory and the usage of your submission
- makefile, in which make all produces all executables as you described in the README file
- memManager.h, memManager.c, memMapMgr.c and any other source files you might have created.
- design.txt a design document that describes the design decisions you made. The design document is supposed to record the important decisions you made about what had to be done (analysis) and how to do it (design). In particular, it should contain the reasons for why you made your decisions. Part of your design document will be the issues list, which identifies the issues that you encountered during the assignment, whether resolved or not, and how you resolved those that were resolved.
- Test a directory containing a collection of your test files, which also must contain a testing report in a text file called testing.txt, describing what and how you tested. We want to be able to easily run the (highest level at least) tests that you ran, so be sure to automate their use in your makefile.
Your submission must only include source files and documentation files. Do not include any executable, object or core files.