CS3410 Spring 2016
Due: 4:30pm, Tuesday, May 17
Reminder: you must work in a group of two for this project. You don't need to have the same partner as the earlier projects.
In this assignment, you will implement a dynamic memory allocation library that supports the allocation, freeing, and resizing of blocks of memory. Your code must follow both the given interface and the functional specifications of the assignment. In all other ways, however, you should be creative: design your own data structures; put your problem-solving skills to work! You are free to implement existing/known approaches to solving this problem or come up with your own original ideas. As you consider your options, you should under no circumstances look at others' code (including code on the internet) or show your code to anyone outside of your group of two.
By now you are familiar with static vs dynamic allocation. Statically allocated memory is allocated on the stack and exists only for the life of the function in which it was allocated; dynamically allocated memory is allocated on the heap and exists from the moment it is allocated until it is explicitly freed. Support for dynamic memory allocation is part of the Standard C Library. For this assignment, however, you will write your own versions of these functions.
A dynamic memory allocator maintains the memory associated with the
heap. The most basic task will be to keep track of which bytes of the
heap are currently in use (i.e., are allocated) and which bytes
are not in use (i.e., free). On real systems, the heap can grow
with the needs of a process. For this assignment, however, we will
consider the heap to be a fixed-size block of memory. The
functions you implement will take a void *heapptr
argument that points to the beginning of the heap that you must
manage. (Of course the heap here being pointed to
by heapptr
is a simulated version of the actual heap that
the C Standard Library manages.) Your dynamic memory allocator will
consist of the following four functions, which are declared
in heaplib.h
and will be defined (by you)
in heaplib.c
:
int hl_init(void *heapptr, unsigned int heap_size)
heapptr
and of
size heap_size
(in bytes). Note that
your hl_init
function does not actually need to allocate
or create the heap. It is given a block of memory of the correct size,
starting at the location pointed to by heapptr
. (When it
comes time for you to test your code, the test cases we provide will
show you a few ways in which this block of memory can be created.)
The hl_init
function should be called once before
there are any calls to hl_alloc
, hl_release
,
or hl_resize
.
Your memory allocator must live entirely inside the heap it is
managing. This means that all meta-data (pointers, size fields, flags
indicating free or in-use) must all live in the heap itself. You may
not use any global arrays, variables, or structures. A good test of
this is whether your implementation supports
multiple heapptr
s. Your code should naturally support
multiple heaps.
Do not assume that heapptr
is 8-byte aligned.
If heap_size
is not large enough to hold the
meta-data required to manage the heap (as you have designed it),
setup fails, and the function returns 0. Returns non-zero if successful.
void *hl_alloc(void *heapptr, unsigned int
block_size)
block_size
bytes from the heap pointed to
by heapptr
.
Returns a pointer to the block of memory on success; returns 0 if the allocator cannot satisfy the request.
Blocks of memory can be of size 0. The returned address should be aligned at multiples of 8 bytes. The function is allowed to allocate more than the requested size, but never less. The memory "allocated" by this function does not need to be zeroed out.
void hl_release(void *heapptr, void *blockptr)
blockptr
(that
currently resides in the heap pointed to by heapptr
).
If blockptr
has the value 0, the function should do
nothing. (If it has some non-zero value that was never the return
value of a call to hl_alloc
or hl_resize
,
the program behavior is undefined. You need not fail gracefully.) For
utlization purposes, released memory should be able to be allocated
again by subsequent calls to hl_alloc
.
The memory released by this function does not need to be zeroed out.
void *hl_resize(void *heapptr, void *blockptr, unsigned int
new_block_size)
blockptr
(that currently resides in the
heap pointed to by heapptr
) from its current size to
size new_block_size
bytes, returning a pointer to the new
block, or 0 if the request cannot be satisfied. The contents of the
block should be preserved. If the location of the block changes
(because it is not possible to make the block pointed to
by blockptr
larger and a new, larger block elsewhere
needs to be used), you can copy the contents by
using memcpy
or cast blockptr
to
a char *
and copy the contents byte by byte.
The new block size might be smaller than the current size of the
block. As it was for hl_alloc
, the return value should be
8-byte aligned. If blockptr
has the value 0, the function
should behave like hl_alloc
.
Note: Your
functions hl_alloc()
, hl_release()
,
and hl_resize()
correspond to the actual C Standard
Library functions malloc()
, free()
,
and realloc()
. Nowhere in heaplib.c
should you call these three functions.
heaplib_naive.c
-- the naive implementation. this is the first file you should look at.
heaplib.c
-- where you will implement your memory allocator
heaplib.h
-- contains the interfaces of the
functions you are to implement.
heaptest.c
-- test file you may use for coding and
debugging. a good place to develop a test before adding it to one of
the official test_.c
tests below.
Makefile
-- compiles 3 versions of 4 executables (see below)
test_c.c
-- tests for correctness
test_u.c
-- tests for heap utilization, exclusively uses:
sizetask.c
-- a task designed by you to measure heaplib's space utilization
sizetask.h
-- its header
test_t.c
-- tests for throughput, exclusively uses:
speedtask.c
-- a task designed by you to measure heaplib throughput
speedtask.h
-- its header
heaptest
, test_c
, test_u
,
and test_t
. The heart of this assignment is your
implementation of the functions declared in heaplib.h
. You
are implementing a library, which does not contain
a main
. The four test files use your library; each has
its own main
. None of the test files are complete (part
of the assignment will be for you to complete them!), but they are a
good start.
How you compile your code will determine whether your tests use the
implementation of heaplib.h
in heaplib_naive.c
or heaplib.c
. Since you
will spend much more time working with heaplib.c
, this is
the default. If you type make help
you will see a
slightly longer version of the following message:
Your custom heaplib.c implementation targets: make : heaplib.c make prof : heaplib.c with profiling symbols make debug : heaplib.c with debugging symbols make print-debug : heaplib.c with debugging symbols and PRINT_DEBUG The naive implementation targets: make naive : heaplib_naive.c make naive-prof : heaplib_naive.c with profiling symbols make naive-debug : heaplib_naive.c with debugging symbols make naive-print-debug : heaplib_naive.c with debugging symbols and PRINT_DEBUG <snip>
The first target (built by typing make
or make
naive
produces "production level" versions of all four
executables. This is how we will compile your code when we test it.
The second target will be discussed later under "Optimizing Your Code".
The third target (built by typing make debug
or make naive-debug
) is an executable that contains all
the symbols (variable and function names, line numbers, etc.) required
to run your code in gdb.
The fourth target (built by typing make print-debug
or make naive-print-debug
) is an executable that has both
debugging symbols and has defined the PRINT_DEBUG macro that will
enable all the debugging print statements in your code.
Go ahead and peek at the Makefile. It doesn't bite and is fantastically documented. (Look, but don't touch!)
We have provided you with a naive implementation of the assignment
in heaplib_naive.c
.
heap_header_t
as follows:
typedef struct heap_header_t { unsigned int size; int bytes_free; char *next_free; } heap_header_t ;This strategy dedicates the beginning of the heap to maintain information about the heap; there are three fields in this header. The first field holds the size of the heap. This field will be set by
hl_init
and never changed again. The second field
indicates how many bytes there are left in the heap. This field will
be useful when trying to determine whether a
particular hl_alloc
call can be successfully serviced. The
third field is a handy shortcut that keeps track of the next unused
byte in the heap. Notice that this field is not strictly necessary,
since it would be possible to calculate the location of this byte,
given the starting address of the heap and the number of free bytes
remaining. But hey, it's naive, right?
Let's step through this naive implementation of some of the
functions. Figures 1 and 2 show the state of memory before and after a
call to hl_init
with a heap of size 32 beginning at
address 0x100:
Figure 3 shows what a subsequent call to hl_alloc
with
a block size of 4 bytes would change the heap:
Figure 4 shows that the allocated block has been filled with data 'abcd'. Figure 5 shows how a call to resize would change the heap:
These diagrams are not intended to show you the correct
behavior of the functions you should implement. Instead they show you
an accurate depiction of what is currently implemented so that you may
fully understand the code you have been given. Notice, for example,
that the current implementation does not support the reuse of a
resized block. This is a huge flaw in this approach from a utilization
standpoint. Similarly, hl_release
does nothing,
meaning that released memory cannot be allocated again by subsequent
calls to hl_alloc
.
Known Correctness Bugs. In addition to being a terribly
inefficient use of space, the naive solution
in heaplib_naive.c
is incorrect in several respects:
heapptr
is assumed to be 8-byte aligned.
hl_reszie
does not copy the values from the
original block to the new block
Although the implementation is woefully inadequate as a solution to the assignment, it provides you important examples of heap management, casting, pointer arithmetic, and debugging strategies:
hl_init
and hl_alloc
. Notice that
casting the heapptr
to a heap_header_t *
is
a straight forward and very readable way to set and access the fields
of the otherwise unspecified heap. (Aside: Casting can be a very
helpful way to peek at memory. Want to know whether a machine is
little or big endian? Write a number into an integer, create a pointer
to the integer, cast the pointer to a char *
and
dereference it. Now you're looking at the byte of the integer in
memory at the lowest address!)
print_heap
function. Although this function may be
incredibly useful to a programmer when implementing and debugging,
this is not the kind of information that should be printed to the
screen when some program includes and makes calls to
your heaplib.c
library. Novice programmers notoriously
litter their code with print statements that are commented in and out
as they code. This is not good form, especially since some straggling
printf
's almost always remain in the final version of the
code. This is particularly devastating when performance matters (which
it does for this assignment).
One solution to this problem is to create a variable such
as debug_mode_f
(_f
often indicates a
flag in C) and put the print statement inside an if
statement
that checks the variable:
if (print_debug_f) print_heap(heap);
This solution has the nice property that (if tied to a command line
option) the flag can be turned off and on each time you run the
program. The problem with this approach is that even your
"production-level" code will be littered with if
statements that always evaluate to false.
The code you have been given solves the problem by placing the print statement as the controlled text in a conditional group:
#ifdef PRINT_DEBUG print_heap(heap); #endif
The preprocessor (part of the compiler) will only insert the
controlled text if the PRINT_DEBUG
has been defined/set.
This Macro approach requires re-compiling in order to insert the
print statements. This may not be the best strategy for every
scenario, but it is for this assignment. Do not use any print
statements inside your heaplib.c
that are not wrapped in
an #ifdef
flag. Compiling and Running
Your Code discussed how to turn the flag on and off at compile
time.
// warning: this code is buggy int hl_init(void *heapptr, unsigned int heap_size) { heap_header_t *heap = (heap_header_t *)heapptr; heap->next_free = heap + sizeof(heap_header_t);This code initializes the
next_free
pointer to point to
the first free byte, which lives past the header. A careful programmer
will not assume to know the size of all types on any machine that
their code might run on. (There might not even be one right answer!)
Instead, we use sizeof
here. The code above, however, is
still flawed. Because heap
is of type heap_header_t
*
, adding some number to it, say 16, will actually move the
pointer forward "16 heap_header_t
s worth" (in other
words 16 x sizeof(heap_header_t)s
). Two correct versions
would be:
heap->next_free = heap + 1;(move ahead 1
heap_header_t
worth)
heap->next_free = (char *)heap + sizeof(heap_header_t);(temporarily cast
heap
to be a char *
so
that adding 16 just adds 16 char
s to the address.)
If you did not understand the problem in the above paragraph or why both solutions work, you are not ready to begin this assignment! Go brush up on your pointer arithmetic.
char *
. For readability, you may be tempted to create
short helper functions for these tasks. Knowing what you now know
about the overhead of a function call and knowing that your code will
be tested for speed, you should instead
use macros. A macro is a <keyword, definition>
pair. Any reference to the keyword will be replaced by the
definition at compile time. You may be familiar with simple macros such as
#define ALIGNMENT 8
which is a great way to rid your code of magic numbers. Macros can also be more complex, taking arguments. For example:
/* Useful shorthand: casts a pointer to a (char *) before adding */ #define ADD_BYTES(base_addr, num_bytes) (((char *)(base_addr)) + (num_bytes))We recommend using macros for any complicated but simple tasks; your code will be much more readable, maintainable, and debuggable at no performance cost.
sizeof()
throughout your
program. uintptr_t
in <stdint.h>
is
guaranteed to contain the size of pointer on the machine where the
executable is running. You may find this useful.
Student implementations of dynamic memory allocators are notoriously ugly and impossible to debug. Yours should not be. First, because you will make your own life a living hell. Second, because we will deduct style points for anything egregious. We have given you sample code with all sorts of tricks in it because these are tricks that expert programmers know about and use regularly. Now that you have been shown these techniques you will be expected to use them.
Cost of a ridiculously long project writeup? 15 minutes. Shedding your status as a novice and being able to produce code that is readable, debuggable, and super fast? Priceless.
Testing is a huge part of writing good code and will be a significant part of your grade for this assignment.
test_c.c
is intended to be a thorough test for the
correctness of any heaplib implementation. At the moment, however, it
only tests two things: whether hl_resize
actually copies
the data from the original block of memory to the resized block of
memory and whether the pointer returned by hl_alloc
is 8
byte aligned. There are many more correctness problems
in heaplib_naive.c
. Modify test_c.c
to catch
all of them.
The goal is to convince yourself that your code is
correct. Try to come up with a number of cases that really stress your
allocation functions. It's a good idea to test corner cases as
well. For example, create a test that uses two different
heap
pointers to two different chunks of memory. Make
sure that a user is never given permission to write past
the heap
associated with any allocation request. (Note: a
user could always write past the heap
, but if a user
requests 32 bytes and is given a pointer to the very last byte in
the heap
, this is a correctness problem. Similarly, a
user should never be given permission to write into memory that was
already reserved (and not freed) in a previous call
to hl_alloc
. Think about how you might test whether data
in a block is preserved over time.
You should maintain the structure of the program output:
When you have completed test_c.c
it should report all
the correctness problems with heaplib_naive.c
. You will
submit this file to CMS. This test will be graded on how thoroughly it
tests the correctness of yours and your fellow students'
implementations of heaplib_naive.c
. Points will be
deducted for false positives (finding errors where there are none) and
false negatives (not finding errors when they are there).
What is correctness? For the purposes of this assignment,
any error that would occur even in an infinite heap is considered a
correctness error. For example, not guaranteeing pointer alignment is
a correctness error. Not implementing hl_release
will be
considered a utilization error, not a correctness error.
A thorough correctness test will not only earn you points and glory, but it will be invaluable in finishing subsequent tasks for this assignment.
heaplib_naive.c
test_c
. Do not
change the definition of heap_header_t
. Do not create any
new typedefs. Once your fix is working, submit it on CMS.
Fixing the heap utilization problems (the orphaned memory
resulting from hl_resize
and hl_release
)
would require a significantly different approach than the naive
implementation. You will not be asked to fix this problem. Instead,
you will be asked to come up with a completely new approach to a
dynamic memory allocator--one that is robust enough to accomplish the
task.
We will try to give you early feedback about Task #1 and Task #2 sometime after Prelim 2. You will be allowed to re-submit these files based on this feedback. Exact dates and times to be announced later.
Your implementation will be graded based on correctness
first. Correct implmentations of heaplib.c
will then be evaluated on both memory utilization
and throughput. (Incorrect implementations will not be tested
for utilization and throughput--and will forgo the points associated
with these tests--because these metrics are meaningless in the context
of an incorrect program. By the metrics we will introduce, the
original (incorrect) version of heaplib_naive.c
has
fantastic utilization and throughput!)
Utilization. When a heap is initialized, it is given a fixed memory area that it can use to fulfill allocation requests. (Note: the actual heap on a real system can grow as needed within the virtual address space of the process. The fixed-sized heap in this assignment is an artificial but simplifying restriction.) Some of this area will be used up by meta-data: information about the memory area, the size of each block, whether it is free, etc. etc. The standard approach to heap management (which our naive implementation did not do!) is to give each block its own header, indicating its size and whether it is free or allocated. This would support freeing a previously allocated block. (Notice the tradeoff: each block requires meta-data, but for this, you gain the ability to reuse free blocks...)
On the one hand, you want to minimize meta-data. On the other hand,
some of this meta data will support a more careful heap management
(careful allocation, free, and resize strategies). Ultimately, we will
judge your utilization via "size tasks" (which measure how large a
heap is required to fulfill a series of calls
to heaplib
). You will be asked to write one such "size
task" for
Task #4.
Throughput. Another important aspect of your design will be
how quickly your library completes the jobs associated with
allocating, freeing, and resizing memory. Different approaches may
improve throughput but require meta-data that might reduce
utilization. You will have to consider these tradeoffs when designing
your approach knowing that both metrics will part of your grade. We
will judge your throughput via "speed tasks" (which measure the
execution time of a series of calls to heaplib
). You will
be asked to write one such "speed task" for Task
#5.
You will have a lot of design choices to make that create a tradeoff between heap utilization and throughput. Here are just a few:
Implicit vs. Explicit Lists. One design choice you will have is whether the list of free and allocated blocks that you maintain is an implicit list or an explicit list. In an implicit list, the size field is enough to help you find the next block. All blocks (both free and allocated) will be in the same list. In an explicit list, pointers determine which block comes next. Now you can have the blocks in any order. This strategy support multiple lists, doubly linked lists, ordered lists, and even trees.
Allocation Strategies. Think about the pros and cons of some common allocation strategies. A first-fit approach always gives the user the first memory block in the region that is big enough to fulfill the request. This provides the fastest response time, but is not necessarily the most space-efficient use of your memory region. A best-fit approach gives the user the smallest memory block that fulfills the request. The allocator will not be as quick because it might search the entire list to find this smallest block, but this is a more efficient use of space. You might be able to speed up this search by maintaining pointers to free memory blocks of certain sizes. You will have to decide whether these efficiency techniques are worth the space overhead that they require.
Fragmentation. After responding to many calls
to hl_alloc
and hl_release
the heap could
become chopped up into small interwoven blocks of allocated and freed
memory. When your memory region becomes fragmented, the sum of
the free blocks of memory might satisfy an hl_alloc
request, but since they are not contiguous, the request will
fail. Whether you implement a first-fit or best-fit
allocation strategy is just one way in which you control the
fragmentation of your memory region. You should also think about how
your implementations of hl_release
and
hl_resize
play a role in your ability to avoid
fragmentation and satisfy future allocation requests.
heaplib.c
.
Remember that you are not allowed to change the interface to any of
the library functions. Any changes you make to heaplib.h
will be ignored when we grade your code. (CMS will not even
accept heaplib.h
as part of your submission.) Remember
that correctness is your first priority.
As you implement your ideas, you should regularly
run test_c
to catch any correctness problems. Catching
bugs as they appear is much easier than catching them all at once at
the end! You may discover that you need to add more test cases to
your test_c.c
file. Remember to test the specs of the
assignment and not the invariants of your specific
approach. For example, if you implement a balanced tree, you might be
tempted to add a test in test_c.c
that checks to see
whether your tree remains balanced at all times. A test like this
should be in an implementation-specific heap consistency checker, not
a "did you follow the specs of the library" correctness test. You are
encouraged but not required to create a consistency checker and you
could easily add something like this to the
general-purpose heaptest.c
which you have been given.
test_u.c
tests your code for utilization by determining approximately how much
memory a heaplib
implementation requires in order to
complete a particular task. A well-managed heap will require less
memory than a poorly managed heap.
You will be asked to create a "size task" that is the body of the
function pass_sizetask()
in sizetask.c
. You
will define a task whose space requirements will set different heap
implementations apart from others: a badly-utilized heap would require
significantly more space than than a well-utilized heap. The best test
would produce a wide spectrum of heap requirements. If every
implementation requires the same amount of space, your test will not
be an effective measure of heap utilization. You may want to try to
judge space management at both a meta-data level and a block-handling
level. The choice is yours, however. (The given function, for example,
might highlight differences in size of headers, but it doesn't address
whether freed blocks can be coalesced, reused, etc.). It is up to you
to determine what you think a good test of utilization will be.
Note: you may have arbitrary numbers in this task, but you should
still avoid "magic numbers". Notice that the code currently
in pass_sizetask()
(which you should replace with your
own test) does several things 64 times. Some of those 64's are
independent (ITERS vs. REQ_SIZE), and some are "linked" (multiple uses
of ITERS). If instead of using the #define ITERS, we had just used the
number 64 in multiple places, changing one of those 64s would
break the code. Well-written code supports bug-free updates.
test_t.c
tests your code for throughput by performing a series of calls to
allocate, resize, and free memory blocks. A well-written library
will be able to service these requests quickly, although the absolute fastest
library likely compromises memory utilization.
You will be asked to create a "speed task" that is the body of the
function standalone_speedtask()
in speedtask.c
. You will define a task whose approximate
space requirements are known up front and available (to the caller who
must first set up the heap for the task) via the
function get_heap_size()
. Since you won't know the
meta-data requirements of each library that will be tested with this
"speed task", the heap estimate should be on the generous side.
The program test_t
will set up a block of memory for
the speed task, start a timer, and then
call standalone_speedtask()
with a pointer to that block
of memory. When the speed task is finished test_t
stops
the timer. It will then compute a throughput of operations per
clock. You must complete the function get_num_ops()
with
the correct number of operations that your speed task requires. The
calculation will not make a distinction between the operations (alloc,
release, or resize), so it's a good idea to use a large number of all
three since some library implementations may have quite unbalanced
runtimes between these three functions. It would also be appropriate
to run the speed test multiple times and take an average, although the
program test_t
which you are given does not. A good test
will produce a large spectrum of runtimes across various library
implementations. The more informative your test is when running it on
everyone's code, the more points you will receive. It is up to you to
determine what you think a good test of throughput would be.
Note: At a minimum, your test should run long enough
that gprof
is able to produce meaningful timing results
(see Task #6 ). Your test must be less than 5
seconds in length or we will not be able to run it as part of our
Leaderboard creation.
Hopefully your dynamic memory allocation library was written with
careful attention to speed. This task will allow you to profile your
code and potentially improve your throughput score by finding out
exactly where your code spends most of its time. For this task, you
will make a version of your executable that has been modified to
support profiling. You will use a program called gprof
which will repeatedly interrupt the execution of your executable and
make a note of which function the executable is currently in. With
enough samples, it will report to you the amount of time your
executable is spending in each of its functions.
Note: In Task #7 you will be asked to
report on this task and how you improved the performance of your code
in response to profiling it. The way to prove that your code got
faster based on your profiling and code optimization efforts is
to show before and after test_t
results. So the process is as follows:
test_t
and keep a copy of the results.
make prof
test_t
:
./test_tThis will run the executable and generate the file
gmon.out
. Now run gprof:
gprof test_tto see where you code is spending its time. Note: if your speed task is not long enough, gprof will not be able to gather timing information. At the top of the output you will see "no accumulated time". Go make your speed task longer and try again. (Remember to rerun
test_t
(Step 1) if you change it.
test_t
(not compiled for profiling!) again. You now have a "before" and "after" version to report on in the next step.
This is an exercise to show that you know how to both profile your code and measure the effects of your improvements. Full credit will be given to anyone who successfully follows these steps even if you are unable to make a remarkable leap in performance. We don't want your arbitrarily making your slow up front, and we know you can't always squeeze blood from a stone.
You will upload a pdf to CMS with the following components:
gdb
, the GNU debugger, helpful while
completing this assignment. (Tutorials can be found
on unknown
road).
heaplib_naive.c
and then type make
and then ./heaptest
it may look as though your change
did nothing. In fact, you should have typed make naive
and the change in your code was simply not incorporated into your
executable. This is just one example of the ways in which you may
occasionally confuse yourself. Take a step back and ask
yourself What am I compiling? What am I running?
Coming soon!
teamname.txt
: 1-line file containing your Team
Name, to be used to identify you on the Leaderboard. The team name
can consist of alphanumerics only plus _ (underscore) or - (hyphen)
but no other symbols. It cannot start or end with a symbol, and must
have no more than 32 characters. Should your teamname not follow
these rules, the 3410 TAs are more than happy to create a team name
for you.
heaplib_naive.c
heaplib.c
test_c.c
sizetask.c
speedtask.c
presentation.pdf
: a pdf version of your final presentation
Coming soon!