include/linux/ckrm_classqueue.h

   1 /* include/linux/ckrm_classqueue.h : cpu control for CKRM
   2  *
   3  * Copyright (C) Haoqiang Zheng, IBM Corp. 2003
   4  *           (C) Hubertus Franke, IBM Corp. 2003
   5  *
   6  * Circular 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 07, 2004
  22  *   clean up, add comments
  23  *
  24  */
  25
  26 #ifndef _CKRM_CLASSQUEUE_H
  27 #define _CKRM_CLASSQUEUE_H
  28
  29 #include <linux/list.h>
  30
  31 #define CLASSQUEUE_SIZE 128
  32 #define CQ_BITMAP_SIZE ((((CLASSQUEUE_SIZE+1+7)/8)+sizeof(long)-1)/sizeof(long))
  33
  34 /**
  35  * struct cq_prio_array: duplicates prio_array defined in sched.c
  36  *
  37  * I duplicate this data structure to make ckrm_classqueue implementation more modular
  38  */
  39 struct cq_prio_array {
  40         int nr_active;
  41         unsigned long bitmap[CQ_BITMAP_SIZE];
  42         struct list_head queue[CLASSQUEUE_SIZE];
  43 };
  44
  45 /**
  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
  50  *
  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
  56  *
  57  * status:
  58  *   hzheng: is 32bit base long enough?
  59  */
  60 struct classqueue_struct {
  61         struct cq_prio_array array;
  62         unsigned long base;
  63         unsigned long base_offset;
  64 };
  65
  66 /**
  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
  71  *
  72  * NOTE: make sure list is empty when it's not in classqueue
  73  */
  74 struct cq_node_struct {
  75         struct list_head list;
  76         int prio;
  77         int index;
  78 };
  79 typedef struct cq_node_struct cq_node_t;
  80
  81 typedef unsigned long long CVT_t;       // cummulative virtual time
  82
  83 static inline void cq_node_init(cq_node_t * node)
  84 {
  85         node->prio = 0;
  86         node->index = -1;
  87         INIT_LIST_HEAD(&node->list);
  88 }
  89
  90 /*if the class is in classqueue*/
  91 static inline int cls_in_classqueue(cq_node_t * node)
  92 {
  93         return !list_empty(&node->list);
  94 }
  95
  96 /*initialize the data structure*/
  97 int classqueue_init(struct classqueue_struct *cq);
  98
  99 /*add the class to classqueue*/
 100 void classqueue_enqueue(struct classqueue_struct *cq, cq_node_t * node, int prio);
 101
 102 /**
 103  * classqueue_dequeue - remove the class from classqueue
 104  *
 105  * internal:
 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?
 109  */
 110 void classqueue_dequeue(struct classqueue_struct *cq, cq_node_t * node);
 111
 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);
 114
 115 /*return the first class in classqueue*/
 116 cq_node_t *classqueue_get_head(struct classqueue_struct *cq);
 117
 118 /*update the base priority of the classqueue*/
 119 void classqueue_update_base(struct classqueue_struct *cq);
 120
 121 /**
 122  * class_compare_prio: compare the priority of this two nodes
 123  */
 124 static inline int class_compare_prio(struct cq_node_struct* node1, struct cq_node_struct* node2)
 125 {
 126         return ( node1->prio - node2->prio);
 127 }
 128
 129 #endif