llvm dev - Feb 2015 - [LLVMdev] [lld] Representation of lld::Reference with a fake target

Hi,

I need an advice on implementation of a very specific kind of relocations
used by MIPS N64 ABI. As usual the main problem is how to pass target specific
data over Native/YAML conversion barrier.

In this ABI relocation record r_info field in fact consists of five subfields:
* r_sym   - symbol index
* r_ssym  - special symbol
* r_type3 - third relocation type
* r_type2 - second relocation type
* r_type  - first relocation type

Up to three these relocations applied one by one. The first relocation uses
an addendum from the relocation record. Each subsequent relocation takes as
its addend the result of the previous operation. Only the final operation
actually modifies the location relocated. The first relocation uses as
a reference symbol specified by the r_sym field. The third relocation
assumes NULL symbol.

The most interesting case is the second relocation. It uses the special
symbol value given by the r_ssym field. This field can contain four
predefined values:
* RSS_UNDEF - zero value
* RSS_GP    - value of gp symbol
* RSS_GP0   - gp0 value taken from the .MIPS.options or .reginfo section
* RSS_LOC   - address of location being relocated

So the problem is how to store these four constants in the
lld::Reference object.
The RSS_UNDEF is obviously not a problem. To represent the RSS_GP value I can
set an AbsoluteAtom created for the "_gp" as the reference's
target. But what
about RSS_GP0 and RSS_LOC? I am considering the following approaches but cannot
select the best one:

a) Create AbsoluteAtom for each of these cases and set them as the
reference's target.
   The problem is that these atoms are fake and should not go to the
symbol table.
   One more problem is to select unique names for these atoms.
b) Use two high bits of lld::Reference::_kindValue field to encode
RSS_xxx value.
   Then decode these bits in the RelocationHandler to calculate result
of relocation.
   In that case the problem is how to represent a relocation kind
value in YAML format.
   The simple xxxRelocationStringTable::kindStrings[] array will not satisfy us.
c) Add one more field to the lld::Reference class. Something like the
DefinedAtom::CodeModel
   field.

Any advices, ideas, and/or objections are much appreciated.

-- 
Simon Atanasyan

Yes, it is always a pain when we have to keep information over the
round-trip conversion from/to Native. Native format is really able to
handle only fields we define to base Atom or Reference and not a subclass
of them. This is, well, hard. This is like a roadblock that is always there
when we do something with Reference. I think this needs fixing.

I once proposed or at least suggested that we remove Native file format
from LLD. I still think that's not a bad idea at all -- no one is using
Native and thus delivers no value currently, but it imposes burden to
developers. This is not a good situation.

If we still want to maintain Native, conversion from/to Native needs to be
easier to support. I can think of a few reasons why supporting Native is
hard.

1. It is not extendable. It only recognizes base classes and not subclasses
of Atom or References.

2. The file format is designed to be mmap()'able, so that you can just mmap
the entire file and cast a struct to read it. It'd be very fast indeed --
but it can't support any optional field or something.

If I would design from scratch, I'd probably use a serializable data
structure like Protocol Buffers or Thrust to represent Atoms and
References, so that all that conversion is automatically done. They are
fast enough and easy to use.

That being said, I think the short term solution for your need is to just
add a new field to Reference.

On Thu, Feb 5, 2015 at 12:22 PM, Simon Atanasyan <simon at atanasyan.com>
wrote:
> Hi,
>
> I need an advice on implementation of a very specific kind of relocations
> used by MIPS N64 ABI. As usual the main problem is how to pass target
> specific
> data over Native/YAML conversion barrier.
>
> In this ABI relocation record r_info field in fact consists of five
> subfields:
> * r_sym   - symbol index
> * r_ssym  - special symbol
> * r_type3 - third relocation type
> * r_type2 - second relocation type
> * r_type  - first relocation type
>
> Up to three these relocations applied one by one. The first relocation uses
> an addendum from the relocation record. Each subsequent relocation takes as
> its addend the result of the previous operation. Only the final operation
> actually modifies the location relocated. The first relocation uses as
> a reference symbol specified by the r_sym field. The third relocation
> assumes NULL symbol.
>
> The most interesting case is the second relocation. It uses the special
> symbol value given by the r_ssym field. This field can contain four
> predefined values:
> * RSS_UNDEF - zero value
> * RSS_GP    - value of gp symbol
> * RSS_GP0   - gp0 value taken from the .MIPS.options or .reginfo section
> * RSS_LOC   - address of location being relocated
>
> So the problem is how to store these four constants in the
> lld::Reference object.
> The RSS_UNDEF is obviously not a problem. To represent the RSS_GP value I
> can
> set an AbsoluteAtom created for the "_gp" as the reference's
target. But
> what
> about RSS_GP0 and RSS_LOC? I am considering the following approaches but
> cannot
> select the best one:
>
> a) Create AbsoluteAtom for each of these cases and set them as the
> reference's target.
>    The problem is that these atoms are fake and should not go to the
> symbol table.
>    One more problem is to select unique names for these atoms.
> b) Use two high bits of lld::Reference::_kindValue field to encode
> RSS_xxx value.
>    Then decode these bits in the RelocationHandler to calculate result
> of relocation.
>    In that case the problem is how to represent a relocation kind
> value in YAML format.
>    The simple xxxRelocationStringTable::kindStrings[] array will not
> satisfy us.
> c) Add one more field to the lld::Reference class. Something like the
> DefinedAtom::CodeModel
>    field.
>
> Any advices, ideas, and/or objections are much appreciated.
>
> --
> Simon Atanasyan
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150205/1e25f827/attachment.html>

The only way currently is to create a new reference, unless we can think 
of adding some target specific metadata information in the Atom model.

This has come up over and over again, we need something in the Atom 
model to store information that is target specific.

Shankar Easwaran

On 2/5/2015 2:22 PM, Simon Atanasyan wrote:
> Hi,
>
> I need an advice on implementation of a very specific kind of relocations
> used by MIPS N64 ABI. As usual the main problem is how to pass target
specific
> data over Native/YAML conversion barrier.
>
> In this ABI relocation record r_info field in fact consists of five
subfields:
> * r_sym   - symbol index
> * r_ssym  - special symbol
> * r_type3 - third relocation type
> * r_type2 - second relocation type
> * r_type  - first relocation type
>
> Up to three these relocations applied one by one. The first relocation uses
> an addendum from the relocation record. Each subsequent relocation takes as
> its addend the result of the previous operation. Only the final operation
> actually modifies the location relocated. The first relocation uses as
> a reference symbol specified by the r_sym field. The third relocation
> assumes NULL symbol.
>
> The most interesting case is the second relocation. It uses the special
> symbol value given by the r_ssym field. This field can contain four
> predefined values:
> * RSS_UNDEF - zero value
> * RSS_GP    - value of gp symbol
> * RSS_GP0   - gp0 value taken from the .MIPS.options or .reginfo section
> * RSS_LOC   - address of location being relocated
>
> So the problem is how to store these four constants in the
> lld::Reference object.
> The RSS_UNDEF is obviously not a problem. To represent the RSS_GP value I
can
> set an AbsoluteAtom created for the "_gp" as the reference's
target. But what
> about RSS_GP0 and RSS_LOC? I am considering the following approaches but
cannot
> select the best one:
>
> a) Create AbsoluteAtom for each of these cases and set them as the
> reference's target.
>     The problem is that these atoms are fake and should not go to the
> symbol table.
>     One more problem is to select unique names for these atoms.
> b) Use two high bits of lld::Reference::_kindValue field to encode
> RSS_xxx value.
>     Then decode these bits in the RelocationHandler to calculate result
> of relocation.
>     In that case the problem is how to represent a relocation kind
> value in YAML format.
>     The simple xxxRelocationStringTable::kindStrings[] array will not
satisfy us.
> c) Add one more field to the lld::Reference class. Something like the
> DefinedAtom::CodeModel
>     field.
>
> Any advices, ideas, and/or objections are much appreciated.
>

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by the
Linux Foundation

Can we remove Native format support? I'd like to get input from anyone who
wants to keep the current Native format in LLD.

On Thu, Feb 5, 2015 at 2:03 PM, Shankar Easwaran <shankare at
codeaurora.org>
wrote:
> The only way currently is to create a new reference, unless we can think
> of adding some target specific metadata information in the Atom model.
>
> This has come up over and over again, we need something in the Atom model
> to store information that is target specific.
>
> Shankar Easwaran
>
>
> On 2/5/2015 2:22 PM, Simon Atanasyan wrote:
>
>> Hi,
>>
>> I need an advice on implementation of a very specific kind of
relocations
>> used by MIPS N64 ABI. As usual the main problem is how to pass target
>> specific
>> data over Native/YAML conversion barrier.
>>
>> In this ABI relocation record r_info field in fact consists of five
>> subfields:
>> * r_sym   - symbol index
>> * r_ssym  - special symbol
>> * r_type3 - third relocation type
>> * r_type2 - second relocation type
>> * r_type  - first relocation type
>>
>> Up to three these relocations applied one by one. The first relocation
>> uses
>> an addendum from the relocation record. Each subsequent relocation
takes
>> as
>> its addend the result of the previous operation. Only the final
operation
>> actually modifies the location relocated. The first relocation uses as
>> a reference symbol specified by the r_sym field. The third relocation
>> assumes NULL symbol.
>>
>> The most interesting case is the second relocation. It uses the special
>> symbol value given by the r_ssym field. This field can contain four
>> predefined values:
>> * RSS_UNDEF - zero value
>> * RSS_GP    - value of gp symbol
>> * RSS_GP0   - gp0 value taken from the .MIPS.options or .reginfo
section
>> * RSS_LOC   - address of location being relocated
>>
>> So the problem is how to store these four constants in the
>> lld::Reference object.
>> The RSS_UNDEF is obviously not a problem. To represent the RSS_GP value
I
>> can
>> set an AbsoluteAtom created for the "_gp" as the
reference's target. But
>> what
>> about RSS_GP0 and RSS_LOC? I am considering the following approaches
but
>> cannot
>> select the best one:
>>
>> a) Create AbsoluteAtom for each of these cases and set them as the
>> reference's target.
>>     The problem is that these atoms are fake and should not go to the
>> symbol table.
>>     One more problem is to select unique names for these atoms.
>> b) Use two high bits of lld::Reference::_kindValue field to encode
>> RSS_xxx value.
>>     Then decode these bits in the RelocationHandler to calculate result
>> of relocation.
>>     In that case the problem is how to represent a relocation kind
>> value in YAML format.
>>     The simple xxxRelocationStringTable::kindStrings[] array will not
>> satisfy us.
>> c) Add one more field to the lld::Reference class. Something like the
>> DefinedAtom::CodeModel
>>     field.
>>
>> Any advices, ideas, and/or objections are much appreciated.
>>
>>
>
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
> by the Linux Foundation
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150206/1e3d7aa0/attachment.html>

Simon,

Sounds like the instruction relocating is so complicated that ELF requires up to
three relocation records to encode how to fix up one instruction.  If that is
the case, why not do the same and have up to three Reference objects on the same
atom offset to record the same info?  I thought that was model that the ELF part
of lld was using - there is a one-to-one mapping of ELF reloc to lld References.

Or am I misunderstanding the issue?

-Nick


On Feb 5, 2015, at 12:22 PM, Simon Atanasyan <simon at atanasyan.com>
wrote:
> Hi,
> 
> I need an advice on implementation of a very specific kind of relocations
> used by MIPS N64 ABI. As usual the main problem is how to pass target
specific
> data over Native/YAML conversion barrier.
> 
> In this ABI relocation record r_info field in fact consists of five
subfields:
> * r_sym   - symbol index
> * r_ssym  - special symbol
> * r_type3 - third relocation type
> * r_type2 - second relocation type
> * r_type  - first relocation type
> 
> Up to three these relocations applied one by one. The first relocation uses
> an addendum from the relocation record. Each subsequent relocation takes as
> its addend the result of the previous operation. Only the final operation
> actually modifies the location relocated. The first relocation uses as
> a reference symbol specified by the r_sym field. The third relocation
> assumes NULL symbol.
> 
> The most interesting case is the second relocation. It uses the special
> symbol value given by the r_ssym field. This field can contain four
> predefined values:
> * RSS_UNDEF - zero value
> * RSS_GP    - value of gp symbol
> * RSS_GP0   - gp0 value taken from the .MIPS.options or .reginfo section
> * RSS_LOC   - address of location being relocated
> 
> So the problem is how to store these four constants in the
> lld::Reference object.
> The RSS_UNDEF is obviously not a problem. To represent the RSS_GP value I
can
> set an AbsoluteAtom created for the "_gp" as the reference's
target. But what
> about RSS_GP0 and RSS_LOC? I am considering the following approaches but
cannot
> select the best one:
> 
> a) Create AbsoluteAtom for each of these cases and set them as the
> reference's target.
>   The problem is that these atoms are fake and should not go to the
> symbol table.
>   One more problem is to select unique names for these atoms.
> b) Use two high bits of lld::Reference::_kindValue field to encode
> RSS_xxx value.
>   Then decode these bits in the RelocationHandler to calculate result
> of relocation.
>   In that case the problem is how to represent a relocation kind
> value in YAML format.
>   The simple xxxRelocationStringTable::kindStrings[] array will not satisfy
us.
> c) Add one more field to the lld::Reference class. Something like the
> DefinedAtom::CodeModel
>   field.
> 
> Any advices, ideas, and/or objections are much appreciated.
> 
> -- 
> Simon Atanasyan
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Nick,

Right now I try to implement exactly the same approach. I split a
relocation record on up to three separate relocations. But there are
two problems on this way.

The first one is how to represent some additional data provided in the
relocation record. That is why I asked the initial question in this
thread. The current solution is to extend the `Reference` class and
add one more attribute to it.

The second problem is how to handle these three relocations. Now the
`TargetRelocationHandler::applyRelocation()` method called one-by-one
for each reference. That is not applied to the MIPS N64 ABI
relocations. In that case we need to calculate the first one, save the
result, calculate the second one using result from the first step,
repeat that for the third relocations and only at the end check the
final result on overflow and apply it to the location. My current idea
is to allow a target specific code to handle the loop over atom's
references now hardcoded in the `AtomSection<ELFT>::write` method.

On Sun, Feb 8, 2015 at 3:21 AM, Nick Kledzik <kledzik at apple.com>
wrote:
> Simon,
>
> Sounds like the instruction relocating is so complicated that ELF requires
up to three relocation records to encode how to fix up one instruction.  If that
is the case, why not do the same and have up to three Reference objects on the
same atom offset to record the same info?  I thought that was model that the ELF
part of lld was using - there is a one-to-one mapping of ELF reloc to lld
References.
>
> Or am I misunderstanding the issue?
>
> -Nick
>
>
> On Feb 5, 2015, at 12:22 PM, Simon Atanasyan <simon at atanasyan.com>
wrote:
>> Hi,
>>
>> I need an advice on implementation of a very specific kind of
relocations
>> used by MIPS N64 ABI. As usual the main problem is how to pass target
specific
>> data over Native/YAML conversion barrier.
>>
>> In this ABI relocation record r_info field in fact consists of five
subfields:
>> * r_sym   - symbol index
>> * r_ssym  - special symbol
>> * r_type3 - third relocation type
>> * r_type2 - second relocation type
>> * r_type  - first relocation type
>>
>> Up to three these relocations applied one by one. The first relocation
uses
>> an addendum from the relocation record. Each subsequent relocation
takes as
>> its addend the result of the previous operation. Only the final
operation
>> actually modifies the location relocated. The first relocation uses as
>> a reference symbol specified by the r_sym field. The third relocation
>> assumes NULL symbol.
>>
>> The most interesting case is the second relocation. It uses the special
>> symbol value given by the r_ssym field. This field can contain four
>> predefined values:
>> * RSS_UNDEF - zero value
>> * RSS_GP    - value of gp symbol
>> * RSS_GP0   - gp0 value taken from the .MIPS.options or .reginfo
section
>> * RSS_LOC   - address of location being relocated
>>
>> So the problem is how to store these four constants in the
>> lld::Reference object.
>> The RSS_UNDEF is obviously not a problem. To represent the RSS_GP value
I can
>> set an AbsoluteAtom created for the "_gp" as the
reference's target. But what
>> about RSS_GP0 and RSS_LOC? I am considering the following approaches
but cannot
>> select the best one:
>>
>> a) Create AbsoluteAtom for each of these cases and set them as the
>> reference's target.
>>   The problem is that these atoms are fake and should not go to the
>> symbol table.
>>   One more problem is to select unique names for these atoms.
>> b) Use two high bits of lld::Reference::_kindValue field to encode
>> RSS_xxx value.
>>   Then decode these bits in the RelocationHandler to calculate result
>> of relocation.
>>   In that case the problem is how to represent a relocation kind
>> value in YAML format.
>>   The simple xxxRelocationStringTable::kindStrings[] array will not
satisfy us.
>> c) Add one more field to the lld::Reference class. Something like the
>> DefinedAtom::CodeModel
>>   field.
>>
>> Any advices, ideas, and/or objections are much appreciated.
>>
>> --
>> Simon Atanasyan
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>


-- 
Simon Atanasyan