CSE 473 Project 2: Memory Allocation
In this project, you will learn about Memory management. This project requires you to implement two memory allocation/de-allocation schemes, specifically Buddy System and Slab Allocation. The functioning of each of these schemes has been discussed in class. One of the jobs of the memory management subsystem is to service memory requests by matching the size of the request with a large enough hole, from which to satisfy the request. You will be given the starting address from where memory is to be allocated ( start_of_memory pointer) together with the size of this memory region ( mem_size = 1 MB).
To implement the allocation policies, you should implement the following three interfaces in a file called my_memory.c , whose semantics are described below.
void setup(int malloc_type, int mem_size, void* start_of_memory);
The purpose of setup() is to perform any initialization of variables that you may need, specify and give you the pointer (start_of_memory) to the total amount of memory at your disposal, and also specify the type of memory allocator.
The parameter malloc_type will be either 0 or 1, denoting 0-Buddy System and 1-Slab Allocation.
void* my_malloc(int size); // returns a pointer to the allocated memory
This function should allocate size bytes of memory from that 1MB chunk of memory that is available for you (using the start_of_memory pointer) using the specified allocation algorithm. On allocation, it returns a pointer to the start of allocated memory. If a request cannot be accommodated by the scheme, this function should return -1. Note that the user programs expect that all the size bytes, starting from the first byte pointed to by the returned pointer, is available to it.
void my_free(void* ptr);
This function deallocates the memory segment being passed by the pointer. Note that when free-ing, the resulting free segment should be merged with relevant neighboring holes (as per the algorithm/scheme) whenever possible to create holes of larger size. No size argument is being explicitly passed in this call.
The size parameter is given only in my_malloc and not in my_free. However, it is necessary to know the size of what is being freed. This should be handled by using the first 4 bytes of the allocated segment to contain the size. However, programs would assume that all the space, starting from the first byte of the returned pointer, is available to be used. Hence, you should ensure that the pointer that my_malloc() returns points to the byte immediately after these 4 bytes (header) containing the size.
• The minimum chunk of memory that the Buddy System can allocate is 1KB.
• Maintain the free (holes) list sorted by increasing addresses individually for different sizes (of powers of 2) as discussed in class.
• Whenever there is a choice of multiple holes that a scheme allows, always pick the hole with the lowest starting address.
• The 4 byte header is used to maintain the size of the allocated chunk within the chunk itself..
• The Slab size is fixed at N_OBJS_PER_SLAB which is always 64 and is defined in my_memory.c. Note that each slab will only contain the objects of the appropriate type/size. However the size of the allocated object itself should be accounted to include its 4 byte header. Hence, when using this scheme for allocating an object, there will be a 4 byte header for the object, and additionally a 4 byte header in the slab itself (where this object resides) which is allocated using Buddy.
• The Slab Descriptor Table itself is maintained as a separate data structure (you can use the system malloc for allocating it). Please use the data structure explained in class for the Slab Descriptor Table.
What to turn in:
1. my_memory.c (and if needed, its header file), containing the above three interface functions which implement all 2 allocation schemes.
2. A report to clarify the assumptions, design choices, the reasons that you made such decisions, and breakdown of the contribution of each member to the project. Also remember to include any special instructions for testing your code.
The project source code and report are due before 11:59 through Github. You need to set up an appointment with the TA to demonstrate your implementation and answer a range of questions related to the entire project (even though an individual may have worked on only one part). Academic dishonesty of any kind will not be tolerated.
Additional Information, PLEASE READ CAREFULLY!!!
1. The inputs and sample outputs are given just for illustrative purposes to test your code. You can create more extensive input files for further testing.
2. The TAs WILL use several other test inputs during the demo and your routines should still work.
3. Please stay tuned constantly to the canvas page for the exact and latest interface functions you need to implement, their arguments, test programs, examples, documentation/manuals and announcements.
4. You can work in teams (at most 2 per team – they could be across sections), or individually, for the project. You are free to choose your partner but if either of you choose to drop out of your team for any reason at any time, each of you will be individually responsible for implementing and demonstrating the entire project and writing the project report by the designated deadline. It does not need to be the same partner as project 1. If you have difficulty finding a partner, give your name to the TAs who will maintain an online list of students without partners to pair you up. Please let the TAs know who you are working with right away.
5. Even though you will work in pairs, each of you should be fully familiar with the entire code and be prepared to answer a range of questions related to the entire project. It will be a good idea to work together at least during the initial design of the code. You should also ensure that there is a fair division of labor between the members.
6. All the code-bases will be tested on the W-204 Linux Lab machines located on the second floor of Westgate. Ensure you test and run them in that environment.
Input File Format (you do not need this unless you are creating extra input files yourself)
The test program will take an input file and perform the required activities. We will provide code to parse the input file and invoke the appropriate functions that you have to implement.