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