ia64/linux-2.6.18-xen.hg

view lib/reed_solomon/reed_solomon.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/rslib.c
3 *
4 * Overview:
5 * Generic Reed Solomon encoder / decoder library
6 *
7 * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
8 *
9 * Reed Solomon code lifted from reed solomon library written by Phil Karn
10 * Copyright 2002 Phil Karn, KA9Q
11 *
12 * $Id: rslib.c,v 1.7 2005/11/07 11:14:59 gleixner Exp $
13 *
14 * This program is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License version 2 as
16 * published by the Free Software Foundation.
17 *
18 * Description:
19 *
20 * The generic Reed Solomon library provides runtime configurable
21 * encoding / decoding of RS codes.
22 * Each user must call init_rs to get a pointer to a rs_control
23 * structure for the given rs parameters. This structure is either
24 * generated or a already available matching control structure is used.
25 * If a structure is generated then the polynomial arrays for
26 * fast encoding / decoding are built. This can take some time so
27 * make sure not to call this function from a time critical path.
28 * Usually a module / driver should initialize the necessary
29 * rs_control structure on module / driver init and release it
30 * on exit.
31 * The encoding puts the calculated syndrome into a given syndrome
32 * buffer.
33 * The decoding is a two step process. The first step calculates
34 * the syndrome over the received (data + syndrome) and calls the
35 * second stage, which does the decoding / error correction itself.
36 * Many hw encoders provide a syndrome calculation over the received
37 * data + syndrome and can call the second stage directly.
38 *
39 */
41 #include <linux/errno.h>
42 #include <linux/kernel.h>
43 #include <linux/init.h>
44 #include <linux/module.h>
45 #include <linux/rslib.h>
46 #include <linux/slab.h>
47 #include <linux/mutex.h>
48 #include <asm/semaphore.h>
50 /* This list holds all currently allocated rs control structures */
51 static LIST_HEAD (rslist);
52 /* Protection for the list */
53 static DEFINE_MUTEX(rslistlock);
55 /**
56 * rs_init - Initialize a Reed-Solomon codec
57 * @symsize: symbol size, bits (1-8)
58 * @gfpoly: Field generator polynomial coefficients
59 * @fcr: first root of RS code generator polynomial, index form
60 * @prim: primitive element to generate polynomial roots
61 * @nroots: RS code generator polynomial degree (number of roots)
62 *
63 * Allocate a control structure and the polynom arrays for faster
64 * en/decoding. Fill the arrays according to the given parameters.
65 */
66 static struct rs_control *rs_init(int symsize, int gfpoly, int fcr,
67 int prim, int nroots)
68 {
69 struct rs_control *rs;
70 int i, j, sr, root, iprim;
72 /* Allocate the control structure */
73 rs = kmalloc(sizeof (struct rs_control), GFP_KERNEL);
74 if (rs == NULL)
75 return NULL;
77 INIT_LIST_HEAD(&rs->list);
79 rs->mm = symsize;
80 rs->nn = (1 << symsize) - 1;
81 rs->fcr = fcr;
82 rs->prim = prim;
83 rs->nroots = nroots;
84 rs->gfpoly = gfpoly;
86 /* Allocate the arrays */
87 rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
88 if (rs->alpha_to == NULL)
89 goto errrs;
91 rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
92 if (rs->index_of == NULL)
93 goto erralp;
95 rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), GFP_KERNEL);
96 if(rs->genpoly == NULL)
97 goto erridx;
99 /* Generate Galois field lookup tables */
100 rs->index_of[0] = rs->nn; /* log(zero) = -inf */
101 rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */
102 sr = 1;
103 for (i = 0; i < rs->nn; i++) {
104 rs->index_of[sr] = i;
105 rs->alpha_to[i] = sr;
106 sr <<= 1;
107 if (sr & (1 << symsize))
108 sr ^= gfpoly;
109 sr &= rs->nn;
110 }
111 /* If it's not primitive, exit */
112 if(sr != 1)
113 goto errpol;
115 /* Find prim-th root of 1, used in decoding */
116 for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);
117 /* prim-th root of 1, index form */
118 rs->iprim = iprim / prim;
120 /* Form RS code generator polynomial from its roots */
121 rs->genpoly[0] = 1;
122 for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
123 rs->genpoly[i + 1] = 1;
124 /* Multiply rs->genpoly[] by @**(root + x) */
125 for (j = i; j > 0; j--) {
126 if (rs->genpoly[j] != 0) {
127 rs->genpoly[j] = rs->genpoly[j -1] ^
128 rs->alpha_to[rs_modnn(rs,
129 rs->index_of[rs->genpoly[j]] + root)];
130 } else
131 rs->genpoly[j] = rs->genpoly[j - 1];
132 }
133 /* rs->genpoly[0] can never be zero */
134 rs->genpoly[0] =
135 rs->alpha_to[rs_modnn(rs,
136 rs->index_of[rs->genpoly[0]] + root)];
137 }
138 /* convert rs->genpoly[] to index form for quicker encoding */
139 for (i = 0; i <= nroots; i++)
140 rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
141 return rs;
143 /* Error exit */
144 errpol:
145 kfree(rs->genpoly);
146 erridx:
147 kfree(rs->index_of);
148 erralp:
149 kfree(rs->alpha_to);
150 errrs:
151 kfree(rs);
152 return NULL;
153 }
156 /**
157 * free_rs - Free the rs control structure, if it is no longer used
158 * @rs: the control structure which is not longer used by the
159 * caller
160 */
161 void free_rs(struct rs_control *rs)
162 {
163 mutex_lock(&rslistlock);
164 rs->users--;
165 if(!rs->users) {
166 list_del(&rs->list);
167 kfree(rs->alpha_to);
168 kfree(rs->index_of);
169 kfree(rs->genpoly);
170 kfree(rs);
171 }
172 mutex_unlock(&rslistlock);
173 }
175 /**
176 * init_rs - Find a matching or allocate a new rs control structure
177 * @symsize: the symbol size (number of bits)
178 * @gfpoly: the extended Galois field generator polynomial coefficients,
179 * with the 0th coefficient in the low order bit. The polynomial
180 * must be primitive;
181 * @fcr: the first consecutive root of the rs code generator polynomial
182 * in index form
183 * @prim: primitive element to generate polynomial roots
184 * @nroots: RS code generator polynomial degree (number of roots)
185 */
186 struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
187 int nroots)
188 {
189 struct list_head *tmp;
190 struct rs_control *rs;
192 /* Sanity checks */
193 if (symsize < 1)
194 return NULL;
195 if (fcr < 0 || fcr >= (1<<symsize))
196 return NULL;
197 if (prim <= 0 || prim >= (1<<symsize))
198 return NULL;
199 if (nroots < 0 || nroots >= (1<<symsize))
200 return NULL;
202 mutex_lock(&rslistlock);
204 /* Walk through the list and look for a matching entry */
205 list_for_each(tmp, &rslist) {
206 rs = list_entry(tmp, struct rs_control, list);
207 if (symsize != rs->mm)
208 continue;
209 if (gfpoly != rs->gfpoly)
210 continue;
211 if (fcr != rs->fcr)
212 continue;
213 if (prim != rs->prim)
214 continue;
215 if (nroots != rs->nroots)
216 continue;
217 /* We have a matching one already */
218 rs->users++;
219 goto out;
220 }
222 /* Create a new one */
223 rs = rs_init(symsize, gfpoly, fcr, prim, nroots);
224 if (rs) {
225 rs->users = 1;
226 list_add(&rs->list, &rslist);
227 }
228 out:
229 mutex_unlock(&rslistlock);
230 return rs;
231 }
233 #ifdef CONFIG_REED_SOLOMON_ENC8
234 /**
235 * encode_rs8 - Calculate the parity for data values (8bit data width)
236 * @rs: the rs control structure
237 * @data: data field of a given type
238 * @len: data length
239 * @par: parity data, must be initialized by caller (usually all 0)
240 * @invmsk: invert data mask (will be xored on data)
241 *
242 * The parity uses a uint16_t data type to enable
243 * symbol size > 8. The calling code must take care of encoding of the
244 * syndrome result for storage itself.
245 */
246 int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par,
247 uint16_t invmsk)
248 {
249 #include "encode_rs.c"
250 }
251 EXPORT_SYMBOL_GPL(encode_rs8);
252 #endif
254 #ifdef CONFIG_REED_SOLOMON_DEC8
255 /**
256 * decode_rs8 - Decode codeword (8bit data width)
257 * @rs: the rs control structure
258 * @data: data field of a given type
259 * @par: received parity data field
260 * @len: data length
261 * @s: syndrome data field (if NULL, syndrome is calculated)
262 * @no_eras: number of erasures
263 * @eras_pos: position of erasures, can be NULL
264 * @invmsk: invert data mask (will be xored on data, not on parity!)
265 * @corr: buffer to store correction bitmask on eras_pos
266 *
267 * The syndrome and parity uses a uint16_t data type to enable
268 * symbol size > 8. The calling code must take care of decoding of the
269 * syndrome result and the received parity before calling this code.
270 */
271 int decode_rs8(struct rs_control *rs, uint8_t *data, uint16_t *par, int len,
272 uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
273 uint16_t *corr)
274 {
275 #include "decode_rs.c"
276 }
277 EXPORT_SYMBOL_GPL(decode_rs8);
278 #endif
280 #ifdef CONFIG_REED_SOLOMON_ENC16
281 /**
282 * encode_rs16 - Calculate the parity for data values (16bit data width)
283 * @rs: the rs control structure
284 * @data: data field of a given type
285 * @len: data length
286 * @par: parity data, must be initialized by caller (usually all 0)
287 * @invmsk: invert data mask (will be xored on data, not on parity!)
288 *
289 * Each field in the data array contains up to symbol size bits of valid data.
290 */
291 int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par,
292 uint16_t invmsk)
293 {
294 #include "encode_rs.c"
295 }
296 EXPORT_SYMBOL_GPL(encode_rs16);
297 #endif
299 #ifdef CONFIG_REED_SOLOMON_DEC16
300 /**
301 * decode_rs16 - Decode codeword (16bit data width)
302 * @rs: the rs control structure
303 * @data: data field of a given type
304 * @par: received parity data field
305 * @len: data length
306 * @s: syndrome data field (if NULL, syndrome is calculated)
307 * @no_eras: number of erasures
308 * @eras_pos: position of erasures, can be NULL
309 * @invmsk: invert data mask (will be xored on data, not on parity!)
310 * @corr: buffer to store correction bitmask on eras_pos
311 *
312 * Each field in the data array contains up to symbol size bits of valid data.
313 */
314 int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len,
315 uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
316 uint16_t *corr)
317 {
318 #include "decode_rs.c"
319 }
320 EXPORT_SYMBOL_GPL(decode_rs16);
321 #endif
323 EXPORT_SYMBOL_GPL(init_rs);
324 EXPORT_SYMBOL_GPL(free_rs);
326 MODULE_LICENSE("GPL");
327 MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
328 MODULE_AUTHOR("Phil Karn, Thomas Gleixner");