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_ZERO is set in FLAGS,
76 then the page is filled with zeros. If no pages are
77 available, returns a null pointer, unless PAL_ASSERT is set in
78 FLAGS, in which case the kernel panics. */
80 palloc_get (enum palloc_flags flags)
82 struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
85 lock_acquire (&pool->lock);
87 /* If there's a page in the free list, take it.
88 Otherwise, if there's a page not yet added to the free list,
90 Otherwise, we're out of memory. */
91 if (!list_empty (&pool->free_list))
92 page = list_entry (list_pop_front (&pool->free_list), struct page, elem);
93 else if (pool->uninit < pool->end)
95 page = (struct page *) pool->uninit;
96 pool->uninit += PGSIZE;
103 if (flags & PAL_ZERO)
104 memset (page, 0, PGSIZE);
108 if (flags & PAL_ASSERT)
109 PANIC ("palloc_get: out of pages");
112 lock_release (&pool->lock);
119 palloc_free (void *page_)
122 struct page *page = page_;
124 ASSERT (page == pg_round_down (page));
125 if (page_from_pool (&kernel_pool, page))
127 else if (page_from_pool (&user_pool, page))
130 PANIC ("freeing invalid pointer");
133 memset (page, 0xcc, PGSIZE);
136 lock_acquire (&pool->lock);
137 list_push_front (&pool->free_list, &page->elem);
138 lock_release (&pool->lock);
141 /* Initializes pool P as starting at START and ending at END,
142 naming it NAME for debugging purposes. */
144 init_pool (struct pool *p, void *start, void *end, const char *name)
146 ASSERT (pg_ofs (start) == 0);
147 ASSERT (pg_ofs (end) == 0);
149 printf ("%d kB allocated for %s.\n",
150 (PGSIZE / 1024) * (pg_no (end) - pg_no (start)), name);
152 lock_init (&p->lock, name);
153 p->start = p->uninit = start;
155 list_init (&p->free_list);
158 /* Returns true if PAGE was allocated from POOL,
161 page_from_pool (const struct pool *pool, void *page_)
163 uint8_t *page = page_;
165 return page >= pool->start && page < pool->uninit;