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 /* this function returns a pointer to the location in the layout list that
 220  * corresponds to addr.
 221  * Rules:
 222  *     IF addr is in a region, a ptr to that region is returned
 223  *     IF addr is not in a region, a ptr to the previous region is returned
 224  *     IF addr is before all regions, returns NULL
 225  *     IF list is empty, returns NULL
 226  */
 227 layout_region_t * get_layout_cursor(vmm_mem_layout_t * layout, addr_t addr) {
 228   layout_region_t * prev_region = layout->head;
 229
 230
 231   while (prev_region != NULL) {
 232     if ( (addr >= prev_region->addr) &&
 233          (addr < (prev_region->addr + (prev_region->num_pages * PAGE_SIZE))) ) {
 234       return prev_region;
 235     } else if (addr < prev_region->addr) {
 236       // If this region is the current head, then this should return NULL
 237       return prev_region->prev;
 238     } else if (addr >= (prev_region->addr + (prev_region->num_pages * PAGE_SIZE))) {
 239       if (prev_region->next) {
 240         prev_region = prev_region->next;
 241       } else {
 242         return prev_region;
 243       }
 244     }
 245   }
 246
 247   return prev_region;
 248 }
 249
 250
 251 /* This is slightly different semantically from the mem list, in that we don't allow overlaps
 252  * we could probably allow overlappig regions of the same type... but I'll let someone else deal with that
 253  */
 254 int add_mem_range(vmm_mem_layout_t * layout, layout_region_t * region) {
 255
 256   layout_region_t * cursor = get_layout_cursor(layout, region->addr);
 257
 258   if (cursor == NULL) {
 259     if (layout->head) {
 260       if (layout->head->addr < region->addr + (region->num_pages * PAGE_SIZE) - 1) {
 261         // overlaps not allowed
 262         return -1;
 263       }
 264       layout->head->prev = region;
 265     }
 266
 267     region->prev = NULL;
 268     region->next = layout->head;
 269     layout->head = region;
 270
 271     layout->num_regions++;
 272     layout->num_pages += region->num_pages;
 273   } else if ((region->addr >= cursor->addr) &&
 274              (region->addr <= cursor->addr + (cursor->num_pages * PAGE_SIZE) - 1)) {
 275     // overlaps not allowed
 276     return -1;
 277   } else if (region->addr > cursor->addr + (cursor->num_pages * PAGE_SIZE) - 1) {
 278     // add region to layout
 279     region->next = cursor->next;
 280     region->prev = cursor;
 281
 282     if (region->next) {
 283       region->next->prev = region;
 284     }
 285     cursor->next = region;
 286
 287     layout->num_regions++;
 288     layout->num_pages += region->num_pages;
 289   } else {
 290     return -1;
 291   }
 292
 293
 294   return 0;
 295 }
 296
 297
 298
 299
 300
 301 int add_shared_mem_range(vmm_mem_layout_t * layout, addr_t addr, uint_t num_pages, addr_t host_addr) {
 302   layout_region_t * shared_region = os_hooks->malloc(sizeof(layout_region_t));
 303   int ret;
 304
 305   shared_region->next = NULL;
 306   shared_region->prev = NULL;
 307   shared_region->addr = addr;
 308   shared_region->num_pages = num_pages;
 309   shared_region->type = SHARED;
 310   shared_region->host_addr = host_addr;
 311
 312   ret = add_mem_range(layout, shared_region);
 313
 314   if (ret != 0) {
 315     VMMFree(shared_region);
 316   }
 317
 318   return ret;
 319 }
 320
 321 int add_unmapped_mem_range(vmm_mem_layout_t * layout, addr_t addr, uint_t num_pages) {
 322   layout_region_t * unmapped_region = os_hooks->malloc(sizeof(layout_region_t));
 323   int ret;
 324
 325   unmapped_region->next = NULL;
 326   unmapped_region->prev = NULL;
 327   unmapped_region->addr = addr;
 328   unmapped_region->num_pages = num_pages;
 329   unmapped_region->type = UNMAPPED;
 330   unmapped_region->host_addr = 0;
 331
 332   ret = add_mem_range(layout, unmapped_region);
 333
 334   if (ret != 0) {
 335     VMMFree(unmapped_region);
 336   }
 337
 338   return ret;
 339 }
 340
 341 int add_guest_mem_range(vmm_mem_layout_t * layout, addr_t addr, uint_t num_pages) {
 342   layout_region_t * guest_region = os_hooks->malloc(sizeof(layout_region_t));
 343   int ret;
 344
 345   guest_region->next = NULL;
 346   guest_region->prev = NULL;
 347   guest_region->addr = addr;
 348   guest_region->num_pages = num_pages;
 349   guest_region->type = GUEST;
 350   guest_region->host_addr = 0;
 351
 352   ret = add_mem_range(layout, guest_region);
 353
 354   if (ret == 0) {
 355     layout->num_guest_pages += num_pages;
 356   } else {
 357     VMMFree(guest_region);
 358   }
 359
 360   return ret;
 361 }
 362
 363
 364
 365 /* Returns the page address of page number 'index' in the memory list
 366  * If index is out of bounds... returns -1 (an invalid page address)
 367  */
 368 addr_t get_mem_layout_addr(vmm_mem_layout_t * layout, uint_t index) {
 369   layout_region_t * reg = layout->head;
 370   uint_t i = index;
 371
 372   // Memory List overrun
 373   if (index > layout->num_pages - 1) {
 374     return -1;
 375   }
 376
 377   while (i >= 0) {
 378     if (!reg) {
 379       return -1;
 380     }
 381
 382     if (reg->num_pages <= index) {
 383       i -= reg->num_pages;
 384       reg = reg->next;
 385     } else {
 386       return reg->addr + (i * PAGE_SIZE);
 387     }
 388   }
 389
 390   return -1;
 391 }
 392
 393
 394
 395
 396 void print_mem_list(vmm_mem_list_t * list) {
 397   mem_region_t * cur = list->head;
 398   int i = 0;
 399
 400   PrintDebug("Memory Region List (regions: %d) (pages: %d)\n", list->num_regions, list->num_pages);
 401
 402   while (cur) {
 403     PrintDebug("%d: 0x%x - 0x%x\n", i, cur->addr, cur->addr + (cur->num_pages * PAGE_SIZE) - 1);
 404     cur = cur->next;
 405     i++;
 406   }
 407   PrintDebug("\n");
 408 }
 409
 410
 411
 412 void print_mem_layout(vmm_mem_layout_t * layout) {
 413   layout_region_t * cur = layout->head;
 414   int i = 0;
 415
 416   PrintDebug("Memory Layout (regions: %d) (pages: %d)\n", layout->num_regions, layout->num_pages);
 417
 418   while (cur) {
 419     PrintDebug("%d: 0x%x - 0x%x\n", i, cur->addr, cur->addr + (cur->num_pages * PAGE_SIZE) - 1);
 420     cur = cur->next;
 421     i++;
 422   }
 423   PrintDebug("\n");
 424 }
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437 #ifdef VMM_MEM_TEST
 438
 439
 440 #include <stdlib.h>
 441 #include <stdio.h>
 442 #include <stdarg.h>
 443
 444 #include <geekos/vmm_paging.h>
 445
 446
 447
 448 struct vmm_os_hooks * os_hooks;
 449
 450 void * TestMalloc(uint_t size) {
 451   return malloc(size);
 452 }
 453
 454 void * TestAllocatePages(int size) {
 455   return malloc(4096 * size);
 456 }
 457
 458
 459 void TestPrint(const char * fmt, ...) {
 460   va_list args;
 461
 462   va_start(args, fmt);
 463   vprintf(fmt, args);
 464   va_end(args);
 465 }
 466
 467 int mem_list_add_test_1(  vmm_mem_list_t * list) {
 468
 469   uint_t offset = 0;
 470
 471   PrintDebug("\n\nTesting Memory List\n");
 472
 473   init_mem_list(list);
 474
 475   offset = PAGE_SIZE * 6;
 476   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 10));
 477   add_mem_list_pages(list, offset, 10);
 478   print_mem_list(list);
 479
 480
 481   offset = 0;
 482   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + PAGE_SIZE * 4);
 483   add_mem_list_pages(list, offset, 4);
 484   print_mem_list(list);
 485
 486   offset = PAGE_SIZE * 20;
 487   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
 488   add_mem_list_pages(list, offset, 1);
 489   print_mem_list(list);
 490
 491   offset = PAGE_SIZE * 21;
 492   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 3));
 493   add_mem_list_pages(list, offset, 3);
 494   print_mem_list(list);
 495
 496
 497   offset = PAGE_SIZE * 10;
 498   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 30));
 499   add_mem_list_pages(list, offset, 30);
 500   print_mem_list(list);
 501
 502
 503   offset = PAGE_SIZE * 5;
 504   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
 505   add_mem_list_pages(list, offset, 1);
 506   print_mem_list(list);
 507
 508
 509
 510   return 0;
 511 }
 512
 513
 514 int mem_layout_add_test_1(vmm_mem_layout_t *layout) {
 515
 516   uint_t offset = 0;
 517
 518   PrintDebug("\n\nTesting Memory Layout\n");
 519
 520   init_mem_layout(layout);
 521
 522   offset = PAGE_SIZE * 6;
 523   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 10));
 524   add_guest_mem_range(layout, offset, 10);
 525   print_mem_layout(layout);
 526
 527
 528   offset = PAGE_SIZE * 20;
 529   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
 530   add_guest_mem_range(layout, offset, 1);
 531   print_mem_layout(layout);
 532
 533
 534   offset = PAGE_SIZE * 16;
 535   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + PAGE_SIZE * 4);
 536   add_guest_mem_range(layout, offset, 4);
 537   print_mem_layout(layout);
 538
 539
 540   offset = PAGE_SIZE * 10;
 541   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 30));
 542   add_guest_mem_range(layout, offset, 30);
 543   print_mem_layout(layout);
 544
 545
 546   offset = 0;
 547   PrintDebug("Adding 0x%x - 0x%x\n", offset, offset + (PAGE_SIZE * 1));
 548   add_guest_mem_range(layout, offset, 1);
 549   print_mem_layout(layout);
 550
 551
 552
 553
 554   return 0;
 555 }
 556
 557
 558
 559 int main(int argc, char ** argv) {
 560   struct vmm_os_hooks dummy_hooks;
 561   os_hooks = &dummy_hooks;
 562
 563   vmm_mem_layout_t layout;
 564   vmm_mem_list_t list;
 565
 566   os_hooks->malloc = &TestMalloc;
 567   os_hooks->free = &free;
 568   os_hooks->print_debug = &TestPrint;
 569   os_hooks->allocate_pages = &TestAllocatePages;
 570
 571
 572
 573   printf("mem_list_add_test_1: %d\n", mem_list_add_test_1(&list));
 574   printf("layout_add_test_1: %d\n", mem_layout_add_test_1(&layout));
 575
 576
 577   pde_t * pde = generate_guest_page_tables(&layout, &list);
 578   PrintDebugPageTables(pde);
 579
 580   return 0;
 581 }
 582 #endif
 583
 584
 585
 586
 587
 588