Program Specifications

For this project, you will be implementing several different routines as part of a shared library. Note that you will not be writing a main() routine for the code that you hand in (but you should implement one for your own testing). We have provided the prototypes for these functions in the file mem.h(whichisavailablefrommoodle);youshouldincludethisheaderfileinyourcodeto ensure that you are adhering to the specification exactly. You should not change mem.h in any way!

We now define each of these routines more precisely.

intMem_Init(intsize,intpolicy):Mem_Initiscalledonetimebya process using your routines. size is the number of bytes that you should request from the OS using mmap(). Note that you may need to round up this amount so that you request memory in units of the page size (see the man pages for getpagesize()). Note that you need to use this allocated memory for your own data structures as well; that is, your infrastructure for tracking the mapping from addresses to memory objects has to be placed in this region as well (its self-contained). policy indicates the method for managing the free list (either 0=first-fit, 1=best-fit=1, and 2=worst-fit) when choosing a chunk of memory for allocation. First-fit uses the first free chunk that is big enough; best-fit uses the smallest chunk that is big enough; and worst-fit uses the largest chunk.You must use mmap(). If you call malloc(), or any other related function, in any of your routines, we will deduct a significant number of points (e.g., 15 points). Similarly, you should not allocate global arrays! However, you may allocate a few global variables (e.g., a pointer to the head of your free list.) This function returns 0 if successful, or -1 if an error happens.

void*Mem_Alloc(intsize):Mem_Allocissimilartothelibraryfunctionmalloc(). Mem_Alloc takes as input the size in bytes of the object to be allocated and returns a pointer to the start of that object. The function returns NULL if there is not enough free space within memory region allocated by Mem_Init to satisfy this request. Free space is selected according to the policy specified by Mem_Init.

intMem_Free(void*ptr):Mem_Freefreesthememoryobjectthatptrfalls within, according to the rules described above. Just like with the standard free(), ifptr is NULL, then no operation is performed. The function returns 0 on success and -1 ifptr to does not fall within a currently allocated object (note that this includes the case where the object was already freed with Mem_Free).

intMem_IsValid(void*ptr):Thisfunctionreturns1ifptrfallswithinacurrently allocated object and 0 if it does not. You may find this function useful when debugging your memory allocator.

intMem_GetSize(void*ptr):Ifptrfallswithintherangeofacurrentlyallocated object, then this function returns the size in bytes of that object; otherwise, the function returns -1. You may find this function useful when debugging your memory allocator.

floatMem_GetFragmentation():Thisfunctionreturnsthefragmentationfactor, which is defined as the size of the largest free chunk divided by the total free memory. If the fragmentation factor is 1, it means theres no fragmentation (i.e., theres only one free chunk); if it is close to 0, the entire free memory is fragmented among small chunks. If theres no more free memory, this function returns 1.

You must provide these routines in a shared library named libmem.so. Placing the routines in a shared library instead of a simple object file makes it easier for other programmers to link with your code. There are further advantages to shared (dynamic) libraries over static libraries. When you link with a static library, the code for the entire library is merged with your object code to create your executable; if you link to many static libraries, your executable will be enormous. However, when you link to a shared library, the library's code is not merged with your program's object code; instead, a small amount of stub code is inserted into your object code and the stub

code finds and invokes the library code when you execute the program. Therefore, shared libraries have two advantages: they lead to smaller executables and they enable users to use the most recent version of the library at run-time.

To create a shared library named libmem.so, use the following commands (assuming your library code is in a single file mem.c):

gcc -c -fpic mem.c gcc -shared -o libmem.so mem.o

To link with this library, you simply specify the base name of the library with "-lmem" and the path to find the library "-L." (the current directory).

gcc mymain.c -lmem -L. -o myprogram

Of course, these commands should be placed in a Makefile.

Before you run "myprogram", you will need to set the environment variable,LD_LIBRARY_PATH, so that the system can find your library at run-time. Assuming you always run myprogram from this same directory, you can use the command:

setenv LD_LIBRARY_PATH ${LD_LIBRARY_PATH}:.

Unix Hints and Test Programs

We are providing you with a lot of flexibility in how you implement this project. In particular, you can choose any suitable data structure for tracking memory objects (i.e., mapping address ranges to the corresponding object). The place you don't have much flexibility is: you must usemmap() for allocating memory region on the heap for this process. In particular, you will usemmap() to map zero'd pages (i.e., allocate new pages) into the address space of the calling process. Note there are different ways that you can call mmap to achieve this same goal; we give one working example here. This example works for Linux:

// open the /dev/zero device int fd = open("/dev/zero", O_RDWR);

// size (in bytes) must be divisible by page size void *ptr = mmap(NULL, size, PROT_READ | PROT_WRITE,

MAP_PRIVATE, fd, 0); if (ptr == MAP_FAILED) {

perror("mmap");

return NULL; }

// close the device (don't worry, mapping should be unaffected)

close(fd); return ptr;

Its good to know that /dev/zero does not work on Mac OS, but one can addMAP_ANONYMOUS option. (Check man-page in this case.)

We will also provide you with a sample program (testmem.c available on moodle) to test your library so that you can test the basic functionalities of your memory allocator. Note that you should feel free to create your own test programs so that you can try different ways of using the memory allocator (e.g., different object sizes, different ordering for allocation and deallocation calls, and different pointers for freeing objects) and also with different policies. We will use our own program to test your library (which you dont have). So, test your code as thoroughly as possible before you submit the code.

/////tester.c/////

#include #include "mem.h"

#define REGION_SIZE (10*1024)

void* myalloc(int size) { printf("allocate memory of size=%d bytes...", size); void* p = Mem_Alloc(size); if(p) printf(" success (p=%p, f=%g) ", p, Mem_GetFragmentation()); else printf(" failed "); return p; }

void myfree(void* p) { printf("free memory at p=%p...", p); if(!Mem_Free(p)) printf(" success (f=%g) ", Mem_GetFragmentation()); else printf(" failed "); } int main(int argc, char* argv[]) { myalloc(1000);

printf("init memory allocator..."); if(Mem_Init(REGION_SIZE, MEM_POLICY_FIRSTFIT) < 0) { printf(" unable to initialize memory allocator! "); return -1; } else printf(" success! "); printf("init memory allocator, again..."); if(Mem_Init(REGION_SIZE, MEM_POLICY_FIRSTFIT) < 0) printf(" failed, but this is expected behavior! "); else { printf(" success, which means the program incorrectly handles duplicate init... "); return -1; }

void* x1 = myalloc(64); void* p1 = myalloc(200); void* x2 = myalloc(64); void* p2 = myalloc(100); void* x3 = myalloc(64); void* p3 = myalloc(100000); void* x4 = myalloc(64); void* p4 = myalloc(500); void* x5 = myalloc(64); myfree(p1); myfree(p1+10); myfree(p2+10); myfree(p3); void* p5 = myalloc(50); myfree(NULL); myfree(x1); myfree(x2); myfree(x3+10); myfree(x4); myfree(x5+10); myfree(p4); myfree(p5); return 0; }

/////mem.h

/* DO NOT CHANGE THIS FILE */

#ifndef MEM_H #define MEM_H

#define MEM_POLICY_FIRSTFIT 0 #define MEM_POLICY_BESTFIT 1 #define MEM_POLICY_WORSTFIT 2

/* This function is called one time by a process using Mem_* routines. size is the number of bytes that you should request from the OS using mmap(). Note that you may need to round up this amount so that you request memory in units of the page size (see the manpages for getpagesize()). Note that you need to use this allocated memory for your own data structures as well; that is, your infrastructure for tracking the mapping from addresses to memory objects has to be placed in this region as well (its self-contained). policy indicates the method for managing the free list (0 for first-fit, 1 for best-fit=1, and 2 for worst-fit) when choosing a chunk of memory for allocation. First-fit uses the first free chunk that is big enough; best-fit uses the smallest chunk that is big enough; and worst-fit uses the largest chunk. The function returns 0 if successful; otherwise, the function returns -1. */ int Mem_Init(int size, int policy);

/* This function is similar to the library function malloc(). Mem_Alloc takes as input the size in bytes of the object to be allocated and returns a pointer to the start of that object. The function returns NULL if there is not enough free space within memory region allocated by Mem_Init to satisfy this request. Free space is selected according to the policy specified by Mem_Init. */ void* Mem_Alloc(int size);

/* This function frees the memory object that ptr falls within. Just like with the standard free() , if ptr is NULL, then no operation is performed. The function returns 0 on success and -1 if ptr does not fall within a currently allocated object (note that this includes the case where the object was already freed with Mem_Free). */ int Mem_Free(void* ptr);

/* This function returns 1 if ptr falls within a currently allocated object and 0 if it does not. You may find this function useful when debugging your memory allocator. */ int Mem_IsValid(void* ptr);

/* If ptr falls within the range of a currently allocated object, then this function returns the size in bytes of that object; otherwise, the function returns -1. You may find this function useful when debugging your memory allocator. */ int Mem_GetSize(void* ptr);

/* This function returns the fragmentation factor, which is defined as the size of the largest free chunk divided by the total free memory. If the fragmentation factor is 1, it means theres no fragmentation (i.e., theres only one free chunk); if it is close to 0, the entire free memory is fragmented among small chunks. If theres no more free memory, this function returns 1. */ float Mem_GetFragmentation();

#endif /*MEM_H*/