drm - Fix kldload issue
[dragonfly.git] / sys / kern / dsched / bfq / wf2q.c
CommitLineData
aabeb187
BP
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
52static void
53wf2q_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 */
70static int
71bfq_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
78RB_PROTOTYPE(wf2q_augtree_t, bfq_thread_io, entry,);
79RB_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 */
99static struct bfq_thread_io *
100wf2q_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 */
135void
136wf2q_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 */
148void
149wf2q_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 */
166void
167wf2q_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 */
176void
177wf2q_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 */
185void
186wf2q_update_vd(struct bfq_thread_io *tdio, int received_service)
187{
188 tdio->vd = tdio->ve + received_service / tdio->weight;
189}
190
191static void
192wf2q_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 */
209struct bfq_thread_io *
210wf2q_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