#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 "threads/mmu.h"
#include "threads/synch.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
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. */
+ size_t first_page; /* Page number of first page. */
+ size_t page_cnt; /* Number of pages. */
};
+/* Tracks pages in use, with a lock protecting it. */
+static struct bitmap *used_map;
+static struct lock used_map_lock;
+
/* Two pools: one for kernel data, one for user pages. */
-struct pool kernel_pool, user_pool;
+static struct pool kernel_pool, user_pool;
+
+/* Maximum number of pages to put in user pool. */
+size_t max_user_pages = SIZE_MAX;
-static void init_pool (struct pool *, void *start, void *end,
+static void init_pool (struct pool *pool, size_t first_page, size_t page_cnt,
const char *name);
static bool page_from_pool (const struct pool *, void *page);
void
palloc_init (void)
{
- /* 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);
- size_t free_pages = (free_end - free_start) / PGSIZE;
- uint8_t *free_middle = free_start + free_pages / 2 * PGSIZE;
-
- /* 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");
+ /* used_map from 1 MB as long as necessary. */
+ size_t bitmap_start = 1024;
+ size_t bitmap_pages = DIV_ROUND_UP (bitmap_needed_bytes (ram_pages), PGSIZE);
+
+ /* Free space from the bitmap to the end of RAM. */
+ size_t free_start = bitmap_start + bitmap_pages;
+ size_t free_pages = ram_pages - free_start;
+
+ /* Kernel and user get half of free space each.
+ User space can be limited by max_user_pages. */
+ size_t half_free = free_pages / 2;
+ size_t kernel_pages = half_free;
+ size_t user_pages = half_free < max_user_pages ? half_free : max_user_pages;
+
+ used_map = bitmap_create_preallocated (ram_pages,
+ ptov (bitmap_start * PGSIZE),
+ bitmap_pages * PGSIZE);
+ init_pool (&kernel_pool, free_start, kernel_pages, "kernel pool");
+ init_pool (&user_pool, free_start + kernel_pages, user_pages, "use pool");
+ lock_init (&used_map_lock, "used_map");
}
-/* Obtains and returns a free page. If PAL_ZERO is set in FLAGS,
- then the page is filled with zeros. If no pages are
+/* Initializes POOL to start (named NAME) at physical page number
+ FIRST_PAGE and continue for PAGE_CNT pages. */
+static void
+init_pool (struct pool *pool, size_t first_page, size_t page_cnt,
+ const char *name)
+{
+ printf ("%zu pages available in %s.\n", page_cnt, name);
+ pool->first_page = first_page;
+ pool->page_cnt = page_cnt;
+}
+
+/* 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;
-
- lock_acquire (&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;
- }
+ struct pool *pool;
+ void *pages;
+ size_t page_idx;
+
+ if (page_cnt == 0)
+ return NULL;
+
+ pool = flags & PAL_USER ? &user_pool : &kernel_pool;
+
+ lock_acquire (&used_map_lock);
+ page_idx = bitmap_scan_and_flip (used_map,
+ pool->first_page, pool->page_cnt,
+ false);
+ lock_release (&used_map_lock);
+
+ if (page_idx != BITMAP_ERROR)
+ pages = ptov (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 (&pool->lock);
-
- return page;
+ return pages;
}
-/* Frees PAGE. */
+/* Obtains and returns a single free page.
+ 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 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 (pg_ofs (pages) == 0);
+ if (pages == NULL || page_cnt == 0)
+ return;
- ASSERT (page == pg_round_down (page));
- if (page_from_pool (&kernel_pool, page))
+ 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 = vtop (pages) / PGSIZE;
#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 (used_map, page_idx, page_cnt));
+ bitmap_set_multiple (used_map, page_idx, page_cnt, false);
}
-/* 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)
+/* Frees the page at PAGE. */
+void
+palloc_free_page (void *page)
{
- 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);
+ palloc_free_multiple (page, 1);
}
/* 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 phys_page_no = vtop (page) / PGSIZE;
- return page >= pool->start && page < pool->uninit;
+ return (phys_page_no >= pool->first_page
+ && phys_page_no < pool->first_page + pool->page_cnt);
}
projects / pintos-anon / blobdiff