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, addr_t addr, uint_t num_pages) {
  42
  43   uint_t num_new_pages = num_pages;
  44   addr_t new_end = addr + (num_pages * PAGE_SIZE) - 1;
  45
  46   mem_region_t * cursor = get_mem_list_cursor(list, addr);
  47
  48
  49   // PrintDebug("Adding: 0x%x - 0x%x\n", addr, num_pages * PAGE_SIZE);
  50
  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     addr_t cursor_end = cursor->addr + (cursor->num_pages * PAGE_SIZE) - 1;
  70
  71     if (addr > cursor_end + 1) {
  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 + 1)) {
  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
 108   // Clean up any overlaps that follow
 109   while ((cursor->next) && (cursor->next->addr <= new_end + 1)) {
 110     mem_region_t * overlap = cursor->next;
 111     addr_t overlap_end = overlap->addr + (overlap->num_pages * PAGE_SIZE) - 1;
 112
 113     cursor->next = overlap->next;
 114     if (overlap->next) {
 115       overlap->next->prev = cursor;
 116     }
 117
 118     if (overlap_end > new_end) {
 119       uint_t extension = (overlap_end - new_end) / PAGE_SIZE;
 120
 121       cursor->num_pages += extension;
 122       num_new_pages -= (overlap->num_pages - extension);
 123     } else {
 124       num_new_pages -= overlap->num_pages;
 125     }
 126
 127     VMMFree(overlap);
 128
 129     list->num_regions--;
 130   }
 131
 132
 133   list->num_pages += num_new_pages;
 134
 135   return 0;
 136 }
 137
 138
 139 /* this function returns a pointer to the location in the memory list that
 140  * corresponds to addr.
 141  * Rules:
 142  *     IF addr is in a region, a ptr to that region is returned
 143  *     IF addr is not in a region, a ptr to the previous region is returned
 144  *     IF addr is before all regions, returns NULL
 145  *     IF list is empty, returns NULL
 146  */
 147 mem_region_t * get_mem_list_cursor(vmm_mem_list_t * list, addr_t addr) {
 148   mem_region_t * prev_region = list->head;
 149
 150   while (prev_region != NULL) {
 151     if ( (addr >= prev_region->addr) &&
 152          (addr < (prev_region->addr + (prev_region->num_pages * PAGE_SIZE) - 1)) ) {
 153       return prev_region;
 154     } else if (addr < prev_region->addr) {
 155       // If this region is the current head, then this should return NULL
 156       return prev_region->prev;
 157     } else if (addr >= (prev_region->addr + (prev_region->num_pages * PAGE_SIZE))) {
 158       if (prev_region->next) {
 159         prev_region = prev_region->next;
 160       } else {
 161         return prev_region;
 162       }
 163     }
 164   }
 165
 166   return prev_region;
 167 }
 168
 169
 170
 171 /* Returns the page address of page number 'index' in the memory list
 172  * If index is out of bounds... returns -1 (an invalid page address)
 173  */
 174 addr_t get_mem_list_addr(vmm_mem_list_t * list, uint_t index) {
 175   mem_region_t * reg = list->head;
 176   uint_t i = index;
 177
 178   // Memory List overrun
 179   if (index > list->num_pages - 1) {
 180     return -1;
 181   }
 182
 183   while (i >= 0) {
 184     if (reg->num_pages <= index) {
 185       i -= reg->num_pages;
 186       reg = reg->next;
 187     } else {
 188       return reg->addr + (i * PAGE_SIZE);
 189     }
 190   }
 191
 192   return -1;
 193 }
 194
 195
 196 void init_mem_layout(vmm_mem_layout_t * layout) {
 197   layout->num_pages = 0;
 198   layout->num_regions = 0;
 199
 200   layout->head = NULL;
 201 }
 202
 203
 204 void free_mem_layout(vmm_mem_layout_t * layout) {
 205   layout_region_t * cursor = layout->head;
 206   layout_region_t * tmp = NULL;
 207
 208   while(cursor) {
 209     tmp = cursor;
 210     cursor = cursor->next;
 211     VMMFree(tmp);
 212   }
 213
 214   VMMFree(layout);
 215
 216 }
 217
 218
 219
 220 /* This is slightly different semantically from the mem list, in that we don't allow overlaps
 221  * we could probably allow overlappig regions of the same type... but I'll let someone else deal with that
 222  */
 223 int add_mem_range(vmm_mem_layout_t * layout, layout_region_t * region) {
 224   layout_region_t * cursor = layout->head;
 225
 226   if ((!cursor) || (cursor->start >= region->end)) {
 227     region->prev = NULL;
 228     region->next = cursor;
 229     layout->num_pages += (region->end - region->start) / PAGE_SIZE;
 230     layout->num_regions++;
 231     layout->head = region;
 232
 233     return 0;
 234   }
 235
 236   while (cursor) {
 237     // Check if it overlaps with the current cursor
 238     if ((cursor->end > region->start) && (cursor->start < region->start)) {
 239       // overlaps not allowed
 240       return -1;
 241     }
 242
 243     // add to the end of the list
 244     if (!(cursor->next)) {
 245       cursor->next = region;
 246       region->prev = cursor;
 247       layout->num_regions++;
 248       layout->num_pages += (region->end - region->start) / PAGE_SIZE;
 249       return 0;
 250     } else if (cursor->next->start >= region->end) {
 251       // add here
 252       region->next = cursor->next;
 253       region->prev = cursor;
 254
 255       cursor->next->prev = region;
 256       cursor->next = region;
 257
 258       layout->num_regions++;
 259       layout->num_pages += (region->end - region->start) / PAGE_SIZE;
 260
 261       return 0;
 262     } else if (cursor->next->end < region->start) {
 263       cursor = cursor->next;
 264     } else {
 265       return -1;
 266     }
 267   }
 268
 269   return -1;
 270 }
 271
 272
 273
 274
 275
 276 int add_shared_mem_range(vmm_mem_layout_t * layout, addr_t start, addr_t end, addr_t host_addr) {
 277   layout_region_t * shared_region = os_hooks->malloc(sizeof(layout_region_t));
 278   int ret;
 279
 280   shared_region->next = NULL;
 281   shared_region->prev = NULL;
 282   shared_region->start = start;
 283   shared_region->end = end;
 284   shared_region->type = SHARED;
 285   shared_region->host_addr = host_addr;
 286
 287   ret = add_mem_range(layout, shared_region);
 288
 289   if (ret != 0) {
 290     VMMFree(shared_region);
 291   }
 292
 293   return ret;
 294 }
 295
 296 int add_unmapped_mem_range(vmm_mem_layout_t * layout, addr_t start, addr_t end) {
 297   layout_region_t * unmapped_region = os_hooks->malloc(sizeof(layout_region_t));
 298   int ret;
 299
 300   unmapped_region->next = NULL;
 301   unmapped_region->prev = NULL;
 302   unmapped_region->start = start;
 303   unmapped_region->end = end;
 304   unmapped_region->type = UNMAPPED;
 305   unmapped_region->host_addr = 0;
 306
 307   ret = add_mem_range(layout, unmapped_region);
 308
 309   if (ret != 0) {
 310     VMMFree(unmapped_region);
 311   }
 312
 313   return ret;
 314 }
 315
 316 int add_guest_mem_range(vmm_mem_layout_t * layout, addr_t start, addr_t end) {
 317   layout_region_t * guest_region = os_hooks->malloc(sizeof(layout_region_t));
 318   int ret;
 319
 320   guest_region->next = NULL;
 321   guest_region->prev = NULL;
 322   guest_region->start = start;
 323   guest_region->end = end;
 324   guest_region->type = GUEST;
 325   guest_region->host_addr = 0;
 326
 327   ret = add_mem_range(layout, guest_region);
 328
 329   if (ret != 0) {
 330     VMMFree(guest_region);
 331   }
 332
 333   return ret;
 334 }
 335
 336
 337
 338 /* Returns the page address of page number 'index' in the memory list
 339  * If index is out of bounds... returns -1 (an invalid page address)
 340  */
 341 addr_t get_mem_layout_addr(vmm_mem_layout_t * layout, uint_t index) {
 342   layout_region_t * reg = layout->head;
 343   uint_t i = index;
 344
 345   // Memory List overrun
 346   if (index > layout->num_pages - 1) {
 347     return -1;
 348   }
 349
 350   while (i >= 0) {
 351     if (!reg) {
 352       return -1;
 353     }
 354
 355     int num_reg_pages = reg->end - reg->start;
 356
 357     if (num_reg_pages <= index) {
 358       i -= num_reg_pages;
 359       reg = reg->next;
 360     } else {
 361       return reg->start + (i * PAGE_SIZE);
 362     }
 363   }
 364
 365   return -1;
 366 }
 367
 368 layout_region_t * get_mem_layout_region(vmm_mem_layout_t * layout, addr_t addr) {
 369   layout_region_t * tmp_reg = layout->head;
 370
 371
 372   while (tmp_reg) {
 373     if ((tmp_reg->start <= addr) && (tmp_reg->end > addr)) {
 374       return tmp_reg;
 375     } else if (tmp_reg->start > addr) {
 376       return NULL;
 377     } else {
 378       tmp_reg = tmp_reg->next;
 379     }
 380   }
 381
 382   return NULL;
 383 }
 384
 385
 386
 387
 388 void print_mem_list(vmm_mem_list_t * list) {
 389   mem_region_t * cur = list->head;
 390   int i = 0;
 391
 392   PrintDebug("Memory Region List (regions: %d) (pages: %d)\n", list->num_regions, list->num_pages);
 393
 394   while (cur) {
 395     PrintDebug("%d: 0x%x - 0x%x\n", i, cur->addr, cur->addr + (cur->num_pages * PAGE_SIZE) - 1);
 396     cur = cur->next;
 397     i++;
 398   }
 399   PrintDebug("\n");
 400 }
 401
 402
 403
 404 void print_mem_layout(vmm_mem_layout_t * layout) {
 405   layout_region_t * cur = layout->head;
 406   int i = 0;
 407
 408   PrintDebug("Memory Layout (regions: %d) (pages: %d)\n", layout->num_regions, layout->num_pages);
 409
 410   while (cur) {
 411     PrintDebug("%d: 0x%x - 0x%x\n", i, cur->start, cur->end -1);
 412     cur = cur->next;
 413     i++;
 414   }
 415   PrintDebug("\n");
 416 }
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428 #ifdef VMM_MEM_TEST
 429
 430
 431 #include <stdlib.h>
 432 #include <stdio.h>
 433 #include <stdarg.h>
 434
 435
 436
 437
 438
 439 struct vmm_os_hooks * os_hooks;
 440
 441 void * TestMalloc(uint_t size) {
 442   return malloc(size);
 443 }
 444
 445 void * TestAllocatePages(int size) {
 446   return malloc(4096 * size);
 447 }
 448
 449
 450 void TestPrint(const char * fmt, ...) {
 451   va_list args;
 452
 453   va_start(args, fmt);
 454   vprintf(fmt, args);
 455   va_end(args);
 456 }
 457
 458 int mem_list_add_test_1(  vmm_mem_list_t * list) {
 459
 460   uint_t offset = 0;
 461
 462   PrintDebug("\n\nTesting Memory List\n");
 463
 464   init_mem_list(list);
 465
 466   offset = PAGE_SIZE * 6;
 467   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 10));
 468   add_mem_list_pages(list, offset, 10);
 469   print_mem_list(list);
 470
 471
 472   offset = 0;
 473   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + PAGE_SIZE * 4);
 474   add_mem_list_pages(list, offset, 4);
 475   print_mem_list(list);
 476
 477   offset = PAGE_SIZE * 20;
 478   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
 479   add_mem_list_pages(list, offset, 1);
 480   print_mem_list(list);
 481
 482   offset = PAGE_SIZE * 21;
 483   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 3));
 484   add_mem_list_pages(list, offset, 3);
 485   print_mem_list(list);
 486
 487
 488   offset = PAGE_SIZE * 10;
 489   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 30));
 490   add_mem_list_pages(list, offset, 30);
 491   print_mem_list(list);
 492
 493
 494   offset = PAGE_SIZE * 5;
 495   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
 496   add_mem_list_pages(list, offset, 1);
 497   print_mem_list(list);
 498
 499
 500
 501   return 0;
 502 }
 503
 504
 505 int mem_layout_add_test_1(vmm_mem_layout_t *layout) {
 506
 507
 508   uint_t start = 0;
 509   uint_t end = 0;
 510
 511   PrintDebug("\n\nTesting Memory Layout\n");
 512
 513   init_mem_layout(layout);
 514
 515   start = 0x6000;
 516   end = 0x10000;;
 517   PrintDebug("Adding 0x%x - 0x%x\n", start, end);
 518   add_guest_mem_range(layout, start, end);
 519   print_mem_layout(layout);
 520
 521
 522   start = 0x1000;
 523   end = 0x3000;
 524   PrintDebug("Adding 0x%x - 0x%x\n", start, end);
 525   add_guest_mem_range(layout, start, end);
 526   print_mem_layout(layout);
 527
 528   start = 0x2000;
 529   end = 0x6000;
 530   PrintDebug("Adding 0x%x - 0x%x\n", start, end);
 531   add_guest_mem_range(layout, start, end);
 532   print_mem_layout(layout);
 533
 534   start = 0x4000;
 535   end = 0x5000;
 536   PrintDebug("Adding 0x%x - 0x%x\n", start, end);
 537   add_guest_mem_range(layout, start, end);
 538   print_mem_layout(layout);
 539
 540
 541   start = 0x5000;
 542   end = 0x7000;
 543   PrintDebug("Adding 0x%x - 0x%x\n", start, end);
 544   add_guest_mem_range(layout, start, end);
 545   print_mem_layout(layout);
 546
 547
 548
 549
 550   return 0;
 551 }
 552
 553
 554
 555 int main(int argc, char ** argv) {
 556   struct vmm_os_hooks dummy_hooks;
 557   os_hooks = &dummy_hooks;
 558
 559   vmm_mem_layout_t layout;
 560   vmm_mem_list_t list;
 561
 562   os_hooks->malloc = &TestMalloc;
 563   os_hooks->free = &free;
 564   os_hooks->print_debug = &TestPrint;
 565   os_hooks->allocate_pages = &TestAllocatePages;
 566
 567
 568
 569   printf("mem_list_add_test_1: %d\n", mem_list_add_test_1(&list));
 570   printf("layout_add_test_1: %d\n", mem_layout_add_test_1(&layout));
 571
 572   return 0;
 573 }
 574 #endif
 575
 576
 577
 578
 579
 580