#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
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_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. */
+/* 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
{
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 (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 = 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;
}
projects / pintos-anon / blobdiff