ia64/linux-2.6.18-xen.hg

view lib/find_next_bit.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 /* find_next_bit.c: fallback find next bit implementation
2 *
3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
10 */
12 #include <linux/bitops.h>
13 #include <linux/module.h>
14 #include <asm/types.h>
15 #include <asm/byteorder.h>
17 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
19 /**
20 * find_next_bit - find the next set bit in a memory region
21 * @addr: The address to base the search on
22 * @offset: The bitnumber to start searching at
23 * @size: The maximum size to search
24 */
25 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
26 unsigned long offset)
27 {
28 const unsigned long *p = addr + BITOP_WORD(offset);
29 unsigned long result = offset & ~(BITS_PER_LONG-1);
30 unsigned long tmp;
32 if (offset >= size)
33 return size;
34 size -= result;
35 offset %= BITS_PER_LONG;
36 if (offset) {
37 tmp = *(p++);
38 tmp &= (~0UL << offset);
39 if (size < BITS_PER_LONG)
40 goto found_first;
41 if (tmp)
42 goto found_middle;
43 size -= BITS_PER_LONG;
44 result += BITS_PER_LONG;
45 }
46 while (size & ~(BITS_PER_LONG-1)) {
47 if ((tmp = *(p++)))
48 goto found_middle;
49 result += BITS_PER_LONG;
50 size -= BITS_PER_LONG;
51 }
52 if (!size)
53 return result;
54 tmp = *p;
56 found_first:
57 tmp &= (~0UL >> (BITS_PER_LONG - size));
58 if (tmp == 0UL) /* Are any bits set? */
59 return result + size; /* Nope. */
60 found_middle:
61 return result + __ffs(tmp);
62 }
64 EXPORT_SYMBOL(find_next_bit);
66 /*
67 * This implementation of find_{first,next}_zero_bit was stolen from
68 * Linus' asm-alpha/bitops.h.
69 */
70 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
71 unsigned long offset)
72 {
73 const unsigned long *p = addr + BITOP_WORD(offset);
74 unsigned long result = offset & ~(BITS_PER_LONG-1);
75 unsigned long tmp;
77 if (offset >= size)
78 return size;
79 size -= result;
80 offset %= BITS_PER_LONG;
81 if (offset) {
82 tmp = *(p++);
83 tmp |= ~0UL >> (BITS_PER_LONG - offset);
84 if (size < BITS_PER_LONG)
85 goto found_first;
86 if (~tmp)
87 goto found_middle;
88 size -= BITS_PER_LONG;
89 result += BITS_PER_LONG;
90 }
91 while (size & ~(BITS_PER_LONG-1)) {
92 if (~(tmp = *(p++)))
93 goto found_middle;
94 result += BITS_PER_LONG;
95 size -= BITS_PER_LONG;
96 }
97 if (!size)
98 return result;
99 tmp = *p;
101 found_first:
102 tmp |= ~0UL << size;
103 if (tmp == ~0UL) /* Are any bits zero? */
104 return result + size; /* Nope. */
105 found_middle:
106 return result + ffz(tmp);
107 }
109 EXPORT_SYMBOL(find_next_zero_bit);
111 #ifdef __BIG_ENDIAN
113 /* include/linux/byteorder does not support "unsigned long" type */
114 static inline unsigned long ext2_swabp(const unsigned long * x)
115 {
116 #if BITS_PER_LONG == 64
117 return (unsigned long) __swab64p((u64 *) x);
118 #elif BITS_PER_LONG == 32
119 return (unsigned long) __swab32p((u32 *) x);
120 #else
121 #error BITS_PER_LONG not defined
122 #endif
123 }
125 /* include/linux/byteorder doesn't support "unsigned long" type */
126 static inline unsigned long ext2_swab(const unsigned long y)
127 {
128 #if BITS_PER_LONG == 64
129 return (unsigned long) __swab64((u64) y);
130 #elif BITS_PER_LONG == 32
131 return (unsigned long) __swab32((u32) y);
132 #else
133 #error BITS_PER_LONG not defined
134 #endif
135 }
137 unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned
138 long size, unsigned long offset)
139 {
140 const unsigned long *p = addr + BITOP_WORD(offset);
141 unsigned long result = offset & ~(BITS_PER_LONG - 1);
142 unsigned long tmp;
144 if (offset >= size)
145 return size;
146 size -= result;
147 offset &= (BITS_PER_LONG - 1UL);
148 if (offset) {
149 tmp = ext2_swabp(p++);
150 tmp |= (~0UL >> (BITS_PER_LONG - offset));
151 if (size < BITS_PER_LONG)
152 goto found_first;
153 if (~tmp)
154 goto found_middle;
155 size -= BITS_PER_LONG;
156 result += BITS_PER_LONG;
157 }
159 while (size & ~(BITS_PER_LONG - 1)) {
160 if (~(tmp = *(p++)))
161 goto found_middle_swap;
162 result += BITS_PER_LONG;
163 size -= BITS_PER_LONG;
164 }
165 if (!size)
166 return result;
167 tmp = ext2_swabp(p);
168 found_first:
169 tmp |= ~0UL << size;
170 if (tmp == ~0UL) /* Are any bits zero? */
171 return result + size; /* Nope. Skip ffz */
172 found_middle:
173 return result + ffz(tmp);
175 found_middle_swap:
176 return result + ffz(ext2_swab(tmp));
177 }
179 EXPORT_SYMBOL(generic_find_next_zero_le_bit);
181 #endif /* __BIG_ENDIAN */