Machine Problem 1: A Simple Memory Allocator Solution

Introduction

In this machine problem, you are to develop a simple memory allocator that implements the functions my malloc() and my free(), very similarly to the UNIX calls malloc() and free(). (Let’s assume that { for whatever reason { you are unhappy with the memory allocator provided by the system.) The objectives of this Machine Problem are

Package a simple module with some static data as a separately compiled unit.

Become deeply familiar with pointer management and array management in the C language (or C++ for that matter).

Become familiar with standard methods for handling command-line arguments in a C/UNIX environment.

Become familiar with simple UNIX development tools (compiler, make, debugger, object le inspector, etc.)

Background: Kernel Memory Management. The kernel manages the physical memory both for itself and for the system and user processes. The memory occupied by the kernel code and its data is reserved and is never used for any other purpose. Other physical memory may be used as frames for virtual memory, for bu er caches, and so on. Most of this memory must be allocated and de-allocated dynamically, and an infrastructure must be in place to keep track of which physical memory is in use, and by whom.

Ideally, physical memory should look like a single, contiguous segment from which an allocator can take memory portions and return them. This is not the case in most systems. Rather, di erent segments of physical memory have di erent properties. For example, DMA may not be able to address physical memory above 16MB. Similarly, the system may contain more physical memory than what can be directly addressed, and the segments above need to be handled using appropriate memory space extension mechanisms. For all these reasons, many operating systems (for example Linux) partition the memory into so-called zones, and treat each zone separately for allocation purposes. Memory allocation requests typically come with a list of zones that can be used to satisfy the request. For example, a particular request may be preferably satis ed from the \normal" zone. If that fails, from the high-memory zone that needs special access mechanisms. Only if that fails too, the allocation may attempt to allocation from the DMA zone.

Within each zone, many systems (for example Linux) use a buddy-system allocator to allocate and free physical memory. This is what you will be providing in this machine problem (for a single zone, and of course not at physical memory level).

Your Assignment. You are to implement a C module (.h and .c les) that realizes a memory allocator as de ned by the following le my allocator.h:


#ifndef _MY_ALLOCATOR_H_

#define _MY_ALLOCATOR_H_

/* File: my_allocator.h */

typedef void * Addr;

unsigned int init_allocator(unsigned int _basic_block_size, unsigned int _length);


Ver 2017C    Page 1
CPSC{313    Machine Problem 1


/* This function initializes the memory allocator and makes a portion of ’_length’ bytes available. The allocator uses a ’_basic_block_size’ as its minimal unit of allocation. The function returns the amount of

memory made available to the allocator. If an error occurred, it returns 0. */

int release_allocator();

/* This function returns any allocated memory to the operating system.

After this function is called, any allocation fails. */

Addr my_malloc(unsigned int _length) {};

/* Allocate _length number of bytes of free memory and returns the address of the allocated portion. Returns 0 when out of memory. */

int my_free(Addr _a) {};

/* Frees the section of physical memory previously allocated using ’my_malloc’. Returns 0 if everything ok. */

#endif

You are to provide the implementation of the memory allocator in form of the le my allocator.c. The memory allocator you are supposed to implement is based on the so-called \Buddy-System" scheme. (A description of this scheme is given in Section 9.8.1 of the Silbershatz et al. textbook. A more detailed description is given in Section 2.5 of D. Knuth, \The Art of Computer Programming. Volume 1 / Fundamental Algorithms". We give a short overview below.)


Buddy-System Memory Allocation:

In our buddy-system memory allocator, memory block sizes are a power of two, starting at the basic block size. For example, if 9kB of memory are requested, the allocator returns 16kB, and 7kB goes wasted { this is called fragmentation. This restriction on allowable block sizes makes the management of free memory blocks very easy: The allocator keeps an array of free lists, one for each allowable block size. Every request is rounded up to the next allowable size, and the corresponding free list is checked. If there is an entry in the free list, this entry is simply used and deleted from the free list.

If the free list is empty (i.e. there are no free memory blocks of this size,) a larger block is selected (using the free list of some larger block size) and split. Whenever a free memory block is split in two, one block gets either used or further split, and the other { its buddy { is added to its corresponding free list.

Example: In the example above, there is no 16kB block available (i.e. the free list for 16kB is empty). The same holds for 32kB blocks. The next-size available block is of size 64kB. The allocator therefore selects a block, say B, of size 64kB (after deleting it from the free list). It then splits B into two blocks, BL and BR of 32kB each. Block BR is added to the 32kB free list. Block BL is further split into BLL and BLR of size 16 kB each. Block BLL is returned by the request, while BLR is added to the 16kB free list.
In this example, the blocks BL and BR are buddies, as are BLL and BLR.

Whenever a memory block is freed, it may be coalesced with its buddy: If the buddy is free as well, the two buddies can be combined to form a single memory block of twice the size of each buddy.
Example: Assume that BLL and BR are free, and that we are just freeing BLR. In this case, BLL and BLR can be coalesced into the single block BL. We therefore delete BLL from its free list

Ver 2017C    Page 2
CPSC{313    Machine Problem 1


and proceed to insert the newly formed BL into its free list. Before we do that, we check with its buddy BR. In this example, BR is free, which allows for BL and BR to be coalesced in turn, to form the 64kB block B. In this process, Block BR is removed from its free list and the newly-formed block B is added to the 64kB free list.

Finding Buddies: The buddy system performs two operations on (free) memory blocks, splitting and coalescing. Whenever we split a free memory block of size 2s with start address A, we generate two buddies: one with start address A, and the other with start address A with the (s 1)th bit ipped.

Finding the buddy of a block being freed is just as simple when the size of the block is known: The address of the buddy block is determined by ipping the appropriate bit of the block’s start address, just as is the case when we split a block. The problem is: How to get hold of the block size? The easy way is to explicitly store it at the beginning of the allocated block, as part of a header. This wastes memory. Alternatively, the size can be implicitly infered from other data, typically stored in the free list. For example, Linux uses a buddy bitmap for each free list. In this bitmap, each bit represents two adjacent blocks of the same size. The bit is \0" if both the blocks are either full or free, and is \1" if exactly one block is free and the other is allocated. By comparing these bits for increasing block sizes we can infer the current block size. This is also not pretty, as the sizes of the bitmaps depends on the amount of memory available.

Managing the Free List: You want to minimize the amount of space needed to manage the Free List. For example, you do not want to implement the lists using traditional means, i.e. with dynamically-created elements that are connected with pointers. An easy solution is to use the free memory blocks themselves to store the free-list data. For example, the rst bytes of each free memory block would contain the pointer to the previous and to the next free memory block of the same size. The pointers to the rst and last block in each free list can easily be stored in an array of pointers, two for each allowable block size.

Note on Block Size: If you decide to put management information into allocated blocks (e.g. the size, as described above), you have to be careful about how this may a ect the size of the allocated block. For example, when you allocate a block of size 5, and add an 8-word header to the block, you are actually allocating a 5 blocks +8 Word, which requires a block of size 8! (This is extremely wasteful.)

Where does my allocator get the memory from? Inside the initializer you will be allocating the required amount of memory from the run time system, using the malloc() command. Don’t forget to free this memory when you release the allocator.

What does my malloc() return? In the case above, putting the management information block in front of the the allocated memory block is as good a place as any. In this case make sure that your my malloc() routine returns the address of the allocated block, not the address of the management info block.


Initializing the Free List and the Free Blocks: You are given the size of the available memory as argument to the init() method. The given memory size is likely not a power-of-two multiple of basic blocks. You are to partition the memory into a sequence of power-of-two sized blocks and initialize the blocks and the free list accordingly.


Ver 2017C    Page 3
CPSC{313    Machine Problem 1


The Assignment

You are to implement a buddy-system memory manager that allocates memory in blocks with sizes that are power-of-two multiples of a basic block size. The basic block size is given as an argument when the allocator is initialized.

The memory allocator shall be implemented as a C module my allocator, which consists of a header le my allocator.h and my allocator.c. (A copy of the header le and a rudimentary preliminary version of the .c le are provided.)

Evaluate the correctness (up to some point) and the performance of your allocator. For this you will be given the source code of a function with a strange implementation of a highly-recursive function (called Ackermann function). In this implementation of the Ackermann function, random blocks of memory are allocated and de-allocated sometime later, generating a large combination of di erent allocation patterns. The Ackerman function is provided in form of two les, i.e., the header le ackerman.h with the interface de nition of the ackerman function, and the implementation in le ackerman.c.

You will write a program called memtest, which reads the basic block size and the memory size (in bytes) from the command line, initializes the memory, and then calls the Ackermann function. It measures the time it takes to perform the number of memory operations. Make sure that the program exits cleanly if aborted (using atexit() to install the exit handler.)

Use the getopt() C library function to parse the command line for arguments. The synopsis of the memtest program is of the form



memtest [-b <blocksize>] [-s <memsize>]

-b <blocksize> defines the block size, in bytes. Default is 128 bytes.

-s <memsize>    defines the size of the memory to be allocated, in bytes. Default is 512kB.

Repeatedly invoke the Ackerman function with increasingly larger numbers of values for n and m (be careful to keep n 3; the processing time increases very steeply for larger numbers of n). Identify at least one point that you may modify in the simple buddy system described above to improve the performance, and argue why it would improve performance.

Make sure that the allocator gets de-allocated (and its memory freed) when the program either exits or aborts (for example, when the user presses Ctrl-C). Use the atexit library function for this.

Submission Process

This machine problem will be submitted using three milestones, where for each milestone you submit an improved version of your allocator. You will start with a simple but silly allocator in Milestone 1 and end with a fully functioning Fibonacci-Buddy-System allocator in Milestone 3. This is just an overview. More details about each of the three milestones will be given in the lab!


Ver 2017C    Page 4
CPSC{313    Machine Problem 1


Milestone 1 - Salami Allocator: In this warm-up submission you will write a totally trivial al-locator: The function init allocator() reserves a given portion of memory for the allocator. Every call to my malloc() cuts o the requested amount of memory from the remainder of the reserved memory. The call to my free() does not free any memory. When all the memory has been used, and no more memory is left, subsequent calls to my malloc() return NULL. For the implementation all you need is a pointer to the beginning of the remaining memory. Whenever memory is allocated, advance the pointer, until you reach the end. This allocator is a good start for what follows.


Milestone 2 - Single-Freelist Allocator: Once you get your brain wrapped around pointers and the general structure of allocators, we can proceed to a more sophisticated allocator, which allocates and frees memory using a single free list. The call to init allocator() reserves the memory and initializes a free list of segments of length blocksize (a parameter to init allocator(). Initially, all blocks are free and are therefore linked up in the free list. Calls to my malloc() allocate one block (i.e. at most blocksize bytes) and remove it from the free list. Calls to my free() return the memory by adding the block back to the free list.


For this you need a set of function to manipulate free lists and blocks in free lists. These functions are to be de ned in a module called free list, which consists of les free list.h and free list.c. The header le should look similar to the following:



typedef struct fl_header { /* header for block in free list */ /* put stuff here */

} FL_HEADER; /* I don’t like to type ’struct’ all the time, so */ /* I like to typedef it away... */

void FL_remove(FL_HEADER * free_list, FL_HEADER * block);

/*    Remove the given block from given free list. The free-list pointer points to the first block in the free list. Depending on your implementation you may not need the free-list pointer.*/

void FL_add(FL_HEADER * free_list, FL_HEADER * block); /* Add a block to the free list. */

Internally, the free list should be implemented as a doubly-linked list of block headers. The implementation of the free list will be discussed more in detail in the lab.

Milestone 3 - Full- edged Fibonacci Buddy System Allocator In this milestone you add

    (1) support for multiple free lists (one for each supported Fibonacci number size, (2) splitting of blocks into smaller blocks, and (3) coalescing of small free blocks into larger free blocks. As a result, you will have a full- edged Fibonacci Buddy System Allocator.

What to Hand In, for each Milestone

You are to hand in at least three  les, with names my allocator.h

and my allocator.c, which de ne and implement your memory allocator, and memtest.c, which implements the main program. For Milestone 2 and Milestone 3 you also have to submit the two les free list.h and free list.c. For Milestone 3 you may have additional les to submit. [(The header file my allocator.h will likely not change from the provided file. If you need to change it, give a compelling reason in the modified source code.)]




Ver 2017C    Page 5
CPSC{313    Machine Problem 1


Only for Milestone 3: In addition to the source code, hand in a le (called analysis.pdf, in PDF format) with the analysis of the e ects on the performance of the system:

{ Repeat the experiments for increasing numbers of allocate/free operations. Vary this number by varying the parameters a and b in the Ackerman function.

{ Determine where the bottlenecks are in the system, or where poor implementation is a ecting performance.

{ Identify at least one point that you would modify in this simple implementation to improve performance. Argue why it would improve performance.

The complete analysis can be made in 500 words or less, and one or two graphs. Make sure that the analysis le contains your name.

Grading of these MPs is a very tedious chore. These hand-in instructions are meant to mitigate the di culty of grading, and to ensure that the grader does not overlook any of your e orts.

Failure to follow the handing instructions will result in lost points.

Submission and Grading of Machine Problems with multiple Milestones

Submission of Milestones: Each milestone must be submitted separately by its given deadline.

Late-submission penalties apply for each milestone separately.

Credit for Milestones: In general, you have to submit all milestones of the machine problem in order to get full credit. Each milestone will give you partial credit.


































Ver 2017C    Page 6