Remembrallocator

code Implement a memory allocator.

• Assign: Monday, 5 December
• Due: By the end of finals, 4:00pm Thursday, 22 December
• Starter Code: fork wellesleycs240 / cs240-malloc (just once!), keep the "cs240-malloc" name, and add bpw as admin. (Need help?)
• Submit:
  • Commit and push your final revision and double-check that you submitted the up-to-date version. (Need help?)
  • Do not submit a paper copy.
• Relevant Reference:
  • dynamic memory allocation
  • programming with memory
  • reasoning about programs
  • C resources
  • debugging resources
  • Mercurial Team Workflow
• Collaboration: Recommended pair code assignment policy, as defined by the syllabus.

Ben will add extensive office hours during reading period and finals for allocator work.

Overview

In this assignment you will implement a dynamic memory allocator for C programs, i.e., your own version of malloc and free. You may use any implementation strategy that works (subject to programming rules). You may use any implementation strategy that works (subject to programming rules, but performance of your memory allocator is a large component of the grade.

We recommend this path for preparation and development of a successful allocator:

1. Sketch, simulate, and understand an implicit free list allocator. You must complete these exercises before asking code/debugging questions.
2. Read reminders about how to work on implementation..
3. Fully implement an implicit free list allocator in C (and test it). This can net a solid B grade.
4. Optionally, extend your implicit free list allocator to create an explicit free list allocator. This can net a solid A grade.
5. Optionally, add Extra Credit open-ended extensions to the allocator.

Contents

• Overview
• Review
• Specification
• Grading
• Required Preparatory/Lab Exercises
• Implicit Free List Allocator
• Explicit Free List Allocator
• Programming Rules
• Compiling and Testing
• Performance
• How to Work
• Extra Credit Open-Ended Extensions

Review

Read CSAPP section 9.9 to become familiar with the type of thinking and coding you will do to build the allocator. The book discusses an implicit free list allocator similar in organization to the one you will build first. The valuable part is the descriptions. The book’s code is useful, but do not get too caught up in the code details, since you will use different starter code.

We recommend the following practice problems on memory allocation, but you do not need to submit solutions. Solutions not in the textbook are available by visiting office hours. Note “word” means 4 bytes for these CSAPP problems, but 8 byte for our assignment.

• CSAPP Practice Problem 9.6
• CSAPP Practice Problem 9.7
• CSAPP Homework Problem 9.15
• CSAPP Homework Problem 9.16

Specification

The cs240-malloc repository contains several starter code files:

• Makefile – recipes for compiling
• mdriver.c – testing driver
• memlib.h – memory/heap interface
• mm.c – memory allocator implementation
• mm.h – memory allocator interface
• traces/ – several trace files (.rep) used for simulated testing
• remaining files are support files you do not need to inspect

You will modify mm.c to implement an allocator interface as declared in mm.h.

int   mm_init();               // Provided.
void* mm_malloc(size_t size);  // Depends on helpers implemented by you.
void  mm_free(void* ptr);      // Implemented by you.

The provided mm.c file partially implements an allocator based on an implicit free list. It provides skeletons of several helper functions beyond the interface above and an implementation of mm_malloc that uses these helper functions. Your job is to complete the helper functions (and possibly add more of your own) as well as mm_free() to implement a memory allocator with good balance of memory utilization and throughput.

The three main memory management functions should work as follows:

• int mm_init(), provided: Initialize the heap. The return value is -1 if there was a problem in performing the initialization and 0 otherwise. The application program (in this case, the driver we provide) calls mm_init exactly once to initalize the system before calling mm_malloc() or mm_free().

• void* mm_malloc(size_t payloadSize): Return a pointer to an allocated block payload of at least payloadSize bytes within the heap or NULL if an error occurred. All payloads must be aligned to 16 bytes. The entire allocated block should lie within the heap region and should not overlap with any other allocated block. (size_t is a type for describing sizes; it’s an unsigned integer large enough to represent any size within the address space.)

• void mm_free(void* ptr): Free the allocated block referenced by the pointer ptr. Assume that ptr was returned by an earlier call to mm_malloc() and has not yet been freed. These semantics match the semantics of malloc and free in the standard C library. Type man malloc in the shell for complete documentation.

Grading

Your grade will be calculated from 100 points as follows:

• Preparatory Exercises (10 points):
  • You may ask questions on the preparatory exercises themselves at any time.
  • You must complete these exercises before asking code/debugging questions of the tutors/instructors.
  • Keep your completed exercises to show to tutors/instructors if asking code questions. Submit them before the due date by either:
    • Adding, committing, and pushing a PDF in your cs240-malloc repository; or
    • Submitting a paper copy in person or under Ben’s door.
• Style (10 points)
• Correctness (40 points), based on passing mdriver tests on the provided traces.
  • 2 points each for short1-bal.rep and short2-bal.rep.
  • 4 points each for all remaining traces.
  • The realloc*.rep traces are not included – they are for an optional extension.
• Performance (40 points) = 44 × P
  • P is the mdriver performance index. A performance index of about 90/100 nets full performance credit. Surpassing this level yields extra credit.

You may use any implementation strategy that works (subject to programming rules). Allocator performance is a large component of the grade for this assignment. A good rule of thumb is that a good implicit free list allocator can net a solid B grade and a good explicit free list allocator can net a solid A grade.

Required Preparatory/Lab Exercises

Complete these exercises to familiarize you with heap layout, block layout, and the basics of the provided starter code. These exercises will count for a small part of your grade.

A. Heap and Block Layout

Submit answers for the following questions in A. Read mm.c to learn about the block layout. Assume words are 8 bytes and pages are 4096 bytes. Pay special attention to the early comments about block and heap layout, as well as the code in mm_init. [We made Minor updates based common questions – no need to come back to these if you already did them.]

1. What is the minimum block size (in bytes) of our allocator?
2. What is stored in the header of each block?
3. What is stored in the footer of each free block?
4. What is the largest payload that could be allocated in a minimum-size block?
5. What is stored in the last word of the heap? (We call this the heap footer; CSAPP calls this the epilogue.)
6. How much space in the heap is never part of any block?

For the following questions, draw memory as an array of words (but not to scale when using big numbers). Use the block layout rules from mm.c and especially the heap setup code in mm_init and note that they vary from the basic rules described in CSAPP. Follow the style of heap drawings used in the CSAPP book (Figures 9.36-9.38), but remember that block details will vary. (Ignore Figure 9.42 – we have no prologue block.) Always draw the heap header word, the heap footer word, and the headers (and footers as needed) for all blocks in the heap.

1. Draw a heap that contains a single allocated block with size 48. (Assume page size = total heap size = 64 bytes)
2. Draw a heap that contains a single free block with size 64. (Assume page size = total heap size = 80 bytes)
3. Draw a heap that contains an allocated block with size 48, followed by a free block of size 32. (Assume page size = total heap size = 96 bytes)
4. Draw a heap that contains a free block of size 32, followed by an allocated block of size 48. (Assume page size = total heap size = 96 bytes)

B. Simulate the Starter Allocator

Submit answers for at least one question in B.

Simulate the starter allocator code by hand starting from an heap generated by a call to mm_init. Assume words are 8 bytes and pages are 4096 bytes. Update a drawing of the heap as you go, following the drawing guidelines from part A. Show exactly what this starter allocator does, not your idea of what an allocator should do. This will force you to read and understand the provided code carefully in detail. Add comments as you go if it helps you to keep notes in addition to the provided comments.

1. Starting from a fresh initial heap, simulate the following requests and update your drawing based on what the starter code allocator does:

     p0 = mm_malloc(12);
     p1 = mm_malloc(16);
     p2 = mm_malloc(16);
     mm_free(p0);
     mm_free(p1);
     p3 = mm_malloc(24);
   

2. Starting from fresh initial heaps, simulate the traces short1-bal.rep and short2-bal.rep from the traces directory in the starter code. The format of trace files is described here.

C. Starter Functions

Submit brief answers for all questions in C.

1. What do the LOAD and PSTORE functions do? Why might it be preferable to use them in place of normal C pointer operations?
2. Given a block pointer bp, write an expression using helper function calls to return the allocation status of the block preceding bp in memory order.
3. What fit policy does search employ?
4. Why does extend_heap coalesce its newly added space? Consider that extend_heap is typically called only if no existing free block is large enough to satisfy the current allocation request.

D. Add and Simulate Pseudocode Features

For each of the following features, add the feature by sketching pseudocode comments within mm.c. Then, before working on the next feature, simulate the allocator with this feature on the sample traces from the previous part, drawing heap state as you go.

1. Sketch a pseudocode implementation of free.
2. Sketch a pseudocode implementation of splitting in allocate.
3. Sketch a pseudocode implementation of coalesce.

Write pseudocode at a sufficient level of detail that you can simulate clearly, but do not get tangled up in C-level pointer work.

Submit pseudocode by committing comments in mm.c. Submit a heap drawing for the simulation of one trace after pseudocoding all 3 features.

Tips

• Take notes on anything you learn during the preparatory exercises.
• Read instructions and comments in provided code carefully.
• Draw diagrams of the heap and execute operations on the visual heap by hand to become familiar with the details or debug.
• Every line of provided code does something meaningful and necessary.

Implicit Free List Allocator

Convert your pseudocode feature implementations to C code one at a time, testing and committing each before starting C code for the next feature.

1. Implement and test free.
2. Implement and test splitting in allocate.
3. Implement and test coalesce.

Run tests on individual traces for debugging and on all traces for general testing and performance evaluation.

• Some provided traces will cause your allocator to run out of memory unless you have completed all three features.
• Any other errors or crashes indicate correctness problems you must fix.
• The traces short1-bal.rep and short2-bal.rep should work from the beginning, but they are suitable only as small debugging samples.
• Write your own small traces to help test or debug individual cases.
• Use check_heap to sanity-check each feature before implementing the next or to help debug when things go wrong.

Search Strategy

Once you have a working implicit free list allocator using a first-fit policy with freeing, splitting, and coalescing implemented, one potential performance improvement strategy is to try alternative fit policies. Consider how they are likely to affect your performance index relative to first fit and relative to the performance improvements that could result from an explicit free list. Make sure to hg commit before trying this. For a next-fit policy, we suggest:

• Add a constant/macro NEXT_FIT_POLICY that is 1 if using next fit or 0 otherwise. Write code such that you can easily switch policies by switching this value. #define NEXT_FIT_POLICY 1
• Use a global variable or the first heap word to save a pointer to the block where the next search should begin. Add helper functions for getting and setting this pointer if using the latter.

Explicit Free List Allocator

The best way to develop an explicit free list allocator (or a more sophisticated seglist allocator) is to first develop a working implicit free list allocator and extend it to use explicit free lists.

Some suggestions as you implement explicit free lists:

1. An explicit free list allocator (or a next-fit allocator) must store a pointer to the list head node somewhere. The first word of the heap (or a single global pointer variable if necessary) is a good place to store this. Helper functions for getting and setting this pointer will keep list manipulations clean.
2. Free blocks must contain next and previous pointers. Consider how this affects block size. Choose a fixed offset within the block to store each of the pointers. Helper functions for getting and setting these pointers will keep list manipulations clean. Using block headers as the target of these pointers in all cases is the simplest, easiest, most efficient option.
3. We suggest disabling coalescing, splitting and free while you complete initial development of the explicit free list.
4. Update search, allocate, and extend_heap to use your explicit free list structure and test the allocator.
5. Update free to use the explicit free list and test it.
6. Update allocate to support splitting with the explicit free list and test it.
7. Update coalesce to support coalescing with the explicit free list and test it.
8. To reach the best performance for this implementation, you likely need to enable compiler optimizations. Add -O to the CFLAGS line in your Makefile, then make clean and make to recompile. You could also consider disabling assertions with -DNODEBUG to save work. (Both of these may make debugging a little more difficult, so use it only once your code is working.)

Seglists and Beyond

Once you have a working explicit free list allocator, a potential performance improvement strategy is to try alternative free list implementations. Weigh difficulty of implementation against likely affect on performance index. Note that seglists or other sophisticated allocation schemes may receive additional extra credit beyond improvement in the performance index.

Programming Rules

• Do not change any of the mm_ function types in mm.c. You may add as many helper functions and macros as you wish and change the existing helper functions.

• Do not invoke any standard memory-management related library calls or system calls. Do not use malloc, calloc, free, realloc, sbrk, brk or any variants of these calls in your code. (You may use all the functions in memlib.c, but if you use the provided starter code, you likely will not need to use these directly.)

• Do not define any global or static compound data structures such as arrays, structs, trees, or lists in your mm.c program. You may declare global scalar variables such as integers, floats, and pointers in mm.c, but avoid them if at all possible.

• For any new functions, write function header comments (and for the main existing functions mm_malloc, mm_free, search, allocate, and coalesce expand existing comments) to describe what the function does, using what policy (if applicable), and what it assumes. Use inline comments to describe details as needed.

• Since some of the unstructured pointer manipulation inherent to allocators can be confusing, small helper functions and short inline comments on steps of the allocation algorithms are recommended.

Compiling and Testing

The driver program mdriver tests your mm.c implementation for correctness, space utilization, and throughput. Build mdriver with make and run it with the command ./mdriver -V (the -V flag displays helpful summary information as described below).

The driver program is controlled by a set of trace files. Each trace file contains a sequence of allocate and free directions that instruct the driver to call your mm_malloc and mm_free functions in some sequence. The driver and the trace files are the same ones we will use when we grade your submitted implementation.

The mdriver executable accepts the following command line arguments:

• -t <tracedir>: Look for the default trace files in directory tracedir instead of the default directory defined in config.h.
• -f <tracefile>: Use one particular tracefile for testing instead of the default set of tracefiles.
• -h: Print a summary of the command line arguments.
• -l: Run and measure libc malloc in addition to the student’s malloc package.
• -v: Verbose output. Print a performance breakdown for each tracefile in a compact table.
• -V: More verbose output. Prints additional diagnostic information as each trace file is processed. Useful during debugging for determining which trace file is causing your malloc package to fail.

Common Testing Tasks

Run tests on individual traces (./mdriver -V -f traces/your-favorite-trace.rep) for debugging and on all traces (./mdriver -V) for general testing and performance evaluation. Some traces provided in the traces directory will cause your allocator to run out of memory until you have completed all three features. Any other errors or crashes indicate correctness problems you must fix. The traces short1-bal.rep and short2-bal.rep should work from the beginning. You may find it useful to write additional traces for debugging.

Trace Format

When learning about the starter code, you will simulate small traces. When testing and debugging, you may find it useful to write and test your own small traces.

Traces used by mdriver summarize the execution of a program as a sequence of malloc and free calls in a simple format.

A trace file contains 4 header lines:

1. Suggested heap size (any number, ignored by our tests).
2. Total number of blocks allocated.
3. Total number of malloc/free events.
4. Weight (any number, ignored by our tests).

Remaining lines after the header give a sequence of allocation events, one per line. Each allocation event is either a malloc event or a free event:

event ::= a id size
        | f id

• Event a i size indicates the ith call to malloc in the trace, requesting payload size. The ID i uniquely identifies the malloc call and the allocation it makes, starting at 0 for the first allocation in the trace.
• Event f i indicates a call to free with the pointer that was returned by the ith malloc call in the trace.

The following example C code would generate the corresponding trace below it:

C code:

p0 = malloc(12);
p1 = malloc(16);
p2 = malloc(16);
free(p0);
free(p1);
p3 = malloc(24);

A corresponding trace:

128
4
6
1
a 0 12
a 1 16
a 2 16
f 0
f 1
a 3 24

Heap Consistency Checker

The function check_heap implements a basic consistency check on the heap and also prints out all blocks in the heap in memory order. You may find it helpful to insert calls to check_heap to assist in testing and debugging allocator features you add. You are also welcome to extend it. Make sure to remove all calls to check_heap before submitting your code. It will definitely affect performance evaluation.

Performance

For the most part, a correct implementation based on our provided code will yield passable performance. Two performance metrics will be used to evaluate your solution:

• Space utilization: The peak ratio between the aggregate amount of memory used by the driver (i.e., allocated via mm_malloc but not yet freed via mm_free) and the size of the heap used by your allocator. The optimal ratio is 1. Choose policies that minimize fragmentation to maximize utilization.
• Throughput: The average number of allocator operations completed per second.

The mdriver program computes a performance index, which is a weighted sum of the space utilization and throughput:

P = 0.6×U + 0.4×min(1, T/T_libc)

where U is your space utilization, T is your throughput, and T_libc is the estimated throughput of the standard C libary (libc) version of malloc on the default traces. The performance index favors space utilization over throughput.

Your allocator must balance utilization and throughput. A performance index of 70-80/100 or above is pretty good. My implementations have achieved the following performance scores:

• Implicit free list with splitting and coalescing:
  • first-fit: 50/100
  • next-fit: 56/100
• Explicit free list with splitting and coalescing:
  • first-fit: 91/100

To reach this level of performance, you likely need to enable compiler optimizations. Add -O to the CFLAGS line in your Makefile, then make clean and make to recompile. You could also consider disabling assertions with -DNODEBUG to save work. (Both of these may make debugging a little more difficult, so use it only once your code is working.)

How to Work

Low-level unguarded memory manipulation code like this allocator is prone to subtle and frustrating bugs. There’s a reason you often use higher-level languages with more protections! The following strategies help to work effectively and avoid long hours of frustration and confusion.

Plan Carefully

Review allocator concepts, complete the preparatory exercises, and read the provided code carefully. Never write code until you have a good idea of what you are doing and what is already there.

Code Defensively

Expect things to go wrong. Anywhere your code relies on an assumption, check it explicitly. Explain to your partner why your code should work. Write error-prone code once carefully and reuse it.

• Use assertions. Anywhere you assume a property of data to hold, assert that property explicitly. Assertions document your assumptions. They are also checked explicitly as your program runs, making it easier to localize the source of an error if one occurs.

• Use the provided helpers for memory access (LOAD, STORE, PLOAD, PSTORE.) and pointer arithmetic (PADD and PSUB). This helps avoid pointer manipulation errors or at least catch them early.

Implement and Test Incrementally

Implement, test, and commit one feature (or sub-feature!) at a time, testing and committing each before you start implementing the next. This will make it much easier to understand what code is involved in a bug.

Debug Methodically

GDB and the check_heap function are the tools of choice. Here are some strategies and other tips.

• Did your program hit an explicit error? An assertion failure? A segfault?
  • Localize the crash. Exactly what line of code, what operation in this line, what value(s) used by this operation manifested what error and crashed? This symptom rarely indicates the cause, but it marks where to begin the search.
    • Use gdb to run the code until it crashes, then find the line that crashed (and the context in which it executed) with bt, backtrace, or where.
    • Inspect the most relevant line of code and the error report to determine what the error means. Was it a segfault? If it was an assertion failure, what was the assertion checking?
    • Inspect the arguments shown in the backtrace or print variables to determine what ill-formed pointer was dereferenced to cause a segmentation fault or what illegal values failed an assertion.
  • Trace backward through the dependences of this broken operation to the original logic error.
    • Invalid values: Did any of this operation’s arguments hold invalid values? Did this operation load any invalid values from memory?
      • What operations produced these invalid values?
        • This is easy to answer for invalid arguments.
        • For invalid memory values, consider what earlier operations (perhaps in completely separate function calls) may have saved (or failed to save) this value. Look ahead to the memory tips.
      • Continue tracing backwards treating these producer operations as broken operations.
    • Invalid choices: Was it invalid to apply this operation here given correct arguments (or regardless of the arguments)?
      • What control flow decision led to execution of this operation?
      • Is the logic of the decision correct?
      • If so, continue tracing backwards treating the control flow decision as a broken operation.
    • Callers: You may need to trace back beyond the function where the crash happened.
      • Get a backtrace to see where the current function was called. (Don’t just assume you know which function called this one. Get the truth.)
      • If you want to inspect local variables in functions that called this one, use up and down in gdb to step up and down the call stack, then print what you want to see.
    • Memory: Remember, mm_malloc and mm_free are called many times during the execution of the driver program. They depend on their arguments, but also the entire contents of the heap as it exists when they are called, so changes made by earlier calls to mm_malloc and mm_free affect data used by this one.
      • Use the check_heap function to scan the heap.
      • Run it at arbitrary times in gdb with call check_heap().
      • Or hard-code calls to it in your code so you see how the heap evolves with each mm_malloc or mm_free call.
  • Minimize the input. Try to write a small trace that captures the essence of the large trace on which your allocator has an error. A smaller trace is easier to reason about in full.

• valgrind will be less useful since you are doing very low-level work, implementing the memory allocator itself. valgrind excels in analyzing programs that use the memory allocator.

• If resorting to printing (try gdb first), use fprintf(stderr, "...", ...) instead of printf("...", ...) and be sure to remember newline for clarity. Disable any printing in final version.

• Use the mdriver -f option. During initial development, using tiny trace files will simplify debugging and testing. We have included two such trace files (short1-bal.rep and short2-bal.rep) that you can use for initial debugging. You can also write your own for targeted debugging/testing.

• Use the mdriver -V option. The -V will option will give a detailed summary for each trace file and indicate when each trace file is read, which will help you isolate errors.

• Does your code seem to be running forever?
  • That might be because it is no longer broken! Comment out those calls to check_heap. Printing the full contents of the heap on every allocation event costs orders of magnitude more than the allocations or frees themselves.
  • Or it might be because you have a size 0 block somewhere other than the heap footer word.

Extra Credit Open-Ended Extensions

There are a number of interesting allocator features you could add if looking for more fun or extra credit. Each is annotated with a possible extra credit award for a thorough, well-designed, well-implemented extension. If your extension also improves performance above a performance index of about 90/100, this will also be reflected in your grade independent of this extra credit. Talk to Ben if you are curious about any of these or if you have ideas for others. Some larger extensions would be larger than the original assignment.

Basic Heap Consistency Checker (up to +5)

Dynamic memory allocators are notoriously tricky to program correctly and efficiently. They involve a lot of subtle, untyped pointer manipulation. In addition to the usual debugging techniques, you may find it helpful to write a heap checker that scans the heap and checks it for consistency.

Some examples of what a heap checker might check are:

• Is every block in the (explicit) free list marked as free?
• Are there any contiguous free blocks that somehow escaped coalescing?
• Is every free block actually in the (explicit) free list?
• Do the pointers in the (explicit) free list point to valid free blocks?
• Do any allocated blocks overlap?
• Do the (explicit free list) pointers in a heap block point to valid heap addresses?

Your heap checker will extend the function int check_heap() in mm.c. Feel free to rename it, break it into several functions, and call it wherever you want. It should check any invariants or consistency conditions you consider prudent. It returns a nonzero value if and only if your heap is consistent. This is not required, but may prove useful. When you submit mm.c, make sure to remove any calls to check_heap as they will slow down your throughput.

Extended Error-Checking (up to +100)

Building from a heap consistency checker, consider how to augment the allocator to do additional error-checking on the fly to detect common errors when using a memory allocator. You could insert extra padding, use canary values, place recently freed blocks in a waiting area, or track additional information about earlier allocations and frees to detect errors.

Implement realloc (up to +20)

Implement a final memory allocation-related function: mm_realloc. The signature for this function, which you will find in your mm.h file, is:

extern void* mm_realloc(void* ptr, size_t size);

Similarly, you should add the following in your mm.c file:

void* mm_realloc(void* ptr, size_t size) {
  // ... implementation here ...
}

Follow the contract of the standard C library’s realloc exactly (pretending that malloc and free are mm_malloc and mm_free, etc.). The man page entry for realloc says:

   The realloc() function changes the size of the memory block pointed to by
   ptr to size bytes.  The contents will be unchanged in the range from the
   start of the region up to the minimum of the old and new sizes.  If the
   new size is larger than the old size, the added memory will not be
   initialized.  If ptr is NULL, then the call is equivalent to
   malloc(size), for all values of size; if size is equal to zero, and ptr
   is not NULL, then the call is equivalent to free(ptr).  Unless ptr is
   NULL, it must have been returned by an earlier call to malloc(), calloc()
   or realloc().  If the area pointed to was moved, a free(ptr) is done.

A good test would be to compare the behavior of your mm_realloc to that of realloc, checking each of the above cases. Your implementation of mm_realloc should also be performant. Avoid copying memory if possible, making use of nearby free blocks. Do not use memcpy to copy memory; instead, copy WORD_SIZE bytes at a time to the new destination while iterating over the existing data.

To run tracefiles that test mm_realloc, compile using make mdriver-realloc. Then, run mdriver-realloc with the -f flag to specify a tracefile, or first edit config.h to include additional realloc tracefiles in the default list.

Seglists or other advanced allocators (up to +50)

Implement a seglist allocator or other sophisticated allocation schemes and measure performance impact.