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

   1 #include "threads/palloc.h"
   2 #include <debug.h>
   3 #include <list.h>
   4 #include <stddef.h>
   5 #include <stdint.h>
   6 #include <stdio.h>
   7 #include <string.h>
   8 #include "threads/init.h"
   9 #include "threads/loader.h"
  10 #include "threads/mmu.h"
  11 #include "threads/synch.h"
  12
  13 /* Page allocator.  Hands out memory in page-size chunks.
  14    See malloc.h for an allocator that hands out smaller
  15    chunks.
  16
  17    System memory is divided into two "pools" called the kernel
  18    and user pools.  The user pool is for user (virtual) memory
  19    pages, the kernel pool for everything else.  The idea here is
  20    that the kernel needs to have memory for its own operations
  21    even if user processes are swapping like mad.
  22
  23    By default, half of system RAM is given to the kernel pool and
  24    half to the user pool.  That should be huge overkill for the
  25    kernel pool, but that's just fine for demonstration purposes.
  26
  27    Within each pool, we simply use a linked list of free pages.
  28    It would be straightforward to add all available memory to
  29    this free list at initialization time.  In practice, though,
  30    that's really slow because it causes the emulator we're
  31    running under to have to fault in every page of memory.  So
  32    instead we only add pages to the free list as needed. */
  33
  34 /* A free page owned by the page allocator. */
  35 struct page
  36   {
  37     list_elem elem;             /* Free list element. */
  38   };
  39
  40 /* A memory pool. */
  41 struct pool
  42   {
  43     struct lock lock;                   /* Mutual exclusion. */
  44     uint8_t *start, *end;               /* Start and end of pool. */
  45     uint8_t *uninit;                    /* First page not yet in free_list. */
  46     struct list free_list;              /* Free pages. */
  47   };
  48
  49 /* Two pools: one for kernel data, one for user pages. */
  50 struct pool kernel_pool, user_pool;
  51
  52 static void init_pool (struct pool *, void *start, void *end,
  53                        const char *name);
  54 static bool page_from_pool (const struct pool *, void *page);
  55
  56 /* Initializes the page allocator. */
  57 void
  58 palloc_init (void)
  59 {
  60   /* End of the kernel as recorded by the linker.
  61      See kernel.lds.S. */
  62   extern char _end;
  63
  64   /* Free memory. */
  65   uint8_t *free_start = pg_round_up (&_end);
  66   uint8_t *free_end = ptov (ram_pages * PGSIZE);
  67   size_t free_pages = (free_end - free_start) / PGSIZE;
  68   uint8_t *free_middle = free_start + free_pages / 2 * PGSIZE;
  69
  70   /* Give half of memory to kernel, half to user. */
  71   init_pool (&kernel_pool, free_start, free_middle, "kernel pool");
  72   init_pool (&user_pool, free_middle, free_end, "user pool");
  73 }
  74
  75 /* Obtains and returns a free page.  If PAL_USER is set, the page
  76    is obtained from the user pool, otherwise from the kernel
  77    pool.  If PAL_ZERO is set in FLAGS, then the page is filled
  78    with zeros.  If no pages are available, returns a null
  79    pointer, unless PAL_ASSERT is set in FLAGS, in which case the
  80    kernel panics. */
  81 void *
  82 palloc_get (enum palloc_flags flags)
  83 {
  84   struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
  85   struct page *page;
  86
  87   lock_acquire (&pool->lock);
  88
  89   /* If there's a page in the free list, take it.
  90      Otherwise, if there's a page not yet added to the free list,
  91      use it.
  92      Otherwise, we're out of memory. */
  93   if (!list_empty (&pool->free_list))
  94     page = list_entry (list_pop_front (&pool->free_list), struct page, elem);
  95   else if (pool->uninit < pool->end)
  96     {
  97       page = (struct page *) pool->uninit;
  98       pool->uninit += PGSIZE;
  99     }
 100   else
 101     page = NULL;
 102
 103   if (page != NULL)
 104     {
 105       if (flags & PAL_ZERO)
 106         memset (page, 0, PGSIZE);
 107     }
 108   else
 109     {
 110       if (flags & PAL_ASSERT)
 111         PANIC ("palloc_get: out of pages");
 112     }
 113
 114   lock_release (&pool->lock);
 115
 116   return page;
 117 }
 118
 119 /* Frees PAGE. */
 120 void
 121 palloc_free (void *page_)
 122 {
 123   struct pool *pool;
 124   struct page *page = page_;
 125
 126   ASSERT (page == pg_round_down (page));
 127   if (page_from_pool (&kernel_pool, page))
 128     pool = &kernel_pool;
 129   else if (page_from_pool (&user_pool, page))
 130     pool = &user_pool;
 131   else
 132     PANIC ("freeing invalid pointer");
 133
 134 #ifndef NDEBUG
 135   memset (page, 0xcc, PGSIZE);
 136 #endif
 137
 138   lock_acquire (&pool->lock);
 139   list_push_front (&pool->free_list, &page->elem);
 140   lock_release (&pool->lock);
 141 }
 142
 143 /* Initializes pool P as starting at START and ending at END,
 144    naming it NAME for debugging purposes. */
 145 static void
 146 init_pool (struct pool *p, void *start, void *end, const char *name)
 147 {
 148   ASSERT (pg_ofs (start) == 0);
 149   ASSERT (pg_ofs (end) == 0);
 150
 151   printf ("%d kB allocated for %s.\n",
 152           (PGSIZE / 1024) * (pg_no (end) - pg_no (start)), name);
 153
 154   lock_init (&p->lock, name);
 155   p->start = p->uninit = start;
 156   p->end = end;
 157   list_init (&p->free_list);
 158 }
 159
 160 /* Returns true if PAGE was allocated from POOL,
 161    false otherwise. */
 162 static bool
 163 page_from_pool (const struct pool *pool, void *page_)
 164 {
 165   uint8_t *page = page_;
 166
 167   return page >= pool->start && page < pool->uninit;
 168 }