pintos-os.org Git - pintos-anon/blob - src/threads/palloc.c

   1 #include "threads/palloc.h"
   2 #include <bitmap.h>
   3 #include <debug.h>
   4 #include <inttypes.h>
   5 #include <round.h>
   6 #include <stddef.h>
   7 #include <stdint.h>
   8 #include <stdio.h>
   9 #include <string.h>
  10 #include "threads/loader.h"
  11 #include "threads/synch.h"
  12 #include "threads/vaddr.h"
  13
  14 /* Page allocator.  Hands out memory in page-size (or
  15    page-multiple) chunks.  See malloc.h for an allocator that
  16    hands out smaller chunks.
  17
  18    System memory is divided into two "pools" called the kernel
  19    and user pools.  The user pool is for user (virtual) memory
  20    pages, the kernel pool for everything else.  The idea here is
  21    that the kernel needs to have memory for its own operations
  22    even if user processes are swapping like mad.
  23
  24    By default, half of system RAM is given to the kernel pool and
  25    half to the user pool.  That should be huge overkill for the
  26    kernel pool, but that's just fine for demonstration purposes. */
  27
  28 /* A memory pool. */
  29 struct pool
  30   {
  31     struct lock lock;                   /* Mutual exclusion. */
  32     struct bitmap *used_map;            /* Bitmap of free pages. */
  33     uint8_t *base;                      /* Base of pool. */
  34   };
  35
  36 /* Two pools: one for kernel data, one for user pages. */
  37 static struct pool kernel_pool, user_pool;
  38
  39 static void init_pool (struct pool *, void *base, size_t page_cnt,
  40                        const char *name);
  41 static bool page_from_pool (const struct pool *, void *page);
  42 static void page_set_cache(void* page, bool enable_cache);
  43
  44 /* Initializes the page allocator.  At most USER_PAGE_LIMIT
  45    pages are put into the user pool. */
  46 void
  47 palloc_init (size_t user_page_limit)
  48 {
  49   /* Free memory starts at 1 MB and runs to the end of RAM. */
  50   uint8_t *free_start = ptov (1024 * 1024);
  51   uint8_t *free_end = ptov (init_ram_pages * PGSIZE);
  52   size_t free_pages = (free_end - free_start) / PGSIZE;
  53   size_t user_pages = free_pages / 2;
  54   size_t kernel_pages;
  55   if (user_pages > user_page_limit)
  56     user_pages = user_page_limit;
  57   kernel_pages = free_pages - user_pages;
  58
  59   /* Give half of memory to kernel, half to user. */
  60   init_pool (&kernel_pool, free_start, kernel_pages, "kernel pool");
  61   init_pool (&user_pool, free_start + kernel_pages * PGSIZE,
  62              user_pages, "user pool");
  63 }
  64
  65 /* Obtains and returns a group of PAGE_CNT contiguous free pages.
  66    If PAL_USER is set, the pages are obtained from the user pool,
  67    otherwise from the kernel pool.  If PAL_ZERO is set in FLAGS,
  68    then the pages are filled with zeros.  If too few pages are
  69    available, returns a null pointer, unless PAL_ASSERT is set in
  70    FLAGS, in which case the kernel panics. */
  71 void *
  72 palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)
  73 {
  74   struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
  75   void *pages;
  76   size_t page_idx;
  77
  78   if (page_cnt == 0)
  79     return NULL;
  80
  81   lock_acquire (&pool->lock);
  82   page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false);
  83   lock_release (&pool->lock);
  84
  85   if (page_idx != BITMAP_ERROR)
  86     pages = pool->base + PGSIZE * page_idx;
  87   else
  88     pages = NULL;
  89
  90   if (pages != NULL)
  91     {
  92       if (flags & PAL_ZERO)
  93         memset (pages, 0, PGSIZE * page_cnt);
  94     }
  95   else
  96     {
  97       if (flags & PAL_ASSERT)
  98         PANIC ("palloc_get: out of pages");
  99     }
 100
 101   return pages;
 102 }
 103
 104 /* Obtains a single free page and returns its kernel virtual
 105    address.
 106    If PAL_USER is set, the page is obtained from the user pool,
 107    otherwise from the kernel pool.  If PAL_ZERO is set in FLAGS,
 108    then the page is filled with zeros.  If no pages are
 109    available, returns a null pointer, unless PAL_ASSERT is set in
 110    FLAGS, in which case the kernel panics. */
 111 void *
 112 palloc_get_page (enum palloc_flags flags)
 113 {
 114   return palloc_get_multiple (flags, 1);
 115 }
 116
 117 /* Frees the PAGE_CNT pages starting at PAGES. */
 118 void
 119 palloc_free_multiple (void *pages, size_t page_cnt)
 120 {
 121   struct pool *pool;
 122   size_t page_idx;
 123
 124   ASSERT (pg_ofs (pages) == 0);
 125   if (pages == NULL || page_cnt == 0)
 126     return;
 127
 128   if (page_from_pool (&kernel_pool, pages))
 129     pool = &kernel_pool;
 130   else if (page_from_pool (&user_pool, pages))
 131     pool = &user_pool;
 132   else
 133     NOT_REACHED ();
 134
 135   page_idx = pg_no (pages) - pg_no (pool->base);
 136
 137 #ifndef NDEBUG
 138   memset (pages, 0xcc, PGSIZE * page_cnt);
 139 #endif
 140
 141   ASSERT (bitmap_all (pool->used_map, page_idx, page_cnt));
 142   bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false);
 143 }
 144
 145 /* Frees the page at PAGE. */
 146 void
 147 palloc_free_page (void *page)
 148 {
 149   palloc_free_multiple (page, 1);
 150 }
 151
 152 /* Initializes pool P as starting at START and ending at END,
 153    naming it NAME for debugging purposes. */
 154 static void
 155 init_pool (struct pool *p, void *base, size_t page_cnt, const char *name)
 156 {
 157   /* We'll put the pool's used_map at its base.
 158      Calculate the space needed for the bitmap
 159      and subtract it from the pool's size. */
 160   size_t bm_pages = DIV_ROUND_UP (bitmap_buf_size (page_cnt), PGSIZE);
 161   if (bm_pages > page_cnt)
 162     PANIC ("Not enough memory in %s for bitmap.", name);
 163   page_cnt -= bm_pages;
 164
 165   printf ("%zu pages available in %s.\n", page_cnt, name);
 166
 167   /* Initialize the pool. */
 168   lock_init (&p->lock);
 169   p->used_map = bitmap_create_in_buf (page_cnt, base, bm_pages * PGSIZE);
 170   p->base = base + bm_pages * PGSIZE;
 171 }
 172
 173 /* Returns true if PAGE was allocated from POOL,
 174    false otherwise. */
 175 static bool
 176 page_from_pool (const struct pool *pool, void *page)
 177 {
 178   size_t page_no = pg_no (page);
 179   size_t start_page = pg_no (pool->base);
 180   size_t end_page = start_page + bitmap_size (pool->used_map);
 181
 182   return page_no >= start_page && page_no < end_page;
 183 }