| 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 | |