ia64/linux-2.6.18-xen.hg

view lib/idr.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 * 2002-10-18 written by Jim Houston jim.houston@ccur.com
3 * Copyright (C) 2002 by Concurrent Computer Corporation
4 * Distributed under the GNU GPL license version 2.
5 *
6 * Modified by George Anzinger to reuse immediately and to use
7 * find bit instructions. Also removed _irq on spinlocks.
8 *
9 * Small id to pointer translation service.
10 *
11 * It uses a radix tree like structure as a sparse array indexed
12 * by the id to obtain the pointer. The bitmap makes allocating
13 * a new id quick.
14 *
15 * You call it to allocate an id (an int) an associate with that id a
16 * pointer or what ever, we treat it as a (void *). You can pass this
17 * id to a user for him to pass back at a later time. You then pass
18 * that id to this code and it returns your pointer.
20 * You can release ids at any time. When all ids are released, most of
21 * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we
22 * don't need to go to the memory "store" during an id allocate, just
23 * so you don't need to be too concerned about locking and conflicts
24 * with the slab allocator.
25 */
27 #ifndef TEST // to test in user space...
28 #include <linux/slab.h>
29 #include <linux/init.h>
30 #include <linux/module.h>
31 #endif
32 #include <linux/err.h>
33 #include <linux/string.h>
34 #include <linux/idr.h>
36 static kmem_cache_t *idr_layer_cache;
38 static struct idr_layer *alloc_layer(struct idr *idp)
39 {
40 struct idr_layer *p;
41 unsigned long flags;
43 spin_lock_irqsave(&idp->lock, flags);
44 if ((p = idp->id_free)) {
45 idp->id_free = p->ary[0];
46 idp->id_free_cnt--;
47 p->ary[0] = NULL;
48 }
49 spin_unlock_irqrestore(&idp->lock, flags);
50 return(p);
51 }
53 /* only called when idp->lock is held */
54 static void __free_layer(struct idr *idp, struct idr_layer *p)
55 {
56 p->ary[0] = idp->id_free;
57 idp->id_free = p;
58 idp->id_free_cnt++;
59 }
61 static void free_layer(struct idr *idp, struct idr_layer *p)
62 {
63 unsigned long flags;
65 /*
66 * Depends on the return element being zeroed.
67 */
68 spin_lock_irqsave(&idp->lock, flags);
69 __free_layer(idp, p);
70 spin_unlock_irqrestore(&idp->lock, flags);
71 }
73 /**
74 * idr_pre_get - reserver resources for idr allocation
75 * @idp: idr handle
76 * @gfp_mask: memory allocation flags
77 *
78 * This function should be called prior to locking and calling the
79 * following function. It preallocates enough memory to satisfy
80 * the worst possible allocation.
81 *
82 * If the system is REALLY out of memory this function returns 0,
83 * otherwise 1.
84 */
85 int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
86 {
87 while (idp->id_free_cnt < IDR_FREE_MAX) {
88 struct idr_layer *new;
89 new = kmem_cache_alloc(idr_layer_cache, gfp_mask);
90 if (new == NULL)
91 return (0);
92 free_layer(idp, new);
93 }
94 return 1;
95 }
96 EXPORT_SYMBOL(idr_pre_get);
98 static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
99 {
100 int n, m, sh;
101 struct idr_layer *p, *new;
102 struct idr_layer *pa[MAX_LEVEL];
103 int l, id;
104 long bm;
106 id = *starting_id;
107 p = idp->top;
108 l = idp->layers;
109 pa[l--] = NULL;
110 while (1) {
111 /*
112 * We run around this while until we reach the leaf node...
113 */
114 n = (id >> (IDR_BITS*l)) & IDR_MASK;
115 bm = ~p->bitmap;
116 m = find_next_bit(&bm, IDR_SIZE, n);
117 if (m == IDR_SIZE) {
118 /* no space available go back to previous layer. */
119 l++;
120 id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
121 if (!(p = pa[l])) {
122 *starting_id = id;
123 return -2;
124 }
125 continue;
126 }
127 if (m != n) {
128 sh = IDR_BITS*l;
129 id = ((id >> sh) ^ n ^ m) << sh;
130 }
131 if ((id >= MAX_ID_BIT) || (id < 0))
132 return -3;
133 if (l == 0)
134 break;
135 /*
136 * Create the layer below if it is missing.
137 */
138 if (!p->ary[m]) {
139 if (!(new = alloc_layer(idp)))
140 return -1;
141 p->ary[m] = new;
142 p->count++;
143 }
144 pa[l--] = p;
145 p = p->ary[m];
146 }
147 /*
148 * We have reached the leaf node, plant the
149 * users pointer and return the raw id.
150 */
151 p->ary[m] = (struct idr_layer *)ptr;
152 __set_bit(m, &p->bitmap);
153 p->count++;
154 /*
155 * If this layer is full mark the bit in the layer above
156 * to show that this part of the radix tree is full.
157 * This may complete the layer above and require walking
158 * up the radix tree.
159 */
160 n = id;
161 while (p->bitmap == IDR_FULL) {
162 if (!(p = pa[++l]))
163 break;
164 n = n >> IDR_BITS;
165 __set_bit((n & IDR_MASK), &p->bitmap);
166 }
167 return(id);
168 }
170 static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
171 {
172 struct idr_layer *p, *new;
173 int layers, v, id;
174 unsigned long flags;
176 id = starting_id;
177 build_up:
178 p = idp->top;
179 layers = idp->layers;
180 if (unlikely(!p)) {
181 if (!(p = alloc_layer(idp)))
182 return -1;
183 layers = 1;
184 }
185 /*
186 * Add a new layer to the top of the tree if the requested
187 * id is larger than the currently allocated space.
188 */
189 while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
190 layers++;
191 if (!p->count)
192 continue;
193 if (!(new = alloc_layer(idp))) {
194 /*
195 * The allocation failed. If we built part of
196 * the structure tear it down.
197 */
198 spin_lock_irqsave(&idp->lock, flags);
199 for (new = p; p && p != idp->top; new = p) {
200 p = p->ary[0];
201 new->ary[0] = NULL;
202 new->bitmap = new->count = 0;
203 __free_layer(idp, new);
204 }
205 spin_unlock_irqrestore(&idp->lock, flags);
206 return -1;
207 }
208 new->ary[0] = p;
209 new->count = 1;
210 if (p->bitmap == IDR_FULL)
211 __set_bit(0, &new->bitmap);
212 p = new;
213 }
214 idp->top = p;
215 idp->layers = layers;
216 v = sub_alloc(idp, ptr, &id);
217 if (v == -2)
218 goto build_up;
219 return(v);
220 }
222 /**
223 * idr_get_new_above - allocate new idr entry above or equal to a start id
224 * @idp: idr handle
225 * @ptr: pointer you want associated with the ide
226 * @start_id: id to start search at
227 * @id: pointer to the allocated handle
228 *
229 * This is the allocate id function. It should be called with any
230 * required locks.
231 *
232 * If memory is required, it will return -EAGAIN, you should unlock
233 * and go back to the idr_pre_get() call. If the idr is full, it will
234 * return -ENOSPC.
235 *
236 * @id returns a value in the range 0 ... 0x7fffffff
237 */
238 int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
239 {
240 int rv;
242 rv = idr_get_new_above_int(idp, ptr, starting_id);
243 /*
244 * This is a cheap hack until the IDR code can be fixed to
245 * return proper error values.
246 */
247 if (rv < 0) {
248 if (rv == -1)
249 return -EAGAIN;
250 else /* Will be -3 */
251 return -ENOSPC;
252 }
253 *id = rv;
254 return 0;
255 }
256 EXPORT_SYMBOL(idr_get_new_above);
258 /**
259 * idr_get_new - allocate new idr entry
260 * @idp: idr handle
261 * @ptr: pointer you want associated with the ide
262 * @id: pointer to the allocated handle
263 *
264 * This is the allocate id function. It should be called with any
265 * required locks.
266 *
267 * If memory is required, it will return -EAGAIN, you should unlock
268 * and go back to the idr_pre_get() call. If the idr is full, it will
269 * return -ENOSPC.
270 *
271 * @id returns a value in the range 0 ... 0x7fffffff
272 */
273 int idr_get_new(struct idr *idp, void *ptr, int *id)
274 {
275 int rv;
277 rv = idr_get_new_above_int(idp, ptr, 0);
278 /*
279 * This is a cheap hack until the IDR code can be fixed to
280 * return proper error values.
281 */
282 if (rv < 0) {
283 if (rv == -1)
284 return -EAGAIN;
285 else /* Will be -3 */
286 return -ENOSPC;
287 }
288 *id = rv;
289 return 0;
290 }
291 EXPORT_SYMBOL(idr_get_new);
293 static void idr_remove_warning(int id)
294 {
295 printk("idr_remove called for id=%d which is not allocated.\n", id);
296 dump_stack();
297 }
299 static void sub_remove(struct idr *idp, int shift, int id)
300 {
301 struct idr_layer *p = idp->top;
302 struct idr_layer **pa[MAX_LEVEL];
303 struct idr_layer ***paa = &pa[0];
304 int n;
306 *paa = NULL;
307 *++paa = &idp->top;
309 while ((shift > 0) && p) {
310 n = (id >> shift) & IDR_MASK;
311 __clear_bit(n, &p->bitmap);
312 *++paa = &p->ary[n];
313 p = p->ary[n];
314 shift -= IDR_BITS;
315 }
316 n = id & IDR_MASK;
317 if (likely(p != NULL && test_bit(n, &p->bitmap))){
318 __clear_bit(n, &p->bitmap);
319 p->ary[n] = NULL;
320 while(*paa && ! --((**paa)->count)){
321 free_layer(idp, **paa);
322 **paa-- = NULL;
323 }
324 if (!*paa)
325 idp->layers = 0;
326 } else
327 idr_remove_warning(id);
328 }
330 /**
331 * idr_remove - remove the given id and free it's slot
332 * idp: idr handle
333 * id: uniqueue key
334 */
335 void idr_remove(struct idr *idp, int id)
336 {
337 struct idr_layer *p;
339 /* Mask off upper bits we don't use for the search. */
340 id &= MAX_ID_MASK;
342 sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
343 if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
344 idp->top->ary[0]) { // We can drop a layer
346 p = idp->top->ary[0];
347 idp->top->bitmap = idp->top->count = 0;
348 free_layer(idp, idp->top);
349 idp->top = p;
350 --idp->layers;
351 }
352 while (idp->id_free_cnt >= IDR_FREE_MAX) {
353 p = alloc_layer(idp);
354 kmem_cache_free(idr_layer_cache, p);
355 return;
356 }
357 }
358 EXPORT_SYMBOL(idr_remove);
360 /**
361 * idr_destroy - release all cached layers within an idr tree
362 * idp: idr handle
363 */
364 void idr_destroy(struct idr *idp)
365 {
366 while (idp->id_free_cnt) {
367 struct idr_layer *p = alloc_layer(idp);
368 kmem_cache_free(idr_layer_cache, p);
369 }
370 }
371 EXPORT_SYMBOL(idr_destroy);
373 /**
374 * idr_find - return pointer for given id
375 * @idp: idr handle
376 * @id: lookup key
377 *
378 * Return the pointer given the id it has been registered with. A %NULL
379 * return indicates that @id is not valid or you passed %NULL in
380 * idr_get_new().
381 *
382 * The caller must serialize idr_find() vs idr_get_new() and idr_remove().
383 */
384 void *idr_find(struct idr *idp, int id)
385 {
386 int n;
387 struct idr_layer *p;
389 n = idp->layers * IDR_BITS;
390 p = idp->top;
392 /* Mask off upper bits we don't use for the search. */
393 id &= MAX_ID_MASK;
395 if (id >= (1 << n))
396 return NULL;
398 while (n > 0 && p) {
399 n -= IDR_BITS;
400 p = p->ary[(id >> n) & IDR_MASK];
401 }
402 return((void *)p);
403 }
404 EXPORT_SYMBOL(idr_find);
406 /**
407 * idr_replace - replace pointer for given id
408 * @idp: idr handle
409 * @ptr: pointer you want associated with the id
410 * @id: lookup key
411 *
412 * Replace the pointer registered with an id and return the old value.
413 * A -ENOENT return indicates that @id was not found.
414 * A -EINVAL return indicates that @id was not within valid constraints.
415 *
416 * The caller must serialize vs idr_find(), idr_get_new(), and idr_remove().
417 */
418 void *idr_replace(struct idr *idp, void *ptr, int id)
419 {
420 int n;
421 struct idr_layer *p, *old_p;
423 n = idp->layers * IDR_BITS;
424 p = idp->top;
426 id &= MAX_ID_MASK;
428 if (id >= (1 << n))
429 return ERR_PTR(-EINVAL);
431 n -= IDR_BITS;
432 while ((n > 0) && p) {
433 p = p->ary[(id >> n) & IDR_MASK];
434 n -= IDR_BITS;
435 }
437 n = id & IDR_MASK;
438 if (unlikely(p == NULL || !test_bit(n, &p->bitmap)))
439 return ERR_PTR(-ENOENT);
441 old_p = p->ary[n];
442 p->ary[n] = ptr;
444 return old_p;
445 }
446 EXPORT_SYMBOL(idr_replace);
448 static void idr_cache_ctor(void * idr_layer, kmem_cache_t *idr_layer_cache,
449 unsigned long flags)
450 {
451 memset(idr_layer, 0, sizeof(struct idr_layer));
452 }
454 static int init_id_cache(void)
455 {
456 if (!idr_layer_cache)
457 idr_layer_cache = kmem_cache_create("idr_layer_cache",
458 sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL);
459 return 0;
460 }
462 /**
463 * idr_init - initialize idr handle
464 * @idp: idr handle
465 *
466 * This function is use to set up the handle (@idp) that you will pass
467 * to the rest of the functions.
468 */
469 void idr_init(struct idr *idp)
470 {
471 init_id_cache();
472 memset(idp, 0, sizeof(struct idr));
473 spin_lock_init(&idp->lock);
474 }
475 EXPORT_SYMBOL(idr_init);