1 #include "threads/palloc.h"
9 #include "threads/init.h"
10 #include "threads/loader.h"
11 #include "threads/mmu.h"
12 #include "threads/synch.h"
14 /* Page allocator. Hands out memory in page-size (or
15 page-multiple) chunks. See malloc.h for an allocator that
16 hands out smaller chunks.
18 System memory is divided into two "pools" called the kernel
19 and user pools. The user pool is for user (virtual) memory
20 pages, the kernel pool for everything else. The idea here is
21 that the kernel needs to have memory for its own operations
22 even if user processes are swapping like mad.
24 By default, half of system RAM is given to the kernel pool and
25 half to the user pool. That should be huge overkill for the
26 kernel pool, but that's just fine for demonstration purposes. */
31 struct lock lock; /* Mutual exclusion. */
32 struct bitmap *used_map; /* Bitmap of free pages. */
33 uint8_t *start, *end; /* Start and end of pool. */
36 /* Two pools: one for kernel data, one for user pages. */
37 struct pool kernel_pool, user_pool;
39 static void init_pool (struct pool *, void *start, void *end,
41 static bool page_from_pool (const struct pool *, void *page);
43 /* Initializes the page allocator. */
47 /* End of the kernel as recorded by the linker.
52 uint8_t *free_start = pg_round_up (&_end);
53 uint8_t *free_end = ptov (ram_pages * PGSIZE);
54 size_t free_pages = (free_end - free_start) / PGSIZE;
55 uint8_t *free_middle = free_start + free_pages / 2 * PGSIZE;
57 /* Give half of memory to kernel, half to user. */
58 init_pool (&kernel_pool, free_start, free_middle, "kernel pool");
59 init_pool (&user_pool, free_middle, free_end, "user pool");
62 /* Obtains and returns a group of PAGE_CNT contiguous free pages.
63 If PAL_USER is set, the pages are obtained from the user pool,
64 otherwise from the kernel pool. If PAL_ZERO is set in FLAGS,
65 then the pages are filled with zeros. If too few pages are
66 available, returns a null pointer, unless PAL_ASSERT is set in
67 FLAGS, in which case the kernel panics. */
69 palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)
71 struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
78 lock_acquire (&pool->lock);
80 page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false);
81 if (page_idx != BITMAP_ERROR)
82 pages = pool->start + PGSIZE * page_idx;
89 memset (pages, 0, PGSIZE * page_cnt);
93 if (flags & PAL_ASSERT)
94 PANIC ("palloc_get: out of pages");
97 lock_release (&pool->lock);
102 /* Obtains and returns a single free page.
103 If PAL_USER is set, the page is obtained from the user pool,
104 otherwise from the kernel pool. If PAL_ZERO is set in FLAGS,
105 then the page is filled with zeros. If no pages are
106 available, returns a null pointer, unless PAL_ASSERT is set in
107 FLAGS, in which case the kernel panics. */
109 palloc_get_page (enum palloc_flags flags)
111 return palloc_get_multiple (flags, 1);
114 /* Frees the PAGE_CNT pages starting at PAGES. */
116 palloc_free_multiple (void *pages, size_t page_cnt)
121 ASSERT (pg_ofs (pages) == 0);
122 if (pages == NULL || page_cnt == 0)
125 if (page_from_pool (&kernel_pool, pages))
127 else if (page_from_pool (&user_pool, pages))
132 page_idx = pg_no (pages) - pg_no (pool->start);
133 ASSERT (pg_no (pages) + page_cnt <= pg_no (pool->end));
136 memset (pages, 0xcc, PGSIZE * page_cnt);
139 lock_acquire (&pool->lock);
140 ASSERT (bitmap_all (pool->used_map, page_idx, page_idx + page_cnt));
141 bitmap_set_multiple (pool->used_map, page_idx, page_idx + page_cnt, false);
142 lock_release (&pool->lock);
145 /* Frees the page at PAGE. */
147 palloc_free_page (void *page)
149 palloc_free_multiple (page, 1);
152 /* Initializes pool P as starting at START and ending at END,
153 naming it NAME for debugging purposes. */
155 init_pool (struct pool *p, void *start, void *end, const char *name)
160 ASSERT (pg_ofs (start) == 0);
161 ASSERT (pg_ofs (end) == 0);
162 ASSERT (end > start);
164 page_cnt = pg_no (end) - pg_no (start);
165 printf ("%d kB allocated for %s.\n", (PGSIZE / 1024) * page_cnt, name);
167 lock_init (&p->lock, name);
168 bitmap_size = ROUND_UP (bitmap_needed_bytes (page_cnt), PGSIZE);
169 p->used_map = bitmap_create_preallocated (page_cnt, start, bitmap_size);
170 p->start = start + bitmap_size;
172 ASSERT (p->end > p->start);
175 /* Returns true if PAGE was allocated from POOL,
178 page_from_pool (const struct pool *pool, void *page_)
180 uint8_t *page = page_;
182 return page >= pool->start && page < pool->end;