[LinuxBIOS] ELF loader in v3

[Patrick Georgi]

Hi,

I got quite far with adding decompression to lar (lzma'd data runs fine,
nrv2b decompression seems to hang), but ran into issues that need
discussion.

Currently, two files in the lar archive are parsed directly out of rom
(using the find_file function which returns a pointer to there).
One of them is "option_table", a 900 byte file (which compresses to 350
or so), where I could live with it staying uncompressed in image.

The other one is the payload.

My current work around, is to just define a place in memory where to
decode it to and then load the ELF image from there.

This complicates ELF loading as now there is a risk that the raw ELF
file and the ELF image overlap. (Right now, I just use an address that I
know is beyond the ELF's range)

I propose a new API for the ELF loader that hides this issue and ensures
that decompression works fine. It would be used like this:
    copy_elf(&archive, "normal/payload", &entrypoint, &last_address)

This function looks up "normal/payload" in the archive starting at
archive, and returns success in the return value. entrypoint could then
be used to jump into the image. last_address contains the last byte used
by the ELF image.

The rationale for returning the entrypoint and last_address is to allow
further loads, so multipart payloads can be used, which provides a
cleaner and simpler way to allow modular payloads.
Specifically, I'd like to see this for the grub2 support I work on, as
it's very trivial to just push the modules as "payload.data" into the
lar archive, load it right behind the ELF image and have grub2 find its
modules at _end.

Regards,
Patrick Georgi

[Stefan Reinauer]

* Patrick Georgi  [070627 20:54]:
> I got quite far with adding decompression to lar (lzma'd data runs fine,
> nrv2b decompression seems to hang), but ran into issues that need
> discussion.

Wow. I would have expected this the other way round.
> Currently, two files in the lar archive are parsed directly out of rom
> (using the find_file function which returns a pointer to there).
> One of them is "option_table", a 900 byte file (which compresses to 350
> or so), where I could live with it staying uncompressed in image.

You read the option table in grub2? Why? (sorry I think we talked about
it but it slipped away in the patch orgies of the recent days.

Config options should be parsed from the LinuxBIOS table like lxbios
does it.
> My current work around, is to just define a place in memory where to
> decode it to and then load the ELF image from there.

I think this is the same on v2's compressed payload, is it?
> This complicates ELF loading as now there is a risk that the raw ELF
> file and the ELF image overlap. (Right now, I just use an address that I
> know is beyond the ELF's range)

Can we use the very low or very high memory for this?

Jordan's talk here at the OLS described how LinuxBIOS relocates itself
from the very low space to TOM during the boot process. I think we
should think carefully about this stuff. Will any OS ever claim to be
copied into the low 1M?
> I propose a new API for the ELF loader that hides this issue and ensures
> that decompression works fine. It would be used like this:
>    copy_elf(&archive, "normal/payload", &entrypoint, &last_address)

Is this going to replace int elfboot_mem(struct lb_memory *mem, void
*where, int size)?

I am not really sure I understand the issue completely yet.
> Specifically, I'd like to see this for the grub2 support I work on, as
> it's very trivial to just push the modules as "payload.data" into the
> lar archive, load it right behind the ELF image and have grub2 find its
> modules at _end.

Could you create a lar-fs for grub2 that is always compiled in for
LinuxBIOS? Then the modules could be easily loaded from there (plus a
kernel, a menu.lst and all the other stuff that we might want to put
there)

Would such an FS solve your specific problem? Would we still need to
solve the generic problem?

Stefan

[Jordan Crouse]

On 29/06/07 20:56 +0200, Stefan Reinauer wrote:
> Jordan's talk here at the OLS described how LinuxBIOS relocates itself
> from the very low space to TOM during the boot process. I think we
> should think carefully about this stuff. Will any OS ever claim to be
> copied into the low 1M?

Eric can correct me, but from what I can tell, the intent of the extra
copy is to allow any arbitrary application to run - even those that are less
then responsible about where they go in memory.  We generalized a little
bit in our talk - what happens in reality in the elf loader is that parts of
the payload that would interfere with the loader are copied into a temporary
buffer, and later, LB copies itself out of the way, and replaces the 
missing chunks back into their rightful place.  I don't believe this code
runs all the time - just in those situations where LB code is at danger.

Its a little hackish, but I would prefer to have that rather then put
restrictions on the payload - we can hope that most payloads are friendly,
but we shouldn't restrict the ones that aren't.

---
Jordan Crouse
Senior Linux Engineer
Advanced Micro Devices, Inc.
<www.amd.com/embeddedprocessors>

[ron minnich]

The 'copy yourself out of the way' elfboot code was incredibly
powerful and fun to read. It was also tricky.

For the first pass, I yanked it from v3 as I had too many 'what the
hell is this doing' questions over the years. It reduced from 668
tricky lines to 215 dead-simple lines. But we also lost the ability to
run arbitrary code. That ability was almost never needed, however.

It would actually be simpler, if we want arbitrary ability to to copy
code around, to put a final 'copy it around' function in ROM, run all
stages of LinuxBIOS, and run the 'copy it all around' bit in ROM.

Or: We do several uncompress lar to rom, run, return to rom phases
now, The final copy step could be a final lar entry.

There are actually lots of ways to do support arbitrary code
destination,  all of them simpler than what we did in V2. I'd like to
explore alternatives before we put the v2 code back.

thanks

ron

[Stefan Reinauer]

* ron minnich  [070629 21:42]:
> For the first pass, I yanked it from v3 as I had too many 'what the
>  hell is this doing' questions over the years. It reduced from 668
>  tricky lines to 215 dead-simple lines. But we also lost the ability to
>  run arbitrary code. That ability was almost never needed, however.

almost? What was the exception?

Stefan

[ron minnich]

On 6/29/07, Stefan Reinauer  wrote:
> almost? What was the exception?

ah, well, I said 'almost' .. but I don't recall the exception :-)

it's possible that in some cases memtest was an exception. But it need
not have been.

ron

[Patrick Georgi]

Stefan Reinauer wrote:
> You read the option table in grub2? Why? (sorry I think we talked about
> it but it slipped away in the patch orgies of the recent days.

I don't. At some point in _LinuxBIOSv3_, some code searches for 
option_table and returns a pointer to ROM for further use.
Of course, this mechanism won't work if the option_table is compressed 
there.

Right now, my solution is to mark it nocompress:, before that, I just 
decompressed it to a fixed location for experimentation.
It has to be done one way or the other.
> I think this is the same on v2's compressed payload, is it?

I have no idea how v2 does it, sorry!
> > This complicates ELF loading as now there is a risk that the raw ELF
> > file and the ELF image overlap. (Right now, I just use an address that I
> > know is beyond the ELF's range)
>
> Can we use the very low or very high memory for this?

Could still be claimed by the ELF image.
My proposal would be to decompress the ELF image to some location, look 
if that location overlaps with the places the data is copied to, and if 
so, determine a large-enough chunk of memory and decompress it to there 
again, and work from there.
Of course, that would happen on every boot, so maybe a default address 
at some harmless location, with the option to override it somehow 
(normal/elf-position in lar containing the address?) is to be preferred.
> should think carefully about this stuff. Will any OS ever claim to be
> copied into the low 1M?

lbgrub2 right now is copied to 64k - though I can change that.
> Is this going to replace int elfboot_mem(struct lb_memory *mem, void
> *where, int size)?
>
> I am not really sure I understand the issue completely yet.

My idea would be to let copy_elf be a wrapper around elfboot_mem (with 
some refactorings to more easily look at the ranges the ELF requires), 
with elfboot_mem still available in case "other" loading mechanisms are 
devised.

The goal is to still have simple to read code.

Of course, the easiest way would be to require the payload to leave a 
defined chunk of memory alone, and that the ELF image fits into that 
memory range.
> Could you create a lar-fs for grub2 that is always compiled in for
> LinuxBIOS? Then the modules could be easily loaded from there (plus a
> kernel, a menu.lst and all the other stuff that we might want to put
> there)
>
> Would such an FS solve your specific problem? Would we still need to
> solve the generic problem?

This (getting the modules somewhere) is actually a separate problem: The 
problem above is that we have to copy a compressed ELF image somewhere 
before elfboot_mem can parse it, which could collide with the memory 
ranges claimed by the ELF sections.

lar-fs would solve having an additional chunk of data somewhere in 
memory where grub2 can find its modules. It would be some extra trouble 
with regard to finding the LAR, providing the decompression routines 
again, _having to freeze or version the lar format_ (because there's an 
external user), ... so I'd rather go with the current solution (just 
creating a large, zeroed array in the grub2 kernel and fill it up with 
modules)
Sorry, if I didn't separate the two issues enough.

Regards,
Patrick Georgi

[ron minnich]

ok, guys, I am attaching the v2 elfboot.c to force you all to read it again :-)

The question you need to think about: is your proposal easier or
harder than what you see done here? I can't comment, I am not sure.

Can we have a "fixup" step in ROM which, if the ELF collides with the
running LB, the ROM code can do the cleanup?

Anyway, here you go.

ron

[Stefan Reinauer]

* Patrick Georgi  [070629 22:03]:
> I don't. At some point in _LinuxBIOSv3_, some code searches for option_table 
>  and returns a pointer to ROM for further use.
>  Of course, this mechanism won't work if the option_table is compressed 
>  there.

Ah! In this case I think the file needs to be in rom uncompressed all
the time because we want to read cmos options before ram is up.
> Right now, my solution is to mark it nocompress:, before that, I just 
>  decompressed it to a fixed location for experimentation.
>  It has to be done one way or the other.

I think the uncompress: marker is fine.
> My proposal would be to decompress the ELF image to some location, look if 
>  that location overlaps with the places the data is copied to, and if so, 
>  determine a large-enough chunk of memory and decompress it to there again, 
>  and work from there.

So the program will not live at the address it asked for?
> lbgrub2 right now is copied to 64k - though I can change that.

If it gets your trouble done for the moment, please move it, until we
really figured the ELF stuff out.
> My idea would be to let copy_elf be a wrapper around elfboot_mem (with some 
>  refactorings to more easily look at the ranges the ELF requires), with 
>  elfboot_mem still available in case "other" loading mechanisms are devised.

we could maybe redo some parts of what we aready have, instead of
creating a layer around it?
> lar-fs would solve having an additional chunk of data somewhere in memory 
>  where grub2 can find its modules. It would be some extra trouble with regard 
>  to finding the LAR, providing the decompression routines again, _having to 
>  freeze or version the lar format_ (because there's an external user), ... so 
>  I'd rather go with the current solution (just creating a large, zeroed array 
>  in the grub2 kernel and fill it up with modules)

I think we really want to freeze lar in the long or even short run. we
should get this finished within the next few weeks. Lets not freeze or
version the format during development. If early versions stop working at
some point, that is not an issue. We dont run on any hardware, yet. 
Decompression is the only issue I see with this at the moment. :( It
will make us have several copies of the same stuff again :(

[ron minnich]

I think we have a lot of control with the ROM payload, so much so that
requiring it to locate itself above 512K is a simple thing to do.
LinuxBIOS does not load general payloads, just ROM payloads, and it is
reasonable to create some restrictions.

thanks

ron

"ron minnich"  writes:
> I think we have a lot of control with the ROM payload, so much so that
> requiring it to locate itself above 512K is a simple thing to do.
> LinuxBIOS does not load general payloads, just ROM payloads, and it is
> reasonable to create some restrictions.

There are a couple of options here.  Ideally linuxbios would execute
from the end of ram instead of the beginning which would mean all
architecturally defined addresses would be free for use for the
payload.  I think I handle this in etherboot by simply running
from the end of memory.

It does sound like this is going to have to be a 2 step process,
decompress and then load.  So really only the code for the final
load step has to get out of the way.

I do know it can be nice to handle something fairly arbitrary and
it really wasn't that much code.

Eric

[Patrick Georgi]

Stefan Reinauer wrote:
> Ah! In this case I think the file needs to be in rom uncompressed all
> the time because we want to read cmos options before ram is up.

Good to know.
> So the program will not live at the address it asked for?

It will - terminology is a bit unforgiving here, as the final memory 
layout is called "ELF Image", just like the file as generated by the linker.

Anyway: The proposal is to decompress the ELF image (the file generated 
by the linker) a second time, if the default location where it is 
compressed to collides with the memory used by the payload. When doing 
it the second time, all information is available to avoid another collision.
> If it gets your trouble done for the moment, please move it, until we
> really figured the ELF stuff out.

Moving it only helps if we decide on a memory layout. I need a place 
where I can decompress the ELF image to - either dynamically using a 
method like the one above or fixed, and reserved for that purpose.

As for my "trouble of the moment", I can just go on uncompressing the 
payload to 0x80000 (which I hardcoded) and move on with grub. That's not 
a permanent solution, though.

Regards,
Patrick Georgi

[Stefan Reinauer]

* Patrick Georgi  [070630 07:47]:
> Anyway: The proposal is to decompress the ELF image (the file generated by 
>  the linker) a second time, if the default location where it is compressed to 
>  collides with the memory used by the payload. When doing it the second time, 
>  all information is available to avoid another collision.

Ok. Then we have two seperate issues that might happen, that are not yet
handled in v3:

* loaded Payload gets into conflict with uncompressed payload
* loaded payload gets into conflict with LinuxBIOS.

Any way to solve these in 1 step? We could enhance the memory space used
by linuxbios by the space used by the decompressed image, and relocate
that space completely on demand when loading the payload wants to use
that area.
> Moving it only helps if we decide on a memory layout. I need a place where I 
>  can decompress the ELF image to - either dynamically using a method like the 
>  one above or fixed, and reserved for that purpose.

I suggest putting the decompress buffer right behind the memory used by
linuxbios.
> As for my "trouble of the moment", I can just go on uncompressing the 
>  payload to 0x80000 (which I hardcoded) and move on with grub. That's not a 
>  permanent solution, though.

Yes, but its fine for the moment.

We could also make the uncompression space configurable in linuxbios,
hidden behind "Advanced user options" or so? So we choose a default
position for every known payload at this time (Filo/Grub/OFW/Linux/?)
and if someone wants to use a payload that breaks this, it can be
changed in the config, in case we have no control over the payload
source to change it there.

Stefan

[ron minnich]

i think it's sounding like we should just bring the v2 elf loader back in?

It seems simpler than the other options I've seen so far.

ron

[Stefan Reinauer]

* ron minnich  [070630 18:38]:
> i think it's sounding like we should just bring the v2 elf loader back in?
>
> It seems simpler than the other options I've seen so far.

It does not solve Patrick's problem though I think.

[Uwe Hermann]

On Fri, Jun 29, 2007 at 10:55:25PM +0200, Stefan Reinauer wrote:
> I think we really want to freeze lar in the long or even short run. we
> should get this finished within the next few weeks. Lets not freeze or
> version the format during development. If early versions stop working at
> some point, that is not an issue. We dont run on any hardware, yet. 
> Decompression is the only issue I see with this at the moment. :( It
> will make us have several copies of the same stuff again :(

We definately need a version field in the lar header, we probably cannot
use the same format forever, there _will_ be changes one day.

I agree that we don't have to worry too much as long as there are no
external users (yet). But in fact, the 'lar' binary itself will be an
"external" user. It will be available from /usr/bin/lar or similar,
as a general utility (_not_ bound to a specific revision of LinuxBIOS).

We'll use 'lar' to add entries (e.g. payloads) to existing images, remove
entries, etc. etc., all from user space with the 'lar' tool.

Thus, this tool must know which version of a lar archives it works on,
and it must contain backwards compatibility code, to not only handle
the lar format which was the newest one when the tool was compiled,
but also all older version (at least those, which were "released" or
marked as "stable" or something)...

For now the work required to do this is almost zero, just add a
'version' entry to the lar header struct and ignore it's value.
Later versions will have to read the version field and act accordingly.

Uwe.

[Stefan Reinauer]

* Uwe Hermann  [070630 16:32]:
> We definately need a version field in the lar header, we probably cannot
> use the same format forever, there _will_ be changes one day.

So what? The lar archive will always work with the lar program that came
with that version of linuxbios.

I agree we want a version at some point, and I am fine if someone sends
a patch that implements it. But lets not use it before our headers have
at least stabilized.
> Thus, this tool must know which version of a lar archives it works on,
> and it must contain backwards compatibility code, to not only handle
> the lar format which was the newest one when the tool was compiled,
> but also all older version (at least those, which were "released" or
> marked as "stable" or something)...

Or at least print an error ("your lar archive is too old, please
update")
> For now the work required to do this is almost zero, just add a
> 'version' entry to the lar header struct and ignore it's value.
> Later versions will have to read the version field and act accordingly.

agreed.

[Jordan Crouse]

On 30/06/07 16:32 +0200, Uwe Hermann wrote:
> On Fri, Jun 29, 2007 at 10:55:25PM +0200, Stefan Reinauer wrote:
> > I think we really want to freeze lar in the long or even short run. we
> > should get this finished within the next few weeks. Lets not freeze or
> > version the format during development. If early versions stop working at
> > some point, that is not an issue. We dont run on any hardware, yet. 
> > Decompression is the only issue I see with this at the moment. :( It
> > will make us have several copies of the same stuff again :(
>
> We definately need a version field in the lar header, we probably cannot
> use the same format forever, there _will_ be changes one day.

Agreed. Stefan and I discussed this briefly at OLS.
> I agree that we don't have to worry too much as long as there are no
> external users (yet). But in fact, the 'lar' binary itself will be an
> "external" user. It will be available from /usr/bin/lar or similar,
> as a general utility (_not_ bound to a specific revision of LinuxBIOS).
>
> We'll use 'lar' to add entries (e.g. payloads) to existing images, remove
> entries, etc. etc., all from user space with the 'lar' tool.
>
> Thus, this tool must know which version of a lar archives it works on,
> and it must contain backwards compatibility code, to not only handle
> the lar format which was the newest one when the tool was compiled,
> but also all older version (at least those, which were "released" or
> marked as "stable" or something)...
>
> For now the work required to do this is almost zero, just add a
> 'version' entry to the lar header struct and ignore it's value.
> Later versions will have to read the version field and act accordingly.

I think now is the time to do that - we can easily break any lar users
now without much penalty.   Later, it won't be so easy.

Jordan

[Peter Stuge]

On Fri, Jun 29, 2007 at 10:03:26PM +0200, Patrick Georgi wrote:
> My proposal would be to decompress the ELF image to some location,
> lookk if that location overlaps with the places the data is copied
> to, and if so, determine a large-enough chunk of memory and
> decompress it to there again

Sorry, NAK. I don't like unneccessary work.

If need be, teach elfboot to peek into compressed streams so that it
can tell the decompressor a safe place to decomress to.

On Fri, Jun 29, 2007 at 10:55:25PM +0200, Stefan Reinauer wrote:
> > Right now, my solution is to mark it nocompress:, before that,
> >  I just decompressed it to a fixed location for experimentation.
> >  It has to be done one way or the other.
>
> I think the uncompress: marker is fine.

It must be automatic.
> I think we really want to freeze lar in the long or even short run.

Certainly, but let's wait until later.

//Peter

[Stefan Reinauer]

* Peter Stuge  [070701 00:51]:
> > > Right now, my solution is to mark it nocompress:, before that,
> > >  I just decompressed it to a fixed location for experimentation.
> > >  It has to be done one way or the other.
> >
> > I think the uncompress: marker is fine.
>
> It must be automatic.

How would l ar know which modules must not be compressed? We have to
teach it at some place.

Jordan Crouse has a surprise for us in a couple of days I guess.
> > I think we really want to freeze lar in the long or even short run.
>
> Certainly, but let's wait until later.

Yes.

[Carl-Daniel Hailfinger]

On 01.07.2007 00:51, Peter Stuge wrote:
> On Fri, Jun 29, 2007 at 10:03:26PM +0200, Patrick Georgi wrote:
> > My proposal would be to decompress the ELF image to some location,
> > lookk if that location overlaps with the places the data is copied
> > to, and if so, determine a large-enough chunk of memory and
> > decompress it to there again
>
> Sorry, NAK. I don't like unneccessary work.
>
> If need be, teach elfboot to peek into compressed streams so that it
> can tell the decompressor a safe place to decomress to.

Sorry, our implementation of lzma decompression does not decompress
to a stream, only in bulk. Choosing streaming decompression is
possible, but the memory requirements made me decide against it.
Decompression speed is also significantly slower for streaming lzma
decompression.

Regards,
Carl-Daniel

[Peter Stuge]

On Sun, Jul 01, 2007 at 02:21:04AM +0200, Carl-Daniel Hailfinger wrote:
> > If need be, teach elfboot to peek into compressed streams so that
> > it can tell the decompressor a safe place to decomress to.
>
> Sorry, our implementation of lzma decompression does not decompress
> to a stream, only in bulk.

So compress only the ELF segments but not the header.

(This is a good reason to have compression built into lar, since
it would constitute crazy weird ELF trickery if done manually.)

//Peter

[LinuxBIOS] OLS audio/video/slides?

[Uwe Hermann]

On Fri, Jun 29, 2007 at 08:56:41PM +0200, Stefan Reinauer wrote:
> Jordan's talk here at the OLS described how LinuxBIOS relocates itself
> from the very low space to TOM during the boot process.

Are there slides, audio recordings or video recordings available?

Thanks, Uwe.

[LinuxBIOS] OLS audio/video/slides?

[Jordan Crouse]

On 30/06/07 16:18 +0200, Uwe Hermann wrote:
> On Fri, Jun 29, 2007 at 08:56:41PM +0200, Stefan Reinauer wrote:
> > Jordan's talk here at the OLS described how LinuxBIOS relocates itself
> > from the very low space to TOM during the boot process.
>
> Are there slides, audio recordings or video recordings available?

Slides will be forthcoming when I finish navigating the shark filled
waters of our web site.  Audio and video recordings will eventually be made
available on linuxsymposium.org as soon as they figure out how much it will
cost to produce them.

Also, the paper itself (which is more detailed then the presentation), is
here:

https://ols2006.108.redhat.com/2007/Reprints/crouse-Reprint.pdf

That will also hopefully be on our website soon enough.  If you have any
questions, let me know.

Jordan

[LinuxBIOS] OLS audio/video/slides?

[Uwe Hermann]

On Mon, Jul 02, 2007 at 08:59:31AM -0600, Jordan Crouse wrote:
> On 30/06/07 16:18 +0200, Uwe Hermann wrote:
> > On Fri, Jun 29, 2007 at 08:56:41PM +0200, Stefan Reinauer wrote:
> > > Jordan's talk here at the OLS described how LinuxBIOS relocates itself
> > > from the very low space to TOM during the boot process.
> >
> > Are there slides, audio recordings or video recordings available?
>
> Slides will be forthcoming when I finish navigating the shark filled
> waters of our web site.  Audio and video recordings will eventually be made
> available on linuxsymposium.org as soon as they figure out how much it will
> cost to produce them.
>
> Also, the paper itself (which is more detailed then the presentation), is
> here:
>
> https://ols2006.108.redhat.com/2007/Reprints/crouse-Reprint.pdf

Great, thanks, added to the wiki.

Uwe.