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