Operating System Assignment

In this assignment, you will write a heap allocator implement a version of malloc and free. However, you must work in the XUbuntu virtual machine for some of the provided code to run.

the mymalloc.c file is where to get started. It has some helper functions and placeholders for the two functions you will implement in this assignment. You can (and should) write other helper functions as necessary.

Description

The my_malloc function will be used to request memory from the heap. It is a user level function (not part of the kernel). The function returns a logical (virtual) address. The my_free function is used to return a block of memory to the allocator. The function takes as argument an address (one returned by my_malloc). To understand how each function is required to behave, keep reading.

void *my_malloc(uint32_t size); void my_free(void *p);

Buddy allocator

The memory allocator you will implement is based on the Buddy algorithm. In this algorithm, the allocator keeps track of memory blocks of size 20, 21, 22, ..., 2MAX_ORDER bytes inside the heap (the part of memory area in the logical address space of a process right after the program code and data). It does this using MAX_ORDER+1 different linked lists. A memory block of size 2n bytes is called an order n block, and the corresponding linked list is called the order n free list. The free_list_start pointers array holds the address of the first memory block of various sizes.

uint32_t *free_list_start[MAX_ORDER+1];

For example, consider the free_list_start[3] pointer. This pointer will point to an address where a memory block of 23 bytes (8 bytes) is available. The first four bytes of that memory block will have information on whether another order 3 block is present. If yes, then the start address of that block will be stored here; otherwise NULL (the C macro) will be stored. This process will repeat as long as there are order 3 blocks present, thereby resulting in a linked list. The blocks must always be arranged in ascending order of their start addresses. See picture below for an illustration.

When a program begins, all free_list_start pointers are set to NULL, since the heap begins at size zero. During memory allocation, my_malloc can use the grow_heap function to request the operating system to allocate some space (4096 bytes for each call) in the heap. More details on when this should be done is given later.

Another rule that the Buddy allocator enforces: the start address of an order k block of memory will always have to be a multiple of 2k. For example, in the picture, the order 3 memory blocks starting at 0x82541008 and the one at 0x82541010 together form a contiguous memory area of 16 bytes; however, they together do not form an order 4 memory block since 0x82541008 is not a multiple of 24.

Implementing my_malloc

The first step in my_malloc is to increase the amount of needed memory by 4 bytes (reason coming up). Therefore, the amount of memory bytes allocated to serve a request is always at least (size+4). The Buddy allocator always allocates memory in size of powers of 2. Therefore, we need to determine the smallest n such that an order n block can serve the request. This can be calculated as

n = (int)ceil(log2(size+4));

The allocation algorithm for the Buddy allocator then proceeds as follows.

If free_list_start[n] is not NULL, delete the first order n memory block from the list.

Store n in the first 4 bytes of that block, and return (4 + start address of the block).

Otherwise, move to the free list of the next higher order and check if it is NULL. Keep doing this until you find one that is not NULL. In case you reach the maximum order (MAX_ORDER) and the free list there is still empty, then you can call grow_heap to receive a 4KB (212 bytes, order 12) memory block. Add this block to the order 12 free list and continue.

Lets say free_list_start[p] is not NULL. Of course, p>n.

delete the first order p memory block from the list; say the start address of that block is s.

add two order (p-1) memory blocks to the order (p-1) free list. The first of the two blocks will begin at address s and the second one will begin at address (s + 2p-1). Remember, the list must be kept in ascending order of the start addresses.

Essentially, you have split a larger chunk of memory into two smaller ones of equal sizes.

Repeat from step 1.

As an example, the following figures show the before and after versions of few of the free lists (order 3, 4, 5) when my_malloc(4) is called. Note that the way the implementation is sought here implies that each my_malloc call should not be for more than 4092 bytes. There are ways to handle this, but is not needed in this assignment.

Order 3, 4 and 5 free lists before calling my_malloc(4)

Order 3, 4 and 5 free lists after calling my_malloc(4)

Implementing my_free

The first step in my_free is to determine how much memory is to be freed. The function takes as input a memory address returned by my_malloc in an earlier call. Since my_malloc stores the order of the memory block allocated, we can use it to determine how much memory is being returned. If p is the start address of the returned area of memory, then the 4 bytes beginning at f=(p-4) has the order (say n). Therefore, we need to insert back an order n memory block beginning at address f into the order n free list. The deallocation algorithm is as follows.

Add the order n block starting at f to the order n free list. Remember, the list must be kept in ascending order of the start addresses.

If n , check whether

the added block and the next (or previous) block in the list together represent a

contiguous memory region, and

the smaller of the two start addresses of the two blocks is a multiple of 2n+1.

If any of the above two conditions is not true, return; otherwise, continue.

The two blocks can be merged and entered into a higher order list.

let f = the smaller of the start addresses of the two blocks.

remove the two blocks from the order n free list.

letn=n+1.

Repeat from step 1 with the updated n and f values.

Therefore, the my_free function returns memory blocks to the free lists, and coalesces contiguous blocks to higher order blocks whenever possible. Note that my_free does not return memory back to the operating system (decrement the heap top). As a program calls my_malloc and my_free, the same heap region gets allocated in different sizes over the life of the program. Since the two functions are running in user space, this reduces the number of system calls that user programs will have to make to request heap memory. The following figure shows an example of my_free.

Order 3, 4 and 5 free lists before calling my_free

Order 3, 4 and 5 free lists after calling my_free

Objective

Use the mymalloc.c file. The file has the grow_heap function and some helper functions to print the free lists and return values. Your objective is to complete the implementation of the my_malloc and my_free functions as per the specifications. The main function is for testing purposes only; what you write in this function will be discarded before grading. The output generated by the provided main function is given in the last page. Some interesting cases that you should test:

malloc such that no splitting is necessary

malloc such that splitting will be necessary; check the case when splitting initiates multiple

levels down

free such that merging happens with the next block in the list

free such that merging happens with the previous block in the list

malloc and free such that merging does not happen

malloc and free such that merging propagates down more than one level

other interesting pointer related errors!!

You can compile the program in the terminal using

gcc -o mymalloc mymalloc.c -lm

and run it using ./mymalloc

sample output:

0x4 0x14 0x24 0x34 0x44 0x54 0x64 0x74 0x4 0x44 

mymalloc.c File:

//

// mymalloc.c

// Name:

//

#include

#include

#include

#include

#include

#define MAX_ORDER 12

#define PAGE_SIZE 0x1000

typedef unsigned long long uint64_t;

typedef unsigned uint32_t;

typedef unsigned short uint16_t;

typedef unsigned char uint8_t;

// function prototypes

void print_ra(void *);

void print_ran(void *);

void print(uint32_t *);

void printAll();

void *grow_heap();

void *my_malloc(uint32_t);

void my_free(void *);

uint32_t *free_list_start[MAX_ORDER+1]; // the free list pointers for different orders

void *start_brk; // the heap start address (set in main())

//////////////////////////////

/* Print address relative to heap start (start_brk)*/

void print_ra(void *a) {

a = (void *)((uint32_t)a-(uint32_t)start_brk);

printf("0x%x",(uint32_t)a);

}

//////////////////////////////

/* Print address relative to heap start (start_brk) with newline*/

void print_ran(void *a) {

print_ra(a);

printf(" ");

}

//////////////////////////////

/* Print a free list*/

void print(uint32_t *pointer) {

if (pointer == NULL)

printf("Empty list. ");

else {

print_ra(pointer);

for (pointer=(uint32_t *)(*pointer); pointer!=NULL; pointer=(uint32_t *)(*pointer)) {

printf("\t");

print_ra(pointer);

}

printf(" ");

}

}

//////////////////////////////

/* Print all free lists*/

void printAll() {

int i;

for (i=0; i

printf("%d:\t",i);

print(free_list_start[i]);

}

}

//////////////////////////////

/* Increment heap top (brk) by one page

Output: NULL if failure; otherwise the old heap top

Meaning: if the function returns a non-NULL value, then

all logical addresses from to

( + PAGE_SIZE - 1) are now usable

*/

void *grow_heap() {

return sbrk(PAGE_SIZE); // tell Linux to increment heap top

}

///////////////////////////////////////////////////////////

/* Allocate memory using Buddy algorithm

Input: amount of requested memory

Output: the beginning address of requested memory, or

NULL if not able to allocate (heap cannot grow anymore)

*/

void *my_malloc(uint32_t size) {

if (size == 0) return NULL;

int n = (int)ceil(log2(size+4)); // order; 4 more bytes to store order

if (n > MAX_ORDER) return NULL;

// TODO: implement as per requirements

}

///////////////////////////////////////////////////////////

/* Deallocate memory using Buddy algorithm

Input: pointer received from my_malloc

*/

void my_free(void *ptr) {

// TODO: implement as per requirements

}

///////////////////////////////////////////////////////////

/* Change this function only for testing. No functionality

should reside in this function; the GTA will use his own

main function.

*/

int main(int argc, char *argv[])

{

int i;

start_brk = sbrk(0); // get heap start address

// initialize all free lists to NULL

for (i=0; i

void *ptr1 = my_malloc(8); print_ran(ptr1);

void *ptr2 = my_malloc(8); print_ran(ptr2);

void *ptr3 = my_malloc(8); print_ran(ptr3);

void *ptr4 = my_malloc(8); print_ran(ptr4);

void *ptr5 = my_malloc(8); print_ran(ptr5);

void *ptr6 = my_malloc(8); print_ran(ptr6);

void *ptr7 = my_malloc(8); print_ran(ptr7);

void *ptr8 = my_malloc(8); print_ran(ptr8);

my_free(ptr3);

my_free(ptr5);

my_free(ptr2);

my_free(ptr1);

my_free(ptr4);

void *ptr9 = my_malloc(48); print_ran(ptr9);

void *ptr10 = my_malloc(8); print_ran(ptr10);

return 0;

}

free list start[3] 0x82520000 0x82520000 0x82541008 8 bytes 0x82541008 0x82541010 8 bytes 0x82541010 NULL 8 bytes free list start[3] 0x82520000 0x82520000 0x82541008 8 bytes 0x82541008 0x82541010 8 bytes 0x82541010 NULL 8 bytes