[U-Boot] Relocation size penalty calculation

J. William Campbell jwilliamcampbell at comcast.net
Sat Oct 17 14:59:13 CEST 2009


Graeme Russ wrote:
> On Thu, Oct 15, 2009 at 3:45 AM, J. William Campbell
> <jwilliamcampbell at comcast.net> wrote:
>   
>> Joakim Tjernlund wrote:
>>     
>   
<megasnip>

> Apologies if this is getting way off-topic for a simple boot loader, but
> this is information I have gathered from far and wide over the net. I am
> surprised that there isn't a web site out there on 'How to create a
> relocatable boot loader'...
>
> OK, its all starting to come together now - It helps when you look at the
> right files ;)
>
> Firstly, u-boot.map
>
>                 0x380589a0                __rel_dyn_start = .
>
> .rel.dyn        0x380589a0     0x42b0
>  *(.rel.dyn)
>  .rel.got       0x00000000        0x0 cpu/i386/start.o
>  .rel.plt       0x00000000        0x0 cpu/i386/start.o
>  .rel.text      0x380589a0     0x2e28 cpu/i386/start.o
>  .rel.start16   0x3805b7c8       0x10 cpu/i386/start.o
>  .rel.data      0x3805b7d8      0xc18 cpu/i386/start.o
>  .rel.rodata    0x3805c3f0      0x360 cpu/i386/start.o
>  .rel.u_boot_cmd
>                 0x3805c750      0x500 cpu/i386/start.o
>                 0x3805cc50                __rel_dyn_end = .
>
>
> And the output of readelf...
>
> Section Headers:
>   [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
>   [ 0]                   NULL            00000000 000000 000000 00      0   0  0
>   [ 1] .text             PROGBITS        38040000 001000 0118a4 00  AX  0   0  4
>   [ 2] .rel.text         REL             00000000 066c68 005d00 08     40   1  4
>   [ 3] .rodata           PROGBITS        380518a4 0128a4 005da5 00   A  0   0  4
>   [ 4] .rel.rodata       REL             00000000 06c968 000360 08     40   3  4
>   [ 5] .interp           PROGBITS        38057649 018649 000013 00   A  0   0  1
>   [ 6] .dynstr           STRTAB          3805765c 01865c 0001ee 00   A  0   0  1
>   [ 7] .hash             HASH            3805784c 01884c 0000cc 04   A 11   0  4
>   [ 8] .data             PROGBITS        38057918 018918 000a3c 00  WA  0   0  4
>   [ 9] .rel.data         REL             00000000 06ccc8 000c18 08     40   8  4
>   [10] .got.plt          PROGBITS        38058354 019354 00000c 04  WA  0   0  4
>   [11] .dynsym           DYNSYM          38058360 019360 000200 10   A  6   1  4
>   [12] .dynamic          DYNAMIC         38058560 019560 000080 08  WA  6   0  4
>   [13] .u_boot_cmd       PROGBITS        380585e0 0195e0 0003c0 00  WA  0   0  4
>   [14] .rel.u_boot_cmd   REL             00000000 06d8e0 000500 08     40  13  4
>   [15] .bss              NOBITS          3805cc50 01ec50 001a34 00  WA  0   0  4
>   [16] .bios             PROGBITS        00000000 01e000 00053e 00  AX  0   0  1
>   [17] .rel.bios         REL             00000000 06dde0 0000c0 08     40  16  4
>   [18] .rel.dyn          REL             380589a0 0199a0 0042b0 08   A 11   0  4
>   [19] .start16          PROGBITS        0000f800 01e800 000110 00  AX  0   0  1
>   [20] .rel.start16      REL             00000000 06dea0 000038 08     40  19  4
>   [21] .resetvec         PROGBITS        0000fff0 01eff0 000010 00  AX  0   0  1
>   [22] .rel.resetvec     REL             00000000 06ded8 000008 08     40  21  4
>
> ...
>
> Relocation section '.rel.text' at offset 0x66c68 contains 2976 entries:
>  Offset     Info    Type            Sym.Value  Sym. Name
> 38040010  00000101 R_386_32          38040000   .text
> 3804001e  00000101 R_386_32          38040000   .text
> 38040028  00000101 R_386_32          38040000   .text
> 3804003f  00000101 R_386_32          38040000   .text
> 38040051  00000101 R_386_32          38040000   .text
> 38040075  00000101 R_386_32          38040000   .text
> 38040085  00000101 R_386_32          38040000   .text
> 3804009d  0003e602 R_386_PC32        380403fa   load_uboot
> 380400a6  00000101 R_386_32          38040000   .text
> 38040015  00029f02 R_386_PC32        3804bdd8   early_board_init
> 38040023  0003f702 R_386_PC32        3804bdda   show_boot_progress_asm
>
> ...
>
> Relocation section '.rel.rodata' at offset 0x6c968 contains 108 entries:
>  Offset     Info    Type            Sym.Value  Sym. Name
> 38051908  00000201 R_386_32          380518a4   .rodata
> 38051938  00000201 R_386_32          380518a4   .rodata
> 38051968  00000201 R_386_32          380518a4   .rodata
> 38051998  00000201 R_386_32          380518a4   .rodata
> 380519c8  00000201 R_386_32          380518a4   .rodata
> 380519f8  00000201 R_386_32          380518a4   .rodata
>
> ...
>
> Relocation section '.rel.dyn' at offset 0x199a0 contains 2134 entries:
>  Offset     Info    Type            Sym.Value  Sym. Name
> 0000f838  00000008 R_386_RELATIVE
> 0000f846  00000008 R_386_RELATIVE
> 38040010  00000008 R_386_RELATIVE
> 3804001e  00000008 R_386_RELATIVE
> 38040028  00000008 R_386_RELATIVE
> 3804003f  00000008 R_386_RELATIVE
> 38040051  00000008 R_386_RELATIVE
> 38040075  00000008 R_386_RELATIVE
> 38040085  00000008 R_386_RELATIVE
>
> Notice that, apart from .rel.dyn, non of the .rel.* sections have the
> A (Allocated) flag set - They do not end up in the stripped binary image.
> .rel.dyn is allocated in the binary image with all the R_386_PC32 entries
> from the other .rel section are discarded and the R_386_32 have been
> 'converted' to R_386_RELATIVE which are simple to adjust (locate in memory
> and adjust by the relocation offset)
>
> The relocation fixup is really easy:
>
> 	Elf32_Rel *rel_dyn_start = (Elf32_Rel *)&__rel_dyn_start;
> 	Elf32_Rel *rel_dyn_end = (Elf32_Rel *)&__rel_dyn_end;
> 	Elf32_Rel *re;
>
> 	for (re = rel_dyn_start; re < rel_dyn_end; re++)
> 	{
> 		if (re->r_offset >= TEXT_BASE)
> 			if (*(ulong *)re->r_offset >= TEXT_BASE)
> 				*(ulong *)(re->r_offset - rel_offset) -= (Elf32_Addr)rel_offset;
> 	}
>
> The size penalty is ~17kB of extra data (which is not copied to RAM) and
> a tiny amount of relocation code (easily offset by removal of other fixups
> such as the command table fixup
>
> Any without using the pic flag in gcc, there is no GOT and no associated
> performance penalty.
>
> Thanks for everyone's help (especially Jocke and Bill)
>   
Great work Graeme. You have taken a lot of conjecture and guessing and 
converted it to actual truth!

In line with your comment about -fpic, the .text segment size goes from 
000137fc down to 000118a4, or about an 8 k reduction in size. -fpic also 
contains a .rel_dyn segment, that presumably needs to be processed the 
same way as in the non -fpic case (otherwise, why would it be there?). 
The size of the "residual" .rel_dyn was 00001228, or 4.6 k. This means 
that the size penalty for not using -fpic is only about 3k bytes total 
in the image, and the ram footprint is actually smaller than with -fpic. 
So now, after Graeme's work here, it is easily possible to support three 
different u-boot configurations, absolute, relocatable, and relocatable 
with -fpic. If there are any size maniacs out there, we can reduce the 
size of the relocation table at the expense of some post-processing. 
These days, 9k of flash vs 4.5k of flash doesn't seem important, but I 
imagine if you are right against the stops on an existing product it can 
be very important!

It will be interesting to see similar numbers for other architectures. I 
expect similar results, but you never know. PPC relocation entries are 
larger, so they become more of an issue.

Still more questions for Graeme if he will indulge me! Are the if 
statements in the relocation code ever false? Are there relocations for 
stuff below TEXT_BASE in
the input binary? If so, do you have any idea why? Not that two if 
statements are a big deal, it is just that I can't explain why there 
would be any relocations below TEXT_BASE, and I can't explain why there 
would be any relocatable references to anything below text base. . I 
assume this might be related to not relocating NULL pointers. That would 
be reflected in the innermost if statement. I would not expect there to 
be any such references, as gas does know the relocation attributes of 
initialized data, and NULL is absolute(?)  Also, if a function is not 
defined (weak or otherwise), the loader should give it an address of 
absolute 0, which would also not generate a relocation entry(?).  It 
would be interesting to intentionally call an un-defined function in 
u-boot and see if the call ends up relocatable. It should not, and if it 
does we should file a bug report for ld!

 Thanks again Graeme!

Best Regards,
Bill Campbell
> Regards,
>
> Graeme
>
>   



More information about the U-Boot mailing list