Remove page coloring
[akaros.git] / kern / src / page_alloc.c
1 /* Copyright (c) 2009, 2010 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  * Kevin Klues <klueska@cs.berkeley.edu>
6  * Barret Rhoden <brho@cs.berkeley.edu> */
7
8 #include <ros/errno.h>
9 #include <sys/queue.h>
10 #include <bitmask.h>
11 #include <page_alloc.h>
12 #include <pmap.h>
13 #include <err.h>
14 #include <string.h>
15 #include <kmalloc.h>
16 #include <blockdev.h>
17
18 spinlock_t page_list_lock = SPINLOCK_INITIALIZER_IRQSAVE;
19
20 page_list_t page_free_list = BSD_LIST_HEAD_INITIALIZER(page_free_list);
21
22 static void __page_decref(page_t *page);
23 static error_t __page_alloc_specific(page_t **page, size_t ppn);
24
25 /* Initializes a page.  We can optimize this a bit since 0 usually works to init
26  * most structures, but we'll hold off on that til it is a problem. */
27 static void __page_init(struct page *page)
28 {
29         memset(page, 0, sizeof(page_t));
30         sem_init(&page->pg_sem, 0);
31         page->pg_is_free = FALSE;
32 }
33
34 static void __real_page_alloc(struct page *page)
35 {
36         BSD_LIST_REMOVE(page, pg_link);
37         __page_init(page);
38 }
39
40 /* Internal version of page_alloc_specific.  Grab the lock first. */
41 static error_t __page_alloc_specific(page_t** page, size_t ppn)
42 {
43         page_t* sp_page = ppn2page(ppn);
44         if (!page_is_free(ppn))
45                 return -ENOMEM;
46         *page = sp_page;
47         __real_page_alloc(sp_page);
48         return 0;
49 }
50
51 /* Helper, allocates a free page. */
52 static struct page *get_a_free_page(void)
53 {
54         struct page *ret;
55
56         spin_lock_irqsave(&page_list_lock);
57         ret = BSD_LIST_FIRST(&page_free_list);
58         if (ret)
59                 __real_page_alloc(ret);
60         spin_unlock_irqsave(&page_list_lock);
61         return ret;
62 }
63
64 /**
65  * @brief Allocates a physical page from a pool of unused physical memory.
66  *
67  * Zeroes the page.
68  *
69  * @param[out] page  set to point to the Page struct
70  *                   of the newly allocated page
71  *
72  * @return ESUCCESS on success
73  * @return -ENOMEM  otherwise
74  */
75 error_t upage_alloc(struct proc *p, page_t **page, bool zero)
76 {
77         struct page *pg = get_a_free_page();
78
79         if (!pg)
80                 return -ENOMEM;
81         *page = pg;
82         if (zero)
83                 memset(page2kva(*page), 0, PGSIZE);
84         return 0;
85 }
86
87 error_t kpage_alloc(page_t **page)
88 {
89         struct page *pg = get_a_free_page();
90
91         if (!pg)
92                 return -ENOMEM;
93         *page = pg;
94         return 0;
95 }
96
97 /* Helper: allocates a refcounted page of memory for the kernel's use and
98  * returns the kernel address (kernbase), or 0 on error. */
99 void *kpage_alloc_addr(void)
100 {
101         struct page *pg = get_a_free_page();
102
103         if (!pg)
104                 return 0;
105         return page2kva(pg);
106 }
107
108 void *kpage_zalloc_addr(void)
109 {
110         void *retval = kpage_alloc_addr();
111         if (retval)
112                 memset(retval, 0, PGSIZE);
113         return retval;
114 }
115
116 /**
117  * @brief Allocated 2^order contiguous physical pages.  Will increment the
118  * reference count for the pages.
119  *
120  * @param[in] order order of the allocation
121  * @param[in] flags memory allocation flags
122  *
123  * @return The KVA of the first page, NULL otherwise.
124  */
125 void *get_cont_pages(size_t order, int flags)
126 {
127         size_t npages = 1 << order;
128
129         size_t naddrpages = max_paddr / PGSIZE;
130         // Find 'npages' free consecutive pages
131         int first = -1;
132         spin_lock_irqsave(&page_list_lock);
133         for(int i=(naddrpages-1); i>=(npages-1); i--) {
134                 int j;
135                 for(j=i; j>=(i-(npages-1)); j--) {
136                         if( !page_is_free(j) ) {
137                                 /* i will be j - 1 next time around the outer loop */
138                                 i = j;
139                                 break;
140                         }
141                 }
142                 /* careful: if we change the allocator and allow npages = 0, then this
143                  * will trip when we set i = j.  then we'll be handing out in-use
144                  * memory. */
145                 if( j == (i-(npages-1)-1)) {
146                         first = j+1;
147                         break;
148                 }
149         }
150         //If we couldn't find them, return NULL
151         if( first == -1 ) {
152                 spin_unlock_irqsave(&page_list_lock);
153                 if (flags & MEM_ERROR)
154                         error(ENOMEM, ERROR_FIXME);
155                 return NULL;
156         }
157
158         for(int i=0; i<npages; i++) {
159                 page_t* page;
160                 __page_alloc_specific(&page, first+i);
161         }
162         spin_unlock_irqsave(&page_list_lock);
163         return ppn2kva(first);
164 }
165
166 /**
167  * @brief Allocated 2^order contiguous physical pages.  Will increment the
168  * reference count for the pages. Get them from NUMA node node.
169  *
170  * @param[in] node which node to allocate from. Unimplemented.
171  * @param[in] order order of the allocation
172  * @param[in] flags memory allocation flags
173  *
174  * @return The KVA of the first page, NULL otherwise.
175  */
176 void *get_cont_pages_node(int node, size_t order, int flags)
177 {
178         return get_cont_pages(order, flags);
179 }
180
181 /**
182  * @brief Allocated 2^order contiguous physical pages starting at paddr 'at'.
183  * Will increment the reference count for the pages.
184  *
185  * We might need some restrictions on size of the alloc and its 'at' alignment.
186  * For instance, for a future buddy allocator (if we go that route), it might be
187  * easier if the order was aligned to the 'at'.  e.g., a 1GB alloc must be at a
188  * 1GB aligned addr.  A 2GB alloc would not be allowed at a merely 1GB
189  * alignment.
190  *
191  * For now, anything goes.  Note that the request is for a physical starting
192  * point, but the return is the KVA.
193  *
194  * @param[in] order order of the allocation
195  * @param[in] at starting address
196  * @param[in] flags memory allocation flags
197  *
198  * @return The KVA of the first page, NULL otherwise.
199  */
200 void *get_cont_phys_pages_at(size_t order, physaddr_t at, int flags)
201 {
202         unsigned long nr_pgs = 1 << order;
203         unsigned long first_pg_nr = pa2ppn(at);
204
205         if (first_pg_nr + nr_pgs > pa2ppn(max_paddr))
206                 return 0;
207         spin_lock_irqsave(&page_list_lock);
208         for (unsigned long i = first_pg_nr; i < first_pg_nr + nr_pgs; i++) {
209                 if (!page_is_free(i)) {
210                         spin_unlock_irqsave(&page_list_lock);
211                         if (flags & MEM_ERROR)
212                                 error(ENOMEM, ERROR_FIXME);
213                         return NULL;
214                 }
215         }
216         for (unsigned long i = first_pg_nr; i < first_pg_nr + nr_pgs; i++)
217                 __real_page_alloc(ppn2page(i));
218         spin_unlock_irqsave(&page_list_lock);
219         return KADDR(at);
220 }
221
222 void free_cont_pages(void *buf, size_t order)
223 {
224         size_t npages = 1 << order;
225         spin_lock_irqsave(&page_list_lock);
226         for (size_t i = kva2ppn(buf); i < kva2ppn(buf) + npages; i++) {
227                 page_t* page = ppn2page(i);
228                 __page_decref(ppn2page(i));
229                 assert(page_is_free(i));
230         }
231         spin_unlock_irqsave(&page_list_lock);
232         return;
233 }
234
235 /* Check if a page with the given physical page # is free. */
236 int page_is_free(size_t ppn)
237 {
238         return ppn2page(ppn)->pg_is_free;
239 }
240
241 /* Frees the page */
242 void page_decref(page_t *page)
243 {
244         spin_lock_irqsave(&page_list_lock);
245         __page_decref(page);
246         spin_unlock_irqsave(&page_list_lock);
247 }
248
249 /* Frees the page.  Don't call this without holding the lock already. */
250 static void __page_decref(page_t *page)
251 {
252         if (atomic_read(&page->pg_flags) & PG_BUFFER)
253                 free_bhs(page);
254         /* Give our page back to the free list.  The protections for this are that
255          * the list lock is grabbed by page_decref. */
256         BSD_LIST_INSERT_HEAD(&page_free_list, page, pg_link);
257         page->pg_is_free = TRUE;
258 }
259
260 /* Attempts to get a lock on the page for IO operations.  If it is already
261  * locked, it will block the kthread until it is unlocked.  Note that this is
262  * really a "sleep on some event", not necessarily the IO, but it is "the page
263  * is ready". */
264 void lock_page(struct page *page)
265 {
266         /* when this returns, we have are the ones to have locked the page */
267         sem_down(&page->pg_sem);
268         assert(!(atomic_read(&page->pg_flags) & PG_LOCKED));
269         atomic_or(&page->pg_flags, PG_LOCKED);
270 }
271
272 /* Unlocks the page, and wakes up whoever is waiting on the lock */
273 void unlock_page(struct page *page)
274 {
275         atomic_and(&page->pg_flags, ~PG_LOCKED);
276         sem_up(&page->pg_sem);
277 }
278
279 void print_pageinfo(struct page *page)
280 {
281         int i;
282         if (!page) {
283                 printk("Null page\n");
284                 return;
285         }
286         printk("Page %d (%p), Flags: 0x%08x Is Free: %d\n", page2ppn(page),
287                page2kva(page), atomic_read(&page->pg_flags),
288                page->pg_is_free);
289         if (page->pg_mapping) {
290                 printk("\tMapped into object %p at index %d\n",
291                        page->pg_mapping->pm_host, page->pg_index);
292         }
293         if (atomic_read(&page->pg_flags) & PG_BUFFER) {
294                 struct buffer_head *bh = (struct buffer_head*)page->pg_private;
295                 i = 0;
296                 while (bh) {
297                         printk("\tBH %d: buffer: %p, sector: %d, nr_sector: %d\n", i,
298                                bh->bh_buffer, bh->bh_sector, bh->bh_nr_sector);
299                         i++;
300                         bh = bh->bh_next;
301                 }
302                 printk("\tPage is %sup to date\n",
303                        atomic_read(&page->pg_flags) & PG_UPTODATE ? "" : "not ");
304         }
305         printk("\tPage is %slocked\n",
306                atomic_read(&page->pg_flags) & PG_LOCKED ? "" : "un");
307         printk("\tPage is %s\n",
308                atomic_read(&page->pg_flags) & PG_DIRTY ? "dirty" : "clean");
309 }