Automatically reorder C/C++ link dependencies in Soong
This uses knowledge of transitive dependencies to reorder
linker command line arguments such that if module A depends
on module B, then module A is automatically listed before
module B in the linker command line.
This should mostly remove the need for Android.bp files to
list all of their static dependencies in link order
Bug: 66260943
Test: reorder the entries of static_libs in an Android.bp and see that linking still succeeds
Change-Id: I20f851ab9f2f30031254e4f30023b6140d15d6c3
diff --git a/android/paths.go b/android/paths.go
index f88d650..ed1e607 100644
--- a/android/paths.go
+++ b/android/paths.go
@@ -303,6 +303,32 @@
return list[:k]
}
+func indexPathList(s Path, list []Path) int {
+ for i, l := range list {
+ if l == s {
+ return i
+ }
+ }
+
+ return -1
+}
+
+func inPathList(p Path, list []Path) bool {
+ return indexPathList(p, list) != -1
+}
+
+func FilterPathList(list []Path, filter []Path) (remainder []Path, filtered []Path) {
+ for _, l := range list {
+ if inPathList(l, filter) {
+ filtered = append(filtered, l)
+ } else {
+ remainder = append(remainder, l)
+ }
+ }
+
+ return
+}
+
// HasExt returns true of any of the paths have extension ext, otherwise false
func (p Paths) HasExt(ext string) bool {
for _, path := range p {
diff --git a/android/testing.go b/android/testing.go
index 519e279..667c1aa 100644
--- a/android/testing.go
+++ b/android/testing.go
@@ -65,7 +65,14 @@
})
if module == nil {
- panic(fmt.Errorf("failed to find module %q variant %q", name, variant))
+ // find all the modules that do exist
+ allModuleNames := []string{}
+ ctx.VisitAllModules(func(m blueprint.Module) {
+ allModuleNames = append(allModuleNames, m.(Module).Name()+"("+ctx.ModuleSubDir(m)+")")
+ })
+
+ panic(fmt.Errorf("failed to find module %q variant %q."+
+ "\nall modules: %v", name, variant, allModuleNames))
}
return TestingModule{module}
diff --git a/cc/cc.go b/cc/cc.go
index 2fafaa2..7163696 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -326,6 +326,11 @@
// Flags used to compile this module
flags Flags
+
+ // When calling a linker, if module A depends on module B, then A must precede B in its command
+ // line invocation. staticDepsInLinkOrder stores the proper ordering of all of the transitive
+ // deps of this module
+ staticDepsInLinkOrder android.Paths
}
func (c *Module) Init() android.Module {
@@ -540,6 +545,51 @@
return name
}
+// orderDeps reorders dependencies into a list such that if module A depends on B, then
+// A will precede B in the resultant list.
+// This is convenient for passing into a linker.
+func orderDeps(directDeps []android.Path, transitiveDeps map[android.Path][]android.Path) (orderedAllDeps []android.Path, orderedDeclaredDeps []android.Path) {
+ // If A depends on B, then
+ // Every list containing A will also contain B later in the list
+ // So, after concatenating all lists, the final instance of B will have come from the same
+ // original list as the final instance of A
+ // So, the final instance of B will be later in the concatenation than the final A
+ // So, keeping only the final instance of A and of B ensures that A is earlier in the output
+ // list than B
+ for _, dep := range directDeps {
+ orderedAllDeps = append(orderedAllDeps, dep)
+ orderedAllDeps = append(orderedAllDeps, transitiveDeps[dep]...)
+ }
+
+ orderedAllDeps = lastUniquePaths(orderedAllDeps)
+
+ // We don't want to add any new dependencies into directDeps (to allow the caller to
+ // intentionally exclude or replace any unwanted transitive dependencies), so we limit the
+ // resultant list to only what the caller has chosen to include in directDeps
+ _, orderedDeclaredDeps = android.FilterPathList(orderedAllDeps, directDeps)
+
+ return orderedAllDeps, orderedDeclaredDeps
+}
+
+func orderStaticModuleDeps(module *Module, deps []*Module) (results []android.Path) {
+ // make map of transitive dependencies
+ transitiveStaticDepNames := make(map[android.Path][]android.Path, len(deps))
+ for _, dep := range deps {
+ transitiveStaticDepNames[dep.outputFile.Path()] = dep.staticDepsInLinkOrder
+ }
+ // get the output file for each declared dependency
+ depFiles := []android.Path{}
+ for _, dep := range deps {
+ depFiles = append(depFiles, dep.outputFile.Path())
+ }
+
+ // reorder the dependencies based on transitive dependencies
+ module.staticDepsInLinkOrder, results = orderDeps(depFiles, transitiveStaticDepNames)
+
+ return results
+
+}
+
func (c *Module) GenerateAndroidBuildActions(actx android.ModuleContext) {
ctx := &moduleContext{
@@ -985,6 +1035,8 @@
func (c *Module) depsToPaths(ctx android.ModuleContext) PathDeps {
var depPaths PathDeps
+ directStaticDeps := []*Module{}
+
ctx.VisitDirectDeps(func(dep blueprint.Module) {
depName := ctx.OtherModuleName(dep)
depTag := ctx.OtherModuleDependencyTag(dep)
@@ -1108,7 +1160,8 @@
depPtr = &depPaths.LateSharedLibsDeps
depFile = ccDep.linker.(libraryInterface).toc()
case staticDepTag, staticExportDepTag:
- ptr = &depPaths.StaticLibs
+ ptr = nil
+ directStaticDeps = append(directStaticDeps, ccDep)
case lateStaticDepTag:
ptr = &depPaths.LateStaticLibs
case wholeStaticDepTag:
@@ -1192,6 +1245,9 @@
}
})
+ // use the ordered dependencies as this module's dependencies
+ depPaths.StaticLibs = append(depPaths.StaticLibs, orderStaticModuleDeps(c, directStaticDeps)...)
+
// Dedup exported flags from dependencies
depPaths.Flags = firstUniqueElements(depPaths.Flags)
depPaths.GeneratedHeaders = android.FirstUniquePaths(depPaths.GeneratedHeaders)
@@ -1417,6 +1473,23 @@
return list[totalSkip:]
}
+// lastUniquePaths is the same as lastUniqueElements but uses Path structs
+func lastUniquePaths(list []android.Path) []android.Path {
+ totalSkip := 0
+ for i := len(list) - 1; i >= totalSkip; i-- {
+ skip := 0
+ for j := i - 1; j >= totalSkip; j-- {
+ if list[i] == list[j] {
+ skip++
+ } else {
+ list[j+skip] = list[j]
+ }
+ }
+ totalSkip += skip
+ }
+ return list[totalSkip:]
+}
+
func getCurrentNdkPrebuiltVersion(ctx DepsContext) string {
if ctx.AConfig().PlatformSdkVersionInt() > config.NdkMaxPrebuiltVersionInt {
return strconv.Itoa(config.NdkMaxPrebuiltVersionInt)
diff --git a/cc/cc_test.go b/cc/cc_test.go
index 94e3e66..b9cdba5 100644
--- a/cc/cc_test.go
+++ b/cc/cc_test.go
@@ -2,9 +2,12 @@
import (
"android/soong/android"
+ "fmt"
"io/ioutil"
"os"
"reflect"
+ "sort"
+ "strings"
"testing"
"github.com/google/blueprint/proptools"
@@ -43,6 +46,7 @@
ctx.RegisterModuleType("cc_library", android.ModuleFactoryAdaptor(libraryFactory))
ctx.RegisterModuleType("toolchain_library", android.ModuleFactoryAdaptor(toolchainLibraryFactory))
ctx.RegisterModuleType("llndk_library", android.ModuleFactoryAdaptor(llndkLibraryFactory))
+ ctx.RegisterModuleType("cc_object", android.ModuleFactoryAdaptor(objectFactory))
ctx.PreDepsMutators(func(ctx android.RegisterMutatorsContext) {
ctx.BottomUp("image", vendorMutator).Parallel()
ctx.BottomUp("link", linkageMutator).Parallel()
@@ -50,6 +54,64 @@
})
ctx.Register()
+ // add some modules that are required by the compiler and/or linker
+ bp = bp + `
+ toolchain_library {
+ name: "libatomic",
+ vendor_available: true,
+ }
+
+ toolchain_library {
+ name: "libcompiler_rt-extras",
+ vendor_available: true,
+ }
+
+ toolchain_library {
+ name: "libgcc",
+ vendor_available: true,
+ }
+
+ cc_library {
+ name: "libc",
+ no_libgcc : true,
+ nocrt : true,
+ system_shared_libs: [],
+ }
+ llndk_library {
+ name: "libc",
+ symbol_file: "",
+ }
+ cc_library {
+ name: "libm",
+ no_libgcc : true,
+ nocrt : true,
+ system_shared_libs: [],
+ }
+ llndk_library {
+ name: "libm",
+ symbol_file: "",
+ }
+ cc_library {
+ name: "libdl",
+ no_libgcc : true,
+ nocrt : true,
+ system_shared_libs: [],
+ }
+ llndk_library {
+ name: "libdl",
+ symbol_file: "",
+ }
+
+ cc_object {
+ name: "crtbegin_so",
+ }
+
+ cc_object {
+ name: "crtend_so",
+ }
+
+`
+
ctx.MockFileSystem(map[string][]byte{
"Android.bp": []byte(bp),
"foo.c": nil,
@@ -57,9 +119,9 @@
})
_, errs := ctx.ParseBlueprintsFiles("Android.bp")
- fail(t, errs)
+ failIfErrored(t, errs)
_, errs = ctx.PrepareBuildActions(config)
- fail(t, errs)
+ failIfErrored(t, errs)
return ctx
}
@@ -79,44 +141,6 @@
},
},
}
- toolchain_library {
- name: "libatomic",
- vendor_available: true,
- }
- toolchain_library {
- name: "libcompiler_rt-extras",
- vendor_available: true,
- }
- cc_library {
- name: "libc",
- no_libgcc : true,
- nocrt : true,
- system_shared_libs: [],
- }
- llndk_library {
- name: "libc",
- symbol_file: "",
- }
- cc_library {
- name: "libm",
- no_libgcc : true,
- nocrt : true,
- system_shared_libs: [],
- }
- llndk_library {
- name: "libm",
- symbol_file: "",
- }
- cc_library {
- name: "libdl",
- no_libgcc : true,
- nocrt : true,
- system_shared_libs: [],
- }
- llndk_library {
- name: "libdl",
- symbol_file: "",
- }
`)
ld := ctx.ModuleForTests("libTest", "android_arm_armv7-a-neon_vendor_shared").Rule("ld")
@@ -339,3 +363,245 @@
}
}
}
+
+var staticLinkDepOrderTestCases = []struct {
+ // This is a string representation of a map[moduleName][]moduleDependency .
+ // It models the dependencies declared in an Android.bp file.
+ in string
+
+ // allOrdered is a string representation of a map[moduleName][]moduleDependency .
+ // The keys of allOrdered specify which modules we would like to check.
+ // The values of allOrdered specify the expected result (of the transitive closure of all
+ // dependencies) for each module to test
+ allOrdered string
+
+ // outOrdered is a string representation of a map[moduleName][]moduleDependency .
+ // The keys of outOrdered specify which modules we would like to check.
+ // The values of outOrdered specify the expected result (of the ordered linker command line)
+ // for each module to test.
+ outOrdered string
+}{
+ // Simple tests
+ {
+ in: "",
+ outOrdered: "",
+ },
+ {
+ in: "a:",
+ outOrdered: "a:",
+ },
+ {
+ in: "a:b; b:",
+ outOrdered: "a:b; b:",
+ },
+ // Tests of reordering
+ {
+ // diamond example
+ in: "a:d,b,c; b:d; c:d; d:",
+ outOrdered: "a:b,c,d; b:d; c:d; d:",
+ },
+ {
+ // somewhat real example
+ in: "bsdiff_unittest:b,c,d,e,f,g,h,i; e:b",
+ outOrdered: "bsdiff_unittest:c,d,e,b,f,g,h,i; e:b",
+ },
+ {
+ // multiple reorderings
+ in: "a:b,c,d,e; d:b; e:c",
+ outOrdered: "a:d,b,e,c; d:b; e:c",
+ },
+ {
+ // should reorder without adding new transitive dependencies
+ in: "bin:lib2,lib1; lib1:lib2,liboptional",
+ allOrdered: "bin:lib1,lib2,liboptional; lib1:lib2,liboptional",
+ outOrdered: "bin:lib1,lib2; lib1:lib2,liboptional",
+ },
+ {
+ // multiple levels of dependencies
+ in: "a:b,c,d,e,f,g,h; f:b,c,d; b:c,d; c:d",
+ allOrdered: "a:e,f,b,c,d,g,h; f:b,c,d; b:c,d; c:d",
+ outOrdered: "a:e,f,b,c,d,g,h; f:b,c,d; b:c,d; c:d",
+ },
+ // tiebreakers for when two modules specifying different orderings and there is no dependency
+ // to dictate an order
+ {
+ // if the tie is between two modules at the end of a's deps, then a's order wins
+ in: "a1:b,c,d,e; a2:b,c,e,d; b:d,e; c:e,d",
+ outOrdered: "a1:b,c,d,e; a2:b,c,e,d; b:d,e; c:e,d",
+ },
+ {
+ // if the tie is between two modules at the start of a's deps, then c's order is used
+ in: "a1:d,e,b1,c1; b1:d,e; c1:e,d; a2:d,e,b2,c2; b2:d,e; c2:d,e",
+ outOrdered: "a1:b1,c1,e,d; b1:d,e; c1:e,d; a2:b2,c2,d,e; b2:d,e; c2:d,e",
+ },
+ // Tests involving duplicate dependencies
+ {
+ // simple duplicate
+ in: "a:b,c,c,b",
+ outOrdered: "a:c,b",
+ },
+ {
+ // duplicates with reordering
+ in: "a:b,c,d,c; c:b",
+ outOrdered: "a:d,c,b",
+ },
+ // Tests to confirm the nonexistence of infinite loops.
+ // These cases should never happen, so as long as the test terminates and the
+ // result is deterministic then that should be fine.
+ {
+ in: "a:a",
+ outOrdered: "a:a",
+ },
+ {
+ in: "a:b; b:c; c:a",
+ allOrdered: "a:b,c; b:c,a; c:a,b",
+ outOrdered: "a:b; b:c; c:a",
+ },
+ {
+ in: "a:b,c; b:c,a; c:a,b",
+ allOrdered: "a:c,a,b; b:a,b,c; c:b,c,a",
+ outOrdered: "a:c,b; b:a,c; c:b,a",
+ },
+}
+
+// converts from a string like "a:b,c; d:e" to (["a","b"], {"a":["b","c"], "d":["e"]}, [{"a", "a.o"}, {"b", "b.o"}])
+func parseModuleDeps(text string) (modulesInOrder []android.Path, allDeps map[android.Path][]android.Path) {
+ // convert from "a:b,c; d:e" to "a:b,c;d:e"
+ strippedText := strings.Replace(text, " ", "", -1)
+ if len(strippedText) < 1 {
+ return []android.Path{}, make(map[android.Path][]android.Path, 0)
+ }
+ allDeps = make(map[android.Path][]android.Path, 0)
+
+ // convert from "a:b,c;d:e" to ["a:b,c", "d:e"]
+ moduleTexts := strings.Split(strippedText, ";")
+
+ outputForModuleName := func(moduleName string) android.Path {
+ return android.PathForTesting(moduleName)
+ }
+
+ for _, moduleText := range moduleTexts {
+ // convert from "a:b,c" to ["a", "b,c"]
+ components := strings.Split(moduleText, ":")
+ if len(components) != 2 {
+ panic(fmt.Sprintf("illegal module dep string %q from larger string %q; must contain one ':', not %v", moduleText, text, len(components)-1))
+ }
+ moduleName := components[0]
+ moduleOutput := outputForModuleName(moduleName)
+ modulesInOrder = append(modulesInOrder, moduleOutput)
+
+ depString := components[1]
+ // convert from "b,c" to ["b", "c"]
+ depNames := strings.Split(depString, ",")
+ if len(depString) < 1 {
+ depNames = []string{}
+ }
+ var deps []android.Path
+ for _, depName := range depNames {
+ deps = append(deps, outputForModuleName(depName))
+ }
+ allDeps[moduleOutput] = deps
+ }
+ return modulesInOrder, allDeps
+}
+
+func TestStaticLinkDependencyOrdering(t *testing.T) {
+ for _, testCase := range staticLinkDepOrderTestCases {
+ errs := []string{}
+
+ // parse testcase
+ _, givenTransitiveDeps := parseModuleDeps(testCase.in)
+ expectedModuleNames, expectedTransitiveDeps := parseModuleDeps(testCase.outOrdered)
+ if testCase.allOrdered == "" {
+ // allow the test case to skip specifying allOrdered
+ testCase.allOrdered = testCase.outOrdered
+ }
+ _, expectedAllDeps := parseModuleDeps(testCase.allOrdered)
+
+ // For each module whose post-reordered dependencies were specified, validate that
+ // reordering the inputs produces the expected outputs.
+ for _, moduleName := range expectedModuleNames {
+ moduleDeps := givenTransitiveDeps[moduleName]
+ orderedAllDeps, orderedDeclaredDeps := orderDeps(moduleDeps, givenTransitiveDeps)
+
+ correctAllOrdered := expectedAllDeps[moduleName]
+ if !reflect.DeepEqual(orderedAllDeps, correctAllOrdered) {
+ errs = append(errs, fmt.Sprintf("orderDeps returned incorrect orderedAllDeps."+
+ "\nInput: %q"+
+ "\nmodule: %v"+
+ "\nexpected: %s"+
+ "\nactual: %s",
+ testCase.in, moduleName, correctAllOrdered, orderedAllDeps))
+ }
+
+ correctOutputDeps := expectedTransitiveDeps[moduleName]
+ if !reflect.DeepEqual(correctOutputDeps, orderedDeclaredDeps) {
+ errs = append(errs, fmt.Sprintf("orderDeps returned incorrect orderedDeclaredDeps."+
+ "\nInput: %q"+
+ "\nmodule: %v"+
+ "\nexpected: %s"+
+ "\nactual: %s",
+ testCase.in, moduleName, correctOutputDeps, orderedDeclaredDeps))
+ }
+ }
+
+ if len(errs) > 0 {
+ sort.Strings(errs)
+ for _, err := range errs {
+ t.Error(err)
+ }
+ }
+ }
+}
+func failIfErrored(t *testing.T, errs []error) {
+ if len(errs) > 0 {
+ for _, err := range errs {
+ t.Error(err)
+ }
+ t.FailNow()
+ }
+}
+
+func getOutputPaths(ctx *android.TestContext, variant string, moduleNames []string) (paths android.Paths) {
+ for _, moduleName := range moduleNames {
+ module := ctx.ModuleForTests(moduleName, variant).Module().(*Module)
+ output := module.outputFile.Path()
+ paths = append(paths, output)
+ }
+ return paths
+}
+
+func TestLibDeps(t *testing.T) {
+ ctx := testCc(t, `
+ cc_library {
+ name: "a",
+ static_libs: ["b", "c", "d"],
+ }
+ cc_library {
+ name: "b",
+ }
+ cc_library {
+ name: "c",
+ static_libs: ["b"],
+ }
+ cc_library {
+ name: "d",
+ }
+
+ `)
+
+ variant := "android_arm64_armv8-a_core_static"
+ moduleA := ctx.ModuleForTests("a", variant).Module().(*Module)
+ actual := moduleA.staticDepsInLinkOrder
+ expected := getOutputPaths(ctx, variant, []string{"c", "b", "d"})
+
+ if !reflect.DeepEqual(actual, expected) {
+ t.Errorf("staticDeps orderings were not propagated correctly"+
+ "\nactual: %v"+
+ "\nexpected: %v",
+ actual,
+ expected,
+ )
+ }
+
+}