diff -r 1e3977e029fd -r 19c77906a845 xen/arch/x86/Makefile --- a/xen/arch/x86/Makefile Mon May 8 18:21:41 2006 +++ b/xen/arch/x86/Makefile Wed May 10 14:30:39 2006 @@ -22,6 +22,8 @@ obj-y += i387.o obj-y += i8259.o obj-y += io_apic.o +obj-y += iocap.o +obj-y += iomm.o obj-y += irq.o obj-y += microcode.o obj-y += mm.o diff -r 1e3977e029fd -r 19c77906a845 xen/arch/x86/setup.c --- a/xen/arch/x86/setup.c Mon May 8 18:21:41 2006 +++ b/xen/arch/x86/setup.c Wed May 10 14:30:39 2006 @@ -439,6 +439,10 @@ scheduler_init(); + io_page_init(); + + iocap_init(); + idle_domain = domain_create(IDLE_DOMAIN_ID, 0); BUG_ON(idle_domain == NULL); diff -r 1e3977e029fd -r 19c77906a845 xen/common/Makefile --- a/xen/common/Makefile Mon May 8 18:21:41 2006 +++ b/xen/common/Makefile Wed May 10 14:30:39 2006 @@ -5,6 +5,7 @@ obj-y += elf.o obj-y += event_channel.o obj-y += grant_table.o +obj-y += iocap.o obj-y += kernel.o obj-y += keyhandler.o obj-y += lib.o @@ -12,6 +13,7 @@ obj-y += multicall.o obj-y += page_alloc.o obj-y += rangeset.o +obj-y += rbtree.o obj-y += sched_bvt.o obj-y += sched_sedf.o obj-y += schedule.o diff -r 1e3977e029fd -r 19c77906a845 xen/common/rangeset.c --- a/xen/common/rangeset.c Mon May 8 18:21:41 2006 +++ b/xen/common/rangeset.c Wed May 10 14:30:39 2006 @@ -32,6 +32,38 @@ unsigned int flags; }; +static inline void spin_lock_2(spinlock_t *l1, spinlock_t *l2) +{ + ASSERT(l1 != l2); + + if (l1 < l2) + { + spin_lock(l1); + spin_lock(l2); + } + else + { + spin_lock(l2); + spin_lock(l1); + } +} + +static inline void spin_unlock_2(spinlock_t *l1, spinlock_t *l2) +{ + ASSERT(l1 != l2); + + if (l1 < l2) + { + spin_unlock(l2); + spin_unlock(l1); + } + else + { + spin_unlock(l1); + spin_unlock(l2); + } +} + /***************************** * Private range functions hide the underlying linked-list implemnetation. */ @@ -241,6 +273,172 @@ return contains; } +int rangeset_contains_partial_range( + struct rangeset *r, unsigned long s, unsigned long e) +{ + struct range *x; + int contains; + + ASSERT(s <= e); + + spin_lock(&r->lock); + x = find_range(r, e); + contains = (x && (s <= x->e)); + spin_unlock(&r->lock); + + return contains; +} + +int rangeset_move_range( + struct rangeset *dest, struct rangeset *src, + unsigned long s, unsigned long e) +{ + int rc = 0; + struct range *n, *x, *y, *z; + + ASSERT(s <= e); + ASSERT(src != dest); + + spin_lock_2(&src->lock, &dest->lock); + + x = find_range(src, s); + + if (x && x->s <= s && e <= x->e) + { + if (x->s == s && x->e == e) + { + list_del(&x->list); + n = x; + } + else + { + /* The mallocs are arranged so that if they fail, no data has + * been moved and the rangesets are still consistent. */ + n = xmalloc(struct range); + if (!n) + { + rc = -ENOMEM; + goto out; + } + n->s = s; + n->e = e; + + if (x->s == s) + x->s = e + 1; + else if (x->e == e) + x->e = s - 1; + else + { + z = xmalloc(struct range); + if (!z) + { + rc = -ENOMEM; + xfree(n); + goto out; + } + + z->e = x->e; + z->s = e + 1; + x->e = s - 1; + insert_range(src, x, z); + } + } + + /* Insert the range into the destination rangeset */ + y = find_range(dest, s); + if (y && y->e >= (s ? s - 1 : s)) /* ensure s doesn't wrap */ + { + if (y->e < e) + { + y->e = e; + while ( (z = next_range(dest, y)) && z->e <= e) + destroy_range(z); + } + + xfree(n); + n = y; + } + else + insert_range(dest, y, n); + + /* Merge with next range if we overlap */ + y = next_range(dest, n); + if (y && (y->s - 1) <= n->e) + { + if (y->e > n->e) + n->e = y->e; + + destroy_range(y); + } + } + else + rc = -ENOENT; + + out: + spin_unlock_2(&src->lock, &dest->lock); + return rc; +} + +int rangeset_move( + struct rangeset *dest, struct rangeset *src) +{ + struct range *x, *y, *z; + + ASSERT(dest != src); + + spin_lock_2(&src->lock, &dest->lock); + + while ((x = first_range(src))) + { + y = find_range(dest, x->s); + + if (y && y->e >= (x->s ? x->s - 1 : x->s)) /* ensure s doesn't wrap */ + { + if (x->e > y->e) + { + y->e = x->e; + while ((z = next_range(dest, y)) && z->e <= y->e) + destroy_range(z); + } + destroy_range(x); + x = y; + } + else + { + list_del(&x->list); + insert_range(dest, y, x); + } + + /* Merge with next range if we overlap */ + y = next_range(dest, x); + if (y && (y->s - 1) <= x->e) + { + if (y->e > x->e) + x->e = y->e; + + destroy_range(y); + } + } + + spin_unlock_2(&src->lock, &dest->lock); + + return 0; +} + +int rangeset_clear(struct rangeset *r) +{ + struct range *x; + + spin_lock(&r->lock); + + while ( (x = first_range(r)) != NULL ) + destroy_range(x); + + spin_unlock(&r->lock); + + return 0; +} + int rangeset_add_singleton( struct rangeset *r, unsigned long s) { diff -r 1e3977e029fd -r 19c77906a845 xen/include/xen/rangeset.h --- a/xen/include/xen/rangeset.h Mon May 8 18:21:41 2006 +++ b/xen/include/xen/rangeset.h Wed May 10 14:30:39 2006 @@ -9,6 +9,8 @@ #ifndef __XEN_RANGESET_H__ #define __XEN_RANGESET_H__ + +#include struct domain; struct rangeset; @@ -46,6 +48,11 @@ int __must_check rangeset_is_empty( struct rangeset *r); +int __must_check rangeset_clear( + struct rangeset *r); +int __must_check rangeset_move( + struct rangeset *dest, struct rangeset *src); + /* Add/remove/query a numeric range. */ int __must_check rangeset_add_range( struct rangeset *r, unsigned long s, unsigned long e); @@ -53,6 +60,11 @@ struct rangeset *r, unsigned long s, unsigned long e); int __must_check rangeset_contains_range( struct rangeset *r, unsigned long s, unsigned long e); +int __must_check rangeset_contains_partial_range( + struct rangeset *r, unsigned long s, unsigned long e); +int __must_check rangeset_move_range( + struct rangeset *dest, struct rangeset *src, + unsigned long s, unsigned long e); /* Add/remove/query a single number. */ int __must_check rangeset_add_singleton( diff -r 1e3977e029fd -r 19c77906a845 xen/common/rbtree.c --- /dev/null Mon May 8 18:21:41 2006 +++ b/xen/common/rbtree.c Wed May 10 14:30:39 2006 @@ -0,0 +1,386 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli + (C) 2002 David Woodhouse + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + linux/lib/rbtree.c +*/ + +#include + +static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *right = node->rb_right; + + if ((node->rb_right = right->rb_left)) + right->rb_left->rb_parent = node; + right->rb_left = node; + + if ((right->rb_parent = node->rb_parent)) + { + if (node == node->rb_parent->rb_left) + node->rb_parent->rb_left = right; + else + node->rb_parent->rb_right = right; + } + else + root->rb_node = right; + node->rb_parent = right; +} + +static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *left = node->rb_left; + + if ((node->rb_left = left->rb_right)) + left->rb_right->rb_parent = node; + left->rb_right = node; + + if ((left->rb_parent = node->rb_parent)) + { + if (node == node->rb_parent->rb_right) + node->rb_parent->rb_right = left; + else + node->rb_parent->rb_left = left; + } + else + root->rb_node = left; + node->rb_parent = left; +} + +void rb_insert_color(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *parent, *gparent; + + while ((parent = node->rb_parent) && parent->rb_color == RB_RED) + { + gparent = parent->rb_parent; + + if (parent == gparent->rb_left) + { + { + register struct rb_node *uncle = gparent->rb_right; + if (uncle && uncle->rb_color == RB_RED) + { + uncle->rb_color = RB_BLACK; + parent->rb_color = RB_BLACK; + gparent->rb_color = RB_RED; + node = gparent; + continue; + } + } + + if (parent->rb_right == node) + { + register struct rb_node *tmp; + __rb_rotate_left(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + parent->rb_color = RB_BLACK; + gparent->rb_color = RB_RED; + __rb_rotate_right(gparent, root); + } else { + { + register struct rb_node *uncle = gparent->rb_left; + if (uncle && uncle->rb_color == RB_RED) + { + uncle->rb_color = RB_BLACK; + parent->rb_color = RB_BLACK; + gparent->rb_color = RB_RED; + node = gparent; + continue; + } + } + + if (parent->rb_left == node) + { + register struct rb_node *tmp; + __rb_rotate_right(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + parent->rb_color = RB_BLACK; + gparent->rb_color = RB_RED; + __rb_rotate_left(gparent, root); + } + } + + root->rb_node->rb_color = RB_BLACK; +} + +static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, + struct rb_root *root) +{ + struct rb_node *other; + + while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node) + { + if (parent->rb_left == node) + { + other = parent->rb_right; + if (other->rb_color == RB_RED) + { + other->rb_color = RB_BLACK; + parent->rb_color = RB_RED; + __rb_rotate_left(parent, root); + other = parent->rb_right; + } + if ((!other->rb_left || + other->rb_left->rb_color == RB_BLACK) + && (!other->rb_right || + other->rb_right->rb_color == RB_BLACK)) + { + other->rb_color = RB_RED; + node = parent; + parent = node->rb_parent; + } + else + { + if (!other->rb_right || + other->rb_right->rb_color == RB_BLACK) + { + register struct rb_node *o_left; + if ((o_left = other->rb_left)) + o_left->rb_color = RB_BLACK; + other->rb_color = RB_RED; + __rb_rotate_right(other, root); + other = parent->rb_right; + } + other->rb_color = parent->rb_color; + parent->rb_color = RB_BLACK; + if (other->rb_right) + other->rb_right->rb_color = RB_BLACK; + __rb_rotate_left(parent, root); + node = root->rb_node; + break; + } + } + else + { + other = parent->rb_left; + if (other->rb_color == RB_RED) + { + other->rb_color = RB_BLACK; + parent->rb_color = RB_RED; + __rb_rotate_right(parent, root); + other = parent->rb_left; + } + if ((!other->rb_left || + other->rb_left->rb_color == RB_BLACK) + && (!other->rb_right || + other->rb_right->rb_color == RB_BLACK)) + { + other->rb_color = RB_RED; + node = parent; + parent = node->rb_parent; + } + else + { + if (!other->rb_left || + other->rb_left->rb_color == RB_BLACK) + { + register struct rb_node *o_right; + if ((o_right = other->rb_right)) + o_right->rb_color = RB_BLACK; + other->rb_color = RB_RED; + __rb_rotate_left(other, root); + other = parent->rb_left; + } + other->rb_color = parent->rb_color; + parent->rb_color = RB_BLACK; + if (other->rb_left) + other->rb_left->rb_color = RB_BLACK; + __rb_rotate_right(parent, root); + node = root->rb_node; + break; + } + } + } + if (node) + node->rb_color = RB_BLACK; +} + +void rb_erase(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *child, *parent; + int color; + + if (!node->rb_left) + child = node->rb_right; + else if (!node->rb_right) + child = node->rb_left; + else + { + struct rb_node *old = node, *left; + + node = node->rb_right; + while ((left = node->rb_left) != NULL) + node = left; + child = node->rb_right; + parent = node->rb_parent; + color = node->rb_color; + + if (child) + child->rb_parent = parent; + if (parent) + { + if (parent->rb_left == node) + parent->rb_left = child; + else + parent->rb_right = child; + } + else + root->rb_node = child; + + if (node->rb_parent == old) + parent = node; + node->rb_parent = old->rb_parent; + node->rb_color = old->rb_color; + node->rb_right = old->rb_right; + node->rb_left = old->rb_left; + + if (old->rb_parent) + { + if (old->rb_parent->rb_left == old) + old->rb_parent->rb_left = node; + else + old->rb_parent->rb_right = node; + } else + root->rb_node = node; + + old->rb_left->rb_parent = node; + if (old->rb_right) + old->rb_right->rb_parent = node; + goto color; + } + + parent = node->rb_parent; + color = node->rb_color; + + if (child) + child->rb_parent = parent; + if (parent) + { + if (parent->rb_left == node) + parent->rb_left = child; + else + parent->rb_right = child; + } + else + root->rb_node = child; + + color: + if (color == RB_BLACK) + __rb_erase_color(child, parent, root); +} + +/* + * This function returns the first node (in sort order) of the tree. + */ +struct rb_node *rb_first(struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_left) + n = n->rb_left; + return n; +} + +struct rb_node *rb_last(struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_right) + n = n->rb_right; + return n; +} + +struct rb_node *rb_next(struct rb_node *node) +{ + /* If we have a right-hand child, go down and then left as far + as we can. */ + if (node->rb_right) { + node = node->rb_right; + while (node->rb_left) + node=node->rb_left; + return node; + } + + /* No right-hand children. Everything down and left is + smaller than us, so any 'next' node must be in the general + direction of our parent. Go up the tree; any time the + ancestor is a right-hand child of its parent, keep going + up. First time it's a left-hand child of its parent, said + parent is our 'next' node. */ + while (node->rb_parent && node == node->rb_parent->rb_right) + node = node->rb_parent; + + return node->rb_parent; +} + +struct rb_node *rb_prev(struct rb_node *node) +{ + /* If we have a left-hand child, go down and then right as far + as we can. */ + if (node->rb_left) { + node = node->rb_left; + while (node->rb_right) + node=node->rb_right; + return node; + } + + /* No left-hand children. Go up till we find an ancestor which + is a right-hand child of its parent */ + while (node->rb_parent && node == node->rb_parent->rb_left) + node = node->rb_parent; + + return node->rb_parent; +} + +void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root) +{ + struct rb_node *parent = victim->rb_parent; + + /* Set the surrounding nodes to point to the replacement */ + if (parent) { + if (victim == parent->rb_left) + parent->rb_left = new; + else + parent->rb_right = new; + } else { + root->rb_node = new; + } + if (victim->rb_left) + victim->rb_left->rb_parent = new; + if (victim->rb_right) + victim->rb_right->rb_parent = new; + + /* Copy the pointers/colour from the victim to the replacement */ + *new = *victim; +} diff -r 1e3977e029fd -r 19c77906a845 xen/include/xen/rbtree.h --- /dev/null Mon May 8 18:21:41 2006 +++ b/xen/include/xen/rbtree.h Wed May 10 14:30:39 2006 @@ -0,0 +1,141 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + xen/include/xen/rbtree.h + + To use rbtrees you'll have to implement your own insert and search cores. + This will avoid us to use callbacks and to drop drammatically performances. + I know it's not the cleaner way, but in C (not in C++) to get + performances and genericity... + + Some example of insert and search follows here. The search is a plain + normal search over an ordered tree. The insert instead must be implemented + int two steps: as first thing the code must insert the element in + order as a red leaf in the tree, then the support library function + rb_insert_color() must be called. Such function will do the + not trivial work to rebalance the rbtree if necessary. + +----------------------------------------------------------------------- +static inline struct page * rb_search_page_cache(struct inode * inode, + unsigned long offset) +{ + struct rb_node * n = inode->i_rb_page_cache.rb_node; + struct page * page; + + while (n) + { + page = rb_entry(n, struct page, rb_page_cache); + + if (offset < page->offset) + n = n->rb_left; + else if (offset > page->offset) + n = n->rb_right; + else + return page; + } + return NULL; +} + +static inline struct page * __rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct rb_node ** p = &inode->i_rb_page_cache.rb_node; + struct rb_node * parent = NULL; + struct page * page; + + while (*p) + { + parent = *p; + page = rb_entry(parent, struct page, rb_page_cache); + + if (offset < page->offset) + p = &(*p)->rb_left; + else if (offset > page->offset) + p = &(*p)->rb_right; + else + return page; + } + + rb_link_node(node, parent, p); + + return NULL; +} + +static inline struct page * rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct page * ret; + if ((ret = __rb_insert_page_cache(inode, offset, node))) + goto out; + rb_insert_color(node, &inode->i_rb_page_cache); + out: + return ret; +} +----------------------------------------------------------------------- +*/ + +#ifndef _LINUX_RBTREE_H +#define _LINUX_RBTREE_H + +#include +#include + +struct rb_node +{ + struct rb_node *rb_parent; + int rb_color; +#define RB_RED 0 +#define RB_BLACK 1 + struct rb_node *rb_right; + struct rb_node *rb_left; +}; + +struct rb_root +{ + struct rb_node *rb_node; +}; + +#define RB_ROOT (struct rb_root) { NULL, } +#define rb_entry(ptr, type, member) container_of(ptr, type, member) + +extern void rb_insert_color(struct rb_node *, struct rb_root *); +extern void rb_erase(struct rb_node *, struct rb_root *); + +/* Find logical next and previous nodes in a tree */ +extern struct rb_node *rb_next(struct rb_node *); +extern struct rb_node *rb_prev(struct rb_node *); +extern struct rb_node *rb_first(struct rb_root *); +extern struct rb_node *rb_last(struct rb_root *); + +/* Fast replacement of a single node without remove/rebalance/add/rebalance */ +extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root); + +static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, + struct rb_node ** rb_link) +{ + node->rb_parent = parent; + node->rb_color = RB_RED; + node->rb_left = node->rb_right = NULL; + + *rb_link = node; +} + +#endif /* _LINUX_RBTREE_H */