Message ID | a95aec1afdeead3d59ab1b8a71b4224fb490321f.1660573629.git.fweimer@redhat.com |
---|---|
State | New |
Headers | show |
Series | Forced ordering for DFS ELF dependency sorting (bug 28937) | expand |
On 15/08/22 11:30, Florian Weimer via Libc-alpha wrote: > As documented in a comment _dl_close_worker, the skipping is actually > needed for correctness. It also seems less surprising if the > just-opened object is always initialized last, even in the presence > of cycles. I think it is BZ#28937, isn't? Also could you extend the explanation as you did in the last comment, the initial phrase sounds confusing. Maybe extend the comment to say that not _dl_sort_maps_dfs will move the main object to front, so where previous you have the maps input as: maps[0].l_name=elf/tst-bz28937-dir/tst-bz28937-a.so maps[1].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a1.so maps[2].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a2.so maps[3].l_name=./libc.so.6 maps[4].l_name=elf/ld.so It will not be properly sorted as: maps[0].l_name=elf/tst-bz28937-dir/tst-bz28937-a.so maps[1].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a1.so maps[2].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a2.so maps[3].l_name=./libc.so.6 maps[4].l_name=elf/ld.so Instead of wrongly: maps[0].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a1.so maps[1].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a2.so maps[2].l_name=elf/tst-bz28937-dir/tst-bz28937-a.so maps[3].l_name=./libc.so.6 maps[4].l_name=elf/ld.so > --- > elf/dl-sort-maps.c | 35 ++++++++++++++++++++++++++--------- > elf/dso-sort-tests-1.def | 7 +++++++ > 2 files changed, 33 insertions(+), 9 deletions(-) > > diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c > index 5b550b1e94..cd2d9c93fc 100644 > --- a/elf/dl-sort-maps.c > +++ b/elf/dl-sort-maps.c > @@ -182,8 +182,9 @@ dfs_traversal (struct link_map ***rpo, struct link_map *map, > > static void > _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, > - bool force_first __attribute__ ((unused)), bool for_fini) > + bool force_first, bool for_fini) > { > + struct link_map *first_map = maps[0]; Move this to where it is actually used. > for (int i = nmaps - 1; i >= 0; i--) > maps[i]->l_visited = 0; > > @@ -208,14 +209,6 @@ _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, > Adjusting the order so that maps[0] is last traversed naturally avoids > this problem. > > - Further, the old "optimization" of skipping the main object at maps[0] > - from the call-site (i.e. _dl_sort_maps(maps+1,nmaps-1)) is in general > - no longer valid, since traversing along object dependency-links > - may "find" the main object even when it is not included in the initial > - order (e.g. a dlopen()'ed shared object can have circular dependencies> - linked back to itself). In such a case, traversing N-1 objects will > - create a N-object result, and raise problems. > - > To summarize, just passing in the full list, and iterating from back > to front makes things much more straightforward. */ > > @@ -274,6 +267,30 @@ _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, > } > > memcpy (maps, rpo, sizeof (struct link_map *) * nmaps); > + > + /* Skipping the first object at maps[0] is not valid in general, > + since traversing along object dependency-links may "find" that > + first object even when it is not included in the initial order > + (e.g. a dlopen()'ed shared object can have circular dependencies > + linked back to itself). In such a case, traversing N-1 objects Double space after period and think we do not reference symbol using '()'. > + will create a N-object result, and raise problems. Instead, > + force the object back into first place after sorting. */ > + if (force_first && maps[0] != first_map) > + { > + struct link_map *saved = maps[0]; > + maps[0] = first_map; > + int i = 1; > + while (true) > + { > + assert (i < nmaps); > + struct link_map *current = maps[i]; > + maps[i] = saved; > + if (current == first_map) > + break; > + saved = current; > + ++i; > + } > + } > } It sounds reasonable to keep the main object as the initial map, although it would slow down a bit normal dlclose. I think it would be possible to optimize the memory move with memmove here, although not sure if it is worth. > > void > diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def > index 5f7f18ef27..4bf9052db1 100644 > --- a/elf/dso-sort-tests-1.def > +++ b/elf/dso-sort-tests-1.def > @@ -64,3 +64,10 @@ output: b>a>{}<a<b > 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[<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];} > + > +# Test that even in the presence of dependency loops involving dlopen'ed > +# object, that object is initialized last (and not unloaded prematurely). > +# Final destructor order is indeterminate due to the cycle. > +tst-bz28937: {+a;+b;-b;+c;%c};a->a1;a->a2;a2->a;b->b1;c->a1;c=>a1 So main program: 1. dlopen 'a' and 'b'; 2. dclose 'b'; 3. dlopen 'c'; 4. dlsym 'c' and calls fn_a from 'c'; And we have a circle dependency where a depends of a2 and a2 depends on 'a'. Do we need to add a test for multiple circles? For instance where you have either another disjointed circle ({+d};d->d2;d2->d) and/or another circle in same dependency chain (a1->b;b1->a)? > +output(glibc.rtld.dynamic_sort=1): {+a[a2>a1>a>];+b[b1>b>];-b[<b<b1];+c[c>];%c(a1());}<a<a2<c<a1 > +output(glibc.rtld.dynamic_sort=2): {+a[a2>a1>a>];+b[b1>b>];-b[<b<b1];+c[c>];%c(a1());}<a2<a<c<a1
On 31/08/22 13:37, Adhemerval Zanella Netto wrote: > > > On 15/08/22 11:30, Florian Weimer via Libc-alpha wrote: >> As documented in a comment _dl_close_worker, the skipping is actually >> needed for correctness. It also seems less surprising if the >> just-opened object is always initialized last, even in the presence >> of cycles. > > I think it is BZ#28937, isn't? Also could you extend the explanation as you > did in the last comment, the initial phrase sounds confusing. Maybe extend > the comment to say that not _dl_sort_maps_dfs will move the main object to > front, so where previous you have the maps input as: > > maps[0].l_name=elf/tst-bz28937-dir/tst-bz28937-a.so > maps[1].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a1.so > maps[2].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a2.so > maps[3].l_name=./libc.so.6 > maps[4].l_name=elf/ld.so > > It will not be properly sorted as: It will *now* be ...
* Adhemerval Zanella Netto: > On 15/08/22 11:30, Florian Weimer via Libc-alpha wrote: >> As documented in a comment _dl_close_worker, the skipping is actually >> needed for correctness. It also seems less surprising if the >> just-opened object is always initialized last, even in the presence >> of cycles. > > I think it is BZ#28937, isn't? Also could you extend the explanation as you > did in the last comment, the initial phrase sounds confusing. I have expanded the commit message. > Maybe extend the comment to say that not _dl_sort_maps_dfs will move > the main object to front, so where previous you have the maps input > as: > > maps[0].l_name=elf/tst-bz28937-dir/tst-bz28937-a.so > maps[1].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a1.so > maps[2].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a2.so > maps[3].l_name=./libc.so.6 > maps[4].l_name=elf/ld.so > > It will not be properly sorted as: > > maps[0].l_name=elf/tst-bz28937-dir/tst-bz28937-a.so > maps[1].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a1.so > maps[2].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a2.so > maps[3].l_name=./libc.so.6 > maps[4].l_name=elf/ld.so > > Instead of wrongly: > > maps[0].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a1.so > maps[1].l_name=[...]/elf/tst-bz28937-dir/tst-bz28937-a2.so > maps[2].l_name=elf/tst-bz28937-dir/tst-bz28937-a.so > maps[3].l_name=./libc.so.6 > maps[4].l_name=elf/ld.so I think with just three elements, it's a bit misleading because a cycle of this size is rotated correctly by the naive approach. >> diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c >> index 5b550b1e94..cd2d9c93fc 100644 >> --- a/elf/dl-sort-maps.c >> +++ b/elf/dl-sort-maps.c >> @@ -182,8 +182,9 @@ dfs_traversal (struct link_map ***rpo, struct link_map *map, >> >> static void >> _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, >> - bool force_first __attribute__ ((unused)), bool for_fini) >> + bool force_first, bool for_fini) >> { >> + struct link_map *first_map = maps[0]; > > Move this to where it is actually used. We need to copy it before it's overwritten by the sort. >> + /* Skipping the first object at maps[0] is not valid in general, >> + since traversing along object dependency-links may "find" that >> + first object even when it is not included in the initial order >> + (e.g. a dlopen()'ed shared object can have circular dependencies >> + linked back to itself). In such a case, traversing N-1 objects > > Double space after period and think we do not reference symbol using '()'. Fixed (although I just copied that part of the comment). >> + will create a N-object result, and raise problems. Instead, >> + force the object back into first place after sorting. */ >> + if (force_first && maps[0] != first_map) >> + { >> + struct link_map *saved = maps[0]; >> + maps[0] = first_map; >> + int i = 1; >> + while (true) >> + { >> + assert (i < nmaps); >> + struct link_map *current = maps[i]; >> + maps[i] = saved; >> + if (current == first_map) >> + break; >> + saved = current; >> + ++i; >> + } >> + } >> } > > It sounds reasonable to keep the main object as the initial map, although > it would slow down a bit normal dlclose. I think it would be possible > to optimize the memory move with memmove here, although not sure if it is > worth. If we make the assert less precise, memmove actually simplifies the code. I've made the change. >> void >> diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def >> index 5f7f18ef27..4bf9052db1 100644 >> --- a/elf/dso-sort-tests-1.def >> +++ b/elf/dso-sort-tests-1.def >> @@ -64,3 +64,10 @@ output: b>a>{}<a<b >> 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[<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];} >> + >> +# Test that even in the presence of dependency loops involving dlopen'ed >> +# object, that object is initialized last (and not unloaded prematurely). >> +# Final destructor order is indeterminate due to the cycle. >> +tst-bz28937: {+a;+b;-b;+c;%c};a->a1;a->a2;a2->a;b->b1;c->a1;c=>a1 > > So main program: > > 1. dlopen 'a' and 'b'; > 2. dclose 'b'; > 3. dlopen 'c'; > 4. dlsym 'c' and calls fn_a from 'c'; > > And we have a circle dependency where a depends of a2 and a2 depends on 'a'. > > Do we need to add a test for multiple circles? For instance where you have > either another disjointed circle ({+d};d->d2;d2->d) and/or another circle > in same dependency chain (a1->b;b1->a)? Could you add this as a follow-up patch? It does not seem strictly related (and I think we already have other tests for unloading cycles). Thanks, Florian
diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c index 5b550b1e94..cd2d9c93fc 100644 --- a/elf/dl-sort-maps.c +++ b/elf/dl-sort-maps.c @@ -182,8 +182,9 @@ dfs_traversal (struct link_map ***rpo, struct link_map *map, static void _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, - bool force_first __attribute__ ((unused)), bool for_fini) + bool force_first, bool for_fini) { + struct link_map *first_map = maps[0]; for (int i = nmaps - 1; i >= 0; i--) maps[i]->l_visited = 0; @@ -208,14 +209,6 @@ _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, Adjusting the order so that maps[0] is last traversed naturally avoids this problem. - Further, the old "optimization" of skipping the main object at maps[0] - from the call-site (i.e. _dl_sort_maps(maps+1,nmaps-1)) is in general - no longer valid, since traversing along object dependency-links - may "find" the main object even when it is not included in the initial - order (e.g. a dlopen()'ed shared object can have circular dependencies - linked back to itself). In such a case, traversing N-1 objects will - create a N-object result, and raise problems. - To summarize, just passing in the full list, and iterating from back to front makes things much more straightforward. */ @@ -274,6 +267,30 @@ _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, } memcpy (maps, rpo, sizeof (struct link_map *) * nmaps); + + /* Skipping the first object at maps[0] is not valid in general, + since traversing along object dependency-links may "find" that + first object even when it is not included in the initial order + (e.g. a dlopen()'ed shared object can have circular dependencies + linked back to itself). In such a case, traversing N-1 objects + will create a N-object result, and raise problems. Instead, + force the object back into first place after sorting. */ + if (force_first && maps[0] != first_map) + { + struct link_map *saved = maps[0]; + maps[0] = first_map; + int i = 1; + while (true) + { + assert (i < nmaps); + struct link_map *current = maps[i]; + maps[i] = saved; + if (current == first_map) + break; + saved = current; + ++i; + } + } } void diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def index 5f7f18ef27..4bf9052db1 100644 --- a/elf/dso-sort-tests-1.def +++ b/elf/dso-sort-tests-1.def @@ -64,3 +64,10 @@ output: b>a>{}<a<b 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[<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];} + +# Test that even in the presence of dependency loops involving dlopen'ed +# object, that object is initialized last (and not unloaded prematurely). +# Final destructor order is indeterminate due to the cycle. +tst-bz28937: {+a;+b;-b;+c;%c};a->a1;a->a2;a2->a;b->b1;c->a1;c=>a1 +output(glibc.rtld.dynamic_sort=1): {+a[a2>a1>a>];+b[b1>b>];-b[<b<b1];+c[c>];%c(a1());}<a<a2<c<a1 +output(glibc.rtld.dynamic_sort=2): {+a[a2>a1>a>];+b[b1>b>];-b[<b<b1];+c[c>];%c(a1());}<a2<a<c<a1