From patchwork Thu Jan 21 18:12:03 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Chung-Lin Tang X-Patchwork-Id: 41785 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 299423887029; Thu, 21 Jan 2021 18:12:28 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from esa2.mentor.iphmx.com (esa2.mentor.iphmx.com [68.232.141.98]) by sourceware.org (Postfix) with ESMTPS id 9B299386188A for ; Thu, 21 Jan 2021 18:12:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 9B299386188A Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=codesourcery.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=ChungLin_Tang@mentor.com IronPort-SDR: ub+MSUGwn02HDj5QApXBBrbUQMkSj4M4B6dB2UL/RAenv9VV2nobKYo67nSP38ORINZKjFKZoj +7HRCX0RzzQV0ipP+QiRLW/mMRA+kfri7erlVWw4SCUfnEsDN70GLSFZoN/S9YqzfodQPisL2A PX5jPYol40fAOLW3HCHo1JcmRGwmoEk13qGS4gpZ8FFEgJiHnrLj2bDpYYztbm2qyGexuK2k6Z z1BDECNFwfELehBCI6uu9tzyuUE3RdDS5qft04ybVyxXodor9v5tYXOZuEckKfIdXkBosmcvSX GOE= X-IronPort-AV: E=Sophos;i="5.79,364,1602576000"; d="scan'208";a="57296846" Received: from orw-gwy-01-in.mentorg.com ([192.94.38.165]) by esa2.mentor.iphmx.com with ESMTP; 21 Jan 2021 10:12:16 -0800 IronPort-SDR: /qeyGqxmpcfmTih693aF3kR7wFYIFr6B4k3xk4qwXoecQK8z7uq1lkpWSyg+25ARjsFlIHZOUt gDMrzhYCAZ1rNBjzKT1EUfM52ZMQaNN1Aq9d21H7inYXCGsgYjIlltpQn9v/aejP5Are5TAlmD CPxCRWJcFpvPyyvFfe+SbpDta4S7qiNN3nbiBYMfaYEJAS6/zXMzAfUiCeJ9eRQ7KuVlviBSgh yzCb7ouOkOzxOV5VLs47bMAdpfjy63vM0XXGHUgCk7sauCO2OOImLbdSVm7qyk9fjK2wl0GBoo TSk= Subject: [PATCH v5 1/2] BZ #17645, fix slow DSO sorting behavior in dynamic loader -- Testing infrastructure To: Florian Weimer References: <91bd3ea0-7a03-df54-ea98-ef0f6d1304f1@codesourcery.com> <87r1mrmc34.fsf@oldenburg2.str.redhat.com> From: Chung-Lin Tang Message-ID: Date: Fri, 22 Jan 2021 02:12:03 +0800 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:78.0) Gecko/20100101 Thunderbird/78.6.1 MIME-Version: 1.0 In-Reply-To: <87r1mrmc34.fsf@oldenburg2.str.redhat.com> Content-Language: en-US X-ClientProxiedBy: SVR-ORW-MBX-06.mgc.mentorg.com (147.34.90.206) To svr-orw-mbx-04.mgc.mentorg.com (147.34.90.204) X-Spam-Status: No, score=-8.1 required=5.0 tests=BAYES_00, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, KAM_SHORT, RCVD_IN_DNSWL_NONE, SCC_10_SHORT_WORD_LINES, SCC_20_SHORT_WORD_LINES, SCC_35_SHORT_WORD_LINES, SCC_5_SHORT_WORD_LINES, SPF_HELO_PASS, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: GNU C Library Errors-To: libc-alpha-bounces@sourceware.org Sender: "Libc-alpha" Hi Florian, thanks for the review. Response to various points below, and updated patch attached. On 2021/1/12 4:51 AM, Florian Weimer wrote: > * Chung-Lin Tang: >> +# DSO sorting tests: >> +# The dso-ordering-test.py script generates testcase source files in $(objpfx), >> +# creating a $(objpfx)-dir for each testcase, and creates a >> +# Makefile fragment to be included. >> +define include_dsosort_tests >> +$(objpfx)$(1).tmp-makefile: $(1) >> + $(PYTHON) $(..)scripts/dso-ordering-test.py \ >> + --description-file $$< --objpfx $(objpfx) --output-makefile $$@ >> +include $(objpfx)$(1).tmp-makefile >> +endef > > Maybe use a different suffix? .mk? > > The file isn't really temporary, so .tmp-makefile seems misleading. I've changed it to ".generated-makefile" About the use of $(eval ...), I didn't find another way to allow wrapping the generation + include of the makefile fragment into a function, so glad that eval is not completely banned... >> +# This function can be used to define a single DSO sorting test, completely >> +# here in the Makefile, for example: >> +# $(eval $(call single_dsosort_test,testcase-name,'a->b->c','c>b>a>{}> +# Currently all tests are defined in description files, and this function is >> +# not utilized, but kept here for possible conveniences. >> +define single_dsosort_test >> +$(objpfx)$(1).tmp-makefile: >> + $(PYTHON) $(..)scripts/dso-ordering-test.py --objpfx $(objpfx) \ >> + $(2) $(1) $(3) --output-makefile $$@ >> +include $(objpfx)$(1).tmp-makefile >> +endef > > I suggest not to include this because it's unused. Okay, removed. >> diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def >> new file mode 100644 >> index 0000000000..51337ec3c7 >> --- /dev/null >> +++ b/elf/dso-sort-tests-1.def >> @@ -0,0 +1,61 @@ >> +# DSO sorting test descriptions. >> +# This file is to be processed by ../scripts/dso-ordering-test.py, see usage >> +# in elf/Makefile for how it is executed. > > As far as I can tell, this is a reasonable collection of tests. > > What's missing is sorting behavior if the main program has a soname. > This seems relevant given that the actual patch seems to change behavior > there. Currently, the expectation is that if the main program has a > soname, it is always initialized last. It does not participate in the > dependency sort. This can change with new algorithm and a DT_NEEDED on > the main program. Hmm, I guess there is indeed some concern here. I'll think more about this before responding to your review of the algorithm parts. OTOH, does the ELF specification dictate in a "hard" sense that the main program is always at the start of the resulting sort, or is it unspecified? > Also not included is a symbol interposition test. I think this could be > achieved with a per-DSO marker that triggers the definition of a global, > exported function. This function would then print the DSO name or main > program name into the output. Some care needs to be taken (by the test > author) to define the function only in some of the DSOs, to get the > desired interposition behavior. But that I think it is not critical to > have this functionality included from the start. That is kind of starting to wade out of the DSO sorting behavior testing goal that this tool was originally designed to do, I think, but could be interesting to expand to. >> +# We test both dynamic loader sorting algorithms >> +tunable_option: glibc.rtld.dynamic_sort=1 >> +tunable_option: glibc.rtld.dynamic_sort=2 > > Given that these tunables do not exist yet, should they be added with > the second patch? This will also avoid the XFAIL. I've tried to make the two patches not textually dependent on one another. I also think they'll probably be approved together, so I'll leave this as is right now. >> diff --git a/scripts/dso-ordering-test.py b/scripts/dso-ordering-test.py >> new file mode 100644 >> index 0000000000..7f0515312c >> --- /dev/null >> +++ b/scripts/dso-ordering-test.py > > Would you please reformat to a line length of 79? And we generally do > not follow the space-before-paren rule for Python source code, e.g., > “exit(1)”, not “exit (1)”. Done. > >> +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 specified on >> +the script command-line, multiple , , 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) > > Is it worh noting that it's necessary to specify the ordering of the > permuted DSOs separately, so that a unique output is generated? I am not entirely sure what you mean here? Do you mean to warn "be careful that all permutations do have the same single expected output"? >> +# Lexer for tokens >> +tokenspec = [ ("OBJ", r"([0-9a-zA-Z]+)"), >> + ("DEP", r"->"), >> + ("CALLREF", r"=>"), >> + ("OBJSET", r"\[([0-9a-zA-Z]+)\]"), > > Should 0-9 be dropped here, given that the DSO names must be single > letters? The script now allows longer strings for DSO names now, e.g. see the test case in elf/dso-sort-tests-2.def. >> +# Main line parser of description language >> +def parse_description_string (t, descr_str): > >> + else: >> + print ("Error: unknown token '%s'" % (value)) >> + exit (-1) > > Would it be possible to include line number and character offset > information here? I think it would help the test author to fix syntax > errors. I've added line number reporting, but character column information is a bit too complicated to implement quickly (at least with my current Python-fu), so please bear with that. >> +def process_testcase (t): >> + global objpfx >> + assert t.test_name >> + >> + base_test_name = t.test_name > > Should the .def file name be included in the test name? This avoid > accidental collisions between different .def files. We place all files related to a testcase inside $(common-objpfx)/elf/-dir/ subdirectory, the .def file name isn't important at this level. >> + if "#" in t.deps: >> + deps = t.deps["#"] >> + if '*' in deps: >> + t.deps["#"].remove ('*') >> + t.add_deps (["#"], non_dep_tgt_objs) > > As far as I understand it, '#' is a synthetic marker. Would it make > sense to use a global variable for it, or put some comment somewhere to > explain its purpose? I've added some related comments around the 'process_main_program' routine. >> + # A circular dependency is satisfied by making a fake DSO >> + # tagged with the correct SONAME >> + depstr = (" $(objpfx)" + test_subdir + "/" >> + + test_name + "-" + dep + ".FAKE.so") > > I think elsewhere we call them “linkmods”. But perhaps that's just me. So I'll leave it like that for now. This is something internal that can be changed any time anyways. >> + makefile.write \ >> + ("$(objpfx)%s.out: $(objpfx)%s/%s.sh%s $(common-objpfx)support/test-run-command\n" >> + % (t.test_name, test_subdir, t.test_name, >> + expected_output_files)) >> + makefile.write ("\t$(SHELL) $< $(common-objpfx) '$(test-wrapper-env)' " >> + "'$(run-program-env)' > $@; $(evaluate-test)\n") > > I've already mentioned that test-run-command does not link on some > targets. I tried to fix it up, but I couldn't get it to build even on > some Linux targets (link failures related to unwinding). I think we > should revisit the timeout handling separately. Or perhaps depend on > the timeout tool from coreutils. Probably the most important change in this v5 update: I've discovered that linking elf/static-stubs.o is enough for test-run-command to link and work; in fact it seems we don't even need any thread library here. I've added a support/Depend file with "elf" in it. The attached version is v5 of the Testing infrastructure parts, with the above mentioned changes. I'll respond to the Algorithm review in a day or two. Thanks, Chung-Lin diff --git a/elf/Makefile b/elf/Makefile index 5e7f938e2d..1cfc22b5d1 100644 --- a/elf/Makefile +++ b/elf/Makefile @@ -450,6 +450,21 @@ 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), +# creating a $(objpfx)-dir for each testcase, and creates a +# Makefile fragment to be included. +define include_dsosort_tests +$(objpfx)$(1).generated-makefile: $(1) + $(PYTHON) $(..)scripts/dso-ordering-test.py \ + --description-file $$< --objpfx $(objpfx) --output-makefile $$@ +include $(objpfx)$(1).generated-makefile +endef + +# 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)) + check-abi: $(objpfx)check-abi-ld.out tests-special += $(objpfx)check-abi-ld.out update-abi: update-abi-ld diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def new file mode 100644 index 0000000000..51337ec3c7 --- /dev/null +++ b/elf/dso-sort-tests-1.def @@ -0,0 +1,61 @@ +# DSO sorting test descriptions. +# This file is to be processed by ../scripts/dso-ordering-test.py, see usage +# in elf/Makefile for how it is executed. + +# We test both dynamic loader sorting algorithms +tunable_option: glibc.rtld.dynamic_sort=1 +tunable_option: glibc.rtld.dynamic_sort=2 + +# Sequence of single dependencies with no cycles. +tst-dso-ordering1: a->b->c +output: c>b>a>{}b->[cd]->e +output: e>d>c>b>a>{}[bc]->[def]->[gh]->i +output: i>h>g>f>e>d>c>b>a>{}b->[de];a->c->d->e +output: e>d>c>b>a>{}c cross link is respected correctly +tst-dso-ordering5: a!->[bc]->d;b->c +output: d>c>b>a>{}[bcde]->f +output: f>e>d>c>b>a>{}[bc];b->[cde];e->f +output: f>e>d>c>b>a>{}b->c=>a;{}->[ba] +output: c>b>a>{}b->c->d->e;{}!->[abcde] +output: e>d>c>b>a>{}b->c->d order). +# The older dynamic_sort=1 algorithm does not achieve this, while the DFS-based +# dynamic_sort=2 algorithm does, although it is still arguable whether going +# beyond spec to do this is the right thing to do. +# The below expected outputs are what the two algorithms currently produce +# respectively, for regression testing purposes. +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 +output(glibc.rtld.dynamic_sort=1): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[A101 +{}->* +A101->(B101 B163 B122 B181) +A102->(B102 B140 B199 B158) +A103->(B103 B117 B176 B135) +A104->(B104 B194 B153 B112) +A105->(B105 B171 B130 B189) +A106->(B106 B148 B107 B166) +A107->(B107 B125 B184 B143) +A108->(B108 B102 B161 B120) +A109->(B109 B179 B138 B197) +A110->(B110 B156 B115 B174) +A111->(B111 B133 B192 B151) +A112->(B112 B110 B169 B128) +A113->(B113 B187 B146 B105) +A114->(B114 B164 B123 B182) +A115->(B115 B141 B200 B159) +A116->(B116 B118 B177 B136) +A117->(B117 B195 B154 B113) +A118->(B118 B172 B131 B190) +A119->(B119 B149 B108 B167) +A120->(B120 B126 B185 B144) +A121->(B121 B103 B162) +A122->(B122 B180 B139 B198) +A123->(B123 B157 B116 B175) +A124->(B124 B134 B193 B152) +A125->(B125 B111 B170 B129) +A126->(B126 B188 B147 B106) +A127->(B127 B165 B124 B183) +A128->(B128 B142 B101 B160) +A129->(B129 B119 B178 B137) +A130->(B130 B196 B155 B114) +A131->(B131 B173 B132 B191) +A132->(B132 B150 B109 B168) +A133->(B133 B127 B186 B145) +A134->(B134 B104 B163 B122) +A135->(B135 B181 B140 B199) +A136->(B136 B158 B117 B176) +A137->(B137 B135 B194 B153) +A138->(B138 B112 B171 B130) +A139->(B139 B189 B148 B107) +A140->(B140 B166 B125 B184) +A141->(B141 B143 B102 B161) +A142->(B142 B120 B179 B138) +A143->(B143 B197 B156 B115) +A144->(B144 B174 B133 B192) +A145->(B145 B151 B110 B169) +A146->(B146 B128 B187) +A147->(B147 B105 B164 B123) +A148->(B148 B182 B141 B200) +A149->(B149 B159 B118 B177) +A150->(B150 B136 B195 B154) +A151->(B151 B113 B172 B131) +A152->(B152 B190 B149 B108) +A153->(B153 B167 B126 B185) +A154->(B154 B144 B103 B162) +A155->(B155 B121 B180 B139) +A156->(B156 B198 B157 B116) +A157->(B157 B175 B134 B193) +A158->(B158 B152 B111 B170) +A159->(B159 B129 B188 B147) +A160->(B160 B106 B165 B124) +A161->(B161 B183 B142 B101) +A162->(B162 B160 B119 B178) +A163->(B163 B137 B196 B155) +A164->(B164 B114 B173 B132) +A165->(B165 B191 B150 B109) +A166->(B166 B168 B127 B186) +A167->(B167 B145 B104 B163) +A168->(B168 B122 B181 B140) +A169->(B169 B199 B158 B117) +A170->(B170 B176 B135 B194) +A171->(B171 B153 B112) +A172->(B172 B130 B189 B148) +A173->(B173 B107 B166 B125) +A174->(B174 B184 B143 B102) +A175->(B175 B161 B120 B179) +A176->(B176 B138 B197 B156) +A177->(B177 B115 B174 B133) +A178->(B178 B192 B151 B110) +A179->(B179 B169 B128 B187) +A180->(B180 B146 B105 B164) +A181->(B181 B123 B182 B141) +A182->(B182 B200 B159 B118) +A183->(B183 B177 B136 B195) +A184->(B184 B154 B113 B172) +A185->(B185 B131 B190 B149) +A186->(B186 B108 B167 B126) +A187->(B187 B185 B144 B103) +A188->(B188 B162 B121 B180) +A189->(B189 B139 B198 B157) +A190->(B190 B116 B175 B134) +A191->(B191 B193 B152 B111) +A192->(B192 B170 B129 B188) +A193->(B193 B147 B106 B165) +A194->(B194 B124 B183 B142) +A195->(B195 B101 B160 B119) +A196->(B196 B178 B137) +A197->(B197 B155 B114 B173) +A198->(B198 B132 B191 B150) +A199->(B199 B109 B168 B127) +A200->(B200 B186 B145 B104) +B101->(C101 C164 C123 C182) +B102->(C102 C141 C200 C159) +B103->(C103 C118 C177 C136) +B104->(C104 C195 C154 C113) +B105->(C105 C172 C131 C190) +B106->(C106 C149 C108 C167) +B107->(C107 C126 C185 C144) +B108->(C108 C103 C162 C121) +B109->(C109 C180 C139 C198) +B110->(C110 C157 C116 C175) +B111->(C111 C134 C193 C152) +B112->(C112 C111 C170 C129) +B113->(C113 C188 C147 C106) +B114->(C114 C165 C124 C183) +B115->(C115 C142 C101 C160) +B116->(C116 C119 C178 C137) +B117->(C117 C196 C155 C114) +B118->(C118 C173 C132 C191) +B119->(C119 C150 C109 C168) +B120->(C120 C127 C186 C145) +B121->(C121 C104 C163 C122) +B122->(C122 C181 C140 C199) +B123->(C123 C158 C117 C176) +B124->(C124 C135 C194 C153) +B125->(C125 C112 C171 C130) +B126->(C126 C189 C148 C107) +B127->(C127 C166 C125 C184) +B128->(C128 C143 C102 C161) +B129->(C129 C120 C179 C138) +B130->(C130 C197 C156 C115) +B131->(C131 C174 C133 C192) +B132->(C132 C151 C110 C169) +B133->(C133 C128 C187 C146) +B134->(C134 C105 C164 C123) +B135->(C135 C182 C141 C200) +B136->(C136 C159 C118 C177) +B137->(C137 C136 C195 C154) +B138->(C138 C113 C172 C131) +B139->(C139 C190 C149 C108) +B140->(C140 C167 C126 C185) +B141->(C141 C144 C103 C162) +B142->(C142 C121 C180 C139) +B143->(C143 C198 C157 C116) +B144->(C144 C175 C134 C193) +B145->(C145 C152 C111 C170) +B146->(C146 C129 C188 C147) +B147->(C147 C106 C165 C124) +B148->(C148 C183 C142 C101) +B149->(C149 C160 C119 C178) +B150->(C150 C137 C196 C155) +B151->(C151 C114 C173 C132) +B152->(C152 C191 C150 C109) +B153->(C153 C168 C127 C186) +B154->(C154 C145 C104 C163) +B155->(C155 C122 C181 C140) +B156->(C156 C199 C158 C117) +B157->(C157 C176 C135 C194) +B158->(C158 C153 C112 C171) +B159->(C159 C130 C189 C148) +B160->(C160 C107 C166 C125) +B161->(C161 C184 C143 C102) +B162->(C162 C161 C120 C179) +B163->(C163 C138 C197 C156) +B164->(C164 C115 C174 C133) +B165->(C165 C192 C151 C110) +B166->(C166 C169 C128 C187) +B167->(C167 C146 C105 C164) +B168->(C168 C123 C182 C141) +B169->(C169 C200 C159 C118) +B170->(C170 C177 C136 C195) +B171->(C171 C154 C113 C172) +B172->(C172 C131 C190 C149) +B173->(C173 C108 C167 C126) +B174->(C174 C185 C144 C103) +B175->(C175 C162 C121 C180) +B176->(C176 C139 C198 C157) +B177->(C177 C116 C175 C134) +B178->(C178 C193 C152 C111) +B179->(C179 C170 C129 C188) +B180->(C180 C147 C106 C165) +B181->(C181 C124 C183 C142) +B182->(C182 C101 C160 C119) +B183->(C183 C178 C137 C196) +B184->(C184 C155 C114 C173) +B185->(C185 C132 C191 C150) +B186->(C186 C109 C168 C127) +B187->(C187 C186 C145 C104) +B188->(C188 C163 C122 C181) +B189->(C189 C140 C199 C158) +B190->(C190 C117 C176 C135) +B191->(C191 C194 C153 C112) +B192->(C192 C171 C130 C189) +B193->(C193 C148 C107 C166) +B194->(C194 C125 C184 C143) +B195->(C195 C102 C161 C120) +B196->(C196 C179 C138 C197) +B197->(C197 C156 C115 C174) +B198->(C198 C133 C192 C151) +B199->(C199 C110 C169 C128) +B200->(C200 C187 C146 C105) +C101->(A165 A124) +C102->(A183 A142) +C103->(A101 A160) +C104->(A119 A178) +C105->(A137 A196) +C106->(A155 A114) +C107->(A173 A132) +C108->(A191 A150) +C109->(A109 A168) +C110->(A127 A186) +C111->(A145 A104) +C112->(A163 A122) +C113->(A181 A140) +C114->(A199 A158) +C115->(A117 A176) +C116->(A135 A194) +C117->(A153 A112) +C118->(A171 A130) +C119->(A189 A148) +C120->(A107 A166) +C121->(A125 A184) +C122->(A143 A102) +C123->(A161 A120) +C124->(A179 A138) +C125->(A197 A156) +C126->(A115 A174) +C127->(A133 A192) +C128->(A151 A110) +C129->(A169 A128) +C130->(A187 A146) +C131->(A105 A164) +C132->(A123 A182) +C133->(A141 A200) +C134->(A159 A118) +C135->(A177 A136) +C136->(A195 A154) +C137->(A113 A172) +C138->(A131 A190) +C139->(A149 A108) +C140->(A167 A126) +C141->(A185 A144) +C142->(A103 A162) +C143->(A121 A180) +C144->(A139 A198) +C145->(A157 A116) +C146->(A175 A134) +C147->(A193 A152) +C148->(A111 A170) +C149->(A129 A188) +C150->(A147 A106) +C151->(A165 A124) +C152->(A183 A142) +C153->(A101 A160) +C154->(A119 A178) +C155->(A137 A196) +C156->(A155 A114) +C157->(A173 A132) +C158->(A191 A150) +C159->(A109 A168) +C160->(A127 A186) +C161->(A145 A104) +C162->(A163 A122) +C163->(A181 A140) +C164->(A199 A158) +C165->(A117 A176) +C166->(A135 A194) +C167->(A153 A112) +C168->(A171 A130) +C169->(A189 A148) +C170->(A107 A166) +C171->(A125 A184) +C172->(A143 A102) +C173->(A161 A120) +C174->(A179 A138) +C175->(A197 A156) +C176->(A115 A174) +C177->(A133 A192) +C178->(A151 A110) +C179->(A169 A128) +C180->(A187 A146) +C181->(A105 A164) +C182->(A123 A182) +C183->(A141 A200) +C184->(A159 A118) +C185->(A177 A136) +C186->(A195 A154) +C187->(A113 A172) +C188->(A131 A190) +C189->(A149 A108) +C190->(A167 A126) +C191->(A185 A144) +C192->(A103 A162) +C193->(A121 A180) +C194->(A139 A198) +C195->(A157 A116) +C196->(A175 A134) +C197->(A193 A152) +C198->(A111 A170) +C199->(A129 A188) +C200->(A147 A106) +M11X11->(M13X14 M12X13 M12X12 M12X11) +M11X12->(M13X25 M12X24 M12X23 M12X22) +M11X13->(M13X21 M12X20 M12X19 M12X18) +M11X14->(M13X17 M12X16 M12X15 M12X14) +M11X15->(M13X13 M12X12 M12X11 M12X25) +M11X16->(M13X24 M12X23 M12X22 M12X21) +M11X17->(M13X20 M12X19 M12X18 M12X17) +M11X18->(M13X16 M12X15 M12X14 M12X13) +M11X19->(M13X12 M12X11 M12X25 M12X24) +M11X20->(M13X23 M12X22 M12X21 M12X20) +M11X21->(M13X19 M12X18 M12X17 M12X16) +M11X22->(M13X15 M12X14 M12X13 M12X12) +M11X23->(M13X11 M12X25 M12X24 M12X23) +M11X24->(M13X22 M12X21 M12X20 M12X19) +M11X25->(M13X18 M12X17 M12X16 M12X15) +M12X11->(M14X14 M13X13 M13X12 M13X11) +M12X12->(M14X25 M13X24 M13X23 M13X22) +M12X13->(M14X21 M13X20 M13X19 M13X18) +M12X14->(M14X17 M13X16 M13X15 M13X14) +M12X15->(M14X13 M13X12 M13X11 M13X25) +M12X16->(M14X24 M13X23 M13X22 M13X21) +M12X17->(M14X20 M13X19 M13X18 M13X17) +M12X18->(M14X16 M13X15 M13X14 M13X13) +M12X19->(M14X12 M13X11 M13X25 M13X24) +M12X20->(M14X23 M13X22 M13X21 M13X20) +M12X21->(M14X19 M13X18 M13X17 M13X16) +M12X22->(M14X15 M13X14 M13X13 M13X12) +M12X23->(M14X11 M13X25 M13X24 M13X23) +M12X24->(M14X22 M13X21 M13X20 M13X19) +M12X25->(M14X18 M13X17 M13X16 M13X15) +M13X11->(M15X14 M14X13 M14X12 M14X11) +M13X12->(M15X25 M14X24 M14X23 M14X22) +M13X13->(M15X21 M14X20 M14X19 M14X18) +M13X14->(M15X17 M14X16 M14X15 M14X14) +M13X15->(M15X13 M14X12 M14X11 M14X25) +M13X16->(M15X24 M14X23 M14X22 M14X21) +M13X17->(M15X20 M14X19 M14X18 M14X17) +M13X18->(M15X16 M14X15 M14X14 M14X13) +M13X19->(M15X12 M14X11 M14X25 M14X24) +M13X20->(M15X23 M14X22 M14X21 M14X20) +M13X21->(M15X19 M14X18 M14X17 M14X16) +M13X22->(M15X15 M14X14 M14X13 M14X12) +M13X23->(M15X11 M14X25 M14X24 M14X23) +M13X24->(M15X22 M14X21 M14X20 M14X19) +M13X25->(M15X18 M14X17 M14X16 M14X15) +M14X11->(M16X14 M15X13 M15X12 M15X11) +M14X12->(M16X25 M15X24 M15X23 M15X22) +M14X13->(M16X21 M15X20 M15X19 M15X18) +M14X14->(M16X17 M15X16 M15X15 M15X14) +M14X15->(M16X13 M15X12 M15X11 M15X25) +M14X16->(M16X24 M15X23 M15X22 M15X21) +M14X17->(M16X20 M15X19 M15X18 M15X17) +M14X18->(M16X16 M15X15 M15X14 M15X13) +M14X19->(M16X12 M15X11 M15X25 M15X24) +M14X20->(M16X23 M15X22 M15X21 M15X20) +M14X21->(M16X19 M15X18 M15X17 M15X16) +M14X22->(M16X15 M15X14 M15X13 M15X12) +M14X23->(M16X11 M15X25 M15X24 M15X23) +M14X24->(M16X22 M15X21 M15X20 M15X19) +M14X25->(M16X18 M15X17 M15X16 M15X15) +M15X11->(M17X14 M16X13 M16X12 M16X11) +M15X12->(M17X25 M16X24 M16X23 M16X22) +M15X13->(M17X21 M16X20 M16X19 M16X18) +M15X14->(M17X17 M16X16 M16X15 M16X14) +M15X15->(M17X13 M16X12 M16X11 M16X25) +M15X16->(M17X24 M16X23 M16X22 M16X21) +M15X17->(M17X20 M16X19 M16X18 M16X17) +M15X18->(M17X16 M16X15 M16X14 M16X13) +M15X19->(M17X12 M16X11 M16X25 M16X24) +M15X20->(M17X23 M16X22 M16X21 M16X20) +M15X21->(M17X19 M16X18 M16X17 M16X16) +M15X22->(M17X15 M16X14 M16X13 M16X12) +M15X23->(M17X11 M16X25 M16X24 M16X23) +M15X24->(M17X22 M16X21 M16X20 M16X19) +M15X25->(M17X18 M16X17 M16X16 M16X15) +M16X11->(M18X14 M17X13 M17X12 M17X11) +M16X12->(M18X25 M17X24 M17X23 M17X22) +M16X13->(M18X21 M17X20 M17X19 M17X18) +M16X14->(M18X17 M17X16 M17X15 M17X14) +M16X15->(M18X13 M17X12 M17X11 M17X25) +M16X16->(M18X24 M17X23 M17X22 M17X21) +M16X17->(M18X20 M17X19 M17X18 M17X17) +M16X18->(M18X16 M17X15 M17X14 M17X13) +M16X19->(M18X12 M17X11 M17X25 M17X24) +M16X20->(M18X23 M17X22 M17X21 M17X20) +M16X21->(M18X19 M17X18 M17X17 M17X16) +M16X22->(M18X15 M17X14 M17X13 M17X12) +M16X23->(M18X11 M17X25 M17X24 M17X23) +M16X24->(M18X22 M17X21 M17X20 M17X19) +M16X25->(M18X18 M17X17 M17X16 M17X15) +M17X11->(M19X14 M18X13 M18X12 M18X11) +M17X12->(M19X25 M18X24 M18X23 M18X22) +M17X13->(M19X21 M18X20 M18X19 M18X18) +M17X14->(M19X17 M18X16 M18X15 M18X14) +M17X15->(M19X13 M18X12 M18X11 M18X25) +M17X16->(M19X24 M18X23 M18X22 M18X21) +M17X17->(M19X20 M18X19 M18X18 M18X17) +M17X18->(M19X16 M18X15 M18X14 M18X13) +M17X19->(M19X12 M18X11 M18X25 M18X24) +M17X20->(M19X23 M18X22 M18X21 M18X20) +M17X21->(M19X19 M18X18 M18X17 M18X16) +M17X22->(M19X15 M18X14 M18X13 M18X12) +M17X23->(M19X11 M18X25 M18X24 M18X23) +M17X24->(M19X22 M18X21 M18X20 M18X19) +M17X25->(M19X18 M18X17 M18X16 M18X15) +M18X11->(M20X14 M19X13 M19X12 M19X11) +M18X12->(M20X25 M19X24 M19X23 M19X22) +M18X13->(M20X21 M19X20 M19X19 M19X18) +M18X14->(M20X17 M19X16 M19X15 M19X14) +M18X15->(M20X13 M19X12 M19X11 M19X25) +M18X16->(M20X24 M19X23 M19X22 M19X21) +M18X17->(M20X20 M19X19 M19X18 M19X17) +M18X18->(M20X16 M19X15 M19X14 M19X13) +M18X19->(M20X12 M19X11 M19X25 M19X24) +M18X20->(M20X23 M19X22 M19X21 M19X20) +M18X21->(M20X19 M19X18 M19X17 M19X16) +M18X22->(M20X15 M19X14 M19X13 M19X12) +M18X23->(M20X11 M19X25 M19X24 M19X23) +M18X24->(M20X22 M19X21 M19X20 M19X19) +M18X25->(M20X18 M19X17 M19X16 M19X15) +M19X11->(M21X14 M20X13 M20X12 M20X11) +M19X12->(M21X25 M20X24 M20X23 M20X22) +M19X13->(M21X21 M20X20 M20X19 M20X18) +M19X14->(M21X17 M20X16 M20X15 M20X14) +M19X15->(M21X13 M20X12 M20X11 M20X25) +M19X16->(M21X24 M20X23 M20X22 M20X21) +M19X17->(M21X20 M20X19 M20X18 M20X17) +M19X18->(M21X16 M20X15 M20X14 M20X13) +M19X19->(M21X12 M20X11 M20X25 M20X24) +M19X20->(M21X23 M20X22 M20X21 M20X20) +M19X21->(M21X19 M20X18 M20X17 M20X16) +M19X22->(M21X15 M20X14 M20X13 M20X12) +M19X23->(M21X11 M20X25 M20X24 M20X23) +M19X24->(M21X22 M20X21 M20X20 M20X19) +M19X25->(M21X18 M20X17 M20X16 M20X15) +M20X11->(M22X14 M21X13 M21X12 M21X11) +M20X12->(M22X25 M21X24 M21X23 M21X22) +M20X13->(M22X21 M21X20 M21X19 M21X18) +M20X14->(M22X17 M21X16 M21X15 M21X14) +M20X15->(M22X13 M21X12 M21X11 M21X25) +M20X16->(M22X24 M21X23 M21X22 M21X21) +M20X17->(M22X20 M21X19 M21X18 M21X17) +M20X18->(M22X16 M21X15 M21X14 M21X13) +M20X19->(M22X12 M21X11 M21X25 M21X24) +M20X20->(M22X23 M21X22 M21X21 M21X20) +M20X21->(M22X19 M21X18 M21X17 M21X16) +M20X22->(M22X15 M21X14 M21X13 M21X12) +M20X23->(M22X11 M21X25 M21X24 M21X23) +M20X24->(M22X22 M21X21 M21X20 M21X19) +M20X25->(M22X18 M21X17 M21X16 M21X15) +M21X11->(M23X15 M22X14 M22X13 M22X12) +M21X12->(M11X11 M23X25 M22X24 M22X23 M22X22) +M21X13->(M23X21 M22X20 M22X19 M22X18) +M21X14->(M23X17 M22X16 M22X15 M22X14) +M21X15->(M23X13 M22X12 M22X11 M22X25) +M21X16->(M23X24 M22X23 M22X22 M22X21) +M21X17->(M23X20 M22X19 M22X18 M22X17) +M21X18->(M23X16 M22X15 M22X14 M22X13) +M21X19->(M23X12 M22X11 M22X25 M22X24) +M21X20->(M23X23 M22X22 M22X21 M22X20) +M21X21->(M23X19 M22X18 M22X17 M22X16) +M21X22->(M23X15 M22X14 M22X13 M22X12) +M21X23->(M23X11 M22X25 M22X24 M22X23) +M21X24->(M23X22 M22X21 M22X20 M22X19) +M21X25->(M23X18 M22X17 M22X16 M22X15) +M22X11->(M24X16 M23X15 M23X14 M23X13) +M22X12->(M12X12 M24X11 M23X25 M23X24 M23X23) +M22X13->(M24X22 M23X21 M23X20 M23X19) +M22X14->(M24X18 M23X17 M23X16 M23X15) +M22X15->(M24X14 M23X13 M23X12 M23X11) +M22X16->(M24X25 M23X24 M23X23 M23X22) +M22X17->(M24X21 M23X20 M23X19 M23X18) +M22X18->(M24X17 M23X16 M23X15 M23X14) +M22X19->(M24X13 M23X12 M23X11 M23X25) +M22X20->(M24X24 M23X23 M23X22 M23X21) +M22X21->(M24X20 M23X19 M23X18 M23X17) +M22X22->(M24X16 M23X15 M23X14 M23X13) +M22X23->(M24X12 M23X11 M23X25 M23X24) +M22X24->(M24X23 M23X22 M23X21 M23X20) +M22X25->(M24X19 M23X18 M23X17 M23X16) +M23X11->(M25X17 M24X16 M24X15 M24X14) +M23X12->(M13X13 M25X12 M24X11 M24X25 M24X24) +M23X13->(M25X23 M24X22 M24X21 M24X20) +M23X14->(M25X19 M24X18 M24X17 M24X16) +M23X15->(M25X15 M24X14 M24X13 M24X12) +M23X16->(M25X11 M24X25 M24X24 M24X23) +M23X17->(M25X22 M24X21 M24X20 M24X19) +M23X18->(M25X18 M24X17 M24X16 M24X15) +M23X19->(M25X14 M24X13 M24X12 M24X11) +M23X20->(M25X25 M24X24 M24X23 M24X22) +M23X21->(M25X21 M24X20 M24X19 M24X18) +M23X22->(M25X17 M24X16 M24X15 M24X14) +M23X23->(M25X13 M24X12 M24X11 M24X25) +M23X24->(M25X24 M24X23 M24X22 M24X21) +M23X25->(M25X20 M24X19 M24X18 M24X17) +M24X11->(M26X18 M25X17 M25X16 M25X15) +M24X12->(M14X14 M26X13 M25X12 M25X11 M25X25) +M24X13->(M26X24 M25X23 M25X22 M25X21) +M24X14->(M26X20 M25X19 M25X18 M25X17) +M24X15->(M26X16 M25X15 M25X14 M25X13) +M24X16->(M26X12 M25X11 M25X25 M25X24) +M24X17->(M26X23 M25X22 M25X21 M25X20) +M24X18->(M26X19 M25X18 M25X17 M25X16) +M24X19->(M26X15 M25X14 M25X13 M25X12) +M24X20->(M26X11 M25X25 M25X24 M25X23) +M24X21->(M26X22 M25X21 M25X20 M25X19) +M24X22->(M26X18 M25X17 M25X16 M25X15) +M24X23->(M26X14 M25X13 M25X12 M25X11) +M24X24->(M26X25 M25X24 M25X23 M25X22) +M24X25->(M26X21 M25X20 M25X19 M25X18) +M25X11->(M27X19 M26X18 M26X17 M26X16) +M25X12->(M15X15 M27X14 M26X13 M26X12 M26X11) +M25X13->(M27X25 M26X24 M26X23 M26X22) +M25X14->(M27X21 M26X20 M26X19 M26X18) +M25X15->(M27X17 M26X16 M26X15 M26X14) +M25X16->(M27X13 M26X12 M26X11 M26X25) +M25X17->(M27X24 M26X23 M26X22 M26X21) +M25X18->(M27X20 M26X19 M26X18 M26X17) +M25X19->(M27X16 M26X15 M26X14 M26X13) +M25X20->(M27X12 M26X11 M26X25 M26X24) +M25X21->(M27X23 M26X22 M26X21 M26X20) +M25X22->(M27X19 M26X18 M26X17 M26X16) +M25X23->(M27X15 M26X14 M26X13 M26X12) +M25X24->(M27X11 M26X25 M26X24 M26X23) +M25X25->(M27X22 M26X21 M26X20 M26X19) +M26X11->(M28X20 M27X19 M27X18 M27X17) +M26X12->(M16X16 M28X15 M27X14 M27X13 M27X12) +M26X13->(M28X11 M27X25 M27X24 M27X23) +M26X14->(M28X22 M27X21 M27X20 M27X19) +M26X15->(M28X18 M27X17 M27X16 M27X15) +M26X16->(M28X14 M27X13 M27X12 M27X11) +M26X17->(M28X25 M27X24 M27X23 M27X22) +M26X18->(M28X21 M27X20 M27X19 M27X18) +M26X19->(M28X17 M27X16 M27X15 M27X14) +M26X20->(M28X13 M27X12 M27X11 M27X25) +M26X21->(M28X24 M27X23 M27X22 M27X21) +M26X22->(M28X20 M27X19 M27X18 M27X17) +M26X23->(M28X16 M27X15 M27X14 M27X13) +M26X24->(M28X12 M27X11 M27X25 M27X24) +M26X25->(M28X23 M27X22 M27X21 M27X20) +M27X11->(M29X21 M28X20 M28X19 M28X18) +M27X12->(M17X17 M29X16 M28X15 M28X14 M28X13) +M27X13->(M29X12 M28X11 M28X25 M28X24) +M27X14->(M29X23 M28X22 M28X21 M28X20) +M27X15->(M29X19 M28X18 M28X17 M28X16) +M27X16->(M29X15 M28X14 M28X13 M28X12) +M27X17->(M29X11 M28X25 M28X24 M28X23) +M27X18->(M29X22 M28X21 M28X20 M28X19) +M27X19->(M29X18 M28X17 M28X16 M28X15) +M27X20->(M29X14 M28X13 M28X12 M28X11) +M27X21->(M29X25 M28X24 M28X23 M28X22) +M27X22->(M29X21 M28X20 M28X19 M28X18) +M27X23->(M29X17 M28X16 M28X15 M28X14) +M27X24->(M29X13 M28X12 M28X11 M28X25) +M27X25->(M29X24 M28X23 M28X22 M28X21) +M28X11->(M30X22 M29X21 M29X20 M29X19) +M28X12->(M18X18 M30X17 M29X16 M29X15 M29X14) +M28X13->(M30X13 M29X12 M29X11 M29X25) +M28X14->(M30X24 M29X23 M29X22 M29X21) +M28X15->(M30X20 M29X19 M29X18 M29X17) +M28X16->(M30X16 M29X15 M29X14 M29X13) +M28X17->(M30X12 M29X11 M29X25 M29X24) +M28X18->(M30X23 M29X22 M29X21 M29X20) +M28X19->(M30X19 M29X18 M29X17 M29X16) +M28X20->(M30X15 M29X14 M29X13 M29X12) +M28X21->(M30X11 M29X25 M29X24 M29X23) +M28X22->(M30X22 M29X21 M29X20 M29X19) +M28X23->(M30X18 M29X17 M29X16 M29X15) +M28X24->(M30X14 M29X13 M29X12 M29X11) +M28X25->(M30X25 M29X24 M29X23 M29X22) +M29X11->(M30X22 M30X21 M30X20) +M29X12->(M30X17 M30X16 M30X15) +M29X13->(M30X13 M30X12 M30X11) +M29X14->(M30X24 M30X23 M30X22) +M29X15->(M30X20 M30X19 M30X18) +M29X16->(M30X16 M30X15 M30X14) +M29X17->(M30X12 M30X11 M30X25) +M29X18->(M30X23 M30X22 M30X21) +M29X19->(M30X19 M30X18 M30X17) +M29X20->(M30X15 M30X14 M30X13) +M29X21->(M30X11 M30X25 M30X24) +M29X22->(M30X22 M30X21 M30X20) +M29X23->(M30X18 M30X17 M30X16) +M29X24->(M30X14 M30X13 M30X12) +M29X25->(M30X25 M30X24 M30X23) +M30X11 +M30X12 +M30X13 +M30X14 +M30X15 +M30X16 +M30X17 +M30X18 +M30X19 +M30X20 +M30X21 +M30X22 +M30X23 +M30X24 +M30X25 +xfail_output(glibc.rtld.dynamic_sort=1): M30X19>M30X15>M30X16>M30X11>M30X12>M30X17>M30X13>M30X14>M29X20>M30X23>M30X24>M30X20>M30X18>M29X15>M29X12>M30X22>M30X21>M29X22>M30X25>M29X19>M29X23>M29X16>M29X24>M29X13>M29X17>M29X18>M28X19>M29X21>M29X25>M29X14>M28X20>M28X15>M28X16>M28X21>M27X18>M29X11>M28X17>M28X11>M28X22>M27X14>M28X18>M27X15>M28X13>M27X11>M28X23>M27X25>M28X14>M28X25>M27X23>M27X22>M28X24>M27X21>M27X13>M27X19>M27X17>M26X11>M26X23>M26X21>M26X22>M26X20>M26X16>M25X21>M17X22>M15X15>M20X14>M20X16>M18X18>M28X12>M27X24>M25X17>M27X20>M26X18>M26X17>M27X16>M26X19>M25X18>M26X24>M25X20>M24X17>M23X18>M25X13>M26X13>M17X23>M16X16>M26X12>M25X12>M26X15>M24X19>M25X23>M25X24>M25X25>M24X20>M25X19>M24X21>M23X17>M22X21>M24X14>M23X22>M24X24>M22X20>M24X13>M25X11>M24X12>M25X15>M23X15>M25X16>M24X22>M23X13>M24X18>M23X14>M22X22>M21X20>M24X25>M23X16>M22X25>M21X19>M22X14>M23X11>M22X15>M21X18>M22X19>M21X17>M20X17>M19X17>M21X24>M21X12>M20X22>M19X16>M18X25>M19X21>M19X20>M18X24>M20X12>M19X11>M23X20>M22X24>M22X16>M21X21>M25X14>M23X19>M23X24>M20X24>M19X12>M18X15>M17X14>M16X18>M14X25>M16X22>M16X20>M17X17>M22X12>M21X11>M20X15>M18X22>M19X24>M19X18>M18X21>M17X16>M17X18>M16X21>M15X20>M19X22>M18X20>M18X11>M17X19>M16X17>M15X21>M16X14>M16X13>M15X22>M14X20>M17X25>M16X19>M14X21>M13X24>M12X12>M16X24>M15X23>M14X16>M16X15>M15X25>M15X11>M15X12>M14X15>M13X14>M14X22>M13X20>M12X13>M11X11>M22X23>M21X15>M21X16>M20X21>M20X20>M18X17>M19X25>M18X23>M21X13>M15X17>M15X18>M18X19>M17X24>M16X12>M17X13>M20X25>M19X23>M15X19>M14X13>M13X18>M15X13>M17X12>M16X11>M18X13>M18X12>M14X11>M14X24>M13X19>M15X14>M17X20>M20X11>M20X13>M21X14>M15X24>M14X12>M13X22>M14X23>M13X23>M14X19>M17X15>M16X25>M17X11>M18X14>M19X19>M21X25>M13X12>M13X11>M14X18>M13X13>M12X11>M15X16>M14X14>M27X12>M17X21>M20X23>M22X13>M21X22>M24X16>M24X15>M26X25>M23X25>M26X14>M23X12>M22X18>M24X11>M16X23>M19X14>M19X13>M21X23>M22X17>M23X23>M23X21>M25X22>M18X16>M19X15>M20X18>M20X19>M22X11>M24X23>C156>C118>C143>C137>C147>C106>C168>C113>C163>C155>C105>C146>C187>A150>C139>C180>C164>C193>C157>A191>C158>B188>A159>C184>C121>C154>B171>A105>C131>C104>B104>C161>C111>B145>C160>B155>A163>C112>C142>B148>C133>B198>A198>A115>C114>B157>A156>C175>B144>A120>C173>B184>A174>C126>B107>A139>C194>B194>A194>C116>B116>C166>B160>B110>A110>C128>B128>A128>C179>B162>A154>C186>B187>A179>C124>B181>A101>C153>B158>A136>C135>C176>A192>B133>A133>C177>B177>A177>C185>C103>B141>A141>C183>A162>C192>C129>B179>C144>B124>B183>C127>B127>A127>B108>A112>B153>A153>C167>B167>A186>A122>C162>A144>B149>C174>B131>A185>C141>B106>A126>A167>C140>B122>A170>C198>B143>C117>C123>B123>A147>A106>C200>B169>C191>B175>A123>B118>A182>C132>B151>A145>A104>A109>C159>C150>B119>A119>A178>B164>B114>A164>C181>A102>C122>B134>A157>A116>C195>B191>B111>C172>B172>A118>B129>A129>C149>A107>C170>B197>A197>A173>B168>A132>C107>B165>A160>A131>C188>A168>B109>C178>A189>A148>C119>C190>C120>B166>B176>C108>B135>B139>A103>B178>A169>B132>C125>C138>B163>A111>B170>C110>A165>C151>C169>C199>A138>C182>A135>B101>B142>C101>C148>B193>B152>A158>A199>C136>B137>A161>B120>A108>A149>A125>B113>A184>C171>A134>A175>A124>B150>B161>B102>A146>A187>C130>B192>B200>A200>A142>A183>C102>B105>B156>A176>C165>B147>A137>A196>B190>A190>B125>C134>C189>B126>B186>A166>B136>B195>A195>B154>B138>B112>B173>A117>B159>B182>A181>A140>C145>B117>A152>A193>C197>B130>A172>A113>A151>B115>A143>B140>B185>B103>A121>A180>A130>A171>B199>C196>B146>B180>C115>B174>B121>A188>B196>B189>C152>C109>A155>A114>M14X17>M13X15>M13X16>M13X17>M12X17>M12X21>M12X25>M12X14>M13X25>M12X15>M13X21>M12X16>M12X18>M12X19>M12X20>M12X22>M12X23>M12X24>M11X25>M11X24>M11X23>M11X22>M11X21>M11X20>M11X19>M11X18>M11X17>M11X16>M11X15>M11X14>M11X13>M11X12>{}M30X15>M30X16>M30X11>M30X12>M30X17>M30X13>M30X14>M29X20>M30X23>M30X24>M30X20>M30X18>M29X15>M29X12>M30X22>M30X21>M29X22>M30X25>M29X19>M29X23>M29X16>M29X24>M29X13>M29X17>M29X18>M28X19>M29X21>M29X25>M29X14>M28X20>M28X15>M28X16>M28X21>M27X18>M29X11>M28X17>M28X11>M28X22>M28X24>M28X23>M27X21>M28X13>M27X20>M27X19>M26X14>M27X25>M28X18>M27X11>M28X25>M27X24>M26X24>M27X15>M27X14>M27X13>M26X23>M27X17>M26X22>M25X13>M28X14>M27X16>M26X19>M26X18>M27X23>M27X22>M26X17>M25X18>M26X21>M25X17>M26X20>M26X15>M26X13>M25X19>M24X14>M25X23>M26X11>M26X25>M25X16>M25X15>M24X22>M25X21>M25X20>M24X21>M25X25>M25X24>M24X20>M23X13>M22X15>M25X14>M24X19>M23X17>M24X25>M23X24>M24X13>M23X15>M24X18>M23X14>M22X11>M24X15>M23X22>M24X11>M23X19>M22X21>M24X24>M23X21>M22X20>M23X25>M22X19>M21X24>M20X23>M22X22>M25X11>M23X16>M22X18>M23X20>M22X17>M21X21>M21X20>M20X24>M22X14>M22X13>M21X11>M21X17>M22X23>M21X16>M20X25>M19X23>M18X16>M21X22>M20X20>M20X19>M21X13>M20X18>M19X13>M21X18>M20X21>M19X24>M18X12>M20X14>M20X13>M22X25>M20X12>M20X15>M19X14>M18X22>M19X18>M20X17>M19X17>M19X16>M18X21>M17X20>M19X19>M18X13>M17X11>M18X17>M19X25>M18X15>M17X25>M18X19>M17X24>M16X19>M15X17>M17X21>M16X24>M18X23>M17X16>M16X25>M19X15>M18X25>M17X23>M16X23>M15X23>M18X14>M17X14>M16X14>M17X18>M16X13>M17X22>M16X12>M15X22>M14X16>M17X12>M16X22>M15X12>M16X11>M15X11>M16X15>M15X25>M14X15>M13X14>M15X18>M16X21>M15X16>M14X21>M15X14>M16X20>M15X13>M14X22>M15X20>M14X20>M13X20>M14X11>M15X19>M14X24>M13X19>M14X13>M13X18>M12X13>M15X24>M14X23>M13X12>M14X12>M13X11>M12X11>M11X11>M21X12>M20X11>M19X11>M18X11>M17X15>M16X18>M14X25>M14X19>M13X24>M13X23>M13X22>M12X12>M22X12>M21X15>M19X22>M18X20>M16X17>M14X14>M24X12>M23X23>M22X16>M21X14>M20X22>M18X24>M16X16>M26X12>M24X16>M23X11>M21X23>M19X20>M17X17>M27X12>M26X16>M25X22>M24X17>M23X18>M21X25>M19X12>M17X19>M15X21>M14X18>M13X13>M23X12>M21X19>M19X21>M17X13>M15X15>M25X12>M24X23>M22X24>M20X16>M18X18>M28X12>A150>C158>B112>A112>C167>B146>A146>C180>B180>A180>C143>B143>A115>C126>B126>A126>C190>B190>A190>C138>B138>A138>C174>B174>A102>C122>B122>A122>C162>B162>A162>C142>B142>A142>C102>B102>A174>C176>B176>A176>C115>B115>A143>C172>B172>A172>C187>B187>A187>C130>B130>A130>C118>B118>A118>C184>B184>A184>C171>B171>A171>C168>B182>A182>C182>B168>A168>C109>B109>A109>C159>B159>A159>C134>B134>A134>C146>B167>A167>C140>B140>A140>C163>B163>A163>C112>B158>A158>C164>B164>A164>C131>B131>A131>C188>B188>A188>C199>B199>A199>C114>B114>A114>C106>B106>A106>C200>B200>A200>C183>B183>A183>C152>B152>A152>C147>B147>A147>C150>B150>A198>C144>B144>A144>C191>B191>A191>C108>B108>A108>C139>B139>A139>C194>B194>A194>C166>B166>A166>C120>B120>A120>C123>B123>A123>C132>B132>A132>C107>B107>A107>C170>B170>A170>C198>B198>A156>C125>B125>A125>C121>B121>A121>C193>B193>A193>C197>B197>A197>C175>B175>A175>C196>B196>A196>C105>B105>A105>C181>B181>A181>C113>B113>A113>C137>B137>A137>C155>B155>A155>C156>B156>A110>C128>B128>A128>C179>B179>A179>C124>B124>A124>C151>B151>A151>C178>B178>A178>C104>B104>A104>C111>B111>A111>C148>B148>A148>C169>B169>A169>C129>B129>A129>C149>B149>A149>C189>B189>A189>C119>B119>A119>C154>B154>A154>C136>B136>A136>C135>B135>A135>C116>B116>A116>C145>B145>A145>C161>B161>A161>C173>B173>A173>C157>B157>A157>C195>B195>A195>C186>B186>A186>C160>B160>A160>C153>B153>A153>C117>B117>A117>C165>B165>A165>C101>B101>A101>C103>B103>A103>C192>B192>A192>C177>B177>A177>C185>B185>A185>C141>B141>A141>C133>B133>A133>C127>B127>A127>C110>B110>M14X17>M13X15>M13X16>M13X17>M12X17>M12X21>M12X25>M12X14>M13X25>M12X15>M13X21>M12X16>M12X18>M12X19>M12X20>M12X22>M12X23>M12X24>M11X25>M11X24>M11X23>M11X22>M11X21>M11X20>M11X19>M11X18>M11X17>M11X16>M11X15>M11X14>M11X13>M11X12>{}. + +"""Generate testcase files and Makefile fragments for DSO sorting test + +This script takes a small description string language, and generates +testcases for displaying the ELF dynamic linker's dependency sorting +behavior, allowing verification. + +Testcase descriptions are semicolon-separated description strings, and +this tool generates a testcase from the description, including main program, +associated modules, and Makefile fragments for including into elf/Makefile. + +This allows automation of what otherwise would be very laborous manual +construction of complex dependency cases, however it must be noted that this +is only a tool to speed up testcase construction, and thus the generation +features are largely mechanical in nature; inconsistencies or errors may occur +if the input description was itself erroronous or have unforeseen interactions. + +The format of the input test description files are: + + # Each test description has a name, lines of description, + # and an expected output specification. Comments use '#'. + testname1: + output: + + # Tests can be marked to be XFAIL by using 'xfail_output' instead + testname2: + xfail_output: + + # A default set of GLIBC_TUNABLES tunables can be specified, for which + # all following tests will run multiple times, once for each of the + # GLIBC_TUNABLES=... strings set by the 'tunable_option' command. + tunable_option: + tunable_option: + + # Test descriptions can use multiple lines, which will all be merged + # together, so order is not important. + testname3: + + + ... + output: + + # 'testname3' will be run and compared two times, for both + # GLIBC_TUNABLES= and + # GLIBC_TUNABLES=. This can be cleared and reset by the + # 'clear_tunables' command: + clear_tunables + + # Multiple expected outputs can also be specified, with an associated + # tunable option in (), which multiple tests will be run with each + # GLIBC_TUNABLES=... option tried. + testname4: + + ... + output(): + output(): + # Individual tunable output cases can be XFAILed, though note that + # this will have the effect of XFAILing the entire 'testname4' test + # in the final top-level tests.sum summary. + xfail_output(): + + # When multiple outputs (with specific tunable strings) are specified, + # these take priority over any active 'tunable_option' settings. + +On the description language used, an example description line string: + + a->b!->[cdef];c=>g=>h;{+c;%c;-c}->a + +Each identifier represents a shared object module, currently sequences of +letters/digits are allowed, case-sensitive. + +All such shared objects have a constructor/destructor generated for them +that emits its name followed by a '>' for constructors, and '<' followed by +its name for destructors, e.g. if the name is 'obj1', then "obj1>" and " 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())' + +For single character object names, square brackets [] in the description +allows specifiying multiple objects; e.g. a->[bcd]->e is equivalent to + a->b->e;a->c->e;a->d->e + +The () parenthesis construct with space separated names is also allowed for +specifying objects. For names with integer suffixes a range can also be used, +e.g. (foo1 bar2-5), specifies DSOs foo1, bar2, bar2, bar3, bar4, bar5. + +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]' + +Sometimes for very complex or large testcases, besides specifying a +few explicit dependencies from main{}, the above default dependency +behavior is still useful to automatically have, but is turned off +upon specifying a single explicit {}->dso_name. +In this case, add {}->* to explicitly add this generation behavior: + + # Main program links to 'foo', and all other objects which have no + # dependency linked to it. + {}->foo,{}->* + +Note that '*' works not only on main{}, but can be used as the +dependency target of any object. Note that it only works as a target, +not a dependency source. + +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 specified on +the script command-line, multiple , , 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) + + +Strings Output by Generated Testcase Programs + +The text output produced by a generated testcase consists of three main +parts: + 1. The constructors' output + 2. Output from the main program + 3. Destructors' output + +To see by example, a simple test description "a->b->c" generates a testcase +that when run, outputs: "c>b>a>{}' character, +and the "c>b>a" part above is the full constructor output by all DSOs, the +order indicating that DSO 'c', which does not depend on any other DSO, has +its constructor run first, followed by 'b' and then 'a'. + +Destructor output for each DSO is a '<' character followed by its name, +reflecting its reverse nature of constructors. In the above example, the +destructor output part is "g=>h;{+c;%c;-c}->a->h + +This produces a testcase, that when executed outputs: + h>a>{+c[g>c>];%c();-c[h dependency as expected. +Inside the main program, the "+c" action triggers a dlopen() of DSO 'c', +causing another chain of constructors "g>c>" to be triggered. Here it is +displayed inside [] brackets for each dlopen call. The same is done for "-c", +a dlclose() of 'c'. + +The "%c" output is due to calling to fn_c() inside DSO 'c', this comprises +of two parts: the '%' character is printed by the caller, here it is the main +program. The 'c' character is printed from inside fn_c(). The '%' character +indicates that this is called by a dlsym() of "fn_c". A '@' character would +mean a direct call (with a symbol reference). These can all be controlled +by the main test program constructs documented earlier. + +The output strings described here is the exact same form placed in +test description files' "output: " line. + + +""" +import sys +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), either specified here as " + "command line argument, or by input file using " + "-f/--description-file option", + nargs="?", default="") +parser.add_argument("test_name", help="Identifier for testcase being " + "generated", nargs="?", default="") +parser.add_argument("--objpfx", + help="Path to place generated files, defaults to " + "current directory if none specified", + nargs="?", default="./") +parser.add_argument("-m", "--output-makefile", + help="File to write Makefile fragment to, defaults to " + "stdout when option not present", nargs="?", default="") +parser.add_argument("-f", "--description-file", + help="Input file containing testcase descriptions", + 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() +test_name = cmdlineargs.test_name +description = cmdlineargs.description +objpfx = cmdlineargs.objpfx +description_file = cmdlineargs.description_file +output_makefile = cmdlineargs.output_makefile +makefile = "" +default_tunable_options = [] + +current_input_lineno = 0 +def error(msg): + global current_input_lineno + print("Error: %s%s" % ((("Line %d, " % current_input_lineno) + if current_input_lineno != 0 else ""), + msg)) + exit(1) + +if(test_name or description) and description_file: + error("both command-line testcase and input file specified") +if test_name and not description: + error("command-line testcase name without description string") + +# Main class type describing a testcase. +class TestDescr: + def __init__(self): + self.objs = [] # list of all DSO objects + self.deps = OrderedDict() # map of DSO object -> list of dependencies + + # map of DSO object -> list of call refs + self.callrefs = OrderedDict() + + # map of DSO object -> list of permutations of dependencies + self.dep_permutations = OrderedDict() + + # list of main program operations + self.main_program = [] + # set if main program needs -ldl + self.main_program_needs_ldl = False + # set if default dependencies added to main + self.main_program_default_deps = True + + self.test_name = "" # name of testcase + self.expected_outputs = OrderedDict() # expected outputs of testcase + self.xfail = False # set if this is a XFAIL testcase + + # Add 'object -> [object, object, ...]' relations to CURR_MAP + def __add_deps_internal(self, 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) + def add_deps(self, src_objs, dst_objs): + self.__add_deps_internal(src_objs, dst_objs, self.deps) + def add_callrefs(self, src_objs, dst_objs): + self.__add_deps_internal(src_objs, dst_objs, self.callrefs) + +# Process commands inside the {} construct. +# Note that throughout this script, the main program object is represented +# by the '#' string. +def process_main_program(test_descr, mainprog_str): + if mainprog_str: + test_descr.main_program = mainprog_str.split(';') + for s in test_descr.main_program: + m = re.match(r"^([+\-%^@])([0-9a-zA-Z]+)$", s) + if not m: + error("'%s' is not recognized main program operation" % (s)) + opr = m.group(1) + if(opr == '+' or opr == '^' or opr == '%' or opr == '-'): + # Determined the main program needs libdl + test_descr.main_program_needs_ldl = True + obj = m.group(2) + if not obj in test_descr.objs: + test_descr.objs.append(obj) + if opr == '%' or opr == '@': + test_descr.add_callrefs(['#'], [obj]) + # We have a main program specified, turn this off + test_descr.main_program_default_deps = False + +# For(a1 a2 b1-12) object set descriptions, expand into an object list +def expand_object_set_string(descr_str): + obj_list = [] + descr_list = descr_str.split() + for descr in descr_list: + m = re.match(r"^([a-zA-Z][0-9a-zA-Z]*)(-[0-9]+)?$", descr) + if not m: + error("'%s' is not a valid object set description" % (descr)) + obj = m.group(1) + idx_end = m.group(2) + if not idx_end: + if not obj in obj_list: + obj_list.append(obj) + else: + idx_end = int(idx_end[1:]) + m = re.match(r"^([0-9a-zA-Z][a-zA-Z]*)([0-9]+)$", obj) + if not m: + error("object description '%s' is malformed" % (obj)) + obj_name = m.group(1) + idx_start = int(m.group (2)) + if idx_start > idx_end: + error("index range %s-%s invalid" % (idx_start, idx_end)) + for i in range(idx_start, idx_end + 1): + o = obj_name + str(i) + if not o in obj_list: + obj_list.append(o) + return obj_list + +# Lexer for tokens +tokenspec = [ ("OBJ", r"([0-9a-zA-Z]+)"), + ("DEP", r"->"), + ("CALLREF", r"=>"), + ("OBJSET", r"\[([0-9a-zA-Z]+)\]"), + ("OBJSET2", r"\(([0-9a-zA-Z \-]+)\)"), + ("OBJSET3", r"\*"), + ("PROG", r"{([0-9a-zA-Z;+^\-%]*)}"), + ("PERMUTE", r"!"), + ("SEMICOL", r";"), + ("ERROR", r".") ] +tok_re = '|'.join('(?P<%s>%s)' % pair for pair in tokenspec) + +# Main line parser of description language +def parse_description_string(t, descr_str): + + # State used when parsing dependencies + curr_objs = [] + in_dep = False + in_callref = False + def clear_dep_state(): + nonlocal in_dep, in_callref + in_dep = in_callref = False + + for m in re.finditer(tok_re, descr_str): + kind = m.lastgroup + value = m.group() + if kind == "OBJ": + if in_dep: + t.add_deps(curr_objs, [value]) + elif in_callref: + t.add_callrefs(curr_objs, [value]) + clear_dep_state() + curr_objs = [value] + if not value in t.objs: + t.objs.append(value) + + elif kind == "OBJSET": + objset = value[1:len(value)-1] + if in_dep: + t.add_deps(curr_objs, list (objset)) + elif in_callref: + t.add_callrefs(curr_objs, list (objset)) + clear_dep_state() + curr_objs = list(objset) + for o in list(objset): + if not o in t.objs: + t.objs.append(o) + + elif kind == "OBJSET2": + descr_str = value[1:len(value)-1] + descr_str.strip() + objs = expand_object_set_string(descr_str) + if not objs: + error("empty object set '%s'" % (value)) + if in_dep: + t.add_deps(curr_objs, objs) + elif in_callref: + t.add_callrefs(curr_objs, objs) + clear_dep_state() + curr_objs = objs + for o in objs: + if not o in t.objs: + t.objs.append(o) + + elif kind == "OBJSET3": + if in_dep: + t.add_deps(curr_objs, ['*']) + elif in_callref: + t.add_callrefs(curr_objs, ['*']) + else: + error("non-dependence target set '*' can only be used " + "as target of ->/=> operations") + clear_dep_state() + curr_objs = ['*'] + + elif kind == "PERMUTE": + if in_dep or in_callref: + error("syntax error, permute operation invalid here") + if not curr_objs: + error("syntax error, no objects to permute here") + + for obj in curr_objs: + if not obj in t.dep_permutations: + # Signal this object has permuted dependencies + t.dep_permutations[obj] = [] + + elif kind == "PROG": + if t.main_program: + error("cannot have more than one main program") + if in_dep: + error("objects cannot have dependency on main program") + if in_callref: + # TODO: A DSO can resolve to a symbol in the main binary, + # which we syntactically allow here, but haven't yet + # implemented. + t.add_callrefs(curr_objs, ["#"]) + process_main_program(t, value[1:len(value)-1]) + clear_dep_state() + curr_objs = ["#"] + + elif kind == "DEP": + if in_dep or in_callref: + error("syntax error, multiple contiguous ->,=> operations") + if '*' in curr_objs: + error("non-dependence target set '*' can only be used " + "as target of ->/=> operations") + in_dep = True + + elif kind == "CALLREF": + if in_dep or in_callref: + error("syntax error, multiple contiguous ->,=> operations") + if '*' in curr_objs: + error("non-dependence target set '*' can only be used " + "as target of ->/=> operations") + in_callref = True + + elif kind == "SEMICOL": + curr_objs = [] + clear_dep_state() + + else: + error("unknown token '%s'" % (value)) + return t + + + +def process_testcase(t): + global objpfx + assert t.test_name + + base_test_name = t.test_name + test_subdir = base_test_name + "-dir" + testpfx = objpfx + test_subdir + "/" + + if not os.path.exists(testpfx): + os.mkdir(testpfx) + + def find_objs_not_depended_on(t): + objs_not_depended_on = [] + for obj in t.objs: + skip = False + for r in t.deps.items(): + if obj in r[1]: + skip = True + break + if not skip: + objs_not_depended_on.append(obj) + return objs_not_depended_on + + non_dep_tgt_objs = find_objs_not_depended_on(t) + for obj in t.objs: + if obj in t.deps: + deps = t.deps[obj] + if '*' in deps: + t.deps[obj].remove('*') + t.add_deps([obj], non_dep_tgt_objs) + if obj in t.callrefs: + deps = t.callrefs[obj] + if '*' in deps: + t.deps[obj].remove('*') + t.add_callrefs([obj], non_dep_tgt_objs) + if "#" in t.deps: + deps = t.deps["#"] + if '*' in deps: + t.deps["#"].remove('*') + t.add_deps(["#"], non_dep_tgt_objs) + + # 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 t.main_program_default_deps: + main_deps = non_dep_tgt_objs + if not main_deps: + error("no objects for default main program to point " + "dependency to(all objects strongly connected?)") + t.add_deps(["#"], main_deps) + + # Some debug output + if cmdlineargs.debug_output: + print("Testcase: %s" % (t.test_name)) + print("All objects: %s" % (t.objs)) + print("--- Static link dependencies ---") + for r in t.deps.items(): + print("%s -> %s" % (r[0], r[1])) + print("--- Objects whose dependencies are to be permuted ---") + for r in t.dep_permutations.items(): + print("%s" % (r[0])) + print("--- Call reference dependencies ---") + for r in t.callrefs.items(): + print("%s => %s" % (r[0], r[1])) + print("--- main program ---") + print(t.main_program) + + # Main testcase generation routine, does Makefile fragment generation, + # testcase source generation, and if --build specified builds testcase. + def generate_testcase(test_descr, test_suffix): + + test_name = test_descr.test_name + test_suffix + + # Print out needed Makefile fragments for use in glibc/elf/Makefile. + module_names = "" + for o in test_descr.objs: + module_names += " " + test_subdir + "/" + test_name + "-" + o + makefile.write("modules-names +=%s\n" % (module_names)) + + # Depth-first traversal, executing FN(OBJ) in post-order + def dfs(t, fn): + def dfs_rec(obj, fn, obj_visited): + if obj in obj_visited: + return + obj_visited[obj] = True + if obj in t.deps: + for dep in t.deps[obj]: + dfs_rec(dep, fn, obj_visited) + fn(obj) + + obj_visited = {} + for obj in t.objs: + dfs_rec(obj, fn, obj_visited) + + # Generate link dependencies for all DSOs, done in a DFS fashion. + # Usually this doesn't need to be this complex, just listing the direct + # dependencies is enough. However to support creating circular + # dependency situations, traversing it by DFS and tracking processing + # status is the natural way to do it. + obj_processed = {} + fake_created = {} + def gen_link_deps(obj): + if obj in test_descr.deps: + dso = test_subdir + "/" + test_name + "-" + obj + ".so" + dependencies = "" + for dep in test_descr.deps[obj]: + if dep in obj_processed: + depstr = (" $(objpfx)" + test_subdir + "/" + + test_name + "-" + dep + ".so") + else: + # A circular dependency is satisfied by making a + # fake DSO tagged with the correct SONAME + depstr = (" $(objpfx)" + test_subdir + "/" + + test_name + "-" + dep + ".FAKE.so") + # Create empty C file and Makefile fragments for fake + # object. This only needs to be done at most once for + # an object name. + if not dep in fake_created: + f = open(testpfx + test_name + "-" + dep + + ".FAKE.c", "w") + f.write(" \n") + f.close() + # Generate rule to create fake object + makefile.write \ + ("LDFLAGS-%s = -Wl,--no-as-needed " + "-Wl,-soname=%s\n" + % (test_name + "-" + dep + ".FAKE.so", + ("$(objpfx)" + test_subdir + "/" + + test_name + "-" + dep + ".so"))) + makefile.write \ + ("modules-names += %s\n" + % (test_subdir + "/" + + test_name + "-" + dep + ".FAKE")) + fake_created[dep] = True + dependencies += depstr + makefile.write("$(objpfx)%s:%s\n" % (dso, dependencies)) + # Mark obj as processed + obj_processed[obj] = True + + dfs(test_descr, gen_link_deps) + + # Print LDFLAGS-* and *-no-z-defs + for o in test_descr.objs: + dso = test_name + "-" + o + ".so" + makefile.write("LDFLAGS-%s = -Wl,--no-as-needed\n" % (dso)) + if o in test_descr.callrefs: + makefile.write("%s-no-z-defs = yes\n" % (dso)) + + # Print dependencies for main test program. + depstr = "" + if '#' in test_descr.deps: + for o in test_descr.deps['#']: + depstr += (" $(objpfx)" + test_subdir + "/" + + test_name + "-" + o + ".so") + if test_descr.main_program_needs_ldl: + depstr += " $(libdl)" + makefile.write("$(objpfx)%s/%s:%s\n" % (test_subdir, test_name, depstr)) + makefile.write("LDFLAGS-%s = -Wl,--no-as-needed\n" % (test_name)) + + not_depended_objs = find_objs_not_depended_on(test_descr) + if not_depended_objs: + depstr = "" + for dep in not_depended_objs: + depstr += (" $(objpfx)" + test_subdir + "/" + + test_name + "-" + dep + ".so") + makefile.write("$(objpfx)%s.out:%s\n" % (base_test_name, depstr)) + + # Add main executable to test-srcs + makefile.write("test-srcs += %s/%s\n" % (test_subdir, test_name)) + # Add dependency on main executable of test + makefile.write("$(objpfx)%s.out: $(objpfx)%s/%s\n" + % (base_test_name, test_subdir, test_name)) + + for r in test_descr.expected_outputs.items(): + tunable_options = [] + specific_tunable = r[0] + xfail = r[1][1] + if specific_tunable != "": + tunable_options = [specific_tunable] + else: + tunable_options = default_tunable_options + if not tunable_options: + tunable_options = [""] + + for tunable in tunable_options: + tunable_env = "" + tunable_sfx = "" + exp_tunable_sfx = "" + if tunable: + tunable_env = "GLIBC_TUNABLES=%s " % tunable + tunable_sfx = "-" + tunable.replace("=","_") + if specific_tunable: + tunable_sfx = "-" + specific_tunable.replace("=","_") + exp_tunable_sfx = tunable_sfx + tunable_descr = ("(%s)" % tunable_env.strip() + if tunable_env else "") + # Write out fragment of shell script for this single test. + test_descr.sh.write \ + ("%s${test_wrapper_env} ${run_program_env} \\\n" + "${common_objpfx}support/test-run-command \\\n" + "${common_objpfx}elf/ld.so \\\n" + "--library-path ${common_objpfx}elf/%s:" + "${common_objpfx}elf:${common_objpfx}.:" + "${common_objpfx}dlfcn \\\n" + "${common_objpfx}elf/%s/%s > \\\n" + " ${common_objpfx}elf/%s/%s%s.output\n" + % (tunable_env ,test_subdir, + test_subdir, test_name, test_subdir, test_name, + tunable_sfx)) + # Generate a run of each test and compare with expected out + test_descr.sh.write \ + ("if [ $? -ne 0 ]; then\n" + " echo '%sFAIL: %s%s execution test'\n" + " something_failed=true\n" + "else\n" + " diff -wu ${common_objpfx}elf/%s/%s%s.output \\\n" + " ${common_objpfx}elf/%s/%s%s.exp\n" + " if [ $? -ne 0 ]; then\n" + " echo '%sFAIL: %s%s expected output comparison'\n" + " something_failed=true\n" + " fi\n" + "fi\n" + % (("X" if xfail else ""), test_name, tunable_descr, + test_subdir, test_name, tunable_sfx, + test_subdir, base_test_name, exp_tunable_sfx, + ("X" if xfail else ""), test_name, tunable_descr)) + + # Generate C files according to dependency and calling relations from + # description string. + for obj in test_descr.objs: + src_name = test_name + "-" + obj + ".c" + f = open(testpfx + src_name, "w") + if obj in test_descr.callrefs: + called_objs = test_descr.callrefs[obj] + for callee in called_objs: + f.write("extern void fn_%s (void);\n" % (callee)) + if len(obj) == 1: + f.write("extern int putchar(int);\n") + f.write("static void __attribute__((constructor)) " + + "init(void){putchar('%s');putchar('>');}\n" % (obj)) + f.write("static void __attribute__((destructor)) " + + "fini(void){putchar('<');putchar('%s');}\n" % (obj)) + else: + f.write('extern int printf(const char *, ...);\n') + f.write('static void __attribute__((constructor)) ' + + 'init(void){printf("%s>");}\n' % (obj)) + f.write('static void __attribute__((destructor)) ' + + 'fini(void){printf("<%s");}\n' % (obj)) + if obj in test_descr.callrefs: + called_objs = test_descr.callrefs[obj] + if len(obj) != 1: + f.write("extern int putchar(int);\n") + f.write("void fn_%s (void) {\n" % (obj)) + if len(obj) == 1: + f.write(" putchar ('%s');\n" % (obj)); + f.write(" putchar ('(');\n"); + else: + f.write(' printf ("%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 test_descr.callrefs.items(): + if obj in callref[1]: + if len(obj) == 1: + # We need to declare printf here in this case. + f.write('extern int printf(const char *, ...);\n') + f.write("void fn_%s (void) {\n" % (obj)) + f.write(' printf ("%s()");\n' % (obj)) + f.write("}\n") + break + f.close() + + # Open C file for writing main program + f = open(testpfx + test_name + ".c", "w") + + # if there are some operations in main(), it means we need -ldl + if test_descr.main_program_needs_ldl: + f.write("#include \n") + f.write("#include \n") + f.write("#include \n") + for s in test_descr.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 generating sanity checking 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(test_descr.main_program): + s = test_descr.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"); + if len(obj) == 1: + f.write(" putchar('%s');\n" % (obj)); + else: + f.write(' printf("%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"); + if len(obj) == 1: + f.write(" putchar('%s');\n" % (obj)); + else: + f.write(' printf("%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(" putchar('%');\n"); + 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(" putchar('@');\n"); + 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() + + # --build option processing: build generated sources using 'build_gcc' + if cmdlineargs.build: + # Helper routine to run a shell command, for running GCC below + def run_cmd(args): + cmd = str.join(' ', args) + if cmdlineargs.debug_output: + print(cmd) + p = subprocess.Popen(args) + p.wait() + if p.returncode != 0: + error("error running command: %s" % (cmd)) + + # Compile individual .os files + for obj in test_descr.objs: + src_name = test_name + "-" + obj + ".c" + obj_name = test_name + "-" + obj + ".os" + run_cmd([build_gcc, "-c", "-fPIC", testpfx + src_name, + "-o", testpfx + obj_name]) + + obj_processed = {} + fake_created = {} + # Function to create -.so + def build_dso(obj): + obj_name = test_name + "-" + obj + ".os" + dso_name = test_name + "-" + obj + ".so" + deps = [] + if obj in test_descr.deps: + for dep in test_descr.deps[obj]: + if dep in obj_processed: + deps.append(dep) + else: + deps.append(dep + ".FAKE") + if not dep in fake_created: + base_name = testpfx + test_name + "-" + dep + cmd = [build_gcc, "-Wl,--no-as-needed", + ("-Wl,-soname=" + base_name + ".so"), + "-shared", base_name + ".FAKE.c", + "-o", base_name + ".FAKE.so"] + run_cmd(cmd) + fake_created[dep] = True + dso_deps = map(lambda d: testpfx + test_name + "-" + d + ".so", + deps) + cmd = ([build_gcc, "-shared", "-o", testpfx + dso_name, + testpfx + obj_name, + "-Wl,--no-as-needed"] + list(dso_deps)) + run_cmd(cmd) + obj_processed[obj] = True + + # Build all DSOs, this needs to be in topological dependency order, + # or link will fail + dfs(test_descr, build_dso) + + # Build main program + deps = [] + if '#' in test_descr.deps: + deps = test_descr.deps['#'] + main_deps = map(lambda d: testpfx + test_name + "-" + d + ".so", + deps) + cmd = ([build_gcc, "-Wl,--no-as-needed", "-o", testpfx + test_name, + testpfx + test_name + ".c", "-L%s" % (os.getcwd()), + "-Wl,-rpath-link=%s" % (os.getcwd())] + + list(main_deps)) + if test_descr.main_program_needs_ldl: + cmd += ["-ldl"] + run_cmd(cmd) + + # Check if we need to enumerate permutations of dependencies + need_permutation_processing = False + if t.dep_permutations: + # Adjust dep_permutations into map of object -> dependency permutations + for r in t.dep_permutations.items(): + obj = r[0] + if obj in t.deps and len(t.deps[obj]) > 1: + deps = t.deps[obj] + t.dep_permutations[obj] = list(itertools.permutations (deps)) + need_permutation_processing = True + + def enum_permutations(t, perm_list): + test_subindex = 1 + curr_perms = [] + def enum_permutations_rec(t, perm_list): + nonlocal 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_rec(t, perm_list[1:]) + else: + for deps in perms: + t.deps[obj] = deps + permstr = "" if obj == "#" else obj + "_" + permstr += str.join('', deps) + curr_perms.append(permstr) + enum_permutations_rec(t, perm_list[1:]) + curr_perms = curr_perms[0:len(curr_perms)-1] + else: + # t.deps is now instantiated with one dependency order + # permutation(across all objects that have multiple + # permutations), now process a testcase + generate_testcase(t, ("_" + str (test_subindex) + + "-" + str.join('-', curr_perms))) + test_subindex += 1 + enum_permutations_rec(t, perm_list) + + # Create *.exp files with expected outputs + for r in t.expected_outputs.items(): + sfx = "" + if r[0] != "": + sfx = "-" + r[0].replace("=","_") + f = open(testpfx + t.test_name + sfx + ".exp", "w") + (output, xfail) = r[1] + f.write('%s' % output) + f.close() + + # Create header part of top-level testcase shell script, to wrap execution + # and output comparison together. + t.sh = open(testpfx + t.test_name + ".sh", "w") + t.sh.write("#!/bin/sh\n") + t.sh.write("# Test driver for %s, generated by " + "dso-ordering-test.py\n" % (t.test_name)) + t.sh.write("common_objpfx=$1\n") + t.sh.write("test_wrapper_env=$2\n") + t.sh.write("run_program_env=$3\n") + t.sh.write("something_failed=false\n") + + # Starting part of Makefile fragment + makefile.write("ifeq (yes,$(build-shared))\n") + + if need_permutation_processing: + enum_permutations(t, list (t.dep_permutations.items())) + else: + # We have no permutations to enumerate, just process testcase normally + generate_testcase(t, "") + + # If testcase is XFAIL, indicate so + if t.xfail: + makefile.write("test-xfail-%s = yes\n" % t.test_name) + + # Output end part of Makefile fragment + expected_output_files = "" + for r in t.expected_outputs.items(): + sfx = "" + if r[0] != "": + sfx = "-" + r[0].replace("=","_") + expected_output_files += " $(objpfx)%s/%s%s.exp" % (test_subdir, + t.test_name, sfx) + makefile.write \ + ("$(objpfx)%s.out: $(objpfx)%s/%s.sh%s " + "$(common-objpfx)support/test-run-command\n" + % (t.test_name, test_subdir, t.test_name, + expected_output_files)) + makefile.write("\t$(SHELL) $< $(common-objpfx) '$(test-wrapper-env)' " + "'$(run-program-env)' > $@; $(evaluate-test)\n") + makefile.write("ifeq ($(run-built-tests),yes)\n") + makefile.write("tests-special += $(objpfx)%s.out\n" % (t.test_name)) + makefile.write("endif\n") + makefile.write("endif\n") + + # Write ending part of shell script generation + t.sh.write("if $something_failed; then\n" + " exit 1\n" + "else\n" + " echo '%sPASS: all tests for %s succeeded'\n" + " exit 0\n" + "fi\n" % (("X" if t.xfail else ""), + t.test_name)) + t.sh.close() + +# Decription file parsing +def parse_description_file(filename): + global default_tunable_options + global current_input_lineno + f = open(filename) + if not f: + error("cannot open description file %s" % (filename)) + descrfile_lines = f.readlines() + t = None + for line in descrfile_lines: + p = re.compile(r"#.*$") + line = p.sub("", line) # Filter out comments + line = line.strip() # Remove excess whitespace + current_input_lineno += 1 + + m = re.match(r"^tunable_option:\s*(.*)$", line) + if m: + if m.group(1) == "": + error("tunable option cannot be empty") + default_tunable_options.append(m.group (1)) + continue + + m = re.match(r"^clear_tunables$", line) + if m: + default_tunable_options = [] + continue + + m = re.match(r"^([^:]+):\s*(.*)$", line) + if m: + o = re.match(r"^output(.*)$", m.group (1)) + xfail = False + if not o: + o = re.match(r"^xfail_output(.*)$", m.group (1)) + if o: + xfail = True; + if o: + if not t: + error("output specification without testcase description") + tsstr = "" + if o.group(1): + ts = re.match(r"^\(([a-zA-Z0-9_.=]*)\)$", o.group (1)) + if not ts: + error("tunable option malformed '%s'" % o.group(1)) + tsstr = ts.group(1) + t.expected_outputs[tsstr] = (m.group(2), xfail) + # Any tunable option XFAILed means entire testcase + # is XFAIL/XPASS + t.xfail |= xfail + else: + if t: + # Starting a new test description, end and process + # current one. + process_testcase(t) + t = TestDescr() + t.test_name = m.group(1) + descr_string = m.group(2) + parse_description_string(t, descr_string) + continue + else: + if line: + if not t: + error("no active testcase description") + parse_description_string(t, line) + # Process last completed test description + if t: + process_testcase(t) + +# Setup Makefile output to file or stdout as selected +if output_makefile: + output_makefile_dir = os.path.dirname(output_makefile) + if output_makefile_dir: + os.makedirs(output_makefile_dir, exist_ok = True) + makefile = open(output_makefile, "w") +else: + makefile = open(sys.stdout.fileno (), "w") + +# Finally, the main top-level calling of above parsing routines. +if description_file: + parse_description_file(description_file) +else: + t = TestDescr() + t.test_name = test_name + parse_description_string(t, description) + process_testcase(t) + +# Close Makefile fragment output +makefile.close() diff --git a/support/Depend b/support/Depend new file mode 100644 index 0000000000..7e7d5dc67c --- /dev/null +++ b/support/Depend @@ -0,0 +1 @@ +elf diff --git a/support/Makefile b/support/Makefile index bb9889efb4..a5f21ed43b 100644 --- a/support/Makefile +++ b/support/Makefile @@ -233,10 +233,16 @@ others-noinstall += shell-container echo-container true-container others += $(LINKS_DSO_PROGRAM) others-noinstall += $(LINKS_DSO_PROGRAM) +others += test-run-command +others-static += test-run-command +others-noinstall += test-run-command +LDLIBS-test-run-command = $(libsupport) + $(objpfx)test-container : $(libsupport) $(objpfx)shell-container : $(libsupport) $(objpfx)echo-container : $(libsupport) $(objpfx)true-container : $(libsupport) +$(objpfx)test-run-command : $(libsupport) $(common-objpfx)elf/static-stubs.o tests = \ README-testing \ diff --git a/support/support_test_main.c b/support/support_test_main.c index cb72512226..4ce3799956 100644 --- a/support/support_test_main.c +++ b/support/support_test_main.c @@ -227,6 +227,18 @@ run_test_function (int argc, char **argv, const struct test_config *config) while (wait_for_debugger) usleep (1000); + if (config->run_command_mode) + { + /* In run-command-mode, the child process executes the command line + arguments as a new program. */ + char **argv_ = xmalloc (sizeof (char *) * argc); + memcpy (argv_, &argv[1], sizeof (char *) * (argc - 1)); + argv_[argc - 1] = NULL; + execv (argv_[0], argv_); + printf ("error: should not return here\n"); + exit (1); + } + if (config->test_function != NULL) return config->test_function (); else if (config->test_function_argv != NULL) diff --git a/support/test-driver.c b/support/test-driver.c index b0bea46dee..1552f62c9b 100644 --- a/support/test-driver.c +++ b/support/test-driver.c @@ -116,7 +116,9 @@ main (int argc, char **argv) #if defined (TEST_FUNCTION) && defined (TEST_FUNCTON_ARGV) # error TEST_FUNCTION and TEST_FUNCTION_ARGV cannot be defined at the same time #endif -#if defined (TEST_FUNCTION) +#ifdef RUN_COMMAND_MODE + test_config.run_command_mode = 1; +#elif defined (TEST_FUNCTION) test_config.test_function = TEST_FUNCTION; #elif defined (TEST_FUNCTION_ARGV) test_config.test_function_argv = TEST_FUNCTION_ARGV; diff --git a/support/test-driver.h b/support/test-driver.h index 8d4f38275d..b44c0ff033 100644 --- a/support/test-driver.h +++ b/support/test-driver.h @@ -36,6 +36,7 @@ struct test_config int expected_signal; /* If non-zero, expect termination by signal. */ char no_mallopt; /* Boolean flag to disable mallopt. */ char no_setvbuf; /* Boolean flag to disable setvbuf. */ + char run_command_mode; /* Boolean flag to indicate run-command-mode. */ const char *optstring; /* Short command line options. */ }; diff --git a/support/test-run-command.c b/support/test-run-command.c new file mode 100644 index 0000000000..61560d7bfb --- /dev/null +++ b/support/test-run-command.c @@ -0,0 +1,22 @@ +/* Main program for test-run-command support utility. + Copyright (C) 2021 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 + . */ + +/* This is basically a configuration of test-driver.c into a general + command-line program runner. */ +#define RUN_COMMAND_MODE +#include