From: Ben Pfaff Date: Mon, 13 Sep 2004 01:23:24 +0000 (+0000) Subject: Introduce "kernel" and "user" pools as a band-aid for user memory X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=commitdiff_plain;h=587548d01521b55e6789d07146f0a84fa09bf879 Introduce "kernel" and "user" pools as a band-aid for user memory pressure on kernel. --- diff --git a/src/threads/palloc.c b/src/threads/palloc.c index 29cb54f..372e528 100644 --- a/src/threads/palloc.c +++ b/src/threads/palloc.c @@ -3,6 +3,7 @@ #include #include #include +#include #include #include "threads/init.h" #include "threads/loader.h" @@ -13,49 +14,62 @@ 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. */ + 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. + + 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 free_elem; /* Free list element. */ + list_elem elem; /* Free list element. */ }; -/* Keeps multiple threads away from free_pages and - uninit_start. */ -static struct lock lock; +/* 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. */ + }; -/* List of free pages. */ -static struct list free_pages; +/* Two pools: one for kernel data, one for user pages. */ +struct pool kernel_pool, user_pool; -/* 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; +static void init_pool (struct pool *, void *start, void *end, + const char *name); +static bool page_from_pool (const struct pool *, void *page); /* Initializes the page allocator. */ void palloc_init (void) { - 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); + /* 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"); } /* Obtains and returns a free page. If PAL_ZERO is set in FLAGS, @@ -65,20 +79,21 @@ palloc_init (void) void * palloc_get (enum palloc_flags flags) { + struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool; struct page *page; - lock_acquire (&lock); + 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 (&free_pages)) - page = list_entry (list_pop_front (&free_pages), struct page, free_elem); - else if (uninit_start < uninit_end) + 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 *) uninit_start; - uninit_start += PGSIZE; + page = (struct page *) pool->uninit; + pool->uninit += PGSIZE; } else page = NULL; @@ -94,7 +109,7 @@ palloc_get (enum palloc_flags flags) PANIC ("palloc_get: out of pages"); } - lock_release (&lock); + lock_release (&pool->lock); return page; } @@ -103,14 +118,49 @@ palloc_get (enum palloc_flags flags) void palloc_free (void *page_) { + struct pool *pool; struct page *page = page_; ASSERT (page == pg_round_down (page)); + if (page_from_pool (&kernel_pool, page)) + pool = &kernel_pool; + else if (page_from_pool (&user_pool, page)) + pool = &user_pool; + else + PANIC ("freeing invalid pointer"); + #ifndef NDEBUG memset (page, 0xcc, PGSIZE); #endif - lock_acquire (&lock); - list_push_front (&free_pages, &page->free_elem); - lock_release (&lock); + lock_acquire (&pool->lock); + list_push_front (&pool->free_list, &page->elem); + lock_release (&pool->lock); +} + +/* 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) +{ + 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); +} + +/* Returns true if PAGE was allocated from POOL, + false otherwise. */ +static bool +page_from_pool (const struct pool *pool, void *page_) +{ + uint8_t *page = page_; + + return page >= pool->start && page < pool->uninit; } diff --git a/src/threads/palloc.h b/src/threads/palloc.h index ca7824e..38a401c 100644 --- a/src/threads/palloc.h +++ b/src/threads/palloc.h @@ -6,7 +6,8 @@ enum palloc_flags { PAL_ASSERT = 001, /* Panic on failure. */ - PAL_ZERO = 002 /* Zero page contents. */ + PAL_ZERO = 002, /* Zero page contents. */ + PAL_USER = 004 /* User page. */ }; void palloc_init (void);