From 97737d1ee3ce95e45a1a4aa636cc2e11a106a9f5 Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Sat, 26 Apr 2014 12:20:20 +0200
Subject: libports: reduce malloc overhead in _ports_bucket_class_iterate

_ports_bucket_class_iterate creates a snapshot of the buckets hash
table.  This is done so that the lock protecting the hash table can be
released while we iterate over the snapshot.

Formerly, a linked list was used to store the snapshot.  As the
maximal number of items is known, using an array is much simpler.

_ports_bucket_class_iterate implements both ports_bucket_iterate and
ports_class_iterate.  For this change might make ports_class_iterate
less efficient memory-wise if the number of ports belonging to the
class is low with respect to the number of ports in the bucket.  If
this happens, we allocate too much.  Alleviate this by releasing
unused memory.

On the other hand, the array representation is more compact.
Furthermore a survey of the Hurd code revealed that
ports_class_iterate is rarely used, while ports_bucket_iterate is used
more often, most prominently in paging code.

* libports/bucket-iterate.c (_ports_bucket_class_iterate): Use an
array instead of a linked list.
---
 libports/bucket-iterate.c | 46 ++++++++++++++++++++++++++++++----------------
 1 file changed, 30 insertions(+), 16 deletions(-)

(limited to 'libports/bucket-iterate.c')

diff --git a/libports/bucket-iterate.c b/libports/bucket-iterate.c
index dc1c7b11..498cf133 100644
--- a/libports/bucket-iterate.c
+++ b/libports/bucket-iterate.c
@@ -31,40 +31,54 @@ _ports_bucket_class_iterate (struct port_bucket *bucket,
 {
   /* This is obscenely ineffecient.  ihash and ports need to cooperate
      more closely to do it efficiently. */
-  struct item
-    {
-      struct item *next;
-      void *p;
-    } *list = 0;
-  struct item *i, *nxt;
+  void **p;
+  size_t i, n, nr_items;
   error_t err;
 
   pthread_mutex_lock (&_ports_lock);
+
+  if (bucket->htable.nr_items == 0)
+    {
+      pthread_mutex_unlock (&_ports_lock);
+      return 0;
+    }
+
+  nr_items = bucket->htable.nr_items;
+  p = malloc (nr_items * sizeof *p);
+  if (p == NULL)
+    return ENOMEM;
+
+  n = 0;
   HURD_IHASH_ITERATE (&bucket->htable, arg)
     {
       struct port_info *const pi = arg;
-      struct item *j;
 
       if (class == 0 || pi->class == class)
 	{
-	  j = malloc (sizeof (struct item));
-	  j->next = list;
-	  j->p = pi;
-	  list = j;
 	  pi->refcnt++;
+	  p[n] = pi;
+	  n++;
 	}
     }
   pthread_mutex_unlock (&_ports_lock);
 
+  if (n != nr_items)
+    {
+      /* We allocated too much.  Release unused memory.  */
+      void **new = realloc (p, n * sizeof *p);
+      if (new)
+        p = new;
+    }
+
   err = 0;
-  for (i = list; i; i = nxt)
+  for (i = 0; i < n; i++)
     {
       if (!err)
-	err = (*fun)(i->p);
-      ports_port_deref (i->p);
-      nxt = i->next;
-      free (i);
+	err = (*fun)(p[i]);
+      ports_port_deref (p[i]);
     }
+
+  free (p);
   return err;
 }
 
-- 
cgit v1.2.3