X-Git-Url: http://v3vee.org/palacios/gitweb/gitweb.cgi?p=palacios.git;a=blobdiff_plain;f=palacios%2Fsrc%2Fpalacios%2Fvmm_mem.c;fp=palacios%2Fsrc%2Fpalacios%2Fvmm_mem.c;h=62bca6659cbf718cf4070272ea581fc9a740ac80;hp=fa17e9761cd5791daa2936082e0c24cb69cb773a;hb=24178516ccd9f46718b687d4c630415eb63ff595;hpb=19b0b4544674b4f9bc727da5242d625f18821a48

diff --git a/palacios/src/palacios/vmm_mem.c b/palacios/src/palacios/vmm_mem.c
index fa17e97..62bca66 100644
--- a/palacios/src/palacios/vmm_mem.c
+++ b/palacios/src/palacios/vmm_mem.c
@@ -24,48 +24,84 @@
 
 
 
-void init_shadow_region(struct shadow_region * entry,
-			addr_t               guest_addr_start,
-			addr_t               guest_addr_end,
-			shdw_region_type_t   shdw_region_type)
-{
-  entry->guest_start = guest_addr_start;
-  entry->guest_end = guest_addr_end;
-  entry->host_type = shdw_region_type;
-  entry->host_addr = 0;
-  entry->next = entry->prev = NULL;
+
+
+
+
+static inline
+struct v3_shadow_region * insert_shadow_region(struct guest_info * info, 
+ 					       struct v3_shadow_region * region);
+
+
+
+void v3_init_shadow_map(struct guest_info * info) {
+  info->mem_map.rb_node = NULL;
+}
+
+void v3_delete_shadow_map(struct guest_info * info) {
+  struct rb_node * node = v3_rb_first(&(info->mem_map));
+  struct v3_shadow_region * reg;
+  struct rb_node * tmp_node = NULL;
+  
+   while (node) {
+    reg = rb_entry(node, struct v3_shadow_region, tree_node);
+    tmp_node = node;
+    node = v3_rb_next(node);
+
+    v3_delete_shadow_region(info, reg);
+  }
 }
 
-int add_shadow_region_passthrough( struct guest_info *  guest_info,
-				   addr_t               guest_addr_start,
-				   addr_t               guest_addr_end,
-				   addr_t               host_addr)
+
+
+
+int v3_add_shadow_mem( struct guest_info *  info,
+		       addr_t               guest_addr_start,
+		       addr_t               guest_addr_end,
+		       addr_t               host_addr)
 {
-  struct shadow_region * entry = (struct shadow_region *)V3_Malloc(sizeof(struct shadow_region));
+  struct v3_shadow_region * entry = (struct v3_shadow_region *)V3_Malloc(sizeof(struct v3_shadow_region));
 
-  init_shadow_region(entry, guest_addr_start, guest_addr_end, 
-		     SHDW_REGION_ALLOCATED);
+  entry->guest_start = guest_addr_start;
+  entry->guest_end = guest_addr_end;
+  entry->host_type = SHDW_REGION_ALLOCATED;
   entry->host_addr = host_addr;
+  entry->write_hook = NULL;
+  entry->read_hook = NULL;
+  entry->priv_data = NULL;
+
+  if (insert_shadow_region(info, entry)) {
+    V3_Free(entry);
+    return -1;
+  }
 
-  return add_shadow_region(&(guest_info->mem_map), entry);
+  return 0;
 }
 
+
+
 int v3_hook_write_mem(struct guest_info * info, addr_t guest_addr_start, addr_t guest_addr_end, 
 		      addr_t host_addr,
 		      int (*write)(addr_t guest_addr, void * src, uint_t length, void * priv_data),
 		      void * priv_data) {
 
-  struct shadow_region * entry = (struct shadow_region *)V3_Malloc(sizeof(struct shadow_region));
+  struct v3_shadow_region * entry = (struct v3_shadow_region *)V3_Malloc(sizeof(struct v3_shadow_region));
 
-  init_shadow_region(entry, guest_addr_start, guest_addr_end, 
-		     SHDW_REGION_WRITE_HOOK);
 
+  entry->guest_start = guest_addr_start;
+  entry->guest_end = guest_addr_end;
+  entry->host_type = SHDW_REGION_WRITE_HOOK;
+  entry->host_addr = host_addr;
   entry->write_hook = write;
   entry->read_hook = NULL;
-  entry->host_addr = host_addr;
   entry->priv_data = priv_data;
 
-  return add_shadow_region(&(info->mem_map), entry);  
+  if (insert_shadow_region(info, entry)) {
+    V3_Free(entry);
+    return -1;
+  }
+
+  return 0;  
 }
 
 int v3_hook_full_mem(struct guest_info * info, addr_t guest_addr_start, addr_t guest_addr_end,
@@ -73,28 +109,79 @@ int v3_hook_full_mem(struct guest_info * info, addr_t guest_addr_start, addr_t g
 		     int (*write)(addr_t guest_addr, void * src, uint_t length, void * priv_data),
 		     void * priv_data) {
   
-  struct shadow_region * entry = (struct shadow_region *)V3_Malloc(sizeof(struct shadow_region));
-
-  init_shadow_region(entry, guest_addr_start, guest_addr_end, 
-		     SHDW_REGION_FULL_HOOK);
+  struct v3_shadow_region * entry = (struct v3_shadow_region *)V3_Malloc(sizeof(struct v3_shadow_region));
 
+  entry->guest_start = guest_addr_start;
+  entry->guest_end = guest_addr_end;
+  entry->host_type = SHDW_REGION_FULL_HOOK;
+  entry->host_addr = (addr_t)NULL;
   entry->write_hook = write;
   entry->read_hook = read;
   entry->priv_data = priv_data;
+  
+  if (insert_shadow_region(info, entry)) {
+    V3_Free(entry);
+    return -1;
+  }
+
+  return 0;
+}
+
+
+
 
-  entry->host_addr = 0;
+static inline 
+struct v3_shadow_region * __insert_shadow_region(struct guest_info * info, 
+						 struct v3_shadow_region * region) {
+  struct rb_node ** p = &(info->mem_map.rb_node);
+  struct rb_node * parent = NULL;
+  struct v3_shadow_region * tmp_region;
 
-  return add_shadow_region(&(info->mem_map), entry);
+  while (*p) {
+    parent = *p;
+    tmp_region = rb_entry(parent, struct v3_shadow_region, tree_node);
+
+    if (region->guest_end <= tmp_region->guest_start) {
+      p = &(*p)->rb_left;
+    } else if (region->guest_start >= tmp_region->guest_end) {
+      p = &(*p)->rb_right;
+    } else {
+      return tmp_region;
+    }
+  }
+
+  rb_link_node(&(region->tree_node), parent, p);
+  
+  return NULL;
 }
 
 
+static inline
+struct v3_shadow_region * insert_shadow_region(struct guest_info * info, 
+ 					       struct v3_shadow_region * region) {
+  struct v3_shadow_region * ret;
+
+  if ((ret = __insert_shadow_region(info, region))) {
+    return ret;
+  }
+  
+  v3_rb_insert_color(&(region->tree_node), &(info->mem_map));
+
+  return NULL;
+}
+						 
+
+
+
+
+
 
 
 int handle_special_page_fault(struct guest_info * info, 
 			      addr_t fault_gva, addr_t fault_gpa, 
 			      pf_error_t access_info) 
 {
- struct shadow_region * reg = get_shadow_region_by_addr(&(info->mem_map), fault_gpa);
+ struct v3_shadow_region * reg = v3_get_shadow_region(info, fault_gpa);
 
   PrintDebug("Handling Special Page Fault\n");
 
@@ -112,7 +199,7 @@ int handle_special_page_fault(struct guest_info * info,
 }
 
 int v3_handle_mem_wr_hook(struct guest_info * info, addr_t guest_va, addr_t guest_pa, 
-			  struct shadow_region * reg, pf_error_t access_info) {
+			  struct v3_shadow_region * reg, pf_error_t access_info) {
 
   addr_t write_src_addr = 0;
 
@@ -133,211 +220,79 @@ int v3_handle_mem_wr_hook(struct guest_info * info, addr_t guest_va, addr_t gues
 }
 
 int v3_handle_mem_full_hook(struct guest_info * info, addr_t guest_va, addr_t guest_pa, 
-			    struct shadow_region * reg, pf_error_t access_info) {
+			    struct v3_shadow_region * reg, pf_error_t access_info) {
   return -1;
 }
 
 
 
-struct shadow_region * v3_get_shadow_region(struct guest_info * info, addr_t addr) {
-  struct shadow_region * reg = info->mem_map.head;
-
-  while (reg) {
-    if ((reg->guest_start <= addr) && (reg->guest_end > addr)) {
-      return reg;
-    } else if (reg->guest_start > addr) {
-      return NULL;
-    } else {
-      reg = reg->next;
-    }
-  }
-  return NULL;
-}
-
-
-void init_shadow_map(struct guest_info * info) {
-  struct shadow_map * map = &(info->mem_map);
-
-  map->num_regions = 0;
-
-  map->head = NULL;
-}
-
+struct v3_shadow_region * v3_get_shadow_region(struct guest_info * info, addr_t guest_addr) {
+  struct rb_node * n = info->mem_map.rb_node;
+  struct v3_shadow_region * reg = NULL;
 
-void free_shadow_map(struct shadow_map * map) {
-  struct shadow_region * cursor = map->head;
-  struct shadow_region * tmp = NULL;
+  while (n) {
+    reg = rb_entry(n, struct v3_shadow_region, tree_node);
 
-  while(cursor) {
-    tmp = cursor;
-    cursor = cursor->next;
-    V3_Free(tmp);
-  }
-
-  V3_Free(map);
-}
-
-
-
-
-int add_shadow_region(struct shadow_map * map,
-		      struct shadow_region * region) 
-{
-  struct shadow_region * cursor = map->head;
-
-  PrintDebug("Adding Shadow Region: (0x%p-0x%p)\n", 
-	     (void *)region->guest_start, (void *)region->guest_end);
-
-  if ((!cursor) || (cursor->guest_start >= region->guest_end)) {
-    region->prev = NULL;
-    region->next = cursor;
-    map->num_regions++;
-    map->head = region;
-    return 0;
-  }
-
-  while (cursor) {
-    // Check if it overlaps with the current cursor
-    if ((cursor->guest_end > region->guest_start) && (cursor->guest_start < region->guest_start)) {
-      // overlaps not allowed
-      return -1;
-    }
-    
-    if (!(cursor->next)) {
-      // add to the end of the list
-      cursor->next = region;
-      region->prev = cursor;
-      region->next = NULL;
-      map->num_regions++;
-      return 0;
-    } else if (cursor->next->guest_start >= region->guest_end) {
-      // add here
-      region->next = cursor->next;
-      region->prev = cursor;
-      
-      cursor->next->prev = region;
-      cursor->next = region;
-
-      map->num_regions++;
-      
-      return 0;
-    } else if (cursor->next->guest_end <= region->guest_start) {
-      cursor = cursor->next;
+    if (guest_addr < reg->guest_start) {
+      n = n->rb_left;
+    } else if (guest_addr >= reg->guest_end) {
+      n = n->rb_right;
     } else {
-      // This cannot happen!
-      // we should panic here
-      return -1;
-    }
-  }
-  
-  // This cannot happen
-  // We should panic here
-  return -1;
-}
-
-
-int delete_shadow_region(struct shadow_map * map,
-			 addr_t guest_start,
-			 addr_t guest_end) {
-  return -1;
-}
-
-
-
-struct shadow_region *get_shadow_region_by_index(struct shadow_map *  map,
-						 uint_t index) {
-  struct shadow_region * reg = map->head;
-  uint_t i = 0;
-
-  while (reg) { 
-    if (i == index) { 
       return reg;
     }
-    reg = reg->next;
-    i++;
   }
-  return NULL;
-}
-
-
-struct shadow_region * get_shadow_region_by_addr(struct shadow_map * map,
-						 addr_t addr) {
-  struct shadow_region * reg = map->head;
 
-  while (reg) {
-    if ((reg->guest_start <= addr) && (reg->guest_end > addr)) {
-      return reg;
-    } else if (reg->guest_start > addr) {
-      return NULL;
-    } else {
-      reg = reg->next;
-    }
-  }
   return NULL;
 }
 
 
-shdw_region_type_t get_shadow_addr_type(struct guest_info * info, addr_t guest_addr) {
-  struct shadow_region * reg = get_shadow_region_by_addr(&(info->mem_map), guest_addr);
 
-  if (!reg) {
-    return SHDW_REGION_INVALID;
+addr_t v3_get_shadow_addr(struct v3_shadow_region * reg, addr_t guest_addr) {
+  if ((reg) && 
+      (reg->host_type != SHDW_REGION_FULL_HOOK) &&
+      (reg->host_type != SHDW_REGION_INVALID)) {
+    return (guest_addr - reg->guest_start) + reg->host_addr;
   } else {
-    return reg->host_type;
-  }
-}
-
-addr_t get_shadow_addr(struct guest_info * info, addr_t guest_addr) {
-  struct shadow_region * reg = get_shadow_region_by_addr(&(info->mem_map), guest_addr);
-
-  if (!reg) {
+    PrintError("MEM Region Invalid\n");
     return 0;
-  } else {
-    return (guest_addr - reg->guest_start) + reg->host_addr;
   }
 }
 
 
-shdw_region_type_t lookup_shadow_map_addr(struct shadow_map * map, addr_t guest_addr, addr_t * host_addr) {
-  struct shadow_region * reg = get_shadow_region_by_addr(map, guest_addr);
 
-  if (!reg) {
-    // No mapping exists
-    return SHDW_REGION_INVALID;
-  } else {
-    switch (reg->host_type) {
-    case SHDW_REGION_ALLOCATED:
-    case SHDW_REGION_WRITE_HOOK:
-     *host_addr = (guest_addr - reg->guest_start) + reg->host_addr;
-     return reg->host_type;
-    case SHDW_REGION_UNALLOCATED:
-    case SHDW_REGION_FULL_HOOK:
-      // ... 
-    default:
-      *host_addr = 0;
-      return reg->host_type;
-    }
+void v3_delete_shadow_region(struct guest_info * info, struct v3_shadow_region * reg) {
+  if (reg != NULL) {
+    v3_rb_erase(&(reg->tree_node), &(info->mem_map));
+
+    V3_Free(reg);
   }
 }
 
 
-void print_shadow_map(struct shadow_map * map) {
-  struct shadow_region * cur = map->head;
+
+
+void print_shadow_map(struct guest_info * info) {
+  struct rb_node * node = v3_rb_first(&(info->mem_map));
+  struct v3_shadow_region * reg;
   int i = 0;
 
-  PrintDebug("Memory Layout (regions: %d) \n", map->num_regions);
+  PrintDebug("Memory Layout:\n");
 
-  while (cur) {
-    PrintDebug("%d:  0x%p - 0x%p -> ", i, 
-	       (void *)cur->guest_start, (void *)(cur->guest_end - 1));
-    if (cur->host_type == SHDW_REGION_ALLOCATED || 
-	cur->host_type == SHDW_REGION_UNALLOCATED) {
-      PrintDebug("0x%p", (void *)(cur->host_addr));
-    }
-    PrintDebug("(%s)\n", shdw_region_type_to_str(cur->host_type));
-    cur = cur->next;
+  do {
+    reg = rb_entry(node, struct v3_shadow_region, tree_node);
+
+    PrintDebug("%d:  0x%p - 0x%p -> 0x%p\n", i, 
+	       (void *)(reg->guest_start), 
+	       (void *)(reg->guest_end - 1), 
+	       (void *)(reg->host_addr));
+
+    PrintDebug("\t(%s) (WriteHook = 0x%p) (ReadHook = 0x%p)\n", 
+	       v3_shdw_region_type_to_str(reg->host_type),
+	       (void *)(reg->write_hook), 
+	       (void *)(reg->read_hook));
+    
     i++;
-  }
+  } while ((node = v3_rb_next(node)));
 }
 
 
@@ -345,183 +300,19 @@ static const uchar_t  SHDW_REGION_INVALID_STR[] = "SHDW_REGION_INVALID";
 static const uchar_t  SHDW_REGION_WRITE_HOOK_STR[] = "SHDW_REGION_WRITE_HOOK";
 static const uchar_t  SHDW_REGION_FULL_HOOK_STR[] = "SHDW_REGION_FULL_HOOK";
 static const uchar_t  SHDW_REGION_ALLOCATED_STR[] = "SHDW_REGION_ALLOCATED";
-static const uchar_t  SHDW_REGION_UNALLOCATED_STR[] = "SHDW_REGION_UNALLOCATED";
 
 
 
-const uchar_t * shdw_region_type_to_str(shdw_region_type_t type) {
+const uchar_t * v3_shdw_region_type_to_str(v3_shdw_region_type_t type) {
   switch (type) {
-  case SHDW_REGION_INVALID: 
-    return SHDW_REGION_INVALID_STR;
   case SHDW_REGION_WRITE_HOOK:
     return SHDW_REGION_WRITE_HOOK_STR;
   case SHDW_REGION_FULL_HOOK:
     return SHDW_REGION_FULL_HOOK_STR;
   case SHDW_REGION_ALLOCATED:
     return SHDW_REGION_ALLOCATED_STR;
-  case SHDW_REGION_UNALLOCATED:
-    return SHDW_REGION_UNALLOCATED_STR;
   default:
     return SHDW_REGION_INVALID_STR;
   }
 }
 
-
-
-
-
-
-
-#ifdef VMM_MEM_TEST
-
-
-#include <stdlib.h>
-#include <stdio.h>
-#include <stdarg.h>
-
-
-
-
-
-struct vmm_os_hooks * os_hooks;
-
-void * TestMalloc(uint_t size) {
-  return malloc(size);
-}
-
-void * TestAllocatePages(int size) {
-  return malloc(4096 * size);
-}
-
-
-void TestPrint(const char * fmt, ...) {
-  va_list args;
-
-  va_start(args, fmt);
-  vprintf(fmt, args);
-  va_end(args);
-}
-
-int mem_list_add_test_1(  vmm_mem_list_t * list) {
-
-  uint_t offset = 0;
-
-  PrintDebug("\n\nTesting Memory List\n");
-
-  init_mem_list(list);
-
-  offset = PAGE_SIZE * 6;
-  PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 10));
-  add_mem_list_pages(list, offset, 10);
-  print_mem_list(list);
-
-
-  offset = 0;
-  PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + PAGE_SIZE * 4);
-  add_mem_list_pages(list, offset, 4);
-  print_mem_list(list);
-
-  offset = PAGE_SIZE * 20;
-  PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
-  add_mem_list_pages(list, offset, 1);
-  print_mem_list(list);
-
-  offset = PAGE_SIZE * 21;
-  PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 3));
-  add_mem_list_pages(list, offset, 3);
-  print_mem_list(list);
-
-
-  offset = PAGE_SIZE * 10;
-  PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 30));
-  add_mem_list_pages(list, offset, 30);
-  print_mem_list(list);
-
-
-  offset = PAGE_SIZE * 5;
-  PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
-  add_mem_list_pages(list, offset, 1);
-  print_mem_list(list);
-
- 
-
-  return 0;
-}
-
-
-int mem_layout_add_test_1(vmm_mem_layout_t * layout) {
-
-  
-  uint_t start = 0;
-  uint_t end = 0;
-
-  PrintDebug("\n\nTesting Memory Layout\n");
-
-  init_mem_layout(layout);
-
-  start = 0x6000;
-  end = 0x10000;;
-  PrintDebug("Adding 0x%x - 0x%x\n", start, end);
-  add_guest_mem_range(layout, start, end);
-  print_mem_layout(layout);
-
-
-  start = 0x1000;
-  end = 0x3000;
-  PrintDebug("Adding 0x%x - 0x%x\n", start, end);
-  add_guest_mem_range(layout, start, end);
-  print_mem_layout(layout);
-
-  start = 0x2000;
-  end = 0x6000;
-  PrintDebug("Adding 0x%x - 0x%x\n", start, end);
-  add_guest_mem_range(layout, start, end);
-  print_mem_layout(layout);
-
-  start = 0x4000;
-  end = 0x5000;
-  PrintDebug("Adding 0x%x - 0x%x\n", start, end);
-  add_guest_mem_range(layout, start, end);
-  print_mem_layout(layout);
-
-
-  start = 0x5000;
-  end = 0x7000;
-  PrintDebug("Adding 0x%x - 0x%x\n", start, end);
-  add_guest_mem_range(layout, start, end);
-  print_mem_layout(layout);
-
-
-
-
-  return 0;
-}
-
-
-
-int main(int argc, char ** argv) {
-  struct vmm_os_hooks dummy_hooks;
-  os_hooks = &dummy_hooks;
-
-  vmm_mem_layout_t layout;
-  vmm_mem_list_t list;
-
-  os_hooks->malloc = &TestMalloc;
-  os_hooks->free = &free;
-  os_hooks->print_debug = &TestPrint;
-  os_hooks->allocate_pages = &TestAllocatePages;
-
-
-
-  printf("mem_list_add_test_1: %d\n", mem_list_add_test_1(&list));
-  printf("layout_add_test_1: %d\n", mem_layout_add_test_1(&layout));
-
-  return 0;
-}
-#endif
-
-
-
-
-
-