Uses kref for struct page
[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 static error_t __page_free(page_t *CT(1) page);
27
28 #ifdef __CONFIG_PAGE_COLORING__
29 #define NUM_KERNEL_COLORS 8
30 #else
31 #define NUM_KERNEL_COLORS 1
32 #endif
33
34
35 // Global list of colors allocated to the general purpose memory allocator
36 uint8_t* global_cache_colors_map;
37 size_t global_next_color = 0;
38
39 void colored_page_alloc_init()
40 {
41         global_cache_colors_map = 
42                kmalloc(BYTES_FOR_BITMASK(llc_cache->num_colors), 0);
43         CLR_BITMASK(global_cache_colors_map, llc_cache->num_colors);
44         for(int i = 0; i < llc_cache->num_colors/NUM_KERNEL_COLORS; i++)
45                 cache_color_alloc(llc_cache, global_cache_colors_map);
46 }
47
48 /**
49  * @brief Clear a Page structure.
50  *
51  * The result has null links and 0 refcount.
52  * Note that the corresponding physical page is NOT initialized!
53  */
54 static void __page_clear(page_t *SAFE page)
55 {
56         memset(page, 0, sizeof(page_t));
57 }
58
59 #define __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, predicate) \
60         /* Find first available color with pages available */                   \
61     /* in the given range */                                                \
62         int i = base_color;                                                     \
63         for (i; i < (base_color+range); i++) {                                  \
64                 if((predicate))                                                     \
65                         break;                                                          \
66         }                                                                       \
67         /* Allocate a page from that color */                                   \
68         if(i < (base_color+range)) {                                            \
69                 *page = LIST_FIRST(&colored_page_free_list[i]);                     \
70                 LIST_REMOVE(*page, pg_link);                                        \
71                 __page_clear(*page);                                                \
72                 /* Note the 0 initial value, due to how user pages are refcnt'd */  \
73                 page_setref((*page), 0);                                            \
74                 return i;                                                           \
75         }                                                                       \
76         return -ENOMEM;
77
78 static ssize_t __page_alloc_from_color_range(page_t** page,  
79                                            uint16_t base_color,
80                                            uint16_t range) 
81 {
82         __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
83                          !LIST_EMPTY(&colored_page_free_list[i]));
84 }
85
86 static ssize_t __page_alloc_from_color_map_range(page_t** page, uint8_t* map, 
87                                               size_t base_color, size_t range)
88 {  
89         __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
90                     GET_BITMASK_BIT(map, i) && !LIST_EMPTY(&colored_page_free_list[i]))
91 }
92
93 static ssize_t __colored_page_alloc(uint8_t* map, page_t** page, 
94                                                size_t next_color)
95 {
96         ssize_t ret;
97         if((ret = __page_alloc_from_color_map_range(page, map, 
98                                    next_color, llc_cache->num_colors - next_color)) < 0)
99                 ret = __page_alloc_from_color_map_range(page, map, 0, next_color);
100         return ret;
101 }
102
103 /* Internal version of page_alloc_specific.  Grab the lock first. */
104 static error_t __page_alloc_specific(page_t** page, size_t ppn)
105 {
106         page_t* sp_page = ppn2page(ppn);
107         if (!page_is_free(ppn))
108                 return -ENOMEM;
109         *page = sp_page;
110         LIST_REMOVE(*page, pg_link);
111         __page_clear(*page);
112         /* Note the 0 initial value, due to how user pages are refcnt'd.  If you
113          * have a page, you need to kref_get it before you *use* it. */
114         page_setref(*page, 0);
115         return 0;
116 }
117
118 /**
119  * @brief Allocates a physical page from a pool of unused physical memory.
120  *
121  * Zeroes the page.
122  *
123  * @param[out] page  set to point to the Page struct
124  *                   of the newly allocated page
125  *
126  * @return ESUCCESS on success
127  * @return -ENOMEM  otherwise
128  */
129 error_t upage_alloc(struct proc* p, page_t** page, int zero)
130 {
131         spin_lock_irqsave(&colored_page_free_list_lock);
132         ssize_t ret = __colored_page_alloc(p->cache_colors_map, 
133                                              page, p->next_cache_color);
134         spin_unlock_irqsave(&colored_page_free_list_lock);
135
136         if (ret >= 0) {
137                 if(zero)
138                         memset(page2kva(*page),0,PGSIZE);
139                 p->next_cache_color = (ret + 1) & (llc_cache->num_colors-1);
140                 return 0;
141         }
142         return ret;
143 }
144
145 error_t kpage_alloc(page_t** page) 
146 {
147         ssize_t ret;
148         spin_lock_irqsave(&colored_page_free_list_lock);
149         if ((ret = __page_alloc_from_color_range(page, global_next_color, 
150                                     llc_cache->num_colors - global_next_color)) < 0)
151                 ret = __page_alloc_from_color_range(page, 0, global_next_color);
152
153         if (ret >= 0) {
154                 global_next_color = ret;        
155                 /* this is the "it's okay if it was 0" kref */
156                 __kref_get(&(*page)->pg_kref, 1);
157                 ret = ESUCCESS;
158         }
159         spin_unlock_irqsave(&colored_page_free_list_lock);
160         
161         return ret;
162 }
163
164 /**
165  * @brief Allocated 2^order contiguous physical pages.  Will increment the
166  * reference count for the pages.
167  *
168  * @param[in] order order of the allocation
169  * @param[in] flags memory allocation flags
170  *
171  * @return The KVA of the first page, NULL otherwise.
172  */
173 void *get_cont_pages(size_t order, int flags)
174 {
175         size_t npages = 1 << order;     
176
177         // Find 'npages' free consecutive pages
178         int first = -1;
179         spin_lock_irqsave(&colored_page_free_list_lock);
180         for(int i=(naddrpages-1); i>=(npages-1); i--) {
181                 int j;
182                 for(j=i; j>=(i-(npages-1)); j--) {
183                         if( !page_is_free(j) ) {
184                                 i = j - 1;
185                                 break;
186                         }
187                 }
188                 if( j == (i-(npages-1)-1)) {
189                         first = j+1;
190                         break;
191                 }
192         }
193         //If we couldn't find them, return NULL
194         if( first == -1 ) {
195                 spin_unlock_irqsave(&colored_page_free_list_lock);
196                 return NULL;
197         }
198
199         for(int i=0; i<npages; i++) {
200                 page_t* page;
201                 __page_alloc_specific(&page, first+i);
202                 __kref_get(&page->pg_kref, 1);
203         }
204         spin_unlock_irqsave(&colored_page_free_list_lock);
205         return ppn2kva(first);
206 }
207
208 void free_cont_pages(void *buf, size_t order)
209 {
210         size_t npages = 1 << order;     
211         spin_lock_irqsave(&colored_page_free_list_lock);
212         for (int i = kva2ppn(buf); i < kva2ppn(buf) + npages; i++) {
213                 __page_decref(ppn2page(i));
214                 assert(page_is_free(i));
215         }
216         spin_unlock_irqsave(&colored_page_free_list_lock);
217         return; 
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 upage_alloc_specific(struct proc* p, 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 error_t kpage_alloc_specific(page_t** page, size_t ppn)
242 {
243         spin_lock_irqsave(&colored_page_free_list_lock);
244         __page_alloc_specific(page, ppn);
245         page_incref(*page);
246         spin_unlock_irqsave(&colored_page_free_list_lock);
247         return 0;
248 }
249
250 /* Returns a page to the free list.
251  *
252  * This function should only be called when the refcnt reaches 0, meaning from
253  * page_release().
254  *
255  * You must hold the page_free list lock before calling this, which is
256  * accomplished via the page_decref locking hacks. */
257 static error_t __page_free(page_t* page) 
258 {
259         __page_clear(page);
260
261         LIST_INSERT_HEAD(
262            &(colored_page_free_list[get_page_color(page2ppn(page), llc_cache)]),
263            page,
264            pg_link
265         );
266
267         return ESUCCESS;
268 }
269
270 error_t page_free(page_t *SAFE page)
271 {
272         error_t retval;
273         spin_lock_irqsave(&colored_page_free_list_lock);
274         retval = __page_free(page);
275         spin_unlock_irqsave(&colored_page_free_list_lock);
276         return retval;
277 }
278
279 /* Check if a page with the given physical page # is free. */
280 int page_is_free(size_t ppn) {
281         page_t* page = ppn2page(ppn);
282         if (kref_refcnt(&page->pg_kref))
283                 return FALSE;
284         return TRUE;
285 }
286
287 /*
288  * Increment the reference count on a page
289  */
290 void page_incref(page_t *page)
291 {
292         __page_incref(page);
293 }
294
295 void __page_incref(page_t *page)
296 {
297         kref_get(&page->pg_kref, 1);
298 }
299
300 /* Decrement the reference count on a page, freeing it if there are no more
301  * refs. */
302 void page_decref(page_t *page)
303 {
304         spin_lock_irqsave(&colored_page_free_list_lock);
305         __page_decref(page);
306         spin_unlock_irqsave(&colored_page_free_list_lock);
307 }
308
309 /* Decrement the reference count on a page, freeing it if there are no more
310  * refs. */
311 static void __page_decref(page_t *page)
312 {
313         kref_put(&page->pg_kref);
314 }
315
316 /* Kref release function. */
317 static void page_release(struct kref *kref)
318 {
319         struct page *page = container_of(kref, struct page, pg_kref);
320         __page_free(page);
321 }
322
323 /* Helper when initializing a page - just to prevent the proliferation of
324  * page_release references (and because this function is sitting around in the
325  * code).  Sets the reference count on a page to a specific value, usually 1. */
326 void page_setref(page_t *page, size_t val)
327 {
328         kref_init(&page->pg_kref, page_release, val); 
329 }
330
331 /*
332  * Get the reference count on a page
333  */
334 size_t page_getref(page_t *page)
335 {
336         return kref_refcnt(&page->pg_kref);
337 }
338
339 /* Attempts to get a lock on the page for IO operations.  If it is already
340  * locked, it will block the thread until it is unlocked. */
341 void lock_page(struct page *page)
342 {
343         /* TODO: (BLK) actually do something!  And this has a race!  Not a big deal
344          * right now, since the only users of this are serialized, but once we have
345          * any sort of real IO, this will be an issue. */
346         assert(!(page->pg_flags & PG_LOCKED));
347         page->pg_flags |= PG_LOCKED;
348 }
349
350 /* Unlocks the page, and wakes up whoever is waiting on the lock */
351 void unlock_page(struct page *page)
352 {
353         /* TODO: (BLK) actually do something!  However this unlock works, it will
354          * need to know who to unlock, and it will have to be called in response to
355          * a basic interrupt...  */
356         page->pg_flags &= ~PG_LOCKED;
357 }