1 /* include/linux/ckrm_classqueue.h : cpu control for CKRM
3 * Copyright (C) Haoqiang Zheng, IBM Corp. 2003
4 * (C) Hubertus Franke, IBM Corp. 2003
6 * Circular 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 * clean up, add comments
26 #ifndef _CKRM_CLASSQUEUE_H
27 #define _CKRM_CLASSQUEUE_H
29 #include <linux/list.h>
31 #define CLASSQUEUE_SIZE 1024 // acb: changed from 128
32 //#define CLASSQUEUE_SIZE 128
33 #define CQ_BITMAP_SIZE ((((CLASSQUEUE_SIZE+1+7)/8)+sizeof(long)-1)/sizeof(long))
36 * struct cq_prio_array: duplicates prio_array defined in sched.c
38 * I duplicate this data structure to make ckrm_classqueue implementation more modular
40 struct cq_prio_array {
42 unsigned long bitmap[CQ_BITMAP_SIZE];
43 struct list_head queue[CLASSQUEUE_SIZE];
47 * struct classqueue_struct - a runqueue of class local runqueues
48 * @array: priority array
49 * @base: base priority
50 * @base_offset: index in array for the base
52 * classqueue can be thought of as runqueue of classes (instead of runqueue of tasks)
53 * as task runqueue, each processor has a classqueue
54 * a class enters the classqueue when the first task in this class local runqueue shows up
55 * a class enters the classqueue when the last task in the local runqueue leaves
56 * class local runqueues are ordered based their priority
59 * hzheng: is 32bit base long enough?
61 struct classqueue_struct {
62 struct cq_prio_array array;
64 unsigned long base_offset;
68 * struct cq_node_struct - the link object between class local runqueue and classqueue
69 * @list: links the class local runqueue to classqueue
70 * @prio: class priority, which is caculated based on it's progress (cvt) and urgency (top_priority)
71 * @index: real index into the classqueue array, calculated based on priority
73 * NOTE: make sure list is empty when it's not in classqueue
75 struct cq_node_struct {
76 struct list_head list;
80 typedef struct cq_node_struct cq_node_t;
82 typedef unsigned long long CVT_t; // cummulative virtual time
84 static inline void cq_node_init(cq_node_t * node)
88 INIT_LIST_HEAD(&node->list);
91 /*if the class is in classqueue*/
92 static inline int cls_in_classqueue(cq_node_t * node)
94 return !list_empty(&node->list);
97 /*initialize the data structure*/
98 int classqueue_init(struct classqueue_struct *cq);
100 /*add the class to classqueue*/
101 void classqueue_enqueue(struct classqueue_struct *cq, cq_node_t * node, int prio);
104 * classqueue_dequeue - remove the class from classqueue
107 * called when the last task is removed from the queue
108 * checked on load balancing and schedule
109 * hzheng: why don't I call it on class_dequeue_task?
111 void classqueue_dequeue(struct classqueue_struct *cq, cq_node_t * node);
113 /*change the position of the class in classqueue*/
114 void classqueue_update_prio(struct classqueue_struct *cq, cq_node_t * node, int new_prio);
116 /*return the first class in classqueue*/
117 cq_node_t *classqueue_get_head(struct classqueue_struct *cq);
119 /*update the base priority of the classqueue*/
120 void classqueue_update_base(struct classqueue_struct *cq);
123 * class_compare_prio: compare the priority of this two nodes
125 static inline int class_compare_prio(struct cq_node_struct* node1, struct cq_node_struct* node2)
127 return ( node1->prio - node2->prio);