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