aboutsummaryrefslogtreecommitdiff
path: root/elf/dl-fini.c
diff options
context:
space:
mode:
authorChung-Lin Tang <cltang@codesourcery.com>2021-10-21 21:41:22 +0800
committerAdhemerval Zanella <adhemerval.zanella@linaro.org>2021-10-21 11:23:53 -0300
commit15a0c5730d1d5aeb95f50c9ec7470640084feae8 (patch)
tree3c38108344adce9db163005cb197b4300a6fff94 /elf/dl-fini.c
parente6fd79f3795d46dfb583e124be49fc063bc3d58b (diff)
downloadglibc-15a0c5730d1d5aeb95f50c9ec7470640084feae8.zip
glibc-15a0c5730d1d5aeb95f50c9ec7470640084feae8.tar.gz
glibc-15a0c5730d1d5aeb95f50c9ec7470640084feae8.tar.bz2
elf: Fix slow DSO sorting behavior in dynamic loader (BZ #17645)
This second patch contains the actual implementation of a new sorting algorithm for shared objects in the dynamic loader, which solves the slow behavior that the current "old" algorithm falls into when the DSO set contains circular dependencies. The new algorithm implemented here is simply depth-first search (DFS) to obtain the Reverse-Post Order (RPO) sequence, a topological sort. A new l_visited:1 bitfield is added to struct link_map to more elegantly facilitate such a search. The DFS algorithm is applied to the input maps[nmap-1] backwards towards maps[0]. This has the effect of a more "shallow" recursion depth in general since the input is in BFS. Also, when combined with the natural order of processing l_initfini[] at each node, this creates a resulting output sorting closer to the intuitive "left-to-right" order in most cases. Another notable implementation adjustment related to this _dl_sort_maps change is the removing of two char arrays 'used' and 'done' in _dl_close_worker to represent two per-map attributes. This has been changed to simply use two new bit-fields l_map_used:1, l_map_done:1 added to struct link_map. This also allows discarding the clunky 'used' array sorting that _dl_sort_maps had to sometimes do along the way. Tunable support for switching between different sorting algorithms at runtime is also added. A new tunable 'glibc.rtld.dynamic_sort' with current valid values 1 (old algorithm) and 2 (new DFS algorithm) has been added. At time of commit of this patch, the default setting is 1 (old algorithm). Signed-off-by: Chung-Lin Tang <cltang@codesourcery.com> Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Diffstat (limited to 'elf/dl-fini.c')
-rw-r--r--elf/dl-fini.c3
1 files changed, 1 insertions, 2 deletions
diff --git a/elf/dl-fini.c b/elf/dl-fini.c
index 6dbdfe4..c683884 100644
--- a/elf/dl-fini.c
+++ b/elf/dl-fini.c
@@ -92,8 +92,7 @@ _dl_fini (void)
/* Now we have to do the sorting. We can skip looking for the
binary itself which is at the front of the search list for
the main namespace. */
- _dl_sort_maps (maps + (ns == LM_ID_BASE), nmaps - (ns == LM_ID_BASE),
- NULL, true);
+ _dl_sort_maps (maps, nmaps, (ns == LM_ID_BASE), true);
/* We do not rely on the linked list of loaded object anymore
from this point on. We have our own list here (maps). The