llvm dev - Apr 2018 - [RFC] Adding a new option to lld to make it easy to maintain compatibility with other linkers

Hi guys,

I'd like to propose a new lld command line option,
--check-library-dependency. We already have a patch (
https://reviews.llvm.org/D45195), and I'm satisfied with it, but I'd
like
to get feedback from those who are using lld before submitting.

--check-library-dependency is an option to prevent an undefined reference
from fetching an archive member written earlier in the command line. It can
be used to keep your program compatible with GNU linkers after you switch
to lld. I'll explain the feature and why you may find it useful below.

lld's symbol resolution semantics is more relaxed than traditional Unix
linkers. For example,

  ld.lld foo.a bar.o

succeeds even if bar.o contains an undefined symbol that have to be
resolved by some object file in foo.a. Traditional Unix linkers don't allow
this kind of backward reference, as they visit each file only once from
left to right in the command line while resolving all undefined symbols at
the moment of visiting.

In the above case, since there's no undefined symbol when a linker visits
foo.a, no files are pulled out from foo.a, and because the linker forgets
about foo.a after visiting, it can't resolve undefined symbols in bar.o
that could have been resolved otherwise.

That lld accepts more relaxed form means that (besides it'd make more
sense) you can accidentally write a command line or a build file that works
only with lld, even if you have a plan to distribute it to wider users who
may be using GNU linkers. With --check-library-dependency, you can detect a
library order that doesn't work with other Unix linkers.

The option is also useful to detect cyclic dependencies between static
archives. Again, lld accepts

  ld.lld foo.a bar.a

even if foo.a and bar.a depend on each other. With
--check-library-dependency, it is handled as an error.

Here is how the option works. We assign a group ID to each file. A file
with a smaller group ID can pull out object files from an archive file with
an equal or greater group ID. Otherwise, it is a reverse dependency and an
error.

A file outside --{start,end}-group gets a fresh ID when instantiated. All
files within the same --{start,end}-group get the same group ID. E.g.

  ld.lld A B --start-group C D --end-group E

A and B form group 0. C, D and their member object files form group 1. E
forms group 2. I think that you can see how this group assignment rule
simulates the traditional linker's semantics.

I think this is a reasonable option to add. What do you guys think?

Rui
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180404/35cc30db/attachment.html>

I believe this will report an error on more command-lines than a
traditional linker would fail to link. E.g.:
  ld.lld foo.o A.a B.a A.a B.a
That "should" work fine if the libs are circularly-dependent, as long
as
there's only a 1-level cycle. I've seen that sort of construct used a
fair
amount, and while the start-group/end-group flags are pretty clearly a
superior option, but are not universally used.

It will also fail to detect some problematic situations in the face of
symbols defined in multiple objects within a group. For example, if you
have:
ld foo.o --start-group A.a B.a --end-group
and:
 foo.o needs a definition of "f"
 A.a:a.o provides "g".
 B.a:b.o provides "f" and requires "g"
 B.a:b2.o provides "g".

IIUC, lld will pull in b1.o to get "f", and then a.o to get
"g". This flag
won't report a failure, as they're in a group. But GNU ld will pull in
b1.o
to get "f" and then continue searching to the right before circling
back
around, and thus find b2.o to provide "g". So, despite no warning
message,
you'll end up with a different link. I mean -- obviously don't do crazy
things like that, but still, no warning.

However, both those issues seem perfectly acceptable for an opt-in warning
flag, and should just be documented so that people know its limitations.


On Wed, Apr 4, 2018 at 6:47 PM Rui Ueyama via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi guys,
>
> I'd like to propose a new lld command line option,
> --check-library-dependency. We already have a patch (
> https://reviews.llvm.org/D45195), and I'm satisfied with it, but
I'd like
> to get feedback from those who are using lld before submitting.
>
> --check-library-dependency is an option to prevent an undefined reference
> from fetching an archive member written earlier in the command line. It can
> be used to keep your program compatible with GNU linkers after you switch
> to lld. I'll explain the feature and why you may find it useful below.
>
> lld's symbol resolution semantics is more relaxed than traditional Unix
> linkers. For example,
>
>   ld.lld foo.a bar.o
>
> succeeds even if bar.o contains an undefined symbol that have to be
> resolved by some object file in foo.a. Traditional Unix linkers don't
allow
> this kind of backward reference, as they visit each file only once from
> left to right in the command line while resolving all undefined symbols at
> the moment of visiting.
>
> In the above case, since there's no undefined symbol when a linker
visits
> foo.a, no files are pulled out from foo.a, and because the linker forgets
> about foo.a after visiting, it can't resolve undefined symbols in bar.o
> that could have been resolved otherwise.
>
> That lld accepts more relaxed form means that (besides it'd make more
> sense) you can accidentally write a command line or a build file that works
> only with lld, even if you have a plan to distribute it to wider users who
> may be using GNU linkers. With --check-library-dependency, you can detect a
> library order that doesn't work with other Unix linkers.
>
> The option is also useful to detect cyclic dependencies between static
> archives. Again, lld accepts
>
>   ld.lld foo.a bar.a
>
> even if foo.a and bar.a depend on each other. With
> --check-library-dependency, it is handled as an error.
>
> Here is how the option works. We assign a group ID to each file. A file
> with a smaller group ID can pull out object files from an archive file with
> an equal or greater group ID. Otherwise, it is a reverse dependency and an
> error.
>
> A file outside --{start,end}-group gets a fresh ID when instantiated. All
> files within the same --{start,end}-group get the same group ID. E.g.
>
>   ld.lld A B --start-group C D --end-group E
>
> A and B form group 0. C, D and their member object files form group 1. E
> forms group 2. I think that you can see how this group assignment rule
> simulates the traditional linker's semantics.
>
> I think this is a reasonable option to add. What do you guys think?
>
> Rui
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180405/0094cf05/attachment.html>

On Wed, Apr 4, 2018 at 7:30 PM James Y Knight <jyknight at google.com>
wrote:
> I believe this will report an error on more command-lines than a
> traditional linker would fail to link. E.g.:
>   ld.lld foo.o A.a B.a A.a B.a
> That "should" work fine if the libs are circularly-dependent, as
long as
> there's only a 1-level cycle. I've seen that sort of construct used
a fair
> amount, and while the start-group/end-group flags are pretty clearly a
> superior option, but are not universally used.
>
Actually it won't report an error for that command line. We (and perhaps
other linkers as well) don't do anything special for files that happen to
be passed to a linker more than once, so the first A.a and second A.a are
handled as different files.

It will also fail to detect some problematic situations in the face
of
> symbols defined in multiple objects within a group. For example, if you
> have:
> ld foo.o --start-group A.a B.a --end-group
> and:
>  foo.o needs a definition of "f"
>  A.a:a.o provides "g".
>  B.a:b.o provides "f" and requires "g"
>  B.a:b2.o provides "g".
>
> IIUC, lld will pull in b1.o to get "f", and then a.o to get
"g". This flag
> won't report a failure, as they're in a group. But GNU ld will pull
in b1.o
> to get "f" and then continue searching to the right before
circling back
> around, and thus find b2.o to provide "g". So, despite no warning
message,
> you'll end up with a different link. I mean -- obviously don't do
crazy
> things like that, but still, no warning.
>
> However, both those issues seem perfectly acceptable for an opt-in warning
> flag, and should just be documented so that people know its limitations.
>
I agree. There's a limitation as you pointed out, but that's acceptable
as
long as we explain it clearly. (And that's why I didn't propose a flag
name
like --gnu-compatible-mode because it's not.)

> On Wed, Apr 4, 2018 at 6:47 PM Rui Ueyama via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi guys,
>>
>> I'd like to propose a new lld command line option,
>> --check-library-dependency. We already have a patch (
>> https://reviews.llvm.org/D45195), and I'm satisfied with it, but
I'd
>> like to get feedback from those who are using lld before submitting.
>>
>> --check-library-dependency is an option to prevent an undefined
reference
>> from fetching an archive member written earlier in the command line. It
can
>> be used to keep your program compatible with GNU linkers after you
switch
>> to lld. I'll explain the feature and why you may find it useful
below.
>>
>> lld's symbol resolution semantics is more relaxed than traditional
Unix
>> linkers. For example,
>>
>>   ld.lld foo.a bar.o
>>
>> succeeds even if bar.o contains an undefined symbol that have to be
>> resolved by some object file in foo.a. Traditional Unix linkers
don't allow
>> this kind of backward reference, as they visit each file only once from
>> left to right in the command line while resolving all undefined symbols
at
>> the moment of visiting.
>>
>> In the above case, since there's no undefined symbol when a linker
visits
>> foo.a, no files are pulled out from foo.a, and because the linker
forgets
>> about foo.a after visiting, it can't resolve undefined symbols in
bar.o
>> that could have been resolved otherwise.
>>
>> That lld accepts more relaxed form means that (besides it'd make
more
>> sense) you can accidentally write a command line or a build file that
works
>> only with lld, even if you have a plan to distribute it to wider users
who
>> may be using GNU linkers. With --check-library-dependency, you can
detect a
>> library order that doesn't work with other Unix linkers.
>>
>> The option is also useful to detect cyclic dependencies between static
>> archives. Again, lld accepts
>>
>>   ld.lld foo.a bar.a
>>
>> even if foo.a and bar.a depend on each other. With
>> --check-library-dependency, it is handled as an error.
>>
>> Here is how the option works. We assign a group ID to each file. A file
>> with a smaller group ID can pull out object files from an archive file
with
>> an equal or greater group ID. Otherwise, it is a reverse dependency and
an
>> error.
>>
>> A file outside --{start,end}-group gets a fresh ID when instantiated.
All
>> files within the same --{start,end}-group get the same group ID. E.g.
>>
>>   ld.lld A B --start-group C D --end-group E
>>
>> A and B form group 0. C, D and their member object files form group 1.
E
>> forms group 2. I think that you can see how this group assignment rule
>> simulates the traditional linker's semantics.
>>
>> I think this is a reasonable option to add. What do you guys think?
>>
>> Rui
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180405/2d0148e8/attachment.html>