Hi Tomas,
On Wed, Sep 26, 2012 at 8:16 PM, Tomas Hlavacek tmshlvck@gmail.com wrote:
Hello Graeme,
On Wed, Sep 26, 2012 at 1:04 AM, Graeme Russ graeme.russ@gmail.com wrote:
Hi Tomas
On Tue, Sep 25, 2012 at 7:09 PM, Graeme Russ graeme.russ@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:
- scan through all heaps to find best fit into previously free()-ed block
- scan through all heaps to find enough free space using the heap header
- 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:
- scan through all heaps to find best fit block
- scan through all heaps to find greater block and split it
- 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