elf: Testing infrastructure for ld.so DSO sorting (BZ #17645)

This is the first of a 2-part patch set that fixes slow DSO sorting behavior in
the dynamic loader, as reported in BZ #17645. In order to facilitate such a
large modification to the dynamic loader, this first patch implements a testing
framework for validating shared object sorting behavior, to enable comparison
between old/new sorting algorithms, and any later enhancements.

This testing infrastructure consists of a Python script
scripts/dso-ordering-test.py' which takes in a description language, consisting
of strings that describe a set of link dependency relations between DSOs, and
generates testcase programs and Makefile fragments to automatically test the
described situation, for example:

  a->b->c->d          # four objects linked one after another

  a->[bc]->d;b->c     # a depends on b and c, which both depend on d,
                      # b depends on c (b,c linked to object a in fixed order)

  a->b->c;{+a;%a;-a}  # a, b, c serially dependent, main program uses
                      # dlopen/dlsym/dlclose on object a

  a->b->c;{}!->[abc]  # a, b, c serially dependent; multiple tests generated
                      # to test all permutations of a, b, c ordering linked
                      # to main program

 (Above is just a short description of what the script can do, more
  documentation is in the script comments.)

Two files containing several new tests, elf/dso-sort-tests-[12].def are added,
including test scenarios for BZ #15311 and Redhat issue #1162810 [1].

Due to the nature of dynamic loader tests, where the sorting behavior and test
output occurs before/after main(), generating testcases to use
support/test-driver.c does not suffice to control meaningful timeout for ld.so.
Therefore a new utility program 'support/test-run-command', based on
test-driver.c/support_test_main.c has been added. This does the same testcase
control, but for a program specified through a command-line rather than at the
source code level. This utility is used to run the dynamic loader testcases
generated by dso-ordering-test.py.

[1] https://bugzilla.redhat.com/show_bug.cgi?id=1162810

Signed-off-by: Chung-Lin Tang  <cltang@codesourcery.com>
Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

10 files changed, 1884 insertions, 1 deletions

diff --git a/elf/Makefile b/elf/Makefile
index bf45d8ee24..bdcf4cb885 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -477,6 +477,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)<testcase-name>-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..873ddf55d9
--- /dev/null
+++ b/elf/dso-sort-tests-1.def
@@ -0,0 +1,66 @@
+# 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>{}<a<b<c
+
+# Sequence including 2 dependent DSOs not at the end of the graph.
+tst-dso-ordering2: a->b->[cd]->e
+output: e>d>c>b>a>{}<a<b<c<d<e
+
+# Complex order with 3 "layers" of full dependencies
+tst-dso-ordering3: a->[bc]->[def]->[gh]->i
+output: i>h>g>f>e>d>c>b>a>{}<a<b<c<d<e<f<g<h<i
+
+# Sequence including 2 dependent DSOs at the end of the graph.
+# Additionally the same dependencies appear in two paths.
+tst-dso-ordering4: a->b->[de];a->c->d->e
+output: e>d>c>b>a>{}<a<b<c<d<e
+
+# Test that b->c cross link is respected correctly
+tst-dso-ordering5: a!->[bc]->d;b->c
+output: d>c>b>a>{}<a<b<c<d
+
+# First DSO fully dependent on 4 DSOs, with another DSO at the end of chain.
+tst-dso-ordering6: a->[bcde]->f
+output: f>e>d>c>b>a>{}<a<b<c<d<e<f
+
+# Sequence including 2 dependent and 3 dependent DSOs, and one of the
+# dependent DSOs is dependent on an earlier DSO.
+tst-dso-ordering7: a->[bc];b->[cde];e->f
+output: f>e>d>c>b>a>{}<a<b<c<d<e<f
+
+# Sequence where the DSO c is unerlinked and calls a function in DSO a which
+# is technically a cycle.  The main executable depends on the first two DSOs.
+# Note: This test has unspecified behavior.
+tst-dso-ordering8: a->b->c=>a;{}->[ba]
+output: c>b>a>{}<a<b<c
+
+# Generate the permutation of DT_NEEDED order between the main binary and
+# all 5 DSOs; all link orders should produce exact same init/fini ordering
+tst-dso-ordering9: a->b->c->d->e;{}!->[abcde]
+output: e>d>c>b>a>{}<a<b<c<d<e
+
+# Test if init/fini ordering behavior is proper, despite main program with
+# an soname that may cause confusion
+tst-dso-ordering10: {}->a->b->c;soname({})=c
+output: b>a>{}<a<b
+
+# Complex example from Bugzilla #15311, under-linked and with circular
+# relocation(dynamic) dependencies. While this is technically unspecified, the
+# presumed reasonable practical behavior is for the destructor order to respect
+# the static DT_NEEDED links (here this means the 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
+xfail_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[<a<c<d<g<f<b<e];}
+output(glibc.rtld.dynamic_sort=2): {+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[<g<f<a<b<c<d<e];}
diff --git a/elf/dso-sort-tests-2.def b/elf/dso-sort-tests-2.def
new file mode 100644
index 0000000000..b79e79ecb7
--- /dev/null
+++ b/elf/dso-sort-tests-2.def
@@ -0,0 +1,614 @@
+# Large DSO sorting testcase adapted from Red Hat Bugzilla 1162810
+#
+# Note that below we specify different expected outputs between dynamic_sort=1
+# and dynamic_sort=2 algorithms, due to circular dependencies in the testcase
+# causing different sorting behavior.  These expected outputs are what the two
+# algorithms currently produce, and are used for regression comparison tests.
+# They are not "definitively" correct outputs, for circular dependencies
+# inherently have unspecified behavior.
+
+xtest(tst-redhat-1162810):
+{}->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)