#424 A more space-efficient heap

[Philipp Klaus Krause]

This is a sketch of a new memory management for the heap. It compiles, but has not been tested in any way. The memory overhead per allocated block is 2 bytes for even-sized blocks and 3 bytes for odd-sized blocks.
This is probably somethign to look into after the 3.5.0 release.

Philipp

P.S.: By using a doubly-linked list, free() and realloc() speed could be improved, incrasing the memory overhead per allocated block to 4 bytes for even-sized blocks and 5 bytes for odd-sized blocks.
P.P.S.: Currently sdcc has two implementations, one has an overhead of 4 bytes per block and slow free(), the other has an overhead of 6 bytes per block and fast free().

[Maarten Brock]

I have a strong feeling that on many occasions you can also use the msb instead of the lsb. I think that often the whole heap will be <32k in size and placed either completely above or below the 32k boundary. We could leave that as an option to the users if they are willing to recompile the heap functions.

[Philipp Klaus Krause]

And for some ports we can should make MSB the default:
AFAIK all the currently existing STM8 variants have all their RAM in the lower 32KB. And accessing the MSB is more efficient even than accesing the LSB on STM8.

Philipp

[Philipp Klaus Krause]

It seems the S08 also have all RAM in the lower 32KB. I guess it's the same for HC08.

Philipp

[Philipp Klaus Krause]

I have come up with a better approach that uses two lists. One lists contains all blocks, the other one contains the free blocks. The list of free blocks is stored in the free blocks, and thus results in no overhead.
We get a total overhead of 2 bytes per allocated block, and don't need any flag bits. For typical use cases we also get a faster malloc().
I'll try to implement a prototype.

Philipp

[Philipp Klaus Krause]

Drafts of malloc() and free() attached. I have not yet completed realloc(), and done no testing or bugfixing.

Philipp

[Philipp Klaus Krause]

The attached versions pass the regression tests for z80 and stm8.

Philipp

[Maarten Brock]

Even though SDCC has a history of requiring the user to call _sdcc_heap_init() I would really like this to disappear. It should either be called in malloc or at startup. Maybe we can even let the linker insert it only when necessary.

Another request I have is to insert a macro in the pointer types that can signify __xdata for the mcs51/ds390. Malloc will always allocate in xdata and never in code/idata/sfr/bit-space. The code for malloc and friends will be more efficient and if the user wants even user code can be. Only the input pointers should be generic pointers.

[Philipp Klaus Krause]

Yes. The files I attached are meant to work as a drop-in replacement, so allow running the regression tests. But there is more to do: What you mentioned, the names of externally visible symbols should start with two underscores, and a common way to pass information on heap location and size (the existing two implementations use different ways).

Philipp

[Philipp Klaus Krause]

I have added the __xdata stuff, and it compile for mcs51, but I'm not an expert on it.

Philipp

[Maarten Brock]

I think there is a bug in line 74 of realloc.c:

maxblocksize += (char *)(next_free->next) - (char *)h;

I think that should be h->next instead of h.

[Philipp Klaus Krause]

Thanks for finding this bug. I added a regression test in revision #9319.

Philipp

[Philipp Klaus Krause]

This is my latest round of changes. It should work as a drop-in replacement for the old one for all ports now. But I see regression failures, so I must have messed something up.

Philipp

[Philipp Klaus Krause]

Improved versions. Tested on hc08, s08, ucz80, stm8, mcs51-small. Mostly working.
There is still a failing assertion in the malloc regression test; it looks like a problem with the creation of a new free block in realloc().

Philipp

[Philipp Klaus Krause]

Passes tests, to be put into SDCC soon.

Philipp

[Maarten Brock]

I still have some concerns.

First, for clarity, would you consider a typedef for the struct?

typedef struct header
{
    struct header XDATA *next;
    struct header XDATA *next_free; // Next free block. Used in free blocks only. Overlaps with user data in non-free blocks.
} XDATA header_t;

Second, what's the -1 doing here? It seems to me it only risks HEAP_END to be smaller than HEAP_START and ensures nothing.

#define HEAP_END (header_t *)(_sdcc_heap + _sdcc_heap_size - 1) // -1 To be sure that HEAP_END is bigger than HEAP_START.

Then in malloc() you check against HEAP_END in a risky way IMO.

    for(h = __sdcc_heap_free, f = &__sdcc_heap_free; h < HEAP_END; f = &(h->next_free), h = h->next_free)

What if the heap lies from 0x8000-0x10000 ? HEAP_END will be 0 ! I think it's better to initialize __sdcc_heap_free->next_free to NULL and check h for being non-NULL.

Finally, if you place __sdcc_heap_free in XDATA as well then f need not be a generic pointer.

header_t * XDATA __sdcc_heap_free;
header_t * XDATA *f;

I hope this makes sense to you.
Maarten

[Maarten Brock]

Oh oh, If we use NULL then __sdcc_heap_free can become 0 again after initialization which retriggers the _sdcc_heap_init() call. Maybe we should try to find a way to conditionally include the initialization in the crt.

[Philipp Klaus Krause]

We can't use 0 to mark the end, as that will mess up size calcultions for the last free block.
The idea is that the last next_free points to a byte just beyond the end of the heap. I put the in -1 in case the last byte f the heap is at the top of the address range. Then the -1 should bring it back to the top of the address range (resulting in the loss of 1 byte of heap space).

Philipp

[Maarten Brock]

Maybe we misunderstand each other. Null should only be used for the end of the next_free list and not for the next list. I don't see yet how that would mess things up.

((char*)h->next - (char*)h) will have the correct result even if next happens to be 0 which actually means 0x10000.

Ok, I understand the -1 now, though the comment should be clearer. And I don't think it is necessary with my proposed change. But how do you prevent HEAP_END to be 0 for the z80?

And the check in realloc for merging with the next free block is also still buggy when next_free equals HEAP_END (or NULL with my proposal). You can not dereference it.

if(next_free == h->next) // Can merge with next block
    maxblocksize += (char XDATA *)(next_free->next) - (char XDATA *)next_free;

Maarten

[Philipp Klaus Krause]

On 19.09.2015 15:42, Maarten Brock wrote:

Ok, I understand the -1 now, though the comment should be clearer. And I
don't think it is necessary with my proposed change. But how do you
prevent HEAP_END to be 0 for the z80?

On the z80 with current crt0, HEAP_END is always the address of the last
byte of the heap, not the byte after it. So we are on the safe side, but
lose that last byte.

Could we come up with one meachanism to communicate heap location and
size, that works the same for all ports? And that only uses symbols
reserved for the imlementation?

Philipp

[Maarten Brock]

How about this?

sdcc_malloc.h:

#define __SDCC_HEAP_SPACE    __xdata

typedef struct __sdcc_header
{
    struct __sdcc_header __SDCC_HEAP_SPACE *next;
    struct __sdcc_header __SDCC_HEAP_SPACE *next_free; // Next free block. Used in free blocks only. Overlaps with user data in non-free blocks.
} __SDCC_HEAP_SPACE * __sdcc_pheader_t;

typedef char __SDCC_HEAP_SPACE * __sdcc_pbyte_t;

heap.c:

#include <sdcc_malloc.h>

#ifndef HEAP_SIZE
#define HEAP_SIZE 1024
#endif

__SDCC_HEAP_SPACE char __sdcc_heap[HEAP_SIZE];
const __sdcc_pheader_t __sdcc_heap_end = (__sdcc_pheader_t)(__sdcc_heap + HEAP_SIZE);

This way the user can simply copy this source, recompile it with the desired heap space and link it with his/her project.

Maarten

[Maarten Brock]

Another option could be to introduce a command line option for setting the heap size and generate the heap when compiling main().

[Philipp Klaus Krause]

On 20.09.2015 18:52, Maarten Brock wrote:

Another option could be to introduce a command line option for setting
the heap size and generate the heap when compiling main().

That's probably the best solution from the user interface perspective.
For z80 and related, it would also be ok, to put some stuff into crt0,
since the user usually has to modify that one anyway. But a command-line
argument is probably easier to use.

Philipp

[Philipp Klaus Krause]

On 20.09.2015 18:52, Maarten Brock wrote:

Another option could be to introduce a command line option for setting
the heap size and generate the heap when compiling main().

That's probably the best solution from the user interface perspective.
But it requires more special-case handling in the compiler.
For z80 and related, it would also be ok, to put some stuff into crt0,
since the user usually has to modify that one anyway. But a command-line
argument is probably easier to use there, too.

Philipp

[Philipp Klaus Krause]

On 20.09.2015 18:51, Maarten Brock wrote:

How about this?

sdcc_malloc.h:

define SDCC_HEAP_SPACE xdata

typedef struct sdcc_header
{
struct sdcc_header SDCC_HEAP_SPACE *next;
struct sdcc_header SDCC_HEAP_SPACE *next_free; // Next free block. Used in free blocks only. Overlaps with user data in non-free blocks.
} SDCC_HEAP_SPACE * __sdcc_pheader_t;

typedef char SDCC_HEAP_SPACE * sdcc_pbyte_t;

heap.c:

include <sdcc_malloc.h>

ifndef HEAP_SIZE

define HEAP_SIZE 1024

endif

SDCC_HEAP_SPACE char sdcc_heap[HEAP_SIZE];
const sdcc_pheader_t sdcc_heap_end = (sdcc_pheader_t)(sdcc_heap + HEAP_SIZE);

This way the user can simply copy this source, recompile it with the
desired heap space and link it with his/her project.

Maarten

It's an elegeant solution from the compiler perspective. Modifying it a
bit, we wouldn't even need an init function. But it is one more source
file the user has to modify, so it is not that elegant from the user
interface perspective.

Philipp