ia64/linux-2.6.18-xen.hg

view lib/ts_fsm.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/ts_fsm.c A naive finite state machine text search approach
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version
7 * 2 of the License, or (at your option) any later version.
8 *
9 * Authors: Thomas Graf <tgraf@suug.ch>
10 *
11 * ==========================================================================
12 *
13 * A finite state machine consists of n states (struct ts_fsm_token)
14 * representing the pattern as a finite automation. The data is read
15 * sequentially on a octet basis. Every state token specifies the number
16 * of recurrences and the type of value accepted which can be either a
17 * specific character or ctype based set of characters. The available
18 * type of recurrences include 1, (0|1), [0 n], and [1 n].
19 *
20 * The algorithm differs between strict/non-strict mode specyfing
21 * whether the pattern has to start at the first octect. Strict mode
22 * is enabled by default and can be disabled by inserting
23 * TS_FSM_HEAD_IGNORE as the first token in the chain.
24 *
25 * The runtime performance of the algorithm should be around O(n),
26 * however while in strict mode the average runtime can be better.
27 */
29 #include <linux/module.h>
30 #include <linux/types.h>
31 #include <linux/string.h>
32 #include <linux/ctype.h>
33 #include <linux/textsearch.h>
34 #include <linux/textsearch_fsm.h>
36 struct ts_fsm
37 {
38 unsigned int ntokens;
39 struct ts_fsm_token tokens[0];
40 };
42 /* other values derived from ctype.h */
43 #define _A 0x100 /* ascii */
44 #define _W 0x200 /* wildcard */
46 /* Map to _ctype flags and some magic numbers */
47 static u16 token_map[TS_FSM_TYPE_MAX+1] = {
48 [TS_FSM_SPECIFIC] = 0,
49 [TS_FSM_WILDCARD] = _W,
50 [TS_FSM_CNTRL] = _C,
51 [TS_FSM_LOWER] = _L,
52 [TS_FSM_UPPER] = _U,
53 [TS_FSM_PUNCT] = _P,
54 [TS_FSM_SPACE] = _S,
55 [TS_FSM_DIGIT] = _D,
56 [TS_FSM_XDIGIT] = _D | _X,
57 [TS_FSM_ALPHA] = _U | _L,
58 [TS_FSM_ALNUM] = _U | _L | _D,
59 [TS_FSM_PRINT] = _P | _U | _L | _D | _SP,
60 [TS_FSM_GRAPH] = _P | _U | _L | _D,
61 [TS_FSM_ASCII] = _A,
62 };
64 static u16 token_lookup_tbl[256] = {
65 _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 0- 3 */
66 _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 4- 7 */
67 _W|_A|_C, _W|_A|_C|_S, _W|_A|_C|_S, _W|_A|_C|_S, /* 8- 11 */
68 _W|_A|_C|_S, _W|_A|_C|_S, _W|_A|_C, _W|_A|_C, /* 12- 15 */
69 _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 16- 19 */
70 _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 20- 23 */
71 _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 24- 27 */
72 _W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 28- 31 */
73 _W|_A|_S|_SP, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 32- 35 */
74 _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 36- 39 */
75 _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 40- 43 */
76 _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 44- 47 */
77 _W|_A|_D, _W|_A|_D, _W|_A|_D, _W|_A|_D, /* 48- 51 */
78 _W|_A|_D, _W|_A|_D, _W|_A|_D, _W|_A|_D, /* 52- 55 */
79 _W|_A|_D, _W|_A|_D, _W|_A|_P, _W|_A|_P, /* 56- 59 */
80 _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 60- 63 */
81 _W|_A|_P, _W|_A|_U|_X, _W|_A|_U|_X, _W|_A|_U|_X, /* 64- 67 */
82 _W|_A|_U|_X, _W|_A|_U|_X, _W|_A|_U|_X, _W|_A|_U, /* 68- 71 */
83 _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 72- 75 */
84 _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 76- 79 */
85 _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 80- 83 */
86 _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 84- 87 */
87 _W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_P, /* 88- 91 */
88 _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 92- 95 */
89 _W|_A|_P, _W|_A|_L|_X, _W|_A|_L|_X, _W|_A|_L|_X, /* 96- 99 */
90 _W|_A|_L|_X, _W|_A|_L|_X, _W|_A|_L|_X, _W|_A|_L, /* 100-103 */
91 _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 104-107 */
92 _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 108-111 */
93 _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 112-115 */
94 _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 116-119 */
95 _W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_P, /* 120-123 */
96 _W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_C, /* 124-127 */
97 _W, _W, _W, _W, /* 128-131 */
98 _W, _W, _W, _W, /* 132-135 */
99 _W, _W, _W, _W, /* 136-139 */
100 _W, _W, _W, _W, /* 140-143 */
101 _W, _W, _W, _W, /* 144-147 */
102 _W, _W, _W, _W, /* 148-151 */
103 _W, _W, _W, _W, /* 152-155 */
104 _W, _W, _W, _W, /* 156-159 */
105 _W|_S|_SP, _W|_P, _W|_P, _W|_P, /* 160-163 */
106 _W|_P, _W|_P, _W|_P, _W|_P, /* 164-167 */
107 _W|_P, _W|_P, _W|_P, _W|_P, /* 168-171 */
108 _W|_P, _W|_P, _W|_P, _W|_P, /* 172-175 */
109 _W|_P, _W|_P, _W|_P, _W|_P, /* 176-179 */
110 _W|_P, _W|_P, _W|_P, _W|_P, /* 180-183 */
111 _W|_P, _W|_P, _W|_P, _W|_P, /* 184-187 */
112 _W|_P, _W|_P, _W|_P, _W|_P, /* 188-191 */
113 _W|_U, _W|_U, _W|_U, _W|_U, /* 192-195 */
114 _W|_U, _W|_U, _W|_U, _W|_U, /* 196-199 */
115 _W|_U, _W|_U, _W|_U, _W|_U, /* 200-203 */
116 _W|_U, _W|_U, _W|_U, _W|_U, /* 204-207 */
117 _W|_U, _W|_U, _W|_U, _W|_U, /* 208-211 */
118 _W|_U, _W|_U, _W|_U, _W|_P, /* 212-215 */
119 _W|_U, _W|_U, _W|_U, _W|_U, /* 216-219 */
120 _W|_U, _W|_U, _W|_U, _W|_L, /* 220-223 */
121 _W|_L, _W|_L, _W|_L, _W|_L, /* 224-227 */
122 _W|_L, _W|_L, _W|_L, _W|_L, /* 228-231 */
123 _W|_L, _W|_L, _W|_L, _W|_L, /* 232-235 */
124 _W|_L, _W|_L, _W|_L, _W|_L, /* 236-239 */
125 _W|_L, _W|_L, _W|_L, _W|_L, /* 240-243 */
126 _W|_L, _W|_L, _W|_L, _W|_P, /* 244-247 */
127 _W|_L, _W|_L, _W|_L, _W|_L, /* 248-251 */
128 _W|_L, _W|_L, _W|_L, _W|_L}; /* 252-255 */
130 static inline int match_token(struct ts_fsm_token *t, u8 d)
131 {
132 if (t->type)
133 return (token_lookup_tbl[d] & t->type) != 0;
134 else
135 return t->value == d;
136 }
138 static unsigned int fsm_find(struct ts_config *conf, struct ts_state *state)
139 {
140 struct ts_fsm *fsm = ts_config_priv(conf);
141 struct ts_fsm_token *cur = NULL, *next;
142 unsigned int match_start, block_idx = 0, tok_idx;
143 unsigned block_len = 0, strict, consumed = state->offset;
144 const u8 *data;
146 #define GET_NEXT_BLOCK() \
147 ({ consumed += block_idx; \
148 block_idx = 0; \
149 block_len = conf->get_next_block(consumed, &data, conf, state); })
151 #define TOKEN_MISMATCH() \
152 do { \
153 if (strict) \
154 goto no_match; \
155 block_idx++; \
156 goto startover; \
157 } while(0)
159 #define end_of_data() unlikely(block_idx >= block_len && !GET_NEXT_BLOCK())
161 if (end_of_data())
162 goto no_match;
164 strict = fsm->tokens[0].recur != TS_FSM_HEAD_IGNORE;
166 startover:
167 match_start = consumed + block_idx;
169 for (tok_idx = 0; tok_idx < fsm->ntokens; tok_idx++) {
170 cur = &fsm->tokens[tok_idx];
172 if (likely(tok_idx < (fsm->ntokens - 1)))
173 next = &fsm->tokens[tok_idx + 1];
174 else
175 next = NULL;
177 switch (cur->recur) {
178 case TS_FSM_SINGLE:
179 if (end_of_data())
180 goto no_match;
182 if (!match_token(cur, data[block_idx]))
183 TOKEN_MISMATCH();
184 break;
186 case TS_FSM_PERHAPS:
187 if (end_of_data() ||
188 !match_token(cur, data[block_idx]))
189 continue;
190 break;
192 case TS_FSM_MULTI:
193 if (end_of_data())
194 goto no_match;
196 if (!match_token(cur, data[block_idx]))
197 TOKEN_MISMATCH();
199 block_idx++;
200 /* fall through */
202 case TS_FSM_ANY:
203 if (next == NULL)
204 goto found_match;
206 if (end_of_data())
207 continue;
209 while (!match_token(next, data[block_idx])) {
210 if (!match_token(cur, data[block_idx]))
211 TOKEN_MISMATCH();
212 block_idx++;
213 if (end_of_data())
214 goto no_match;
215 }
216 continue;
218 /*
219 * Optimization: Prefer small local loop over jumping
220 * back and forth until garbage at head is munched.
221 */
222 case TS_FSM_HEAD_IGNORE:
223 if (end_of_data())
224 continue;
226 while (!match_token(next, data[block_idx])) {
227 /*
228 * Special case, don't start over upon
229 * a mismatch, give the user the
230 * chance to specify the type of data
231 * allowed to be ignored.
232 */
233 if (!match_token(cur, data[block_idx]))
234 goto no_match;
236 block_idx++;
237 if (end_of_data())
238 goto no_match;
239 }
241 match_start = consumed + block_idx;
242 continue;
243 }
245 block_idx++;
246 }
248 if (end_of_data())
249 goto found_match;
251 no_match:
252 return UINT_MAX;
254 found_match:
255 state->offset = consumed + block_idx;
256 return match_start;
257 }
259 static struct ts_config *fsm_init(const void *pattern, unsigned int len,
260 gfp_t gfp_mask)
261 {
262 int i, err = -EINVAL;
263 struct ts_config *conf;
264 struct ts_fsm *fsm;
265 struct ts_fsm_token *tokens = (struct ts_fsm_token *) pattern;
266 unsigned int ntokens = len / sizeof(*tokens);
267 size_t priv_size = sizeof(*fsm) + len;
269 if (len % sizeof(struct ts_fsm_token) || ntokens < 1)
270 goto errout;
272 for (i = 0; i < ntokens; i++) {
273 struct ts_fsm_token *t = &tokens[i];
275 if (t->type > TS_FSM_TYPE_MAX || t->recur > TS_FSM_RECUR_MAX)
276 goto errout;
278 if (t->recur == TS_FSM_HEAD_IGNORE &&
279 (i != 0 || i == (ntokens - 1)))
280 goto errout;
281 }
283 conf = alloc_ts_config(priv_size, gfp_mask);
284 if (IS_ERR(conf))
285 return conf;
287 fsm = ts_config_priv(conf);
288 fsm->ntokens = ntokens;
289 memcpy(fsm->tokens, pattern, len);
291 for (i = 0; i < fsm->ntokens; i++) {
292 struct ts_fsm_token *t = &fsm->tokens[i];
293 t->type = token_map[t->type];
294 }
296 return conf;
298 errout:
299 return ERR_PTR(err);
300 }
302 static void *fsm_get_pattern(struct ts_config *conf)
303 {
304 struct ts_fsm *fsm = ts_config_priv(conf);
305 return fsm->tokens;
306 }
308 static unsigned int fsm_get_pattern_len(struct ts_config *conf)
309 {
310 struct ts_fsm *fsm = ts_config_priv(conf);
311 return fsm->ntokens * sizeof(struct ts_fsm_token);
312 }
314 static struct ts_ops fsm_ops = {
315 .name = "fsm",
316 .find = fsm_find,
317 .init = fsm_init,
318 .get_pattern = fsm_get_pattern,
319 .get_pattern_len = fsm_get_pattern_len,
320 .owner = THIS_MODULE,
321 .list = LIST_HEAD_INIT(fsm_ops.list)
322 };
324 static int __init init_fsm(void)
325 {
326 return textsearch_register(&fsm_ops);
327 }
329 static void __exit exit_fsm(void)
330 {
331 textsearch_unregister(&fsm_ops);
332 }
334 MODULE_LICENSE("GPL");
336 module_init(init_fsm);
337 module_exit(exit_fsm);