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

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

[Robert Schiele]

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.

This is where I am at the moment. Before digging deeper into the root
cause I thought I'd give people here a chance to jump in with their
knowledge to point me into the right direction in case you have an
idea what might go wrong here.

Especially I am interested about your opinion whether this could also
be caused by corrupt object files from the compiler/assembler or
whether this for sure is a problem with ld/libbfd. Unfortunately I
cannot provide the code that is reproducing that because first of all
it is proprietary software and after all it is really huge, such that
shipping that stuff would not be very practicable. Also given the
involved code it doesn't seem that I could easily create a smaller
test case that also reproduces this.

Hopefully someone has some hints before I dig deeper into this.

Robert

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

[Robert Schiele]

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

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

[Robert Schiele]

On Tue, Jan 8, 2013 at 12:10 PM, Robert Schiele <rschiele@gmail.com> wrote:
> 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.

I also did some bisecting to see when the problem first occurred. In
fact I saw it first after
http://sourceware.org/ml/binutils/2008-06/msg00273.html got committed.
Obviously this does not mean that this is the culprit since the bug
could just have been triggered by that in my case. But it could also
be that this change invalidates some assumptions that were made in the
original implementation as described in my previous mails.

Richard, since it seems the original implementation of this idea
(http://sourceware.org/ml/binutils/2007-10/msg00409.html) and the
patch that seems to break it
(http://sourceware.org/ml/binutils/2008-06/msg00273.html) are from
you, you might have the best idea of what might be going wrong here.

Robert

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

[Richard Sandiford]

Robert Schiele <rschiele@gmail.com> writes:
> On Tue, Jan 8, 2013 at 12:10 PM, Robert Schiele <rschiele@gmail.com> wrote:
>> 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.
>
> I also did some bisecting to see when the problem first occurred. In
> fact I saw it first after
> http://sourceware.org/ml/binutils/2008-06/msg00273.html got committed.
> Obviously this does not mean that this is the culprit since the bug
> could just have been triggered by that in my case. But it could also
> be that this change invalidates some assumptions that were made in the
> original implementation as described in my previous mails.
>
> Richard, since it seems the original implementation of this idea
> (http://sourceware.org/ml/binutils/2007-10/msg00409.html) and the
> patch that seems to break it
> (http://sourceware.org/ml/binutils/2008-06/msg00273.html) are from
> you, you might have the best idea of what might be going wrong here.

Sorry, it's going to very hard to help here without a testcase.
Can you give any more information about the relocations whose
offsets changed?

Richard

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

[Robert Schiele]

On Tue, Jan 8, 2013 at 8:15 PM, Richard Sandiford
<rdsandiford@googlemail.com> wrote:
> Sorry, it's going to very hard to help here without a testcase.

Yes, I feared so. I was just hoping that you might have an immediate
idea from the information collection. I am trying to produce a
non-proprietary test case now that I can easily hand out.

Robert

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

[Robert Schiele]

On Tue, Jan 8, 2013 at 8:15 PM, Richard Sandiford
<rdsandiford@googlemail.com> wrote:
> Robert Schiele <rschiele@gmail.com> writes:
> Can you give any more information about the relocations whose
> offsets changed?

The offending relocations are R_MIPS_GOT_PAGE relocations against
.rodata.str1.8 sections.

Robert

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

[Robert Schiele]

On Thu, Jan 10, 2013 at 10:18 AM, Robert Schiele <rschiele@gmail.com> wrote:
> The offending relocations are R_MIPS_GOT_PAGE relocations against
> .rodata.str1.8 sections.

And giving that one further thought, this section is SHF_MERGE |
SHF_STRINGS and thus it is kind of expected that from the merging it
could happen that the offsets of those relocations can change for a
different amount since other stuff could have been merged in between.
If that happens it is actually quite likely that they can cover more
pages than they initially did and thus the assumption mentioned above
that you can get an upper bound of pages affected by just summing up
the affected pages of the individual objects before is no longer true.

Do you agree or do I have a wrong understanding here of how things work?

Robert

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

[Robert Schiele]

On Wed, Jan 9, 2013 at 4:09 PM, Robert Schiele <rschiele@gmail.com> wrote:
> On Tue, Jan 8, 2013 at 8:15 PM, Richard Sandiford
> <rdsandiford@googlemail.com> wrote:
>> Sorry, it's going to very hard to help here without a testcase.
>
> Yes, I feared so. I was just hoping that you might have an immediate
> idea from the information collection. I am trying to produce a
> non-proprietary test case now that I can easily hand out.

Ok, finally I have one but it is not really a small one. Given that it
seems only possible to trigger that for links large enough to involve
the code handling the case a single GOT gets too large I ended up with
something that is compressed about 6.5M. You can download the beast
here: http://sdrv.ms/VPT3hi

Note that this is partially auto generated ELF data and I am not
perfectly sure whether it is 100% standards compliant but at least
libbfd does not seem to complain about it (besides the error mentioned
here that I can also reproduce with gcc generated stuff).

You need to unpack the test case into some empty directory. Inside you
will find some object files, some static libraries and some shared
libraries. Additionally there is a script "reproduce" that tries to
reproduce the problem. You have to adapt the name of the linker you
want to use. I built mine with /home/rschiele/src/binutils/configure
--target=mips64-octeon-linux-gnu --with-sysroot=/xxxx

Should some of the auto generated stuff be too much confusing feel
free to ask specific questions such that I could do corresponding
investigations on the real proprietary code.

As already mentioned in my mail from yesterday I feel pretty certain
now that the calculation for the upper bound of GOT pages is not
correct for the case of sections that get merged (like string pools)
since their range can expand during the merge and thus a set of
relocations can cover more pages afterwards than it did before. But I
am not sure yet what a correct upper bound would be in that case that
would not hurt the regular case too much.

Robert

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

[Robert Schiele]

Hi again,

On Thu, Jan 10, 2013 at 10:48 AM, Robert Schiele <rschiele@gmail.com> wrote:
> On Thu, Jan 10, 2013 at 10:18 AM, Robert Schiele <rschiele@gmail.com> wrote:
>> The offending relocations are R_MIPS_GOT_PAGE relocations against
>> .rodata.str1.8 sections.
>
> And giving that one further thought, this section is SHF_MERGE |
> SHF_STRINGS and thus it is kind of expected that from the merging it
> could happen that the offsets of those relocations can change for a
> different amount since other stuff could have been merged in between.
> If that happens it is actually quite likely that they can cover more
> pages than they initially did and thus the assumption mentioned above
> that you can get an upper bound of pages affected by just summing up
> the affected pages of the individual objects before is no longer true.

This might for sure not be the smartest solution but at least it
should fix it (and does in my case) if I just replace the

g->local_gotno += (pages < g->page_gotno ? pages : g->page_gotno);

with the conservative

g->local_gotno += pages;

Does anyone see a problem with that? Do you expect major penalties
from this super conservative approach?

Robert

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

[Richard Sandiford]

Robert Schiele <rschiele@gmail.com> writes:
> On Thu, Jan 10, 2013 at 10:48 AM, Robert Schiele <rschiele@gmail.com> wrote:
>> On Thu, Jan 10, 2013 at 10:18 AM, Robert Schiele <rschiele@gmail.com> wrote:
>>> The offending relocations are R_MIPS_GOT_PAGE relocations against
>>> .rodata.str1.8 sections.
>>
>> And giving that one further thought, this section is SHF_MERGE |
>> SHF_STRINGS and thus it is kind of expected that from the merging it
>> could happen that the offsets of those relocations can change for a
>> different amount since other stuff could have been merged in between.
>> If that happens it is actually quite likely that they can cover more
>> pages than they initially did and thus the assumption mentioned above
>> that you can get an upper bound of pages affected by just summing up
>> the affected pages of the individual objects before is no longer true.
>
> This might for sure not be the smartest solution but at least it
> should fix it (and does in my case) if I just replace the
>
> g->local_gotno += (pages < g->page_gotno ? pages : g->page_gotno);
>
> with the conservative
>
> g->local_gotno += pages;
>
> Does anyone see a problem with that? Do you expect major penalties
> from this super conservative approach?

You'll need to do it consistently for all page_gotno tests
(mips_elf_merge_got_with, mips_elf_merge_gots, mips_elf_multi_got and
mips_elf_lay_out_got), otherwise you could end up merging GOTs based on
the current estimate and lay them out using the conservative one, which
could lead to overflow in the global region.  But yeah, I think you'd
be safe changing those four places, as a local hack to get round the bug.
It should be equivalent to reverting my patch.

FWIW, I experimented with one way of handling SEC_MERGE this weekend,
but ran out time before I had something I was happy with.  Hope to
return to it again soon.

Richard

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

[Robert Schiele]

On Mon, Jan 14, 2013 at 2:47 PM, Richard Sandiford
<rdsandiford@googlemail.com> wrote:
> You'll need to do it consistently for all page_gotno tests
> (mips_elf_merge_got_with, mips_elf_merge_gots, mips_elf_multi_got and
> mips_elf_lay_out_got), otherwise you could end up merging GOTs based on
> the current estimate and lay them out using the conservative one, which
> could lead to overflow in the global region.  But yeah, I think you'd
> be safe changing those four places, as a local hack to get round the bug.

So, with consistent you mean something like this?

diff --git a/bfd/elfxx-mips.c b/bfd/elfxx-mips.c
index 4036273..24716dc 100644
--- a/bfd/elfxx-mips.c
+++ b/bfd/elfxx-mips.c
@@ -4276,8 +4276,6 @@ mips_elf_merge_got_with (struct
mips_elf_bfd2got_hash *bfd2got,

   /* Work out how many page entries we would need for the combined GOT.  */
   estimate = arg->max_pages;
-  if (estimate >= from->page_gotno + to->page_gotno)
-    estimate = from->page_gotno + to->page_gotno;

   /* And conservatively estimate how many local and TLS entries
      would be needed.  */
@@ -4337,8 +4335,6 @@ mips_elf_merge_gots (void **bfd2got_, void *p)

   /* Work out the number of page, local and TLS entries.  */
   estimate = arg->max_pages;
-  if (estimate > g->page_gotno)
-    estimate = g->page_gotno;
   estimate += g->local_gotno + g->tls_gotno;

   /* We place TLS GOT entries after both locals and globals.  The globals
@@ -4687,7 +4683,7 @@ mips_elf_multi_got (bfd *abfd, struct bfd_link_info *info,
       assign += htab->reserved_gotno;
       g->assigned_gotno = assign;
       g->local_gotno += assign;
-      g->local_gotno += (pages < g->page_gotno ? pages : g->page_gotno);
+      g->local_gotno += pages;
       assign = g->local_gotno + g->global_gotno + g->tls_gotno;

       /* Take g out of the direct list, and push it onto the reversed
@@ -8918,11 +8914,6 @@ mips_elf_lay_out_got (bfd *output_bfd, struct
bfd_link_info *info)
        sections.  Is 5 enough?  */
     page_gotno = (loadable_size >> 16) + 5;

-  /* Choose the smaller of the two estimates; both are intended to be
-     conservative.  */
-  if (page_gotno > g->page_gotno)
-    page_gotno = g->page_gotno;
-
   g->local_gotno += page_gotno;
   s->size += g->local_gotno * MIPS_ELF_GOT_SIZE (output_bfd);
   s->size += g->global_gotno * MIPS_ELF_GOT_SIZE (output_bfd);

> FWIW, I experimented with one way of handling SEC_MERGE this weekend,
> but ran out time before I had something I was happy with.  Hope to
> return to it again soon.

That sounds promising, thanks!

Robert

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

[Richard Sandiford]

Robert Schiele <rschiele@gmail.com> writes:
> On Mon, Jan 14, 2013 at 2:47 PM, Richard Sandiford
> <rdsandiford@googlemail.com> wrote:
>> You'll need to do it consistently for all page_gotno tests
>> (mips_elf_merge_got_with, mips_elf_merge_gots, mips_elf_multi_got and
>> mips_elf_lay_out_got), otherwise you could end up merging GOTs based on
>> the current estimate and lay them out using the conservative one, which
>> could lead to overflow in the global region.  But yeah, I think you'd
>> be safe changing those four places, as a local hack to get round the bug.
>
> So, with consistent you mean something like this?

Yeah, that looks good.

Richard