RFH/RFC: symbol index overflow in MIPS linker stubs...

RFH/RFC: symbol index overflow in MIPS linker stubs...

[David Daney]

I am doing some testing of the gcj java compiler that is part of 
gcc-4.2, and have come across a problem.

This is the ld version I am using:
$ mipsel-linux-ld --version
GNU ld version 2.16.91 20050817

libgcj.so.7 contains more than 2^15 symbols in its symbol table.  If a 
linker stub requires an index for a symbol that has an index greater 
than 2^15, then the index gets sign extended into a negative number. 
The result is a SIGSEGV at runtime when ld.so tries to look up the 
symbol with a negative index.

Here is a dissassembly that shows the problem:


  # objdump -d -z -j .MIPS.stubs /lib/libgcj.so.7

/lib/libgcj.so.7:     file format elf32-tradlittlemips

Disassembly of section .MIPS.stubs:

01597f40 <.MIPS.stubs>:
  1597f40:       8f998010        lw      t9,-32752(gp)
  1597f44:       03e07821        move    t7,ra
  1597f48:       0320f809        jalr    t9
  1597f4c:       241897cd        li      t8,-26675
  1597f50:       8f998010        lw      t9,-32752(gp)
  1597f54:       03e07821        move    t7,ra
  1597f58:       0320f809        jalr    t9
  1597f5c:       241897b2        li      t8,-26702


Note that the symbol index loaded into t8 is negative.

I think we could easily change the stubs so that they used ori (an 
unsigned immediate load), instead of li.  This would work for symbol 
tables of size up to 2^16.

FWIW: I tested this theory by hand editing the stubs to use the unsigned 
immediate load and the library now runs correctly.

A second option might be to use a two instruction sequence to load t8, 
but that would change the size of the stubs.  I don't know if that would 
be portable or possible.

Comments please.

David Daney

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[Thiemo Seufer]

David Daney wrote:
> I am doing some testing of the gcj java compiler that is part of 
> gcc-4.2, and have come across a problem.
> 
> This is the ld version I am using:
> $ mipsel-linux-ld --version
> GNU ld version 2.16.91 20050817
> 
> libgcj.so.7 contains more than 2^15 symbols in its symbol table.  If a 
> linker stub requires an index for a symbol that has an index greater 
> than 2^15, then the index gets sign extended into a negative number. 
> The result is a SIGSEGV at runtime when ld.so tries to look up the 
> symbol with a negative index.

Thank you for debugging this long-standing problem.

> Here is a dissassembly that shows the problem:
> 
> 
>  # objdump -d -z -j .MIPS.stubs /lib/libgcj.so.7
> 
> /lib/libgcj.so.7:     file format elf32-tradlittlemips
> 
> Disassembly of section .MIPS.stubs:
> 
> 01597f40 <.MIPS.stubs>:
>  1597f40:       8f998010        lw      t9,-32752(gp)
>  1597f44:       03e07821        move    t7,ra
>  1597f48:       0320f809        jalr    t9
>  1597f4c:       241897cd        li      t8,-26675
>  1597f50:       8f998010        lw      t9,-32752(gp)
>  1597f54:       03e07821        move    t7,ra
>  1597f58:       0320f809        jalr    t9
>  1597f5c:       241897b2        li      t8,-26702
> 
> 
> Note that the symbol index loaded into t8 is negative.
> 
> I think we could easily change the stubs so that they used ori (an 
> unsigned immediate load), instead of li.  This would work for symbol 
> tables of size up to 2^16.
> 
> FWIW: I tested this theory by hand editing the stubs to use the unsigned 
> immediate load and the library now runs correctly.

That's STUB_LI16 in bfd/elfxx-mips.c:635, used at line 8020. The FIXME
immediately above the latter line is also interesting.

> A second option might be to use a two instruction sequence to load t8, 
> but that would change the size of the stubs.  I don't know if that would 
> be portable or possible.
> 
> Comments please.

I would favour a two instruction sequence, applications will continue to
grow. There might be some compatibility traps, but at a superficial
glance I haven't found an obvious blocker.


Thiemo

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[David Daney]

Thiemo Seufer wrote:
> David Daney wrote:
> 
>>I am doing some testing of the gcj java compiler that is part of 
>>gcc-4.2, and have come across a problem.
>>
>>This is the ld version I am using:
>>$ mipsel-linux-ld --version
>>GNU ld version 2.16.91 20050817
>>
>>libgcj.so.7 contains more than 2^15 symbols in its symbol table.  If a 
>>linker stub requires an index for a symbol that has an index greater 
>>than 2^15, then the index gets sign extended into a negative number. 
>>The result is a SIGSEGV at runtime when ld.so tries to look up the 
>>symbol with a negative index.
> 
> 
> Thank you for debugging this long-standing problem.
> 
> 
>>Here is a dissassembly that shows the problem:
>>
>>
>> # objdump -d -z -j .MIPS.stubs /lib/libgcj.so.7
>>
>>/lib/libgcj.so.7:     file format elf32-tradlittlemips
>>
>>Disassembly of section .MIPS.stubs:
>>
>>01597f40 <.MIPS.stubs>:
>> 1597f40:       8f998010        lw      t9,-32752(gp)
>> 1597f44:       03e07821        move    t7,ra
>> 1597f48:       0320f809        jalr    t9
>> 1597f4c:       241897cd        li      t8,-26675
>> 1597f50:       8f998010        lw      t9,-32752(gp)
>> 1597f54:       03e07821        move    t7,ra
>> 1597f58:       0320f809        jalr    t9
>> 1597f5c:       241897b2        li      t8,-26702
>>
>>
>>Note that the symbol index loaded into t8 is negative.
>>
>>I think we could easily change the stubs so that they used ori (an 
>>unsigned immediate load), instead of li.  This would work for symbol 
>>tables of size up to 2^16.
>>
>>FWIW: I tested this theory by hand editing the stubs to use the unsigned 
>>immediate load and the library now runs correctly.
> 
> 
> That's STUB_LI16 in bfd/elfxx-mips.c:635, used at line 8020. The FIXME
> immediately above the latter line is also interesting.
> 
> 
>>A second option might be to use a two instruction sequence to load t8, 
>>but that would change the size of the stubs.  I don't know if that would 
>>be portable or possible.
>>
>>Comments please.
> 
> 
> I would favour a two instruction sequence, applications will continue to
> grow. There might be some compatibility traps, but at a superficial
> glance I haven't found an obvious blocker.
> 

Unless you want to fix it, I will work on a patch.

David Daney

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[Daniel Jacobowitz]

On Wed, Jun 07, 2006 at 08:27:59PM +0100, Thiemo Seufer wrote:
> I would favour a two instruction sequence, applications will continue to
> grow. There might be some compatibility traps, but at a superficial
> glance I haven't found an obvious blocker.

If we can change the stub sequence without ABI problems, why waste an
instruction?  Support both.

-- 
Daniel Jacobowitz
CodeSourcery

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[Thiemo Seufer]

Daniel Jacobowitz wrote:
> On Wed, Jun 07, 2006 at 08:27:59PM +0100, Thiemo Seufer wrote:
> > I would favour a two instruction sequence, applications will continue to
> > grow. There might be some compatibility traps, but at a superficial
> > glance I haven't found an obvious blocker.
> 
> If we can change the stub sequence without ABI problems, why waste an
> instruction?  Support both.

Will the stub section support varying entry sizes? I'm not sure.


Thiemo

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[Daniel Jacobowitz]

On Wed, Jun 07, 2006 at 09:03:30PM +0100, Thiemo Seufer wrote:
> Daniel Jacobowitz wrote:
> > On Wed, Jun 07, 2006 at 08:27:59PM +0100, Thiemo Seufer wrote:
> > > I would favour a two instruction sequence, applications will continue to
> > > grow. There might be some compatibility traps, but at a superficial
> > > glance I haven't found an obvious blocker.
> > 
> > If we can change the stub sequence without ABI problems, why waste an
> > instruction?  Support both.
> 
> Will the stub section support varying entry sizes? I'm not sure.

This is solveable, as a simple matter of programming, or ignorable,
by padding the shorter entries with a trailing nop.

-- 
Daniel Jacobowitz
CodeSourcery

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[David Daney]

Daniel Jacobowitz wrote:
> On Wed, Jun 07, 2006 at 09:03:30PM +0100, Thiemo Seufer wrote:
> 
>>Daniel Jacobowitz wrote:
>>
>>>On Wed, Jun 07, 2006 at 08:27:59PM +0100, Thiemo Seufer wrote:
>>>
>>>>I would favour a two instruction sequence, applications will continue to
>>>>grow. There might be some compatibility traps, but at a superficial
>>>>glance I haven't found an obvious blocker.
>>>
>>>If we can change the stub sequence without ABI problems, why waste an
>>>instruction?  Support both.
>>
>>Will the stub section support varying entry sizes? I'm not sure.
> 
> 
> This is solveable, as a simple matter of programming, or ignorable,
> by padding the shorter entries with a trailing nop.
> 

I think the best option is to unconditionally increase the stub size by 
4 bytes.  The value of MIPS_FUNCTION_STUB_SIZE is used in quite a few 
places in elfxx-mips.c, so it seems a bit risky to change it for 
variable size stubs.

I am working on a patch now.

David Daney.

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[Thiemo Seufer]

Daniel Jacobowitz wrote:
> On Wed, Jun 07, 2006 at 09:03:30PM +0100, Thiemo Seufer wrote:
> > Daniel Jacobowitz wrote:
> > > On Wed, Jun 07, 2006 at 08:27:59PM +0100, Thiemo Seufer wrote:
> > > > I would favour a two instruction sequence, applications will continue to
> > > > grow. There might be some compatibility traps, but at a superficial
> > > > glance I haven't found an obvious blocker.
> > > 
> > > If we can change the stub sequence without ABI problems, why waste an
> > > instruction?  Support both.
> > 
> > Will the stub section support varying entry sizes? I'm not sure.
> 
> This is solveable, as a simple matter of programming, or ignorable,
> by padding the shorter entries with a trailing nop.

The first two entries are handled specially, this makes the second
option more likely. OTOH, saving an instruction when we have anyway
branches and memory access in between is probably not worth much.


Thiemo

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[Richard Sandiford]

David Daney <ddaney@avtrex.com> writes:
> I think we could easily change the stubs so that they used ori (an 
> unsigned immediate load), instead of li.  This would work for symbol 
> tables of size up to 2^16.
>
> FWIW: I tested this theory by hand editing the stubs to use the unsigned 
> immediate load and the library now runs correctly.
>
> A second option might be to use a two instruction sequence to load t8, 
> but that would change the size of the stubs.  I don't know if that would 
> be portable or possible.

I'm with Daniel (if I've understood him correctly): I think it _is_
worth going the extra mile and only using the longer stubs if the
largest dynindx requires it.  We know when calculating the size of
the stub section what the maximum dynindx should be, so we can select
between the 16- and 20-byte stubs at the same time.  We can then record
the chosen size in mips_elf_link_hash_table.

I'm a little worried that using longer stubs might confuse the native
IRIX tools, but I no longer have access to IRIX, so I can't check.
I don't think that's a problem for the cases that really need it --
what else can we do? -- but I think it is one reason to prefer the
traditional stubs when possible.

All FWIW.

Richard

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[Richard Sandiford]

David Daney <ddaney@avtrex.com> writes:
> There are three ways to do this:
>
> 1) Always use a 20 byte stub.  This allows for up to 2^31 - 1 dynamic 
> symbols.  You are concerned that this would break IRIX tools.

Well, "would"'s a bit a too strong.  It's only a vague "might".
It's o32 I'm particularly worried about: the o32 IRIX tools
are a bit weird.

That wouldn't be much of an argument if it wasn't fairly easy
to do #2 or #3, of course, but it does look fairly easy.

> 2) Use modified 16 byte stub if there are fewer than 2^16 dynamic 
> symbols, otherwise use new 20 byte stub.
>
> 3) Use original 16 byte stub if fewer than 2^15 - 1 dynamic symbols. 
> Modified 16 byte stub for 2^15 - 2^16 dynamic symbols.  Otherwise, use 
> the new 20 byte stub.
>
> Option #1 is easiest.  I already have a working patch.
>
> Options #2 and #3 are more work, which would you prefer?

I don't really mind.  #3 shouldn't be much harder than #2 though -- we
could just make the LI16 vary depending on the dynindx -- so I suppose
it wins as the ultra-safe option.

It's me who's being awkward here, especially since you've already
got a working patch, so I'm happy to try #3 if you like.

Richard

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[David Daney]

Richard Sandiford wrote:
> David Daney <ddaney@avtrex.com> writes:
> 
>>There are three ways to do this:
>>
>>1) Always use a 20 byte stub.  This allows for up to 2^31 - 1 dynamic 
>>symbols.  You are concerned that this would break IRIX tools.
> 
> 
> Well, "would"'s a bit a too strong.  It's only a vague "might".
> It's o32 I'm particularly worried about: the o32 IRIX tools
> are a bit weird.
> 
> That wouldn't be much of an argument if it wasn't fairly easy
> to do #2 or #3, of course, but it does look fairly easy.
> 

My main concern is that in _bfd_mips_elf_adjust_dynamic_symbol I need to 
know the size of the stub, but I am uncertain if we will know the number 
of dynamic symbols at this point so that we can choose the proper stub size.

David Daney

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[Richard Sandiford]

David Daney <ddaney@avtrex.com> writes:
> Richard Sandiford wrote:
>> David Daney <ddaney@avtrex.com> writes:
>> 
>>>There are three ways to do this:
>>>
>>>1) Always use a 20 byte stub.  This allows for up to 2^31 - 1 dynamic 
>>>symbols.  You are concerned that this would break IRIX tools.
>> 
>> 
>> Well, "would"'s a bit a too strong.  It's only a vague "might".
>> It's o32 I'm particularly worried about: the o32 IRIX tools
>> are a bit weird.
>> 
>> That wouldn't be much of an argument if it wasn't fairly easy
>> to do #2 or #3, of course, but it does look fairly easy.
>> 
>
> My main concern is that in _bfd_mips_elf_adjust_dynamic_symbol I need to 
> know the size of the stub, but I am uncertain if we will know the number 
> of dynamic symbols at this point so that we can choose the proper stub size.

AIUI, _bfd_mips_elf_adjust_dynamic_symbol is called after
_bfd_mips_elf_always_size_sections (see bfd_elf_size_dynamic_sections)
so I think we're OK there.

Richard

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[Thiemo Seufer]

Richard Sandiford wrote:
> David Daney <ddaney@avtrex.com> writes:
> > I think we could easily change the stubs so that they used ori (an 
> > unsigned immediate load), instead of li.  This would work for symbol 
> > tables of size up to 2^16.
> >
> > FWIW: I tested this theory by hand editing the stubs to use the unsigned 
> > immediate load and the library now runs correctly.
> >
> > A second option might be to use a two instruction sequence to load t8, 
> > but that would change the size of the stubs.  I don't know if that would 
> > be portable or possible.
> 
> I'm with Daniel (if I've understood him correctly): I think it _is_
> worth going the extra mile and only using the longer stubs if the
> largest dynindx requires it.

Thinking again about it, currently the stub fits in a cacheline, so
there might be a bigger performance impact than I estimated before.
IOW, I agree.

[snip]
> I'm a little worried that using longer stubs might confuse the native
> IRIX tools, but I no longer have access to IRIX, so I can't check.
> I don't think that's a problem for the cases that really need it --
> what else can we do? -- but I think it is one reason to prefer the
> traditional stubs when possible.

Probably some IRIX user is interested in testing the patch.

Thiemo

Re: RFH/RFC: symbol index overflow in MIPS linker stubs...

[David Daney]

Richard Sandiford wrote:
> David Daney <ddaney@avtrex.com> writes:
> 
>>I think we could easily change the stubs so that they used ori (an 
>>unsigned immediate load), instead of li.  This would work for symbol 
>>tables of size up to 2^16.
>>
>>FWIW: I tested this theory by hand editing the stubs to use the unsigned 
>>immediate load and the library now runs correctly.
>>
>>A second option might be to use a two instruction sequence to load t8, 
>>but that would change the size of the stubs.  I don't know if that would 
>>be portable or possible.
> 
> 
> I'm with Daniel (if I've understood him correctly): I think it _is_
> worth going the extra mile and only using the longer stubs if the
> largest dynindx requires it.  We know when calculating the size of
> the stub section what the maximum dynindx should be, so we can select
> between the 16- and 20-byte stubs at the same time.  We can then record
> the chosen size in mips_elf_link_hash_table.
> 
> I'm a little worried that using longer stubs might confuse the native
> IRIX tools, but I no longer have access to IRIX, so I can't check.
> I don't think that's a problem for the cases that really need it --
> what else can we do? -- but I think it is one reason to prefer the
> traditional stubs when possible.
> 

Thanks for looking at this.

What is your take on changing the 16 byte stub to not do sign extension? 
The stub size would remain the same, only the contents of the stub would 
change.

There are three ways to do this:

1) Always use a 20 byte stub.  This allows for up to 2^31 - 1 dynamic 
symbols.  You are concerned that this would break IRIX tools.

2) Use modified 16 byte stub if there are fewer than 2^16 dynamic 
symbols, otherwise use new 20 byte stub.

3) Use original 16 byte stub if fewer than 2^15 - 1 dynamic symbols. 
Modified 16 byte stub for 2^15 - 2^16 dynamic symbols.  Otherwise, use 
the new 20 byte stub.

Option #1 is easiest.  I already have a working patch.

Options #2 and #3 are more work, which would you prefer?

David Daney.