CPSC 1430 Programming and Problem Solving IIProgramming Assignment #5: “Typed Arena Allocator”This assignment focuses on linked lists and memory concepts.Project LoreYou have decided to leave your job...

CPSC 1430 Programming and Problem Solving II

Programming Assignment #5: “Typed Arena Allocator”

This assignment focuses on linked lists and memory concepts.

Project Lore

You have decided to leave your job at
Silly Little Games
, but first you want to work on a project that will look good on your resume. You hear that a division of the company wants a typed arena allocator for an upcoming project, and decide to take on the task.

Typed Arena Allocators

Anallocatoris a module which provides an interface for allocating and deallocating memory. Generally speaking, a call to one of an allocator's allocation functions returns a pointer to storage that will not be returned by any other allocation function until a pointer to that storage is passed to one of the allocator's free functions. For example, the standard allocator provided by C has the allocation function
malloc
and the freeing function
free
.

Atyped allocatoris an allocator that only allocates storage for a specific type. In other words, the pointers returned by its allocating functions only ever identify storage meant for a specific type of data.

Anarena allocatoris an allocator that only allocates storage held within a pre-allocated range of memory called anarena. All pointers returned by its allocating functions only ever identify storage that exists within this arena.

Hence, atyped arena allocatoris an allocator that only returns pointers to storage meant for one type of data, and that storage must only exist in a pre-allocated range of memory.

With these restrictions, it is relatively straightforward to implement a memory allocator. Because all storage from such an allocator must be from a predetermined pool of storage and with a predetermined type,it can be served from array where each element contains that associated type.

Implementation Requirements

This project requires the implementation of five types, all of which should be defined inallocator.h, with the associated methods defined inallocator.cpp.

1. 
   Three classes, respectively called
   outOfMemory
   ,
outOfBounds
, and
   doubleFree
   . While these classes must be defined, all that is required is that they can be constructed, destructed, and thrown as errors. An empty definition block for these classes should suffice.
   


2. 
   A struct called
link
, which stores an instance of a pre-defined type called
item
, as well as a
   link*
   which is used to join together
   link
   instances into a linked list.Theitemmembermustbe the first member declared in this struct.You can add additional members to this struct, if you like.
   
   
   
   
   


3. 
   A class called
arenaAllocator
, which serves as atyped arena allocatorfor the type
item
, using an array of type
link
as an arena, and alinked listto represent which link's items are not currently allocated.
   

1. 
   
   
   
   1. 
      Members:
      
      
      • 
        
bool safety
: represents whether or not memory safety checks occur for allocation and deallocation operations
      
      
      • 
        
link* arenaPointer
: identifies the arena (array) which the
arenaAllocator
instance serves storage from. This arena should be allocated during the construction of the owning instance and deleted only on the destruction of the instance.
      
      
      • 
        
link* head
: identifies the head of the linked list which contains all links in the arena
      
      
      • More members may be added, butALL data members must be private.
      
      
      
      
      
   
   
   2. 
      Methods:
      
      
      
      
      • 
        
void setSafety()
: sets the value of the member
safety

        
      
      
      • 
        
        bool inBounds(item*)
        : returns
true
if and only if the input identifies storage in the arena (this one is given to you for free - look below).
      
      
      • 
        
item* alloc()
: removes a link from the instance's free list and returns a pointer to its item member. If the free list is empty, the method's behavior depends upon the value of
safety
:
        
        
        • if
safety
is
true
, then an instance of
outOfMemory
is thrown
        
        
        • if
safety
is
false
, then
nullptr
is returned.
        
        
        
        
      
      
      • 
        
void free(item*)
: adds the link containing the identified item to the instance's free list. If the input points outside of the arena or if the input is already free, the method's behavior depends upon the value of safety:
        
        
        
        
        • if
safety
is
true
, then an instance of
outOfBounds
is thrown if the input points outside of the arena and an instance of
doubleFree
is thrown if the input is already free
        
        
        • if
safety
is
false
, then checks for out-of-bounds errors and double-frees do not occur, and no errors are thrown.
        
        
        
        
      
      
      • 
        
arenaAllocator(int size)
: constructs an
arenaAllocator
instance with an arena of capacity
size
and
safety
set to
false

        
      
      
      • 
        
~arenaAllocator()
: destructs an
arenaAllocator
instance, freeing the arena used to serve its allocations. If safety is
true
, the destructing instance should print the addresses of any items that were not freed at the moment of destruction.
      
      
      • More methods may be added, butthe methods listed above must be public.
      
      
      
      
      
   
   
   
   

For the purposes of checking that your code properly compiles upon submission, a test driver must be submitted alongside this class code in a file namedp5.cpp.This driver code will NOT be tested against buggy allocator implementations, but I will provide partial credit to submissions which fail to implement allocator requirements and which catch those failures with a well-designed unit test.

Additionally, a file nameditem.h
should be submitted alongsidep5.cpp,allocator.h, andallocator.cpp. This file must define an
item
type that works with the submitted allocator and test driver code.

Useful Pointer Arithmetic

The fact that
item
is the first member of
link
is very important. If a struct/class doesn't use any advanced OOP features, the C++ standard guarantees that the first member of a struct has the same address as the struct itself. Hence, we can directly cast between pointers to links and pointers to the contained items:

struct link{
item data;
link* next;
};
item* linkToItem(link* theLink){
return (item*) theLink;
}
link* itemToLink(item* theItem)
{
return (link*) theItem;
}

You should use this property when converting between
link*
and
item*
for the
alloc
and
free
methods.

For checking if a pointer identifies storage in an array, you should use
std::less
and
std::greater

to determine the address's position relative to the array bounds. This is because the normal inequality operators don't work 100% correct if the input points outside of the arena. Since this is very non-obvious, below is an implementation you can use for
inBounds
.

// be sure to #include 
bool arenaAllocator::inBounds(item* thePointer)
{
bool afterEnd  = std::greater{}(thePointer, (arenaPtr+size));
bool beforeStart = std::less{}(thePointer, arenaPtr   );
return ! ( afterEnd || beforeStart );
}

Getting Started

An initial version ofitem.handp5.cppis available to help get you started. You can copy it to your current directory on the cs1 server using the following command:

cp /home/fac/bcuneo/class/cs1430/p5/* .

The test driver code in this initial version of p5.cpp is not comprehensive, but it should detect most errors in your allocation/deallocation logic.

Testing for Memory Bugs

The program
valgrind
can tell if another program has leaks memory or performs improper memory accesses.

You can testp4by running the commandvalgrind --leak-check=full ./p5. The program will behave normally until it finishes, at which point
valgrind
will print diagnostic information about how your P5 executable used memory.

Your program has no memory leaks if
valgrind
prints the messageAll heap blocks were freed -- no leaks are possible.

If other memory errors occurred during execution,
valgrind
will report them to you as they occur.

Building the Project

This program must build with a Makefile.

To use a Makefile, place it in your project directory (with the file nameMakefile) and runmake. A default Makefile is provided with the starter code (see above). You may edit the Makefile, if you choose.

The content of this Makefile should look like the block below. If you copy/paste from this block, ensure that the indentation is still a single tab character after pasting.

Makefile Contents:

p5: p5.cpp allocator.o item.h
g++ p5.cpp allocator.o -std=c++11 -Wall -g -o p5
allocator.o: allocator.h allocator.cpp item.h
g++ allocator.cpp    -std=c++11 -Wall -g -c

Submitting the Project

The source code files must be namedMakefile,p5.cpp, allocator.h,allocator.cpp, and item.h.