535d16e40f2d7b4ac88fe9c833101a8697b099f4
[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 #define l1 (available_caches.l1)
19 #define l2 (available_caches.l2)
20 #define l3 (available_caches.l3)
21
22 static void __page_decref(page_t *page);
23 static error_t __page_alloc_specific(page_t **page, size_t ppn);
24
25 #ifdef CONFIG_PAGE_COLORING
26 #define NUM_KERNEL_COLORS 8
27 #else
28 #define NUM_KERNEL_COLORS 1
29 #endif
30
31
32 // Global list of colors allocated to the general purpose memory allocator
33 uint8_t* global_cache_colors_map;
34 size_t global_next_color = 0;
35
36 void colored_page_alloc_init()
37 {
38         global_cache_colors_map = 
39                kmalloc(BYTES_FOR_BITMASK(llc_cache->num_colors), 0);
40         CLR_BITMASK(global_cache_colors_map, llc_cache->num_colors);
41         for(int i = 0; i < llc_cache->num_colors/NUM_KERNEL_COLORS; i++)
42                 cache_color_alloc(llc_cache, global_cache_colors_map);
43 }
44
45 /* Initializes a page.  We can optimize this a bit since 0 usually works to init
46  * most structures, but we'll hold off on that til it is a problem. */
47 static void __page_init(struct page *page)
48 {
49         memset(page, 0, sizeof(page_t));
50         page_setref(page, 1);
51         sem_init(&page->pg_sem, 0);
52 }
53
54 #define __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, predicate) \
55         /* Find first available color with pages available */                   \
56     /* in the given range */                                                \
57         int i = base_color;                                                     \
58         for (i; i < (base_color+range); i++) {                                  \
59                 if((predicate))                                                     \
60                         break;                                                          \
61         }                                                                       \
62         /* Allocate a page from that color */                                   \
63         if(i < (base_color+range)) {                                            \
64                 *page = BSD_LIST_FIRST(&colored_page_free_list[i]);                 \
65                 BSD_LIST_REMOVE(*page, pg_link);                                    \
66                 __page_init(*page);                                                 \
67                 return i;                                                           \
68         }                                                                       \
69         return -ENOMEM;
70
71 static ssize_t __page_alloc_from_color_range(page_t** page,  
72                                            uint16_t base_color,
73                                            uint16_t range) 
74 {
75         __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
76                          !BSD_LIST_EMPTY(&colored_page_free_list[i]));
77 }
78
79 static ssize_t __page_alloc_from_color_map_range(page_t** page, uint8_t* map, 
80                                               size_t base_color, size_t range)
81 {  
82         __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
83                     GET_BITMASK_BIT(map, i) &&
84                         !BSD_LIST_EMPTY(&colored_page_free_list[i]))
85 }
86
87 static ssize_t __colored_page_alloc(uint8_t* map, page_t** page, 
88                                                size_t next_color)
89 {
90         ssize_t ret;
91         if((ret = __page_alloc_from_color_map_range(page, map, 
92                                    next_color, llc_cache->num_colors - next_color)) < 0)
93                 ret = __page_alloc_from_color_map_range(page, map, 0, next_color);
94         return ret;
95 }
96
97 static void __real_page_alloc(struct page *page)
98 {
99         BSD_LIST_REMOVE(page, pg_link);
100         __page_init(page);
101 }
102
103 /* Internal version of page_alloc_specific.  Grab the lock first. */
104 static error_t __page_alloc_specific(page_t** page, size_t ppn)
105 {
106         page_t* sp_page = ppn2page(ppn);
107         if (!page_is_free(ppn))
108                 return -ENOMEM;
109         *page = sp_page;
110         __real_page_alloc(sp_page);
111         return 0;
112 }
113
114 /**
115  * @brief Allocates a physical page from a pool of unused physical memory.
116  * Note, the page IS reference counted.
117  *
118  * Zeroes the page.
119  *
120  * @param[out] page  set to point to the Page struct
121  *                   of the newly allocated page
122  *
123  * @return ESUCCESS on success
124  * @return -ENOMEM  otherwise
125  */
126 error_t upage_alloc(struct proc* p, page_t** page, int zero)
127 {
128         spin_lock_irqsave(&colored_page_free_list_lock);
129         ssize_t ret = __colored_page_alloc(p->cache_colors_map, 
130                                              page, p->next_cache_color);
131         spin_unlock_irqsave(&colored_page_free_list_lock);
132
133         if (ret >= 0) {
134                 if(zero)
135                         memset(page2kva(*page),0,PGSIZE);
136                 p->next_cache_color = (ret + 1) & (llc_cache->num_colors-1);
137                 return 0;
138         }
139         return ret;
140 }
141
142 /* Allocates a refcounted page of memory for the kernel's use */
143 error_t kpage_alloc(page_t** page) 
144 {
145         ssize_t ret;
146         spin_lock_irqsave(&colored_page_free_list_lock);
147         if ((ret = __page_alloc_from_color_range(page, global_next_color, 
148                                     llc_cache->num_colors - global_next_color)) < 0)
149                 ret = __page_alloc_from_color_range(page, 0, global_next_color);
150
151         if (ret >= 0) {
152                 global_next_color = ret;        
153                 ret = ESUCCESS;
154         }
155         spin_unlock_irqsave(&colored_page_free_list_lock);
156         
157         return ret;
158 }
159
160 /* Helper: allocates a refcounted page of memory for the kernel's use and
161  * returns the kernel address (kernbase), or 0 on error. */
162 void *kpage_alloc_addr(void)
163 {
164         struct page *a_page;
165         if (kpage_alloc(&a_page))
166                 return 0;
167         return page2kva(a_page);
168 }
169
170 void *kpage_zalloc_addr(void)
171 {
172         void *retval = kpage_alloc_addr();
173         if (retval)
174                 memset(retval, 0, PGSIZE);
175         return retval;
176 }
177
178 /**
179  * @brief Allocated 2^order contiguous physical pages.  Will increment the
180  * reference count for the pages.
181  *
182  * @param[in] order order of the allocation
183  * @param[in] flags memory allocation flags
184  *
185  * @return The KVA of the first page, NULL otherwise.
186  */
187 void *get_cont_pages(size_t order, int flags)
188 {
189         size_t npages = 1 << order;     
190
191         size_t naddrpages = max_paddr / PGSIZE;
192         // Find 'npages' free consecutive pages
193         int first = -1;
194         spin_lock_irqsave(&colored_page_free_list_lock);
195         for(int i=(naddrpages-1); i>=(npages-1); i--) {
196                 int j;
197                 for(j=i; j>=(i-(npages-1)); j--) {
198                         if( !page_is_free(j) ) {
199                                 i = j - 1;
200                                 break;
201                         }
202                 }
203                 if( j == (i-(npages-1)-1)) {
204                         first = j+1;
205                         break;
206                 }
207         }
208         //If we couldn't find them, return NULL
209         if( first == -1 ) {
210                 spin_unlock_irqsave(&colored_page_free_list_lock);
211                 if (flags & MEM_ERROR)
212                         error(ENOMEM, ERROR_FIXME);
213                 return NULL;
214         }
215
216         for(int i=0; i<npages; i++) {
217                 page_t* page;
218                 __page_alloc_specific(&page, first+i);
219         }
220         spin_unlock_irqsave(&colored_page_free_list_lock);
221         return ppn2kva(first);
222 }
223
224 /**
225  * @brief Allocated 2^order contiguous physical pages.  Will increment the
226  * reference count for the pages. Get them from NUMA node node.
227  *
228  * @param[in] node which node to allocate from. Unimplemented.
229  * @param[in] order order of the allocation
230  * @param[in] flags memory allocation flags
231  *
232  * @return The KVA of the first page, NULL otherwise.
233  */
234 void *get_cont_pages_node(int node, size_t order, int flags)
235 {
236         return get_cont_pages(order, flags);
237 }
238
239 /**
240  * @brief Allocated 2^order contiguous physical pages starting at paddr 'at'.
241  * Will increment the reference count for the pages.
242  *
243  * We might need some restrictions on size of the alloc and its 'at' alignment.
244  * For instance, for a future buddy allocator (if we go that route), it might be
245  * easier if the order was aligned to the 'at'.  e.g., a 1GB alloc must be at a
246  * 1GB aligned addr.  A 2GB alloc would not be allowed at a merely 1GB
247  * alignment.
248  *
249  * For now, anything goes.  Note that the request is for a physical starting
250  * point, but the return is the KVA.
251  *
252  * @param[in] order order of the allocation
253  * @param[in] at starting address
254  * @param[in] flags memory allocation flags
255  *
256  * @return The KVA of the first page, NULL otherwise.
257  */
258 void *get_cont_phys_pages_at(size_t order, physaddr_t at, int flags)
259 {
260         unsigned long nr_pgs = 1 << order;
261         unsigned long first_pg_nr = pa2ppn(at);
262
263         if (first_pg_nr + nr_pgs > pa2ppn(max_paddr))
264                 return 0;
265         spin_lock_irqsave(&colored_page_free_list_lock);
266         for (unsigned long i = first_pg_nr; i < first_pg_nr + nr_pgs; i++) {
267                 if (!page_is_free(i)) {
268                         spin_unlock_irqsave(&colored_page_free_list_lock);
269                         if (flags & MEM_ERROR)
270                                 error(ENOMEM, ERROR_FIXME);
271                         return NULL;
272                 }
273         }
274         for (unsigned long i = first_pg_nr; i < first_pg_nr + nr_pgs; i++)
275                 __real_page_alloc(ppn2page(i));
276         spin_unlock_irqsave(&colored_page_free_list_lock);
277         return KADDR(at);
278 }
279
280 void free_cont_pages(void *buf, size_t order)
281 {
282         size_t npages = 1 << order;     
283         spin_lock_irqsave(&colored_page_free_list_lock);
284         for (size_t i = kva2ppn(buf); i < kva2ppn(buf) + npages; i++) {
285                 page_t* page = ppn2page(i);
286                 __page_decref(ppn2page(i));
287                 assert(page_is_free(i));
288         }
289         spin_unlock_irqsave(&colored_page_free_list_lock);
290         return; 
291 }
292
293 /*
294  * Allocates a specific physical page.
295  * Does NOT set the contents of the physical page to zero -
296  * the caller must do that if necessary.
297  *
298  * ppn         -- the page number to allocate
299  * *page       -- is set to point to the Page struct 
300  *                of the newly allocated page
301  *
302  * RETURNS 
303  *   ESUCCESS  -- on success
304  *   -ENOMEM   -- otherwise 
305  */
306 error_t upage_alloc_specific(struct proc* p, page_t** page, size_t ppn)
307 {
308         spin_lock_irqsave(&colored_page_free_list_lock);
309         __page_alloc_specific(page, ppn);
310         spin_unlock_irqsave(&colored_page_free_list_lock);
311         return 0;
312 }
313
314 error_t kpage_alloc_specific(page_t** page, size_t ppn)
315 {
316         spin_lock_irqsave(&colored_page_free_list_lock);
317         __page_alloc_specific(page, ppn);
318         spin_unlock_irqsave(&colored_page_free_list_lock);
319         return 0;
320 }
321
322 /* Check if a page with the given physical page # is free. */
323 int page_is_free(size_t ppn) {
324         page_t* page = ppn2page(ppn);
325         if (kref_refcnt(&page->pg_kref))
326                 return FALSE;
327         return TRUE;
328 }
329
330 /*
331  * Increment the reference count on a page
332  */
333 void page_incref(page_t *page)
334 {
335         kref_get(&page->pg_kref, 1);
336 }
337
338 /* Decrement the reference count on a page, freeing it if there are no more
339  * refs. */
340 void page_decref(page_t *page)
341 {
342         spin_lock_irqsave(&colored_page_free_list_lock);
343         __page_decref(page);
344         spin_unlock_irqsave(&colored_page_free_list_lock);
345 }
346
347 /* Decrement the reference count on a page, freeing it if there are no more
348  * refs.  Don't call this without holding the lock already. */
349 static void __page_decref(page_t *page)
350 {
351         kref_put(&page->pg_kref);
352 }
353
354 /* Kref release function. */
355 static void page_release(struct kref *kref)
356 {
357         struct page *page = container_of(kref, struct page, pg_kref);
358
359         if (atomic_read(&page->pg_flags) & PG_BUFFER)
360                 free_bhs(page);
361         /* Give our page back to the free list.  The protections for this are that
362          * the list lock is grabbed by page_decref. */
363         BSD_LIST_INSERT_HEAD(
364            &(colored_page_free_list[get_page_color(page2ppn(page), llc_cache)]),
365            page,
366            pg_link
367         );
368 }
369
370 /* Helper when initializing a page - just to prevent the proliferation of
371  * page_release references (and because this function is sitting around in the
372  * code).  Sets the reference count on a page to a specific value, usually 1. */
373 void page_setref(page_t *page, size_t val)
374 {
375         kref_init(&page->pg_kref, page_release, val); 
376 }
377
378 /* Attempts to get a lock on the page for IO operations.  If it is already
379  * locked, it will block the kthread until it is unlocked.  Note that this is
380  * really a "sleep on some event", not necessarily the IO, but it is "the page
381  * is ready". */
382 void lock_page(struct page *page)
383 {
384         /* when this returns, we have are the ones to have locked the page */
385         sem_down(&page->pg_sem);
386         assert(!(atomic_read(&page->pg_flags) & PG_LOCKED));
387         atomic_or(&page->pg_flags, PG_LOCKED);
388 }
389
390 /* Unlocks the page, and wakes up whoever is waiting on the lock */
391 void unlock_page(struct page *page)
392 {
393         atomic_and(&page->pg_flags, ~PG_LOCKED);
394         sem_up(&page->pg_sem);
395 }
396
397 void print_pageinfo(struct page *page)
398 {
399         int i;
400         if (!page) {
401                 printk("Null page\n");
402                 return;
403         }
404         printk("Page %d (%p), Flags: 0x%08x Refcnt: %d\n", page2ppn(page),
405                page2kva(page), atomic_read(&page->pg_flags),
406                kref_refcnt(&page->pg_kref));
407         if (page->pg_mapping) {
408                 printk("\tMapped into object %p at index %d\n",
409                        page->pg_mapping->pm_host, page->pg_index);
410         }
411         if (atomic_read(&page->pg_flags) & PG_BUFFER) {
412                 struct buffer_head *bh = (struct buffer_head*)page->pg_private;
413                 i = 0;
414                 while (bh) {
415                         printk("\tBH %d: buffer: %p, sector: %d, nr_sector: %d\n", i,
416                                bh->bh_buffer, bh->bh_sector, bh->bh_nr_sector);
417                         i++;
418                         bh = bh->bh_next;
419                 }
420                 printk("\tPage is %sup to date\n",
421                        atomic_read(&page->pg_flags) & PG_UPTODATE ? "" : "not ");
422         }
423         printk("\tPage is %slocked\n",
424                atomic_read(&page->pg_flags) & PG_LOCKED ? "" : "un");
425         printk("\tPage is %s\n",
426                atomic_read(&page->pg_flags) & PG_DIRTY ? "dirty" : "clean");
427 }