Please read the C Programming book, Chapter 8.7, A Storage Allocator. In this chapter, you can see the traditional C implementation of malloc() and free().
If you never use pointers in C, please read the C programming book. Specifically, go to the index page and find "pointer", "struct", and "struct, pointer". You will manipulate struct-pointers a lot! Hence, you need to be an expert in manipulating pointers. In addition, you might want to read the C notes again, part 2 in particular.
The idea of this project is you are given a chunk of memory to manage (this chunk of memory is returned by mmap()). To manage this chunk of memory, you must have internal data structures (e.g. list of free blocks). The rule is to store your internal structures within the given memory. In other words, in your mem.c file, you should only have one global pointer which points to the base address of the given memory. If your design requires you to create global arrays, or you need to call malloc(), it implies your design is wrong!
Please download this ppt slides [or in pdf] for some illustrations of free space management.
int *p = 2000; // set p to point to address 2000
p = p + 2; // p now will point to address 2008
// because the compiler knows p is a pointer
// to an integer (4 bytes). Hence, addition
// of 2 will actually give 2 x 4 bytes
int *q = 2000; // set q to point to address 2000
q = ((void*)q) + 2; // q now points to address 2002
// because we have casted q to void*
// Hence, addition of 2 will give 2
x = [requested size (and has been rounded up to 4-byte alignment) ]
y = [size of this free block]
if ( y < x + sizeof(object_header) )
the requested area (x) does not fit here
if ( y == x + sizeof(object_header) )
this free block fits exactly the requested size + header
converts this free block into an object block
if ( y > x + sizeof(object_header) ) {
left_over = y - x - sizeof(object_header);
if ( left_over >= sizeof(free_header) )
create a new smaller free block in the left over area
if ( left_over < sizeof(free_header) )
you have two choices:
1. take the left over area and add it to x
then convert this free block into an object block
OR
2. return error
}
void *ptr = Mem_Alloc(100);
ret = Mem_Free(ptr); // ok
ret = Mem_Free(ptr); // should fail
In the discussion last time, we have talked about how you should add a
constant "magic number" in each header of allocated region (let's name
this the object header). The magic number is used in this way:
If not tested thoroughly, it is highly possible that your code is buggy. For example: there is a hole (lost space) between a free block and an object block, object block and free block are overlapping each other, a pointer points to an address outside the valid memory region, etc.
To test your code, you should create your own tests (e.g. alloc and free hundred and thousand times). We will also provide your some test files. However, if your program fails, these test files are not sufficient to pinpoint where the problem is. Hence, we suggest you to create a meta-compiler in your library to help you debug complex program such as this project.
A meta-compiler is a specific compiler that verifies your program behavior; gcc is a compiler, but it does not know the high-level intent of your program. On the hand, a meta-compiler "knows" the high-level intent of your program.
In this project, your program is supposedly to manage the memory correctly. What does "correct" mean? How do you check correctness? The answer is you need to rewrite the specification from English to C code. Below is a list of some specifications that your program should adhere to. You can add more if you think of any.
if (free_header < object_header)
if (free_header + free_header->size > object_header)
ERROR! return -1, and print a descriptive error message here
if (...)
// more possibilities here (add them yourself)
if (free_header + free_header->size == free_header->next)
ERROR!
// Assume this free_header is not the last block in the
// memory region, then I expect the neighboring block to be
// an object block. If not, there is a gap.
object_header = free_header + free_header->size;
if (object_header->magic_number != YOUR_MAGIC_NUMBER)
// ERROR!
Iterate all free headers
if (free_header->next >= base + sizeOfRegion)
ERROR!
if (free_header + free_header->size >= base + sizeOfRegion)
ERROR!
Iterate all object headers
if (object_header + sizeof(object_header) + object_header->size >=
base + sizeOfRegion)
ERROR!
The basic idea here, if your code is complex and buggy, there could be hundreds possibilities of error. By writing your own meta-compiler, you could pinpoint which specific error you should be dealing with. Without a meta-compiler, you will be guessing what the problem is. The more checks you put in your meta-compiler, the more error information you can get. Think more of what checks you should add. These checks often depend on your specific implementation.
How should you implement the meta-compiler? Simply create a Mem_Check() function in your library code. Remember that in your library, you should be able to access all information that you need. Mem_Check() simply peruses that information to find where the problem is. We will not grade your Mem_Check() implementation; it is simply for your own benefit. You can call Mem_Check() anywhere in your test file. Here is an example:
int main() {
Mem_Init(someSize);
// some tests here (say testA)
Mem_Check(); // if no error is printed,
// then you pass testA
// some tests here (say testB)
Mem_Check(); // if no error is printed,
// then you pass testB
// some tests here (say testC)
Mem_Check(); // if some errors are printed here,
// then you know you fail testC,
// plus you will know what the problem is
}