* dll_init.cc (dll_list::find_by_modname): New function to search the dll list

for a module name only (no path).
(dll_list::alloc): Initialize newly-added members of struct dll.
(dll_list::append): New function to factor out the append operation
(used by dll_list::topsort).
(dll_list::populate_deps): New function to identify dll dependencies.
(dll_list::topsort): New function to sort the dll list topologically by
dependencies.
(dll_list::topsort_visit): New helper function for the above.
* dll_init.h (dll::ndeps): New class member.
(dll::deps): Ditto.
(dll::modname): Ditto.
(dll_list::find_by_modname): New function related to topsort.
(dll_list::populate_all_deps): Ditto.
(dll_list::populate_deps): Ditto.
(dll_list::topsort): Ditto.
(dll_list::topsort_visit): Ditto.
(dll_list::append): Ditto.
(pefile): New struct allowing simple introspection of dll images.
* fork.cc (fork): Topologically sort the dll list before forking
* child_info.h (CURR_CHILD_INFO_MAGIC): Refresh.
(child_info::refresh_cygheap): New function.
* spawn.cc (spawn_guts): Call refresh_cygheap before creating a new process to
ensure that cygheap_max is up-to-date.
* fork.cc (frok::parent): Ditto.

6 files changed, 207 insertions, 35 deletions

diff --git a/winsup/cygwin/ChangeLog b/winsup/cygwin/ChangeLog
index 5d377eb..3dcca69 100644
--- a/winsup/cygwin/ChangeLog
+++ b/winsup/cygwin/ChangeLog
@@ -1,3 +1,34 @@
+2011-05-30  Ryan Johnson  <ryan.johnson@cs.utoronto.ca>
+
+	* dll_init.cc (dll_list::find_by_modname): New function to search the
+	dll list for a module name only (no path).
+	(dll_list::alloc): Initialize newly-added members of struct dll.
+	(dll_list::append): New function to factor out the append operation
+	(used by dll_list::topsort).
+	(dll_list::populate_deps): New function to identify dll dependencies.
+	(dll_list::topsort): New function to sort the dll list topologically by
+	dependencies.
+	(dll_list::topsort_visit): New helper function for the above.
+	* dll_init.h (dll::ndeps): New class member.
+	(dll::deps): Ditto.
+	(dll::modname): Ditto.
+	(dll_list::find_by_modname): New function related to topsort.
+	(dll_list::populate_all_deps): Ditto.
+	(dll_list::populate_deps): Ditto.
+	(dll_list::topsort): Ditto.
+	(dll_list::topsort_visit): Ditto.
+	(dll_list::append): Ditto.
+	(pefile): New struct allowing simple introspection of dll images.
+	* fork.cc (fork): Topologically sort the dll list before forking
+
+2011-05-30  Christopher Faylor  <me.cygwin2011@cgf.cx>
+
+	* child_info.h (CURR_CHILD_INFO_MAGIC): Refresh.
+	(child_info::refresh_cygheap): New function.
+	* spawn.cc (spawn_guts): Call refresh_cygheap before creating a new
+	process to ensure that cygheap_max is up-to-date.
+	* fork.cc (frok::parent): Ditto.
+
 2011-05-30  Christopher Faylor  <me.cygwin2011@cgf.cx>
 
 	* cygheap.cc (cygheap_dummy): Rename from cygheap_at_start.
@@ -926,7 +957,7 @@
 
 	* fhandler.h (fhandler_dev_tape::_lock): Add bool parameter.
 	* fhandler_tape.cc (lock): Call _lock with false argument.
-	(_lock): Take bool cancelable parameter.  Handle O_NONBLOCK. 
+	(_lock): Take bool cancelable parameter.  Handle O_NONBLOCK.
 	Make cancelable if cancelabe parameter is true.
 	(fhandler_dev_tape::raw_read): Call _lock with true argument.
 	(fhandler_dev_tape::raw_write): Ditto.
@@ -1125,7 +1156,7 @@
 	(close): Ditto.
 	(fsync): Ditto.
 	* termios.cc (tcdrain): Ditto.
-	* thread.cc: Align list of cancellation points with above changes. 
+	* thread.cc: Align list of cancellation points with above changes.
 	Mark not-implemented functions, too.
 	(cancelable_wait): Don't set unused object indices to WAIT_FAILED
 	since that could result in wrong behaviour.  Set them to the invalid
@@ -1387,7 +1418,7 @@
 	* path.h (isproc_dev): Use FH_PROC_MAX_MINOR rather than FH_PROC.
 
 2011-04-19  Peter Rosin  <peda@lysator.liu.se>
-	
+
 	* select.cc (pipe_cleanup): Make sure that device_specific_pipe is
 	always deleted regardless of whether it has a unique thread associated
 	with it.
@@ -1422,7 +1453,7 @@
 	(get_registry_hive_path): Use RtlQueryRegistryValues to fetch path from
 	registry.
 	(load_registry_hive): Drop useless check for user hive being available.
-	Load hive using NtLoadKey. 
+	Load hive using NtLoadKey.
 	* registry.h: Accommodate above changes.
 	* sched.cc (sched_rr_get_interval): Use wide char arguments in reg_key
 	functions.
@@ -2574,7 +2605,7 @@
 	to implement ondemand partition locking.
 	(fhandler_dev_floppy::write_file): Call lock_partition from here if
 	writing failed due to a potential write restriction on a disk
-	partition.  
+	partition.
 	(fhandler_dev_floppy::open): Don't lock partitions here.
 	(fhandler_dev_floppy::close): Keep track of partition handle reference
 	count.  Close handles and remove partitions pointer ony if count is 0.
@@ -2588,7 +2619,7 @@
 	method.
 	* fhandler_floppy.cc (fhandler_dev_floppy::fhandler_dev_floppy): Zero
 	out partitions array.
-	(fhandler_dev_floppy::open): Fix "entire disk" condition for call to 
+	(fhandler_dev_floppy::open): Fix "entire disk" condition for call to
 	DeviceIoControl (FSCTL_ALLOW_EXTENDED_DASD_IO).
 	When opening disks for writing, call DeviceIoControl (FSCTL_LOCK_VOLUME)
 	on all affected disk partitions starting with Vista.
@@ -2611,4 +2642,4 @@
 2011-01-02  Christopher Faylor  <me+cygwin@cgf.cx>
 
 	* ChangeLog-2010: Create from ChangeLog.
-	* ChangeLog: Start fresh. 
+	* ChangeLog: Start fresh.
diff --git a/winsup/cygwin/child_info.h b/winsup/cygwin/child_info.h
index 806cd08..ae236db 100644
--- a/winsup/cygwin/child_info.h
+++ b/winsup/cygwin/child_info.h
@@ -38,7 +38,7 @@ enum child_status
 #define EXEC_MAGIC_SIZE sizeof(child_info)
 
 /* Change this value if you get a message indicating that it is out-of-sync. */
-#define CURR_CHILD_INFO_MAGIC 0x76ca2aaeU
+#define CURR_CHILD_INFO_MAGIC 0xeef5640dU
 
 /* NOTE: Do not make gratuitous changes to the names or organization of the
    below class.  The layout is checksummed to determine compatibility between
@@ -65,6 +65,7 @@ public:
   child_info (unsigned, child_info_types, bool);
   child_info (): subproc_ready (NULL), parent (NULL) {}
   ~child_info ();
+  void refresh_cygheap () { cygheap_max = ::cygheap_max; }
   void ready (bool);
   bool sync (int, HANDLE&, DWORD) __attribute__ ((regparm (3)));
   DWORD proc_retry (HANDLE) __attribute__ ((regparm (2)));
diff --git a/winsup/cygwin/dll_init.cc b/winsup/cygwin/dll_init.cc
index 060ff49..44d7b7a 100644
--- a/winsup/cygwin/dll_init.cc
+++ b/winsup/cygwin/dll_init.cc
@@ -116,6 +116,18 @@ dll_list::operator[] (const PWCHAR name)
   return NULL;
 }
 
+/* Look for a dll based on is short name only (no path) */
+dll *
+dll_list::find_by_modname (const PWCHAR name)
+{
+  dll *d = &start;
+  while ((d = d->next) != NULL)
+    if (!wcscasecmp (name, d->modname))
+      return d;
+
+  return NULL;
+}
+
 #define RETRIES 1000
 
 /* Allocate space for a dll struct. */
@@ -161,15 +173,14 @@ dll_list::alloc (HINSTANCE h, per_process *p, dll_type type)
       d->handle = h;
       d->has_dtors = true;
       d->p = p;
+      d->ndeps = 0;
+      d->deps = NULL;
+      d->modname = wcsrchr (d->name, L'\\');
+      if (d->modname)
+       d->modname++;
       d->image_size = ((pefile*)h)->optional_hdr ()->SizeOfImage;
       d->type = type;
-      if (end == NULL)
-	end = &start;	/* Point to "end" of dll chain. */
-      end->next = d;	/* Standard linked list stuff. */
-      d->next = NULL;
-      d->prev = end;
-      end = d;
-      tot++;
+      append (d);
       if (type == DLL_LOAD)
 	loaded_dlls++;
     }
@@ -178,6 +189,119 @@ dll_list::alloc (HINSTANCE h, per_process *p, dll_type type)
   return d;
 }
 
+void
+dll_list::append (dll* d)
+{
+  if (end == NULL)
+    end = &start;	/* Point to "end" of dll chain. */
+  end->next = d;	/* Standard linked list stuff. */
+  d->next = NULL;
+  d->prev = end;
+  end = d;
+  tot++;
+}
+
+void dll_list::populate_deps (dll* d)
+{
+  WCHAR wmodname[NT_MAX_PATH];
+  pefile* pef = (pefile*) d->handle;
+  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;
+  for (PIMAGE_IMPORT_DESCRIPTOR id=
+	(PIMAGE_IMPORT_DESCRIPTOR) pef->rva (dd->VirtualAddress);
+      dd->Size && id->Name;
+      id++)
+    {
+      char* modname = pef->rva (id->Name);
+      sys_mbstowcs (wmodname, NT_MAX_PATH, modname);
+      if (dll* dep = find_by_modname (wmodname))
+	{
+	  if (d->ndeps >= maxdeps)
+	    {
+	      maxdeps = 2*(1+maxdeps);
+	      d->deps = (dll**) crealloc (d->deps, maxdeps*sizeof (dll*));
+	    }
+	  d->deps[d->ndeps++] = dep;
+	}
+    }
+  
+  /* add one to differentiate no deps from unknown */
+  d->ndeps++;
+}
+
+
+void
+dll_list::topsort ()
+{
+  /* Anything to do? */
+  if (!end)
+    return;
+  
+  /* make sure we have all the deps available */
+  dll* d = &start;
+  while ((d = d->next))
+    if (!d->ndeps)
+      populate_deps (d);
+  
+  /* unlink head and tail pointers so the sort can rebuild the list */
+  d = start.next;
+  start.next = end = NULL;
+  topsort_visit (d, true);
+
+  /* clear node markings made by the sort */
+  d = &start;
+  while ((d = d->next))
+    {
+      debug_printf ("%W", d->modname);
+      for (int i=1; i < -d->ndeps; i++)
+	debug_printf ("-> %W", d->deps[i-1]->modname);
+
+      /* It would be really nice to be able to keep this information
+	 around for next time, but we don't have an easy way to
+	 invalidate cached dependencies when a module unloads. */
+      d->ndeps = 0;
+      cfree (d->deps);
+      d->deps = NULL;
+    }
+}
+
+/* A recursive in-place topological sort. The result is ordered so that
+   dependencies of a dll appear before it in the list.
+
+   NOTE: this algorithm is guaranteed to terminate with a "partial
+   order" of dlls but does not do anything smart about cycles: an
+   arbitrary dependent dll will necessarily appear first. Perhaps not
+   surprisingly, Windows ships several dlls containing dependency
+   cycles, including SspiCli/RPCRT4.dll and a lovely tangle involving
+   USP10/LPK/GDI32/USER32.dll). Fortunately, we don't care about
+   Windows DLLs here, and cygwin dlls should behave better */
+void
+dll_list::topsort_visit (dll* d, bool seek_tail)
+{
+  /* Recurse to the end of the dll chain, then visit nodes as we
+     unwind. We do this because once we start visiting nodes we can no
+     longer trust any _next_ pointers.
+
+     We "mark" visited nodes (to avoid revisiting them) by negating
+     ndeps (undone once the sort completes). */
+  if (seek_tail && d->next)
+    topsort_visit (d->next, true);
+  
+  if (d->ndeps > 0)
+    {
+      d->ndeps = -d->ndeps;
+      for (long i=1; i < -d->ndeps; i++)
+	topsort_visit (d->deps[i-1], false);
+
+      append (d);
+    }
+}
+
+
 dll *
 dll_list::find (void *retaddr)
 {
@@ -322,7 +446,7 @@ reserve_at (const PWCHAR name, DWORD here, DWORD dll_base, DWORD dll_size)
   size = end - here;
   if (!VirtualAlloc ((void *) here, size, MEM_RESERVE, PAGE_NOACCESS))
     api_fatal ("couldn't allocate memory %p(%d) for '%W' alignment, %E\n",
-               here, size, name);
+	       here, size, name);
   return here;
 }
 
@@ -332,7 +456,7 @@ release_at (const PWCHAR name, DWORD here)
 {
   if (!VirtualFree ((void *) here, 0, MEM_RELEASE))
     api_fatal ("couldn't release memory %p for '%W' alignment, %E\n",
-               here, name);
+	       here, name);
 }
 
 /* Reload DLLs after a fork.  Iterates over the list of dynamically loaded
@@ -368,13 +492,13 @@ dll_list::load_after_fork (HANDLE parent)
 	  /* If we reached here on the second iteration of the for loop
 	     then there is a lot of memory to release. */
 	  if (i > 0)
-            {
-              release_upto (d->name, (DWORD) d->handle);
+	    {
+	      release_upto (d->name, (DWORD) d->handle);
 
-              if (preferred_block)
-                release_at (d->name, preferred_block);
-              preferred_block = 0;
-            }
+	      if (preferred_block)
+		release_at (d->name, preferred_block);
+	      preferred_block = 0;
+	    }
 
 	  if (h == d->handle)
 	    break;		/* Success */
@@ -385,19 +509,19 @@ dll_list::load_after_fork (HANDLE parent)
 		       d->name, d->handle, h);
 
 	  /* Dll loaded in the wrong place.  Dunno why this happens but it
-             always seems to happen when there are multiple DLLs with the
-             same base address.  In the "forked" process, the relocated DLL
-             may load at a different address. So, block all of the memory up
-             to the relocated load address and try again. */
+	     always seems to happen when there are multiple DLLs with the
+	     same base address.  In the "forked" process, the relocated DLL
+	     may load at a different address. So, block all of the memory up
+	     to the relocated load address and try again. */
 	  reserve_upto (d->name, (DWORD) d->handle);
 
-          /* Also, if the DLL loaded at a higher address than wanted (probably
-             it's base address), reserve the memory at that address. This can
-             happen if it couldn't load at the preferred base in the parent, but
-             can in the child, due to differences in the load ordering.
-             Block memory at it's preferred address and try again. */
-          if ((DWORD) h > (DWORD) d->handle)
-            preferred_block = reserve_at (d->name, (DWORD) h,
+	  /* Also, if the DLL loaded at a higher address than wanted (probably
+	     it's base address), reserve the memory at that address. This can
+	     happen if it couldn't load at the preferred base in the parent, but
+	     can in the child, due to differences in the load ordering.
+	     Block memory at it's preferred address and try again. */
+	  if ((DWORD) h > (DWORD) d->handle)
+	    preferred_block = reserve_at (d->name, (DWORD) h,
 					  (DWORD) d->handle, d->image_size);
 
 	}
diff --git a/winsup/cygwin/dll_init.h b/winsup/cygwin/dll_init.h
index dc5c570..ea3f628 100644
--- a/winsup/cygwin/dll_init.h
+++ b/winsup/cygwin/dll_init.h
@@ -52,6 +52,9 @@ struct dll
   int count;
   bool has_dtors;
   dll_type type;
+  long ndeps;
+  dll** deps;
+  PWCHAR modname;
   DWORD image_size;
   WCHAR name[1];
   void detach ();
@@ -85,6 +88,13 @@ public:
   void detach (void *);
   void init ();
   void load_after_fork (HANDLE);
+  dll *find_by_modname (const PWCHAR name);
+  void populate_all_deps ();
+  void populate_deps (dll* d);
+  void topsort ();
+  void topsort_visit (dll* d, bool goto_tail);
+  void append (dll* d);
+  
   dll *inext ()
   {
     while ((hold = hold->next))
diff --git a/winsup/cygwin/fork.cc b/winsup/cygwin/fork.cc
index 9e34da6..1dbfebe 100644
--- a/winsup/cygwin/fork.cc
+++ b/winsup/cygwin/fork.cc
@@ -397,6 +397,7 @@ frok::parent (volatile char * volatile stack_here)
   /* Remove impersonation */
   cygheap->user.deimpersonate ();
   fix_impersonation = true;
+  ch.refresh_cygheap ();
 
   while (1)
     {
@@ -601,7 +602,6 @@ extern "C" int
 fork ()
 {
   frok grouped;
-  /* No cygheap allocation beyond this point. */
 
   debug_printf ("entering");
   grouped.load_dlls = 0;
@@ -635,6 +635,11 @@ fork ()
 	return -1;
       }
 
+    /* Put the dll list in topological dependency ordering, in
+       hopes that the child will have a better shot at loading dlls
+       properly if it only has to deal with one at a time.  */
+    dlls.topsort ();
+
     ischild = !!setjmp (grouped.ch.jmp);
 
     volatile char * volatile esp;
diff --git a/winsup/cygwin/spawn.cc b/winsup/cygwin/spawn.cc
index df1eb1a..970f0af 100644
--- a/winsup/cygwin/spawn.cc
+++ b/winsup/cygwin/spawn.cc
@@ -560,6 +560,7 @@ spawn_guts (const char *prog_arg, const char *const *argv,
 	  || cygheap->fdtab.need_fixup_before ()))
     c_flags |= CREATE_SUSPENDED;
 
+  ch.refresh_cygheap ();
   /* When ruid != euid we create the new process under the current original
      account and impersonate in child, this way maintaining the different
      effective vs. real ids.