From: Jack Lange Date: Wed, 28 Jan 2009 00:31:54 +0000 (-0600) Subject: changed the io_map implementation to use red-black trees instead of linked list X-Git-Url: http://v3vee.org/palacios/gitweb/gitweb.cgi?p=palacios.git;a=commitdiff_plain;h=a6865d183eedbdf3e5510e4be89dcb5ce51b5953 changed the io_map implementation to use red-black trees instead of linked list --- diff --git a/palacios/build/Makefile b/palacios/build/Makefile index 6b8332b..3969547 100644 --- a/palacios/build/Makefile +++ b/palacios/build/Makefile @@ -266,6 +266,7 @@ VMM_OBJS := \ palacios/svm_msr.o \ palacios/vmm_socket.o \ palacios/vmm_xed.o \ + palacios/vmm_rbtree.o \ # vmx.c vmcs_gen.c vmcs.c diff --git a/palacios/include/palacios/vm_guest.h b/palacios/include/palacios/vm_guest.h index eb67f2b..29ea0c5 100644 --- a/palacios/include/palacios/vm_guest.h +++ b/palacios/include/palacios/vm_guest.h @@ -126,7 +126,7 @@ struct guest_info { // This structure is how we get interrupts for the guest struct v3_intr_state intr_state; - struct vmm_io_map io_map; + v3_io_map_t io_map; struct v3_msr_map msr_map; // device_map diff --git a/palacios/include/palacios/vmm_io.h b/palacios/include/palacios/vmm_io.h index 9bfc197..8db4f71 100644 --- a/palacios/include/palacios/vmm_io.h +++ b/palacios/include/palacios/vmm_io.h @@ -25,11 +25,16 @@ #include #include +#include + +typedef struct rb_root v3_io_map_t; struct guest_info; -int v3_unhook_io_port(struct guest_info * info, uint_t port); +void v3_init_io_map(struct guest_info * info); + + /* External API */ @@ -38,27 +43,12 @@ int v3_hook_io_port(struct guest_info * info, uint_t port, int (*write)(ushort_t port, void * src, uint_t length, void * priv_data), void * priv_data); +int v3_unhook_io_port(struct guest_info * info, uint_t port); - -struct vmm_io_hook; - -struct vmm_io_map { - uint_t num_ports; - struct vmm_io_hook * head; - -}; - - -void v3_init_vmm_io_map(struct guest_info * info); - -// FOREACH_IO_HOOK(vmm_io_map_t * io_map, vmm_io_hook_t * io_hook) -#define FOREACH_IO_HOOK(io_map, io_hook) for (io_hook = (io_map).head; io_hook != NULL; io_hook = (io_hook)->next) - - -struct vmm_io_hook { +struct v3_io_hook { ushort_t port; // Reads data into the IO port (IN, INS) @@ -68,17 +58,16 @@ struct vmm_io_hook { int (*write)(ushort_t port, void * src, uint_t length, void * priv_data); void * priv_data; - - struct vmm_io_hook * next; - struct vmm_io_hook * prev; + + struct rb_node tree_node; }; -struct vmm_io_hook * v3_get_io_hook(struct vmm_io_map * io_map, uint_t port); +struct v3_io_hook * v3_get_io_hook(struct guest_info * info, uint_t port); -void v3_print_io_map(struct vmm_io_map * io_map); +void v3_print_io_map(struct guest_info * info); diff --git a/palacios/src/palacios/svm.c b/palacios/src/palacios/svm.c index 96802d4..b052eee 100644 --- a/palacios/src/palacios/svm.c +++ b/palacios/src/palacios/svm.c @@ -37,6 +37,7 @@ #include #include +#include extern void v3_stgi(); @@ -191,8 +192,9 @@ static void Init_VMCB_BIOS(vmcb_t * vmcb, struct guest_info *vm_info) { - if (vm_info->io_map.num_ports > 0) { - struct vmm_io_hook * iter; + if ( !RB_EMPTY_ROOT(&(vm_info->io_map)) ) { + struct v3_io_hook * iter; + struct rb_node * io_node = v3_rb_first(&(vm_info->io_map)); addr_t io_port_bitmap; io_port_bitmap = (addr_t)V3_VAddr(V3_AllocPages(3)); @@ -202,14 +204,16 @@ static void Init_VMCB_BIOS(vmcb_t * vmcb, struct guest_info *vm_info) { //PrintDebug("Setting up IO Map at 0x%x\n", io_port_bitmap); - FOREACH_IO_HOOK(vm_info->io_map, iter) { + do { + iter = rb_entry(io_node, struct v3_io_hook, tree_node); + ushort_t port = iter->port; uchar_t * bitmap = (uchar_t *)io_port_bitmap; bitmap += (port / 8); // PrintDebug("Setting Bit for port 0x%x\n", port); *bitmap |= 1 << (port % 8); - } + } while ((io_node = v3_rb_next(io_node))); //PrintDebugMemDump((uchar_t*)io_port_bitmap, PAGE_SIZE *2); diff --git a/palacios/src/palacios/svm_io.c b/palacios/src/palacios/svm_io.c index 04b488b..e43deb0 100644 --- a/palacios/src/palacios/svm_io.c +++ b/palacios/src/palacios/svm_io.c @@ -17,9 +17,6 @@ * redistribute, and modify it as specified in the file "V3VEE_LICENSE". */ - - - #include #include #include @@ -41,7 +38,7 @@ int v3_handle_svm_io_in(struct guest_info * info) { // vmcb_saved_state_t * guest_state = GET_VMCB_SAVE_STATE_AREA((vmcb_t*)(info->vmm_data)); struct svm_io_info * io_info = (struct svm_io_info *)&(ctrl_area->exit_info1); - struct vmm_io_hook * hook = v3_get_io_hook(&(info->io_map), io_info->port); + struct v3_io_hook * hook = v3_get_io_hook(info, io_info->port); int read_size = 0; if (hook == NULL) { @@ -85,7 +82,7 @@ int v3_handle_svm_io_ins(struct guest_info * info) { struct svm_io_info * io_info = (struct svm_io_info *)&(ctrl_area->exit_info1); - struct vmm_io_hook * hook = v3_get_io_hook(&(info->io_map), io_info->port); + struct v3_io_hook * hook = v3_get_io_hook(info, io_info->port); int read_size = 0; addr_t dst_addr = 0; @@ -221,7 +218,7 @@ int v3_handle_svm_io_out(struct guest_info * info) { // vmcb_saved_state_t * guest_state = GET_VMCB_SAVE_STATE_AREA((vmcb_t*)(info->vmm_data)); struct svm_io_info * io_info = (struct svm_io_info *)&(ctrl_area->exit_info1); - struct vmm_io_hook * hook = v3_get_io_hook(&(info->io_map), io_info->port); + struct v3_io_hook * hook = v3_get_io_hook(info, io_info->port); int write_size = 0; if (hook == NULL) { @@ -264,7 +261,7 @@ int v3_handle_svm_io_outs(struct guest_info * info) { struct svm_io_info * io_info = (struct svm_io_info *)&(ctrl_area->exit_info1); - struct vmm_io_hook * hook = v3_get_io_hook(&(info->io_map), io_info->port); + struct v3_io_hook * hook = v3_get_io_hook(info, io_info->port); int write_size = 0; addr_t dst_addr = 0; diff --git a/palacios/src/palacios/vmm_config.c b/palacios/src/palacios/vmm_config.c index 949b115..99033e5 100644 --- a/palacios/src/palacios/vmm_config.c +++ b/palacios/src/palacios/vmm_config.c @@ -68,7 +68,7 @@ int v3_config_guest(struct guest_info * info, struct v3_vm_config * config_ptr) // Initialize the subsystem data strutures v3_init_time(info); - v3_init_vmm_io_map(info); + v3_init_io_map(info); v3_init_msr_map(info); v3_init_interrupt_state(info); v3_init_dev_mgr(info); diff --git a/palacios/src/palacios/vmm_io.c b/palacios/src/palacios/vmm_io.c index 514d8e1..e3820b9 100644 --- a/palacios/src/palacios/vmm_io.c +++ b/palacios/src/palacios/vmm_io.c @@ -34,89 +34,79 @@ static int default_write(ushort_t port, void *src, uint_t length, void * priv_da static int default_read(ushort_t port, void * dst, uint_t length, void * priv_data); -void v3_init_vmm_io_map(struct guest_info * info) { - struct vmm_io_map * io_map = &(info->io_map); - io_map->num_ports = 0; - io_map->head = NULL; +void v3_init_io_map(struct guest_info * info) { + info->io_map.rb_node = NULL; } -static int add_io_hook(struct vmm_io_map * io_map, struct vmm_io_hook * io_hook) { +static inline struct v3_io_hook * __insert_io_hook(struct guest_info * info, struct v3_io_hook * hook) { + struct rb_node ** p = &(info->io_map.rb_node); + struct rb_node * parent = NULL; + struct v3_io_hook * tmp_hook = NULL; - if (!(io_map->head)) { - io_map->head = io_hook; - io_map->num_ports = 1; - return 0; - } else if (io_map->head->port > io_hook->port) { - io_hook->next = io_map->head; + while (*p) { + parent = *p; + tmp_hook = rb_entry(parent, struct v3_io_hook, tree_node); - io_map->head->prev = io_hook; - io_map->head = io_hook; - io_map->num_ports++; - - return 0; - } else { - struct vmm_io_hook * tmp_hook = io_map->head; - - while ((tmp_hook->next) && - (tmp_hook->next->port <= io_hook->port)) { - tmp_hook = tmp_hook->next; - } - - if (tmp_hook->port == io_hook->port) { - //tmp_hook->read = io_hook->read; - //tmp_hook->write = io_hook->write; - //V3_Free(io_hook); - return -1; + if (hook->port < tmp_hook->port) { + p = &(*p)->rb_left; + } else if (hook->port > tmp_hook->port) { + p = &(*p)->rb_right; } else { - io_hook->prev = tmp_hook; - io_hook->next = tmp_hook->next; + return tmp_hook; + } + } + rb_link_node(&(hook->tree_node), parent, p); + + return NULL; +} - if (tmp_hook->next) { - tmp_hook->next->prev = io_hook; - } - tmp_hook->next = io_hook; +static inline struct v3_io_hook * insert_io_hook(struct guest_info * info, struct v3_io_hook * hook) { + struct v3_io_hook * ret; - io_map->num_ports++; - return 0; - } + if ((ret = __insert_io_hook(info, hook))) { + return ret; } - return -1; + + v3_rb_insert_color(&(hook->tree_node), &(info->io_map)); + + return NULL; } -static int remove_io_hook(struct vmm_io_map * io_map, struct vmm_io_hook * io_hook) { - if (io_map->head == io_hook) { - io_map->head = io_hook->next; - } else if (io_hook->prev) { - io_hook->prev->next = io_hook->next; - } else { - return -1; - // data corruption failure - } - - if (io_hook->next) { - io_hook->next->prev = io_hook->prev; - } - io_map->num_ports--; +struct v3_io_hook * v3_get_io_hook(struct guest_info * info, uint_t port) { + struct rb_node * n = info->io_map.rb_node; + struct v3_io_hook * hook = NULL; - return 0; + while (n) { + hook = rb_entry(n, struct v3_io_hook, tree_node); + + if (port < hook->port) { + n = n->rb_left; + } else if (port > hook->port) { + n = n->rb_right; + } else { + return hook; + } + } + + return NULL; } + int v3_hook_io_port(struct guest_info * info, uint_t port, int (*read)(ushort_t port, void * dst, uint_t length, void * priv_data), int (*write)(ushort_t port, void * src, uint_t length, void * priv_data), void * priv_data) { - struct vmm_io_map * io_map = &(info->io_map); - struct vmm_io_hook * io_hook = (struct vmm_io_hook *)V3_Malloc(sizeof(struct vmm_io_hook)); + struct v3_io_hook * io_hook = (struct v3_io_hook *)V3_Malloc(sizeof(struct v3_io_hook)); io_hook->port = port; @@ -132,12 +122,10 @@ int v3_hook_io_port(struct guest_info * info, uint_t port, io_hook->write = write; } - io_hook->next = NULL; - io_hook->prev = NULL; io_hook->priv_data = priv_data; - if (add_io_hook(io_map, io_hook) != 0) { + if (insert_io_hook(info, io_hook)) { V3_Free(io_hook); return -1; } @@ -146,40 +134,35 @@ int v3_hook_io_port(struct guest_info * info, uint_t port, } int v3_unhook_io_port(struct guest_info * info, uint_t port) { - struct vmm_io_map * io_map = &(info->io_map); - struct vmm_io_hook * hook = v3_get_io_hook(io_map, port); + struct v3_io_hook * hook = v3_get_io_hook(info, port); if (hook == NULL) { return -1; } - remove_io_hook(io_map, hook); + v3_rb_erase(&(hook->tree_node), &(info->io_map)); + return 0; } -struct vmm_io_hook * v3_get_io_hook(struct vmm_io_map * io_map, uint_t port) { - struct vmm_io_hook * tmp_hook; - FOREACH_IO_HOOK(*io_map, tmp_hook) { - if (tmp_hook->port == port) { - return tmp_hook; - } - } - return NULL; -} -void v3_print_io_map(struct vmm_io_map * io_map) { - struct vmm_io_hook * iter = io_map->head; + +void v3_print_io_map(struct guest_info * info) { + struct v3_io_hook * tmp_hook = NULL; + struct rb_node * node = v3_rb_first(&(info->io_map)); PrintDebug("VMM IO Map (Entries=%d)\n", io_map->num_ports); - while (iter) { + do { + tmp_hook = rb_entry(node, struct v3_io_hook, tree_node); + PrintDebug("IO Port: %hu (Read=%p) (Write=%p)\n", - iter->port, - (void *)(iter->read), (void *)(iter->write)); - } + tmp_hook->port, + (void *)(tmp_hook->read), (void *)(tmp_hook->write)); + } while ((node = v3_rb_next(node))); }