ia64/xen-unstable

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