Mailing List Archive

# HG changeset patch
# User kaf24@firebug.cl.cam.ac.uk
# Node ID 8d0b62f0aa8d5a3dcb51f98403511d21601a0752
# Parent 188ef899e626442b361732eb3eeafb5c5152f333
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>

diff -r 188ef899e626 -r 8d0b62f0aa8d xen/common/domain.c
--- a/xen/common/domain.c Wed Dec 28 15:23:42 2005
+++ b/xen/common/domain.c Thu Dec 29 14:47:23 2005
@@ -16,6 +16,7 @@
#include <xen/console.h>
#include <xen/softirq.h>
#include <xen/domain_page.h>
+#include <xen/rangeset.h>
#include <asm/debugger.h>
#include <public/dom0_ops.h>
#include <public/sched.h>
@@ -65,6 +66,8 @@
free_domain(d);
return NULL;
}
+
+ rangeset_domain_initialise(d);

arch_do_createdomain(v);

@@ -271,6 +274,8 @@
*pd = d->next_in_hashbucket;
write_unlock(&domlist_lock);

+ rangeset_domain_destroy(d);
+
evtchn_destroy(d);
grant_table_destroy(d);

diff -r 188ef899e626 -r 8d0b62f0aa8d xen/common/keyhandler.c
--- a/xen/common/keyhandler.c Wed Dec 28 15:23:42 2005
+++ b/xen/common/keyhandler.c Thu Dec 29 14:47:23 2005
@@ -11,6 +11,7 @@
#include <xen/sched.h>
#include <xen/softirq.h>
#include <xen/domain.h>
+#include <xen/rangeset.h>
#include <asm/debugger.h>

#define KEY_MAX 256
@@ -121,6 +122,8 @@
d->handle[ 4], d->handle[ 5], d->handle[ 6], d->handle[ 7],
d->handle[ 8], d->handle[ 9], d->handle[10], d->handle[11],
d->handle[12], d->handle[13], d->handle[14], d->handle[15]);
+
+ rangeset_domain_printk(d);

dump_pageframe_info(d);

diff -r 188ef899e626 -r 8d0b62f0aa8d xen/include/xen/sched.h
--- a/xen/include/xen/sched.h Wed Dec 28 15:23:42 2005
+++ b/xen/include/xen/sched.h Thu Dec 29 14:47:23 2005
@@ -109,6 +109,9 @@

struct domain *next_in_list;
struct domain *next_in_hashbucket;
+
+ struct list_head rangesets;
+ spinlock_t rangesets_lock;

/* Event channel information. */
struct evtchn *evtchn[NR_EVTCHN_BUCKETS];
diff -r 188ef899e626 -r 8d0b62f0aa8d xen/common/rangeset.c
--- /dev/null Wed Dec 28 15:23:42 2005
+++ b/xen/common/rangeset.c Thu Dec 29 14:47:23 2005
@@ -0,0 +1,356 @@
+/******************************************************************************
+ * rangeset.c
+ *
+ * Creation, maintenance and automatic destruction of per-domain sets of
+ * numeric ranges.
+ *
+ * Copyright (c) 2005, K A Fraser
+ */
+
+#include <xen/sched.h>
+#include <xen/rangeset.h>
+
+/* An inclusive range [s,e] and pointer to next range in ascending order. */
+struct range {
+ struct list_head list;
+ unsigned long s, e;
+};
+
+struct rangeset {
+ /* Owning domain and threaded list of rangesets. */
+ struct list_head rangeset_list;
+ struct domain *domain;
+
+ /* Ordered list of ranges contained in this set, and protecting lock. */
+ struct list_head range_list;
+ spinlock_t lock;
+
+ /* Pretty-printing name. */
+ char name[32];
+
+ /* RANGESETF_??? */
+ unsigned int flags;
+};
+
+/* Find highest range lower than or containing s. NULL if no such range. */
+static struct range *find_range(
+ struct rangeset *r, unsigned long s)
+{
+ struct range *x = NULL, *y;
+
+ list_for_each_entry ( y, &r->range_list, list )
+ {
+ if ( y->s > s )
+ break;
+ x = y;
+ }
+
+ return x;
+}
+
+/* Remove a range from its list and free it. */
+static void destroy_range(
+ struct range *x)
+{
+ list_del(&x->list);
+ xfree(x);
+}
+
+int rangeset_add_range(
+ struct rangeset *r, unsigned long s, unsigned long e)
+{
+ struct range *x, *y;
+ int rc = 0;
+
+ spin_lock(&r->lock);
+
+ x = find_range(r, s);
+ y = find_range(r, e);
+
+ if ( x == y )
+ {
+ if ( (x == NULL) || ((x->e < s) && ((x->e + 1) != s)) )
+ {
+ x = xmalloc(struct range);
+ if ( x == NULL )
+ {
+ rc = -ENOMEM;
+ goto out;
+ }
+
+ x->s = s;
+ x->e = e;
+
+ list_add(&x->list, (y != NULL) ? &y->list : &r->range_list);
+ }
+
+ if ( x->e < e )
+ x->e = e;
+ }
+ else
+ {
+ if ( x == NULL )
+ {
+ x = list_entry(r->range_list.next, struct range, list);
+ x->s = s;
+ }
+ else if ( (x->e < s) && ((x->e + 1) != s) )
+ {
+ x = list_entry(x->list.next, struct range, list);
+ x->s = s;
+ }
+
+ x->e = (y->e > e) ? y->e : e;
+
+ for ( ; ; )
+ {
+ y = list_entry(x->list.next, struct range, list);
+ if ( (x->list.next == &r->range_list) || (y->e > x->e) )
+ break;
+ destroy_range(y);
+ }
+ }
+
+ y = list_entry(x->list.next, struct range, list);
+ if ( (x->list.next != &r->range_list) && ((x->e + 1) == y->s) )
+ {
+ x->e = y->e;
+ destroy_range(y);
+ }
+
+ out:
+ spin_unlock(&r->lock);
+ return rc;
+}
+
+int rangeset_remove_range(
+ struct rangeset *r, unsigned long s, unsigned long e)
+{
+ struct range *x, *y, *t;
+ int rc = 0;
+
+ spin_lock(&r->lock);
+
+ x = find_range(r, s);
+ y = find_range(r, e);
+
+ if ( x == y )
+ {
+ if ( (x == NULL) || (x->e < s) )
+ goto out;
+
+ if ( (x->s < s) && (x->e > e) )
+ {
+ y = xmalloc(struct range);
+ if ( y == NULL )
+ {
+ rc = -ENOMEM;
+ goto out;
+ }
+ y->s = e + 1;
+ y->e = x->e;
+ x->e = s - 1;
+ list_add(&y->list, &x->list);
+ }
+ else if ( (x->s == s) && (x->e <= e) )
+ destroy_range(x);
+ else if ( x->s == s )
+ x->s = e + 1;
+ else if ( x->e <= e )
+ x->e = s - 1;
+ }
+ else
+ {
+ if ( x == NULL )
+ x = list_entry(r->range_list.next, struct range, list);
+
+ if ( x->s < s )
+ {
+ x->e = s - 1;
+ x = list_entry(x->list.next, struct range, list);
+ }
+
+ while ( x != y )
+ {
+ t = x;
+ x = list_entry(x->list.next, struct range, list);
+ destroy_range(t);
+ }
+
+ x->s = e + 1;
+ if ( x->s > x->e )
+ destroy_range(x);
+ }
+
+ out:
+ spin_unlock(&r->lock);
+ return rc;
+}
+
+int rangeset_contains_range(
+ struct rangeset *r, unsigned long s, unsigned long e)
+{
+ struct range *x;
+ int contains;
+
+ spin_lock(&r->lock);
+ x = find_range(r, s);
+ contains = (x && (x->e >= e));
+ spin_unlock(&r->lock);
+
+ return contains;
+}
+
+int rangeset_add_singleton(
+ struct rangeset *r, unsigned long s)
+{
+ return rangeset_add_range(r, s, s);
+}
+
+int rangeset_remove_singleton(
+ struct rangeset *r, unsigned long s)
+{
+ return rangeset_remove_range(r, s, s);
+}
+
+int rangeset_contains_singleton(
+ struct rangeset *r, unsigned long s)
+{
+ return rangeset_contains_range(r, s, s);
+}
+
+struct rangeset *rangeset_new(
+ struct domain *d, char *name, unsigned int flags)
+{
+ struct rangeset *r;
+
+ r = xmalloc(struct rangeset);
+ if ( r == NULL )
+ return NULL;
+
+ spin_lock_init(&r->lock);
+ INIT_LIST_HEAD(&r->range_list);
+
+ BUG_ON(flags & ~RANGESETF_prettyprint_hex);
+ r->flags = flags;
+
+ if ( name != NULL )
+ {
+ strncpy(r->name, name, sizeof(r->name));
+ r->name[sizeof(r->name)-1] = '\0';
+ }
+ else
+ {
+ sprintf(r->name, "(no name)");
+ }
+
+ if ( (r->domain = d) != NULL )
+ {
+ spin_lock(&d->rangesets_lock);
+ list_add(&r->rangeset_list, &d->rangesets);
+ spin_unlock(&d->rangesets_lock);
+ }
+
+ return r;
+}
+
+void rangeset_destroy(
+ struct rangeset *r)
+{
+ if ( r == NULL )
+ return;
+
+ if ( r->domain != NULL )
+ {
+ spin_lock(&r->domain->rangesets_lock);
+ list_del(&r->rangeset_list);
+ spin_unlock(&r->domain->rangesets_lock);
+ }
+
+ while ( !list_empty(&r->range_list) )
+ {
+ struct range *x = list_entry(r->range_list.next, struct range, list);
+ destroy_range(x);
+ }
+
+ xfree(r);
+}
+
+void rangeset_domain_initialise(
+ struct domain *d)
+{
+ INIT_LIST_HEAD(&d->rangesets);
+ spin_lock_init(&d->rangesets_lock);
+}
+
+void rangeset_domain_destroy(
+ struct domain *d)
+{
+ struct rangeset *r;
+
+ while ( !list_empty(&d->rangesets) )
+ {
+ r = list_entry(d->rangesets.next, struct rangeset, rangeset_list);
+
+ BUG_ON(r->domain != d);
+ r->domain = NULL;
+ list_del(&r->rangeset_list);
+
+ rangeset_destroy(r);
+ }
+}
+
+static void print_limit(struct rangeset *r, unsigned long s)
+{
+ printk((r->flags & RANGESETF_prettyprint_hex) ? "%lx" : "%lu", s);
+}
+
+void rangeset_printk(
+ struct rangeset *r)
+{
+ int nr_printed = 0;
+ struct range *x;
+
+ spin_lock(&r->lock);
+
+ printk("%10s {", r->name);
+
+ list_for_each_entry ( x, &r->range_list, list )
+ {
+ if ( nr_printed++ )
+ printk(",");
+ printk(" ");
+ print_limit(r, x->s);
+ if ( x->s != x->e )
+ {
+ printk("-");
+ print_limit(r, x->e);
+ }
+ }
+
+ printk(" }");
+
+ spin_unlock(&r->lock);
+}
+
+void rangeset_domain_printk(
+ struct domain *d)
+{
+ struct rangeset *r;
+
+ printk("Rangesets belonging to domain %d:\n", d->domain_id);
+
+ spin_lock(&d->rangesets_lock);
+
+ if ( list_empty(&d->rangesets) )
+ printk(" None\n");
+
+ list_for_each_entry ( r, &d->rangesets, rangeset_list )
+ {
+ printk(" ");
+ rangeset_printk(r);
+ printk("\n");
+ }
+
+ spin_unlock(&d->rangesets_lock);
+}
diff -r 188ef899e626 -r 8d0b62f0aa8d xen/include/xen/rangeset.h
--- /dev/null Wed Dec 28 15:23:42 2005
+++ b/xen/include/xen/rangeset.h Thu Dec 29 14:47:23 2005
@@ -0,0 +1,68 @@
+/******************************************************************************
+ * rangeset.h
+ *
+ * Creation, maintenance and automatic destruction of per-domain sets of
+ * numeric ranges.
+ *
+ * Copyright (c) 2005, K A Fraser
+ */
+
+#ifndef __XEN_RANGESET_H__
+#define __XEN_RANGESET_H__
+
+struct domain;
+struct rangeset;
+
+/*
+ * Initialise/destroy per-domain rangeset information.
+ *
+ * It is invalid to create or destroy a rangeset belonging to a domain @d
+ * before rangeset_domain_initialise(d) returns or after calling
+ * rangeset_domain_destroy(d).
+ */
+void rangeset_domain_initialise(
+ struct domain *d);
+void rangeset_domain_destroy(
+ struct domain *d);
+
+/*
+ * Create/destroy a rangeset. Optionally attach to specified domain @d for
+ * auto-destruction when the domain dies. A name may be specified, for use
+ * in debug pretty-printing, and various RANGESETF flags (defined below).
+ *
+ * It is invalid to perform any operation on a rangeset @r after calling
+ * rangeset_destroy(r).
+ */
+struct rangeset *rangeset_new(
+ struct domain *d, char *name, unsigned int flags);
+void rangeset_destroy(
+ struct rangeset *r);
+
+/* Flags for passing to rangeset_new(). */
+ /* Pretty-print range limits in hexadecimal. */
+#define _RANGESETF_prettyprint_hex 0
+#define RANGESETF_prettyprint_hex (1U << _RANGESETF_prettyprint_hex)
+
+/* Add/remove/query a numeric range. */
+int rangeset_add_range(
+ struct rangeset *r, unsigned long s, unsigned long e);
+int rangeset_remove_range(
+ struct rangeset *r, unsigned long s, unsigned long e);
+int rangeset_contains_range(
+ struct rangeset *r, unsigned long s, unsigned long e);
+
+/* Add/remove/query a single number. */
+int rangeset_add_singleton(
+ struct rangeset *r, unsigned long s);
+int rangeset_remove_singleton(
+ struct rangeset *r, unsigned long s);
+int rangeset_contains_singleton(
+ struct rangeset *r, unsigned long s);
+
+/* Rangeset pretty printing. */
+void rangeset_printk(
+ struct rangeset *r);
+void rangeset_domain_printk(
+ struct domain *d);
+
+#endif /* __XEN_RANGESET_H__ */

_______________________________________________
Xen-changelog mailing list
Xen-changelog@lists.xensource.com
http://lists.xensource.com/xen-changelog