Project 2 - Memory Allocation

Objectives:

Throughly understand memory allocation, i.e., malloc() and free()
Use pointers

Background

void* malloc( size_t size ) tries to allocate a chunk of memory of size bytes (on the heap).
void free( void* ptr ) expects as an argument an address returned from malloc(). It unassigns or releases that chunk of memory. If ptr is NULL, no operation is performed.

Assignment

Create a project2.c file and write the implementations of malloc(), free(), along with heapInit() and printFreeList() (as specified in project2.h). Use project2-main.c as a driver for your code. Match the format of the output in the examples when displaying the Free List (with printFreeList()). Use the Free List structure specified in Chapter 17 Free Space Management.
Your program needs to be able to compile using the following:

gcc *.c

You can assume 1) that the heap will be initialized with a value greater or equal to 16 and 2) that all calls to malloc() will request a size evenly divisible by the word size for the host system. Do not (permanently) change the code in either project2.h or project2-main.c. Do not define any global or static compound data structures such as arrays, structs, trees, or lists in your project2.c. However, you are allowed to declare global scalar variables such as integers, doubles, pointers and simple structs in project2.c.

Examples

Using no command-line arguments:

gcc project2-main.c project2.c -o project2
./project2

stdout: project2-answerKey0.txt

Free List:
Free chunk at 0x100000000 (size: 112, next: 0x0)

Free List:
Free chunk at 0x100000000 (size: 80, next: 0x0)

Free List:
Free chunk at 0x100000060 (size: 16, next: 0x100000000)
Free chunk at 0x100000000 (size: 80, next: 0x0)

Free List:
Free chunk at 0x100000060 (size: 16, next: 0x100000000)
Free chunk at 0x100000000 (size: 80, next: 0x0)

Free List:
Free chunk at 0x100000060 (size: 16, next: 0x100000000)
Free chunk at 0x100000000 (size: 8, next: 0x0)


ALERT: malloc( 72 ) returned NULL!

Free List:
Free chunk at 0x100000060 (size: 16, next: 0x100000000)
Free chunk at 0x100000000 (size: 8, next: 0x0)

Free List:
Free chunk at 0x100000060 (size: 0, next: 0x100000000)
Free chunk at 0x100000000 (size: 8, next: 0x0)

Free List:
Free chunk at 0x100000070 (size: 0, next: 0x100000060)
Free chunk at 0x100000060 (size: 0, next: 0x100000000)
Free chunk at 0x100000000 (size: 8, next: 0x0)

Free List:
Free chunk at 0x100000070 (size: 0, next: 0x100000060)
Free chunk at 0x100000060 (size: 0, next: 0x100000000)
Free chunk at 0x100000000 (size: 8, next: 0x0)

Free List:
Free chunk at 0x100000018 (size: 56, next: 0x100000070)
Free chunk at 0x100000070 (size: 0, next: 0x100000060)
Free chunk at 0x100000060 (size: 0, next: 0x100000000)
Free chunk at 0x100000000 (size: 8, next: 0x0)

Using 112 and -2 for the command-line arguments:

gcc project2-main.c project2.c -o project2
./project2 112 -2

stdout: project2-answerKey112_-2.txt

Free List:
Free chunk at 0x100000000 (size: 96, next: 0x0)

Free List:
Free chunk at 0x100000000 (size: 64, next: 0x0)

Free List:
Free chunk at 0x100000000 (size: 32, next: 0x0)

Free List:
Free chunk at 0x100000000 (size: 0, next: 0x0)


ALERT: malloc( 24 ) returned NULL!

Free List:
Free chunk at 0x100000000 (size: 0, next: 0x0)

Free List:
Free chunk at 0x100000050 (size: 16, next: 0x100000000)
Free chunk at 0x100000000 (size: 0, next: 0x0)

Free List:
Free chunk at 0x100000030 (size: 16, next: 0x100000050)
Free chunk at 0x100000050 (size: 16, next: 0x100000000)
Free chunk at 0x100000000 (size: 0, next: 0x0)

Free List:
Free chunk at 0x100000010 (size: 16, next: 0x100000030)
Free chunk at 0x100000030 (size: 16, next: 0x100000050)
Free chunk at 0x100000050 (size: 16, next: 0x100000000)
Free chunk at 0x100000000 (size: 0, next: 0x0)

Also try using 1048576 and 0 for the command-line arguments:

gcc project2-main.c project2.c -o project2
./project2 1048576 0

Hints

Before you write any code, answer the following questions:
- How do you know how much memory to free given just a pointer?
- How do you keep track of the free blocks?
- What do you do with the extra space when allocating memory that is smaller than the free block it is placed in?
- How do you pick a block to use for allocation?
Before writing any code, make sure that you can correctly split a memory chunk. Write out on paper what the value should be before coding.
During initial development, using no command-line arguments (or project2-cmdline0.txt) and make sure it matches the example exactly (except that each time it's probably going to pick a different starting location for the heap, so just make sure that values are relative to that)
Compile with gcc -g and use a debugger. A debugger will help you isolate and identify out of bounds memory references.
Understand the implementation in Chapter 17 Free Space Management. Re-read it before coding!
Do your implementation in stages. Start with initializing the heap, then implementing the printFreeList() function (creating stubs for malloc() and free()). Test it. Then, add your implementation of malloc(). After test that, then, add in your implementation of free().
Start early!

Rubric:

Points       Item
----------   --------------------------------------------------------------
_____ /  0   Program compiles without errors
_____ / 10   Documentation
             Header comment block at the beginning of each file with:
             + Your full name
             + Date(s) code was written
             + Description
             Comments explaining the role of each variable and major section of code
             
             Correctness - Program solves the assigned problem using methods described in program description
_____ / 15   Initializing the heap
_____ / 10   Displaying the Free List
_____ / 25   malloc() (including returning NULL when out of memory)
_____ / 25   free() (including NULL as an argument)
_____ /  0   Program executes without crashing
_____ /  2   Completed rubric (estimates for each line including hours spent)

_____ / 87   Total


_____  Approximate number of hours spent

Submission

Before submitting this assignment, make sure there are no compilation errors. If there are, fix them before submitting. You may need to edit and compile your program multiple times before it compiles successfully. Verify that the output is correct. Once you are able to successfully run the program with the correct output, you are ready to submit the program. Make a gzipped tarball (.tgz) of the following files: project2.c, project2.h, project2-main.c and rubric-yourlastname.txt. You can make the tarball with the following command:

tar -czf project2.tgz project2.c project2.h project2-main.c rubric-yourlastname.txt

Submit your tarball to the Assignments tab in CougarVIEW. (Note: Do not submit files with spaces in their names.)

Notes

If you want to match the output exactly, download the linked files into the same directory as the executable then run the following in a terminal window:
```
gcc  project2-main.c project2.c  -lm  -o project2
./project2  > output.txt
perl project2-postScript.pl '' '' output.txt project2-answerKey0.txt
```
The second line, where we're running the executable project2, uses the contents of the project2-cmdline0.txt for the command-line arguments. Additionally, we're also redirecting stdout with the ">" symbol to go to output.txt (instead of the screen). This allows us to run it without having to type anything. The third line changes the contents of output.txt by adjusting all of the addresses so that it can be compared with the answer key. It then calls diff on your adjusted output file and the answer key. If the two files match exactly (which is what you want) then the .pl script just displays your output (but not output from diff). If diff shows one or more differences, fix them and run it again. For details about interpreting the output of diff, see the Using diff section on the Misc. webpage. Also, for the second example:
```
gcc  project2-main.c project2.c  -lm  -o project2
./project2  112 -2  > output.txt
perl project2-postScript.pl '' '' output.txt project2-answerKey112_-2.txt
```

Questions and Answers

In the heapInit() function, do you want us to use malloc() from [the libc] library to allocate a big chunk of memory for initializing the heap? Or you want us to use some data structures like array and list to represent the heap?
For this project, do not make any calls to malloc() (outside of those in project2-main.c. This is especially true of heapInit(), because it will be called to initialize things for future calls to malloc(). The textbook details a system call to make in the Embedding A Free List sub-section.
For the address, how do we make sure the starting address is 0x100000000 for the heap?
Don't worry about getting the address to be 0x100000000. I wrote a perl script to shift all of the reported addresses to make the comparisons easier. You're welcome :)
In my output, it prints out "(nil)", and I used "%p" for printing addresses. How do I make it prints out like "0x0"?
Don't worry about it. I'll compile it on my system, which will produce 0x0.
Thank you for "writing the Perl script to shift all of the reported addresses". However, is any way that I check if my shifted addresses are correct?
The perl script changes the contents of the output file and then runs diff on the changed file. You can do the same after running the .pl file with:
```
perl project2-postScript.pl '' '' output.txt project2-answerKey0.txt
diff -w project2-answerKey0.txt  project2-answerKey0.txt
```
I'm getting a seg fault. What's a good way to figure out why?
You have two main options:
1. gdb. It's the debugger for UNIX.
2. Systematically compare your output to a benchmark. For this project, compare it against the answer keys. Notice the first place that your output diverges from the answer key. Tackle that problem first. Repeat.
When I do math with an address, the values I'm getting are 8 (or 16) times larger (or smaller) than what I need. Why?
The following code takes a node_t pointer and adds size * sizeof(node_t) to it:
```
int size = 100;
node_t* curr = head;
printf( "%x\n", curr + size );
```
C is helping you out by doing pointer arithmetic. C assumes that if you're going to do math with a data type, that you intend to do that in increments of the size of that data type. This is usually true, but not for this project. To get 100 bytes added to the current address, you need tell C to treat curr as a generic pointer by casting it as a void* first:
```
printf( "%x\n", (void*)curr + size );
```

Optional (submitting working copy via CougarVIEW, then email these solutions directly to me):

Implement Best Fit, Worst Fit, and/or Binary Buddy allocation.
Implement a tree (or other data structure) for your Free List
Explain why the assumptions above simplify this project
Coalesce available memory chunks as appropriate

Operating Systems

CPSC 3125