ia64/xen-unstable

view xen/common/rangeset.c @ 9706:3c05406f5e0a

In some cases, say for instance for some bizzare reason
the tree was checked out of CVS, which doens't neccessarily
store file permissions, mkbuildtree may not be executable.
So run them explicitly via bash.

Signed-Off-By: Horms <horms@verge.net.au>
author kaf24@firebug.cl.cam.ac.uk
date Thu Apr 13 11:24:00 2006 +0100 (2006-04-13)
parents 03382076472c
children 03fd2accb4d9
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/rangeset.h>
13 /* An inclusive range [s,e] and pointer to next range in ascending order. */
14 struct range {
15 struct list_head list;
16 unsigned long s, e;
17 };
19 struct rangeset {
20 /* Owning domain and threaded list of rangesets. */
21 struct list_head rangeset_list;
22 struct domain *domain;
24 /* Ordered list of ranges contained in this set, and protecting lock. */
25 struct list_head range_list;
26 spinlock_t lock;
28 /* Pretty-printing name. */
29 char name[32];
31 /* RANGESETF flags. */
32 unsigned int flags;
33 };
35 /*****************************
36 * Private range functions hide the underlying linked-list implemnetation.
37 */
39 /* Find highest range lower than or containing s. NULL if no such range. */
40 static struct range *find_range(
41 struct rangeset *r, unsigned long s)
42 {
43 struct range *x = NULL, *y;
45 list_for_each_entry ( y, &r->range_list, list )
46 {
47 if ( y->s > s )
48 break;
49 x = y;
50 }
52 return x;
53 }
55 /* Return the lowest range in the set r, or NULL if r is empty. */
56 static struct range *first_range(
57 struct rangeset *r)
58 {
59 if ( list_empty(&r->range_list) )
60 return NULL;
61 return list_entry(r->range_list.next, struct range, list);
62 }
64 /* Return range following x in ascending order, or NULL if x is the highest. */
65 static struct range *next_range(
66 struct rangeset *r, struct range *x)
67 {
68 if ( x->list.next == &r->range_list )
69 return NULL;
70 return list_entry(x->list.next, struct range, list);
71 }
73 /* Insert range y after range x in r. Insert as first range if x is NULL. */
74 static void insert_range(
75 struct rangeset *r, struct range *x, struct range *y)
76 {
77 list_add(&y->list, (x != NULL) ? &x->list : &r->range_list);
78 }
80 /* Remove a range from its list and free it. */
81 static void destroy_range(
82 struct range *x)
83 {
84 list_del(&x->list);
85 xfree(x);
86 }
88 /*****************************
89 * Core public functions
90 */
92 int rangeset_add_range(
93 struct rangeset *r, unsigned long s, unsigned long e)
94 {
95 struct range *x, *y;
96 int rc = 0;
98 ASSERT(s <= e);
100 spin_lock(&r->lock);
102 x = find_range(r, s);
103 y = find_range(r, e);
105 if ( x == y )
106 {
107 if ( (x == NULL) || ((x->e < s) && ((x->e + 1) != s)) )
108 {
109 x = xmalloc(struct range);
110 if ( x == NULL )
111 {
112 rc = -ENOMEM;
113 goto out;
114 }
116 x->s = s;
117 x->e = e;
119 insert_range(r, y, x);
120 }
121 else if ( x->e < e )
122 x->e = e;
123 }
124 else
125 {
126 if ( x == NULL )
127 {
128 x = first_range(r);
129 x->s = s;
130 }
131 else if ( (x->e < s) && ((x->e + 1) != s) )
132 {
133 x = next_range(r, x);
134 x->s = s;
135 }
137 x->e = (y->e > e) ? y->e : e;
139 for ( ; ; )
140 {
141 y = next_range(r, x);
142 if ( (y == NULL) || (y->e > x->e) )
143 break;
144 destroy_range(y);
145 }
146 }
148 y = next_range(r, x);
149 if ( (y != NULL) && ((x->e + 1) == y->s) )
150 {
151 x->e = y->e;
152 destroy_range(y);
153 }
155 out:
156 spin_unlock(&r->lock);
157 return rc;
158 }
160 int rangeset_remove_range(
161 struct rangeset *r, unsigned long s, unsigned long e)
162 {
163 struct range *x, *y, *t;
164 int rc = 0;
166 ASSERT(s <= e);
168 spin_lock(&r->lock);
170 x = find_range(r, s);
171 y = find_range(r, e);
173 if ( x == y )
174 {
175 if ( (x == NULL) || (x->e < s) )
176 goto out;
178 if ( (x->s < s) && (x->e > e) )
179 {
180 y = xmalloc(struct range);
181 if ( y == NULL )
182 {
183 rc = -ENOMEM;
184 goto out;
185 }
187 y->s = e + 1;
188 y->e = x->e;
189 x->e = s - 1;
191 insert_range(r, x, y);
192 }
193 else if ( (x->s == s) && (x->e <= e) )
194 destroy_range(x);
195 else if ( x->s == s )
196 x->s = e + 1;
197 else if ( x->e <= e )
198 x->e = s - 1;
199 }
200 else
201 {
202 if ( x == NULL )
203 x = first_range(r);
205 if ( x->s < s )
206 {
207 x->e = s - 1;
208 x = next_range(r, x);
209 }
211 while ( x != y )
212 {
213 t = x;
214 x = next_range(r, x);
215 destroy_range(t);
216 }
218 x->s = e + 1;
219 if ( x->s > x->e )
220 destroy_range(x);
221 }
223 out:
224 spin_unlock(&r->lock);
225 return rc;
226 }
228 int rangeset_contains_range(
229 struct rangeset *r, unsigned long s, unsigned long e)
230 {
231 struct range *x;
232 int contains;
234 ASSERT(s <= e);
236 spin_lock(&r->lock);
237 x = find_range(r, s);
238 contains = (x && (x->e >= e));
239 spin_unlock(&r->lock);
241 return contains;
242 }
244 int rangeset_add_singleton(
245 struct rangeset *r, unsigned long s)
246 {
247 return rangeset_add_range(r, s, s);
248 }
250 int rangeset_remove_singleton(
251 struct rangeset *r, unsigned long s)
252 {
253 return rangeset_remove_range(r, s, s);
254 }
256 int rangeset_contains_singleton(
257 struct rangeset *r, unsigned long s)
258 {
259 return rangeset_contains_range(r, s, s);
260 }
262 int rangeset_is_empty(
263 struct rangeset *r)
264 {
265 return list_empty(&r->range_list);
266 }
268 struct rangeset *rangeset_new(
269 struct domain *d, char *name, unsigned int flags)
270 {
271 struct rangeset *r;
273 r = xmalloc(struct rangeset);
274 if ( r == NULL )
275 return NULL;
277 spin_lock_init(&r->lock);
278 INIT_LIST_HEAD(&r->range_list);
280 BUG_ON(flags & ~RANGESETF_prettyprint_hex);
281 r->flags = flags;
283 if ( name != NULL )
284 {
285 strncpy(r->name, name, sizeof(r->name));
286 r->name[sizeof(r->name)-1] = '\0';
287 }
288 else
289 {
290 sprintf(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 }