Bug 1162810 - glibc: [RFE] Improve performance of dynamic loader for deeply nested DSO dependencies.
Summary: glibc: [RFE] Improve performance of dynamic loader for deeply nested DSO depe...
Keywords:
Status: CLOSED ERRATA
Alias: None
Product: Fedora
Classification: Fedora
Component: glibc
Version: rawhide
Hardware: Unspecified
OS: Unspecified
unspecified
unspecified
Target Milestone: ---
Assignee: glibc team
QA Contact: Fedora Extras Quality Assurance
URL:
Whiteboard:
Depends On:
Blocks: 1159809 1305145 2032647
TreeView+ depends on / blocked
 
Reported: 2014-11-11 18:16 UTC by Paulo Andrade
Modified: 2022-04-14 09:59 UTC (History)
9 users (show)

Fixed In Version: glibc-2.34-18.fc35 glibc-2.34.9000-16.fc36
Doc Type: Bug Fix
Doc Text:
Clone Of:
Environment:
Last Closed: 2019-10-23 15:22:13 UTC
Type: Bug
Embargoed:

Attachments (Terms of Use)
Experimental glibc-dso_deps.patch (7.70 KB, patch)
2014-11-11 18:16 UTC, Paulo Andrade 		no flags Details | Diff
Experimental glibc-dso_deps.patch (11.07 KB, patch)
2014-11-13 23:34 UTC, Paulo Andrade 		no flags Details | Diff
Experimental glibc-dso_deps.patch (11.32 KB, patch)
2014-11-14 17:34 UTC, Paulo Andrade 		no flags Details | Diff
dso_deps.c (10.24 KB, text/plain)
2015-03-08 16:58 UTC, Paulo Andrade 		no flags Details
dso_1 (14 bytes, text/plain)
2015-03-08 17:04 UTC, Paulo Andrade 		no flags Details
dso_2 (20 bytes, text/plain)
2015-03-08 17:09 UTC, Paulo Andrade 		no flags Details
dso_3 (16.12 KB, text/plain)
2015-03-08 17:13 UTC, Paulo Andrade 		no flags Details
dso_4 (20 bytes, text/plain)
2015-03-08 17:14 UTC, Paulo Andrade 		no flags Details
dso_5 (20 bytes, text/plain)
2015-03-08 17:16 UTC, Paulo Andrade 		no flags Details
Patch version that needs an environment variable to enable the new sort (11.22 KB, patch)
2015-03-08 19:37 UTC, Paulo Andrade 		no flags Details | Diff
Add an extra variant that better matches current glibc sort (sort in reverse order) (11.62 KB, text/x-csrc)
2015-03-10 19:34 UTC, Paulo Andrade 		no flags Details
Show Obsolete (2) View All


Links
System ID Private Priority Status Summary Last Updated
Red Hat Bugzilla 1159809 1 high CLOSED glibc: Improve performance of dynamic loader for deeply nested DSO dependencies. 2023-12-15 15:50:01 UTC
Sourceware 15310 0 P2 NEW _dl_sort_fini is O(n^3) causing slow exit when many dsos 2021-01-04 17:43:03 UTC
Sourceware 17645 0 P2 NEW RFE: Improve performance of dynamic loader for deeply nested DSO dependencies. 2021-01-04 17:43:03 UTC

Description Paulo Andrade 2014-11-11 18:16:51 UTC 
Created attachment 956382 [details]
Experimental glibc-dso_deps.patch

There are 3 instances of a very cpu intensive loop (at
least for a sample test case) in glibc when sorting DSO
dependencies. The 3 instances are slightly different:

dl-open.c: "i" start at 0

dl-deps.c: "i" starts at 1, with the comment
  /* We can skip looking for the binary itself which is at the front
     of the search list for the main namespace.  */

dl-fini.c: "i" starts at 0 or 1, like this:
   /* We can skip looking for the binary itself which is at the front
      of the search list for the main namespace.  */
  unsigned int i = ns == LM_ID_BASE;
Also in dl-fini.c there is the extra check for
ordering based on "maps[k]->l_reldeps"
information.

I am running the attached experimental patch in rawhide,
and a slightly different variant on rhel-7 and do not see
any problems.
Comment 1 Paulo Andrade 2014-11-11 18:21:53 UTC 
Without the patch, running the first command in the
test case in #1159809, it takes 8 sec, and perf output
looks like this:

 31,24%  timedlopen  ld-2.17.so         [.] _dl_map_object_deps
 18,36%  timedlopen  ld-2.17.so         [.] _wordcopy_fwd_aligned
 16,50%  timedlopen  ld-2.17.so         [.] _dl_sort_fini
 15,47%  timedlopen  ld-2.17.so         [.] dl_open_worker
 13,08%  timedlopen  ld-2.17.so         [.] _wordcopy_fwd_dest_aligned
  4,95%  timedlopen  ld-2.17.so         [.] memmove
  0,07%  timedlopen  ld-2.17.so         [.] do_lookup_x

with the patch, it takes 10ms, and perf output
looks like this:

 17,45%  timedlopen  ld-2.17.so         [.] do_lookup_x
  9,54%  timedlopen  ld-2.17.so         [.] strcmp
  6,91%  timedlopen  ld-2.17.so         [.] _dl_map_object_deps
  6,12%  timedlopen  ld-2.17.so         [.] _dl_name_match_p
  4,35%  timedlopen  ld-2.17.so         [.] _dl_sort_fini
  4,33%  timedlopen  ld-2.17.so         [.] dl_open_worker
Comment 2 Paulo Andrade 2014-11-12 19:07:19 UTC 
I was trying to find some test case where it would cause
problems, etc. Well, glibc make check already has
tst-initorder ...

Calling p0 tst-initorder, it is like this:

p0 -> a4 a1 b2 a3 b1 a2 p0
a1 -> a1
a2 -> a2
a3 -> b2 b1 a2 a1 a3
a4 -> a3 b2 b1 a2 a1 a4
b1 -> b1
b2 -> b1 a2 a1 b2

where -> stands for link order, or implicit dependency
on "self".

Since a1, a2 and b1 do not have dependencies on other
DSO, their order should not matter much.

But a stable sort, and the test case expects:

p0 a4 a3 b2 b1 a2 a1


My initial algorithm (dumb bubble sort) was just based on
simple observation, and I was assuming ld.so would somehow
not leave "indirect" dependencies in the l_initfini vector.


The new algorithm is a kind of "stable" topological sort.
The "template" (as there are 3 slightly different variants
of the sorting) is this:

---%<---
void weight(struct link_map **maps, size_t nmaps, char *seen, unsigned int *w) {
    unsigned int i, c;
    struct link_map *m, **r;
    for (i = 0; i < nmaps; ++i) {
	m = maps[i];
	if ((r = m->l_initfini)) {
	    c = 0;
	    while (*r) {
		if (*r != m && !seen[(*r)->l_idx])
		    ++c;
		++r;
	    }
	    w[i] = c;
	}
	else
	    w[i] = 0;
    }
}

static void sort (struct link_map **maps, size_t nmaps)
{
    unsigned int	 c, i, k;
    unsigned int	 w[nmaps];
    char		 seen[nmaps];
    struct link_map	*t;
    memset(seen, 0, nmaps);
    weight(maps, k = nmaps, seen, w);
    c = 0;
    while (k > 1) {
	for (i = 0; i < k; ++i) {
	    if (w[i] == c) {
		--k;
		seen[maps[i]->l_idx] = 1;
		t = maps[k];
		maps[k] = maps[i];
		maps[i] = t;
		weight(maps, k, seen, w);
		c = -1;
		break;
	    }
	}
	++c;
    }
}
---%<---

By "stable" I mean it does not change input order if two entries
have the same "weight". It does not try to do anything smart
when finding a cycle (when c > 0 in the sort loop), and is also
a very fast algorithm (virtually no cost vs 8+ sec cost for the
test case).

I am far more confident with the new test, as it pass the glibc
make check test, is very fast and should at least leave data in
a stable sorting in case of loops.

Any comments?
Comment 3 Paulo Andrade 2014-11-13 23:34:22 UTC 
Created attachment 957371 [details]
Experimental glibc-dso_deps.patch

With this patch, rawhide glibc "make check" pass all tests.

Note that it adds an extra dependency in elf/Makefile,
because otherwise it would do a different sorting on
constructors in a test case, if compared to the "current"
code.

The test that would fail without adding an extra
dependency expects:

start_a1
start_a2
start_b1
start_b2
start_a3
start_a4
main
finish_a4
finish_a3
finish_b2
finish_b1
finish_a2
finish_a1

but "a1" and "b1" do not have any dependencies, and
without the elf/Makefile patch it would result in:

start_a1
start_b1
start_a2
start_b2
start_a3
start_a4
main
finish_a4
finish_a3
finish_b2
finish_b1
finish_a2
finish_a1

The initial input is for the above constructors is:

[0] = ""		()
[1] = a4		(a4 a3 libc.so)
[2] = a1		(a1 libc.so)
[3] = b2		(b2 b1 a2 libc.so)
[4] = libc.so		(libc.so ld.so)
[5] = a3		(a3 b2 b1 libc.so)
[6] = b1		(b1 libc.so)
[7] = a2		(a2 a1 libc.so)
[8] = ld.so		()

In () is the l_initfini vector.

Note that the "proposed", but still experimental patch only
moves entries once during the sorting, contrary to the
current code that may waste way too much cpu on memmove
calls.
Comment 4 Paulo Andrade 2014-11-14 17:34:59 UTC 
Created attachment 957686 [details]
Experimental glibc-dso_deps.patch

Add safety checks to the patch, as it had some issues
on "complex" applications.

The change is basically this:

+  /* l_idx not set or is unreliable at this point */
+  for (i = 0; i < nmaps; ++i)
+    {
+      if (maps[i]->l_idx >= 0)
+	maps[i]->l_idx = i;
+    }

and added guard for "l_idx < 0" that is a flag when unloading
a shared object, but just in case check it in other places.

It also sets l_idx (if not < 0) because on dlopen there will
be commonly several entries with the same l_idx, but the
patch wants unique values, and those are only added
by glibc when unloading. Search for l_idx in
elf/dl-close.c ...
Comment 5 Paulo Andrade 2015-03-08 16:58:54 UTC 
Created attachment 999360 [details]
dso_deps.c

This is a simple program to to allow comparing
the initially proposed patch sorting, the current
glibc sorting, and a modified patch that attempts
to break cycles at the point where it leaves less
interdependency (if there are multiple cycles,
it attempts to break the big ones first).

The input for the program is a file in the
format:

NAME [DEP1...DEPN]

entries. Note that while it is quite close to,
it is not exactly the same input format of
tsort.

Compile the test program with:

gcc -O0 -g3 dso_deps.c -o dso_deps
Comment 6 Paulo Andrade 2015-03-08 17:04:19 UTC 
Created attachment 999361 [details]
dso_1

Sample run:

--8<--
$ ./dso_deps dso_1 $ ./dso_deps -v dso_1 
a(b c)
b(c)
c(a)
ORG: a b c
NEW: c a b
Real time: 4e-06 sec

BST: a b c
Real time: 3e-06 sec

CUR: a b c
Real time: 5e-06 sec
--8<--

The new algorithm finds a cycle, so, in the second
pass it chooses to break in "b" (last entry), after
that, it finds that "c" depends on "a".

The "best_sort" is the original algorithm choosing
the best, not the first, entry with the same weight,
and happens to give the same result as current glibc,
but note that there is no exact solution, as it is
a full cycle (but the best solution is to have "a"
last, i.e. first element in the list).
Comment 7 Paulo Andrade 2015-03-08 17:09:40 UTC 
Created attachment 999364 [details]
dso_2

---8<---
$ ./dso_deps -v dso_2
a(b c)
b(c d e)
c()
d()
e(f)
f()
ORG: a b c d e f
NEW: a b d e f c
Real time: 5e-06 sec

BST: a b e f c d
Real time: 3e-06 sec

CUR: a b c d e f
Real time: 3e-06 sec
---8<---

In this case:
  "b" and "c" must be after "a" in the output
  "c", "d" and "e" must be after "b"
  "f" must be after "e"

All solutions are valid. The "BST" output, puts
the smallest "isles" last (to be loaded last or
unloaded first).
Comment 8 Paulo Andrade 2015-03-08 17:13:29 UTC 
Created attachment 999365 [details]
dso_3

This is actually the test case that caused the patch
proposal:

---8<---
$ ./dso_deps -v dso_3
A101(B101 B163 B122 B181)
B101(C101 C164 C123 C182)
B163(C163 C138 C197 C156)
B122(C122 C181 C140 C199)
B181(C181 C124 C183 C142)
A102(B102 B140 B199 B158)
B102(C102 C141 C200 C159)
B140(C140 C167 C126 C185)
B199(C199 C110 C169 C128)
B158(C158 C153 C112 C171)
A103(B103 B117 B176 B135)
B103(C103 C118 C177 C136)
B117(C117 C196 C155 C114)
B176(C176 C139 C198 C157)
B135(C135 C182 C141 C200)
A104(B104 B194 B153 B112)
B104(C104 C195 C154 C113)
B194(C194 C125 C184 C143)
B153(C153 C168 C127 C186)
B112(C112 C111 C170 C129)
A105(B105 B171 B130 B189)
B105(C105 C172 C131 C190)
B171(C171 C154 C113 C172)
B130(C130 C197 C156 C115)
B189(C189 C140 C199 C158)
A106(B106 B148 B107 B166)
B106(C106 C149 C108 C167)
B148(C148 C183 C142 C101)
B107(C107 C126 C185 C144)
B166(C166 C169 C128 C187)
A107(B107 B125 B184 B143)
B125(C125 C112 C171 C130)
B184(C184 C155 C114 C173)
B143(C143 C198 C157 C116)
A108(B108 B102 B161 B120)
B108(C108 C103 C162 C121)
B161(C161 C184 C143 C102)
B120(C120 C127 C186 C145)
A109(B109 B179 B138 B197)
B109(C109 C180 C139 C198)
B179(C179 C170 C129 C188)
B138(C138 C113 C172 C131)
B197(C197 C156 C115 C174)
A110(B110 B156 B115 B174)
B110(C110 C157 C116 C175)
B156(C156 C199 C158 C117)
B115(C115 C142 C101 C160)
B174(C174 C185 C144 C103)
A111(B111 B133 B192 B151)
B111(C111 C134 C193 C152)
B133(C133 C128 C187 C146)
B192(C192 C171 C130 C189)
B151(C151 C114 C173 C132)
A112(B112 B110 B169 B128)
B169(C169 C200 C159 C118)
B128(C128 C143 C102 C161)
A113(B113 B187 B146 B105)
B113(C113 C188 C147 C106)
B187(C187 C186 C145 C104)
B146(C146 C129 C188 C147)
A114(B114 B164 B123 B182)
B114(C114 C165 C124 C183)
B164(C164 C115 C174 C133)
B123(C123 C158 C117 C176)
B182(C182 C101 C160 C119)
A115(B115 B141 B200 B159)
B141(C141 C144 C103 C162)
B200(C200 C187 C146 C105)
B159(C159 C130 C189 C148)
A116(B116 B118 B177 B136)
B116(C116 C119 C178 C137)
B118(C118 C173 C132 C191)
B177(C177 C116 C175 C134)
B136(C136 C159 C118 C177)
A117(B117 B195 B154 B113)
B195(C195 C102 C161 C120)
B154(C154 C145 C104 C163)
A118(B118 B172 B131 B190)
B172(C172 C131 C190 C149)
B131(C131 C174 C133 C192)
B190(C190 C117 C176 C135)
A119(B119 B149 B108 B167)
B119(C119 C150 C109 C168)
B149(C149 C160 C119 C178)
B167(C167 C146 C105 C164)
A120(B120 B126 B185 B144)
B126(C126 C189 C148 C107)
B185(C185 C132 C191 C150)
B144(C144 C175 C134 C193)
A121(B121 B103 B162)
B121(C121 C104 C163 C122)
B162(C162 C161 C120 C179)
A122(B122 B180 B139 B198)
B180(C180 C147 C106 C165)
B139(C139 C190 C149 C108)
B198(C198 C133 C192 C151)
A123(B123 B157 B116 B175)
B157(C157 C176 C135 C194)
B175(C175 C162 C121 C180)
A124(B124 B134 B193 B152)
B124(C124 C135 C194 C153)
B134(C134 C105 C164 C123)
B193(C193 C148 C107 C166)
B152(C152 C191 C150 C109)
A125(B125 B111 B170 B129)
B170(C170 C177 C136 C195)
B129(C129 C120 C179 C138)
A126(B126 B188 B147 B106)
B188(C188 C163 C122 C181)
B147(C147 C106 C165 C124)
A127(B127 B165 B124 B183)
B127(C127 C166 C125 C184)
B165(C165 C192 C151 C110)
B183(C183 C178 C137 C196)
A128(B128 B142 B101 B160)
B142(C142 C121 C180 C139)
B160(C160 C107 C166 C125)
A129(B129 B119 B178 B137)
B178(C178 C193 C152 C111)
B137(C137 C136 C195 C154)
A130(B130 B196 B155 B114)
B196(C196 C179 C138 C197)
B155(C155 C122 C181 C140)
A131(B131 B173 B132 B191)
B173(C173 C108 C167 C126)
B132(C132 C151 C110 C169)
B191(C191 C194 C153 C112)
A132(B132 B150 B109 B168)
B150(C150 C137 C196 C155)
B168(C168 C123 C182 C141)
A133(B133 B127 B186 B145)
B186(C186 C109 C168 C127)
B145(C145 C152 C111 C170)
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)
C101(A165 A124)
C164(A199 A158)
C123(A161 A120)
C182(A123 A182)
C102(A183 A142)
C141(A185 A144)
C200(A147 A106)
C159(A109 A168)
C103(A101 A160)
C118(A171 A130)
C177(A133 A192)
C136(A195 A154)
C104(A119 A178)
C195(A157 A116)
C154(A119 A178)
C113(A181 A140)
C105(A137 A196)
C172(A143 A102)
C131(A105 A164)
C190(A167 A126)
C106(A155 A114)
C149(A129 A188)
C108(A191 A150)
C167(A153 A112)
C107(A173 A132)
C126(A115 A174)
C185(A177 A136)
C144(A139 A198)
C162(A163 A122)
C121(A125 A184)
C109(A109 A168)
C180(A187 A146)
C139(A149 A108)
C198(A111 A170)
C110(A127 A186)
C157(A173 A132)
C116(A135 A194)
C175(A197 A156)
C111(A145 A104)
C134(A159 A118)
C193(A121 A180)
C152(A183 A142)
C112(A163 A122)
C170(A107 A166)
C129(A169 A128)
C188(A131 A190)
C147(A193 A152)
C114(A199 A158)
C165(A117 A176)
C124(A179 A138)
C183(A141 A200)
C115(A117 A176)
C142(A103 A162)
C160(A127 A186)
C119(A189 A148)
C178(A151 A110)
C137(A113 A172)
C117(A153 A112)
C196(A175 A134)
C155(A137 A196)
C173(A161 A120)
C132(A123 A182)
C191(A185 A144)
C150(A147 A106)
C168(A171 A130)
C120(A107 A166)
C127(A133 A192)
C186(A195 A154)
C145(A157 A116)
C163(A181 A140)
C122(A143 A102)
C181(A105 A164)
C140(A167 A126)
C199(A129 A188)
C158(A191 A150)
C176(A115 A174)
C135(A177 A136)
C194(A139 A198)
C153(A101 A160)
C125(A197 A156)
C171(A125 A184)
C130(A187 A146)
C189(A149 A108)
C148(A111 A170)
C166(A135 A194)
C184(A159 A118)
C128(A151 A110)
C143(A121 A180)
C161(A145 A104)
C179(A169 A128)
C138(A131 A190)
C197(A193 A152)
C156(A155 A114)
C174(A179 A138)
C133(A141 A200)
C192(A103 A162)
C151(A165 A124)
C169(A189 A148)
C187(A113 A172)
C146(A175 A134)
M11X11(M13X14 M12X13 M12X12 M12X11)
M13X14(M15X17 M14X16 M14X15 M14X14)
M12X13(M14X21 M13X20 M13X19 M13X18)
M12X12(M14X25 M13X24 M13X23 M13X22)
M12X11(M14X14 M13X13 M13X12 M13X11)
M11X12(M13X25 M12X24 M12X23 M12X22)
M13X25(M15X18 M14X17 M14X16 M14X15)
M12X24(M14X22 M13X21 M13X20 M13X19)
M12X23(M14X11 M13X25 M13X24 M13X23)
M12X22(M14X15 M13X14 M13X13 M13X12)
M11X13(M13X21 M12X20 M12X19 M12X18)
M13X21(M15X19 M14X18 M14X17 M14X16)
M12X20(M14X23 M13X22 M13X21 M13X20)
M12X19(M14X12 M13X11 M13X25 M13X24)
M12X18(M14X16 M13X15 M13X14 M13X13)
M11X14(M13X17 M12X16 M12X15 M12X14)
M13X17(M15X20 M14X19 M14X18 M14X17)
M12X16(M14X24 M13X23 M13X22 M13X21)
M12X15(M14X13 M13X12 M13X11 M13X25)
M12X14(M14X17 M13X16 M13X15 M13X14)
M11X15(M13X13 M12X12 M12X11 M12X25)
M13X13(M15X21 M14X20 M14X19 M14X18)
M12X25(M14X18 M13X17 M13X16 M13X15)
M11X16(M13X24 M12X23 M12X22 M12X21)
M13X24(M15X22 M14X21 M14X20 M14X19)
M12X21(M14X19 M13X18 M13X17 M13X16)
M11X17(M13X20 M12X19 M12X18 M12X17)
M13X20(M15X23 M14X22 M14X21 M14X20)
M12X17(M14X20 M13X19 M13X18 M13X17)
M11X18(M13X16 M12X15 M12X14 M12X13)
M13X16(M15X24 M14X23 M14X22 M14X21)
M11X19(M13X12 M12X11 M12X25 M12X24)
M13X12(M15X25 M14X24 M14X23 M14X22)
M11X20(M13X23 M12X22 M12X21 M12X20)
M13X23(M15X11 M14X25 M14X24 M14X23)
M11X21(M13X19 M12X18 M12X17 M12X16)
M13X19(M15X12 M14X11 M14X25 M14X24)
M11X22(M13X15 M12X14 M12X13 M12X12)
M13X15(M15X13 M14X12 M14X11 M14X25)
M11X23(M13X11 M12X25 M12X24 M12X23)
M13X11(M15X14 M14X13 M14X12 M14X11)
M11X24(M13X22 M12X21 M12X20 M12X19)
M13X22(M15X15 M14X14 M14X13 M14X12)
M11X25(M13X18 M12X17 M12X16 M12X15)
M13X18(M15X16 M14X15 M14X14 M14X13)
M14X14(M16X17 M15X16 M15X15 M15X14)
M14X25(M16X18 M15X17 M15X16 M15X15)
M14X21(M16X19 M15X18 M15X17 M15X16)
M14X17(M16X20 M15X19 M15X18 M15X17)
M14X13(M16X21 M15X20 M15X19 M15X18)
M14X24(M16X22 M15X21 M15X20 M15X19)
M14X20(M16X23 M15X22 M15X21 M15X20)
M14X16(M16X24 M15X23 M15X22 M15X21)
M14X12(M16X25 M15X24 M15X23 M15X22)
M14X23(M16X11 M15X25 M15X24 M15X23)
M14X19(M16X12 M15X11 M15X25 M15X24)
M14X15(M16X13 M15X12 M15X11 M15X25)
M14X11(M16X14 M15X13 M15X12 M15X11)
M14X22(M16X15 M15X14 M15X13 M15X12)
M14X18(M16X16 M15X15 M15X14 M15X13)
M15X14(M17X17 M16X16 M16X15 M16X14)
M15X25(M17X18 M16X17 M16X16 M16X15)
M15X21(M17X19 M16X18 M16X17 M16X16)
M15X17(M17X20 M16X19 M16X18 M16X17)
M15X13(M17X21 M16X20 M16X19 M16X18)
M15X24(M17X22 M16X21 M16X20 M16X19)
M15X20(M17X23 M16X22 M16X21 M16X20)
M15X16(M17X24 M16X23 M16X22 M16X21)
M15X12(M17X25 M16X24 M16X23 M16X22)
M15X23(M17X11 M16X25 M16X24 M16X23)
M15X19(M17X12 M16X11 M16X25 M16X24)
M15X15(M17X13 M16X12 M16X11 M16X25)
M15X11(M17X14 M16X13 M16X12 M16X11)
M15X22(M17X15 M16X14 M16X13 M16X12)
M15X18(M17X16 M16X15 M16X14 M16X13)
M16X14(M18X17 M17X16 M17X15 M17X14)
M16X25(M18X18 M17X17 M17X16 M17X15)
M16X21(M18X19 M17X18 M17X17 M17X16)
M16X17(M18X20 M17X19 M17X18 M17X17)
M16X13(M18X21 M17X20 M17X19 M17X18)
M16X24(M18X22 M17X21 M17X20 M17X19)
M16X20(M18X23 M17X22 M17X21 M17X20)
M16X16(M18X24 M17X23 M17X22 M17X21)
M16X12(M18X25 M17X24 M17X23 M17X22)
M16X23(M18X11 M17X25 M17X24 M17X23)
M16X19(M18X12 M17X11 M17X25 M17X24)
M16X15(M18X13 M17X12 M17X11 M17X25)
M16X11(M18X14 M17X13 M17X12 M17X11)
M16X22(M18X15 M17X14 M17X13 M17X12)
M16X18(M18X16 M17X15 M17X14 M17X13)
M17X14(M19X17 M18X16 M18X15 M18X14)
M17X25(M19X18 M18X17 M18X16 M18X15)
M17X21(M19X19 M18X18 M18X17 M18X16)
M17X17(M19X20 M18X19 M18X18 M18X17)
M17X13(M19X21 M18X20 M18X19 M18X18)
M17X24(M19X22 M18X21 M18X20 M18X19)
M17X20(M19X23 M18X22 M18X21 M18X20)
M17X16(M19X24 M18X23 M18X22 M18X21)
M17X12(M19X25 M18X24 M18X23 M18X22)
M17X23(M19X11 M18X25 M18X24 M18X23)
M17X19(M19X12 M18X11 M18X25 M18X24)
M17X15(M19X13 M18X12 M18X11 M18X25)
M17X11(M19X14 M18X13 M18X12 M18X11)
M17X22(M19X15 M18X14 M18X13 M18X12)
M17X18(M19X16 M18X15 M18X14 M18X13)
M18X14(M20X17 M19X16 M19X15 M19X14)
M18X25(M20X18 M19X17 M19X16 M19X15)
M18X21(M20X19 M19X18 M19X17 M19X16)
M18X17(M20X20 M19X19 M19X18 M19X17)
M18X13(M20X21 M19X20 M19X19 M19X18)
M18X24(M20X22 M19X21 M19X20 M19X19)
M18X20(M20X23 M19X22 M19X21 M19X20)
M18X16(M20X24 M19X23 M19X22 M19X21)
M18X12(M20X25 M19X24 M19X23 M19X22)
M18X23(M20X11 M19X25 M19X24 M19X23)
M18X19(M20X12 M19X11 M19X25 M19X24)
M18X15(M20X13 M19X12 M19X11 M19X25)
M18X11(M20X14 M19X13 M19X12 M19X11)
M18X22(M20X15 M19X14 M19X13 M19X12)
M18X18(M20X16 M19X15 M19X14 M19X13)
M19X14(M21X17 M20X16 M20X15 M20X14)
M19X25(M21X18 M20X17 M20X16 M20X15)
M19X21(M21X19 M20X18 M20X17 M20X16)
M19X17(M21X20 M20X19 M20X18 M20X17)
M19X13(M21X21 M20X20 M20X19 M20X18)
M19X24(M21X22 M20X21 M20X20 M20X19)
M19X20(M21X23 M20X22 M20X21 M20X20)
M19X16(M21X24 M20X23 M20X22 M20X21)
M19X12(M21X25 M20X24 M20X23 M20X22)
M19X23(M21X11 M20X25 M20X24 M20X23)
M19X19(M21X12 M20X11 M20X25 M20X24)
M19X15(M21X13 M20X12 M20X11 M20X25)
M19X11(M21X14 M20X13 M20X12 M20X11)
M19X22(M21X15 M20X14 M20X13 M20X12)
M19X18(M21X16 M20X15 M20X14 M20X13)
M20X14(M22X17 M21X16 M21X15 M21X14)
M20X25(M22X18 M21X17 M21X16 M21X15)
M20X21(M22X19 M21X18 M21X17 M21X16)
M20X17(M22X20 M21X19 M21X18 M21X17)
M20X13(M22X21 M21X20 M21X19 M21X18)
M20X24(M22X22 M21X21 M21X20 M21X19)
M20X20(M22X23 M21X22 M21X21 M21X20)
M20X16(M22X24 M21X23 M21X22 M21X21)
M20X12(M22X25 M21X24 M21X23 M21X22)
M20X23(M22X11 M21X25 M21X24 M21X23)
M20X19(M22X12 M21X11 M21X25 M21X24)
M20X15(M22X13 M21X12 M21X11 M21X25)
M20X11(M22X14 M21X13 M21X12 M21X11)
M20X22(M22X15 M21X14 M21X13 M21X12)
M20X18(M22X16 M21X15 M21X14 M21X13)
M21X14(M23X17 M22X16 M22X15 M22X14)
M21X25(M23X18 M22X17 M22X16 M22X15)
M21X21(M23X19 M22X18 M22X17 M22X16)
M21X17(M23X20 M22X19 M22X18 M22X17)
M21X13(M23X21 M22X20 M22X19 M22X18)
M21X24(M23X22 M22X21 M22X20 M22X19)
M21X20(M23X23 M22X22 M22X21 M22X20)
M21X16(M23X24 M22X23 M22X22 M22X21)
M21X12(M11X11 M23X25 M22X24 M22X23 M22X22)
M21X23(M23X11 M22X25 M22X24 M22X23)
M21X19(M23X12 M22X11 M22X25 M22X24)
M21X15(M23X13 M22X12 M22X11 M22X25)
M21X11(M23X15 M22X14 M22X13 M22X12)
M21X22(M23X15 M22X14 M22X13 M22X12)
M21X18(M23X16 M22X15 M22X14 M22X13)
M22X14(M24X18 M23X17 M23X16 M23X15)
M22X25(M24X19 M23X18 M23X17 M23X16)
M22X21(M24X20 M23X19 M23X18 M23X17)
M22X17(M24X21 M23X20 M23X19 M23X18)
M22X13(M24X22 M23X21 M23X20 M23X19)
M22X24(M24X23 M23X22 M23X21 M23X20)
M22X20(M24X24 M23X23 M23X22 M23X21)
M22X16(M24X25 M23X24 M23X23 M23X22)
M22X12(M12X12 M24X11 M23X25 M23X24 M23X23)
M22X23(M24X12 M23X11 M23X25 M23X24)
M22X19(M24X13 M23X12 M23X11 M23X25)
M22X15(M24X14 M23X13 M23X12 M23X11)
M22X11(M24X16 M23X15 M23X14 M23X13)
M22X22(M24X16 M23X15 M23X14 M23X13)
M22X18(M24X17 M23X16 M23X15 M23X14)
M23X15(M25X15 M24X14 M24X13 M24X12)
M23X25(M25X20 M24X19 M24X18 M24X17)
M23X21(M25X21 M24X20 M24X19 M24X18)
M23X17(M25X22 M24X21 M24X20 M24X19)
M23X13(M25X23 M24X22 M24X21 M24X20)
M23X24(M25X24 M24X23 M24X22 M24X21)
M23X20(M25X25 M24X24 M24X23 M24X22)
M23X16(M25X11 M24X25 M24X24 M24X23)
M23X12(M13X13 M25X12 M24X11 M24X25 M24X24)
M23X23(M25X13 M24X12 M24X11 M24X25)
M23X19(M25X14 M24X13 M24X12 M24X11)
M23X11(M25X17 M24X16 M24X15 M24X14)
M23X22(M25X17 M24X16 M24X15 M24X14)
M23X18(M25X18 M24X17 M24X16 M24X15)
M24X16(M26X12 M25X11 M25X25 M25X24)
M23X14(M25X19 M24X18 M24X17 M24X16)
M24X11(M26X18 M25X17 M25X16 M25X15)
M24X22(M26X18 M25X17 M25X16 M25X15)
M24X18(M26X19 M25X18 M25X17 M25X16)
M24X14(M26X20 M25X19 M25X18 M25X17)
M24X25(M26X21 M25X20 M25X19 M25X18)
M24X21(M26X22 M25X21 M25X20 M25X19)
M24X17(M26X23 M25X22 M25X21 M25X20)
M24X13(M26X24 M25X23 M25X22 M25X21)
M24X24(M26X25 M25X24 M25X23 M25X22)
M24X20(M26X11 M25X25 M25X24 M25X23)
M24X12(M14X14 M26X13 M25X12 M25X11 M25X25)
M24X23(M26X14 M25X13 M25X12 M25X11)
M24X19(M26X15 M25X14 M25X13 M25X12)
M25X17(M27X24 M26X23 M26X22 M26X21)
M24X15(M26X16 M25X15 M25X14 M25X13)
M25X12(M15X15 M27X14 M26X13 M26X12 M26X11)
M25X23(M27X15 M26X14 M26X13 M26X12)
M25X19(M27X16 M26X15 M26X14 M26X13)
M25X15(M27X17 M26X16 M26X15 M26X14)
M25X11(M27X19 M26X18 M26X17 M26X16)
M25X22(M27X19 M26X18 M26X17 M26X16)
M25X18(M27X20 M26X19 M26X18 M26X17)
M25X14(M27X21 M26X20 M26X19 M26X18)
M25X25(M27X22 M26X21 M26X20 M26X19)
M25X21(M27X23 M26X22 M26X21 M26X20)
M25X13(M27X25 M26X24 M26X23 M26X22)
M25X24(M27X11 M26X25 M26X24 M26X23)
M25X20(M27X12 M26X11 M26X25 M26X24)
M26X18(M28X21 M27X20 M27X19 M27X18)
M25X16(M27X13 M26X12 M26X11 M26X25)
M26X13(M28X11 M27X25 M27X24 M27X23)
M26X24(M28X12 M27X11 M27X25 M27X24)
M26X20(M28X13 M27X12 M27X11 M27X25)
M26X16(M28X14 M27X13 M27X12 M27X11)
M26X12(M16X16 M28X15 M27X14 M27X13 M27X12)
M26X23(M28X16 M27X15 M27X14 M27X13)
M26X19(M28X17 M27X16 M27X15 M27X14)
M26X15(M28X18 M27X17 M27X16 M27X15)
M26X11(M28X20 M27X19 M27X18 M27X17)
M26X22(M28X20 M27X19 M27X18 M27X17)
M26X14(M28X22 M27X21 M27X20 M27X19)
M26X25(M28X23 M27X22 M27X21 M27X20)
M26X21(M28X24 M27X23 M27X22 M27X21)
M27X19(M29X18 M28X17 M28X16 M28X15)
M26X17(M28X25 M27X24 M27X23 M27X22)
M27X14(M29X23 M28X22 M28X21 M28X20)
M27X25(M29X24 M28X23 M28X22 M28X21)
M27X21(M29X25 M28X24 M28X23 M28X22)
M27X17(M29X11 M28X25 M28X24 M28X23)
M27X13(M29X12 M28X11 M28X25 M28X24)
M27X24(M29X13 M28X12 M28X11 M28X25)
M27X20(M29X14 M28X13 M28X12 M28X11)
M27X16(M29X15 M28X14 M28X13 M28X12)
M27X12(M17X17 M29X16 M28X15 M28X14 M28X13)
M27X23(M29X17 M28X16 M28X15 M28X14)
M27X15(M29X19 M28X18 M28X17 M28X16)
M27X11(M29X21 M28X20 M28X19 M28X18)
M27X22(M29X21 M28X20 M28X19 M28X18)
M28X20(M30X15 M29X14 M29X13 M29X12)
M27X18(M29X22 M28X21 M28X20 M28X19)
M28X15(M30X20 M29X19 M29X18 M29X17)
M28X11(M30X22 M29X21 M29X20 M29X19)
M28X22(M30X22 M29X21 M29X20 M29X19)
M28X18(M30X23 M29X22 M29X21 M29X20)
M28X14(M30X24 M29X23 M29X22 M29X21)
M28X25(M30X25 M29X24 M29X23 M29X22)
M28X21(M30X11 M29X25 M29X24 M29X23)
M28X17(M30X12 M29X11 M29X25 M29X24)
M28X13(M30X13 M29X12 M29X11 M29X25)
M28X24(M30X14 M29X13 M29X12 M29X11)
M28X16(M30X16 M29X15 M29X14 M29X13)
M28X12(M18X18 M30X17 M29X16 M29X15 M29X14)
M28X23(M30X18 M29X17 M29X16 M29X15)
M29X21(M30X11 M30X25 M30X24)
M28X19(M30X19 M29X18 M29X17 M29X16)
M29X16(M30X16 M30X15 M30X14)
M29X12(M30X17 M30X16 M30X15)
M29X23(M30X18 M30X17 M30X16)
M29X19(M30X19 M30X18 M30X17)
M29X15(M30X20 M30X19 M30X18)
M29X11(M30X22 M30X21 M30X20)
M29X22(M30X22 M30X21 M30X20)
M29X18(M30X23 M30X22 M30X21)
M29X14(M30X24 M30X23 M30X22)
M29X25(M30X25 M30X24 M30X23)
M29X17(M30X12 M30X11 M30X25)
M29X13(M30X13 M30X12 M30X11)
M29X24(M30X14 M30X13 M30X12)
M30X22()
M29X20(M30X15 M30X14 M30X13)
M30X17()
M30X13()
M30X24()
M30X20()
M30X16()
M30X12()
M30X23()
M30X19()
M30X15()
M30X11()
M30X18()
M30X14()
M30X25()
M30X21()
ORG: 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 B125 B184 B143 A108 B108 B161 B120 A109 B109 B179 B138 B197 A110 B110 B156 B115 B174 A111 B111 B133 B192 B151 A112 B169 B128 A113 B113 B187 B146 A114 B114 B164 B123 B182 A115 B141 B200 B159 A116 B116 B118 B177 B136 A117 B195 B154 A118 B172 B131 B190 A119 B119 B149 B167 A120 B126 B185 B144 A121 B121 B162 A122 B180 B139 B198 A123 B157 B175 A124 B124 B134 B193 B152 A125 B170 B129 A126 B188 B147 A127 B127 B165 B183 A128 B142 B160 A129 B178 B137 A130 B196 B155 A131 B173 B132 B191 A132 B150 B168 A133 B186 B145 A134 A135 A136 A137 A138 A139 A140 A141 A142 A143 A144 A145 A146 A147 A148 A149 A150 A151 A152 A153 A154 A155 A156 A157 A158 A159 A160 A161 A162 A163 A164 A165 A166 A167 A168 A169 A170 A171 A172 A173 A174 A175 A176 A177 A178 A179 A180 A181 A182 A183 A184 A185 A186 A187 A188 A189 A190 A191 A192 A193 A194 A195 A196 A197 A198 A199 A200 C101 C164 C123 C182 C102 C141 C200 C159 C103 C118 C177 C136 C104 C195 C154 C113 C105 C172 C131 C190 C106 C149 C108 C167 C107 C126 C185 C144 C162 C121 C109 C180 C139 C198 C110 C157 C116 C175 C111 C134 C193 C152 C112 C170 C129 C188 C147 C114 C165 C124 C183 C115 C142 C160 C119 C178 C137 C117 C196 C155 C173 C132 C191 C150 C168 C120 C127 C186 C145 C163 C122 C181 C140 C199 C158 C176 C135 C194 C153 C125 C171 C130 C189 C148 C166 C184 C128 C143 C161 C179 C138 C197 C156 C174 C133 C192 C151 C169 C187 C146 M11X11 M13X14 M12X13 M12X12 M12X11 M11X12 M13X25 M12X24 M12X23 M12X22 M11X13 M13X21 M12X20 M12X19 M12X18 M11X14 M13X17 M12X16 M12X15 M12X14 M11X15 M13X13 M12X25 M11X16 M13X24 M12X21 M11X17 M13X20 M12X17 M11X18 M13X16 M11X19 M13X12 M11X20 M13X23 M11X21 M13X19 M11X22 M13X15 M11X23 M13X11 M11X24 M13X22 M11X25 M13X18 M14X14 M14X25 M14X21 M14X17 M14X13 M14X24 M14X20 M14X16 M14X12 M14X23 M14X19 M14X15 M14X11 M14X22 M14X18 M15X14 M15X25 M15X21 M15X17 M15X13 M15X24 M15X20 M15X16 M15X12 M15X23 M15X19 M15X15 M15X11 M15X22 M15X18 M16X14 M16X25 M16X21 M16X17 M16X13 M16X24 M16X20 M16X16 M16X12 M16X23 M16X19 M16X15 M16X11 M16X22 M16X18 M17X14 M17X25 M17X21 M17X17 M17X13 M17X24 M17X20 M17X16 M17X12 M17X23 M17X19 M17X15 M17X11 M17X22 M17X18 M18X14 M18X25 M18X21 M18X17 M18X13 M18X24 M18X20 M18X16 M18X12 M18X23 M18X19 M18X15 M18X11 M18X22 M18X18 M19X14 M19X25 M19X21 M19X17 M19X13 M19X24 M19X20 M19X16 M19X12 M19X23 M19X19 M19X15 M19X11 M19X22 M19X18 M20X14 M20X25 M20X21 M20X17 M20X13 M20X24 M20X20 M20X16 M20X12 M20X23 M20X19 M20X15 M20X11 M20X22 M20X18 M21X14 M21X25 M21X21 M21X17 M21X13 M21X24 M21X20 M21X16 M21X12 M21X23 M21X19 M21X15 M21X11 M21X22 M21X18 M22X14 M22X25 M22X21 M22X17 M22X13 M22X24 M22X20 M22X16 M22X12 M22X23 M22X19 M22X15 M22X11 M22X22 M22X18 M23X15 M23X25 M23X21 M23X17 M23X13 M23X24 M23X20 M23X16 M23X12 M23X23 M23X19 M23X11 M23X22 M23X18 M24X16 M23X14 M24X11 M24X22 M24X18 M24X14 M24X25 M24X21 M24X17 M24X13 M24X24 M24X20 M24X12 M24X23 M24X19 M25X17 M24X15 M25X12 M25X23 M25X19 M25X15 M25X11 M25X22 M25X18 M25X14 M25X25 M25X21 M25X13 M25X24 M25X20 M26X18 M25X16 M26X13 M26X24 M26X20 M26X16 M26X12 M26X23 M26X19 M26X15 M26X11 M26X22 M26X14 M26X25 M26X21 M27X19 M26X17 M27X14 M27X25 M27X21 M27X17 M27X13 M27X24 M27X20 M27X16 M27X12 M27X23 M27X15 M27X11 M27X22 M28X20 M27X18 M28X15 M28X11 M28X22 M28X18 M28X14 M28X25 M28X21 M28X17 M28X13 M28X24 M28X16 M28X12 M28X23 M29X21 M28X19 M29X16 M29X12 M29X23 M29X19 M29X15 M29X11 M29X22 M29X18 M29X14 M29X25 M29X17 M29X13 M29X24 M30X22 M29X20 M30X17 M30X13 M30X24 M30X20 M30X16 M30X12 M30X23 M30X19 M30X15 M30X11 M30X18 M30X14 M30X25 M30X21
NEW: C156 A114 C119 A148 A181 B182 A169 A147 B105 A193 B165 B138 C131 A164 B132 B199 C110 A127 A176 A105 B149 A145 B169 C169 A185 C153 A160 B114 C114 A199 A115 B141 C141 A182 A124 B124 A152 B156 A172 A139 B189 A159 C140 A126 B147 C165 A189 C179 A184 A118 B172 A190 B190 A155 B139 C190 A200 A134 A157 B134 B200 C105 A196 A150 A163 A183 B136 C149 A129 B137 C136 A117 A154 B154 A167 B104 C154 C104 A119 A195 A162 B119 B167 C124 A179 C199 A188 B162 A121 B121 A138 B171 A141 C172 A102 B102 A125 B129 A144 B144 A191 B193 B111 C193 C107 A132 C159 A168 B168 A135 A187 B181 C142 A128 B160 A178 B178 A137 B135 A130 B196 C182 B195 C102 A103 B103 C103 A101 B101 C164 A158 B152 C152 C113 A136 B106 B117 A142 B163 C163 A143 A140 B140 C117 C167 A112 B128 A149 A151 C120 A166 A153 C150 C200 A156 A106 B166 C128 A110 A174 B174 B110 A165 C109 A109 B109 B143 C198 A170 B176 C157 A173 A107 B107 C144 A192 B188 B170 A180 A120 B185 C195 A116 A186 A111 B151 C132 A123 B116 B127 C166 C116 A194 C138 C125 A197 A198 B123 A113 B113 B179 C123 C188 A131 B173 B118 B184 C173 A161 B142 C139 B191 A108 B108 C162 B125 C112 A122 B180 C106 C108 B126 C126 A175 B175 C121 C185 A177 B177 C175 C177 C118 A171 A133 B145 A104 B112 C111 C134 C170 C180 A146 B146 C129 C147 B148 C183 B164 B115 B130 C115 C160 B183 C178 B150 C137 C196 B155 C155 C191 B186 B153 C168 B120 C127 B187 C186 C145 B122 C122 C181 B158 C158 B157 C176 C135 C194 C171 B159 B192 C130 C189 C148 B194 C184 B161 C143 C161 B197 C197 B131 C174 B198 C133 C192 C151 B133 C187 C146 C101 M11X18 M11X16 M11X23 M11X13 M11X12 M11X19 M12X24 M12X23 M11X20 M11X24 M12X20 M11X17 M12X19 M11X21 M11X14 M11X15 M11X25 M12X15 M11X11 M12X11 M12X25 M11X22 M12X12 M13X24 M13X11 M12X13 M13X20 M12X17 M12X18 M13X25 M14X16 M12X16 M13X22 M12X22 M13X13 M12X14 M14X20 M13X15 M14X12 M15X22 M12X21 M13X18 M14X13 M13X16 M14X21 M15X18 M13X19 M16X21 M14X11 M16X14 M17X16 M18X21 M20X19 M22X12 M13X14 M14X15 M13X17 M14X19 M13X23 M15X11 M16X13 M13X12 M14X23 M15X24 M14X24 M15X20 M15X16 M13X21 M14X17 M14X25 M14X14 M14X18 M15X15 M15X19 M15X23 M16X25 M14X22 M15X12 M15X13 M16X23 M15X17 M16X19 M16X12 M17X24 M16X20 M16X24 M17X20 M15X14 M15X21 M16X18 M16X22 M16X11 M17X17 M17X13 M15X25 M16X15 M17X12 M16X16 M17X23 M17X11 M17X15 M17X22 M18X12 M18X19 M18X23 M19X24 M17X21 M18X18 M18X22 M19X13 M18X11 M16X17 M17X18 M17X25 M17X14 M18X15 M18X16 M18X20 M18X14 M19X14 M19X25 M19X11 M19X22 M18X17 M20X20 M20X16 M19X15 M20X12 M21X22 M18X13 M19X19 M19X23 M19X18 M20X15 M20X11 M21X11 M21X12 M20X25 M20X14 M21X15 M17X19 M18X24 M19X20 M19X12 M20X22 M18X25 M19X17 M19X21 M20X18 M19X16 M20X17 M20X21 M21X17 M20X13 M21X18 M22X13 M21X16 M20X24 M21X21 M22X17 M21X20 M21X24 M21X13 M22X21 M23X19 M22X20 M23X23 M24X12 M21X19 M22X19 M23X12 M25X12 M22X23 M20X23 M21X25 M22X15 M22X11 M22X22 M22X18 M23X15 M21X23 M22X24 M23X20 M24X23 M21X14 M22X14 M23X16 M22X25 M23X13 M23X17 M23X21 M24X20 M24X13 M24X24 M25X23 M26X12 M24X19 M22X16 M23X24 M23X25 M23X14 M23X18 M24X17 M24X21 M24X25 M23X22 M24X14 M25X19 M25X20 M26X24 M26X13 M27X24 M28X12 M24X18 M25X16 M23X11 M24X16 M25X24 M24X22 M24X15 M25X13 M24X11 M25X14 M25X18 M25X22 M25X11 M26X18 M26X25 M25X15 M26X14 M27X20 M26X16 M25X21 M25X25 M26X20 M27X12 M26X15 M26X19 M27X16 M26X17 M25X17 M26X22 M26X23 M27X13 M26X11 M27X17 M27X25 M27X14 M27X18 M28X25 M27X15 M28X21 M26X21 M27X23 M27X21 M28X14 M28X11 M28X22 M29X23 M27X19 M28X16 M27X22 M28X17 M28X13 M28X24 M27X11 M28X19 M28X23 M29X11 M28X20 M29X13 M29X12 M28X15 M29X19 M29X15 M28X18 M29X22 M30X20 M29X14 M29X25 M29X17 M29X24 M30X12 M29X20 M30X13 M30X17 M29X21 M30X24 M29X16 M30X16 M29X18 M30X23 M30X19 M30X15 M30X11 M30X18 M30X14 M30X25 M30X21 M30X22
Real time: 0.005003 sec

BST: C153 C110 A127 A160 A193 B165 A147 A105 B105 B138 C131 A164 B132 A169 B199 A176 B114 C114 A199 C141 A145 B169 C169 A185 A152 B149 A181 C119 A148 A115 B141 B172 A124 B124 C104 A119 B119 A172 A139 B189 A159 C140 A126 B147 C165 A189 C179 A184 A118 A190 B190 A155 B139 C190 C149 A129 A150 A200 A183 B136 A182 B200 A157 A163 A134 B134 C105 A196 B137 C136 A117 A154 B154 A167 B104 C154 A114 B182 A195 A162 B167 C124 A179 B156 C199 A188 B162 A121 B121 A138 B171 A141 C172 A102 B102 A125 B129 A144 B144 A191 B193 B111 C193 C107 A132 C159 A168 B168 A135 A187 B181 C142 A128 B160 A178 B178 A137 B135 A130 B196 C182 B195 C102 A103 B103 C103 A101 B101 C164 A158 B152 C152 C113 A136 B106 B117 A142 B163 C163 A143 A140 B140 C117 C167 A112 B128 A149 A151 C120 A166 A153 C150 C200 A156 A106 B166 C128 A110 A174 B174 B110 A165 C109 A109 B109 B143 C198 A170 B176 C157 A173 A107 B107 C144 A192 B188 B170 A180 A120 B185 C195 A116 A186 A111 B151 C132 A123 B116 B127 C166 C116 A194 C138 C125 A197 A198 B123 A113 B113 B179 C123 C188 A131 B173 B118 B184 C173 A161 B142 C139 B191 A108 B108 C162 B125 C112 A122 B180 C106 C108 B126 C126 A175 B175 C121 C185 A177 B177 C175 C177 C118 A171 A133 B145 A104 B112 C111 C134 C170 C180 A146 B146 C129 C147 B148 C183 C194 B115 B164 C115 C160 B183 C178 B150 C137 C196 B155 C155 C191 B186 B153 C168 B120 C127 B187 C186 C145 B122 C122 C181 B158 C158 B157 C176 C135 C171 B130 B159 B192 C130 C189 C148 B194 C184 B161 C143 C161 B197 C197 B131 C174 B198 C133 C192 C151 B133 C187 C146 C101 C156 M11X22 M11X25 M11X24 M11X11 M11X17 M11X21 M12X17 M11X20 M11X18 M12X13 M11X13 M12X19 M11X14 M12X15 M11X15 M11X19 M11X23 M12X25 M12X14 M11X12 M12X24 M12X12 M12X16 M13X19 M11X16 M12X22 M12X18 M12X23 M13X25 M13X15 M12X20 M13X22 M13X23 M14X25 M13X14 M12X21 M13X18 M14X15 M13X16 M13X20 M12X11 M13X12 M13X24 M14X21 M14X14 M15X16 M13X11 M14X11 M14X22 M15X12 M13X21 M14X23 M13X13 M13X17 M14X19 M14X12 M14X16 M15X23 M14X20 M16X23 M14X17 M15X17 M15X24 M14X18 M15X13 M16X19 M15X25 M15X14 M16X15 M17X25 M14X24 M14X13 M15X19 M15X20 M16X16 M20X15 M16X20 M16X24 M17X21 M18X17 M18X13 M19X19 M21X12 M15X15 M15X11 M16X12 M17X22 M15X21 M20X11 M15X18 M16X25 M17X17 M15X22 M16X14 M19X18 M16X11 M17X11 M16X22 M17X12 M18X22 M16X21 M17X16 M17X23 M18X23 M16X17 M17X18 M17X13 M18X18 M18X14 M19X14 M16X18 M16X13 M17X20 M17X14 M19X15 M18X15 M18X19 M19X25 M17X15 M18X11 M19X11 M17X19 M17X24 M18X24 M18X20 M19X20 M19X12 M20X22 M18X25 M18X21 M19X16 M18X16 M18X12 M19X23 M19X17 M19X13 M19X24 M19X21 M20X19 M21X11 M19X22 M20X12 M20X16 M20X20 M21X22 M22X12 M20X24 M20X18 M20X21 M21X13 M20X25 M21X16 M20X13 M21X20 M22X22 M20X17 M21X17 M21X21 M22X18 M23X15 M21X24 M22X21 M23X19 M22X20 M23X23 M24X12 M22X19 M21X19 M23X12 M24X19 M25X12 M22X23 M20X23 M20X14 M21X15 M22X11 M21X23 M22X25 M21X25 M21X14 M22X16 M23X25 M22X14 M23X17 M25X16 M26X12 M21X18 M22X13 M22X24 M23X21 M24X11 M22X17 M23X20 M24X22 M23X24 M23X16 M24X24 M23X18 M23X14 M24X17 M23X22 M24X15 M25X15 M24X25 M24X13 M25X22 M26X16 M25X20 M27X12 M26X24 M27X24 M28X12 M24X18 M22X15 M23X11 M24X16 M25X24 M24X23 M25X11 M25X13 M23X13 M24X20 M25X23 M24X14 M25X18 M26X25 M25X14 M26X18 M26X14 M27X20 M24X21 M25X21 M25X25 M26X20 M25X19 M26X15 M26X19 M27X16 M26X17 M25X17 M26X13 M26X23 M26X21 M27X14 M27X25 M27X21 M28X22 M26X11 M27X11 M27X15 M26X22 M27X17 M27X23 M27X13 M28X24 M28X11 M27X22 M28X18 M27X19 M28X16 M28X13 M28X17 M27X18 M28X21 M29X25 M28X19 M28X23 M28X20 M29X13 M28X25 M29X24 M28X15 M29X17 M28X14 M29X21 M29X22 M30X25 M29X14 M29X20 M30X13 M29X19 M30X12 M29X12 M29X23 M30X17 M29X15 M30X24 M29X16 M30X16 M29X18 M30X23 M30X19 M30X15 M30X11 M30X18 M30X14 M29X11 M30X21 M30X22 M30X20
Real time: 0.006444 sec

CUR: A173 A132 A155 A125 B170 B200 B169 B128 A165 B191 B137 B174 A178 A149 C178 C137 A142 A183 B119 B149 A170 A111 B192 B144 C144 C103 A182 B194 A159 A118 B190 C132 A123 C141 A109 B197 A156 B198 A176 B138 A190 A131 B132 C122 A102 A143 B156 B110 C120 C195 B134 B193 A169 B195 C177 C136 A195 A154 C105 B189 B171 A147 A192 A133 B188 B147 C147 C113 A181 A140 B103 B117 C114 C183 C179 A128 C118 C173 A103 B135 C199 A175 B179 B187 C115 C133 A141 A200 B104 C154 C164 A158 A199 B109 C174 A138 B123 C117 B115 B159 A167 A126 B126 C189 A115 B141 A163 A122 B102 C200 B143 C143 A121 A180 B180 B162 B140 B199 A161 A120 B120 B161 C161 A104 C101 C139 A108 A135 C125 B186 B151 C151 A124 B106 C106 C180 A146 A187 B185 A112 B112 A107 B125 B152 C109 A168 A127 C149 A188 B121 A129 B178 C111 A145 B145 C170 A166 B168 B127 C166 C104 A119 B167 B108 C108 A150 B118 C191 A144 A185 B181 B101 A196 A137 C169 A148 A157 B175 A116 B116 C119 A189 B157 C135 C168 A130 B196 A171 C153 A101 A160 B124 C194 A139 A198 B150 C150 A106 B107 C185 A177 B177 C116 A194 C175 A197 B155 B139 B183 C196 B142 C121 B133 A136 B158 C158 C171 A184 B176 C176 B166 C187 A172 A113 B146 C146 A134 B122 C181 C128 A151 B172 B131 C131 A105 B105 B130 A164 B173 C167 A153 B153 B163 C156 A114 B182 B114 C197 A152 A193 B165 C165 A117 B154 C145 C126 A174 B184 C155 B148 C192 C110 C142 A162 B160 C160 A186 A191 B111 B136 C159 C130 C112 B129 B113 C123 A110 C193 C162 C157 C140 C172 C190 C186 C124 C129 B164 A179 C127 C163 C134 C138 C102 C188 C107 C182 C198 C184 C148 C152 M11X12 M11X13 M11X14 M11X15 M11X16 M11X17 M11X18 M11X19 M11X20 M12X22 M11X21 M12X18 M11X22 M12X14 M11X23 M12X25 M13X15 M12X23 M12X24 M11X24 M12X21 M13X16 M12X19 M12X20 M11X25 M12X17 M13X17 M12X15 M13X25 M12X16 M13X21 M14X17 M14X11 M13X20 M21X13 M20X20 M17X14 M16X12 M15X23 M20X23 M25X15 M23X14 M20X19 M20X18 M19X15 M20X12 M26X17 M26X16 M23X13 M11X11 M13X14 M14X16 M12X13 M13X19 M13X18 M14X15 M12X11 M13X12 M14X22 M15X12 M13X11 M21X25 M20X16 M21X23 M18X17 M18X18 M17X19 M15X16 M22X25 M22X11 M19X24 M21X22 M18X20 M23X22 M21X11 M19X12 M24X20 M23X19 M21X15 M22X12 M12X12 M13X24 M14X21 M13X23 M14X25 M15X17 M14X24 M14X23 M13X22 M14X13 M15X18 M15X19 M16X24 M14X12 M24X17 M25X20 M22X24 M20X14 M24X14 M24X13 M22X21 M23X18 M19X11 M19X20 M17X16 M18X21 M20X15 M19X23 M18X24 M18X23 M25X14 M24X18 M22X22 M25X25 M23X21 M22X15 M21X17 M22X19 M17X24 M18X11 M19X13 M17X13 M23X11 M24X16 M24X15 M23X25 M19X17 M19X16 M20X22 M21X14 M21X24 M16X15 M17X25 M22X18 M19X22 M18X13 M20X21 M19X18 M20X13 M15X14 M23X17 M24X19 M22X20 M23X23 M17X22 M17X21 M19X19 M20X11 M21X12 M18X16 M20X24 M21X20 M21X21 M22X16 M22X17 M19X21 M21X18 M22X14 M23X16 M23X15 M22X13 M23X20 M24X22 M25X16 M25X12 M13X13 M14X20 M15X21 M15X20 M16X22 M15X22 M16X14 M14X19 M15X11 M16X13 M15X25 M15X24 M16X21 M14X18 M15X13 M16X18 M16X20 M17X20 M16X19 M17X11 M18X12 M20X25 M21X16 M22X23 M24X12 M14X14 M15X15 M16X25 M17X15 M16X11 M23X24 M24X23 M24X21 M25X21 M26X20 M17X12 M16X17 M17X18 M18X15 M18X14 M24X24 M25X23 M26X12 M27X12 M17X17 M18X19 M19X25 M20X17 M21X19 M23X12 M24X11 M18X22 M16X16 M16X23 M19X14 M17X23 M18X25 M24X25 M25X17 M25X22 M25X11 M25X13 M25X24 M25X19 M26X15 M25X18 M26X18 M26X24 M26X25 M26X19 M27X16 M26X13 M27X24 M26X14 M27X20 M28X12 M26X11 M27X11 M27X25 M28X13 M26X21 M27X22 M27X23 M28X14 M27X21 M26X22 M27X18 M27X17 M27X19 M28X15 M26X23 M27X15 M28X16 M28X17 M28X18 M27X13 M28X24 M28X25 M28X11 M27X14 M28X21 M28X22 M28X20 M28X23 M29X21 M28X19 M29X16 M29X12 M29X23 M29X19 M29X15 M29X11 M29X22 M29X18 M29X14 M29X25 M29X17 M29X13 M29X24 M30X22 M29X20 M30X17 M30X13 M30X24 M30X20 M30X16 M30X12 M30X23 M30X19 M30X15 M30X11 M30X18 M30X14 M30X25 M30X21
Real time: 61.7648 sec
---8<---

Well, just comparing exection time:
NEW: 0.005003 sec
BST: 0.006444 sec
CUR: 61.7648 sec

This is a pathological sample case, constructed by the user to
show the problem they are having in their code.
Comment 9 Paulo Andrade 2015-03-08 17:14:55 UTC 
Created attachment 999366 [details]
dso_4

---8<---
$ ./dso_deps -v dso_4
a(b)
b(c)
c(d)
d(e)
e(f)
f()
ORG: a b c d e f
NEW: a b c d e f
Real time: 5e-06 sec

BST: a b c d e f
Real time: 3e-06 sec

CUR: a b c d e f
Real time: 3e-06 sec
---8<---

Simple run of a "problem" with only one solution.
Comment 10 Paulo Andrade 2015-03-08 17:16:14 UTC 
Created attachment 999367 [details]
dso_5

---8<---
$ ./dso_deps -v dso_5
b(a)
a()
c(b)
d(c)
e(d)
f(e)
ORG: b a c d e f
NEW: f e d c b a
Real time: 5e-06 sec

BST: f e d c b a
Real time: 3e-06 sec

CUR: f e d c b a
Real time: 7e-06 sec
---8<---

Another run of a problem with only one solution.
Difference from dso_4 is that all entries are
"permuted".
Comment 11 Paulo Andrade 2015-03-08 19:37:57 UTC 
Created attachment 999381 [details]
Patch version that needs an environment variable to enable the new sort

Now a question for a proposed patch.
Do you believe the best patch proposal
would be to have an environment variable?

Say, something like:

LD_SORT_ALG

and then, default to the current glibc
sorting, and use other values to implement
other sorting?

Right now I have the simple attached patch,
using the

LD_FAST_SORT

environment variable, that if set, and empty,
defaults to the new sort.

But only after the attached patch, I wrote the
simple logic to choose (or attempt to) the best
entry to break cycles.

This patch removes a chunk from the previous
one, that attempted to mimic code in current
glibc, but I could not find or create a case
where it would matter, that was the chunk:

+  /* If a cycle exists with a link time dependency,
+     preserve the latter.  */
+  for (i = from; i < nmaps; ++i)
+    {
+      m = maps[i];
+      if (m->l_reldeps)
+	{
+	  r = &m->l_reldeps->list[0];
+	  c = m->l_reldeps->act;
+	  while (c-- > 0)
+	    {
+	      if (*r != m && (*r)->l_idx >= 0 && !seen[(*r)->l_idx])
+		  ++w[i];
+	      ++r;
+	    }
+ 	}
+    }

for dl-fini.c.

Other than the above, and using an environment
variable, the new patch also better documents
the algorithm.

Sample run, with the original test case, of the patch:

$ ./timedlopen libM11X11.so libM11X12.so
Success!!
dlopen of libM11X11.so took 3620 CPU msec, 3636 WALL msec
Success!!
Second time dlopen of libM11X12.so took 3980 CPU msec, 4002 WALL msec
$
$ LD_FAST_SORT= ./timedlopen libM11X11.so libM11X12.so
Success!!
dlopen of libM11X11.so took 10 CPU msec, 20 WALL msec
Success!!
Second time dlopen of libM11X12.so took 0 CPU msec, 6 WALL msec

I am running rawhide with this patch, can run
kde, libreoffice, firefox, and several other
"complex" applications and did not notice any
problems.
Comment 12 Paulo Andrade 2015-03-10 19:34:34 UTC 
Created attachment 1000112 [details]
Add an extra variant that better matches current glibc sort (sort in reverse order)

There was a bug that could not properly show
the variant that tries to break cycles in the
point it would be, or look like to be) better,
leaving less cycles. It was the change:

---8<---
  putchar('\n');

+ memcpy(the_maps, sav_maps, sizeof(struct link_map *) * num_maps);
  start_timer();
  best_sort(the_maps, num_maps);
---8<---

The new version adds a new reverse_sort variant,
basically changing "sort" as in the pseudo patch:

-     for (i = 0; i < k; ++i)
+     for (i = k - 1; i >= 0; --i)

This version has the side effect of better
matching the current glibc sort algorithm,
including an almost identical result for
the dso_3 test.

Mostly important should be that for a full
cycle as in the dso_2 test, the new reverse_sort
variant (marked REV) looks more natural:

---8<---
$ ./dso_deps dso_2
a(b c)
b(c d e)
c()
d()
e(f)
f()
ORG: a b c d e f
NEW: a b d e f c
Real time: 5e-06 sec

BST: a b d e f c
Real time: 3e-06 sec

CUR: a b c d e f
Real time: 3e-06 sec

REV: a b c d e f
Real time: 3e-06 sec
---8<---
Comment 13 Carlos O'Donell 2015-11-04 19:51:50 UTC 
Related is upstream bug 15310.
Comment 14 Carlos O'Donell 2015-11-04 19:52:27 UTC 
Please do not look at the attachments in sourceware bug 15310 because the submitter does not have FSF copyright assignment.
Comment 18 Carlos O'Donell 2019-10-23 15:22:13 UTC 
This bug is going to be tracked upstream with bug:
https://sourceware.org/bugzilla/show_bug.cgi?id=17645

Then when this is fixed upstream we'll bring it into rawhide as part of our weekly sync.

I'm looking into this again because we have another submission upstream to fix the same situation.

I'm marking this bug CLOSED/UPSTREAM to keep the Fedora bug list shorter.

Please move any comments upstream.
Comment 19 Florian Weimer 2022-04-14 09:59:19 UTC 
This was fixed in Fedora 35 and Red Hat Enterprise Linux 9.0 via bug 2032647.
Note You need to log in before you can comment on or make changes to this bug.