CMSC313, Computer Organization & Assembly Language Programming, Spring 2013

Project 5: DIY Memory Allocation

Due: Tuesday April 2, 2013, 11:59pm

Objective

Background

A simple way to achieve this do-it-yourself memory allocation is to declare a "large" global array of blocks. Each time your program needs a block of memory, you use an item of the array instead of asking the operating system for a chunk of memory. You keep track of a list of free blocks in your array by linking the unused items together in a linked list.

You do not need to create a new data structure to link the free blocks together: simply reuse one of the fields of the array item as the "next" pointer. You also do not need to use real pointers to link the free blocks together, you can just use the array index of the next item in the list of free blocks. Thus, you can simply reuse any integer field as the "next pointer". When your program deallocates a block of memory, that block is added to the linked list of free blocks. The beginning of the free block list will be stored in a global variable. Initially, the list of free blocks is the entire array.

If your memory allocations needs are modest, doing your own memory allocation can be faster than making calls to library functions.

Assignment

Note: This project description deliberately avoids using C syntax. This is so you figure out how to look up the syntax of various elements of the C programming language.

For this assignment, you will work with structs that represent fractions. The struct must have fields called sign, numerator and denominator. These should be, respectively, signed char, unsigned int and unsigned int. You must use typedef and struct to define a fraction type.

Your memory allocator should use a "large" global array of fractions. This must be defined in a separate file along with another global variable for the beginning of the free block list. Both the global variables should be declared static to give them file scope and ensure that code in other files does not access these variables directly.

In the same file, you must supply four functions: init_Heap(), new_frac(), del_frac() and dump_heap().

• init_Heap() must be called once by the program using your functions before calls to any other functions are made. This allows you to set up any housekeeping needed for your memory allocator. For example, this is when you can initialize your linked list of free blocks.

• new_frac() must return a pointer to fraction. This must be the address of an item in your global array of fractions. It should be an item taken from the list of free blocks. (Don't forget to remove it from the list of free blocks!)

• del_frac() takes a pointer to fraction and adds that item to the free block list. The programmer using your functions promises to never use that item again, unless the item is given to her/him by a subsequent call to new_frac().

• dump_heap() is for debugging/diagnostic purposes. It should print out the entire contents of the global array and the head of the free block list. This allows you to see how your memory allocator is working.

You must also supply a header file called frac_heap.h. Any program that includes frac_heap.h should be able to use your memory allocator without any additional declarations or definitions.

You should make your declarations and definitions compatible with this sample main program: main5.c. The main program should compile with your code without any modification. You should infer the correct function prototypes of the four functions listed above from how they are used in the main program.

In addition to this sample main program, you should write several main programs that test various features of your memory allocator.

Implementation Notes

• You must allocate memory from your global array. You are not allowed to use malloc(), calloc(), free() or any variation thereof.

• Please name the file that has the memory allocator functions frac_heap.c and name your test files: test1.c, test2.c, test3.c, ...

• Make sure that your test programs fully exercise your memory allocation functions. The program main5.c does not.

• You should use a constant for the size of your global array.

• For readability, zero out the sign and numerator fields when del_frac() is called. That way, when you dump out the array, it is more obvious which items of the array are free. This is assuming that you are using the denominator field for linking the free block list.

• You should not have any extra fields in fraction. You should just have sign, numerator and denominator.

• When you link the free blocks together, use the index of the item in the array for linking, not its address. For example, if item #18 follows item #13 in the free blocks list, then you should store the number 18 in the denominator field of item #13. Since denominator is an unsigned integer, the compiler will not complain. If you tried to store a pointer in the denominator field, it will be a type mismatch error. (Yes, you can force the compiler to do this by type casting, but let's not start your first C program by telling the compiler to ignore types.)

• [Added 2013-03-26 12:13]  You cannot use 0 to indicate the end of the free blocks list, since 0 is a perfectly fine index for the first item in the global array. What can you use instead?

• Your del_frac() function receives a pointer parameter, but you really want to know the index of the array item that corresponds to that pointer. (So, you can use it for linking in the free blocks list.) Pointer arithmetic saves the day. If we have the declarations: int A[20], *p1, *p2, i ; then after the statements: p1 = &A[0] ; p2 = &A[15] ; i = p2 - p1 ; the variable i will have the value 15. You can think of this as a case where "pointer algebra" works, since the statements p1 = &A[0] ; i = 15 ; p2 = p1 + i; will make p2 point to A[15]. If we "solved" for i, we would get i = p2 - p1 ;

• Your del_frac() function should do some error checking and make sure that the pointer passed to it is actually pointing to an item in your global array and not some random place in memory.

• Here is a sample output from the sample main program: main5.txt. Your output does not have to look identical to this, but it gives you an idea of what should happen when you run the program.

Extra Credit (10 points)

For extra credit, devise a scheme that allows the programmer to request an array of fractions. The interaction should look like this:

In the example above, your new_frac_array() function should allocate a contiguous block of 10 items from the global array and return a pointer to the beginning of the contiguous block. Note that F is a pointer that can be used as an array of fractions. It is not an array of pointers each pointing to a fraction. Your new_frac_array() function may have to do some searching to find such a contiguous block.

Deallocating an array of fractions requires some work, because you are only given a pointer and not the size of the array. For this scheme to work, you memory allocator must keep track of the size of the arrays you have allocated previously. In the example above, when F is deallocated, your del_frac_array() function has to figure out that F was an array of 10 fractions. To do this, you will need a separate global table to remember the sizes of the arrays allocated previously. You are allowed to devise whatever scheme suits you. You do not have to be terribly efficient (that's difficult), but you are not allowed to add additional fields to fraction and you be graded on the amount of extra memory used (less is better).

Turning in your program

Use the UNIX submit command on the GL system to turn in your project. You must submit the header file frac_heap.h, the implementation frac_heap.c and your test programs test1.c, test2.c, ...

In addition, submit a typescript file showing that your test programs compiled and ran.

You may optionally submit a README file explaining anything the graders might need to know about compiling and/or running your programs.

Your submit commands will look like:

submit cs313 proj5 frac_heap.h frac_heap.c
submit cs313 proj5 test1.c test2.c test3.c test4.c test5.c test6.c
submit cs313 proj5 typescript README