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 128
32 #define CQ_BITMAP_SIZE ((((CLASSQUEUE_SIZE+1+7)/8)+sizeof(long)-1)/sizeof(long))
35 * struct cq_prio_array: duplicates prio_array defined in sched.c
37 * I duplicate this data structure to make ckrm_classqueue implementation more modular
39 struct cq_prio_array {
41 unsigned long bitmap[CQ_BITMAP_SIZE];
42 struct list_head queue[CLASSQUEUE_SIZE];
46 * struct classqueue_struct - a runqueue of class local runqueues
47 * @array: priority array
48 * @base: base priority
49 * @base_offset: index in array for the base
51 * classqueue can be thought of as runqueue of classes (instead of runqueue of tasks)
52 * as task runqueue, each processor has a classqueue
53 * a class enters the classqueue when the first task in this class local runqueue shows up
54 * a class enters the classqueue when the last task in the local runqueue leaves
55 * class local runqueues are ordered based their priority
58 * hzheng: is 32bit base long enough?
60 struct classqueue_struct {
61 struct cq_prio_array array;
63 unsigned long base_offset;
67 * struct cq_node_struct - the link object between class local runqueue and classqueue
68 * @list: links the class local runqueue to classqueue
69 * @prio: class priority, which is caculated based on it's progress (cvt) and urgency (top_priority)
70 * @index: real index into the classqueue array, calculated based on priority
72 * NOTE: make sure list is empty when it's not in classqueue
74 struct cq_node_struct {
75 struct list_head list;
79 typedef struct cq_node_struct cq_node_t;
81 typedef unsigned long long CVT_t; // cummulative virtual time
83 static inline void cq_node_init(cq_node_t * node)
87 INIT_LIST_HEAD(&node->list);
90 /*if the class is in classqueue*/
91 static inline int cls_in_classqueue(cq_node_t * node)
93 return !list_empty(&node->list);
96 /*initialize the data structure*/
97 int classqueue_init(struct classqueue_struct *cq);
99 /*add the class to classqueue*/
100 void classqueue_enqueue(struct classqueue_struct *cq, cq_node_t * node, int prio);
103 * classqueue_dequeue - remove the class from classqueue
106 * called when the last task is removed from the queue
107 * checked on load balancing and schedule
108 * hzheng: why don't I call it on class_dequeue_task?
110 void classqueue_dequeue(struct classqueue_struct *cq, cq_node_t * node);
112 /*change the position of the class in classqueue*/
113 void classqueue_update_prio(struct classqueue_struct *cq, cq_node_t * node, int new_prio);
115 /*return the first class in classqueue*/
116 cq_node_t *classqueue_get_head(struct classqueue_struct *cq);
118 /*update the base priority of the classqueue*/
119 void classqueue_update_base(struct classqueue_struct *cq);
122 * class_compare_prio: compare the priority of this two nodes
124 static inline int class_compare_prio(struct cq_node_struct* node1, struct cq_node_struct* node2)
126 return ( node1->prio - node2->prio);