From mboxrd@z Thu Jan 1 00:00:00 1970 From: Graeme Russ Date: Thu, 27 Sep 2012 09:03:44 +1000 Subject: [U-Boot] [PATCH v8] [RFC] early_malloc for DM added. In-Reply-To: References: <1346069529-27397-1-git-send-email-tmshlvck@gmail.com> <201209240111.57287.marex@denx.de> <201209241619.50452.marex@denx.de> Message-ID: List-Id: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: u-boot@lists.denx.de Hi Tomas, On Wed, Sep 26, 2012 at 8:16 PM, Tomas Hlavacek wrote: > Hello Graeme, > > On Wed, Sep 26, 2012 at 1:04 AM, Graeme Russ wrote: >> Hi Tomas >> >> On Tue, Sep 25, 2012 at 7:09 PM, Graeme Russ 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