ia64/linux-2.6.18-xen.hg

view lib/textsearch.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/textsearch.c Generic text search interface
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 * Pablo Neira Ayuso <pablo@eurodev.net>
11 *
12 * ==========================================================================
13 *
14 * INTRODUCTION
15 *
16 * The textsearch infrastructure provides text searching facitilies for
17 * both linear and non-linear data. Individual search algorithms are
18 * implemented in modules and chosen by the user.
19 *
20 * ARCHITECTURE
21 *
22 * User
23 * +----------------+
24 * | finish()|<--------------(6)-----------------+
25 * |get_next_block()|<--------------(5)---------------+ |
26 * | | Algorithm | |
27 * | | +------------------------------+
28 * | | | init() find() destroy() |
29 * | | +------------------------------+
30 * | | Core API ^ ^ ^
31 * | | +---------------+ (2) (4) (8)
32 * | (1)|----->| prepare() |---+ | |
33 * | (3)|----->| find()/next() |-----------+ |
34 * | (7)|----->| destroy() |----------------------+
35 * +----------------+ +---------------+
36 *
37 * (1) User configures a search by calling _prepare() specifying the
38 * search parameters such as the pattern and algorithm name.
39 * (2) Core requests the algorithm to allocate and initialize a search
40 * configuration according to the specified parameters.
41 * (3) User starts the search(es) by calling _find() or _next() to
42 * fetch subsequent occurrences. A state variable is provided
43 * to the algorihtm to store persistant variables.
44 * (4) Core eventually resets the search offset and forwards the find()
45 * request to the algorithm.
46 * (5) Algorithm calls get_next_block() provided by the user continously
47 * to fetch the data to be searched in block by block.
48 * (6) Algorithm invokes finish() after the last call to get_next_block
49 * to clean up any leftovers from get_next_block. (Optional)
50 * (7) User destroys the configuration by calling _destroy().
51 * (8) Core notifies the algorithm to destroy algorithm specific
52 * allocations. (Optional)
53 *
54 * USAGE
55 *
56 * Before a search can be performed, a configuration must be created
57 * by calling textsearch_prepare() specyfing the searching algorithm and
58 * the pattern to look for. The returned configuration may then be used
59 * for an arbitary amount of times and even in parallel as long as a
60 * separate struct ts_state variable is provided to every instance.
61 *
62 * The actual search is performed by either calling textsearch_find_-
63 * continuous() for linear data or by providing an own get_next_block()
64 * implementation and calling textsearch_find(). Both functions return
65 * the position of the first occurrence of the patern or UINT_MAX if
66 * no match was found. Subsequent occurences can be found by calling
67 * textsearch_next() regardless of the linearity of the data.
68 *
69 * Once you're done using a configuration it must be given back via
70 * textsearch_destroy.
71 *
72 * EXAMPLE
73 *
74 * int pos;
75 * struct ts_config *conf;
76 * struct ts_state state;
77 * const char *pattern = "chicken";
78 * const char *example = "We dance the funky chicken";
79 *
80 * conf = textsearch_prepare("kmp", pattern, strlen(pattern),
81 * GFP_KERNEL, TS_AUTOLOAD);
82 * if (IS_ERR(conf)) {
83 * err = PTR_ERR(conf);
84 * goto errout;
85 * }
86 *
87 * pos = textsearch_find_continuous(conf, &state, example, strlen(example));
88 * if (pos != UINT_MAX)
89 * panic("Oh my god, dancing chickens at %d\n", pos);
90 *
91 * textsearch_destroy(conf);
92 *
93 * ==========================================================================
94 */
96 #include <linux/module.h>
97 #include <linux/types.h>
98 #include <linux/string.h>
99 #include <linux/init.h>
100 #include <linux/rcupdate.h>
101 #include <linux/err.h>
102 #include <linux/textsearch.h>
104 static LIST_HEAD(ts_ops);
105 static DEFINE_SPINLOCK(ts_mod_lock);
107 static inline struct ts_ops *lookup_ts_algo(const char *name)
108 {
109 struct ts_ops *o;
111 rcu_read_lock();
112 list_for_each_entry_rcu(o, &ts_ops, list) {
113 if (!strcmp(name, o->name)) {
114 if (!try_module_get(o->owner))
115 o = NULL;
116 rcu_read_unlock();
117 return o;
118 }
119 }
120 rcu_read_unlock();
122 return NULL;
123 }
125 /**
126 * textsearch_register - register a textsearch module
127 * @ops: operations lookup table
128 *
129 * This function must be called by textsearch modules to announce
130 * their presence. The specified &@ops must have %name set to a
131 * unique identifier and the callbacks find(), init(), get_pattern(),
132 * and get_pattern_len() must be implemented.
133 *
134 * Returns 0 or -EEXISTS if another module has already registered
135 * with same name.
136 */
137 int textsearch_register(struct ts_ops *ops)
138 {
139 int err = -EEXIST;
140 struct ts_ops *o;
142 if (ops->name == NULL || ops->find == NULL || ops->init == NULL ||
143 ops->get_pattern == NULL || ops->get_pattern_len == NULL)
144 return -EINVAL;
146 spin_lock(&ts_mod_lock);
147 list_for_each_entry(o, &ts_ops, list) {
148 if (!strcmp(ops->name, o->name))
149 goto errout;
150 }
152 list_add_tail_rcu(&ops->list, &ts_ops);
153 err = 0;
154 errout:
155 spin_unlock(&ts_mod_lock);
156 return err;
157 }
159 /**
160 * textsearch_unregister - unregister a textsearch module
161 * @ops: operations lookup table
162 *
163 * This function must be called by textsearch modules to announce
164 * their disappearance for examples when the module gets unloaded.
165 * The &ops parameter must be the same as the one during the
166 * registration.
167 *
168 * Returns 0 on success or -ENOENT if no matching textsearch
169 * registration was found.
170 */
171 int textsearch_unregister(struct ts_ops *ops)
172 {
173 int err = 0;
174 struct ts_ops *o;
176 spin_lock(&ts_mod_lock);
177 list_for_each_entry(o, &ts_ops, list) {
178 if (o == ops) {
179 list_del_rcu(&o->list);
180 goto out;
181 }
182 }
184 err = -ENOENT;
185 out:
186 spin_unlock(&ts_mod_lock);
187 return err;
188 }
190 struct ts_linear_state
191 {
192 unsigned int len;
193 const void *data;
194 };
196 static unsigned int get_linear_data(unsigned int consumed, const u8 **dst,
197 struct ts_config *conf,
198 struct ts_state *state)
199 {
200 struct ts_linear_state *st = (struct ts_linear_state *) state->cb;
202 if (likely(consumed < st->len)) {
203 *dst = st->data + consumed;
204 return st->len - consumed;
205 }
207 return 0;
208 }
210 /**
211 * textsearch_find_continuous - search a pattern in continuous/linear data
212 * @conf: search configuration
213 * @state: search state
214 * @data: data to search in
215 * @len: length of data
216 *
217 * A simplified version of textsearch_find() for continuous/linear data.
218 * Call textsearch_next() to retrieve subsequent matches.
219 *
220 * Returns the position of first occurrence of the pattern or
221 * UINT_MAX if no occurrence was found.
222 */
223 unsigned int textsearch_find_continuous(struct ts_config *conf,
224 struct ts_state *state,
225 const void *data, unsigned int len)
226 {
227 struct ts_linear_state *st = (struct ts_linear_state *) state->cb;
229 conf->get_next_block = get_linear_data;
230 st->data = data;
231 st->len = len;
233 return textsearch_find(conf, state);
234 }
236 /**
237 * textsearch_prepare - Prepare a search
238 * @algo: name of search algorithm
239 * @pattern: pattern data
240 * @len: length of pattern
241 * @gfp_mask: allocation mask
242 * @flags: search flags
243 *
244 * Looks up the search algorithm module and creates a new textsearch
245 * configuration for the specified pattern. Upon completion all
246 * necessary refcnts are held and the configuration must be put back
247 * using textsearch_put() after usage.
248 *
249 * Note: The format of the pattern may not be compatible between
250 * the various search algorithms.
251 *
252 * Returns a new textsearch configuration according to the specified
253 * parameters or a ERR_PTR().
254 */
255 struct ts_config *textsearch_prepare(const char *algo, const void *pattern,
256 unsigned int len, gfp_t gfp_mask, int flags)
257 {
258 int err = -ENOENT;
259 struct ts_config *conf;
260 struct ts_ops *ops;
262 ops = lookup_ts_algo(algo);
263 #ifdef CONFIG_KMOD
264 /*
265 * Why not always autoload you may ask. Some users are
266 * in a situation where requesting a module may deadlock,
267 * especially when the module is located on a NFS mount.
268 */
269 if (ops == NULL && flags & TS_AUTOLOAD) {
270 request_module("ts_%s", algo);
271 ops = lookup_ts_algo(algo);
272 }
273 #endif
275 if (ops == NULL)
276 goto errout;
278 conf = ops->init(pattern, len, gfp_mask);
279 if (IS_ERR(conf)) {
280 err = PTR_ERR(conf);
281 goto errout;
282 }
284 conf->ops = ops;
285 return conf;
287 errout:
288 if (ops)
289 module_put(ops->owner);
291 return ERR_PTR(err);
292 }
294 /**
295 * textsearch_destroy - destroy a search configuration
296 * @conf: search configuration
297 *
298 * Releases all references of the configuration and frees
299 * up the memory.
300 */
301 void textsearch_destroy(struct ts_config *conf)
302 {
303 if (conf->ops) {
304 if (conf->ops->destroy)
305 conf->ops->destroy(conf);
306 module_put(conf->ops->owner);
307 }
309 kfree(conf);
310 }
312 EXPORT_SYMBOL(textsearch_register);
313 EXPORT_SYMBOL(textsearch_unregister);
314 EXPORT_SYMBOL(textsearch_prepare);
315 EXPORT_SYMBOL(textsearch_find_continuous);
316 EXPORT_SYMBOL(textsearch_destroy);