Cleaned up page_free()
[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 <arch/bitmask.h>
14 #include <page_alloc.h>
15 #include <pmap.h>
16 #include <string.h>
17 #include <kmalloc.h>
18
19 #define l1 (available_caches.l1)
20 #define l2 (available_caches.l2)
21 #define l3 (available_caches.l3)
22
23 static void __page_decref(page_t *CT(1) page);
24 static void __page_incref(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 /**
48  * @brief Clear a Page structure.
49  *
50  * The result has null links and 0 refcount.
51  * Note that the corresponding physical page is NOT initialized!
52  */
53 static void __page_clear(page_t *SAFE page)
54 {
55         memset(page, 0, sizeof(page_t));
56 }
57
58 #define __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, predicate) \
59         /* Find first available color with pages available */                   \
60     /* in the given range */                                                \
61         int i = base_color;                                                     \
62         for (i; i < (base_color+range); i++) {                                  \
63                 if((predicate))                                                     \
64                         break;                                                          \
65         }                                                                       \
66         /* Allocate a page from that color */                                   \
67         if(i < (base_color+range)) {                                            \
68                 *page = LIST_FIRST(&colored_page_free_list[i]);                     \
69                 LIST_REMOVE(*page, pg_link);                                        \
70                 __page_clear(*page);                                                \
71                 /* Note the 0 initial value, due to how user pages are refcnt'd */  \
72                 page_setref((*page), 0);                                            \
73                 return i;                                                           \
74         }                                                                       \
75         return -ENOMEM;
76
77 static ssize_t __page_alloc_from_color_range(page_t** page,  
78                                            uint16_t base_color,
79                                            uint16_t range) 
80 {
81         __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
82                          !LIST_EMPTY(&colored_page_free_list[i]));
83 }
84
85 static ssize_t __page_alloc_from_color_map_range(page_t** page, uint8_t* map, 
86                                               size_t base_color, size_t range)
87 {  
88         __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
89                     GET_BITMASK_BIT(map, i) && !LIST_EMPTY(&colored_page_free_list[i]))
90 }
91
92 static ssize_t __colored_page_alloc(uint8_t* map, page_t** page, 
93                                                size_t next_color)
94 {
95         ssize_t ret;
96         if((ret = __page_alloc_from_color_map_range(page, map, 
97                                    next_color, llc_cache->num_colors - next_color)) < 0)
98                 ret = __page_alloc_from_color_map_range(page, map, 0, next_color);
99         return ret;
100 }
101
102 /* Internal version of page_alloc_specific.  Grab the lock first. */
103 static error_t __page_alloc_specific(page_t** page, size_t ppn)
104 {
105         page_t* sp_page = ppn2page(ppn);
106         if (!page_is_free(ppn))
107                 return -ENOMEM;
108         *page = sp_page;
109         LIST_REMOVE(*page, pg_link);
110         __page_clear(*page);
111         /* Note the 0 initial value, due to how user pages are refcnt'd.  If you
112          * have a page, you need to kref_get it before you *use* it. */
113         page_setref(*page, 0);
114         return 0;
115 }
116
117 /**
118  * @brief Allocates a physical page from a pool of unused physical memory.
119  *
120  * Zeroes the page.
121  *
122  * @param[out] page  set to point to the Page struct
123  *                   of the newly allocated page
124  *
125  * @return ESUCCESS on success
126  * @return -ENOMEM  otherwise
127  */
128 error_t upage_alloc(struct proc* p, page_t** page, int zero)
129 {
130         spin_lock_irqsave(&colored_page_free_list_lock);
131         ssize_t ret = __colored_page_alloc(p->cache_colors_map, 
132                                              page, p->next_cache_color);
133         spin_unlock_irqsave(&colored_page_free_list_lock);
134
135         if (ret >= 0) {
136                 if(zero)
137                         memset(page2kva(*page),0,PGSIZE);
138                 p->next_cache_color = (ret + 1) & (llc_cache->num_colors-1);
139                 return 0;
140         }
141         return ret;
142 }
143
144 error_t kpage_alloc(page_t** page) 
145 {
146         ssize_t ret;
147         spin_lock_irqsave(&colored_page_free_list_lock);
148         if ((ret = __page_alloc_from_color_range(page, global_next_color, 
149                                     llc_cache->num_colors - global_next_color)) < 0)
150                 ret = __page_alloc_from_color_range(page, 0, global_next_color);
151
152         if (ret >= 0) {
153                 global_next_color = ret;        
154                 /* this is the "it's okay if it was 0" kref */
155                 __kref_get(&(*page)->pg_kref, 1);
156                 ret = ESUCCESS;
157         }
158         spin_unlock_irqsave(&colored_page_free_list_lock);
159         
160         return ret;
161 }
162
163 /**
164  * @brief Allocated 2^order contiguous physical pages.  Will increment the
165  * reference count for the pages.
166  *
167  * @param[in] order order of the allocation
168  * @param[in] flags memory allocation flags
169  *
170  * @return The KVA of the first page, NULL otherwise.
171  */
172 void *get_cont_pages(size_t order, int flags)
173 {
174         size_t npages = 1 << order;     
175
176         // Find 'npages' free consecutive pages
177         int first = -1;
178         spin_lock_irqsave(&colored_page_free_list_lock);
179         for(int i=(naddrpages-1); i>=(npages-1); i--) {
180                 int j;
181                 for(j=i; j>=(i-(npages-1)); j--) {
182                         if( !page_is_free(j) ) {
183                                 i = j - 1;
184                                 break;
185                         }
186                 }
187                 if( j == (i-(npages-1)-1)) {
188                         first = j+1;
189                         break;
190                 }
191         }
192         //If we couldn't find them, return NULL
193         if( first == -1 ) {
194                 spin_unlock_irqsave(&colored_page_free_list_lock);
195                 return NULL;
196         }
197
198         for(int i=0; i<npages; i++) {
199                 page_t* page;
200                 __page_alloc_specific(&page, first+i);
201                 __kref_get(&page->pg_kref, 1);
202         }
203         spin_unlock_irqsave(&colored_page_free_list_lock);
204         return ppn2kva(first);
205 }
206
207 void free_cont_pages(void *buf, size_t order)
208 {
209         size_t npages = 1 << order;     
210         spin_lock_irqsave(&colored_page_free_list_lock);
211         for (int i = kva2ppn(buf); i < kva2ppn(buf) + npages; i++) {
212                 __page_decref(ppn2page(i));
213                 assert(page_is_free(i));
214         }
215         spin_unlock_irqsave(&colored_page_free_list_lock);
216         return; 
217 }
218
219 /*
220  * Allocates a specific physical page.
221  * Does NOT set the contents of the physical page to zero -
222  * the caller must do that if necessary.
223  *
224  * ppn         -- the page number to allocate
225  * *page       -- is set to point to the Page struct 
226  *                of the newly allocated page
227  *
228  * RETURNS 
229  *   ESUCCESS  -- on success
230  *   -ENOMEM   -- otherwise 
231  */
232 error_t upage_alloc_specific(struct proc* p, page_t** page, size_t ppn)
233 {
234         spin_lock_irqsave(&colored_page_free_list_lock);
235         __page_alloc_specific(page, ppn);
236         spin_unlock_irqsave(&colored_page_free_list_lock);
237         return 0;
238 }
239
240 error_t kpage_alloc_specific(page_t** page, size_t ppn)
241 {
242         spin_lock_irqsave(&colored_page_free_list_lock);
243         __page_alloc_specific(page, ppn);
244         page_incref(*page);
245         spin_unlock_irqsave(&colored_page_free_list_lock);
246         return 0;
247 }
248
249 /* Check if a page with the given physical page # is free. */
250 int page_is_free(size_t ppn) {
251         page_t* page = ppn2page(ppn);
252         if (kref_refcnt(&page->pg_kref))
253                 return FALSE;
254         return TRUE;
255 }
256
257 /*
258  * Increment the reference count on a page
259  */
260 void page_incref(page_t *page)
261 {
262         __page_incref(page);
263 }
264
265 void __page_incref(page_t *page)
266 {
267         kref_get(&page->pg_kref, 1);
268 }
269
270 /* Decrement the reference count on a page, freeing it if there are no more
271  * refs. */
272 void page_decref(page_t *page)
273 {
274         spin_lock_irqsave(&colored_page_free_list_lock);
275         __page_decref(page);
276         spin_unlock_irqsave(&colored_page_free_list_lock);
277 }
278
279 /* Decrement the reference count on a page, freeing it if there are no more
280  * refs.  Don't call this without holding the lock already. */
281 static void __page_decref(page_t *page)
282 {
283         kref_put(&page->pg_kref);
284 }
285
286 /* Kref release function. */
287 static void page_release(struct kref *kref)
288 {
289         struct page *page = container_of(kref, struct page, pg_kref);
290
291         /* Probably issues with this, get rid of it on a future review */
292         __page_clear(page);
293         /* Give our page back to the free list.  The protections for this are that
294          * the list lock is grabbed by page_decref. */
295         LIST_INSERT_HEAD(
296            &(colored_page_free_list[get_page_color(page2ppn(page), llc_cache)]),
297            page,
298            pg_link
299         );
300 }
301
302 /* Helper when initializing a page - just to prevent the proliferation of
303  * page_release references (and because this function is sitting around in the
304  * code).  Sets the reference count on a page to a specific value, usually 1. */
305 void page_setref(page_t *page, size_t val)
306 {
307         kref_init(&page->pg_kref, page_release, val); 
308 }
309
310 /* Attempts to get a lock on the page for IO operations.  If it is already
311  * locked, it will block the thread until it is unlocked. */
312 void lock_page(struct page *page)
313 {
314         /* TODO: (BLK) actually do something!  And this has a race!  Not a big deal
315          * right now, since the only users of this are serialized, but once we have
316          * any sort of real IO, this will be an issue. */
317         assert(!(page->pg_flags & PG_LOCKED));
318         page->pg_flags |= PG_LOCKED;
319 }
320
321 /* Unlocks the page, and wakes up whoever is waiting on the lock */
322 void unlock_page(struct page *page)
323 {
324         /* TODO: (BLK) actually do something!  However this unlock works, it will
325          * need to know who to unlock, and it will have to be called in response to
326          * a basic interrupt...  */
327         page->pg_flags &= ~PG_LOCKED;
328 }