LLD input graph handling proposal

Shankar and I discussed input file handling, and we came up with a design that may greatly simplify the input file handling, while giving more flexibility to developer to support complicated options, such as --{start,end}-group, -z rescan or -z rescan-now. It’d worth pursuing, so here’s the idea:

  1. We wouldn’t probably want to let Resolver to handle the input graph directly, for we don’t want to implement the details of input graph control node behavior for --{start,end}-group, -z rescan{,-now}, or whatever you define as a new linker option. Implementing it to Resolver would make it messy.

  2. We would instead add a new method nextFile() to LinkingContext, which returns a new file from which Resolver should try to resolve undefined symbols. Resolver wouldn’t handle the input graph at all. Instead, Resolver calls nextFile() repeatedly to link until nextFile() returns a null value.

  3. Resolver will notify Linking Context when (A) all undefined symbols are resolved (success), or (B) it detects it’s in an infinite loop in which it cannot resolve any symbols anymore (failure). Linking Context will do whatever it thinks appropriate for the event notification.

So, with this mechanism, one can implement --{start,end}-group this way: Assume command line –start-group a b c --end-group d. nextFile() returns a, b, c, a, b, c, a, … until it gets notified that Resolver cannot resolve symbol any longer. If notified, next call of nextFile() will return d. This is how “search the files in the group repeatedly until all possible references are resolved” is implemented.

“-z rescan”, which is an option to let the linker to reprocess all files up to the command line option position, can be implemented this way: Assume command line a b -z rescan c. nextFile() returns a b a b c in this order. That makes Resolver to reprocess file a and b twice.

The logic for --whole-archive can also be implemented: Linking Context should usually return a null value for nextFile() if it gets notified all symbols are resolved in order to terminate Resolver. However, if --whole-archive option is given, it should continue to return new files to let Resolver to include all files appeared in the command line.

Overall, this seems to be a clean API that is powerful enough to implement complex semantics.

Thanks Ruiu, for putting this together.

I like this proposal much, as it simplifies the resolver a lot and leaves it to the LinkingContext on how symbol resolution should happen.

The Resolver will have a state

enum ResolverState : uint8_t {
      unChanged = 0x0, // no change
      newWeakAtoms = 0x1, // Found weak atoms
      newUndefinedAtoms = 0x4, // Added new undefined atoms
      newDefinedAtoms = 0x8, // Added new defined atoms
      newAbsoluteAtoms = 0x10, // Added new absolute atoms
      newSharedLibraryAtoms = 0x20, // Added new shared library atoms
};

nextFile() can be renamed to nextFiles(), that would return a range of input files, makes it much easier to handle when there are no groups.

Thanks

Shankar Easwaran

Rui,

I like this in general, but have a few questions.

Hi Nick,

Rui,

I like this in general, but have a few questions.

2. We would instead add a new method nextFile() to LinkingContext, which returns a new file from which Resolver should try to resolve undefined symbols. Resolver wouldn't handle the input graph at all. Instead, Resolver calls nextFile() repeatedly to link until nextFile() returns a null value.

3. Resolver will notify Linking Context when (A) all undefined symbols are resolved (success), or (B) it detects it's in an infinite loop in which it cannot resolve any symbols anymore (failure). Linking Context will do whatever it thinks appropriate for the event notification.

How does the Resolver detect an infinite loop? As in the example below, it is supposed to keep getting a,b,c,a,b,c… At some point, no more undefines are being fulfilled by a,b,c,a,b,c…, but how does the resolver know that the files are repeating, to know to tell the InputGraph to move on?

nextFile could pass the current resolver state at the time when its called, the linkingcontext can return the next file to be processed as below :-

nextFile(currentResolverState) :-

a) Returns the next file if the current node is not a group node
b) Returns the next file in the group node, if the current node is a group node and the resolver state states undefined /weak / shared library atoms were added.
c) Returns the start file in the group node, if the resolver state states undefined/weak/shared library atoms were added
d) If the state is unchanged, no symbols were added exit the group and move to the next node.

Thanks

Shankar Easwaran

So you prefer detecting loop in Linking Context based on the information
it's passed by Resolver, over letting Resolver to do that? Not sure if we
want the additional information sorted by atom type, but that way should
work too.

That is not how groups work. The resolver has to keep checking each file in the group, in order, until there is one full pass of the group and none in the group provided any more content.

nextFile could pass the current resolver state at the time when its called, the linkingcontext can return the next file to be processed as below :-

nextFile(currentResolverState) :-

a) Returns the next file if the current node is not a group node
b) Returns the next file in the group node, if the current node is a group node and the resolver state states undefined /weak / shared library atoms were added.
c) Returns the start file in the group node, if the resolver state states undefined/weak/shared library atoms were added
d) If the state is unchanged, no symbols were added exit the group and move to the next node.

What causes the Resolver state to change? I understand the state of “there are undefines remaining”, but the “something was added” is a transient state. Each last file, changes it.

The InputGraph knows how to exit a group, but does not know if it should.
The Resolver knows which files added content, but does not know which files are in what groups.

How about this for InputGraph:

void fileAddedContent(File ); // asserts that File param is the same thing nextFile() last returned
File *nextFile();

The Resolver, also tells the InputGraph which files it used. When in a group, the InputGraph keeps a flag for the group of whether it has contributed anything. It starts as false for the first entry in the group. If fileAddedContent() is called, the flag is updated. When nextFile() is called and the previous entry was the last in the group, if the flag says nothing in that pass contributed, the InputGraph exits the group and moves on to the next file.

-Nick

I don't want to make Resolver to have a reference to input graph. The point
of this proposal is to separate input graph handling from Resolver and
instead making Linker Context to do that task. Resolver shouldn't have
knowledge on how it should iterate over input files, focusing only on core
linking. Linking Context should implement the policy and "feed" input files
to Resolver. Resolver should blindly consume an input file given by Linking
Context, and report its status to Linking Context.

How about this: add integer parameters to nextFile() to report the current
number of undefined and defined atoms. With that information, Linking
Context is able to decide what file should be fed to Resolver next. For
example, it can detect from the atom counts whether Resolver need to exit
--{start,end}-group loop or not.

Sorry for the long mail. This should explain things better. Here is a example with a state diagram on how the above proposal works. The main idea is to keep a running state of the resolver and the capturing the resolver state of each input file in the group by the linkingcontext. lld -flavor gnu main.o thread.o --start-group libc.a libpthread.a --end-group function.o main.o has atoms ------------------------ main (defined) printf(undefined) fn(undefined) thread.o has atoms ----------------------------- pthread_create (undefined) libc.a(printf.o) has atoms ------------------------------------ printf(defined) libc.a(exit.o) has atoms ---------------------------------- exit(defined) libpthread.a has atoms --------------------------------- pthread_create(defined) exit(undefined) function.o has atoms ------------------------------- fn(defined) State diagram with time information Resolver resolverState Context(nextFile) -------------- ------------------ ---------------- resolverState = initialState nextFile(resolverState) initialState ELFContextState=processingFileNode, return a.o resolverState = nochange process(a.o) state = definedatoms/undefinedatoms (reason: main/printf) nextFile(resolverState) definedAtoms/undefinedAtoms ELFContextState=processingFileNode, return b.o resolverState = nochange process(b.o) state = undefinedatoms(reason: pthread_create) nextFile(resolverState) undefinedAtoms ELFContextState=processingGroupNode, return libc.a resolverState=nochange process(libc.a) process(printf.o) state = definedatom (reason: printf) nextFile(resolverState) definedAtoms ELFContextState=processingGroupNode, state[libc.a]=definedAtoms, return libpthread.a resolverState=nochange process(libpthread.a) process(pthread.o) state = definedatom/undefinedatoms (reason: pthread_create/exit) nextFile(resolverState) definedAtoms/undefinedatoms ELFContextState=processingGroupNode, state[libpthread.a]=definedAtoms|undefinedAtoms, return libc.a (returns the first file in the group) resolverState=nochange process(libc.a) process(exit.o) state = definedatom (reason: exit) nextfile(resolverState) definedAtoms ELFContextState=processingGroupNode, state[libc.a] = definedAtoms, return libpthread.a resolverState=nochange process(libc.a) state = nochange nextfile(resolverState) nochange ELFContextState=processingGroupNode, state[libpthread.a] = nochange, resolverState=nochange process(function.o) state = definedatom (reason: fn) Exit. Thanks Shankar Easwaran

My email client spoilt the whole email, will create a pdf and send it.

That was the part of the original proposal I didn't agree with and I
still don't do. While the resolver shouldn't have to deal with the
details of the command line, it certainly should know about the input
graph. I wouldn't be surprised if it can make a significant difference
for group processing whether a DFS or BFS is applied, even if the result
doesn't change. There are other concerns like the recursive processing
of DT_NEEDED for ELF and the resulting implications for symbol
resolution and locking.

Joerg

Someone should certainly know about the input graph, but it isn't
necessarily be Resolver. In my proposal Linking Context gets update for
each step of linking from Resolver and makes a decision based on that. I
don't see why you think the search order would change in this model. I
think it shouldn't change.

I don't also understand if DT_NEEDED is related to this. DT_NEEDED is not
represented by input graph. And what is *recursive* processing of DT_NEEDED?

Hi,

Attached is the pdf of the operation to make things easier to read.

Thanks

Shankar Easwaran

design.pdf (44.5 KB)

I don't want to make Resolver to have a reference to input graph. The point
of this proposal is to separate input graph handling from Resolver and
instead making Linker Context to do that task.

That was the part of the original proposal I didn't agree with and I
still don't do. While the resolver shouldn't have to deal with the
details of the command line, it certainly should know about the input
graph. I wouldn't be surprised if it can make a significant difference
for group processing whether a DFS or BFS is applied, even if the result
doesn't change.

Resolver still doesnot deal with details of the command line. Its only supposed to read inputs as specified in command line order (for ELF).
Darwin does things differently.

nextFile encompasses all the details of symbol resolution on which file to iterate next during linking.

There are other concerns like the recursive processing
of DT_NEEDED for ELF and the resulting implications for symbol
resolution and locking.

With nextFile, and the resolver state, the LinkingContext is in full control of the resolver operation.

Thanks

Shankar Easwaran

Hi Nick,

Read this along with this example extract:

ld -flavor gnu main.o thread.o --start-group libc.a libpthread.a --end-group function.o

main.o has atoms

design.pdf (44.5 KB)

Shankar,

I think your proposal and mine are pretty much the same. The difference is passing back info to the InputGraph as a parameter in nextFile() vs as a separate method call. My original draft email had a parameter in nextFile(), but it seemed a little confusing because the information was referring to the previous file. That is, if the current resolver state has newDefinedAtoms, that really means the last file (returned by nextFile()) caused new atoms to be added.

In your ResolverState you have bits for all the kinds of atoms added. Is all that needed? I think all the InputGraph needs to know is if the last file was used. A group is scanned repeatedly until there is one complete pass in which no new files were used.

Also, is nextFile() going to be in InputGraph and directly accessed by the Resolver? Or is nextFile in LinkingContext (which forwards it to the InputGraph)? I assume the later.

Currently, the Resolver has buildInitialAtomList() and resolveUndefines() which matches the way darwin links. I assume part of this change is to unify those two methods by just have one loop that uses nextFile().

Given that nextFile() is basically an iteration mechanism, perhaps we can make it conform to C++11 iterators. The one issue is the feedback of whether the file was used or not. A separate notifyFileAddedContent() method (instead of a parameter to nextFile()) could fix that. And if Resolver::doFile() called linkingContext.notifyFileAddedContent() for every file used (even object files), then the Resolver algorithm would look like:

for (File *file : linkingContext) {
if (file.kind() == object) {
// add
}
else if (file.kind() == archive) {
if (resolvesSomeUndefs(file)) {
// add
}
}
}

-Nick

Yes just bits, to say whether it was used and contributed undefined atoms or Defined Weak atoms. Yes the latter. Yes. This also makes the resolver totally dependent on InputGraph/LinkingContext. Yes, its an iterator. I was thinking on a second pass around the same. nextFile could work on a range of files, until it reaches a ControlNode in the InputGraph. I like notifyFileAddedContent. makes it more extendable and can be called from anywhere in the resolver after the call from nextFile. I will start implementing this solution. make Thanks Shankar Easwaran

Searching a symbol in a shared library according to ELF semantics means
recursively searching in all depending libraries as well.

Joerg

Hi Joerg,

I would love to have this behavior(solaris/hp-ux linkers used to do this).

cat > main.c << \!
int main() {
   fn();
   fn1();
}
!

cat > fn.c << \!
int fn() {
   return 0;
}
!

cat > fn1.c << \!
int fn1() {
   return 0;
}
!

gcc -c -fPIC main.c fn.c fn1.c
ld -shared fn1.o -o libfn1.so
ld -shared fn.o -o libfn.so -L. -lfn1
ld main.o libfn.so
ld: warning: libfn1.so, needed by libfn.so, not found (try using -rpath or -rpath-link)
ld: warning: cannot find entry symbol _start; defaulting to 00000000004002f0
main.o: In function `main':
main.c:(.text+0x14): undefined reference to `fn1'

Any ways of making the GNU linker do a DFS/BFS search on dependent libraries ?

Thanks

Shankar Easwaran

I just want to mention that although I assume we’ll use this abstraction for some features that we have already support, I’d really like to see the first patch to be minimal that just implements the nextFile() which is connected to the existing infrastructure. We can then replace code step by step. Incremental patches are always preferred.