[U-Boot] [PATCH v8] [RFC] early_malloc for DM added.

[Tomas Hlavacek]

Hello Graeme,

On Wed, Sep 26, 2012 at 1:04 AM, Graeme Russ <graeme.russ at gmail.com> wrote:
> Hi Tomas
>
> On Tue, Sep 25, 2012 at 7:09 PM, Graeme Russ <graeme.russ at gmail.com> wrote:
>
>> We should implement each of malloc(), free(), calloc(), and realloc().
>>
>> Don't worry about reclaiming and reusing space with a proper free()
>> implementation. Remember, all memory allocated on the early heap must be
>> relocated anyway.
>>
>> Maybe if you add a size_t value immediately before the allocated space which
>> stores the block size. So:
>>
>> size_t *bytes_ptr = ptr;
>> bytes_ptr--;
>> size_t bytes = *bytes_ptr;
>>
>> gives you the block size
>
> I've been thinking about this a bit more, and for the sake of 4 bytes,
> this additional 'size' member could be quite handy:
>  - We effectively end up with a linked-list of allocated blocks

Yes, this makes sense. Knowing size of allocated blocks enables the
early_malloc to do the whole set of malloc* functions.

Do you think it would be also useful to have a basic check that the
pointer passed to new early_free() and/or early_realloc() is valid? I
mean check that the pointer really points at the start of the block
and there is a valid header preceding the block. We can have a magic
number in the header for example. Or I can store a list of allocated
blocks as a variable-sized array in the early_heap_header.

>  - free() could set the high bit to tag the block as 'de-allocated'

Well, we would end up with malloc doing:

1) scan through all heaps to find best fit into previously free()-ed block
2) scan through all heaps to find enough free space using the heap header
3) call early_brk to obtain more space

Data structures would be:

The scanning two different header types for free space seems to me
being a bit redundant. What do you think about replacing point (2) and
using block headers instead of free space pointer in the heap header
and just split the block when there is not exact size match. I mean:

1) scan through all heaps to find best fit block
2) scan through all heaps to find greater block and split it
3) call early_brk to obtain more space

Data structures would be:

struct early_heap_header {
    int heap_size;
    phys_addr_t reloc_addr_old;
}

struct early_block_header {
    int magic;
    int size;
}

The brand new early_heap right after it's creation would consist of a
early_heap_header followed by a early_block_header with the free bit
set to true.

>  - When a block is relocated into the permanent heap, free() should be
>    called on the source (early heap) block

Well, that time we would have only a copy of the early_heap on certain
platforms. Assuming that first we set off drivers and DM using
early_heap(s), then we would copy each early_heap to some computed
address and jump to board_init_r. In board_init_r we would access the
early_heap copy via translation function using the address offset
(early_heap_copy - early_heap_copy->reloc_addr_old).

To do the early_free correctly in this mid-relocation state I would
have to allow early_* code to operate during this period. It is not
that hard to do, but maybe it is conceptually wrong because it means
operating early_malloc/realloc/free code on a copy of it's own data
after relocation.

>  - We can call a 'cleanup' function after early heap is no longer needed
>    and check that every block has the high bit set

Yes, it would help. When each block has to be free()-ed or relocated
and then free()-ed, it could help find memory leaks during early init.

>  - We can re-use blocks by scanning for a tagged block with the same size
>    (usefull for drivers that allocate temporary buffers which are always
>    the same size)
>  - If there are no early heaps with enough space for a given malloc
>    operation, but there is a tagged block that is larger than the
>    requested size, we can split tagged blocks
>
> Remebering back to when I suggested a list of relocation helpers (one for
> each allocated block), I think we can implement that as an additional field
> in the block header (stretching the header to 8 bytes). This can come later.

Do you mean we should place a pointer pointing at a relocation
function into each block header? I think it would end up in situation
like: Somebody is allocating a tree for example, he would set the
helper function into the root element and NULL pointers to other
nodes, because it makes more sense to relocate tree recursively from
the root.

Tomas