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