 Memory Allocator
This function is a memory allocator. Allocations are made from a chunk of memory, which in C is simply an array of chars. Memory is always allocated in multiples of a constant block size, so allocations are internally rounded up in size.
A consecutive group of blocks of memory, whether free or allocated, will be called a span. A second "in use" array tracks whether each block is allocated or freed; the "in use" array has one element per block. If a span is free, all the entries in the "in use" array that correspond to the blocks in the span contain the same positive value, which is the number of blocks in the span. If a span is allocated, all the corresponding entries in the "in use" array contain the same negative value, which is the negative of the number of blocks in the span.
The code uses some definitions interpreted by the C pre-processor:
#define MEMORY_SIZE 8000
#define BLOCK_SIZE 16
#define BLOCK_COUNT (MEMORY_SIZE / BLOCK_SIZE )
The following code allocates the main memory array and the "in use" array:
char array[MEMORY_SIZE];
int array_in_use[BLOCK_COUNT];
In addition, it assumes the following initialization function has been called, which initializes the "in use" array to show that every block is free and is part of a span that covers the entire chunk of allocatable memory:
void mem_init()
{
int i;
for (i = 0; i < BLOCK_COUNT; i++) {
array_in_use[i] = BLOCK_COUNT;
}
}
Source Code
1. void *
2. mem_alloc(int length)
3. {
4. int i;
5. int blocks_needed, old_span_size;
6. int block_index, best_fit;
7.
8. blocks_needed =
9. (length + (BLOCK_SIZE-1)) / BLOCK_SIZE;
10.
11. // Now try to find the smallest free span that has
12. // blocks_needed blocks available. best_fit stores
13. // the index of the start of the best span found
14. // so far.
15.
16. block_index = 0;
17. best_fit = -1; // indicate nothing found so far
18.
19. while (block_index < BLOCK_COUNT) {
20.
21. if (array_in_use[block_index] >=
22. blocks_needed) {
23.
24. if (best_fit == -1) {
25. best_fit = block_index;
26. } else {
27. if (array_in_use[block_index] <
28. array_in_use[best_fit]) {
29. best_fit = block_index;
30. }
31. }
32. }
33. // Skip to the next span
34. block_index += array_in_use[block_index];
35. }
36.
37. // if best_fit stayed at -1, then nothing was found
38. if (best_fit == -1) {
39. return NULL;
40. }
41.
42. // Found a span; split it into two spans,
43. // the allocated part and the remaining free part.
44.
45. old_span_size = array_in_use[best_fit];
46. for (i = 0; i < blocks_needed; i++ ) {
47. array_in_use[best_fit + i] = -blocks_needed;
48. }
49. for (i = blocks_needed; i < old_span_size; i++) {
50. array_in_use[best_fit + i] -= blocks_needed;
51. }
52.
53. return (array + (best_fit * BLOCK_SIZE));
54. }
Suggestions
What is the goal of the while loop on lines 19-35? What variable is being set and what should it be set to when it is done? The calculation of blocks_needed on lines 8-9 and the return statement on line 53 are both complicated. Verify that they are correct. What is the loop counter for the while loop on lines 19-35? Is it properly incremented? Are the initialization and termination clauses correct? For the five local variables, note any sections of the code in which they stay invariant.
Hints
Walk through the code with the following parameters to the function:
The initial case: Nothing has been allocated, so the array_in_use[] array is still set up the way it was by the memory_init() function: array_in_use[0] == BLOCK_COUNT
array_in_use[1] == BLOCK_COUNT
array_in_use[2] == BLOCK_COUNT
...
array_in_use[BLOCK_COUNT-1] == BLOCK_COUNT
and the function mem_alloc(BLOCK_SIZE)is called. One block is allocated, the second block in array[]. Check that the code correctly picks a block that can fit the request. Therefore array_in_use[0] == 1
array_in_use[1] == -1
array_in_use[2] == BLOCK_COUNT-2
array_in_use[3] == BLOCK_COUNT-2
array_in_use[4] == BLOCK_COUNT-2
...
array_in_use[BLOCK_COUNT-1] == BLOCK_COUNT-2
and the function mem_alloc(BLOCK_SIZE+1) is called.
Explanation of the Bug
At the end of the while loop starting on line 19, the index of the next span to check is calculated using the knowledge that the number of blocks in this span is stored in array_in_use[], on line 34:
block_index += array_in_use[block_index];
However, this only works for free spans, where the corresponding array_in_use[] element has a positive value.
When crossing allocated spans, where array_in_use[] has a negative value, the if on line 21 always fails because blocks_needed is positive. That's how the code avoids reallocating an already allocated span. However, array_in_use[] is negative, so to fix this A.logic bug, line 34 should be replaced with code like the following:
if (array_in_use[block_index] < 0) {
block_index += -array_in_use[block_index];
} else {
block_index += array_in_use[block_index];
}
For the first hint, no allocated spans exist, so the array_in_use[] values are always positive. In fact, there is only one free span, so the while loop iterates once, with block_index equal to 0; the code on line 34 adds BLOCK_COUNT to block_index (array_in_use[0] is equal to BLOCK_COUNT), at which point, block_index is equal to BLOCK_COUNT and the while condition on line 19 is false.
In the case of the second hint, blocks_needed is 2. Thus, the first span checked by the if on lines 21-22, with block_index equal to 0, won't be big enough: array_in_use[0] is 1, and blocks_needed is 2. Line 34 changes block_index to 1; on the second iteration of the while loop, the check on lines 21-22 is also false because array_in_use[1] is -1. The code to advance block_index on line 34, instead of changing it to 2 as it should, instead moves it back to 0. So, the while winds up looping forever as block_index ping-pongs between 0 and 1.
| 
