Hello,
I have updated RFC for Distributed ThinLTO. I have also simplified it quite a bit. Please have a look and let me know if you have any questions/comments.
Integrated Distributed ThinLTO
Goal
We have customers with LLVM-based toolchains that use a variety of different build and distribution systems including but not limited to our own. We’d like to implement support for an integrated Distributed ThinLTO (DTLTO) approach to improve their build performance, while making adoption of DTLTO seamless, as easy as adding a couple of options on the command line.
1. Challenges
DTLTO is more complex for integration into existing build systems compared to ThinLTO, because build rule dependencies are not known in advance, and they become available only after DTLTO’s ThinLink phase completes and for each of the bitcode files a list of its import files becomes known.
1.1 For some high-level build systems (such as Bazel or Buck) integration with DTLTO is not so challenging, since there is way to overcome the problem of dynamic dependencies by pruning everything that is not needed. These build systems start off with every DTLTO backend compile depending on every input module, but after the ThinLink step is finished and actual dependencies are known, they use the information about the dependencies to prune down those lists. Unfortunately, very few build systems have this capability.
1.2 For all other build systems, a non-trivial rewrite of a project’s buildscript/makefile is required. Build/Makefile developers will do the following steps to enable DTLTO for a project.
(a) unpack archives and place their members between –start-lib/–end-lib pair on the linker command line (note: this task is even more challenging than it seems on the surface, since name collision prevention when unpacking the same archives in different parallel processes is required)
(b) ThinLink step needs to be invoked
(c) after the ThinLink step is completed and the dependencies become known (it could be done by parsing the content of the import files), a script needs to be written to generate a set of codegen command lines; this set of command lines will need to be fed to the distribution system; also all the dependencies have to be copied to the particular remote machines.
(d) after the distribution system returns the result of the compilation, the buildscript/makefile will have to identify which files failed to compile and re-do the compilation for these files on the local machine
(e) A final link phase needs to be performed, linking all the native object files.
We are not aware of any large scale project that is using DTLTO (with the exception of projects built under Bazel or Buck), simply because modifying existing build scripts/makefiles to do the steps mentioned will be very difficult.
2. Our solution
In simple words, our DTLTO project will orchestrate all the steps described in section 1.2.
We are planning to place all the DTLTO functionality into a separate DTLTO subproject (shared library), because in essence, DTLTO is one library with well-defined interface.
We will need 2 major API functions:
- A function that converts archives into thin archives (it will need to get called before the scanning phase in the linker);
- A function that performs ThinLink and Codegen (it will need to get called after the scanning phase). The input for this function will be a list of preserved symbols and the list of bitcode files; the output will be a list of native object files.
- Firstly, ThinLink will get invoked.
- Dynamic dependencies created by the ThinLink step will be determined. A generic JSON file containing the list of compilation command lines will be created. It will also contain the locations of the output native object files and the list of dependencies to be copied on the remote node.
- A custom script of some sort will be passed to the DTLTO shared library and it will be spawned as a separate process. [Note: each distribution system will require its own custom script]. The script would take the information in the generic JSON file generated in the previous step, convert it to the custom (distribution system specific) Makefile/Fast build .FB file/JSON/Incredibuild XML/etc, and invoke the remote build system.
- Final link will be executed once the spawn process completes.
Only a few dozen of lines of code will be added to the linker to process the DTLTO parameters, to load the shared library and invoke a few API functions.
Note: If a new distribution system must be supported, interested parties will have to implement their custom script (or some kind of child process, e.g. an executable) that has a knowledge of a particular distribution system. This script or a child process will be spawned from the DTLTO shared library.
As a part of our upstreaming efforts, we will provide a script that will support the IceCream distribution system. That script could be used as an example for the other developers of what needs to be done to support a different distribution system.
3. Overview of existing popular Open Source & Proprietary systems that could be used for ThinLTO codegen distribution
Some or all of these systems could be potentially supported, bringing a lot of value for the ThinLTO customers who have already deployed one of these systems.
- Distcc
- Icecream. We are planning to provide support for IceCream as a part of our upstreaming efforts.
- FastBuild. There are several parties that showed interest in support of integrated DTLTO solution with FastBuild. Unfortunately, we anticipate that Fastbuild will not perform as well when integrated with DTLTO compared to the other distribution systems mentioned here, because FastBuild doesn’t support load balancing. The performance result of DTLTO integrated with Fastbuild might even get worse when a project has several link processes executed in parallel.
- Incredibuild; Incredibuild is one of the most popular proprietary build systems.
- SN-DBS; SN-DBS is a proprietary distributed build system developed by SN Systems, which is part of Sony. SN-DBS uses job description documents in the form of JSON files for distributing jobs across the network. In Sony, we already have production level DTLTO implementation using SN-DBS. Several of our customers effortlessly switched from using ThinLTO into using Distributive ThinLTO.
4. Challenges & problems
This section describes the challenges that we encountered when implementing DTLTO integration with our proprietary distributed build system called SN-DBS. All of these problems will be applicable to DTLTO integration with any distributed system in general. The solution for these problems is described in detail in Section 6.
4.1 Regular archives handling
Archive files can be huge. It would be too time-consuming to send the whole archive to a remote node. One of the solutions is to convert regular archives into thin archives and send individual thin archive members to the remote machines.
4.2 Processes access to file system synchronization
Since at any given moment several linker processes can be active on a given machine, they can access the same files at the same time. We need to provide a reliable synchronization mechanism. The existing LLVM file access mutex is not adequate since it does not have a reliable way to detect abnormal process failure.
4.3 File name clashes
We can have situations where file names can clash with each other. We need to provide file name isolation for each individual link target.
4.4 Remote execution is not reliable and can fail at any time
We need to provide a fallback system that can do code generation on a local machine for those modules where remote code generation failed.
5. Linker execution flow
5.1 Linker options
The following options need to be added:
- An option that tells the linker to use the integrated DTLTO approach and specifies what kind of distribution system to use [–distribute=[icecream/distcc/fastbuid/incredibuild]
- Options for debugging and testing.
5.2. The linker will invoke DTLTO’s API function for archive conversion (Pre-SCAN Phase)
This is what this API function will do:
If an input file is a regular archive:
- Convert regular archive into a thin archive. If the regular archive contains another regular archive, it will be converted to a thin archive during the next linker scan pass.
- Replace the path to the regular archive with a path to the thin archive.
After the scan phase has completed, the linker has determined a list of input bitcode modules that will participate in the final link. Also, by now, the linker has collected all symbol resolution information.
5.3. The linker will invoke DTLTO’s API function to perform ThinLink and Codegen (Post-SCAN Phase)
This is what this API function will do:
- Invoke ThinLink step. Individual module summary index file and cross module import files will get produced.
- Check if any of the input bitcode has a corresponding cache entry. If the cache entry exists, this particular bitcode will be excluded from code generation.
- Generate generic build script (JSON file). This JSON file will contain the list of compilation command lines, the locations of the output native object files and the list of dependencies to be copied on the remote node.
- Invoke the custom script that has the knowledge of specifics of a particular distribution system. That script needs to be written by developers who are planning to support integration of DTLTO with a particular build system and passed to the DTLTO shared library as a parameter. The script would take the information in the generic JSON file generated in the previous step, convert it to the custom (distribution system specific) Makefile/Fast build .FB file/JSON/Incredibuild XML/etc, and invoke the remote build system.
- Check that the list of expected native object files matches the list of the files returned after build script execution. If any of the native object files are missing, the DTLTO shared library uses the fallback system to perform code generation locally for all of these missing native object files.
- Place native object files into corresponding cache entries.
- Perform the final link and produce an executable.
6. Implementation details
6.1 Regular to Thin Archive converter
In section 4.1 we explained why dealing with regular archives is inefficient and proposed converting regular archives into thin archives, later copying only individual thin archive members to remote nodes.
We implemented a regular to thin archive converter based on llvm/Object/Archive.h
- The regular to thin archive converter creates or opens an inter-process sync object.
- It acquires sync object lock.
- It determines to what directory to unpack the regular archive members. This decision is based on the command line option, system temp, or current process directory (in this priority).
- If the thin archive doesn’t exist:
- Unpack the regular archive
- Create the thin archive from regular archive members
- Else:
- Check the thin archive file modification time***
- If (the thin archive is newer than the regular archive) &&*** ( **the thin archive integrity is good):
- Use existing thin archive
- Else:
- Unpack the regular archive
- Create the thin archive from regular archive members.
Note: all thin archive members match regular archive members
6.2 Fallback code generation
In section 4.4 we described a problem that remote execution is not as reliable as local execution and it can fail at any time (e.g. a network is down, remote nodes are not accessible, etc). So, we need to implement a reliable fallback mechanism that can do code generation on a local machine for all those modules that failed to generate remotely.
- Check if a list of missing native object files is not empty.
- Create queue of commands for performing codegen for missing native object files.
- Use the process pool to execute the queue of commands.
- Report fatal error if some native object files are still missing.
7. Usage
With our integrated DTLTO approach it will be trivial for a build master/Makefile developer to enable DTLTO for any kind of project, no matter how complex it is. All that will be required is to add one additional option --distribute=[icecream/distcc/fastbuid/incredibuild] on the linker command line.
Let’s say we have this rule to perform linking of an executable using ThinLTO:
program.elf: main.bc.o libsupport.a
lld --lto=thin main.bc.o -lsupport -o program.elf
If we want to start using DTLTO with Icecream as a distribution system, we simply can add “–distribution=icecream” to the list of linker options. Our Integrated DTLTO approach will take care of everything, from handling archives of bitcode files (which are currently not supported by current DTLTO implementation), to caching, and to managing situations when the distribution system failed to produce the native object file (fallback mechanism).
program.elf: main.bc.o libsupport.a
lld --lto=thin --distribution=icecream main.bc.o -lsupport -o program.elf
| kromanova