Goals

• Learn to design and to implement a custom memory allocator: The operating system provides mechanisms for dynamic allocation in contiguous memory spaces. There are multiple criteria to assess how well these mechanisms work, including speed of execution and the minimization of external fragmentation (to that end, you learned of different policies for allocation decisions, such as first- fit, best-fit, and worst-fit). In this lab, you will design and implement a memory allocation system to work in user space and apply the concepts you have studied so far.
• Learn to work with a source tree similar to what you would find in open software. This lab gives you, as a starting point, a source code tree that includes a number of files and a Makefile to build separately compiled objects. This code includes a test suite that serves to shake the implementation around to expose bugs and test its functionality. You will add your new files to this source code tree, modify the Makefile given to you, and implement a test suite of your own to exercise your custom memory allocator.

Credits

This lab was developed by Prof. L. Felipe Perrone. Permission to reuse this material in parts or in its entirety is granted provided that this credits note is not removed. Additional students files associated with this lab, as well as any existing solutions can be provided upon request by e-mail to perrone[at]bucknell[dot]edu

Set Up

Read your SGG textbook from the start of Chapter 9 through 9.2 (8 up through 8.3 9th edition), inclusively.

For labs 7 and 8, it will be helpful to read:

• Building your own memory manager for C/C++ projects (IBM DeveloperWorks)
• Hoard: A Scalable Memory Allocator for Multithreaded Applications. Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson. In Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), Cambridge, MA, U.S.A. November 12-15, 2000.

Create a new directory for this week’s work:

~/csci315/Labs/Lab7

Problem (70 points)

The implementation of a doubly-linked list abstract data type (ADT) in C is given to you. You may use this code with the usual guarantees of open software: The solution that is being given to you has undergone a good amount of testing, but there are no guarantees that it is absolutely perfect. You may want to read the code to understand the implementation, you may want to test it further, or do anything else you find appropriate to develop the confidence you have in it.

Copy the files (recursively) from:

/home/cs315/Labs/Lab7 (or ~cs315/Labs/Lab7)

Be sure to put the files you create for this lab in the appropriate directories in this source code tree! That is, new header files should go in include/, new source files should go in src/, etc. Note that you may want to modify the code of this doubly-linked list so as to have a little more information in the node structure than what is given to you in the original module. (See more about this point in the description of the deallocate function below.) If you modify the doubly-linked list code, you should want to modify the test suite in src/dlisttest.c and run these tests to ensure that the module runs correctly after your changes.

For this problem, you will create a custom memory allocator. Since your code will not be part of the operating system, it will execute in user mode. The general idea is that one who uses your allocator will include a header file which declares your functions and also link with the code that defines/implements them. A program using your allocator will have to get it initialized before any calls are made to use dynamically allocated memory; our standard prototype for the initialization is:

int allocator_init(size_t size);

This function will create and initialize two doubly-linked lists used for memory management: one which keeps track of the memory that is available (call it free_list) and another which keeps track of memory which is already in use (call it allocated_list). All the memory manipulated by your allocator will reside in the heap of the process that uses it. When allocator_init starts, it will call the standard malloc to request a contiguous space of size bytes from the underlying operating system. The pointer received from malloc will be used to initialize a single node in your free_list; your allocated_list must start out empty. If the malloc call does not succeed, this function must return -1, otherwise, it must return 0. The correct implementation of this function earns you 12 points.

Ultimately, a custom memory allocator will need an API similar to what you have for malloc and free, functions that provide dynamic memory allocation in C. With that in mind, we define the API for a function to allocate memory and another to deallocate. (We will not worry about implementing anything like calloc and realloc, although they would be simple extensions once your basic functionality is implemented.)

void *allocate (size_t size);

Equivalent to malloc. This function will traverse the free_list and find a contiguous chunk of memory that can be used to satisfy the request of an area of size bytes. If the caller makes a request for memory that is larger than what your allocator can honor, this function must return NULL. Your allocate function must be flexible enough to allow for different allocation policies, namely first-fit, best-fit, and worst-fit. You should probably create three functions, one for each of these policies, which are used internally by allocate and are not visible to the user of your custom memory allocator. Having those functions allows you to make easy modifications to the policy used by allocate. You will want to design your code so that it is easy run experiments with different allocation policies, so think carefully about how you will define your functions prototypes. The design of these functions’ API and their implementation (obviously) is up to you. You should describe all additional functions used in your code in a file called designAPI.txt that is turned in with the other deliverables for this lab (a clear and well-written design description earns you 12 points; be sure to place this file in the doc/ directory of your source code tree). The correct implementation of this function earns you 12 points.

int deallocate(void *ptr);

Equivalent to free. This function will use ptr to find the corresponding node in the allocated_list and free up that chunk of memory. If the caller attempts to deallocate a pointer that cannot be found in the allocated_list, this function must return -1, otherwise it must return 0. To make your development process easier, at first, you can simply move the deallocated memory from the allocated_list to the free_list. Note that just as the C library’s  free, deallocate does not ask you for the size of the memory you are returning to the system. Think about how you can make your custom allocator keep track of the size of each allocated chunk of memory — the cleanest solution might require you to change the code of the doubly-linked list given to you. This modification will earn you 7 points. The correct implementation of this function earns you 12 points.

The entire code of your custom memory allocator will be encapsulated in two files:

• allocator.h
• allocator.c

To test your implementation, you will need to create one or more test programs, each with their own main() function, to exercise your memory allocator.  If you have a single file with all your tests, submit it as memory-test.c. If you have multiple files, append a number to the end of this file name; for instance, you could have: memory-test-1.c, memory- test-2.c, etc. Regardless of how many files you submit with your test suite, you should aim to exercise your custom allocators in a number of difference scenarios to try to expose bugs and convince yourself (and those who grade your work!) that your implementation is correct. The implementation of your test program(s) corresponds to 15 points.

Finally, you have to put together a Makefile for one to build your allocator (as a separately compiled module) and all the corresponding tests. Not submitting a Makefile that builds all your code correctly will lose you 10 points.

When you are done with this, you need to:

• git add Makefile
• git add src/allocator.c
• git add include/allocator.h
• git add doc/designAPI.txt
• git add src/memory-test*
• git add [any of dnode/dlist.[c,h] that you modified]
• git commit -m “Lab7 completed”
• git push

Rubric

1. [12 points] The correct implementation of allocator_init.
2. [12 points] A clear explanation of the design of your supporting functions for dealing with various policies for contiguous memory allocation (best-fit, first-fit, and worst-fit). Your document should describe the API of your functions and how they are used in your custom memory allocator.
3. [12 points] The correct implementation of allocate.
4. [7 points] Your correct modification to the doubly-linked list module given to you, which should support your deallocate implementation.
5. [12 points] The correct implementation of deallocate.
6. [15 points] The implementation of a test suite that can verify that all the functionality of your custom memory allocator works without bugs.
7. [-10 points] The student hasn’t submitted a Makefile that builds all the files used in the implementation and in the testing of the custom memory allocator.

Additional Challenge (30% additional points on this lab total)

Once the functionality described above works to specification, you may want to tackle an extra credit problem: you can check if the deallocated memory is adjacent to any other chunk of free memory and consolidate the corresponding free_list nodes into a single node representing the sum of the sizes of the two original nodes.

If you decide to go for this challenge, PLEASE place your implementation in directory Lab7/extra-credit in which you will replicate the entire source code tree. Submit this  via git as usual. (You will need to have the standard, un-optimized allocator for the next lab.)