I have taken a look at the algorithm used by malloc(), andfrom avr-libc, and there seems to be a few usage patterns that are safe from the point of view of heap fragmentation:

1. Allocate only long-lived buffers

By this I mean: allocate all you need at the beginning of the program, and never free it. Of course, in this case, you could as well use static buffers...

2. Allocate only short-lived buffers

Meaning: you free the buffer before allocating anything else. A reasonable example might look like this:

void foo()
{
    size_t size = figure_out_needs();
    char * buffer = malloc(size);
    if (!buffer) fail();
    do_whatever_with(buffer);
    free(buffer);
}

If there is no malloc inside do_whatever_with(), or if that function frees whatever it allocates, then you are safe from fragmentation.

3. Always free the last allocated buffer

This is a generalization of the two previous cases. If you use the heap like a stack (last in is first out), then it will behave like a stack and not fragment. It should be noted that in this case it is safe to resize the last allocated buffer with realloc().

4. Always allocate the same size

This will not prevent fragmentation, but it is safe in the sense that the heap will not grow larger than the maximum used size. If all your buffers have the same size, you can be sure that, whenever you free one of them, the slot will be available for subsequent allocations.