1 #include "threads/palloc.h"
10 #include "threads/loader.h"
11 #include "threads/synch.h"
12 #include "threads/vaddr.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 *base; /* Base of pool. */
36 /* Two pools: one for kernel data, one for user pages. */
37 static struct pool kernel_pool, user_pool;
39 static void init_pool (struct pool *, void *base, size_t page_cnt,
41 static bool page_from_pool (const struct pool *, void *page);
43 /* Initializes the page allocator. At most USER_PAGE_LIMIT
44 pages are put into the user pool. */
46 palloc_init (size_t user_page_limit)
48 /* Free memory starts at 1 MB and runs to the end of RAM. */
49 uint8_t *free_start = ptov (1024 * 1024);
50 uint8_t *free_end = ptov (init_ram_pages * PGSIZE);
51 size_t free_pages = (free_end - free_start) / PGSIZE;
52 size_t user_pages = free_pages / 2;
54 if (user_pages > user_page_limit)
55 user_pages = user_page_limit;
56 kernel_pages = free_pages - user_pages;
58 /* Give half of memory to kernel, half to user. */
59 init_pool (&kernel_pool, free_start, kernel_pages, "kernel pool");
60 init_pool (&user_pool, free_start + kernel_pages * PGSIZE,
61 user_pages, "user pool");
64 /* Obtains and returns a group of PAGE_CNT contiguous free pages.
65 If PAL_USER is set, the pages are obtained from the user pool,
66 otherwise from the kernel pool. If PAL_ZERO is set in FLAGS,
67 then the pages are filled with zeros. If too few pages are
68 available, returns a null pointer, unless PAL_ASSERT is set in
69 FLAGS, in which case the kernel panics. */
71 palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)
73 struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
80 lock_acquire (&pool->lock);
81 page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false);
82 lock_release (&pool->lock);
84 if (page_idx != BITMAP_ERROR)
85 pages = pool->base + PGSIZE * page_idx;
92 memset (pages, 0, PGSIZE * page_cnt);
96 if (flags & PAL_ASSERT)
97 PANIC ("palloc_get: out of pages");
103 /* Obtains a single free page and returns its kernel virtual
105 If PAL_USER is set, the page is obtained from the user pool,
106 otherwise from the kernel pool. If PAL_ZERO is set in FLAGS,
107 then the page is filled with zeros. If no pages are
108 available, returns a null pointer, unless PAL_ASSERT is set in
109 FLAGS, in which case the kernel panics. */
111 palloc_get_page (enum palloc_flags flags)
113 return palloc_get_multiple (flags, 1);
116 /* Frees the PAGE_CNT pages starting at PAGES. */
118 palloc_free_multiple (void *pages, size_t page_cnt)
123 ASSERT (pg_ofs (pages) == 0);
124 if (pages == NULL || page_cnt == 0)
127 if (page_from_pool (&kernel_pool, pages))
129 else if (page_from_pool (&user_pool, pages))
134 page_idx = pg_no (pages) - pg_no (pool->base);
137 memset (pages, 0xcc, PGSIZE * page_cnt);
140 ASSERT (bitmap_all (pool->used_map, page_idx, page_cnt));
141 bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false);
144 /* Frees the page at PAGE. */
146 palloc_free_page (void *page)
148 palloc_free_multiple (page, 1);
151 /* Initializes pool P as starting at START and ending at END,
152 naming it NAME for debugging purposes. */
154 init_pool (struct pool *p, void *base, size_t page_cnt, const char *name)
156 /* We'll put the pool's used_map at its base.
157 Calculate the space needed for the bitmap
158 and subtract it from the pool's size. */
159 size_t bm_pages = DIV_ROUND_UP (bitmap_buf_size (page_cnt), PGSIZE);
160 if (bm_pages > page_cnt)
161 PANIC ("Not enough memory in %s for bitmap.", name);
162 page_cnt -= bm_pages;
164 printf ("%zu pages available in %s.\n", page_cnt, name);
166 /* Initialize the pool. */
167 lock_init (&p->lock);
168 p->used_map = bitmap_create_in_buf (page_cnt, base, bm_pages * PGSIZE);
169 p->base = base + bm_pages * PGSIZE;
172 /* Returns true if PAGE was allocated from POOL,
175 page_from_pool (const struct pool *pool, void *page)
177 size_t page_no = pg_no (page);
178 size_t start_page = pg_no (pool->base);
179 size_t end_page = start_page + bitmap_size (pool->used_map);
181 return page_no >= start_page && page_no < end_page;