ia64/linux-2.6.18-xen.hg

view lib/ts_bm.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_bm.c Boyer-Moore text search implementation
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: Pablo Neira Ayuso <pablo@eurodev.net>
10 *
11 * ==========================================================================
12 *
13 * Implements Boyer-Moore string matching algorithm:
14 *
15 * [1] A Fast String Searching Algorithm, R.S. Boyer and Moore.
16 * Communications of the Association for Computing Machinery,
17 * 20(10), 1977, pp. 762-772.
18 * http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
19 *
20 * [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004
21 * http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
22 *
23 * Note: Since Boyer-Moore (BM) performs searches for matchings from right
24 * to left, it's still possible that a matching could be spread over
25 * multiple blocks, in that case this algorithm won't find any coincidence.
26 *
27 * If you're willing to ensure that such thing won't ever happen, use the
28 * Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose
29 * the proper string search algorithm depending on your setting.
30 *
31 * Say you're using the textsearch infrastructure for filtering, NIDS or
32 * any similar security focused purpose, then go KMP. Otherwise, if you
33 * really care about performance, say you're classifying packets to apply
34 * Quality of Service (QoS) policies, and you don't mind about possible
35 * matchings spread over multiple fragments, then go BM.
36 */
38 #include <linux/kernel.h>
39 #include <linux/module.h>
40 #include <linux/types.h>
41 #include <linux/string.h>
42 #include <linux/textsearch.h>
44 /* Alphabet size, use ASCII */
45 #define ASIZE 256
47 #if 0
48 #define DEBUGP printk
49 #else
50 #define DEBUGP(args, format...)
51 #endif
53 struct ts_bm
54 {
55 u8 * pattern;
56 unsigned int patlen;
57 unsigned int bad_shift[ASIZE];
58 unsigned int good_shift[0];
59 };
61 static unsigned int bm_find(struct ts_config *conf, struct ts_state *state)
62 {
63 struct ts_bm *bm = ts_config_priv(conf);
64 unsigned int i, text_len, consumed = state->offset;
65 const u8 *text;
66 int shift = bm->patlen, bs;
68 for (;;) {
69 text_len = conf->get_next_block(consumed, &text, conf, state);
71 if (unlikely(text_len == 0))
72 break;
74 while (shift < text_len) {
75 DEBUGP("Searching in position %d (%c)\n",
76 shift, text[shift]);
77 for (i = 0; i < bm->patlen; i++)
78 if (text[shift-i] != bm->pattern[bm->patlen-1-i])
79 goto next;
81 /* London calling... */
82 DEBUGP("found!\n");
83 return consumed += (shift-(bm->patlen-1));
85 next: bs = bm->bad_shift[text[shift-i]];
87 /* Now jumping to... */
88 shift = max_t(int, shift-i+bs, shift+bm->good_shift[i]);
89 }
90 consumed += text_len;
91 }
93 return UINT_MAX;
94 }
96 static int subpattern(u8 *pattern, int i, int j, int g)
97 {
98 int x = i+g-1, y = j+g-1, ret = 0;
100 while(pattern[x--] == pattern[y--]) {
101 if (y < 0) {
102 ret = 1;
103 break;
104 }
105 if (--g == 0) {
106 ret = pattern[i-1] != pattern[j-1];
107 break;
108 }
109 }
111 return ret;
112 }
114 static void compute_prefix_tbl(struct ts_bm *bm)
115 {
116 int i, j, g;
118 for (i = 0; i < ASIZE; i++)
119 bm->bad_shift[i] = bm->patlen;
120 for (i = 0; i < bm->patlen - 1; i++)
121 bm->bad_shift[bm->pattern[i]] = bm->patlen - 1 - i;
123 /* Compute the good shift array, used to match reocurrences
124 * of a subpattern */
125 bm->good_shift[0] = 1;
126 for (i = 1; i < bm->patlen; i++)
127 bm->good_shift[i] = bm->patlen;
128 for (i = bm->patlen-1, g = 1; i > 0; g++, i--) {
129 for (j = i-1; j >= 1-g ; j--)
130 if (subpattern(bm->pattern, i, j, g)) {
131 bm->good_shift[g] = bm->patlen-j-g;
132 break;
133 }
134 }
135 }
137 static struct ts_config *bm_init(const void *pattern, unsigned int len,
138 gfp_t gfp_mask)
139 {
140 struct ts_config *conf;
141 struct ts_bm *bm;
142 unsigned int prefix_tbl_len = len * sizeof(unsigned int);
143 size_t priv_size = sizeof(*bm) + len + prefix_tbl_len;
145 conf = alloc_ts_config(priv_size, gfp_mask);
146 if (IS_ERR(conf))
147 return conf;
149 bm = ts_config_priv(conf);
150 bm->patlen = len;
151 bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len;
152 memcpy(bm->pattern, pattern, len);
153 compute_prefix_tbl(bm);
155 return conf;
156 }
158 static void *bm_get_pattern(struct ts_config *conf)
159 {
160 struct ts_bm *bm = ts_config_priv(conf);
161 return bm->pattern;
162 }
164 static unsigned int bm_get_pattern_len(struct ts_config *conf)
165 {
166 struct ts_bm *bm = ts_config_priv(conf);
167 return bm->patlen;
168 }
170 static struct ts_ops bm_ops = {
171 .name = "bm",
172 .find = bm_find,
173 .init = bm_init,
174 .get_pattern = bm_get_pattern,
175 .get_pattern_len = bm_get_pattern_len,
176 .owner = THIS_MODULE,
177 .list = LIST_HEAD_INIT(bm_ops.list)
178 };
180 static int __init init_bm(void)
181 {
182 return textsearch_register(&bm_ops);
183 }
185 static void __exit exit_bm(void)
186 {
187 textsearch_unregister(&bm_ops);
188 }
190 MODULE_LICENSE("GPL");
192 module_init(init_bm);
193 module_exit(exit_bm);