From 53a6dbb9f5337e77fce9c2672488c1c5e0621beb Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Sat, 14 Jan 2012 14:20:07 -0500 Subject: Completed PAI for C-EDF. --- litmus/litmus_softirq.c | 5 + litmus/sched_cedf.c | 319 ++++++++++++++++++++++++++++++++++++------ litmus/sched_plugin.c | 8 +- litmus/sched_trace_external.c | 8 +- 4 files changed, 289 insertions(+), 51 deletions(-) (limited to 'litmus') diff --git a/litmus/litmus_softirq.c b/litmus/litmus_softirq.c index f5cca964b6c6..c49676c6d3a7 100644 --- a/litmus/litmus_softirq.c +++ b/litmus/litmus_softirq.c @@ -470,6 +470,9 @@ static void do_lit_tasklet(struct klitirqd_info* which, /* execute tasklet if it has my priority and is free */ if ((t->owner == which->current_owner) && tasklet_trylock(t)) { if (!atomic_read(&t->count)) { + + sched_trace_tasklet_begin(t->owner); + if (!test_and_clear_bit(TASKLET_STATE_SCHED, &t->state)) { BUG(); @@ -480,6 +483,8 @@ static void do_lit_tasklet(struct klitirqd_info* which, atomic_dec(count); + sched_trace_tasklet_end(t->owner, 0ul); + continue; /* process more tasklets */ } tasklet_unlock(t); diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c index f0356de60b2f..4924da21865e 100644 --- a/litmus/sched_cedf.c +++ b/litmus/sched_cedf.c @@ -124,6 +124,7 @@ typedef struct clusterdomain { #ifdef CONFIG_LITMUS_PAI_SOFTIRQD + raw_spinlock_t tasklet_lock; struct tasklet_head pending_tasklets; #endif @@ -429,36 +430,137 @@ static void cedf_tick(struct task_struct* t) #ifdef CONFIG_LITMUS_PAI_SOFTIRQD -void __do_lit_tasklet(struct tasklet_struct* tasklet) +void __do_lit_tasklet(struct tasklet_struct* tasklet, unsigned long flushed) { - if (!test_and_clear_bit(TASKLET_STATE_SCHED, &tasklet->state)) - { + if (!atomic_read(&tasklet->count)) { + sched_trace_tasklet_begin(tasklet->owner); + + if (!test_and_clear_bit(TASKLET_STATE_SCHED, &tasklet->state)) + { + BUG(); + } + TRACE("%s: Invoking tasklet with owner pid = %d (flushed = %d).\n", __FUNCTION__, tasklet->owner->pid, flushed); + tasklet->func(tasklet->data); + tasklet_unlock(tasklet); + + sched_trace_tasklet_end(tasklet->owner, flushed); + } + else { BUG(); } - TRACE("%s: Invoking tasklet with owner pid = %d.\n", __FUNCTION__, tasklet->owner->pid); - tasklet->func(tasklet->data); - tasklet_unlock(tasklet); +} + + +void __extract_tasklets(cedf_domain_t* cluster, struct task_struct* task, struct tasklet_head* task_tasklets) +{ + struct tasklet_struct* step; + struct tasklet_struct* tasklet; + struct tasklet_struct* prev; + + task_tasklets->head = NULL; + task_tasklets->tail = &(task_tasklets->head); + + prev = NULL; + for(step = cluster->pending_tasklets.head; step != NULL; step = step->next) + { + if(step->owner == task) + { + TRACE("%s: Found tasklet to flush: %d\n", __FUNCTION__, step->owner->pid); + + tasklet = step; + + if(prev) { + prev->next = tasklet->next; + } + else if(cluster->pending_tasklets.head == tasklet) { + // we're at the head. + cluster->pending_tasklets.head = tasklet->next; + } + + if(cluster->pending_tasklets.tail == &tasklet) { + // we're at the tail + if(prev) { + cluster->pending_tasklets.tail = &prev; + } + else { + cluster->pending_tasklets.tail = &(cluster->pending_tasklets.head); + } + } + + tasklet->next = NULL; + *(task_tasklets->tail) = tasklet; + task_tasklets->tail = &(tasklet->next); + } + else { + prev = step; + } + } +} + +void flush_tasklets(cedf_domain_t* cluster, struct task_struct* task) +{ + unsigned long flags; + struct tasklet_head task_tasklets; + struct tasklet_struct* step; + + raw_spin_lock_irqsave(&cluster->cedf_lock, flags); + __extract_tasklets(cluster, task, &task_tasklets); + raw_spin_unlock_irqrestore(&cluster->cedf_lock, flags); + + if(cluster->pending_tasklets.head != NULL) { + TRACE("%s: Flushing tasklets for %d...\n", __FUNCTION__, task->pid); + } + + // now execute any flushed tasklets. + for(step = cluster->pending_tasklets.head; step != NULL; /**/) + { + struct tasklet_struct* temp = step->next; + + step->next = NULL; + __do_lit_tasklet(step, 1ul); + step = temp; + } } -void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* next) + +void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* sched_task) { int work_to_do = 1; struct tasklet_struct *tasklet = NULL; - - TRACE("%s: entered.\n", __FUNCTION__); + struct tasklet_struct *step; + unsigned long flags; while(work_to_do) { // remove tasklet at head of list if it has higher priority. - raw_spin_lock(&cluster->cedf_lock); - // remove tasklet at head. + raw_spin_lock_irqsave(&cluster->cedf_lock, flags); + + + step = cluster->pending_tasklets.head; + TRACE("%s: (BEFORE) dumping tasklet queue...\n", __FUNCTION__); + while(step != NULL){ + TRACE("%s: %p (%d)\n", __FUNCTION__, step, step->owner->pid); + step = step->next; + } + TRACE("%s: tail = %p (%d)\n", __FUNCTION__, *(cluster->pending_tasklets.tail), (*(cluster->pending_tasklets.tail) != NULL) ? (*(cluster->pending_tasklets.tail))->owner->pid : -1); + TRACE("%s: done.\n", __FUNCTION__); + + if(cluster->pending_tasklets.head != NULL) { + // remove tasklet at head. tasklet = cluster->pending_tasklets.head; - if(edf_higher_prio(tasklet->owner, next)) { + if(edf_higher_prio(tasklet->owner, sched_task)) { + + if(NULL == tasklet->next) { + // tasklet is at the head, list only has one element + TRACE("%s: Tasklet for %d is the last element in tasklet queue.\n", __FUNCTION__, tasklet->owner->pid); + cluster->pending_tasklets.tail = &(cluster->pending_tasklets.head); + } + // remove the tasklet from the queue cluster->pending_tasklets.head = tasklet->next; - + TRACE("%s: Removed tasklet for %d from tasklet queue.\n", __FUNCTION__, tasklet->owner->pid); } else { @@ -467,12 +569,24 @@ void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* next) } } else { - //TRACE("%s: Tasklet queue is empty.\n", __FUNCTION__); + TRACE("%s: Tasklet queue is empty.\n", __FUNCTION__); } - raw_spin_unlock(&cluster->cedf_lock); + + + step = cluster->pending_tasklets.head; + TRACE("%s: (AFTER) dumping tasklet queue...\n", __FUNCTION__); + while(step != NULL){ + TRACE("%s: %p (%d)\n", __FUNCTION__, step, step->owner->pid); + step = step->next; + } + TRACE("%s: tail = %p (%d)\n", __FUNCTION__, *(cluster->pending_tasklets.tail), (*(cluster->pending_tasklets.tail) != NULL) ? (*(cluster->pending_tasklets.tail))->owner->pid : -1); + TRACE("%s: done.\n", __FUNCTION__); + + + raw_spin_unlock_irqrestore(&cluster->cedf_lock, flags); if(tasklet) { - __do_lit_tasklet(tasklet); + __do_lit_tasklet(tasklet, 0ul); tasklet = NULL; } else { @@ -480,7 +594,50 @@ void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* next) } } - TRACE("%s: exited.\n", __FUNCTION__); + //TRACE("%s: exited.\n", __FUNCTION__); +} + + +void run_tasklets(struct task_struct* sched_task) +{ + cedf_domain_t* cluster; + +#if 0 + int task_is_rt = is_realtime(sched_task); + cedf_domain_t* cluster; + + if(is_realtime(sched_task)) { + cluster = task_cpu_cluster(sched_task); + } + else { + cluster = remote_cluster(get_cpu()); + } + + if(cluster && cluster->pending_tasklets.head != NULL) { + TRACE("%s: There are tasklets to process.\n", __FUNCTION__); + + do_lit_tasklets(cluster, sched_task); + } + + if(!task_is_rt) { + put_cpu_no_resched(); + } +#else + + preempt_disable(); + + cluster = (is_realtime(sched_task)) ? + task_cpu_cluster(sched_task) : + remote_cluster(smp_processor_id()); + + if(cluster && cluster->pending_tasklets.head != NULL) { + TRACE("%s: There are tasklets to process.\n", __FUNCTION__); + do_lit_tasklets(cluster, sched_task); + } + + preempt_enable_no_resched(); + +#endif } @@ -489,41 +646,47 @@ void __add_pai_tasklet(struct tasklet_struct* tasklet, cedf_domain_t* cluster) struct tasklet_struct* step; step = cluster->pending_tasklets.head; - TRACE("%s: (BEFORE) dumping tasklet queue...\n"); + TRACE("%s: (BEFORE) dumping tasklet queue...\n", __FUNCTION__); while(step != NULL){ - TRACE("%s: %d\n", __FUNCTION__, step->owner); + TRACE("%s: %p (%d)\n", __FUNCTION__, step, step->owner->pid); step = step->next; } + TRACE("%s: tail = %p (%d)\n", __FUNCTION__, *(cluster->pending_tasklets.tail), (*(cluster->pending_tasklets.tail) != NULL) ? (*(cluster->pending_tasklets.tail))->owner->pid : -1); TRACE("%s: done.\n", __FUNCTION__); + tasklet->next = NULL; // make sure there are no old values floating around + step = cluster->pending_tasklets.head; if(step == NULL) { TRACE("%s: tasklet queue empty. inserting tasklet for %d at head.\n", __FUNCTION__, tasklet->owner->pid); // insert at tail. - tasklet->next = NULL; *(cluster->pending_tasklets.tail) = tasklet; - cluster->pending_tasklets.tail = &tasklet->next; + cluster->pending_tasklets.tail = &(tasklet->next); } - else if((*cluster->pending_tasklets.tail != NULL) && - edf_higher_prio((*cluster->pending_tasklets.tail)->owner, tasklet->owner)) { + else if((*(cluster->pending_tasklets.tail) != NULL) && + edf_higher_prio((*(cluster->pending_tasklets.tail))->owner, tasklet->owner)) { // insert at tail. TRACE("%s: tasklet belongs at end. inserting tasklet for %d at tail.\n", __FUNCTION__, tasklet->owner->pid); - tasklet->next = NULL; *(cluster->pending_tasklets.tail) = tasklet; - cluster->pending_tasklets.tail = &tasklet->next; + cluster->pending_tasklets.tail = &(tasklet->next); } else { + + WARN_ON(1 == 1); + // insert the tasklet somewhere in the middle. - + + TRACE("%s: tasklet belongs somewhere in the middle.\n", __FUNCTION__); + while(step->next && edf_higher_prio(step->next->owner, tasklet->owner)) { step = step->next; } // insert tasklet right before step->next. - TRACE("%s: tasklet belongs at end. inserting tasklet for %d between %d and %d.\n", __FUNCTION__, tasklet->owner->pid, step->owner->pid, (step->next) ? step->next->owner->pid : -1); + TRACE("%s: inserting tasklet for %d between %d and %d.\n", __FUNCTION__, tasklet->owner->pid, step->owner->pid, (step->next) ? step->next->owner->pid : -1); tasklet->next = step->next; step->next = tasklet; @@ -540,9 +703,10 @@ void __add_pai_tasklet(struct tasklet_struct* tasklet, cedf_domain_t* cluster) step = cluster->pending_tasklets.head; TRACE("%s: (AFTER) dumping tasklet queue...\n", __FUNCTION__); while(step != NULL){ - TRACE("%s: %d\n", __FUNCTION__, step->owner); + TRACE("%s: %p (%d)\n", __FUNCTION__, step, step->owner->pid); step = step->next; } + TRACE("%s: tail = %p (%d)\n", __FUNCTION__, *(cluster->pending_tasklets.tail), (*(cluster->pending_tasklets.tail) != NULL) ? (*(cluster->pending_tasklets.tail))->owner->pid : -1); TRACE("%s: done.\n", __FUNCTION__); // TODO: Maintain this list in priority order. @@ -553,37 +717,89 @@ void __add_pai_tasklet(struct tasklet_struct* tasklet, cedf_domain_t* cluster) int enqueue_pai_tasklet(struct tasklet_struct* tasklet) { - cedf_domain_t* cluster = task_cpu_cluster(tasklet->owner); - cpu_entry_t *lowest; + cedf_domain_t *cluster = NULL; + cpu_entry_t *targetCPU = NULL; + int thisCPU; + int runLocal = 0; + int runNow = 0; unsigned long flags; if(unlikely((tasklet->owner == NULL) || !is_realtime(tasklet->owner))) { TRACE("%s: No owner associated with this tasklet!\n", __FUNCTION__); - BUG(); + return 0; } + cluster = task_cpu_cluster(tasklet->owner); + raw_spin_lock_irqsave(&cluster->cedf_lock, flags); - lowest = lowest_prio_cpu(cluster); - if (edf_higher_prio(tasklet->owner, lowest->linked)) { - if (smp_processor_id() == lowest->cpu) { - TRACE("%s: Running tasklet on CPU where it was received.\n", __FUNCTION__); - // execute the tasklet now. - __do_lit_tasklet(tasklet); + thisCPU = smp_processor_id(); + +#if 1 +#ifdef CONFIG_SCHED_CPU_AFFINITY + { + cpu_entry_t* affinity = NULL; + + // use this CPU if it is in our cluster and isn't running any RT work. + if(cpu_isset(thisCPU, *cluster->cpu_map) && (__get_cpu_var(cedf_cpu_entries).linked == NULL)) { + affinity = &(__get_cpu_var(cedf_cpu_entries)); } else { - // preempt the lowest CPU - __add_pai_tasklet(tasklet, cluster); - - TRACE("%s: Triggering CPU %d to run tasklet.\n", __FUNCTION__, lowest->cpu); - - preempt(lowest); + // this CPU is busy or shouldn't run tasklet in this cluster. + // look for available near by CPUs. + // NOTE: Affinity towards owner and not this CPU. Is this right? + affinity = + cedf_get_nearest_available_cpu(cluster, + &per_cpu(cedf_cpu_entries, task_cpu(tasklet->owner))); } + + targetCPU = affinity; + } +#endif +#endif + + if (targetCPU == NULL) { + targetCPU = lowest_prio_cpu(cluster); + } + + if (edf_higher_prio(tasklet->owner, targetCPU->linked)) { + if (thisCPU == targetCPU->cpu) { + TRACE("%s: Run tasklet locally (and now).\n", __FUNCTION__); + runLocal = 1; + runNow = 1; + } + else { + TRACE("%s: Run tasklet remotely (and now).\n", __FUNCTION__); + runLocal = 0; + runNow = 1; + } + } + else { + runLocal = 0; + runNow = 0; + } + + if(!runLocal) { + // enqueue the tasklet + __add_pai_tasklet(tasklet, cluster); } raw_spin_unlock_irqrestore(&cluster->cedf_lock, flags); + + if (runLocal /*&& runNow */) { // runNow == 1 is implied + TRACE("%s: Running tasklet on CPU where it was received.\n", __FUNCTION__); + __do_lit_tasklet(tasklet, 0ul); + } + else if (runNow /*&& !runLocal */) { // runLocal == 0 is implied + TRACE("%s: Triggering CPU %d to run tasklet.\n", __FUNCTION__, targetCPU->cpu); + preempt(targetCPU); // need to be protected by cedf_lock? + } + else { + TRACE("%s: Scheduling of tasklet was deferred.\n", __FUNCTION__); + } + return(1); // success } @@ -721,9 +937,14 @@ static struct task_struct* cedf_schedule(struct task_struct * prev) raw_spin_unlock(&cluster->cedf_lock); + /* #ifdef CONFIG_LITMUS_PAI_SOFTIRQD - do_lit_tasklets(cluster, next); -#endif + if(cluster->pending_tasklets.head != NULL) // peak at data. normally locked with cluster->cedf_lock + { + do_lit_tasklets(cluster, next); + } +#endif +*/ #ifdef WANT_ALL_SCHED_EVENTS TRACE("cedf_lock released, next=0x%p\n", next); @@ -865,6 +1086,10 @@ static void cedf_task_exit(struct task_struct * t) } raw_spin_unlock_irqrestore(&cluster->cedf_lock, flags); +#ifdef CONFIG_LITMUS_PAI_SOFTIRQD + flush_tasklets(cluster, t); +#endif + BUG_ON(!is_realtime(t)); TRACE_TASK(t, "RIP\n"); } @@ -1684,8 +1909,9 @@ static long cedf_activate_plugin(void) #ifdef CONFIG_LITMUS_PAI_SOFTIRQD + raw_spin_lock_init(&(cedf[i].tasklet_lock)); cedf[i].pending_tasklets.head = NULL; - cedf[i].pending_tasklets.tail = &cedf[i].pending_tasklets.head; + cedf[i].pending_tasklets.tail = &(cedf[i].pending_tasklets.head); #endif @@ -1803,6 +2029,7 @@ static struct sched_plugin cedf_plugin __cacheline_aligned_in_smp = { #endif #ifdef CONFIG_LITMUS_PAI_SOFTIRQD .enqueue_pai_tasklet = enqueue_pai_tasklet, + .run_tasklets = run_tasklets, #endif }; diff --git a/litmus/sched_plugin.c b/litmus/sched_plugin.c index e393d749baf5..d977e80aa32f 100644 --- a/litmus/sched_plugin.c +++ b/litmus/sched_plugin.c @@ -155,9 +155,14 @@ static void litmus_dummy_clear_prio_inh_klitirqd(struct task_struct* klitirqd, #ifdef CONFIG_LITMUS_PAI_SOFTIRQD static int litmus_dummy_enqueue_pai_tasklet(struct tasklet_struct* t) { - TRACE("PAI Tasklet unsupported in this plugin!!!!!!\n"); + TRACE("%s: PAI Tasklet unsupported in this plugin!!!!!!\n", __FUNCTION__); return(0); // failure. } + +static void litmus_dummy_run_tasklets(struct task_struct* t) +{ + //TRACE("%s: PAI Tasklet unsupported in this plugin!!!!!!\n", __FUNCTION__); +} #endif @@ -187,6 +192,7 @@ struct sched_plugin linux_sched_plugin = { #endif #ifdef CONFIG_LITMUS_PAI_SOFTIRQD .enqueue_pai_tasklet = litmus_dummy_enqueue_pai_tasklet, + .run_tasklets = litmus_dummy_run_tasklets, #endif .admit_task = litmus_dummy_admit_task }; diff --git a/litmus/sched_trace_external.c b/litmus/sched_trace_external.c index 5b7e6152416a..cf8e1d78aa77 100644 --- a/litmus/sched_trace_external.c +++ b/litmus/sched_trace_external.c @@ -34,15 +34,15 @@ EXPORT_SYMBOL(__sched_trace_work_end_external); void __sched_trace_nv_interrupt_begin_external(u32 device) { - unsigned long _device = device; - sched_trace_nv_interrupt_begin(_device); + //unsigned long _device = device; + sched_trace_nv_interrupt_begin((unsigned long)device); } EXPORT_SYMBOL(__sched_trace_nv_interrupt_begin_external); void __sched_trace_nv_interrupt_end_external(u32 device) { - unsigned long _device = device; - sched_trace_nv_interrupt_end(_device); + //unsigned long _device = device; + sched_trace_nv_interrupt_end((unsigned long)device); } EXPORT_SYMBOL(__sched_trace_nv_interrupt_end_external); -- cgit v1.2.2