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.

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 through 8.3 in 9th edition), inclusively.

For this lab and the next, 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:

cp -r ~cs315/Labs/Lab7/ ~/csci315/Labs/.

(This recursively copies the ~cs315 user’s Lab7 folder to your course Labs folder.) In this directory, create a file called pre-lab7.txt where you will write BRIEF and CLEAR answers to the questions below.

Problem 1 (12 points)

The operating system must keep track of which portions of memory have been “doled out” to processes (e.g. in use)  and which portions are unallocated (e.g. free). In this lab, you will implement a custom memory allocator, which will keep track of allocated and free memory chunks using two doubly-linked lists. One list will be called the free-list (sections of memory that are not allocated) and the allocated-list (sections of memory that are in use).

Consider that memory will be allocated:

• At the time each process is created (so that its executable can be loaded into memory).
• At the time each process calls malloc.

Consider that memory is de-allocated:

• At the time each process calls free.
• At the time each process is terminated.

1. Reflect on how processes will cause insertions and removals in the doubly-linked lists that keep track of the memory that is allocated or free. Discuss whether doubly-linked lists are suitable for use in a custom memory allocator. (2 points)
2. Propose one or more data structures that might work as well or possibly better than doubly-linked lists for keeping track of allocated and free memory. (2 points)
3. Define the term external fragmentation and describe a scenario where it occurs. (1 points)
4. Define the term internal fragmentation and describe a scenario where it occurs. (1 points)
5. Describe the first-fit allocation policy. Give one advantage and one disadvantage of its use. (2 points)
6. Describe the best-fit allocation policy. Give one advantage and one disadvantage of its use. (2 points)
7. Describe the worst-fit allocation policy. Give one advantage and one disadvantage of its use. (2 points)

Problem 2 (18 points)

The code provided includes the implementation of a doubly-linked list (dlist.h/c) of doubly-linked nodes (dnode.h/c) along with numerous useful functions that act on these structs. There is also one program (dlisttest.c) that claims to test this implementation. Study the code provided carefully, maybe even write new tests to assure yourself of its correctness in edge cases (empty list, single element list, removal from a single element list, etc.). Be aware that this code is provided “AS IS”, WITHOUT WARRANTY OF ANY KIND.

To help with the upcoming lab, our custom memory allocator will use dlist’s to track blocks of memory. To do this we need a pointer to the block and its size. Make the following changes.

1. Currently the dnode structure includes only one data member, a void *data. In order to keep track of the size of each memory block (whether it is allocated or unallocated), you should probably add an additional data member of type size_t to the dnode struct. (You may dream up other designs to address this issue, but know that they may break the dlisttest provided.) Modify the dlist and dnode functions to work with the expanded dnode from above. (9 points)
2. Write a dlist_print function (and optionally also dnode_print or print functions to other structures, see 1) that provides a formatted printout of the contents of a dlist, perhaps like the example below, which shows a dlist with two dnodes (use %p in printf of a pointer). (4 points):
   
   dlist: –[250, 0x3e52c0]—-[25, 0x3e5482]–
   
3. Write a test program, src/alloc-dlist_test.c, that demonstrates the correctness of this improved dlist. (5 points)
4. Define a new composite struct with two members (void *, size_t), and have dnode’s data variable point to this new struct instead of a void.

When you are done with this, you need to (from your Lab7 folder for example):

• git add pre-lab7.txt src/ include/
• git commit “pre-lab 7 completed”
• git push