Re: [PATCH 1/2][RFC] #17645, fix slow DSO sorting behavior in dynamic loader

[Chung-Lin Tang <chunglin_tang@mentor.com>]

[-- Attachment #1: Type: text/plain, Size: 1856 bytes --]

On 2019/7/23 9:21 PM, Florian Weimer wrote:
> Is => intended to cover the case of run-time dependencies added late due
> to lazy binding?
> 
> Currently, those late dependencies have two effects, I think: They keep
> around the referenced libraries longer than before (so that dlclose
> would not remove an object which is still in used solely due to lazy
> binding).  And the ELF destructors are reordered to reflect these added
> run-time dependencies.

Yes, you can test that. The effect of => is to create a caller/callee relation
between objects: 'x=>y' creates fn_x() and fn_y() in those two DSOs,
and fn_x() has a call to fn_y().

Though that's the only immediate effect that => has. To construct a test of
run-time added dependencies related to dlopen/etc. you also need to add those
operations inside the '{}' construct.

All the created DSOs have a constructor/destructor that outputs their single
character name. The generated main() program prints '[]' brackets after
dlopen/dlclose calls to separate out the following constructor/destructor output.
So taken whole, the entire output string should capture all constructor/destructor
activity and ordering behavior.

> Can your test framework test both cases?  What's your position on the
> second effect?  I think it sometimes results in destructors running not
> in the opposite order of constructors, due to the new topological sort.
> (This also happens with the current implementation.)

What I did in the ld.so code patch was add a second pass of sorting that ignores
runtime deps, prioritizing link dependencies; this appears to also be what prior
discussion pointed towards, see more details in that 2nd email with the actual
code patch.

I have attached an updated patch here; fixed some bugs in the script related to
the '@' operator for the main program construct.

Thanks,
Chung-Lin

[-- Attachment #2: dlsort-01-tests-v2.patch --]
[-- Type: text/plain, Size: 24210 bytes --]

diff --git a/elf/Makefile b/elf/Makefile
index a3eefd1..1c4e941 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -383,6 +383,48 @@ tests-special += $(objpfx)order-cmp.out $(objpfx)tst-array1-cmp.out \
 		 $(objpfx)tst-unused-dep-cmp.out
 endif
 
+# DSO sorting tests:
+# The dso-ordering-test.py script generates testcase source files in $(objpfx),
+# and outputs Makefile fragments for use here. However because normal output
+# from $(shell ..) has newlines changed into spaces, we have to save it to a
+# temporary file and then include it. We wrap this entire testcase construction
+# into a function here to make things more convenient.
+define test_dso_ordering
+$(shell $(PYTHON) $(..)scripts/dso-ordering-test.py \
+	$(2) $(1) $(objpfx) > $(objpfx)$(1).tmp-makefile)
+$(shell echo $(3) > $(objpfx)$(1).exp)
+include $(objpfx)$(1).tmp-makefile
+endef
+
+# Individual DSO sorting tests. The test description and expected output for
+# each test is specified directly here. See the source of dso-ordering-test.py
+# for documentation on this.
+# Note that we need to create the $(objpfx) directory here immediately to hold
+# the generated source files and Makefile fragments.
+$(shell mkdir -p $(objpfx))
+$(eval $(call test_dso_ordering,tst-dso-ordering1,'a->b->c','cba{}abc'))
+$(eval $(call test_dso_ordering,tst-dso-ordering2,\
+	'a->b->[cd]->e','edcba{}abcde'))
+$(eval $(call test_dso_ordering,tst-dso-ordering3,\
+	'a->[bc]->[def]->[gh]->i','ihgfedcba{}abcdefghi'))
+$(eval $(call test_dso_ordering,tst-dso-ordering4,\
+	'a->b->[de];a->c->d->e','edcba{}abcde'))
+$(eval $(call test_dso_ordering,tst-dso-ordering5,\
+	'a->[bc]->d;b->c','dcba{}abcd'))
+$(eval $(call test_dso_ordering,tst-dso-ordering6,\
+	'a->[bcde]->f','fedcba{}abcdef'))
+$(eval $(call test_dso_ordering,tst-dso-ordering7,\
+	'a->[bc];b->[cde];e->f','fedcba{}abcdef'))
+$(eval $(call test_dso_ordering,tst-dso-ordering8,\
+	'a->b->c=>a;{}->[ba]','cba{}abc'))
+$(eval $(call test_dso_ordering,tst-dso-ordering9,\
+	'a->b->c->d->e;{}!->[abcde]','edcba{}abcde'))
+
+# From BZ #15311
+$(eval $(call test_dso_ordering,tst-bz15311,\
+'{+a;+e;+f;+g;+d;%d;-d;-g;-f;-e;-a};a->b->c->d;d=>[ba];c=>a;b=>e=>a;c=>f=>b;d=>g=>c',\
+'{+a[dcba];+e[e];+f[f];+g[g];+d[];<d<b<e<a>>><a><g<c<a><f<b<e<a>>>>>>>;-d[];-g[];-f[];-e[];-a[gfabcde];}'))
+
 check-abi: $(objpfx)check-abi-ld.out
 tests-special += $(objpfx)check-abi-ld.out
 update-abi: update-abi-ld
diff --git a/scripts/dso-ordering-test.py b/scripts/dso-ordering-test.py
new file mode 100644
index 0000000..a494ba2
--- /dev/null
+++ b/scripts/dso-ordering-test.py
@@ -0,0 +1,556 @@
+#!/usr/bin/python3
+# Generate testcase files and Makefile fragments for DSO sorting test
+# Copyright (C) 2019 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
+# <http://www.gnu.org/licenses/>.
+
+"""Generate testcase files and Makefile fragments for DSO sorting test
+
+This script takes a semicolon-separated description string, and generates
+a testcase, including main program and associated modules, and Makefile
+fragments for including into elf/Makefile.
+
+This is intended to speed up complex dynamic linker testcase construction,
+therefore features are largely mechanical in nature; inconsistencies or
+errors may occur if input case was itself erroronous or have
+unforeseen interactions.
+
+On the description language used, as an example description string:
+
+  a->b!->[cdef];c=>g=>h;{+c;%c;-c}->a
+
+Each single alphabet character represents a shared object module (currently
+[a-zA-Z0-9] are allowed, case-sensitive)
+All such shared objects have a constructor/destructor generated for them
+that emits its single character name by putchar().
+
+The -> operator specifies a link time dependency, these can be chained for
+convenience (e.g. a->b->c->d).
+
+The => operator creates a call-reference, e.g. for a=>b, an fn_a() function
+is created inside module 'a', which calls fn_b() in module 'b'.
+These module functions emit '<name>' output in nested form,
+e.g. a=>b emits '<a<b>>'
+
+Square brackets [] in the description specifies multiple objects;
+e.g. a->[bcd]->e is equivalent to a->b->e;a->c->e;a->d->e
+
+A {} construct specifies the main test program, and its link dependencies
+are also specified using ->. Inside {}, a few ;-seperated constructs are
+allowed:
+         +a   Loads module a using dlopen(RTLD_LAZY|RTLD_GLOBAL)
+         :a   Loads module a using dlopen(RTLD_LAZY)
+         %a   Use dlsym() to load and call fn_a()
+         @a   Calls fn_a() directly.
+         -a   Unloads module a using dlclose()
+
+The generated main program outputs '{' '}' with all output from above
+constructs in between. The other output before/after {} are the ordered
+constructor/destructor output.
+
+If no {} construct is present, a default empty main program is linked
+against all objects which have no dependency linked to it. e.g. for
+'[ab]->c;d->e', the default main program is equivalent to '{}->[abd]'
+
+The '!' operator after object names turns on permutation of its
+dependencies, e.g. while a->[bcd] only generates one set of objects,
+with 'a.so' built with a link line of "b.so c.so d.so", for a!->[bcd]
+permutations of a's dependencies creates multiple testcases with
+different link line orders: "b.so c.so d.so", "c.so b.so d.so",
+"b.so d.so c.so", etc. Note that for a <test-name> specified on
+the script command-line, multiple <test-name_1>, <test-name_2>, etc.
+tests will be generated (e.g. for a!->[bc]!->[de], eight tests with
+different link orders for a, b, and c will be generated)
+
+"""
+
+import re
+import os
+import subprocess
+import argparse
+from collections import OrderedDict
+import itertools
+
+# BUILD_GCC is only used under the --build option,
+# which builds the generated testcase, including DSOs using BUILD_GCC.
+# Mainly for testing purposes, especially debugging of this script,
+# and can be changed here to another toolchain path if needed.
+build_gcc = "gcc"
+
+parser = argparse.ArgumentParser()
+parser.add_argument("description",
+                    help="Description string of DSO dependency test to be "
+                    "generated (see script source for documentation of "
+                    "description language)")
+parser.add_argument("test_name", help="Identifier for testcase being "
+                    "generated")
+parser.add_argument("objpfx",
+                    help="Path to place generated files, defaults to "
+                    "current directory if none specified",
+                    nargs="?", default="./")
+parser.add_argument("--build", help="After C testcase generated, build it "
+                    "using gcc (for manual testing purposes)",
+                    action="store_true")
+parser.add_argument("--debug-output", help="Prints some internal data "
+                    "structures; used for debugging of this script",
+                    action="store_true")
+cmdlineargs = parser.parse_args()
+base_test_name = cmdlineargs.test_name
+test_name = cmdlineargs.test_name
+objpfx = cmdlineargs.objpfx
+
+obj_deps = OrderedDict()
+obj_callrefs = OrderedDict()
+
+all_objs = []
+curr_objs = []
+
+obj_dep_permutations = OrderedDict()
+
+# Add 'object -> [object, object, ...]' relations to CURR_MAP
+def add_deps (src_objs, dst_objs, curr_map):
+    for src in src_objs:
+        for dst in dst_objs:
+            if not src in curr_map:
+                curr_map[src] = []
+            if not dst in curr_map[src]:
+                curr_map[src].append (dst)
+
+# For inside the {} construct
+main_program = []
+main_program_needs_ldl = False
+main_program_default_deps = True
+def process_main_program (mainprog_str):
+    global main_program
+    global main_program_needs_ldl
+    global main_program_default_deps
+    if mainprog_str:
+        main_program = mainprog_str.split (';')
+    for s in main_program:
+        m = re.match (r"^([+\-%:@])([0-9a-zA-Z]+)$", s)
+        if not m: print ("'%s'" % (s))
+        assert (m)
+        # Determined the main program needs libdl
+        main_program_needs_ldl = True
+        if len(m.group(2)) > 1:
+            print ("Error: only single character object names allowed, "
+                   + "'%s' is invalid" % (m.group(1)))
+            exit -1
+        obj = m.group(2)
+        if not obj in all_objs:
+            all_objs.append (obj)
+        if m.group(1) == '%' or m.group(1) == '@':
+            add_deps (['#'], [obj], obj_callrefs)
+    # We have a main program specified, turn this off
+    main_program_default_deps = False
+
+# Lexer for tokens
+tokenspec = [ ("OBJ",      r"([0-9a-zA-Z]+)"),
+              ("DEP",      r"->"),
+              ("CALLREF",  r"=>"),
+              ("OBJSET",   r"\[([0-9a-zA-Z]+)\]"),
+              ("PROG",     r"{([0-9a-zA-Z;+:\-%@]*)}"),
+              ("PERMUTE",  r"!"),
+              ("SEMICOL",  r";"),
+              ("ERROR",    r".") ]
+tok_re = '|'.join('(?P<%s>%s)' % pair for pair in tokenspec)
+
+# State used when parsing dependencies
+in_dep = False
+in_callref = False
+def clear_dep_state ():
+    global in_dep, in_callref
+    in_dep = in_callref = False
+
+# Main parser
+for m in re.finditer(tok_re, cmdlineargs.description):
+    kind = m.lastgroup
+    value = m.group ()
+    if kind == "OBJ":
+        if len (value) > 1:
+            print ("Error: only single character object names allowed, "
+                   + "'%s' is invalid" % (value))
+            exit (-1)
+        if in_dep:
+            add_deps (curr_objs, [value], obj_deps)
+        elif in_callref:
+            add_deps (curr_objs, [value], obj_callrefs)
+        clear_dep_state ()
+        curr_objs = [value]
+        if not value in all_objs:
+            all_objs.append (value)
+
+    elif kind == "OBJSET":
+        objset = value[1:len(value)-1]
+        if in_dep:
+            add_deps (curr_objs, list (objset), obj_deps)
+        elif in_callref:
+            add_deps (curr_objs, list (objset), obj_callrefs)
+        clear_dep_state ()
+        curr_objs = list (objset)
+        for o in list (objset):
+            if not o in all_objs:
+                all_objs.append (o)
+
+    elif kind == "PERMUTE":
+        if in_dep or in_callref:
+            print ("Error: syntax error, permute operation invalid here")
+            exit -1
+        if not curr_objs:
+            print ("Error: syntax error, no objects to permute here")
+            exit -1
+        for obj in curr_objs:
+            if not obj in obj_dep_permutations:
+                # Signal this object has permutated dependencies
+                obj_dep_permutations[obj] = []
+
+    elif kind == "PROG":
+        if main_program:
+            print ("Error: cannot have more than one main program")
+            exit (-1)
+        if in_dep:
+            print ("Error: objects cannot have dependency on main program")
+            exit (-1)
+        if in_callref:
+            add_deps (curr_objs, ["#"], obj_callrefs)
+        process_main_program (value[1:len(value)-1])
+        clear_dep_state ()
+        curr_objs = ["#"]
+
+    elif kind == "DEP":
+        if in_dep or in_callref:
+            print ("Error: syntax error, multiple contiguous ->,=> operations")
+            exit -1
+        in_dep = True
+
+    elif kind == "CALLREF":
+        if in_dep or in_callref:
+            print ("Error: syntax error, multiple contiguous ->,=> operations")
+            exit -1
+        in_callref = True
+        
+    elif kind == "SEMICOL":
+        curr_objs = []
+        clear_dep_state ()
+
+    else:
+        print ("Error: unknown token '%s'" % (value))
+        exit (-1)
+
+def find_objs_not_depended_on ():
+    global all_objs, obj_deps
+    objs_not_depended_on = []
+    for obj in all_objs:
+        skip = False
+        for r in obj_deps.items():
+            if obj in r[1]:
+                skip = True
+                break
+        if not skip:
+            objs_not_depended_on.append (obj)
+    return objs_not_depended_on
+        
+# If no main program was specified in dependency description, make a
+# default main program with deps pointing to all DSOs which are not
+# depended by another DSO.
+if main_program_default_deps:
+    main_deps = find_objs_not_depended_on ()
+    # main_deps = []
+    # for o in all_objs:
+    #     skip = False
+    #     for r in obj_deps.items():
+    #         if o in r[1]:
+    #             skip = True
+    #             break
+    #     if skip:
+    #         continue
+    #     main_deps.append (o)
+    add_deps (["#"], main_deps, obj_deps)    
+        
+# Debug output
+if cmdlineargs.debug_output:
+    print ("All objects: %s" % (all_objs))
+    print ("--- Static link dependencies ---")
+    for r in obj_deps.items():
+        print ("%s -> %s" % (r[0], r[1]))
+    print ("--- Objects whose dependencies are to be permutated ---")
+    for r in obj_dep_permutations.items():
+        print ("%s" % (r[0]))
+    #print (obj_dep_permutations)
+    print ("--- Call reference dependencies ---")
+    for r in obj_callrefs.items():
+        print ("%s => %s" % (r[0], r[1]))
+    print ("--- main program ---")
+    print (main_program)
+
+# Main testcase processing routine, does Makefile fragment generation,
+# testcase source generation, and if --build specified builds testcase.
+def process_testcase (test_name):
+    global objpfx, all_objs, obj_deps, obj_callrefs
+    global base_test_name, main_program, main_program_needs_ldl
+
+    # Print out needed Makefile fragments for use in glibc/elf/Makefile.
+    #if makefile:
+    print ("ifeq (yes,$(build-shared))")
+    t = ""
+    for o in all_objs:
+        t += " " + test_name + "-" + o
+    print ("modules-names +=%s" % (t))
+    print ("tests += %s" % (test_name))
+
+    # Print direct link dependencies for each DSO
+    for obj in all_objs:
+        if obj in obj_deps:
+            dso = test_name + "-" + obj + ".so"
+            depstr = ""
+            for dep in obj_deps[obj]:
+                depstr += " $(objpfx)" + test_name + "-" + dep + ".so"
+            print ("$(objpfx)%s:%s" % (dso, depstr))
+
+    # Print LDFLAGS-* and *-no-z-defs
+    for o in all_objs:
+        dso = test_name + "-" + o + ".so"
+        print ("LDFLAGS-%s = $(no-as-needed)" % (dso))
+        if o in obj_callrefs:
+            print ("%s-no-z-defs = yes" % (dso))
+
+    # Print dependencies for main test program
+    depstr = ""
+    if '#' in obj_deps:
+        for o in obj_deps['#']:
+            depstr += " $(objpfx)" + test_name + "-" + o + ".so"
+    if main_program_needs_ldl:
+        depstr += " $(libdl)"
+    print ("$(objpfx)%s:%s" % (test_name, depstr))
+    print ("LDFLAGS-%s = $(no-as-needed)" % (test_name))
+
+    not_depended_objs = find_objs_not_depended_on ()
+    if not_depended_objs:
+        depstr = ""
+        for dep in not_depended_objs:
+            depstr += " $(objpfx)" + test_name + "-" + dep + ".so"
+        print ("$(objpfx)%s.out:%s" % (test_name, depstr))
+    
+    # Note this is compared with the "base" <test_name>.exp, not
+    # <test_name>_<N> with permutation index
+    print ("$(objpfx)%s-cmp.out: $(objpfx)%s.exp $(objpfx)%s.out"
+           % (test_name, base_test_name, test_name))
+    print ("\tdiff -wu $^ > $@; $(evaluate-test)")
+    print ("endif")
+    print ("ifeq ($(run-built-tests),yes)")
+    print ("tests-special += $(objpfx)%s-cmp.out" % (test_name))
+    print ("endif")
+
+    # Generate C files according to dependency and calling relations from
+    # description string.
+    for obj in all_objs:
+        src_name = test_name + "-" + obj + ".c"
+        f = open (objpfx + src_name, "w")
+        if obj in obj_callrefs:
+            called_objs = obj_callrefs[obj]
+            for callee in called_objs:
+                f.write ("extern void fn_%s (void);\n" % (callee))
+        f.write ("extern int putchar(int);\n")
+        f.write ("static void __attribute__((constructor)) " +
+                 "init(void){putchar('%s');}\n" % (obj))
+        f.write ("static void __attribute__((destructor)) " +
+                 "fini(void){putchar('%s');}\n" % (obj))
+        if obj in obj_callrefs:
+            called_objs = obj_callrefs[obj]
+            f.write ("void fn_%s (void) {\n" % (obj))
+            f.write ("  putchar ('<');\n");
+            f.write ("  putchar ('%s');\n" % (obj));
+            for callee in called_objs:
+                f.write ("  fn_%s ();\n" % (callee))
+            f.write ("  putchar ('>');\n");
+            f.write ("}\n")
+        else:
+            for callref in obj_callrefs.items():
+                if obj in callref[1]:
+                    f.write ("void fn_%s (void) {\n" % (obj))
+                    f.write ("  putchar ('<');\n");
+                    f.write ("  putchar ('%s');\n" % (obj));
+                    f.write ("  putchar ('>');\n");
+                    f.write ("}\n")
+                    break
+        f.close ()
+
+    # Open C file for writing
+    f = open (objpfx + test_name + ".c", "w")
+
+    # if there are some operations in main(), it means we need -ldl
+    if main_program_needs_ldl:
+        f.write ("#include <dlfcn.h>\n")
+    f.write ("#include <stdio.h>\n")
+    f.write ("#include <stdlib.h>\n")
+    for s in main_program:
+        if s[0] == '@':
+            f.write ("extern void fn_%s (void);\n" % (s[1]));
+    f.write ("int main (void) {\n")
+    f.write ("  putchar('{');\n")
+
+    # Helper routine for sanity check code
+    def put_fail_check (fail_cond, action_desc):
+        f.write ('  if (%s) { printf ("\\n%s failed: %%s\\n", '
+                 'dlerror ()); exit (1);}\n' % (fail_cond, action_desc))
+    i = 0
+    while i < len(main_program):
+        s = main_program[i]
+        obj = s[len(s)-1]
+        dso = test_name + "-" + obj
+        if s[0] == '+' or s[0] == ':':
+            if s[0] == '+':
+                dlopen_flags = "RTLD_LAZY|RTLD_GLOBAL"
+                f.write ("  putchar('+');\n");
+            else:
+                dlopen_flags = "RTLD_LAZY"
+                f.write ("  putchar(':');\n");
+            f.write ("  putchar('%s');\n" % (obj));
+            f.write ("  putchar('[');\n");
+            f.write ('  void *%s = dlopen ("%s.so", %s);\n'
+                     % (obj, dso, dlopen_flags))
+            put_fail_check ("!%s" % (obj),
+                            "%s.so dlopen" % (dso))
+            f.write ("  putchar(']');\n");
+        elif s[0] == '-':
+            f.write ("  putchar('-');\n");
+            f.write ("  putchar('%s');\n" % (obj));
+            f.write ("  putchar('[');\n");
+            put_fail_check ("dlclose (%s) != 0" % (obj),
+                            "%s.so dlclose" % (dso))
+            f.write ("  putchar(']');\n");
+        elif s[0] == '%':
+            f.write ('  void (*fn_%s)(void) = dlsym (%s, "fn_%s");\n'
+                     % (obj, obj, obj))
+            put_fail_check ("!fn_%s" % (obj),
+                            "dlsym(fn_%s) from %s.so" % (obj, dso))
+            f.write ("  fn_%s ();\n" % (obj))
+        elif s[0] == '@':
+            f.write ("  fn_%s ();\n" % (obj))
+        f.write ("  putchar(';');\n");
+        i += 1
+    f.write ("  putchar('}');\n")
+    f.write ("  return 0;\n")
+    f.write ("}\n")
+    f.close ()
+
+    # Helper routine to run a shell command, for running GCC below
+    def run_cmd (args):
+        if cmdlineargs.debug_output:
+            print (str.join (' ', args))
+        p = subprocess.Popen (args)
+        p.wait ()
+        if p.returncode != 0:
+            print ("Error running: %s" % (str.join (' ', args)))
+            exit -1
+
+    # Depth-first traversal, executing FN(OBJ) in post-order
+    obj_visited = {}
+    def dfs (obj, fn):
+        if obj in obj_visited:
+            return
+        obj_visited[obj] = True
+        if obj in obj_deps:
+            for dep in obj_deps[obj]:
+                dfs (dep, fn)
+        fn (obj)
+
+    # Function to create <test_name>-<obj>.so
+    def build_dso (obj):
+        obj_name = test_name + "-" + obj + ".os"
+        dso_name = test_name + "-" + obj + ".so"
+        deps = []
+        if obj in obj_deps:
+            deps = obj_deps[obj]
+        dso_deps = map (lambda d: objpfx + test_name + "-" + d + ".so", deps)
+        cmd = ([build_gcc, "-shared", "-o", objpfx + dso_name,
+                objpfx + obj_name, "-Wl,--no-as-needed"] + list(dso_deps))
+        run_cmd (cmd)
+
+    # --build option processing: build generated sources using 'build_gcc'
+    if cmdlineargs.build:
+        # Compile individual .os files
+        for obj in all_objs:
+            src_name = test_name + "-" + obj + ".c"
+            obj_name = test_name + "-" + obj + ".os"
+            run_cmd ([build_gcc, "-c", "-fPIC", objpfx + src_name,
+                      "-o", objpfx + obj_name])
+
+        # Build all DSOs, this needs to be in topological dependency order,
+        # or link will fail
+        for obj in all_objs:
+            dfs (obj, build_dso)
+
+        # Build main program
+        deps = []
+        if '#' in obj_deps:
+            deps = obj_deps['#']
+        main_deps = map (lambda d: objpfx + test_name + "-" + d + ".so", deps)
+        cmd = ([build_gcc, "-Wl,--no-as-needed", "-o", objpfx + test_name,
+                objpfx + test_name + ".c", "-L%s" % (os.getcwd ()),
+                "-Wl,-rpath-link=%s" % (os.getcwd ())]
+               + list (main_deps))
+        if main_program_needs_ldl:
+            cmd += ["-ldl"]
+        run_cmd (cmd)
+
+# Check if we need to enumerate permutations of dependencies
+need_permutation_processing = False       
+if obj_dep_permutations:
+    # Adjust obj_dep_permutations into map of object -> dependency permutations
+    for r in obj_dep_permutations.items():
+        obj = r[0]
+        if obj in obj_deps and len(obj_deps[obj]) > 1:
+            deps = obj_deps[obj]
+            obj_dep_permutations[obj] = list (itertools.permutations (deps))
+            need_permutation_processing = True
+
+test_subindex = 1
+curr_perms = []
+def enum_permutations (perm_list):
+    global test_name, obj_deps, test_subindex, curr_perms
+    if len(perm_list) >= 1:
+        curr = perm_list[0]
+        obj = curr[0]
+        perms = curr[1]
+        if not perms:
+            # This may be an empty list if no multiple dependencies to permute
+            # were found, skip to next in this case
+            enum_permutations (perm_list[1:])
+        else:
+            for deps in perms:
+                obj_deps[obj] = deps
+                permstr = "" if obj == "#" else obj + "_"
+                permstr += str.join ('', deps)
+                curr_perms.append (permstr) 
+                enum_permutations (perm_list[1:])
+                curr_perms = curr_perms[0:len(curr_perms)-1]
+    else:
+        # obj_deps is now instantiated with one dependency order permutation
+        # (across all objects that have multiple permutations)
+        # Now process a testcase
+        #if not os.path.exists (objpfx + base_test_name+ "-permutations/"):
+        #    os.mkdir (objpfx + base_test_name+ "-permutations/")
+        process_testcase (base_test_name + "_" + str (test_subindex)
+                          + "-" + str.join ('-', curr_perms))
+        test_subindex += 1
+
+if need_permutation_processing:
+    enum_permutations (list (obj_dep_permutations.items()))
+else:
+    # We have no permutations to enumerate, just process testcase normally
+    process_testcase (test_name)
+