[PATCH] Preserve order of dlopen'd modules in dll_list::topsort

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[PATCH] Preserve order of dlopen'd modules in dll_list::topsort

David Allsopp-4
This patch (below - I hope I have managed to format this email correctly)
alters the behaviour of dll_list::topsort to preserve the order of dlopen'd
units.

The load order of unrelated DLLs is reversed every time fork is called,
since dll_list::topsort finds the tail of the list and then unwinds to
reinsert items. My change takes advantage of what should be undefined
behaviour in dll_list::populate_deps (ndeps non-zero and ndeps and deps not
initialised) to allow the deps field to be initialised prior to the call and
appended to, rather than overwritten.

All DLLs which have been dlopen'd have their deps list initialised with the
list of all previously dlopen'd units. These extra dependencies mean that
the unwind preserves the order of dlopen'd units.

The motivation for this is the FlexDLL linker used in OCaml. The FlexDLL
linker allows a dlopen'd unit to refer to symbols in previously dlopen'd
units and it resolves these symbols in DllMain before anything else has
initialised (including the Cygwin DLL). This means that dependencies may
exist between dlopen'd units (which the OCaml runtime system understands)
but which Windows is unaware of. During fork, the process-level table which
FlexDLL uses to get the symbol table of each DLL is copied over but because
the load order of dlopen'd DLLs is reversed, it is possible for FlexDLL to
attempt to access memory in the DLL before it has been loaded and hence it
fails with an access violation. Because the list is reversed on each call to
fork, it means that a subsequent call to fork puts the DLLs back into the
correct order, hence "even" invocations of fork work!

An interesting side-effect is that this only occurs if the DLLs load at
their preferred base address - if they have to be rebased, then FlexDLL
works because at the time that the dependent unit is loaded out of order,
there is still in memory the "dummy" DONT_RESOLVE_DLL_REFERENCES version of
the dependency which, as it happens, will contain the correct symbol table
in the data section. For my tests, this initially appeared to be an x86-only
problem, but that was only because the two DLLs on x64 should have been
rebased.

I'm very happy to include the complete detail for this and, for the
extremely keen, the relevant Git branch in OCaml which demonstrates this
problem. Given the way in which FlexDLL operates, I would contend that this
is a sensible change of behaviour for the Cygwin DLL, though not a bug fix.
I'd be extremely happy to see this patch integrated, as the workaround
necessary in FlexDLL to support Cygwin's fork is horrible (and
non-transparent to the library user).

This patch is licensed under 2-clause BSD as per winsup/CONTRIBUTORS,
Copyright (c) 2017, MetaStack Solutions Ltd.


--dra

Signed-off-by: David Allsopp <[hidden email]>
---
 winsup/cygwin/dll_init.cc   | 45
++++++++++++++++++++++++++++++++++++++++++---
 winsup/cygwin/release/2.7.1 |  2 ++
 2 files changed, 44 insertions(+), 3 deletions(-)

diff --git a/winsup/cygwin/dll_init.cc b/winsup/cygwin/dll_init.cc index
0fe5714..d3c6114 100644
--- a/winsup/cygwin/dll_init.cc
+++ b/winsup/cygwin/dll_init.cc
@@ -271,9 +271,16 @@ void dll_list::populate_deps (dll* d)
   PIMAGE_DATA_DIRECTORY dd = pef->idata_dir (IMAGE_DIRECTORY_ENTRY_IMPORT);
   /* Annoyance: calling crealloc with a NULL pointer will use the
      wrong heap and crash, so we have to replicate some code */
-  long maxdeps = 4;
-  d->deps = (dll**) cmalloc (HEAP_2_DLL, maxdeps*sizeof (dll*));
-  d->ndeps = 0;
+  long maxdeps;
+  if (d->ndeps == 0)
+    {
+      maxdeps = 4;
+      d->deps = (dll**) cmalloc (HEAP_2_DLL, maxdeps*sizeof (dll*));
+    }
+  else
+    {
+      maxdeps = d->ndeps;
+    }
   for (PIMAGE_IMPORT_DESCRIPTOR id=
  (PIMAGE_IMPORT_DESCRIPTOR) pef->rva (dd->VirtualAddress);
       dd->Size && id->Name;
@@ -304,6 +311,38 @@ dll_list::topsort ()
   if (!end || end == &start)
     return;
 
+  if (loaded_dlls > 0)
+    {
+      /* Ensure that all dlopen'd DLLs depend on previously dlopen'd DLLs.
This prevents topsort
+         from reversing the order of dlopen'd DLLs on calls to fork. */
+      dll* d = &start;
+      long maxdeps = 4;
+      long dlopen_ndeps = 0;
+      dll** dlopen_deps = (dll**) cmalloc (HEAP_2_DLL, maxdeps*sizeof
(dll*));
+      while ((d = d->next))
+        {
+          if (d->type == DLL_LOAD)
+            {
+              /* Initialise d->deps with all previously dlopen'd DLLs. */
+              if (dlopen_ndeps)
+                {
+                  d->ndeps = dlopen_ndeps;
+                  d->deps = (dll**) cmalloc (HEAP_2_DLL,
dlopen_ndeps*sizeof (dll*));
+                  memcpy (d->deps, dlopen_deps, dlopen_ndeps*sizeof
(dll*));
+                  populate_deps (d);
+                }
+              /* Add this DLL to the list of previously dlopen'd DLLs. */
+              if (dlopen_ndeps >= maxdeps)
+                {
+                  maxdeps = 2*(1+maxdeps);
+                  dlopen_deps = (dll**) crealloc(dlopen_deps,
maxdeps*sizeof (dll*));
+                }
+              dlopen_deps[dlopen_ndeps++] = d;
+            }
+        }
+      cfree(dlopen_deps);
+    }
+
   /* make sure we have all the deps available */
   dll* d = &start;
   while ((d = d->next))
diff --git a/winsup/cygwin/release/2.7.1 b/winsup/cygwin/release/2.7.1 index
54e1100..411a0ae 100644
--- a/winsup/cygwin/release/2.7.1
+++ b/winsup/cygwin/release/2.7.1
@@ -8,6 +8,8 @@ What changed:
 - cygcheck and strace now always generate output with Unix LF line endings,
   rather than with DOS/Windows CR LF line endings.
 
+- fork now preserves the load order of unrelated dlopen'd modules.
+
 
 Bug Fixes
 ---------
--
2.10.2.windows.1


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [PATCH] Preserve order of dlopen'd modules in dll_list::topsort

Corinna Vinschen-2
Hi David,

On Feb 25 16:27, David Allsopp wrote:

> This patch (below - I hope I have managed to format this email correctly)
> alters the behaviour of dll_list::topsort to preserve the order of dlopen'd
> units.
>
> The load order of unrelated DLLs is reversed every time fork is called,
> since dll_list::topsort finds the tail of the list and then unwinds to
> reinsert items. My change takes advantage of what should be undefined
> behaviour in dll_list::populate_deps (ndeps non-zero and ndeps and deps not
> initialised) to allow the deps field to be initialised prior to the call and
> appended to, rather than overwritten.
>
> All DLLs which have been dlopen'd have their deps list initialised with the
> list of all previously dlopen'd units. These extra dependencies mean that
> the unwind preserves the order of dlopen'd units.
>
> The motivation for this is the FlexDLL linker used in OCaml. The FlexDLL
> linker allows a dlopen'd unit to refer to symbols in previously dlopen'd
> units and it resolves these symbols in DllMain before anything else has
> initialised (including the Cygwin DLL). This means that dependencies may
> exist between dlopen'd units (which the OCaml runtime system understands)
> but which Windows is unaware of. During fork, the process-level table which
> FlexDLL uses to get the symbol table of each DLL is copied over but because
> the load order of dlopen'd DLLs is reversed, it is possible for FlexDLL to
> attempt to access memory in the DLL before it has been loaded and hence it
> fails with an access violation. Because the list is reversed on each call to
> fork, it means that a subsequent call to fork puts the DLLs back into the
> correct order, hence "even" invocations of fork work!
>
> An interesting side-effect is that this only occurs if the DLLs load at
> their preferred base address - if they have to be rebased, then FlexDLL
> works because at the time that the dependent unit is loaded out of order,
> there is still in memory the "dummy" DONT_RESOLVE_DLL_REFERENCES version of
> the dependency which, as it happens, will contain the correct symbol table
> in the data section. For my tests, this initially appeared to be an x86-only
> problem, but that was only because the two DLLs on x64 should have been
> rebased.
>
> I'm very happy to include the complete detail for this and, for the
> extremely keen, the relevant Git branch in OCaml which demonstrates this
> problem. Given the way in which FlexDLL operates, I would contend that this
> is a sensible change of behaviour for the Cygwin DLL, though not a bug fix.
> I'd be extremely happy to see this patch integrated, as the workaround
> necessary in FlexDLL to support Cygwin's fork is horrible (and
> non-transparent to the library user).
>
> This patch is licensed under 2-clause BSD as per winsup/CONTRIBUTORS,
> Copyright (c) 2017, MetaStack Solutions Ltd.
First of all, I think this makes perfect sense.  I just have a few
questions in terms of the patch itself.

- Your browser inserts undesired line breaks, so the patch is broken.
  Can you please resend the `git format-patch' output as attachment?

- While you're at it, please reformat your patch so the line length
  is not longer than 80 chars.

- Last but not least.  You add code to topsort so the loaded DLLs
  are handled first.  The subsequent code is untouched.  However,
  shouldn't the next loop then restrict calling populate_deps to the
  linked DLLs only, at least for performance?


Thanks,
Corinna

--
Corinna Vinschen                  Please, send mails regarding Cygwin to
Cygwin Maintainer                 cygwin AT cygwin DOT com
Red Hat

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: [PATCH] Preserve order of dlopen'd modules in dll_list::topsort

David Allsopp-4
Hi Corinna,

Corinna Vinschen wrote:

> Hi David,
>
> On Feb 25 16:27, David Allsopp wrote:
> > This patch (below - I hope I have managed to format this email
> > correctly) alters the behaviour of dll_list::topsort to preserve the
> > order of dlopen'd units.
> >
> > The load order of unrelated DLLs is reversed every time fork is
> > called, since dll_list::topsort finds the tail of the list and then
> > unwinds to reinsert items. My change takes advantage of what should be
> > undefined behaviour in dll_list::populate_deps (ndeps non-zero and
> > ndeps and deps not
> > initialised) to allow the deps field to be initialised prior to the
> > call and appended to, rather than overwritten.
> >
> > All DLLs which have been dlopen'd have their deps list initialised
> > with the list of all previously dlopen'd units. These extra
> > dependencies mean that the unwind preserves the order of dlopen'd units.
> >
> > The motivation for this is the FlexDLL linker used in OCaml. The
> > FlexDLL linker allows a dlopen'd unit to refer to symbols in
> > previously dlopen'd units and it resolves these symbols in DllMain
> > before anything else has initialised (including the Cygwin DLL). This
> > means that dependencies may exist between dlopen'd units (which the
> > OCaml runtime system understands) but which Windows is unaware of.
> > During fork, the process-level table which FlexDLL uses to get the
> > symbol table of each DLL is copied over but because the load order of
> > dlopen'd DLLs is reversed, it is possible for FlexDLL to attempt to
> > access memory in the DLL before it has been loaded and hence it fails
> > with an access violation. Because the list is reversed on each call to
> > fork, it means that a subsequent call to fork puts the DLLs back into
> > the correct order, hence "even" invocations of fork work!
> >
> > An interesting side-effect is that this only occurs if the DLLs load
> > at their preferred base address - if they have to be rebased, then
> > FlexDLL works because at the time that the dependent unit is loaded
> > out of order, there is still in memory the "dummy"
> > DONT_RESOLVE_DLL_REFERENCES version of the dependency which, as it
> > happens, will contain the correct symbol table in the data section.
> > For my tests, this initially appeared to be an x86-only problem, but
> > that was only because the two DLLs on x64 should have been rebased.
> >
> > I'm very happy to include the complete detail for this and, for the
> > extremely keen, the relevant Git branch in OCaml which demonstrates
> > this problem. Given the way in which FlexDLL operates, I would contend
> > that this is a sensible change of behaviour for the Cygwin DLL, though
> > not a bug fix.
> > I'd be extremely happy to see this patch integrated, as the workaround
> > necessary in FlexDLL to support Cygwin's fork is horrible (and
> > non-transparent to the library user).
> >
> > This patch is licensed under 2-clause BSD as per winsup/CONTRIBUTORS,
> > Copyright (c) 2017, MetaStack Solutions Ltd.
>
> First of all, I think this makes perfect sense.  I just have a few
> questions in terms of the patch itself.
>
> - Your browser inserts undesired line breaks, so the patch is broken.
>   Can you please resend the `git format-patch' output as attachment?
Darn - sorry about that (it's the first time I'd tried to send a format-patch, rather than as a PR). Patch attached.

> - While you're at it, please reformat your patch so the line length
>   is not longer than 80 chars.

Done - sorry, I'd inferred a longer length from a few other longer lines!

> - Last but not least.  You add code to topsort so the loaded DLLs
>   are handled first.  The subsequent code is untouched.  However,
>   shouldn't the next loop then restrict calling populate_deps to the
>   linked DLLs only, at least for performance?

Oops :$ That's an artefact of the "story" of the patch's development. As it happens, the first dlopen'd DLL would have been initialised in the second loop, not the first, but the presence of two loops like that was indeed mostly inefficient. I've kept the original one as a "fast path" for the case of no dlopen'd DLLs, though I don't know if that's a worthwhile optimisation.

All best,


David

0001-Preserve-order-of-dlopen-d-modules-in-dll_list-topso.patch (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [PATCH] Preserve order of dlopen'd modules in dll_list::topsort

Corinna Vinschen-2
Hi David,

thanks for the new patch.

On Feb 27 17:13, David Allsopp wrote:
> Corinna Vinschen wrote:
> > On Feb 25 16:27, David Allsopp wrote:
> > > This patch (below - I hope I have managed to format this email
> > > correctly) alters the behaviour of dll_list::topsort to preserve the
> > > order of dlopen'd units.
> > > [...]
> > > This patch is licensed under 2-clause BSD as per winsup/CONTRIBUTORS,
> > > Copyright (c) 2017, MetaStack Solutions Ltd.

Do you really want to make it (c) MetaStack?

I'm asking because this way I can't add you personally as contributor to
the CONTRIBUTORS file and you will have to continue to add per-patch
copyright.  The idea of the CONTRIBUTORS file was to claim BSD 2-clause
for your first and all subsequent patches you provide to Cygwin, so you
never have to think about the copyright stuff again.  Your choice.

> > - While you're at it, please reformat your patch so the line length
> >   is not longer than 80 chars.
>
> Done - sorry, I'd inferred a longer length from a few other longer lines!

Yeah, the surrounding codes has a few minor formatting issues, in fact.

> > - Last but not least.  You add code to topsort so the loaded DLLs
> >   are handled first.  The subsequent code is untouched.  However,
> >   shouldn't the next loop then restrict calling populate_deps to the
> >   linked DLLs only, at least for performance?
>
> Oops :$ That's an artefact of the "story" of the patch's development.
> As it happens, the first dlopen'd DLL would have been initialised in
> the second loop, not the first, but the presence of two loops like
> that was indeed mostly inefficient. I've kept the original one as a
> "fast path" for the case of no dlopen'd DLLs, though I don't know if
> that's a worthwhile optimisation.
Well, interesting point.  Basically your new code is a drop-in
replacement, except for the fact that it always calls an extra
cmalloc/cfree.  However, this is only required if loaded_dlls > 0 so I
think we may get away with removing the old loop with a simple tweak to
your new one:

  dll** dlopen_deps = NULL;
  if (loaded_dlls > 0)
    dlopen_deps = (dll**) cmalloc (HEAP_2_DLL, maxdeps*sizeof (dll*));
  while ((d = d->next))
    {
      [...]
    }
  if (dlopen_deps)
    cfree (dlopen_deps);

Do you want to tweak your patch accordingly?


Thanks,
Corinna

--
Corinna Vinschen                  Please, send mails regarding Cygwin to
Cygwin Maintainer                 cygwin AT cygwin DOT com
Red Hat

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: [PATCH] Preserve order of dlopen'd modules in dll_list::topsort

David Allsopp-4
Hi Corinna,

Thanks for the feedback!

Corinna Vinschen wrote:

> Hi David,
>
> thanks for the new patch.
>
> On Feb 27 17:13, David Allsopp wrote:
> > Corinna Vinschen wrote:
> > > On Feb 25 16:27, David Allsopp wrote:
> > > > This patch (below - I hope I have managed to format this email
> > > > correctly) alters the behaviour of dll_list::topsort to preserve
> > > > the order of dlopen'd units.
> > > > [...]
> > > > This patch is licensed under 2-clause BSD as per
> > > > winsup/CONTRIBUTORS, Copyright (c) 2017, MetaStack Solutions Ltd.
>
> Do you really want to make it (c) MetaStack?
Oh, I was assuming that there would just be an implied mapping! Simple is best (MetaStack is just me, anyway!), so the previous patch and this fixup may be merged as my personal copyright, yes.

<snip>

> > > - Last but not least.  You add code to topsort so the loaded DLLs
> > >   are handled first.  The subsequent code is untouched.  However,
> > >   shouldn't the next loop then restrict calling populate_deps to the
> > >   linked DLLs only, at least for performance?
> >
> > Oops :$ That's an artefact of the "story" of the patch's development.
> > As it happens, the first dlopen'd DLL would have been initialised in
> > the second loop, not the first, but the presence of two loops like
> > that was indeed mostly inefficient. I've kept the original one as a
> > "fast path" for the case of no dlopen'd DLLs, though I don't know if
> > that's a worthwhile optimisation.
>
> Well, interesting point.  Basically your new code is a drop-in
> replacement, except for the fact that it always calls an extra
> cmalloc/cfree.  However, this is only required if loaded_dlls > 0 so I
> think we may get away with removing the old loop with a simple tweak to
> your new one:
>
>   dll** dlopen_deps = NULL;
>   if (loaded_dlls > 0)
>     dlopen_deps = (dll**) cmalloc (HEAP_2_DLL, maxdeps*sizeof (dll*));
>   while ((d = d->next))
>     {
>       [...]
>     }
>   if (dlopen_deps)
>     cfree (dlopen_deps);
>
> Do you want to tweak your patch accordingly?
That's much neater - attached is a fixup (which obviously looks a lot clearer with git diff --ignore-all-space)

All best,


David

0001-Fixup-8607cf.patch (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [PATCH] Preserve order of dlopen'd modules in dll_list::topsort

Corinna Vinschen-2
Hi David,

On Feb 28 11:48, David Allsopp wrote:

> Corinna Vinschen wrote:
> > On Feb 27 17:13, David Allsopp wrote:
> > > Corinna Vinschen wrote:
> > > > On Feb 25 16:27, David Allsopp wrote:
> > > > > This patch (below - I hope I have managed to format this email
> > > > > correctly) alters the behaviour of dll_list::topsort to preserve
> > > > > the order of dlopen'd units.
> > > > > [...]
> > > > > This patch is licensed under 2-clause BSD as per
> > > > > winsup/CONTRIBUTORS, Copyright (c) 2017, MetaStack Solutions Ltd.
> >
> > Do you really want to make it (c) MetaStack?
>
> Oh, I was assuming that there would just be an implied mapping! Simple is best (MetaStack is just me, anyway!), so the previous patch and this fixup may be merged as my personal copyright, yes.
>
> <snip>
> >   if (loaded_dlls > 0)
> >     dlopen_deps = (dll**) cmalloc (HEAP_2_DLL, maxdeps*sizeof (dll*));
> >   while ((d = d->next))
> >     {
> >       [...]
> >     }
> >   if (dlopen_deps)
> >     cfree (dlopen_deps);
> >
> > Do you want to tweak your patch accordingly?
>
> That's much neater - attached is a fixup (which obviously looks a lot clearer with git diff --ignore-all-space)
Applied and pushed.  I took the liberty to add two formatting tweaks,
as well as most of the description of your OP for the log message,
and squashed this into a single patch.

I'll uploaded new developer snapshots to https://cygwin.com/snapshots/
containing your patch for testing today.  This might take a while since
I have trouble with my cable provider and my upload speed is currently
almost 0 :-P


Thanks,
Corinna

--
Corinna Vinschen                  Please, send mails regarding Cygwin to
Cygwin Maintainer                 cygwin AT cygwin DOT com
Red Hat

signature.asc (836 bytes) Download Attachment
Loading...