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

   1 #include "palloc.h"
   2 #include <stddef.h>
   3 #include <stdint.h>
   4 #include "debug.h"
   5 #include "init.h"
   6 #include "loader.h"
   7 #include "lib.h"
   8 #include "list.h"
   9 #include "mmu.h"
  10 #include "synch.h"
  11
  12 /* Page allocator.  Hands out memory in page-size chunks.
  13    See malloc.h for an allocator that hands out smaller
  14    chunks.
  15
  16    We simply use a linked list of free pages.  It would be
  17    straightforward to add all available memory to this free list
  18    at initialization time.  In practice, though, that's really
  19    slow because it causes the emulator we're running under to
  20    have to fault in every page of memory.  So instead we only add
  21    pages to the free list as needed. */
  22
  23 /* A free page owned by the page allocator. */
  24 struct page
  25   {
  26     list_elem free_elem;        /* Free list element. */
  27   };
  28
  29 /* Keeps multiple threads away from free_pages and
  30    uninit_start. */
  31 static struct lock lock;
  32
  33 /* List of free pages. */
  34 static struct list free_pages;
  35
  36 /* Range of pages (expressed as byte pointers to the beginnings
  37    of pages) that we haven't added to the free list yet. */
  38 static uint8_t *uninit_start, *uninit_end;
  39
  40 /* Initializes the page allocator. */
  41 void
  42 palloc_init (void)
  43 {
  44   extern char _start, _end;
  45
  46   /* Kernel static code and data, in 4 kB pages.
  47      We can figure this out because the linker records the start
  48      and end of the kernel as _start and _end.  See
  49      kernel.lds.S. */
  50   size_t kernel_pages = (&_end - &_start + 4095) / 4096;
  51
  52   /* Then we know how much is available to allocate. */
  53   uninit_start = ptov (LOADER_KERN_BASE + kernel_pages * PGSIZE);
  54   uninit_end = ptov (ram_pages * PGSIZE);
  55
  56   /* Initialize other variables. */
  57   lock_init (&lock, "palloc");
  58   list_init (&free_pages);
  59 }
  60
  61 /* Obtains and returns a free page.  If PAL_ZERO is set in FLAGS,
  62    then the page is filled with zeros.  If no pages are
  63    available, returns a null pointer, unless PAL_ASSERT is set in
  64    FLAGS, in which case the kernel panics. */
  65 void *
  66 palloc_get (enum palloc_flags flags)
  67 {
  68   struct page *page;
  69
  70   lock_acquire (&lock);
  71
  72   /* If there's a page in the free list, take it.
  73      Otherwise, if there's a page not yet added to the free list,
  74      use it.
  75      Otherwise, we're out of memory. */
  76   if (!list_empty (&free_pages))
  77     page = list_entry (list_pop_front (&free_pages), struct page, free_elem);
  78   else if (uninit_start < uninit_end)
  79     {
  80       page = (struct page *) uninit_start;
  81       uninit_start += PGSIZE;
  82     }
  83   else
  84     page = NULL;
  85
  86   if (page != NULL)
  87     {
  88       if (flags & PAL_ZERO)
  89         memset (page, 0, PGSIZE);
  90     }
  91   else
  92     {
  93       if (flags & PAL_ASSERT)
  94         PANIC ("palloc_get: out of pages");
  95     }
  96
  97   lock_release (&lock);
  98
  99   return page;
 100 }
 101
 102 /* Frees PAGE. */
 103 void
 104 palloc_free (void *page_)
 105 {
 106   struct page *page = page_;
 107
 108   ASSERT (page == pg_round_down (page));
 109 #ifndef NDEBUG
 110   memset (page, 0xcc, PGSIZE);
 111 #endif
 112
 113   lock_acquire (&lock);
 114   list_push_front (&free_pages, &page->free_elem);
 115   lock_release (&lock);
 116 }