Page allocator

The page allocator declared in threads/palloc.h allocates memory in units of a page. It is most often used to allocate memory one page at a time, but it can also allocate multiple contiguous pages at once.

The page allocator divides the memory it allocates into two pools, called the kernel and user pools. By default, each pool gets half of system memory above 1 MiB, but the division can be changed with the -ul kernel command line option. An allocation request draws from one pool or the other. If one pool becomes empty, the other may still have free pages. The user pool should be used for allocating memory for user processes and the kernel pool for all other allocations. This distinction is not very relevant in this project, since all threads you will be dealing with are kernel threads (unlike in Project Userprog). For Project Threads, all allocations should be made from the user pool.

Each pool’s usage is tracked with a bitmap, one bit per page in the pool. A request to allocate n pages scans the bitmap for n consecutive bits set to false, indicating that those pages are free, and then sets those bits to true to mark them as used. This is a “first fit” allocation strategy.

The page allocator is subject to fragmentation. That is, it may not be possible to allocate n contiguous pages even though n or more pages are free, because the free pages are separated by used pages. In fact, in pathological cases it may be impossible to allocate 2 contiguous pages even though half of the pool’s pages are free. Single-page requests can’t fail due to fragmentation, so requests for multiple contiguous pages should be limited as much as possible.

Pages may not be allocated from interrupt context, but they may be freed. When a page is freed, all of its bytes are cleared to 0xcc, as a debugging aid.

Page allocator types and functions are described below.

void * palloc_get_page (enum palloc_flags flags)

void * palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)

Obtains and returns one page, or page_cnt contiguous pages, respectively. Returns a null pointer if the pages cannot be allocated.

The flags argument may be any combination of the following flags:

PAL_ASSERT

If the pages cannot be allocated, panic the kernel. This is only appropriate during kernel initialization. User processes should never be permitted to panic the kernel.

PAL_ZERO

Zero all the bytes in the allocated pages before returning them. If not set, the contents of newly allocated pages are unpredictable.

PAL_USER

Obtain the pages from the user pool. If not set, pages are allocated from the kernel pool.

void palloc_free_page (void *page)

void palloc_free_multiple (void *pages, size_t page_cnt)

Frees one page, or page_cnt contiguous pages, respectively, starting at pages. All of the pages must have been obtained using palloc_get_page or palloc_get_multiple.