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 */
9
10 #include <xen/sched.h>
11 #include <xen/errno.h>
12 #include <xen/rangeset.h>
13 #include <xsm/xsm.h>
14
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 };
20
21 struct rangeset {
22 /* Owning domain and threaded list of rangesets. */
23 struct list_head rangeset_list;
24 struct domain *domain;
25
26 /* Ordered list of ranges contained in this set, and protecting lock. */
27 struct list_head range_list;
28
29 /* Number of ranges that can be allocated */
30 long nr_ranges;
31 rwlock_t lock;
32
33 /* Pretty-printing name. */
34 char name[32];
35
36 /* RANGESETF flags. */
37 unsigned int flags;
38 };
39
40 /*****************************
41 * Private range functions hide the underlying linked-list implemnetation.
42 */
43
44 /* Find highest range lower than or containing s. NULL if no such range. */
find_range(struct rangeset * r,unsigned long s)45 static struct range *find_range(
46 struct rangeset *r, unsigned long s)
47 {
48 struct range *x = NULL, *y;
49
50 list_for_each_entry ( y, &r->range_list, list )
51 {
52 if ( y->s > s )
53 break;
54 x = y;
55 }
56
57 return x;
58 }
59
60 /* Return the lowest range in the set r, or NULL if r is empty. */
first_range(struct rangeset * r)61 static struct range *first_range(
62 struct rangeset *r)
63 {
64 if ( list_empty(&r->range_list) )
65 return NULL;
66 return list_entry(r->range_list.next, struct range, list);
67 }
68
69 /* Return range following x in ascending order, or NULL if x is the highest. */
next_range(struct rangeset * r,struct range * x)70 static struct range *next_range(
71 struct rangeset *r, struct range *x)
72 {
73 if ( x->list.next == &r->range_list )
74 return NULL;
75 return list_entry(x->list.next, struct range, list);
76 }
77
78 /* Insert range y after range x in r. Insert as first range if x is NULL. */
insert_range(struct rangeset * r,struct range * x,struct range * y)79 static void insert_range(
80 struct rangeset *r, struct range *x, struct range *y)
81 {
82 list_add(&y->list, (x != NULL) ? &x->list : &r->range_list);
83 }
84
85 /* Remove a range from its list and free it. */
destroy_range(struct rangeset * r,struct range * x)86 static void destroy_range(
87 struct rangeset *r, struct range *x)
88 {
89 r->nr_ranges++;
90
91 list_del(&x->list);
92 xfree(x);
93 }
94
95 /* Allocate a new range */
alloc_range(struct rangeset * r)96 static struct range *alloc_range(
97 struct rangeset *r)
98 {
99 struct range *x;
100
101 if ( r->nr_ranges == 0 )
102 return NULL;
103
104 x = xmalloc(struct range);
105 if ( x )
106 --r->nr_ranges;
107
108 return x;
109 }
110
111 /*****************************
112 * Core public functions
113 */
114
rangeset_add_range(struct rangeset * r,unsigned long s,unsigned long e)115 int rangeset_add_range(
116 struct rangeset *r, unsigned long s, unsigned long e)
117 {
118 struct range *x, *y;
119 int rc = 0;
120
121 ASSERT(s <= e);
122
123 write_lock(&r->lock);
124
125 x = find_range(r, s);
126 y = find_range(r, e);
127
128 if ( x == y )
129 {
130 if ( (x == NULL) || ((x->e < s) && ((x->e + 1) != s)) )
131 {
132 x = alloc_range(r);
133 if ( x == NULL )
134 {
135 rc = -ENOMEM;
136 goto out;
137 }
138
139 x->s = s;
140 x->e = e;
141
142 insert_range(r, y, x);
143 }
144 else if ( x->e < e )
145 x->e = e;
146 }
147 else
148 {
149 if ( x == NULL )
150 {
151 x = first_range(r);
152 x->s = s;
153 }
154 else if ( (x->e < s) && ((x->e + 1) != s) )
155 {
156 x = next_range(r, x);
157 x->s = s;
158 }
159
160 x->e = (y->e > e) ? y->e : e;
161
162 for ( ; ; )
163 {
164 y = next_range(r, x);
165 if ( (y == NULL) || (y->e > x->e) )
166 break;
167 destroy_range(r, y);
168 }
169 }
170
171 y = next_range(r, x);
172 if ( (y != NULL) && ((x->e + 1) == y->s) )
173 {
174 x->e = y->e;
175 destroy_range(r, y);
176 }
177
178 out:
179 write_unlock(&r->lock);
180 return rc;
181 }
182
rangeset_remove_range(struct rangeset * r,unsigned long s,unsigned long e)183 int rangeset_remove_range(
184 struct rangeset *r, unsigned long s, unsigned long e)
185 {
186 struct range *x, *y, *t;
187 int rc = 0;
188
189 ASSERT(s <= e);
190
191 write_lock(&r->lock);
192
193 x = find_range(r, s);
194 y = find_range(r, e);
195
196 if ( x == y )
197 {
198 if ( (x == NULL) || (x->e < s) )
199 goto out;
200
201 if ( (x->s < s) && (x->e > e) )
202 {
203 y = alloc_range(r);
204 if ( y == NULL )
205 {
206 rc = -ENOMEM;
207 goto out;
208 }
209
210 y->s = e + 1;
211 y->e = x->e;
212 x->e = s - 1;
213
214 insert_range(r, x, y);
215 }
216 else if ( (x->s == s) && (x->e <= e) )
217 destroy_range(r, x);
218 else if ( x->s == s )
219 x->s = e + 1;
220 else if ( x->e <= e )
221 x->e = s - 1;
222 }
223 else
224 {
225 if ( x == NULL )
226 x = first_range(r);
227
228 if ( x->s < s )
229 {
230 x->e = s - 1;
231 x = next_range(r, x);
232 }
233
234 while ( x != y )
235 {
236 t = x;
237 x = next_range(r, x);
238 destroy_range(r, t);
239 }
240
241 x->s = e + 1;
242 if ( x->s > x->e )
243 destroy_range(r, x);
244 }
245
246 out:
247 write_unlock(&r->lock);
248 return rc;
249 }
250
rangeset_contains_range(struct rangeset * r,unsigned long s,unsigned long e)251 bool_t rangeset_contains_range(
252 struct rangeset *r, unsigned long s, unsigned long e)
253 {
254 struct range *x;
255 bool_t contains;
256
257 ASSERT(s <= e);
258
259 read_lock(&r->lock);
260 x = find_range(r, s);
261 contains = (x && (x->e >= e));
262 read_unlock(&r->lock);
263
264 return contains;
265 }
266
rangeset_overlaps_range(struct rangeset * r,unsigned long s,unsigned long e)267 bool_t rangeset_overlaps_range(
268 struct rangeset *r, unsigned long s, unsigned long e)
269 {
270 struct range *x;
271 bool_t overlaps;
272
273 ASSERT(s <= e);
274
275 read_lock(&r->lock);
276 x = find_range(r, e);
277 overlaps = (x && (s <= x->e));
278 read_unlock(&r->lock);
279
280 return overlaps;
281 }
282
rangeset_report_ranges(struct rangeset * r,unsigned long s,unsigned long e,int (* cb)(unsigned long s,unsigned long e,void *),void * ctxt)283 int rangeset_report_ranges(
284 struct rangeset *r, unsigned long s, unsigned long e,
285 int (*cb)(unsigned long s, unsigned long e, void *), void *ctxt)
286 {
287 struct range *x;
288 int rc = 0;
289
290 read_lock(&r->lock);
291
292 for ( x = first_range(r); x && (x->s <= e) && !rc; x = next_range(r, x) )
293 if ( x->e >= s )
294 rc = cb(max(x->s, s), min(x->e, e), ctxt);
295
296 read_unlock(&r->lock);
297
298 return rc;
299 }
300
rangeset_claim_range(struct rangeset * r,unsigned long size,unsigned long * s)301 int rangeset_claim_range(struct rangeset *r, unsigned long size,
302 unsigned long *s)
303 {
304 struct range *prev, *next;
305 unsigned long start = 0;
306
307 write_lock(&r->lock);
308
309 for ( prev = NULL, next = first_range(r);
310 next;
311 prev = next, next = next_range(r, next) )
312 {
313 if ( (next->s - start) >= size )
314 goto insert;
315
316 if ( next->e == ~0UL )
317 goto out;
318
319 start = next->e + 1;
320 }
321
322 if ( (~0UL - start) + 1 >= size )
323 goto insert;
324
325 out:
326 write_unlock(&r->lock);
327 return -ENOSPC;
328
329 insert:
330 if ( unlikely(!prev) )
331 {
332 next = alloc_range(r);
333 if ( !next )
334 {
335 write_unlock(&r->lock);
336 return -ENOMEM;
337 }
338
339 next->s = start;
340 next->e = start + size - 1;
341 insert_range(r, prev, next);
342 }
343 else
344 prev->e += size;
345
346 write_unlock(&r->lock);
347
348 *s = start;
349
350 return 0;
351 }
352
rangeset_add_singleton(struct rangeset * r,unsigned long s)353 int rangeset_add_singleton(
354 struct rangeset *r, unsigned long s)
355 {
356 return rangeset_add_range(r, s, s);
357 }
358
rangeset_remove_singleton(struct rangeset * r,unsigned long s)359 int rangeset_remove_singleton(
360 struct rangeset *r, unsigned long s)
361 {
362 return rangeset_remove_range(r, s, s);
363 }
364
rangeset_contains_singleton(struct rangeset * r,unsigned long s)365 bool_t rangeset_contains_singleton(
366 struct rangeset *r, unsigned long s)
367 {
368 return rangeset_contains_range(r, s, s);
369 }
370
rangeset_is_empty(const struct rangeset * r)371 bool_t rangeset_is_empty(
372 const struct rangeset *r)
373 {
374 return ((r == NULL) || list_empty(&r->range_list));
375 }
376
rangeset_new(struct domain * d,char * name,unsigned int flags)377 struct rangeset *rangeset_new(
378 struct domain *d, char *name, unsigned int flags)
379 {
380 struct rangeset *r;
381
382 r = xmalloc(struct rangeset);
383 if ( r == NULL )
384 return NULL;
385
386 rwlock_init(&r->lock);
387 INIT_LIST_HEAD(&r->range_list);
388 r->nr_ranges = -1;
389
390 BUG_ON(flags & ~RANGESETF_prettyprint_hex);
391 r->flags = flags;
392
393 if ( name != NULL )
394 {
395 safe_strcpy(r->name, name);
396 }
397 else
398 {
399 snprintf(r->name, sizeof(r->name), "(no name)");
400 }
401
402 if ( (r->domain = d) != NULL )
403 {
404 spin_lock(&d->rangesets_lock);
405 list_add(&r->rangeset_list, &d->rangesets);
406 spin_unlock(&d->rangesets_lock);
407 }
408
409 return r;
410 }
411
rangeset_destroy(struct rangeset * r)412 void rangeset_destroy(
413 struct rangeset *r)
414 {
415 struct range *x;
416
417 if ( r == NULL )
418 return;
419
420 if ( r->domain != NULL )
421 {
422 spin_lock(&r->domain->rangesets_lock);
423 list_del(&r->rangeset_list);
424 spin_unlock(&r->domain->rangesets_lock);
425 }
426
427 while ( (x = first_range(r)) != NULL )
428 destroy_range(r, x);
429
430 xfree(r);
431 }
432
rangeset_limit(struct rangeset * r,unsigned int limit)433 void rangeset_limit(
434 struct rangeset *r, unsigned int limit)
435 {
436 r->nr_ranges = limit;
437 }
438
rangeset_domain_initialise(struct domain * d)439 void rangeset_domain_initialise(
440 struct domain *d)
441 {
442 INIT_LIST_HEAD(&d->rangesets);
443 spin_lock_init(&d->rangesets_lock);
444 }
445
rangeset_domain_destroy(struct domain * d)446 void rangeset_domain_destroy(
447 struct domain *d)
448 {
449 struct rangeset *r;
450
451 while ( !list_empty(&d->rangesets) )
452 {
453 r = list_entry(d->rangesets.next, struct rangeset, rangeset_list);
454
455 BUG_ON(r->domain != d);
456 r->domain = NULL;
457 list_del(&r->rangeset_list);
458
459 rangeset_destroy(r);
460 }
461 }
462
rangeset_swap(struct rangeset * a,struct rangeset * b)463 void rangeset_swap(struct rangeset *a, struct rangeset *b)
464 {
465 LIST_HEAD(tmp);
466
467 if ( a < b )
468 {
469 write_lock(&a->lock);
470 write_lock(&b->lock);
471 }
472 else
473 {
474 write_lock(&b->lock);
475 write_lock(&a->lock);
476 }
477
478 list_splice_init(&a->range_list, &tmp);
479 list_splice_init(&b->range_list, &a->range_list);
480 list_splice(&tmp, &b->range_list);
481
482 write_unlock(&a->lock);
483 write_unlock(&b->lock);
484 }
485
486 /*****************************
487 * Pretty-printing functions
488 */
489
print_limit(struct rangeset * r,unsigned long s)490 static void print_limit(struct rangeset *r, unsigned long s)
491 {
492 printk((r->flags & RANGESETF_prettyprint_hex) ? "%lx" : "%lu", s);
493 }
494
rangeset_printk(struct rangeset * r)495 void rangeset_printk(
496 struct rangeset *r)
497 {
498 int nr_printed = 0;
499 struct range *x;
500
501 read_lock(&r->lock);
502
503 printk("%-10s {", r->name);
504
505 for ( x = first_range(r); x != NULL; x = next_range(r, x) )
506 {
507 if ( nr_printed++ )
508 printk(",");
509 printk(" ");
510 print_limit(r, x->s);
511 if ( x->s != x->e )
512 {
513 printk("-");
514 print_limit(r, x->e);
515 }
516 }
517
518 printk(" }");
519
520 read_unlock(&r->lock);
521 }
522
rangeset_domain_printk(struct domain * d)523 void rangeset_domain_printk(
524 struct domain *d)
525 {
526 struct rangeset *r;
527
528 printk("Rangesets belonging to domain %u:\n", d->domain_id);
529
530 spin_lock(&d->rangesets_lock);
531
532 if ( list_empty(&d->rangesets) )
533 printk(" None\n");
534
535 list_for_each_entry ( r, &d->rangesets, rangeset_list )
536 {
537 printk(" ");
538 rangeset_printk(r);
539 printk("\n");
540 }
541
542 spin_unlock(&d->rangesets_lock);
543 }
544
545 /*
546 * Local variables:
547 * mode: C
548 * c-file-style: "BSD"
549 * c-basic-offset: 4
550 * tab-width: 4
551 * indent-tabs-mode: nil
552 * End:
553 */
554