X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fthreads%2Fpalloc.c;h=e3cfafb7fc1bd468345288cef3ffafa61e7c7a4e;hb=f6580e9ad405b519dbe85027691bf3c66074b0a4;hp=0fe5f94b9e9f83c4553c537353957475c21f07aa;hpb=750d21936d284127e265d050ccbce76fca1ece1a;p=pintos-anon

diff --git a/src/threads/palloc.c b/src/threads/palloc.c
index 0fe5f94..e3cfafb 100644
--- a/src/threads/palloc.c
+++ b/src/threads/palloc.c
@@ -1,61 +1,116 @@
 #include "palloc.h"
 #include <stddef.h>
 #include <stdint.h>
-#include <string.h>
-#include "debug.h"
+#include "init.h"
+#include "loader.h"
 #include "mmu.h"
+#include "synch.h"
+#include "lib/debug.h"
+#include "lib/lib.h"
+#include "lib/list.h"
+
+/* Page allocator.  Hands out memory in page-size chunks.
+   See malloc.h for an allocator that hands out smaller
+   chunks.
+
+   We simply use a linked list of free pages.  It would be
+   straightforward to add all available memory to this free list
+   at initialization time.  In practice, though, that's really
+   slow because it causes the emulator we're running under to
+   have to fault in every page of memory.  So instead we only add
+   pages to the free list as needed. */
 
 /* A free page owned by the page allocator. */
 struct page
   {
-    struct page *next;  /* Next free page, or null at end of chain. */
+    list_elem free_elem;        /* Free list element. */
   };
 
-static struct page *free_pages;
+/* Keeps multiple threads away from free_pages and
+   uninit_start. */
+static struct lock lock;
+
+/* List of free pages. */
+static struct list free_pages;
+
+/* Range of pages (expressed as byte pointers to the beginnings
+   of pages) that we haven't added to the free list yet. */
 static uint8_t *uninit_start, *uninit_end;
 
+/* Initializes the page allocator. */
 void
-palloc_init (uint8_t *start, uint8_t *end) 
+palloc_init (void) 
 {
-  uninit_start = start;
-  uninit_end = end;
+  extern char _start, _end;
+
+  /* Kernel static code and data, in 4 kB pages.
+     We can figure this out because the linker records the start
+     and end of the kernel as _start and _end.  See
+     kernel.lds.S. */
+  size_t kernel_pages = (&_end - &_start + 4095) / 4096;
+
+  /* Then we know how much is available to allocate. */
+  uninit_start = ptov (LOADER_KERN_BASE + kernel_pages * PGSIZE);
+  uninit_end = ptov (ram_pages * PGSIZE);
+
+  /* Initialize other variables. */
+  lock_init (&lock, "palloc");
+  list_init (&free_pages);
 }
 
+/* Obtains and returns a free page.  If PAL_ZERO is set in FLAGS,
+   then the page is filled with zeros.  If no pages are
+   available, returns a null pointer, unless PAL_ASSERT is set in
+   FLAGS, in which case the kernel panics. */
 void *
 palloc_get (enum palloc_flags flags)
 {
   struct page *page;
 
-  if (free_pages == NULL && uninit_start < uninit_end) 
+  lock_acquire (&lock);
+
+  /* If there's a page in the free list, take it.
+     Otherwise, if there's a page not yet added to the free list,
+     use it.
+     Otherwise, we're out of memory. */
+  if (!list_empty (&free_pages))
+    page = list_entry (list_pop_front (&free_pages), struct page, free_elem);
+  else if (uninit_start < uninit_end) 
     {
-      palloc_free (uninit_start);
-      uninit_start += NBPG;
+      page = (struct page *) uninit_start;
+      uninit_start += PGSIZE;
     }
+  else
+    page = NULL;
 
-  page = free_pages;
   if (page != NULL) 
     {
-      free_pages = page->next;
       if (flags & PAL_ZERO)
-        memset (page, 0, NBPG);
+        memset (page, 0, PGSIZE);
     }
   else 
     {
       if (flags & PAL_ASSERT)
-        panic ("palloc_get: out of pages");
+        PANIC ("palloc_get: out of pages");
     }
+
+  lock_release (&lock);
   
   return page;
 }
 
+/* Frees PAGE. */
 void
 palloc_free (void *page_) 
 {
   struct page *page = page_;
-  ASSERT((uintptr_t) page % NBPG == 0);
+
+  ASSERT (page == pg_round_down (page));
 #ifndef NDEBUG
-  memset (page, 0xcc, NBPG);
+  memset (page, 0xcc, PGSIZE);
 #endif
-  page->next = free_pages;
-  free_pages = page;
+
+  lock_acquire (&lock);
+  list_push_front (&free_pages, &page->free_elem);
+  lock_release (&lock);
 }