sys/kern/dsched/bfq/wf2q.c

   1 /*
   2  * Copyright (c) 2011 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Brills Peng <brillsp@gmail.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 /*
  36  * Augment RB-tree for B-WF2Q+ queuing algorithm:
  37  *  - The key of the binary tree is the virtual eligible time (start time)
  38  *  - Each node maintains an additional min_vd value, which
  39  *    is the minimum virtual deadline (finish time) among the node and its
  40  *    children
  41  *  - Every operation on the tree changing the childs of a node will
  42  *    trigger RB_AUGMENT() marco, which change min_vd along the path to
  43  *    the root
  44  */
  45
  46 #include <kern/dsched/bfq/wf2q.h>
  47
  48
  49 #undef RB_AUGMENT
  50 #define RB_AUGMENT(x) wf2q_augment_func(x);
  51
  52 static void
  53 wf2q_augment_func(struct bfq_thread_io *node)
  54 {
  55         struct bfq_thread_io *tmp = node, *tmp2;
  56         int min_vd;
  57         do{
  58                 min_vd = tmp->vd;
  59                 tmp2 = RB_LEFT(tmp, entry);
  60                 min_vd = tmp2 ? MIN(tmp2->min_vd, min_vd) : min_vd;
  61                 tmp2 = RB_RIGHT(tmp, entry);
  62                 min_vd = tmp2 ? MIN(tmp2->min_vd, min_vd) : min_vd;
  63                 tmp->min_vd = min_vd;
  64         }while((tmp = RB_PARENT(tmp,entry)));
  65 }
  66
  67 /*
  68  * The rb-tree is indexed by the virtual eligible (start) time
  69  */
  70 static int
  71 bfq_thread_io_cmp(struct bfq_thread_io *a, struct bfq_thread_io *b)
  72 {
  73         if (a->ve - b->ve <= 0)
  74                 return -1;
  75         return 1;
  76 }
  77
  78 RB_PROTOTYPE(wf2q_augtree_t, bfq_thread_io, entry,);
  79 RB_GENERATE(wf2q_augtree_t, bfq_thread_io, entry, bfq_thread_io_cmp);
  80
  81 /*
  82  * The algorithm is from
  83  *      I. Stoica and H. Abdel-Wahab, ``Earliest Eligible Virtual Deadline
  84  *  First: A Flexible and Accurate Mechanism for Proportional Share
  85  *  Resource Allocation,'' technical report.
  86  *
  87  *  http://www.cs.berkeley.edu/~istoica/papers/eevdf-tr-95.pdf
  88  *
  89  *  - Partition the tree into two parts by ve:
  90  *  - One part contains nodes with ve smaller than vtime
  91  *  - The other part contains nodes with ve larger than vtime
  92  *  - In the first part, find the node with minimum vd, along the
  93  *    min_vd value path
  94  *
  95  *  Returns
  96  *      NULL, if no node with ve smaller than vtime
  97  *      or the elegible node with minimum vd.
  98  */
  99 static struct bfq_thread_io *
 100 wf2q_augtree_get_eligible_with_min_vd(struct wf2q_augtree_t *tree, int vtime)
 101 {
 102         struct bfq_thread_io *node = RB_ROOT(tree), *st_tree = NULL, *path_req = NULL;
 103         while (node) {
 104                 if (node->ve <= vtime) {
 105                         /* update node with earliest deadline along path. */
 106                         if ((!path_req) || (path_req->vd > node->vd))
 107                                 path_req = node;
 108                         /* update root of subtree containing earliest deadline */
 109                         if ((!st_tree) || (RB_LEFT(node,entry) && st_tree->min_vd > RB_LEFT(node,entry)->min_vd))
 110                                 st_tree = RB_LEFT(node,entry);
 111                         node = RB_RIGHT(node, entry);
 112                 } else
 113                         node = RB_LEFT(node, entry);
 114         }
 115         /* check whether node with earliest deadline was along path */
 116         if ((!st_tree) || (st_tree->min_vd >= path_req->vd))
 117                 return path_req;
 118         /* return node with earliest deadline from subtree */
 119         for (node = st_tree; node; ) {
 120                 /* if node found, return it */
 121                 if (st_tree->min_vd == node->vd)
 122                         return node;
 123                 /* XXX: modified temporarily */
 124                 if (RB_LEFT(node, entry) && node->min_vd == RB_LEFT(node, entry)->min_vd)
 125                         node = RB_LEFT(node, entry);
 126                 else
 127                         node = RB_RIGHT(node, entry);
 128         }
 129         return NULL;
 130 }
 131
 132 /*
 133  * This function initializes a wf2q structure
 134  */
 135 void
 136 wf2q_init(struct wf2q_t *pwf2q)
 137 {
 138         RB_INIT(&pwf2q->wf2q_augtree);
 139         pwf2q->wf2q_virtual_time = 0;
 140         pwf2q->wf2q_tdio_count = 0;
 141 }
 142
 143 /*
 144  * Insert a tdio into a wf2q queue.
 145  * The virtual eligible (start) time and deadline is handled
 146  * according to the current virtual time (in wf2q_t).
 147  */
 148 void
 149 wf2q_insert_thread_io(struct wf2q_t *wf2q, struct bfq_thread_io *tdio)
 150 {
 151         /*
 152          * TODO: The anticipatory parts
 153          * start time varies on whether the tdio is being waited
 154          */
 155         tdio->ve = MAX(wf2q->wf2q_virtual_time, tdio->vd);
 156         tdio->vd = tdio->ve + tdio->budget / tdio->weight;
 157         tdio->min_vd = tdio->vd;
 158         RB_INSERT(wf2q_augtree_t, &wf2q->wf2q_augtree, tdio);
 159         wf2q->wf2q_tdio_count++;
 160 }
 161
 162 /*
 163  * Remove a thread_io struct from the augment tree,
 164  * called before a thread is destroyed.
 165  */
 166 void
 167 wf2q_remove_thread_io(struct wf2q_t *wf2q, struct bfq_thread_io *tdio)
 168 {
 169         RB_REMOVE(wf2q_augtree_t, &wf2q->wf2q_augtree, tdio);
 170         wf2q->wf2q_tdio_count--;
 171 }
 172
 173 /*
 174  * Increase the current virtual time as services are provided
 175  */
 176 void
 177 wf2q_inc_tot_service(struct wf2q_t *wf2q, int amount)
 178 {
 179         wf2q->wf2q_virtual_time += amount;
 180 }
 181
 182 /*
 183  * Update a tdio's virtual deadline as it received service
 184  */
 185 void
 186 wf2q_update_vd(struct bfq_thread_io *tdio, int received_service)
 187 {
 188         tdio->vd = tdio->ve + received_service / tdio->weight;
 189 }
 190
 191 static void
 192 wf2q_tree_dump(struct bfq_thread_io *root, int level)
 193 {
 194         int i;
 195         if (!root) return;
 196         for (i = 0; i < level; i++)
 197                 kprintf("-");
 198         kprintf("vd: %d; ve: %d; min_vd: %d\n", root->vd, root->ve, root->min_vd);
 199         wf2q_tree_dump(RB_LEFT(root,entry), level + 1);
 200         wf2q_tree_dump(RB_RIGHT(root, entry), level + 1);
 201 }
 202
 203 /*
 204  * Get a tdio with minimum virtual deadline and virtual eligible
 205  * time smaller than the current virtual time.
 206  * If there is no such tdio, update the current virtual time to
 207  * the minimum ve in the queue. (And there must be one eligible then)
 208  */
 209 struct bfq_thread_io *
 210 wf2q_get_next_thread_io(struct wf2q_t *wf2q)
 211 {
 212         struct bfq_thread_io *tdio;
 213         struct wf2q_augtree_t *tree = &wf2q->wf2q_augtree;
 214         if (!(tdio = wf2q_augtree_get_eligible_with_min_vd(tree, wf2q->wf2q_virtual_time))) {
 215                 tdio = RB_MIN(wf2q_augtree_t, tree);
 216                 if (!tdio)
 217                         return NULL;
 218                 wf2q->wf2q_virtual_time = tdio->ve;
 219                 tdio = wf2q_augtree_get_eligible_with_min_vd(tree, wf2q->wf2q_virtual_time);
 220         }
 221         if (!tdio) {
 222                 kprintf("!!!wf2q: wf2q_tdio_count=%d\n", wf2q->wf2q_tdio_count);
 223                 wf2q_tree_dump(RB_ROOT(tree), 0);
 224                 KKASSERT(0);
 225         }
 226         RB_REMOVE(wf2q_augtree_t, tree, tdio);
 227         wf2q->wf2q_tdio_count--;
 228         return tdio;
 229 }
 230
 231