Coding strategy: the helpful part
Casting.
Take a look at the implementations of hl_init and
hl_alloc. Notice that casting the heapptr to
a block_header_t * is a straight forward and very readable
way to set and access the fields of the otherwise unspecified heap.
(Aside: Casting can be a very helpful way to peek at memory. Want to
know whether a machine is little or big endian? Write a number into an
integer, create a pointer to the integer, cast the pointer to a
char * and dereference it. Now you're looking at the byte
of the integer in memory at the lowest address!)
Debug-only print statements.
Notice the print_block_header function. Although this
function may be incredibly useful to a programmer when implementing and
debugging, this is not the kind of information that should be printed
to the screen when some program includes and makes calls to your
heaplib.c library. Novice programmers notoriously litter
their code with print statements that are commented in and out as they
code. This is not good form, especially since some straggling
printf's almost always remain in the final version of the
code. This is particularly devastating when performance matters (which
it does for this assignment).
One solution to this problem is to create a variable such as
debug_mode_f (_f often indicates a flag in C)
and put the print statement inside an if statement that
checks the variable:
if (print_debug_f) {
print_heap(heap);
}
This solution has the nice property that (if tied to a command line
option) the flag can be turned off and on each time you run the
program. The problem with this approach is that even your
"production-level" code will be littered with if
statements that always evaluate to false.
The code you have been given solves the problem by placing the print
statement as the controlled text in a conditional group:
#ifdef PRINT_DEBUG
print_heap(heap);
#endif
The preprocessor (part of the compiler) will only insert the controlled
text if the PRINT_DEBUG has been defined/set.
This Macro approach requires re-compiling in order to insert the print
statements. This may not be the best strategy for every scenario, but
it is for this assignment. Do not use any print statements inside
your heaplib.c that are not wrapped in an
#ifdef flag. Compiling
and Running Your Code discussed how to turn the flag on and off
at compile time.
Pointer arithmetic.
To implement this assignment, you will want to use pointer arithmetic.
As a basic example, see the following snippet of code:
// warning: this code is buggy
int hl_init(void *heapptr, unsigned int heap_size) {
block_header_t *heap = (block_header_t *)heapptr;
heap->next_free = heap + sizeof(block_header_t);
...
This code initializes the next_free pointer to point to
the first free byte, which lives past the header. A careful programmer
will not assume to know the size of all types on any machine that their
code might run on. (There might not even be one right answer!) Instead,
we use sizeof. The code above, however, is still flawed.
Because heap is of type block_header_t *,
adding some number to it, say 16, will move the pointer
forward "16 block_header_ts worth" (in other words, 16 x
sizeof(block_header_t)). Two correct versions would be:
heap->next_free = heap + 1;
(move ahead 1 block_header_t worth) or
heap->next_free = (char *)heap + sizeof(block_header_t);
(temporarily cast heap to be a char * so
that adding 16 just adds 16 chars to the address.)
If you did not understand the problem in the above paragraph or why
both solutions work, you are not ready to begin this assignment! Go
brush up on your pointer arithmetic.
Using Macros.
Given the amount of pointer arithmetic required for this assignment,
you may find your code littered with many small but hard-to-read lines
of code that are performing essentially the same task repeatedly. For
example, you may find that you frequently add some number of bytes to
an address that needs to be cast to a char *. For
readability, you may be tempted to create short helper functions for
these tasks. Knowing what you now know about the overhead of a function
call and knowing that your code will be tested for speed, you should
instead use macros. A macro is a <keyword,
definition> pair. Any reference to the keyword will be replaced by
the definition at compile time. You may be familiar with simple
macros such as:
#define ALIGNMENT 8
which is a great way to rid your code of magic numbers. Macros can
also be more complex, taking arguments. For example:
/* Useful shorthand: casts a pointer to a (char *) before adding */
#define ADD_BYTES(base_addr, num_bytes) (((char *)(base_addr)) + (num_bytes))
We recommend using macros for any complicated but simple tasks; your
code will be much more readable, maintainable, and debuggable at no
performance cost.
Using sizeof.
Notice that nowhere in this code are the sizes of types assumed to be
known. Different types are of different sizes in different
environments. We will test your code on the course VM. Even still, your
library code should have no "magic numbers" that make assumptions about
sizes, even if they are correct on the course VM. One solution is to
call sizeof() throughout your program.
uintptr_t in <stdint.h> is guaranteed
to contain the size of pointer on the machine where the executable is
running. You may find this useful.
Ternary Operators.
Ternary operators are very
useful because they allow you to have a conditional output without explicitly
writing an if statement.
block->in_use_f ? "Yes" : "No"
The value before the ? is a boolean expression, and if
true, evaluates to "Yes", otherwise it evaluates to
"No".
Note that the ternary operator has very low precedence, so be sure to
wrap your ternary operator usage in parentheses! i.e.
(x ? 1 : 2)
instead of
x ? 1 : 2
Student implementations of dynamic memory allocators are notoriously ugly
and impossible to debug. Yours should not be. First, because you
will make your own life a living hell. Second, because we will deduct
style points for anything egregious. We have given you sample code with
all sorts of tricks in it because these are tricks that expert
programmers know about and use regularly. Now that you have been shown
these techniques, you will be expected to use them.
Cost of a ridiculously long project writeup? 15 minutes. Shedding
your status as a novice and being able to produce code that is readable,
debuggable, and super fast? Priceless.