Compilation and Linking

Q) Why do we have to #include mymalloc.h and why do we need the function declarations inside it? A) As we learned, the compiler needs to know the prototype for functions to know how to generate code for the calls to that function. The prototype tells the compiler the types and number of arguments and also the type of the return value so that it can reserve the appropriate space on the stack. So you've got to declare the prototype somewhere. You can do it directly at the top of your .c source file, or you can do it at a .h header file and then include it in your .c file. The header file is usually more preferred since then, you can include that header file in any .c file that uses the set of declared functions. Your .h file should contain the following declarations at the least:

void *my_malloc(int size); void my_free(void *ptr);

This file should be included in mallocdrv.c in the given location at the top of the file.

Q) When I link my two .c files with "gcc mallocdrv.c mymalloc.c" I get errors that say:

/tmp/cctd8fGM.o: In function `my_free': mymalloc.c:(.text+0x249): multiple definition of `my_free' /tmp/ccfpkm11.o:mallocdrv.c:(.text+0x249): first defined here

What does this mean?

A) Apparently you included 'mymalloc.c' inside 'mallocdrv.c' instead of 'mymalloc.h'. As we've learned, the #include directive would cause the preprocessor to copy and paste whatever was in that file into the location of the include. So essentially, if you had 'my_free' defined in 'mymalloc.c', you will have it defined again in 'mallocdrv.c'. As you can imagine, this is going to cause a problem with the linker because now it has the same symbol defined twice in two .o files and it does not know which address to associate with the symbol, hence the error.

Malloc Test Driver

Q) How do I know that my output is correct for the mallocdrv.c test driver?

A) Before you modify mallocdrv.c, it uses the standard C library malloc. So without you doing any modifications, if you compile mallocdrv.c as is, it will generate a certain output A. You are asked to modify the MALLOC and FREE macros in mallocdrv.c so that it uses the my_malloc that you provide. After doing the modification, it will generate a certain output B. Output A should equal to output B, since the output of a program should remain identical no matter what allocator you use. Identical with a few qualifications:

1) 'test1' prints out the numbers from 1 to 100 in random order, and the order changes at every run. So as long as B prints out all 100 numbers in whatever order reliably, you can consider that to be identical to A.

2) 'test2' prints out the numbers in sorted order, but this time the numbers themselves are generated randomly. So as long as B prints out a set of numbers between 1 to 100, in sorted order, you are good.

3) The addresses of brk may be different, due to differences in the size of the executable image, after which the heap starts. However, the *size* of the heap (the difference between original brk and current brk) should be identical with the sample output.

The tests are written to apply pressure on your allocator as much as possible, including the randomness, and are not particularly good for debugging your code. For debugging, you probably want to use a tester where the output does not differ on every run. If you really want to use mallocdrv.c for debugging, it is a good idea to comment out the line with 'srand((unsigned int)time(NULL));'. That will at least give you a deterministic set of outputs at every run, since not seeding the pseudo random number generator with the current time means you will get the exact set of pseudo random numbers at every run.

Debugging Your Allocator

Q) Why does my program keep getting SEGFAULTS when I'm pretty sure the program is algorithmically correct?

A) Try running on GDB and printing the address of the pointer that is giving you the segfault (before you do this remember that you have to give gcc the '-g' option to include debug symbols in the binary). If the address is within the heap range (between original brk and current brk), there is no reason you would get a segfault since those pages have been mapped already. It is because the address somehow escaped that range. One common reason for this happening is sloppy pointer arithmetic. If you declare Node *temp; and you do temp + size, you are not adding size bytes to temp as you think you are doing. Remember in pointer arithmetic, +1 is equal to the size of the base type in bytes. So if you do temp + 1, instead of going 1 byte further, you are going sizeof(Node) bytes further. This is one important reason for pointers to have base types, if you remember from the lecture. So you should really be doing (char*)temp + size to get byte offsets.

Q) At some point I get the feeling one of the blocks is getting messed up (e.g. a block has an incorrect size). What do I do?

A) Try calling dump_heap() each time the heap is modified and locate where things went wrong.