Multiple relocation in ELF

Multiple relocation in ELF

[Santosh]

Hi 

I have a query regarding relocation in ELF

I come across some thing like 

ADDIU r2, RELOCATABLE_SYMBOL + RELOCATABLE_SYMBOL 

In ELF, we can emit relocation information for only one symbol having
its symbol index, offset and relocation value to apply. But when I try
to give more than one relocatable symbol, it cannot be represented by
ELF format. 

I checked the MIPS ABI document, in that nothing is mentioned about
multiple relocation support. 

Is our understanding is correct or is there any other way to support. 
Please give your inputs 

Thank you
I Santhosh

Re: Multiple relocation in ELF

[Alan Modra]

On Mon, Jul 24, 2006 at 04:22:41PM +0530, Santosh wrote:
> ADDIU r2, RELOCATABLE_SYMBOL + RELOCATABLE_SYMBOL 
> 
> In ELF, we can emit relocation information for only one symbol having
> its symbol index, offset and relocation value to apply. But when I try
> to give more than one relocatable symbol, it cannot be represented by
> ELF format. 

ELF can support multiple symbols in a relocation expression.  The trick
is to apply multiple suitably defined relocations to the one location.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: Multiple relocation in ELF

[Michael Eager]

Alan Modra wrote:
> On Mon, Jul 24, 2006 at 04:22:41PM +0530, Santosh wrote:
>> ADDIU r2, RELOCATABLE_SYMBOL + RELOCATABLE_SYMBOL 
>>
>> In ELF, we can emit relocation information for only one symbol having
>> its symbol index, offset and relocation value to apply. But when I try
>> to give more than one relocatable symbol, it cannot be represented by
>> ELF format. 
> 
> ELF can support multiple symbols in a relocation expression.  The trick
> is to apply multiple suitably defined relocations to the one location.

Alan --

Can you give an example of how this might be done?  I don't think that
it is possible to apply two relocations to a single location in ELF.

I can think of one way that this might work, but it's problematic:

If the relocations are in REL format, the addend is saved in the
object file.  (If RELA is used, the addend is in the reloc entry.)
In either case, it seems that the result value from the first
relocation will computed and stored in the output, then overwritten
by the computation of the second relocation.  The only way that
these two relocations could be composed is if REL format is used,
and the result of the relocation overwrote the value in the *input*
object file, so that the result value from the first relocation
is used as the addend of the second.

If this is the scheme, I don't think that this behavior is defined
by the ELF spec.

-- 
Michael Eager	 eager@eagercon.com
1960 Park Blvd., Palo Alto, CA 94306  650-325-8077

Re: Multiple relocation in ELF

[Ian Lance Taylor]

Michael Eager <eager@eagercon.com> writes:

> Can you give an example of how this might be done?  I don't think that
> it is possible to apply two relocations to a single location in ELF.

You need to write the relocation semantics so that it will work.  It
won't work in general.

The 64-bit MIPS ABI is an example of a processor supplement which
applies multiple relocations to a single address.  However, it does it
in a different way, by changing the reloc format.

In general it's very odd to want to add two relocatable symbols.  The
result is unlikely to be useful.

Ian

Re: Multiple relocation in ELF

[Alan Modra]

On Mon, Jul 24, 2006 at 11:26:27AM -0700, Michael Eager wrote:
> Alan Modra wrote:
> >ELF can support multiple symbols in a relocation expression.  The trick
> >is to apply multiple suitably defined relocations to the one location.
> 
> Can you give an example of how this might be done?  I don't think that
> it is possible to apply two relocations to a single location in ELF.

Suppose you want to calculate 32-bit expressions of the form

  (sym1 + addend) * sym2

then use two relocs R_XYZ_ADDR32 and R_XYZ_MULT32 at the same location,
with the MULT32 reloc appearing after the ADDR32 one.
R_XYZ_ADDR32 operates as per usual ELF relocs, calculating sym + addend
and storing to the section contents.  R_XYZ_MULT32 is defined to read
the section contents and multiply that value by sym, then store the
result back to the section.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: Multiple relocation in ELF

[David Daney]

Ian Lance Taylor wrote:
> Michael Eager <eager@eagercon.com> writes:
> 
> 
>>Can you give an example of how this might be done?  I don't think that
>>it is possible to apply two relocations to a single location in ELF.
> 
> 
> You need to write the relocation semantics so that it will work.  It
> won't work in general.
> 
> The 64-bit MIPS ABI is an example of a processor supplement which
> applies multiple relocations to a single address.  However, it does it
> in a different way, by changing the reloc format.
> 

Just a couple of days ago on gcc@gcc.gnu.org, this very point came up. 
It turns out that generating jump tables for case statements is one 
place where this could be of use.  If the jump table is in a different 
section than the code, you might need relocations to evaluate the 
distance between two symbols.

David Daney.

Re: Multiple relocation in ELF

[Ian Lance Taylor]

David Daney <ddaney@avtrex.com> writes:

> Ian Lance Taylor wrote:
> > Michael Eager <eager@eagercon.com> writes:
> >
> >>Can you give an example of how this might be done?  I don't think that
> >>it is possible to apply two relocations to a single location in ELF.
> > You need to write the relocation semantics so that it will work.  It
> > won't work in general.
> > The 64-bit MIPS ABI is an example of a processor supplement which
> > applies multiple relocations to a single address.  However, it does it
> > in a different way, by changing the reloc format.
> >
> 
> Just a couple of days ago on gcc@gcc.gnu.org, this very point came
> up. It turns out that generating jump tables for case statements is
> one place where this could be of use.  If the jump table is in a
> different section than the code, you might need relocations to
> evaluate the distance between two symbols.

Note that you can always do a jump table using a PC relative
relocation against a single symbol, plus an addend.  However, I agree
that in some cases it can be useful to be able to have a relocation
which represents the difference between two symbols.  I do question
whether it is ever useful to have a relocation which represents the
sum of two symbols.

Ian

RE: Multiple relocation in ELF

[Dave Korn]

On 25 July 2006 05:20, Ian Lance Taylor wrote:


>  I do question
> whether it is ever useful to have a relocation which represents the
> sum of two symbols.


  Could be if you were planning to divide the result by two, perhaps!  (I
agree it's a bit of a stretch...)

    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

Re: Multiple relocation in ELF

[Paul Koning]

>>>>> "Ian" == Ian Lance Taylor <iant@google.com> writes:

 Ian> Note that you can always do a jump table using a PC relative
 Ian> relocation against a single symbol, plus an addend.  However, I
 Ian> agree that in some cases it can be useful to be able to have a
 Ian> relocation which represents the difference between two symbols.
 Ian> I do question whether it is ever useful to have a relocation
 Ian> which represents the sum of two symbols.

I don't have examples readily at hand.  However, what was then called
"complex relocation" was supported, AND was used in real world
software, in DEC assemblers going back all the way to Macro-11 back in
1974 or so.  In other words, ELF apparently has trouble representing
things that other binary formats have handled for 30 years.

     paul

Re: Multiple relocation in ELF

[Richard Earnshaw]

On Mon, 2006-07-24 at 19:26, Michael Eager wrote:
> Alan Modra wrote:
> > On Mon, Jul 24, 2006 at 04:22:41PM +0530, Santosh wrote:
> >> ADDIU r2, RELOCATABLE_SYMBOL + RELOCATABLE_SYMBOL 
> >>
> >> In ELF, we can emit relocation information for only one symbol having
> >> its symbol index, offset and relocation value to apply. But when I try
> >> to give more than one relocatable symbol, it cannot be represented by
> >> ELF format. 
> > 
> > ELF can support multiple symbols in a relocation expression.  The trick
> > is to apply multiple suitably defined relocations to the one location.
> 
> Alan --
> 
> Can you give an example of how this might be done?  I don't think that
> it is possible to apply two relocations to a single location in ELF.
> 
> I can think of one way that this might work, but it's problematic:
> 
> If the relocations are in REL format, the addend is saved in the
> object file.  (If RELA is used, the addend is in the reloc entry.)
> In either case, it seems that the result value from the first
> relocation will computed and stored in the output, then overwritten
> by the computation of the second relocation.  The only way that
> these two relocations could be composed is if REL format is used,
> and the result of the relocation overwrote the value in the *input*
> object file, so that the result value from the first relocation
> is used as the addend of the second.
> 
> If this is the scheme, I don't think that this behavior is defined
> by the ELF spec.

The ELF spec is pretty specific on this issue.  It's known as a composed
sequence

- Multiple relocations on the same place must all be of the same type
(all REL or all RELA).
- Composed relocations are processed in order in the table
- The initial addend for the first relocation in the sequence is
extracted as normal
- Subsequent relocations use the result of the previous relocation
calculation as the initial addend value.

The result is only written back at the end of the composed sequence.

Note, however, that since all relocations are machine specific the rules
can be varied somewhat.  In particular a relocation code can be
specified to terminate a sequence or to start a new one.

R.

Re: Multiple relocation in ELF

[Michael Eager]

Richard Earnshaw wrote:
> On Mon, 2006-07-24 at 19:26, Michael Eager wrote:
>> Alan Modra wrote:
>>> On Mon, Jul 24, 2006 at 04:22:41PM +0530, Santosh wrote:
>>>> ADDIU r2, RELOCATABLE_SYMBOL + RELOCATABLE_SYMBOL 
>>>>
>>>> In ELF, we can emit relocation information for only one symbol having
>>>> its symbol index, offset and relocation value to apply. But when I try
>>>> to give more than one relocatable symbol, it cannot be represented by
>>>> ELF format. 
>>> ELF can support multiple symbols in a relocation expression.  The trick
>>> is to apply multiple suitably defined relocations to the one location.
>> Alan --
>>
>> Can you give an example of how this might be done?  I don't think that
>> it is possible to apply two relocations to a single location in ELF.
>>
>> I can think of one way that this might work, but it's problematic:
>>
>> If the relocations are in REL format, the addend is saved in the
>> object file.  (If RELA is used, the addend is in the reloc entry.)
>> In either case, it seems that the result value from the first
>> relocation will computed and stored in the output, then overwritten
>> by the computation of the second relocation.  The only way that
>> these two relocations could be composed is if REL format is used,
>> and the result of the relocation overwrote the value in the *input*
>> object file, so that the result value from the first relocation
>> is used as the addend of the second.
>>
>> If this is the scheme, I don't think that this behavior is defined
>> by the ELF spec.
> 
> The ELF spec is pretty specific on this issue.  It's known as a composed
> sequence
> 
> - Multiple relocations on the same place must all be of the same type
> (all REL or all RELA).
> - Composed relocations are processed in order in the table
> - The initial addend for the first relocation in the sequence is
> extracted as normal
> - Subsequent relocations use the result of the previous relocation
> calculation as the initial addend value.
> 
> The result is only written back at the end of the composed sequence.
> 
> Note, however, that since all relocations are machine specific the rules
> can be varied somewhat.  In particular a relocation code can be
> specified to terminate a sequence or to start a new one.

Thanks.  You're right -- it is specified in the ELF 4.1 draft.


-- 
Michael Eager	 eager@eagercon.com
1960 Park Blvd., Palo Alto, CA 94306  650-325-8077

Re: Multiple relocation in ELF

[Ian Lance Taylor]

Paul Koning <pkoning@equallogic.com> writes:

> >>>>> "Ian" == Ian Lance Taylor <iant@google.com> writes:
> 
>  Ian> Note that you can always do a jump table using a PC relative
>  Ian> relocation against a single symbol, plus an addend.  However, I
>  Ian> agree that in some cases it can be useful to be able to have a
>  Ian> relocation which represents the difference between two symbols.
>  Ian> I do question whether it is ever useful to have a relocation
>  Ian> which represents the sum of two symbols.
> 
> I don't have examples readily at hand.  However, what was then called
> "complex relocation" was supported, AND was used in real world
> software, in DEC assemblers going back all the way to Macro-11 back in
> 1974 or so.  In other words, ELF apparently has trouble representing
> things that other binary formats have handled for 30 years.

That is certainly true.  The IEEE object file format, for example, can
represent any arbitrary expression when computing relocations.

The ELF approach--a fixed set of relocations with predefined
algorithms--is used because it works for 99.99% of programs,
specifically including all pure C/C++ programs, and it permits the
linker to run faster.  And, of course, it is extensible when new
relocation algorithms are needed.

Ian

Re: Multiple relocation in ELF

[Paul Brook]

> Note that you can always do a jump table using a PC relative
> relocation against a single symbol, plus an addend.

Not always. You may want to put the table itself in .rodata (to reduce code 
size for better constant pool placement), and have the values in the table be 
relative to the branch instruction. Especially with hot/cold partitioning 
there's no guarantee that both the jump and the target will be in the same 
section. eg:

.section rodata
table:
  .word label1 - label2

.section text.hot
label2:
  branch (pc + load(table + reg))

.section text.cold
label1:
  code

Paul

Re: Multiple relocation in ELF

[Ian Lance Taylor]

Paul Brook <paul@codesourcery.com> writes:

> > Note that you can always do a jump table using a PC relative
> > relocation against a single symbol, plus an addend.
> 
> Not always. You may want to put the table itself in .rodata (to reduce code 
> size for better constant pool placement), and have the values in the table be 
> relative to the branch instruction. Especially with hot/cold partitioning 
> there's no guarantee that both the jump and the target will be in the same 
> section. eg:

I agree that that case won't work, but I stand by my statement.  You
do have to make the values in the table be relative to the start of
the table.  That is a restriction, but it is unlikely to be a serious
one.  You have to put the address of the table into a register either
way, and then you have to load the branch offset either way.  The
question then is whether you want to jump to the sum of two registers
(which generally means an addition followed by a jump to register
indirect), or jump to a PC relative address plus a register.  Most
modern processors generally do not have an instruction which jumps to
a PC relative address plus a register (if you need a separate
addition, then you might as well use the other approach).

(I agree that in the specific case of such a processor, it would be
desirable to define a relocation pair which can compute the different
of two arbitrary symbols.  Such a relocation pair is conceptually no
different than, e.g., R_MIPS_HI16/R_MIPS_LO16.)

Ian

RE: Multiple relocation in ELF

[Santosh]

> -----Original Message-----
> From: Michael Eager [mailto:eager@eagercon.com]
> Sent: Tuesday, July 25, 2006 6:22 PM
> To: Richard Earnshaw
> Cc: Santosh; binutils@sourceware.org
> Subject: Re: Multiple relocation in ELF
> 
> Richard Earnshaw wrote:
> > On Mon, 2006-07-24 at 19:26, Michael Eager wrote:
> >> Alan Modra wrote:
> >>> On Mon, Jul 24, 2006 at 04:22:41PM +0530, Santosh wrote:
> >>>> ADDIU r2, RELOCATABLE_SYMBOL + RELOCATABLE_SYMBOL
> >>>>
> >>>> In ELF, we can emit relocation information for only one symbol
having
> >>>> its symbol index, offset and relocation value to apply. But when
I
> try
> >>>> to give more than one relocatable symbol, it cannot be
represented by
> >>>> ELF format.
> >>> ELF can support multiple symbols in a relocation expression.  The
> trick
> >>> is to apply multiple suitably defined relocations to the one
location.
> >> Alan --
> >>
> >> Can you give an example of how this might be done?  I don't think
that
> >> it is possible to apply two relocations to a single location in
ELF.
> >>
> >> I can think of one way that this might work, but it's problematic:
> >>
> >> If the relocations are in REL format, the addend is saved in the
> >> object file.  (If RELA is used, the addend is in the reloc entry.)
> >> In either case, it seems that the result value from the first
> >> relocation will computed and stored in the output, then overwritten
> >> by the computation of the second relocation.  The only way that
> >> these two relocations could be composed is if REL format is used,
> >> and the result of the relocation overwrote the value in the *input*
> >> object file, so that the result value from the first relocation
> >> is used as the addend of the second.
> >>
> >> If this is the scheme, I don't think that this behavior is defined
> >> by the ELF spec.
> >
> > The ELF spec is pretty specific on this issue.  It's known as a
composed
> > sequence
> >
> > - Multiple relocations on the same place must all be of the same
type
> > (all REL or all RELA).
> > - Composed relocations are processed in order in the table
> > - The initial addend for the first relocation in the sequence is
> > extracted as normal
> > - Subsequent relocations use the result of the previous relocation
> > calculation as the initial addend value.
> >
> > The result is only written back at the end of the composed sequence.
> >
> > Note, however, that since all relocations are machine specific the
rules
> > can be varied somewhat.  In particular a relocation code can be
> > specified to terminate a sequence or to start a new one.
> 
> Thanks.  You're right -- it is specified in the ELF 4.1 draft.
> 

Please provide the link for ELF 4.1 draft.

Thank you
I Santhosh

Re: Multiple relocation in ELF

[Ian Lance Taylor]

"Santosh" <santosh@acmet.com> writes:

> Please provide the link for ELF 4.1 draft.

http://sco.com/developers/gabi/

Ian

RE: Multiple relocation in ELF

[Santosh]

Thank you for sending the link, I will check them. 

I Santhosh

> -----Original Message-----
> From: binutils-owner@sourceware.org
[mailto:binutils-owner@sourceware.org]
> On Behalf Of Ian Lance Taylor
> Sent: Wednesday, July 26, 2006 8:19 PM
> To: santosh@acmet.com
> Cc: binutils@sourceware.org
> Subject: Re: Multiple relocation in ELF
> 
> "Santosh" <santosh@acmet.com> writes:
> 
> > Please provide the link for ELF 4.1 draft.
> 
> http://sco.com/developers/gabi/
> 
> Ian