Add further DSO dependency sorting tests

[Carlos O'Donell]

On 12/12/24 6:03 PM, Joseph Myers wrote:
> The current DSO dependency sorting tests are for a limited number of
> specific cases, including some from particular bug reports.

Correct.
 
> Add tests that systematically cover all possible DAGs for an
> executable and the shared libraries it depends on, directly or
> indirectly, up to four objects (an executable and three shared
> libraries).  (For this kind of DAG - ones with a single source vertex
> from which all others are reachable, and an ordering on the edges from
> each vertex - there are 57 DAGs on four vertices, 3399 on five
> vertices and 1026944 on six vertices; see
> https://arxiv.org/pdf/2303.14710 for more details on this enumeration.
> I've tested that the 3399 cases with five vertices do all pass if
> enabled.)

Can we xtest these tests? How long did the five vertices case take to run?

These two questions do not block the acceptance of this patch, but I'm curious
how long it took and what you considered.

> These tests are replicating the sorting logic from the dynamic linker
> (thereby, for example, asserting that it doesn't accidentally change);

This is great, and exactly the kind of cross-checking and V&V that we want here.

> I'm not claiming that the logic in the dynamic linker is in some
> abstract sense optimal.  Note that these tests do illustrate how in
> some cases the two sorting algorithms produce different results for a
> DAG (I think all the existing tests for such differences are ones
> involving cycles, and the motivation for the new algorithm was also to
> improve the handling of cycles):

Correct.

>   tst-dso-ordering-all4-44: a->[bc];{}->[cba]
>   output(glibc.rtld.dynamic_sort=1): c>b>a>{}<a<b<c
>   output(glibc.rtld.dynamic_sort=2): b>c>a>{}<a<c<b

The DFS walk ensures the deepest dependencies are setup and resolved
first and in this case it's a's DT_NEEDED in order.

The {}'s DT_NEEDED order cannot be satisfied at the same time as
a's DT_NEEDED order. The original algorithm in this case *appears*
to honour {}'s DT_NEEDED order.

This looks OK to me.

> They also illustrate that sometimes the sorting algorithms do not
> follow the order in which dependencies are listed in DT_NEEDED even
> though there is a valid topological sort that does follow that, which
> might be counterintuitive considering that the DT_NEEDED ordering is
> followed in the simplest cases:
> 
>   tst-dso-ordering-all4-56: {}->[abc]
>   output: c>b>a>{}<a<b<c

The DFS need not traverse any further and can initialize DT_NEEDED in order.

> shows such a simple case following DT_NEEDED order for destructor
> execution (the reverse of it for constructor execution), but
> 
>   tst-dso-ordering-all4-41: a->[cb];{}->[cba]
>   output: c>b>a>{}<a<b<c

The DFS must traverse to a and setup DT_NEEDED in order, now c>b>
followed by a.
 
> shows that c and b are in the opposite order to what might be expected
> from the simplest case, though there is no dependency requiring such
> an opposite order to be used.

For me this shows that we need a tool like lari that shows this order
to developers so they can know what to expect.

This is a problem of expectation setting balanced against implementation
complexity and application design.

> (I'm not asserting that either of those things is a problem, simply
> observing them as less obvious properties of the sorting algorithms
> shown up by these tests.)

Agreed, this still looks good to me, and I re-reviewed the examples above
by going through the tests and code.

> Tested for x86_64.

LGTM.

Thank you very much for improving the testing here!

Reviewed-by: Carlos O'Donell <carlos@redhat.com>

> diff --git a/elf/Makefile b/elf/Makefile
> index 9172d7306e..a5a25a8370 100644
> --- a/elf/Makefile
> +++ b/elf/Makefile
> @@ -1311,15 +1311,39 @@ $(objpfx)$(1).generated-makefile: $(1)
>  	mv $$@T $$@
>  -include $(objpfx)$(1).generated-makefile
>  endef
> +# Likewise, where the .def file itself is generated.
> +define include_dsosort_tests_objpfx
> +$(objpfx)$(1).generated-makefile: $(objpfx)$(1)
> +	$(PYTHON) $(..)scripts/dso-ordering-test.py \
> +	--description-file $$< --objpfx $(objpfx) --output-makefile $$@T
> +	mv $$@T $$@
> +-include $(objpfx)$(1).generated-makefile
> +endef
>  endif
>  
>  postclean-generated += $(objpfx)/dso-sort-tests-1.generated-makefile \
> -		       $(objpfx)/dso-sort-tests-2.generated-makefile
> +		       $(objpfx)/dso-sort-tests-2.generated-makefile \
> +		       $(objpfx)/dso-sort-tests-all2.generated-makefile \
> +		       $(objpfx)/dso-sort-tests-all3.generated-makefile \
> +		       $(objpfx)/dso-sort-tests-all4.generated-makefile

OK.

>  
>  # Generate from each testcase description file
>  $(eval $(call include_dsosort_tests,dso-sort-tests-1.def))
>  $(eval $(call include_dsosort_tests,dso-sort-tests-2.def))
>  
> +$(objpfx)dso-sort-tests-all2.def: dso-sort-tests-all.py
> +	$(PYTHON) $< 2 > $@
> +
> +$(objpfx)dso-sort-tests-all3.def: dso-sort-tests-all.py
> +	$(PYTHON) $< 3 > $@
> +
> +$(objpfx)dso-sort-tests-all4.def: dso-sort-tests-all.py
> +	$(PYTHON) $< 4 > $@

OK.

> +
> +$(eval $(call include_dsosort_tests_objpfx,dso-sort-tests-all2.def))
> +$(eval $(call include_dsosort_tests_objpfx,dso-sort-tests-all3.def))
> +$(eval $(call include_dsosort_tests_objpfx,dso-sort-tests-all4.def))
> +
>  # BZ15311 is intentionally underlinked.
>  LDFLAGS-tst-bz15311-b.so += -Wl,-z,lazy
>  LDFLAGS-tst-bz15311-c.so += -Wl,-z,lazy
> diff --git a/elf/dso-sort-tests-all.py b/elf/dso-sort-tests-all.py
> new file mode 100755
> index 0000000000..703e7d2edd
> --- /dev/null
> +++ b/elf/dso-sort-tests-all.py
> @@ -0,0 +1,218 @@
> +#!/usr/bin/env python3
> +# Generate all DAGs for dependency ordering of a given number of objects.

OK.

> +# Copyright (C) 2024 Free Software Foundation, Inc.
> +# This file is part of the GNU C Library.
> +#
> +# The GNU C Library is free software; you can redistribute it and/or
> +# modify it under the terms of the GNU Lesser General Public
> +# License as published by the Free Software Foundation; either
> +# version 2.1 of the License, or (at your option) any later version.
> +#
> +# The GNU C Library is distributed in the hope that it will be useful,
> +# but WITHOUT ANY WARRANTY; without even the implied warranty of
> +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +# Lesser General Public License for more details.
> +#
> +# You should have received a copy of the GNU Lesser General Public
> +# License along with the GNU C Library; if not, see
> +# <https://www.gnu.org/licenses/>.
> +
> +import argparse
> +import sys
> +
> +
> +def print_dag(state, dag, postorder, postorder_new):
> +    """Print a DAG in the form used by dso-ordering-test.py."""
> +    out = []
> +    for i in range(len(dag)):
> +        if dag[i]:
> +            if i == len(dag) - 1:
> +                name = '{}'
> +            else:
> +                name = chr(ord('a') + len(dag) - 2 - i)
> +            this_deps = [chr(ord('a') + len(dag) - 2 - j) for j in dag[i]]
> +            this_out = ('[%s]' % (''.join(this_deps))
> +                        if len(this_deps) > 1
> +                        else this_deps[0])
> +            out.append('%s->%s' % (name, this_out))
> +    output_old = (
> +        '%s>{}<%s' %
> +        ('>'.join(chr(ord('a') + i) for i in range(len(dag) - 2, -1, -1)),
> +         '<'.join(chr(ord('a') + i) for i in range(0, len(dag) - 1))))
> +    if postorder == postorder_new:
> +        print('tst-dso-ordering-all%d-%d: %s\n'
> +              'output: %s\n'
> +              % (len(dag), state['num_dags'], ';'.join(out), output_old))
> +    else:
> +        names_new = [chr(ord('a') + len(dag) - 2 - x)
> +                     for x in postorder_new[:-1]]
> +        output_new = '%s>{}<%s' % ('>'.join(names_new),
> +                                   '<'.join(reversed(names_new)))
> +        print('tst-dso-ordering-all%d-%d: %s\n'
> +              'output(glibc.rtld.dynamic_sort=1): %s\n'
> +              'output(glibc.rtld.dynamic_sort=2): %s\n'
> +              % (len(dag), state['num_dags'], ';'.join(out), output_old,
> +                 output_new))
> +    state['num_dags'] += 1

OK. Print it.

> +
> +
> +def gen_postorder_old(dag, postorder):

OK. Wow, what work here to create a matching old-style postorder.

> +    """Generate a postorder traversal of the vertices of the given
> +    DAG, in the particular choice of ordering that corresponds to how
> +    the dynamic linker sorts constructor executions (old algorithm)."""
> +    # First list all the vertices, breadth-first.
> +    postorder.append(len(dag) - 1)
> +    for i in range(len(dag)):
> +        for v in dag[postorder[i]]:
> +            if v not in postorder:
> +                postorder.append(v)
> +    # Now move any vertex with an edge from a later one to just after
> +    # the last vertex with an edge to it (emulating the older dynamic
> +    # linker algorithm).
> +    changed = True
> +    while changed:
> +        changed = False
> +        i = 0
> +        while i < len(dag):
> +            move_past = None
> +            for k in range(len(dag) - 1, i, -1):
> +                if postorder[i] in dag[postorder[k]]:
> +                    move_past = k
> +                    break
> +            if move_past is None:
> +                i += 1
> +            else:
> +                changed = True
> +                postorder[i:k+1] = postorder[i+1:k+1] + [postorder[i]]
> +    # Finally, reverse the list.
> +    postorder.reverse()
> +
> +
> +def gen_postorder_dfs(dag, postorder, v):
> +    """Traverse the dependencies of a vertex as part of generating a
> +    postorder traversal of the given DAG (new algorithm)."""

OK. Lovely and simple :-}

> +    if v in postorder:
> +        return
> +    for d in dag[v]:
> +        gen_postorder_dfs(dag, postorder, d)
> +    postorder.append(v)
> +
> +
> +def gen_postorder_new(dag, postorder):
> +    """Generate a postorder traversal of the vertices of the given
> +    DAG, in the particular choice of ordering that corresponds to how
> +    the dynamic linker sorts constructor executions (new algorithm)."""
> +    # First list all the vertices, breadth-first.
> +    tmp = []
> +    tmp.append(len(dag) - 1)
> +    for i in range(len(dag)):
> +        for v in dag[tmp[i]]:
> +            if v not in tmp:
> +                tmp.append(v)
> +    # Starting at the end of the breadth-first list, do depth-first
> +    # traversal of dependencies to add to the final ordering.
> +    for v in reversed(tmp):
> +        gen_postorder_dfs(dag, postorder, v)

OK. Uses gen_postorder_dfs.

> +
> +
> +def gen_orderings_rec_sub(state, dag, num_done, num_swaps_done):
> +    """Generate possible orderings for the edges out from each vertex
> +    of a DAG and test whether a postorder traversal yields the
> +    vertices in order, where orderings have already been generated for
> +    some number of vertices and some number of initial edges have been
> +    chosen in the ordering for the next vertex."""
> +    if num_swaps_done >= len(dag[num_done]) - 1:
> +        gen_orderings_rec(state, dag, num_done + 1)
> +    else:
> +        for i in range(num_swaps_done, len(dag[num_done])):
> +            ndag = dag
> +            if i != num_swaps_done:
> +                ndag = ndag.copy()
> +                ndag[num_done] = ndag[num_done].copy()
> +                first = ndag[num_done][num_swaps_done]
> +                second = ndag[num_done][i]
> +                ndag[num_done][i] = first
> +                ndag[num_done][num_swaps_done] = second
> +            gen_orderings_rec_sub(state, ndag, num_done, num_swaps_done + 1)
> +
> +def gen_orderings_rec(state, dag, num_done):

OK.

> +    """Generate possible orderings for the edges out from each vertex
> +    of a DAG and test whether a postorder traversal yields the
> +    vertices in order, where orderings have already been generated for
> +    some number of vertices."""
> +    if num_done == len(dag):
> +        postorder = []
> +        gen_postorder_old(dag, postorder)
> +        if postorder == sorted(postorder):
> +            postorder_new = []
> +            gen_postorder_new(dag, postorder_new)
> +            print_dag(state, dag, postorder, postorder_new)
> +    else:
> +        gen_orderings_rec_sub(state, dag, num_done, 0)

OK.

> +
> +
> +def gen_orderings(state, dag):
> +    """Generate possible orderings for the edges out from each vertex
> +    of a DAG and test whether a postorder traversal yields the
> +    vertices in order."""
> +    gen_orderings_rec(state, dag, 0)

OK. We generate orderings every time we reach the maximum number of vertices.
Note: We will visit all possible such DAGs and each time we reach the maximum number
of vertices we emit an ordering.

> +
> +
> +def gen_dags_rec_sub(state, partial_dag, num_vertices, num_done_last):
> +    """Generate DAGs, where a partial DAG for an initial subsequence
> +    of the vertices, and partial information about edges from the last
> +    vertex, are passed in."""

OK.

> +    if num_done_last == len(partial_dag) - 1:
> +        gen_dags_rec(state, partial_dag, num_vertices)
> +    else:
> +        # Recurse with an edge to vertex num_done_last.
> +        new_dag = partial_dag.copy()
> +        new_dag[-1] = new_dag[-1].copy()
> +        new_dag[-1].append(num_done_last)
> +        gen_dags_rec_sub(state, new_dag, num_vertices, num_done_last + 1)

OK. Descend.

> +        # Recurse without an edge to vertex num_done_last, unless this is
> +        # the last vertex and num_done_last is not otherwise reachable.
> +        can_recurse_without = len(partial_dag) < num_vertices
> +        if not can_recurse_without:
> +            for i in range(num_done_last + 1, len(partial_dag) - 1):
> +                if num_done_last in partial_dag[i]:
> +                    can_recurse_without = True
> +                    break
> +        if can_recurse_without:
> +            gen_dags_rec_sub(state, partial_dag, num_vertices,
> +                             num_done_last + 1)
> +
> +
> +def gen_dags_rec(state, partial_dag, num_vertices):
> +    """Generate DAGs, where a partial DAG for an initial subsequence
> +    of the vertices is passed in."""

OK. Initial partial_dag is empty, with number of verticies being the maximum value.
Note: state contains num_dags at 0.

> +    if len(partial_dag) == num_vertices:
> +        gen_orderings(state, partial_dag)

OK. This is the step when gen_dags_rec_sub calls gen_dags_rec with an equal partial_dag
and forms the terminating sequence.

> +    else:
> +        partial_dag = partial_dag.copy()
> +        partial_dag.append([])
> +        gen_dags_rec_sub(state, partial_dag, num_vertices, 0)

OK. Descend initially at 0 done last.

> +
> +
> +def gen_dags(state, num_vertices):
> +    """Generate DAGs with the given number of vertices, last vertex a
> +    distinguished root vertex from which all the others can be
> +    reached, order of edges from each vertex considered significant,
> +    such that a postorder traversal (corresponding to the order in
> +    which DSO dependency constructors are executed) yields the
> +    vertices in order."""

OK. Agreed, order of edges matters (otherwise postorder is not meaningful).
Note: state contains num_dags at 0.

> +    gen_dags_rec(state, [[]], num_vertices)
> +
> +
> +def main(argv):
> +    """The main entry point."""
> +    parser = argparse.ArgumentParser(
> +        description='Generate DAGs to test DSO dependency ordering.')
> +    parser.add_argument('num_objects', help='number of objects in DAG')
> +    print('tunable_option: glibc.rtld.dynamic_sort=1\n'
> +          'tunable_option: glibc.rtld.dynamic_sort=2\n')

OK. Generates test for old and new.

> +    gen_dags({'num_dags': 0}, int(parser.parse_args(argv).num_objects))

OK. Number of objects to permute DAGs.

> +
> +
> +if __name__ == '__main__':
> +    main(sys.argv[1:])
> 


-- 
Cheers,
Carlos.