X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=blobdiff_plain;f=src%2Fthreads%2Fpalloc.c;h=4fc8394c8f078a20c5a48722c36e3e022658620e;hp=372e528c319954d5271c3605a28d9779984578b9;hb=a03618133f7df0954802a470a4bee7674f7aed45;hpb=587548d01521b55e6789d07146f0a84fa09bf879

diff --git a/src/threads/palloc.c b/src/threads/palloc.c
index 372e528..4fc8394 100644
--- a/src/threads/palloc.c
+++ b/src/threads/palloc.c
@@ -1,18 +1,19 @@
 #include "threads/palloc.h"
+#include <bitmap.h>
 #include <debug.h>
-#include <list.h>
+#include <inttypes.h>
+#include <round.h>
 #include <stddef.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <string.h>
-#include "threads/init.h"
 #include "threads/loader.h"
-#include "threads/mmu.h"
 #include "threads/synch.h"
+#include "threads/vaddr.h"
 
-/* Page allocator.  Hands out memory in page-size chunks.
-   See malloc.h for an allocator that hands out smaller
-   chunks.
+/* Page allocator.  Hands out memory in page-size (or
+   page-multiple) chunks.  See malloc.h for an allocator that
+   hands out smaller chunks.
 
    System memory is divided into two "pools" called the kernel
    and user pools.  The user pool is for user (virtual) memory
@@ -22,86 +23,73 @@
 
    By default, half of system RAM is given to the kernel pool and
    half to the user pool.  That should be huge overkill for the
-   kernel pool, but that's just fine for demonstration purposes.
-
-   Within each pool, 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
-  {
-    list_elem elem;             /* Free list element. */
-  };
+   kernel pool, but that's just fine for demonstration purposes. */
 
 /* A memory pool. */
 struct pool
   {
     struct lock lock;                   /* Mutual exclusion. */
-    uint8_t *start, *end;               /* Start and end of pool. */
-    uint8_t *uninit;                    /* First page not yet in free_list. */
-    struct list free_list;              /* Free pages. */
+    struct bitmap *used_map;            /* Bitmap of free pages. */
+    uint8_t *base;                      /* Base of pool. */
   };
 
 /* Two pools: one for kernel data, one for user pages. */
-struct pool kernel_pool, user_pool;
+static struct pool kernel_pool, user_pool;
 
-static void init_pool (struct pool *, void *start, void *end,
+static void init_pool (struct pool *, void *base, size_t page_cnt,
                        const char *name);
 static bool page_from_pool (const struct pool *, void *page);
 
-/* Initializes the page allocator. */
+/* Initializes the page allocator.  At most USER_PAGE_LIMIT
+   pages are put into the user pool. */
 void
-palloc_init (void) 
+palloc_init (size_t user_page_limit)
 {
-  /* End of the kernel as recorded by the linker.
-     See kernel.lds.S. */
-  extern char _end;
-
-  /* Free memory. */
-  uint8_t *free_start = pg_round_up (&_end);
-  uint8_t *free_end = ptov (ram_pages * PGSIZE);
+  /* Free memory starts at 1 MB and runs to the end of RAM. */
+  uint8_t *free_start = ptov (1024 * 1024);
+  uint8_t *free_end = ptov (init_ram_pages * PGSIZE);
   size_t free_pages = (free_end - free_start) / PGSIZE;
-  uint8_t *free_middle = free_start + free_pages / 2 * PGSIZE;
+  size_t user_pages = free_pages / 2;
+  size_t kernel_pages;
+  if (user_pages > user_page_limit)
+    user_pages = user_page_limit;
+  kernel_pages = free_pages - user_pages;
 
   /* Give half of memory to kernel, half to user. */
-  init_pool (&kernel_pool, free_start, free_middle, "kernel pool");
-  init_pool (&user_pool, free_middle, free_end, "user pool");
+  init_pool (&kernel_pool, free_start, kernel_pages, "kernel pool");
+  init_pool (&user_pool, free_start + kernel_pages * PGSIZE,
+             user_pages, "user pool");
 }
 
-/* Obtains and returns a free page.  If PAL_ZERO is set in FLAGS,
-   then the page is filled with zeros.  If no pages are
+/* Obtains and returns a group of PAGE_CNT contiguous free pages.
+   If PAL_USER is set, the pages are obtained from the user pool,
+   otherwise from the kernel pool.  If PAL_ZERO is set in FLAGS,
+   then the pages are filled with zeros.  If too few 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)
+palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)
 {
   struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
-  struct page *page;
+  void *pages;
+  size_t page_idx;
+
+  if (page_cnt == 0)
+    return NULL;
 
   lock_acquire (&pool->lock);
+  page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false);
+  lock_release (&pool->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 (&pool->free_list))
-    page = list_entry (list_pop_front (&pool->free_list), struct page, elem);
-  else if (pool->uninit < pool->end)
-    {
-      page = (struct page *) pool->uninit;
-      pool->uninit += PGSIZE;
-    }
+  if (page_idx != BITMAP_ERROR)
+    pages = pool->base + PGSIZE * page_idx;
   else
-    page = NULL;
+    pages = NULL;
 
-  if (page != NULL) 
+  if (pages != NULL) 
     {
       if (flags & PAL_ZERO)
-        memset (page, 0, PGSIZE);
+        memset (pages, 0, PGSIZE * page_cnt);
     }
   else 
     {
@@ -109,58 +97,86 @@ palloc_get (enum palloc_flags flags)
         PANIC ("palloc_get: out of pages");
     }
 
-  lock_release (&pool->lock);
-  
-  return page;
+  return pages;
+}
+
+/* Obtains a single free page and returns its kernel virtual
+   address.
+   If PAL_USER is set, the page is obtained from the user pool,
+   otherwise from the kernel pool.  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_page (enum palloc_flags flags) 
+{
+  return palloc_get_multiple (flags, 1);
 }
 
-/* Frees PAGE. */
+/* Frees the PAGE_CNT pages starting at PAGES. */
 void
-palloc_free (void *page_) 
+palloc_free_multiple (void *pages, size_t page_cnt) 
 {
   struct pool *pool;
-  struct page *page = page_;
+  size_t page_idx;
 
-  ASSERT (page == pg_round_down (page));
-  if (page_from_pool (&kernel_pool, page))
+  ASSERT (pg_ofs (pages) == 0);
+  if (pages == NULL || page_cnt == 0)
+    return;
+
+  if (page_from_pool (&kernel_pool, pages))
     pool = &kernel_pool;
-  else if (page_from_pool (&user_pool, page))
+  else if (page_from_pool (&user_pool, pages))
     pool = &user_pool;
   else
-    PANIC ("freeing invalid pointer");
+    NOT_REACHED ();
+
+  page_idx = pg_no (pages) - pg_no (pool->base);
 
 #ifndef NDEBUG
-  memset (page, 0xcc, PGSIZE);
+  memset (pages, 0xcc, PGSIZE * page_cnt);
 #endif
 
-  lock_acquire (&pool->lock);
-  list_push_front (&pool->free_list, &page->elem);
-  lock_release (&pool->lock);
+  ASSERT (bitmap_all (pool->used_map, page_idx, page_cnt));
+  bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false);
+}
+
+/* Frees the page at PAGE. */
+void
+palloc_free_page (void *page) 
+{
+  palloc_free_multiple (page, 1);
 }
 
 /* Initializes pool P as starting at START and ending at END,
    naming it NAME for debugging purposes. */
 static void
-init_pool (struct pool *p, void *start, void *end, const char *name) 
+init_pool (struct pool *p, void *base, size_t page_cnt, const char *name) 
 {
-  ASSERT (pg_ofs (start) == 0);
-  ASSERT (pg_ofs (end) == 0);
-
-  printf ("%d kB allocated for %s.\n",
-          (PGSIZE / 1024) * (pg_no (end) - pg_no (start)), name);
-
-  lock_init (&p->lock, name);
-  p->start = p->uninit = start;
-  p->end = end;
-  list_init (&p->free_list);
+  /* We'll put the pool's used_map at its base.
+     Calculate the space needed for the bitmap
+     and subtract it from the pool's size. */
+  size_t bm_pages = DIV_ROUND_UP (bitmap_buf_size (page_cnt), PGSIZE);
+  if (bm_pages > page_cnt)
+    PANIC ("Not enough memory in %s for bitmap.", name);
+  page_cnt -= bm_pages;
+
+  printf ("%zu pages available in %s.\n", page_cnt, name);
+
+  /* Initialize the pool. */
+  lock_init (&p->lock);
+  p->used_map = bitmap_create_in_buf (page_cnt, base, bm_pages * PGSIZE);
+  p->base = base + bm_pages * PGSIZE;
 }
 
 /* Returns true if PAGE was allocated from POOL,
    false otherwise. */
 static bool
-page_from_pool (const struct pool *pool, void *page_) 
+page_from_pool (const struct pool *pool, void *page) 
 {
-  uint8_t *page = page_;
+  size_t page_no = pg_no (page);
+  size_t start_page = pg_no (pool->base);
+  size_t end_page = start_page + bitmap_size (pool->used_map);
 
-  return page >= pool->start && page < pool->uninit;
+  return page_no >= start_page && page_no < end_page;
 }