ia64/linux-2.6.18-xen.hg

view lib/sort.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 * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
3 *
4 * Jan 23 2005 Matt Mackall <mpm@selenic.com>
5 */
7 #include <linux/kernel.h>
8 #include <linux/module.h>
9 #include <linux/sort.h>
10 #include <linux/slab.h>
12 static void u32_swap(void *a, void *b, int size)
13 {
14 u32 t = *(u32 *)a;
15 *(u32 *)a = *(u32 *)b;
16 *(u32 *)b = t;
17 }
19 static void generic_swap(void *a, void *b, int size)
20 {
21 char t;
23 do {
24 t = *(char *)a;
25 *(char *)a++ = *(char *)b;
26 *(char *)b++ = t;
27 } while (--size > 0);
28 }
30 /*
31 * sort - sort an array of elements
32 * @base: pointer to data to sort
33 * @num: number of elements
34 * @size: size of each element
35 * @cmp: pointer to comparison function
36 * @swap: pointer to swap function or NULL
37 *
38 * This function does a heapsort on the given array. You may provide a
39 * swap function optimized to your element type.
40 *
41 * Sorting time is O(n log n) both on average and worst-case. While
42 * qsort is about 20% faster on average, it suffers from exploitable
43 * O(n*n) worst-case behavior and extra memory requirements that make
44 * it less suitable for kernel use.
45 */
47 void sort(void *base, size_t num, size_t size,
48 int (*cmp)(const void *, const void *),
49 void (*swap)(void *, void *, int size))
50 {
51 /* pre-scale counters for performance */
52 int i = (num/2) * size, n = num * size, c, r;
54 if (!swap)
55 swap = (size == 4 ? u32_swap : generic_swap);
57 /* heapify */
58 for ( ; i >= 0; i -= size) {
59 for (r = i; r * 2 < n; r = c) {
60 c = r * 2;
61 if (c < n - size && cmp(base + c, base + c + size) < 0)
62 c += size;
63 if (cmp(base + r, base + c) >= 0)
64 break;
65 swap(base + r, base + c, size);
66 }
67 }
69 /* sort */
70 for (i = n - size; i >= 0; i -= size) {
71 swap(base, base + i, size);
72 for (r = 0; r * 2 < i; r = c) {
73 c = r * 2;
74 if (c < i - size && cmp(base + c, base + c + size) < 0)
75 c += size;
76 if (cmp(base + r, base + c) >= 0)
77 break;
78 swap(base + r, base + c, size);
79 }
80 }
81 }
83 EXPORT_SYMBOL(sort);
85 #if 0
86 /* a simple boot-time regression test */
88 int cmpint(const void *a, const void *b)
89 {
90 return *(int *)a - *(int *)b;
91 }
93 static int sort_test(void)
94 {
95 int *a, i, r = 1;
97 a = kmalloc(1000 * sizeof(int), GFP_KERNEL);
98 BUG_ON(!a);
100 printk("testing sort()\n");
102 for (i = 0; i < 1000; i++) {
103 r = (r * 725861) % 6599;
104 a[i] = r;
105 }
107 sort(a, 1000, sizeof(int), cmpint, NULL);
109 for (i = 0; i < 999; i++)
110 if (a[i] > a[i+1]) {
111 printk("sort() failed!\n");
112 break;
113 }
115 kfree(a);
117 return 0;
118 }
120 module_init(sort_test);
121 #endif