kernel/ckrm_classqueue.c

   1 /* kernel/ckrm_classqueue.c : implements the class queue
   2  *
   3  * Copyright (C) Haoqiang Zheng, IBM Corp. 2003
   4  *           (C) Hubertus Franke, IBM Corp. 2003
   5  *
   6  * Class queue functionality for CKRM cpu controller
   7  *
   8  * Latest version, more details at http://ckrm.sf.net
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2 of the License, or
  13  * (at your option) any later version.
  14  *
  15  */
  16
  17 /* Changes
  18  *
  19  * Aug 28, 2003
  20  *        Created.
  21  * July 08, 2004
  22  *        classqueue now has a fixed size
  23  *        major clean up
  24  *        function/structure names are changed to more intuitive ones
  25  */
  26 #include <linux/sched.h>
  27 #include <linux/ckrm_classqueue.h>
  28
  29 #define cq_nr_member(cq) (cq->array.nr_active)
  30 #define CLASSQUEUE_MASK   (CLASSQUEUE_SIZE - 1)
  31
  32 /**
  33  * get_node_index -
  34  *      translate the logical priority to the real index in the queue
  35  *
  36  * validate the position
  37  * a valid prio is [cq->base,cq->base + size -1]
  38  * check whether node is supposed to be enqeued beyond above window and
  39  * if so set the need_repos flag
  40  */
  41 static inline unsigned long get_node_index(struct classqueue_struct *cq,
  42                                            cq_node_t * node)
  43 {
  44         unsigned long index;
  45         int max_prio;
  46
  47         if (!cq_nr_member(cq))
  48                 return 0;
  49
  50         max_prio = cq->base + (CLASSQUEUE_SIZE - 1);
  51         if (unlikely(node->prio > max_prio)) {
  52                 node->real_prio = node->prio;
  53                 node->prio = max_prio;
  54                 node->need_repos = 1;
  55         } else
  56                 node->need_repos = 0;
  57
  58         if (unlikely(node->prio < cq->base))
  59                 node->prio = cq->base;
  60
  61         index = (cq->base_offset + (node->prio - cq->base)) ;
  62         return ( index & CLASSQUEUE_MASK );   // ensure its in limits
  63 }
  64
  65 /**
  66  * initialize a class queue object
  67  */
  68 int classqueue_init(struct classqueue_struct *cq, int enabled)
  69 {
  70         int i;
  71         struct cq_prio_array *array;
  72
  73         array = &cq->array;
  74         for (i = 0; i < CLASSQUEUE_SIZE; i++) {
  75                 INIT_LIST_HEAD(array->queue + i);
  76                 __clear_bit(i, array->bitmap);
  77         }
  78         // delimiter for bitsearch
  79         __set_bit(CLASSQUEUE_SIZE, array->bitmap);
  80         array->nr_active = 0;
  81
  82         cq->base = 0;
  83         cq->base_offset = 0;
  84         cq->enabled = enabled;
  85
  86         return 0;
  87 }
  88
  89 /**
  90  *classqueue_enqueue - add the class to classqueue based on its prio
  91  */
  92 void classqueue_enqueue(struct classqueue_struct *cq,
  93                         cq_node_t * node, int prio)
  94 {
  95         int index;
  96
  97         //get real index
  98         if (cq_nr_member(cq)) {
  99                 index = get_node_index(cq, node);
 100         } else {                //the first one
 101                 cq->base = prio;
 102                 cq->base_offset = 0;
 103                 index = 0;
 104         }
 105
 106         //add to the queue
 107         list_add(&(node->list), &cq->array.queue[index]);
 108         __set_bit(index, cq->array.bitmap);
 109         cq->array.nr_active++;
 110
 111         node->index = index;
 112         node->prio = prio;
 113 }
 114
 115 void classqueue_dequeue(struct classqueue_struct *cq, cq_node_t * node)
 116 {
 117         //delete from queue
 118         list_del_init(&(node->list));
 119         cq->array.nr_active--;
 120
 121         //check clear the bitmap
 122         if (list_empty(&cq->array.queue[node->index]))
 123                 __clear_bit(node->index, cq->array.bitmap);
 124 }
 125
 126 void classqueue_update_prio(struct classqueue_struct *cq,
 127                             cq_node_t * node, int new_pos)
 128 {
 129         int index;
 130
 131         if (! cls_in_classqueue(node))
 132                 return;
 133
 134         node->prio = new_pos;
 135         index = get_node_index(cq, node);
 136
 137         //remove from the original position
 138         list_del_init(&(node->list));
 139         if (list_empty(&cq->array.queue[node->index]))
 140                 __clear_bit(node->index, cq->array.bitmap);
 141
 142         //add to new positon, round robin for classes with same priority
 143         list_add_tail(&(node->list), &cq->array.queue[index]);
 144         __set_bit(index, cq->array.bitmap);
 145         node->index = index;
 146 }
 147
 148
 149 static inline void __classqueue_update_base(struct classqueue_struct *cq,
 150                                             int new_base)
 151 {
 152         int max_prio;
 153         if (unlikely(new_base <= cq->base)) // base will never move back
 154                 return;
 155         if (unlikely(!cq_nr_member(cq))) {
 156                 cq->base_offset = 0;
 157                 cq->base = new_base;        // is this necessary ??
 158                 return;
 159         }
 160
 161         max_prio = cq->base + (CLASSQUEUE_SIZE - 1);
 162         if (unlikely(new_base > max_prio))
 163                 new_base = max_prio;
 164
 165         cq->base_offset = (cq->base_offset + (new_base - cq->base)) & CLASSQUEUE_MASK;
 166         cq->base = new_base;
 167 }
 168
 169 /**
 170  *classqueue_get_min_prio: return the priority of the last node in queue
 171  *
 172  * this function can be called without runqueue lock held
 173  * return 0 if there's nothing in the queue
 174  */
 175 static inline int classqueue_get_min_prio(struct classqueue_struct *cq)
 176 {
 177         cq_node_t *result = NULL;
 178         int pos;
 179
 180         /*
 181          * search over the bitmap to get the first class in the queue
 182          */
 183         pos = find_next_bit(cq->array.bitmap, CLASSQUEUE_SIZE, cq->base_offset);
 184         //do circular search from the beginning
 185         if (pos >= CLASSQUEUE_SIZE)
 186                 pos = find_first_bit(cq->array.bitmap, CLASSQUEUE_SIZE);
 187
 188         if (pos < CLASSQUEUE_SIZE) {
 189                 result = list_entry(cq->array.queue[pos].next, cq_node_t, list);
 190                 if (list_empty(&cq->array.queue[pos]))
 191                         result = NULL;
 192         }
 193         if (result)
 194                 return result->prio;
 195         else
 196                 return 0;
 197 }
 198
 199 /**
 200  * this function must be called with runqueue lock held
 201  */
 202 cq_node_t *classqueue_get_head(struct classqueue_struct *cq)
 203 {
 204         cq_node_t *node;
 205         int pos;
 206         int index;
 207         int new_base;
 208
 209 search_again:
 210         node = NULL;
 211         /*
 212          * search over the bitmap to get the first class in the queue
 213          */
 214         pos = find_next_bit(cq->array.bitmap, CLASSQUEUE_SIZE, cq->base_offset);
 215         //do circular search from the beginning
 216         if (pos >= CLASSQUEUE_SIZE)
 217                 pos = find_first_bit(cq->array.bitmap, CLASSQUEUE_SIZE);
 218
 219         if (pos < CLASSQUEUE_SIZE) {
 220                 //BUG_ON(list_empty(&cq->array.queue[pos]));
 221                 node = list_entry(cq->array.queue[pos].next, cq_node_t, list);
 222         }
 223
 224         //check if the node need to be repositioned
 225         if (likely(! node || ! node->need_repos))
 226                 return node;
 227
 228         // We need to reposition this node in the class queue
 229         // BUG_ON(node->prio == node->real_prio);
 230
 231         //remove from the original position
 232         list_del_init(&(node->list));
 233         if (list_empty(&cq->array.queue[node->index]))
 234           __clear_bit(node->index, cq->array.bitmap);
 235
 236         new_base = classqueue_get_min_prio(cq);
 237         node->prio = node->real_prio;
 238
 239         if (! new_base)
 240                 new_base  = node->real_prio;
 241         else if (node->real_prio < new_base)
 242                 new_base  = node->real_prio;
 243         __classqueue_update_base(cq,new_base);
 244
 245         index = get_node_index(cq, node);
 246         //add to new positon, round robin for classes with same priority
 247         list_add_tail(&(node->list), &cq->array.queue[index]);
 248         __set_bit(index, cq->array.bitmap);
 249         node->index = index;
 250
 251         goto search_again;
 252 }
 253
 254 /**
 255  * Moving the end of queue forward
 256  * the new_base here is logical, we need to translate to the abosule position
 257  */
 258 void classqueue_update_base(struct classqueue_struct *cq)
 259 {
 260         int new_base;
 261
 262         if (! cq_nr_member(cq)) {
 263                 cq->base = 0;
 264                 cq->base_offset = 0;
 265                 return;
 266         }
 267
 268         new_base = classqueue_get_min_prio(cq);
 269         __classqueue_update_base(cq,new_base);
 270 }