RFC: .gnu.linkonce.* and shared libraries

RFC: .gnu.linkonce.* and shared libraries

[Jakub Jelinek]

Hi!

While testing the prelinking stuff I found that some KDE C++ programs have
excessive number of conflicts. Typically the ratio of conflicts vs. sum of
all non-RELATIVE relocations is like 1% and even some huge C++ programs like
konqueror which have more than 65000 relocations have something like 1500
conflicts. But some C++ programs have up to 30000 conflicts out of 80000
total relocations, like kmail. That seems bad.
Although prelinking still seems to be a win:
LD_DEBUG=statistics /usr/bin/popmail_conduit	# prelinked
20462:
20462:  runtime linker statistics:
20462:    total startup time in dynamic loader: 4485444 clock cycles
20462:              time needed for relocation: 2281637 clock cycles (50.8)
20462:                   number of relocations: 24041
20462:             time needed to load objects: 1987949 clock cycles (44.3)
LD_DEBUG=statistics /save/usr/bin/popmail_conduit	# non-prelinked, lazy
20466:
20466:  runtime linker statistics:
20466:    total startup time in dynamic loader: 110883574 clock cycles
20466:              time needed for relocation: 108693508 clock cycles (98.0)
20466:                   number of relocations: 46310
20466:             time needed to load objects: 1985271 clock cycles (1.7)
LD_DEBUG=statistics LD_BIND_NOW=1 /save/usr/bin/popmail_conduit # non-prelinked
20468:
20468:  runtime linker statistics:
20468:    total startup time in dynamic loader: 191296068 clock cycles
20468:              time needed for relocation: 189113247 clock cycles (98.8)
20468:                   number of relocations: 61628
20468:             time needed to load objects: 1977346 clock cycles (1.0)

24000 conflicts occupy 288K in the binary (note that 288K does not mean 288K
more of shared pages, because although ld.so accesses the conflict section,
it does not on the other side access the .rel* sections of the binary and
all libraries).

I believe the main reason is that .gnu.linkonce.* has link-once semantics
only within a single link object (be it shared library or binary), not
within whole program.

Now, what would you think about extending .gnu.linkonce.* semantics to the
whole program? My idea is this:

1) so that programs which rely on the current .gnu.linkonce.* semantics
would still work, compiler would specially mark the .gnu.linkonce.* section
which wants this new behaviour.
Using
        .section .gnu.linkonce.t._Z3foov,"axm",@progbits,.LFE1-.LFB1
looks like a good idea for this to me, since SHF_MERGE with entity size
equal to the size of the section is exactly what .gnu.linkonce.* is doing.

2) ld would normally eliminate all but once such section

3) once all dependent libraries are mapped, if there are any dynamic
libraries, linker searches all those libraries if it finds an area in the
corresponding section (.gnu.linkonce.t -> .text etc.) of the library, which:

  a) has the required alignment of .gnu.linkonce.* section
  b) all the symbols against the .gnu.linkonce.* section are present there
     too, with the same symbol properties, at the same relative offset
     from start of .gnu.linkonce.* section resp. of the area in the library
  c) likewise for relocations against .gnu.linkonce.* section resp. area,
     again it has to be the same relocation type, same visibility, against
     the same symbol, with the same addend etc.
  d) the content of the .gnu.linkonce.t section is identical to the content
     of the area (for RELA relocations against the area after all
     relocations are relocated to canonical form)

4) if all these conditions are met, then the .gnu.linkonce.* section is
thrown away from the link

I believe this would kill quite a lot of relocations in C++ shared libraries
and binaries linked against them and would reduce drastically the number of
conflicts too, in addition to making the libraries/binaries smaller.
What do you think?

	Jakub

Re: RFC: .gnu.linkonce.* and shared libraries

[Ian Lance Taylor]

Jakub Jelinek <jakub@redhat.com> writes:

> 3) once all dependent libraries are mapped, if there are any dynamic
> libraries, linker searches all those libraries if it finds an area in the
> corresponding section (.gnu.linkonce.t -> .text etc.) of the library, which:
> 
>   a) has the required alignment of .gnu.linkonce.* section
>   b) all the symbols against the .gnu.linkonce.* section are present there
>      too, with the same symbol properties, at the same relative offset
>      from start of .gnu.linkonce.* section resp. of the area in the library
>   c) likewise for relocations against .gnu.linkonce.* section resp. area,
>      again it has to be the same relocation type, same visibility, against
>      the same symbol, with the same addend etc.
>   d) the content of the .gnu.linkonce.t section is identical to the content
>      of the area (for RELA relocations against the area after all
>      relocations are relocated to canonical form)

How does the dynamic linker locate .gnu.linkonce sections?  Remember
that the dynamic linker does not look at section headers.  It only
looks at program segments.

Ian

Re: RFC: .gnu.linkonce.* and shared libraries

[Jakub Jelinek]

On Wed, Jul 11, 2001 at 12:43:15PM -0700, Ian Lance Taylor wrote:
> Jakub Jelinek <jakub@redhat.com> writes:
> 
> > 3) once all dependent libraries are mapped, if there are any dynamic
> > libraries, linker searches all those libraries if it finds an area in the
> > corresponding section (.gnu.linkonce.t -> .text etc.) of the library, which:
> > 
> >   a) has the required alignment of .gnu.linkonce.* section
> >   b) all the symbols against the .gnu.linkonce.* section are present there
> >      too, with the same symbol properties, at the same relative offset
> >      from start of .gnu.linkonce.* section resp. of the area in the library
> >   c) likewise for relocations against .gnu.linkonce.* section resp. area,
> >      again it has to be the same relocation type, same visibility, against
> >      the same symbol, with the same addend etc.
> >   d) the content of the .gnu.linkonce.t section is identical to the content
> >      of the area (for RELA relocations against the area after all
> >      relocations are relocated to canonical form)
> 
> How does the dynamic linker locate .gnu.linkonce sections?  Remember
> that the dynamic linker does not look at section headers.  It only
> looks at program segments.

I perhaps have not written it clearly.
All of 1)-4) would be done in the static linker, not dynamic linker.
Example (using gcc-2.96-RH, but there is nothing different here for gcc
3.0):

ld -o kmail ... kbusyptr.o ... -lqt ...

kbusyptr.o:

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
...
  [ 8] .gnu.linkonce.d._ PROGBITS        00000000 000aa0 000040 00  WA  0   0 32
  [ 9] .rel.gnu.linkonce REL             00000000 00252c 000040 08     22   8  4
...
Relocation section '.rel.gnu.linkonce.d.__vt_7QBitmap' at offset 0x252c contains 8 entries:
  Offset    Info  Type            Symbol's Value  Symbol's Name
  00000004  05401 R_386_32              00000000  __tf7QBitmap
  00000008  05501 R_386_32              00000000  _._7QBitmap
  0000000c  05601 R_386_32              00000000  setX11Data__12QPaintDevic
  00000010  05701 R_386_32              00000000  cmd__12QPaintDeviceiP8QPa
  00000014  05801 R_386_32              00000000  metric__C7QPixmapi
  00000018  05901 R_386_32              00000000  fontMet__C12QPaintDeviceP
  0000001c  05a01 R_386_32              00000000  fontInf__C12QPaintDeviceP
  00000020  05b01 R_386_32              00000000  detach__7QPixmap

Symbol table '.symtab' contains 112 entries:
...
    63: 00000000    40 OBJECT  WEAK   DEFAULT    8 __vt_7QBitmap
...
Contents of section .gnu.linkonce.d.__vt_7QBitmap:
 0000 00000000 00000000 00000000 00000000  ................
 0010 00000000 00000000 00000000 00000000  ................
 0020 00000000 00000000 00000000 00000000  ................
 0030 00000000 00000000 00000000 00000000  ................

/usr/lib/qt-2.3.1/lib/libqt.so.2.3.1:

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
...
  [ 6] .rel.data         REL             000ab468 0ab468 02aa08 08   A  2  10  4
...
  [16] .data             PROGBITS        0049bbe0 49abe0 020660 00  WA  0   0 32
...
Relocation section '.rel.data' at offset 0xab468 contains 21825 entries:
  Offset    Info  Type            Symbol's Value  Symbol's Name
...
  004a92b4  14cd01 R_386_32              0014af20  encodedData__C17QClipboar
  004a92c4  31aa01 R_386_32              003db550  __tf7QBitmap
  004a92c8  98001 R_386_32              003db500  _._7QBitmap
  004a92cc  c7701 R_386_32              00161f00  setX11Data__12QPaintDevic
  004a92d0  128301 R_386_32              00162180  cmd__12QPaintDeviceiP8QPa
  004a92d4  149601 R_386_32              0015c400  metric__C7QPixmapi
  004a92d8  306b01 R_386_32              001621e0  fontMet__C12QPaintDeviceP
  004a92dc  317b01 R_386_32              001621f0  fontInf__C12QPaintDeviceP
  004a92e0  f3401 R_386_32              0015c1b0  detach__7QPixmap
  004a9304  1cab01 R_386_32              003db640  __tft8QIntDict1Z10QColorD
...
Symbol table '.dynsym' contains 12899 entries:
...
  8170: 004a92c0    40 OBJECT  WEAK   DEFAULT   16 __vt_7QBitmap
...
Contents of section .data:
...
 4a92c0 00000000 00000000 00000000 00000000  ................
 4a92d0 00000000 00000000 00000000 00000000  ................
 4a92e0 00000000 00000000 00000000 00000000  ................
 4a92f0 00000000 00000000 00000000 00000000  ................

(this is about all ld would need to check to find out that it can safely throw away
.gnu.linkonce.d.__vt_7QBitmap provided it has:
  [ 8] .gnu.linkonce.d._ PROGBITS        00000000 000aa0 000040 40 WAM  0   0 32
instead of
  [ 8] .gnu.linkonce.d._ PROGBITS        00000000 000aa0 000040 00  WA  0   0 32
).
Note that if /usr/lib/qt-2.3.1/lib/libqt.so.2.3.1 was prelinked:
a) the relocations would be RELA in .gnu.reloc sections instead and would not
be necessarily in the same order as in .rela.gnu.linkonce.d.__vt_7QBitmap -
what matters if the relative offsets in r_offset fields are the same
b) the content of the area would not necesssarily match the content of the
sections in places which have relocations against them - one would need to
put r_addends/0 whatever the default state is before comparing them.

	Jakub

Re: RFC: .gnu.linkonce.* and shared libraries

[Ian Lance Taylor]

Jakub Jelinek <jakub@redhat.com> writes:

> I perhaps have not written it clearly.
> All of 1)-4) would be done in the static linker, not dynamic linker.

Sorry, I misunderstood.

The only relevant issue then is that your scheme is robust in the face
of running against a dynamic library which is not the specific one
which was linked against.

Ian

Re: RFC: .gnu.linkonce.* and shared libraries

[Jakub Jelinek]

On Wed, Jul 11, 2001 at 02:11:06PM -0700, Ian Lance Taylor wrote:
> Jakub Jelinek <jakub@redhat.com> writes:
> 
> > I perhaps have not written it clearly.
> > All of 1)-4) would be done in the static linker, not dynamic linker.
> 
> Sorry, I misunderstood.
> 
> The only relevant issue then is that your scheme is robust in the face
> of running against a dynamic library which is not the specific one
> which was linked against.

That's why the compiler/programmer has to ask for it explicitely.
As far as I understand C++, having e.g. different vtables in a program would
make it non-conforming. Although the exact content of inline
functions/methods in .gnu.linkonce.t.* sections can change, it needs to be
compiled from the same sequence of tokens, so it should do the same thing.
Languages which don't have such requirements and where this would cause
troubles will just have to avoid using .gnu.linkonce.* sections with
SHF_MERGE flag set.

	Jakub

Re: RFC: .gnu.linkonce.* and shared libraries

[Jason Merrill]

>>>>> "Jakub" == Jakub Jelinek <jakub@redhat.com> writes:

> On Wed, Jul 11, 2001 at 02:11:06PM -0700, Ian Lance Taylor wrote:
>> Jakub Jelinek <jakub@redhat.com> writes:
>> 
>> > I perhaps have not written it clearly.
>> > All of 1)-4) would be done in the static linker, not dynamic linker.
>> 
>> Sorry, I misunderstood.
>> 
>> The only relevant issue then is that your scheme is robust in the face
>> of running against a dynamic library which is not the specific one
>> which was linked against.

> That's why the compiler/programmer has to ask for it explicitely.
> As far as I understand C++, having e.g. different vtables in a program would
> make it non-conforming.

Considering the entire program, perhaps.  The problem comes when the stuff
in .gnu.linkonce.foo is not part of the intended API of the library, but a
side effect of the implementation.  If the implementation changes (say, to
use list<T> instead of vector<T>), the instantiations present in the
library change, so if the linker had decided the executable could just use
the vector<int> code in the library things break.

Jason

.hidden for _ZTS.*? (was Re: RFC: .gnu.linkonce.* and shared libraries)

[Jakub Jelinek]

On Thu, Jul 12, 2001 at 12:35:22AM +0100, Jason Merrill wrote:
> >>>>> "Jakub" == Jakub Jelinek <jakub@redhat.com> writes:
> 
> > On Wed, Jul 11, 2001 at 02:11:06PM -0700, Ian Lance Taylor wrote:
> >> Jakub Jelinek <jakub@redhat.com> writes:
> >> 
> >> > I perhaps have not written it clearly.
> >> > All of 1)-4) would be done in the static linker, not dynamic linker.
> >> 
> >> Sorry, I misunderstood.
> >> 
> >> The only relevant issue then is that your scheme is robust in the face
> >> of running against a dynamic library which is not the specific one
> >> which was linked against.
> 
> > That's why the compiler/programmer has to ask for it explicitely.
> > As far as I understand C++, having e.g. different vtables in a program would
> > make it non-conforming.
> 
> Considering the entire program, perhaps.  The problem comes when the stuff
> in .gnu.linkonce.foo is not part of the intended API of the library, but a
> side effect of the implementation.  If the implementation changes (say, to
> use list<T> instead of vector<T>), the instantiations present in the
> library change, so if the linker had decided the executable could just use
> the vector<int> code in the library things break.

Bad. It would be good if C++ libraries clearly marked what they consider
exported interface and what not.
Anyway, I killed some conflicts at least by using knowledge about C++
virtual tables and typeinfo stuff (mainly that they are only referenced by
the associated _ZTV resp. _ZTI symbol, there is nothing like:
        .weak   _ZTV1B
        .section        .gnu.linkonce.d._ZTV1B,"aw",@progbits
        .align 8
        .type   _ZTV1B,@object
        .size   _ZTV1B,16
_ZTV1B:
.L257:				# <- This cannot happen
        .long   0
        .long   _ZTI1B
        .long   _ZN1BD1Ev
.L258:				# <- Neither this
        .long   _ZN1BD0Ev
). That means I can kill conflicts for virtual tables/typeinfo which will
not be referenced anyway, because there is a conflict for the containing
_ZTV resp. _ZTI symbol too.

Now, related question:

Shouldn't G++ 3.0+ emit
        .weak   _ZTS1A
	.hidden	_ZTS1A		# <- This
        .section        .gnu.linkonce.r._ZTS1A,"a",@progbits
        .type   _ZTS1A,@object
        .size   _ZTS1A,3
_ZTS1A:
        .string "1A"
?
From my reading of rtti and
http://reality.sgi.com/dehnert_engr/cxx/abi.html#vague (5.2.4)
a _ZTS.* object is only ever referenced from the corresponding _ZTI object.
But that means _ZTS comes always with _ZTI together, so if symbol lookup
from _ZTI winds in ELF object XYZ, symbol oookup for _ZTS will wind that
too. So, if _ZTS.* are STV_HIDDEN inside of each objects, it should have no
influence on program behaviour and should save quite a few
a) relocations
b) symbol lookups
c) DYNSYM symbols

If you agree, I'll try to cook up a patch...

	Jakub