palacios/src/geekos/vmm_mem.c

   1 #include <geekos/vmm_mem.h>
   2 #include <geekos/vmm.h>
   3 #include <geekos/vmm_util.h>
   4
   5 extern struct vmm_os_hooks * os_hooks;
   6
   7
   8 void init_mem_list(vmm_mem_list_t * list) {
   9   list->num_pages = 0;
  10   list->long_mode = false;
  11
  12   list->num_regions = 0;
  13   list->head = NULL;
  14 }
  15
  16
  17 void free_mem_list(vmm_mem_list_t * list) {
  18   mem_region_t * cursor = list->head;
  19   mem_region_t * tmp = NULL;
  20
  21   while(cursor) {
  22     tmp = cursor;
  23     cursor = cursor->next;
  24     VMMFree(tmp);
  25   }
  26
  27   VMMFree(list);
  28 }
  29
  30 /*** FOR THE LOVE OF GOD WRITE SOME UNIT TESTS FOR THIS THING ***/
  31
  32
  33
  34 // Scan the current list, and extend an existing region if one exists
  35 // Otherwise create a new region and merge it into the correct location in the list
  36 //
  37 // We scan to find the position at which to add the new region and insert it
  38 // Then we clean up any region following the new region that overlaps
  39 //
  40 // JRL: This is pretty hairy...
  41 int add_mem_list_pages(vmm_mem_list_t * list, ullong_t addr, uint_t num_pages) {
  42
  43   uint_t num_new_pages = num_pages;
  44   ullong_t new_end = addr + (num_pages * PAGE_SIZE);
  45
  46   mem_region_t * cursor = get_mem_list_cursor(list, addr);
  47
  48
  49
  50   // PrintDebug("Adding: 0x%x - 0x%x\n", addr, num_pages * PAGE_SIZE);
  51
  52   // Make a new region at the head of the list
  53   if (cursor == NULL) {
  54     cursor = os_hooks->malloc(sizeof(mem_region_t));
  55
  56     cursor->prev = NULL;
  57     cursor->addr = addr;
  58     cursor->num_pages = num_pages;
  59
  60     cursor->next = list->head;
  61     list->head = cursor;
  62
  63     if (cursor->next) {
  64       cursor->next->prev = cursor;
  65     }
  66
  67     list->num_regions++;
  68   } else {
  69     ullong_t cursor_end = cursor->addr + (cursor->num_pages * PAGE_SIZE);
  70
  71     if (addr > cursor_end) {
  72       // address falls after cursor region
  73
  74       mem_region_t * new_region = os_hooks->malloc(sizeof(mem_region_t));
  75
  76       new_region->prev = cursor;
  77       new_region->next = cursor->next;
  78
  79       if (cursor->next) {
  80         cursor->next->prev = new_region;
  81       }
  82       cursor->next = new_region;
  83
  84       new_region->addr = addr;
  85       new_region->num_pages = num_pages;
  86
  87       list->num_regions++;
  88
  89       cursor = new_region;
  90     } else if ((addr >= cursor->addr) &&
  91                (addr <= cursor_end)) {
  92       // address falls inside the cursor region
  93
  94
  95       // The region has already been added
  96       if (new_end <= cursor_end) {
  97         return -1;
  98       }
  99
 100       // We need to extend the old region
 101       num_new_pages = (new_end - cursor_end) / PAGE_SIZE;
 102       cursor->num_pages += num_new_pages;
 103
 104     }
 105   }
 106
 107   // Clean up any overlaps that follow
 108   while ((cursor->next) && (cursor->next->addr <= new_end)) {
 109     mem_region_t * overlap = cursor->next;
 110     ullong_t overlap_end = overlap->addr + (overlap->num_pages * PAGE_SIZE);
 111
 112     cursor->next = overlap->next;
 113     if (overlap->next) {
 114       overlap->next->prev = cursor;
 115     }
 116
 117     if (overlap_end > new_end) {
 118       uint_t extension = (overlap_end - new_end) / PAGE_SIZE;
 119
 120       cursor->num_pages += extension;
 121       num_new_pages -= (overlap->num_pages - extension);
 122     } else {
 123       num_new_pages -= overlap->num_pages;
 124     }
 125
 126     VMMFree(overlap);
 127
 128     list->num_regions--;
 129   }
 130
 131
 132   list->num_pages += num_new_pages;
 133
 134   return 0;
 135 }
 136
 137
 138 /* this function returns a pointer to the location in the memory list that
 139  * corresponds to addr.
 140  * Rules:
 141  *     IF addr is in a region, a ptr to that region is returned
 142  *     IF addr is not in a region, a ptr to the previous region is returned
 143  *     IF addr is before all regions, returns NULL
 144  *     IF list is empty, returns NULL
 145  */
 146 mem_region_t * get_mem_list_cursor(vmm_mem_list_t * list, ullong_t addr) {
 147   mem_region_t * prev_region = list->head;
 148
 149   while (prev_region != NULL) {
 150     if ( (addr >= prev_region->addr) &&
 151          (addr <= (prev_region->addr + (prev_region->num_pages * PAGE_SIZE))) ) {
 152       return prev_region;
 153     } else if (addr < prev_region->addr) {
 154       // If this region is the current head, then this should return NULL
 155       return prev_region->prev;
 156     } else if (addr > (prev_region->addr + (prev_region->num_pages * PAGE_SIZE))) {
 157       if (prev_region->next) {
 158         prev_region = prev_region->next;
 159       } else {
 160         return prev_region;
 161       }
 162     }
 163   }
 164
 165   return prev_region;
 166 }
 167
 168
 169
 170 void init_mem_layout(vmm_mem_layout_t * layout) {
 171   layout->num_pages = 0;
 172   layout->num_regions = 0;
 173
 174   layout->head = NULL;
 175 }
 176
 177
 178 void free_mem_layout(vmm_mem_layout_t * layout) {
 179   layout_region_t * cursor = layout->head;
 180   layout_region_t * tmp = NULL;
 181
 182   while(cursor) {
 183     tmp = cursor;
 184     cursor = cursor->next;
 185     VMMFree(tmp);
 186   }
 187
 188   VMMFree(layout);
 189
 190 }
 191
 192
 193 /* this function returns a pointer to the location in the layout list that
 194  * corresponds to addr.
 195  * Rules:
 196  *     IF addr is in a region, a ptr to that region is returned
 197  *     IF addr is not in a region, a ptr to the previous region is returned
 198  *     IF addr is before all regions, returns NULL
 199  *     IF list is empty, returns NULL
 200  */
 201 layout_region_t * get_layout_cursor(vmm_mem_layout_t * layout, ullong_t addr) {
 202   layout_region_t * prev_region = layout->head;
 203
 204
 205   while (prev_region != NULL) {
 206     if ( (addr >= prev_region->addr) &&
 207          (addr <= (prev_region->addr + (prev_region->num_pages * PAGE_SIZE))) ) {
 208       return prev_region;
 209     } else if (addr < prev_region->addr) {
 210       // If this region is the current head, then this should return NULL
 211       return prev_region->prev;
 212     } else if (addr > (prev_region->addr + (prev_region->num_pages * PAGE_SIZE))) {
 213       if (prev_region->next) {
 214         prev_region = prev_region->next;
 215       } else {
 216         return prev_region;
 217       }
 218     }
 219   }
 220
 221   return prev_region;
 222 }
 223
 224
 225 /* This is slightly different semantically from the mem list, in that we don't allow overlaps
 226  * we could probably allow overlappig regions of the same type... but I'll let someone else deal with that
 227  */
 228 int add_mem_range(vmm_mem_layout_t * layout, layout_region_t * region) {
 229
 230   layout_region_t * cursor = get_layout_cursor(layout, region->addr);
 231
 232   if (cursor == NULL) {
 233     if (layout->head) {
 234       if (layout->head->addr < region->addr + (region->num_pages * PAGE_SIZE)) {
 235         // overlaps not allowed
 236         return -1;
 237       }
 238       layout->head->prev = region;
 239     }
 240
 241     region->prev = NULL;
 242     region->next = layout->head;
 243     layout->head = region;
 244
 245     layout->num_regions++;
 246     layout->num_pages += region->num_pages;
 247   } else if ((region->addr >= cursor->addr) &&
 248              (region->addr <= cursor->addr + (cursor->num_pages * PAGE_SIZE))) {
 249     // overlaps not allowed
 250     return -1;
 251   } else if (region->addr > cursor->addr + (cursor->num_pages * PAGE_SIZE)) {
 252     // add region to layout
 253     region->next = cursor->next;
 254     region->prev = cursor;
 255
 256     if (region->next) {
 257       region->next->prev = region;
 258     }
 259     cursor->next = region;
 260
 261     layout->num_regions++;
 262     layout->num_pages += region->num_pages;
 263   } else {
 264     return -1;
 265   }
 266
 267
 268   return 0;
 269 }
 270
 271
 272
 273
 274
 275 int add_shared_mem_range(vmm_mem_layout_t * layout, ullong_t addr, uint_t num_pages, ullong_t host_addr) {
 276   layout_region_t * shared_region = os_hooks->malloc(sizeof(layout_region_t));
 277
 278   shared_region->next = NULL;
 279   shared_region->prev = NULL;
 280   shared_region->addr = addr;
 281   shared_region->num_pages = num_pages;
 282   shared_region->type = SHARED;
 283   shared_region->host_addr = host_addr;
 284
 285   return add_mem_range(layout, shared_region);
 286 }
 287
 288 int add_unmapped_mem_range(vmm_mem_layout_t * layout, ullong_t addr, uint_t num_pages) {
 289   layout_region_t * unmapped_region = os_hooks->malloc(sizeof(layout_region_t));
 290
 291   unmapped_region->next = NULL;
 292   unmapped_region->prev = NULL;
 293   unmapped_region->addr = addr;
 294   unmapped_region->num_pages = num_pages;
 295   unmapped_region->type = UNMAPPED;
 296   unmapped_region->host_addr = 0;
 297
 298   return add_mem_range(layout, unmapped_region);
 299 }
 300
 301 int add_guest_mem_range(vmm_mem_layout_t * layout, ullong_t addr, uint_t num_pages) {
 302   layout_region_t * guest_region = os_hooks->malloc(sizeof(layout_region_t));
 303
 304   guest_region->next = NULL;
 305   guest_region->prev = NULL;
 306   guest_region->addr = addr;
 307   guest_region->num_pages = num_pages;
 308   guest_region->type = GUEST;
 309   guest_region->host_addr = 0;
 310
 311   return add_mem_range(layout, guest_region);
 312 }
 313
 314
 315
 316
 317
 318 void print_mem_list(vmm_mem_list_t * list) {
 319   mem_region_t * cur = list->head;
 320   int i = 0;
 321
 322   PrintDebug("Memory Region List (regions: %d) (pages: %d)\n", list->num_regions, list->num_pages);
 323
 324   while (cur) {
 325     PrintDebug("%d: 0x%x - 0x%x\n", i, cur->addr, cur->addr + (cur->num_pages * PAGE_SIZE));
 326     cur = cur->next;
 327     i++;
 328   }
 329   PrintDebug("\n");
 330 }
 331
 332
 333
 334 void print_mem_layout(vmm_mem_layout_t * layout) {
 335   layout_region_t * cur = layout->head;
 336   int i = 0;
 337
 338   PrintDebug("Memory Layout (regions: %d) (pages: %d)\n", layout->num_regions, layout->num_pages);
 339
 340   while (cur) {
 341     PrintDebug("%d: 0x%x - 0x%x\n", i, cur->addr, cur->addr + (cur->num_pages * PAGE_SIZE));
 342     cur = cur->next;
 343     i++;
 344   }
 345   PrintDebug("\n");
 346 }
 347
 348
 349
 350 #ifdef VMM_MEM_TEST
 351 #include <stdlib.h>
 352 #include <stdio.h>
 353 #include <stdarg.h>
 354
 355
 356
 357
 358 struct vmm_os_hooks * os_hooks;
 359
 360 void * TestMalloc(uint_t size) {
 361   return malloc(size);
 362 }
 363
 364 void TestPrint(const char * fmt, ...) {
 365   va_list args;
 366
 367   va_start(args, fmt);
 368   vprintf(fmt, args);
 369   va_end(args);
 370 }
 371
 372 int mem_list_add_test_1() {
 373   vmm_mem_list_t list;
 374   uint_t offset = 0;
 375
 376   init_mem_list(&list);
 377
 378   offset = PAGE_SIZE * 6;
 379   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 10));
 380   add_mem_list_pages(&list, PAGE_SIZE * 6, 10);
 381   print_mem_list(&list);
 382
 383
 384   offset = 0;
 385   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + PAGE_SIZE * 4);
 386   add_mem_list_pages(&list, 0, 4);
 387   print_mem_list(&list);
 388
 389   offset = PAGE_SIZE * 20;
 390   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
 391   add_mem_list_pages(&list, PAGE_SIZE * 20, 1);
 392   print_mem_list(&list);
 393
 394
 395   offset = PAGE_SIZE * 10;
 396   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 30));
 397   add_mem_list_pages(&list, PAGE_SIZE * 10, 30);
 398   print_mem_list(&list);
 399
 400   return 0;
 401 }
 402
 403
 404 int mem_layout_add_test_1() {
 405   vmm_mem_layout_t layout;
 406   uint_t offset = 0;
 407
 408   init_mem_layout(&layout);
 409
 410   offset = PAGE_SIZE * 6;
 411   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 10));
 412   add_guest_mem_range(&layout, PAGE_SIZE * 6, 10);
 413   print_mem_layout(&layout);
 414
 415
 416   offset = 0;
 417   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + PAGE_SIZE * 4);
 418   add_guest_mem_range(&layout, 0, 4);
 419   print_mem_layout(&layout);
 420
 421   offset = PAGE_SIZE * 20;
 422   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
 423   add_guest_mem_range(&layout, PAGE_SIZE * 20, 1);
 424   print_mem_layout(&layout);
 425
 426
 427   offset = PAGE_SIZE * 10;
 428   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 30));
 429   add_guest_mem_range(&layout, PAGE_SIZE * 10, 30);
 430   print_mem_layout(&layout);
 431
 432   return 0;
 433 }
 434
 435
 436
 437 int main(int argc, char ** argv) {
 438   struct vmm_os_hooks dummy_hooks;
 439   os_hooks = &dummy_hooks;
 440
 441   os_hooks->malloc = &TestMalloc;
 442   os_hooks->free = &free;
 443   os_hooks->print_debug = &TestPrint;
 444
 445
 446   printf("mem_list_add_test_1: %d\n", mem_list_add_test_1());
 447   printf("layout_add_test_t: %d\n", mem_layout_add_test_1());
 448
 449   return 0;
 450 }
 451 #endif