debuggers.hg

annotate xen/common/sched_sedf.c @ 22848:6341fe0f4e5a

Added tag 4.1.0-rc2 for changeset 9dca60d88c63
author Keir Fraser <keir@xen.org>
date Tue Jan 25 14:06:55 2011 +0000 (2011-01-25)
parents 548c808be2a6
children
rev   line source
kaf24@4847 1 /******************************************************************************
sd386@3487 2 * Simple EDF scheduler for xen
sd386@3487 3 *
sd386@3487 4 * by Stephan Diestelhorst (C) 2004 Cambridge University
sd386@3487 5 * based on code by Mark Williamson (C) 2004 Intel Research Cambridge
sd386@3487 6 */
sd386@3487 7
cl349@5323 8 #include <xen/lib.h>
sd386@3487 9 #include <xen/sched.h>
sd386@3487 10 #include <xen/sched-if.h>
kaf24@8616 11 #include <xen/timer.h>
sd386@3487 12 #include <xen/softirq.h>
sd386@3487 13 #include <xen/time.h>
kaf24@11236 14 #include <xen/errno.h>
sd386@3487 15
sd386@4451 16 /*verbosity settings*/
sd386@4410 17 #define SEDFLEVEL 0
kaf24@9629 18 #define PRINT(_f, _a...) \
kaf24@9629 19 do { \
kaf24@9629 20 if ( (_f) <= SEDFLEVEL ) \
kaf24@9629 21 printk(_a ); \
kaf24@9629 22 } while ( 0 )
sd386@3487 23
keir@21258 24 #define SEDF_CPUONLINE(_pool) \
keir@21258 25 (((_pool) == NULL) ? &cpupool_free_cpus : &(_pool)->cpu_valid)
keir@21258 26
sd386@4767 27 #ifndef NDEBUG
kaf24@5184 28 #define SEDF_STATS
kaf24@9629 29 #define CHECK(_p) \
kaf24@9629 30 do { \
kaf24@9629 31 if ( !(_p) ) \
kaf24@9629 32 printk("Check '%s' failed, line %d, file %s\n", \
kaf24@9629 33 #_p , __LINE__, __FILE__); \
kaf24@9629 34 } while ( 0 )
sd386@4767 35 #else
kaf24@5184 36 #define CHECK(_p) ((void)0)
sd386@4410 37 #endif
sd386@4410 38
sd386@3611 39 #define EXTRA_NONE (0)
sd386@3611 40 #define EXTRA_AWARE (1)
sd386@4080 41 #define EXTRA_RUN_PEN (2)
sd386@4080 42 #define EXTRA_RUN_UTIL (4)
sd386@4080 43 #define EXTRA_WANT_PEN_Q (8)
sd386@4080 44 #define EXTRA_PEN_Q (0)
sd386@4080 45 #define EXTRA_UTIL_Q (1)
sd386@4767 46 #define SEDF_ASLEEP (16)
sd386@4080 47
sd386@3888 48 #define EXTRA_QUANTUM (MICROSECS(500))
sd386@3611 49 #define WEIGHT_PERIOD (MILLISECS(100))
sd386@3611 50 #define WEIGHT_SAFETY (MILLISECS(5))
sd386@3487 51
kaf24@9302 52 #define PERIOD_MAX MILLISECS(10000) /* 10s */
kaf24@9302 53 #define PERIOD_MIN (MICROSECS(10)) /* 10us */
kaf24@9302 54 #define SLICE_MIN (MICROSECS(5)) /* 5us */
kaf24@9202 55
sd386@4767 56 #define IMPLY(a, b) (!(a) || (b))
sd386@4767 57 #define EQ(a, b) ((!!(a)) == (!!(b)))
sd386@4767 58
sd386@4767 59
sd386@4680 60 struct sedf_dom_info {
kaf24@5184 61 struct domain *domain;
sd386@4680 62 };
kaf24@9629 63
kaf24@9629 64 struct sedf_vcpu_info {
kaf24@5327 65 struct vcpu *vcpu;
kaf24@5184 66 struct list_head list;
kaf24@5184 67 struct list_head extralist[2];
kaf24@5184 68
kaf24@5184 69 /*Parameters for EDF*/
kaf24@5184 70 s_time_t period; /*=(relative deadline)*/
kaf24@5184 71 s_time_t slice; /*=worst case execution time*/
kaf24@5184 72
kaf24@5184 73 /*Advaced Parameters*/
kaf24@5184 74 /*Latency Scaling*/
shand@11173 75 s_time_t period_orig;
kaf24@5184 76 s_time_t slice_orig;
kaf24@5184 77 s_time_t latency;
kaf24@5184 78
kaf24@5184 79 /*status of domain*/
kaf24@9629 80 int status;
kaf24@5184 81 /*weights for "Scheduling for beginners/ lazy/ etc." ;)*/
kaf24@9629 82 short weight;
kaf24@9629 83 short extraweight;
kaf24@5184 84 /*Bookkeeping*/
kaf24@5184 85 s_time_t deadl_abs;
kaf24@5184 86 s_time_t sched_start_abs;
kaf24@5184 87 s_time_t cputime;
kaf24@5184 88 /* times the domain un-/blocked */
kaf24@5184 89 s_time_t block_abs;
kaf24@5184 90 s_time_t unblock_abs;
kaf24@5184 91
kaf24@5184 92 /*scores for {util, block penalty}-weighted extratime distribution*/
shand@11173 93 int score[2];
kaf24@5184 94 s_time_t short_block_lost_tot;
kaf24@5184 95
kaf24@5184 96 /*Statistics*/
kaf24@5184 97 s_time_t extra_time_tot;
sd386@4410 98
sd386@4410 99 #ifdef SEDF_STATS
kaf24@5184 100 s_time_t block_time_tot;
kaf24@5184 101 s_time_t penalty_time_tot;
kaf24@5184 102 int block_tot;
kaf24@5184 103 int short_block_tot;
kaf24@5184 104 int long_block_tot;
kaf24@5184 105 int short_cont;
kaf24@5184 106 int pen_extra_blocks;
kaf24@5184 107 int pen_extra_slices;
sd386@4410 108 #endif
sd386@3487 109 };
sd386@3487 110
sd386@3487 111 struct sedf_cpu_info {
kaf24@5184 112 struct list_head runnableq;
kaf24@5184 113 struct list_head waitq;
kaf24@5184 114 struct list_head extraq[2];
kaf24@5190 115 s_time_t current_slice_expires;
sd386@3487 116 };
sd386@3487 117
kaf24@9629 118 #define EDOM_INFO(d) ((struct sedf_vcpu_info *)((d)->sched_priv))
kaf24@11017 119 #define CPU_INFO(cpu) \
kaf24@11017 120 ((struct sedf_cpu_info *)per_cpu(schedule_data, cpu).sched_priv)
kaf24@9629 121 #define LIST(d) (&EDOM_INFO(d)->list)
kaf24@9629 122 #define EXTRALIST(d,i) (&(EDOM_INFO(d)->extralist[i]))
kaf24@9629 123 #define RUNQ(cpu) (&CPU_INFO(cpu)->runnableq)
kaf24@5184 124 #define WAITQ(cpu) (&CPU_INFO(cpu)->waitq)
kaf24@9629 125 #define EXTRAQ(cpu,i) (&(CPU_INFO(cpu)->extraq[i]))
keir@21468 126 #define IDLETASK(cpu) (idle_vcpu[cpu])
sd386@3611 127
kaf24@5184 128 #define PERIOD_BEGIN(inf) ((inf)->deadl_abs - (inf)->period)
sd386@3487 129
sd386@4080 130 #define DIV_UP(x,y) (((x) + (y) - 1) / y)
sd386@4080 131
kaf24@9629 132 #define extra_runs(inf) ((inf->status) & 6)
sd386@4767 133 #define extra_get_cur_q(inf) (((inf->status & 6) >> 1)-1)
kaf24@9629 134 #define sedf_runnable(edom) (!(EDOM_INFO(edom)->status & SEDF_ASLEEP))
sd386@4767 135
sd386@4767 136
keir@21327 137 static void sedf_dump_cpu_state(const struct scheduler *ops, int i);
sd386@4080 138
kaf24@9629 139 static inline int extraq_on(struct vcpu *d, int i)
kaf24@9629 140 {
kaf24@5184 141 return ((EXTRALIST(d,i)->next != NULL) &&
kaf24@5184 142 (EXTRALIST(d,i)->next != EXTRALIST(d,i)));
sd386@4080 143 }
sd386@4080 144
kaf24@5327 145 static inline void extraq_add_head(struct vcpu *d, int i)
sd386@3611 146 {
sd386@4080 147 list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
sd386@4767 148 ASSERT(extraq_on(d, i));
sd386@3611 149 }
sd386@3611 150
kaf24@5327 151 static inline void extraq_add_tail(struct vcpu *d, int i)
sd386@3487 152 {
sd386@4080 153 list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
sd386@4767 154 ASSERT(extraq_on(d, i));
sd386@3611 155 }
sd386@3611 156
kaf24@5327 157 static inline void extraq_del(struct vcpu *d, int i)
sd386@3611 158 {
kaf24@5184 159 struct list_head *list = EXTRALIST(d,i);
kaf24@5184 160 ASSERT(extraq_on(d,i));
kaf24@9629 161 PRINT(3, "Removing domain %i.%i from L%i extraq\n",
shand@11173 162 d->domain->domain_id, d->vcpu_id, i);
kaf24@5184 163 list_del(list);
kaf24@5184 164 list->next = NULL;
kaf24@5184 165 ASSERT(!extraq_on(d, i));
sd386@3611 166 }
sd386@3611 167
sd386@4451 168 /* adds a domain to the queue of processes which are aware of extra time. List
sd386@4451 169 is sorted by score, where a lower score means higher priority for an extra
sd386@4451 170 slice. It also updates the score, by simply subtracting a fixed value from
sd386@4451 171 each entry, in order to avoid overflow. The algorithm works by simply
sd386@4451 172 charging each domain that recieved extratime with an inverse of its weight.
sd386@3888 173 */
kaf24@9629 174 static inline void extraq_add_sort_update(struct vcpu *d, int i, int sub)
kaf24@9629 175 {
kaf24@5184 176 struct list_head *cur;
kaf24@5327 177 struct sedf_vcpu_info *curinf;
kaf24@5184 178
kaf24@5184 179 ASSERT(!extraq_on(d,i));
kaf24@9629 180
kaf24@5184 181 PRINT(3, "Adding domain %i.%i (score= %i, short_pen= %"PRIi64")"
kaf24@5184 182 " to L%i extraq\n",
kaf24@5184 183 d->domain->domain_id, d->vcpu_id, EDOM_INFO(d)->score[i],
shand@11173 184 EDOM_INFO(d)->short_block_lost_tot, i);
kaf24@9629 185
kaf24@9629 186 /*
kaf24@9629 187 * Iterate through all elements to find our "hole" and on our way
kaf24@9629 188 * update all the other scores.
kaf24@9629 189 */
kaf24@9629 190 list_for_each ( cur, EXTRAQ(d->processor, i) )
kaf24@9629 191 {
kaf24@5327 192 curinf = list_entry(cur,struct sedf_vcpu_info,extralist[i]);
kaf24@5184 193 curinf->score[i] -= sub;
kaf24@9629 194 if ( EDOM_INFO(d)->score[i] < curinf->score[i] )
kaf24@5184 195 break;
kaf24@9629 196 PRINT(4,"\tbehind domain %i.%i (score= %i)\n",
kaf24@9629 197 curinf->vcpu->domain->domain_id,
kaf24@9629 198 curinf->vcpu->vcpu_id, curinf->score[i]);
kaf24@5184 199 }
kaf24@9629 200
kaf24@9629 201 /* cur now contains the element, before which we'll enqueue. */
kaf24@5184 202 PRINT(3, "\tlist_add to %p\n", cur->prev);
kaf24@5184 203 list_add(EXTRALIST(d,i),cur->prev);
kaf24@5184 204
kaf24@9629 205 /* Continue updating the extraq. */
kaf24@9629 206 if ( (cur != EXTRAQ(d->processor,i)) && sub )
kaf24@9629 207 {
kaf24@9629 208 for ( cur = cur->next; cur != EXTRAQ(d->processor,i); cur = cur->next )
kaf24@9629 209 {
kaf24@9629 210 curinf = list_entry(cur,struct sedf_vcpu_info, extralist[i]);
kaf24@5184 211 curinf->score[i] -= sub;
kaf24@5184 212 PRINT(4, "\tupdating domain %i.%i (score= %u)\n",
kaf24@5327 213 curinf->vcpu->domain->domain_id,
kaf24@5327 214 curinf->vcpu->vcpu_id, curinf->score[i]);
kaf24@5184 215 }
kaf24@9629 216 }
kaf24@9629 217
kaf24@5184 218 ASSERT(extraq_on(d,i));
sd386@3888 219 }
kaf24@9629 220 static inline void extraq_check(struct vcpu *d)
kaf24@9629 221 {
kaf24@9629 222 if ( extraq_on(d, EXTRA_UTIL_Q) )
kaf24@9629 223 {
kaf24@9629 224 PRINT(2,"Dom %i.%i is on L1 extraQ\n",
kaf24@9629 225 d->domain->domain_id, d->vcpu_id);
kaf24@9629 226
kaf24@9629 227 if ( !(EDOM_INFO(d)->status & EXTRA_AWARE) &&
kaf24@9629 228 !extra_runs(EDOM_INFO(d)) )
kaf24@9629 229 {
kaf24@5184 230 extraq_del(d, EXTRA_UTIL_Q);
kaf24@5184 231 PRINT(2,"Removed dom %i.%i from L1 extraQ\n",
kaf24@5184 232 d->domain->domain_id, d->vcpu_id);
kaf24@5184 233 }
kaf24@9629 234 }
kaf24@9629 235 else
kaf24@9629 236 {
kaf24@9629 237 PRINT(2, "Dom %i.%i is NOT on L1 extraQ\n",
kaf24@9629 238 d->domain->domain_id,
kaf24@5184 239 d->vcpu_id);
kaf24@9629 240
kaf24@9629 241 if ( (EDOM_INFO(d)->status & EXTRA_AWARE) && sedf_runnable(d) )
kaf24@5184 242 {
kaf24@5184 243 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
kaf24@9629 244 PRINT(2,"Added dom %i.%i to L1 extraQ\n",
kaf24@9629 245 d->domain->domain_id, d->vcpu_id);
kaf24@5184 246 }
kaf24@5184 247 }
sd386@3611 248 }
sd386@4767 249
kaf24@9629 250 static inline void extraq_check_add_unblocked(struct vcpu *d, int priority)
kaf24@9629 251 {
kaf24@5327 252 struct sedf_vcpu_info *inf = EDOM_INFO(d);
kaf24@9629 253
kaf24@9629 254 if ( inf->status & EXTRA_AWARE )
kaf24@9629 255 /* Put on the weighted extraq without updating any scores. */
kaf24@9629 256 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
sd386@4767 257 }
sd386@4767 258
kaf24@9629 259 static inline int __task_on_queue(struct vcpu *d)
kaf24@9629 260 {
kaf24@5184 261 return (((LIST(d))->next != NULL) && (LIST(d)->next != LIST(d)));
sd386@4767 262 }
kaf24@9629 263
kaf24@5327 264 static inline void __del_from_queue(struct vcpu *d)
sd386@3487 265 {
sd386@3487 266 struct list_head *list = LIST(d);
sd386@4767 267 ASSERT(__task_on_queue(d));
kaf24@4847 268 PRINT(3,"Removing domain %i.%i (bop= %"PRIu64") from runq/waitq\n",
kaf24@4915 269 d->domain->domain_id, d->vcpu_id, PERIOD_BEGIN(EDOM_INFO(d)));
sd386@3487 270 list_del(list);
sd386@3487 271 list->next = NULL;
sd386@4767 272 ASSERT(!__task_on_queue(d));
sd386@3487 273 }
sd386@3487 274
sd386@4767 275 typedef int(*list_comparer)(struct list_head* el1, struct list_head* el2);
sd386@4767 276
kaf24@9629 277 static inline void list_insert_sort(
kaf24@9629 278 struct list_head *list, struct list_head *element, list_comparer comp)
kaf24@9629 279 {
kaf24@5184 280 struct list_head *cur;
kaf24@9629 281
kaf24@9629 282 /* Iterate through all elements to find our "hole". */
kaf24@9629 283 list_for_each( cur, list )
kaf24@9629 284 if ( comp(element, cur) < 0 )
kaf24@5184 285 break;
kaf24@9629 286
kaf24@9629 287 /* cur now contains the element, before which we'll enqueue. */
kaf24@5184 288 PRINT(3,"\tlist_add to %p\n",cur->prev);
kaf24@5184 289 list_add(element, cur->prev);
kaf24@9629 290 }
kaf24@9629 291
keir@18096 292 #define DOMAIN_COMPARER(name, field, comp1, comp2) \
keir@18096 293 static int name##_comp(struct list_head* el1, struct list_head* el2) \
keir@18096 294 { \
keir@18096 295 struct sedf_vcpu_info *d1, *d2; \
keir@18096 296 d1 = list_entry(el1,struct sedf_vcpu_info, field); \
keir@18096 297 d2 = list_entry(el2,struct sedf_vcpu_info, field); \
keir@18096 298 if ( (comp1) == (comp2) ) \
keir@18096 299 return 0; \
keir@18096 300 if ( (comp1) < (comp2) ) \
keir@18096 301 return -1; \
keir@18096 302 else \
keir@18096 303 return 1; \
sd386@4767 304 }
kaf24@9629 305
sd386@4451 306 /* adds a domain to the queue of processes which wait for the beginning of the
sd386@4451 307 next period; this list is therefore sortet by this time, which is simply
sd386@4451 308 absol. deadline - period
sd386@3487 309 */
kaf24@9629 310 DOMAIN_COMPARER(waitq, list, PERIOD_BEGIN(d1), PERIOD_BEGIN(d2));
kaf24@9629 311 static inline void __add_to_waitqueue_sort(struct vcpu *v)
kaf24@9629 312 {
kaf24@9629 313 ASSERT(!__task_on_queue(v));
kaf24@5184 314 PRINT(3,"Adding domain %i.%i (bop= %"PRIu64") to waitq\n",
kaf24@9629 315 v->domain->domain_id, v->vcpu_id, PERIOD_BEGIN(EDOM_INFO(v)));
kaf24@9629 316 list_insert_sort(WAITQ(v->processor), LIST(v), waitq_comp);
kaf24@9629 317 ASSERT(__task_on_queue(v));
sd386@3487 318 }
sd386@3487 319
sd386@4451 320 /* adds a domain to the queue of processes which have started their current
sd386@4451 321 period and are runnable (i.e. not blocked, dieing,...). The first element
sd386@4451 322 on this list is running on the processor, if the list is empty the idle
sd386@4451 323 task will run. As we are implementing EDF, this list is sorted by deadlines.
sd386@3487 324 */
kaf24@9629 325 DOMAIN_COMPARER(runq, list, d1->deadl_abs, d2->deadl_abs);
kaf24@9629 326 static inline void __add_to_runqueue_sort(struct vcpu *v)
kaf24@9629 327 {
kaf24@5184 328 PRINT(3,"Adding domain %i.%i (deadl= %"PRIu64") to runq\n",
kaf24@9629 329 v->domain->domain_id, v->vcpu_id, EDOM_INFO(v)->deadl_abs);
kaf24@9629 330 list_insert_sort(RUNQ(v->processor), LIST(v), runq_comp);
sd386@3487 331 }
sd386@3487 332
kaf24@8541 333
keir@21327 334 static void *sedf_alloc_vdata(const struct scheduler *ops, struct vcpu *v, void *dd)
kaf24@8541 335 {
kaf24@10281 336 struct sedf_vcpu_info *inf;
kaf24@8541 337
keir@21258 338 inf = xmalloc(struct sedf_vcpu_info);
keir@21258 339 if ( inf == NULL )
keir@21258 340 return NULL;
kaf24@8541 341
keir@21258 342 memset(inf, 0, sizeof(struct sedf_vcpu_info));
kaf24@9629 343 inf->vcpu = v;
keir@21258 344
kaf24@10476 345 /* Every VCPU gets an equal share of extratime by default. */
kaf24@10476 346 inf->deadl_abs = 0;
kaf24@10476 347 inf->latency = 0;
kaf24@10476 348 inf->status = EXTRA_AWARE | SEDF_ASLEEP;
kaf24@10476 349 inf->extraweight = 1;
kaf24@10476 350
kaf24@9629 351 if ( v->domain->domain_id == 0 )
kaf24@8541 352 {
kaf24@10476 353 /* Domain0 gets 75% guaranteed (15ms every 20ms). */
kaf24@5184 354 inf->period = MILLISECS(20);
kaf24@5184 355 inf->slice = MILLISECS(15);
kaf24@8541 356 }
kaf24@8541 357 else
kaf24@8541 358 {
kaf24@10476 359 /* Best-effort extratime only. */
kaf24@5184 360 inf->period = WEIGHT_PERIOD;
kaf24@5184 361 inf->slice = 0;
kaf24@5184 362 }
kaf24@8541 363
kaf24@5184 364 inf->period_orig = inf->period; inf->slice_orig = inf->slice;
kaf24@5184 365 INIT_LIST_HEAD(&(inf->list));
kaf24@5184 366 INIT_LIST_HEAD(&(inf->extralist[EXTRA_PEN_Q]));
kaf24@5184 367 INIT_LIST_HEAD(&(inf->extralist[EXTRA_UTIL_Q]));
kaf24@5184 368
kaf24@9629 369 if ( !is_idle_vcpu(v) )
kaf24@8541 370 {
kaf24@9629 371 extraq_check(v);
kaf24@8541 372 }
kaf24@8541 373 else
kaf24@8541 374 {
keir@21258 375 inf->deadl_abs = 0;
keir@21258 376 inf->status &= ~SEDF_ASLEEP;
kaf24@5184 377 }
kaf24@10281 378
keir@21258 379 return inf;
keir@21258 380 }
keir@21258 381
keir@21258 382 static void *
keir@21327 383 sedf_alloc_pdata(const struct scheduler *ops, int cpu)
keir@21258 384 {
keir@21258 385 struct sedf_cpu_info *spc;
keir@21258 386
keir@21258 387 spc = xmalloc(struct sedf_cpu_info);
keir@21258 388 BUG_ON(spc == NULL);
keir@21258 389 memset(spc, 0, sizeof(*spc));
keir@21258 390 INIT_LIST_HEAD(&spc->waitq);
keir@21258 391 INIT_LIST_HEAD(&spc->runnableq);
keir@21258 392 INIT_LIST_HEAD(&spc->extraq[EXTRA_PEN_Q]);
keir@21258 393 INIT_LIST_HEAD(&spc->extraq[EXTRA_UTIL_Q]);
keir@21258 394
keir@21258 395 return (void *)spc;
keir@21258 396 }
keir@21258 397
keir@21258 398 static void
keir@21327 399 sedf_free_pdata(const struct scheduler *ops, void *spc, int cpu)
keir@21258 400 {
keir@21258 401 if ( spc == NULL )
keir@21258 402 return;
keir@21258 403
keir@21258 404 xfree(spc);
keir@21258 405 }
keir@21258 406
keir@21327 407 static void sedf_free_vdata(const struct scheduler *ops, void *priv)
keir@21258 408 {
keir@21258 409 xfree(priv);
keir@21258 410 }
keir@21258 411
keir@21258 412 static void *
keir@21327 413 sedf_alloc_domdata(const struct scheduler *ops, struct domain *d)
keir@21258 414 {
keir@21258 415 void *mem;
keir@21258 416
keir@21258 417 mem = xmalloc(struct sedf_dom_info);
keir@21258 418 if ( mem == NULL )
keir@21258 419 return NULL;
keir@21258 420
keir@21258 421 memset(mem, 0, sizeof(struct sedf_dom_info));
keir@21258 422
keir@21258 423 return mem;
keir@21258 424 }
keir@21258 425
keir@21327 426 static int sedf_init_domain(const struct scheduler *ops, struct domain *d)
keir@21258 427 {
keir@21258 428 d->sched_priv = sedf_alloc_domdata(ops, d);
keir@21258 429 if ( d->sched_priv == NULL )
keir@21258 430 return -ENOMEM;
keir@21258 431
kaf24@10281 432 return 0;
sd386@3487 433 }
sd386@3487 434
keir@21327 435 static void sedf_free_domdata(const struct scheduler *ops, void *data)
kfraser@12284 436 {
keir@21258 437 xfree(data);
kfraser@12284 438 }
kfraser@12284 439
keir@21327 440 static void sedf_destroy_domain(const struct scheduler *ops, struct domain *d)
kfraser@12284 441 {
keir@21258 442 sedf_free_domdata(ops, d->sched_priv);
kfraser@12284 443 }
kfraser@12284 444
keir@21327 445 static int sedf_pick_cpu(const struct scheduler *ops, struct vcpu *v)
ack@12291 446 {
ack@12291 447 cpumask_t online_affinity;
keir@21258 448 cpumask_t *online;
ack@12291 449
keir@21258 450 online = SEDF_CPUONLINE(v->domain->cpupool);
keir@21258 451 cpus_and(online_affinity, v->cpu_affinity, *online);
ack@12291 452 return first_cpu(online_affinity);
ack@12291 453 }
ack@12291 454
kaf24@8541 455 /*
kaf24@8541 456 * Handles the rescheduling & bookkeeping of domains running in their
kaf24@8541 457 * guaranteed timeslice.
kaf24@8541 458 */
kaf24@8541 459 static void desched_edf_dom(s_time_t now, struct vcpu* d)
kaf24@8541 460 {
kaf24@5327 461 struct sedf_vcpu_info* inf = EDOM_INFO(d);
kaf24@9629 462
kaf24@9629 463 /* Current domain is running in real time mode. */
kaf24@5184 464 ASSERT(__task_on_queue(d));
kaf24@9629 465
kaf24@9629 466 /* Update the domain's cputime. */
kaf24@5184 467 inf->cputime += now - inf->sched_start_abs;
sd386@4451 468
kaf24@9629 469 /*
kaf24@9629 470 * Scheduling decisions which don't remove the running domain from the
kaf24@9629 471 * runq.
kaf24@9629 472 */
kaf24@8541 473 if ( (inf->cputime < inf->slice) && sedf_runnable(d) )
kaf24@5184 474 return;
kaf24@5184 475
kaf24@5184 476 __del_from_queue(d);
kaf24@5184 477
kaf24@9629 478 /*
kaf24@9629 479 * Manage bookkeeping (i.e. calculate next deadline, memorise
kaf24@9629 480 * overrun-time of slice) of finished domains.
kaf24@9629 481 */
kaf24@8541 482 if ( inf->cputime >= inf->slice )
kaf24@8541 483 {
kaf24@5184 484 inf->cputime -= inf->slice;
kaf24@5184 485
kaf24@8541 486 if ( inf->period < inf->period_orig )
kaf24@8541 487 {
kaf24@9629 488 /* This domain runs in latency scaling or burst mode. */
kaf24@9629 489 inf->period *= 2;
kaf24@9629 490 inf->slice *= 2;
kaf24@9629 491 if ( (inf->period > inf->period_orig) ||
kaf24@9629 492 (inf->slice > inf->slice_orig) )
kaf24@5184 493 {
kaf24@9629 494 /* Reset slice and period. */
kaf24@9629 495 inf->period = inf->period_orig;
kaf24@9629 496 inf->slice = inf->slice_orig;
kaf24@5184 497 }
kaf24@5184 498 }
kaf24@9629 499
kaf24@9629 500 /* Set next deadline. */
kaf24@5184 501 inf->deadl_abs += inf->period;
kaf24@5184 502 }
kaf24@5184 503
kaf24@9629 504 /* Add a runnable domain to the waitqueue. */
kaf24@8541 505 if ( sedf_runnable(d) )
kaf24@8541 506 {
kaf24@5184 507 __add_to_waitqueue_sort(d);
kaf24@8541 508 }
kaf24@8541 509 else
kaf24@8541 510 {
kaf24@9629 511 /* We have a blocked realtime task -> remove it from exqs too. */
kaf24@8541 512 if ( extraq_on(d, EXTRA_PEN_Q) )
kaf24@8541 513 extraq_del(d, EXTRA_PEN_Q);
kaf24@8541 514 if ( extraq_on(d, EXTRA_UTIL_Q) )
kaf24@8541 515 extraq_del(d, EXTRA_UTIL_Q);
kaf24@5184 516 }
kaf24@8541 517
kaf24@5184 518 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
kaf24@5184 519 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
kaf24@5184 520 sedf_runnable(d)));
sd386@4080 521 }
sd386@4080 522
kaf24@8541 523
sd386@4080 524 /* Update all elements on the queues */
kaf24@8541 525 static void update_queues(
kaf24@8541 526 s_time_t now, struct list_head *runq, struct list_head *waitq)
kaf24@8541 527 {
kaf24@8541 528 struct list_head *cur, *tmp;
kaf24@5327 529 struct sedf_vcpu_info *curinf;
kaf24@5184 530
kaf24@5184 531 PRINT(3,"Updating waitq..\n");
kaf24@8541 532
kaf24@9629 533 /*
kaf24@9629 534 * Check for the first elements of the waitqueue, whether their
kaf24@9629 535 * next period has already started.
kaf24@9629 536 */
kaf24@9629 537 list_for_each_safe ( cur, tmp, waitq )
kaf24@9629 538 {
kaf24@5327 539 curinf = list_entry(cur, struct sedf_vcpu_info, list);
kaf24@5184 540 PRINT(4,"\tLooking @ dom %i.%i\n",
kaf24@5327 541 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
kaf24@9629 542 if ( PERIOD_BEGIN(curinf) > now )
kaf24@5184 543 break;
kaf24@9629 544 __del_from_queue(curinf->vcpu);
kaf24@9629 545 __add_to_runqueue_sort(curinf->vcpu);
kaf24@5184 546 }
kaf24@5184 547
kaf24@5184 548 PRINT(3,"Updating runq..\n");
kaf24@8541 549
kaf24@9629 550 /* Process the runq, find domains that are on the runq that shouldn't. */
kaf24@9629 551 list_for_each_safe ( cur, tmp, runq )
kaf24@9629 552 {
kaf24@5327 553 curinf = list_entry(cur,struct sedf_vcpu_info,list);
kaf24@5184 554 PRINT(4,"\tLooking @ dom %i.%i\n",
kaf24@5327 555 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
kaf24@8541 556
kaf24@8541 557 if ( unlikely(curinf->slice == 0) )
kaf24@8541 558 {
kaf24@9629 559 /* Ignore domains with empty slice. */
kaf24@5184 560 PRINT(4,"\tUpdating zero-slice domain %i.%i\n",
kaf24@5327 561 curinf->vcpu->domain->domain_id,
kaf24@5327 562 curinf->vcpu->vcpu_id);
kaf24@5327 563 __del_from_queue(curinf->vcpu);
jrb44@7200 564
kaf24@9629 565 /* Move them to their next period. */
kaf24@5184 566 curinf->deadl_abs += curinf->period;
kaf24@9629 567
kaf24@9629 568 /* Ensure that the start of the next period is in the future. */
kaf24@8541 569 if ( unlikely(PERIOD_BEGIN(curinf) < now) )
jrb44@7200 570 curinf->deadl_abs +=
jrb44@7200 571 (DIV_UP(now - PERIOD_BEGIN(curinf),
kaf24@9629 572 curinf->period)) * curinf->period;
kaf24@8541 573
kaf24@9629 574 /* Put them back into the queue. */
kaf24@9629 575 __add_to_waitqueue_sort(curinf->vcpu);
kaf24@9629 576 }
kaf24@9629 577 else if ( unlikely((curinf->deadl_abs < now) ||
kaf24@9629 578 (curinf->cputime > curinf->slice)) )
kaf24@8541 579 {
kaf24@9629 580 /*
kaf24@9629 581 * We missed the deadline or the slice was already finished.
kaf24@9629 582 * Might hapen because of dom_adj.
kaf24@9629 583 */
kaf24@5184 584 PRINT(4,"\tDomain %i.%i exceeded it's deadline/"
kaf24@5184 585 "slice (%"PRIu64" / %"PRIu64") now: %"PRIu64
kaf24@5184 586 " cputime: %"PRIu64"\n",
kaf24@5327 587 curinf->vcpu->domain->domain_id,
kaf24@5327 588 curinf->vcpu->vcpu_id,
kaf24@5184 589 curinf->deadl_abs, curinf->slice, now,
kaf24@5184 590 curinf->cputime);
kaf24@5327 591 __del_from_queue(curinf->vcpu);
kaf24@9629 592
kaf24@9629 593 /* Common case: we miss one period. */
kaf24@5184 594 curinf->deadl_abs += curinf->period;
kaf24@5184 595
kaf24@9629 596 /*
kaf24@9629 597 * If we are still behind: modulo arithmetic, force deadline
kaf24@9629 598 * to be in future and aligned to period borders.
kaf24@9629 599 */
kaf24@9629 600 if ( unlikely(curinf->deadl_abs < now) )
kaf24@5184 601 curinf->deadl_abs +=
kaf24@5184 602 DIV_UP(now - curinf->deadl_abs,
kaf24@5184 603 curinf->period) * curinf->period;
kaf24@9257 604 ASSERT(curinf->deadl_abs >= now);
kaf24@9629 605
kaf24@9629 606 /* Give a fresh slice. */
kaf24@5184 607 curinf->cputime = 0;
kaf24@9629 608 if ( PERIOD_BEGIN(curinf) > now )
kaf24@5327 609 __add_to_waitqueue_sort(curinf->vcpu);
kaf24@5184 610 else
kaf24@5327 611 __add_to_runqueue_sort(curinf->vcpu);
kaf24@5184 612 }
kaf24@5184 613 else
kaf24@5184 614 break;
kaf24@5184 615 }
kaf24@9629 616
kaf24@5184 617 PRINT(3,"done updating the queues\n");
sd386@4080 618 }
sd386@4080 619
kaf24@8541 620
sd386@4451 621 /* removes a domain from the head of the according extraQ and
sd386@4451 622 requeues it at a specified position:
sd386@4451 623 round-robin extratime: end of extraQ
sd386@4451 624 weighted ext.: insert in sorted list by score
sd386@4451 625 if the domain is blocked / has regained its short-block-loss
sd386@4451 626 time it is not put on any queue */
kaf24@9629 627 static void desched_extra_dom(s_time_t now, struct vcpu *d)
kaf24@8541 628 {
kaf24@5327 629 struct sedf_vcpu_info *inf = EDOM_INFO(d);
kaf24@8541 630 int i = extra_get_cur_q(inf);
kaf24@9629 631 unsigned long oldscore;
kaf24@9629 632
kaf24@5184 633 ASSERT(extraq_on(d, i));
kaf24@9629 634
kaf24@9629 635 /* Unset all running flags. */
kaf24@5184 636 inf->status &= ~(EXTRA_RUN_PEN | EXTRA_RUN_UTIL);
kaf24@9629 637 /* Fresh slice for the next run. */
kaf24@5184 638 inf->cputime = 0;
kaf24@9629 639 /* Accumulate total extratime. */
kaf24@5184 640 inf->extra_time_tot += now - inf->sched_start_abs;
kaf24@9629 641 /* Remove extradomain from head of the queue. */
kaf24@5184 642 extraq_del(d, i);
sd386@4080 643
kaf24@9629 644 /* Update the score. */
kaf24@8541 645 oldscore = inf->score[i];
kaf24@8541 646 if ( i == EXTRA_PEN_Q )
kaf24@8541 647 {
kaf24@5184 648 /*domain was running in L0 extraq*/
kaf24@5184 649 /*reduce block lost, probably more sophistication here!*/
kaf24@5184 650 /*inf->short_block_lost_tot -= EXTRA_QUANTUM;*/
kaf24@5184 651 inf->short_block_lost_tot -= now - inf->sched_start_abs;
kaf24@5184 652 PRINT(3,"Domain %i.%i: Short_block_loss: %"PRIi64"\n",
kaf24@5327 653 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id,
kaf24@5184 654 inf->short_block_lost_tot);
kaf24@10476 655 #if 0
kaf24@10476 656 /*
kaf24@10476 657 * KAF: If we don't exit short-blocking state at this point
kaf24@10476 658 * domain0 can steal all CPU for up to 10 seconds before
kaf24@10476 659 * scheduling settles down (when competing against another
kaf24@10476 660 * CPU-bound domain). Doing this seems to make things behave
kaf24@10476 661 * nicely. Noone gets starved by default.
kaf24@10476 662 */
kaf24@9629 663 if ( inf->short_block_lost_tot <= 0 )
kaf24@10476 664 #endif
kaf24@9629 665 {
kaf24@5184 666 PRINT(4,"Domain %i.%i compensated short block loss!\n",
kaf24@5327 667 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id);
kaf24@5184 668 /*we have (over-)compensated our block penalty*/
kaf24@5184 669 inf->short_block_lost_tot = 0;
kaf24@5184 670 /*we don't want a place on the penalty queue anymore!*/
kaf24@5184 671 inf->status &= ~EXTRA_WANT_PEN_Q;
kaf24@5184 672 goto check_extra_queues;
kaf24@5184 673 }
kaf24@9629 674
kaf24@5184 675 /*we have to go again for another try in the block-extraq,
kaf24@5184 676 the score is not used incremantally here, as this is
kaf24@5184 677 already done by recalculating the block_lost*/
kaf24@5184 678 inf->score[EXTRA_PEN_Q] = (inf->period << 10) /
kaf24@5184 679 inf->short_block_lost_tot;
kaf24@5184 680 oldscore = 0;
kaf24@8541 681 }
kaf24@8541 682 else
kaf24@5184 683 {
kaf24@5184 684 /*domain was running in L1 extraq => score is inverse of
kaf24@5184 685 utilization and is used somewhat incremental!*/
kaf24@8541 686 if ( !inf->extraweight )
kaf24@5184 687 /*NB: use fixed point arithmetic with 10 bits*/
kaf24@5184 688 inf->score[EXTRA_UTIL_Q] = (inf->period << 10) /
kaf24@5184 689 inf->slice;
kaf24@5184 690 else
sd386@5863 691 /*conversion between realtime utilisation and extrawieght:
sd386@5863 692 full (ie 100%) utilization is equivalent to 128 extraweight*/
kaf24@5184 693 inf->score[EXTRA_UTIL_Q] = (1<<17) / inf->extraweight;
kaf24@5184 694 }
kaf24@8541 695
kaf24@5184 696 check_extra_queues:
kaf24@5184 697 /* Adding a runnable domain to the right queue and removing blocked ones*/
kaf24@8541 698 if ( sedf_runnable(d) )
kaf24@8541 699 {
kaf24@5184 700 /*add according to score: weighted round robin*/
sd386@5863 701 if (((inf->status & EXTRA_AWARE) && (i == EXTRA_UTIL_Q)) ||
sd386@5863 702 ((inf->status & EXTRA_WANT_PEN_Q) && (i == EXTRA_PEN_Q)))
kaf24@5184 703 extraq_add_sort_update(d, i, oldscore);
kaf24@5184 704 }
kaf24@8541 705 else
kaf24@8541 706 {
kaf24@5184 707 /*remove this blocked domain from the waitq!*/
kaf24@5184 708 __del_from_queue(d);
kaf24@5184 709 /*make sure that we remove a blocked domain from the other
kaf24@5184 710 extraq too*/
kaf24@8541 711 if ( i == EXTRA_PEN_Q )
kaf24@8541 712 {
kaf24@8541 713 if ( extraq_on(d, EXTRA_UTIL_Q) )
kaf24@8541 714 extraq_del(d, EXTRA_UTIL_Q);
kaf24@8541 715 }
kaf24@8541 716 else
kaf24@8541 717 {
kaf24@8541 718 if ( extraq_on(d, EXTRA_PEN_Q) )
kaf24@8541 719 extraq_del(d, EXTRA_PEN_Q);
kaf24@5184 720 }
kaf24@5184 721 }
kaf24@9629 722
kaf24@5184 723 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
kaf24@5184 724 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
kaf24@5184 725 sedf_runnable(d)));
sd386@4080 726 }
sd386@4080 727
kaf24@8541 728
kaf24@8541 729 static struct task_slice sedf_do_extra_schedule(
kaf24@8541 730 s_time_t now, s_time_t end_xt, struct list_head *extraq[], int cpu)
kaf24@8541 731 {
kaf24@5184 732 struct task_slice ret;
kaf24@5327 733 struct sedf_vcpu_info *runinf;
jrb44@7200 734 ASSERT(end_xt > now);
kaf24@8541 735
kaf24@5184 736 /* Enough time left to use for extratime? */
kaf24@8541 737 if ( end_xt - now < EXTRA_QUANTUM )
kaf24@5184 738 goto return_idle;
kaf24@8541 739
kaf24@8541 740 if ( !list_empty(extraq[EXTRA_PEN_Q]) )
kaf24@8541 741 {
kaf24@5184 742 /*we still have elements on the level 0 extraq
kaf24@5184 743 => let those run first!*/
kaf24@5184 744 runinf = list_entry(extraq[EXTRA_PEN_Q]->next,
kaf24@5327 745 struct sedf_vcpu_info, extralist[EXTRA_PEN_Q]);
kaf24@5184 746 runinf->status |= EXTRA_RUN_PEN;
kaf24@5327 747 ret.task = runinf->vcpu;
kaf24@5184 748 ret.time = EXTRA_QUANTUM;
sd386@4410 749 #ifdef SEDF_STATS
kaf24@5184 750 runinf->pen_extra_slices++;
sd386@4410 751 #endif
kaf24@8541 752 }
kaf24@8541 753 else
kaf24@8541 754 {
kaf24@8541 755 if ( !list_empty(extraq[EXTRA_UTIL_Q]) )
kaf24@8541 756 {
kaf24@5184 757 /*use elements from the normal extraqueue*/
kaf24@5184 758 runinf = list_entry(extraq[EXTRA_UTIL_Q]->next,
sd386@5863 759 struct sedf_vcpu_info,
sd386@5863 760 extralist[EXTRA_UTIL_Q]);
kaf24@5184 761 runinf->status |= EXTRA_RUN_UTIL;
kaf24@5327 762 ret.task = runinf->vcpu;
kaf24@5184 763 ret.time = EXTRA_QUANTUM;
kaf24@5184 764 }
kaf24@5184 765 else
kaf24@5184 766 goto return_idle;
kaf24@8541 767 }
sd386@4080 768
kaf24@5184 769 ASSERT(ret.time > 0);
kaf24@5184 770 ASSERT(sedf_runnable(ret.task));
kaf24@5184 771 return ret;
kaf24@5184 772
kaf24@5184 773 return_idle:
kaf24@5184 774 ret.task = IDLETASK(cpu);
kaf24@5184 775 ret.time = end_xt - now;
kaf24@5184 776 ASSERT(ret.time > 0);
kaf24@5184 777 ASSERT(sedf_runnable(ret.task));
kaf24@5184 778 return ret;
sd386@4080 779 }
kaf24@8541 780
kaf24@8541 781
sd386@4080 782 /* Main scheduling function
sd386@4451 783 Reasons for calling this function are:
sd386@4451 784 -timeslice for the current period used up
sd386@4451 785 -domain on waitqueue has started it's period
sd386@4451 786 -and various others ;) in general: determine which domain to run next*/
keir@21390 787 static struct task_slice sedf_do_schedule(
keir@21390 788 const struct scheduler *ops, s_time_t now, bool_t tasklet_work_scheduled)
sd386@4080 789 {
kaf24@8541 790 int cpu = smp_processor_id();
kaf24@5184 791 struct list_head *runq = RUNQ(cpu);
kaf24@5184 792 struct list_head *waitq = WAITQ(cpu);
kaf24@5327 793 struct sedf_vcpu_info *inf = EDOM_INFO(current);
kaf24@8011 794 struct list_head *extraq[] = {
kaf24@8011 795 EXTRAQ(cpu, EXTRA_PEN_Q), EXTRAQ(cpu, EXTRA_UTIL_Q)};
kaf24@8011 796 struct sedf_vcpu_info *runinf, *waitinf;
kaf24@8011 797 struct task_slice ret;
kaf24@8011 798
kaf24@5184 799 /*idle tasks don't need any of the following stuf*/
kaf24@8563 800 if ( is_idle_vcpu(current) )
kaf24@5184 801 goto check_waitq;
kaf24@5184 802
kaf24@5184 803 /* create local state of the status of the domain, in order to avoid
kaf24@5184 804 inconsistent state during scheduling decisions, because data for
kaf24@8547 805 vcpu_runnable is not protected by the scheduling lock!*/
kaf24@8547 806 if ( !vcpu_runnable(current) )
kaf24@5184 807 inf->status |= SEDF_ASLEEP;
kaf24@5184 808
kaf24@8541 809 if ( inf->status & SEDF_ASLEEP )
kaf24@5184 810 inf->block_abs = now;
sd386@4767 811
kaf24@8541 812 if ( unlikely(extra_runs(inf)) )
kaf24@8541 813 {
kaf24@5184 814 /*special treatment of domains running in extra time*/
kaf24@5184 815 desched_extra_dom(now, current);
kaf24@5184 816 }
kaf24@5184 817 else
kaf24@5184 818 {
kaf24@5184 819 desched_edf_dom(now, current);
kaf24@5184 820 }
kaf24@5184 821 check_waitq:
kaf24@5184 822 update_queues(now, runq, waitq);
keir@21258 823
kaf24@5184 824 /*now simply pick the first domain from the runqueue, which has the
kaf24@5184 825 earliest deadline, because the list is sorted*/
kaf24@5184 826
keir@21243 827 /* Tasklet work (which runs in idle VCPU context) overrides all else. */
keir@21390 828 if ( tasklet_work_scheduled ||
keir@21390 829 (list_empty(runq) && list_empty(waitq)) ||
keir@21390 830 unlikely(!cpu_isset(cpu, *SEDF_CPUONLINE(per_cpu(cpupool, cpu)))) )
keir@21243 831 {
keir@21243 832 ret.task = IDLETASK(cpu);
keir@21243 833 ret.time = SECONDS(1);
keir@21243 834 }
keir@21243 835 else if ( !list_empty(runq) )
kaf24@8541 836 {
kaf24@5327 837 runinf = list_entry(runq->next,struct sedf_vcpu_info,list);
kaf24@5327 838 ret.task = runinf->vcpu;
kaf24@8541 839 if ( !list_empty(waitq) )
kaf24@8541 840 {
kaf24@5184 841 waitinf = list_entry(waitq->next,
kaf24@5327 842 struct sedf_vcpu_info,list);
kaf24@5184 843 /*rerun scheduler, when scheduled domain reaches it's
kaf24@5184 844 end of slice or the first domain from the waitqueue
kaf24@5184 845 gets ready*/
kaf24@5184 846 ret.time = MIN(now + runinf->slice - runinf->cputime,
kaf24@5184 847 PERIOD_BEGIN(waitinf)) - now;
kaf24@5184 848 }
kaf24@8541 849 else
kaf24@8541 850 {
kaf24@5184 851 ret.time = runinf->slice - runinf->cputime;
kaf24@5184 852 }
kaf24@5184 853 }
keir@21243 854 else
kaf24@8541 855 {
kaf24@5327 856 waitinf = list_entry(waitq->next,struct sedf_vcpu_info, list);
kaf24@5184 857 /*we could not find any suitable domain
kaf24@5184 858 => look for domains that are aware of extratime*/
kaf24@5184 859 ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf),
kaf24@5184 860 extraq, cpu);
kaf24@5184 861 }
sd386@4080 862
kaf24@5184 863 /*TODO: Do something USEFUL when this happens and find out, why it
kaf24@5184 864 still can happen!!!*/
kaf24@8541 865 if ( ret.time < 0)
kaf24@8541 866 {
kaf24@5184 867 printk("Ouch! We are seriously BEHIND schedule! %"PRIi64"\n",
kaf24@5184 868 ret.time);
kaf24@5184 869 ret.time = EXTRA_QUANTUM;
kaf24@5184 870 }
kaf24@8541 871
keir@21671 872 ret.migrated = 0;
keir@21671 873
kaf24@5184 874 EDOM_INFO(ret.task)->sched_start_abs = now;
kaf24@5184 875 CHECK(ret.time > 0);
kaf24@5184 876 ASSERT(sedf_runnable(ret.task));
kaf24@5190 877 CPU_INFO(cpu)->current_slice_expires = now + ret.time;
kaf24@5184 878 return ret;
sd386@3487 879 }
sd386@3487 880
kaf24@8541 881
keir@21327 882 static void sedf_sleep(const struct scheduler *ops, struct vcpu *d)
kaf24@8541 883 {
kaf24@8541 884 PRINT(2,"sedf_sleep was called, domain-id %i.%i\n",
kaf24@8541 885 d->domain->domain_id, d->vcpu_id);
kaf24@5184 886
kaf24@8563 887 if ( is_idle_vcpu(d) )
kaf24@5184 888 return;
sd386@4767 889
kaf24@5184 890 EDOM_INFO(d)->status |= SEDF_ASLEEP;
kaf24@5184 891
kaf24@11017 892 if ( per_cpu(schedule_data, d->processor).curr == d )
kaf24@8541 893 {
kaf24@5184 894 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
kaf24@5184 895 }
kaf24@8541 896 else
kaf24@8541 897 {
kaf24@5184 898 if ( __task_on_queue(d) )
kaf24@5184 899 __del_from_queue(d);
kaf24@8541 900 if ( extraq_on(d, EXTRA_UTIL_Q) )
kaf24@5184 901 extraq_del(d, EXTRA_UTIL_Q);
kaf24@8541 902 if ( extraq_on(d, EXTRA_PEN_Q) )
kaf24@5184 903 extraq_del(d, EXTRA_PEN_Q);
kaf24@5184 904 }
sd386@3487 905 }
sd386@3487 906
kaf24@8541 907
sd386@4451 908 /* This function wakes up a domain, i.e. moves them into the waitqueue
sd386@3487 909 * things to mention are: admission control is taking place nowhere at
sd386@3487 910 * the moment, so we can't be sure, whether it is safe to wake the domain
sd386@3487 911 * up at all. Anyway, even if it is safe (total cpu usage <=100%) there are
sd386@3487 912 * some considerations on when to allow the domain to wake up and have it's
sd386@3487 913 * first deadline...
sd386@4451 914 * I detected 3 cases, which could describe the possible behaviour of the
sd386@4451 915 * scheduler,
sd386@3487 916 * and I'll try to make them more clear:
sd386@3487 917 *
sd386@3487 918 * 1. Very conservative
sd386@3487 919 * -when a blocked domain unblocks, it is allowed to start execution at
sd386@3487 920 * the beginning of the next complete period
sd386@3487 921 * (D..deadline, R..running, B..blocking/sleeping, U..unblocking/waking up
sd386@3487 922 *
sd386@3487 923 * DRRB_____D__U_____DRRRRR___D________ ...
sd386@3487 924 *
sd386@3487 925 * -this causes the domain to miss a period (and a deadlline)
sd386@3487 926 * -doesn't disturb the schedule at all
sd386@3487 927 * -deadlines keep occuring isochronous
sd386@3487 928 *
sd386@3611 929 * 2. Conservative Part 1: Short Unblocking
sd386@4451 930 * -when a domain unblocks in the same period as it was blocked it
sd386@4451 931 * unblocks and may consume the rest of it's original time-slice minus
sd386@4451 932 * the time it was blocked
sd386@3487 933 * (assume period=9, slice=5)
sd386@3487 934 *
sd386@3487 935 * DRB_UR___DRRRRR___D...
sd386@3487 936 *
sd386@4451 937 * -this also doesn't disturb scheduling, but might lead to the fact, that
sd386@4451 938 * the domain can't finish it's workload in the period
sd386@4451 939 * -in addition to that the domain can be treated prioritised when
sd386@4451 940 * extratime is available
jbulpin@7026 941 * -addition: experiments have shown that this may have a HUGE impact on
sd386@4451 942 * performance of other domains, becaus it can lead to excessive context
sd386@4451 943 * switches
kaf24@9629 944 *
sd386@3611 945 * Part2: Long Unblocking
sd386@3487 946 * Part 2a
sd386@4451 947 * -it is obvious that such accounting of block time, applied when
sd386@4451 948 * unblocking is happening in later periods, works fine aswell
sd386@4451 949 * -the domain is treated as if it would have been running since the start
sd386@4451 950 * of its new period
sd386@3487 951 *
sd386@3487 952 * DRB______D___UR___D...
sd386@3487 953 *
sd386@3487 954 * Part 2b
sd386@4451 955 * -if one needs the full slice in the next period, it is necessary to
sd386@4451 956 * treat the unblocking time as the start of the new period, i.e. move
sd386@4451 957 * the deadline further back (later)
sd386@4451 958 * -this doesn't disturb scheduling as well, because for EDF periods can
sd386@4451 959 * be treated as minimal inter-release times and scheduling stays
sd386@4451 960 * correct, when deadlines are kept relative to the time the process
sd386@4451 961 * unblocks
sd386@3487 962 *
sd386@4451 963 * DRB______D___URRRR___D...<prev [Thread] next>
sd386@4451 964 * (D) <- old deadline was here
sd386@3487 965 * -problem: deadlines don't occur isochronous anymore
sd386@3611 966 * Part 2c (Improved Atropos design)
sd386@4451 967 * -when a domain unblocks it is given a very short period (=latency hint)
sd386@4451 968 * and slice length scaled accordingly
sd386@3611 969 * -both rise again to the original value (e.g. get doubled every period)
sd386@3487 970 *
sd386@3487 971 * 3. Unconservative (i.e. incorrect)
sd386@4451 972 * -to boost the performance of I/O dependent domains it would be possible
sd386@4451 973 * to put the domain into the runnable queue immediately, and let it run
sd386@4451 974 * for the remainder of the slice of the current period
sd386@3611 975 * (or even worse: allocate a new full slice for the domain)
sd386@4451 976 * -either behaviour can lead to missed deadlines in other domains as
sd386@4451 977 * opposed to approaches 1,2a,2b
sd386@3487 978 */
kaf24@8541 979 static void unblock_short_extra_support(
kaf24@8541 980 struct sedf_vcpu_info* inf, s_time_t now)
kaf24@8541 981 {
kaf24@5184 982 /*this unblocking scheme tries to support the domain, by assigning it
kaf24@5184 983 a priority in extratime distribution according to the loss of time
kaf24@5184 984 in this slice due to blocking*/
kaf24@5184 985 s_time_t pen;
kaf24@5184 986
kaf24@5184 987 /*no more realtime execution in this period!*/
kaf24@5184 988 inf->deadl_abs += inf->period;
kaf24@8541 989 if ( likely(inf->block_abs) )
kaf24@8541 990 {
kaf24@5184 991 //treat blocked time as consumed by the domain*/
kaf24@5184 992 /*inf->cputime += now - inf->block_abs;*/
kaf24@5184 993 /*penalty is time the domain would have
kaf24@5184 994 had if it continued to run */
kaf24@5184 995 pen = (inf->slice - inf->cputime);
kaf24@8541 996 if ( pen < 0 )
kaf24@8541 997 pen = 0;
kaf24@5184 998 /*accumulate all penalties over the periods*/
kaf24@5184 999 /*inf->short_block_lost_tot += pen;*/
kaf24@5184 1000 /*set penalty to the current value*/
kaf24@5184 1001 inf->short_block_lost_tot = pen;
kaf24@5184 1002 /*not sure which one is better.. but seems to work well...*/
kaf24@5184 1003
kaf24@8541 1004 if ( inf->short_block_lost_tot )
kaf24@8541 1005 {
kaf24@5184 1006 inf->score[0] = (inf->period << 10) /
kaf24@5184 1007 inf->short_block_lost_tot;
sd386@4410 1008 #ifdef SEDF_STATS
kaf24@5184 1009 inf->pen_extra_blocks++;
sd386@4410 1010 #endif
kaf24@8541 1011 if ( extraq_on(inf->vcpu, EXTRA_PEN_Q) )
kaf24@5184 1012 /*remove domain for possible resorting!*/
kaf24@5327 1013 extraq_del(inf->vcpu, EXTRA_PEN_Q);
kaf24@5184 1014 else
kaf24@5184 1015 /*remember that we want to be on the penalty q
kaf24@5184 1016 so that we can continue when we (un-)block
kaf24@5184 1017 in penalty-extratime*/
kaf24@5184 1018 inf->status |= EXTRA_WANT_PEN_Q;
kaf24@5184 1019
kaf24@5184 1020 /*(re-)add domain to the penalty extraq*/
sd386@5863 1021 extraq_add_sort_update(inf->vcpu, EXTRA_PEN_Q, 0);
kaf24@5184 1022 }
kaf24@5184 1023 }
kaf24@8541 1024
kaf24@5184 1025 /*give it a fresh slice in the next period!*/
kaf24@5184 1026 inf->cputime = 0;
sd386@4080 1027 }
kaf24@8541 1028
kaf24@8541 1029
kaf24@8541 1030 static void unblock_long_cons_b(struct sedf_vcpu_info* inf,s_time_t now)
kaf24@8541 1031 {
kaf24@5184 1032 /*Conservative 2b*/
kaf24@5184 1033 /*Treat the unblocking time as a start of a new period */
kaf24@5184 1034 inf->deadl_abs = now + inf->period;
kaf24@5184 1035 inf->cputime = 0;
sd386@3611 1036 }
kaf24@8541 1037
kaf24@8541 1038
kaf24@5184 1039 #define DOMAIN_EDF 1
kaf24@5184 1040 #define DOMAIN_EXTRA_PEN 2
kaf24@5184 1041 #define DOMAIN_EXTRA_UTIL 3
kaf24@5184 1042 #define DOMAIN_IDLE 4
kaf24@8541 1043 static inline int get_run_type(struct vcpu* d)
kaf24@8541 1044 {
kaf24@5327 1045 struct sedf_vcpu_info* inf = EDOM_INFO(d);
kaf24@8563 1046 if (is_idle_vcpu(d))
kaf24@5184 1047 return DOMAIN_IDLE;
kaf24@5184 1048 if (inf->status & EXTRA_RUN_PEN)
kaf24@5184 1049 return DOMAIN_EXTRA_PEN;
kaf24@5184 1050 if (inf->status & EXTRA_RUN_UTIL)
kaf24@5184 1051 return DOMAIN_EXTRA_UTIL;
kaf24@5184 1052 return DOMAIN_EDF;
sd386@4080 1053 }
kaf24@8541 1054
kaf24@8541 1055
sd386@4451 1056 /*Compares two domains in the relation of whether the one is allowed to
sd386@4451 1057 interrupt the others execution.
sd386@4080 1058 It returns true (!=0) if a switch to the other domain is good.
sd386@4080 1059 Current Priority scheme is as follows:
kaf24@5184 1060 EDF > L0 (penalty based) extra-time >
kaf24@5184 1061 L1 (utilization) extra-time > idle-domain
sd386@4080 1062 In the same class priorities are assigned as following:
kaf24@5184 1063 EDF: early deadline > late deadline
kaf24@5184 1064 L0 extra-time: lower score > higher score*/
kaf24@8541 1065 static inline int should_switch(struct vcpu *cur,
kaf24@8541 1066 struct vcpu *other,
kaf24@8541 1067 s_time_t now)
kaf24@8541 1068 {
kaf24@5327 1069 struct sedf_vcpu_info *cur_inf, *other_inf;
kaf24@5184 1070 cur_inf = EDOM_INFO(cur);
kaf24@5184 1071 other_inf = EDOM_INFO(other);
kaf24@5184 1072
kaf24@9629 1073 /* Check whether we need to make an earlier scheduling decision. */
kaf24@9629 1074 if ( PERIOD_BEGIN(other_inf) <
kaf24@9629 1075 CPU_INFO(other->processor)->current_slice_expires )
kaf24@5184 1076 return 1;
kaf24@9629 1077
kaf24@9629 1078 /* No timing-based switches need to be taken into account here. */
kaf24@9629 1079 switch ( get_run_type(cur) )
kaf24@9629 1080 {
kaf24@5184 1081 case DOMAIN_EDF:
kaf24@9629 1082 /* Do not interrupt a running EDF domain. */
kaf24@5184 1083 return 0;
kaf24@5184 1084 case DOMAIN_EXTRA_PEN:
kaf24@9629 1085 /* Check whether we also want the L0 ex-q with lower score. */
kaf24@9629 1086 return ((other_inf->status & EXTRA_WANT_PEN_Q) &&
kaf24@9629 1087 (other_inf->score[EXTRA_PEN_Q] <
kaf24@9629 1088 cur_inf->score[EXTRA_PEN_Q]));
kaf24@5184 1089 case DOMAIN_EXTRA_UTIL:
kaf24@9629 1090 /* Check whether we want the L0 extraq. Don't
kaf24@9629 1091 * switch if both domains want L1 extraq.
kaf24@9629 1092 */
kaf24@9629 1093 return !!(other_inf->status & EXTRA_WANT_PEN_Q);
kaf24@5184 1094 case DOMAIN_IDLE:
kaf24@5184 1095 return 1;
kaf24@5184 1096 }
kaf24@9629 1097
kaf24@5184 1098 return 1;
sd386@4080 1099 }
kaf24@8541 1100
keir@21327 1101 static void sedf_wake(const struct scheduler *ops, struct vcpu *d)
kaf24@8541 1102 {
kaf24@5184 1103 s_time_t now = NOW();
kaf24@5327 1104 struct sedf_vcpu_info* inf = EDOM_INFO(d);
kaf24@7392 1105
sd386@5863 1106 PRINT(3, "sedf_wake was called, domain-id %i.%i\n",d->domain->domain_id,
sd386@5863 1107 d->vcpu_id);
kaf24@7392 1108
kaf24@8563 1109 if ( unlikely(is_idle_vcpu(d)) )
kaf24@5184 1110 return;
kaf24@5184 1111
kaf24@8541 1112 if ( unlikely(__task_on_queue(d)) )
kaf24@8541 1113 {
kaf24@5184 1114 PRINT(3,"\tdomain %i.%i is already in some queue\n",
kaf24@5184 1115 d->domain->domain_id, d->vcpu_id);
kaf24@5184 1116 return;
kaf24@5184 1117 }
kaf24@8541 1118
kaf24@5184 1119 ASSERT(!sedf_runnable(d));
kaf24@5184 1120 inf->status &= ~SEDF_ASLEEP;
kaf24@5184 1121 ASSERT(!extraq_on(d, EXTRA_UTIL_Q));
kaf24@5184 1122 ASSERT(!extraq_on(d, EXTRA_PEN_Q));
kaf24@5184 1123
kaf24@8541 1124 if ( unlikely(inf->deadl_abs == 0) )
kaf24@8541 1125 {
kaf24@5184 1126 /*initial setup of the deadline*/
kaf24@5184 1127 inf->deadl_abs = now + inf->slice;
kaf24@8541 1128 }
kaf24@5184 1129
kaf24@8541 1130 PRINT(3, "waking up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64
kaf24@8541 1131 "now= %"PRIu64")\n",
kaf24@8541 1132 d->domain->domain_id, d->vcpu_id, inf->deadl_abs, inf->period, now);
kaf24@8541 1133
kaf24@5184 1134 #ifdef SEDF_STATS
kaf24@5184 1135 inf->block_tot++;
sd386@4410 1136 #endif
kaf24@8541 1137
kaf24@8541 1138 if ( unlikely(now < PERIOD_BEGIN(inf)) )
kaf24@8541 1139 {
kaf24@7485 1140 PRINT(4,"extratime unblock\n");
kaf24@5184 1141 /* unblocking in extra-time! */
kaf24@8541 1142 if ( inf->status & EXTRA_WANT_PEN_Q )
kaf24@8541 1143 {
kaf24@5184 1144 /*we have a domain that wants compensation
kaf24@5184 1145 for block penalty and did just block in
kaf24@5184 1146 its compensation time. Give it another
kaf24@5184 1147 chance!*/
kaf24@5184 1148 extraq_add_sort_update(d, EXTRA_PEN_Q, 0);
kaf24@5184 1149 }
kaf24@5184 1150 extraq_check_add_unblocked(d, 0);
kaf24@5184 1151 }
kaf24@8541 1152 else
kaf24@8541 1153 {
kaf24@8541 1154 if ( now < inf->deadl_abs )
kaf24@8541 1155 {
kaf24@5184 1156 PRINT(4,"short unblocking\n");
kaf24@5184 1157 /*short blocking*/
sd386@4410 1158 #ifdef SEDF_STATS
kaf24@5184 1159 inf->short_block_tot++;
sd386@4410 1160 #endif
kaf24@5184 1161 unblock_short_extra_support(inf, now);
sd386@4080 1162
kaf24@5184 1163 extraq_check_add_unblocked(d, 1);
kaf24@5184 1164 }
kaf24@8541 1165 else
kaf24@8541 1166 {
kaf24@5184 1167 PRINT(4,"long unblocking\n");
kaf24@5184 1168 /*long unblocking*/
sd386@4410 1169 #ifdef SEDF_STATS
kaf24@5184 1170 inf->long_block_tot++;
sd386@4410 1171 #endif
kaf24@5184 1172 unblock_long_cons_b(inf, now);
sd386@4767 1173
kaf24@5184 1174 extraq_check_add_unblocked(d, 1);
kaf24@5184 1175 }
kaf24@5184 1176 }
kaf24@8541 1177
kaf24@8541 1178 PRINT(3, "woke up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64
kaf24@8541 1179 "now= %"PRIu64")\n",
kaf24@8541 1180 d->domain->domain_id, d->vcpu_id, inf->deadl_abs,
kaf24@5184 1181 inf->period, now);
kaf24@8541 1182
kaf24@8541 1183 if ( PERIOD_BEGIN(inf) > now )
kaf24@8541 1184 {
kaf24@5184 1185 __add_to_waitqueue_sort(d);
kaf24@5184 1186 PRINT(3,"added to waitq\n");
kaf24@5184 1187 }
kaf24@8541 1188 else
kaf24@8541 1189 {
kaf24@5184 1190 __add_to_runqueue_sort(d);
kaf24@5184 1191 PRINT(3,"added to runq\n");
kaf24@5184 1192 }
kaf24@5184 1193
sd386@4410 1194 #ifdef SEDF_STATS
kaf24@5184 1195 /*do some statistics here...*/
kaf24@8541 1196 if ( inf->block_abs != 0 )
kaf24@8541 1197 {
kaf24@5184 1198 inf->block_time_tot += now - inf->block_abs;
kaf24@5184 1199 inf->penalty_time_tot +=
kaf24@5184 1200 PERIOD_BEGIN(inf) + inf->cputime - inf->block_abs;
kaf24@5184 1201 }
sd386@4410 1202 #endif
kaf24@8541 1203
kaf24@5184 1204 /*sanity check: make sure each extra-aware domain IS on the util-q!*/
kaf24@5184 1205 ASSERT(IMPLY(inf->status & EXTRA_AWARE, extraq_on(d, EXTRA_UTIL_Q)));
kaf24@5184 1206 ASSERT(__task_on_queue(d));
kaf24@5184 1207 /*check whether the awakened task needs to invoke the do_schedule
kaf24@5184 1208 routine. Try to avoid unnecessary runs but:
kaf24@5184 1209 Save approximation: Always switch to scheduler!*/
sos22@5919 1210 ASSERT(d->processor >= 0);
sos22@5919 1211 ASSERT(d->processor < NR_CPUS);
kaf24@11017 1212 ASSERT(per_cpu(schedule_data, d->processor).curr);
kaf24@8541 1213
kaf24@11017 1214 if ( should_switch(per_cpu(schedule_data, d->processor).curr, d, now) )
kaf24@5184 1215 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
sd386@3487 1216 }
sd386@3487 1217
kaf24@8541 1218
kaf24@8541 1219 /* Print a lot of useful information about a domains in the system */
kaf24@8541 1220 static void sedf_dump_domain(struct vcpu *d)
kaf24@8541 1221 {
kaf24@5184 1222 printk("%i.%i has=%c ", d->domain->domain_id, d->vcpu_id,
kfraser@14692 1223 d->is_running ? 'T':'F');
kaf24@9008 1224 printk("p=%"PRIu64" sl=%"PRIu64" ddl=%"PRIu64" w=%hu"
kaf24@8541 1225 " sc=%i xtr(%s)=%"PRIu64" ew=%hu",
kaf24@5184 1226 EDOM_INFO(d)->period, EDOM_INFO(d)->slice, EDOM_INFO(d)->deadl_abs,
kaf24@9008 1227 EDOM_INFO(d)->weight,
kaf24@8541 1228 EDOM_INFO(d)->score[EXTRA_UTIL_Q],
kaf24@5184 1229 (EDOM_INFO(d)->status & EXTRA_AWARE) ? "yes" : "no",
kaf24@5184 1230 EDOM_INFO(d)->extra_time_tot, EDOM_INFO(d)->extraweight);
kaf24@8541 1231
sd386@4410 1232 #ifdef SEDF_STATS
kaf24@8541 1233 if ( EDOM_INFO(d)->block_time_tot != 0 )
kfraser@11908 1234 printk(" pen=%"PRIu64"%%", (EDOM_INFO(d)->penalty_time_tot * 100) /
kaf24@5184 1235 EDOM_INFO(d)->block_time_tot);
kaf24@8541 1236 if ( EDOM_INFO(d)->block_tot != 0 )
kfraser@11908 1237 printk("\n blks=%u sh=%u (%u%%) (shc=%u (%u%%) shex=%i "\
kaf24@5184 1238 "shexsl=%i) l=%u (%u%%) avg: b=%"PRIu64" p=%"PRIu64"",
kaf24@5184 1239 EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_block_tot,
kaf24@5184 1240 (EDOM_INFO(d)->short_block_tot * 100)
kaf24@5184 1241 / EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_cont,
kaf24@5184 1242 (EDOM_INFO(d)->short_cont * 100) / EDOM_INFO(d)->block_tot,
kaf24@5184 1243 EDOM_INFO(d)->pen_extra_blocks,
kaf24@5184 1244 EDOM_INFO(d)->pen_extra_slices,
kaf24@5184 1245 EDOM_INFO(d)->long_block_tot,
kaf24@5184 1246 (EDOM_INFO(d)->long_block_tot * 100) / EDOM_INFO(d)->block_tot,
kaf24@5184 1247 (EDOM_INFO(d)->block_time_tot) / EDOM_INFO(d)->block_tot,
kaf24@5184 1248 (EDOM_INFO(d)->penalty_time_tot) / EDOM_INFO(d)->block_tot);
sd386@4410 1249 #endif
kfraser@11908 1250 printk("\n");
sd386@3487 1251 }
sd386@3487 1252
kaf24@8541 1253
keir@21258 1254 /* dumps all domains on the specified cpu */
keir@21327 1255 static void sedf_dump_cpu_state(const struct scheduler *ops, int i)
sd386@3487 1256 {
kaf24@5184 1257 struct list_head *list, *queue, *tmp;
kaf24@5327 1258 struct sedf_vcpu_info *d_inf;
kaf24@5184 1259 struct domain *d;
kaf24@5327 1260 struct vcpu *ed;
kaf24@5184 1261 int loop = 0;
kaf24@5184 1262
kaf24@5184 1263 printk("now=%"PRIu64"\n",NOW());
kaf24@5184 1264 queue = RUNQ(i);
kaf24@5184 1265 printk("RUNQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
kaf24@5184 1266 (unsigned long) queue->next, (unsigned long) queue->prev);
kaf24@8541 1267 list_for_each_safe ( list, tmp, queue )
kaf24@8541 1268 {
kaf24@5184 1269 printk("%3d: ",loop++);
kaf24@5327 1270 d_inf = list_entry(list, struct sedf_vcpu_info, list);
kaf24@5327 1271 sedf_dump_domain(d_inf->vcpu);
kaf24@5184 1272 }
kaf24@5184 1273
kaf24@5184 1274 queue = WAITQ(i); loop = 0;
kaf24@5184 1275 printk("\nWAITQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
kaf24@5184 1276 (unsigned long) queue->next, (unsigned long) queue->prev);
kaf24@8541 1277 list_for_each_safe ( list, tmp, queue )
kaf24@8541 1278 {
kaf24@5184 1279 printk("%3d: ",loop++);
kaf24@5327 1280 d_inf = list_entry(list, struct sedf_vcpu_info, list);
kaf24@5327 1281 sedf_dump_domain(d_inf->vcpu);
kaf24@5184 1282 }
kaf24@5184 1283
kaf24@5184 1284 queue = EXTRAQ(i,EXTRA_PEN_Q); loop = 0;
kaf24@5184 1285 printk("\nEXTRAQ (penalty) rq %lx n: %lx, p: %lx\n",
kaf24@5184 1286 (unsigned long)queue, (unsigned long) queue->next,
kaf24@5184 1287 (unsigned long) queue->prev);
kaf24@8541 1288 list_for_each_safe ( list, tmp, queue )
kaf24@8541 1289 {
kaf24@5327 1290 d_inf = list_entry(list, struct sedf_vcpu_info,
kaf24@5184 1291 extralist[EXTRA_PEN_Q]);
kaf24@5184 1292 printk("%3d: ",loop++);
kaf24@5327 1293 sedf_dump_domain(d_inf->vcpu);
kaf24@5184 1294 }
kaf24@5184 1295
kaf24@5184 1296 queue = EXTRAQ(i,EXTRA_UTIL_Q); loop = 0;
kaf24@5184 1297 printk("\nEXTRAQ (utilization) rq %lx n: %lx, p: %lx\n",
kaf24@5184 1298 (unsigned long)queue, (unsigned long) queue->next,
kaf24@5184 1299 (unsigned long) queue->prev);
kaf24@8541 1300 list_for_each_safe ( list, tmp, queue )
kaf24@8541 1301 {
kaf24@5327 1302 d_inf = list_entry(list, struct sedf_vcpu_info,
kaf24@5184 1303 extralist[EXTRA_UTIL_Q]);
kaf24@5184 1304 printk("%3d: ",loop++);
kaf24@5327 1305 sedf_dump_domain(d_inf->vcpu);
kaf24@5184 1306 }
kaf24@5184 1307
kaf24@5184 1308 loop = 0;
kaf24@5184 1309 printk("\nnot on Q\n");
kaf24@8541 1310
kfraser@14074 1311 rcu_read_lock(&domlist_read_lock);
kaf24@8541 1312 for_each_domain ( d )
kaf24@5184 1313 {
kaf24@8541 1314 for_each_vcpu(d, ed)
kaf24@8541 1315 {
kaf24@8541 1316 if ( !__task_on_queue(ed) && (ed->processor == i) )
kaf24@8541 1317 {
kaf24@8541 1318 printk("%3d: ",loop++);
kaf24@8541 1319 sedf_dump_domain(ed);
kaf24@8541 1320 }
kaf24@5184 1321 }
kaf24@5184 1322 }
kfraser@14074 1323 rcu_read_unlock(&domlist_read_lock);
sd386@3611 1324 }
kaf24@8541 1325
kaf24@8541 1326
kaf24@8541 1327 /* Adjusts periods and slices of the domains accordingly to their weights. */
keir@21258 1328 static int sedf_adjust_weights(struct cpupool *c, struct xen_domctl_scheduler_op *cmd)
kaf24@8541 1329 {
kaf24@5327 1330 struct vcpu *p;
kaf24@5184 1331 struct domain *d;
keir@21436 1332 unsigned int cpu, nr_cpus = last_cpu(cpu_online_map) + 1;
keir@18561 1333 int *sumw = xmalloc_array(int, nr_cpus);
keir@18561 1334 s_time_t *sumt = xmalloc_array(s_time_t, nr_cpus);
keir@18561 1335
keir@18561 1336 if ( !sumw || !sumt )
keir@18561 1337 {
keir@18561 1338 xfree(sumt);
keir@18561 1339 xfree(sumw);
keir@18561 1340 return -ENOMEM;
keir@18561 1341 }
keir@18561 1342 memset(sumw, 0, nr_cpus * sizeof(*sumw));
keir@18561 1343 memset(sumt, 0, nr_cpus * sizeof(*sumt));
kfraser@14074 1344
kaf24@9629 1345 /* Sum across all weights. */
kfraser@14074 1346 rcu_read_lock(&domlist_read_lock);
kaf24@8541 1347 for_each_domain( d )
kaf24@8541 1348 {
keir@21258 1349 if ( c != d->cpupool )
keir@21258 1350 continue;
kaf24@8541 1351 for_each_vcpu( d, p )
kaf24@8541 1352 {
keir@21436 1353 if ( (cpu = p->processor) >= nr_cpus )
keir@21436 1354 continue;
keir@21436 1355
kaf24@8541 1356 if ( EDOM_INFO(p)->weight )
kaf24@8541 1357 {
keir@21436 1358 sumw[cpu] += EDOM_INFO(p)->weight;
kaf24@8541 1359 }
kaf24@8541 1360 else
kaf24@8541 1361 {
kaf24@8541 1362 /*don't modify domains who don't have a weight, but sum
kaf24@8541 1363 up the time they need, projected to a WEIGHT_PERIOD,
kaf24@8541 1364 so that this time is not given to the weight-driven
kaf24@8541 1365 domains*/
kaf24@8541 1366 /*check for overflows*/
kaf24@8541 1367 ASSERT((WEIGHT_PERIOD < ULONG_MAX)
kaf24@8541 1368 && (EDOM_INFO(p)->slice_orig < ULONG_MAX));
keir@21436 1369 sumt[cpu] +=
kaf24@8541 1370 (WEIGHT_PERIOD * EDOM_INFO(p)->slice_orig) /
kaf24@8541 1371 EDOM_INFO(p)->period_orig;
kaf24@8541 1372 }
kaf24@5184 1373 }
kaf24@5184 1374 }
kfraser@14074 1375 rcu_read_unlock(&domlist_read_lock);
kaf24@8541 1376
kaf24@9629 1377 /* Adjust all slices (and periods) to the new weight. */
kfraser@14074 1378 rcu_read_lock(&domlist_read_lock);
kaf24@8541 1379 for_each_domain( d )
kaf24@8541 1380 {
kaf24@8541 1381 for_each_vcpu ( d, p )
kaf24@8541 1382 {
keir@21436 1383 if ( (cpu = p->processor) >= nr_cpus )
keir@21436 1384 continue;
kaf24@8541 1385 if ( EDOM_INFO(p)->weight )
kaf24@8541 1386 {
kaf24@8541 1387 EDOM_INFO(p)->period_orig =
kaf24@8541 1388 EDOM_INFO(p)->period = WEIGHT_PERIOD;
kaf24@8541 1389 EDOM_INFO(p)->slice_orig =
kaf24@8541 1390 EDOM_INFO(p)->slice =
kaf24@8541 1391 (EDOM_INFO(p)->weight *
keir@21436 1392 (WEIGHT_PERIOD - WEIGHT_SAFETY - sumt[cpu])) / sumw[cpu];
kaf24@8541 1393 }
kaf24@5184 1394 }
kaf24@5184 1395 }
kfraser@14074 1396 rcu_read_unlock(&domlist_read_lock);
kaf24@8541 1397
keir@18561 1398 xfree(sumt);
keir@18561 1399 xfree(sumw);
keir@18561 1400
kaf24@5184 1401 return 0;
sd386@3487 1402 }
sd386@3487 1403
kaf24@8541 1404
sd386@3487 1405 /* set or fetch domain scheduling parameters */
keir@21327 1406 static int sedf_adjust(const struct scheduler *ops, struct domain *p, struct xen_domctl_scheduler_op *op)
kaf24@8541 1407 {
kaf24@5327 1408 struct vcpu *v;
keir@18561 1409 int rc;
sd386@4767 1410
kfraser@11295 1411 PRINT(2,"sedf_adjust was called, domain-id %i new period %"PRIu64" "
kaf24@5184 1412 "new slice %"PRIu64"\nlatency %"PRIu64" extra:%s\n",
kfraser@11295 1413 p->domain_id, op->u.sedf.period, op->u.sedf.slice,
kfraser@11295 1414 op->u.sedf.latency, (op->u.sedf.extratime)?"yes":"no");
kaf24@8541 1415
kfraser@11295 1416 if ( op->cmd == XEN_DOMCTL_SCHEDOP_putinfo )
kaf24@5184 1417 {
kaf24@9629 1418 /* Check for sane parameters. */
kfraser@11295 1419 if ( !op->u.sedf.period && !op->u.sedf.weight )
kaf24@5184 1420 return -EINVAL;
kfraser@11295 1421 if ( op->u.sedf.weight )
kaf24@9629 1422 {
kfraser@11295 1423 if ( (op->u.sedf.extratime & EXTRA_AWARE) &&
kfraser@11295 1424 (!op->u.sedf.period) )
kaf24@9629 1425 {
kaf24@9629 1426 /* Weight-driven domains with extratime only. */
kaf24@9629 1427 for_each_vcpu ( p, v )
kaf24@9629 1428 {
kfraser@11295 1429 EDOM_INFO(v)->extraweight = op->u.sedf.weight;
kaf24@5327 1430 EDOM_INFO(v)->weight = 0;
kaf24@5327 1431 EDOM_INFO(v)->slice = 0;
kaf24@5327 1432 EDOM_INFO(v)->period = WEIGHT_PERIOD;
kaf24@5184 1433 }
kaf24@9629 1434 }
kaf24@9629 1435 else
kaf24@9629 1436 {
kaf24@9629 1437 /* Weight-driven domains with real-time execution. */
kaf24@9629 1438 for_each_vcpu ( p, v )
kfraser@11295 1439 EDOM_INFO(v)->weight = op->u.sedf.weight;
kaf24@5184 1440 }
kaf24@5184 1441 }
kaf24@9629 1442 else
kaf24@9629 1443 {
kaf24@9629 1444 /* Time-driven domains. */
kaf24@9629 1445 for_each_vcpu ( p, v )
kaf24@9629 1446 {
kaf24@8976 1447 /*
kaf24@8976 1448 * Sanity checking: note that disabling extra weight requires
kaf24@8976 1449 * that we set a non-zero slice.
kaf24@8976 1450 */
kfraser@11295 1451 if ( (op->u.sedf.period > PERIOD_MAX) ||
kfraser@11295 1452 (op->u.sedf.period < PERIOD_MIN) ||
kfraser@11295 1453 (op->u.sedf.slice > op->u.sedf.period) ||
kfraser@11295 1454 (op->u.sedf.slice < SLICE_MIN) )
kaf24@5184 1455 return -EINVAL;
kaf24@5327 1456 EDOM_INFO(v)->weight = 0;
kaf24@5327 1457 EDOM_INFO(v)->extraweight = 0;
kaf24@5327 1458 EDOM_INFO(v)->period_orig =
kfraser@11295 1459 EDOM_INFO(v)->period = op->u.sedf.period;
kaf24@5327 1460 EDOM_INFO(v)->slice_orig =
kfraser@11295 1461 EDOM_INFO(v)->slice = op->u.sedf.slice;
kaf24@5184 1462 }
kaf24@5184 1463 }
kaf24@9629 1464
keir@21258 1465 rc = sedf_adjust_weights(p->cpupool, op);
keir@18561 1466 if ( rc )
keir@18561 1467 return rc;
kaf24@9629 1468
kaf24@9629 1469 for_each_vcpu ( p, v )
kaf24@9629 1470 {
kaf24@5327 1471 EDOM_INFO(v)->status =
kaf24@5327 1472 (EDOM_INFO(v)->status &
kfraser@11295 1473 ~EXTRA_AWARE) | (op->u.sedf.extratime & EXTRA_AWARE);
kfraser@11295 1474 EDOM_INFO(v)->latency = op->u.sedf.latency;
kaf24@5327 1475 extraq_check(v);
kaf24@5184 1476 }
kaf24@5184 1477 }
kfraser@11295 1478 else if ( op->cmd == XEN_DOMCTL_SCHEDOP_getinfo )
kaf24@5184 1479 {
kfraser@10679 1480 if ( p->vcpu[0] == NULL )
kfraser@10679 1481 return -EINVAL;
kfraser@11295 1482 op->u.sedf.period = EDOM_INFO(p->vcpu[0])->period;
kfraser@11295 1483 op->u.sedf.slice = EDOM_INFO(p->vcpu[0])->slice;
kfraser@11295 1484 op->u.sedf.extratime = EDOM_INFO(p->vcpu[0])->status & EXTRA_AWARE;
kfraser@11295 1485 op->u.sedf.latency = EDOM_INFO(p->vcpu[0])->latency;
kfraser@11295 1486 op->u.sedf.weight = EDOM_INFO(p->vcpu[0])->weight;
kaf24@5184 1487 }
kaf24@9629 1488
kfraser@11295 1489 PRINT(2,"sedf_adjust_finished\n");
kaf24@5184 1490 return 0;
sd386@3487 1491 }
sd386@3487 1492
keir@21327 1493 const struct scheduler sched_sedf_def = {
sd386@3487 1494 .name = "Simple EDF Scheduler",
sd386@3487 1495 .opt_name = "sedf",
kfraser@11295 1496 .sched_id = XEN_SCHEDULER_SEDF,
sd386@3487 1497
kfraser@12284 1498 .init_domain = sedf_init_domain,
kfraser@12284 1499 .destroy_domain = sedf_destroy_domain,
kfraser@12284 1500
keir@21258 1501 .alloc_vdata = sedf_alloc_vdata,
keir@21258 1502 .free_vdata = sedf_free_vdata,
keir@21258 1503 .alloc_pdata = sedf_alloc_pdata,
keir@21258 1504 .free_pdata = sedf_free_pdata,
keir@21258 1505 .alloc_domdata = sedf_alloc_domdata,
keir@21258 1506 .free_domdata = sedf_free_domdata,
keir@21258 1507
sd386@3487 1508 .do_schedule = sedf_do_schedule,
ack@12291 1509 .pick_cpu = sedf_pick_cpu,
sd386@3487 1510 .dump_cpu_state = sedf_dump_cpu_state,
sd386@3487 1511 .sleep = sedf_sleep,
sd386@3487 1512 .wake = sedf_wake,
kfraser@11295 1513 .adjust = sedf_adjust,
sd386@3487 1514 };
kaf24@7485 1515
kaf24@7485 1516 /*
kaf24@7485 1517 * Local variables:
kaf24@7485 1518 * mode: C
kaf24@7485 1519 * c-set-style: "BSD"
kaf24@7485 1520 * c-basic-offset: 4
kaf24@7485 1521 * tab-width: 4
kaf24@7485 1522 * indent-tabs-mode: nil
kaf24@7485 1523 * End:
kaf24@7485 1524 */