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 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))
  34
  35 /**
  36  * struct cq_prio_array: duplicates prio_array defined in sched.c
  37  *
  38  * I duplicate this data structure to make ckrm_classqueue implementation more modular
  39  */
  40 struct cq_prio_array {
  41         int nr_active;
  42         unsigned long bitmap[CQ_BITMAP_SIZE];
  43         struct list_head queue[CLASSQUEUE_SIZE];
  44 };
  45
  46 /**
  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
  51  *
  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
  57  *
  58  * status:
  59  *   hzheng: is 32bit base long enough?
  60  */
  61 struct classqueue_struct {
  62         struct cq_prio_array array;
  63         unsigned long base;
  64         unsigned long base_offset;
  65 };
  66
  67 /**
  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
  72  *
  73  * NOTE: make sure list is empty when it's not in classqueue
  74  */
  75 struct cq_node_struct {
  76         struct list_head list;
  77         int prio;
  78         int index;
  79 };
  80 typedef struct cq_node_struct cq_node_t;
  81
  82 typedef unsigned long long CVT_t;       // cummulative virtual time
  83
  84 static inline void cq_node_init(cq_node_t * node)
  85 {
  86         node->prio = 0;
  87         node->index = -1;
  88         INIT_LIST_HEAD(&node->list);
  89 }
  90
  91 /*if the class is in classqueue*/
  92 static inline int cls_in_classqueue(cq_node_t * node)
  93 {
  94         return !list_empty(&node->list);
  95 }
  96
  97 /*initialize the data structure*/
  98 int classqueue_init(struct classqueue_struct *cq);
  99
 100 /*add the class to classqueue*/
 101 void classqueue_enqueue(struct classqueue_struct *cq, cq_node_t * node, int prio);
 102
 103 /**
 104  * classqueue_dequeue - remove the class from classqueue
 105  *
 106  * internal:
 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?
 110  */
 111 void classqueue_dequeue(struct classqueue_struct *cq, cq_node_t * node);
 112
 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);
 115
 116 /*return the first class in classqueue*/
 117 cq_node_t *classqueue_get_head(struct classqueue_struct *cq);
 118
 119 /*update the base priority of the classqueue*/
 120 void classqueue_update_base(struct classqueue_struct *cq);
 121
 122 /**
 123  * class_compare_prio: compare the priority of this two nodes
 124  */
 125 static inline int class_compare_prio(struct cq_node_struct* node1, struct cq_node_struct* node2)
 126 {
 127         return ( node1->prio - node2->prio);
 128 }
 129
 130 #endif