76270991fb9119fe40989ab0cbedaf3d29f42c0a
[viridis.git] / mm / page_alloc.c
1 /* vim: set ts=4 sw=4 sts=4 et : */
2
3 /* Physical and virtual page allocator */
4
5 /* API:
6  *
7  * page_alloc_init() - done before SMP, locking unnecessary
8  *
9  * Physical page allocator (handles locking):
10  *
11  * page_alloc_phys(u32 order);
12  * page_alloc_free_phys(u64 address);
13  *
14  * Virtual page allocator:
15  *
16  * page_alloc(u32 order);
17  * page_alloc_free(void *address);
18  */
19
20 #include <kernel.h>
21 #include <domain.h>
22 #include <vsalloc.h>
23 #include <map.h>
24
25 #include <asm/spinlock.h>
26
27 struct page_block {
28     u64 address;
29     struct page_block *next;
30 };
31
32 u64 total_mem;
33
34 /* MAX_ORDER is the order of the largest block of memory that we track. Linux uses
35  * 11 for 8M chunks which seems like a good default size as it's large enough to
36  * accomodate even the largest allocation.
37  *
38  *  0 - 4k
39  *  1 - 8k
40  *  2 - 16k
41  *  3 - 32k
42  *  4 - 64k
43  *  5 - 128k
44  *  6 - 256k
45  *  7 - 512k
46  *  8 - 1M
47  *  9 - 2M
48  * 10 - 4M
49  * 11 - 8M
50  */
51
52 #define MAX_ORDER 11
53
54 struct page_block *free_pages[MAX_ORDER + 1] = { 0 };
55 struct page_block *used_pages[MAX_ORDER + 1] = { 0 };
56
57 struct page_block *unused_page_blocks = NULL;
58
59 DEFINE_SPINLOCK(page_alloc_lock) = SPINLOCK_UNLOCKED;
60
61 static inline void __setprev(struct page_block **head, struct page_block *prev,
62                              struct page_block *next)
63 {
64     if (prev)
65         prev->next = next;
66     else
67         *head = next;
68 }
69
70 static void __page_list_add(struct page_block **head, struct page_block *new)
71 {
72     new->next = *head;
73     *head = new;
74 }
75
76 static struct page_block *__pop_unused_page_block(void)
77 {
78     struct page_block *ret = unused_page_blocks;
79
80     if (ret != NULL) {
81         unused_page_blocks = ret->next;
82         ret->next = NULL;
83     }
84
85     return ret;
86 }
87
88 static void __push_unused_page_block(struct page_block *block)
89 {
90     block->next = unused_page_blocks;
91     unused_page_blocks = block;
92 }
93
94 /* Similar to __page_list_add, except it will actual perform the merge */
95
96 static void __free_phys(struct page_block *phys, u32 order)
97 {
98     struct page_block *cur, *prev;
99     u64 buddy_address;
100     u32 merge;
101
102     phys->next = NULL;
103
104     if (free_pages[order] == NULL) {
105         free_pages[order] = phys;
106         return;
107     }
108
109     /* For orders under MAX_ORDER, attempt to find buddies, and merge them as
110      * up as far as possible.*/
111
112     for (order = order; order < MAX_ORDER; order++) {
113         buddy_address = (phys->address ^ (1 << (order + PAGE_SHIFT)));
114
115         prev = NULL;
116         merge = 0;
117
118         for (cur = free_pages[order]; cur; prev = cur, cur = cur->next) {
119             if (cur->address != buddy_address)
120                 continue;
121
122             /* Patch the buddy out of the list */
123             __setprev(&free_pages[order], prev, cur->next);
124
125             /* If buddy's address is smaller, it has the right address
126              * of the combined block, so move it over before releasing
127              * the buddy
128              */
129
130             if (cur->address < phys->address)
131                 phys->address = cur->address;
132
133             __push_unused_page_block(cur);
134
135             /* Since we merged, we want to attempt to merge up another order */
136             merge = 1;
137             break;
138         }
139
140         /* If merge is set, we need to advance to the next highest order
141          * to attempt to integrate phys into it.
142          */
143         if (merge)
144             continue;
145
146         /* If merge is unset, it means that we didn't find a buddy, but we
147          * made it to the end of the order list without finding a greater
148          * page block address, so just tack it on.
149          */
150
151         __setprev(&free_pages[order], prev, phys);
152
153         return;
154     }
155
156     /* If we get here, it means that we're at MAX_ORDER, no merging
157      * is possible, so just insert it with __page_list_add
158      */
159
160     __page_list_add(&free_pages[order], phys);
161 }
162
163 /* Get a physical address of a block of (1 << order) pages
164  * 
165  * returns 0 if invalid (no mem / order too big)
166  */
167
168 u64 page_alloc_phys(u32 order)
169 {
170     struct page_block *new;
171     u64 end, left_over_pages, pages;
172     u64 ret = 0;
173     int i, j;
174
175     if (order > MAX_ORDER)
176         return 0;
177
178     spinlock_lock(&page_alloc_lock);
179
180     for (i = order; i <= MAX_ORDER; i++) {
181         if (free_pages[i] == NULL)
182             continue;
183
184         new = free_pages[i];
185         ret = new->address;
186         free_pages[i] = new->next;
187
188         __page_list_add(&used_pages[order], new);
189
190         /* If it's just the right size, we're done */
191
192         if (i == order)
193             goto done;
194
195         /* Otherwise, we need to split the block up */
196
197         /* Example, 1M order, being fulfilled by an 8M block The 8M block needs
198          * to be broken in 1M, 1M, 2M, 4M blocks.
199          */
200
201         left_over_pages = (1 << i) - (1 << order);
202         end = ret + (1 << (i + PAGE_SHIFT));
203
204         for (j = i - 1; j >= 0; j--) {
205             pages = (1 << j);
206             while (left_over_pages >= pages) {
207                 new = __pop_unused_page_block();
208                 new->address = end - (pages << PAGE_SHIFT);
209                 end = new->address;
210                 __free_phys(new, j);
211
212                 left_over_pages -= pages;
213             }
214         }
215
216         break;
217     }
218
219  done:
220     spinlock_unlock(&page_alloc_lock);
221
222     return ret;
223 }
224
225 /* Counterpart to page_alloc_phys, unlike __free_phys, it will search for its
226  * record in used_pages first, returns -EINVAL or the order of the freed
227  * allocation
228  */
229
230 s32 page_alloc_free_phys(u64 phys)
231 {
232     struct page_block *cur, *prev;
233     s32 ret = -EINVAL;
234     int i;
235
236     spinlock_lock(&page_alloc_lock);
237
238     for (i = 0; i < MAX_ORDER; i++) {
239         prev = NULL;
240         for (cur = used_pages[i]; cur; prev = cur, cur = cur->next) {
241             if (cur->address == phys) {
242                 __setprev(&used_pages[i], prev, cur->next);
243                 __free_phys(cur, i);
244                 ret = i;
245                 goto done;
246             }
247         }
248     }
249
250  done:
251     spinlock_unlock(&page_alloc_lock);
252
253     return ret;
254 }
255
256 /* Allocate a page to a given virtual address. */
257 /* Expects virtual address to be pre-allocated as well. */
258
259 static void __reserve_region(u64 address, u64 pages);
260
261 void *page_alloc_to_virtual(u64 virtual, u32 order)
262 {
263     u64 physical, cur_page;
264     u64 end_virt = virtual + (1 << (order + PAGE_SHIFT));
265     u32 try_again;
266
267     do {
268         try_again = 0;
269         physical = page_alloc_phys(order);
270         if (physical == 0)
271             return NULL;
272
273         map_pages(virtual, physical, (1 << order));
274         cur_page = virtual;
275
276         while (cur_page < end_virt) {
277             if(__clear_page((void *) cur_page)) {
278                 unmap_pages(virtual, (1 << order));
279                 page_alloc_free_phys(physical);
280                 __reserve_region(cur_page, 1);
281
282                 try_again = 1;
283                 break;
284             }
285
286             cur_page += PAGE_SIZE;
287         }
288
289     } while (try_again);
290
291     return (void *)virtual;
292 }
293
294 s64 page_alloc_free_from_virtual(u64 virtual)
295 {
296     u64 phys = map_virt_to_phys(virtual);
297     s32 order;
298
299     if (phys) {
300         order = page_alloc_free_phys(phys);
301         if (order >= 0)
302             unmap_pages(virtual, 1 << order);
303         return order;
304     }
305
306     return -1;
307 }
308
309 void *page_alloc(u32 order)
310 {
311     void *virtual;
312     void *ret;
313
314     if (order > MAX_ORDER)
315         return NULL;
316
317     virtual = vsalloc("page heap", 0, 1 << order);
318
319     if (virtual == NULL)
320         return NULL;
321
322     ret = page_alloc_to_virtual((u64) virtual, order);
323
324     if (ret == NULL) {
325         vfree(virtual, 1 << order);
326         return NULL;
327     }
328
329     return ret;
330 }
331
332 void page_alloc_free(void *virtual)
333 {
334     s64 order = page_alloc_free_from_virtual((u64) virtual);
335     vfree(virtual, 1 << order);
336 }
337
338 /* vmalloc functions give finer grain control of the allocation size, but you
339  * have to keep track of the page count yourself, and the allocator can't
340  * guarantee it's physically contiguous.
341  */
342
343 void page_vmalloc_free(void *virtual, u32 pages)
344 {
345     s64 order;
346     u32 size;
347
348     while (pages) {
349         order = page_alloc_free_from_virtual((u64) virtual);
350         size = (1 << order);
351
352         pages -= size;
353         virtual = (void *)((u64) virtual + (size << PAGE_SHIFT));
354     }
355 }
356
357 static void *__vmalloc_to_virtual(void *virtual, u32 pages)
358 {
359     u32 allocd_pages = 0;
360     u32 size;
361     void *cur = virtual;
362     int i;
363
364     for (i = MAX_ORDER; pages; i--) {
365         size = (1 << i);
366         while (pages >= size) {
367             if (page_alloc_to_virtual((u64) cur, i) == NULL)
368                 goto undo;
369
370             cur = (void *)((u64) cur + (size << PAGE_SHIFT));
371             pages -= size;
372             allocd_pages += size;
373         }
374     }
375
376     return virtual;
377
378  undo:
379     page_vmalloc_free(virtual, allocd_pages);
380
381     return NULL;
382 }
383
384 void *page_vmalloc(u32 pages)
385 {
386     void *virtual;
387
388     virtual = vsalloc("page vmalloc", 0, pages);
389
390     if (virtual == NULL)
391         return NULL;
392
393     return __vmalloc_to_virtual(virtual, pages);
394 }
395
396 void *page_vrealloc(void *virtual, u32 cur_pages, u32 want_pages)
397 {
398     void *new_alloc;
399     u64 phys, cur;
400     int i = 0;
401
402     if (want_pages < cur_pages)
403         return NULL;
404
405     new_alloc = vsalloc("page vrealloc", 0, want_pages);
406
407     if (!new_alloc)
408         return NULL;
409
410     /* Remap our old physical pages into place, zero copy */
411     if (virtual) {
412         cur = (u64) new_alloc;
413         for (i = 0; i < cur_pages; i++) {
414             phys = map_virt_to_phys((u64) virtual);
415
416             map_page(cur, phys);
417
418             cur += PAGE_SIZE;
419             virtual = (void *) (((u64) virtual) + PAGE_SIZE);
420         }
421     }
422
423     /* Attempt to fill the rest of the new space with new mem. */
424     if (__vmalloc_to_virtual((void *) cur, want_pages - i) == NULL)
425         goto undo;
426
427     return new_alloc;
428
429  undo:
430     for (i = i - 1; i >= 0; i--) {
431         virtual = (void *) (((u64) virtual) - PAGE_SIZE);
432         cur -= PAGE_SIZE;
433
434         phys = map_virt_to_phys(cur);
435         unmap_page(cur);
436         map_page((u64) virtual, phys);
437     }
438
439     return NULL;
440 }
441
442 /* INIT STUFF BEYOND THIS POINT */
443 /* The rest of this file is init for the allocators */
444
445 /* __init_free_region will place a number of __page_block structs on free_pages
446  * without doing any form of checking, and without removing from used_pages.
447  */
448
449 static void __init_free_region(u64 address, u64 pages)
450 {
451     struct page_block *new;
452     s32 order;
453     u32 size, mask;
454
455     while (pages)
456     {
457         /* Search for the biggest order that the address is aligned to and that
458          * isn't larger than the region
459          */
460
461         for (order = MAX_ORDER; order >= 0; order--) {
462             size = 1 << order;
463             mask = ((size << PAGE_SHIFT) - 1);
464             if ((address & mask)||(size > pages)) {
465                 if (order == 0) {
466                     address = PAGE_ALIGN_UP(address);
467                     pages--;
468                 } else
469                     continue;
470             } else {
471                 new = __pop_unused_page_block();
472
473                 new->address = address;
474                 new->next = NULL;
475                 __page_list_add(&free_pages[order], new);
476
477                 address += (size << PAGE_SHIFT);
478                 pages -= size;
479                 break;
480             }
481         }
482     }
483 }
484
485 /* After unused_page_blocks has been properly converted to a virtual pointer,
486  * initialize the structs to form a linked list just like an order of free or
487  * used pages so we can allocate and free them
488  */
489
490 static void __init_unused_page_blocks(u64 max_page_blocks)
491 {
492     int i;
493
494     for (i = 0; i < (max_page_blocks - 1); i++)
495         unused_page_blocks[i].next = &unused_page_blocks[i + 1];
496     unused_page_blocks[i].next = NULL;
497 }
498
499 /* Determine how many extra pages of page structures we'll need for an
500  * allocation of num_pages @ start, assuming it's entirely unpaged.
501  *
502  * The important thing here is that it's address sensitive, so a two page
503  * allocation could return anywhere between 3 and 6 overhead pages depending on
504  * how many page structure borders are being crossed.
505  */
506
507 static u32 __overhead_pages(u64 start, u64 num_pages)
508 {
509     u64 pdp_pages, pd_pages, pt_pages;
510     u64 end = start + (num_pages * PAGE_SIZE);
511
512     pdp_pages = (PML4E(end) - PML4E(start)) + 1;
513
514     if (pdp_pages > 1) {
515         pd_pages = (512 - PDPE(start)) + PDPE(end);
516         pd_pages += (pdp_pages - 2) * 512;
517     } else
518         pd_pages = (PDPE(end) - PDPE(start)) + 1;
519
520     if (pd_pages > 1) {
521         pt_pages = (512 - PDE(start)) + PDE(end);
522         pt_pages += (pd_pages - 2) * 512;
523     } else
524         pt_pages = (PDE(end) - PDE(start)) + 1;
525
526     return (pdp_pages + pd_pages + pt_pages);
527 }
528
529 /* Remove pages from the free list, without adding them to the used list, so
530  * they are unfreeable, if we're going to use these pages, either reserved
531  * memory from GRUB or integral kernel structures, it's not going to be through
532  * the page allocator.
533  */
534
535 static void __reserve_region(u64 address, u64 pages)
536 {
537     struct page_block *cur = NULL;
538     struct page_block *prev;
539     u64 last_pages;
540
541     if (PAGE_ALIGN_OFF(address))
542         pages++;
543
544     address = PAGE_ALIGN(address);
545
546     int order, size_pages, size, num_free;
547
548     while (pages > 0) {
549         last_pages = pages;
550         for (order = MAX_ORDER; order >= 0; order--) {
551             size_pages = 1 << order;
552             size = size_pages << PAGE_SHIFT;
553
554             /* First, find the free block that contains address. */
555
556             prev = NULL;
557             for (cur = free_pages[order]; cur; prev = cur, cur = cur->next) {
558                 if (cur->address <= address && (cur->address + size) > address)
559                     break;
560             }
561
562             /* Didn't find relevant chunk */
563             if (!cur)
564                 continue;
565
566             /* Okay, we've found the block, let's break it up */
567
568             /* First, patch it out of the current order list */
569
570             __setprev(&free_pages[order], prev, cur->next);
571             cur->next = NULL;
572
573             /* If our address is somewhere inside the block, free
574              * all of the memory before it and shrink sizes.
575              */
576
577             if (address != cur->address) {
578                 num_free = (address - cur->address) >> PAGE_SHIFT;
579                 __init_free_region(cur->address, num_free);
580
581                 size_pages -= num_free;
582                 size = (size_pages << PAGE_SHIFT);
583             }
584
585             /* If the remaining block is bigger or equal to what we're freeing,
586              * then just discard this page_block and start again with the
587              * remaining free block */
588
589             if (pages >= size_pages) {
590                 __push_unused_page_block(cur);
591                 pages -= size_pages;
592                 address += size;
593                 break;
594             }
595
596             /* Otherwise, we know we have pages at the end to free as well */
597
598             __init_free_region(address + (pages << PAGE_SHIFT),
599                                size_pages - pages);
600
601             /* Finally, discard cur */
602
603             __push_unused_page_block(cur);
604             return;
605         }
606
607         /* If we searched everywhere for this address but didn't find it,
608          * then go ahead and advance. This can happen when you have overlapping
609          * reserves. For example, trying to reserve GRUB info that's already
610          * been reserved in the mmap.
611          */
612
613         if (last_pages == pages) {
614             pages--;
615             address += PAGE_SIZE;
616         }
617     }
618 }
619
620 int page_alloc_init(struct boot_header *header)
621 {
622     struct plat_memmap cur = { 0 };
623
624     u64 max_phys_address, max_pages, page_block_pages;
625     u64 base, length;
626     u64 alloc_address, alloc_size, free_pages_address;
627     u64 virtual, physical;
628
629     u64 kernel_size, stack_size;
630
631     u32 overhead, i;
632
633     /* For some reason the grub memmap size field doesn't include
634      * the size field itself, so we add 4.
635      */
636
637     max_phys_address = 0;
638     total_mem = 0;
639
640     do {
641         platform->parse_memmap(platform, &cur);
642         if (cur.type == PLAT_MEMMAP_FREE)
643             max_phys_address = cur.end;
644         total_mem += (cur.end - cur.start);
645
646     } while(cur.next);
647
648     /* max_page_blocks describes how many page_block structs we'd have if the
649      * entirety of physical memory was allocated in 4k chunks (maximum
650      * fragmentation).
651      */
652
653     max_pages = max_phys_address >> PAGE_SHIFT;
654
655     /* page_block_pages describes how many pages we need to reserve if we are
656      * going to store max_page_blocks.
657      */
658
659     page_block_pages =
660         ((max_pages * sizeof(struct page_block)) >> PAGE_SHIFT) + 1;
661
662     /* Search the mmap for a chunk of contiguous memory that we can use */
663
664     /* Because there should be a large chunk of free memory >1M this should
665      * never fail in practice, but if it does, we're fucked
666      */
667
668     alloc_address = MAXLONG;
669     stack_size = STACK_PAGES << PAGE_SHIFT;
670
671     do {
672         platform->parse_memmap(platform, &cur);
673
674         /* We don't care about reserved memory */
675         if (cur.type != PLAT_MEMMAP_FREE)
676             continue;
677
678         /* If this is the block our binary is in, then adjust its base and
679          * length to avoid the binary and the page structures we allocated
680          * immediately afterward.
681          */
682
683         /* Assume that we are in a contiguous block of memory that started
684          * before or at KERNEL_START and ended after our page structures. If
685          * this isn't true then we shouldn't have gotten this far.
686          */
687
688         if (((cur.start <= KERNEL_START) && (cur.end >= KERNEL_START)) ||
689            ((cur.start <= header->end_structures) &&
690                  (cur.end >= header->end_structures)))
691             base = header->end_structures;
692         else if (cur.start <= STACK_PAGES_PHYS &&
693                    (cur.end >= (STACK_PAGES_PHYS + stack_size)))
694             base = STACK_PAGES_PHYS + stack_size;
695         else
696             base = cur.start;
697
698         length = (cur.end - base);
699
700         /* Round up to page size, adjust length accordingly */
701         length -= PAGE_ALIGN_OFF(base);
702         base = PAGE_ALIGN(base);
703
704         /* If we allocated at this address, find out how many page structure
705          * pages we'd need to add to get it all allocated*/
706
707         overhead = __overhead_pages(base, page_block_pages);
708         alloc_size = ((page_block_pages + overhead) * PAGE_SIZE);
709
710         /* Too short, skip to the next block */
711         if (length < alloc_size)
712             continue;
713
714         /* We're page-aligned, non clobbering and large enough, done! */
715         alloc_address = base;
716         break;
717
718     } while (cur.next);
719
720     /* We couldn't find a large enough block, we're fucked. */
721
722     if (alloc_address == MAXLONG)
723         return -1;
724
725     /* big_alloc is now a physical pointer to a contiguous piece of
726      * memory that can hold enough page_block structs to control all of our
727      * pages at maximum fragmentation, as well as the page structures needed to
728      * map them
729      *
730      * We also know we need `overhead` pages of structures (at most).
731      */
732
733     unused_page_blocks =
734         (struct page_block *)(alloc_address + (overhead << PAGE_SHIFT));
735
736     free_pages_address = alloc_address;
737
738     physical = (u64) unused_page_blocks;
739     virtual = (VIRT_BASE | physical);
740
741     for (i = 0; i < page_block_pages; i++) {
742         map_page_early(virtual, physical, &free_pages_address);
743         __clear_page((u64 *) virtual);
744         physical += PAGE_SIZE;
745         virtual += PAGE_SIZE;
746     }
747
748     /* Convert to a virtual pointer */
749     unused_page_blocks =
750         (struct page_block *)(VIRT_BASE | ((long)unused_page_blocks));
751
752     __init_unused_page_blocks(max_pages);
753
754     test_page_alloc(max_pages);
755
756     /* Now put that reserved memory to use */
757     __init_free_region(0, max_pages);
758
759     /* Now iterate once more on the memmap and alloc all the unavailable pages */
760
761     do {
762         platform->parse_memmap(platform, &cur);
763         if (cur.type == PLAT_MEMMAP_FREE)
764             continue;
765
766         /* Partial pages are useless to us, so -expand- bad sections by
767          * page aligning base and rounding the length up to a multiple
768          * of page size
769          */
770
771         base = PAGE_ALIGN(cur.start);
772         length = PAGE_ALIGN_UP(cur.end) - base;
773
774         /* Mark the physical addresses as allocated */
775
776         __reserve_region(base, length >> PAGE_SHIFT);
777     } while (cur.next);
778
779     /* Stuff we should reserve, despite not being reserved in the map */
780     __reserve_region(EXTRA_RES_START, EXTRA_RES_PAGES);
781
782     /* Finally, mark our own pages as allocated */
783
784     kernel_size = (header->end_structures - KERNEL_START);
785     stack_size = (STACK_PAGES << PAGE_SHIFT);
786
787     __reserve_region(STACK_PAGES_PHYS, STACK_PAGES);
788     __reserve_region(REALMODE_PA, 1);
789     __reserve_region(KERNEL_START, kernel_size >> PAGE_SHIFT);
790     __reserve_region(alloc_address, alloc_size >> PAGE_SHIFT);
791
792     /* page_alloc_to_virtual has to be working before now */
793
794     /* potentially test domain code before we start relying on vsalloc */
795
796     test_domain();
797
798     vsalloc_init();
799
800     return 0;
801 }
802
803 #ifdef TEST_PAGE_ALLOC
804 static inline void test_orders(struct page_block **head, u64 * orders)
805 {
806     struct page_block *block;
807     int counter = 0;
808     int i = 0;
809
810     for (i = 0; i <= MAX_ORDER; i++) {
811         counter = 0;
812         for (block = head[i]; block; block = block->next)
813             counter++;
814
815         assert(counter == orders[i]);
816     }
817 }
818
819 static inline void test_order_index(struct page_block *block, u32 index,
820                                     u64 address, u32 nextnull)
821 {
822     int i;
823
824     for (i = 0; i < index; i++)
825         block = block->next;
826
827     assert(block->address == address);
828     assert(!nextnull != !block->next); /* logical XOR */
829 }
830
831 void test_page_alloc(u64 max_pages)
832 {
833     struct page_block *upb_bak = unused_page_blocks;
834     int i;
835
836     u64 free_orders[MAX_ORDER + 1] = { 0 };
837     u64 used_orders[MAX_ORDER + 1] = { 0 };
838
839     test_orders(free_pages, free_orders);
840     test_orders(used_pages, used_orders);
841
842     /* Alloc 1GB of memory */
843
844     __init_free_region(0, (1 * 1024 * 1024 * 1024) >> PAGE_SHIFT);
845
846     /* Should create 128 blocks of 8M */
847     /* No allocations, obviously */
848
849     free_orders[MAX_ORDER] = 128;
850
851     test_orders(free_pages, free_orders);
852     test_orders(used_pages, used_orders);
853
854     test_order_index(free_pages[MAX_ORDER], 0, 0, 0);
855     test_order_index(free_pages[MAX_ORDER], 1, 0x800000, 0);
856     test_order_index(free_pages[MAX_ORDER], 2, 0x1000000, 0);
857
858     /* Reserve 0 - 4M, should split 1 8M block in 2 4M */
859     /* reserve_region won't record it on used_pages */
860
861     __reserve_region(0, 0x400);
862
863     free_orders[MAX_ORDER] = 127;
864     free_orders[MAX_ORDER - 1] = 1;
865
866     test_orders(free_pages, free_orders);
867     test_orders(used_pages, used_orders);
868
869     test_order_index(free_pages[MAX_ORDER], 0, 0x800000, 0);
870     test_order_index(free_pages[MAX_ORDER], 1, 0x1000000, 0);
871     test_order_index(free_pages[MAX_ORDER - 1], 0, 0x400000, 1);
872
873     /* Reserve 12M - 13M, should split the 8M - 16M
874      * block into 1 more 4M, 1 1M, and 1 2M block */
875
876     __reserve_region(0xc00000, 0x100);
877
878     free_orders[MAX_ORDER] = 126;
879     free_orders[MAX_ORDER - 1] = 2;
880     free_orders[MAX_ORDER - 2] = 1;
881     free_orders[MAX_ORDER - 3] = 1;
882
883     test_orders(free_pages, free_orders);
884     test_orders(used_pages, used_orders);
885
886     test_order_index(free_pages[MAX_ORDER], 0, 0x1000000, 0);
887     test_order_index(free_pages[MAX_ORDER], 1, 0x1800000, 0);
888     test_order_index(free_pages[MAX_ORDER - 1], 0, 0x400000, 0);
889     test_order_index(free_pages[MAX_ORDER - 1], 1, 0x800000, 1);
890
891     /* Now using page_alloc_phys should return the first two already
892      * split blocks
893      */
894
895     assert(page_alloc_phys(MAX_ORDER - 1) == 0x400000);
896
897     assert(page_alloc_phys(MAX_ORDER - 1) == 0x800000);
898
899     free_orders[MAX_ORDER - 1] = 0;
900     used_orders[MAX_ORDER - 1] = 2;
901
902     test_orders(free_pages, free_orders);
903     test_orders(used_pages, used_orders);
904
905     /* A third 4M alloc should split an 8M block and return its
906      * lower address
907      */
908
909     assert(page_alloc_phys(MAX_ORDER - 1) == 0x1000000);
910
911     free_orders[MAX_ORDER] -= 1;
912     free_orders[MAX_ORDER - 1] = 1;
913
914     used_orders[MAX_ORDER - 1] = 3;
915
916     test_orders(free_pages, free_orders);
917     test_orders(used_pages, used_orders);
918
919     test_order_index(free_pages[MAX_ORDER], 0, 0x1800000, 0);
920     test_order_index(free_pages[MAX_ORDER - 1], 0, 0x1400000, 1);
921
922     /* Now a free should properly reconstitute the 8M block */
923
924     page_alloc_free_phys(0x1000000);
925
926     free_orders[MAX_ORDER] += 1;
927     free_orders[MAX_ORDER - 1] = 0;
928
929     used_orders[MAX_ORDER - 1] = 2;
930
931     test_orders(free_pages, free_orders);
932     test_orders(used_pages, used_orders);
933
934     test_order_index(free_pages[MAX_ORDER], 0, 0x1000000, 0);
935
936     /* We're done, now reset our structures */
937
938     unused_page_blocks = upb_bak;
939     __init_unused_page_blocks(max_pages);
940
941     for (i = 0; i <= MAX_ORDER; i++) {
942         free_pages[i] = NULL;
943         used_pages[i] = NULL;
944     }
945 }
946 #endif
947
948 #ifdef TEST_FULLMEM
949
950 /* The fullmem test is designed to stress the page allocator, vsalloc (domain
951  * allocator), and the objcache all to the point of memory exhaustion. This
952  * test is quite intensive and very slow so it shouldn't be enabled by default.
953  *
954  * I'd really like to be able to assert that the pre free/used page count is
955  * identical to post free/used page count, but we can't. The domain allocator
956  * will never free memory. It will only use a handful of pages, and it will
957  * reuse those pages, but it won't ever return them to the allocator.
958  *
959  * Ironically, in this test, most of those allocations are done via vfree()
960  * because where vsalloc() is able to combine a ton of page allocations into a
961  * single struct, when we free, that range is split up between the pages we're
962  * freeing and the pages that were handed out to the objcache that we're not
963  * freeing until the objcache_destroy call at the end.
964  *
965  * To ensure that this is a flat cost, instead of a memory leak, this test can
966  * be run twice. The second time, vsalloc() should be expanded as far as it
967  * needs right off the bat, and so pre and post numbers should be identical.
968  * Indeed, the second run outputs something like this:
969  *
970  * free_pages : 0x3fb5a -> 0x0 -> 0x3fb5a
971  *
972  * used_pages : 0x12 -> 0x3fb6c -> 0x12
973  *
974  * Which looks just right. We could solve this by making the domain allocator
975  * free unused memory, but that would possibly happen on alloc or free and be
976  * intensive enough (since we'd be searching multiple times and potentially
977  * shifting memory around) that I don't think that's worth it to save a page or
978  * two in the actual usecase where you're *not* allocating the entire world in
979  * a single context and the memory will be freed when the context is destroyed
980  * anyway.
981  */
982
983 #include <objcache.h>
984
985 DEFINE_OBJCACHE(fullmem_oc, u64);
986
987 static u64 __num_pages(struct page_block **head)
988 {
989     struct page_block *cur;
990     u64 ret = 0;
991     int i;
992
993     for(i = 0; i <= MAX_ORDER; i++) {
994         cur = head[i];
995         while (cur) {
996             ret += (1 << i);
997             cur = cur->next;
998         }
999     }
1000
1001     return ret;
1002 }
1003
1004 #define free_pages() __num_pages(free_pages)
1005 #define used_pages() __num_pages(used_pages)
1006
1007 void test_fullmem(void)
1008 {
1009     void *virt;
1010     u64 start_long = OVERHEAD_LONGS(&fullmem_oc);
1011     u64 objs_per_page = (OVERHEAD_BITS(&fullmem_oc) - OVERHEAD_OBJECTS(&fullmem_oc));
1012     u64 *got, *curpage;
1013
1014     u64 pre_free, mid_free, post_free;
1015     u64 pre_used, mid_used, post_used;
1016
1017     int i = 0, j = 0;
1018
1019     printk("Starting full memory test\n");
1020
1021     pre_free = free_pages();
1022     pre_used = used_pages();
1023
1024     while(1) {
1025         virt = page_alloc(0);
1026
1027         if (!virt)
1028             break;
1029
1030         got = objcache_get(&fullmem_oc);
1031
1032         if (!got) {
1033             page_alloc_free(virt);
1034             break;
1035         }
1036
1037         *got = (u64) virt;
1038
1039         if (i % 256 == 0) /* 256 pages per MB */
1040             printk("%d MB\n", i / 256);
1041
1042         i++;
1043     }
1044
1045     printk("Alloc'd all mem in %d page_alloc calls\n", i);
1046
1047     mid_free = free_pages();
1048     mid_used = used_pages();
1049
1050     curpage = (u64 *) fullmem_oc.start_page;
1051
1052     while(j < i) {
1053         virt = (void *) curpage[start_long + j % objs_per_page];
1054         page_alloc_free(virt);
1055
1056         j++;
1057
1058         if (j % objs_per_page == 0)
1059             curpage = (u64 *) curpage[start_long - 1];
1060     }
1061
1062     objcache_destroy(&fullmem_oc);
1063
1064     post_free = free_pages();
1065     post_used = used_pages();
1066
1067     printk("free_pages : 0x%lx -> 0x%lx -> 0x%lx\n", pre_free, mid_free, post_free);
1068     printk("used_pages : 0x%lx -> 0x%lx -> 0x%lx\n", pre_used, mid_used, post_used);
1069
1070     printk("Freed everything\n");
1071 }
1072 #endif