ia64/xen-unstable

view xen/common/sched_sedf.c @ 9776:72f9c751d3ea

Replace &foo[0] with foo where the latter seems cleaner
(which is usually, and particularly when its an argument
to one of the bitops functions).

Signed-off-by: Keir Fraser <keir@xensource.com>
author kaf24@firebug.cl.cam.ac.uk
date Wed Apr 19 18:32:20 2006 +0100 (2006-04-19)
parents 81bc9e9fb40d
children 6993a0f91efc
line source
1 /******************************************************************************
2 * Simple EDF scheduler for xen
3 *
4 * by Stephan Diestelhorst (C) 2004 Cambridge University
5 * based on code by Mark Williamson (C) 2004 Intel Research Cambridge
6 */
8 #include <xen/lib.h>
9 #include <xen/sched.h>
10 #include <xen/sched-if.h>
11 #include <public/sched_ctl.h>
12 #include <xen/timer.h>
13 #include <xen/softirq.h>
14 #include <xen/time.h>
16 /*verbosity settings*/
17 #define SEDFLEVEL 0
18 #define PRINT(_f, _a...) \
19 do { \
20 if ( (_f) <= SEDFLEVEL ) \
21 printk(_a ); \
22 } while ( 0 )
24 #ifndef NDEBUG
25 #define SEDF_STATS
26 #define CHECK(_p) \
27 do { \
28 if ( !(_p) ) \
29 printk("Check '%s' failed, line %d, file %s\n", \
30 #_p , __LINE__, __FILE__); \
31 } while ( 0 )
32 #else
33 #define CHECK(_p) ((void)0)
34 #endif
36 #define EXTRA_NONE (0)
37 #define EXTRA_AWARE (1)
38 #define EXTRA_RUN_PEN (2)
39 #define EXTRA_RUN_UTIL (4)
40 #define EXTRA_WANT_PEN_Q (8)
41 #define EXTRA_PEN_Q (0)
42 #define EXTRA_UTIL_Q (1)
43 #define SEDF_ASLEEP (16)
45 #define EXTRA_QUANTUM (MICROSECS(500))
46 #define WEIGHT_PERIOD (MILLISECS(100))
47 #define WEIGHT_SAFETY (MILLISECS(5))
49 #define PERIOD_MAX MILLISECS(10000) /* 10s */
50 #define PERIOD_MIN (MICROSECS(10)) /* 10us */
51 #define SLICE_MIN (MICROSECS(5)) /* 5us */
53 #define IMPLY(a, b) (!(a) || (b))
54 #define EQ(a, b) ((!!(a)) == (!!(b)))
57 struct sedf_dom_info {
58 struct domain *domain;
59 };
61 struct sedf_vcpu_info {
62 struct vcpu *vcpu;
63 struct list_head list;
64 struct list_head extralist[2];
66 /*Parameters for EDF*/
67 s_time_t period; /*=(relative deadline)*/
68 s_time_t slice; /*=worst case execution time*/
70 /*Advaced Parameters*/
71 /*Latency Scaling*/
72 s_time_t period_orig;
73 s_time_t slice_orig;
74 s_time_t latency;
76 /*status of domain*/
77 int status;
78 /*weights for "Scheduling for beginners/ lazy/ etc." ;)*/
79 short weight;
80 short extraweight;
81 /*Bookkeeping*/
82 s_time_t deadl_abs;
83 s_time_t sched_start_abs;
84 s_time_t cputime;
85 /* times the domain un-/blocked */
86 s_time_t block_abs;
87 s_time_t unblock_abs;
89 /*scores for {util, block penalty}-weighted extratime distribution*/
90 int score[2];
91 s_time_t short_block_lost_tot;
93 /*Statistics*/
94 s_time_t extra_time_tot;
96 #ifdef SEDF_STATS
97 s_time_t block_time_tot;
98 s_time_t penalty_time_tot;
99 int block_tot;
100 int short_block_tot;
101 int long_block_tot;
102 int short_cont;
103 int pen_extra_blocks;
104 int pen_extra_slices;
105 #endif
106 };
108 struct sedf_cpu_info {
109 struct list_head runnableq;
110 struct list_head waitq;
111 struct list_head extraq[2];
112 s_time_t current_slice_expires;
113 };
115 #define EDOM_INFO(d) ((struct sedf_vcpu_info *)((d)->sched_priv))
116 #define CPU_INFO(cpu) ((struct sedf_cpu_info *)schedule_data[cpu].sched_priv)
117 #define LIST(d) (&EDOM_INFO(d)->list)
118 #define EXTRALIST(d,i) (&(EDOM_INFO(d)->extralist[i]))
119 #define RUNQ(cpu) (&CPU_INFO(cpu)->runnableq)
120 #define WAITQ(cpu) (&CPU_INFO(cpu)->waitq)
121 #define EXTRAQ(cpu,i) (&(CPU_INFO(cpu)->extraq[i]))
122 #define IDLETASK(cpu) ((struct vcpu *)schedule_data[cpu].idle)
124 #define PERIOD_BEGIN(inf) ((inf)->deadl_abs - (inf)->period)
126 #define MIN(x,y) (((x)<(y))?(x):(y))
127 #define DIV_UP(x,y) (((x) + (y) - 1) / y)
129 #define extra_runs(inf) ((inf->status) & 6)
130 #define extra_get_cur_q(inf) (((inf->status & 6) >> 1)-1)
131 #define sedf_runnable(edom) (!(EDOM_INFO(edom)->status & SEDF_ASLEEP))
134 static void sedf_dump_cpu_state(int i);
136 static inline int extraq_on(struct vcpu *d, int i)
137 {
138 return ((EXTRALIST(d,i)->next != NULL) &&
139 (EXTRALIST(d,i)->next != EXTRALIST(d,i)));
140 }
142 static inline void extraq_add_head(struct vcpu *d, int i)
143 {
144 list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
145 ASSERT(extraq_on(d, i));
146 }
148 static inline void extraq_add_tail(struct vcpu *d, int i)
149 {
150 list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
151 ASSERT(extraq_on(d, i));
152 }
154 static inline void extraq_del(struct vcpu *d, int i)
155 {
156 struct list_head *list = EXTRALIST(d,i);
157 ASSERT(extraq_on(d,i));
158 PRINT(3, "Removing domain %i.%i from L%i extraq\n",
159 d->domain->domain_id, d->vcpu_id, i);
160 list_del(list);
161 list->next = NULL;
162 ASSERT(!extraq_on(d, i));
163 }
165 /* adds a domain to the queue of processes which are aware of extra time. List
166 is sorted by score, where a lower score means higher priority for an extra
167 slice. It also updates the score, by simply subtracting a fixed value from
168 each entry, in order to avoid overflow. The algorithm works by simply
169 charging each domain that recieved extratime with an inverse of its weight.
170 */
171 static inline void extraq_add_sort_update(struct vcpu *d, int i, int sub)
172 {
173 struct list_head *cur;
174 struct sedf_vcpu_info *curinf;
176 ASSERT(!extraq_on(d,i));
178 PRINT(3, "Adding domain %i.%i (score= %i, short_pen= %"PRIi64")"
179 " to L%i extraq\n",
180 d->domain->domain_id, d->vcpu_id, EDOM_INFO(d)->score[i],
181 EDOM_INFO(d)->short_block_lost_tot, i);
183 /*
184 * Iterate through all elements to find our "hole" and on our way
185 * update all the other scores.
186 */
187 list_for_each ( cur, EXTRAQ(d->processor, i) )
188 {
189 curinf = list_entry(cur,struct sedf_vcpu_info,extralist[i]);
190 curinf->score[i] -= sub;
191 if ( EDOM_INFO(d)->score[i] < curinf->score[i] )
192 break;
193 PRINT(4,"\tbehind domain %i.%i (score= %i)\n",
194 curinf->vcpu->domain->domain_id,
195 curinf->vcpu->vcpu_id, curinf->score[i]);
196 }
198 /* cur now contains the element, before which we'll enqueue. */
199 PRINT(3, "\tlist_add to %p\n", cur->prev);
200 list_add(EXTRALIST(d,i),cur->prev);
202 /* Continue updating the extraq. */
203 if ( (cur != EXTRAQ(d->processor,i)) && sub )
204 {
205 for ( cur = cur->next; cur != EXTRAQ(d->processor,i); cur = cur->next )
206 {
207 curinf = list_entry(cur,struct sedf_vcpu_info, extralist[i]);
208 curinf->score[i] -= sub;
209 PRINT(4, "\tupdating domain %i.%i (score= %u)\n",
210 curinf->vcpu->domain->domain_id,
211 curinf->vcpu->vcpu_id, curinf->score[i]);
212 }
213 }
215 ASSERT(extraq_on(d,i));
216 }
217 static inline void extraq_check(struct vcpu *d)
218 {
219 if ( extraq_on(d, EXTRA_UTIL_Q) )
220 {
221 PRINT(2,"Dom %i.%i is on L1 extraQ\n",
222 d->domain->domain_id, d->vcpu_id);
224 if ( !(EDOM_INFO(d)->status & EXTRA_AWARE) &&
225 !extra_runs(EDOM_INFO(d)) )
226 {
227 extraq_del(d, EXTRA_UTIL_Q);
228 PRINT(2,"Removed dom %i.%i from L1 extraQ\n",
229 d->domain->domain_id, d->vcpu_id);
230 }
231 }
232 else
233 {
234 PRINT(2, "Dom %i.%i is NOT on L1 extraQ\n",
235 d->domain->domain_id,
236 d->vcpu_id);
238 if ( (EDOM_INFO(d)->status & EXTRA_AWARE) && sedf_runnable(d) )
239 {
240 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
241 PRINT(2,"Added dom %i.%i to L1 extraQ\n",
242 d->domain->domain_id, d->vcpu_id);
243 }
244 }
245 }
247 static inline void extraq_check_add_unblocked(struct vcpu *d, int priority)
248 {
249 struct sedf_vcpu_info *inf = EDOM_INFO(d);
251 if ( inf->status & EXTRA_AWARE )
252 /* Put on the weighted extraq without updating any scores. */
253 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
254 }
256 static inline int __task_on_queue(struct vcpu *d)
257 {
258 return (((LIST(d))->next != NULL) && (LIST(d)->next != LIST(d)));
259 }
261 static inline void __del_from_queue(struct vcpu *d)
262 {
263 struct list_head *list = LIST(d);
264 ASSERT(__task_on_queue(d));
265 PRINT(3,"Removing domain %i.%i (bop= %"PRIu64") from runq/waitq\n",
266 d->domain->domain_id, d->vcpu_id, PERIOD_BEGIN(EDOM_INFO(d)));
267 list_del(list);
268 list->next = NULL;
269 ASSERT(!__task_on_queue(d));
270 }
272 typedef int(*list_comparer)(struct list_head* el1, struct list_head* el2);
274 static inline void list_insert_sort(
275 struct list_head *list, struct list_head *element, list_comparer comp)
276 {
277 struct list_head *cur;
279 /* Iterate through all elements to find our "hole". */
280 list_for_each( cur, list )
281 if ( comp(element, cur) < 0 )
282 break;
284 /* cur now contains the element, before which we'll enqueue. */
285 PRINT(3,"\tlist_add to %p\n",cur->prev);
286 list_add(element, cur->prev);
287 }
289 #define DOMAIN_COMPARER(name, field, comp1, comp2) \
290 int name##_comp(struct list_head* el1, struct list_head* el2) \
291 { \
292 struct sedf_vcpu_info *d1, *d2; \
293 d1 = list_entry(el1,struct sedf_vcpu_info, field); \
294 d2 = list_entry(el2,struct sedf_vcpu_info, field); \
295 if ( (comp1) == (comp2) ) \
296 return 0; \
297 if ( (comp1) < (comp2) ) \
298 return -1; \
299 else \
300 return 1; \
301 }
303 /* adds a domain to the queue of processes which wait for the beginning of the
304 next period; this list is therefore sortet by this time, which is simply
305 absol. deadline - period
306 */
307 DOMAIN_COMPARER(waitq, list, PERIOD_BEGIN(d1), PERIOD_BEGIN(d2));
308 static inline void __add_to_waitqueue_sort(struct vcpu *v)
309 {
310 ASSERT(!__task_on_queue(v));
311 PRINT(3,"Adding domain %i.%i (bop= %"PRIu64") to waitq\n",
312 v->domain->domain_id, v->vcpu_id, PERIOD_BEGIN(EDOM_INFO(v)));
313 list_insert_sort(WAITQ(v->processor), LIST(v), waitq_comp);
314 ASSERT(__task_on_queue(v));
315 }
317 /* adds a domain to the queue of processes which have started their current
318 period and are runnable (i.e. not blocked, dieing,...). The first element
319 on this list is running on the processor, if the list is empty the idle
320 task will run. As we are implementing EDF, this list is sorted by deadlines.
321 */
322 DOMAIN_COMPARER(runq, list, d1->deadl_abs, d2->deadl_abs);
323 static inline void __add_to_runqueue_sort(struct vcpu *v)
324 {
325 PRINT(3,"Adding domain %i.%i (deadl= %"PRIu64") to runq\n",
326 v->domain->domain_id, v->vcpu_id, EDOM_INFO(v)->deadl_abs);
327 list_insert_sort(RUNQ(v->processor), LIST(v), runq_comp);
328 }
331 /* Allocates memory for per domain private scheduling data*/
332 static int sedf_alloc_task(struct vcpu *v)
333 {
334 PRINT(2, "sedf_alloc_task was called, domain-id %i.%i\n",
335 v->domain->domain_id, v->vcpu_id);
337 if ( v->domain->sched_priv == NULL )
338 {
339 v->domain->sched_priv = xmalloc(struct sedf_dom_info);
340 if ( v->domain->sched_priv == NULL )
341 return -1;
342 memset(v->domain->sched_priv, 0, sizeof(struct sedf_dom_info));
343 }
345 if ( (v->sched_priv = xmalloc(struct sedf_vcpu_info)) == NULL )
346 return -1;
348 memset(v->sched_priv, 0, sizeof(struct sedf_vcpu_info));
350 return 0;
351 }
354 /* Setup the sedf_dom_info */
355 static void sedf_add_task(struct vcpu *v)
356 {
357 struct sedf_vcpu_info *inf = EDOM_INFO(v);
359 inf->vcpu = v;
361 PRINT(2,"sedf_add_task was called, domain-id %i.%i\n",
362 v->domain->domain_id, v->vcpu_id);
364 /* Allocate per-CPU context if this is the first domain to be added. */
365 if ( unlikely(schedule_data[v->processor].sched_priv == NULL) )
366 {
367 schedule_data[v->processor].sched_priv =
368 xmalloc(struct sedf_cpu_info);
369 BUG_ON(schedule_data[v->processor].sched_priv == NULL);
370 memset(CPU_INFO(v->processor), 0, sizeof(*CPU_INFO(v->processor)));
371 INIT_LIST_HEAD(WAITQ(v->processor));
372 INIT_LIST_HEAD(RUNQ(v->processor));
373 INIT_LIST_HEAD(EXTRAQ(v->processor,EXTRA_PEN_Q));
374 INIT_LIST_HEAD(EXTRAQ(v->processor,EXTRA_UTIL_Q));
375 }
377 if ( v->domain->domain_id == 0 )
378 {
379 /*set dom0 to something useful to boot the machine*/
380 inf->period = MILLISECS(20);
381 inf->slice = MILLISECS(15);
382 inf->latency = 0;
383 inf->deadl_abs = 0;
384 inf->status = EXTRA_AWARE | SEDF_ASLEEP;
385 }
386 else
387 {
388 /*other domains run in best effort mode*/
389 inf->period = WEIGHT_PERIOD;
390 inf->slice = 0;
391 inf->deadl_abs = 0;
392 inf->latency = 0;
393 inf->status = EXTRA_AWARE | SEDF_ASLEEP;
394 inf->extraweight = 1;
395 }
397 inf->period_orig = inf->period; inf->slice_orig = inf->slice;
398 INIT_LIST_HEAD(&(inf->list));
399 INIT_LIST_HEAD(&(inf->extralist[EXTRA_PEN_Q]));
400 INIT_LIST_HEAD(&(inf->extralist[EXTRA_UTIL_Q]));
402 if ( !is_idle_vcpu(v) )
403 {
404 extraq_check(v);
405 }
406 else
407 {
408 EDOM_INFO(v)->deadl_abs = 0;
409 EDOM_INFO(v)->status &= ~SEDF_ASLEEP;
410 }
411 }
413 /* Frees memory used by domain info */
414 static void sedf_free_task(struct domain *d)
415 {
416 int i;
418 PRINT(2,"sedf_free_task was called, domain-id %i\n",d->domain_id);
420 xfree(d->sched_priv);
422 for ( i = 0; i < MAX_VIRT_CPUS; i++ )
423 if ( d->vcpu[i] )
424 xfree(d->vcpu[i]->sched_priv);
425 }
427 /*
428 * Handles the rescheduling & bookkeeping of domains running in their
429 * guaranteed timeslice.
430 */
431 static void desched_edf_dom(s_time_t now, struct vcpu* d)
432 {
433 struct sedf_vcpu_info* inf = EDOM_INFO(d);
435 /* Current domain is running in real time mode. */
436 ASSERT(__task_on_queue(d));
438 /* Update the domain's cputime. */
439 inf->cputime += now - inf->sched_start_abs;
441 /*
442 * Scheduling decisions which don't remove the running domain from the
443 * runq.
444 */
445 if ( (inf->cputime < inf->slice) && sedf_runnable(d) )
446 return;
448 __del_from_queue(d);
450 /*
451 * Manage bookkeeping (i.e. calculate next deadline, memorise
452 * overrun-time of slice) of finished domains.
453 */
454 if ( inf->cputime >= inf->slice )
455 {
456 inf->cputime -= inf->slice;
458 if ( inf->period < inf->period_orig )
459 {
460 /* This domain runs in latency scaling or burst mode. */
461 inf->period *= 2;
462 inf->slice *= 2;
463 if ( (inf->period > inf->period_orig) ||
464 (inf->slice > inf->slice_orig) )
465 {
466 /* Reset slice and period. */
467 inf->period = inf->period_orig;
468 inf->slice = inf->slice_orig;
469 }
470 }
472 /* Set next deadline. */
473 inf->deadl_abs += inf->period;
474 }
476 /* Add a runnable domain to the waitqueue. */
477 if ( sedf_runnable(d) )
478 {
479 __add_to_waitqueue_sort(d);
480 }
481 else
482 {
483 /* We have a blocked realtime task -> remove it from exqs too. */
484 if ( extraq_on(d, EXTRA_PEN_Q) )
485 extraq_del(d, EXTRA_PEN_Q);
486 if ( extraq_on(d, EXTRA_UTIL_Q) )
487 extraq_del(d, EXTRA_UTIL_Q);
488 }
490 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
491 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
492 sedf_runnable(d)));
493 }
496 /* Update all elements on the queues */
497 static void update_queues(
498 s_time_t now, struct list_head *runq, struct list_head *waitq)
499 {
500 struct list_head *cur, *tmp;
501 struct sedf_vcpu_info *curinf;
503 PRINT(3,"Updating waitq..\n");
505 /*
506 * Check for the first elements of the waitqueue, whether their
507 * next period has already started.
508 */
509 list_for_each_safe ( cur, tmp, waitq )
510 {
511 curinf = list_entry(cur, struct sedf_vcpu_info, list);
512 PRINT(4,"\tLooking @ dom %i.%i\n",
513 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
514 if ( PERIOD_BEGIN(curinf) > now )
515 break;
516 __del_from_queue(curinf->vcpu);
517 __add_to_runqueue_sort(curinf->vcpu);
518 }
520 PRINT(3,"Updating runq..\n");
522 /* Process the runq, find domains that are on the runq that shouldn't. */
523 list_for_each_safe ( cur, tmp, runq )
524 {
525 curinf = list_entry(cur,struct sedf_vcpu_info,list);
526 PRINT(4,"\tLooking @ dom %i.%i\n",
527 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
529 if ( unlikely(curinf->slice == 0) )
530 {
531 /* Ignore domains with empty slice. */
532 PRINT(4,"\tUpdating zero-slice domain %i.%i\n",
533 curinf->vcpu->domain->domain_id,
534 curinf->vcpu->vcpu_id);
535 __del_from_queue(curinf->vcpu);
537 /* Move them to their next period. */
538 curinf->deadl_abs += curinf->period;
540 /* Ensure that the start of the next period is in the future. */
541 if ( unlikely(PERIOD_BEGIN(curinf) < now) )
542 curinf->deadl_abs +=
543 (DIV_UP(now - PERIOD_BEGIN(curinf),
544 curinf->period)) * curinf->period;
546 /* Put them back into the queue. */
547 __add_to_waitqueue_sort(curinf->vcpu);
548 }
549 else if ( unlikely((curinf->deadl_abs < now) ||
550 (curinf->cputime > curinf->slice)) )
551 {
552 /*
553 * We missed the deadline or the slice was already finished.
554 * Might hapen because of dom_adj.
555 */
556 PRINT(4,"\tDomain %i.%i exceeded it's deadline/"
557 "slice (%"PRIu64" / %"PRIu64") now: %"PRIu64
558 " cputime: %"PRIu64"\n",
559 curinf->vcpu->domain->domain_id,
560 curinf->vcpu->vcpu_id,
561 curinf->deadl_abs, curinf->slice, now,
562 curinf->cputime);
563 __del_from_queue(curinf->vcpu);
565 /* Common case: we miss one period. */
566 curinf->deadl_abs += curinf->period;
568 /*
569 * If we are still behind: modulo arithmetic, force deadline
570 * to be in future and aligned to period borders.
571 */
572 if ( unlikely(curinf->deadl_abs < now) )
573 curinf->deadl_abs +=
574 DIV_UP(now - curinf->deadl_abs,
575 curinf->period) * curinf->period;
576 ASSERT(curinf->deadl_abs >= now);
578 /* Give a fresh slice. */
579 curinf->cputime = 0;
580 if ( PERIOD_BEGIN(curinf) > now )
581 __add_to_waitqueue_sort(curinf->vcpu);
582 else
583 __add_to_runqueue_sort(curinf->vcpu);
584 }
585 else
586 break;
587 }
589 PRINT(3,"done updating the queues\n");
590 }
593 /* removes a domain from the head of the according extraQ and
594 requeues it at a specified position:
595 round-robin extratime: end of extraQ
596 weighted ext.: insert in sorted list by score
597 if the domain is blocked / has regained its short-block-loss
598 time it is not put on any queue */
599 static void desched_extra_dom(s_time_t now, struct vcpu *d)
600 {
601 struct sedf_vcpu_info *inf = EDOM_INFO(d);
602 int i = extra_get_cur_q(inf);
603 unsigned long oldscore;
605 ASSERT(extraq_on(d, i));
607 /* Unset all running flags. */
608 inf->status &= ~(EXTRA_RUN_PEN | EXTRA_RUN_UTIL);
609 /* Fresh slice for the next run. */
610 inf->cputime = 0;
611 /* Accumulate total extratime. */
612 inf->extra_time_tot += now - inf->sched_start_abs;
613 /* Remove extradomain from head of the queue. */
614 extraq_del(d, i);
616 /* Update the score. */
617 oldscore = inf->score[i];
618 if ( i == EXTRA_PEN_Q )
619 {
620 /*domain was running in L0 extraq*/
621 /*reduce block lost, probably more sophistication here!*/
622 /*inf->short_block_lost_tot -= EXTRA_QUANTUM;*/
623 inf->short_block_lost_tot -= now - inf->sched_start_abs;
624 PRINT(3,"Domain %i.%i: Short_block_loss: %"PRIi64"\n",
625 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id,
626 inf->short_block_lost_tot);
627 if ( inf->short_block_lost_tot <= 0 )
628 {
629 PRINT(4,"Domain %i.%i compensated short block loss!\n",
630 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id);
631 /*we have (over-)compensated our block penalty*/
632 inf->short_block_lost_tot = 0;
633 /*we don't want a place on the penalty queue anymore!*/
634 inf->status &= ~EXTRA_WANT_PEN_Q;
635 goto check_extra_queues;
636 }
638 /*we have to go again for another try in the block-extraq,
639 the score is not used incremantally here, as this is
640 already done by recalculating the block_lost*/
641 inf->score[EXTRA_PEN_Q] = (inf->period << 10) /
642 inf->short_block_lost_tot;
643 oldscore = 0;
644 }
645 else
646 {
647 /*domain was running in L1 extraq => score is inverse of
648 utilization and is used somewhat incremental!*/
649 if ( !inf->extraweight )
650 /*NB: use fixed point arithmetic with 10 bits*/
651 inf->score[EXTRA_UTIL_Q] = (inf->period << 10) /
652 inf->slice;
653 else
654 /*conversion between realtime utilisation and extrawieght:
655 full (ie 100%) utilization is equivalent to 128 extraweight*/
656 inf->score[EXTRA_UTIL_Q] = (1<<17) / inf->extraweight;
657 }
659 check_extra_queues:
660 /* Adding a runnable domain to the right queue and removing blocked ones*/
661 if ( sedf_runnable(d) )
662 {
663 /*add according to score: weighted round robin*/
664 if (((inf->status & EXTRA_AWARE) && (i == EXTRA_UTIL_Q)) ||
665 ((inf->status & EXTRA_WANT_PEN_Q) && (i == EXTRA_PEN_Q)))
666 extraq_add_sort_update(d, i, oldscore);
667 }
668 else
669 {
670 /*remove this blocked domain from the waitq!*/
671 __del_from_queue(d);
672 /*make sure that we remove a blocked domain from the other
673 extraq too*/
674 if ( i == EXTRA_PEN_Q )
675 {
676 if ( extraq_on(d, EXTRA_UTIL_Q) )
677 extraq_del(d, EXTRA_UTIL_Q);
678 }
679 else
680 {
681 if ( extraq_on(d, EXTRA_PEN_Q) )
682 extraq_del(d, EXTRA_PEN_Q);
683 }
684 }
686 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
687 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
688 sedf_runnable(d)));
689 }
692 static struct task_slice sedf_do_extra_schedule(
693 s_time_t now, s_time_t end_xt, struct list_head *extraq[], int cpu)
694 {
695 struct task_slice ret;
696 struct sedf_vcpu_info *runinf;
697 ASSERT(end_xt > now);
699 /* Enough time left to use for extratime? */
700 if ( end_xt - now < EXTRA_QUANTUM )
701 goto return_idle;
703 if ( !list_empty(extraq[EXTRA_PEN_Q]) )
704 {
705 /*we still have elements on the level 0 extraq
706 => let those run first!*/
707 runinf = list_entry(extraq[EXTRA_PEN_Q]->next,
708 struct sedf_vcpu_info, extralist[EXTRA_PEN_Q]);
709 runinf->status |= EXTRA_RUN_PEN;
710 ret.task = runinf->vcpu;
711 ret.time = EXTRA_QUANTUM;
712 #ifdef SEDF_STATS
713 runinf->pen_extra_slices++;
714 #endif
715 }
716 else
717 {
718 if ( !list_empty(extraq[EXTRA_UTIL_Q]) )
719 {
720 /*use elements from the normal extraqueue*/
721 runinf = list_entry(extraq[EXTRA_UTIL_Q]->next,
722 struct sedf_vcpu_info,
723 extralist[EXTRA_UTIL_Q]);
724 runinf->status |= EXTRA_RUN_UTIL;
725 ret.task = runinf->vcpu;
726 ret.time = EXTRA_QUANTUM;
727 }
728 else
729 goto return_idle;
730 }
732 ASSERT(ret.time > 0);
733 ASSERT(sedf_runnable(ret.task));
734 return ret;
736 return_idle:
737 ret.task = IDLETASK(cpu);
738 ret.time = end_xt - now;
739 ASSERT(ret.time > 0);
740 ASSERT(sedf_runnable(ret.task));
741 return ret;
742 }
745 /* Main scheduling function
746 Reasons for calling this function are:
747 -timeslice for the current period used up
748 -domain on waitqueue has started it's period
749 -and various others ;) in general: determine which domain to run next*/
750 static struct task_slice sedf_do_schedule(s_time_t now)
751 {
752 int cpu = smp_processor_id();
753 struct list_head *runq = RUNQ(cpu);
754 struct list_head *waitq = WAITQ(cpu);
755 struct sedf_vcpu_info *inf = EDOM_INFO(current);
756 struct list_head *extraq[] = {
757 EXTRAQ(cpu, EXTRA_PEN_Q), EXTRAQ(cpu, EXTRA_UTIL_Q)};
758 struct sedf_vcpu_info *runinf, *waitinf;
759 struct task_slice ret;
761 /*idle tasks don't need any of the following stuf*/
762 if ( is_idle_vcpu(current) )
763 goto check_waitq;
765 /* create local state of the status of the domain, in order to avoid
766 inconsistent state during scheduling decisions, because data for
767 vcpu_runnable is not protected by the scheduling lock!*/
768 if ( !vcpu_runnable(current) )
769 inf->status |= SEDF_ASLEEP;
771 if ( inf->status & SEDF_ASLEEP )
772 inf->block_abs = now;
774 if ( unlikely(extra_runs(inf)) )
775 {
776 /*special treatment of domains running in extra time*/
777 desched_extra_dom(now, current);
778 }
779 else
780 {
781 desched_edf_dom(now, current);
782 }
783 check_waitq:
784 update_queues(now, runq, waitq);
786 /*now simply pick the first domain from the runqueue, which has the
787 earliest deadline, because the list is sorted*/
789 if ( !list_empty(runq) )
790 {
791 runinf = list_entry(runq->next,struct sedf_vcpu_info,list);
792 ret.task = runinf->vcpu;
793 if ( !list_empty(waitq) )
794 {
795 waitinf = list_entry(waitq->next,
796 struct sedf_vcpu_info,list);
797 /*rerun scheduler, when scheduled domain reaches it's
798 end of slice or the first domain from the waitqueue
799 gets ready*/
800 ret.time = MIN(now + runinf->slice - runinf->cputime,
801 PERIOD_BEGIN(waitinf)) - now;
802 }
803 else
804 {
805 ret.time = runinf->slice - runinf->cputime;
806 }
807 CHECK(ret.time > 0);
808 goto sched_done;
809 }
811 if ( !list_empty(waitq) )
812 {
813 waitinf = list_entry(waitq->next,struct sedf_vcpu_info, list);
814 /*we could not find any suitable domain
815 => look for domains that are aware of extratime*/
816 ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf),
817 extraq, cpu);
818 CHECK(ret.time > 0);
819 }
820 else
821 {
822 /*this could probably never happen, but one never knows...*/
823 /*it can... imagine a second CPU, which is pure scifi ATM,
824 but one never knows ;)*/
825 ret.task = IDLETASK(cpu);
826 ret.time = SECONDS(1);
827 }
829 sched_done:
830 /*TODO: Do something USEFUL when this happens and find out, why it
831 still can happen!!!*/
832 if ( ret.time < 0)
833 {
834 printk("Ouch! We are seriously BEHIND schedule! %"PRIi64"\n",
835 ret.time);
836 ret.time = EXTRA_QUANTUM;
837 }
839 EDOM_INFO(ret.task)->sched_start_abs = now;
840 CHECK(ret.time > 0);
841 ASSERT(sedf_runnable(ret.task));
842 CPU_INFO(cpu)->current_slice_expires = now + ret.time;
843 return ret;
844 }
847 static void sedf_sleep(struct vcpu *d)
848 {
849 PRINT(2,"sedf_sleep was called, domain-id %i.%i\n",
850 d->domain->domain_id, d->vcpu_id);
852 if ( is_idle_vcpu(d) )
853 return;
855 EDOM_INFO(d)->status |= SEDF_ASLEEP;
857 if ( schedule_data[d->processor].curr == d )
858 {
859 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
860 }
861 else
862 {
863 if ( __task_on_queue(d) )
864 __del_from_queue(d);
865 if ( extraq_on(d, EXTRA_UTIL_Q) )
866 extraq_del(d, EXTRA_UTIL_Q);
867 if ( extraq_on(d, EXTRA_PEN_Q) )
868 extraq_del(d, EXTRA_PEN_Q);
869 }
870 }
873 /* This function wakes up a domain, i.e. moves them into the waitqueue
874 * things to mention are: admission control is taking place nowhere at
875 * the moment, so we can't be sure, whether it is safe to wake the domain
876 * up at all. Anyway, even if it is safe (total cpu usage <=100%) there are
877 * some considerations on when to allow the domain to wake up and have it's
878 * first deadline...
879 * I detected 3 cases, which could describe the possible behaviour of the
880 * scheduler,
881 * and I'll try to make them more clear:
882 *
883 * 1. Very conservative
884 * -when a blocked domain unblocks, it is allowed to start execution at
885 * the beginning of the next complete period
886 * (D..deadline, R..running, B..blocking/sleeping, U..unblocking/waking up
887 *
888 * DRRB_____D__U_____DRRRRR___D________ ...
889 *
890 * -this causes the domain to miss a period (and a deadlline)
891 * -doesn't disturb the schedule at all
892 * -deadlines keep occuring isochronous
893 *
894 * 2. Conservative Part 1: Short Unblocking
895 * -when a domain unblocks in the same period as it was blocked it
896 * unblocks and may consume the rest of it's original time-slice minus
897 * the time it was blocked
898 * (assume period=9, slice=5)
899 *
900 * DRB_UR___DRRRRR___D...
901 *
902 * -this also doesn't disturb scheduling, but might lead to the fact, that
903 * the domain can't finish it's workload in the period
904 * -in addition to that the domain can be treated prioritised when
905 * extratime is available
906 * -addition: experiments have shown that this may have a HUGE impact on
907 * performance of other domains, becaus it can lead to excessive context
908 * switches
909 *
910 * Part2: Long Unblocking
911 * Part 2a
912 * -it is obvious that such accounting of block time, applied when
913 * unblocking is happening in later periods, works fine aswell
914 * -the domain is treated as if it would have been running since the start
915 * of its new period
916 *
917 * DRB______D___UR___D...
918 *
919 * Part 2b
920 * -if one needs the full slice in the next period, it is necessary to
921 * treat the unblocking time as the start of the new period, i.e. move
922 * the deadline further back (later)
923 * -this doesn't disturb scheduling as well, because for EDF periods can
924 * be treated as minimal inter-release times and scheduling stays
925 * correct, when deadlines are kept relative to the time the process
926 * unblocks
927 *
928 * DRB______D___URRRR___D...<prev [Thread] next>
929 * (D) <- old deadline was here
930 * -problem: deadlines don't occur isochronous anymore
931 * Part 2c (Improved Atropos design)
932 * -when a domain unblocks it is given a very short period (=latency hint)
933 * and slice length scaled accordingly
934 * -both rise again to the original value (e.g. get doubled every period)
935 *
936 * 3. Unconservative (i.e. incorrect)
937 * -to boost the performance of I/O dependent domains it would be possible
938 * to put the domain into the runnable queue immediately, and let it run
939 * for the remainder of the slice of the current period
940 * (or even worse: allocate a new full slice for the domain)
941 * -either behaviour can lead to missed deadlines in other domains as
942 * opposed to approaches 1,2a,2b
943 */
944 static void unblock_short_extra_support(
945 struct sedf_vcpu_info* inf, s_time_t now)
946 {
947 /*this unblocking scheme tries to support the domain, by assigning it
948 a priority in extratime distribution according to the loss of time
949 in this slice due to blocking*/
950 s_time_t pen;
952 /*no more realtime execution in this period!*/
953 inf->deadl_abs += inf->period;
954 if ( likely(inf->block_abs) )
955 {
956 //treat blocked time as consumed by the domain*/
957 /*inf->cputime += now - inf->block_abs;*/
958 /*penalty is time the domain would have
959 had if it continued to run */
960 pen = (inf->slice - inf->cputime);
961 if ( pen < 0 )
962 pen = 0;
963 /*accumulate all penalties over the periods*/
964 /*inf->short_block_lost_tot += pen;*/
965 /*set penalty to the current value*/
966 inf->short_block_lost_tot = pen;
967 /*not sure which one is better.. but seems to work well...*/
969 if ( inf->short_block_lost_tot )
970 {
971 inf->score[0] = (inf->period << 10) /
972 inf->short_block_lost_tot;
973 #ifdef SEDF_STATS
974 inf->pen_extra_blocks++;
975 #endif
976 if ( extraq_on(inf->vcpu, EXTRA_PEN_Q) )
977 /*remove domain for possible resorting!*/
978 extraq_del(inf->vcpu, EXTRA_PEN_Q);
979 else
980 /*remember that we want to be on the penalty q
981 so that we can continue when we (un-)block
982 in penalty-extratime*/
983 inf->status |= EXTRA_WANT_PEN_Q;
985 /*(re-)add domain to the penalty extraq*/
986 extraq_add_sort_update(inf->vcpu, EXTRA_PEN_Q, 0);
987 }
988 }
990 /*give it a fresh slice in the next period!*/
991 inf->cputime = 0;
992 }
995 static void unblock_long_cons_b(struct sedf_vcpu_info* inf,s_time_t now)
996 {
997 /*Conservative 2b*/
998 /*Treat the unblocking time as a start of a new period */
999 inf->deadl_abs = now + inf->period;
1000 inf->cputime = 0;
1004 #define DOMAIN_EDF 1
1005 #define DOMAIN_EXTRA_PEN 2
1006 #define DOMAIN_EXTRA_UTIL 3
1007 #define DOMAIN_IDLE 4
1008 static inline int get_run_type(struct vcpu* d)
1010 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1011 if (is_idle_vcpu(d))
1012 return DOMAIN_IDLE;
1013 if (inf->status & EXTRA_RUN_PEN)
1014 return DOMAIN_EXTRA_PEN;
1015 if (inf->status & EXTRA_RUN_UTIL)
1016 return DOMAIN_EXTRA_UTIL;
1017 return DOMAIN_EDF;
1021 /*Compares two domains in the relation of whether the one is allowed to
1022 interrupt the others execution.
1023 It returns true (!=0) if a switch to the other domain is good.
1024 Current Priority scheme is as follows:
1025 EDF > L0 (penalty based) extra-time >
1026 L1 (utilization) extra-time > idle-domain
1027 In the same class priorities are assigned as following:
1028 EDF: early deadline > late deadline
1029 L0 extra-time: lower score > higher score*/
1030 static inline int should_switch(struct vcpu *cur,
1031 struct vcpu *other,
1032 s_time_t now)
1034 struct sedf_vcpu_info *cur_inf, *other_inf;
1035 cur_inf = EDOM_INFO(cur);
1036 other_inf = EDOM_INFO(other);
1038 /* Check whether we need to make an earlier scheduling decision. */
1039 if ( PERIOD_BEGIN(other_inf) <
1040 CPU_INFO(other->processor)->current_slice_expires )
1041 return 1;
1043 /* No timing-based switches need to be taken into account here. */
1044 switch ( get_run_type(cur) )
1046 case DOMAIN_EDF:
1047 /* Do not interrupt a running EDF domain. */
1048 return 0;
1049 case DOMAIN_EXTRA_PEN:
1050 /* Check whether we also want the L0 ex-q with lower score. */
1051 return ((other_inf->status & EXTRA_WANT_PEN_Q) &&
1052 (other_inf->score[EXTRA_PEN_Q] <
1053 cur_inf->score[EXTRA_PEN_Q]));
1054 case DOMAIN_EXTRA_UTIL:
1055 /* Check whether we want the L0 extraq. Don't
1056 * switch if both domains want L1 extraq.
1057 */
1058 return !!(other_inf->status & EXTRA_WANT_PEN_Q);
1059 case DOMAIN_IDLE:
1060 return 1;
1063 return 1;
1066 void sedf_wake(struct vcpu *d)
1068 s_time_t now = NOW();
1069 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1071 PRINT(3, "sedf_wake was called, domain-id %i.%i\n",d->domain->domain_id,
1072 d->vcpu_id);
1074 if ( unlikely(is_idle_vcpu(d)) )
1075 return;
1077 if ( unlikely(__task_on_queue(d)) )
1079 PRINT(3,"\tdomain %i.%i is already in some queue\n",
1080 d->domain->domain_id, d->vcpu_id);
1081 return;
1084 ASSERT(!sedf_runnable(d));
1085 inf->status &= ~SEDF_ASLEEP;
1086 ASSERT(!extraq_on(d, EXTRA_UTIL_Q));
1087 ASSERT(!extraq_on(d, EXTRA_PEN_Q));
1089 if ( unlikely(inf->deadl_abs == 0) )
1091 /*initial setup of the deadline*/
1092 inf->deadl_abs = now + inf->slice;
1095 PRINT(3, "waking up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64
1096 "now= %"PRIu64")\n",
1097 d->domain->domain_id, d->vcpu_id, inf->deadl_abs, inf->period, now);
1099 #ifdef SEDF_STATS
1100 inf->block_tot++;
1101 #endif
1103 if ( unlikely(now < PERIOD_BEGIN(inf)) )
1105 PRINT(4,"extratime unblock\n");
1106 /* unblocking in extra-time! */
1107 if ( inf->status & EXTRA_WANT_PEN_Q )
1109 /*we have a domain that wants compensation
1110 for block penalty and did just block in
1111 its compensation time. Give it another
1112 chance!*/
1113 extraq_add_sort_update(d, EXTRA_PEN_Q, 0);
1115 extraq_check_add_unblocked(d, 0);
1117 else
1119 if ( now < inf->deadl_abs )
1121 PRINT(4,"short unblocking\n");
1122 /*short blocking*/
1123 #ifdef SEDF_STATS
1124 inf->short_block_tot++;
1125 #endif
1126 unblock_short_extra_support(inf, now);
1128 extraq_check_add_unblocked(d, 1);
1130 else
1132 PRINT(4,"long unblocking\n");
1133 /*long unblocking*/
1134 #ifdef SEDF_STATS
1135 inf->long_block_tot++;
1136 #endif
1137 unblock_long_cons_b(inf, now);
1139 extraq_check_add_unblocked(d, 1);
1143 PRINT(3, "woke up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64
1144 "now= %"PRIu64")\n",
1145 d->domain->domain_id, d->vcpu_id, inf->deadl_abs,
1146 inf->period, now);
1148 if ( PERIOD_BEGIN(inf) > now )
1150 __add_to_waitqueue_sort(d);
1151 PRINT(3,"added to waitq\n");
1153 else
1155 __add_to_runqueue_sort(d);
1156 PRINT(3,"added to runq\n");
1159 #ifdef SEDF_STATS
1160 /*do some statistics here...*/
1161 if ( inf->block_abs != 0 )
1163 inf->block_time_tot += now - inf->block_abs;
1164 inf->penalty_time_tot +=
1165 PERIOD_BEGIN(inf) + inf->cputime - inf->block_abs;
1167 #endif
1169 /*sanity check: make sure each extra-aware domain IS on the util-q!*/
1170 ASSERT(IMPLY(inf->status & EXTRA_AWARE, extraq_on(d, EXTRA_UTIL_Q)));
1171 ASSERT(__task_on_queue(d));
1172 /*check whether the awakened task needs to invoke the do_schedule
1173 routine. Try to avoid unnecessary runs but:
1174 Save approximation: Always switch to scheduler!*/
1175 ASSERT(d->processor >= 0);
1176 ASSERT(d->processor < NR_CPUS);
1177 ASSERT(schedule_data[d->processor].curr);
1179 if ( should_switch(schedule_data[d->processor].curr, d, now) )
1180 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
1184 static int sedf_set_affinity(struct vcpu *v, cpumask_t *affinity)
1186 if ( v == current )
1187 return cpu_isset(v->processor, *affinity) ? 0 : -EBUSY;
1189 vcpu_pause(v);
1190 v->cpu_affinity = *affinity;
1191 v->processor = first_cpu(v->cpu_affinity);
1192 vcpu_unpause(v);
1194 return 0;
1198 /* Print a lot of useful information about a domains in the system */
1199 static void sedf_dump_domain(struct vcpu *d)
1201 printk("%i.%i has=%c ", d->domain->domain_id, d->vcpu_id,
1202 test_bit(_VCPUF_running, &d->vcpu_flags) ? 'T':'F');
1203 printk("p=%"PRIu64" sl=%"PRIu64" ddl=%"PRIu64" w=%hu"
1204 " sc=%i xtr(%s)=%"PRIu64" ew=%hu",
1205 EDOM_INFO(d)->period, EDOM_INFO(d)->slice, EDOM_INFO(d)->deadl_abs,
1206 EDOM_INFO(d)->weight,
1207 EDOM_INFO(d)->score[EXTRA_UTIL_Q],
1208 (EDOM_INFO(d)->status & EXTRA_AWARE) ? "yes" : "no",
1209 EDOM_INFO(d)->extra_time_tot, EDOM_INFO(d)->extraweight);
1211 #ifdef SEDF_STATS
1212 if ( EDOM_INFO(d)->block_time_tot != 0 )
1213 printf(" pen=%"PRIu64"%%", (EDOM_INFO(d)->penalty_time_tot * 100) /
1214 EDOM_INFO(d)->block_time_tot);
1215 if ( EDOM_INFO(d)->block_tot != 0 )
1216 printf("\n blks=%u sh=%u (%u%%) (shc=%u (%u%%) shex=%i "\
1217 "shexsl=%i) l=%u (%u%%) avg: b=%"PRIu64" p=%"PRIu64"",
1218 EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_block_tot,
1219 (EDOM_INFO(d)->short_block_tot * 100)
1220 / EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_cont,
1221 (EDOM_INFO(d)->short_cont * 100) / EDOM_INFO(d)->block_tot,
1222 EDOM_INFO(d)->pen_extra_blocks,
1223 EDOM_INFO(d)->pen_extra_slices,
1224 EDOM_INFO(d)->long_block_tot,
1225 (EDOM_INFO(d)->long_block_tot * 100) / EDOM_INFO(d)->block_tot,
1226 (EDOM_INFO(d)->block_time_tot) / EDOM_INFO(d)->block_tot,
1227 (EDOM_INFO(d)->penalty_time_tot) / EDOM_INFO(d)->block_tot);
1228 #endif
1229 printf("\n");
1233 /* dumps all domains on hte specified cpu */
1234 static void sedf_dump_cpu_state(int i)
1236 struct list_head *list, *queue, *tmp;
1237 struct sedf_vcpu_info *d_inf;
1238 struct domain *d;
1239 struct vcpu *ed;
1240 int loop = 0;
1242 printk("now=%"PRIu64"\n",NOW());
1243 queue = RUNQ(i);
1244 printk("RUNQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1245 (unsigned long) queue->next, (unsigned long) queue->prev);
1246 list_for_each_safe ( list, tmp, queue )
1248 printk("%3d: ",loop++);
1249 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1250 sedf_dump_domain(d_inf->vcpu);
1253 queue = WAITQ(i); loop = 0;
1254 printk("\nWAITQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1255 (unsigned long) queue->next, (unsigned long) queue->prev);
1256 list_for_each_safe ( list, tmp, queue )
1258 printk("%3d: ",loop++);
1259 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1260 sedf_dump_domain(d_inf->vcpu);
1263 queue = EXTRAQ(i,EXTRA_PEN_Q); loop = 0;
1264 printk("\nEXTRAQ (penalty) rq %lx n: %lx, p: %lx\n",
1265 (unsigned long)queue, (unsigned long) queue->next,
1266 (unsigned long) queue->prev);
1267 list_for_each_safe ( list, tmp, queue )
1269 d_inf = list_entry(list, struct sedf_vcpu_info,
1270 extralist[EXTRA_PEN_Q]);
1271 printk("%3d: ",loop++);
1272 sedf_dump_domain(d_inf->vcpu);
1275 queue = EXTRAQ(i,EXTRA_UTIL_Q); loop = 0;
1276 printk("\nEXTRAQ (utilization) rq %lx n: %lx, p: %lx\n",
1277 (unsigned long)queue, (unsigned long) queue->next,
1278 (unsigned long) queue->prev);
1279 list_for_each_safe ( list, tmp, queue )
1281 d_inf = list_entry(list, struct sedf_vcpu_info,
1282 extralist[EXTRA_UTIL_Q]);
1283 printk("%3d: ",loop++);
1284 sedf_dump_domain(d_inf->vcpu);
1287 loop = 0;
1288 printk("\nnot on Q\n");
1290 for_each_domain ( d )
1292 for_each_vcpu(d, ed)
1294 if ( !__task_on_queue(ed) && (ed->processor == i) )
1296 printk("%3d: ",loop++);
1297 sedf_dump_domain(ed);
1304 /* Adjusts periods and slices of the domains accordingly to their weights. */
1305 static int sedf_adjust_weights(struct sched_adjdom_cmd *cmd)
1307 struct vcpu *p;
1308 struct domain *d;
1309 int sumw[NR_CPUS];
1310 s_time_t sumt[NR_CPUS];
1311 int cpu;
1313 for ( cpu = 0; cpu < NR_CPUS; cpu++ )
1315 sumw[cpu] = 0;
1316 sumt[cpu] = 0;
1319 /* Sum across all weights. */
1320 for_each_domain( d )
1322 for_each_vcpu( d, p )
1324 if ( EDOM_INFO(p)->weight )
1326 sumw[p->processor] += EDOM_INFO(p)->weight;
1328 else
1330 /*don't modify domains who don't have a weight, but sum
1331 up the time they need, projected to a WEIGHT_PERIOD,
1332 so that this time is not given to the weight-driven
1333 domains*/
1334 /*check for overflows*/
1335 ASSERT((WEIGHT_PERIOD < ULONG_MAX)
1336 && (EDOM_INFO(p)->slice_orig < ULONG_MAX));
1337 sumt[p->processor] +=
1338 (WEIGHT_PERIOD * EDOM_INFO(p)->slice_orig) /
1339 EDOM_INFO(p)->period_orig;
1344 /* Adjust all slices (and periods) to the new weight. */
1345 for_each_domain( d )
1347 for_each_vcpu ( d, p )
1349 if ( EDOM_INFO(p)->weight )
1351 EDOM_INFO(p)->period_orig =
1352 EDOM_INFO(p)->period = WEIGHT_PERIOD;
1353 EDOM_INFO(p)->slice_orig =
1354 EDOM_INFO(p)->slice =
1355 (EDOM_INFO(p)->weight *
1356 (WEIGHT_PERIOD - WEIGHT_SAFETY - sumt[p->processor])) /
1357 sumw[p->processor];
1362 return 0;
1366 /* set or fetch domain scheduling parameters */
1367 static int sedf_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd)
1369 struct vcpu *v;
1371 PRINT(2,"sedf_adjdom was called, domain-id %i new period %"PRIu64" "
1372 "new slice %"PRIu64"\nlatency %"PRIu64" extra:%s\n",
1373 p->domain_id, cmd->u.sedf.period, cmd->u.sedf.slice,
1374 cmd->u.sedf.latency, (cmd->u.sedf.extratime)?"yes":"no");
1376 if ( cmd->direction == SCHED_INFO_PUT )
1378 /* Check for sane parameters. */
1379 if ( !cmd->u.sedf.period && !cmd->u.sedf.weight )
1380 return -EINVAL;
1381 if ( cmd->u.sedf.weight )
1383 if ( (cmd->u.sedf.extratime & EXTRA_AWARE) &&
1384 (!cmd->u.sedf.period) )
1386 /* Weight-driven domains with extratime only. */
1387 for_each_vcpu ( p, v )
1389 EDOM_INFO(v)->extraweight = cmd->u.sedf.weight;
1390 EDOM_INFO(v)->weight = 0;
1391 EDOM_INFO(v)->slice = 0;
1392 EDOM_INFO(v)->period = WEIGHT_PERIOD;
1395 else
1397 /* Weight-driven domains with real-time execution. */
1398 for_each_vcpu ( p, v )
1399 EDOM_INFO(v)->weight = cmd->u.sedf.weight;
1402 else
1404 /* Time-driven domains. */
1405 for_each_vcpu ( p, v )
1407 /*
1408 * Sanity checking: note that disabling extra weight requires
1409 * that we set a non-zero slice.
1410 */
1411 if ( (cmd->u.sedf.period > PERIOD_MAX) ||
1412 (cmd->u.sedf.period < PERIOD_MIN) ||
1413 (cmd->u.sedf.slice > cmd->u.sedf.period) ||
1414 (cmd->u.sedf.slice < SLICE_MIN) )
1415 return -EINVAL;
1416 EDOM_INFO(v)->weight = 0;
1417 EDOM_INFO(v)->extraweight = 0;
1418 EDOM_INFO(v)->period_orig =
1419 EDOM_INFO(v)->period = cmd->u.sedf.period;
1420 EDOM_INFO(v)->slice_orig =
1421 EDOM_INFO(v)->slice = cmd->u.sedf.slice;
1425 if ( sedf_adjust_weights(cmd) )
1426 return -EINVAL;
1428 for_each_vcpu ( p, v )
1430 EDOM_INFO(v)->status =
1431 (EDOM_INFO(v)->status &
1432 ~EXTRA_AWARE) | (cmd->u.sedf.extratime & EXTRA_AWARE);
1433 EDOM_INFO(v)->latency = cmd->u.sedf.latency;
1434 extraq_check(v);
1437 else if ( cmd->direction == SCHED_INFO_GET )
1439 cmd->u.sedf.period = EDOM_INFO(p->vcpu[0])->period;
1440 cmd->u.sedf.slice = EDOM_INFO(p->vcpu[0])->slice;
1441 cmd->u.sedf.extratime = EDOM_INFO(p->vcpu[0])->status & EXTRA_AWARE;
1442 cmd->u.sedf.latency = EDOM_INFO(p->vcpu[0])->latency;
1443 cmd->u.sedf.weight = EDOM_INFO(p->vcpu[0])->weight;
1446 PRINT(2,"sedf_adjdom_finished\n");
1447 return 0;
1450 struct scheduler sched_sedf_def = {
1451 .name = "Simple EDF Scheduler",
1452 .opt_name = "sedf",
1453 .sched_id = SCHED_SEDF,
1455 .alloc_task = sedf_alloc_task,
1456 .add_task = sedf_add_task,
1457 .free_task = sedf_free_task,
1458 .do_schedule = sedf_do_schedule,
1459 .dump_cpu_state = sedf_dump_cpu_state,
1460 .sleep = sedf_sleep,
1461 .wake = sedf_wake,
1462 .adjdom = sedf_adjdom,
1463 .set_affinity = sedf_set_affinity
1464 };
1466 /*
1467 * Local variables:
1468 * mode: C
1469 * c-set-style: "BSD"
1470 * c-basic-offset: 4
1471 * tab-width: 4
1472 * indent-tabs-mode: nil
1473 * End:
1474 */