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