1 #include "threads/palloc.h"
8 #include "threads/init.h"
9 #include "threads/loader.h"
10 #include "threads/mmu.h"
11 #include "threads/synch.h"
13 /* Page allocator. Hands out memory in page-size chunks.
14 See malloc.h for an allocator that hands out smaller
17 System memory is divided into two "pools" called the kernel
18 and user pools. The user pool is for user (virtual) memory
19 pages, the kernel pool for everything else. The idea here is
20 that the kernel needs to have memory for its own operations
21 even if user processes are swapping like mad.
23 By default, half of system RAM is given to the kernel pool and
24 half to the user pool. That should be huge overkill for the
25 kernel pool, but that's just fine for demonstration purposes.
27 Within each pool, we simply use a linked list of free pages.
28 It would be straightforward to add all available memory to
29 this free list at initialization time. In practice, though,
30 that's really slow because it causes the emulator we're
31 running under to have to fault in every page of memory. So
32 instead we only add pages to the free list as needed. */
34 /* A free page owned by the page allocator. */
37 list_elem elem; /* Free list element. */
43 struct lock lock; /* Mutual exclusion. */
44 uint8_t *start, *end; /* Start and end of pool. */
45 uint8_t *uninit; /* First page not yet in free_list. */
46 struct list free_list; /* Free pages. */
49 /* Two pools: one for kernel data, one for user pages. */
50 struct pool kernel_pool, user_pool;
52 static void init_pool (struct pool *, void *start, void *end,
54 static bool page_from_pool (const struct pool *, void *page);
56 /* Initializes the page allocator. */
60 /* End of the kernel as recorded by the linker.
65 uint8_t *free_start = pg_round_up (&_end);
66 uint8_t *free_end = ptov (ram_pages * PGSIZE);
67 size_t free_pages = (free_end - free_start) / PGSIZE;
68 uint8_t *free_middle = free_start + free_pages / 2 * PGSIZE;
70 /* Give half of memory to kernel, half to user. */
71 init_pool (&kernel_pool, free_start, free_middle, "kernel pool");
72 init_pool (&user_pool, free_middle, free_end, "user pool");
75 /* Obtains and returns a free page. If PAL_USER is set, the page
76 is obtained from the user pool, otherwise from the kernel
77 pool. If PAL_ZERO is set in FLAGS, then the page is filled
78 with zeros. If no pages are available, returns a null
79 pointer, unless PAL_ASSERT is set in FLAGS, in which case the
82 palloc_get (enum palloc_flags flags)
84 struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
87 lock_acquire (&pool->lock);
89 /* If there's a page in the free list, take it.
90 Otherwise, if there's a page not yet added to the free list,
92 Otherwise, we're out of memory. */
93 if (!list_empty (&pool->free_list))
94 page = list_entry (list_pop_front (&pool->free_list), struct page, elem);
95 else if (pool->uninit < pool->end)
97 page = (struct page *) pool->uninit;
98 pool->uninit += PGSIZE;
105 if (flags & PAL_ZERO)
106 memset (page, 0, PGSIZE);
110 if (flags & PAL_ASSERT)
111 PANIC ("palloc_get: out of pages");
114 lock_release (&pool->lock);
121 palloc_free (void *page_)
124 struct page *page = page_;
126 ASSERT (page == pg_round_down (page));
127 if (page_from_pool (&kernel_pool, page))
129 else if (page_from_pool (&user_pool, page))
132 PANIC ("freeing invalid pointer");
135 memset (page, 0xcc, PGSIZE);
138 lock_acquire (&pool->lock);
139 list_push_front (&pool->free_list, &page->elem);
140 lock_release (&pool->lock);
143 /* Initializes pool P as starting at START and ending at END,
144 naming it NAME for debugging purposes. */
146 init_pool (struct pool *p, void *start, void *end, const char *name)
148 ASSERT (pg_ofs (start) == 0);
149 ASSERT (pg_ofs (end) == 0);
151 printf ("%d kB allocated for %s.\n",
152 (PGSIZE / 1024) * (pg_no (end) - pg_no (start)), name);
154 lock_init (&p->lock, name);
155 p->start = p->uninit = start;
157 list_init (&p->free_list);
160 /* Returns true if PAGE was allocated from POOL,
163 page_from_pool (const struct pool *pool, void *page_)
165 uint8_t *page = page_;
167 return page >= pool->start && page < pool->uninit;