From bdce67bc2babc2e5b3b2440964e9cf819ac814dc Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Wed, 21 Mar 2012 16:26:27 -0400 Subject: GSN-EDF: Use binary heap instead of binomial heap. Use binary heap to track CPU priorities. --- include/litmus/binheap.h | 4 ++-- litmus/sched_gsn_edf.c | 47 +++++++++++++++++++++++++---------------------- 2 files changed, 27 insertions(+), 24 deletions(-) diff --git a/include/litmus/binheap.h b/include/litmus/binheap.h index b8dd8e03da60..9fe5dc13d032 100644 --- a/include/litmus/binheap.h +++ b/include/litmus/binheap.h @@ -36,7 +36,7 @@ struct binheap_node { * Signature of compator function. Assumed 'less-than' (min-heap). * Pass in 'greater-than' for max-heap. * - * TODO: Consider macor-based implementation that allows comparator to be + * TODO: Consider macro-based implementation that allows comparator to be * inlined (similar to Linux red/black tree) for greater efficiency. */ typedef int (*binheap_order_t)(struct binheap_node *a, @@ -364,7 +364,7 @@ static inline void __binheap_add(struct binheap_node *new_node, { /* NULL data pointers are used internally */ if(!data) { - WARN(); + WARN_ON(!data); return; } diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c index 6ed504f4750e..549a4dad037d 100644 --- a/litmus/sched_gsn_edf.c +++ b/litmus/sched_gsn_edf.c @@ -23,6 +23,7 @@ #include #include +#include #ifdef CONFIG_SCHED_CPU_AFFINITY #include @@ -103,15 +104,15 @@ typedef struct { int cpu; struct task_struct* linked; /* only RT tasks */ struct task_struct* scheduled; /* only RT tasks */ - struct bheap_node* hn; + int in_heap; /* == 0/1: not in / in heap*/ + struct binheap_node hn; } cpu_entry_t; DEFINE_PER_CPU(cpu_entry_t, gsnedf_cpu_entries); cpu_entry_t* gsnedf_cpus[NR_CPUS]; /* the cpus queue themselves according to priority in here */ -static struct bheap_node gsnedf_heap_node[NR_CPUS]; -static struct bheap gsnedf_cpu_heap; +static struct binheap_handle gsnedf_cpu_heap; static rt_domain_t gsnedf; #define gsnedf_lock (gsnedf.ready_lock) @@ -122,33 +123,33 @@ static rt_domain_t gsnedf; #define WANT_ALL_SCHED_EVENTS */ -static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b) +static int cpu_lower_prio(struct binheap_node *_a, struct binheap_node *_b) { - cpu_entry_t *a, *b; - a = _a->value; - b = _b->value; + cpu_entry_t *a = binheap_entry(_a, cpu_entry_t, hn); + cpu_entry_t *b = binheap_entry(_b, cpu_entry_t, hn); + /* Note that a and b are inverted: we want the lowest-priority CPU at * the top of the heap. */ return edf_higher_prio(b->linked, a->linked); } + /* update_cpu_position - Move the cpu entry to the correct place to maintain * order in the cpu queue. Caller must hold gsnedf lock. */ static void update_cpu_position(cpu_entry_t *entry) { - if (likely(bheap_node_in_heap(entry->hn))) - bheap_delete(cpu_lower_prio, &gsnedf_cpu_heap, entry->hn); - bheap_insert(cpu_lower_prio, &gsnedf_cpu_heap, entry->hn); + if (likely(entry->in_heap)) + binheap_delete(&entry->hn, &gsnedf_cpu_heap, cpu_entry_t, hn); + binheap_add(&entry->hn, &gsnedf_cpu_heap, cpu_entry_t, hn); + entry->in_heap = 1; } /* caller must hold gsnedf lock */ static cpu_entry_t* lowest_prio_cpu(void) { - struct bheap_node* hn; - hn = bheap_peek(cpu_lower_prio, &gsnedf_cpu_heap); - return hn->value; + return binheap_top_entry(&gsnedf_cpu_heap, cpu_entry_t, hn); } @@ -665,10 +666,10 @@ static void set_priority_inheritance(struct task_struct* t, struct task_struct* * We can't use heap_decrease() here since * the cpu_heap is ordered in reverse direction, so * it is actually an increase. */ - bheap_delete(cpu_lower_prio, &gsnedf_cpu_heap, - gsnedf_cpus[linked_on]->hn); - bheap_insert(cpu_lower_prio, &gsnedf_cpu_heap, - gsnedf_cpus[linked_on]->hn); + binheap_delete(&gsnedf_cpus[linked_on]->hn, + &gsnedf_cpu_heap, cpu_entry_t, hn); + binheap_add(&gsnedf_cpus[linked_on]->hn, + &gsnedf_cpu_heap, cpu_entry_t, hn); } else { /* holder may be queued: first stop queue changes */ raw_spin_lock(&gsnedf.release_lock); @@ -965,14 +966,15 @@ static long gsnedf_activate_plugin(void) int cpu; cpu_entry_t *entry; - bheap_init(&gsnedf_cpu_heap); + INIT_BINHEAP_HANDLE(&gsnedf_cpu_heap, cpu_lower_prio); #ifdef CONFIG_RELEASE_MASTER gsnedf.release_master = atomic_read(&release_master_cpu); #endif for_each_online_cpu(cpu) { entry = &per_cpu(gsnedf_cpu_entries, cpu); - bheap_node_init(&entry->hn, entry); + INIT_BINHEAP_NODE(&entry->hn); + entry->in_heap = 0; entry->linked = NULL; entry->scheduled = NULL; #ifdef CONFIG_RELEASE_MASTER @@ -1013,14 +1015,15 @@ static int __init init_gsn_edf(void) int cpu; cpu_entry_t *entry; - bheap_init(&gsnedf_cpu_heap); + INIT_BINHEAP_HANDLE(&gsnedf_cpu_heap, cpu_lower_prio); /* initialize CPU state */ for (cpu = 0; cpu < NR_CPUS; cpu++) { entry = &per_cpu(gsnedf_cpu_entries, cpu); gsnedf_cpus[cpu] = entry; entry->cpu = cpu; - entry->hn = &gsnedf_heap_node[cpu]; - bheap_node_init(&entry->hn, entry); + + INIT_BINHEAP_NODE(&entry->hn); + entry->in_heap = 0; } edf_domain_init(&gsnedf, NULL, gsnedf_release_jobs); return register_sched_plugin(&gsn_edf_plugin); -- cgit v1.2.2