-#include "palloc.h"
+#include "threads/palloc.h"
+#include <bitmap.h>
+#include <debug.h>
+#include <inttypes.h>
+#include <round.h>
#include <stddef.h>
#include <stdint.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
+#include <stdio.h>
+#include <string.h>
+#include "threads/loader.h"
+#include "threads/synch.h"
+#include "threads/vaddr.h"
+
+/* 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
+ pages, the kernel pool for everything else. The idea here is
+ that the kernel needs to have memory for its own operations
+ even if user processes are swapping like mad.
+
+ 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. */
+
+/* A memory pool. */
+struct pool
{
- list_elem free_elem; /* Free list element. */
+ struct lock lock; /* Mutual exclusion. */
+ struct bitmap *used_map; /* Bitmap of free pages. */
+ uint8_t *base; /* Base of pool. */
};
-/* Keeps multiple threads away from free_pages and
- uninit_start. */
-static struct lock lock;
+/* Two pools: one for kernel data, one for user pages. */
+static struct pool kernel_pool, user_pool;
-/* List of free pages. */
-static struct list free_pages;
+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);
-/* 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. */
+/* 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)
{
- 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);
+ /* 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;
+ 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, 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 page *page;
+ struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
+ void *pages;
+ size_t page_idx;
- lock_acquire (&lock);
+ if (page_cnt == 0)
+ return NULL;
- /* 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)
- {
- page = (struct page *) uninit_start;
- uninit_start += PGSIZE;
- }
+ lock_acquire (&pool->lock);
+ page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false);
+ lock_release (&pool->lock);
+
+ 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
{
PANIC ("palloc_get: out of pages");
}
- lock_release (&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 page *page = page_;
+ struct pool *pool;
+ size_t page_idx;
+
+ 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, pages))
+ pool = &user_pool;
+ else
+ NOT_REACHED ();
+
+ page_idx = pg_no (pages) - pg_no (pool->base);
- ASSERT (page == pg_round_down (page));
#ifndef NDEBUG
- memset (page, 0xcc, PGSIZE);
+ memset (pages, 0xcc, PGSIZE * page_cnt);
#endif
- lock_acquire (&lock);
- list_push_front (&free_pages, &page->free_elem);
- lock_release (&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 *base, size_t page_cnt, const char *name)
+{
+ /* 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)
+{
+ 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_no >= start_page && page_no < end_page;
}
projects / pintos-anon / blobdiff