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