Assignment 7: Heap allocator

Due: Fri Mar 17 11:59 pm
No late submissions accepted.

Assignment by Julie Zelenski, based on original assignment given by Randal Bryant & David O'Hallaron (CMU)

Learning goals

In completing this assignment, you will:

1. study the internals of the heap allocator
2. experiment with the process of evaluating and choosing among alternative designs
3. apply optimization techniques to find and mitigate runtime/memory inefficiencies
4. explore performance trade-offs and weigh improvements against the complexity of code required to achieve them
5. bring together all of your CS107 skills and knowledge into a satisfying capstone experience!

Your assignment

You are to design and implement an allocator that implements malloc, realloc, and free. Your allocator obtains a large contiguous segment from the OS and parcels out this segment to service dynamic allocation requests. The key goals for the allocator include:

• it must correctly service any combination of well-formed requests
• it makes compact use of memory (i.e. densely-packed, low fragmentation)
• it runs fast

Just three little functions? How hard can that be? :-) The challenge is to strike a balance between tight memory utilization and high throughput, while maintaining correctness in all situations. It is possible to write an efficient allocator with a couple hundred lines of code. However, it will require your most skilled and sophisticated coding and you may end up more proud of those three functions than any code you've written heretofore. What a great way to finish off an awesome quarter!

For this assignment, you have the option of working in a team of two or working individually. The project requirements are the same either way. A team makes one submission and both partners receive the same score. Read our advice for successful partnership.

Implementation requirements

• The interface should match the standard libc allocator. Carefully read the malloc man page for what constitutes a well-formed request and the required handling to which your allocator must conform. Note there are a few oddballs (malloc(0) and the like) to take into account. Ignore esoteric details from the NOTES section of the man page.
• There is no requirement on how to handle improper requests. If a client reallocs a stack address, frees an already freed pointer, overruns past the end of an allocated block, or other such incorrect usage, your response can be anything, including crashing or corrupting the heap.
• Your routines are named mymalloc, myrealloc, and myfree to avoid clashes with the libc version. You will also implement myinit to configure the initial state and validate_heap to verify internal heap consistency.
• An allocated block must be at least as large as requested, but it is not required to be exactly that size. The maximum size request your design must accommodate is INT_MAX bytes. If asked for a block larger than the max size, your allocate should return NULL, just as with any request that cannot be serviced. Every allocated block must be aligned to an address that is a multiple of the ALIGNMENT constant (8). It's your choice whether small requests are rounded up to some minimum size.
• The heap segment is a large contiguous region of memory obtained from the OS. We provide routines that interface with the OS for you to manage this segment. These functions are documented in segment.h.
• You cannot invoke any memory-management functions other than those provided in segment.h. By "memory-management" we specifically mean those operations that allocate or deallocate memory, so no calls to malloc, realloc, free, calloc, sbrk, brk, mmap, or related variants. The use of other library functions is fine, e.g. memmove and memset can be used as they do not allocate or deallocate memory.
• Your allocator may use a small amount of static global data, limited to at most 500 bytes. This restriction dictates the bulk of the heap housekeeping must be stored within the heap segment itself. There is no constraint on what you store (i.e. no requirement to use or not use block header/footers, which kind of data structures) but there is a condition on where you store it (i.e. at most 500 bytes of data can be stored in global variables; all additional housekeeping must be stored within your heap segment).
• Your validate_heap function will be called from our test harness when checking correctness to verify the internal consistency of the heap data structures after servicing each request. This is here to help you with debugging. The validity check will not be made during any performance testing, so there is no concern about its efficiency (or lack thereof).
• Our test harness measures allocator utilization and throughput. Utilization is the ratio of the number of in-use payload bytes to the total heap segment size. For example, if 100 blocks of size 32 have been allocated and the heap segment is currently the size of one page (4K), the utilization will be (32*100)/4096 = 78%. Throughput counts the number of requests serviced per second. The throughput performance is reported as a percentage relative to a fixed target. The utilization ranges from 0 to 100%, the throughput from 0 to > 100%.
• Your submitted project will include a readme.txt file that documents your design, how you chose its features, your efforts to optimize, and your evaluation of the end result.
• Our code review for this assignment will involve less scrutiny, which is an appropriate segue for the end to CS107. Our TAs have expended untold hours this quarter to provide detailed feedback on your code, but subsequent systems classes tend to grade mostly/solely on functionality. The belief is that you will have internalized the lessons of CS106/107 and can apply your own internal compass. You may rejoice that can get away with all sorts of questionable practices when no one is looking closely, but we hope our efforts have helped convince you that writing clean code is truly its own reward in terms of easier testing, debugging, maintenance, and more.
• Don't miss out on the companion advice page: Go to advice/FAQ page

Using the alloctest program and script files

You can do simple testing of your allocator with an ordinary C program that makes targeted malloc/realloc/free calls. The given simple.c program can be used in this way. We also provide alloctest.c, a script-based test harness for the allocator. The alloctest program reads a script file, executes its requests, verifies they were correctly serviced, and measures allocator performance. A sample report on one script is shown below.

alloctest -f tiny1.script
Evaluating allocator on tiny1....done.

 script name     correct?    utilization   requests       secs        Kreq/sec
-------------------------------------------------------------------------------
tiny1                Y            33%           12       0.000018        675
-------------------------------------------------------------------------------

Aggregate 1 of 1                  33%           12       0.000018        675
33% (utilization) 6% (throughput, expressed relative to performance target)

Below is an overview of how alloctest operates. You can review the code in alloctest.c for further details.

• If you invoke alloctest with no arguments, it runs all the scripts from /afs/ir/class/cs107/samples/assign7. Invoke wth the -f flag to change which scripts are being run. The -f argument is the path to a single script file or a directory of script files.
• Script files
  • A script file is a text file containing a sequence of allocator requests expressed in a simple domain-specific language. Open one of the tiny scripts in a text editor to see the format.
  • The starter project contains a few tiny scripts intended as a first step in early development and debugging.
  • The directory /afs/ir/class/cs107/samples/assign7 contains a collection of varied scripts. These large scripts are best suited for testing the performance of an already-debugged implementation. The ones named x-trace were constructed by tracing the allocation calls made by a running program, e.g. reassemble-trace traces assignment 1. These represent real world testing patterns. The scripts named x-pattern were mechanically generated via patterns such as alternately allocating a small and large chunk.
  • You can make your own script files in order to help with early development or to experiment with different use cases or patterns for performance testing.
• Invoking alloctest -c will only verify correctness, alloctest -p will only measure performance. The default (no flags) does both: first correctness, then performance.
• When testing correctness, it has simple checks to try to verify that the requests are being properly serviced (addresses are aligned, blocks non-overlapping, payload contents maintained, validate heap succeeds) and reports an error when any of those checks fail
• One easy-to-overlook detail is that alloctest calls the allocator's myinit function after executing one script and before starting another. To prevent bugs due to ghost heap housekeeping leftover from the previous script, your myinit function must correctly wipe the slate clean, removing any previous heap contents and starting fresh.
• The performance evaluation uses the timer functions from B&O that count cycles by reading the processor's real-time clock and does repeat trials until the results converge. It will do at least 3 trials, and up to as many as 20, to smooth out measurement noise. It does no correctness checks while running the scripts to measure performance.

Grading

Background information on how we grade assignments. The focus of this assignment, and much of the weight in grading, is concentrated on efficiency.

Correctness (48 points)

• Basic cases (26 points) Correct servicing of sequences of mixed requests. We will test on the provided simple program, the published sample scripts, and a few additional scripts. It is essential your allocator work reliably on all valid sequences to earn these points.
• Robustness (20 points) Handling of required unusual/edge conditions (request too large, malloc 0 bytes, etc.)
• Clean compile (2 points) We expect your code to compile cleanly without warnings.

Performance (80 points)

We will use alloctest to measure your allocator's utilization and throughput on a set of mixed scripts that are similar, but not identical, to the published samples. The scoring formula will be as follows:

• U = utilization - 25
• T = throughput / 2
• Values for U and T are capped to the range [0, 50]. Full-credit benchmarks are U = 40 (utilization >= 65%) and T = 40 (throughput >= 80%). There are up to 10 bonus points per category for exceeding the benchmarks.
• Performance points = 1.5*min(U,T) + .5*max(U,T). This blend rewards a balance between the two, rather than going to extremes to optimize one at the expense of the other.

Submissions with bugs that interfere with performance testing will earn points at a reduced rate. The performance points formula will be applied to the scripts which operate correctly with a penalty adjustment for the failures.

The scripts use for performance grading will be similar to the set of sample scripts. Your allocator's performance on the published samples is predictive of the measurement we will make for grading, but not an exact match. The goal is not to tune your allocator to perform at its best on exactly and only the samples, but instead develop a design that fares well in a wide variety of scenarios, for which the samples are representative possibilities.

Code quality (buckets weighted to contribute ~20 points)

• We expect your allocator code to be clean and readable. We will look for descriptive names, helpful comments, and consistent layout. We expect your code to show thoughtful design and appropriate decomposition. Control flow should be clear and direct. We expect common code to be factored out and unified. Complex tasks or tricky expressions that are repeated should be decomposed into shared helpers.
• The code review will also assess the thoroughness and quality of your validate_heap routine.

Design documentation (32 points)

A number of points are allocated for the readme file where you will document your allocator design, along with your process and results. You are to address the issues below with clear, complete, and concise writing. The intended audience is a programmer-literate peer.

• Overview. (8 points) Summarize the key implementation features (e.g. data structures and algorithms used).
• Rationale. (8 points) Provide a brief justification of why you made those design choices (esp. in light of alternatives tried/considered).
• Optimization. (8 points) Describe techniques/strategies you used to analyze performance and make improvements. Where appropriate, provide supporting data (timing results, callgrind counts and cache statistics, disassembly comparison, etc.) on your efforts.
• Evaluation. (8 points) Give a realistic evaluation of the overall strengths/weaknesses of your final allocator.
• References. You must include proper citation for any resources (people, books, web, etc.) that contributed to the design of your allocator.

We will evaluate your design document on its thoughtfulness and completeness in describing, analyzing, and evaluating your design and process. Readme credit is not tied to successful performance results. If your results are not what you'd hoped for, use the readme to tell us about it, i.e. the observed problems, what its root cause seems to be, what you tried that didn't pan out, what you learned in the process, and so on.

Getting started

Check out a copy of the starter project from your cs107 repository using the command

hg clone /afs/ir/class/cs107/repos/assign7/$USER assign7

The starter repo contains these files:

• Makefile The Makefile builds two targets: simple and alloctest. Edit ALLOCATOR_EXTRA_CFLAGS to configure the best build settings for your allocator; make no other changes to the Makefile.
• allocator.c/.h Edit allocator.c to implement your allocator (remove/replace the trivial implementation given in starter).
• segment.c/.h The segment.c module provides the low-level memory allocator. Do not edit these files.
• fcyc.c/.h The fcyc.c module is the cycle-counting timer from Chapter 5 of the Bryant and O'Hallaron. Do not edit these files.
• simple.c The simple.c module is a sample program that manipulates linked lists and strings using dynamic allocation. You can use/change/cannibalize this program for testing.
• alloctest.c The alloctest.c module contains the script-driven test harness to evaluate your allocator. Do not edit this file.
• script files The project contains a few scripts. The tiny scripts are suitable for very simple testing and serve as examples of the script file format. There is a collection of large scripts in the cs107/samples/assign7 directory for further testing and performance measurements. You can also write your own script files.
• readme.txt Edit this text file to document your design decisions and rationale.

Special attention to the Honor Code

Before you begin coding, you'll want to consider a range of design options. The textbook contains good foundation material which you are encouraged to review as a starting point. You may also find it helpful to talk over implementation options and trade-offs with classmates. Your readme must properly cite any external resources or discussions that influenced your design. When it comes to code-level specifics, your allocator must be your independent work. Under no circumstances should you be studying code from outside sources nor incorporating such code. If you accidentally stumble across allocator code written by someone else, we expect you to immediately about-face from it and get back to designing and writing your own allocator. We have a zero-tolerance policy for submissions containing code that has been adopted/borrowed from others. Lacking citation, this act constitutes plagiarism and will handled as a violation of the Honor Code.

A student who is retaking the course may not re-use the design, code, or documentation from any previous effort. The prohibition against re-use applies regardless of whether the original submission was partnered or individual. The best approach to avoiding problems is to discard all work from the past, as it can be a temptation that you're better off without.

Finishing

When finished, don't forget to submit your files for grading. Only one partner makes the submission, not both.

Absolutely no submissions will be accepted after the deadline, nor will there be any option to make up from a missed/poor submission. Cutting it too close can land you on the wrong side of the deadline with no recourse other than to discard all your hard work into the rubbish bin. Do not let this happen to you -- submit early, submit often, so you'll have an insurance policy against any unexpected last-minute mishap.

Check in with post-task self-check and it's definitely time to celebrate-- congratulations on an awesome quarter!