From 8382bdd7884a6d38f7529e0517dd9a7083f4ce73 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Thu, 23 Sep 2004 00:58:29 +0000 Subject: [PATCH] Rewrite page allocator to support multi-page allocations. Change interface to reflect it, update references. Make malloc() and free() willing to handle big blocks. --- src/filesys/fsutil.c | 12 ++-- src/threads/init.c | 4 +- src/threads/malloc.c | 43 ++++++++++---- src/threads/palloc.c | 129 +++++++++++++++++++++++------------------ src/threads/palloc.h | 8 ++- src/threads/thread.c | 4 +- src/userprog/pagedir.c | 10 ++-- src/userprog/process.c | 16 ++--- src/userprog/tss.c | 2 +- 9 files changed, 132 insertions(+), 96 deletions(-) diff --git a/src/filesys/fsutil.c b/src/filesys/fsutil.c index cc0e335..7756946 100644 --- a/src/filesys/fsutil.c +++ b/src/filesys/fsutil.c @@ -55,7 +55,7 @@ copy_in (const char *filename, off_t size) PANIC ("%s: open failed", filename); /* Do copy. */ - buffer = palloc_get (PAL_ASSERT); + buffer = palloc_get_page (PAL_ASSERT); sector = 0; while (size > 0) { @@ -66,7 +66,7 @@ copy_in (const char *filename, off_t size) filename, (unsigned long long) size); size -= chunk_size; } - palloc_free (buffer); + palloc_free_page (buffer); file_close (dst); } @@ -84,7 +84,7 @@ copy_out (const char *filename) off_t size; disk_sector_t sector; - buffer = palloc_get (PAL_ASSERT | PAL_ZERO); + buffer = palloc_get_page (PAL_ASSERT | PAL_ZERO); /* Open source file. */ src = filesys_open (filename); @@ -115,7 +115,7 @@ copy_out (const char *filename) disk_write (dst, sector++, buffer); size -= chunk_size; } - palloc_free (buffer); + palloc_free_page (buffer); file_close (src); } @@ -160,7 +160,7 @@ fsutil_print (const char *filename) file = filesys_open (filename); if (file == NULL) PANIC ("%s: open failed", filename); - buffer = palloc_get (PAL_ASSERT); + buffer = palloc_get_page (PAL_ASSERT); for (;;) { off_t n = file_read (file, buffer, PGSIZE); @@ -169,6 +169,6 @@ fsutil_print (const char *filename) hex_dump (0, buffer, n, true); } - palloc_free (buffer); + palloc_free_page (buffer); file_close (file); } diff --git a/src/threads/init.c b/src/threads/init.c index 855afa0..1afa865 100644 --- a/src/threads/init.c +++ b/src/threads/init.c @@ -163,7 +163,7 @@ paging_init (void) uint32_t *pd, *pt; size_t page; - pd = base_page_dir = palloc_get (PAL_ASSERT | PAL_ZERO); + pd = base_page_dir = palloc_get_page (PAL_ASSERT | PAL_ZERO); pt = NULL; for (page = 0; page < ram_pages; page++) { @@ -174,7 +174,7 @@ paging_init (void) if (pd[pde_idx] == 0) { - pt = palloc_get (PAL_ASSERT | PAL_ZERO); + pt = palloc_get_page (PAL_ASSERT | PAL_ZERO); pd[pde_idx] = pde_create (pt); } diff --git a/src/threads/malloc.c b/src/threads/malloc.c index 9910bf4..487e938 100644 --- a/src/threads/malloc.c +++ b/src/threads/malloc.c @@ -1,6 +1,7 @@ #include "threads/malloc.h" #include #include +#include #include #include #include @@ -27,10 +28,11 @@ blocks, we remove all of the arena's blocks from the free list and give the arena back to the page allocator. - Major limitation: the largest block that can be allocated is - PGSIZE / 2, or 2 kB. Use palloc_get() to allocate pages (4 kB - blocks). You're on your own if you need more memory than - that. */ + We can't handle blocks bigger than 2 kB using this scheme, + because they're too big to fit in a single page with a + descriptor. We handle those by allocating contiguous pages + with the page allocator and sticking the allocation size at + the beginning of the allocated block's arena header. */ /* Descriptor. */ struct desc @@ -48,8 +50,8 @@ struct desc struct arena { unsigned magic; /* Always set to ARENA_MAGIC. */ - struct desc *desc; /* Owning descriptor. */ - size_t free_cnt; /* Number of free blocks. */ + struct desc *desc; /* Owning descriptor, null for big block. */ + size_t free_cnt; /* Free blocks; pages in big block. */ }; /* Free block. */ @@ -71,7 +73,7 @@ malloc_init (void) { size_t block_size; - for (block_size = 16; block_size < PGSIZE; block_size *= 2) + for (block_size = 16; block_size < PGSIZE / 2; block_size *= 2) { struct desc *d = &descs[desc_cnt++]; ASSERT (desc_cnt <= sizeof descs / sizeof *descs); @@ -102,8 +104,19 @@ malloc (size_t size) break; if (d == descs + desc_cnt) { - printf ("malloc: %zu byte allocation too big\n", size); - return NULL; + /* SIZE is too big for any descriptor. + Allocate enough pages to hold SIZE plus an arena. */ + size_t page_cnt = DIV_ROUND_UP (size + sizeof *a, PGSIZE); + a = palloc_get_multiple (0, page_cnt); + if (a == NULL) + return NULL; + + /* Initialize the arena to indicate a big block of PAGE_CNT + pages, and return it. */ + a->magic = ARENA_MAGIC; + a->desc = NULL; + a->free_cnt = page_cnt; + return a + 1; } lock_acquire (&d->lock); @@ -114,7 +127,7 @@ malloc (size_t size) size_t i; /* Allocate a page. */ - a = palloc_get (0); + a = palloc_get_page (0); if (a == NULL) { lock_release (&d->lock); @@ -177,13 +190,19 @@ free (void *p) a = block_to_arena (b); d = a->desc; + if (d == NULL) + { + /* It's a big block. Free its pages. */ + palloc_free_multiple (a, a->free_cnt); + return; + } + #ifndef NDEBUG memset (b, 0xcd, d->block_size); #endif lock_acquire (&d->lock); - /* Add block to free list. */ list_push_front (&d->free_list, &b->free_elem); @@ -198,7 +217,7 @@ free (void *p) struct block *b = arena_to_block (a, i); list_remove (&b->free_elem); } - palloc_free (a); + palloc_free_page (a); } lock_release (&d->lock); diff --git a/src/threads/palloc.c b/src/threads/palloc.c index f00b31e..f7d49b2 100644 --- a/src/threads/palloc.c +++ b/src/threads/palloc.c @@ -1,6 +1,7 @@ #include "threads/palloc.h" +#include #include -#include +#include #include #include #include @@ -10,9 +11,9 @@ #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 @@ -22,28 +23,14 @@ 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. */ + struct bitmap *used_map; /* Bitmap of free pages. */ 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. */ }; /* Two pools: one for kernel data, one for user pages. */ @@ -72,38 +59,34 @@ palloc_init (void) init_pool (&user_pool, free_middle, free_end, "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); - /* 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; - } + page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false); + if (page_idx != BITMAP_ERROR) + pages = pool->start + 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 { @@ -113,48 +96,80 @@ palloc_get (enum palloc_flags flags) lock_release (&pool->lock); - return page; + return pages; +} + +/* 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 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->start); + ASSERT (pg_no (pages) + page_cnt <= pg_no (pool->end)); #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); + ASSERT (bitmap_all (pool->used_map, page_idx, page_idx + page_cnt)); + bitmap_set_multiple (pool->used_map, page_idx, page_idx + page_cnt, false); lock_release (&pool->lock); } +/* 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) { + size_t bitmap_size; + size_t page_cnt; + ASSERT (pg_ofs (start) == 0); ASSERT (pg_ofs (end) == 0); + ASSERT (end > start); - printf ("%d kB allocated for %s.\n", - (PGSIZE / 1024) * (pg_no (end) - pg_no (start)), name); + page_cnt = pg_no (end) - pg_no (start); + printf ("%d kB allocated for %s.\n", (PGSIZE / 1024) * page_cnt, name); lock_init (&p->lock, name); - p->start = p->uninit = start; + bitmap_size = ROUND_UP (bitmap_needed_bytes (page_cnt), PGSIZE); + p->used_map = bitmap_create_preallocated (page_cnt, start, bitmap_size); + p->start = start + bitmap_size; p->end = end; - list_init (&p->free_list); + ASSERT (p->end > p->start); } /* Returns true if PAGE was allocated from POOL, @@ -164,5 +179,5 @@ page_from_pool (const struct pool *pool, void *page_) { uint8_t *page = page_; - return page >= pool->start && page < pool->uninit; + return page >= pool->start && page < pool->end; } diff --git a/src/threads/palloc.h b/src/threads/palloc.h index 38a401c..45e0f42 100644 --- a/src/threads/palloc.h +++ b/src/threads/palloc.h @@ -1,7 +1,7 @@ #ifndef THREADS_PALLOC_H #define THREADS_PALLOC_H -#include +#include enum palloc_flags { @@ -11,7 +11,9 @@ enum palloc_flags }; void palloc_init (void); -void *palloc_get (enum palloc_flags); -void palloc_free (void *); +void *palloc_get_page (enum palloc_flags); +void *palloc_get_multiple (enum palloc_flags, size_t page_cnt); +void palloc_free_page (void *); +void palloc_free_multiple (void *, size_t page_cnt); #endif /* threads/palloc.h */ diff --git a/src/threads/thread.c b/src/threads/thread.c index eb96465..e85bc16 100644 --- a/src/threads/thread.c +++ b/src/threads/thread.c @@ -112,7 +112,7 @@ thread_create (const char *name, int priority, ASSERT (function != NULL); /* Allocate thread. */ - t = palloc_get (PAL_ZERO); + t = palloc_get_page (PAL_ZERO); if (t == NULL) return TID_ERROR; @@ -370,7 +370,7 @@ schedule_tail (struct thread *prev) { ASSERT (prev != cur); if (prev != initial_thread) - palloc_free (prev); + palloc_free_page (prev); } } diff --git a/src/userprog/pagedir.c b/src/userprog/pagedir.c index 7d1018e..f26496d 100644 --- a/src/userprog/pagedir.c +++ b/src/userprog/pagedir.c @@ -13,7 +13,7 @@ uint32_t * pagedir_create (void) { - uint32_t *pd = palloc_get (0); + uint32_t *pd = palloc_get_page (0); memcpy (pd, base_page_dir, PGSIZE); return pd; } @@ -37,10 +37,10 @@ pagedir_destroy (uint32_t *pd) for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++) if (*pte & PG_P) - palloc_free (pte_get_page (*pte)); - palloc_free (pt); + palloc_free_page (pte_get_page (*pte)); + palloc_free_page (pt); } - palloc_free (pd); + palloc_free_page (pd); } /* Returns the mapping of user virtual address UADDR in page @@ -68,7 +68,7 @@ lookup_page (uint32_t *pd, void *uaddr, bool create) { if (create) { - pt = palloc_get (PAL_ZERO); + pt = palloc_get_page (PAL_ZERO); if (pt == NULL) return NULL; diff --git a/src/userprog/process.c b/src/userprog/process.c index 5b50aa5..36c1bd0 100644 --- a/src/userprog/process.c +++ b/src/userprog/process.c @@ -31,7 +31,7 @@ process_execute (const char *filename) /* Make a copy of FILENAME. Otherwise there's a race between the caller and load(). */ - fn_copy = palloc_get (0); + fn_copy = palloc_get_page (0); if (fn_copy == NULL) return TID_ERROR; strlcpy (fn_copy, filename, PGSIZE); @@ -39,7 +39,7 @@ process_execute (const char *filename) /* Create a new thread to execute FILENAME. */ tid = thread_create (filename, PRI_DEFAULT, execute_thread, fn_copy); if (tid == TID_ERROR) - palloc_free (fn_copy); + palloc_free_page (fn_copy); return tid; } @@ -62,7 +62,7 @@ execute_thread (void *filename_) success = load (filename, &if_.eip, &if_.esp); /* If load failed, quit. */ - palloc_free (filename); + palloc_free_page (filename); if (!success) thread_exit (); @@ -347,14 +347,14 @@ load_segment (struct file *file, const struct Elf32_Phdr *phdr) file into the page and zero the rest. */ size_t read_bytes = filesz_left >= PGSIZE ? PGSIZE : filesz_left; size_t zero_bytes = PGSIZE - read_bytes; - uint8_t *kpage = palloc_get (PAL_USER); + uint8_t *kpage = palloc_get_page (PAL_USER); if (kpage == NULL) return false; /* Do the reading and zeroing. */ if (file_read (file, kpage, read_bytes) != (int) read_bytes) { - palloc_free (kpage); + palloc_free_page (kpage); return false; } memset (kpage + read_bytes, 0, zero_bytes); @@ -363,7 +363,7 @@ load_segment (struct file *file, const struct Elf32_Phdr *phdr) /* Add the page to the process's address space. */ if (!install_page (upage, kpage)) { - palloc_free (kpage); + palloc_free_page (kpage); return false; } } @@ -379,14 +379,14 @@ setup_stack (void **esp) uint8_t *kpage; bool success = false; - kpage = palloc_get (PAL_USER | PAL_ZERO); + kpage = palloc_get_page (PAL_USER | PAL_ZERO); if (kpage != NULL) { success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage); if (success) *esp = PHYS_BASE; else - palloc_free (kpage); + palloc_free_page (kpage); } else printf ("failed to allocate process stack\n"); diff --git a/src/userprog/tss.c b/src/userprog/tss.c index 4e1dc00..cddad93 100644 --- a/src/userprog/tss.c +++ b/src/userprog/tss.c @@ -80,7 +80,7 @@ tss_init (void) /* Our TSS is never used in a call gate or task gate, so only a few fields of it are ever referenced, and those are the only ones we initialize. */ - tss = palloc_get (PAL_ASSERT | PAL_ZERO); + tss = palloc_get_page (PAL_ASSERT | PAL_ZERO); tss->esp0 = ptov(0x20000); tss->ss0 = SEL_KDSEG; tss->bitmap = 0xdfff; -- 2.30.2