[U-Boot] Early malloc() summary

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi All,

While the need for early malloc() came about from the driver model and
the desire to make drivers usable before relocation, I think we can all
agree that its scope may well not be limited to use by drivers. A few
examples I can think of the top of my head include:

  - pre-console buffer
  - bd struct
  - early env

(not that I'm advocating any of these get modified to use early malloc,
they are simply presented as examples outside the driver model)

So we all know the intent:
 - have the ability to allocate memory prior to relocation

And we all know the problems:
 1. Preserving allocation references accross relocation
 2. Any given driver may need to use early malloc() on some boards but not
    on others

He is my (hopefully final) design input on this...

1. Create a register_malloc_reloc_func() function
2. Wrap malloc() with a (gd->flags & GD_FLG_RELOC) test
3. Call reloc_early_heap() sometime between mem_malloc_init() and
   enables_caches()
4. Set gd->flags |= GD_FLG_RELOC after calling reloc_early_heap()

register_malloc_reloc_func()
============================
This function registers a relocation helper function. The helper functions
will be called by reloc_early_heap(). The purpose of each helper function
is to relocate data structures from the early heap to the final heap.

int register_malloc_reloc_func(function *helper)
{
  /*
   * Check is already relocated - If so, no need to register the function
   * as all calls to malloc() will be using the final heap anyway
   */
  if (gd->flags & GD_FLG_RELOC)
    return 0;

  /* Add this function to the list of relocation helpers */
  ...blah blah blah...

  return 0;
}

NOTE: It is not strictly neccessary to use register_malloc_reloc_func() if
you have some other hook in the relocation process that will call helper
functions. Yes, I'm looking at you Driver Model :). For Driver Model, maybe
the driver core will register a single function which will step through all
the driver cores and call their relocation functions. It really does not
matter (although it may if things need to be relocated in a particular
order)

malloc()
========
void *malloc(size_t size)
{
  if (gd->flags & GD_FLG_RELOC)
    return dl_malloc(size);

  return early_malloc(size);
}

reloc_early_heap()
==================
int reloc_early_heap()
{
  /* Call each funtion previously registered */
  ... blah blah blah ...

  return 0;
}

Now there has been some discussion about the performance penalties of the
relocation process, copying the early heap twice, etc, etc.

My thought: Keep it simple for now. Worry about optimising it to death
later.

So there are my thoughts.<EOL>

<EOF>

Regards,

Graeme

[U-Boot] Early malloc() summary

[Wolfgang Denk]

Dear Graeme Russ,

In message <CALButCL9btmPEW3Uiv9=tU4Yk7fdTUruzpCcVqMLynpzWv6Pug@mail.gmail.com> you wrote:
> 
> While the need for early malloc() came about from the driver model and
> the desire to make drivers usable before relocation, I think we can all
> agree that its scope may well not be limited to use by drivers. A few
> examples I can think of the top of my head include:

I agree with all this,  but can we please stop this discussion here
and now?

The DM project is big and complicated enough, and I would really like
that they can come up with a straightforward, simple and robust
design.

Adding additional requirements to DM parts here and there will make
this even more complex, and delay design and implementation.

Given that the project team is running under some resource
constrictions (like we all do) we should try to help to get this
implemented as quickly as possible, and not add more and more
requirements that actually have nothing to do with DM.

I suggest we discuss such an extension separately, and ideally after
the DM code has been merged mainline.


> So we all know the intent:
>  - have the ability to allocate memory prior to relocation

Actually I see things different.

With the advent of SPL the strict barrier before/after relocation has
started to crumble.  Already now we have systems which set up a "real"
malloc arena and stack in RAM in the SPL, so they can use features
(like file system support) at a stage that in our "pre/after" type of
thinking would never allow it.

Initally I was not happy about this, and anly accepted it grudgingly,
but the longer I think about it I tend to believe that we really
should allow users such flexibility if their hardware allows it.
Hardware configurations have become so manifold that we should allow
to make maximum use of available features.

So we not only talk about malloc() before "relocation", but actually
runnign arbitrary code.

> And we all know the problems:
>  1. Preserving allocation references accross relocation
>  2. Any given driver may need to use early malloc() on some boards but not
>     on others

Again, I think we will have separate interfaces for malloc(0 and
early_malloc().  Code that cannot be sure of it's runtime environment
(like drivers) will have to provide proper provisions for a mode
switch.  All other code should either "just work" (if standard
malloc() is available under this name, then it is supposed to work),
or break at build time (because f unresolved references to the
malloc/calloc/free names).

> My thought: Keep it simple for now. Worry about optimising it to death
> later.


Switching the focus back to DM, I really would like to ask to delay
alls uch activities until DM has been done (or at least has stabilized
so far that we can affort the luxury of thinking about the next
version with fancy extensions).

Thanks.

Best regards,

Wolfgang Denk

-- 
DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
If only God would give me some clear sign! Like making a large  depo-
sit in my name at a Swiss Bank.                         - Woody Allen

[U-Boot] Early malloc() summary

[Marek Vasut]

Dear Wolfgang Denk,

> Dear Graeme Russ,
> 
> In message 
<CALButCL9btmPEW3Uiv9=tU4Yk7fdTUruzpCcVqMLynpzWv6Pug@mail.gmail.com> you wrote:
> > While the need for early malloc() came about from the driver model and
> > the desire to make drivers usable before relocation, I think we can all
> > agree that its scope may well not be limited to use by drivers. A few
> 
> > examples I can think of the top of my head include:
> I agree with all this,  but can we please stop this discussion here
> and now?

Why should we? We can still run the DM in three people and leave the malloc 
stuff offloaded to Thomas, as he is gaining good knowledge of this stuff.

Besides, the malloc goo is pretty separate part.

> The DM project is big and complicated enough, and I would really like
> that they can come up with a straightforward, simple and robust
> design.
> 
> Adding additional requirements to DM parts here and there will make
> this even more complex, and delay design and implementation.
> 
> Given that the project team is running under some resource
> constrictions (like we all do) we should try to help to get this
> implemented as quickly as possible, and not add more and more
> requirements that actually have nothing to do with DM.
> 
> I suggest we discuss such an extension separately, and ideally after
> the DM code has been merged mainline.
> 
> > So we all know the intent:
> >  - have the ability to allocate memory prior to relocation
> 
> Actually I see things different.
> 
> With the advent of SPL the strict barrier before/after relocation has
> started to crumble.  Already now we have systems which set up a "real"
> malloc arena and stack in RAM in the SPL, so they can use features
> (like file system support) at a stage that in our "pre/after" type of
> thinking would never allow it.
> 
> Initally I was not happy about this, and anly accepted it grudgingly,
> but the longer I think about it I tend to believe that we really
> should allow users such flexibility if their hardware allows it.
> Hardware configurations have become so manifold that we should allow
> to make maximum use of available features.
> 
> So we not only talk about malloc() before "relocation", but actually
> runnign arbitrary code.

So ... we should aim for firing up the real mallocator as soon as possible and 
maybe implement discontigmem (sparsemem) into it, so we don't have to bother 
with relocating pointers maybe?

The only problem I see is platforms where the memory disappears.

> > And we all know the problems:
> >  1. Preserving allocation references accross relocation
> >  2. Any given driver may need to use early malloc() on some boards but
> >  not
> >  
> >     on others
> 
> Again, I think we will have separate interfaces for malloc(0 and
> early_malloc().  Code that cannot be sure of it's runtime environment
> (like drivers) will have to provide proper provisions for a mode
> switch.  All other code should either "just work" (if standard
> malloc() is available under this name, then it is supposed to work),
> or break at build time (because f unresolved references to the
> malloc/calloc/free names).
> 
> > My thought: Keep it simple for now. Worry about optimising it to death
> > later.
> 
> Switching the focus back to DM, I really would like to ask to delay
> alls uch activities until DM has been done (or at least has stabilized
> so far that we can affort the luxury of thinking about the next
> version with fancy extensions).

We still need to handle the pre-reloc drivers somehow, you know ... but I still 
believe we can pull the DM internals in three people and leave Thomas to do 
proper malloc stuff ...

> Thanks.
> 
> Best regards,
> 
> Wolfgang Denk

Best regards,
Marek Vasut

[U-Boot] Early malloc() summary

[Tomas Hlavacek]

Hello Marek,

On Sun, Aug 12, 2012 at 1:16 AM, Marek Vasut <marex@denx.de> wrote:
>
> So ... we should aim for firing up the real mallocator as soon as possible and
> maybe implement discontigmem (sparsemem) into it, so we don't have to bother
> with relocating pointers maybe?
>
> The only problem I see is platforms where the memory disappears.

I doubt that on ARM for instance you can set off real mallocator that
early without completely rewriting it. The idea of having one complex
mallocator working in the same manner in board_init_f and board_init_r
stages, being able to operate on all platforms using their nifty
memory-management/model features and being seamless to users is really
tempting. But do we need/want to introduce such deep rewrites? What
would be the justification? I would say we should stick with the
Wolfgang's opinion: Create small and efficient early_malloc for DM and
prepare it for future extensions and possible reuses.

>> Switching the focus back to DM, I really would like to ask to delay
>> alls uch activities until DM has been done (or at least has stabilized
>> so far that we can affort the luxury of thinking about the next
>> version with fancy extensions).
>
> We still need to handle the pre-reloc drivers somehow, you know ... but I still
> believe we can pull the DM internals in three people and leave Thomas to do
> proper malloc stuff ...

Yes, this is the main question: Should I hack malloc() function or
does it make sense to have both early_malloc() and malloc() exposed to
DM cores/drivers?

The first is better from the point of view of drivers - when you ask
for memory, you get it. But you have to check yourself whether you
need to relocate your pointers or not, though we can provide
"relocation chain" you can register your relocation routine into to
facilitate it. The later makes sense because this makes it explicit
that whenever you use early_malloc() you are responsible for
relocating your data on your own (again, we can provide some facility
for ir).

There is a third path possible: We can provide early_malloc() and say
wrapped_malloc() which can be the third function "give me memory, I do
not care whether it is early or not". So drivers and/or DM can choose
to use malloc routines working in early-only, late-only or both.

Tomas


-- 
Tom?? Hlav??ek <tmshlvck@gmail.com>

[U-Boot] Early malloc() summary

[Marek Vasut]

Dear Tomas Hlavacek,

> Hello Marek,
> 
> On Sun, Aug 12, 2012 at 1:16 AM, Marek Vasut <marex@denx.de> wrote:
> > So ... we should aim for firing up the real mallocator as soon as
> > possible and maybe implement discontigmem (sparsemem) into it, so we
> > don't have to bother with relocating pointers maybe?
> > 
> > The only problem I see is platforms where the memory disappears.
> 
> I doubt that on ARM for instance you can set off real mallocator that
> early without completely rewriting it.

Esp. on ARM, I won't see much of a problem. You usually have some small SRAM 
where such allocator could run.

> The idea of having one complex
> mallocator working in the same manner in board_init_f and board_init_r
> stages, being able to operate on all platforms using their nifty
> memory-management/model features

Do you need them? You usually need only a piece of RW memory.

> and being seamless to users is really
> tempting. But do we need/want to introduce such deep rewrites?

Deep rewrites? You'd only need to implement sparsemem into it, which might be 
list of RW memory areas instead of one memory area.

> What
> would be the justification? I would say we should stick with the
> Wolfgang's opinion: Create small and efficient early_malloc for DM and
> prepare it for future extensions and possible reuses.

dm_malloc you mean? I'm not happy about it, maybe Graeme can pour in some crazy 
juice in our direction again?

> >> Switching the focus back to DM, I really would like to ask to delay
> >> alls uch activities until DM has been done (or at least has stabilized
> >> so far that we can affort the luxury of thinking about the next
> >> version with fancy extensions).
> > 
> > We still need to handle the pre-reloc drivers somehow, you know ... but I
> > still believe we can pull the DM internals in three people and leave
> > Thomas to do proper malloc stuff ...
> 
> Yes, this is the main question: Should I hack malloc() function or
> does it make sense to have both early_malloc() and malloc() exposed to
> DM cores/drivers?

This is indeed the main question -- ideas ?

> The first is better from the point of view of drivers - when you ask
> for memory, you get it. But you have to check yourself whether you
> need to relocate your pointers or not, though we can provide
> "relocation chain" you can register your relocation routine into to
> facilitate it. The later makes sense because this makes it explicit
> that whenever you use early_malloc() you are responsible for
> relocating your data on your own (again, we can provide some facility
> for ir).
> 
> There is a third path possible: We can provide early_malloc() and say
> wrapped_malloc() which can be the third function "give me memory, I do
> not care whether it is early or not". So drivers and/or DM can choose
> to use malloc routines working in early-only, late-only or both.
> 
> Tomas

Best regards,
Marek Vasut

[U-Boot] Early malloc() summary

[Albert ARIBAUD]

Hi Marek,

On Tue, 14 Aug 2012 14:37:29 +0200, Marek Vasut <marex@denx.de> wrote:
> Dear Tomas Hlavacek,
> 
> > Hello Marek,
> > 
> > On Sun, Aug 12, 2012 at 1:16 AM, Marek Vasut <marex@denx.de> wrote:
> > > So ... we should aim for firing up the real mallocator as soon as
> > > possible and maybe implement discontigmem (sparsemem) into it, so
> > > we don't have to bother with relocating pointers maybe?
> > > 
> > > The only problem I see is platforms where the memory disappears.
> > 
> > I doubt that on ARM for instance you can set off real mallocator
> > that early without completely rewriting it.
> 
> Esp. on ARM, I won't see much of a problem. You usually have some
> small SRAM where such allocator could run.

... or not; for instance, orion5x / edminiv2 does not have such SRAM. So
how do we handle this there?

Amicalement,
-- 
Albert.

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi Marek,

On Tue, Aug 14, 2012 at 10:37 PM, Marek Vasut <marex@denx.de> wrote:
> Dear Tomas Hlavacek,
>
>> Hello Marek,
>>
>> On Sun, Aug 12, 2012 at 1:16 AM, Marek Vasut <marex@denx.de> wrote:
>> > So ... we should aim for firing up the real mallocator as soon as
>> > possible and maybe implement discontigmem (sparsemem) into it, so we
>> > don't have to bother with relocating pointers maybe?
>> >
>> > The only problem I see is platforms where the memory disappears.
>>
>> I doubt that on ARM for instance you can set off real mallocator that
>> early without completely rewriting it.
>
> Esp. on ARM, I won't see much of a problem. You usually have some small SRAM
> where such allocator could run.
>
>> The idea of having one complex
>> mallocator working in the same manner in board_init_f and board_init_r
>> stages, being able to operate on all platforms using their nifty
>> memory-management/model features
>
> Do you need them? You usually need only a piece of RW memory.
>
>> and being seamless to users is really
>> tempting. But do we need/want to introduce such deep rewrites?
>
> Deep rewrites? You'd only need to implement sparsemem into it, which might be
> list of RW memory areas instead of one memory area.
>

OK, stop right there (please) - This gets into a highly architecturally
specific implementations of malloc. Let's not go there OK :)

>> What
>> would be the justification? I would say we should stick with the
>> Wolfgang's opinion: Create small and efficient early_malloc for DM and
>> prepare it for future extensions and possible reuses.
>
> dm_malloc you mean? I'm not happy about it, maybe Graeme can pour in some crazy
> juice in our direction again?

I don't like the idea of dm_malloc() either, but it may be the only way to
get this past Wolfgang in the initial pass...

>> >> Switching the focus back to DM, I really would like to ask to delay
>> >> alls uch activities until DM has been done (or at least has stabilized
>> >> so far that we can affort the luxury of thinking about the next
>> >> version with fancy extensions).
>> >
>> > We still need to handle the pre-reloc drivers somehow, you know ... but I
>> > still believe we can pull the DM internals in three people and leave
>> > Thomas to do proper malloc stuff ...
>>
>> Yes, this is the main question: Should I hack malloc() function or
>> does it make sense to have both early_malloc() and malloc() exposed to
>> DM cores/drivers?
>
> This is indeed the main question -- ideas ?
>
>> The first is better from the point of view of drivers - when you ask
>> for memory, you get it. But you have to check yourself whether you
>> need to relocate your pointers or not, though we can provide
>> "relocation chain" you can register your relocation routine into to
>> facilitate it. The later makes sense because this makes it explicit
>> that whenever you use early_malloc() you are responsible for
>> relocating your data on your own (again, we can provide some facility
>> for ir).

And there is the crux of it. Two failure scenarios:

 1) Write a driver which uses malloc() and fail to implement a relocation
    helper - Driver blows up after relocation

 2) Write a driver using malloc() which you never thought to use prior to
    relocation and it blows up because someone used it pre-relocation or
    in SPL and didn't convert it to use early_malloc()

Neither can be picked up by at build time...

>> There is a third path possible: We can provide early_malloc() and say
>> wrapped_malloc() which can be the third function "give me memory, I do
>> not care whether it is early or not". So drivers and/or DM can choose
>> to use malloc routines working in early-only, late-only or both.

Third path is dm_malloc() - Although ugly, it has a few nicities...

 1) It wraps malloc() and early_malloc() around a gd->flags & GD_FLG_RELOC
    test
 2) We can pass a pointer to a driver_core struct (or whatever struct it
    is that holds the 'reloc' helper function pointer). We can't pick up
    misuse at compile time, but dm_malloc() can print a meaningful message
    if it is called pre-relocation with no relocation function. (We should
    add a flag to indicate that no relocation helper is required which may
    be the case for very simple drivers)
 3) We can see right away when driver developers forget to use it
 4) It will (hopefully) get past Wolfgang
 5) It can be implemented 'right now'
 6) We can always come back later and replace it since the usage will be
    consistent

So my vote would be for:

void *early_malloc(size_t bytes)
{
   ...blah...
}

void *dm_malloc(struct driver_core *drv, size_t bytes)
{
  if (gd->flags & GD_FLG_RELOC) {
    return malloc(bytes);
  } else {
    if (!drv->reloc && !(drv->flags & NO_RELOC_FUNC))
      puts("ARRRRRGGGGGG - Early malloc with no reloc function!!!!");
    return early_malloc(bytes);
  }
}

Let's leave it at that for the time being - my other thought of registering
ealry_malloc relocation helpers can wait until someone other than DM needs
to use early_malloc(). Until then, DM can deal with managing the calls to
the relocation functions.

Hows that sound?

Regards,

Graeme

[U-Boot] Early malloc() summary

[Marek Vasut]

Dear Graeme Russ,

> Hi Marek,
> 
> On Tue, Aug 14, 2012 at 10:37 PM, Marek Vasut <marex@denx.de> wrote:
> > Dear Tomas Hlavacek,
> > 
> >> Hello Marek,
> >> 
> >> On Sun, Aug 12, 2012 at 1:16 AM, Marek Vasut <marex@denx.de> wrote:
> >> > So ... we should aim for firing up the real mallocator as soon as
> >> > possible and maybe implement discontigmem (sparsemem) into it, so we
> >> > don't have to bother with relocating pointers maybe?
> >> > 
> >> > The only problem I see is platforms where the memory disappears.
> >> 
> >> I doubt that on ARM for instance you can set off real mallocator that
> >> early without completely rewriting it.
> > 
> > Esp. on ARM, I won't see much of a problem. You usually have some small
> > SRAM where such allocator could run.
> > 
> >> The idea of having one complex
> >> mallocator working in the same manner in board_init_f and board_init_r
> >> stages, being able to operate on all platforms using their nifty
> >> memory-management/model features
> > 
> > Do you need them? You usually need only a piece of RW memory.
> > 
> >> and being seamless to users is really
> >> tempting. But do we need/want to introduce such deep rewrites?
> > 
> > Deep rewrites? You'd only need to implement sparsemem into it, which
> > might be list of RW memory areas instead of one memory area.
> 
> OK, stop right there (please) - This gets into a highly architecturally
> specific implementations of malloc. Let's not go there OK :)

Not really, today you give the mallocator one slab of memory on which it 
operates ... making it so it'd operate on a list of such slabs shouldn't be 
_that_ hard.

> >> What
> >> would be the justification? I would say we should stick with the
> >> Wolfgang's opinion: Create small and efficient early_malloc for DM and
> >> prepare it for future extensions and possible reuses.
> > 
> > dm_malloc you mean? I'm not happy about it, maybe Graeme can pour in some
> > crazy juice in our direction again?
> 
> I don't like the idea of dm_malloc() either, but it may be the only way to
> get this past Wolfgang in the initial pass...

Hehe >:-)

> >> >> Switching the focus back to DM, I really would like to ask to delay
> >> >> alls uch activities until DM has been done (or at least has
> >> >> stabilized so far that we can affort the luxury of thinking about
> >> >> the next version with fancy extensions).
> >> > 
> >> > We still need to handle the pre-reloc drivers somehow, you know ...
> >> > but I still believe we can pull the DM internals in three people and
> >> > leave Thomas to do proper malloc stuff ...
> >> 
> >> Yes, this is the main question: Should I hack malloc() function or
> >> does it make sense to have both early_malloc() and malloc() exposed to
> >> DM cores/drivers?
> > 
> > This is indeed the main question -- ideas ?
> > 
> >> The first is better from the point of view of drivers - when you ask
> >> for memory, you get it. But you have to check yourself whether you
> >> need to relocate your pointers or not, though we can provide
> >> "relocation chain" you can register your relocation routine into to
> >> facilitate it. The later makes sense because this makes it explicit
> >> that whenever you use early_malloc() you are responsible for
> >> relocating your data on your own (again, we can provide some facility
> >> for ir).
> 
> And there is the crux of it. Two failure scenarios:
> 
>  1) Write a driver which uses malloc() and fail to implement a relocation
>     helper - Driver blows up after relocation
> 
>  2) Write a driver using malloc() which you never thought to use prior to
>     relocation and it blows up because someone used it pre-relocation or
>     in SPL and didn't convert it to use early_malloc()
> 
> Neither can be picked up by at build time...

Yes.

> >> There is a third path possible: We can provide early_malloc() and say
> >> wrapped_malloc() which can be the third function "give me memory, I do
> >> not care whether it is early or not". So drivers and/or DM can choose
> >> to use malloc routines working in early-only, late-only or both.
> 
> Third path is dm_malloc() - Although ugly, it has a few nicities...
> 
>  1) It wraps malloc() and early_malloc() around a gd->flags & GD_FLG_RELOC
>     test
>  2) We can pass a pointer to a driver_core struct (or whatever struct it
>     is that holds the 'reloc' helper function pointer). We can't pick up
>     misuse at compile time, but dm_malloc() can print a meaningful message
>     if it is called pre-relocation with no relocation function. (We should
>     add a flag to indicate that no relocation helper is required which may
>     be the case for very simple drivers)
>  3) We can see right away when driver developers forget to use it
>  4) It will (hopefully) get past Wolfgang

:-D

>  5) It can be implemented 'right now'
>  6) We can always come back later and replace it since the usage will be
>     consistent
> 
> So my vote would be for:
> 
> void *early_malloc(size_t bytes)
> {
>    ...blah...
> }
> 
> void *dm_malloc(struct driver_core *drv, size_t bytes)
> {
>   if (gd->flags & GD_FLG_RELOC) {
>     return malloc(bytes);
>   } else {
>     if (!drv->reloc && !(drv->flags & NO_RELOC_FUNC))
>       puts("ARRRRRGGGGGG - Early malloc with no reloc function!!!!");
>     return early_malloc(bytes);
>   }
> }
> 
> Let's leave it at that for the time being - my other thought of registering
> ealry_malloc relocation helpers can wait until someone other than DM needs
> to use early_malloc(). Until then, DM can deal with managing the calls to
> the relocation functions.

Let's wait for Thomas on that ... I'm fine with anything that works ;-)

> Hows that sound?
> 
> Regards,
> 
> Graeme

[U-Boot] Early malloc() summary

[Marek Vasut]

Dear Albert ARIBAUD,

> Hi Marek,
> 
> On Tue, 14 Aug 2012 14:37:29 +0200, Marek Vasut <marex@denx.de> wrote:
> > Dear Tomas Hlavacek,
> > 
> > > Hello Marek,
> > > 
> > > On Sun, Aug 12, 2012 at 1:16 AM, Marek Vasut <marex@denx.de> wrote:
> > > > So ... we should aim for firing up the real mallocator as soon as
> > > > possible and maybe implement discontigmem (sparsemem) into it, so
> > > > we don't have to bother with relocating pointers maybe?
> > > > 
> > > > The only problem I see is platforms where the memory disappears.
> > > 
> > > I doubt that on ARM for instance you can set off real mallocator
> > > that early without completely rewriting it.
> > 
> > Esp. on ARM, I won't see much of a problem. You usually have some
> > small SRAM where such allocator could run.
> 
> ... or not; for instance, orion5x / edminiv2 does not have such SRAM. So
> how do we handle this there?

Lock cachelines on top of RAM and make some ... indeed, I mentioned it somewhere 
in this thread before that there are such devices.

But in case we lock cachelines, then start DRAM underneath, can we somehow 
(painlessly) trigger writeback of the data back into DRAM so we can unlock the 
cache?

> Amicalement,

Best regards,
Marek Vasut

[U-Boot] Early malloc() summary

[Marek Vasut]

Dear Graeme Russ,

[...]

> 
> Third path is dm_malloc() - Although ugly, it has a few nicities...

Thinking about dm_malloc() ... if it's entirely different, the semantics can be 
adjusted too ... say to "int dm_malloc(void **ptr, size_t size);":

- return int: error code
- **ptr: pointer to allocated memory, that way we can possibly implement pointer 
tracking (of course that'd need more work, might be a debug feature)
- size: size of allocated area

Of course that'd need -- in case you'd copy pointers -- another function to do 
so. etc etc.

[...]

off and out.

Best regards,
Marek Vasut

[U-Boot] Early malloc() summary

[Tomas Hlavacek]

On Tue, Aug 14, 2012 at 3:54 PM, Graeme Russ <graeme.russ@gmail.com> wrote:

>> dm_malloc you mean? I'm not happy about it, maybe Graeme can pour in some crazy
>> juice in our direction again?
>
> I don't like the idea of dm_malloc() either, but it may be the only way to
> get this past Wolfgang in the initial pass...

I agree, I am going to do it like that.

>>> Yes, this is the main question: Should I hack malloc() function or
>>> does it make sense to have both early_malloc() and malloc() exposed to
>>> DM cores/drivers?
>>
>> This is indeed the main question -- ideas ?
>>
>>> The first is better from the point of view of drivers - when you ask
>>> for memory, you get it. But you have to check yourself whether you
>>> need to relocate your pointers or not, though we can provide
>>> "relocation chain" you can register your relocation routine into to
>>> facilitate it. The later makes sense because this makes it explicit
>>> that whenever you use early_malloc() you are responsible for
>>> relocating your data on your own (again, we can provide some facility
>>> for ir).
>
> And there is the crux of it. Two failure scenarios:
>
>  1) Write a driver which uses malloc() and fail to implement a relocation
>     helper - Driver blows up after relocation
>
>  2) Write a driver using malloc() which you never thought to use prior to
>     relocation and it blows up because someone used it pre-relocation or
>     in SPL and didn't convert it to use early_malloc()
>
> Neither can be picked up by at build time...
>
>>> There is a third path possible: We can provide early_malloc() and say
>>> wrapped_malloc() which can be the third function "give me memory, I do
>>> not care whether it is early or not". So drivers and/or DM can choose
>>> to use malloc routines working in early-only, late-only or both.
>
> Third path is dm_malloc() - Although ugly, it has a few nicities...
>
>  1) It wraps malloc() and early_malloc() around a gd->flags & GD_FLG_RELOC
>     test
>  2) We can pass a pointer to a driver_core struct (or whatever struct it
>     is that holds the 'reloc' helper function pointer). We can't pick up
>     misuse at compile time, but dm_malloc() can print a meaningful message
>     if it is called pre-relocation with no relocation function. (We should
>     add a flag to indicate that no relocation helper is required which may
>     be the case for very simple drivers)

Yes, but it would prevent using dm_malloc(size_t size, driver *drv)
for one-time buffers inside helper functions - strdup() for instance,
inside drivers in early stage. In that case we need
dm_malloc_nocheck(size_t size) or we need to pass a pointer to the
driver structure to each and every function call in driver which might
want to call dm_malloc. Both seems impractical to me.

>  3) We can see right away when driver developers forget to use it

Yes. And I could add a debug check into malloc() to verify we have the
flag GD_FLG_RELOC set and yell when it is not.

>
> Let's leave it at that for the time being - my other thought of registering
> early_malloc relocation helpers can wait until someone other than DM needs
> to use early_malloc(). Until then, DM can deal with managing the calls to
> the relocation functions.

I think so. We can connect the DM function into the relocation chain
when it is needed.

Thanks,
Tomas


-- 
Tom?? Hlav??ek <tmshlvck@gmail.com>

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi Marek,

On 08/15/2012 12:00 AM, Marek Vasut wrote:
> Dear Graeme Russ,
> 
>> Hi Marek,
>>
>> On Tue, Aug 14, 2012 at 10:37 PM, Marek Vasut <marex@denx.de> wrote:
>>> Dear Tomas Hlavacek,
>>>
>>>> Hello Marek,
>>>>
>>>> On Sun, Aug 12, 2012 at 1:16 AM, Marek Vasut <marex@denx.de> wrote:
>>>>> So ... we should aim for firing up the real mallocator as soon as
>>>>> possible and maybe implement discontigmem (sparsemem) into it, so we
>>>>> don't have to bother with relocating pointers maybe?
>>>>>
>>>>> The only problem I see is platforms where the memory disappears.
>>>>
>>>> I doubt that on ARM for instance you can set off real mallocator that
>>>> early without completely rewriting it.
>>>
>>> Esp. on ARM, I won't see much of a problem. You usually have some small
>>> SRAM where such allocator could run.
>>>
>>>> The idea of having one complex
>>>> mallocator working in the same manner in board_init_f and board_init_r
>>>> stages, being able to operate on all platforms using their nifty
>>>> memory-management/model features
>>>
>>> Do you need them? You usually need only a piece of RW memory.
>>>
>>>> and being seamless to users is really
>>>> tempting. But do we need/want to introduce such deep rewrites?
>>>
>>> Deep rewrites? You'd only need to implement sparsemem into it, which
>>> might be list of RW memory areas instead of one memory area.
>>
>> OK, stop right there (please) - This gets into a highly architecturally
>> specific implementations of malloc. Let's not go there OK :)
> 
> Not really, today you give the mallocator one slab of memory on which it 
> operates ... making it so it'd operate on a list of such slabs shouldn't be 
> _that_ hard.

When you start throwing around "discontigmem", "sparsemem" and "nifty
memory-management/model features" you are talking architecture specifics

Regards,

Graeme

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi Marek,

On 08/15/2012 09:56 AM, Marek Vasut wrote:
> Dear Graeme Russ,
> 
> [...]
> 
>>
>> Third path is dm_malloc() - Although ugly, it has a few nicities...
> 
> Thinking about dm_malloc() ... if it's entirely different, the semantics can be 
> adjusted too ... say to "int dm_malloc(void **ptr, size_t size);":
> 
> - return int: error code
> - **ptr: pointer to allocated memory, that way we can possibly implement pointer 
> tracking (of course that'd need more work, might be a debug feature)
> - size: size of allocated area

I think we should keep the semantics as close as possible to malloc(). If
there is an error, return NULL. For starters, if we do later go with a
common malloc() which gets wrapped, changing the code will be a lot easier.

Regards,

Graeme

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi Tomas,

On 08/15/2012 10:00 PM, Tomas Hlavacek wrote:
> On Tue, Aug 14, 2012 at 3:54 PM, Graeme Russ <graeme.russ@gmail.com> wrote:
> 
>>> dm_malloc you mean? I'm not happy about it, maybe Graeme can pour in some crazy
>>> juice in our direction again?
>>
>> I don't like the idea of dm_malloc() either, but it may be the only way to
>> get this past Wolfgang in the initial pass...
> 
> I agree, I am going to do it like that.

Progress :)

>>>> Yes, this is the main question: Should I hack malloc() function or
>>>> does it make sense to have both early_malloc() and malloc() exposed to
>>>> DM cores/drivers?
>>>
>>> This is indeed the main question -- ideas ?
>>>
>>>> The first is better from the point of view of drivers - when you ask
>>>> for memory, you get it. But you have to check yourself whether you
>>>> need to relocate your pointers or not, though we can provide
>>>> "relocation chain" you can register your relocation routine into to
>>>> facilitate it. The later makes sense because this makes it explicit
>>>> that whenever you use early_malloc() you are responsible for
>>>> relocating your data on your own (again, we can provide some facility
>>>> for ir).
>>
>> And there is the crux of it. Two failure scenarios:
>>
>>  1) Write a driver which uses malloc() and fail to implement a relocation
>>     helper - Driver blows up after relocation
>>
>>  2) Write a driver using malloc() which you never thought to use prior to
>>     relocation and it blows up because someone used it pre-relocation or
>>     in SPL and didn't convert it to use early_malloc()
>>
>> Neither can be picked up by at build time...
>>
>>>> There is a third path possible: We can provide early_malloc() and say
>>>> wrapped_malloc() which can be the third function "give me memory, I do
>>>> not care whether it is early or not". So drivers and/or DM can choose
>>>> to use malloc routines working in early-only, late-only or both.
>>
>> Third path is dm_malloc() - Although ugly, it has a few nicities...
>>
>>  1) It wraps malloc() and early_malloc() around a gd->flags & GD_FLG_RELOC
>>     test
>>  2) We can pass a pointer to a driver_core struct (or whatever struct it
>>     is that holds the 'reloc' helper function pointer). We can't pick up
>>     misuse at compile time, but dm_malloc() can print a meaningful message
>>     if it is called pre-relocation with no relocation function. (We should
>>     add a flag to indicate that no relocation helper is required which may
>>     be the case for very simple drivers)
> 
> Yes, but it would prevent using dm_malloc(size_t size, driver *drv)
> for one-time buffers inside helper functions - strdup() for instance,

Hmm, I hadn't thought of that

> inside drivers in early stage. In that case we need
> dm_malloc_nocheck(size_t size) or we need to pass a pointer to the
> driver structure to each and every function call in driver which might
> want to call dm_malloc. Both seems impractical to me.

maybe something along the lines of:

static void *pre_reloc_malloc(size_t bytes)
{
  ...do magic...
  return pointer to malloc'd memory
}

void *early_malloc(size_t bytes, int (*reloc_helper)(void *))
{
  if (reloc_helper) {
    /*
     * Maybe one day we will register reloc_helper (if not already
     * registered). But for now, driver core will manage that
     */
  }

   return pre_reloc_malloc(bytes)
}

void *dm_malloc(struct driver_core *drv, size_t bytes)
{
  if (gd->flags & GD_FLG_RELOC) {
    return malloc(bytes);
  } else {
    if (!drv) {
      debug("dm_malloc requires a driver pointer!!!");
      return NULL;
    }

    /*
     * DM core deals with driver reloc functions, but we check
     * anyway
     */
    if (!drv->reloc && !(drv->flags & NO_RELOC_FUNC))
      debug("Early malloc with no reloc function!!!!");

    /*
     * One day this might be:
     *   return early_malloc(bytes, drv->reloc);
     * and the early malloc infrastructure will call all the
     * relocation helpers. But for now, driver core will be...
     */
    return early_malloc(bytes, dm_core_reloc);
  }
}

>>  3) We can see right away when driver developers forget to use it
> 
> Yes. And I could add a debug check into malloc() to verify we have the
> flag GD_FLG_RELOC set and yell when it is not.


If you want to do this, do so in a separate patch so it can be (n)ack'd
separately

>> Let's leave it at that for the time being - my other thought of registering
>> early_malloc relocation helpers can wait until someone other than DM needs
>> to use early_malloc(). Until then, DM can deal with managing the calls to
>> the relocation functions.
> 
> I think so. We can connect the DM function into the relocation chain
> when it is needed.

Regards,

Graeme

[U-Boot] Early malloc() summary

[Marek Vasut]

Dear Graeme Russ,

[...]

> >>  2) We can pass a pointer to a driver_core struct (or whatever struct it
> >>  
> >>     is that holds the 'reloc' helper function pointer). We can't pick up
> >>     misuse at compile time, but dm_malloc() can print a meaningful
> >>     message if it is called pre-relocation with no relocation function.
> >>     (We should add a flag to indicate that no relocation helper is
> >>     required which may be the case for very simple drivers)
> > 
> > Yes, but it would prevent using dm_malloc(size_t size, driver *drv)
> > for one-time buffers inside helper functions - strdup() for instance,
> 
> Hmm, I hadn't thought of that

So, we're back to square 1 ?

[...]

Best regards,
Marek Vasut

[U-Boot] Early malloc() summary

[Marek Vasut]

Dear Graeme Russ,

> Hi Marek,
> 
> On 08/15/2012 12:00 AM, Marek Vasut wrote:
> > Dear Graeme Russ,
> > 
> >> Hi Marek,
> >> 
> >> On Tue, Aug 14, 2012 at 10:37 PM, Marek Vasut <marex@denx.de> wrote:
> >>> Dear Tomas Hlavacek,
> >>> 
> >>>> Hello Marek,
> >>>> 
> >>>> On Sun, Aug 12, 2012 at 1:16 AM, Marek Vasut <marex@denx.de> wrote:
> >>>>> So ... we should aim for firing up the real mallocator as soon as
> >>>>> possible and maybe implement discontigmem (sparsemem) into it, so we
> >>>>> don't have to bother with relocating pointers maybe?
> >>>>> 
> >>>>> The only problem I see is platforms where the memory disappears.
> >>>> 
> >>>> I doubt that on ARM for instance you can set off real mallocator that
> >>>> early without completely rewriting it.
> >>> 
> >>> Esp. on ARM, I won't see much of a problem. You usually have some small
> >>> SRAM where such allocator could run.
> >>> 
> >>>> The idea of having one complex
> >>>> mallocator working in the same manner in board_init_f and board_init_r
> >>>> stages, being able to operate on all platforms using their nifty
> >>>> memory-management/model features
> >>> 
> >>> Do you need them? You usually need only a piece of RW memory.
> >>> 
> >>>> and being seamless to users is really
> >>>> tempting. But do we need/want to introduce such deep rewrites?
> >>> 
> >>> Deep rewrites? You'd only need to implement sparsemem into it, which
> >>> might be list of RW memory areas instead of one memory area.
> >> 
> >> OK, stop right there (please) - This gets into a highly architecturally
> >> specific implementations of malloc. Let's not go there OK :)
> > 
> > Not really, today you give the mallocator one slab of memory on which it
> > operates ... making it so it'd operate on a list of such slabs shouldn't
> > be _that_ hard.
> 
> When you start throwing around "discontigmem", "sparsemem" and "nifty
> memory-management/model features" you are talking architecture specifics

In uboot, not so much ... in uboot it'd be just a matter of making one memory 
are that's currently available to malloc() into list of memory areas and that's 
all. Not specific at all


Best regards,
Marek Vasut

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi Marek,

On Fri, Aug 17, 2012 at 12:50 AM, Marek Vasut <marex@denx.de> wrote:
> Dear Graeme Russ,
>
> [...]
>
>> >>  2) We can pass a pointer to a driver_core struct (or whatever struct it
>> >>
>> >>     is that holds the 'reloc' helper function pointer). We can't pick up
>> >>     misuse at compile time, but dm_malloc() can print a meaningful
>> >>     message if it is called pre-relocation with no relocation function.
>> >>     (We should add a flag to indicate that no relocation helper is
>> >>     required which may be the case for very simple drivers)
>> >
>> > Yes, but it would prevent using dm_malloc(size_t size, driver *drv)
>> > for one-time buffers inside helper functions - strdup() for instance,
>>
>> Hmm, I hadn't thought of that
>
> So, we're back to square 1 ?

Nope - just a slight tweak is all

Regards,

Graeme

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi Marek,

On Fri, Aug 17, 2012 at 12:52 AM, Marek Vasut <marek.vasut@gmail.com> wrote:
> Dear Graeme Russ,
>

[snip]

>> When you start throwing around "discontigmem", "sparsemem" and "nifty
>> memory-management/model features" you are talking architecture specifics
>
> In uboot, not so much ... in uboot it'd be just a matter of making one memory
> are that's currently available to malloc() into list of memory areas and that's
> all. Not specific at all

Oh, I thought you were talking about having the early heap map to the
same location of the heap post-relocation by using MMUs or cache-line
mapping

If all you are talking about is discontiguous blocks of heap, I
already put a proposal forward for that

Regards,

Graeme

[U-Boot] Early malloc() summary

[Marek Vasut]

Dear Graeme Russ,

> Hi Marek,
> 
> On Fri, Aug 17, 2012 at 12:50 AM, Marek Vasut <marex@denx.de> wrote:
> > Dear Graeme Russ,
> > 
> > [...]
> > 
> >> >>  2) We can pass a pointer to a driver_core struct (or whatever struct
> >> >>  it
> >> >>  
> >> >>     is that holds the 'reloc' helper function pointer). We can't pick
> >> >>     up misuse at compile time, but dm_malloc() can print a
> >> >>     meaningful message if it is called pre-relocation with no
> >> >>     relocation function. (We should add a flag to indicate that no
> >> >>     relocation helper is required which may be the case for very
> >> >>     simple drivers)
> >> > 
> >> > Yes, but it would prevent using dm_malloc(size_t size, driver *drv)
> >> > for one-time buffers inside helper functions - strdup() for instance,
> >> 
> >> Hmm, I hadn't thought of that
> > 
> > So, we're back to square 1 ?
> 
> Nope - just a slight tweak is all

What tweak ?

> Regards,
> 
> Graeme

Best regards,
Marek Vasut

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi Marek,

On Fri, Aug 17, 2012 at 9:32 AM, Marek Vasut <marek.vasut@gmail.com> wrote:
> Dear Graeme Russ,
>

>> >> Hmm, I hadn't thought of that
>> >
>> > So, we're back to square 1 ?
>>
>> Nope - just a slight tweak is all
>
> What tweak ?

Didn't you read the rest of my email?

Regards,

Graeme

[U-Boot] Early malloc() summary

[Marek Vasut]

Dear Graeme Russ,

> Hi Marek,
> 
> On Fri, Aug 17, 2012 at 9:32 AM, Marek Vasut <marek.vasut@gmail.com> wrote:
> > Dear Graeme Russ,
> > 
> >> >> Hmm, I hadn't thought of that
> >> > 
> >> > So, we're back to square 1 ?
> >> 
> >> Nope - just a slight tweak is all
> > 
> > What tweak ?
> 
> Didn't you read the rest of my email?

No :-)

So every strdup will need a driver associated with it ?

> Regards,
> 
> Graeme

Best regards,
Marek Vasut

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi Marek,

On Fri, Aug 17, 2012 at 10:34 AM, Marek Vasut <marek.vasut@gmail.com> wrote:
> Dear Graeme Russ,
>
>> Hi Marek,
>>
>> On Fri, Aug 17, 2012 at 9:32 AM, Marek Vasut <marek.vasut@gmail.com> wrote:
>> > Dear Graeme Russ,
>> >
>> >> >> Hmm, I hadn't thought of that
>> >> >
>> >> > So, we're back to square 1 ?
>> >>
>> >> Nope - just a slight tweak is all
>> >
>> > What tweak ?
>>
>> Didn't you read the rest of my email?
>
> No :-)
>
> So every strdup will need a driver associated with it ?

No...

dm_malloc(bytes, driver *)
  |
  +-> early_malloc(bytes, reloc_helper *)  /* Pre-Relocation */
  |     |
  |     +->register_helper(reloc_helper *)
  |     |
  |     +->pre_reloc_malloc(size_t bytes)
  |
  +-> malloc(bytes)                        /* Post-Relocation */


Drivers call dm_malloc(), helper functions call early_malloc()

dm_malloc() is implemented in the DM core code and checks for whether the
call is pre- or post- relocation. If pre-relocation, it checks for the
driver having a relocation helper (or the 'I don't need one' flag)

early_malloc() is implemented in the early malloc code seperate from the
DM code.

**** WARNING!!! STOP READING NOW!!! ****

early_malloc() registers a relocation function (if provided) which will be
called during relocation. DM core will strip this out as it will (for the
time being) handle the calling of the relocation helper for each of the
registered drivers. In the long term, I think that responsibility might be
able to be taken away from DM core (but there may be call-order issues that
might make that impossible)

The way I imagine it in the future, any code that might possible allocate
memory prior to relocation would do something like:

static int my_relocator(void *data)
{
  struct foo *new_bar;

  new_bar = malloc(sizeof(struct foo));
  mem_cpy(new_bar, data, sizeof(struct foo));

  /* Tweak internal new_bar members */

  return 0;
}

int some_function()
{
  struct foo *bar;

  bar = malloc(sizeof(struct foo));
  register_helper(bar, my_relocator);

  return 0;
}


And behind the scenes we have:

data = malloc(bytes);
          |
          +->data = pre_reloc_malloc(size_t bytes)   /* Pre-Relocation */
          |     |
          |     +->add_to_reloc_list(data)
          |     |
          |     +->return data;
          |
          +->malloc(size_t bytes);                   /* Post-Relocation */

register_helper(data, reloc_helper *)
          |
          +->update_reloc_list(data, reloc_helper *) /* Pre-Relocation */
          |
          +->Do Nothing                              /* Post-Relocation */

During relocation, the 'reloc list' is processed. Each 'data' entry with no
'reloc_helper' will elicite a (debug) warning to let you know about data
that was allocated but will not be relocated.

Regards,

Graeme

[U-Boot] Early malloc() summary

[Tomas Hlavacek]

Hello Graeme!

On Fri, Aug 17, 2012 at 3:15 AM, Graeme Russ <graeme.russ@gmail.com> wrote:
> dm_malloc(bytes, driver *)
>   |
>   +-> early_malloc(bytes, reloc_helper *)  /* Pre-Relocation */
>   |     |
>   |     +->register_helper(reloc_helper *)
>   |     |
>   |     +->pre_reloc_malloc(size_t bytes)
>   |
>   +-> malloc(bytes)                        /* Post-Relocation */
>
>
> Drivers call dm_malloc(), helper functions call early_malloc()
>
> dm_malloc() is implemented in the DM core code and checks for whether the
> call is pre- or post- relocation. If pre-relocation, it checks for the
> driver having a relocation helper (or the 'I don't need one' flag)
>
> early_malloc() is implemented in the early malloc code seperate from the
> DM code.
>
> **** WARNING!!! STOP READING NOW!!! ****
>
> early_malloc() registers a relocation function (if provided) which will be
> called during relocation. DM core will strip this out as it will (for the
> time being) handle the calling of the relocation helper for each of the
> registered drivers. In the long term, I think that responsibility might be
> able to be taken away from DM core (but there may be call-order issues that
> might make that impossible)
>
> The way I imagine it in the future, any code that might possible allocate
> memory prior to relocation would do something like:
>
> static int my_relocator(void *data)
> {
>   struct foo *new_bar;
>
>   new_bar = malloc(sizeof(struct foo));
>   mem_cpy(new_bar, data, sizeof(struct foo));
>
>   /* Tweak internal new_bar members */
>
>   return 0;
> }
>
> int some_function()
> {
>   struct foo *bar;
>
>   bar = malloc(sizeof(struct foo));
>   register_helper(bar, my_relocator);
>
>   return 0;
> }
>
>
> And behind the scenes we have:
>
> data = malloc(bytes);
>           |
>           +->data = pre_reloc_malloc(size_t bytes)   /* Pre-Relocation */
>           |     |
>           |     +->add_to_reloc_list(data)
>           |     |
>           |     +->return data;
>           |
>           +->malloc(size_t bytes);                   /* Post-Relocation */
>
> register_helper(data, reloc_helper *)
>           |
>           +->update_reloc_list(data, reloc_helper *) /* Pre-Relocation */
>           |
>           +->Do Nothing                              /* Post-Relocation */
>
> During relocation, the 'reloc list' is processed. Each 'data' entry with no
> 'reloc_helper' will elicite a (debug) warning to let you know about data
> that was allocated but will not be relocated.

OK, I got this. It seems to me that everything starts with
pre_reloc_malloc(). And I think that this is roughly equivalent to my
void *early_malloc(size_t) function in previous experimental patches.
But I am not sure that the identifier pre_reloc_malloc() is proper for
this function because on archs without strict separation of
board_init_f and board_init_r, where the U-Boot is running in RAM from
the very beginning and no relocation is needed (microblaze, nios2,
openrisc, sh) it does not reflect the actual use - it is the function
used to obtain allocation from early_heap. And I think that in case of
that architectures we still need early_heap and working dm_malloc()
before the true malloc() is initialized. (It is because we might still
need to create the DM tree before malloc is initialized to facilitate
DM part of actual memory and malloc initialization.)

I am thinking about a way to obtain some space for the first
early_heap (assuming that I have the heap header you suggested some
time ago that has void *next_early_heap for future expansion with
arch-specific or CPU/board-specific ways to grab non-contiguous
early_heap). Do you know some elegant way to obtain some early_heap
space that would work on each architectures in question? It came to my
mind that I can steal the space from the early stack by something like
this:

#define DECLARE_EARLY_HEAP_ON_STACK char
__early_heap[CONFIG_SYS_EARLY_HEAP_SIZE]; \
					gd->early_heap_first = (void *)__early_heap

void board_init_f()
{
...
memset(gd) here
...
DECLARE_EARLY_HEAP_ON_STACK;

Although it is somehow architecture independent (except the fact that
we need sensible value of CONFIG_SYS_EARLY_HEAP_SIZE and it is perhaps
not feasible for x86 which has 3 init stages - board_init_f,
board_init_f_r and board_init_r, the stack is lost in between
board_init_f and board_init_f_r, but true malloc() is initialized as
late as in board_init_r, if I understand it well), but I am not sure
whether it is acceptable way to grab early_heap space like that.

My intention is to keep the prospective patch with early_heap and
pre_reloc_malloc() relatively low-profile and do it without
unnecessary architecture/CPU/ board specific code when possible.
Anyway I think we are going to need only as low as 20B of early_heap
for the root DM node on wast majority boards and therefore we could go
forward with really small early_heap in the beginning.

What do you think?

Tomas


-- 
Tom?? Hlav??ek <tmshlvck@gmail.com>

[U-Boot] Early malloc() summary

[Graeme Russ]

Hi Tomas,

On Sun, Aug 19, 2012 at 11:21 PM, Tomas Hlavacek <tmshlvck@gmail.com> wrote:
> Hello Graeme!
>
> On Fri, Aug 17, 2012 at 3:15 AM, Graeme Russ <graeme.russ@gmail.com> wrote:
>> dm_malloc(bytes, driver *)
>>   |
>>   +-> early_malloc(bytes, reloc_helper *)  /* Pre-Relocation */
>>   |     |
>>   |     +->register_helper(reloc_helper *)
>>   |     |
>>   |     +->pre_reloc_malloc(size_t bytes)
>>   |
>>   +-> malloc(bytes)                        /* Post-Relocation */
>>
>>
>> Drivers call dm_malloc(), helper functions call early_malloc()
>>
>> dm_malloc() is implemented in the DM core code and checks for whether the
>> call is pre- or post- relocation. If pre-relocation, it checks for the
>> driver having a relocation helper (or the 'I don't need one' flag)
>>
>> early_malloc() is implemented in the early malloc code seperate from the
>> DM code.
>>
>> **** WARNING!!! STOP READING NOW!!! ****
>>
>> early_malloc() registers a relocation function (if provided) which will be
>> called during relocation. DM core will strip this out as it will (for the
>> time being) handle the calling of the relocation helper for each of the
>> registered drivers. In the long term, I think that responsibility might be
>> able to be taken away from DM core (but there may be call-order issues that
>> might make that impossible)
>>
>> The way I imagine it in the future, any code that might possible allocate
>> memory prior to relocation would do something like:
>>
>> static int my_relocator(void *data)
>> {
>>   struct foo *new_bar;
>>
>>   new_bar = malloc(sizeof(struct foo));
>>   mem_cpy(new_bar, data, sizeof(struct foo));
>>
>>   /* Tweak internal new_bar members */
>>
>>   return 0;
>> }
>>
>> int some_function()
>> {
>>   struct foo *bar;
>>
>>   bar = malloc(sizeof(struct foo));
>>   register_helper(bar, my_relocator);
>>
>>   return 0;
>> }
>>
>>
>> And behind the scenes we have:
>>
>> data = malloc(bytes);
>>           |
>>           +->data = pre_reloc_malloc(size_t bytes)   /* Pre-Relocation */
>>           |     |
>>           |     +->add_to_reloc_list(data)
>>           |     |
>>           |     +->return data;
>>           |
>>           +->malloc(size_t bytes);                   /* Post-Relocation */
>>
>> register_helper(data, reloc_helper *)
>>           |
>>           +->update_reloc_list(data, reloc_helper *) /* Pre-Relocation */
>>           |
>>           +->Do Nothing                              /* Post-Relocation */
>>
>> During relocation, the 'reloc list' is processed. Each 'data' entry with no
>> 'reloc_helper' will elicite a (debug) warning to let you know about data
>> that was allocated but will not be relocated.
>
> OK, I got this. It seems to me that everything starts with
> pre_reloc_malloc(). And I think that this is roughly equivalent to my
> void *early_malloc(size_t) function in previous experimental patches.

Correct

> But I am not sure that the identifier pre_reloc_malloc() is proper for
> this function because on archs without strict separation of
> board_init_f and board_init_r, where the U-Boot is running in RAM from
> the very beginning and no relocation is needed (microblaze, nios2,
> openrisc, sh) it does not reflect the actual use - it is the function

Good point, which also highlights why wrapping malloc() might be a good
approach. Architectures which already have SDRAM initialised (either by the
Soc's IPL or the board's SPL for example) prior to U-Boot being loaded
should be allowed to initialise the malloc heap 'extremely early' (perhaps
before even console output). In such cases, there would not be a need to
perform any kind of malloc chunk relocations

> used to obtain allocation from early_heap. And I think that in case of
> that architectures we still need early_heap and working dm_malloc()

Yes, but as above, in some cases early heap may be one and the same as
'late' heap

> before the true malloc() is initialized. (It is because we might still
> need to create the DM tree before malloc is initialized to facilitate
> DM part of actual memory and malloc initialization.)

I think it may be a good exercise (later, not now) to look at these 'U-Boot
already running in RAM' cases and see if 'late' malloc can be initialised
before DM...

> I am thinking about a way to obtain some space for the first
> early_heap (assuming that I have the heap header you suggested some
> time ago that has void *next_early_heap for future expansion with
> arch-specific or CPU/board-specific ways to grab non-contiguous
> early_heap). Do you know some elegant way to obtain some early_heap
> space that would work on each architectures in question? It came to my

No - it is very arch specific. Some may allocate from locked cach lines,
others from SRAM - Who knows. That is why I suggested a brk() function
that would do the allocation in the background.

> mind that I can steal the space from the early stack by something like
> this:
>
> #define DECLARE_EARLY_HEAP_ON_STACK char
> __early_heap[CONFIG_SYS_EARLY_HEAP_SIZE]; \
>                                         gd->early_heap_first = (void *)__early_heap
>
> void board_init_f()
> {
> ...
> memset(gd) here
> ...
> DECLARE_EARLY_HEAP_ON_STACK;

Yes, that could be a possibility

> Although it is somehow architecture independent (except the fact that
> we need sensible value of CONFIG_SYS_EARLY_HEAP_SIZE and it is perhaps
> not feasible for x86 which has 3 init stages - board_init_f,
> board_init_f_r and board_init_r, the stack is lost in between
> board_init_f and board_init_f_r, but true malloc() is initialized as
> late as in board_init_r, if I understand it well), but I am not sure

Yes, you understand it well. The init phases for x86 are designed that way
to get caches online as quick as possible. IMNSHO, I think this sequence
should extend to all architectures that initialise SDRAM in board_init_f()
(as opposed to IPL or SPL). board_init_f_r() copies gd to SDRAM, turns on
caches and then relocates U-Boot into SDRAM. It would be trivial to change
that to:

  - init malloc() pool
  - copy gd to SDRAM
  - relocate early malloc pool
  - turn on caches
  - relocate U-Boot

The crux is to keep the early malloc pool as small as possible (or more
specificially, keep the amount which needs to be relocated as small as
possible). That way, the amount of data moved while caches are off is
minimised.

Hmmm... Maybe early_free() could de-register any relocation helper that
has been associated with that block...

> whether it is acceptable way to grab early_heap space like that.

I think it is valid.

> My intention is to keep the prospective patch with early_heap and
> pre_reloc_malloc() relatively low-profile and do it without
> unnecessary architecture/CPU/ board specific code when possible.

Good :)

> Anyway I think we are going to need only as low as 20B of early_heap
> for the root DM node on wast majority boards and therefore we could go
> forward with really small early_heap in the beginning.

You will need as much as is required for each of the drivers that are
initialised early. Some boards may not even need DM early. But this is
not really anything that you need to be concerned about...

> What do you think?

Start by assuming there is some arbitrary amount of memory available to
the early_malloc() core and create the implementation from there. Don't
worry about all my 'relocation helper' stuff (that is the DM core's problem
for now)

We can then investigate, at an arch-specific level, how to create that
block of memory for early_malloc()

Regards,

Graeme