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_ZERO is set in FLAGS,
  76    then the page is filled with zeros.  If no pages are
  77    available, returns a null pointer, unless PAL_ASSERT is set in
  78    FLAGS, in which case the kernel panics. */
  79 void *
  80 palloc_get (enum palloc_flags flags)
  81 {
  82   struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
  83   struct page *page;
  84
  85   lock_acquire (&pool->lock);
  86
  87   /* If there's a page in the free list, take it.
  88      Otherwise, if there's a page not yet added to the free list,
  89      use it.
  90      Otherwise, we're out of memory. */
  91   if (!list_empty (&pool->free_list))
  92     page = list_entry (list_pop_front (&pool->free_list), struct page, elem);
  93   else if (pool->uninit < pool->end)
  94     {
  95       page = (struct page *) pool->uninit;
  96       pool->uninit += PGSIZE;
  97     }
  98   else
  99     page = NULL;
 100
 101   if (page != NULL)
 102     {
 103       if (flags & PAL_ZERO)
 104         memset (page, 0, PGSIZE);
 105     }
 106   else
 107     {
 108       if (flags & PAL_ASSERT)
 109         PANIC ("palloc_get: out of pages");
 110     }
 111
 112   lock_release (&pool->lock);
 113
 114   return page;
 115 }
 116
 117 /* Frees PAGE. */
 118 void
 119 palloc_free (void *page_)
 120 {
 121   struct pool *pool;
 122   struct page *page = page_;
 123
 124   ASSERT (page == pg_round_down (page));
 125   if (page_from_pool (&kernel_pool, page))
 126     pool = &kernel_pool;
 127   else if (page_from_pool (&user_pool, page))
 128     pool = &user_pool;
 129   else
 130     PANIC ("freeing invalid pointer");
 131
 132 #ifndef NDEBUG
 133   memset (page, 0xcc, PGSIZE);
 134 #endif
 135
 136   lock_acquire (&pool->lock);
 137   list_push_front (&pool->free_list, &page->elem);
 138   lock_release (&pool->lock);
 139 }
 140
 141 /* Initializes pool P as starting at START and ending at END,
 142    naming it NAME for debugging purposes. */
 143 static void
 144 init_pool (struct pool *p, void *start, void *end, const char *name)
 145 {
 146   ASSERT (pg_ofs (start) == 0);
 147   ASSERT (pg_ofs (end) == 0);
 148
 149   printf ("%d kB allocated for %s.\n",
 150           (PGSIZE / 1024) * (pg_no (end) - pg_no (start)), name);
 151
 152   lock_init (&p->lock, name);
 153   p->start = p->uninit = start;
 154   p->end = end;
 155   list_init (&p->free_list);
 156 }
 157
 158 /* Returns true if PAGE was allocated from POOL,
 159    false otherwise. */
 160 static bool
 161 page_from_pool (const struct pool *pool, void *page_)
 162 {
 163   uint8_t *page = page_;
 164
 165   return page >= pool->start && page < pool->uninit;
 166 }