debuggers.hg

annotate xen/common/sched_atropos.c @ 3658:0ef6e8e6e85d

find changesets by author, revision, files, or words in the commit message
bitkeeper revision 1.1159.212.71 (4200f0afX_JumfbEHQex6TdFENULMQ)

Merge labyrinth.cl.cam.ac.uk:/auto/groups/xeno-xenod/BK/xen-unstable.bk
into labyrinth.cl.cam.ac.uk:/auto/groups/xeno/users/iap10/xeno-clone/xen-unstable.bk
author iap10@labyrinth.cl.cam.ac.uk
date Wed Feb 02 15:24:31 2005 +0000 (2005-02-02)
parents 51052c8b6456 f98fa170a9f4
children bbe8541361dd 4294cfa9fad3
rev   line source
mwilli2@1284 1 /*
kaf24@3568 2 * atropos.c
kaf24@3568 3 * ---------
mwilli2@1284 4 *
mwilli2@1284 5 * Copyright (c) 1994 University of Cambridge Computer Laboratory.
mwilli2@1284 6 * This is part of Nemesis; consult your contract for terms and conditions.
mwilli2@1284 7 *
mwilli2@1284 8 * ID : $Id: atropos.c 1.1 Tue, 13 Apr 1999 13:30:49 +0100 dr10009 $
mwilli2@1284 9 *
mwilli2@1284 10 * This is the "atropos" CPU scheduler.
mwilli2@1284 11 */
mwilli2@1284 12
mwilli2@1284 13 /* Ported to Xen's generic scheduler interface by Mark Williamson
mwilli2@1284 14 * these modifications are (C) 2004 Intel Research Cambridge
mwilli2@1284 15 */
mwilli2@1284 16
kaf24@1304 17 #include <xen/config.h>
kaf24@1304 18 #include <xen/init.h>
kaf24@1304 19 #include <xen/lib.h>
mwilli2@1284 20 #include <xen/time.h>
mwilli2@1284 21 #include <xen/sched.h>
mwilli2@1284 22 #include <xen/sched-if.h>
kaf24@2827 23 #include <public/sched_ctl.h>
mwilli2@1284 24 #include <xen/trace.h>
mwilli2@1284 25
mwilli2@1284 26 #define ATROPOS_TASK_UNBLOCKED 16
mwilli2@1284 27 #define ATROPOS_TASK_WAIT 32
gm281@2564 28 #define ATROPOS_TASK_BLOCKED 48
mwilli2@1284 29
mwilli2@1345 30 /* Atropos-specific per-domain data */
mwilli2@1284 31 struct at_dom_info
mwilli2@1284 32 {
mwilli2@1284 33 /* MAW Xen additions */
kaf24@1543 34 struct domain *owner; /* the domain this data belongs to */
gm281@2564 35 struct list_head run_list; /* runqueue */
kaf24@1304 36 struct list_head waitq; /* wait queue */
mwilli2@1284 37
mwilli2@1284 38 /* (what remains of) the original fields */
mwilli2@1284 39
mwilli2@1345 40 s_time_t deadline; /* Next deadline */
mwilli2@1345 41 s_time_t prevddln; /* Previous deadline */
mwilli2@1284 42
mwilli2@1345 43 s_time_t remain; /* Time remaining this period */
mwilli2@1345 44 s_time_t period; /* Current period of time allocation */
mwilli2@1345 45 s_time_t nat_period; /* Natural period */
mwilli2@1345 46 s_time_t slice; /* Current length of allocation */
mwilli2@1345 47 s_time_t nat_slice; /* Natural length of allocation */
mwilli2@1345 48 s_time_t latency; /* Unblocking latency */
mwilli2@1284 49
mwilli2@1345 50 int xtratime; /* Prepared to accept extra time? */
gm281@2564 51 int state; /* Keeps Atropos domain state */
mwilli2@1284 52 };
mwilli2@1284 53
mwilli2@1345 54 /* Atropos-specific per-CPU data */
mwilli2@1284 55 struct at_cpu_info
mwilli2@1284 56 {
kaf24@2634 57 struct list_head runq;
kaf24@2634 58 struct list_head waitq;
mwilli2@1284 59 };
mwilli2@1284 60
mwilli2@1284 61
kaf24@1489 62 #define DOM_INFO(_p) ((struct at_dom_info *)((_p)->sched_priv))
gm281@2564 63 #define CPU_INFO(_c) ((struct at_cpu_info *)((schedule_data[_c]).sched_priv))
gm281@2564 64 #define WAITQ(cpu) (&CPU_INFO(cpu)->waitq)
gm281@2564 65 #define RUNQ(cpu) (&CPU_INFO(cpu)->runq)
gm281@2564 66 #define RUNLIST(_d) (&DOM_INFO(_d)->run_list)
mwilli2@1284 67
mwilli2@1284 68 #define BESTEFFORT_QUANTUM MILLISECS(5)
mwilli2@1284 69
gm281@2564 70 static void at_dump_cpu_state(int cpu);
gm281@2564 71
gm281@2564 72 static inline void __add_to_runqueue_head(struct domain *d)
gm281@2564 73 {
gm281@2564 74 list_add(RUNLIST(d), RUNQ(d->processor));
gm281@2564 75 }
gm281@2564 76
gm281@2564 77 static inline void __add_to_runqueue_tail(struct domain *d)
gm281@2564 78 {
gm281@2564 79 list_add_tail(RUNLIST(d), RUNQ(d->processor));
gm281@2564 80 }
gm281@2564 81
gm281@2564 82 static inline void __del_from_runqueue(struct domain *d)
gm281@2564 83 {
gm281@2564 84 struct list_head *runlist = RUNLIST(d);
gm281@2564 85 list_del(runlist);
gm281@2564 86 runlist->next = NULL;
gm281@2564 87 }
gm281@2564 88
gm281@2564 89 static inline int __task_on_runqueue(struct domain *d)
gm281@2564 90 {
gm281@2564 91 return (RUNLIST(d))->next != NULL;
gm281@2564 92 }
gm281@2564 93
mwilli2@1345 94
mwilli2@1284 95 /** calculate the length of a linked list */
mwilli2@1284 96 static int q_len(struct list_head *q)
mwilli2@1284 97 {
mwilli2@1284 98 int i = 0;
kaf24@3568 99 struct at_dom_info *tmp;
kaf24@3568 100 list_for_each_entry ( tmp, q, waitq )
kaf24@3568 101 i++;
mwilli2@1284 102 return i;
mwilli2@1284 103 }
mwilli2@1284 104
mwilli2@1284 105
kaf24@1543 106 /** waitq_el - get the domain that owns a wait queue list element */
kaf24@1543 107 static inline struct domain *waitq_el(struct list_head *l)
mwilli2@1284 108 {
mwilli2@1284 109 struct at_dom_info *inf;
mwilli2@1284 110 inf = list_entry(l, struct at_dom_info, waitq);
mwilli2@1284 111 return inf->owner;
mwilli2@1284 112 }
mwilli2@1284 113
mwilli2@1284 114
mwilli2@1284 115 /*
mwilli2@1284 116 * requeue
mwilli2@1284 117 *
mwilli2@1284 118 * Places the specified domain on the appropriate queue.
mwilli2@1284 119 * The wait queue is ordered by the time at which the domain
mwilli2@1284 120 * will receive more CPU time. If a domain has no guaranteed time
mwilli2@1284 121 * left then the domain will be placed on the WAIT queue until
mwilli2@1284 122 * its next period.
mwilli2@1284 123 *
mwilli2@1284 124 * Note that domains can be on the wait queue with remain > 0
mwilli2@1284 125 * as a result of being blocked for a short time.
mwilli2@1284 126 * These are scheduled in preference to domains with remain < 0
mwilli2@1284 127 * in an attempt to improve interactive performance.
mwilli2@1284 128 */
kaf24@1543 129 static void requeue(struct domain *sdom)
mwilli2@1284 130 {
kaf24@3568 131 struct at_dom_info *i, *inf = DOM_INFO(sdom);
mwilli2@1284 132
kaf24@3568 133 if ( !domain_runnable(sdom) )
kaf24@3568 134 return;
gm281@2564 135
kaf24@3568 136 if ( (inf->state == ATROPOS_TASK_WAIT) ||
kaf24@3568 137 (inf->state == ATROPOS_TASK_UNBLOCKED) )
mwilli2@1284 138 {
kaf24@3568 139 list_for_each_entry ( i, WAITQ(sdom->processor), waitq )
mwilli2@1284 140 {
kaf24@1304 141 if ( i->deadline > inf->deadline )
mwilli2@1284 142 {
kaf24@3568 143 __list_add(&inf->waitq, i->waitq.prev, &i->waitq);
mwilli2@1284 144 break;
mwilli2@1284 145 }
mwilli2@1284 146 }
mwilli2@1284 147
kaf24@3568 148 if ( &i->waitq == WAITQ(sdom->processor) )
mwilli2@1284 149 list_add_tail(&inf->waitq, WAITQ(sdom->processor));
mwilli2@1284 150 }
kaf24@1543 151 else if ( domain_runnable(sdom) )
mwilli2@1284 152 {
kaf24@3568 153 list_for_each_entry ( i, RUNQ(sdom->processor), run_list )
mwilli2@1284 154 {
kaf24@3568 155 if ( (i->deadline > inf->deadline) || is_idle_task(i->owner) )
mwilli2@1284 156 {
kaf24@3568 157 __list_add(&inf->run_list, i->run_list.prev, &i->run_list);
mwilli2@1284 158 break;
mwilli2@1284 159 }
mwilli2@1284 160 }
mwilli2@1284 161
kaf24@3568 162 if ( &i->waitq == RUNQ(sdom->processor) )
gm281@2564 163 list_add_tail(&inf->run_list, RUNQ(sdom->processor));
mwilli2@1284 164 }
mwilli2@1284 165 /* silently ignore tasks in other states like BLOCKED, DYING, STOPPED, etc
mwilli2@1284 166 * - they shouldn't be on any queue */
mwilli2@1284 167 }
mwilli2@1284 168
gm281@2564 169 /** at_alloc_task - allocate private info for a task */
gm281@2564 170 static int at_alloc_task(struct domain *p)
gm281@2564 171 {
gm281@2564 172 ASSERT(p != NULL);
gm281@2564 173
iap10@3650 174 p->sched_priv = xmalloc(struct at_dom_info);
kaf24@3568 175 if ( p->sched_priv == NULL )
gm281@2564 176 return -1;
gm281@2564 177
gm281@2564 178 return 0;
gm281@2564 179 }
gm281@2564 180
gm281@2564 181
kaf24@2217 182 /* prepare a task to be added to scheduling */
kaf24@2217 183 static void at_add_task(struct domain *p)
mwilli2@1284 184 {
mwilli2@1284 185 s_time_t now = NOW();
mwilli2@1284 186
mwilli2@1284 187 ASSERT( p->sched_priv != NULL );
mwilli2@1284 188
mwilli2@1284 189 DOM_INFO(p)->owner = p;
mwilli2@1284 190 p->lastschd = now;
mwilli2@1284 191
mwilli2@1345 192 /* DOM 0's parameters must be set here for it to boot the system! */
kaf24@2748 193 if(p->id == 0)
mwilli2@1284 194 {
mwilli2@1284 195 DOM_INFO(p)->remain = MILLISECS(15);
mwilli2@1345 196 DOM_INFO(p)->nat_period =
mwilli2@1345 197 DOM_INFO(p)->period = MILLISECS(20);
mwilli2@1345 198 DOM_INFO(p)->nat_slice =
mwilli2@1345 199 DOM_INFO(p)->slice = MILLISECS(15);
mwilli2@1345 200 DOM_INFO(p)->latency = MILLISECS(5);
mwilli2@1284 201 DOM_INFO(p)->xtratime = 1;
mwilli2@1284 202 DOM_INFO(p)->deadline = now;
mwilli2@1284 203 DOM_INFO(p)->prevddln = now;
mwilli2@1284 204 }
mwilli2@1284 205 else /* other domains run basically best effort unless otherwise set */
mwilli2@1284 206 {
mwilli2@1284 207 DOM_INFO(p)->remain = 0;
mwilli2@1345 208 DOM_INFO(p)->nat_period =
mwilli2@1345 209 DOM_INFO(p)->period = SECONDS(10);
mwilli2@1345 210 DOM_INFO(p)->nat_slice =
mwilli2@1345 211 DOM_INFO(p)->slice = MILLISECS(10);
mwilli2@1345 212 DOM_INFO(p)->latency = SECONDS(10);
mwilli2@1284 213 DOM_INFO(p)->xtratime = 1;
gm281@2564 214 DOM_INFO(p)->deadline = now;
gm281@2564 215 // DOM_INFO(p)->deadline = now + SECONDS(10);
mwilli2@1284 216 DOM_INFO(p)->prevddln = 0;
mwilli2@1284 217 }
mwilli2@1284 218
gm281@2564 219 INIT_LIST_HEAD(&(DOM_INFO(p)->run_list));
mwilli2@1284 220 INIT_LIST_HEAD(&(DOM_INFO(p)->waitq));
mwilli2@1284 221 }
mwilli2@1284 222
mwilli2@1284 223 /**
mwilli2@1284 224 * dequeue - remove a domain from any queues it is on.
mwilli2@1284 225 * @sdom: the task to remove
mwilli2@1284 226 */
kaf24@1543 227 static void dequeue(struct domain *sdom)
mwilli2@1284 228 {
mwilli2@1284 229 struct at_dom_info *inf = DOM_INFO(sdom);
gm281@2564 230
kaf24@2748 231 ASSERT(sdom->id != IDLE_DOMAIN_ID);
mwilli2@1284 232
mwilli2@1284 233 /* just delete it from all the queues! */
mwilli2@1284 234 list_del(&inf->waitq);
mwilli2@1284 235 INIT_LIST_HEAD(&inf->waitq);
gm281@2564 236
mwilli2@1284 237
mwilli2@1284 238 if(__task_on_runqueue(sdom))
mwilli2@1284 239 __del_from_runqueue(sdom);
mwilli2@1284 240 }
mwilli2@1284 241
mwilli2@1284 242
mwilli2@1284 243 /*
mwilli2@1284 244 * unblock
mwilli2@1284 245 *
mwilli2@1284 246 * This function deals with updating the sdom for a domain
mwilli2@1284 247 * which has just been unblocked.
mwilli2@1284 248 *
mwilli2@1345 249 * Xen's Atropos treats unblocking slightly differently to Nemesis:
mwilli2@1345 250 *
mwilli2@1345 251 * - "Short blocking" domains (i.e. that unblock before their deadline has
mwilli2@1345 252 * expired) are treated the same as in nemesis (put on the wait queue and
mwilli2@1345 253 * given preferential treatment in selecting domains for extra time).
mwilli2@1345 254 *
mwilli2@1345 255 * - "Long blocking" domains do not simply have their period truncated to their
mwilli2@1345 256 * unblocking latency as before but also have their slice recomputed to be the
mwilli2@1345 257 * same fraction of their new period. Each time the domain is scheduled, the
mwilli2@1345 258 * period and slice are doubled until they reach their original ("natural")
mwilli2@1345 259 * values, as set by the user (and stored in nat_period and nat_slice). The
mwilli2@1345 260 * idea is to give better response times to unblocking whilst preserving QoS
mwilli2@1345 261 * guarantees to other domains.
mwilli2@1284 262 */
kaf24@1543 263 static void unblock(struct domain *sdom)
mwilli2@1284 264 {
mwilli2@1284 265 s_time_t time = NOW();
mwilli2@1284 266 struct at_dom_info *inf = DOM_INFO(sdom);
gm281@2564 267
mwilli2@1284 268 dequeue(sdom);
mwilli2@1284 269
mwilli2@1284 270 /* We distinguish two cases... short and long blocks */
mwilli2@1345 271 if ( inf->deadline < time )
mwilli2@1345 272 {
mwilli2@1345 273 /* Long blocking case */
mwilli2@1345 274
kaf24@3568 275 /* The sdom has passed its deadline since it was blocked.
kaf24@3568 276 Give it its new deadline based on the latency value. */
kaf24@3568 277 inf->prevddln = time;
mwilli2@1345 278
mwilli2@1345 279 /* Scale the scheduling parameters as requested by the latency hint. */
kaf24@3568 280 inf->deadline = time + inf->latency;
mwilli2@1345 281 inf->slice = inf->nat_slice / ( inf->nat_period / inf->latency );
mwilli2@1345 282 inf->period = inf->latency;
kaf24@3568 283 inf->remain = inf->slice;
mwilli2@1345 284 }
gm281@2564 285 else
mwilli2@1345 286 {
mwilli2@1345 287 /* Short blocking case */
mwilli2@1345 288
kaf24@3568 289 /* We leave REMAIN intact, but put this domain on the WAIT
kaf24@3568 290 queue marked as recently unblocked. It will be given
kaf24@3568 291 priority over other domains on the wait queue until while
kaf24@3568 292 REMAIN>0 in a generous attempt to help it make up for its
kaf24@3568 293 own foolishness. */
kaf24@3568 294 if(inf->remain > 0)
gm281@2564 295 inf->state = ATROPOS_TASK_UNBLOCKED;
mwilli2@1284 296 else
gm281@2564 297 inf->state = ATROPOS_TASK_WAIT;
mwilli2@1284 298 }
mwilli2@1284 299
mwilli2@1284 300 requeue(sdom);
gm281@2564 301 }
mwilli2@1284 302
gm281@2564 303
gm281@2564 304 static int at_init_idle_task(struct domain *p)
gm281@2564 305 {
gm281@2564 306 if(at_alloc_task(p) < 0) return -1;
gm281@2564 307
gm281@2564 308 at_add_task(p);
gm281@2564 309
gm281@2564 310 dequeue(p);
gm281@2564 311 requeue(p);
gm281@2564 312
gm281@2564 313 return 0;
mwilli2@1284 314 }
mwilli2@1284 315
gm281@2564 316
gm281@2564 317 static void block(struct domain* sdom)
gm281@2564 318 {
gm281@2564 319 DOM_INFO(sdom)->state = ATROPOS_TASK_BLOCKED;
gm281@2564 320 dequeue(sdom);
gm281@2564 321 requeue(sdom);
gm281@2564 322 }
gm281@2564 323
gm281@2564 324
mwilli2@1284 325 /**
mwilli2@1284 326 * ATROPOS - main scheduler function
mwilli2@1284 327 */
mwilli2@1284 328 task_slice_t ksched_scheduler(s_time_t time)
mwilli2@1284 329 {
kaf24@3568 330 struct domain *cur_sdom = current; /* Current sdom */
kaf24@3568 331 s_time_t newtime;
kaf24@3568 332 s_time_t ranfor; /* How long the domain ran */
kaf24@3568 333 struct domain *sdom; /* tmp. scheduling domain */
mwilli2@1284 334 int cpu = cur_sdom->processor; /* current CPU */
mwilli2@1284 335 struct at_dom_info *cur_info;
mwilli2@1284 336 static unsigned long waitq_rrobin = 0;
mwilli2@1284 337 int i;
mwilli2@1284 338 task_slice_t ret;
mwilli2@1284 339
gm281@2564 340
mwilli2@1284 341 cur_info = DOM_INFO(cur_sdom);
mwilli2@1284 342
mwilli2@1284 343 ASSERT( cur_sdom != NULL);
mwilli2@1284 344
mwilli2@1284 345 /* If we were spinning in the idle loop, there is no current
mwilli2@1284 346 * domain to deschedule. */
mwilli2@1345 347 if (is_idle_task(cur_sdom))
kaf24@3568 348 goto deschedule_done;
mwilli2@1284 349
mwilli2@1284 350 /*****************************
mwilli2@1284 351 *
mwilli2@1284 352 * Deschedule the current scheduling domain
mwilli2@1284 353 *
mwilli2@1284 354 ****************************/
mwilli2@1284 355
kaf24@3568 356 /* Record the time the domain was preempted and for how long it
mwilli2@1284 357 ran. Work out if the domain is going to be blocked to save
mwilli2@1284 358 some pointless queue shuffling */
mwilli2@1284 359 cur_sdom->lastdeschd = time;
mwilli2@1284 360
mwilli2@1284 361 ranfor = (time - cur_sdom->lastschd);
mwilli2@1284 362
mwilli2@1284 363 dequeue(cur_sdom);
mwilli2@1284 364
kaf24@1543 365 if ( domain_runnable(cur_sdom) ||
gm281@2564 366 (cur_info->state == ATROPOS_TASK_UNBLOCKED) )
mwilli2@1345 367 {
mwilli2@1284 368
kaf24@3568 369 /* In this block, we are doing accounting for an sdom which has
kaf24@3568 370 been running in contracted time. Note that this could now happen
kaf24@3568 371 even if the domain is on the wait queue (i.e. if it blocked) */
mwilli2@1284 372
kaf24@3568 373 /* Deduct guaranteed time from the domain */
kaf24@3568 374 cur_info->remain -= ranfor;
mwilli2@1284 375
kaf24@3568 376 /* If guaranteed time has run out... */
kaf24@3568 377 if ( cur_info->remain <= 0 )
mwilli2@1345 378 {
kaf24@3568 379 /* Move domain to correct position in WAIT queue */
mwilli2@1284 380 /* XXX sdom_unblocked doesn't need this since it is
mwilli2@1345 381 already in the correct place. */
kaf24@3568 382 cur_info->state = ATROPOS_TASK_WAIT;
kaf24@3568 383 }
mwilli2@1284 384 }
mwilli2@1284 385
mwilli2@1284 386 requeue(cur_sdom);
mwilli2@1284 387
kaf24@3568 388 deschedule_done:
mwilli2@1284 389 /*****************************
mwilli2@1284 390 *
mwilli2@1284 391 * We have now successfully descheduled the current sdom.
mwilli2@1284 392 * The next task is the allocate CPU time to any sdom it is due to.
mwilli2@1284 393 *
gm281@2564 394 ****************************/
mwilli2@1284 395 cur_sdom = NULL;
mwilli2@1284 396
mwilli2@1284 397 /*****************************
mwilli2@1284 398 *
mwilli2@1284 399 * Allocate CPU time to any waiting domains who have passed their
mwilli2@1284 400 * period deadline. If necessary, move them to run queue.
mwilli2@1284 401 *
mwilli2@1284 402 ****************************/
gm281@2564 403
mwilli2@1284 404 while(!list_empty(WAITQ(cpu)) &&
kaf24@3568 405 DOM_INFO(sdom = waitq_el(WAITQ(cpu)->next))->deadline <= time )
gm281@2564 406 {
mwilli2@1284 407
kaf24@3568 408 struct at_dom_info *inf = DOM_INFO(sdom);
mwilli2@1284 409 dequeue(sdom);
gm281@2564 410
mwilli2@1345 411 if ( inf->period != inf->nat_period )
mwilli2@1345 412 {
mwilli2@1345 413 /* This domain has had its parameters adjusted as a result of
mwilli2@1345 414 * unblocking and they need to be adjusted before requeuing it */
mwilli2@1345 415 inf->slice *= 2;
mwilli2@1345 416 inf->period *= 2;
mwilli2@1345 417
mwilli2@1345 418 if ( inf->period > inf->nat_period )
mwilli2@1345 419 {
mwilli2@1345 420 inf->period = inf->nat_period;
mwilli2@1345 421 inf->slice = inf->nat_slice;
mwilli2@1345 422 }
mwilli2@1345 423 }
mwilli2@1345 424
kaf24@3568 425 /* Domain begins a new period and receives a slice of CPU
kaf24@3568 426 * If this domain has been blocking then throw away the
kaf24@3568 427 * rest of it's remain - it can't be trusted */
kaf24@3568 428 if (inf->remain > 0)
kaf24@3568 429 inf->remain = inf->slice;
gm281@2564 430 else
kaf24@3568 431 inf->remain += inf->slice;
mwilli2@1345 432
kaf24@3568 433 inf->prevddln = inf->deadline;
kaf24@3568 434 inf->deadline += inf->period;
mwilli2@1345 435
kaf24@1543 436 if ( inf->remain <= 0 )
gm281@2564 437 inf->state = ATROPOS_TASK_WAIT;
mwilli2@1284 438
kaf24@3568 439 /* Place on the appropriate queue */
kaf24@3568 440 requeue(sdom);
mwilli2@1284 441 }
mwilli2@1284 442
mwilli2@1284 443 /*****************************
mwilli2@1284 444 *
mwilli2@1284 445 * Next we need to pick an sdom to run.
mwilli2@1284 446 * If anything is actually 'runnable', we run that.
mwilli2@1284 447 * If nothing is, we pick a waiting sdom to run optimistically.
mwilli2@1284 448 * If there aren't even any of those, we have to spin waiting for an
mwilli2@1284 449 * event or a suitable time condition to happen.
mwilli2@1284 450 *
mwilli2@1284 451 ****************************/
mwilli2@1284 452
mwilli2@1284 453 /* we guarantee there's always something on the runqueue */
gm281@2564 454 cur_info = list_entry(RUNQ(cpu)->next,
gm281@2564 455 struct at_dom_info, run_list);
mwilli2@1284 456
gm281@2564 457 cur_sdom = cur_info->owner;
mwilli2@1284 458 newtime = time + cur_info->remain;
mwilli2@1284 459
mwilli2@1284 460 /* MAW - the idle domain is always on the run queue. We run from the
mwilli2@1284 461 * runqueue if it's NOT the idle domain or if there's nothing on the wait
mwilli2@1284 462 * queue */
kaf24@2748 463 if (cur_sdom->id == IDLE_DOMAIN_ID && !list_empty(WAITQ(cpu)))
mwilli2@1345 464 {
kaf24@3568 465 struct at_dom_info *inf;
kaf24@3568 466
kaf24@3568 467 /* Try running a domain on the WAIT queue - this part of the
kaf24@3568 468 scheduler isn't particularly efficient but then again, we
kaf24@3568 469 don't have any guaranteed domains to worry about. */
mwilli2@1284 470
kaf24@3568 471 /* See if there are any unblocked domains on the WAIT
kaf24@3568 472 queue who we can give preferential treatment to. */
gm281@2564 473
kaf24@3568 474 list_for_each_entry ( inf, WAITQ(cpu), waitq )
mwilli2@1284 475 {
mwilli2@1284 476 sdom = inf->owner;
mwilli2@1284 477
kaf24@3568 478 if (inf->state == ATROPOS_TASK_UNBLOCKED)
gm281@2564 479 {
kaf24@3568 480 cur_sdom = sdom;
kaf24@3568 481 cur_info = inf;
kaf24@3568 482 newtime = time + inf->remain;
kaf24@3568 483 goto found;
kaf24@3568 484 }
kaf24@3568 485 }
mwilli2@1284 486
mwilli2@1284 487 /* init values needed to approximate round-robin for slack time */
mwilli2@1284 488 i = 0;
mwilli2@1284 489 if ( waitq_rrobin >= q_len(WAITQ(cpu)))
mwilli2@1284 490 waitq_rrobin = 0;
mwilli2@1284 491
gm281@2564 492
kaf24@3568 493 /* Last chance: pick a domain on the wait queue with the XTRA
kaf24@3568 494 flag set. The NEXT_OPTM field is used to cheaply achieve
kaf24@3568 495 an approximation of round-robin order */
kaf24@3568 496 list_for_each_entry ( inf, WAITQ(cpu), waitq )
mwilli2@1345 497 {
mwilli2@1345 498 sdom = inf->owner;
mwilli2@1345 499
gm281@2564 500 if (inf->xtratime && i >= waitq_rrobin)
gm281@2564 501 {
mwilli2@1345 502 cur_sdom = sdom;
mwilli2@1345 503 cur_info = inf;
mwilli2@1345 504 newtime = time + BESTEFFORT_QUANTUM;
mwilli2@1345 505 waitq_rrobin = i + 1; /* set this value ready for next */
mwilli2@1345 506 goto found;
mwilli2@1284 507 }
mwilli2@1345 508
mwilli2@1345 509 i++;
mwilli2@1345 510 }
mwilli2@1284 511 }
mwilli2@1284 512
kaf24@3568 513 found:
mwilli2@1284 514 /**********************
mwilli2@1284 515 *
mwilli2@1284 516 * We now have to work out the time when we next need to
mwilli2@1284 517 * make a scheduling decision. We set the alarm timer
mwilli2@1284 518 * to cause an interrupt at that time.
mwilli2@1284 519 *
mwilli2@1284 520 **********************/
mwilli2@1284 521
mwilli2@1284 522 #define MIN(x,y) ( ( x < y ) ? x : y )
mwilli2@1284 523 #define MAX(x,y) ( ( x > y ) ? x : y )
mwilli2@1284 524
mwilli2@1284 525 /* If we might be able to run a waiting domain before this one has */
mwilli2@1284 526 /* exhausted its time, cut short the time allocation */
mwilli2@1284 527 if (!list_empty(WAITQ(cpu)))
mwilli2@1284 528 {
kaf24@3568 529 newtime = MIN(newtime,
mwilli2@1284 530 DOM_INFO(waitq_el(WAITQ(cpu)->next))->deadline);
mwilli2@1284 531 }
mwilli2@1284 532
mwilli2@1284 533 /* don't allow pointlessly small time slices */
mwilli2@1284 534 newtime = MAX(newtime, time + BESTEFFORT_QUANTUM);
mwilli2@1284 535
mwilli2@1284 536 ret.task = cur_sdom;
mwilli2@1284 537 ret.time = newtime - time;
mwilli2@1284 538
kaf24@2748 539 TRACE_1D(0, cur_sdom->id);
mwilli2@1284 540
mwilli2@1284 541 return ret;
mwilli2@1284 542 }
mwilli2@1284 543
mwilli2@1284 544
mwilli2@1284 545 /* set up some private data structures */
mwilli2@1284 546 static int at_init_scheduler()
mwilli2@1284 547 {
mwilli2@1284 548 int i;
mwilli2@1284 549
kaf24@1489 550 for ( i = 0; i < NR_CPUS; i++ )
mwilli2@1284 551 {
kaf24@1958 552 schedule_data[i].sched_priv = xmalloc(sizeof(struct at_cpu_info));
kaf24@1489 553 if ( schedule_data[i].sched_priv == NULL )
mwilli2@1284 554 return -1;
gm281@2564 555 INIT_LIST_HEAD(WAITQ(i));
gm281@2564 556 INIT_LIST_HEAD(RUNQ(i));
mwilli2@1284 557 }
mwilli2@1284 558
mwilli2@1284 559 return 0;
mwilli2@1284 560 }
mwilli2@1284 561
mwilli2@1284 562
mwilli2@1284 563 /* print relevant per-domain info for a run queue dump */
kaf24@1543 564 static void at_dump_runq_el(struct domain *p)
mwilli2@1284 565 {
mwilli2@1284 566 printk("lastschd = %llu, xtratime = %d ",
mwilli2@1284 567 p->lastschd, DOM_INFO(p)->xtratime);
mwilli2@1284 568 }
mwilli2@1284 569
mwilli2@1284 570
gm281@2564 571 /* dump relevant per-cpu state for a run queue dump */
gm281@2564 572 static void at_dump_cpu_state(int cpu)
gm281@2564 573 {
kaf24@3568 574 struct list_head *queue;
gm281@2564 575 int loop = 0;
gm281@2564 576 struct at_dom_info *d_inf;
gm281@2564 577 struct domain *d;
gm281@2564 578
gm281@2564 579 queue = RUNQ(cpu);
gm281@2564 580 printk("\nRUNQUEUE rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
kaf24@3568 581 (unsigned long) queue->next, (unsigned long) queue->prev);
gm281@2564 582
kaf24@3568 583 list_for_each_entry ( d_inf, queue, run_list )
gm281@2564 584 {
gm281@2564 585 d = d_inf->owner;
kaf24@2748 586 printk("%3d: %d has=%c ", loop++, d->id,
kaf24@3568 587 test_bit(DF_RUNNING, &d->flags) ? 'T':'F');
gm281@2564 588 at_dump_runq_el(d);
gm281@2564 589 printk("c=0x%X%08X\n", (u32)(d->cpu_time>>32), (u32)d->cpu_time);
gm281@2564 590 printk(" l: %lx n: %lx p: %lx\n",
kaf24@3568 591 (unsigned long)&d_inf->run_list,
kaf24@3568 592 (unsigned long)d_inf->run_list.next,
kaf24@3568 593 (unsigned long)d_inf->run_list.prev);
gm281@2564 594 }
gm281@2564 595
gm281@2564 596
gm281@2564 597 queue = WAITQ(cpu);
gm281@2564 598 printk("\nWAITQUEUE rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
kaf24@3568 599 (unsigned long) queue->next, (unsigned long) queue->prev);
gm281@2564 600
kaf24@3568 601 list_for_each_entry ( d_inf, queue, waitq )
gm281@2564 602 {
gm281@2564 603 d = d_inf->owner;
kaf24@2748 604 printk("%3d: %d has=%c ", loop++, d->id,
kaf24@3568 605 test_bit(DF_RUNNING, &d->flags) ? 'T':'F');
gm281@2564 606 at_dump_runq_el(d);
gm281@2564 607 printk("c=0x%X%08X\n", (u32)(d->cpu_time>>32), (u32)d->cpu_time);
gm281@2564 608 printk(" l: %lx n: %lx p: %lx\n",
kaf24@3568 609 (unsigned long)&d_inf->waitq,
kaf24@3568 610 (unsigned long)d_inf->waitq.next,
kaf24@3568 611 (unsigned long)d_inf->waitq.prev);
gm281@2564 612 }
gm281@2564 613
gm281@2564 614 }
gm281@2564 615
mwilli2@1284 616 /* set or fetch domain scheduling parameters */
kaf24@1543 617 static int at_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd)
mwilli2@1284 618 {
mwilli2@1284 619 if ( cmd->direction == SCHED_INFO_PUT )
mwilli2@1284 620 {
mwilli2@1345 621 /* sanity checking! */
mwilli2@1345 622 if( cmd->u.atropos.latency > cmd->u.atropos.nat_period
mwilli2@1345 623 || cmd->u.atropos.latency == 0
mwilli2@1345 624 || cmd->u.atropos.nat_slice > cmd->u.atropos.nat_period )
mwilli2@1345 625 return -EINVAL;
mwilli2@1345 626
mwilli2@1345 627 DOM_INFO(p)->nat_period = cmd->u.atropos.nat_period;
mwilli2@1345 628 DOM_INFO(p)->nat_slice = cmd->u.atropos.nat_slice;
mwilli2@1284 629 DOM_INFO(p)->latency = cmd->u.atropos.latency;
mwilli2@1284 630 DOM_INFO(p)->xtratime = !!cmd->u.atropos.xtratime;
mwilli2@1284 631 }
mwilli2@1284 632 else if ( cmd->direction == SCHED_INFO_GET )
mwilli2@1284 633 {
mwilli2@1345 634 cmd->u.atropos.nat_period = DOM_INFO(p)->nat_period;
mwilli2@1345 635 cmd->u.atropos.nat_slice = DOM_INFO(p)->nat_slice;
mwilli2@1284 636 cmd->u.atropos.latency = DOM_INFO(p)->latency;
mwilli2@1284 637 cmd->u.atropos.xtratime = DOM_INFO(p)->xtratime;
mwilli2@1284 638 }
mwilli2@1284 639
mwilli2@1284 640 return 0;
mwilli2@1284 641 }
mwilli2@1284 642
mwilli2@1284 643 /* free memory associated with a task */
kaf24@1543 644 static void at_free_task(struct domain *p)
mwilli2@1284 645 {
iap10@3651 646 xfree( DOM_INFO(p) );
mwilli2@1284 647 }
mwilli2@1284 648
mwilli2@1345 649
mwilli2@1284 650 /* print decoded domain private state value (if known) */
mwilli2@1284 651 static int at_prn_state(int state)
mwilli2@1284 652 {
mwilli2@1284 653 int ret = 0;
mwilli2@1284 654
mwilli2@1284 655 switch(state)
mwilli2@1284 656 {
mwilli2@1284 657 case ATROPOS_TASK_UNBLOCKED:
mwilli2@1284 658 printk("Unblocked");
mwilli2@1284 659 break;
mwilli2@1284 660 case ATROPOS_TASK_WAIT:
mwilli2@1284 661 printk("Wait");
mwilli2@1284 662 break;
mwilli2@1284 663 default:
mwilli2@1284 664 ret = -1;
mwilli2@1284 665 }
mwilli2@1284 666
mwilli2@1284 667 return ret;
mwilli2@1284 668 }
mwilli2@1284 669
mwilli2@1284 670 struct scheduler sched_atropos_def = {
mwilli2@1284 671 .name = "Atropos Soft Real Time Scheduler",
mwilli2@1284 672 .opt_name = "atropos",
mwilli2@1284 673 .sched_id = SCHED_ATROPOS,
mwilli2@1284 674 .init_scheduler = at_init_scheduler,
gm281@2564 675 .init_idle_task = at_init_idle_task,
mwilli2@1284 676 .alloc_task = at_alloc_task,
mwilli2@1284 677 .add_task = at_add_task,
mwilli2@1284 678 .free_task = at_free_task,
gm281@2564 679 .wake = unblock,
gm281@2564 680 .sleep = block,
mwilli2@1284 681 .do_schedule = ksched_scheduler,
mwilli2@1284 682 .adjdom = at_adjdom,
mwilli2@1284 683 .dump_cpu_state = at_dump_cpu_state,
mwilli2@1284 684 .prn_state = at_prn_state,
mwilli2@1284 685 };