direct-io.hg

changeset 8448:8d0b62f0aa8d

Add auto-destructing per-domain rangeset data structure,
for representing sets of contiguous numeric ranges. This
will be used for representing permissions lists (e.g.,
io memory, io ports, irqs).

Signed-off-by: Keir Fraser <keir@xensource.com>
author kaf24@firebug.cl.cam.ac.uk
date Thu Dec 29 15:47:23 2005 +0100 (2005-12-29)
parents 188ef899e626
children b54e981957eb
files xen/common/domain.c xen/common/keyhandler.c xen/common/rangeset.c xen/include/xen/rangeset.h xen/include/xen/sched.h
line diff
     1.1 --- a/xen/common/domain.c	Wed Dec 28 16:23:42 2005 +0100
     1.2 +++ b/xen/common/domain.c	Thu Dec 29 15:47:23 2005 +0100
     1.3 @@ -16,6 +16,7 @@
     1.4  #include <xen/console.h>
     1.5  #include <xen/softirq.h>
     1.6  #include <xen/domain_page.h>
     1.7 +#include <xen/rangeset.h>
     1.8  #include <asm/debugger.h>
     1.9  #include <public/dom0_ops.h>
    1.10  #include <public/sched.h>
    1.11 @@ -66,6 +67,8 @@ struct domain *do_createdomain(domid_t d
    1.12          return NULL;
    1.13      }
    1.14  
    1.15 +    rangeset_domain_initialise(d);
    1.16 +
    1.17      arch_do_createdomain(v);
    1.18      
    1.19      if ( !is_idle_task(d) )
    1.20 @@ -271,6 +274,8 @@ void domain_destruct(struct domain *d)
    1.21      *pd = d->next_in_hashbucket;
    1.22      write_unlock(&domlist_lock);
    1.23  
    1.24 +    rangeset_domain_destroy(d);
    1.25 +
    1.26      evtchn_destroy(d);
    1.27      grant_table_destroy(d);
    1.28  
     2.1 --- a/xen/common/keyhandler.c	Wed Dec 28 16:23:42 2005 +0100
     2.2 +++ b/xen/common/keyhandler.c	Thu Dec 29 15:47:23 2005 +0100
     2.3 @@ -11,6 +11,7 @@
     2.4  #include <xen/sched.h>
     2.5  #include <xen/softirq.h>
     2.6  #include <xen/domain.h>
     2.7 +#include <xen/rangeset.h>
     2.8  #include <asm/debugger.h>
     2.9  
    2.10  #define KEY_MAX 256
    2.11 @@ -122,6 +123,8 @@ static void do_task_queues(unsigned char
    2.12                 d->handle[ 8], d->handle[ 9], d->handle[10], d->handle[11],
    2.13                 d->handle[12], d->handle[13], d->handle[14], d->handle[15]);
    2.14  
    2.15 +        rangeset_domain_printk(d);
    2.16 +
    2.17          dump_pageframe_info(d);
    2.18                 
    2.19          for_each_vcpu ( d, v ) {
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/xen/common/rangeset.c	Thu Dec 29 15:47:23 2005 +0100
     3.3 @@ -0,0 +1,356 @@
     3.4 +/******************************************************************************
     3.5 + * rangeset.c
     3.6 + * 
     3.7 + * Creation, maintenance and automatic destruction of per-domain sets of
     3.8 + * numeric ranges.
     3.9 + * 
    3.10 + * Copyright (c) 2005, K A Fraser
    3.11 + */
    3.12 +
    3.13 +#include <xen/sched.h>
    3.14 +#include <xen/rangeset.h>
    3.15 +
    3.16 +/* An inclusive range [s,e] and pointer to next range in ascending order. */
    3.17 +struct range {
    3.18 +    struct list_head list;
    3.19 +    unsigned long s, e;
    3.20 +};
    3.21 +
    3.22 +struct rangeset {
    3.23 +    /* Owning domain and threaded list of rangesets. */
    3.24 +    struct list_head rangeset_list;
    3.25 +    struct domain   *domain;
    3.26 +
    3.27 +    /* Ordered list of ranges contained in this set, and protecting lock. */
    3.28 +    struct list_head range_list;
    3.29 +    spinlock_t       lock;
    3.30 +
    3.31 +    /* Pretty-printing name. */
    3.32 +    char             name[32];
    3.33 +
    3.34 +    /* RANGESETF_??? */
    3.35 +    unsigned int     flags;
    3.36 +};
    3.37 +
    3.38 +/* Find highest range lower than or containing s. NULL if no such range. */
    3.39 +static struct range *find_range(
    3.40 +    struct rangeset *r, unsigned long s)
    3.41 +{
    3.42 +    struct range *x = NULL, *y;
    3.43 +
    3.44 +    list_for_each_entry ( y, &r->range_list, list )
    3.45 +    {
    3.46 +        if ( y->s > s )
    3.47 +            break;
    3.48 +        x = y;
    3.49 +    }
    3.50 +
    3.51 +    return x;
    3.52 +}
    3.53 +
    3.54 +/* Remove a range from its list and free it. */
    3.55 +static void destroy_range(
    3.56 +    struct range *x)
    3.57 +{
    3.58 +    list_del(&x->list);
    3.59 +    xfree(x);
    3.60 +}
    3.61 +
    3.62 +int rangeset_add_range(
    3.63 +    struct rangeset *r, unsigned long s, unsigned long e)
    3.64 +{
    3.65 +    struct range *x, *y;
    3.66 +    int rc = 0;
    3.67 +
    3.68 +    spin_lock(&r->lock);
    3.69 +
    3.70 +    x = find_range(r, s);
    3.71 +    y = find_range(r, e);
    3.72 +
    3.73 +    if ( x == y )
    3.74 +    {
    3.75 +        if ( (x == NULL) || ((x->e < s) && ((x->e + 1) != s)) )
    3.76 +        {
    3.77 +            x = xmalloc(struct range);
    3.78 +            if ( x == NULL )
    3.79 +            {
    3.80 +                rc = -ENOMEM;
    3.81 +                goto out;
    3.82 +            }
    3.83 +
    3.84 +            x->s = s;
    3.85 +            x->e = e;
    3.86 +
    3.87 +            list_add(&x->list, (y != NULL) ? &y->list : &r->range_list);
    3.88 +        }
    3.89 +        
    3.90 +        if ( x->e < e )
    3.91 +            x->e = e;
    3.92 +    }
    3.93 +    else
    3.94 +    {
    3.95 +        if ( x == NULL )
    3.96 +        {
    3.97 +            x = list_entry(r->range_list.next, struct range, list);
    3.98 +            x->s = s;
    3.99 +        }
   3.100 +        else if ( (x->e < s) && ((x->e + 1) != s) )
   3.101 +        {
   3.102 +            x = list_entry(x->list.next, struct range, list);
   3.103 +            x->s = s;
   3.104 +        }
   3.105 +        
   3.106 +        x->e = (y->e > e) ? y->e : e;
   3.107 +
   3.108 +        for ( ; ; )
   3.109 +        {
   3.110 +            y = list_entry(x->list.next, struct range, list);
   3.111 +            if ( (x->list.next == &r->range_list) || (y->e > x->e) )
   3.112 +                break;
   3.113 +            destroy_range(y);
   3.114 +        }
   3.115 +    }
   3.116 +
   3.117 +    y = list_entry(x->list.next, struct range, list);
   3.118 +    if ( (x->list.next != &r->range_list) && ((x->e + 1) == y->s) )
   3.119 +    {
   3.120 +        x->e = y->e;
   3.121 +        destroy_range(y);
   3.122 +    }
   3.123 +
   3.124 + out:
   3.125 +    spin_unlock(&r->lock);
   3.126 +    return rc;
   3.127 +}
   3.128 +
   3.129 +int rangeset_remove_range(
   3.130 +    struct rangeset *r, unsigned long s, unsigned long e)
   3.131 +{
   3.132 +    struct range *x, *y, *t;
   3.133 +    int rc = 0;
   3.134 +
   3.135 +    spin_lock(&r->lock);
   3.136 +
   3.137 +    x = find_range(r, s);
   3.138 +    y = find_range(r, e);
   3.139 +
   3.140 +    if ( x == y )
   3.141 +    {
   3.142 +        if ( (x == NULL) || (x->e < s) )
   3.143 +            goto out;
   3.144 +
   3.145 +        if ( (x->s < s) && (x->e > e) )
   3.146 +        {
   3.147 +            y = xmalloc(struct range);
   3.148 +            if ( y == NULL )
   3.149 +            {
   3.150 +                rc = -ENOMEM;
   3.151 +                goto out;
   3.152 +            }
   3.153 +            y->s = e + 1;
   3.154 +            y->e = x->e;
   3.155 +            x->e = s - 1;
   3.156 +            list_add(&y->list, &x->list);
   3.157 +        }
   3.158 +        else if ( (x->s == s) && (x->e <= e) )
   3.159 +            destroy_range(x);
   3.160 +        else if ( x->s == s )
   3.161 +            x->s = e + 1;
   3.162 +        else if ( x->e <= e )
   3.163 +            x->e = s - 1;
   3.164 +    }
   3.165 +    else
   3.166 +    {
   3.167 +        if ( x == NULL )
   3.168 +            x = list_entry(r->range_list.next, struct range, list);
   3.169 +
   3.170 +        if ( x->s < s )
   3.171 +        {
   3.172 +            x->e = s - 1;
   3.173 +            x = list_entry(x->list.next, struct range, list);
   3.174 +        }
   3.175 +
   3.176 +        while ( x != y )
   3.177 +        {
   3.178 +            t = x;
   3.179 +            x = list_entry(x->list.next, struct range, list);
   3.180 +            destroy_range(t);
   3.181 +        }
   3.182 +
   3.183 +        x->s = e + 1;
   3.184 +        if ( x->s > x->e )
   3.185 +            destroy_range(x);
   3.186 +    }
   3.187 +
   3.188 + out:
   3.189 +    spin_unlock(&r->lock);
   3.190 +    return rc;
   3.191 +}
   3.192 +
   3.193 +int rangeset_contains_range(
   3.194 +    struct rangeset *r, unsigned long s, unsigned long e)
   3.195 +{
   3.196 +    struct range *x;
   3.197 +    int contains;
   3.198 +
   3.199 +    spin_lock(&r->lock);
   3.200 +    x = find_range(r, s);
   3.201 +    contains = (x && (x->e >= e));
   3.202 +    spin_unlock(&r->lock);
   3.203 +
   3.204 +    return contains;
   3.205 +}
   3.206 +
   3.207 +int rangeset_add_singleton(
   3.208 +    struct rangeset *r, unsigned long s)
   3.209 +{
   3.210 +    return rangeset_add_range(r, s, s);
   3.211 +}
   3.212 +
   3.213 +int rangeset_remove_singleton(
   3.214 +    struct rangeset *r, unsigned long s)
   3.215 +{
   3.216 +    return rangeset_remove_range(r, s, s);
   3.217 +}
   3.218 +
   3.219 +int rangeset_contains_singleton(
   3.220 +    struct rangeset *r, unsigned long s)
   3.221 +{
   3.222 +    return rangeset_contains_range(r, s, s);
   3.223 +}
   3.224 +
   3.225 +struct rangeset *rangeset_new(
   3.226 +    struct domain *d, char *name, unsigned int flags)
   3.227 +{
   3.228 +    struct rangeset *r;
   3.229 +
   3.230 +    r = xmalloc(struct rangeset);
   3.231 +    if ( r == NULL )
   3.232 +        return NULL;
   3.233 +
   3.234 +    spin_lock_init(&r->lock);
   3.235 +    INIT_LIST_HEAD(&r->range_list);
   3.236 +
   3.237 +    BUG_ON(flags & ~RANGESETF_prettyprint_hex);
   3.238 +    r->flags = flags;
   3.239 +
   3.240 +    if ( name != NULL )
   3.241 +    {
   3.242 +        strncpy(r->name, name, sizeof(r->name));
   3.243 +        r->name[sizeof(r->name)-1] = '\0';
   3.244 +    }
   3.245 +    else
   3.246 +    {
   3.247 +        sprintf(r->name, "(no name)");
   3.248 +    }
   3.249 +
   3.250 +    if ( (r->domain = d) != NULL )
   3.251 +    {
   3.252 +        spin_lock(&d->rangesets_lock);
   3.253 +        list_add(&r->rangeset_list, &d->rangesets);
   3.254 +        spin_unlock(&d->rangesets_lock);
   3.255 +    }
   3.256 +
   3.257 +    return r;
   3.258 +}
   3.259 +
   3.260 +void rangeset_destroy(
   3.261 +    struct rangeset *r)
   3.262 +{
   3.263 +    if ( r == NULL )
   3.264 +        return;
   3.265 +
   3.266 +    if ( r->domain != NULL )
   3.267 +    {
   3.268 +        spin_lock(&r->domain->rangesets_lock);
   3.269 +        list_del(&r->rangeset_list);
   3.270 +        spin_unlock(&r->domain->rangesets_lock);
   3.271 +    }
   3.272 +
   3.273 +    while ( !list_empty(&r->range_list) )
   3.274 +    {
   3.275 +        struct range *x = list_entry(r->range_list.next, struct range, list);
   3.276 +        destroy_range(x);
   3.277 +    }
   3.278 +
   3.279 +    xfree(r);
   3.280 +}
   3.281 +
   3.282 +void rangeset_domain_initialise(
   3.283 +    struct domain *d)
   3.284 +{
   3.285 +    INIT_LIST_HEAD(&d->rangesets);
   3.286 +    spin_lock_init(&d->rangesets_lock);
   3.287 +}
   3.288 +
   3.289 +void rangeset_domain_destroy(
   3.290 +    struct domain *d)
   3.291 +{
   3.292 +    struct rangeset *r;
   3.293 +
   3.294 +    while ( !list_empty(&d->rangesets) )
   3.295 +    {
   3.296 +        r = list_entry(d->rangesets.next, struct rangeset, rangeset_list);
   3.297 +
   3.298 +        BUG_ON(r->domain != d);
   3.299 +        r->domain = NULL;
   3.300 +        list_del(&r->rangeset_list);
   3.301 +
   3.302 +        rangeset_destroy(r);
   3.303 +    }
   3.304 +}
   3.305 +
   3.306 +static void print_limit(struct rangeset *r, unsigned long s)
   3.307 +{
   3.308 +    printk((r->flags & RANGESETF_prettyprint_hex) ? "%lx" : "%lu", s);
   3.309 +}
   3.310 +
   3.311 +void rangeset_printk(
   3.312 +    struct rangeset *r)
   3.313 +{
   3.314 +    int nr_printed = 0;
   3.315 +    struct range *x;
   3.316 +
   3.317 +    spin_lock(&r->lock);
   3.318 +
   3.319 +    printk("%10s {", r->name);
   3.320 +
   3.321 +    list_for_each_entry ( x, &r->range_list, list )
   3.322 +    {
   3.323 +        if ( nr_printed++ )
   3.324 +            printk(",");
   3.325 +        printk(" ");
   3.326 +        print_limit(r, x->s);
   3.327 +        if ( x->s != x->e )
   3.328 +        {
   3.329 +            printk("-");
   3.330 +            print_limit(r, x->e);
   3.331 +        }
   3.332 +    }
   3.333 +
   3.334 +    printk(" }");
   3.335 +
   3.336 +    spin_unlock(&r->lock);
   3.337 +}
   3.338 +
   3.339 +void rangeset_domain_printk(
   3.340 +    struct domain *d)
   3.341 +{
   3.342 +    struct rangeset *r;
   3.343 +
   3.344 +    printk("Rangesets belonging to domain %d:\n", d->domain_id);
   3.345 +
   3.346 +    spin_lock(&d->rangesets_lock);
   3.347 +
   3.348 +    if ( list_empty(&d->rangesets) )
   3.349 +        printk("    None\n");
   3.350 +
   3.351 +    list_for_each_entry ( r, &d->rangesets, rangeset_list )
   3.352 +    {
   3.353 +        printk("    ");
   3.354 +        rangeset_printk(r);
   3.355 +        printk("\n");
   3.356 +    }
   3.357 +
   3.358 +    spin_unlock(&d->rangesets_lock);
   3.359 +}
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/xen/include/xen/rangeset.h	Thu Dec 29 15:47:23 2005 +0100
     4.3 @@ -0,0 +1,68 @@
     4.4 +/******************************************************************************
     4.5 + * rangeset.h
     4.6 + * 
     4.7 + * Creation, maintenance and automatic destruction of per-domain sets of
     4.8 + * numeric ranges.
     4.9 + * 
    4.10 + * Copyright (c) 2005, K A Fraser
    4.11 + */
    4.12 +
    4.13 +#ifndef __XEN_RANGESET_H__
    4.14 +#define __XEN_RANGESET_H__
    4.15 +
    4.16 +struct domain;
    4.17 +struct rangeset;
    4.18 +
    4.19 +/*
    4.20 + * Initialise/destroy per-domain rangeset information.
    4.21 + * 
    4.22 + * It is invalid to create or destroy a rangeset belonging to a domain @d
    4.23 + * before rangeset_domain_initialise(d) returns or after calling
    4.24 + * rangeset_domain_destroy(d).
    4.25 + */
    4.26 +void rangeset_domain_initialise(
    4.27 +    struct domain *d);
    4.28 +void rangeset_domain_destroy(
    4.29 +    struct domain *d);
    4.30 +
    4.31 +/*
    4.32 + * Create/destroy a rangeset. Optionally attach to specified domain @d for
    4.33 + * auto-destruction when the domain dies. A name may be specified, for use
    4.34 + * in debug pretty-printing, and various RANGESETF flags (defined below).
    4.35 + * 
    4.36 + * It is invalid to perform any operation on a rangeset @r after calling
    4.37 + * rangeset_destroy(r).
    4.38 + */
    4.39 +struct rangeset *rangeset_new(
    4.40 +    struct domain *d, char *name, unsigned int flags);
    4.41 +void rangeset_destroy(
    4.42 +    struct rangeset *r);
    4.43 +
    4.44 +/* Flags for passing to rangeset_new(). */
    4.45 + /* Pretty-print range limits in hexadecimal. */
    4.46 +#define _RANGESETF_prettyprint_hex 0
    4.47 +#define RANGESETF_prettyprint_hex  (1U << _RANGESETF_prettyprint_hex)
    4.48 +
    4.49 +/* Add/remove/query a numeric range. */
    4.50 +int rangeset_add_range(
    4.51 +    struct rangeset *r, unsigned long s, unsigned long e);
    4.52 +int rangeset_remove_range(
    4.53 +    struct rangeset *r, unsigned long s, unsigned long e);
    4.54 +int rangeset_contains_range(
    4.55 +    struct rangeset *r, unsigned long s, unsigned long e);
    4.56 +
    4.57 +/* Add/remove/query a single number. */
    4.58 +int rangeset_add_singleton(
    4.59 +    struct rangeset *r, unsigned long s);
    4.60 +int rangeset_remove_singleton(
    4.61 +    struct rangeset *r, unsigned long s);
    4.62 +int rangeset_contains_singleton(
    4.63 +    struct rangeset *r, unsigned long s);
    4.64 +
    4.65 +/* Rangeset pretty printing. */
    4.66 +void rangeset_printk(
    4.67 +    struct rangeset *r);
    4.68 +void rangeset_domain_printk(
    4.69 +    struct domain *d);
    4.70 +
    4.71 +#endif /* __XEN_RANGESET_H__ */
     5.1 --- a/xen/include/xen/sched.h	Wed Dec 28 16:23:42 2005 +0100
     5.2 +++ b/xen/include/xen/sched.h	Thu Dec 29 15:47:23 2005 +0100
     5.3 @@ -110,6 +110,9 @@ struct domain
     5.4      struct domain   *next_in_list;
     5.5      struct domain   *next_in_hashbucket;
     5.6  
     5.7 +    struct list_head rangesets;
     5.8 +    spinlock_t       rangesets_lock;
     5.9 +
    5.10      /* Event channel information. */
    5.11      struct evtchn   *evtchn[NR_EVTCHN_BUCKETS];
    5.12      spinlock_t       evtchn_lock;