ia64/linux-2.6.18-xen.hg

view lib/libcrc32c.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 * CRC32C
3 *@Article{castagnoli-crc,
4 * author = { Guy Castagnoli and Stefan Braeuer and Martin Herrman},
5 * title = {{Optimization of Cyclic Redundancy-Check Codes with 24
6 * and 32 Parity Bits}},
7 * journal = IEEE Transactions on Communication,
8 * year = {1993},
9 * volume = {41},
10 * number = {6},
11 * pages = {},
12 * month = {June},
13 *}
14 * Used by the iSCSI driver, possibly others, and derived from the
15 * the iscsi-crc.c module of the linux-iscsi driver at
16 * http://linux-iscsi.sourceforge.net.
17 *
18 * Following the example of lib/crc32, this function is intended to be
19 * flexible and useful for all users. Modules that currently have their
20 * own crc32c, but hopefully may be able to use this one are:
21 * net/sctp (please add all your doco to here if you change to
22 * use this one!)
23 * <endoflist>
24 *
25 * Copyright (c) 2004 Cisco Systems, Inc.
26 *
27 * This program is free software; you can redistribute it and/or modify it
28 * under the terms of the GNU General Public License as published by the Free
29 * Software Foundation; either version 2 of the License, or (at your option)
30 * any later version.
31 *
32 */
33 #include <linux/crc32c.h>
34 #include <linux/compiler.h>
35 #include <linux/module.h>
36 #include <asm/byteorder.h>
38 MODULE_AUTHOR("Clay Haapala <chaapala@cisco.com>");
39 MODULE_DESCRIPTION("CRC32c (Castagnoli) calculations");
40 MODULE_LICENSE("GPL");
42 #define CRC32C_POLY_BE 0x1EDC6F41
43 #define CRC32C_POLY_LE 0x82F63B78
45 #ifndef CRC_LE_BITS
46 # define CRC_LE_BITS 8
47 #endif
50 /*
51 * Haven't generated a big-endian table yet, but the bit-wise version
52 * should at least work.
53 */
54 #if defined CRC_BE_BITS && CRC_BE_BITS != 1
55 #undef CRC_BE_BITS
56 #endif
57 #ifndef CRC_BE_BITS
58 # define CRC_BE_BITS 1
59 #endif
61 EXPORT_SYMBOL(crc32c_le);
63 #if CRC_LE_BITS == 1
64 /*
65 * Compute things bit-wise, as done in crc32.c. We could share the tight
66 * loop below with crc32 and vary the POLY if we don't find value in terms
67 * of space and maintainability in keeping the two modules separate.
68 */
69 u32 __attribute_pure__
70 crc32c_le(u32 crc, unsigned char const *p, size_t len)
71 {
72 int i;
73 while (len--) {
74 crc ^= *p++;
75 for (i = 0; i < 8; i++)
76 crc = (crc >> 1) ^ ((crc & 1) ? CRC32C_POLY_LE : 0);
77 }
78 return crc;
79 }
80 #else
82 /*
83 * This is the CRC-32C table
84 * Generated with:
85 * width = 32 bits
86 * poly = 0x1EDC6F41
87 * reflect input bytes = true
88 * reflect output bytes = true
89 */
91 static const u32 crc32c_table[256] = {
92 0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
93 0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
94 0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
95 0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
96 0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
97 0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
98 0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
99 0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
100 0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
101 0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
102 0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
103 0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
104 0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
105 0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
106 0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
107 0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
108 0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
109 0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
110 0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
111 0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
112 0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
113 0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
114 0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
115 0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
116 0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
117 0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
118 0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
119 0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
120 0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
121 0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
122 0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
123 0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
124 0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
125 0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
126 0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
127 0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
128 0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
129 0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
130 0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
131 0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
132 0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
133 0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
134 0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
135 0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
136 0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
137 0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
138 0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
139 0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
140 0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
141 0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
142 0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
143 0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
144 0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
145 0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
146 0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
147 0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
148 0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
149 0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
150 0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
151 0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
152 0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
153 0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
154 0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
155 0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
156 };
158 /*
159 * Steps through buffer one byte at at time, calculates reflected
160 * crc using table.
161 */
163 u32 __attribute_pure__
164 crc32c_le(u32 seed, unsigned char const *data, size_t length)
165 {
166 u32 crc = __cpu_to_le32(seed);
168 while (length--)
169 crc =
170 crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);
172 return __le32_to_cpu(crc);
173 }
175 #endif /* CRC_LE_BITS == 8 */
177 EXPORT_SYMBOL(crc32c_be);
179 #if CRC_BE_BITS == 1
180 u32 __attribute_pure__
181 crc32c_be(u32 crc, unsigned char const *p, size_t len)
182 {
183 int i;
184 while (len--) {
185 crc ^= *p++ << 24;
186 for (i = 0; i < 8; i++)
187 crc =
188 (crc << 1) ^ ((crc & 0x80000000) ? CRC32C_POLY_BE :
189 0);
190 }
191 return crc;
192 }
193 #endif
195 /*
196 * Unit test
197 *
198 * A small unit test suite is implemented as part of the crypto suite.
199 * Select CRYPTO_CRC32C and use the tcrypt module to run the tests.
200 */