1 /* include/linux/ckrm_sched.h - Supports CKRM scheduling
3 * Copyright (C) Haoqiang Zheng, IBM Corp. 2004
4 * Copyright (C) Hubertus Franke, IBM Corp. 2004
6 * Latest version, more details at http://ckrm.sf.net
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
18 #define CC_BUG_ON_DO(cond,action) do { if (cond) action; BUG_ON(cond); } while(0)
19 #define CC_BUG_ON(cond) BUG_ON(cond)
21 #include <linux/sched.h>
22 #include <linux/ckrm_rc.h>
23 #include <linux/ckrm_classqueue.h>
26 #define CVT_UPDATE_TICK (1*HZ/1 ?: 1)
27 #define CLASS_BONUS_RATE 22 // shift from ns to increase class bonus
28 #define PRIORITY_BONUS_RATE 0 // ?? Hubertus
30 #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
33 unsigned long bitmap[BITMAP_SIZE];
34 struct list_head queue[MAX_PRIO];
37 struct ckrm_local_runqueue {
38 cq_node_t classqueue_linkobj; /*links in classqueue */
39 struct ckrm_cpu_class *cpu_class; // class it belongs to
40 struct classqueue_struct *classqueue; // classqueue it belongs tow
42 unsigned long long uncounted_ns;
44 prio_array_t *active, *expired, arrays[2];
46 set to 0 on init, become null or array switch
47 set to jiffies whenever an non-interactive job expires
48 reset to jiffies if expires
50 unsigned long expired_timestamp;
53 * highest priority of tasks in active
54 * initialized to be MAX_PRIO
55 * updated on enqueue, dequeue
58 CVT_t local_cvt; // snapshot of local_cvt, update on every loadbalance
59 unsigned long magic; //for debugging
63 * @last_sleep: the last time it sleeps, last_sleep = 0 when not sleeping
65 struct ckrm_cpu_class_local_stat {
66 unsigned long long run;
67 unsigned long long total;
68 unsigned long long last_sleep;
69 unsigned long cpu_demand; /*estimated cpu demand */
73 * ckrm_cpu_class_stat - cpu usage statistics maintained for each class
76 struct ckrm_cpu_class_stat {
79 unsigned long long total_ns; /*how much nano-secs it has consumed */
81 struct ckrm_cpu_class_local_stat local_stats[NR_CPUS];
82 unsigned long cpu_demand;
84 /*temp stat used by cpu monitor */
85 int effective_guarantee;
87 int glut; //true or false
89 * effective_share: for both default class and its children
90 * self_effective_share: just for the default class
93 int self_effective_share;
96 typedef struct ckrm_cpu_class_stat ckrm_stat_t;
99 * manages the class status
100 * there should be only one instance of this object for each class in the whole system
102 struct ckrm_cpu_class {
103 struct ckrm_core_class *core;
104 struct ckrm_core_class *parent;
105 struct ckrm_shares shares;
106 spinlock_t cnt_lock; // always grab parent's lock first and then child's
107 CVT_t global_cvt; // total cummulative virtual time
108 struct ckrm_cpu_class_stat stat;
109 struct list_head links; // for linking up in cpu classes
110 struct ckrm_local_runqueue local_queues[NR_CPUS]; // runqueues
113 #if CONFIG_CKRM_CPU_SCHEDULE
114 #define rq_active(p,rq) (get_task_class_queue(p)->active)
115 #define rq_expired(p,rq) (get_task_class_queue(p)->expired)
117 #define rq_active(p,rq) (rq->active)
118 #define rq_expired(p,rq) (rq->expired)
121 //#define cpu_class_weight(cls) (cls->shares.my_guarantee)
122 #define cpu_class_weight(cls) (cls->stat.self_effective_share)
124 #define bpt_queue(cpu) (& (cpu_rq(cpu)->classqueue) )
125 CVT_t get_min_cvt(int cpu);
127 struct classqueue_struct *get_cpu_classqueue(int cpu);
129 extern struct ckrm_cpu_class default_cpu_class_obj;
130 #define default_cpu_class (&default_cpu_class_obj)
132 #define local_queue_nr_running(local_queue) \
133 (local_queue->active->nr_active + local_queue->expired->nr_active)
135 static inline struct ckrm_local_runqueue *
136 get_ckrm_local_runqueue(struct ckrm_cpu_class*cls, int cpu)
138 return &(cls->local_queues[cpu]);
141 static inline struct ckrm_local_runqueue *get_task_class_queue(struct task_struct *p)
143 return &(p->cpu_class->local_queues[task_cpu(p)]);
146 #define task_list_entry(list) list_entry(list,struct task_struct,run_list)
147 #define class_list_entry(list) list_entry(list,struct ckrm_local_runqueue,classqueue_linkobj)
149 /* some additional interfaces exported from sched.c */
151 void dequeue_task(struct task_struct *p, prio_array_t * array);
152 void enqueue_task(struct task_struct *p, prio_array_t * array);
153 struct runqueue *task_rq_lock(task_t * p, unsigned long *flags);
154 void task_rq_unlock(struct runqueue *rq, unsigned long *flags);
155 extern spinlock_t cvt_lock;
156 extern rwlock_t class_list_lock;
157 extern struct list_head active_cpu_classes;
159 /*functions exported by ckrm_cpu_class.c*/
160 int __init init_ckrm_sched_res(void);
161 void init_cpu_classes(void);
163 /*functions exported by ckrm_cpu_monitor.c*/
164 void ckrm_cpu_monitor(void);
165 void ckrm_cpu_stat_init(struct ckrm_cpu_class_stat *stat);
166 #define CPU_DEMAND_ENQUEUE 0
167 #define CPU_DEMAND_DEQUEUE 1
168 #define CPU_DEMAND_DESCHEDULE 2
169 void cpu_demand_event(struct ckrm_cpu_class_local_stat* local_stat, int event, unsigned long long len);
171 #define get_task_local_stat(p) (&(p)->cpu_class->stat.local_stats[task_cpu(p)])
172 #define get_rq_local_stat(lrq,cpu) (&(lrq)->cpu_class->stat.local_stats[cpu])
175 * get_effective_prio: return the effective priority of a class local queue
177 * class priority = progress * a + urgency * b
178 * progress = queue cvt
179 * urgency = queue top priority
180 * a and b are scaling factors
181 * currently, prio increases by 1 if either: top_priority increase by one
182 * or, local_cvt increases by 4ms
184 static inline int get_effective_prio(struct ckrm_local_runqueue * lcq)
189 prio = lcq->local_cvt >> CLASS_BONUS_RATE;
191 prio += lcq->top_priority >> PRIORITY_BONUS_RATE;
197 * update_class_priority:
199 * called whenever cvt or top_priority changes
201 * internal: (calling structure)
202 * update_class_priority
203 * -- set_top_priority
204 * -- class_enqueue_task
205 * -- class_dequeue_task
206 * -- rq_get_next_task (queue switch)
207 * -- update_local_cvt
209 * -- update_global_cvt
211 static inline void update_class_priority(struct ckrm_local_runqueue *local_rq)
213 int effective_prio = get_effective_prio(local_rq);
214 classqueue_update_prio(local_rq->classqueue,
215 &local_rq->classqueue_linkobj,
220 * set the new top priority and reposition the queue
221 * called when: task enqueue/dequeue and queue switch
223 static inline void set_top_priority(struct ckrm_local_runqueue *class_queue,
226 class_queue->top_priority = new_priority;
227 update_class_priority(class_queue);
230 static inline void class_enqueue_task(struct task_struct *p,
231 prio_array_t * array)
233 struct ckrm_local_runqueue *queue;
236 queue = get_task_class_queue(p);
238 if (! cls_in_classqueue(&queue->classqueue_linkobj)) {
239 cpu_demand_event(get_task_local_stat(p),CPU_DEMAND_ENQUEUE,0);
240 /*make sure the cvt of this class is up to date*/
241 queue->local_cvt = get_min_cvt(task_cpu(p));
242 effective_prio = get_effective_prio(queue);
243 classqueue_enqueue(queue->classqueue, &queue->classqueue_linkobj, effective_prio);
246 if ((p->prio < queue->top_priority) && (array == queue->active))
247 set_top_priority(queue, p->prio);
251 static inline void class_dequeue_task(struct task_struct *p,
252 prio_array_t * array)
254 struct ckrm_local_runqueue *queue = get_task_class_queue(p);
256 if ((array == queue->active) && (p->prio == queue->top_priority)
257 && list_empty(&(array->queue[p->prio])))
258 set_top_priority(queue,
259 find_next_bit(array->bitmap, MAX_PRIO,
264 * called after a task is switched out. Update the local cvt accounting
265 * we need to stick with long instead of long long due to nonexistent 64-bit division
267 static inline void update_local_cvt(struct task_struct *p, unsigned long nsec)
269 struct ckrm_local_runqueue *class_queue = get_task_class_queue(p);
270 struct ckrm_cpu_class *cls = class_queue->cpu_class;
272 unsigned long cvt_inc = nsec / cpu_class_weight(cls);
274 class_queue->local_cvt += cvt_inc;
275 class_queue->uncounted_cvt += cvt_inc;
277 class_queue->uncounted_ns += nsec;
278 update_class_priority(class_queue);
282 * called during loadbalancing
283 * to charge the class with locally accumulated cvt
285 void update_global_cvts(int this_cpu);
290 static inline int class_preempts_curr(struct task_struct * p, struct task_struct* curr)
292 struct cq_node_struct* node1 = &(get_task_class_queue(p)->classqueue_linkobj);
293 struct cq_node_struct* node2 = &(get_task_class_queue(curr)->classqueue_linkobj);
295 return (class_compare_prio(node1,node2) < 0);