2 * Physical memory allocation
3 * Copyright (c) 2001,2003,2004 David H. Hovemeyer <daveho@cs.umd.edu>
4 * Copyright (c) 2003, Jeffrey K. Hollingsworth <hollings@cs.umd.edu>
7 * This is free software. You are permitted to use,
8 * redistribute, and modify it as specified in the file "COPYING".
11 #include <geekos/defs.h>
12 #include <geekos/ktypes.h>
13 #include <geekos/kassert.h>
14 #include <geekos/bootinfo.h>
15 #include <geekos/gdt.h>
16 #include <geekos/screen.h>
17 #include <geekos/int.h>
18 #include <geekos/malloc.h>
19 #include <geekos/string.h>
20 #include <geekos/paging.h>
21 #include <geekos/mem.h>
23 /* ----------------------------------------------------------------------
25 * ---------------------------------------------------------------------- */
28 * List of Page structures representing each page of physical memory.
30 struct Page* g_pageList;
33 * Number of pages currently available on the freelist.
35 uint_t g_freePageCount = 0;
37 /* ----------------------------------------------------------------------
38 * Private data and functions
39 * ---------------------------------------------------------------------- */
44 extern int debugFaults;
45 #define Debug(args...) if (debugFaults) Print(args)
48 * List of pages available for allocation.
50 static struct Page_List s_freeList;
53 * Total number of physical pages.
55 int unsigned s_numPages;
58 * Add a range of pages to the inventory of physical memory.
60 static void Add_Page_Range(ulong_t start, ulong_t end, int flags)
64 KASSERT(Is_Page_Multiple(start));
65 KASSERT(Is_Page_Multiple(end));
68 for (addr = start; addr < end; addr += PAGE_SIZE) {
69 struct Page *page = Get_Page(addr);
73 if (flags == PAGE_AVAIL) {
74 /* Add the page to the freelist */
75 Add_To_Back_Of_Page_List(&s_freeList, page);
77 /* Update free page count */
80 Set_Next_In_Page_List(page, 0);
81 Set_Prev_In_Page_List(page, 0);
90 /* ----------------------------------------------------------------------
92 * ---------------------------------------------------------------------- */
95 * The linker defines this symbol to indicate the end of
96 * the executable image.
101 * Initialize memory management data structures.
102 * Enables the use of Alloc_Page() and Free_Page() functions.
104 void Init_Mem(struct Boot_Info* bootInfo)
106 ulong_t numPages = bootInfo->memSizeKB >> 2;
107 ulong_t endOfMem = numPages * PAGE_SIZE;
108 unsigned numPageListBytes = sizeof(struct Page) * numPages;
109 ulong_t pageListAddr;
113 memset(&s_freeList, 0, sizeof(struct Page_List));
115 KASSERT(bootInfo->memSizeKB > 0);
116 Print("Booting with %d KB memory\n", bootInfo->memSizeKB);
119 * Before we do anything, switch from setup.asm's temporary GDT
120 * to the kernel's permanent GDT.
125 * We'll put the list of Page objects right after the end
126 * of the kernel, and mark it as "kernel". This will bootstrap
127 * us sufficiently that we can start allocating pages and
128 * keeping track of them.
130 pageListAddr = Round_Up_To_Page((ulong_t) &end);
131 g_pageList = (struct Page*) pageListAddr;
132 kernEnd = Round_Up_To_Page(pageListAddr + numPageListBytes);
133 s_numPages = numPages;
138 * The initial kernel thread and its stack are placed
139 * just beyond the ISA hole.
141 //KASSERT(ISA_HOLE_END == KERN_THREAD_OBJ);
142 //KASSERT(KERN_STACK == KERN_THREAD_OBJ + PAGE_SIZE);
145 * Memory looks like this:
146 * 0 - start: available (might want to preserve BIOS data area)
147 * start - end: kernel
148 * end - ISA_HOLE_START: available
149 * ISA_HOLE_START - ISA_HOLE_END: used by hardware (and ROM BIOS?)
150 * ISA_HOLE_END - HIGHMEM_START: used by initial kernel thread
151 * HIGHMEM_START - end of memory: available
152 * (the kernel heap is located at HIGHMEM_START; any unused memory
153 * beyond that is added to the freelist)
157 * 0 - PAGE_SIZE: Unused
158 * PAGE_SIZE - (PAGE_SIZE+8192): init kernel thread stack
159 * (PAGE_SIZE+8192) - ISA_HOLE_START: Available
160 * ISA_HOLE_START - ISA_HOLE_END: HW
161 * ISA_HOLE_END - end: Kernel+PageList
162 * end - (end+1MB): heap
163 * (end+1MB) - end of mem: free
169 Add_Page_Range(0, PAGE_SIZE, PAGE_UNUSED);
170 // Add_Page_Range(PAGE_SIZE, KERNEL_START_ADDR, PAGE_AVAIL);
171 //Add_Page_Range(KERNEL_START_ADDR, kernEnd, PAGE_KERN);
172 //Add_Page_Range(kernEnd, ISA_HOLE_START, PAGE_AVAIL);
173 Add_Page_Range(PAGE_SIZE, PAGE_SIZE + 8192, PAGE_ALLOCATED);
174 Add_Page_Range(PAGE_SIZE + 8192, ISA_HOLE_START, PAGE_AVAIL);
175 Add_Page_Range(ISA_HOLE_START, ISA_HOLE_END, PAGE_HW);
176 //Add_Page_Range(ISA_HOLE_END, HIGHMEM_START, PAGE_ALLOCATED);
177 Add_Page_Range(HIGHMEM_START, kernEnd, PAGE_KERN);
178 Add_Page_Range(kernEnd, kernEnd + KERNEL_HEAP_SIZE, PAGE_HEAP);
180 Add_Page_Range(kernEnd + KERNEL_HEAP_SIZE, endOfMem, PAGE_AVAIL);
182 // Add_Page_Range(HIGHMEM_START, HIGHMEM_START + KERNEL_HEAP_SIZE, PAGE_HEAP);
183 // Add_Page_Range(HIGHMEM_START + KERNEL_HEAP_SIZE, endOfMem, PAGE_AVAIL);
185 /* Initialize the kernel heap */
186 // Init_Heap(HIGHMEM_START, KERNEL_HEAP_SIZE);
188 Print("Initing heap\n");
189 Init_Heap(kernEnd, KERNEL_HEAP_SIZE);
191 Print("%uKB memory detected, %u pages in freelist, %d bytes in kernel heap\n",
192 bootInfo->memSizeKB, g_freePageCount, KERNEL_HEAP_SIZE);
196 * Initialize the .bss section of the kernel executable image.
200 extern char BSS_START, BSS_END;
202 /* Fill .bss with zeroes */
203 memset(&BSS_START, '\0', &BSS_END - &BSS_START);
207 * Allocate a page of physical memory.
209 void* Alloc_Page(void)
214 bool iflag = Begin_Int_Atomic();
216 /* See if we have a free page */
217 if (!Is_Page_List_Empty(&s_freeList)) {
218 /* Remove the first page on the freelist. */
219 page = Get_Front_Of_Page_List(&s_freeList);
220 KASSERT((page->flags & PAGE_ALLOCATED) == 0);
221 Remove_From_Front_Of_Page_List(&s_freeList);
223 /* Mark page as having been allocated. */
224 page->flags |= PAGE_ALLOCATED;
226 result = (void*) Get_Page_Address(page);
229 End_Int_Atomic(iflag);
235 * Choose a page to evict.
236 * Returns null if no pages are available.
238 static struct Page *Find_Page_To_Page_Out()
241 struct Page *curr, *best;
245 for (i=0; i < s_numPages; i++) {
246 if ((g_pageList[i].flags & PAGE_PAGEABLE) &&
247 (g_pageList[i].flags & PAGE_ALLOCATED)) {
248 if (!best) best = &g_pageList[i];
249 curr = &g_pageList[i];
250 if ((curr->clock < best->clock) && (curr->flags & PAGE_PAGEABLE)) {
260 * Allocate a page of pageable physical memory, to be mapped
261 * into a user address space.
263 * @param entry pointer to user page table entry which will
264 * refer to the allocated page
265 * @param vaddr virtual address where page will be mapped
266 * in user address space
268 void* Alloc_Pageable_Page(pte_t *entry, ulong_t vaddr)
272 struct Page* page = 0;
274 iflag = Begin_Int_Atomic();
276 KASSERT(!Interrupts_Enabled());
277 KASSERT(Is_Page_Multiple(vaddr));
279 paddr = Alloc_Page();
281 page = Get_Page((ulong_t) paddr);
282 KASSERT((page->flags & PAGE_PAGEABLE) == 0);
286 /* Select a page to steal from another process */
287 Debug("About to hunt for a page to page out\n");
288 page = Find_Page_To_Page_Out();
289 KASSERT(page->flags & PAGE_PAGEABLE);
290 paddr = (void*) Get_Page_Address(page);
291 Debug("Selected page at addr %p (age = %d)\n", paddr, page->clock);
293 /* Find a place on disk for it */
294 pagefileIndex = Find_Space_On_Paging_File();
295 if (pagefileIndex < 0)
296 /* No space available in paging file. */
298 Debug("Free disk page at index %d\n", pagefileIndex);
300 /* Make the page temporarily unpageable (can't let another process steal it) */
301 page->flags &= ~(PAGE_PAGEABLE);
303 /* Lock the page so it cannot be freed while we're writing */
304 page->flags |= PAGE_LOCKED;
306 /* Write the page to disk. Interrupts are enabled, since the I/O may block. */
307 Debug("Writing physical frame %p to paging file at %d\n", paddr, pagefileIndex);
309 Write_To_Paging_File(paddr, page->vaddr, pagefileIndex);
310 Disable_Interrupts();
312 /* While we were writing got notification this page isn't even needed anymore */
313 if (page->flags & PAGE_ALLOCATED)
315 /* The page is still in use update its bookeping info */
316 /* Update page table to reflect the page being on disk */
317 page->entry->present = 0;
318 page->entry->kernelInfo = KINFO_PAGE_ON_DISK;
319 page->entry->pageBaseAddr = pagefileIndex; /* Remember where it is located! */
323 /* The page got freed, don't need bookeeping or it on disk */
324 Free_Space_On_Paging_File(pagefileIndex);
326 /* Its still allocated though to us now */
327 page->flags |= PAGE_ALLOCATED;
330 /* Unlock the page */
331 page->flags &= ~(PAGE_LOCKED);
333 /* XXX - flush TLB should only flush the one page */
337 /* Fill in accounting information for page */
338 page->flags |= PAGE_PAGEABLE;
340 page->entry->kernelInfo = 0;
342 KASSERT(page->flags & PAGE_ALLOCATED);
345 End_Int_Atomic(iflag);
350 * Free a page of physical memory.
352 void Free_Page(void* pageAddr)
354 ulong_t addr = (ulong_t) pageAddr;
358 iflag = Begin_Int_Atomic();
360 KASSERT(Is_Page_Multiple(addr));
362 /* Get the Page object for this page */
363 page = Get_Page(addr);
364 KASSERT((page->flags & PAGE_ALLOCATED) != 0);
366 /* Clear the allocation bit */
367 page->flags &= ~(PAGE_ALLOCATED);
369 /* When a page is locked, don't free it just let other thread know its not needed */
370 if (page->flags & PAGE_LOCKED)
373 /* Clear the pageable bit */
374 page->flags &= ~(PAGE_PAGEABLE);
376 /* Put the page back on the freelist */
377 Add_To_Back_Of_Page_List(&s_freeList, page);
380 End_Int_Atomic(iflag);