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 struct pool kernel_pool, user_pool;
  38
  39 /* Maximum number of pages to put in user pool. */
  40 size_t user_page_limit = SIZE_MAX;
  41
  42 static void init_pool (struct pool *, void *base, size_t page_cnt,
  43                        const char *name);
  44 static bool page_from_pool (const struct pool *, void *page);
  45 static void page_set_cache(void* page, bool enable_cache);
  46
  47 /* Initializes the page allocator. */
  48 void
  49 palloc_init (void)
  50 {
  51   /* Free memory starts at 1 MB and runs to the end of RAM. */
  52   uint8_t *free_start = ptov (1024 * 1024);
  53   uint8_t *free_end = ptov (ram_pages * PGSIZE);
  54   size_t free_pages = (free_end - free_start) / PGSIZE;
  55   size_t user_pages = free_pages / 2;
  56   size_t kernel_pages;
  57   if (user_pages > user_page_limit)
  58     user_pages = user_page_limit;
  59   kernel_pages = free_pages - user_pages;
  60
  61   /* Give half of memory to kernel, half to user. */
  62   init_pool (&kernel_pool, free_start, kernel_pages, "kernel pool");
  63   init_pool (&user_pool, free_start + kernel_pages * PGSIZE,
  64              user_pages, "user pool");
  65 }
  66
  67 /* Obtains and returns a group of PAGE_CNT contiguous free pages.
  68    If PAL_USER is set, the pages are obtained from the user pool,
  69    otherwise from the kernel pool.  If PAL_ZERO is set in FLAGS,
  70    then the pages are filled with zeros.  If too few pages are
  71    available, returns a null pointer, unless PAL_ASSERT is set in
  72    FLAGS, in which case the kernel panics. */
  73 void *
  74 palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)
  75 {
  76   struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
  77   void *pages;
  78   size_t page_idx;
  79
  80   if (page_cnt == 0)
  81     return NULL;
  82
  83   lock_acquire (&pool->lock);
  84   page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false);
  85   lock_release (&pool->lock);
  86
  87   if (page_idx != BITMAP_ERROR)
  88     pages = pool->base + PGSIZE * page_idx;
  89   else
  90     pages = NULL;
  91
  92   if (pages != NULL)
  93     {
  94       if (flags & PAL_ZERO)
  95         memset (pages, 0, PGSIZE * page_cnt);
  96     }
  97   else
  98     {
  99       if (flags & PAL_ASSERT)
 100         PANIC ("palloc_get: out of pages");
 101     }
 102
 103   return pages;
 104 }
 105
 106 /* Obtains a single free page and returns its kernel virtual
 107    address.
 108    If PAL_USER is set, the page is obtained from the user pool,
 109    otherwise from the kernel pool.  If PAL_ZERO is set in FLAGS,
 110    then the page is filled with zeros.  If no pages are
 111    available, returns a null pointer, unless PAL_ASSERT is set in
 112    FLAGS, in which case the kernel panics. */
 113 void *
 114 palloc_get_page (enum palloc_flags flags)
 115 {
 116   return palloc_get_multiple (flags, 1);
 117 }
 118
 119 /* Frees the PAGE_CNT pages starting at PAGES. */
 120 void
 121 palloc_free_multiple (void *pages, size_t page_cnt)
 122 {
 123   struct pool *pool;
 124   size_t page_idx;
 125
 126   ASSERT (pg_ofs (pages) == 0);
 127   if (pages == NULL || page_cnt == 0)
 128     return;
 129
 130   if (page_from_pool (&kernel_pool, pages))
 131     pool = &kernel_pool;
 132   else if (page_from_pool (&user_pool, pages))
 133     pool = &user_pool;
 134   else
 135     NOT_REACHED ();
 136
 137   page_idx = pg_no (pages) - pg_no (pool->base);
 138
 139 #ifndef NDEBUG
 140   memset (pages, 0xcc, PGSIZE * page_cnt);
 141 #endif
 142
 143   ASSERT (bitmap_all (pool->used_map, page_idx, page_cnt));
 144   bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false);
 145 }
 146
 147 /* Frees the page at PAGE. */
 148 void
 149 palloc_free_page (void *page)
 150 {
 151   palloc_free_multiple (page, 1);
 152 }
 153
 154 /* Initializes pool P as starting at START and ending at END,
 155    naming it NAME for debugging purposes. */
 156 static void
 157 init_pool (struct pool *p, void *base, size_t page_cnt, const char *name)
 158 {
 159   /* We'll put the pool's used_map at its base.
 160      Calculate the space needed for the bitmap
 161      and subtract it from the pool's size. */
 162   size_t bm_pages = DIV_ROUND_UP (bitmap_buf_size (page_cnt), PGSIZE);
 163   if (bm_pages > page_cnt)
 164     PANIC ("Not enough memory in %s for bitmap.", name);
 165   page_cnt -= bm_pages;
 166
 167   printf ("%zu pages available in %s.\n", page_cnt, name);
 168
 169   /* Initialize the pool. */
 170   lock_init (&p->lock);
 171   p->used_map = bitmap_create_in_buf (page_cnt, base, bm_pages * PGSIZE);
 172   p->base = base + bm_pages * PGSIZE;
 173 }
 174
 175 /* Returns true if PAGE was allocated from POOL,
 176    false otherwise. */
 177 static bool
 178 page_from_pool (const struct pool *pool, void *page)
 179 {
 180   size_t page_no = pg_no (page);
 181   size_t start_page = pg_no (pool->base);
 182   size_t end_page = start_page + bitmap_size (pool->used_map);
 183
 184   return page_no >= start_page && page_no < end_page;
 185 }