2008-02-15 Neal H. Walfield <neal@gnu.org>

	* activity.h: Include "list.h".
	(LIST_CLASS_TYPE): Declare a activity_children list.
	(struct activity): Change children's type to a struct
	activity_children_list.  Replace sibling_next and sibling_prev
	with sibling, a struct list_node.
	(activity_for_each_inmemory_child): Remove macro.
	* activity.c (children_list_insert_after): Remove function.
	Replace uses with appropriate list function.
	(children_list_detach): Likewise.
	* pager.c (pager_collect): Replace use of
	activity_for_each_inmemory_child with a list iterator.
	* ager.c (ager_loop): Likewise.

5 files changed, 155 insertions, 193 deletions

diff --git a/viengoos/ChangeLog b/viengoos/ChangeLog
index 11b3b06..f0c7267 100644
--- a/viengoos/ChangeLog
+++ b/viengoos/ChangeLog
@@ -1,5 +1,20 @@
 2008-02-15  Neal H. Walfield  <neal@gnu.org>
 
+	* activity.h: Include "list.h".
+	(LIST_CLASS_TYPE): Declare a activity_children list.
+	(struct activity): Change children's type to a struct
+	activity_children_list.  Replace sibling_next and sibling_prev
+	with sibling, a struct list_node.
+	(activity_for_each_inmemory_child): Remove macro.
+	* activity.c (children_list_insert_after): Remove function.
+	Replace uses with appropriate list function.
+	(children_list_detach): Likewise.
+	* pager.c (pager_collect): Replace use of
+	activity_for_each_inmemory_child with a list iterator.
+	* ager.c (ager_loop): Likewise.
+
+2008-02-15  Neal H. Walfield  <neal@gnu.org>
+
 	* object.h (object_desc_unmap) [_L4_TEST_ENVIRONMENT]: Do nothing.
 	(object_desc_unmap) [_L4_TEST_ENVIRONMENT]: When adding the dirty
 	bit, be careful to make sure that the correct value is bitwise
diff --git a/viengoos/activity.c b/viengoos/activity.c
index 8013af5..906de0b 100644
--- a/viengoos/activity.c
+++ b/viengoos/activity.c
@@ -27,50 +27,6 @@
 
 struct activity *root_activity;
 
-/* Add ACTIVITY to ACTIVITY->PARENT's children list after AFTER.  */
-static void
-children_list_insert_after (struct activity *activity, struct activity *after)
-{
-  assert (activity->parent);
-
-  if (! after)
-    /* Insert at head of list.  */
-    {
-      activity->sibling_next = activity->parent->children;
-      if (activity->parent->children)
-	activity->parent->children->sibling_prev = activity;
-      activity->parent->children = activity;
-    }
-  else
-    {
-      assert (activity->parent == after->parent);
-      assert (after->policy.sibling_rel.priority
-	      >= activity->policy.sibling_rel.priority);
-
-      activity->sibling_next = after->sibling_next;
-      activity->sibling_prev = after;
-      if (activity->sibling_next)
-	activity->sibling_next->sibling_prev = activity;
-      after->sibling_next = activity;
-    }
-}
-
-/* Remove ACTIVITY from ACTIVITY->PARENT's children list.  */
-static void
-children_list_detach (struct activity *activity)
-{
-  if (activity->sibling_prev)
-    activity->sibling_prev->sibling_next = activity->sibling_next;
-  else
-    {
-      assert (activity->parent->children == activity);
-      activity->parent->children = activity->sibling_next;
-    }
-
-  if (activity->sibling_next)
-    activity->sibling_next->sibling_prev = activity->sibling_prev;
-}
-
 void
 activity_create (struct activity *parent,
 		 struct activity *child)
@@ -325,30 +281,30 @@ activity_prepare (struct activity *principal, struct activity *activity)
   assert (activity->parent);
 
   /* Link to parent's children list.  */
-  assert (! activity->parent->children
-	  || ! activity->parent->children->sibling_prev);
-
-  if (! activity->parent->children
-      || (activity->policy.sibling_rel.priority
-	  >= activity->parent->children->policy.sibling_rel.priority))
-    children_list_insert_after (activity, NULL);
+  struct activity *head;
+  head = activity_children_list_head (&activity->parent->children);
+  if (! head || (activity->policy.sibling_rel.priority
+		 >= head->policy.sibling_rel.priority))
+    activity_children_list_insert_after (&activity->parent->children,
+					 activity, NULL);
   else
     {
       struct activity *last;
+      struct activity *next;
 
-      for (last = activity->parent->children;
-	   last->sibling_next
-	     && (last->sibling_next->policy.sibling_rel.priority
+      for (last = head;
+	   (next = activity_children_list_next (last))
+	     && (next->policy.sibling_rel.priority
 		 > activity->policy.sibling_rel.priority);
-	   last = last->sibling_next)
+	   last = next)
 	;
 
       assert (last);
-      children_list_insert_after (activity, last);
+      activity_children_list_insert_after (&activity->parent->children,
+					   activity, last);
     }
 
-  /* ACTIVITY has no in-memory children.  */
-  activity->children = NULL;
+  activity_children_list_init (&activity->children);
 }
 
 void
@@ -356,7 +312,7 @@ activity_deprepare (struct activity *principal, struct activity *victim)
 {
   /* If we have any in-memory children or frames, then we can't be
      paged out.  */
-  assert (! victim->children);
+  assert (! activity_children_list_head (&victim->children));
   assert (! activity_lru_list_count (&victim->active));
   assert (! activity_lru_list_count (&victim->inactive_clean));
   assert (! activity_lru_list_count (&victim->inactive_dirty));
@@ -366,7 +322,7 @@ activity_deprepare (struct activity *principal, struct activity *victim)
   /* Unlink from parent's children list.  */
   assert (victim->parent);
 
-  children_list_detach (victim);
+  activity_children_list_unlink (&victim->parent->children, victim);
 }
 
 void
@@ -386,15 +342,16 @@ activity_policy_update (struct activity *activity,
       activity->policy.sibling_rel.priority = priority;
 
       struct activity *prev;
-      for (prev = activity->sibling_prev;
+      for (prev = activity_children_list_prev (activity);
 	   prev && prev->policy.sibling_rel.priority < priority;
-	   prev = prev->sibling_prev)
+	   prev = activity_children_list_prev (prev))
 	;
 
-      if (prev != activity->sibling_prev)
+      if (prev != activity_children_list_prev (activity))
 	{
-	  children_list_detach (activity);
-	  children_list_insert_after (activity, prev);
+	  activity_children_list_unlink (&activity->parent->children, activity);
+	  activity_children_list_insert_after (&activity->parent->children,
+					       activity, prev);
 	}
     }
   else
@@ -403,16 +360,18 @@ activity_policy_update (struct activity *activity,
       activity->policy.sibling_rel.priority = priority;
 
       struct activity *next;
+      struct activity *next_next;
       for (next = activity;
-	   next->sibling_next
-	     && next->sibling_next->policy.sibling_rel.priority > priority;
-	   next = next->sibling_next)
+	   (next_next = activity_children_list_next (next))
+	     && next_next->policy.sibling_rel.priority > priority;
+	   next = next_next)
 	;
 
       if (next != activity)
 	{
-	  children_list_detach (activity);
-	  children_list_insert_after (activity, next);
+	  activity_children_list_unlink (&activity->parent->children, activity);
+	  activity_children_list_insert_after (&activity->parent->children,
+					       activity, next);
 	}
     }
 
@@ -430,12 +389,16 @@ do_activity_dump (struct activity *activity, int indent)
   int dirty = activity_lru_list_count (&activity->inactive_dirty);
   int clean = activity_lru_list_count (&activity->inactive_clean);
 
-  printf ("%s %llx: %d frames (active: %d, dirty: %d, clean: %d) "
-	  "(total frames: %d)\n",
+  printf ("%s %llx: %d frames (act: %d, drt: %d, cln: %d) "
+	  "(total: %d); %d/%d; %d/%d\n",
 	  indent_string,
 	  object_to_object_desc ((struct object *) activity)->oid,
 	  activity->frames_local, active, dirty, clean,
-	  activity->frames_total);
+	  activity->frames_total,
+	  activity->policy.sibling_rel.priority,
+	  activity->policy.sibling_rel.weight,
+	  activity->policy.child_rel.priority,
+	  activity->policy.child_rel.weight);
 
   struct activity *child;
   activity_for_each_child (activity, child,
diff --git a/viengoos/activity.h b/viengoos/activity.h
index 61d87f5..53201f0 100644
--- a/viengoos/activity.h
+++ b/viengoos/activity.h
@@ -25,11 +25,14 @@
 
 #include "cap.h"
 #include "object.h"
+#include "list.h"
 
 /* Forward.  */
 struct object_desc;
 struct thread;
 
+LIST_CLASS_TYPE(activity_children)
+
 struct activity
 {
   /* On-disk data.  */
@@ -59,13 +62,13 @@ struct activity
      be in memory if its parent is in memory.  It is only NULL for the
      root activity.  This pointer is setup by activity_prepare.  */
   struct activity *parent;
-  /* List of in-memory children.  Children that are not in memory are
-     not on this list.  When an activity is paged in, activity_prepare
-     attaches it to its parent's children list.  On page-out,
-     activity_deprepare detaches it.  */
-  struct activity *children;
-  struct activity *sibling_next;
-  struct activity *sibling_prev;
+  /* List of in-memory children, sorted highest priority first.
+     Children that are not in memory are not on this list.  When an
+     activity is paged in, activity_prepare attaches it to its
+     parent's children list.  On page-out, activity_deprepare detaches
+     it.  */
+  struct activity_children_list children;
+  struct list_node sibling;
 
   /* Objects owned by this activity whose priority is
      OBJECT_PRIORITY_LRU and for which DESC->EVICTION_CANDIDATE is
@@ -93,7 +96,7 @@ struct activity
      This is the sum of the number of objects on ACTIVE,
      INACTIVE_CLEAN and INACTIVE_DIRTY plus the number of frames
      allocated to each child.  This does not include the number of
-     frames on the page out list.  */
+     frames on the eviction_clean and eviction_dirty lists.  */
   uint32_t frames_total;
 
   /* Whether the activity has been marked as dead (and thus will be
@@ -106,6 +109,8 @@ struct activity
   struct activity_stats stats[ACTIVITY_STATS_PERIODS + 1];
 };
 
+LIST_CLASS(activity_children, struct activity, sibling, false)
+
 /* Return the current activity stat structure.  */
 #define ACTIVITY_STATS(__as_activity)					\
   ({									\
@@ -219,29 +224,6 @@ activity_charge (struct activity *activity, int objects)
       }									\
   } while (0)
 
-/* Iterate over ACTIVITY's children which are in memory.  */
-#define activity_for_each_inmemory_child(__feic_activity, __feic_child,	\
-					 __feic_code)			\
-  do									\
-    {									\
-      if (__feic_activity->children)					\
-	assert (! __feic_activity->children->sibling_prev);		\
-									\
-      for (__feic_child = __feic_activity->children; __feic_child;	\
-	   __feic_child = __feic_child->sibling_next)			\
-	{								\
-	  assert (__feic_child->parent == __feic_activity);		\
-	  assert (object_type ((struct object *) __feic_child)		\
-		  == cap_activity_control);				\
-	  if (__feic_child->sibling_next)				\
-	    assert (__feic_child->sibling_next->sibling_prev		\
-		    == __feic_child);					\
-									\
-	  __feic_code;							\
-	}								\
-    }									\
-  while (0)
-
 
 /* Dump the activity ACTIVITY and its children to the screen.  */
 extern void activity_dump (struct activity *activity);
diff --git a/viengoos/ager.c b/viengoos/ager.c
index aa520c6..2979195 100644
--- a/viengoos/ager.c
+++ b/viengoos/ager.c
@@ -251,40 +251,41 @@ ager_loop (l4_thread_id_t main_thread)
 	    uint32_t remaining_frames = frames;
 
 	    struct activity *child;
-	    activity_for_each_inmemory_child
-	      (activity, child,
-	       ({
-		 if (! have_self
-		     && (activity->policy.child_rel.priority
-			 <= child->policy.sibling_rel.priority))
-		   {
-		     have_self = true;
-
-		     if (! have_one
-			 || priority > activity->policy.child_rel.priority)
-		       {
-			 priority = activity->policy.child_rel.priority;
-			 frames = remaining_frames;
-		       }
-
-		     remaining_frames -= activity->frames_local;
-
-		     ACTIVITY_STAT_UPDATE (activity, available, frames);
-		   }
-
-		 if (! have_one
-		     || priority > child->policy.sibling_rel.priority)
-		   {
-		     priority = child->policy.sibling_rel.priority;
-		     frames = remaining_frames;
-		   }
-
-		 remaining_frames -= child->frames_total;
-
-		 ACTIVITY_STAT_UPDATE (activity, available, frames);
-
-		 doit (child, frames);
-	       }));
+	    for (child = activity_children_list_head (&activity->children);
+		 child;
+		 child = activity_children_list_next (child))
+	      {
+		if (! have_self
+		    && (activity->policy.child_rel.priority
+			<= child->policy.sibling_rel.priority))
+		  {
+		    have_self = true;
+
+		    if (! have_one
+			|| priority > activity->policy.child_rel.priority)
+		      {
+			priority = activity->policy.child_rel.priority;
+			frames = remaining_frames;
+		      }
+
+		    remaining_frames -= activity->frames_local;
+
+		    ACTIVITY_STAT_UPDATE (activity, available, frames);
+		  }
+
+		if (! have_one
+		    || priority > child->policy.sibling_rel.priority)
+		  {
+		    priority = child->policy.sibling_rel.priority;
+		    frames = remaining_frames;
+		  }
+
+		remaining_frames -= child->frames_total;
+
+		ACTIVITY_STAT_UPDATE (activity, available, frames);
+
+		doit (child, frames);
+	      }
 
 	    if (! have_self)
 	      ACTIVITY_STAT_UPDATE (activity, available, frames);
diff --git a/viengoos/pager.c b/viengoos/pager.c
index cb4de04..4e77c8b 100644
--- a/viengoos/pager.c
+++ b/viengoos/pager.c
@@ -79,61 +79,62 @@ pager_collect (void)
       frames = victim_frames;
 
       struct activity *child;
-      activity_for_each_inmemory_child
-	(parent, child,
-	 ({
-	   if (child->policy.sibling_rel.priority < victim_policy.priority)
-	     /* CHILD has a lower absolute priority.  */
-	     {
-	       victim = child;
-	       victim_frames = victim->frames_total;
-	       victim_policy = victim->policy.sibling_rel;
-
-	       /* Reset the weight.  */
-	       weight = victim_policy.weight;
-	       frames = victim_frames;
-	     }
-	   else if (child->policy.sibling_rel.priority
-		    == victim_policy.priority)
-	     /* CHILD and VICTIM have equal priority.  Steal from the one
-		which has the most pages taking into their respective
-		weights.  */
-	     {
-	       weight += child->policy.sibling_rel.weight;
-	       frames += child->frames_total;
-
-	       if (child->policy.sibling_rel.weight == victim_policy.weight)
-		 /* CHILD and VICTIM have the same weight.  Prefer the
-		    one with more frames.  */
-		 {
-		   if (child->frames_total > frames)
-		     {
-		       victim = child;
-		       victim_frames = victim->frames_total;
-		       victim_policy = victim->policy.sibling_rel;
-		     }
-		 }
-	       else
-		 {
-		   int f = child->frames_total + victim_frames;
-		   int w = child->policy.sibling_rel.weight
-		     + victim_policy.weight;
-
-		   int child_excess = child->frames_total
-		     - (child->policy.sibling_rel.weight * f) / w;
-		   int victim_excess = victim_frames
-		     - (victim_policy.weight * f) / w;
-
-		   if (child_excess > victim_excess)
-		     /* CHILD has more excess frames than VICTIM.  */
-		     {
-		       victim = child;
-		       victim_frames = victim->frames_total;
-		       victim_policy = victim->policy.sibling_rel;
-		     }
-		 }
-	     }
-	 }));
+      for (child = activity_children_list_head (&parent->children);
+	   child;
+	   child = activity_children_list_next (child))
+	{
+	  if (child->policy.sibling_rel.priority < victim_policy.priority)
+	    /* CHILD has a lower absolute priority.  */
+	    {
+	      victim = child;
+	      victim_frames = victim->frames_total;
+	      victim_policy = victim->policy.sibling_rel;
+
+	      /* Reset the weight.  */
+	      weight = victim_policy.weight;
+	      frames = victim_frames;
+	    }
+	  else if (child->policy.sibling_rel.priority
+		   == victim_policy.priority)
+	    /* CHILD and VICTIM have equal priority.  Steal from the one
+	       which has the most pages taking into their respective
+	       weights.  */
+	    {
+	      weight += child->policy.sibling_rel.weight;
+	      frames += child->frames_total;
+
+	      if (child->policy.sibling_rel.weight == victim_policy.weight)
+		/* CHILD and VICTIM have the same weight.  Prefer the
+		   one with more frames.  */
+		{
+		  if (child->frames_total > frames)
+		    {
+		      victim = child;
+		      victim_frames = victim->frames_total;
+		      victim_policy = victim->policy.sibling_rel;
+		    }
+		}
+	      else
+		{
+		  int f = child->frames_total + victim_frames;
+		  int w = child->policy.sibling_rel.weight
+		    + victim_policy.weight;
+
+		  int child_excess = child->frames_total
+		    - (child->policy.sibling_rel.weight * f) / w;
+		  int victim_excess = victim_frames
+		    - (victim_policy.weight * f) / w;
+
+		  if (child_excess > victim_excess)
+		    /* CHILD has more excess frames than VICTIM.  */
+		    {
+		      victim = child;
+		      victim_frames = victim->frames_total;
+		      victim_policy = victim->policy.sibling_rel;
+		    }
+		}
+	    }
+	}
 
       if (frames >= goal)
 	/* The number of frames at this priority level exceed the