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 <round.h>
   5 #include <stddef.h>
   6 #include <stdint.h>
   7 #include <stdio.h>
   8 #include <string.h>
   9 #include "threads/init.h"
  10 #include "threads/loader.h"
  11 #include "threads/mmu.h"
  12 #include "threads/synch.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 *start, *end;               /* Start and end of pool. */
  34   };
  35
  36 /* Two pools: one for kernel data, one for user pages. */
  37 struct pool kernel_pool, user_pool;
  38
  39 static void init_pool (struct pool *, void *start, void *end,
  40                        const char *name);
  41 static bool page_from_pool (const struct pool *, void *page);
  42
  43 /* Initializes the page allocator. */
  44 void
  45 palloc_init (void)
  46 {
  47   /* End of the kernel as recorded by the linker.
  48      See kernel.lds.S. */
  49   extern char _end;
  50
  51   /* Free memory. */
  52   uint8_t *free_start = pg_round_up (&_end);
  53   uint8_t *free_end = ptov (ram_pages * PGSIZE);
  54   size_t free_pages = (free_end - free_start) / PGSIZE;
  55   uint8_t *free_middle = free_start + free_pages / 2 * PGSIZE;
  56
  57   /* Give half of memory to kernel, half to user. */
  58   init_pool (&kernel_pool, free_start, free_middle, "kernel pool");
  59   init_pool (&user_pool, free_middle, free_end, "user pool");
  60 }
  61
  62 /* Obtains and returns a group of PAGE_CNT contiguous free pages.
  63    If PAL_USER is set, the pages are obtained from the user pool,
  64    otherwise from the kernel pool.  If PAL_ZERO is set in FLAGS,
  65    then the pages are filled with zeros.  If too few pages are
  66    available, returns a null pointer, unless PAL_ASSERT is set in
  67    FLAGS, in which case the kernel panics. */
  68 void *
  69 palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)
  70 {
  71   struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
  72   void *pages;
  73   size_t page_idx;
  74
  75   if (page_cnt == 0)
  76     return NULL;
  77
  78   lock_acquire (&pool->lock);
  79
  80   page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false);
  81   if (page_idx != BITMAP_ERROR)
  82     pages = pool->start + PGSIZE * page_idx;
  83   else
  84     pages = NULL;
  85
  86   if (pages != NULL)
  87     {
  88       if (flags & PAL_ZERO)
  89         memset (pages, 0, PGSIZE * page_cnt);
  90     }
  91   else
  92     {
  93       if (flags & PAL_ASSERT)
  94         PANIC ("palloc_get: out of pages");
  95     }
  96
  97   lock_release (&pool->lock);
  98
  99   return pages;
 100 }
 101
 102 /* Obtains and returns a single free page.
 103    If PAL_USER is set, the page is obtained from the user pool,
 104    otherwise from the kernel pool.  If PAL_ZERO is set in FLAGS,
 105    then the page is filled with zeros.  If no pages are
 106    available, returns a null pointer, unless PAL_ASSERT is set in
 107    FLAGS, in which case the kernel panics. */
 108 void *
 109 palloc_get_page (enum palloc_flags flags)
 110 {
 111   return palloc_get_multiple (flags, 1);
 112 }
 113
 114 /* Frees the PAGE_CNT pages starting at PAGES. */
 115 void
 116 palloc_free_multiple (void *pages, size_t page_cnt)
 117 {
 118   struct pool *pool;
 119   size_t page_idx;
 120
 121   ASSERT (pg_ofs (pages) == 0);
 122   if (pages == NULL || page_cnt == 0)
 123     return;
 124
 125   if (page_from_pool (&kernel_pool, pages))
 126     pool = &kernel_pool;
 127   else if (page_from_pool (&user_pool, pages))
 128     pool = &user_pool;
 129   else
 130     NOT_REACHED ();
 131
 132   page_idx = pg_no (pages) - pg_no (pool->start);
 133   ASSERT (pg_no (pages) + page_cnt <= pg_no (pool->end));
 134
 135 #ifndef NDEBUG
 136   memset (pages, 0xcc, PGSIZE * page_cnt);
 137 #endif
 138
 139   lock_acquire (&pool->lock);
 140   ASSERT (bitmap_all (pool->used_map, page_idx, page_idx + page_cnt));
 141   bitmap_set_multiple (pool->used_map, page_idx, page_idx + page_cnt, false);
 142   lock_release (&pool->lock);
 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 *start, void *end, const char *name)
 156 {
 157   size_t bitmap_size;
 158   size_t page_cnt;
 159
 160   ASSERT (pg_ofs (start) == 0);
 161   ASSERT (pg_ofs (end) == 0);
 162   ASSERT (end > start);
 163
 164   page_cnt = pg_no (end) - pg_no (start);
 165   printf ("%d kB allocated for %s.\n", (PGSIZE / 1024) * page_cnt, name);
 166
 167   lock_init (&p->lock, name);
 168   bitmap_size = ROUND_UP (bitmap_needed_bytes (page_cnt), PGSIZE);
 169   p->used_map = bitmap_create_preallocated (page_cnt, start, bitmap_size);
 170   p->start = start + bitmap_size;
 171   p->end = end;
 172   ASSERT (p->end > p->start);
 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   uint8_t *page = page_;
 181
 182   return page >= pool->start && page < pool->end;
 183 }