ia64/xen-unstable

view xen/common/rangeset.c @ 12390:e28beea6d228

[IA64] Fix time services of EFI emulation

This patch serializes the execution of following efi.runtimes.
- GetTime
- SetTime
- GetWakeTime
- SetWakeTime

Linux/ia64 uses similar spinlocks in the EFI RTC driver.

Signed-off-by: Masaki Kanno <kanno.masaki@jp.fujitsu.com>
author awilliam@xenbuild.aw
date Fri Nov 10 12:03:19 2006 -0700 (2006-11-10)
parents 03fd2accb4d9
children b2c1eeee2dcf
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 strncpy(r->name, name, sizeof(r->name));
287 r->name[sizeof(r->name)-1] = '\0';
288 }
289 else
290 {
291 sprintf(r->name, "(no name)");
292 }
294 if ( (r->domain = d) != NULL )
295 {
296 spin_lock(&d->rangesets_lock);
297 list_add(&r->rangeset_list, &d->rangesets);
298 spin_unlock(&d->rangesets_lock);
299 }
301 return r;
302 }
304 void rangeset_destroy(
305 struct rangeset *r)
306 {
307 struct range *x;
309 if ( r == NULL )
310 return;
312 if ( r->domain != NULL )
313 {
314 spin_lock(&r->domain->rangesets_lock);
315 list_del(&r->rangeset_list);
316 spin_unlock(&r->domain->rangesets_lock);
317 }
319 while ( (x = first_range(r)) != NULL )
320 destroy_range(x);
322 xfree(r);
323 }
325 void rangeset_domain_initialise(
326 struct domain *d)
327 {
328 INIT_LIST_HEAD(&d->rangesets);
329 spin_lock_init(&d->rangesets_lock);
330 }
332 void rangeset_domain_destroy(
333 struct domain *d)
334 {
335 struct rangeset *r;
337 while ( !list_empty(&d->rangesets) )
338 {
339 r = list_entry(d->rangesets.next, struct rangeset, rangeset_list);
341 BUG_ON(r->domain != d);
342 r->domain = NULL;
343 list_del(&r->rangeset_list);
345 rangeset_destroy(r);
346 }
347 }
349 /*****************************
350 * Pretty-printing functions
351 */
353 static void print_limit(struct rangeset *r, unsigned long s)
354 {
355 printk((r->flags & RANGESETF_prettyprint_hex) ? "%lx" : "%lu", s);
356 }
358 void rangeset_printk(
359 struct rangeset *r)
360 {
361 int nr_printed = 0;
362 struct range *x;
364 spin_lock(&r->lock);
366 printk("%-10s {", r->name);
368 for ( x = first_range(r); x != NULL; x = next_range(r, x) )
369 {
370 if ( nr_printed++ )
371 printk(",");
372 printk(" ");
373 print_limit(r, x->s);
374 if ( x->s != x->e )
375 {
376 printk("-");
377 print_limit(r, x->e);
378 }
379 }
381 printk(" }");
383 spin_unlock(&r->lock);
384 }
386 void rangeset_domain_printk(
387 struct domain *d)
388 {
389 struct rangeset *r;
391 printk("Rangesets belonging to domain %u:\n", d->domain_id);
393 spin_lock(&d->rangesets_lock);
395 if ( list_empty(&d->rangesets) )
396 printk(" None\n");
398 list_for_each_entry ( r, &d->rangesets, rangeset_list )
399 {
400 printk(" ");
401 rangeset_printk(r);
402 printk("\n");
403 }
405 spin_unlock(&d->rangesets_lock);
406 }