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
  31 /**
  32  * get_index - translate the logical priority to the real index in the queue
  33  *
  34  * validate the position
  35  * a valid prio is [cq->base,cq->base + size -1]
  36  */
  37 static inline unsigned long get_index(struct classqueue_struct *cq, int *prio)
  38 {
  39         unsigned long index;
  40         int max_prio;
  41
  42         if (!cq_nr_member(cq))
  43                 return 0;
  44
  45         max_prio = cq->base + (CLASSQUEUE_SIZE - 1);
  46         if (*prio > max_prio)
  47                 *prio = max_prio;
  48         if (*prio < cq->base)
  49                 *prio = cq->base;
  50
  51         index = (cq->base_offset + (*prio - cq->base)) ;
  52         if (index >= CLASSQUEUE_SIZE)
  53                 index -= CLASSQUEUE_SIZE;
  54
  55         return index;
  56 }
  57
  58 /**
  59  * initialize a class queue object
  60  */
  61 int classqueue_init(struct classqueue_struct *cq)
  62 {
  63         int i;
  64         struct cq_prio_array *array;
  65
  66         array = &cq->array;
  67         for (i = 0; i < CLASSQUEUE_SIZE; i++) {
  68                 INIT_LIST_HEAD(array->queue + i);
  69                 __clear_bit(i, array->bitmap);
  70         }
  71         // delimiter for bitsearch
  72         __set_bit(CLASSQUEUE_SIZE, array->bitmap);
  73         array->nr_active = 0;
  74
  75         cq->base = 0;
  76         cq->base_offset = -1;   //not valid yet
  77
  78         return 0;
  79 }
  80
  81 /**
  82  *classqueue_enqueue - add the class to classqueue based on its prio
  83  */
  84 void classqueue_enqueue(struct classqueue_struct *cq,
  85                         cq_node_t * node, int prio)
  86 {
  87         int index;
  88
  89         //get real index
  90         if (cq_nr_member(cq)) {
  91                 index = get_index(cq, &prio);
  92         } else {                //the first one
  93                 cq->base = prio;
  94                 cq->base_offset = 0;
  95                 index = 0;
  96         }
  97
  98         //add to the queue
  99         list_add(&(node->list), &cq->array.queue[index]);
 100         __set_bit(index, cq->array.bitmap);
 101         cq->array.nr_active++;
 102
 103         node->index = index;
 104         node->prio = prio;
 105 }
 106
 107 void classqueue_dequeue(struct classqueue_struct *cq, cq_node_t * node)
 108 {
 109         //delete from queue
 110         list_del_init(&(node->list));
 111         cq->array.nr_active--;
 112
 113         //check clear the bitmap
 114         if (list_empty(&cq->array.queue[node->index]))
 115                 __clear_bit(node->index, cq->array.bitmap);
 116 }
 117
 118 void classqueue_update_prio(struct classqueue_struct *cq,
 119                             cq_node_t * node, int new_pos)
 120 {
 121         int index;
 122
 123         if (! cls_in_classqueue(node))
 124                 return;
 125
 126         index = get_index(cq, &new_pos);
 127         node->prio = new_pos;
 128
 129         //remove from the original position
 130         list_del_init(&(node->list));
 131         if (list_empty(&cq->array.queue[node->index]))
 132                 __clear_bit(node->index, cq->array.bitmap);
 133
 134         //add to new positon, round robin for classes with same priority
 135         list_add_tail(&(node->list), &cq->array.queue[index]);
 136         __set_bit(index, cq->array.bitmap);
 137         node->index = index;
 138 }
 139
 140 /**
 141  *classqueue_get_min_prio: return the priority of the last node in queue
 142  *
 143  * this function can be called without runqueue lock held
 144  */
 145 static inline int classqueue_get_min_prio(struct classqueue_struct *cq)
 146 {
 147         cq_node_t *result = NULL;
 148         int pos;
 149
 150         /*
 151          * search over the bitmap to get the first class in the queue
 152          */
 153         pos = find_next_bit(cq->array.bitmap, CLASSQUEUE_SIZE, cq->base_offset);
 154         //do circular search from the beginning
 155         if (pos >= CLASSQUEUE_SIZE)
 156                 pos = find_first_bit(cq->array.bitmap, CLASSQUEUE_SIZE);
 157
 158         if (pos < CLASSQUEUE_SIZE) {
 159                 result = list_entry(cq->array.queue[pos].next, cq_node_t, list);
 160                 if (list_empty(&cq->array.queue[pos]))
 161                         result = NULL;
 162         }
 163         if (result)
 164                 return result->prio;
 165         else
 166                 return 0;
 167 }
 168
 169 /**
 170  * this function must be called with runqueue lock held
 171  */
 172 cq_node_t *classqueue_get_head(struct classqueue_struct *cq)
 173 {
 174         cq_node_t *result = NULL;
 175         int pos;
 176
 177         /*
 178          * search over the bitmap to get the first class in the queue
 179          */
 180         pos = find_next_bit(cq->array.bitmap, CLASSQUEUE_SIZE, cq->base_offset);
 181         //do circular search from the beginning
 182         if (pos >= CLASSQUEUE_SIZE)
 183                 pos = find_first_bit(cq->array.bitmap, CLASSQUEUE_SIZE);
 184
 185         if (pos < CLASSQUEUE_SIZE) {
 186                 BUG_ON(list_empty(&cq->array.queue[pos]));
 187                 result = list_entry(cq->array.queue[pos].next, cq_node_t, list);
 188         }
 189         return result;
 190 }
 191
 192 /**
 193  * Moving the end of queue forward
 194  * the new_base here is logical, we need to translate to the abosule position
 195  */
 196 void classqueue_update_base(struct classqueue_struct *cq)
 197 {
 198         int new_base;
 199
 200         if (! cq_nr_member(cq)) {
 201                 cq->base_offset = -1;   //not defined
 202                 return;
 203         }
 204
 205         new_base = classqueue_get_min_prio(cq);
 206
 207         if (new_base > cq->base) {
 208                 cq->base_offset = get_index(cq, &new_base);
 209                 cq->base = new_base;
 210         }
 211 }