debuggers.hg

view xen/common/rangeset.c @ 22227:fecdbe814a9f

rangesets: add function to query for overlaps

Signed-off-by: Jan Beulich <jbeulich@novell.com>
author Keir Fraser <keir.fraser@citrix.com>
date Mon Sep 20 18:50:06 2010 +0100 (2010-09-20)
parents 7a206c6f216a
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_overlaps_range(
255 struct rangeset *r, unsigned long s, unsigned long e)
256 {
257 struct range *x;
258 int overlaps;
260 ASSERT(s <= e);
262 spin_lock(&r->lock);
263 x = find_range(r, e);
264 overlaps = (x && (s <= x->e));
265 spin_unlock(&r->lock);
267 return overlaps;
268 }
270 int rangeset_report_ranges(
271 struct rangeset *r, unsigned long s, unsigned long e,
272 int (*cb)(unsigned long s, unsigned long e, void *), void *ctxt)
273 {
274 struct range *x;
275 int rc = 0;
277 spin_lock(&r->lock);
279 for ( x = find_range(r, s); x && (x->s <= e) && !rc; x = next_range(r, x) )
280 if ( x->e >= s )
281 rc = cb(max(x->s, s), min(x->e, e), ctxt);
283 spin_unlock(&r->lock);
285 return rc;
286 }
288 int rangeset_add_singleton(
289 struct rangeset *r, unsigned long s)
290 {
291 return rangeset_add_range(r, s, s);
292 }
294 int rangeset_remove_singleton(
295 struct rangeset *r, unsigned long s)
296 {
297 return rangeset_remove_range(r, s, s);
298 }
300 int rangeset_contains_singleton(
301 struct rangeset *r, unsigned long s)
302 {
303 return rangeset_contains_range(r, s, s);
304 }
306 int rangeset_is_empty(
307 struct rangeset *r)
308 {
309 return ((r == NULL) || list_empty(&r->range_list));
310 }
312 struct rangeset *rangeset_new(
313 struct domain *d, char *name, unsigned int flags)
314 {
315 struct rangeset *r;
317 r = xmalloc(struct rangeset);
318 if ( r == NULL )
319 return NULL;
321 spin_lock_init(&r->lock);
322 INIT_LIST_HEAD(&r->range_list);
324 BUG_ON(flags & ~RANGESETF_prettyprint_hex);
325 r->flags = flags;
327 if ( name != NULL )
328 {
329 safe_strcpy(r->name, name);
330 }
331 else
332 {
333 snprintf(r->name, sizeof(r->name), "(no name)");
334 }
336 if ( (r->domain = d) != NULL )
337 {
338 spin_lock(&d->rangesets_lock);
339 list_add(&r->rangeset_list, &d->rangesets);
340 spin_unlock(&d->rangesets_lock);
341 }
343 return r;
344 }
346 void rangeset_destroy(
347 struct rangeset *r)
348 {
349 struct range *x;
351 if ( r == NULL )
352 return;
354 if ( r->domain != NULL )
355 {
356 spin_lock(&r->domain->rangesets_lock);
357 list_del(&r->rangeset_list);
358 spin_unlock(&r->domain->rangesets_lock);
359 }
361 while ( (x = first_range(r)) != NULL )
362 destroy_range(x);
364 xfree(r);
365 }
367 void rangeset_domain_initialise(
368 struct domain *d)
369 {
370 INIT_LIST_HEAD(&d->rangesets);
371 spin_lock_init(&d->rangesets_lock);
372 }
374 void rangeset_domain_destroy(
375 struct domain *d)
376 {
377 struct rangeset *r;
379 while ( !list_empty(&d->rangesets) )
380 {
381 r = list_entry(d->rangesets.next, struct rangeset, rangeset_list);
383 BUG_ON(r->domain != d);
384 r->domain = NULL;
385 list_del(&r->rangeset_list);
387 rangeset_destroy(r);
388 }
389 }
391 /*****************************
392 * Pretty-printing functions
393 */
395 static void print_limit(struct rangeset *r, unsigned long s)
396 {
397 printk((r->flags & RANGESETF_prettyprint_hex) ? "%lx" : "%lu", s);
398 }
400 void rangeset_printk(
401 struct rangeset *r)
402 {
403 int nr_printed = 0;
404 struct range *x;
406 spin_lock(&r->lock);
408 printk("%-10s {", r->name);
410 for ( x = first_range(r); x != NULL; x = next_range(r, x) )
411 {
412 if ( nr_printed++ )
413 printk(",");
414 printk(" ");
415 print_limit(r, x->s);
416 if ( x->s != x->e )
417 {
418 printk("-");
419 print_limit(r, x->e);
420 }
421 }
423 printk(" }");
425 spin_unlock(&r->lock);
426 }
428 void rangeset_domain_printk(
429 struct domain *d)
430 {
431 struct rangeset *r;
433 printk("Rangesets belonging to domain %u:\n", d->domain_id);
435 spin_lock(&d->rangesets_lock);
437 if ( list_empty(&d->rangesets) )
438 printk(" None\n");
440 list_for_each_entry ( r, &d->rangesets, rangeset_list )
441 {
442 printk(" ");
443 rangeset_printk(r);
444 printk("\n");
445 }
447 spin_unlock(&d->rangesets_lock);
448 }