ia64/linux-2.6.18-xen.hg

view lib/crc32.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 * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com>
3 * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks!
4 * Code was from the public domain, copyright abandoned. Code was
5 * subsequently included in the kernel, thus was re-licensed under the
6 * GNU GPL v2.
7 *
8 * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com>
9 * Same crc32 function was used in 5 other places in the kernel.
10 * I made one version, and deleted the others.
11 * There are various incantations of crc32(). Some use a seed of 0 or ~0.
12 * Some xor at the end with ~0. The generic crc32() function takes
13 * seed as an argument, and doesn't xor at the end. Then individual
14 * users can do whatever they need.
15 * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
16 * fs/jffs2 uses seed 0, doesn't xor with ~0.
17 * fs/partitions/efi.c uses seed ~0, xor's with ~0.
18 *
19 * This source code is licensed under the GNU General Public License,
20 * Version 2. See the file COPYING for more details.
21 */
23 #include <linux/crc32.h>
24 #include <linux/kernel.h>
25 #include <linux/module.h>
26 #include <linux/compiler.h>
27 #include <linux/types.h>
28 #include <linux/slab.h>
29 #include <linux/init.h>
30 #include <asm/atomic.h>
31 #include "crc32defs.h"
32 #if CRC_LE_BITS == 8
33 #define tole(x) __constant_cpu_to_le32(x)
34 #define tobe(x) __constant_cpu_to_be32(x)
35 #else
36 #define tole(x) (x)
37 #define tobe(x) (x)
38 #endif
39 #include "crc32table.h"
41 MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
42 MODULE_DESCRIPTION("Ethernet CRC32 calculations");
43 MODULE_LICENSE("GPL");
45 /**
46 * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32
47 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
48 * other uses, or the previous crc32 value if computing incrementally.
49 * @p: pointer to buffer over which CRC is run
50 * @len: length of buffer @p
51 */
52 u32 __attribute_pure__ crc32_le(u32 crc, unsigned char const *p, size_t len);
54 #if CRC_LE_BITS == 1
55 /*
56 * In fact, the table-based code will work in this case, but it can be
57 * simplified by inlining the table in ?: form.
58 */
60 u32 __attribute_pure__ crc32_le(u32 crc, unsigned char const *p, size_t len)
61 {
62 int i;
63 while (len--) {
64 crc ^= *p++;
65 for (i = 0; i < 8; i++)
66 crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0);
67 }
68 return crc;
69 }
70 #else /* Table-based approach */
72 u32 __attribute_pure__ crc32_le(u32 crc, unsigned char const *p, size_t len)
73 {
74 # if CRC_LE_BITS == 8
75 const u32 *b =(u32 *)p;
76 const u32 *tab = crc32table_le;
78 # ifdef __LITTLE_ENDIAN
79 # define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8)
80 # else
81 # define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8)
82 # endif
84 crc = __cpu_to_le32(crc);
85 /* Align it */
86 if(unlikely(((long)b)&3 && len)){
87 do {
88 u8 *p = (u8 *)b;
89 DO_CRC(*p++);
90 b = (void *)p;
91 } while ((--len) && ((long)b)&3 );
92 }
93 if(likely(len >= 4)){
94 /* load data 32 bits wide, xor data 32 bits wide. */
95 size_t save_len = len & 3;
96 len = len >> 2;
97 --b; /* use pre increment below(*++b) for speed */
98 do {
99 crc ^= *++b;
100 DO_CRC(0);
101 DO_CRC(0);
102 DO_CRC(0);
103 DO_CRC(0);
104 } while (--len);
105 b++; /* point to next byte(s) */
106 len = save_len;
107 }
108 /* And the last few bytes */
109 if(len){
110 do {
111 u8 *p = (u8 *)b;
112 DO_CRC(*p++);
113 b = (void *)p;
114 } while (--len);
115 }
117 return __le32_to_cpu(crc);
118 #undef ENDIAN_SHIFT
119 #undef DO_CRC
121 # elif CRC_LE_BITS == 4
122 while (len--) {
123 crc ^= *p++;
124 crc = (crc >> 4) ^ crc32table_le[crc & 15];
125 crc = (crc >> 4) ^ crc32table_le[crc & 15];
126 }
127 return crc;
128 # elif CRC_LE_BITS == 2
129 while (len--) {
130 crc ^= *p++;
131 crc = (crc >> 2) ^ crc32table_le[crc & 3];
132 crc = (crc >> 2) ^ crc32table_le[crc & 3];
133 crc = (crc >> 2) ^ crc32table_le[crc & 3];
134 crc = (crc >> 2) ^ crc32table_le[crc & 3];
135 }
136 return crc;
137 # endif
138 }
139 #endif
141 /**
142 * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
143 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for
144 * other uses, or the previous crc32 value if computing incrementally.
145 * @p: pointer to buffer over which CRC is run
146 * @len: length of buffer @p
147 */
148 u32 __attribute_pure__ crc32_be(u32 crc, unsigned char const *p, size_t len);
150 #if CRC_BE_BITS == 1
151 /*
152 * In fact, the table-based code will work in this case, but it can be
153 * simplified by inlining the table in ?: form.
154 */
156 u32 __attribute_pure__ crc32_be(u32 crc, unsigned char const *p, size_t len)
157 {
158 int i;
159 while (len--) {
160 crc ^= *p++ << 24;
161 for (i = 0; i < 8; i++)
162 crc =
163 (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE :
164 0);
165 }
166 return crc;
167 }
169 #else /* Table-based approach */
170 u32 __attribute_pure__ crc32_be(u32 crc, unsigned char const *p, size_t len)
171 {
172 # if CRC_BE_BITS == 8
173 const u32 *b =(u32 *)p;
174 const u32 *tab = crc32table_be;
176 # ifdef __LITTLE_ENDIAN
177 # define DO_CRC(x) crc = tab[ (crc ^ (x)) & 255 ] ^ (crc>>8)
178 # else
179 # define DO_CRC(x) crc = tab[ ((crc >> 24) ^ (x)) & 255] ^ (crc<<8)
180 # endif
182 crc = __cpu_to_be32(crc);
183 /* Align it */
184 if(unlikely(((long)b)&3 && len)){
185 do {
186 u8 *p = (u8 *)b;
187 DO_CRC(*p++);
188 b = (u32 *)p;
189 } while ((--len) && ((long)b)&3 );
190 }
191 if(likely(len >= 4)){
192 /* load data 32 bits wide, xor data 32 bits wide. */
193 size_t save_len = len & 3;
194 len = len >> 2;
195 --b; /* use pre increment below(*++b) for speed */
196 do {
197 crc ^= *++b;
198 DO_CRC(0);
199 DO_CRC(0);
200 DO_CRC(0);
201 DO_CRC(0);
202 } while (--len);
203 b++; /* point to next byte(s) */
204 len = save_len;
205 }
206 /* And the last few bytes */
207 if(len){
208 do {
209 u8 *p = (u8 *)b;
210 DO_CRC(*p++);
211 b = (void *)p;
212 } while (--len);
213 }
214 return __be32_to_cpu(crc);
215 #undef ENDIAN_SHIFT
216 #undef DO_CRC
218 # elif CRC_BE_BITS == 4
219 while (len--) {
220 crc ^= *p++ << 24;
221 crc = (crc << 4) ^ crc32table_be[crc >> 28];
222 crc = (crc << 4) ^ crc32table_be[crc >> 28];
223 }
224 return crc;
225 # elif CRC_BE_BITS == 2
226 while (len--) {
227 crc ^= *p++ << 24;
228 crc = (crc << 2) ^ crc32table_be[crc >> 30];
229 crc = (crc << 2) ^ crc32table_be[crc >> 30];
230 crc = (crc << 2) ^ crc32table_be[crc >> 30];
231 crc = (crc << 2) ^ crc32table_be[crc >> 30];
232 }
233 return crc;
234 # endif
235 }
236 #endif
238 /**
239 * bitreverse - reverse the order of bits in a u32 value
240 * @x: value to be bit-reversed
241 */
242 u32 bitreverse(u32 x)
243 {
244 x = (x >> 16) | (x << 16);
245 x = (x >> 8 & 0x00ff00ff) | (x << 8 & 0xff00ff00);
246 x = (x >> 4 & 0x0f0f0f0f) | (x << 4 & 0xf0f0f0f0);
247 x = (x >> 2 & 0x33333333) | (x << 2 & 0xcccccccc);
248 x = (x >> 1 & 0x55555555) | (x << 1 & 0xaaaaaaaa);
249 return x;
250 }
252 EXPORT_SYMBOL(crc32_le);
253 EXPORT_SYMBOL(crc32_be);
254 EXPORT_SYMBOL(bitreverse);
256 /*
257 * A brief CRC tutorial.
258 *
259 * A CRC is a long-division remainder. You add the CRC to the message,
260 * and the whole thing (message+CRC) is a multiple of the given
261 * CRC polynomial. To check the CRC, you can either check that the
262 * CRC matches the recomputed value, *or* you can check that the
263 * remainder computed on the message+CRC is 0. This latter approach
264 * is used by a lot of hardware implementations, and is why so many
265 * protocols put the end-of-frame flag after the CRC.
266 *
267 * It's actually the same long division you learned in school, except that
268 * - We're working in binary, so the digits are only 0 and 1, and
269 * - When dividing polynomials, there are no carries. Rather than add and
270 * subtract, we just xor. Thus, we tend to get a bit sloppy about
271 * the difference between adding and subtracting.
272 *
273 * A 32-bit CRC polynomial is actually 33 bits long. But since it's
274 * 33 bits long, bit 32 is always going to be set, so usually the CRC
275 * is written in hex with the most significant bit omitted. (If you're
276 * familiar with the IEEE 754 floating-point format, it's the same idea.)
277 *
278 * Note that a CRC is computed over a string of *bits*, so you have
279 * to decide on the endianness of the bits within each byte. To get
280 * the best error-detecting properties, this should correspond to the
281 * order they're actually sent. For example, standard RS-232 serial is
282 * little-endian; the most significant bit (sometimes used for parity)
283 * is sent last. And when appending a CRC word to a message, you should
284 * do it in the right order, matching the endianness.
285 *
286 * Just like with ordinary division, the remainder is always smaller than
287 * the divisor (the CRC polynomial) you're dividing by. Each step of the
288 * division, you take one more digit (bit) of the dividend and append it
289 * to the current remainder. Then you figure out the appropriate multiple
290 * of the divisor to subtract to being the remainder back into range.
291 * In binary, it's easy - it has to be either 0 or 1, and to make the
292 * XOR cancel, it's just a copy of bit 32 of the remainder.
293 *
294 * When computing a CRC, we don't care about the quotient, so we can
295 * throw the quotient bit away, but subtract the appropriate multiple of
296 * the polynomial from the remainder and we're back to where we started,
297 * ready to process the next bit.
298 *
299 * A big-endian CRC written this way would be coded like:
300 * for (i = 0; i < input_bits; i++) {
301 * multiple = remainder & 0x80000000 ? CRCPOLY : 0;
302 * remainder = (remainder << 1 | next_input_bit()) ^ multiple;
303 * }
304 * Notice how, to get at bit 32 of the shifted remainder, we look
305 * at bit 31 of the remainder *before* shifting it.
306 *
307 * But also notice how the next_input_bit() bits we're shifting into
308 * the remainder don't actually affect any decision-making until
309 * 32 bits later. Thus, the first 32 cycles of this are pretty boring.
310 * Also, to add the CRC to a message, we need a 32-bit-long hole for it at
311 * the end, so we have to add 32 extra cycles shifting in zeros at the
312 * end of every message,
313 *
314 * So the standard trick is to rearrage merging in the next_input_bit()
315 * until the moment it's needed. Then the first 32 cycles can be precomputed,
316 * and merging in the final 32 zero bits to make room for the CRC can be
317 * skipped entirely.
318 * This changes the code to:
319 * for (i = 0; i < input_bits; i++) {
320 * remainder ^= next_input_bit() << 31;
321 * multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
322 * remainder = (remainder << 1) ^ multiple;
323 * }
324 * With this optimization, the little-endian code is simpler:
325 * for (i = 0; i < input_bits; i++) {
326 * remainder ^= next_input_bit();
327 * multiple = (remainder & 1) ? CRCPOLY : 0;
328 * remainder = (remainder >> 1) ^ multiple;
329 * }
330 *
331 * Note that the other details of endianness have been hidden in CRCPOLY
332 * (which must be bit-reversed) and next_input_bit().
333 *
334 * However, as long as next_input_bit is returning the bits in a sensible
335 * order, we can actually do the merging 8 or more bits at a time rather
336 * than one bit at a time:
337 * for (i = 0; i < input_bytes; i++) {
338 * remainder ^= next_input_byte() << 24;
339 * for (j = 0; j < 8; j++) {
340 * multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
341 * remainder = (remainder << 1) ^ multiple;
342 * }
343 * }
344 * Or in little-endian:
345 * for (i = 0; i < input_bytes; i++) {
346 * remainder ^= next_input_byte();
347 * for (j = 0; j < 8; j++) {
348 * multiple = (remainder & 1) ? CRCPOLY : 0;
349 * remainder = (remainder << 1) ^ multiple;
350 * }
351 * }
352 * If the input is a multiple of 32 bits, you can even XOR in a 32-bit
353 * word at a time and increase the inner loop count to 32.
354 *
355 * You can also mix and match the two loop styles, for example doing the
356 * bulk of a message byte-at-a-time and adding bit-at-a-time processing
357 * for any fractional bytes at the end.
358 *
359 * The only remaining optimization is to the byte-at-a-time table method.
360 * Here, rather than just shifting one bit of the remainder to decide
361 * in the correct multiple to subtract, we can shift a byte at a time.
362 * This produces a 40-bit (rather than a 33-bit) intermediate remainder,
363 * but again the multiple of the polynomial to subtract depends only on
364 * the high bits, the high 8 bits in this case.
365 *
366 * The multile we need in that case is the low 32 bits of a 40-bit
367 * value whose high 8 bits are given, and which is a multiple of the
368 * generator polynomial. This is simply the CRC-32 of the given
369 * one-byte message.
370 *
371 * Two more details: normally, appending zero bits to a message which
372 * is already a multiple of a polynomial produces a larger multiple of that
373 * polynomial. To enable a CRC to detect this condition, it's common to
374 * invert the CRC before appending it. This makes the remainder of the
375 * message+crc come out not as zero, but some fixed non-zero value.
376 *
377 * The same problem applies to zero bits prepended to the message, and
378 * a similar solution is used. Instead of starting with a remainder of
379 * 0, an initial remainder of all ones is used. As long as you start
380 * the same way on decoding, it doesn't make a difference.
381 */
383 #ifdef UNITTEST
385 #include <stdlib.h>
386 #include <stdio.h>
388 #if 0 /*Not used at present */
389 static void
390 buf_dump(char const *prefix, unsigned char const *buf, size_t len)
391 {
392 fputs(prefix, stdout);
393 while (len--)
394 printf(" %02x", *buf++);
395 putchar('\n');
397 }
398 #endif
400 static void bytereverse(unsigned char *buf, size_t len)
401 {
402 while (len--) {
403 unsigned char x = *buf;
404 x = (x >> 4) | (x << 4);
405 x = (x >> 2 & 0x33) | (x << 2 & 0xcc);
406 x = (x >> 1 & 0x55) | (x << 1 & 0xaa);
407 *buf++ = x;
408 }
409 }
411 static void random_garbage(unsigned char *buf, size_t len)
412 {
413 while (len--)
414 *buf++ = (unsigned char) random();
415 }
417 #if 0 /* Not used at present */
418 static void store_le(u32 x, unsigned char *buf)
419 {
420 buf[0] = (unsigned char) x;
421 buf[1] = (unsigned char) (x >> 8);
422 buf[2] = (unsigned char) (x >> 16);
423 buf[3] = (unsigned char) (x >> 24);
424 }
425 #endif
427 static void store_be(u32 x, unsigned char *buf)
428 {
429 buf[0] = (unsigned char) (x >> 24);
430 buf[1] = (unsigned char) (x >> 16);
431 buf[2] = (unsigned char) (x >> 8);
432 buf[3] = (unsigned char) x;
433 }
435 /*
436 * This checks that CRC(buf + CRC(buf)) = 0, and that
437 * CRC commutes with bit-reversal. This has the side effect
438 * of bytewise bit-reversing the input buffer, and returns
439 * the CRC of the reversed buffer.
440 */
441 static u32 test_step(u32 init, unsigned char *buf, size_t len)
442 {
443 u32 crc1, crc2;
444 size_t i;
446 crc1 = crc32_be(init, buf, len);
447 store_be(crc1, buf + len);
448 crc2 = crc32_be(init, buf, len + 4);
449 if (crc2)
450 printf("\nCRC cancellation fail: 0x%08x should be 0\n",
451 crc2);
453 for (i = 0; i <= len + 4; i++) {
454 crc2 = crc32_be(init, buf, i);
455 crc2 = crc32_be(crc2, buf + i, len + 4 - i);
456 if (crc2)
457 printf("\nCRC split fail: 0x%08x\n", crc2);
458 }
460 /* Now swap it around for the other test */
462 bytereverse(buf, len + 4);
463 init = bitreverse(init);
464 crc2 = bitreverse(crc1);
465 if (crc1 != bitreverse(crc2))
466 printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n",
467 crc1, crc2, bitreverse(crc2));
468 crc1 = crc32_le(init, buf, len);
469 if (crc1 != crc2)
470 printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1,
471 crc2);
472 crc2 = crc32_le(init, buf, len + 4);
473 if (crc2)
474 printf("\nCRC cancellation fail: 0x%08x should be 0\n",
475 crc2);
477 for (i = 0; i <= len + 4; i++) {
478 crc2 = crc32_le(init, buf, i);
479 crc2 = crc32_le(crc2, buf + i, len + 4 - i);
480 if (crc2)
481 printf("\nCRC split fail: 0x%08x\n", crc2);
482 }
484 return crc1;
485 }
487 #define SIZE 64
488 #define INIT1 0
489 #define INIT2 0
491 int main(void)
492 {
493 unsigned char buf1[SIZE + 4];
494 unsigned char buf2[SIZE + 4];
495 unsigned char buf3[SIZE + 4];
496 int i, j;
497 u32 crc1, crc2, crc3;
499 for (i = 0; i <= SIZE; i++) {
500 printf("\rTesting length %d...", i);
501 fflush(stdout);
502 random_garbage(buf1, i);
503 random_garbage(buf2, i);
504 for (j = 0; j < i; j++)
505 buf3[j] = buf1[j] ^ buf2[j];
507 crc1 = test_step(INIT1, buf1, i);
508 crc2 = test_step(INIT2, buf2, i);
509 /* Now check that CRC(buf1 ^ buf2) = CRC(buf1) ^ CRC(buf2) */
510 crc3 = test_step(INIT1 ^ INIT2, buf3, i);
511 if (crc3 != (crc1 ^ crc2))
512 printf("CRC XOR fail: 0x%08x != 0x%08x ^ 0x%08x\n",
513 crc3, crc1, crc2);
514 }
515 printf("\nAll test complete. No failures expected.\n");
516 return 0;
517 }
519 #endif /* UNITTEST */