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