BZ #17645, fix slow DSO sorting behavior in dynamic loader -- Algorithm changesazanella/dso-opt

This part is the actual code changes.  While the past attempts appeared
to be either (1) more sophisticated graph algorithms, with attempts to
add Tarjan SCC, or (2) modifying of heuristics to augment the old
algorithm to behave more reasonably, here I have basically adhered to
the KISS principle.

The main algorithm 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.

I also have experimented with doing an iterative version, but it is
obviously harder to understand, and actually slower when measured by
hp-timing.h facilities.  I have chosen to use simple recursive DFS, for
clarity and performance (Some measures were however taken to curb
recursion depth)

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.

Per-the discussion in #15311 about relocation dependencies overriding
link dependencies, similar to comments #7,#9 there, a second pass of
link-dependency-only sorting has been added in that case. Detection of
existence of reldeps is done during the first DFS traversal pass, to
cull away unneeded cases of this 2nd sorting pass. This also allows
discarding of the simple limited cycle detection (i.e. X has reldep on Y,
Y links to X) in the current algorithm.  A testcase expressing the
BZ#15311 case has also been added.

On the further general issue of circular dependencies causing SCCs
across shared objects, the ELF specification explicitly states that
behavior in this case is undefined, although I have found at least one
reference describing Solaris' behavior here as basically retaining the
received original ordering of those objects [1]. While quite well defined,
I'm a little unsure this is the reasonable behavior, as this seems to
imply a single circular dependency link will nullify correct topological
dependency behavior for the majority of nodes within that SCC.

The Tarjan SCC algorthm has been mentioned multiple times in these
related BZ issues.  It could be said that the Tarjan algorithm is a
generalization of post-order DFS traversal; some might say that's an
understatement, but the phases of the node visiting and processing
really look analogous.  It would be possible to extend and implement it
mostly within the confines of the code of my patch, but considering the
undefined status in the spec, arguably some ambiguities of proper
reasonable behavior, and the much more bookkeeping in a piece of code
that will be repeatedly executed an incredible number of times across
all systems, of which only applies to quite rare cases, I have refrained
from adding that kind of processing in this patch, though such issues
may be revisited later.

Other two notable implementation adjustments related to this
_dl_sort_maps() change are:

  (1) The additional pass of sorting in dl_open_worker() right before
      relocation has been removed.  _dl_map_object_deps() already does
      a pass of sorting, and simply collecting objects by that order is
      adequate. Sorting again in that place before relocation appears
      to be redundant.

  (2) The use of two char arrays 'used' and 'done' in _dl_close_worker
      to represent two per-map attributes has been changed to simply use
      the two bits in the 'l_reserved' field in struct link_map to
      implement.  This also allows discarding the clunky 'used' array
      sorting that _dl_sort_maps had to (sometimes) do along the way.

This patch has been tested on x86_64-linux, powerpc64le-linux,
aarch64-linux without regressions (includes the new tests I've added).

[1] https://docs.oracle.com/cd/E19957-01/806-0641/6j9vuquip/index.html
    (section "Initialization and Termination Routines")

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

0 files changed, 0 insertions, 0 deletions