ia64/linux-2.6.18-xen.hg

view lib/reed_solomon/decode_rs.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 * lib/reed_solomon/decode_rs.c
3 *
4 * Overview:
5 * Generic Reed Solomon encoder / decoder library
6 *
7 * Copyright 2002, Phil Karn, KA9Q
8 * May be used under the terms of the GNU General Public License (GPL)
9 *
10 * Adaption to the kernel by Thomas Gleixner (tglx@linutronix.de)
11 *
12 * $Id: decode_rs.c,v 1.7 2005/11/07 11:14:59 gleixner Exp $
13 *
14 */
16 /* Generic data width independent code which is included by the
17 * wrappers.
18 */
19 {
20 int deg_lambda, el, deg_omega;
21 int i, j, r, k, pad;
22 int nn = rs->nn;
23 int nroots = rs->nroots;
24 int fcr = rs->fcr;
25 int prim = rs->prim;
26 int iprim = rs->iprim;
27 uint16_t *alpha_to = rs->alpha_to;
28 uint16_t *index_of = rs->index_of;
29 uint16_t u, q, tmp, num1, num2, den, discr_r, syn_error;
30 /* Err+Eras Locator poly and syndrome poly The maximum value
31 * of nroots is 8. So the necessary stack size will be about
32 * 220 bytes max.
33 */
34 uint16_t lambda[nroots + 1], syn[nroots];
35 uint16_t b[nroots + 1], t[nroots + 1], omega[nroots + 1];
36 uint16_t root[nroots], reg[nroots + 1], loc[nroots];
37 int count = 0;
38 uint16_t msk = (uint16_t) rs->nn;
40 /* Check length parameter for validity */
41 pad = nn - nroots - len;
42 if (pad < 0 || pad >= nn)
43 return -ERANGE;
45 /* Does the caller provide the syndrome ? */
46 if (s != NULL)
47 goto decode;
49 /* form the syndromes; i.e., evaluate data(x) at roots of
50 * g(x) */
51 for (i = 0; i < nroots; i++)
52 syn[i] = (((uint16_t) data[0]) ^ invmsk) & msk;
54 for (j = 1; j < len; j++) {
55 for (i = 0; i < nroots; i++) {
56 if (syn[i] == 0) {
57 syn[i] = (((uint16_t) data[j]) ^
58 invmsk) & msk;
59 } else {
60 syn[i] = ((((uint16_t) data[j]) ^
61 invmsk) & msk) ^
62 alpha_to[rs_modnn(rs, index_of[syn[i]] +
63 (fcr + i) * prim)];
64 }
65 }
66 }
68 for (j = 0; j < nroots; j++) {
69 for (i = 0; i < nroots; i++) {
70 if (syn[i] == 0) {
71 syn[i] = ((uint16_t) par[j]) & msk;
72 } else {
73 syn[i] = (((uint16_t) par[j]) & msk) ^
74 alpha_to[rs_modnn(rs, index_of[syn[i]] +
75 (fcr+i)*prim)];
76 }
77 }
78 }
79 s = syn;
81 /* Convert syndromes to index form, checking for nonzero condition */
82 syn_error = 0;
83 for (i = 0; i < nroots; i++) {
84 syn_error |= s[i];
85 s[i] = index_of[s[i]];
86 }
88 if (!syn_error) {
89 /* if syndrome is zero, data[] is a codeword and there are no
90 * errors to correct. So return data[] unmodified
91 */
92 count = 0;
93 goto finish;
94 }
96 decode:
97 memset(&lambda[1], 0, nroots * sizeof(lambda[0]));
98 lambda[0] = 1;
100 if (no_eras > 0) {
101 /* Init lambda to be the erasure locator polynomial */
102 lambda[1] = alpha_to[rs_modnn(rs,
103 prim * (nn - 1 - eras_pos[0]))];
104 for (i = 1; i < no_eras; i++) {
105 u = rs_modnn(rs, prim * (nn - 1 - eras_pos[i]));
106 for (j = i + 1; j > 0; j--) {
107 tmp = index_of[lambda[j - 1]];
108 if (tmp != nn) {
109 lambda[j] ^=
110 alpha_to[rs_modnn(rs, u + tmp)];
111 }
112 }
113 }
114 }
116 for (i = 0; i < nroots + 1; i++)
117 b[i] = index_of[lambda[i]];
119 /*
120 * Begin Berlekamp-Massey algorithm to determine error+erasure
121 * locator polynomial
122 */
123 r = no_eras;
124 el = no_eras;
125 while (++r <= nroots) { /* r is the step number */
126 /* Compute discrepancy at the r-th step in poly-form */
127 discr_r = 0;
128 for (i = 0; i < r; i++) {
129 if ((lambda[i] != 0) && (s[r - i - 1] != nn)) {
130 discr_r ^=
131 alpha_to[rs_modnn(rs,
132 index_of[lambda[i]] +
133 s[r - i - 1])];
134 }
135 }
136 discr_r = index_of[discr_r]; /* Index form */
137 if (discr_r == nn) {
138 /* 2 lines below: B(x) <-- x*B(x) */
139 memmove (&b[1], b, nroots * sizeof (b[0]));
140 b[0] = nn;
141 } else {
142 /* 7 lines below: T(x) <-- lambda(x)-discr_r*x*b(x) */
143 t[0] = lambda[0];
144 for (i = 0; i < nroots; i++) {
145 if (b[i] != nn) {
146 t[i + 1] = lambda[i + 1] ^
147 alpha_to[rs_modnn(rs, discr_r +
148 b[i])];
149 } else
150 t[i + 1] = lambda[i + 1];
151 }
152 if (2 * el <= r + no_eras - 1) {
153 el = r + no_eras - el;
154 /*
155 * 2 lines below: B(x) <-- inv(discr_r) *
156 * lambda(x)
157 */
158 for (i = 0; i <= nroots; i++) {
159 b[i] = (lambda[i] == 0) ? nn :
160 rs_modnn(rs, index_of[lambda[i]]
161 - discr_r + nn);
162 }
163 } else {
164 /* 2 lines below: B(x) <-- x*B(x) */
165 memmove(&b[1], b, nroots * sizeof(b[0]));
166 b[0] = nn;
167 }
168 memcpy(lambda, t, (nroots + 1) * sizeof(t[0]));
169 }
170 }
172 /* Convert lambda to index form and compute deg(lambda(x)) */
173 deg_lambda = 0;
174 for (i = 0; i < nroots + 1; i++) {
175 lambda[i] = index_of[lambda[i]];
176 if (lambda[i] != nn)
177 deg_lambda = i;
178 }
179 /* Find roots of error+erasure locator polynomial by Chien search */
180 memcpy(&reg[1], &lambda[1], nroots * sizeof(reg[0]));
181 count = 0; /* Number of roots of lambda(x) */
182 for (i = 1, k = iprim - 1; i <= nn; i++, k = rs_modnn(rs, k + iprim)) {
183 q = 1; /* lambda[0] is always 0 */
184 for (j = deg_lambda; j > 0; j--) {
185 if (reg[j] != nn) {
186 reg[j] = rs_modnn(rs, reg[j] + j);
187 q ^= alpha_to[reg[j]];
188 }
189 }
190 if (q != 0)
191 continue; /* Not a root */
192 /* store root (index-form) and error location number */
193 root[count] = i;
194 loc[count] = k;
195 /* If we've already found max possible roots,
196 * abort the search to save time
197 */
198 if (++count == deg_lambda)
199 break;
200 }
201 if (deg_lambda != count) {
202 /*
203 * deg(lambda) unequal to number of roots => uncorrectable
204 * error detected
205 */
206 count = -1;
207 goto finish;
208 }
209 /*
210 * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
211 * x**nroots). in index form. Also find deg(omega).
212 */
213 deg_omega = deg_lambda - 1;
214 for (i = 0; i <= deg_omega; i++) {
215 tmp = 0;
216 for (j = i; j >= 0; j--) {
217 if ((s[i - j] != nn) && (lambda[j] != nn))
218 tmp ^=
219 alpha_to[rs_modnn(rs, s[i - j] + lambda[j])];
220 }
221 omega[i] = index_of[tmp];
222 }
224 /*
225 * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
226 * inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form
227 */
228 for (j = count - 1; j >= 0; j--) {
229 num1 = 0;
230 for (i = deg_omega; i >= 0; i--) {
231 if (omega[i] != nn)
232 num1 ^= alpha_to[rs_modnn(rs, omega[i] +
233 i * root[j])];
234 }
235 num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)];
236 den = 0;
238 /* lambda[i+1] for i even is the formal derivative
239 * lambda_pr of lambda[i] */
240 for (i = min(deg_lambda, nroots - 1) & ~1; i >= 0; i -= 2) {
241 if (lambda[i + 1] != nn) {
242 den ^= alpha_to[rs_modnn(rs, lambda[i + 1] +
243 i * root[j])];
244 }
245 }
246 /* Apply error to data */
247 if (num1 != 0 && loc[j] >= pad) {
248 uint16_t cor = alpha_to[rs_modnn(rs,index_of[num1] +
249 index_of[num2] +
250 nn - index_of[den])];
251 /* Store the error correction pattern, if a
252 * correction buffer is available */
253 if (corr) {
254 corr[j] = cor;
255 } else {
256 /* If a data buffer is given and the
257 * error is inside the message,
258 * correct it */
259 if (data && (loc[j] < (nn - nroots)))
260 data[loc[j] - pad] ^= cor;
261 }
262 }
263 }
265 finish:
266 if (eras_pos != NULL) {
267 for (i = 0; i < count; i++)
268 eras_pos[i] = loc[i] - pad;
269 }
270 return count;
272 }