Re: invocation of mips_elf_multi_got can cause not enough GOT space for local GOT entries

[Robert Schiele <rschiele at gmail dot com>]

On Fri, Jan 4, 2013 at 4:36 PM, Robert Schiele <rschiele@gmail.com> wrote:
> Hi,
>
> I ran into a problem on a huge link for mips64 Linux ELF target that
> causes the linker to fail with the error message "not enough GOT space
> for local GOT entries".
>
> This is not a new problem since it happens with current master branch
> as well as very old releases I went back to.
>
> Debugging the problem so far revealed that the counting of the regular
> local_gotno values goes all well and corresponds to the entries later
> accumulated to assigned_gotno (excluding the page entries) but for one
> specific GOT that is created during the invocation of
> mips_elf_multi_got the page number added up in
>
>       g->local_gotno += (pages < g->page_gotno ? pages : g->page_gotno);
>
> Seems to be incorrect. In that specific case
> mips_elf_make_got_pages_per_bfd gets invoked by
>
>   /* Also count how many page entries each input bfd requires.  */
>   htab_traverse (g->got_page_entries, mips_elf_make_got_pages_per_bfd,
>                  &got_per_bfd_arg);
>
> often, adding up to page_gotno of various GOTs in the line
>
>   g->page_gotno += entry->num_pages;
>
> For the specific GOT this line of code is triggered 3 times, each time
> with a value entry->num_pages of 2, counting up to a page_gotno for
> this GOT of 6. Since this number is smaller than pages (which is 98)
> the 6 is used for counting.
>
> Later it turns out though that the invocation of
> mips_elf_create_local_got_entry from within mips_elf_got_page causes a
> total of 7 entries, which then in the end obviously steals one slot
> that would be needed later for another entry.

After digging deeper into this it seems to me that either the
assumption made in mips_elf_multi_got that the sum of pages of all
relevant entries as calculated through invocation of

  /* Also count how many page entries each input bfd requires.  */
  htab_traverse (g->got_page_entries, mips_elf_make_got_pages_per_bfd,
                 &got_per_bfd_arg);

is incorrect or if theoretically this is correct, something else is
going wrong in the linking step regarding calculation of the new
addends.

The reason I believe that is the following observation:

For a specific object file I am linking in I can see the following
invocations of mips_elf_record_got_page_entry:

invoked for relocation with index=16 type=20 offset=340 addend=8,
concludes to 1 page with one range min 8, max 8
invoked for relocation with index=16 type=20 offset=2100 addend=24,
concludes to 2 pages with one range min 8, max 24
invoked for relocation with index=16 type=20 offset=2140 addend=32,
concludes to 2 pages with one range min 8, max 32
invoked for relocation with index=16 type=20 offset=2248 addend=40,
concludes to 2 pages with one range min 8, max 40
invoked for relocation with index=16 type=20 offset=2356 addend=48,
concludes to 2 pages with one range min 8, max 48
invoked for relocation with index=16 type=20 offset=2396 addend=64,
concludes to 2 pages with one range min 8, max 64
invoked for relocation with index=16 type=20 offset=2432 addend=88,
concludes to 2 pages with one range min 8, max 88
invoked for relocation with index=16 type=20 offset=2532 addend=104,
concludes to 2 pages with one range min 8, max 104
invoked for relocation with index=16 type=20 offset=2572 addend=112,
concludes to 2 pages with one range min 8, max 112
invoked for relocation with index=16 type=20 offset=2608 addend=128,
concludes to 2 pages with one range min 8, max 128
invoked for relocation with index=16 type=20 offset=2636 addend=144,
concludes to 2 pages with one range min 8, max 144
invoked for relocation with index=16 type=20 offset=2736 addend=160,
concludes to 2 pages with one range min 8, max 160
invoked for relocation with index=16 type=20 offset=2836 addend=176,
concludes to 2 pages with one range min 8, max 176
invoked for relocation with index=16 type=20 offset=2940 addend=184,
concludes to 2 pages with one range min 8, max 184
[...]

So, you see that up to the point quoted we are at 2 pages.

Now in the final stage when the relocations are actually calculated we
get different behavior for the same relocations:

invoked for relocation with index=16 type=20 offset=340 addend=247288,
thus page 0x20470000(symbol+addend=0x20473a28), thus new page -> 1
invoked for relocation with index=16 type=20 offset=2100
addend=247304, thus page 0x20470000(symbol+addend=0x20473a38)
invoked for relocation with index=16 type=20 offset=2140
addend=247312, thus page 0x20470000(symbol+addend=0x20473a40)
invoked for relocation with index=16 type=20 offset=2248
addend=247320, thus page 0x20470000(symbol+addend=0x20473a48)
invoked for relocation with index=16 type=20 offset=2356
addend=247328, thus page 0x20470000(symbol+addend=0x20473a50)
invoked for relocation with index=16 type=20 offset=2396
addend=247344, thus page 0x20470000(symbol+addend=0x20473a60)
invoked for relocation with index=16 type=20 offset=2432
addend=247368, thus page 0x20470000(symbol+addend=0x20473a78)
invoked for relocation with index=16 type=20 offset=2532
addend=247384, thus page 0x20470000(symbol+addend=0x20473a88)
invoked for relocation with index=16 type=20 offset=2572
addend=247392, thus page 0x20470000(symbol+addend=0x20473a90)
invoked for relocation with index=16 type=20 offset=2608
addend=247408, thus page 0x20470000(symbol+addend=0x20473aa0)
invoked for relocation with index=16 type=20 offset=2636
addend=247424, thus page 0x20470000(symbol+addend=0x20473ab0)
invoked for relocation with index=16 type=20 offset=2736
addend=247440, thus page 0x20470000(symbol+addend=0x20473ac0)
invoked for relocation with index=16 type=20 offset=2836 addend=27440,
thus page 0x20440000(symbol+addend=0x2043df60), thus new page -> 2
invoked for relocation with index=16 type=20 offset=2940 addend=84808,
thus page 0x20450000(symbol+addend=0x2044bf78), thus new page -> 3

As you can see we have now already 3 pages at this place. This happens
since the last two addends changed significantly relatively to the
others.

Thus I wonder whether it is actually unexpected behavior that this
relative changes occur or if this is expected behavior it seems quite
obvious to me that the assumption of mips_elf_multi_got it makes about
calculation of the new page numbers cannot be generally correct.

Any opinions from someone that understands this MIPS code in
bfd/elfxx-mips.c better than myself?

Robert