BXE: min->MIN, plus an spatch
[akaros.git] / kern / arch / x86 / page_alloc.c
1 /* Copyright (c) 2009 The Regents of the University  of California. 
2  * See the COPYRIGHT files at the top of this source tree for full 
3  * license information.
4  * 
5  * Barret Rhoden <brho@cs.berkeley.edu>
6  * Kevin Klues <klueska@cs.berkeley.edu> */
7
8 #ifdef __SHARC__
9 #pragma nosharc
10 #define SINIT(x) x
11 #endif
12
13 #include <sys/queue.h>
14 #include <page_alloc.h>
15 #include <pmap.h>
16 #include <kmalloc.h>
17 #include <multiboot.h>
18
19 spinlock_t colored_page_free_list_lock = SPINLOCK_INITIALIZER_IRQSAVE;
20
21 page_list_t LCKD(&colored_page_free_list_lock) * CT(llc_cache->num_colors) RO
22   colored_page_free_list = NULL;
23
24 static void page_alloc_bootstrap() {
25         // Allocate space for the array required to manage the free lists
26         size_t list_size = llc_cache->num_colors*sizeof(page_list_t);
27         page_list_t LCKD(&colored_page_free_list_lock)*tmp =
28             (page_list_t*)boot_alloc(list_size,PGSIZE);
29         colored_page_free_list = SINIT(tmp);
30         for (int i = 0; i < llc_cache->num_colors; i++)
31                 LIST_INIT(&colored_page_free_list[i]);
32 }
33
34 /* Can do whatever here.  For now, our page allocator just works with colors,
35  * not NUMA zones or anything. */
36 static void track_free_page(struct page *page)
37 {
38         LIST_INSERT_HEAD(&colored_page_free_list[get_page_color(page2ppn(page),
39                                                                 llc_cache)],
40                          page, pg_link);
41         nr_free_pages++;
42         /* Page was previous marked as busy, need to set it free explicitly */
43         page_setref(page, 0);
44 }
45
46 static struct page *pa64_to_page(uint64_t paddr)
47 {
48         return &pages[paddr >> PGSHIFT];
49 }
50
51 static bool pa64_is_in_kernel(uint64_t paddr)
52 {
53         extern char end[];
54         /* kernel is linked and loaded here (in kernel{32,64}.ld */
55         return (EXTPHYSMEM <= paddr) && (paddr < PADDR(end));
56 }
57
58 /* Helper.  For every page in the entry, this will determine whether or not the
59  * page is free, and handle accordingly.  All pages are marked as busy by
60  * default, and we're just determining which of them could be free. */
61 static void parse_mboot_region(struct multiboot_mmap_entry *entry, void *data)
62 {
63         physaddr_t boot_freemem_paddr = (physaddr_t)data;
64         bool in_bootzone = (entry->addr <= boot_freemem_paddr) &&
65                            (boot_freemem_paddr < entry->addr + entry->len);
66
67         if (entry->type != MULTIBOOT_MEMORY_AVAILABLE)
68                 return;
69         /* TODO: we'll have some issues with jumbo allocation */
70         /* Most entries are page aligned, though on some machines below EXTPHYSMEM
71          * we may have some that aren't.  If two regions collide on the same page
72          * (one of them starts unaligned), we need to only handle the page once, and
73          * err on the side of being busy.
74          *
75          * Since these regions happen below EXTPHYSMEM, they are all marked busy (or
76          * else we'll panic).  I'll probably rewrite this for jumbos before I find a
77          * machine with unaligned mboot entries in higher memory. */
78         if (PGOFF(entry->addr))
79                 assert(entry->addr < EXTPHYSMEM);
80         for (uint64_t i = ROUNDDOWN(entry->addr, PGSIZE);
81              i < entry->addr + entry->len;
82              i += PGSIZE) {
83                 /* Skip pages we'll never map (above KERNBASE).  Once we hit one of
84                  * them, we know the rest are too (for this entry). */
85                 if (i >= max_paddr)
86                         return;
87                 /* Mark low mem as busy (multiboot stuff is there, usually, too).  Since
88                  * that memory may be freed later (like the smp_boot page), we'll treat
89                  * it like it is busy/allocated. */
90                 if (i < EXTPHYSMEM)
91                         continue;
92                 /* Mark as busy pages already allocated in boot_alloc() */
93                 if (in_bootzone && (i < boot_freemem_paddr))
94                         continue;
95                 /* Need to double check for the kernel, in case it wasn't in the
96                  * bootzone.  If it was in the bootzone, we already skipped it. */
97                 if (pa64_is_in_kernel(i))
98                         continue;
99                 track_free_page(pa64_to_page(i));
100         }
101 }
102
103 static void check_range(uint64_t start, uint64_t end, int expect)
104 {
105         int ref;
106         if (PGOFF(start))
107                 printk("Warning: check_range given unaligned addr 0x%016llx\n", start);
108         for (uint64_t i = start; i < end; i += PGSIZE)  {
109                 ref = kref_refcnt(&pa64_to_page(i)->pg_kref);
110                 if (ref != expect) {
111                         printk("Error: while checking range [0x%016llx, 0x%016llx), "
112                                "physaddr 0x%016llx refcnt was %d, expected %d\n", start,
113                                end, i, ref, expect);
114                         panic("");
115                 }
116         }
117 }
118
119 /* Note this doesn't check all of memory.  There are some chunks of 'memory'
120  * that aren't reported by MB at all, like the VRAM sections at 0xa0000. */
121 static void check_mboot_region(struct multiboot_mmap_entry *entry, void *data)
122 {
123         extern char end[];
124         physaddr_t boot_freemem_paddr = (physaddr_t)data;
125         bool in_bootzone = (entry->addr <= boot_freemem_paddr) &&
126                            (boot_freemem_paddr < entry->addr + entry->len);
127         /* Need to deal with 32b wrap-around */
128         uint64_t zone_end = MIN(entry->addr + entry->len, (uint64_t)max_paddr);
129
130         if (entry->type != MULTIBOOT_MEMORY_AVAILABLE) {
131                 check_range(entry->addr, zone_end, 1);
132                 return;
133         }
134         if (zone_end <= EXTPHYSMEM) {
135                 check_range(entry->addr, zone_end, 1);
136                 return;
137         }
138         /* this may include the kernel */
139         if (in_bootzone) {
140                 /* boot_freemem might not be page aligned.  If it's part-way through a
141                  * page, that page should be busy */
142                 check_range(entry->addr, ROUNDUP(PADDR(boot_freemem), PGSIZE), 1);
143                 check_range(ROUNDUP(PADDR(boot_freemem), PGSIZE), zone_end, 0);
144                 assert(zone_end == PADDR(boot_freelimit));
145                 return;
146         }
147         /* kernel's range (hardcoded in the linker script).  If we're checking now,
148          * it means the kernel is not in the same entry as the bootzone. */
149         if (entry->addr == EXTPHYSMEM) {
150                 check_range(EXTPHYSMEM, PADDR(end), 1);
151                 check_range(ROUNDUP(PADDR(end), PGSIZE), zone_end, 0);
152                 return;
153         }
154 }
155
156 /* Since we can't parse multiboot mmap entries, we need to just guess at what
157  * pages are free and which ones aren't.
158  *
159  * Despite the lack of info from mbi, I know there is a magic hole in physical
160  * memory that we can't use, from the IOAPIC_PBASE on up [0xfec00000,
161  * 0xffffffff] (I'm being pessimistic).  But, that's not pessimistic enough!
162  * Qemu still doesn't like that.   From using 0xe0000000 instead works for mine.
163  * According to http://wiki.osdev.org/Memory_Map_(x86), some systems could
164  * reserve from [0xc0000000, 0xffffffff].  Anyway, in lieu of real memory
165  * detection, I'm just skipping that entire region.
166  *
167  * We may or may not have more free memory above this magic hole, depending on
168  * both the amount of RAM we have as well as 32 vs 64 bit.
169  *
170  * So we'll go with two free memory regions:
171  *
172  *              [ 0, ROUNDUP(boot_freemem_paddr, PGSIZE) ) = busy
173  *              [ ROUNDUP(boot_freemem_paddr, PGSIZE), TOP_OF_1 ) = free
174  *              [ MAGIC_HOLE, 0x0000000100000000 ) = busy
175  *              (and maybe this:)
176  *              [ 0x0000000100000000, max_paddr ) = free
177  *
178  * where TOP_OF_1 is the min of IOAPIC_PBASE and max_paddr.
179  *
180  * For the busy regions, I don't actually need to mark the pages as busy.  They
181  * were marked busy when the pages array was created (same as when we parse
182  * multiboot info).  I'll just assert that they are properly marked as busy.
183  *
184  * As with parsing mbi regions, this will ignore the hairy areas below
185  * EXTPHYSMEM, and mark the entire kernel and anything we've boot alloc'd as
186  * busy. */
187 static void account_for_pages(physaddr_t boot_freemem_paddr)
188 {
189         physaddr_t top_of_busy = ROUNDUP(boot_freemem_paddr, PGSIZE);
190         physaddr_t top_of_free_1 = MIN(0xc0000000, max_paddr);
191         physaddr_t start_of_free_2;
192
193         printk("Warning: poor memory detection (qemu?).  May lose 1GB of RAM\n");
194         for (physaddr_t i = 0; i < top_of_busy; i += PGSIZE)
195                 assert(kref_refcnt(&pa64_to_page(i)->pg_kref) == 1);
196         for (physaddr_t i = top_of_busy; i < top_of_free_1; i += PGSIZE)
197                 track_free_page(pa64_to_page(i));
198         /* If max_paddr is less than the start of our potential second free mem
199          * region, we can just leave.  We also don't want to poke around the pages
200          * array either (and accidentally run off the end of the array).
201          *
202          * Additionally, 32 bit doesn't acknowledge pmem above the 4GB mark. */
203 #ifdef CONFIG_X86_64
204         start_of_free_2 = 0x0000000100000000;
205         if (max_paddr < start_of_free_2)
206                 return;
207         for (physaddr_t i = top_of_free_1; i < start_of_free_2; i += PGSIZE)
208                 assert(kref_refcnt(&pa64_to_page(i)->pg_kref) == 1);
209         for (physaddr_t i = start_of_free_2; i < max_paddr; i += PGSIZE)
210                 track_free_page(pa64_to_page(i));
211 #endif /* CONFIG_X86_64 */
212 }
213
214 /* Initialize the memory free lists.  After this, do not use boot_alloc. */
215 void page_alloc_init(struct multiboot_info *mbi)
216 {
217         page_alloc_bootstrap();
218         /* First, we need to initialize the pages array such that all memory is busy
219          * by default.
220          *
221          * To init the free list(s), each page that is already allocated/busy will
222          * remain increfed.  All other pages that were reported as 'free' will be
223          * added to a free list.  Their refcnts are set to 0.
224          *
225          * To avoid a variety of headaches, any memory below 1MB is considered busy.
226          * Likewise, everything in the kernel, up to _end is also busy.  And
227          * everything we've already boot_alloc'd is busy.  These chunks of memory
228          * are reported as 'free' by multiboot.
229          *
230          * We'll also abort the mapping for any addresses over max_paddr, since
231          * we'll never use them.  'pages' does not track them either.
232          *
233          * One special note: we actually use the memory at 0x1000 for smp_boot.
234          * It'll get set to 'used' like the others; just FYI.
235          *
236          * Finally, if we want to use actual jumbo page allocation (not just
237          * mapping), we need to round up _end, and make sure all of multiboot's
238          * sections are jumbo-aligned. */
239         physaddr_t boot_freemem_paddr = PADDR(ROUNDUP(boot_freemem, PGSIZE));
240
241         for (long i = 0; i < max_nr_pages; i++)
242                 page_setref(&pages[i], 1);
243         if (mboot_has_mmaps(mbi)) {
244                 mboot_foreach_mmap(mbi, parse_mboot_region, (void*)boot_freemem_paddr);
245                 /* Test the page alloc - if this gets slow, we can CONFIG it */
246                 mboot_foreach_mmap(mbi, check_mboot_region, (void*)boot_freemem_paddr);
247         } else {
248                 /* No multiboot mmap regions (probably run from qemu with -kernel) */
249                 account_for_pages(boot_freemem_paddr);
250         }
251         printk("Number of free pages: %lu\n", nr_free_pages);
252         printk("Page alloc init successful\n");
253 }