ia64/xen-unstable

view xen/common/rangeset.c @ 17062:0769835cf50f

x86 shadow: Reduce scope of shadow lock.

emulate_map_dest doesn't require holding lock, since
only shadow related operation possibly involved is to
remove shadow which is less frequent and can acquire
lock inside. Rest are either guest table walk or
per-vcpu monitor table manipulation

Signed-off-by Kevin Tian <kevin.tian@intel.com>
author Keir Fraser <keir.fraser@citrix.com>
date Thu Feb 14 10:33:12 2008 +0000 (2008-02-14)
parents 6236adfbebe6
children 44f039c4aee4
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 ((r == NULL) || 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 }