ia64/linux-2.6.18-xen.hg

view lib/rbtree.c @ 897:329ea0ccb344

balloon: try harder to balloon up under memory pressure.

Currently if the balloon driver is unable to increase the guest's
reservation it assumes the failure was due to reaching its full
allocation, gives up on the ballooning operation and records the limit
it reached as the "hard limit". The driver will not try again until
the target is set again (even to the same value).

However it is possible that ballooning has in fact failed due to
memory pressure in the host and therefore it is desirable to keep
attempting to reach the target in case memory becomes available. The
most likely scenario is that some guests are ballooning down while
others are ballooning up and therefore there is temporary memory
pressure while things stabilise. You would not expect a well behaved
toolstack to ask a domain to balloon to more than its allocation nor
would you expect it to deliberately over-commit memory by setting
balloon targets which exceed the total host memory.

This patch drops the concept of a hard limit and causes the balloon
driver to retry increasing the reservation on a timer in the same
manner as when decreasing the reservation.

Also if we partially succeed in increasing the reservation
(i.e. receive less pages than we asked for) then we may as well keep
those pages rather than returning them to Xen.

Signed-off-by: Ian Campbell <ian.campbell@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri Jun 05 14:01:20 2009 +0100 (2009-06-05)
parents 831230e53067
children
line source
1 /*
2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 linux/lib/rbtree.c
21 */
23 #include <linux/rbtree.h>
24 #include <linux/module.h>
26 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
27 {
28 struct rb_node *right = node->rb_right;
29 struct rb_node *parent = rb_parent(node);
31 if ((node->rb_right = right->rb_left))
32 rb_set_parent(right->rb_left, node);
33 right->rb_left = node;
35 rb_set_parent(right, parent);
37 if (parent)
38 {
39 if (node == parent->rb_left)
40 parent->rb_left = right;
41 else
42 parent->rb_right = right;
43 }
44 else
45 root->rb_node = right;
46 rb_set_parent(node, right);
47 }
49 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
50 {
51 struct rb_node *left = node->rb_left;
52 struct rb_node *parent = rb_parent(node);
54 if ((node->rb_left = left->rb_right))
55 rb_set_parent(left->rb_right, node);
56 left->rb_right = node;
58 rb_set_parent(left, parent);
60 if (parent)
61 {
62 if (node == parent->rb_right)
63 parent->rb_right = left;
64 else
65 parent->rb_left = left;
66 }
67 else
68 root->rb_node = left;
69 rb_set_parent(node, left);
70 }
72 void rb_insert_color(struct rb_node *node, struct rb_root *root)
73 {
74 struct rb_node *parent, *gparent;
76 while ((parent = rb_parent(node)) && rb_is_red(parent))
77 {
78 gparent = rb_parent(parent);
80 if (parent == gparent->rb_left)
81 {
82 {
83 register struct rb_node *uncle = gparent->rb_right;
84 if (uncle && rb_is_red(uncle))
85 {
86 rb_set_black(uncle);
87 rb_set_black(parent);
88 rb_set_red(gparent);
89 node = gparent;
90 continue;
91 }
92 }
94 if (parent->rb_right == node)
95 {
96 register struct rb_node *tmp;
97 __rb_rotate_left(parent, root);
98 tmp = parent;
99 parent = node;
100 node = tmp;
101 }
103 rb_set_black(parent);
104 rb_set_red(gparent);
105 __rb_rotate_right(gparent, root);
106 } else {
107 {
108 register struct rb_node *uncle = gparent->rb_left;
109 if (uncle && rb_is_red(uncle))
110 {
111 rb_set_black(uncle);
112 rb_set_black(parent);
113 rb_set_red(gparent);
114 node = gparent;
115 continue;
116 }
117 }
119 if (parent->rb_left == node)
120 {
121 register struct rb_node *tmp;
122 __rb_rotate_right(parent, root);
123 tmp = parent;
124 parent = node;
125 node = tmp;
126 }
128 rb_set_black(parent);
129 rb_set_red(gparent);
130 __rb_rotate_left(gparent, root);
131 }
132 }
134 rb_set_black(root->rb_node);
135 }
136 EXPORT_SYMBOL(rb_insert_color);
138 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
139 struct rb_root *root)
140 {
141 struct rb_node *other;
143 while ((!node || rb_is_black(node)) && node != root->rb_node)
144 {
145 if (parent->rb_left == node)
146 {
147 other = parent->rb_right;
148 if (rb_is_red(other))
149 {
150 rb_set_black(other);
151 rb_set_red(parent);
152 __rb_rotate_left(parent, root);
153 other = parent->rb_right;
154 }
155 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
156 (!other->rb_right || rb_is_black(other->rb_right)))
157 {
158 rb_set_red(other);
159 node = parent;
160 parent = rb_parent(node);
161 }
162 else
163 {
164 if (!other->rb_right || rb_is_black(other->rb_right))
165 {
166 struct rb_node *o_left;
167 if ((o_left = other->rb_left))
168 rb_set_black(o_left);
169 rb_set_red(other);
170 __rb_rotate_right(other, root);
171 other = parent->rb_right;
172 }
173 rb_set_color(other, rb_color(parent));
174 rb_set_black(parent);
175 if (other->rb_right)
176 rb_set_black(other->rb_right);
177 __rb_rotate_left(parent, root);
178 node = root->rb_node;
179 break;
180 }
181 }
182 else
183 {
184 other = parent->rb_left;
185 if (rb_is_red(other))
186 {
187 rb_set_black(other);
188 rb_set_red(parent);
189 __rb_rotate_right(parent, root);
190 other = parent->rb_left;
191 }
192 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
193 (!other->rb_right || rb_is_black(other->rb_right)))
194 {
195 rb_set_red(other);
196 node = parent;
197 parent = rb_parent(node);
198 }
199 else
200 {
201 if (!other->rb_left || rb_is_black(other->rb_left))
202 {
203 register struct rb_node *o_right;
204 if ((o_right = other->rb_right))
205 rb_set_black(o_right);
206 rb_set_red(other);
207 __rb_rotate_left(other, root);
208 other = parent->rb_left;
209 }
210 rb_set_color(other, rb_color(parent));
211 rb_set_black(parent);
212 if (other->rb_left)
213 rb_set_black(other->rb_left);
214 __rb_rotate_right(parent, root);
215 node = root->rb_node;
216 break;
217 }
218 }
219 }
220 if (node)
221 rb_set_black(node);
222 }
224 void rb_erase(struct rb_node *node, struct rb_root *root)
225 {
226 struct rb_node *child, *parent;
227 int color;
229 if (!node->rb_left)
230 child = node->rb_right;
231 else if (!node->rb_right)
232 child = node->rb_left;
233 else
234 {
235 struct rb_node *old = node, *left;
237 node = node->rb_right;
238 while ((left = node->rb_left) != NULL)
239 node = left;
240 child = node->rb_right;
241 parent = rb_parent(node);
242 color = rb_color(node);
244 if (child)
245 rb_set_parent(child, parent);
246 if (parent == old) {
247 parent->rb_right = child;
248 parent = node;
249 } else
250 parent->rb_left = child;
252 node->rb_parent_color = old->rb_parent_color;
253 node->rb_right = old->rb_right;
254 node->rb_left = old->rb_left;
256 if (rb_parent(old))
257 {
258 if (rb_parent(old)->rb_left == old)
259 rb_parent(old)->rb_left = node;
260 else
261 rb_parent(old)->rb_right = node;
262 } else
263 root->rb_node = node;
265 rb_set_parent(old->rb_left, node);
266 if (old->rb_right)
267 rb_set_parent(old->rb_right, node);
268 goto color;
269 }
271 parent = rb_parent(node);
272 color = rb_color(node);
274 if (child)
275 rb_set_parent(child, parent);
276 if (parent)
277 {
278 if (parent->rb_left == node)
279 parent->rb_left = child;
280 else
281 parent->rb_right = child;
282 }
283 else
284 root->rb_node = child;
286 color:
287 if (color == RB_BLACK)
288 __rb_erase_color(child, parent, root);
289 }
290 EXPORT_SYMBOL(rb_erase);
292 /*
293 * This function returns the first node (in sort order) of the tree.
294 */
295 struct rb_node *rb_first(struct rb_root *root)
296 {
297 struct rb_node *n;
299 n = root->rb_node;
300 if (!n)
301 return NULL;
302 while (n->rb_left)
303 n = n->rb_left;
304 return n;
305 }
306 EXPORT_SYMBOL(rb_first);
308 struct rb_node *rb_last(struct rb_root *root)
309 {
310 struct rb_node *n;
312 n = root->rb_node;
313 if (!n)
314 return NULL;
315 while (n->rb_right)
316 n = n->rb_right;
317 return n;
318 }
319 EXPORT_SYMBOL(rb_last);
321 struct rb_node *rb_next(struct rb_node *node)
322 {
323 struct rb_node *parent;
325 /* If we have a right-hand child, go down and then left as far
326 as we can. */
327 if (node->rb_right) {
328 node = node->rb_right;
329 while (node->rb_left)
330 node=node->rb_left;
331 return node;
332 }
334 /* No right-hand children. Everything down and left is
335 smaller than us, so any 'next' node must be in the general
336 direction of our parent. Go up the tree; any time the
337 ancestor is a right-hand child of its parent, keep going
338 up. First time it's a left-hand child of its parent, said
339 parent is our 'next' node. */
340 while ((parent = rb_parent(node)) && node == parent->rb_right)
341 node = parent;
343 return parent;
344 }
345 EXPORT_SYMBOL(rb_next);
347 struct rb_node *rb_prev(struct rb_node *node)
348 {
349 struct rb_node *parent;
351 /* If we have a left-hand child, go down and then right as far
352 as we can. */
353 if (node->rb_left) {
354 node = node->rb_left;
355 while (node->rb_right)
356 node=node->rb_right;
357 return node;
358 }
360 /* No left-hand children. Go up till we find an ancestor which
361 is a right-hand child of its parent */
362 while ((parent = rb_parent(node)) && node == parent->rb_left)
363 node = parent;
365 return parent;
366 }
367 EXPORT_SYMBOL(rb_prev);
369 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
370 struct rb_root *root)
371 {
372 struct rb_node *parent = rb_parent(victim);
374 /* Set the surrounding nodes to point to the replacement */
375 if (parent) {
376 if (victim == parent->rb_left)
377 parent->rb_left = new;
378 else
379 parent->rb_right = new;
380 } else {
381 root->rb_node = new;
382 }
383 if (victim->rb_left)
384 rb_set_parent(victim->rb_left, new);
385 if (victim->rb_right)
386 rb_set_parent(victim->rb_right, new);
388 /* Copy the pointers/colour from the victim to the replacement */
389 *new = *victim;
390 }
391 EXPORT_SYMBOL(rb_replace_node);