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