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 (file)
--- 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 (file)
--- 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 (file)
--- a/palacios/include/palacios/vmm_io.h
+++ b/palacios/include/palacios/vmm_io.h
@@ -25,11 +25,16 @@
 
 #include <palacios/vmm_types.h>
 #include <palacios/vmm_util.h>
+#include <palacios/vmm_rbtree.h>
+
+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 (file)
--- a/palacios/src/palacios/svm.c
+++ b/palacios/src/palacios/svm.c
@@ -37,6 +37,7 @@
 #include <palacios/vmm_lowlevel.h>
 #include <palacios/svm_msr.h>
 
+#include <palacios/vmm_rbtree.h>
 
 
 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 (file)
--- 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 <palacios/svm_io.h>
 #include <palacios/vmm_io.h>
 #include <palacios/vmm_ctrl_regs.h>
@@ -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 (file)
--- 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 (file)
--- 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)));
 }