ia64/xen-unstable

view xen/common/rangeset.c @ 19835:edfdeb150f27

Fix buildsystem to detect udev > version 124

udev removed the udevinfo symlink from versions higher than 123 and
xen's build-system could not detect if udev is in place and has the
required version.

Signed-off-by: Marc-A. Dahlhaus <mad@wol.de>
author Keir Fraser <keir.fraser@citrix.com>
date Thu Jun 25 13:02:37 2009 +0100 (2009-06-25)
parents 44f039c4aee4
children
line source
1 /******************************************************************************
2 * rangeset.c
3 *
4 * Creation, maintenance and automatic destruction of per-domain sets of
5 * numeric ranges.
6 *
7 * Copyright (c) 2005, K A Fraser
8 */
10 #include <xen/sched.h>
11 #include <xen/errno.h>
12 #include <xen/rangeset.h>
13 #include <xsm/xsm.h>
15 /* An inclusive range [s,e] and pointer to next range in ascending order. */
16 struct range {
17 struct list_head list;
18 unsigned long s, e;
19 };
21 struct rangeset {
22 /* Owning domain and threaded list of rangesets. */
23 struct list_head rangeset_list;
24 struct domain *domain;
26 /* Ordered list of ranges contained in this set, and protecting lock. */
27 struct list_head range_list;
28 spinlock_t lock;
30 /* Pretty-printing name. */
31 char name[32];
33 /* RANGESETF flags. */
34 unsigned int flags;
35 };
37 /*****************************
38 * Private range functions hide the underlying linked-list implemnetation.
39 */
41 /* Find highest range lower than or containing s. NULL if no such range. */
42 static struct range *find_range(
43 struct rangeset *r, unsigned long s)
44 {
45 struct range *x = NULL, *y;
47 list_for_each_entry ( y, &r->range_list, list )
48 {
49 if ( y->s > s )
50 break;
51 x = y;
52 }
54 return x;
55 }
57 /* Return the lowest range in the set r, or NULL if r is empty. */
58 static struct range *first_range(
59 struct rangeset *r)
60 {
61 if ( list_empty(&r->range_list) )
62 return NULL;
63 return list_entry(r->range_list.next, struct range, list);
64 }
66 /* Return range following x in ascending order, or NULL if x is the highest. */
67 static struct range *next_range(
68 struct rangeset *r, struct range *x)
69 {
70 if ( x->list.next == &r->range_list )
71 return NULL;
72 return list_entry(x->list.next, struct range, list);
73 }
75 /* Insert range y after range x in r. Insert as first range if x is NULL. */
76 static void insert_range(
77 struct rangeset *r, struct range *x, struct range *y)
78 {
79 list_add(&y->list, (x != NULL) ? &x->list : &r->range_list);
80 }
82 /* Remove a range from its list and free it. */
83 static void destroy_range(
84 struct range *x)
85 {
86 list_del(&x->list);
87 xfree(x);
88 }
90 /*****************************
91 * Core public functions
92 */
94 int rangeset_add_range(
95 struct rangeset *r, unsigned long s, unsigned long e)
96 {
97 struct range *x, *y;
98 int rc = 0;
100 rc = xsm_add_range(r->domain, r->name, s, e);
101 if ( rc )
102 return rc;
104 ASSERT(s <= e);
106 spin_lock(&r->lock);
108 x = find_range(r, s);
109 y = find_range(r, e);
111 if ( x == y )
112 {
113 if ( (x == NULL) || ((x->e < s) && ((x->e + 1) != s)) )
114 {
115 x = xmalloc(struct range);
116 if ( x == NULL )
117 {
118 rc = -ENOMEM;
119 goto out;
120 }
122 x->s = s;
123 x->e = e;
125 insert_range(r, y, x);
126 }
127 else if ( x->e < e )
128 x->e = e;
129 }
130 else
131 {
132 if ( x == NULL )
133 {
134 x = first_range(r);
135 x->s = s;
136 }
137 else if ( (x->e < s) && ((x->e + 1) != s) )
138 {
139 x = next_range(r, x);
140 x->s = s;
141 }
143 x->e = (y->e > e) ? y->e : e;
145 for ( ; ; )
146 {
147 y = next_range(r, x);
148 if ( (y == NULL) || (y->e > x->e) )
149 break;
150 destroy_range(y);
151 }
152 }
154 y = next_range(r, x);
155 if ( (y != NULL) && ((x->e + 1) == y->s) )
156 {
157 x->e = y->e;
158 destroy_range(y);
159 }
161 out:
162 spin_unlock(&r->lock);
163 return rc;
164 }
166 int rangeset_remove_range(
167 struct rangeset *r, unsigned long s, unsigned long e)
168 {
169 struct range *x, *y, *t;
170 int rc = 0;
172 rc = xsm_remove_range(r->domain, r->name, s, e);
173 if ( rc )
174 return rc;
176 ASSERT(s <= e);
178 spin_lock(&r->lock);
180 x = find_range(r, s);
181 y = find_range(r, e);
183 if ( x == y )
184 {
185 if ( (x == NULL) || (x->e < s) )
186 goto out;
188 if ( (x->s < s) && (x->e > e) )
189 {
190 y = xmalloc(struct range);
191 if ( y == NULL )
192 {
193 rc = -ENOMEM;
194 goto out;
195 }
197 y->s = e + 1;
198 y->e = x->e;
199 x->e = s - 1;
201 insert_range(r, x, y);
202 }
203 else if ( (x->s == s) && (x->e <= e) )
204 destroy_range(x);
205 else if ( x->s == s )
206 x->s = e + 1;
207 else if ( x->e <= e )
208 x->e = s - 1;
209 }
210 else
211 {
212 if ( x == NULL )
213 x = first_range(r);
215 if ( x->s < s )
216 {
217 x->e = s - 1;
218 x = next_range(r, x);
219 }
221 while ( x != y )
222 {
223 t = x;
224 x = next_range(r, x);
225 destroy_range(t);
226 }
228 x->s = e + 1;
229 if ( x->s > x->e )
230 destroy_range(x);
231 }
233 out:
234 spin_unlock(&r->lock);
235 return rc;
236 }
238 int rangeset_contains_range(
239 struct rangeset *r, unsigned long s, unsigned long e)
240 {
241 struct range *x;
242 int contains;
244 ASSERT(s <= e);
246 spin_lock(&r->lock);
247 x = find_range(r, s);
248 contains = (x && (x->e >= e));
249 spin_unlock(&r->lock);
251 return contains;
252 }
254 int rangeset_add_singleton(
255 struct rangeset *r, unsigned long s)
256 {
257 return rangeset_add_range(r, s, s);
258 }
260 int rangeset_remove_singleton(
261 struct rangeset *r, unsigned long s)
262 {
263 return rangeset_remove_range(r, s, s);
264 }
266 int rangeset_contains_singleton(
267 struct rangeset *r, unsigned long s)
268 {
269 return rangeset_contains_range(r, s, s);
270 }
272 int rangeset_is_empty(
273 struct rangeset *r)
274 {
275 return ((r == NULL) || list_empty(&r->range_list));
276 }
278 struct rangeset *rangeset_new(
279 struct domain *d, char *name, unsigned int flags)
280 {
281 struct rangeset *r;
283 r = xmalloc(struct rangeset);
284 if ( r == NULL )
285 return NULL;
287 spin_lock_init(&r->lock);
288 INIT_LIST_HEAD(&r->range_list);
290 BUG_ON(flags & ~RANGESETF_prettyprint_hex);
291 r->flags = flags;
293 if ( name != NULL )
294 {
295 safe_strcpy(r->name, name);
296 }
297 else
298 {
299 snprintf(r->name, sizeof(r->name), "(no name)");
300 }
302 if ( (r->domain = d) != NULL )
303 {
304 spin_lock(&d->rangesets_lock);
305 list_add(&r->rangeset_list, &d->rangesets);
306 spin_unlock(&d->rangesets_lock);
307 }
309 return r;
310 }
312 void rangeset_destroy(
313 struct rangeset *r)
314 {
315 struct range *x;
317 if ( r == NULL )
318 return;
320 if ( r->domain != NULL )
321 {
322 spin_lock(&r->domain->rangesets_lock);
323 list_del(&r->rangeset_list);
324 spin_unlock(&r->domain->rangesets_lock);
325 }
327 while ( (x = first_range(r)) != NULL )
328 destroy_range(x);
330 xfree(r);
331 }
333 void rangeset_domain_initialise(
334 struct domain *d)
335 {
336 INIT_LIST_HEAD(&d->rangesets);
337 spin_lock_init(&d->rangesets_lock);
338 }
340 void rangeset_domain_destroy(
341 struct domain *d)
342 {
343 struct rangeset *r;
345 while ( !list_empty(&d->rangesets) )
346 {
347 r = list_entry(d->rangesets.next, struct rangeset, rangeset_list);
349 BUG_ON(r->domain != d);
350 r->domain = NULL;
351 list_del(&r->rangeset_list);
353 rangeset_destroy(r);
354 }
355 }
357 /*****************************
358 * Pretty-printing functions
359 */
361 static void print_limit(struct rangeset *r, unsigned long s)
362 {
363 printk((r->flags & RANGESETF_prettyprint_hex) ? "%lx" : "%lu", s);
364 }
366 void rangeset_printk(
367 struct rangeset *r)
368 {
369 int nr_printed = 0;
370 struct range *x;
372 spin_lock(&r->lock);
374 printk("%-10s {", r->name);
376 for ( x = first_range(r); x != NULL; x = next_range(r, x) )
377 {
378 if ( nr_printed++ )
379 printk(",");
380 printk(" ");
381 print_limit(r, x->s);
382 if ( x->s != x->e )
383 {
384 printk("-");
385 print_limit(r, x->e);
386 }
387 }
389 printk(" }");
391 spin_unlock(&r->lock);
392 }
394 void rangeset_domain_printk(
395 struct domain *d)
396 {
397 struct rangeset *r;
399 printk("Rangesets belonging to domain %u:\n", d->domain_id);
401 spin_lock(&d->rangesets_lock);
403 if ( list_empty(&d->rangesets) )
404 printk(" None\n");
406 list_for_each_entry ( r, &d->rangesets, rangeset_list )
407 {
408 printk(" ");
409 rangeset_printk(r);
410 printk("\n");
411 }
413 spin_unlock(&d->rangesets_lock);
414 }