[U-Boot] early_malloc outline

[Tomas Hlavacek]

Dear Wolfgang,

On Tue, Aug 7, 2012 at 11:07 PM, Wolfgang Denk <wd at denx.de> wrote:

> But "relocation" means that you have to add the address difference
> (aka relocation offset) to _all_ pointers pointing into this area.
> And there is no way to keep track of _all_ such pointers.

Sure there is no way to do relocation of all data in the early_malloc
arena generically (= for all data present regardless of their origin
and use). And neither I want to do so.

It comes down to the reason for implementing early_malloc: The reason
is to facilitate minimalistic heap allocation for driver model tree in
the early init phase. It is essential to start building the tree in
the early phase (= in board_init_f) in order to have drivers bound to
their cores before first use and to be able to call particular drivers
through DM driver cores from the very beginning. (Driver cores are
structs that are DM abstractions of particular drivers; this structs
are held in DM tree.) It is also needed to build DM tree in runtime,
otherwise the DM tree generated in compile-time would be board
specific and it would disallow prospective unification of resulting
ROMs for more than one board.

The reason for having DM tree is that driver cores use identification
that belongs to an ordered set and a tree offers the fastest way to
search by driver core ID (assuming that hash tables do not suite the
purpose well because of space consumption and constant possibility of
adding new values and repeated rehashing, but essentially hash tables
could be used as well). Anyway I think I am not the right advocate of
DM design nor a supplement for design documents which are going to be
presented here in near future. I would rather have an input for DM
design from this discussion, than discussion about
output/decisions/suggestions from DM project.

Regarding relocation I want to implement it only for DM tree assuming
that I can retain the root pointer in GD and I can traverse the tree
using computed offsets. But there are obvious problems when the
early_malloc is used for another purpose than DM. Another users (which
is what Graeme suggested to take into account) might want to use the
early_heap during early init but he might want not to retain data and
therefore copying that data to RAM would be waste of CPU time and RAM.
In the opposite case when another user would like to retain his data,
he must relocate it on his own (which means retain needed pointers and
rectify them afterwards).

Thinking about possibilities I have: I can try to satisfy both cases
in cost of introducing extra complexity or even dead-code to
early_mallocator by having two heap types (for allocations that are
going to be retained and for allocations that are not to be copied to
RAM). Only the first type is going to be copied to RAM for later
data-specific relocation (done by each user in some relocation chain).
Or I can only satisfy needs of DM which is the way I would prefer.

>
> I am convinced that you _cannot_ reliably relocate the malloc arena if
> you use the standard malloc//calloc/free interface for early
> allocation.

Forgive me my ignorance but why?

Assuming that there is a DM driver core with certain dm_core_init()
function that calls malloc() and then registers the DM driver core
into the DM tree, it is still the same function for early and late
init. The only difference is that pointers inside the DM driver core
have to be recomputed when this driver core is in the DM tree at the
time of relocation. It seems to me that there is no need for code
duplication or adding extra complexity to distinguish early and late
cases and call sometimes early_malloc() instead of malloc().

(Sure I can create a "private" wrapper, for example dm_malloc(),
dm_calloc(), dm_free(),... strictly for DM needs.)

Tomas

-- 
Tomáš Hlaváček <tmshlvck at gmail.com>