* mmap.cc: Convert usage of dynamically growing cmalloced arrays to

	cmalloced linked lists throughout.
	(class mmap_record): Add LIST_ENTRY element.
	(mmap_record::match): New method, taking over match algorithm from
	list::search_record.
	(class mmap_list): Rename from class list.  Add LIST_ENTRY.  Convert
	recs to a LIST_HEAD.  Drop nrecs and maxrecs members.
	(mmap_list::get_record): Drop entirely.
	(mmap_list::free_recs): Drop entirely.
	(mmap_list::del_record): Take mmap_record to delete as parameter.
	(mmap_list::search_record): Convert to mmap_record::match.
	(class mmap_areas): Rename from class map.  Convert lists to LIST_HEAD.
	(mmap_areas::get_list): Drop entirely.
	(mmap_areas::del_list): Take mmap_list to delete as parameter.
	(mprotect): Fix indentation.

2 files changed, 176 insertions, 200 deletions

diff --git a/winsup/cygwin/ChangeLog b/winsup/cygwin/ChangeLog
index df62e24bc..0c4f45e9e 100644
--- a/winsup/cygwin/ChangeLog
+++ b/winsup/cygwin/ChangeLog
@@ -1,3 +1,21 @@
+2007-11-27  Corinna Vinschen  <corinna@vinschen.de>
+
+	* mmap.cc: Convert usage of dynamically growing cmalloced arrays to
+	cmalloced linked lists throughout.
+	(class mmap_record): Add LIST_ENTRY element.
+	(mmap_record::match): New method, taking over match algorithm from
+	list::search_record.
+	(class mmap_list): Rename from class list.  Add LIST_ENTRY.  Convert
+	recs to a LIST_HEAD.  Drop nrecs and maxrecs members.
+	(mmap_list::get_record): Drop entirely.
+	(mmap_list::free_recs): Drop entirely.
+	(mmap_list::del_record): Take mmap_record to delete as parameter.
+	(mmap_list::search_record): Convert to mmap_record::match.
+	(class mmap_areas): Rename from class map.  Convert lists to LIST_HEAD.
+	(mmap_areas::get_list): Drop entirely.
+	(mmap_areas::del_list): Take mmap_list to delete as parameter.
+	(mprotect): Fix indentation.
+
 2007-11-26  Christopher Faylor  <me+cygwin@cgf.cx>
 
 	Change many cygheap allocation routines to their *_abort analogs.
diff --git a/winsup/cygwin/mmap.cc b/winsup/cygwin/mmap.cc
index 69e64b48b..38ca0073f 100644
--- a/winsup/cygwin/mmap.cc
+++ b/winsup/cygwin/mmap.cc
@@ -24,6 +24,7 @@ details. */
 #include "pinfo.h"
 #include "sys/cygwin.h"
 #include "ntdll.h"
+#include <sys/queue.h>
 
 /* __PROT_ATTACH indicates an anonymous mapping which is supposed to be
    attached to a file mapping for pages beyond the file's EOF.  The idea
@@ -231,16 +232,20 @@ MapView (HANDLE h, void *addr, size_t len, DWORD openflags,
    The class structure:
 
    One member of class map per process, global variable mmapped_areas.
-   Contains a dynamic class list array.  Each list entry represents all
-   mapping to a file, keyed by file descriptor and file name hash.
-   Each list entry contains a dynamic class mmap_record array.  Each
-   mmap_record represents exactly one mapping.  For each mapping, there's
+   Contains a singly-linked list of type class mmap_list.  Each mmap_list
+   entry represents all mapping to a file, keyed by file descriptor and
+   file name hash.
+   Each list entry contains a singly-linked list of type class mmap_record.
+   Each mmap_record represents exactly one mapping.  For each mapping, there's
    an additional so called `page_map'.  It's an array of bits, one bit
    per mapped memory page.  The bit is set if the page is accessible,
    unset otherwise. */
 
 class mmap_record
 {
+  public:
+    LIST_ENTRY (mmap_record) mr_next;
+
   private:
     int fd;
     HANDLE mapping_hdl;
@@ -294,6 +299,7 @@ class mmap_record
     void free_page_map () { if (page_map) cfree (page_map); }
 
     DWORD find_unused_pages (DWORD pages) const;
+    bool match (caddr_t addr, DWORD len, caddr_t &m_addr, DWORD &m_len);
     _off64_t map_pages (_off64_t off, DWORD len);
     bool map_pages (caddr_t addr, DWORD len);
     bool unmap_pages (caddr_t addr, DWORD len);
@@ -309,45 +315,40 @@ class mmap_record
     bool compatible_flags (int fl) const;
 };
 
-class list
+class mmap_list
 {
+  public:
+    LIST_ENTRY (mmap_list) ml_next;
+    LIST_HEAD (, mmap_record) recs;
+
   private:
-    mmap_record *recs;
-    int nrecs, maxrecs;
     int fd;
     __ino64_t hash;
 
   public:
     int get_fd () const { return fd; }
     __ino64_t get_hash () const { return hash; }
-    mmap_record *get_record (int i) { return i >= nrecs ? NULL : recs + i; }
 
     bool anonymous () const { return fd == -1; }
     void set (int nfd, struct __stat64 *st);
     mmap_record *add_record (mmap_record r);
-    bool del_record (int i);
-    void free_recs () { if (recs) cfree (recs); }
+    bool del_record (mmap_record *rec);
     mmap_record *search_record (_off64_t off, DWORD len);
-    long search_record (caddr_t addr, DWORD len, caddr_t &m_addr, DWORD &m_len,
-		long start);
     caddr_t try_map (void *addr, size_t len, int flags, _off64_t off);
 };
 
-class map
+class mmap_areas
 {
-  private:
-    list *lists;
-    unsigned nlists, maxlists;
-
   public:
-    list *get_list (unsigned i) { return i >= nlists ? NULL : lists + i; }
-    list *get_list_by_fd (int fd, struct __stat64 *st);
-    list *add_list (int fd, struct __stat64 *st);
-    void del_list (unsigned i);
+    LIST_HEAD (, mmap_list) lists;
+
+    mmap_list *get_list_by_fd (int fd, struct __stat64 *st);
+    mmap_list *add_list (int fd, struct __stat64 *st);
+    void del_list (mmap_list *ml);
 };
 
 /* This is the global map structure pointer. */
-static map mmapped_areas;
+static mmap_areas mmapped_areas;
 
 bool
 mmap_record::compatible_flags (int fl) const
@@ -378,6 +379,25 @@ mmap_record::find_unused_pages (DWORD pages) const
 }
 
 bool
+mmap_record::match (caddr_t addr, DWORD len, caddr_t &m_addr, DWORD &m_len)
+{
+  caddr_t low = (addr >= get_address ()) ? addr : get_address ();
+  caddr_t high = get_address ();
+  if (filler ())
+    high += get_len ();
+  else
+    high += (PAGE_CNT (get_len ()) * getsystempagesize ());
+  high = (addr + len < high) ? addr + len : high;
+  if (low < high)
+    {
+      m_addr = low;
+      m_len = high - low;
+      return true;
+    }
+  return false;
+}
+
+bool
 mmap_record::alloc_page_map ()
 {
   /* Allocate one bit per page */
@@ -517,79 +537,48 @@ mmap_record::free_fh (fhandler_base *fh)
 }
 
 mmap_record *
-list::add_record (mmap_record r)
+mmap_list::add_record (mmap_record r)
 {
-  if (nrecs == maxrecs)
+  mmap_record *rec = (mmap_record *) cmalloc (HEAP_MMAP, sizeof (mmap_record));
+  if (!rec)
+    return NULL;
+  *rec = r;
+  if (!rec->alloc_page_map ())
     {
-      mmap_record *new_recs;
-      if (maxrecs == 0)
-	new_recs = (mmap_record *)
-			cmalloc (HEAP_MMAP, 5 * sizeof (mmap_record));
-      else
-	new_recs = (mmap_record *)
-			crealloc (recs, (maxrecs + 5) * sizeof (mmap_record));
-      if (!new_recs)
-	return NULL;
-      maxrecs += 5;
-      recs = new_recs;
+      cfree (rec);
+      return NULL;
     }
-  recs[nrecs] = r;
-  if (!recs[nrecs].alloc_page_map ())
-    return NULL;
-  return recs + nrecs++;
+  LIST_INSERT_HEAD (&recs, rec, mr_next);
+  return rec;
 }
 
 /* Used in mmap() */
 mmap_record *
-list::search_record (_off64_t off, DWORD len)
+mmap_list::search_record (_off64_t off, DWORD len)
 {
+  mmap_record *rec;
+
   if (anonymous () && !off)
     {
       len = PAGE_CNT (len);
-      for (int i = 0; i < nrecs; ++i)
-	if (recs[i].find_unused_pages (len) != (DWORD)-1)
-	  return recs + i;
+      LIST_FOREACH (rec, &recs, mr_next)
+	if (rec->find_unused_pages (len) != (DWORD)-1)
+	  return rec;
     }
   else
     {
-      for (int i = 0; i < nrecs; ++i)
-	if (off >= recs[i].get_offset ()
+      LIST_FOREACH (rec, &recs, mr_next)
+	if (off >= rec->get_offset ()
 	    && off + len
-	       <= recs[i].get_offset ()
-		  + (PAGE_CNT (recs[i].get_len ()) * getsystempagesize ()))
-	  return recs + i;
+	       <= rec->get_offset ()
+		  + (PAGE_CNT (rec->get_len ()) * getsystempagesize ()))
+	  return rec;
     }
   return NULL;
 }
 
-/* Used in munmap() */
-long
-list::search_record (caddr_t addr, DWORD len, caddr_t &m_addr, DWORD &m_len,
-		     long start)
-{
-  caddr_t low, high;
-
-  for (long i = start + 1; i < nrecs; ++i)
-    {
-      low = (addr >= recs[i].get_address ()) ? addr : recs[i].get_address ();
-      high = recs[i].get_address ();
-      if (recs[i].filler ())
-	high += recs[i].get_len ();
-      else
-	high += (PAGE_CNT (recs[i].get_len ()) * getsystempagesize ());
-      high = (addr + len < high) ? addr + len : high;
-      if (low < high)
-	{
-	  m_addr = low;
-	  m_len = high - low;
-	  return i;
-	}
-    }
-  return -1;
-}
-
 void
-list::set (int nfd, struct __stat64 *st)
+mmap_list::set (int nfd, struct __stat64 *st)
 {
   fd = nfd;
   if (!anonymous ())
@@ -599,27 +588,22 @@ list::set (int nfd, struct __stat64 *st)
 	 the file. */
       hash = st ? st->st_ino : (__ino64_t) 0;
     }
-  nrecs = maxrecs = 0;
-  recs = NULL;
+  LIST_INIT (&recs);
 }
 
 bool
-list::del_record (int i)
+mmap_list::del_record (mmap_record *rec)
 {
-  if (i < nrecs)
-    {
-      recs[i].free_page_map ();
-      for (; i < nrecs - 1; i++)
-	recs[i] = recs[i + 1];
-      nrecs--;
-    }
+  rec->free_page_map ();
+  LIST_REMOVE (rec, mr_next);
+  cfree (rec);
   /* Return true if the list is empty which allows the caller to remove
-     this list from the list array. */
-  return !nrecs;
+     this list from the list of lists. */
+  return !LIST_FIRST(&recs);
 }
 
 caddr_t
-list::try_map (void *addr, size_t len, int flags, _off64_t off)
+mmap_list::try_map (void *addr, size_t len, int flags, _off64_t off)
 {
   mmap_record *rec;
 
@@ -642,11 +626,12 @@ list::try_map (void *addr, size_t len, int flags, _off64_t off)
 	 if a memory region is unmapped and remapped with MAP_FIXED. */
       caddr_t u_addr;
       DWORD u_len;
-      long record_idx = -1;
-      if ((record_idx = search_record ((caddr_t) addr, len, u_addr, u_len,
-				       record_idx)) >= 0)
+
+      LIST_FOREACH (rec, &recs, mr_next)
+	if (rec->match ((caddr_t) addr, len, u_addr, u_len))
+	  break;
+      if (rec)
 	{
-	  rec = get_record (record_idx);
 	  if (u_addr > (caddr_t) addr || u_addr + len < (caddr_t) addr + len
 	      || !rec->compatible_flags (flags))
 	    {
@@ -664,52 +649,39 @@ list::try_map (void *addr, size_t len, int flags, _off64_t off)
   return NULL;
 }
 
-list *
-map::get_list_by_fd (int fd, struct __stat64 *st)
+mmap_list *
+mmap_areas::get_list_by_fd (int fd, struct __stat64 *st)
 {
-  unsigned i;
-  for (i = 0; i < nlists; i++)
+  mmap_list *ml;
+  LIST_FOREACH (ml, &lists, ml_next)
     {
-      if (fd == -1 && lists[i].anonymous ())
-	return lists + i;
+      if (fd == -1 && ml->anonymous ())
+	return ml;
       /* The fd isn't sufficient since it could already be the fd of another
 	 file.  So we use the inode number as evaluated by fstat to identify
 	 the file. */
-      if (fd != -1 && st && lists[i].get_hash () == st->st_ino)
-	return lists + i;
+      if (fd != -1 && st && ml->get_hash () == st->st_ino)
+	return ml;
     }
   return 0;
 }
 
-list *
-map::add_list (int fd, struct __stat64 *st)
+mmap_list *
+mmap_areas::add_list (int fd, struct __stat64 *st)
 {
-  if (nlists == maxlists)
-    {
-      list *new_lists;
-      if (maxlists == 0)
-	new_lists = (list *) cmalloc (HEAP_MMAP, 5 * sizeof (list));
-      else
-	new_lists = (list *) crealloc (lists, (maxlists + 5) * sizeof (list));
-      if (!new_lists)
-	return NULL;
-      maxlists += 5;
-      lists = new_lists;
-    }
-  lists[nlists].set (fd, st);
-  return lists + nlists++;
+  mmap_list *ml = (mmap_list *) cmalloc (HEAP_MMAP, sizeof (mmap_list));
+  if (!ml)
+    return NULL;
+  ml->set (fd, st);
+  LIST_INSERT_HEAD (&lists, ml, ml_next);
+  return ml;
 }
 
 void
-map::del_list (unsigned i)
+mmap_areas::del_list (mmap_list *ml)
 {
-  if (i < nlists)
-    {
-      lists[i].free_recs ();
-      for (; i < nlists - 1; i++)
-	lists[i] = lists[i + 1];
-      nlists--;
-    }
+  LIST_REMOVE (ml, ml_next);
+  cfree (ml);
 }
 
 /* This function is called from exception_handler when a segmentation
@@ -733,7 +705,7 @@ map::del_list (unsigned i)
 mmap_region_status
 mmap_is_attached_or_noreserve (void *addr, size_t len)
 {
-  list *map_list = mmapped_areas.get_list_by_fd (-1, NULL);
+  mmap_list *map_list = mmapped_areas.get_list_by_fd (-1, NULL);
 
   size_t pagesize = getpagesize ();
   caddr_t start_addr = (caddr_t) rounddown ((uintptr_t) addr, pagesize);
@@ -743,16 +715,14 @@ mmap_is_attached_or_noreserve (void *addr, size_t len)
   if (map_list == NULL)
     return MMAP_NONE;
 
-  while (len > 0)
-    {
-      caddr_t u_addr;
-      DWORD u_len;
-      long record_idx = map_list->search_record (start_addr, len,
-						 u_addr, u_len, -1);
-      if (record_idx < 0)
-	return MMAP_NONE;
+  mmap_record *rec;
+  caddr_t u_addr;
+  DWORD u_len;
 
-      mmap_record *rec = map_list->get_record (record_idx);
+  LIST_FOREACH (rec, &map_list->recs, mr_next)
+    {
+      if (!rec->match (start_addr, len, u_addr, u_len))
+	continue;
       if (rec->attached ())
 	return MMAP_RAISE_SIGBUS;
       if (!rec->noreserve ())
@@ -768,13 +738,14 @@ mmap_is_attached_or_noreserve (void *addr, size_t len)
 
       start_addr += commit_len;
       len -= commit_len;
+      if (!len)
+	return MMAP_NORESERVE_COMMITED;
     }
-
-    return MMAP_NORESERVE_COMMITED;
+  return MMAP_NONE;
 }
 
 static caddr_t
-mmap_worker (list *map_list, fhandler_base *fh, caddr_t base, size_t len,
+mmap_worker (mmap_list *map_list, fhandler_base *fh, caddr_t base, size_t len,
 	     int prot, int flags, int fd, _off64_t off, struct __stat64 *st)
 {
   HANDLE h = fh->mmap (&base, len, prot, flags, off);
@@ -807,7 +778,7 @@ mmap64 (void *addr, size_t len, int prot, int flags, int fd, _off64_t off)
   fhandler_base *fh = NULL;
   fhandler_disk_file *fh_disk_file = NULL; /* Used for reopening a disk file
 					      when necessary. */
-  list *map_list = NULL;
+  mmap_list *map_list = NULL;
   size_t orig_len = 0;
   caddr_t base = NULL;
   struct __stat64 st;
@@ -1113,19 +1084,17 @@ munmap (void *addr, size_t len)
 
   /* Iterate through the map, unmap pages between addr and addr+len
      in all maps. */
-  list *map_list;
-  for (unsigned list_idx = 0;
-       (map_list = mmapped_areas.get_list (list_idx));
-       ++list_idx)
+  mmap_list *map_list, *next_map_list;
+  LIST_FOREACH_SAFE (map_list, &mmapped_areas.lists, ml_next, next_map_list)
     {
-      long record_idx = -1;
+      mmap_record *rec, *next_rec;
       caddr_t u_addr;
       DWORD u_len;
 
-      while ((record_idx = map_list->search_record((caddr_t)addr, len, u_addr,
-						   u_len, record_idx)) >= 0)
-	{
-	  mmap_record *rec = map_list->get_record (record_idx);
+      LIST_FOREACH_SAFE (rec, &map_list->recs, mr_next, next_rec)
+        {
+	  if (!rec->match ((caddr_t) addr, len, u_addr, u_len))
+	    continue;
 	  if (rec->unmap_pages (u_addr, u_len))
 	    {
 	      /* The whole record has been unmapped, so we now actually
@@ -1137,11 +1106,11 @@ munmap (void *addr, size_t len)
 	      rec->free_fh (fh);
 
 	      /* ...and delete the record. */
-	      if (map_list->del_record (record_idx--))
+	      if (map_list->del_record (rec))
 		{
 		  /* Yay, the last record has been removed from the list,
 		     we can remove the list now, too. */
-		  mmapped_areas.del_list (list_idx--);
+		  mmapped_areas.del_list (map_list);
 		  break;
 		}
 	    }
@@ -1159,7 +1128,7 @@ extern "C" int
 msync (void *addr, size_t len, int flags)
 {
   int ret = -1;
-  list *map_list;
+  mmap_list *map_list;
 
   syscall_printf ("msync (addr: %p, len %u, flags %x)", addr, len, flags);
 
@@ -1178,26 +1147,22 @@ msync (void *addr, size_t len, int flags)
 
   /* Iterate through the map, looking for the mmapped area.
      Error if not found. */
-  for (unsigned list_idx = 0;
-       (map_list = mmapped_areas.get_list (list_idx));
-       ++list_idx)
+  LIST_FOREACH (map_list, &mmapped_areas.lists, ml_next)
     {
       mmap_record *rec;
-      for (int record_idx = 0;
-	   (rec = map_list->get_record (record_idx));
-	   ++record_idx)
+      LIST_FOREACH (rec, &map_list->recs, mr_next)
 	{
-	  if (rec->access ((caddr_t)addr))
+	  if (rec->access ((caddr_t) addr))
 	    {
 	      /* Check whole area given by len. */
 	      for (DWORD i = getpagesize (); i < len; i += getpagesize ())
-		if (!rec->access ((caddr_t)addr + i))
+		if (!rec->access ((caddr_t) addr + i))
 		  {
 		    set_errno (ENOMEM);
 		    goto out;
 		  }
 	      fhandler_base *fh = rec->alloc_fh ();
-	      ret = fh->msync (rec->get_handle (), (caddr_t)addr, len, flags);
+	      ret = fh->msync (rec->get_handle (), (caddr_t) addr, len, flags);
 	      rec->free_fh (fh);
 	      goto out;
 	    }
@@ -1238,40 +1203,37 @@ mprotect (void *addr, size_t len, int prot)
 
   /* Iterate through the map, protect pages between addr and addr+len
      in all maps. */
-  list *map_list;
-  for (unsigned list_idx = 0;
-      (map_list = mmapped_areas.get_list (list_idx));
-      ++list_idx)
-   {
-     long record_idx = -1;
-     caddr_t u_addr;
-     DWORD u_len;
-
-     while ((record_idx = map_list->search_record((caddr_t)addr, len,
-						  u_addr, u_len,
-						  record_idx)) >= 0)
-       {
-	 mmap_record *rec = map_list->get_record (record_idx);
-	 in_mapped = true;
-	 if (rec->attached ())
-	   continue;
-	 new_prot = gen_protect (prot, rec->get_flags ());
-	 if (rec->noreserve ())
-	   {
-	     if (new_prot == PAGE_NOACCESS)
-	       ret = VirtualFree (u_addr, u_len, MEM_DECOMMIT);
-	     else
-	       ret = !!VirtualAlloc (u_addr, u_len, MEM_COMMIT, new_prot);
-	   }
-	 else
-	   ret = VirtualProtect (u_addr, u_len, new_prot, &old_prot);
-	 if (!ret)
-	   {
-	     __seterrno ();
-	     break;
-	   }
-       }
-   }
+  mmap_list *map_list;
+  LIST_FOREACH (map_list, &mmapped_areas.lists, ml_next)
+    {
+      mmap_record *rec;
+      caddr_t u_addr;
+      DWORD u_len;
+
+      LIST_FOREACH (rec, &map_list->recs, mr_next)
+        {
+	  if (!rec->match ((caddr_t) addr, len, u_addr, u_len))
+	    continue;
+	  in_mapped = true;
+	  if (rec->attached ())
+	    continue;
+	  new_prot = gen_protect (prot, rec->get_flags ());
+	  if (rec->noreserve ())
+	    {
+	      if (new_prot == PAGE_NOACCESS)
+		ret = VirtualFree (u_addr, u_len, MEM_DECOMMIT);
+	      else
+		ret = !!VirtualAlloc (u_addr, u_len, MEM_COMMIT, new_prot);
+	    }
+	  else
+	    ret = VirtualProtect (u_addr, u_len, new_prot, &old_prot);
+	  if (!ret)
+	    {
+	      __seterrno ();
+	      break;
+	    }
+	}
+    }
 
   ReleaseResourceLock (LOCK_MMAP_LIST, WRITE_LOCK | READ_LOCK, "mprotect");
 
@@ -1757,15 +1719,11 @@ int __stdcall
 fixup_mmaps_after_fork (HANDLE parent)
 {
   /* Iterate through the map */
-  list *map_list;
-  for (unsigned list_idx = 0;
-       (map_list = mmapped_areas.get_list (list_idx));
-       ++list_idx)
+  mmap_list *map_list;
+  LIST_FOREACH (map_list, &mmapped_areas.lists, ml_next)
     {
       mmap_record *rec;
-      for (int record_idx = 0;
-	   (rec = map_list->get_record (record_idx));
-	   ++record_idx)
+      LIST_FOREACH (rec, &map_list->recs, mr_next)
 	{
 	  debug_printf ("fd %d, h 0x%x, address %p, len 0x%x, prot: 0x%x, "
 			"flags: 0x%x, offset %X",