| Deadline |
Tuesday, December 5, 11:59pm Extensions are not given for Bonus Questions |
| Name on Marmoset | BQ3 |
| To Submit |
alloc.cc
|
| Bonus Points | Up to +0.25% on your final grade |
This question is about writing a dynamic memory allocator for int arrays in C++.
(Racket is not an option for this question
because the implementation requires working with
memory at a low level.)
You will write two C++ functions called New
(which implements the functionality of new int[n])
and Delete (which implements the functionality of delete [] a;).
To help Marmoset test your allocator, we impose an unusual requirement on New.
Instead of returning a pointer to the allocated block, it returns an integer offset, which
can be added to the starting address of the heap to get a pointer to the allocated block.
For a failed allocation, it returns a negative integer (instead of a null pointer).
This is mainly to ensure your implementation of New does not simply call an existing memory allocation routine
like the C++ new operator or malloc.
Normally we allow you to use whatever C++ features and libraries you want, but there are some restrictions for this question.
Your implementation file
Your allocator is not required to produce output, so it is optional to include these libraries, but they can be used for
debugging purposes.
Debugging information must either be printed to standard error, or removed from your file before you submit,
so the debugging output does not get mixed in with the output produced by Marmoset's test programs.
The restriction on
Do not use preprocessor macros (Restriction Information
alloc.cc
should not #include
any libraries or files except for:
<string>
<iostream> (C++ style I/O)
<cstdio> (C style I/O, in case you prefer it to C++ stream I/O)
#include also counts files you create yourself. You should write your entire implementation alloc.cc rather than splitting it across multiple files.
#define). This could interfere with the test programs Marmoset uses.
We recommend you use the free list algorithm discussed in the notes and lectures
(the version with variable-size blocks, a sorted free list, and merging) and that you adopt the following conventions.
Conventions for the Free List Algorithm
int beyond what the user requested.int values in the block (not the number of bytes as in the notes). The first slot itself is included in this count.int values and make things more awkward.
int elements stored in the first slot,
and a negative number stored in the second slot.New should return the offset of the second slot in the block
to the user (because the first slot is reserved by the allocator).Delete,
it will be the address of the second slot, and your allocator must account for this.
We provide a code template and a debugging utility, which are both written with the assumption you will use the free list algorithm with the above conventions (see the "Code Template" and "Testing Your Allocator" sections below).
However, other reasonable algorithms (e.g. binary buddy system) should be able to pass the Marmoset tests if you want to try implementing a different algorithm.
In addition to declarations for
The
Use the location and size information to set up the initial state of the heap
and any necessary variables. For example, you should store the
If using the free list algorithm with the recommended conventions, you should also do the following in New and Delete, you must write a function called Init
which contains the initialization logic for your allocator. Marmoset uses this function to tell your program the
location and size of the heap that you should use for allocation.
Initialization Details
Init function has signature void Init(int *heapStart, int heapSize).
Each main program that Marmoset uses will start by initializing a large int array.
Before making any calls to New or Delete, Marmoset will call Init and pass a pointer to the int array as the first parameter, and
pass the number of elements in the array as the second parameter. Marmoset will only call Init once.
heapStart pointer in a global variable
so that your implementations of New and Delete can refer to it.
Init:
heapStart.
heapSize at heapStart[0], and store a negative value in heapStart[1]
(indicating the end of the free list).
This means the free list will start out containing a single block of size heapSize.
The test programs used by Marmoset will always provide a heap of size 2,410,000 (i.e., the heap contains
2,410,000 slots and each slot holds a single int). The reason for passing the heap size as a parameter
is so you can do your own testing with smaller heaps if you want.
Download the following template file: alloc.cc
Regardless of whether you implement the free list algorithm or some other algorithm,
you must use the exact function names and signatures provided
in this file, or the programs used by Marmoset will not be able to call
upon your allocator.
You can rename the parameters if you'd like,
but the function names, sequences of parameter types, and return value types must be the same.
The
The
The Functions Provided By The Template
Init function has signature void Init(int *heapStart, int heapSize).
As explained above, Marmoset will call the Init function exactly one time,
before any calls to New or Delete, and pass the location
and size of the heap as parameters.
New function has signature int New(int n).
The parameter n is the number of elements
in the int array that should be allocated.
It should return an integer offset (relative to the start of the heap) representing
the location of the allocated array.
Delete function has signature void Delete(int *addr).
The parameter addr is either
the address of
a block that should be deleted, or a null pointer. If it is a null pointer, Delete should do nothing. Otherwise,
it should delete the allocated block, allowing it to be reused by future calls to New.
We provide two files to help you test your allocator:
New and Delete commands and prints a representation of the heap after each command.
Compile these files together with alloc.cc. For example:
g++ -g -std=c++17 alloc.cc simple.cc -o simple
g++ -g -std=c++17 alloc.cc debug.cc -o debug
The
The
If you are not implementing the free list algorithm, you could perhaps use this as a starting point to write your
own debugging tool.
Here is a sample session
of debug.cc program provides a simple interface for interactively testing your allocator.
Using
debug.cc
n size to allocate a block of size size. For example, n 241 will
call New(241) attempt to allocate a block of 241 int values.
The index/offset returned by New
will be displayed (or if the allocation failed, a message saying so will be displayed).d index to delete the block at index/offset index from the start of the
heap. The index must be one that was returned by an earlier n command and has not already been deleted.
For example, if n 241 allocated a block successfully and returned index 15, then d 15 will
delete that block.
[ ] and free blocks indicated by curly braces { }.
debug.cc program assumes you are implementing the free list algorithm
and are following the specific implementation conventions we listed earlier.
If you implemented the free list algorithm differently, you may have to modify
the functions in debug.cc.
debug.cc
with a small heap of size 241.
Note that the test programs on Marmoset will use a much larger heap (size 2,410,000).
The default heap size used by debug.cc is 2,410,000, but this can be changed
if you find it easier to debug with a small heap.
./debug
{0:241 NULL}
<<< n 1
allocated block index: 1
[0:2]{2:239 NULL}
<<< n 16
allocated block index: 3
[0:2][2:17]{19:222 NULL}
<<< n 200
allocated block index: 20
[0:2][2:17][19:201]{220:21 NULL}
<<< n 20
allocated block index: 221
[0:2][2:17][19:201][220:21]
<<< d 3
[0:2]{2:17 NULL}[19:201][220:21]
<<< d 221
[0:2]{2:17 220}[19:201]{220:21 NULL}
<<< d 1
{0:19 220}[19:201]{220:21 NULL}
<<< d 20
{0:241 NULL}
Test your allocator with different block sizes and pay attention to the arrangement of free and allocated blocks, and the links between free blocks that form the free list. Some things to watch out for: