Proper sobliv draining and many bug fixes.wip-2012.3-gpu-sobliv-budget-w-kshark

Proper sobliv draining: Always and only drain budget
from a task if its BASE priority is among the top
m processors in the cluster. This required some
work with timers and tracking of consumed budget
while a task is suspended (since the Linux rq won't
track this for us).

Had to introduce a number of hacks and kludges to
make this work in the required timeframe:
1) C-EDF's ready queue lock becomes recursive (yuck!)
2) Extend bheap with a for_each visitor function.
This is needed to set a timer for each newly released
job.
3) Dual-binary heap structure in C-EDF to divide
jobs into top-m and not-top-m tasks.
4) Restructured the budget plugin API. Unfortunatly,
there is not a lot of overlap between SIMPLE and
SOBLIV draining policies.

1 files changed, 5 insertions, 15 deletions

diff --git a/litmus/bheap.c b/litmus/bheap.c
index 403c09cc9e81..c69d75c28aaf 100644
--- a/litmus/bheap.c
+++ b/litmus/bheap.c
@@ -5,8 +5,6 @@ void bheap_init(struct bheap* heap)
 {
         heap->head = NULL;
         heap->min  = NULL;
-
-//      heap->size = 0;
 }
 
 void bheap_node_init(struct bheap_node** _h, void* value)
@@ -21,19 +19,19 @@ void bheap_node_init(struct bheap_node** _h, void* value)
 }
 
 
-static void __bheap_for_all(struct bheap_node *h, bheap_for_all_t fn, void* args)
+static void __bheap_for_each(struct bheap_node *h, bheap_for_each_t fn, void* args)
 {
         /* pre-order */
         fn(h, args);
 
         /* depth-first */
         if (h->child)
-                __bheap_for_all(h->child, fn, args);
+                __bheap_for_each(h->child, fn, args);
         if (h->next)
-                __bheap_for_all(h->next, fn, args);
+                __bheap_for_each(h->next, fn, args);
 }
 
-void bheap_for_all(struct bheap* heap, bheap_for_all_t fn, void* args)
+void bheap_for_each(struct bheap* heap, bheap_for_each_t fn, void* args)
 {
         struct bheap_node *head;
 
@@ -41,7 +39,7 @@ void bheap_for_all(struct bheap* heap, bheap_for_all_t fn, void* args)
         BUG_ON(!fn);
 
         head = heap->head;
-        __bheap_for_all(head, fn, args);
+        __bheap_for_each(head, fn, args);
 }
 
 /* make child a subtree of root */
@@ -198,8 +196,6 @@ void bheap_insert(bheap_prio_t higher_prio, struct bheap* heap,
                 heap->min   = node;
         } else
                 __bheap_union(higher_prio, heap, node);
-
-//      ++heap->size;
 }
 
 void bheap_uncache_min(bheap_prio_t higher_prio, struct bheap* heap)
@@ -222,8 +218,6 @@ void bheap_union(bheap_prio_t higher_prio,
         __bheap_union(higher_prio, target, addition->head);
         /* this is a destructive merge */
         addition->head = NULL;
-
-//      target->size += addition->size;
 }
 
 struct bheap_node* bheap_peek(bheap_prio_t higher_prio,
@@ -245,8 +239,6 @@ struct bheap_node* bheap_take(bheap_prio_t higher_prio,
         if (node)
                 node->degree = NOT_IN_HEAP;
 
-//      --heap->size;
-
         return node;
 }
 
@@ -320,8 +312,6 @@ void bheap_delete(bheap_prio_t higher_prio, struct bheap* heap,
                 heap->min = NULL;
 
         node->degree = NOT_IN_HEAP;
-
-//      --heap->size;
 }
 
 /* allocate a heap node for value and insert into the heap */