* [PATCH 0/3] Forced ordering for DFS ELF dependency sorting (bug 28937) @ 2022-08-15 14:30 Florian Weimer 2022-08-15 14:30 ` [PATCH 1/3] scripts/dso-ordering-test.py: Generate program run-time dependencies Florian Weimer ` (2 more replies) 0 siblings, 3 replies; 10+ messages in thread From: Florian Weimer @ 2022-08-15 14:30 UTC (permalink / raw) To: libc-alpha An Arch Linux test case showed that in some cases, dlclose could unload mappings that are still in use. Triggering this requires dependency cycles, which is why I think this is somewhat rare. Tested on i686-linux-gnu and x86_64-linux-gnu. Thanks, Florian Florian Weimer (3): scripts/dso-ordering-test.py: Generate program run-time dependencies elf: Rename _dl_sort_maps parameter from skip to force_first elf: Implement force_first handling in _dl_sort_maps_dfs elf/dl-sort-maps.c | 47 ++++++++++++++++++++++++------------ elf/dso-sort-tests-1.def | 7 ++++++ scripts/dso-ordering-test.py | 14 +++++------ sysdeps/generic/ldsodefs.h | 6 +++-- 4 files changed, 50 insertions(+), 24 deletions(-) base-commit: 453b88efe6fa79f5c7c6fccc3a520c75fdd43074 -- 2.37.1 ^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 1/3] scripts/dso-ordering-test.py: Generate program run-time dependencies 2022-08-15 14:30 [PATCH 0/3] Forced ordering for DFS ELF dependency sorting (bug 28937) Florian Weimer @ 2022-08-15 14:30 ` Florian Weimer 2022-08-15 14:35 ` Florian Weimer 2022-08-29 14:30 ` Adhemerval Zanella Netto 2022-08-15 14:30 ` [PATCH 2/3] elf: Rename _dl_sort_maps parameter from skip to force_first Florian Weimer 2022-08-15 14:30 ` [PATCH 3/3] elf: Implement force_first handling in _dl_sort_maps_dfs Florian Weimer 2 siblings, 2 replies; 10+ messages in thread From: Florian Weimer @ 2022-08-15 14:30 UTC (permalink / raw) To: libc-alpha The main program needs to depend on all shared objects, even objects that have link-time dependencies among shared objects. Filtering out shared objects that already have an link-time dependencies is not necessary here; make will do this automatically. --- scripts/dso-ordering-test.py | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/scripts/dso-ordering-test.py b/scripts/dso-ordering-test.py index 2dd6bfda18..f6d22aa00e 100644 --- a/scripts/dso-ordering-test.py +++ b/scripts/dso-ordering-test.py @@ -707,13 +707,12 @@ def process_testcase(t): "\t$(compile.c) $(OUTPUT_OPTION)\n") makefile.write (rule) - 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)) + # Ensure that all shared objects are built before running the + # test, whether there link-time dependencies or not. + depobjs = ["$(objpfx){}/{}-{}.so".format(test_subdir, test_name, dep) + for dep in test_descr.objs] + makefile.write("$(objpfx){}.out: {}\n".format( + base_test_name, " ".join(depobjs))) # Add main executable to test-srcs makefile.write("test-srcs += %s/%s\n" % (test_subdir, test_name)) @@ -779,6 +778,7 @@ def process_testcase(t): # description string. for obj in test_descr.objs: src_name = test_name + "-" + obj + ".c" + print('Generating {}...'.format(src_name)) f = open(testpfx_src + src_name, "w") if obj in test_descr.callrefs: called_objs = test_descr.callrefs[obj] -- 2.37.1 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 1/3] scripts/dso-ordering-test.py: Generate program run-time dependencies 2022-08-15 14:30 ` [PATCH 1/3] scripts/dso-ordering-test.py: Generate program run-time dependencies Florian Weimer @ 2022-08-15 14:35 ` Florian Weimer 2022-08-29 14:30 ` Adhemerval Zanella Netto 1 sibling, 0 replies; 10+ messages in thread From: Florian Weimer @ 2022-08-15 14:35 UTC (permalink / raw) To: Florian Weimer via Libc-alpha * Florian Weimer via Libc-alpha: > The main program needs to depend on all shared objects, even objects > that have link-time dependencies among shared objects. Filtering > out shared objects that already have an link-time dependencies is not > necessary here; make will do this automatically. > --- > scripts/dso-ordering-test.py | 14 +++++++------- > 1 file changed, 7 insertions(+), 7 deletions(-) > > diff --git a/scripts/dso-ordering-test.py b/scripts/dso-ordering-test.py > index 2dd6bfda18..f6d22aa00e 100644 > --- a/scripts/dso-ordering-test.py > +++ b/scripts/dso-ordering-test.py > @@ -707,13 +707,12 @@ def process_testcase(t): > "\t$(compile.c) $(OUTPUT_OPTION)\n") > makefile.write (rule) > > - 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)) > + # Ensure that all shared objects are built before running the > + # test, whether there link-time dependencies or not. > + depobjs = ["$(objpfx){}/{}-{}.so".format(test_subdir, test_name, dep) > + for dep in test_descr.objs] > + makefile.write("$(objpfx){}.out: {}\n".format( > + base_test_name, " ".join(depobjs))) > > # Add main executable to test-srcs > makefile.write("test-srcs += %s/%s\n" % (test_subdir, test_name)) > @@ -779,6 +778,7 @@ def process_testcase(t): > # description string. > for obj in test_descr.objs: > src_name = test_name + "-" + obj + ".c" > + print('Generating {}...'.format(src_name)) > f = open(testpfx_src + src_name, "w") > if obj in test_descr.callrefs: > called_objs = test_descr.callrefs[obj] Ugh, I'm going to remove that debugging leftover before committing. Thanks, Florian ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 1/3] scripts/dso-ordering-test.py: Generate program run-time dependencies 2022-08-15 14:30 ` [PATCH 1/3] scripts/dso-ordering-test.py: Generate program run-time dependencies Florian Weimer 2022-08-15 14:35 ` Florian Weimer @ 2022-08-29 14:30 ` Adhemerval Zanella Netto 1 sibling, 0 replies; 10+ messages in thread From: Adhemerval Zanella Netto @ 2022-08-29 14:30 UTC (permalink / raw) To: Florian Weimer, libc-alpha On 15/08/22 11:30, Florian Weimer via Libc-alpha wrote: > The main program needs to depend on all shared objects, even objects > that have link-time dependencies among shared objects. Filtering > out shared objects that already have an link-time dependencies is not > necessary here; make will do this automatically. LGTM with the print debug leftover removed. Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org> > --- > scripts/dso-ordering-test.py | 14 +++++++------- > 1 file changed, 7 insertions(+), 7 deletions(-) > > diff --git a/scripts/dso-ordering-test.py b/scripts/dso-ordering-test.py > index 2dd6bfda18..f6d22aa00e 100644 > --- a/scripts/dso-ordering-test.py > +++ b/scripts/dso-ordering-test.py > @@ -707,13 +707,12 @@ def process_testcase(t): > "\t$(compile.c) $(OUTPUT_OPTION)\n") > makefile.write (rule) > > - 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)) > + # Ensure that all shared objects are built before running the > + # test, whether there link-time dependencies or not. > + depobjs = ["$(objpfx){}/{}-{}.so".format(test_subdir, test_name, dep) > + for dep in test_descr.objs] > + makefile.write("$(objpfx){}.out: {}\n".format( > + base_test_name, " ".join(depobjs))) > > # Add main executable to test-srcs > makefile.write("test-srcs += %s/%s\n" % (test_subdir, test_name)) > @@ -779,6 +778,7 @@ def process_testcase(t): > # description string. > for obj in test_descr.objs: > src_name = test_name + "-" + obj + ".c" > + print('Generating {}...'.format(src_name)) > f = open(testpfx_src + src_name, "w") > if obj in test_descr.callrefs: > called_objs = test_descr.callrefs[obj] ^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 2/3] elf: Rename _dl_sort_maps parameter from skip to force_first 2022-08-15 14:30 [PATCH 0/3] Forced ordering for DFS ELF dependency sorting (bug 28937) Florian Weimer 2022-08-15 14:30 ` [PATCH 1/3] scripts/dso-ordering-test.py: Generate program run-time dependencies Florian Weimer @ 2022-08-15 14:30 ` Florian Weimer 2022-08-29 16:40 ` Adhemerval Zanella Netto 2022-08-15 14:30 ` [PATCH 3/3] elf: Implement force_first handling in _dl_sort_maps_dfs Florian Weimer 2 siblings, 1 reply; 10+ messages in thread From: Florian Weimer @ 2022-08-15 14:30 UTC (permalink / raw) To: libc-alpha The new implementation will not be able to skip an arbitrary number of objects. --- elf/dl-sort-maps.c | 14 +++++++------- sysdeps/generic/ldsodefs.h | 6 ++++-- 2 files changed, 11 insertions(+), 9 deletions(-) diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c index 96638d7ed1..5b550b1e94 100644 --- a/elf/dl-sort-maps.c +++ b/elf/dl-sort-maps.c @@ -27,12 +27,12 @@ If FOR_FINI is true, this is called for finishing an object. */ static void _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps, - unsigned int skip, bool for_fini) + bool force_first, bool for_fini) { /* Allows caller to do the common optimization of skipping the first map, usually the main binary. */ - maps += skip; - nmaps -= skip; + maps += force_first; + nmaps -= force_first; /* A list of one element need not be sorted. */ if (nmaps <= 1) @@ -182,7 +182,7 @@ dfs_traversal (struct link_map ***rpo, struct link_map *map, static void _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, - unsigned int skip __attribute__ ((unused)), bool for_fini) + bool force_first __attribute__ ((unused)), bool for_fini) { for (int i = nmaps - 1; i >= 0; i--) maps[i]->l_visited = 0; @@ -286,7 +286,7 @@ _dl_sort_maps_init (void) void _dl_sort_maps (struct link_map **maps, unsigned int nmaps, - unsigned int skip, bool for_fini) + bool force_first, bool for_fini) { /* It can be tempting to use a static function pointer to store and call the current selected sorting algorithm routine, but experimentation @@ -296,9 +296,9 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps, input cases. A simple if-case with direct function calls appears to be the fastest. */ if (__glibc_likely (GLRO(dl_dso_sort_algo) == dso_sort_algorithm_original)) - _dl_sort_maps_original (maps, nmaps, skip, for_fini); + _dl_sort_maps_original (maps, nmaps, force_first, for_fini); else - _dl_sort_maps_dfs (maps, nmaps, skip, for_fini); + _dl_sort_maps_dfs (maps, nmaps, force_first, for_fini); } #endif /* HAVE_TUNABLES. */ diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h index 050a3032de..6b256b8388 100644 --- a/sysdeps/generic/ldsodefs.h +++ b/sysdeps/generic/ldsodefs.h @@ -1048,9 +1048,11 @@ extern void _dl_init (struct link_map *main_map, int argc, char **argv, initializer functions have completed. */ extern void _dl_fini (void) attribute_hidden; -/* Sort array MAPS according to dependencies of the contained objects. */ +/* Sort array MAPS according to dependencies of the contained objects. + If FORCE_FIRST, MAPS[0] keeps its place even if the dependencies + say otherwise. */ extern void _dl_sort_maps (struct link_map **maps, unsigned int nmaps, - unsigned int skip, bool for_fini) attribute_hidden; + bool force_first, bool for_fini) attribute_hidden; /* The dynamic linker calls this function before and having changing any shared object mappings. The `r_state' member of `struct r_debug' -- 2.37.1 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 2/3] elf: Rename _dl_sort_maps parameter from skip to force_first 2022-08-15 14:30 ` [PATCH 2/3] elf: Rename _dl_sort_maps parameter from skip to force_first Florian Weimer @ 2022-08-29 16:40 ` Adhemerval Zanella Netto 0 siblings, 0 replies; 10+ messages in thread From: Adhemerval Zanella Netto @ 2022-08-29 16:40 UTC (permalink / raw) To: Florian Weimer, libc-alpha On 15/08/22 11:30, Florian Weimer via Libc-alpha wrote: > The new implementation will not be able to skip an arbitrary number > of objects. LGTM, thanks. Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org> > --- > elf/dl-sort-maps.c | 14 +++++++------- > sysdeps/generic/ldsodefs.h | 6 ++++-- > 2 files changed, 11 insertions(+), 9 deletions(-) > > diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c > index 96638d7ed1..5b550b1e94 100644 > --- a/elf/dl-sort-maps.c > +++ b/elf/dl-sort-maps.c > @@ -27,12 +27,12 @@ > If FOR_FINI is true, this is called for finishing an object. */ > static void > _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps, > - unsigned int skip, bool for_fini) > + bool force_first, bool for_fini) > { > /* Allows caller to do the common optimization of skipping the first map, > usually the main binary. */ > - maps += skip; > - nmaps -= skip; > + maps += force_first; > + nmaps -= force_first; > > /* A list of one element need not be sorted. */ > if (nmaps <= 1) > @@ -182,7 +182,7 @@ dfs_traversal (struct link_map ***rpo, struct link_map *map, > > static void > _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, > - unsigned int skip __attribute__ ((unused)), bool for_fini) > + bool force_first __attribute__ ((unused)), bool for_fini) > { > for (int i = nmaps - 1; i >= 0; i--) > maps[i]->l_visited = 0; > @@ -286,7 +286,7 @@ _dl_sort_maps_init (void) > > void > _dl_sort_maps (struct link_map **maps, unsigned int nmaps, > - unsigned int skip, bool for_fini) > + bool force_first, bool for_fini) > { > /* It can be tempting to use a static function pointer to store and call > the current selected sorting algorithm routine, but experimentation > @@ -296,9 +296,9 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps, > input cases. A simple if-case with direct function calls appears to > be the fastest. */ > if (__glibc_likely (GLRO(dl_dso_sort_algo) == dso_sort_algorithm_original)) > - _dl_sort_maps_original (maps, nmaps, skip, for_fini); > + _dl_sort_maps_original (maps, nmaps, force_first, for_fini); > else > - _dl_sort_maps_dfs (maps, nmaps, skip, for_fini); > + _dl_sort_maps_dfs (maps, nmaps, force_first, for_fini); > } > > #endif /* HAVE_TUNABLES. */ > diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h > index 050a3032de..6b256b8388 100644 > --- a/sysdeps/generic/ldsodefs.h > +++ b/sysdeps/generic/ldsodefs.h > @@ -1048,9 +1048,11 @@ extern void _dl_init (struct link_map *main_map, int argc, char **argv, > initializer functions have completed. */ > extern void _dl_fini (void) attribute_hidden; > > -/* Sort array MAPS according to dependencies of the contained objects. */ > +/* Sort array MAPS according to dependencies of the contained objects. > + If FORCE_FIRST, MAPS[0] keeps its place even if the dependencies > + say otherwise. */ > extern void _dl_sort_maps (struct link_map **maps, unsigned int nmaps, > - unsigned int skip, bool for_fini) attribute_hidden; > + bool force_first, bool for_fini) attribute_hidden; > > /* The dynamic linker calls this function before and having changing > any shared object mappings. The `r_state' member of `struct r_debug' ^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 3/3] elf: Implement force_first handling in _dl_sort_maps_dfs 2022-08-15 14:30 [PATCH 0/3] Forced ordering for DFS ELF dependency sorting (bug 28937) Florian Weimer 2022-08-15 14:30 ` [PATCH 1/3] scripts/dso-ordering-test.py: Generate program run-time dependencies Florian Weimer 2022-08-15 14:30 ` [PATCH 2/3] elf: Rename _dl_sort_maps parameter from skip to force_first Florian Weimer @ 2022-08-15 14:30 ` Florian Weimer 2022-08-31 16:37 ` Adhemerval Zanella Netto 2 siblings, 1 reply; 10+ messages in thread From: Florian Weimer @ 2022-08-15 14:30 UTC (permalink / raw) To: libc-alpha 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. --- 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]; 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 -- 2.37.1 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 3/3] elf: Implement force_first handling in _dl_sort_maps_dfs 2022-08-15 14:30 ` [PATCH 3/3] elf: Implement force_first handling in _dl_sort_maps_dfs Florian Weimer @ 2022-08-31 16:37 ` Adhemerval Zanella Netto 2022-08-31 16:37 ` Adhemerval Zanella Netto 2022-09-06 6:39 ` Florian Weimer 0 siblings, 2 replies; 10+ messages in thread From: Adhemerval Zanella Netto @ 2022-08-31 16:37 UTC (permalink / raw) To: libc-alpha, Florian Weimer 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 3/3] elf: Implement force_first handling in _dl_sort_maps_dfs 2022-08-31 16:37 ` Adhemerval Zanella Netto @ 2022-08-31 16:37 ` Adhemerval Zanella Netto 2022-09-06 6:39 ` Florian Weimer 1 sibling, 0 replies; 10+ messages in thread From: Adhemerval Zanella Netto @ 2022-08-31 16:37 UTC (permalink / raw) To: libc-alpha, Florian Weimer 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 ... ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 3/3] elf: Implement force_first handling in _dl_sort_maps_dfs 2022-08-31 16:37 ` Adhemerval Zanella Netto 2022-08-31 16:37 ` Adhemerval Zanella Netto @ 2022-09-06 6:39 ` Florian Weimer 1 sibling, 0 replies; 10+ messages in thread From: Florian Weimer @ 2022-09-06 6:39 UTC (permalink / raw) To: Adhemerval Zanella Netto; +Cc: libc-alpha * 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2022-09-06 6:39 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-08-15 14:30 [PATCH 0/3] Forced ordering for DFS ELF dependency sorting (bug 28937) Florian Weimer 2022-08-15 14:30 ` [PATCH 1/3] scripts/dso-ordering-test.py: Generate program run-time dependencies Florian Weimer 2022-08-15 14:35 ` Florian Weimer 2022-08-29 14:30 ` Adhemerval Zanella Netto 2022-08-15 14:30 ` [PATCH 2/3] elf: Rename _dl_sort_maps parameter from skip to force_first Florian Weimer 2022-08-29 16:40 ` Adhemerval Zanella Netto 2022-08-15 14:30 ` [PATCH 3/3] elf: Implement force_first handling in _dl_sort_maps_dfs Florian Weimer 2022-08-31 16:37 ` Adhemerval Zanella Netto 2022-08-31 16:37 ` Adhemerval Zanella Netto 2022-09-06 6:39 ` Florian Weimer
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).