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
 138         node->index = index;
 139 }
 140
 141 cq_node_t *classqueue_get_head(struct classqueue_struct *cq)
 142 {
 143         cq_node_t *result = NULL;
 144         int pos;
 145
 146         /*
 147          * search over the bitmap to get the first class in the queue
 148          */
 149         pos = find_next_bit(cq->array.bitmap, CLASSQUEUE_SIZE, cq->base_offset);
 150         if (pos >= CLASSQUEUE_SIZE) {   //do circular search from the beginning
 151                 pos = find_first_bit(cq->array.bitmap, CLASSQUEUE_SIZE);
 152         }
 153
 154         if (pos < CLASSQUEUE_SIZE) {
 155                 BUG_ON(list_empty(&cq->array.queue[pos]));
 156                 result = list_entry(cq->array.queue[pos].next, cq_node_t, list);
 157         }
 158         return result;
 159 }
 160
 161 /**
 162  * Moving the end of queue forward
 163  * the new_base here is logical, we need to translate to the abosule position
 164  */
 165 void classqueue_update_base(struct classqueue_struct *cq, int new_base)
 166 {
 167         if (!cq_nr_member(cq)) {
 168                 cq->base_offset = -1;   //not defined
 169                 return;
 170         }
 171
 172         //      assert(new_base >= cq->base);
 173
 174         if (new_base > cq->base) {
 175                 cq->base_offset = get_index(cq, &new_base);
 176                 cq->base = new_base;
 177         }
 178 }