ia64/xen-unstable

view xen/common/rangeset.c @ 15647:cc48264ed647

Merge
author Tim Deegan <Tim.Deegan@xensource.com>
date Tue Jul 24 14:53:06 2007 +0100 (2007-07-24)
parents bef7fbe25a9f
children 6236adfbebe6
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>
14 /* An inclusive range [s,e] and pointer to next range in ascending order. */
15 struct range {
16 struct list_head list;
17 unsigned long s, e;
18 };
20 struct rangeset {
21 /* Owning domain and threaded list of rangesets. */
22 struct list_head rangeset_list;
23 struct domain *domain;
25 /* Ordered list of ranges contained in this set, and protecting lock. */
26 struct list_head range_list;
27 spinlock_t lock;
29 /* Pretty-printing name. */
30 char name[32];
32 /* RANGESETF flags. */
33 unsigned int flags;
34 };
36 /*****************************
37 * Private range functions hide the underlying linked-list implemnetation.
38 */
40 /* Find highest range lower than or containing s. NULL if no such range. */
41 static struct range *find_range(
42 struct rangeset *r, unsigned long s)
43 {
44 struct range *x = NULL, *y;
46 list_for_each_entry ( y, &r->range_list, list )
47 {
48 if ( y->s > s )
49 break;
50 x = y;
51 }
53 return x;
54 }
56 /* Return the lowest range in the set r, or NULL if r is empty. */
57 static struct range *first_range(
58 struct rangeset *r)
59 {
60 if ( list_empty(&r->range_list) )
61 return NULL;
62 return list_entry(r->range_list.next, struct range, list);
63 }
65 /* Return range following x in ascending order, or NULL if x is the highest. */
66 static struct range *next_range(
67 struct rangeset *r, struct range *x)
68 {
69 if ( x->list.next == &r->range_list )
70 return NULL;
71 return list_entry(x->list.next, struct range, list);
72 }
74 /* Insert range y after range x in r. Insert as first range if x is NULL. */
75 static void insert_range(
76 struct rangeset *r, struct range *x, struct range *y)
77 {
78 list_add(&y->list, (x != NULL) ? &x->list : &r->range_list);
79 }
81 /* Remove a range from its list and free it. */
82 static void destroy_range(
83 struct range *x)
84 {
85 list_del(&x->list);
86 xfree(x);
87 }
89 /*****************************
90 * Core public functions
91 */
93 int rangeset_add_range(
94 struct rangeset *r, unsigned long s, unsigned long e)
95 {
96 struct range *x, *y;
97 int rc = 0;
99 ASSERT(s <= e);
101 spin_lock(&r->lock);
103 x = find_range(r, s);
104 y = find_range(r, e);
106 if ( x == y )
107 {
108 if ( (x == NULL) || ((x->e < s) && ((x->e + 1) != s)) )
109 {
110 x = xmalloc(struct range);
111 if ( x == NULL )
112 {
113 rc = -ENOMEM;
114 goto out;
115 }
117 x->s = s;
118 x->e = e;
120 insert_range(r, y, x);
121 }
122 else if ( x->e < e )
123 x->e = e;
124 }
125 else
126 {
127 if ( x == NULL )
128 {
129 x = first_range(r);
130 x->s = s;
131 }
132 else if ( (x->e < s) && ((x->e + 1) != s) )
133 {
134 x = next_range(r, x);
135 x->s = s;
136 }
138 x->e = (y->e > e) ? y->e : e;
140 for ( ; ; )
141 {
142 y = next_range(r, x);
143 if ( (y == NULL) || (y->e > x->e) )
144 break;
145 destroy_range(y);
146 }
147 }
149 y = next_range(r, x);
150 if ( (y != NULL) && ((x->e + 1) == y->s) )
151 {
152 x->e = y->e;
153 destroy_range(y);
154 }
156 out:
157 spin_unlock(&r->lock);
158 return rc;
159 }
161 int rangeset_remove_range(
162 struct rangeset *r, unsigned long s, unsigned long e)
163 {
164 struct range *x, *y, *t;
165 int rc = 0;
167 ASSERT(s <= e);
169 spin_lock(&r->lock);
171 x = find_range(r, s);
172 y = find_range(r, e);
174 if ( x == y )
175 {
176 if ( (x == NULL) || (x->e < s) )
177 goto out;
179 if ( (x->s < s) && (x->e > e) )
180 {
181 y = xmalloc(struct range);
182 if ( y == NULL )
183 {
184 rc = -ENOMEM;
185 goto out;
186 }
188 y->s = e + 1;
189 y->e = x->e;
190 x->e = s - 1;
192 insert_range(r, x, y);
193 }
194 else if ( (x->s == s) && (x->e <= e) )
195 destroy_range(x);
196 else if ( x->s == s )
197 x->s = e + 1;
198 else if ( x->e <= e )
199 x->e = s - 1;
200 }
201 else
202 {
203 if ( x == NULL )
204 x = first_range(r);
206 if ( x->s < s )
207 {
208 x->e = s - 1;
209 x = next_range(r, x);
210 }
212 while ( x != y )
213 {
214 t = x;
215 x = next_range(r, x);
216 destroy_range(t);
217 }
219 x->s = e + 1;
220 if ( x->s > x->e )
221 destroy_range(x);
222 }
224 out:
225 spin_unlock(&r->lock);
226 return rc;
227 }
229 int rangeset_contains_range(
230 struct rangeset *r, unsigned long s, unsigned long e)
231 {
232 struct range *x;
233 int contains;
235 ASSERT(s <= e);
237 spin_lock(&r->lock);
238 x = find_range(r, s);
239 contains = (x && (x->e >= e));
240 spin_unlock(&r->lock);
242 return contains;
243 }
245 int rangeset_add_singleton(
246 struct rangeset *r, unsigned long s)
247 {
248 return rangeset_add_range(r, s, s);
249 }
251 int rangeset_remove_singleton(
252 struct rangeset *r, unsigned long s)
253 {
254 return rangeset_remove_range(r, s, s);
255 }
257 int rangeset_contains_singleton(
258 struct rangeset *r, unsigned long s)
259 {
260 return rangeset_contains_range(r, s, s);
261 }
263 int rangeset_is_empty(
264 struct rangeset *r)
265 {
266 return list_empty(&r->range_list);
267 }
269 struct rangeset *rangeset_new(
270 struct domain *d, char *name, unsigned int flags)
271 {
272 struct rangeset *r;
274 r = xmalloc(struct rangeset);
275 if ( r == NULL )
276 return NULL;
278 spin_lock_init(&r->lock);
279 INIT_LIST_HEAD(&r->range_list);
281 BUG_ON(flags & ~RANGESETF_prettyprint_hex);
282 r->flags = flags;
284 if ( name != NULL )
285 {
286 safe_strcpy(r->name, name);
287 }
288 else
289 {
290 snprintf(r->name, sizeof(r->name), "(no name)");
291 }
293 if ( (r->domain = d) != NULL )
294 {
295 spin_lock(&d->rangesets_lock);
296 list_add(&r->rangeset_list, &d->rangesets);
297 spin_unlock(&d->rangesets_lock);
298 }
300 return r;
301 }
303 void rangeset_destroy(
304 struct rangeset *r)
305 {
306 struct range *x;
308 if ( r == NULL )
309 return;
311 if ( r->domain != NULL )
312 {
313 spin_lock(&r->domain->rangesets_lock);
314 list_del(&r->rangeset_list);
315 spin_unlock(&r->domain->rangesets_lock);
316 }
318 while ( (x = first_range(r)) != NULL )
319 destroy_range(x);
321 xfree(r);
322 }
324 void rangeset_domain_initialise(
325 struct domain *d)
326 {
327 INIT_LIST_HEAD(&d->rangesets);
328 spin_lock_init(&d->rangesets_lock);
329 }
331 void rangeset_domain_destroy(
332 struct domain *d)
333 {
334 struct rangeset *r;
336 while ( !list_empty(&d->rangesets) )
337 {
338 r = list_entry(d->rangesets.next, struct rangeset, rangeset_list);
340 BUG_ON(r->domain != d);
341 r->domain = NULL;
342 list_del(&r->rangeset_list);
344 rangeset_destroy(r);
345 }
346 }
348 /*****************************
349 * Pretty-printing functions
350 */
352 static void print_limit(struct rangeset *r, unsigned long s)
353 {
354 printk((r->flags & RANGESETF_prettyprint_hex) ? "%lx" : "%lu", s);
355 }
357 void rangeset_printk(
358 struct rangeset *r)
359 {
360 int nr_printed = 0;
361 struct range *x;
363 spin_lock(&r->lock);
365 printk("%-10s {", r->name);
367 for ( x = first_range(r); x != NULL; x = next_range(r, x) )
368 {
369 if ( nr_printed++ )
370 printk(",");
371 printk(" ");
372 print_limit(r, x->s);
373 if ( x->s != x->e )
374 {
375 printk("-");
376 print_limit(r, x->e);
377 }
378 }
380 printk(" }");
382 spin_unlock(&r->lock);
383 }
385 void rangeset_domain_printk(
386 struct domain *d)
387 {
388 struct rangeset *r;
390 printk("Rangesets belonging to domain %u:\n", d->domain_id);
392 spin_lock(&d->rangesets_lock);
394 if ( list_empty(&d->rangesets) )
395 printk(" None\n");
397 list_for_each_entry ( r, &d->rangesets, rangeset_list )
398 {
399 printk(" ");
400 rangeset_printk(r);
401 printk("\n");
402 }
404 spin_unlock(&d->rangesets_lock);
405 }