1 #include <geekos/vmm_mem.h>
2 #include <geekos/vmm.h>
3 #include <geekos/vmm_util.h>
5 extern struct vmm_os_hooks * os_hooks;
8 void init_mem_list(vmm_mem_list_t * list) {
10 list->long_mode = false;
12 list->num_regions = 0;
17 void free_mem_list(vmm_mem_list_t * list) {
18 mem_region_t * cursor = list->head;
19 mem_region_t * tmp = NULL;
23 cursor = cursor->next;
30 /*** FOR THE LOVE OF GOD WRITE SOME UNIT TESTS FOR THIS THING ***/
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
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
40 // JRL: This is pretty hairy...
41 int add_mem_list_pages(vmm_mem_list_t * list, addr_t addr, uint_t num_pages) {
43 uint_t num_new_pages = num_pages;
44 addr_t new_end = addr + (num_pages * PAGE_SIZE) - 1;
46 mem_region_t * cursor = get_mem_list_cursor(list, addr);
49 // PrintDebug("Adding: 0x%x - 0x%x\n", addr, num_pages * PAGE_SIZE);
52 // Make a new region at the head of the list
54 cursor = os_hooks->malloc(sizeof(mem_region_t));
58 cursor->num_pages = num_pages;
60 cursor->next = list->head;
64 cursor->next->prev = cursor;
69 addr_t cursor_end = cursor->addr + (cursor->num_pages * PAGE_SIZE) - 1;
71 if (addr > cursor_end + 1) {
72 // address falls after cursor region
74 mem_region_t * new_region = os_hooks->malloc(sizeof(mem_region_t));
76 new_region->prev = cursor;
77 new_region->next = cursor->next;
80 cursor->next->prev = new_region;
82 cursor->next = new_region;
84 new_region->addr = addr;
85 new_region->num_pages = num_pages;
90 } else if ((addr >= cursor->addr) &&
91 (addr <= cursor_end + 1)) {
92 // address falls inside the cursor region
95 // The region has already been added
96 if (new_end <= cursor_end) {
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;
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;
113 cursor->next = overlap->next;
115 overlap->next->prev = cursor;
118 if (overlap_end > new_end) {
119 uint_t extension = (overlap_end - new_end) / PAGE_SIZE;
121 cursor->num_pages += extension;
122 num_new_pages -= (overlap->num_pages - extension);
124 num_new_pages -= overlap->num_pages;
133 list->num_pages += num_new_pages;
139 /* this function returns a pointer to the location in the memory list that
140 * corresponds to addr.
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
147 mem_region_t * get_mem_list_cursor(vmm_mem_list_t * list, addr_t addr) {
148 mem_region_t * prev_region = list->head;
150 while (prev_region != NULL) {
151 if ( (addr >= prev_region->addr) &&
152 (addr < (prev_region->addr + (prev_region->num_pages * PAGE_SIZE) - 1)) ) {
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;
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)
174 addr_t get_mem_list_addr(vmm_mem_list_t * list, uint_t index) {
175 mem_region_t * reg = list->head;
178 // Memory List overrun
179 if (index > list->num_pages - 1) {
184 if (reg->num_pages <= index) {
188 return reg->addr + (i * PAGE_SIZE);
196 void init_mem_layout(vmm_mem_layout_t * layout) {
197 layout->num_pages = 0;
198 layout->num_regions = 0;
204 void free_mem_layout(vmm_mem_layout_t * layout) {
205 layout_region_t * cursor = layout->head;
206 layout_region_t * tmp = NULL;
210 cursor = cursor->next;
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
223 int add_mem_range(vmm_mem_layout_t * layout, layout_region_t * region) {
224 layout_region_t * cursor = layout->head;
226 if ((!cursor) || (cursor->start >= region->end)) {
228 region->next = cursor;
229 layout->num_pages += (region->end - region->start) / PAGE_SIZE;
230 layout->num_regions++;
231 layout->head = region;
237 // Check if it overlaps with the current cursor
238 if ((cursor->end > region->start) && (cursor->start < region->start)) {
239 // overlaps not allowed
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;
250 } else if (cursor->next->start >= region->end) {
252 region->next = cursor->next;
253 region->prev = cursor;
255 cursor->next->prev = region;
256 cursor->next = region;
258 layout->num_regions++;
259 layout->num_pages += (region->end - region->start) / PAGE_SIZE;
262 } else if (cursor->next->end < region->start) {
263 cursor = cursor->next;
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));
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;
287 ret = add_mem_range(layout, shared_region);
290 VMMFree(shared_region);
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));
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;
307 ret = add_mem_range(layout, unmapped_region);
310 VMMFree(unmapped_region);
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));
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;
327 ret = add_mem_range(layout, guest_region);
330 VMMFree(guest_region);
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)
341 addr_t get_mem_layout_addr(vmm_mem_layout_t * layout, uint_t index) {
342 layout_region_t * reg = layout->head;
345 // Memory List overrun
346 if (index > layout->num_pages - 1) {
355 int num_reg_pages = reg->end - reg->start;
357 if (num_reg_pages <= index) {
361 return reg->start + (i * PAGE_SIZE);
368 layout_region_t * get_mem_layout_region(vmm_mem_layout_t * layout, addr_t addr) {
369 layout_region_t * tmp_reg = layout->head;
373 if ((tmp_reg->start <= addr) && (tmp_reg->end > addr)) {
375 } else if (tmp_reg->start > addr) {
378 tmp_reg = tmp_reg->next;
388 void print_mem_list(vmm_mem_list_t * list) {
389 mem_region_t * cur = list->head;
392 PrintDebug("Memory Region List (regions: %d) (pages: %d)\n", list->num_regions, list->num_pages);
395 PrintDebug("%d: 0x%x - 0x%x\n", i, cur->addr, cur->addr + (cur->num_pages * PAGE_SIZE) - 1);
404 void print_mem_layout(vmm_mem_layout_t * layout) {
405 layout_region_t * cur = layout->head;
408 PrintDebug("Memory Layout (regions: %d) (pages: %d)\n", layout->num_regions, layout->num_pages);
411 PrintDebug("%d: 0x%x - 0x%x\n", i, cur->start, cur->end -1);
439 struct vmm_os_hooks * os_hooks;
441 void * TestMalloc(uint_t size) {
445 void * TestAllocatePages(int size) {
446 return malloc(4096 * size);
450 void TestPrint(const char * fmt, ...) {
458 int mem_list_add_test_1( vmm_mem_list_t * list) {
462 PrintDebug("\n\nTesting Memory List\n");
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);
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);
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);
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);
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);
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);
505 int mem_layout_add_test_1(vmm_mem_layout_t *layout) {
511 PrintDebug("\n\nTesting Memory Layout\n");
513 init_mem_layout(layout);
517 PrintDebug("Adding 0x%x - 0x%x\n", start, end);
518 add_guest_mem_range(layout, start, end);
519 print_mem_layout(layout);
524 PrintDebug("Adding 0x%x - 0x%x\n", start, end);
525 add_guest_mem_range(layout, start, end);
526 print_mem_layout(layout);
530 PrintDebug("Adding 0x%x - 0x%x\n", start, end);
531 add_guest_mem_range(layout, start, end);
532 print_mem_layout(layout);
536 PrintDebug("Adding 0x%x - 0x%x\n", start, end);
537 add_guest_mem_range(layout, start, end);
538 print_mem_layout(layout);
543 PrintDebug("Adding 0x%x - 0x%x\n", start, end);
544 add_guest_mem_range(layout, start, end);
545 print_mem_layout(layout);
555 int main(int argc, char ** argv) {
556 struct vmm_os_hooks dummy_hooks;
557 os_hooks = &dummy_hooks;
559 vmm_mem_layout_t layout;
562 os_hooks->malloc = &TestMalloc;
563 os_hooks->free = &free;
564 os_hooks->print_debug = &TestPrint;
565 os_hooks->allocate_pages = &TestAllocatePages;
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));