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;
112 KASSERT(bootInfo->memSizeKB > 0);
115 * Before we do anything, switch from setup.asm's temporary GDT
116 * to the kernel's permanent GDT.
121 * We'll put the list of Page objects right after the end
122 * of the kernel, and mark it as "kernel". This will bootstrap
123 * us sufficiently that we can start allocating pages and
124 * keeping track of them.
126 pageListAddr = Round_Up_To_Page((ulong_t) &end);
127 g_pageList = (struct Page*) pageListAddr;
128 kernEnd = Round_Up_To_Page(pageListAddr + numPageListBytes);
129 s_numPages = numPages;
134 * The initial kernel thread and its stack are placed
135 * just beyond the ISA hole.
137 //KASSERT(ISA_HOLE_END == KERN_THREAD_OBJ);
138 //KASSERT(KERN_STACK == KERN_THREAD_OBJ + PAGE_SIZE);
141 * Memory looks like this:
142 * 0 - start: available (might want to preserve BIOS data area)
143 * start - end: kernel
144 * end - ISA_HOLE_START: available
145 * ISA_HOLE_START - ISA_HOLE_END: used by hardware (and ROM BIOS?)
146 * ISA_HOLE_END - HIGHMEM_START: used by initial kernel thread
147 * HIGHMEM_START - end of memory: available
148 * (the kernel heap is located at HIGHMEM_START; any unused memory
149 * beyond that is added to the freelist)
153 * 0 - PAGE_SIZE: Unused
154 * PAGE_SIZE - (PAGE_SIZE+8192): init kernel thread stack
155 * (PAGE_SIZE+8192) - ISA_HOLE_START: Available
156 * ISA_HOLE_START - ISA_HOLE_END: HW
157 * ISA_HOLE_END - end: Kernel+PageList
158 * end - (end+1MB): heap
159 * (end+1MB) - end of mem: free
165 Add_Page_Range(0, PAGE_SIZE, PAGE_UNUSED);
166 // Add_Page_Range(PAGE_SIZE, KERNEL_START_ADDR, PAGE_AVAIL);
167 //Add_Page_Range(KERNEL_START_ADDR, kernEnd, PAGE_KERN);
168 //Add_Page_Range(kernEnd, ISA_HOLE_START, PAGE_AVAIL);
169 Add_Page_Range(PAGE_SIZE, PAGE_SIZE + 8192, PAGE_ALLOCATED);
170 Add_Page_Range(PAGE_SIZE + 8192, ISA_HOLE_START, PAGE_AVAIL);
171 Add_Page_Range(ISA_HOLE_START, ISA_HOLE_END, PAGE_HW);
172 //Add_Page_Range(ISA_HOLE_END, HIGHMEM_START, PAGE_ALLOCATED);
173 Add_Page_Range(HIGHMEM_START, kernEnd, PAGE_KERN);
174 Add_Page_Range(kernEnd, kernEnd + KERNEL_HEAP_SIZE, PAGE_HEAP);
176 Add_Page_Range(kernEnd + KERNEL_HEAP_SIZE, endOfMem, PAGE_AVAIL);
178 // Add_Page_Range(HIGHMEM_START, HIGHMEM_START + KERNEL_HEAP_SIZE, PAGE_HEAP);
179 // Add_Page_Range(HIGHMEM_START + KERNEL_HEAP_SIZE, endOfMem, PAGE_AVAIL);
181 /* Initialize the kernel heap */
182 // Init_Heap(HIGHMEM_START, KERNEL_HEAP_SIZE);
183 Init_Heap(kernEnd, KERNEL_HEAP_SIZE);
185 Print("%uKB memory detected, %u pages in freelist, %d bytes in kernel heap\n",
186 bootInfo->memSizeKB, g_freePageCount, KERNEL_HEAP_SIZE);
190 * Initialize the .bss section of the kernel executable image.
194 extern char BSS_START, BSS_END;
196 /* Fill .bss with zeroes */
197 memset(&BSS_START, '\0', &BSS_END - &BSS_START);
201 * Allocate a page of physical memory.
203 void* Alloc_Page(void)
208 bool iflag = Begin_Int_Atomic();
210 /* See if we have a free page */
211 if (!Is_Page_List_Empty(&s_freeList)) {
212 /* Remove the first page on the freelist. */
213 page = Get_Front_Of_Page_List(&s_freeList);
214 KASSERT((page->flags & PAGE_ALLOCATED) == 0);
215 Remove_From_Front_Of_Page_List(&s_freeList);
217 /* Mark page as having been allocated. */
218 page->flags |= PAGE_ALLOCATED;
220 result = (void*) Get_Page_Address(page);
223 End_Int_Atomic(iflag);
229 * Choose a page to evict.
230 * Returns null if no pages are available.
232 static struct Page *Find_Page_To_Page_Out()
235 struct Page *curr, *best;
239 for (i=0; i < s_numPages; i++) {
240 if ((g_pageList[i].flags & PAGE_PAGEABLE) &&
241 (g_pageList[i].flags & PAGE_ALLOCATED)) {
242 if (!best) best = &g_pageList[i];
243 curr = &g_pageList[i];
244 if ((curr->clock < best->clock) && (curr->flags & PAGE_PAGEABLE)) {
254 * Allocate a page of pageable physical memory, to be mapped
255 * into a user address space.
257 * @param entry pointer to user page table entry which will
258 * refer to the allocated page
259 * @param vaddr virtual address where page will be mapped
260 * in user address space
262 void* Alloc_Pageable_Page(pte_t *entry, ulong_t vaddr)
266 struct Page* page = 0;
268 iflag = Begin_Int_Atomic();
270 KASSERT(!Interrupts_Enabled());
271 KASSERT(Is_Page_Multiple(vaddr));
273 paddr = Alloc_Page();
275 page = Get_Page((ulong_t) paddr);
276 KASSERT((page->flags & PAGE_PAGEABLE) == 0);
280 /* Select a page to steal from another process */
281 Debug("About to hunt for a page to page out\n");
282 page = Find_Page_To_Page_Out();
283 KASSERT(page->flags & PAGE_PAGEABLE);
284 paddr = (void*) Get_Page_Address(page);
285 Debug("Selected page at addr %p (age = %d)\n", paddr, page->clock);
287 /* Find a place on disk for it */
288 pagefileIndex = Find_Space_On_Paging_File();
289 if (pagefileIndex < 0)
290 /* No space available in paging file. */
292 Debug("Free disk page at index %d\n", pagefileIndex);
294 /* Make the page temporarily unpageable (can't let another process steal it) */
295 page->flags &= ~(PAGE_PAGEABLE);
297 /* Lock the page so it cannot be freed while we're writing */
298 page->flags |= PAGE_LOCKED;
300 /* Write the page to disk. Interrupts are enabled, since the I/O may block. */
301 Debug("Writing physical frame %p to paging file at %d\n", paddr, pagefileIndex);
303 Write_To_Paging_File(paddr, page->vaddr, pagefileIndex);
304 Disable_Interrupts();
306 /* While we were writing got notification this page isn't even needed anymore */
307 if (page->flags & PAGE_ALLOCATED)
309 /* The page is still in use update its bookeping info */
310 /* Update page table to reflect the page being on disk */
311 page->entry->present = 0;
312 page->entry->kernelInfo = KINFO_PAGE_ON_DISK;
313 page->entry->pageBaseAddr = pagefileIndex; /* Remember where it is located! */
317 /* The page got freed, don't need bookeeping or it on disk */
318 Free_Space_On_Paging_File(pagefileIndex);
320 /* Its still allocated though to us now */
321 page->flags |= PAGE_ALLOCATED;
324 /* Unlock the page */
325 page->flags &= ~(PAGE_LOCKED);
327 /* XXX - flush TLB should only flush the one page */
331 /* Fill in accounting information for page */
332 page->flags |= PAGE_PAGEABLE;
334 page->entry->kernelInfo = 0;
336 KASSERT(page->flags & PAGE_ALLOCATED);
339 End_Int_Atomic(iflag);
344 * Free a page of physical memory.
346 void Free_Page(void* pageAddr)
348 ulong_t addr = (ulong_t) pageAddr;
352 iflag = Begin_Int_Atomic();
354 KASSERT(Is_Page_Multiple(addr));
356 /* Get the Page object for this page */
357 page = Get_Page(addr);
358 KASSERT((page->flags & PAGE_ALLOCATED) != 0);
360 /* Clear the allocation bit */
361 page->flags &= ~(PAGE_ALLOCATED);
363 /* When a page is locked, don't free it just let other thread know its not needed */
364 if (page->flags & PAGE_LOCKED)
367 /* Clear the pageable bit */
368 page->flags &= ~(PAGE_PAGEABLE);
370 /* Put the page back on the freelist */
371 Add_To_Back_Of_Page_List(&s_freeList, page);
374 End_Int_Atomic(iflag);