Multigot mechanism and a related MIPS linker error

[Uma shankar]

Posting again with  the proper subject title -

For our MIPS cross-compiler,
gcc version is  4.2.0
binutils version is 2.17.90.

When our application  tries to link with third-party library,  the
MIPS linker reports  failure as
"ld: Bad value"

The library is not available to us.

Since the linking passes after applying the patches  given by Richard
Sandiford at http://sourceware.org/ml/binutils/2008-06/msg00270.html ,
we  figured that the error has something to do with multigot feature.
The description of the patch is difficult for us to understand.

We want to reproduce the failure with a test program.  As  a first
step, we are are trying to access  many extern symbols
from main(). But when the GOT table size  exceeds 64 Kb,  the linker
fails with message such as :
"relocation truncated to fit: R_MIPS_GOT16 against `global_variable__d13155'"

With less than 64 Kb GOT ,  I can see that the binary is in multigot
mode. (Each function's prolog is assigning
a different value for gp reg. )

a) In multigot mode, why should linker fail to create larger-than-64Kb
 GOT ?   The very purpose of multigot
is to overcome this limit, isn't it ?

b) I looked at another application built in our company with same
toolchain.  Its GOT is 188 Kb in size.
(There are about 33000 extern symbol entries in the GOT .) I  looked
at its linking options and did not find anything special.
I looked  at its binary.  It is NOT in xgot mode.  Any clues ?

c) For the above binary mentioned in  ,  I can see lot of relocation
entries in .rel.dyn for the GOT table fixup.  From what I know,
in MIPS,  reloc entries are not needed for GOT relocation.  Why would
the linker output those for this binary?

d) I want to understand the ld test-suite
(/toolchain/testsuite/binutils/testsuite/ld/ld-mips-elf)  Is there any
writeup  somewhere ?

                 thanks a lot
                 shankar

[Nick Clifton]

Hi Shankar,

> For our MIPS cross-compiler,
> gcc version is  4.2.0
> binutils version is 2.17.90.

I assume that you know that 2.17.90 is an old binutils release ?  We are
currently on release 2.19 and 2.20 will be out shortly.


I am not a MIPS expert, so I am not going to try to answer your
questions about the multigot feature, but I can answer this question:

> d) I want to understand the ld test-suite
> (/toolchain/testsuite/binutils/testsuite/ld/ld-mips-elf)  Is there any
> writeup  somewhere ?

There is no writeup.  (Maybe someone would like to create one ?)  In
essence though the linker tests are meant to be self-documenting.

What happens is that in each sub-directory of the testsuite there are
one or more "expect" files.  These are files that have the .exp
extension.  They are written in a scripting language called expect.
(http://en.wikipedia.org/wiki/Expect).  These files decide which tests
should be run based on the target being tested, and occasionally they
contain extra code to help with the testing.  Some helper code can also
be found in the ld/testsuite/lib/ld-lib.exp file.

Most individual linker tests consist of one or more assembler or C
source files (with .s or .c extensions) and also an expected output file
(with a .d extension).  The .d file actually drives the test.  At the
start of the file are various directives which specify things like the
name of the test, the source files that must be assembled or compiled
first, the command line options to pass to the linker, the program used
to examine the output of the linker and so on.

Ideally each test will check just one particular feature of the linker,
or make sure that one particular bug is no longer present in the linker.
  Also the tests should be separated into sub-directories based on the
target that they are for or the general area of the linker that they are
testing.  Hence the ld-mips-elf sub-directory contains tests for MIPS
linkers that use the ELF file format.

The testsuite itself is run using another tool called DejaGnu
(http://en.wikipedia.org/wiki/Dejagnu).  Apart from setting up a
site.exp file and DEJAGNU environment variable before using dejagnu for
the first time, most testers will not need to deeply into the internals
of DejaGnu.

I hope that this explanation helps.

Cheers
   Nick

[Richard Sandiford-5]

"Umashankar V.K." <shankar.vk@...> writes:

> We want to reproduce the failure with a test program.  As  a first
> step, we are are trying to access  many extern symbols
> from main(). But when the GOT table size  exceeds 64 Kb,  the linker
> fails with message such as :
> "relocation truncated to fit: R_MIPS_GOT16 against `global_variable__d13155'"
>
> With less than 64 Kb GOT ,  I can see that the binary is in multigot
> mode. (Each function's prolog is assigning
> a different value for gp reg. )
>
> a) In multigot mode, why should linker fail to create larger-than-64Kb
>  GOT ?   The very purpose of multigot
> is to overcome this limit, isn't it ?

Yes, but it assigns GOTs on a _per-object_ basis.  There isn't enough
information in a relocatable object file to tell for sure which function
"owns" a particular GP-relative relocation (such as a R_MIPS_GPREL32
relocation in a data section), so the linker has to use the same _gp
throughout a given input object.

There's also the issue that nested functions and parent functions might
assume the same GOT, and again, there's no defined way of telling whether
one function is nested within another.  Also, non-escaping static functions
can in principle be optimised to use the caller's GOT (since every
caller is then in the same input object).

So the purpose of the multigot feature is to make sure that input
objects can be linked together when each input object individually
uses less than 64k of GOT.  It can't cope with the case where
individual functions (or individual input objects) need a bigger GOT.
Like you say, any input object that requires such a big GOT must be
compiled with -mxgot.

> b) I looked at another application built in our company with same
> toolchain.  Its GOT is 188 Kb in size.
> (There are about 33000 extern symbol entries in the GOT .) I  looked
> at its linking options and did not find anything special.
> I looked  at its binary.  It is NOT in xgot mode.  Any clues ?

I'm guessing the individual objects in this case used less than 64k
of GOT each.

> c) For the above binary mentioned in  ,  I can see lot of relocation
> entries in .rel.dyn for the GOT table fixup.  From what I know,
> in MIPS,  reloc entries are not needed for GOT relocation.  Why would
> the linker output those for this binary?

MIPS multigots are a trick.  The ABI only defines a single GOT,
which I'll call the "ABI-defined" GOT.  As you say, this GOT needs
no relocations.  The information is instead provided in two ways:

  (a) Dymamic tags give the limits of the local and global parts
      of the GOT.

  (b) The global part of the GOT is directly mapped to the end
      of the dynamic symbol table.

But what do you do if you need multiple GOTs, and several GOTs
need to refer to the same symbol S?  S appears only once in the
dynamic symbol table, so it can only appear once in the ABI-defined GOT.

Multigots could only share GOT entries like this if you were able to
sort the symbols in such a way that every multigot represented a 64k
(or smaller) window into the ABI-defined GOT.  And that isn't possible
in the general case.  Objects often refer to both common symbols (like
stdio routines) and object-specific symbols.  Once you get >128k of
object-specific symbols, it isn't possible for all of them to be in
a 64k window that also contains the ABI GOT entries for the stdio
routines.

So what we do instead is create a set of entirely separate GOTs,
each <64k in size.  We designate one of them as the "primary" GOT and
refer to the others as "secondary" GOTs.  We try to put as much as
possible into the primary GOT.

The primary GOT lives at the start of the ABI-defined GOT, and is
managed in the usual relocation-free way.  The secondary GOTs are
instead just blobs of data that are relocated in the same way as
ordinary data, using the R_MIPS_REL32s that you saw.

Of course, every global symbol involved in a relocation must also
be in the ABI-defined GOT, so that GOT is often bigger than 64k.
However, the primary GOT lives at the beginning of the ABI-defined
GOT and is always <64k in size.

We could try to optimise the case where input objects (or groups
of input objects) have GOTs that don't overlap at all, but that's
so rare that I don't think it's worth bothering in practice.

Richard

[Richard Sandiford-5]

Richard Sandiford <rdsandiford@...> writes:

> MIPS multigots are a trick.  The ABI only defines a single GOT,
> which I'll call the "ABI-defined" GOT.  As you say, this GOT needs
> no relocations.  The information is instead provided in two ways:
>
>   (a) Dymamic tags give the limits of the local and global parts
>       of the GOT.
>
>   (b) The global part of the GOT is directly mapped to the end
>       of the dynamic symbol table.
>
> But what do you do if you need multiple GOTs, and several GOTs
> need to refer to the same symbol S?  S appears only once in the
> dynamic symbol table, so it can only appear once in the ABI-defined GOT.
>
> Multigots could only share GOT entries like this if you were able to
> sort the symbols in such a way that every multigot represented a 64k
> (or smaller) window into the ABI-defined GOT.  And that isn't possible
> in the general case.  Objects often refer to both common symbols (like
> stdio routines) and object-specific symbols.  Once you get >128k of
> object-specific symbols, it isn't possible for all of them to be in
> a 64k window that also contains the ABI GOT entries for the stdio
> routines.

I forgot an even more important restriction: the local part of the
ABI-defined GOT has to come before the global part.  In practice,
almost all GOTs have some local entries, so this would restrict
the windows even further.

Richard

[Uma shankar]

On Wed, Oct 14, 2009 at 1:06 AM, Richard Sandiford
<rdsandiford@...> wrote:

> The primary GOT lives at the start of the ABI-defined GOT, and is
> managed in the usual relocation-free way.  The secondary GOTs are
> instead just blobs of data that are relocated in the same way as
> ordinary data, using the R_MIPS_REL32s that you saw.
>
> Of course, every global symbol involved in a relocation must also
> be in the ABI-defined GOT, so that GOT is often bigger than 64k.
> However, the primary GOT lives at the beginning of the ABI-defined
> GOT and is always <64k in size.
>
> We could try to optimise the case where input objects (or groups
> of input objects) have GOTs that don't overlap at all, but that's
> so rare that I don't think it's worth bothering in practice.
>
> Richard
>
>

Thanks for the reply.
What qualifies a  symbol to be put in primary GOT ?  Is this just  on
"as seen" basis during linking ?

Suppose i am linking  3 files  a.o , b.o  and c.o  into  a
dynamically-linked executable.
Also,  assume that  each of these 3 files  access 16 K globals ( local
+ extern ). Out of this, let
4K be  common symbols , such as  from libc.

The simple way of creating GOT of the exe will be to put  entries for
all globals of a.o  in primary GOT .
And the entries for b.o and c.o  will be "blobs of data" you mention -
to be relocated dynamically.

But I assume  it will not be done this way.  The common symbols  may
get a preferential place in primary GOT. If so,
I  have not understood the reason.

I do not understand how the functions inside a.o, b.o and c.o can
access the common symbols  without  duplicating those
symbols in primary and secondary GOTs . ( I did look at  .rel section
of an  exe and  did find multiple
entries for some common symbols like printf )

Also, how is the best multigot layout found - the one with least
duplicated entries ?

Sorry, if my questions are silly.  I am new to MIPS and linker concepts.

( What is a forced-local symbol ? Is this same as static variables in
C language ? )

                 shankar

[Richard Sandiford-5]

Uma shankar <shankar.vk@...> writes:

> On Wed, Oct 14, 2009 at 1:06 AM, Richard Sandiford
> <rdsandiford@...> wrote:
>> The primary GOT lives at the start of the ABI-defined GOT, and is
>> managed in the usual relocation-free way.  The secondary GOTs are
>> instead just blobs of data that are relocated in the same way as
>> ordinary data, using the R_MIPS_REL32s that you saw.
>>
>> Of course, every global symbol involved in a relocation must also
>> be in the ABI-defined GOT, so that GOT is often bigger than 64k.
>> However, the primary GOT lives at the beginning of the ABI-defined
>> GOT and is always <64k in size.
>>
>> We could try to optimise the case where input objects (or groups
>> of input objects) have GOTs that don't overlap at all, but that's
>> so rare that I don't think it's worth bothering in practice.
>>
>> Richard
>>
>>
>
> Thanks for the reply.
> What qualifies a  symbol to be put in primary GOT ?  Is this just  on
> "as seen" basis during linking ?
>
> Suppose i am linking  3 files  a.o , b.o  and c.o  into  a
> dynamically-linked executable.
> Also,  assume that  each of these 3 files  access 16 K globals ( local
> + extern ). Out of this, let
> 4K be  common symbols , such as  from libc.
>
> The simple way of creating GOT of the exe will be to put  entries for
> all globals of a.o  in primary GOT .
> And the entries for b.o and c.o  will be "blobs of data" you mention -
> to be relocated dynamically.
>
> But I assume  it will not be done this way.  The common symbols  may
> get a preferential place in primary GOT. If so,
> I  have not understood the reason.

I'm not sure I understand the question, sorry.

> I do not understand how the functions inside a.o, b.o and c.o can
> access the common symbols  without  duplicating those
> symbols in primary and secondary GOTs . ( I did look at  .rel section
> of an  exe and  did find multiple
> entries for some common symbols like printf )

Exactly.  That's the point I was trying to make.  We sometimes need to
duplicate symbols in order to keep everything within range of a 16-bit
load offset.  And the problem is that the ABI-defined, reloc-free GOT
scheme you were asking about only allows a symbol to be mentioned once.
We therefore add secondary GOTs that are (from an ABI point of view)
just "blobs of data" that are relocated by R_MIPS_REL.  Those blobs of
data all refer to symbols in the ABI-defined GOT, since every symbol
mentioned in a relocation must also be in the ABI-defined GOT.

In other words, every entry in a secondary GOT duplicates a symbol
in the ABI-defined GOT.

> Also, how is the best multigot layout found - the one with least
> duplicated entries ?

We don't work too hard on that.  It's an NP-complete problem.
We just go through each input object in turn and try the following
three things, in order:

  - use the primary GOT
  - use the last-used secondary GOT
  - create a new secondary GOT

(This algorithm is from memory, so sorry if I'm oversimplifying.)

Richard

[Uma shankar]

On Tue, Nov 10, 2009 at 1:29 AM, Richard Sandiford
<rdsandiford@...> wrote:

>
> I'm not sure I understand the question, sorry.
>
>> I do not understand how the functions inside a.o, b.o and c.o can
>> access the common symbols  without  duplicating those
>> symbols in primary and secondary GOTs . ( I did look at  .rel section
>> of an  exe and  did find multiple
>> entries for some common symbols like printf )
>
> Exactly.  That's the point I was trying to make.  We sometimes need to
> duplicate symbols in order to keep everything within range of a 16-bit
> load offset.  And the problem is that the ABI-defined, reloc-free GOT
> scheme you were asking about only allows a symbol to be mentioned once.
> We therefore add secondary GOTs that are (from an ABI point of view)
> just "blobs of data" that are relocated by R_MIPS_REL.  Those blobs of
> data all refer to symbols in the ABI-defined GOT, since every symbol
> mentioned in a relocation must also be in the ABI-defined GOT.
>
> In other words, every entry in a secondary GOT duplicates a symbol
> in the ABI-defined GOT.
>
>> Also, how is the best multigot layout found - the one with least
>> duplicated entries ?
>
> We don't work too hard on that.  It's an NP-complete problem.
> We just go through each input object in turn and try the following
> three things, in order:
>
>  - use the primary GOT
>  - use the last-used secondary GOT
>  - create a new secondary GOT
>
> (This algorithm is from memory, so sorry if I'm oversimplifying.)
>
> Richard
>

ok.
I have a bit of understanding now.

I guess i will have to figure out the rest  by some analysis and
searching the mailing lists for information .
The linker code itself will take much more time to understand.

There  is no other source of information on MIPS linker internals,  I suppose.

[ As I mentioned in the first post, my  official task is to create
some  obj files and try to link them into a  shared-library This
linking should  fail  due to the reasons that are addressed by the
patch  posted at
http://sourceware.org/ml/binutils/2008-06/msg00270.html .
And later, with the patched loader,  it should link.

So, I have to understand what data and function accesses should be
present in the objs for that problem to occur.
I  won't ask for it ;  but I  won't mind  getting some clue from you.   =;)  ]

               thanks
               shankar