include/linux/ckrm_sched.h

   1 /* include/linux/ckrm_sched.h - Supports CKRM scheduling
   2  *
   3  * Copyright (C) Haoqiang Zheng,  IBM Corp. 2004
   4  * Copyright (C) Hubertus Franke,  IBM Corp. 2004
   5  *
   6  * Latest version, more details at http://ckrm.sf.net
   7  *
   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.
  12  *
  13  */
  14
  15 #ifndef _CKRM_SCHED_H
  16 #define _CKRM_SCHED_H
  17
  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)
  20
  21 #include <linux/sched.h>
  22 #include <linux/ckrm_rc.h>
  23 #include <linux/ckrm_classqueue.h>
  24
  25 //update every second
  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
  29
  30 #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
  31 struct prio_array {
  32         int nr_active;
  33         unsigned long bitmap[BITMAP_SIZE];
  34         struct list_head queue[MAX_PRIO];
  35 };
  36
  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
  41         CVT_t uncounted_cvt;
  42         unsigned long long uncounted_ns;
  43
  44         prio_array_t *active, *expired, arrays[2];
  45         /*
  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
  49          */
  50         unsigned long expired_timestamp;
  51
  52         /*
  53          * highest priority of tasks in active
  54          * initialized to be MAX_PRIO
  55          * updated on enqueue, dequeue
  56          */
  57         int top_priority;
  58         CVT_t local_cvt;        // snapshot of local_cvt, update on every loadbalance
  59         unsigned long magic;    //for debugging
  60 };
  61
  62 /**
  63  * @last_sleep: the last time it sleeps, last_sleep = 0 when not sleeping
  64  */
  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 */
  70 };
  71
  72 /**
  73  * ckrm_cpu_class_stat - cpu usage statistics maintained for each class
  74  *
  75  */
  76 struct ckrm_cpu_class_stat {
  77         spinlock_t stat_lock;
  78
  79         unsigned long long total_ns;    /*how much nano-secs it has consumed */
  80
  81         struct ckrm_cpu_class_local_stat local_stats[NR_CPUS];
  82         unsigned long cpu_demand;
  83
  84         /*temp stat used by cpu monitor */
  85         int effective_guarantee;
  86         int effective_limit;
  87         int glut;               //true or false
  88         /*
  89          * effective_share: for both default class and its children
  90          * self_effective_share: just for the default class
  91          */
  92         int effective_share;
  93         int self_effective_share;
  94 };
  95
  96 typedef struct ckrm_cpu_class_stat ckrm_stat_t;
  97
  98 /*
  99  * manages the class status
 100  * there should be only one instance of this object for each class in the whole system
 101  */
 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
 111 };
 112
 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)
 116 #else
 117 #define rq_active(p,rq)   (rq->active)
 118 #define rq_expired(p,rq)  (rq->expired)
 119 #endif
 120
 121 //#define cpu_class_weight(cls) (cls->shares.my_guarantee)
 122 #define cpu_class_weight(cls) (cls->stat.self_effective_share)
 123
 124 #define bpt_queue(cpu) (& (cpu_rq(cpu)->classqueue) )
 125 CVT_t get_min_cvt(int cpu);
 126
 127 struct classqueue_struct *get_cpu_classqueue(int cpu);
 128
 129 extern struct ckrm_cpu_class default_cpu_class_obj;
 130 #define default_cpu_class (&default_cpu_class_obj)
 131
 132 #define local_queue_nr_running(local_queue) \
 133              (local_queue->active->nr_active + local_queue->expired->nr_active)
 134
 135 static inline struct ckrm_local_runqueue *
 136 get_ckrm_local_runqueue(struct ckrm_cpu_class*cls, int cpu)
 137 {
 138         return &(cls->local_queues[cpu]);
 139 }
 140
 141 static inline struct ckrm_local_runqueue *get_task_class_queue(struct task_struct *p)
 142 {
 143         return &(p->cpu_class->local_queues[task_cpu(p)]);
 144 }
 145
 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)
 148
 149 /* some additional interfaces exported from sched.c */
 150 struct runqueue;
 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;
 158
 159 /*functions exported by ckrm_cpu_class.c*/
 160 int __init init_ckrm_sched_res(void);
 161 void init_cpu_classes(void);
 162
 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);
 170
 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])
 173
 174 /**
 175  * get_effective_prio: return the effective priority of a class local queue
 176  *
 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
 183  */
 184 static inline int get_effective_prio(struct ckrm_local_runqueue * lcq)
 185 {
 186         int prio;
 187
 188         // cumulative usage
 189         prio = lcq->local_cvt >> CLASS_BONUS_RATE;
 190         // queue urgency
 191         prio += lcq->top_priority >> PRIORITY_BONUS_RATE;
 192
 193         return prio;
 194 }
 195
 196 /**
 197  * update_class_priority:
 198  *
 199  * called whenever cvt or top_priority changes
 200  *
 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
 208  *      -- schedule
 209  *   -- update_global_cvt
 210  */
 211 static inline void update_class_priority(struct ckrm_local_runqueue *local_rq)
 212 {
 213         int effective_prio = get_effective_prio(local_rq);
 214         classqueue_update_prio(local_rq->classqueue,
 215                                &local_rq->classqueue_linkobj,
 216                                effective_prio);
 217 }
 218
 219 /*
 220  *  set the new top priority and reposition the queue
 221  *  called when: task enqueue/dequeue and queue switch
 222  */
 223 static inline void set_top_priority(struct ckrm_local_runqueue *class_queue,
 224                                     int new_priority)
 225 {
 226         class_queue->top_priority = new_priority;
 227         update_class_priority(class_queue);
 228 }
 229
 230 static inline void class_enqueue_task(struct task_struct *p,
 231                                       prio_array_t * array)
 232 {
 233         struct ckrm_local_runqueue *queue;
 234         int effective_prio;
 235
 236         queue = get_task_class_queue(p);
 237
 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);
 244         }
 245
 246         if ((p->prio < queue->top_priority) && (array == queue->active))
 247                 set_top_priority(queue, p->prio);
 248
 249 }
 250
 251 static inline void class_dequeue_task(struct task_struct *p,
 252                                       prio_array_t * array)
 253 {
 254         struct ckrm_local_runqueue *queue = get_task_class_queue(p);
 255
 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,
 260                                                p->prio));
 261 }
 262
 263 /*
 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
 266  */
 267 static inline void update_local_cvt(struct task_struct *p, unsigned long nsec)
 268 {
 269         struct ckrm_local_runqueue *class_queue = get_task_class_queue(p);
 270         struct ckrm_cpu_class *cls = class_queue->cpu_class;
 271
 272         unsigned long cvt_inc = nsec / cpu_class_weight(cls);
 273
 274         class_queue->local_cvt += cvt_inc;
 275         class_queue->uncounted_cvt += cvt_inc;
 276
 277         class_queue->uncounted_ns += nsec;
 278         update_class_priority(class_queue);
 279 }
 280
 281 /*
 282  * called during loadbalancing
 283  * to charge the class with locally accumulated cvt
 284  */
 285 void update_global_cvts(int this_cpu);
 286
 287 /**
 288  *
 289  */
 290 static inline int class_preempts_curr(struct task_struct * p, struct task_struct* curr)
 291 {
 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);
 294
 295         return (class_compare_prio(node1,node2) < 0);
 296 }
 297 #endif