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  * Overview:
  26  * ---------
  27  *
  28  * Please read Documentation/ckrm/cpu_sched for a general overview of
  29  * how the O(1) CKRM scheduler.
  30  *
  31  * ckrm_classqueue.h provides the definition to maintain the
  32  * per cpu class runqueue.
  33  *
  34  */
  35
  36 #ifndef _CKRM_CLASSQUEUE_H
  37 #define _CKRM_CLASSQUEUE_H
  38
  39 #include <linux/list.h>
  40
  41 #warning mef: is classqueue_size big enough for PlanetLab
  42 #define CLASSQUEUE_SIZE_SHIFT   7
  43 #define CLASSQUEUE_SIZE ( 1 << CLASSQUEUE_SIZE_SHIFT )
  44 #define CQ_BITMAP_SIZE ((((CLASSQUEUE_SIZE+1+7)/8)+sizeof(long)-1)/sizeof(long))
  45
  46 /**
  47  * struct cq_prio_array: duplicates prio_array defined in sched.c
  48  */
  49 struct cq_prio_array {
  50         int nr_active;
  51         unsigned long bitmap[CQ_BITMAP_SIZE];
  52         struct list_head queue[CLASSQUEUE_SIZE];
  53 };
  54
  55 /**
  56  * struct classqueue_struct - a runqueue of class local runqueues
  57  * @array: priority array
  58  * @base: base priority
  59  * @base_offset: index in array for the base
  60  *
  61  * classqueue can be thought of as runqueue of lrq's (per cpu object of
  62  * a CKRM class as task runqueue (instead of runqueue of tasks)
  63  * - a class's local lrq is enqueued into the local classqueue when a
  64  *   first task is enqueued lrq.
  65  * - a class's local lrq is removed from the local classqueue when the
  66  *   last task is dequeued from the lrq.
  67  * - lrq's are ordered based on their priority (determined elsewhere)
  68  *   ( CKRM: caculated based on it's progress (cvt) and urgency (top_priority)
  69  */
  70
  71 struct classqueue_struct {
  72         int enabled;                   // support dynamic on/off
  73         unsigned long base;
  74         unsigned long base_offset;
  75         struct cq_prio_array array;
  76 };
  77
  78 /**
  79  * struct cq_node_struct:
  80  * - the link object between class local runqueue and classqueue
  81  * @list: links the class local runqueue to classqueue
  82  * @prio: class priority
  83  * @index: real index into the classqueue array, calculated based on priority
  84  */
  85 struct cq_node_struct {
  86         struct list_head list;
  87         int prio;
  88         int index;
  89         /*
  90          * set when the class jump out of the class queue window
  91          * class with this value set should be repositioned whenever classqueue slides window
  92          * real_prio is valid when need_repos is set
  93          */
  94         int real_prio;
  95         int need_repos;
  96 };
  97 typedef struct cq_node_struct cq_node_t;
  98
  99 static inline void cq_node_init(cq_node_t * node)
 100 {
 101         node->prio = 0;
 102         node->index = -1;
 103         node->real_prio = 0;
 104         node->need_repos = 0;
 105         INIT_LIST_HEAD(&node->list);
 106 }
 107
 108 /*if the class is in classqueue*/
 109 static inline int cls_in_classqueue(cq_node_t * node)
 110 {
 111         return !list_empty(&node->list);
 112 }
 113
 114 /*initialize the data structure*/
 115 int classqueue_init(struct classqueue_struct *cq, int enabled);
 116
 117 /*add the class to classqueue at given priority */
 118 void classqueue_enqueue(struct classqueue_struct *cq,
 119                         cq_node_t * node, int prio);
 120
 121 /*remove the class from classqueue */
 122 void classqueue_dequeue(struct classqueue_struct *cq, cq_node_t * node);
 123
 124 /*change the position of the class in classqueue*/
 125 void classqueue_update_prio(struct classqueue_struct *cq,
 126                             cq_node_t * node, int new_prio);
 127
 128 /*return the first class in classqueue*/
 129 cq_node_t *classqueue_get_head(struct classqueue_struct *cq);
 130
 131 /*update the base priority of the classqueue*/
 132 void classqueue_update_base(struct classqueue_struct *cq);
 133
 134 /**
 135  * class_compare_prio: compare the priority of this two nodes
 136  */
 137 static inline int class_compare_prio(struct cq_node_struct* node1,
 138                                      struct cq_node_struct* node2)
 139 {
 140         return ( node1->prio - node2->prio);
 141 }
 142
 143 #endif