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 cq_node_t *classqueue_get_head(struct classqueue_struct *cq)
143 cq_node_t *result = NULL;
147 * search over the bitmap to get the first class in the queue
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);
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);
162 * Moving the end of queue forward
163 * the new_base here is logical, we need to translate to the abosule position
165 void classqueue_update_base(struct classqueue_struct *cq, int new_base)
167 if (!cq_nr_member(cq)) {
168 cq->base_offset = -1; //not defined
172 // assert(new_base >= cq->base);
174 if (new_base > cq->base) {
175 cq->base_offset = get_index(cq, &new_base);