1 /* kernel/ckrm_classqueue.c : implements the class queue
3 * Copyright (C) Haoqiang Zheng, IBM Corp. 2003
4 * (C) Hubertus Franke, IBM Corp. 2003
6 * Class queue functionality for CKRM cpu controller
8 * Latest version, more details at http://ckrm.sf.net
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.
22 * classqueue now has a fixed size
24 * function/structure names are changed to more intuitive ones
26 #include <linux/sched.h>
27 #include <linux/ckrm_classqueue.h>
29 #define cq_nr_member(cq) (cq->array.nr_active)
32 * get_index - translate the logical priority to the real index in the queue
34 * validate the position
35 * a valid prio is [cq->base,cq->base + size -1]
37 static inline unsigned long get_index(struct classqueue_struct *cq, int *prio)
42 if (!cq_nr_member(cq))
45 max_prio = cq->base + (CLASSQUEUE_SIZE - 1);
51 index = (cq->base_offset + (*prio - cq->base)) ;
52 if (index >= CLASSQUEUE_SIZE)
53 index -= CLASSQUEUE_SIZE;
59 * initialize a class queue object
61 int classqueue_init(struct classqueue_struct *cq)
64 struct cq_prio_array *array;
67 for (i = 0; i < CLASSQUEUE_SIZE; i++) {
68 INIT_LIST_HEAD(array->queue + i);
69 __clear_bit(i, array->bitmap);
71 // delimiter for bitsearch
72 __set_bit(CLASSQUEUE_SIZE, array->bitmap);
76 cq->base_offset = -1; //not valid yet
82 *classqueue_enqueue - add the class to classqueue based on its prio
84 void classqueue_enqueue(struct classqueue_struct *cq,
85 cq_node_t * node, int prio)
90 if (cq_nr_member(cq)) {
91 index = get_index(cq, &prio);
92 } else { //the first one
99 list_add(&(node->list), &cq->array.queue[index]);
100 __set_bit(index, cq->array.bitmap);
101 cq->array.nr_active++;
107 void classqueue_dequeue(struct classqueue_struct *cq, cq_node_t * node)
110 list_del_init(&(node->list));
111 cq->array.nr_active--;
113 //check clear the bitmap
114 if (list_empty(&cq->array.queue[node->index]))
115 __clear_bit(node->index, cq->array.bitmap);
118 void classqueue_update_prio(struct classqueue_struct *cq,
119 cq_node_t * node, int new_pos)
123 if (! cls_in_classqueue(node))
126 index = get_index(cq, &new_pos);
127 node->prio = new_pos;
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);
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);
141 *classqueue_get_min_prio: return the priority of the last node in queue
143 * this function can be called without runqueue lock held
145 static inline int classqueue_get_min_prio(struct classqueue_struct *cq)
147 cq_node_t *result = NULL;
151 * search over the bitmap to get the first class in the queue
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);
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]))
170 * this function must be called with runqueue lock held
172 cq_node_t *classqueue_get_head(struct classqueue_struct *cq)
174 cq_node_t *result = NULL;
178 * search over the bitmap to get the first class in the queue
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);
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);
193 * Moving the end of queue forward
194 * the new_base here is logical, we need to translate to the abosule position
196 void classqueue_update_base(struct classqueue_struct *cq)
200 if (! cq_nr_member(cq)) {
201 cq->base_offset = -1; //not defined
205 new_base = classqueue_get_min_prio(cq);
207 if (new_base > cq->base) {
208 cq->base_offset = get_index(cq, &new_base);