Skip to content

Commit a772452

Browse files
oquenchilcopybara-github
oquenchil
authored and
copybara-github
committed
Fix order of linker inputs in cc_[shared_library|binary]
In c73900b the order of the linker inputs in the linking command line was fixed for common archives between different direct deps. Before that fix the direct deps were merged sequentially without taking into account dependencies (no topological sort). After the change we were doing a topological sort but it was wrong in a way. The cc_shared_library graph is a parallel graph to the cc_library graph. The former decides partitions of the latter. From the top level cc_library every other cc_library is reachable even if it was already linked to a cc_shared_library in the dynamic dependencies. The depset that we were using for linker inputs only took into account the cc_libraries for doing a topological sort, it didn't take into account any pruning we might have done from the graph due to the presence of a shared library. After the depset was sorted we then filtered the linker inputs of cc_libraries that were already present in cc_shared_libraries in dynamic_deps. This was wrong. A cc_shared_library should be treated as a black box and its dependencies should not have any influence on the final topological order of the linker inputs. This CL addresses that by taking into account pruned inputs. In a first attempt this change re-implemented topological sorting using Kahn's algorithm but this was different to what is implemented by depset(order="topological") since in Kahn's the nodes without incoming edges are always processed first. This had the undesired effect that even when it was possible to respect the order of the deps as listed on the BUILD file and still produce a valid topological sort, Kahn's ignored the order. A second attempt (the one in this CL) re-builds a topological depset by changing the pruning algorithm to traverse the graph depth-first, then lets Bazel handle the sorting by flattening the depset. This CL also fixes the order for linker_inputs in cc_binary which had a wrong order by listing shared libraries first followed by static linker inputs without any consideration for all of the above. RELNOTES:none PiperOrigin-RevId: 542208041 Change-Id: Icaf3b488f3208259ff0bb0eef3318bef582533c5
1 parent f2a2d5f commit a772452

File tree

5 files changed

+262
-36
lines changed

5 files changed

+262
-36
lines changed

‎src/main/starlark/builtins_bzl/common/cc/cc_binary.bzl‎

Lines changed: 87 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
"""cc_binary Starlark implementation replacing native"""
1616

1717
load(":common/cc/semantics.bzl", "semantics")
18-
load(":common/cc/cc_shared_library.bzl", "GraphNodeInfo", "build_exports_map_from_only_dynamic_deps", "build_link_once_static_libs_map", "merge_cc_shared_library_infos", "separate_static_and_dynamic_link_libraries", "throw_linked_but_not_exported_errors")
18+
load(":common/cc/cc_shared_library.bzl", "CcSharedLibraryInfo", "GraphNodeInfo", "build_exports_map_from_only_dynamic_deps", "build_link_once_static_libs_map", "merge_cc_shared_library_infos", "separate_static_and_dynamic_link_libraries", "sort_linker_inputs", "throw_linked_but_not_exported_errors")
1919
load(":common/cc/cc_helper.bzl", "cc_helper", "linker_mode")
2020
load(":common/cc/cc_info.bzl", "CcInfo")
2121
load(":common/cc/cc_common.bzl", "cc_common")
@@ -331,10 +331,26 @@ def _collect_transitive_dwo_artifacts(cc_compilation_outputs, cc_debug_context,
331331
transitive_dwo_files = cc_debug_context.files
332332
return depset(dwo_files, transitive = [transitive_dwo_files])
333333

334-
def _filter_libraries_that_are_linked_dynamically(ctx, cc_linking_context, cpp_config):
334+
def _build_map_direct_dynamic_dep_to_transitive_dynamic_deps(ctx):
335+
all_dynamic_dep_linker_inputs = {}
336+
direct_dynamic_dep_to_transitive_dynamic_deps = {}
337+
for dep in ctx.attr.dynamic_deps:
338+
owner = dep[CcSharedLibraryInfo].linker_input.owner
339+
all_dynamic_dep_linker_inputs[owner] = dep[CcSharedLibraryInfo].linker_input
340+
transitive_dynamic_dep_labels = []
341+
for dynamic_dep in dep[CcSharedLibraryInfo].dynamic_deps.to_list():
342+
all_dynamic_dep_linker_inputs[dynamic_dep[1].owner] = dynamic_dep[1]
343+
transitive_dynamic_dep_labels.append(dynamic_dep[1].owner)
344+
transitive_dynamic_dep_labels_set = depset(transitive_dynamic_dep_labels, order = "topological")
345+
for export in dep[CcSharedLibraryInfo].exports:
346+
direct_dynamic_dep_to_transitive_dynamic_deps[export] = transitive_dynamic_dep_labels_set
347+
348+
return direct_dynamic_dep_to_transitive_dynamic_deps, all_dynamic_dep_linker_inputs
349+
350+
def _filter_libraries_that_are_linked_dynamically(ctx, cc_linking_context):
335351
merged_cc_shared_library_infos = merge_cc_shared_library_infos(ctx)
336352
link_once_static_libs_map = build_link_once_static_libs_map(merged_cc_shared_library_infos)
337-
exports_map = build_exports_map_from_only_dynamic_deps(merged_cc_shared_library_infos)
353+
transitive_exports = build_exports_map_from_only_dynamic_deps(merged_cc_shared_library_infos)
338354
static_linker_inputs = []
339355
linker_inputs = cc_linking_context.linker_inputs.to_list()
340356

@@ -344,28 +360,89 @@ def _filter_libraries_that_are_linked_dynamically(ctx, cc_linking_context, cpp_c
344360
can_be_linked_dynamically = {}
345361
for linker_input in linker_inputs:
346362
owner = str(linker_input.owner)
347-
if owner in exports_map:
363+
if owner in transitive_exports:
348364
can_be_linked_dynamically[owner] = True
349365

350-
(link_statically_labels, link_dynamically_labels) = separate_static_and_dynamic_link_libraries(graph_structure_aspect_nodes, can_be_linked_dynamically)
366+
transitive_dynamic_dep_labels = {}
367+
368+
# Entries in unused_dynamic_linker_inputs will be marked None if they are
369+
# used
370+
(
371+
transitive_dynamic_dep_labels,
372+
unused_dynamic_linker_inputs,
373+
) = _build_map_direct_dynamic_dep_to_transitive_dynamic_deps(ctx)
374+
375+
(
376+
targets_to_be_linked_statically_map,
377+
targets_to_be_linked_dynamically_set,
378+
topologically_sorted_labels,
379+
) = separate_static_and_dynamic_link_libraries(
380+
graph_structure_aspect_nodes,
381+
can_be_linked_dynamically,
382+
transitive_dynamic_dep_labels,
383+
)
384+
385+
topologically_sorted_labels = [ctx.label] + topologically_sorted_labels
351386

352387
linker_inputs_seen = {}
353388
linked_statically_but_not_exported = {}
389+
label_to_linker_inputs = {}
390+
391+
def _add_linker_input_to_dict(owner, linker_input):
392+
label_to_linker_inputs.setdefault(owner, []).append(linker_input)
393+
394+
linker_inputs_count = 0
354395
for linker_input in linker_inputs:
355396
stringified_linker_input = cc_helper.stringify_linker_input(linker_input)
356397
if stringified_linker_input in linker_inputs_seen:
357398
continue
358399
linker_inputs_seen[stringified_linker_input] = True
359400
owner = str(linker_input.owner)
360-
if owner not in link_dynamically_labels and (owner in link_statically_labels or str(ctx.label) == owner):
401+
if owner in targets_to_be_linked_dynamically_set:
402+
unused_dynamic_linker_inputs[transitive_exports[owner].owner] = None
403+
_add_linker_input_to_dict(linker_input.owner, transitive_exports[owner])
404+
linker_inputs_count += 1
405+
elif owner in targets_to_be_linked_statically_map or str(ctx.label) == owner:
361406
if owner in link_once_static_libs_map:
362-
linked_statically_but_not_exported.setdefault(link_once_static_libs_map[owner], []).append(owner)
407+
linked_statically_but_not_exported.setdefault(targets_to_be_linked_statically_map[owner], []).append(owner)
363408
else:
364-
static_linker_inputs.append(linker_input)
409+
_add_linker_input_to_dict(linker_input.owner, linker_input)
410+
linker_inputs_count += 1
411+
412+
# Unlike Unix on Windows every dynamic dependency must be linked to the
413+
# main binary, even indirect ones that are dependencies of direct
414+
# dynamic dependencies of this binary. So even though linking indirect
415+
# dynamic dependencies is not needed for Unix, we link them here too
416+
# because we cannot know whether the shared libraries were linked with
417+
# RUNPATH or RPATH. If they were linked with the former, then the loader
418+
# won't search in the runfiles directory of this binary for the library, it
419+
# will only search in the RUNPATH set at the time of linking the shared
420+
# library and we cannot possibly know at that point the runfiles directory
421+
# of all of its dependents.
422+
#
423+
# TODO(bazel-team):Add a feature so that indirect dynamic dependencies are
424+
# not linked. This should be opt-in for those people that are creating a
425+
# production binary and have manually set the RPATH/RUNPATHS correctly.
426+
topologically_sorted_labels_set = {label: True for label in topologically_sorted_labels}
427+
for dynamic_linker_input_owner, unused_linker_input in unused_dynamic_linker_inputs.items():
428+
if unused_linker_input:
429+
_add_linker_input_to_dict(
430+
dynamic_linker_input_owner,
431+
unused_dynamic_linker_inputs[dynamic_linker_input_owner],
432+
)
433+
linker_inputs_count += 1
434+
if dynamic_linker_input_owner not in topologically_sorted_labels_set:
435+
topologically_sorted_labels.append(dynamic_linker_input_owner)
365436

366437
throw_linked_but_not_exported_errors(linked_statically_but_not_exported)
367438

368-
return cc_common.create_linking_context(linker_inputs = depset(exports_map.values() + static_linker_inputs, order = "topological"))
439+
sorted_linker_inputs = sort_linker_inputs(
440+
topologically_sorted_labels,
441+
label_to_linker_inputs,
442+
linker_inputs_count,
443+
)
444+
445+
return cc_common.create_linking_context(linker_inputs = depset(sorted_linker_inputs, order = "topological"))
369446

370447
def _create_transitive_linking_actions(
371448
ctx,
@@ -446,7 +523,7 @@ def _create_transitive_linking_actions(
446523
cc_linking_context = cc_info.linking_context
447524

448525
if len(ctx.attr.dynamic_deps) > 0:
449-
cc_linking_context = _filter_libraries_that_are_linked_dynamically(ctx, cc_linking_context, cpp_config)
526+
cc_linking_context = _filter_libraries_that_are_linked_dynamically(ctx, cc_linking_context)
450527
link_deps_statically = True
451528
if linking_mode == linker_mode.LINKING_DYNAMIC:
452529
link_deps_statically = False

‎src/main/starlark/builtins_bzl/common/cc/cc_shared_library.bzl‎

Lines changed: 135 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -50,24 +50,77 @@ CcSharedLibraryInfo = provider(
5050
},
5151
)
5252

53+
def _programmatic_error(message = ""):
54+
fail("Your build has triggered a programmatic error in the cc_shared_library rule. " +
55+
"Please file an issue in https://github.com/bazelbuild/bazel : {}".format(message))
56+
57+
def _sort_linker_inputs(topologically_sorted_labels, label_to_linker_inputs, linker_inputs_count):
58+
# len(label_to_linker_inputs) might not match the topologically_sorted_labels
59+
# size. The latter is looking at nodes in the graph but a node may not
60+
# necessarily contribute any linker_inputs. For example a cc_library with
61+
# no sources and only deps. Every linker_input.owner must be in
62+
# topologically_sorted_labels otherwise there is an error in the rule
63+
# implementation of the target providing that linker_input, e.g. it's
64+
# missing a CcSharedLibraryHintInfo if it had custom owner names for linker
65+
# inputs.
66+
sorted_linker_inputs = []
67+
for label in topologically_sorted_labels:
68+
if label not in label_to_linker_inputs:
69+
# This is ok. It can happen if no linker_inputs
70+
# were added by a node in the graph.
71+
continue
72+
sorted_linker_inputs.extend(label_to_linker_inputs[label])
73+
74+
if len(sorted_linker_inputs) != linker_inputs_count:
75+
owners = []
76+
for sorted_linker_input in sorted_linker_inputs:
77+
owners.append(str(sorted_linker_input.owner))
78+
_programmatic_error("{} vs {}".format(",".join(owners), linker_inputs_count))
79+
80+
return sorted_linker_inputs
81+
5382
# For each target, find out whether it should be linked statically or
54-
# dynamically.
83+
# dynamically. The transitive_dynamic_dep_labels parameter is only needed for
84+
# binaries because they link all dynamic_deps (cc_binary|cc_test).
5585
def _separate_static_and_dynamic_link_libraries(
5686
direct_children,
57-
can_be_linked_dynamically):
87+
can_be_linked_dynamically,
88+
transitive_dynamic_dep_labels = {}):
5889
node = None
59-
all_children = list(direct_children)
90+
all_children = reversed(direct_children)
6091
targets_to_be_linked_statically_map = {}
6192
targets_to_be_linked_dynamically_set = {}
62-
6393
seen_labels = {}
6494

95+
# The cc_shared_library graph is parallel to the cc_library graph.
96+
# Propagation of linker inputs between cc_libraries happens via the CcInfo
97+
# provider. Parallel to this we have cc_shared_libraries which may decide
98+
# different partitions of the cc_library graph.
99+
#
100+
# In a previous implementation of cc_shared_library we relied on the
101+
# topological sort given by flattening
102+
# cc_info.linking_context.linker_inputs.to_list(), however this was wrong
103+
# because the dependencies of a shared library (i.e. a pruned node here)
104+
# influenced the final order.
105+
#
106+
# In order to fix this, the pruning below was changed from breadth-first
107+
# traversal to depth-first traversal. While doing this we also recreate a
108+
# depset with topological order that takes into account the pruned nodes
109+
# and which will later be used to order the libraries in the linking
110+
# command line. This will be in topological order and will respect the
111+
# order of the deps as listed on the BUILD file as much as possible.
112+
#
113+
# Here we say "first_owner" because each node (see GraphNodeInfo) may have
114+
# more than one linker_input (each potentially with a different owner) but
115+
# using only the first owner as a key is enough.
116+
first_owner_to_depset = {}
117+
65118
# Horrible I know. Perhaps Starlark team gives me a way to prune a tree.
66119
for i in range(2147483647):
67-
if i == len(all_children):
120+
if not len(all_children):
68121
break
69122

70-
node = all_children[i]
123+
node = all_children[-1]
71124

72125
must_add_children = False
73126

@@ -85,6 +138,8 @@ def _separate_static_and_dynamic_link_libraries(
85138
# the cc_shared_library implementation owners.
86139
has_owners_seen = False
87140
has_owners_not_seen = False
141+
linked_dynamically = False
142+
linked_statically = False
88143
for owner in node.owners:
89144
# TODO(bazel-team): Do not convert Labels to string to save on
90145
# garbage string allocations.
@@ -99,18 +154,62 @@ def _separate_static_and_dynamic_link_libraries(
99154

100155
if owner_str in can_be_linked_dynamically:
101156
targets_to_be_linked_dynamically_set[owner_str] = True
157+
linked_dynamically = True
102158
else:
103159
targets_to_be_linked_statically_map[owner_str] = node.linkable_more_than_once
104160
must_add_children = True
161+
linked_statically = True
105162

106163
if has_owners_seen and has_owners_not_seen:
107-
fail("Your build has triggered a programmatic error in the cc_shared_library rule. " +
108-
"Please file an issue in https://github.com/bazelbuild/bazel")
164+
_programmatic_error()
165+
166+
if linked_dynamically and linked_statically:
167+
error_owners_list = [str(owner) for owner in node.owners]
168+
169+
# Our granularity is target level. Unless there is a different
170+
# unsupported custom implementation of this rule it should be
171+
# impossible for two linker_inputs from the same target to be
172+
# linked differently, one statically and the other dynamically.
173+
_programmatic_error(
174+
message = "Nodes with linker_inputs linked statically and dynamically:" +
175+
"\n{}".format("\n".join(error_owners_list)),
176+
)
109177

110178
if must_add_children:
111-
all_children.extend(node.children)
112-
113-
return (targets_to_be_linked_statically_map, targets_to_be_linked_dynamically_set)
179+
# The order in which we process the children matter. all_children
180+
# is being used as a stack, we will process first the nodes at the
181+
# top of the stack (last in the list). The children are the
182+
# dependencies of the current node, in order to respect the order
183+
# in which dependencies were listed in the deps attribute in the
184+
# BUILD file we must reverse the list so that the first one listed
185+
# in the BUILD file is processed first.
186+
all_children.extend(reversed(node.children))
187+
else:
188+
if node.owners[0] not in first_owner_to_depset:
189+
# We have 3 cases in this branch:
190+
# 1. Node has no children
191+
# 2. The children have been pruned because the node is linked dynamically
192+
# 3. Node has children that have been processed
193+
# For case 3 we add the children's depsets. For case 2 we add the dynamic
194+
# dep labels for transitive dynamic deps.
195+
transitive = []
196+
if str(node.owners[0]) in targets_to_be_linked_statically_map:
197+
for child in node.children:
198+
transitive.append(first_owner_to_depset[child.owners[0]])
199+
elif str(node.owners[0]) in transitive_dynamic_dep_labels:
200+
transitive.append(transitive_dynamic_dep_labels[str(node.owners[0])])
201+
202+
first_owner_to_depset[node.owners[0]] = depset(direct = node.owners, transitive = transitive, order = "topological")
203+
all_children.pop()
204+
205+
topologically_sorted_labels = []
206+
if direct_children:
207+
transitive = []
208+
for child in direct_children:
209+
transitive.append(first_owner_to_depset[child.owners[0]])
210+
topologically_sorted_labels = depset(transitive = transitive, order = "topological").to_list()
211+
212+
return (targets_to_be_linked_statically_map, targets_to_be_linked_dynamically_set, topologically_sorted_labels)
114213

115214
def _create_linker_context(ctx, linker_inputs):
116215
return cc_common.create_linking_context(
@@ -129,7 +228,7 @@ def _merge_cc_shared_library_infos(ctx):
129228
dynamic_deps.append(dynamic_dep_entry)
130229
transitive_dynamic_deps.append(dep[CcSharedLibraryInfo].dynamic_deps)
131230

132-
return depset(direct = dynamic_deps, transitive = transitive_dynamic_deps)
231+
return depset(direct = dynamic_deps, transitive = transitive_dynamic_deps, order = "topological")
133232

134233
def _build_exports_map_from_only_dynamic_deps(merged_shared_library_infos):
135234
exports_map = {}
@@ -267,7 +366,6 @@ def _filter_inputs(
267366
deps,
268367
transitive_exports,
269368
link_once_static_libs_map):
270-
linker_inputs = []
271369
curr_link_once_static_libs_set = {}
272370

273371
graph_structure_aspect_nodes = []
@@ -291,7 +389,11 @@ def _filter_inputs(
291389

292390
# The targets_to_be_linked_statically_map points to whether the target to
293391
# be linked statically can be linked more than once.
294-
(targets_to_be_linked_statically_map, targets_to_be_linked_dynamically_set) = _separate_static_and_dynamic_link_libraries(
392+
(
393+
targets_to_be_linked_statically_map,
394+
targets_to_be_linked_dynamically_set,
395+
topologically_sorted_labels,
396+
) = _separate_static_and_dynamic_link_libraries(
295397
graph_structure_aspect_nodes,
296398
can_be_linked_dynamically,
297399
)
@@ -313,6 +415,11 @@ def _filter_inputs(
313415
precompiled_only_dynamic_libraries = []
314416
exports = {}
315417
linker_inputs_seen = {}
418+
linker_inputs_count = 0
419+
label_to_linker_inputs = {}
420+
421+
def _add_linker_input_to_dict(owner, linker_input):
422+
label_to_linker_inputs.setdefault(owner, []).append(linker_input)
316423

317424
# We use this dictionary to give an error if a target containing only
318425
# precompiled dynamic libraries is placed directly in roots. If such a
@@ -331,7 +438,8 @@ def _filter_inputs(
331438
# Link the library in this iteration dynamically,
332439
# transitive_exports contains the artifacts produced by a
333440
# cc_shared_library
334-
linker_inputs.append(transitive_exports[owner])
441+
_add_linker_input_to_dict(linker_input.owner, transitive_exports[owner])
442+
linker_inputs_count += 1
335443
elif owner in targets_to_be_linked_statically_map:
336444
if owner in link_once_static_libs_map:
337445
# We are building a dictionary that will allow us to give
@@ -357,7 +465,8 @@ def _filter_inputs(
357465
if not len(static_libraries):
358466
if owner in direct_deps_set:
359467
dynamic_only_roots[owner] = True
360-
linker_inputs.append(linker_input)
468+
_add_linker_input_to_dict(linker_input.owner, linker_input)
469+
linker_inputs_count += 1
361470
continue
362471
if len(static_libraries) and owner in dynamic_only_roots:
363472
dynamic_only_roots.pop(owner)
@@ -377,7 +486,8 @@ def _filter_inputs(
377486
):
378487
exports[owner] = True
379488

380-
linker_inputs.append(linker_input_to_be_linked_statically)
489+
_add_linker_input_to_dict(linker_input.owner, linker_input_to_be_linked_statically)
490+
linker_inputs_count += 1
381491

382492
if not targets_to_be_linked_statically_map[owner]:
383493
curr_link_once_static_libs_set[owner] = True
@@ -390,8 +500,14 @@ def _filter_inputs(
390500
message += dynamic_only_root + "\n"
391501
fail(message)
392502

503+
sorted_linker_inputs = _sort_linker_inputs(
504+
topologically_sorted_labels,
505+
label_to_linker_inputs,
506+
linker_inputs_count,
507+
)
508+
393509
_throw_linked_but_not_exported_errors(linked_statically_but_not_exported)
394-
return (exports, linker_inputs, curr_link_once_static_libs_set.keys(), precompiled_only_dynamic_libraries)
510+
return (exports, sorted_linker_inputs, curr_link_once_static_libs_set.keys(), precompiled_only_dynamic_libraries)
395511

396512
def _throw_linked_but_not_exported_errors(error_libs_dict):
397513
if not error_libs_dict:
@@ -684,3 +800,4 @@ build_link_once_static_libs_map = _build_link_once_static_libs_map
684800
build_exports_map_from_only_dynamic_deps = _build_exports_map_from_only_dynamic_deps
685801
throw_linked_but_not_exported_errors = _throw_linked_but_not_exported_errors
686802
separate_static_and_dynamic_link_libraries = _separate_static_and_dynamic_link_libraries
803+
sort_linker_inputs = _sort_linker_inputs

0 commit comments

Comments
 (0)