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