 Memory Free
This function frees memory allocated by the previous program. To reiterate, memory is allocated out of a block of memory, in multiples of a specified block size. A consecutive group of blocks of memory, whether free or allocated, is called a span. An "in use" array tracks whether each block is allocated or freed. 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 the pre-processor definitions:
#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];
The code assumes that the buffer passed to be freed was in fact allocated by a correctly functioning version of the memory allocator, and is in the proper range and aligned correctly. It also assumes that the array_in_use array has not been corrupted.
Source Code
1. void
2. mem_free(char * buffer)
3. {
4. int i, buffer_index, buffer_block_count;
5. int adjust_start, adjust_end;
6. int adjust_value;
7. int prev_block_count, next_block_count;
8.
9. // Fix up array_in_use[] if the spans before and/or
10. // after are also free.
11.
12. buffer_index = (buffer - array) / BLOCK_SIZE;
13. buffer_block_count = -array_in_use[buffer_index];
14.
15. // These start out just fixing up this span --
16. // they may grow if the previous and/or next span
17. // has to be merged in. The fixup will be done
18. // starting at array_in_use[adjust_start], up to
19. // but not including array_in_use[adjust_end].
20.
21. adjust_start = buffer_index;
22. adjust_end = buffer_index + buffer_block_count;
23. adjust_value = buffer_block_count;
24.
25. // See if there is a previous span and is it free.
26.
27. if ((adjust_start > 0) &&
28. (array_in_use[adjust_start - 1] > 0)) {
29.
30. prev_block_count = array_in_use[adjust_start-1];
31. adjust_start -= prev_block_count;
32. adjust_value += prev_block_count;
33. }
34.
35. // See if there is a next span and is it free.
36.
37. if ((adjust_end < BLOCK_COUNT) &&
38. (array_in_use[adjust_end+1] > 0)) {
39.
40. next_block_count = array_in_use[adjust_end+1];
41. adjust_end += next_block_count;
42. adjust_value += next_block_count;
43. }
44.
45. // Now mark the span as free and the proper size.
46.
47. for (i = adjust_start; i < adjust_end; i++) {
48. array_in_use[i] = adjust_value;
49. }
50. }
Suggestions
What are the empty and trivial input cases for this function? The code has various comments. Do the comments correctly match the functionality of the blocks they describe? The code has many local variables. Which ones are used throughout the function and which ones are used only in certain blocks? What are the valid values for indexing into array_in_use? Are they properly enforced? In cases where expressions are used, what does that imply about restrictions on the indexing variables? Are those followed?
Hints
Walk through the code with the following parameters to the function:
Verify that the code correctly restores all memory to be a single free span if only one allocation exists and it is freed. So, there is one allocation, starting at the third block and continuing for two blocks. array_in_use[] is set up as follows: array_in_use[0] == 2
array_in_use[1] == 2
array_in_use[2] == -2
array_in_use[3] == -2
array_in_use[4] == BLOCK_COUNT-4
array_in_use[5] == BLOCK_COUNT-4
array_in_use[6] == BLOCK_COUNT-4
...
array_in_use[BLOCK_COUNT-1] == BLOCK_COUNT-4
The single allocation is freed. In effect, mem_free(array + (2*BLOCK_SIZE))
is called, although the caller of mem_free() should not actually know about internal details, such as array[] and BLOCK_SIZE. Test the boundary case of a single large allocated span, with one small free span at the end: There is one allocation, starting at block 0 and continuing for BLOCK_COUNT-1 blocks, followed by one free block. Therefore, array_in_use[] is set up:
array_in_use[0] == -(BLOCK_COUNT-1)
array_in_use[1] == -(BLOCK_COUNT-1)
...
array_in_use[BLOCK_COUNT-2] == -(BLOCK_COUNT-1)
array_in_use[BLOCK_COUNT-1] == 1
The single allocation is freed. In effect,
mem_free(array)
is called.
Explanation of the Bug
The code that checks if the next span is free, on lines 37-43
if ((adjust_end < BLOCK_COUNT) &&
(array_in_use[adjust_end+1] > 0)) {
next_block_count = array_in_use[adjust_end+1];
adjust_end += next_block_count;
adjust_value += next_block_count;
}
indexes into array_in_use[] incorrectly. Because adjust_end is defined to be one more than the block number at the end of the buffer being freed, it is incorrect to add 1 to it. This is an A.off-by-one error that becomes a D.index error. The code needs to be as follows:
if ((adjust_end < BLOCK_COUNT) &&
(array_in_use[adjust_end] > 0)) {
next_block_count = array_in_use[adjust_end];
adjust_end += next_block_count;
adjust_value += next_block_count;
}
The example in the first hint works because adjust_end is 4 when the code arrives at line 37. The comparison on line 38 will look at array_in_use[5] when it should be looking at array_in_use[4], but because they are both equal to the same thing (BLOCK_COUNT-4), next_block_count is set to BLOCK_COUNT-4 on line 40, and adjust_end is then properly modified from 4 to BLOCK_COUNT on line 41.
With the second hint, adjust_end is equal to BLOCK_COUNT-1 at line 37. As a result, the comparison on line 38 indexes array_in_use[BLOCK_COUNT], which is past the end of array_in_use[], and results in either a crash or undefined behavior, depending on whether the integer at that memory location is positive or negative.
| 
