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

[Graeme Russ]

Hi Tomas,

On Wed, Sep 26, 2012 at 8:16 PM, Tomas Hlavacek <tmshlvck at gmail.com> wrote:
> 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.

The goal of early_malloc is to be lightweight and fast, not bullet-proof.

>>  - 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;
> }

Hmm, what is reloc_addr_old all about?

> struct early_block_header {
>     int magic;
>     int size;
> }

NAK on the magic - waste of space

> 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.

Hmm, I think you may be on to something:

struct early_heap_header {
        struct early_heap_header *next_heap;
};

struch early_block {
        size_t size;
        unsigned char *data;
}

We could reserve the upper, say, 8 bits of size as flags. This leaves 24
bits as usable 'size' value (if anyone needs to allocate a 16M chunck of
memory early then we have a problem)

So the early heap starts out with an early_heap_header and an early_block
with size set to the size of the early heap (minus headers) with the
'free' and 'last block' flags set. The first call to early_malloc() would:
 - Split the block
 - Set the size to the appropriate value
 - Clear the 'free' and 'last block' flags
 - Create a new early_block after the allocated space
 - Set the size of the new block to the size of the remaining space
 - Set the 'free' and 'last block' flags of the new block

When calling early_malloc(), search through the list. If you find a free
block of exactly the right size, use it. If not, then while you are
scanning, keep a reference to the smallest free block larger than the
requested size. That leave a decision:
 - Do we always split the first 'smallest free block', or;
 - Do we always split the last block?

If there are no free blocks that can be split, call early_brk()

>>  - 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).

Me == 100% lost :)

Looks like you are still clinging onto the double-copy. If so, I'm still
not convinced.

> 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.

Me == 110% lost :(

>>  - 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.

That's the idea - find poorly written drivers that assumed they would never
be initialised pre-relocation and don't handle relocation correctly.

>>  - 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.

Exactly - One of the flags could be 'no relocate' or some such

Regards,

Graeme