You are expected to do your own work on all homework assignments. You may (and are encouraged to) engage in general discussions with your classmates regarding the assignments, but specific details of a solution, including the solution itself, must always be your own work. (See the statement of Academic Dishonesty on the Syllabus).
Assignments need to be turned in via Laulima. Check the Syllabus for the late assignment policy for the course.
You should turn in single plain text file named README.txt with your answers to the assignment’s questions. Your file must be readable “as is” and points will be removed if the report is not readable.
In this exercise we look at “reverse engineering” code to try to determine how the heap in a C program is managed. Consider the following C program (compiled as an executable called memory):
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
int chunk_sizes[4];
if ((argc != 2) ||
(sscanf(argv[1], "%d,%d,%d,%d", &chunk_sizes[0], &chunk_sizes[1], &chunk_sizes[2], &chunk_sizes[3]) != 4) ||
(chunk_sizes[0] < 0) || (chunk_sizes[1] < 0) || (chunk_sizes[2] < 0) || (chunk_sizes[3] < 0) ) {
fprintf(stderr,"Usage: %s < a , b, c, d>\n", argv[0]);
fprintf(stderr," where a, b, c, and d above must be >=0 integers (chunk sizes)\n");
exit(1);
}
char *ptrs[9];
unsigned long sizes[9] = {1024, 128, 1024, 512, 1024, 32, 1024, 64, 1024};
for (int i=0; i < 9; i++) {
ptrs[i] = (char *)calloc(sizes[i], sizeof(char));
printf("%ld | ", (unsigned long)(ptrs[i]));
}
printf("\n--------------\n");
for (int i=1; i < 9; i += 2) { // Note the +=2
free(ptrs[i]);
}
for (int i=0; i < 4; i++) {
if (chunk_sizes[i] > 0) {
char *chunk = (char *)calloc(chunk_sizes[i], sizeof(char));
printf("The %d-byte chunk was allocated at address %ld\n", chunk_sizes[i], (unsigned long)chunk);
}
}
}
Invoking the program as
./memory 0,0,0,0produces this output:
0 | 1024 | 1152 | 2176 | 2688 | 3712 | 3744 | 4768 | 4832 |
--------------Note: If you actually run this program on your machine, results will not be as nice as above due to address-space randomization (among other things).
If invoking the program as
./memory 40,0,0,0produced this output:
0 | 1024 | 1152 | 2176 | 2688 | 3712 | 3744 | 4768 | 4832 |
--------------
The 40-byte chunk was allocated at address 4768would you conclude that the heap allocator, when it allocates a chunk of RAM in a hole, allotes that chunk at the beginining of the hole (i.e., lower addresses in the hole) or at the end of the hole (i.e., higher addresses in the hole). Why? To explain why just use a contraposition argument (e.g., if the heap allocator did X then Y would have happened, but instead Z happened).
Whatever the heap allocator does, this is what we assume it does for all subsequent questions.
If invoking the program as
./memory 120, 300, 80, 30were to produce this output:
0 | 1024 | 1152 | 2176 | 2688 | 3712 | 3744 | 4768 | 4832 |
--------------
The 120-byte chunk was allocated at address 2176
The 300-byte chunk was allocated at address 2296
The 80-byte chunk was allocated at address 1024
The 30-byte chunk was allocated at address 3712would you say that the heap allocator uses
Explain why.
If invoking the program as
./memory 80,200,220,20were to produce this output:
0 | 1024 | 1152 | 2176 | 2688 | 3712 | 3744 | 4768 | 4832 |
--------------
The 80-byte chunk was allocated at address 1024
The 200-byte chunk was allocated at address 2176
The 220-byte chunk was allocated at address 2376
The 20-byte chunk was allocated at address 3712would you say that the heap allocator uses
Explain why.
After looking up some documentation, you find out that the heap allocator uses best fit! What would the output of the memory program be when invoked as follows:
./memory 90, 20, 30, 20