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