ia64/linux-2.6.18-xen.hg

view lib/sha1.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 * SHA transform algorithm, originally taken from code written by
3 * Peter Gutmann, and placed in the public domain.
4 */
6 #include <linux/kernel.h>
7 #include <linux/module.h>
8 #include <linux/cryptohash.h>
10 /* The SHA f()-functions. */
12 #define f1(x,y,z) (z ^ (x & (y ^ z))) /* x ? y : z */
13 #define f2(x,y,z) (x ^ y ^ z) /* XOR */
14 #define f3(x,y,z) ((x & y) + (z & (x ^ y))) /* majority */
16 /* The SHA Mysterious Constants */
18 #define K1 0x5A827999L /* Rounds 0-19: sqrt(2) * 2^30 */
19 #define K2 0x6ED9EBA1L /* Rounds 20-39: sqrt(3) * 2^30 */
20 #define K3 0x8F1BBCDCL /* Rounds 40-59: sqrt(5) * 2^30 */
21 #define K4 0xCA62C1D6L /* Rounds 60-79: sqrt(10) * 2^30 */
23 /*
24 * sha_transform: single block SHA1 transform
25 *
26 * @digest: 160 bit digest to update
27 * @data: 512 bits of data to hash
28 * @W: 80 words of workspace (see note)
29 *
30 * This function generates a SHA1 digest for a single 512-bit block.
31 * Be warned, it does not handle padding and message digest, do not
32 * confuse it with the full FIPS 180-1 digest algorithm for variable
33 * length messages.
34 *
35 * Note: If the hash is security sensitive, the caller should be sure
36 * to clear the workspace. This is left to the caller to avoid
37 * unnecessary clears between chained hashing operations.
38 */
39 void sha_transform(__u32 *digest, const char *in, __u32 *W)
40 {
41 __u32 a, b, c, d, e, t, i;
43 for (i = 0; i < 16; i++)
44 W[i] = be32_to_cpu(((const __be32 *)in)[i]);
46 for (i = 0; i < 64; i++)
47 W[i+16] = rol32(W[i+13] ^ W[i+8] ^ W[i+2] ^ W[i], 1);
49 a = digest[0];
50 b = digest[1];
51 c = digest[2];
52 d = digest[3];
53 e = digest[4];
55 for (i = 0; i < 20; i++) {
56 t = f1(b, c, d) + K1 + rol32(a, 5) + e + W[i];
57 e = d; d = c; c = rol32(b, 30); b = a; a = t;
58 }
60 for (; i < 40; i ++) {
61 t = f2(b, c, d) + K2 + rol32(a, 5) + e + W[i];
62 e = d; d = c; c = rol32(b, 30); b = a; a = t;
63 }
65 for (; i < 60; i ++) {
66 t = f3(b, c, d) + K3 + rol32(a, 5) + e + W[i];
67 e = d; d = c; c = rol32(b, 30); b = a; a = t;
68 }
70 for (; i < 80; i ++) {
71 t = f2(b, c, d) + K4 + rol32(a, 5) + e + W[i];
72 e = d; d = c; c = rol32(b, 30); b = a; a = t;
73 }
75 digest[0] += a;
76 digest[1] += b;
77 digest[2] += c;
78 digest[3] += d;
79 digest[4] += e;
80 }
81 EXPORT_SYMBOL(sha_transform);
83 /*
84 * sha_init: initialize the vectors for a SHA1 digest
85 *
86 * @buf: vector to initialize
87 */
88 void sha_init(__u32 *buf)
89 {
90 buf[0] = 0x67452301;
91 buf[1] = 0xefcdab89;
92 buf[2] = 0x98badcfe;
93 buf[3] = 0x10325476;
94 buf[4] = 0xc3d2e1f0;
95 }