Active message deadlock and kmalloc canary
[akaros.git] / kern / src / 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  * Kevin Klues <klueska@cs.berkeley.edu>    
6  */
7
8 #ifdef __SHARC__
9 #pragma nosharc
10 #endif
11
12 #include <sys/queue.h>
13 #include <page_alloc.h>
14 #include <pmap.h>
15 #include <string.h>
16
17 static void __page_decref(page_t *page);
18 static error_t __page_alloc_specific(page_t** page, size_t ppn);
19 static error_t __page_free(page_t* page);
20
21 /**
22  * @brief Clear a Page structure.
23  *
24  * The result has null links and 0 refcount.
25  * Note that the corresponding physical page is NOT initialized!
26  */
27 static void page_clear(page_t *SAFE page)
28 {
29         memset(page, 0, sizeof(page_t));
30 }
31
32 error_t page_alloc_from_color_range(page_t** page,  
33                                     uint16_t base_color,
34                                     uint16_t range) {
35
36         // Find first available color with pages available
37     //  in the proper range
38         int i = base_color;
39         spin_lock_irqsave(&colored_page_free_list_lock);
40         for(i; i<(base_color+range); i++) {
41                 if(!LIST_EMPTY(&colored_page_free_list[i]))
42                         break;
43         }
44         // Alocate a page from that color
45         if(i < (base_color+range)) {
46                 *page = LIST_FIRST(&colored_page_free_list[i]);
47                 LIST_REMOVE(*page, page_link);
48                 page_clear(*page);
49                 spin_unlock_irqsave(&colored_page_free_list_lock);
50                 return ESUCCESS;
51         }
52         spin_unlock_irqsave(&colored_page_free_list_lock);
53         return -ENOMEM;
54 }
55
56 /**
57  * @brief Allocates a physical page from a pool of unused physical memory
58  *
59  * Does NOT set the contents of the physical page to zero -
60  * the caller must do that if necessary.
61  *
62  * @param[out] page  set to point to the Page struct
63  *                   of the newly allocated page
64  *
65  * @return ESUCCESS on success
66  * @return -ENOMEM  otherwise
67  */
68 error_t page_alloc(page_t** page) 
69 {
70         return page_alloc_from_color_range(page, 0, llc_num_colors);
71 }
72
73 /**
74  * @brief Allocated 2^order contiguous physical pages.  Will increment the
75  * reference count for the pages.
76  *
77  * @param[in] order order of the allocation
78  * @param[in] flags memory allocation flags
79  *
80  * @return The KVA of the first page, NULL otherwise.
81  */
82 void *get_cont_pages(size_t order, int flags)
83 {
84         size_t npages = 1 << order;     
85
86         // Find 'npages' free consecutive pages
87         int first = -1;
88         spin_lock_irqsave(&colored_page_free_list_lock);
89         for(int i=(naddrpages-1); i>=(npages-1); i--) {
90                 int j;
91                 for(j=i; j>=(i-(npages-1)); j--) {
92                         if( !page_is_free(j) ) {
93                                 i = j - 1;
94                                 break;
95                         }
96                 }
97                 if( j == (i-(npages-1)-1)) {
98                         first = j+1;
99                         break;
100                 }
101         }
102         //If we couldn't find them, return NULL
103         if( first == -1 ) {
104                 spin_unlock_irqsave(&colored_page_free_list_lock);
105                 return NULL;
106         }
107
108         for(int i=0; i<npages; i++) {
109                 page_t* page;
110                 __page_alloc_specific(&page, first+i);
111                 page_incref(page); 
112         }
113         spin_unlock_irqsave(&colored_page_free_list_lock);
114         return ppn2kva(first);
115 }
116
117 void free_cont_pages(void *buf, size_t order)
118 {
119         size_t npages = 1 << order;     
120         spin_lock_irqsave(&colored_page_free_list_lock);
121         for (int i = kva2ppn(buf); i < kva2ppn(buf) + npages; i++) {
122                 __page_decref(ppn2page(i));
123                 assert(page_is_free(i));
124         }
125         spin_unlock_irqsave(&colored_page_free_list_lock);
126         return; 
127 }
128
129 /*
130  * This macro defines multiple functions of the form:
131  * error_t _cache##_page_alloc(page_t** page, size_t color)
132  *
133  * Each of these functions operates on a different level of 
134  * of the cache heirarchy, and allocates a physical page
135  * from the list of pages corresponding to the supplied 
136  * color for the given cache.  
137  * 
138  * Does NOT set the contents of the physical page to zero -
139  * the caller must do that if necessary.
140  *
141  * color       -- the color from which to allocate a page
142  * *page       -- is set to point to the Page struct 
143  *                of the newly allocated page
144  *
145  * RETURNS 
146  *   ESUCCESS  -- on success
147  *   -ENOMEM   -- otherwise 
148  *
149  * error_t _cache##_page_alloc(page_t** page, size_t color)
150  * {
151  *       if(!LIST_EMPTY(&(_cache##_cache_colored_page_list)[(color)])) {
152  *        *(page) = LIST_FIRST(&(_cache##_cache_colored_page_list)[(color)]);
153  *               LIST_REMOVE(*page, global_link);
154  *               REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LISTS(page);
155  *               page_clear(*page);
156  *               return ESUCCESS;
157  *       }
158  *       return -ENOMEM;
159  * }
160  */
161 error_t l1_page_alloc(page_t** page, size_t color)
162 {
163         if(available_caches.l1)
164         {
165                 uint16_t range = llc_num_colors / get_cache_num_page_colors(&l1);
166                 uint16_t base_color = color*range;
167                 return page_alloc_from_color_range(page, base_color, range);
168         }
169         return -ENOCACHE;
170 }
171
172 error_t l2_page_alloc(page_t** page, size_t color)
173 {
174         if(available_caches.l2)
175         {
176                 uint16_t range = llc_num_colors / get_cache_num_page_colors(&l2);
177                 uint16_t base_color = color*range;
178                 return page_alloc_from_color_range(page, base_color, range);
179         }
180         return -ENOCACHE;
181 }
182
183 error_t l3_page_alloc(page_t** page, size_t color)
184 {
185         if(available_caches.l3)
186         {
187                 uint16_t range = llc_num_colors / get_cache_num_page_colors(&l3);
188                 uint16_t base_color = color*range;
189                 return page_alloc_from_color_range(page, base_color, range);
190         }
191         return -ENOCACHE;
192 }
193
194 /* Internal version of page_alloc_specific.  Grab the lock first. */
195 static error_t __page_alloc_specific(page_t** page, size_t ppn)
196 {
197         page_t* sp_page = ppn2page(ppn);
198         if( sp_page->page_ref != 0 )
199                 return -ENOMEM;
200         *page = sp_page;
201         LIST_REMOVE(*page, page_link);
202
203         page_clear(*page);
204         return 0;
205 }
206
207 /*
208  * Allocates a specific physical page.
209  * Does NOT set the contents of the physical page to zero -
210  * the caller must do that if necessary.
211  *
212  * ppn         -- the page number to allocate
213  * *page       -- is set to point to the Page struct 
214  *                of the newly allocated page
215  *
216  * RETURNS 
217  *   ESUCCESS  -- on success
218  *   -ENOMEM   -- otherwise 
219  */
220 error_t page_alloc_specific(page_t** page, size_t ppn)
221 {
222         spin_lock_irqsave(&colored_page_free_list_lock);
223         __page_alloc_specific(page, ppn);
224         spin_unlock_irqsave(&colored_page_free_list_lock);
225         return 0;
226 }
227
228 /*
229  * Return a page to the free list.
230  * (This function should only be called when pp->page_ref reaches 0.)
231  * You must hold the page_free list lock before calling this.
232  */
233 static error_t __page_free(page_t* page) 
234 {
235         page_clear(page);
236         cache_t* llc = available_caches.llc;
237
238         LIST_INSERT_HEAD(
239            &(colored_page_free_list[get_page_color(page2ppn(page), llc)]),
240            page,
241            page_link
242         );
243
244         return ESUCCESS;
245 }
246
247 error_t page_free(page_t *SAFE page)
248 {
249         error_t retval;
250         spin_lock_irqsave(&colored_page_free_list_lock);
251         retval = __page_free(page);
252         spin_unlock_irqsave(&colored_page_free_list_lock);
253         return retval;
254 }
255
256 /*
257  * Check if a page with the given pyhysical page # is free
258  */
259 int page_is_free(size_t ppn) {
260         page_t* page = ppn2page(ppn);
261         if( page->page_ref == 0 )
262                 return TRUE;
263         return FALSE;
264 }
265
266 /*
267  * Increment the reference count on a page
268  */
269 void page_incref(page_t *page)
270 {
271         page->page_ref++;
272 }
273
274 /*
275  * Decrement the reference count on a page,
276  * freeing it if there are no more refs.
277  */
278 void page_decref(page_t *page)
279 {
280         spin_lock_irqsave(&colored_page_free_list_lock);
281         __page_decref(page);
282         spin_unlock_irqsave(&colored_page_free_list_lock);
283 }
284
285 /*
286  * Decrement the reference count on a page,
287  * freeing it if there are no more refs.
288  */
289 static void __page_decref(page_t *page)
290 {
291         if (--page->page_ref == 0)
292                 __page_free(page);
293 }
294
295 /*
296  * Set the reference count on a page to a specific value
297  */
298 void page_setref(page_t *page, size_t val)
299 {
300         page->page_ref = val;
301 }
302
303 /*
304  * Get the reference count on a page
305  */
306 size_t page_getref(page_t *page)
307 {
308         return page->page_ref;
309 }
310