kthread_usleep()
[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 <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 /* Initializes a page.  We can optimize this a bit since 0 usually works to init
48  * most structures, but we'll hold off on that til it is a problem. */
49 static void __page_init(struct page *page)
50 {
51         memset(page, 0, sizeof(page_t));
52         page_setref(page, 1);
53         sem_init(&page->pg_sem, 0);
54 }
55
56 #define __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, predicate) \
57         /* Find first available color with pages available */                   \
58     /* in the given range */                                                \
59         int i = base_color;                                                     \
60         for (i; i < (base_color+range); i++) {                                  \
61                 if((predicate))                                                     \
62                         break;                                                          \
63         }                                                                       \
64         /* Allocate a page from that color */                                   \
65         if(i < (base_color+range)) {                                            \
66                 *page = LIST_FIRST(&colored_page_free_list[i]);                     \
67                 LIST_REMOVE(*page, pg_link);                                        \
68                 __page_init(*page);                                                 \
69                 return i;                                                           \
70         }                                                                       \
71         return -ENOMEM;
72
73 static ssize_t __page_alloc_from_color_range(page_t** page,  
74                                            uint16_t base_color,
75                                            uint16_t range) 
76 {
77         __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
78                          !LIST_EMPTY(&colored_page_free_list[i]));
79 }
80
81 static ssize_t __page_alloc_from_color_map_range(page_t** page, uint8_t* map, 
82                                               size_t base_color, size_t range)
83 {  
84         __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
85                     GET_BITMASK_BIT(map, i) && !LIST_EMPTY(&colored_page_free_list[i]))
86 }
87
88 static ssize_t __colored_page_alloc(uint8_t* map, page_t** page, 
89                                                size_t next_color)
90 {
91         ssize_t ret;
92         if((ret = __page_alloc_from_color_map_range(page, map, 
93                                    next_color, llc_cache->num_colors - next_color)) < 0)
94                 ret = __page_alloc_from_color_map_range(page, map, 0, next_color);
95         return ret;
96 }
97
98 static void __real_page_alloc(struct page *page)
99 {
100         LIST_REMOVE(page, pg_link);
101         __page_init(page);
102 }
103
104 /* Internal version of page_alloc_specific.  Grab the lock first. */
105 static error_t __page_alloc_specific(page_t** page, size_t ppn)
106 {
107         page_t* sp_page = ppn2page(ppn);
108         if (!page_is_free(ppn))
109                 return -ENOMEM;
110         *page = sp_page;
111         __real_page_alloc(sp_page);
112         return 0;
113 }
114
115 /**
116  * @brief Allocates a physical page from a pool of unused physical memory.
117  * Note, the page IS reference counted.
118  *
119  * Zeroes the page.
120  *
121  * @param[out] page  set to point to the Page struct
122  *                   of the newly allocated page
123  *
124  * @return ESUCCESS on success
125  * @return -ENOMEM  otherwise
126  */
127 error_t upage_alloc(struct proc* p, page_t** page, int zero)
128 {
129         spin_lock_irqsave(&colored_page_free_list_lock);
130         ssize_t ret = __colored_page_alloc(p->cache_colors_map, 
131                                              page, p->next_cache_color);
132         spin_unlock_irqsave(&colored_page_free_list_lock);
133
134         if (ret >= 0) {
135                 if(zero)
136                         memset(page2kva(*page),0,PGSIZE);
137                 p->next_cache_color = (ret + 1) & (llc_cache->num_colors-1);
138                 return 0;
139         }
140         return ret;
141 }
142
143 /* Allocates a refcounted page of memory for the kernel's use */
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                 ret = ESUCCESS;
155         }
156         spin_unlock_irqsave(&colored_page_free_list_lock);
157         
158         return ret;
159 }
160
161 /* Helper: allocates a refcounted page of memory for the kernel's use and
162  * returns the kernel address (kernbase), or 0 on error. */
163 void *kpage_alloc_addr(void)
164 {
165         struct page *a_page;
166         if (kpage_alloc(&a_page))
167                 return 0;
168         return page2kva(a_page);
169 }
170
171 void *kpage_zalloc_addr(void)
172 {
173         void *retval = kpage_alloc_addr();
174         if (retval)
175                 memset(retval, 0, PGSIZE);
176         return retval;
177 }
178
179 /**
180  * @brief Allocated 2^order contiguous physical pages.  Will increment the
181  * reference count for the pages.
182  *
183  * @param[in] order order of the allocation
184  * @param[in] flags memory allocation flags
185  *
186  * @return The KVA of the first page, NULL otherwise.
187  */
188 void *get_cont_pages(size_t order, int flags)
189 {
190         size_t npages = 1 << order;     
191
192         size_t naddrpages = max_paddr / PGSIZE;
193         // Find 'npages' free consecutive pages
194         int first = -1;
195         spin_lock_irqsave(&colored_page_free_list_lock);
196         for(int i=(naddrpages-1); i>=(npages-1); i--) {
197                 int j;
198                 for(j=i; j>=(i-(npages-1)); j--) {
199                         if( !page_is_free(j) ) {
200                                 i = j - 1;
201                                 break;
202                         }
203                 }
204                 if( j == (i-(npages-1)-1)) {
205                         first = j+1;
206                         break;
207                 }
208         }
209         //If we couldn't find them, return NULL
210         if( first == -1 ) {
211                 spin_unlock_irqsave(&colored_page_free_list_lock);
212                 return NULL;
213         }
214
215         for(int i=0; i<npages; i++) {
216                 page_t* page;
217                 __page_alloc_specific(&page, first+i);
218         }
219         spin_unlock_irqsave(&colored_page_free_list_lock);
220         return ppn2kva(first);
221 }
222
223 /**
224  * @brief Allocated 2^order contiguous physical pages.  Will increment the
225  * reference count for the pages. Get them from NUMA node node.
226  *
227  * @param[in] node which node to allocate from. Unimplemented.
228  * @param[in] order order of the allocation
229  * @param[in] flags memory allocation flags
230  *
231  * @return The KVA of the first page, NULL otherwise.
232  */
233 void *get_cont_pages_node(int node, size_t order, int flags)
234 {
235         return get_cont_pages(order, flags);
236 }
237
238 /**
239  * @brief Allocated 2^order contiguous physical pages starting at paddr 'at'.
240  * Will increment the reference count for the pages.
241  *
242  * We might need some restrictions on size of the alloc and its 'at' alignment.
243  * For instance, for a future buddy allocator (if we go that route), it might be
244  * easier if the order was aligned to the 'at'.  e.g., a 1GB alloc must be at a
245  * 1GB aligned addr.  A 2GB alloc would not be allowed at a merely 1GB
246  * alignment.
247  *
248  * For now, anything goes.  Note that the request is for a physical starting
249  * point, but the return is the KVA.
250  *
251  * @param[in] order order of the allocation
252  * @param[in] at starting address
253  * @param[in] flags memory allocation flags
254  *
255  * @return The KVA of the first page, NULL otherwise.
256  */
257 void *get_cont_phys_pages_at(size_t order, physaddr_t at, int flags)
258 {
259         unsigned long nr_pgs = 1 << order;
260         unsigned long first_pg_nr = pa2ppn(at);
261
262         if (first_pg_nr + nr_pgs > pa2ppn(max_paddr))
263                 return 0;
264         spin_lock_irqsave(&colored_page_free_list_lock);
265         for (unsigned long i = first_pg_nr; i < first_pg_nr + nr_pgs; i++) {
266                 if (!page_is_free(i)) {
267                         spin_unlock_irqsave(&colored_page_free_list_lock);
268                         return 0;
269                 }
270         }
271         for (unsigned long i = first_pg_nr; i < first_pg_nr + nr_pgs; i++)
272                 __real_page_alloc(ppn2page(i));
273         spin_unlock_irqsave(&colored_page_free_list_lock);
274         return KADDR(at);
275 }
276
277 void free_cont_pages(void *buf, size_t order)
278 {
279         size_t npages = 1 << order;     
280         spin_lock_irqsave(&colored_page_free_list_lock);
281         for (size_t i = kva2ppn(buf); i < kva2ppn(buf) + npages; i++) {
282                 page_t* page = ppn2page(i);
283                 __page_decref(ppn2page(i));
284                 assert(page_is_free(i));
285         }
286         spin_unlock_irqsave(&colored_page_free_list_lock);
287         return; 
288 }
289
290 /*
291  * Allocates a specific physical page.
292  * Does NOT set the contents of the physical page to zero -
293  * the caller must do that if necessary.
294  *
295  * ppn         -- the page number to allocate
296  * *page       -- is set to point to the Page struct 
297  *                of the newly allocated page
298  *
299  * RETURNS 
300  *   ESUCCESS  -- on success
301  *   -ENOMEM   -- otherwise 
302  */
303 error_t upage_alloc_specific(struct proc* p, page_t** page, size_t ppn)
304 {
305         spin_lock_irqsave(&colored_page_free_list_lock);
306         __page_alloc_specific(page, ppn);
307         spin_unlock_irqsave(&colored_page_free_list_lock);
308         return 0;
309 }
310
311 error_t kpage_alloc_specific(page_t** page, size_t ppn)
312 {
313         spin_lock_irqsave(&colored_page_free_list_lock);
314         __page_alloc_specific(page, ppn);
315         spin_unlock_irqsave(&colored_page_free_list_lock);
316         return 0;
317 }
318
319 /* Check if a page with the given physical page # is free. */
320 int page_is_free(size_t ppn) {
321         page_t* page = ppn2page(ppn);
322         if (kref_refcnt(&page->pg_kref))
323                 return FALSE;
324         return TRUE;
325 }
326
327 /*
328  * Increment the reference count on a page
329  */
330 void page_incref(page_t *page)
331 {
332         kref_get(&page->pg_kref, 1);
333 }
334
335 /* Decrement the reference count on a page, freeing it if there are no more
336  * refs. */
337 void page_decref(page_t *page)
338 {
339         spin_lock_irqsave(&colored_page_free_list_lock);
340         __page_decref(page);
341         spin_unlock_irqsave(&colored_page_free_list_lock);
342 }
343
344 /* Decrement the reference count on a page, freeing it if there are no more
345  * refs.  Don't call this without holding the lock already. */
346 static void __page_decref(page_t *page)
347 {
348         kref_put(&page->pg_kref);
349 }
350
351 /* Kref release function. */
352 static void page_release(struct kref *kref)
353 {
354         struct page *page = container_of(kref, struct page, pg_kref);
355
356         if (atomic_read(&page->pg_flags) & PG_BUFFER)
357                 free_bhs(page);
358         /* Give our page back to the free list.  The protections for this are that
359          * the list lock is grabbed by page_decref. */
360         LIST_INSERT_HEAD(
361            &(colored_page_free_list[get_page_color(page2ppn(page), llc_cache)]),
362            page,
363            pg_link
364         );
365 }
366
367 /* Helper when initializing a page - just to prevent the proliferation of
368  * page_release references (and because this function is sitting around in the
369  * code).  Sets the reference count on a page to a specific value, usually 1. */
370 void page_setref(page_t *page, size_t val)
371 {
372         kref_init(&page->pg_kref, page_release, val); 
373 }
374
375 /* Attempts to get a lock on the page for IO operations.  If it is already
376  * locked, it will block the kthread until it is unlocked.  Note that this is
377  * really a "sleep on some event", not necessarily the IO, but it is "the page
378  * is ready". */
379 void lock_page(struct page *page)
380 {
381         /* when this returns, we have are the ones to have locked the page */
382         sem_down(&page->pg_sem);
383         assert(!(atomic_read(&page->pg_flags) & PG_LOCKED));
384         atomic_or(&page->pg_flags, PG_LOCKED);
385 }
386
387 /* Unlocks the page, and wakes up whoever is waiting on the lock */
388 void unlock_page(struct page *page)
389 {
390         atomic_and(&page->pg_flags, ~PG_LOCKED);
391         sem_up(&page->pg_sem);
392 }
393
394 void print_pageinfo(struct page *page)
395 {
396         int i;
397         if (!page) {
398                 printk("Null page\n");
399                 return;
400         }
401         printk("Page %d (%p), Flags: 0x%08x Refcnt: %d\n", page2ppn(page),
402                page2kva(page), atomic_read(&page->pg_flags),
403                kref_refcnt(&page->pg_kref));
404         if (page->pg_mapping) {
405                 printk("\tMapped into object %p at index %d\n",
406                        page->pg_mapping->pm_host, page->pg_index);
407         }
408         if (atomic_read(&page->pg_flags) & PG_BUFFER) {
409                 struct buffer_head *bh = (struct buffer_head*)page->pg_private;
410                 i = 0;
411                 while (bh) {
412                         printk("\tBH %d: buffer: %p, sector: %d, nr_sector: %d\n", i,
413                                bh->bh_buffer, bh->bh_sector, bh->bh_nr_sector);
414                         i++;
415                         bh = bh->bh_next;
416                 }
417                 printk("\tPage is %sup to date\n",
418                        atomic_read(&page->pg_flags) & PG_UPTODATE ? "" : "not ");
419         }
420         printk("\tPage is %slocked\n",
421                atomic_read(&page->pg_flags) & PG_LOCKED ? "" : "un");
422         printk("\tPage is %s\n",
423                atomic_read(&page->pg_flags) & PG_DIRTY ? "dirty" : "clean");
424 }