debuggers.hg

view xen/common/sched_atropos.c @ 3705:4294cfa9fad3

bitkeeper revision 1.1159.212.95 (4204aa0ee0re5Xx1zWrJ9ejxzgRs3w)

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