test/geekos_test_vm/src/geekos/mem.c

   1 /*
   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>
   5  * $Revision: 1.1 $
   6  *
   7  * This is free software.  You are permitted to use,
   8  * redistribute, and modify it as specified in the file "COPYING".
   9  */
  10
  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>
  22
  23 /* ----------------------------------------------------------------------
  24  * Global data
  25  * ---------------------------------------------------------------------- */
  26
  27 /*
  28  * List of Page structures representing each page of physical memory.
  29  */
  30 struct Page* g_pageList;
  31
  32 /*
  33  * Number of pages currently available on the freelist.
  34  */
  35 uint_t g_freePageCount = 0;
  36
  37 /* ----------------------------------------------------------------------
  38  * Private data and functions
  39  * ---------------------------------------------------------------------- */
  40
  41 /*
  42  * Defined in paging.c
  43  */
  44 extern int debugFaults;
  45 #define Debug(args...) if (debugFaults) Print(args)
  46
  47 /*
  48  * List of pages available for allocation.
  49  */
  50 static struct Page_List s_freeList;
  51
  52 /*
  53  * Total number of physical pages.
  54  */
  55 int unsigned s_numPages;
  56
  57 /*
  58  * Add a range of pages to the inventory of physical memory.
  59  */
  60 static void Add_Page_Range(ulong_t start, ulong_t end, int flags)
  61 {
  62     ulong_t addr;
  63
  64     KASSERT(Is_Page_Multiple(start));
  65     KASSERT(Is_Page_Multiple(end));
  66     KASSERT(start < end);
  67
  68     for (addr = start; addr < end; addr += PAGE_SIZE) {
  69         struct Page *page = Get_Page(addr);
  70
  71         page->flags = flags;
  72
  73         if (flags == PAGE_AVAIL) {
  74             /* Add the page to the freelist */
  75             Add_To_Back_Of_Page_List(&s_freeList, page);
  76
  77             /* Update free page count */
  78             ++g_freePageCount;
  79         } else {
  80             Set_Next_In_Page_List(page, 0);
  81             Set_Prev_In_Page_List(page, 0);
  82         }
  83
  84         page->clock = 0;
  85         page->vaddr = 0;
  86         page->entry = 0;
  87     }
  88 }
  89
  90 /* ----------------------------------------------------------------------
  91  * Public functions
  92  * ---------------------------------------------------------------------- */
  93
  94 /*
  95  * The linker defines this symbol to indicate the end of
  96  * the executable image.
  97  */
  98 extern char end;
  99
 100 /*
 101  * Initialize memory management data structures.
 102  * Enables the use of Alloc_Page() and Free_Page() functions.
 103  */
 104 void Init_Mem(struct Boot_Info* bootInfo)
 105 {
 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;
 110     ulong_t kernEnd;
 111
 112
 113     memset(&s_freeList, 0, sizeof(struct Page_List));
 114
 115     KASSERT(bootInfo->memSizeKB > 0);
 116     Print("Booting with %d KB memory\n", bootInfo->memSizeKB);
 117
 118     /*
 119      * Before we do anything, switch from setup.asm's temporary GDT
 120      * to the kernel's permanent GDT.
 121      */
 122     Init_GDT();
 123
 124     /*
 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.
 129      */
 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;
 134
 135
 136
 137     /*
 138      * The initial kernel thread and its stack are placed
 139      * just beyond the ISA hole.
 140      */
 141     //KASSERT(ISA_HOLE_END == KERN_THREAD_OBJ);
 142     //KASSERT(KERN_STACK == KERN_THREAD_OBJ + PAGE_SIZE);
 143
 144     /*
 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)
 154      */
 155
 156     /* JRL CHANGE
 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
 164      *
 165      *
 166      */
 167
 168
 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);
 179
 180     Add_Page_Range(kernEnd + KERNEL_HEAP_SIZE, endOfMem, PAGE_AVAIL);
 181
 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);
 184
 185     /* Initialize the kernel heap */
 186     //    Init_Heap(HIGHMEM_START, KERNEL_HEAP_SIZE);
 187
 188     Print("Initing heap\n");
 189     Init_Heap(kernEnd, KERNEL_HEAP_SIZE);
 190
 191     Print("%uKB memory detected, %u pages in freelist, %d bytes in kernel heap\n",
 192           bootInfo->memSizeKB, g_freePageCount, KERNEL_HEAP_SIZE);
 193 }
 194
 195 /*
 196  * Initialize the .bss section of the kernel executable image.
 197  */
 198 void Init_BSS(void)
 199 {
 200     extern char BSS_START, BSS_END;
 201
 202     /* Fill .bss with zeroes */
 203     memset(&BSS_START, '\0', &BSS_END - &BSS_START);
 204 }
 205
 206 /*
 207  * Allocate a page of physical memory.
 208  */
 209 void* Alloc_Page(void)
 210 {
 211     struct Page* page;
 212     void *result = 0;
 213
 214     bool iflag = Begin_Int_Atomic();
 215
 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);
 222
 223         /* Mark page as having been allocated. */
 224         page->flags |= PAGE_ALLOCATED;
 225         g_freePageCount--;
 226         result = (void*) Get_Page_Address(page);
 227     }
 228
 229     End_Int_Atomic(iflag);
 230
 231     return result;
 232 }
 233
 234 /*
 235  * Choose a page to evict.
 236  * Returns null if no pages are available.
 237  */
 238 static struct Page *Find_Page_To_Page_Out()
 239 {
 240     int i;
 241     struct Page *curr, *best;
 242
 243     best = NULL;
 244
 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)) {
 251                 best = curr;
 252             }
 253         }
 254     }
 255
 256     return best;
 257 }
 258
 259 /**
 260  * Allocate a page of pageable physical memory, to be mapped
 261  * into a user address space.
 262  *
 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
 267  */
 268 void* Alloc_Pageable_Page(pte_t *entry, ulong_t vaddr)
 269 {
 270     bool iflag;
 271     void* paddr = 0;
 272     struct Page* page = 0;
 273
 274     iflag = Begin_Int_Atomic();
 275
 276     KASSERT(!Interrupts_Enabled());
 277     KASSERT(Is_Page_Multiple(vaddr));
 278
 279     paddr = Alloc_Page();
 280     if (paddr != 0) {
 281         page = Get_Page((ulong_t) paddr);
 282         KASSERT((page->flags & PAGE_PAGEABLE) == 0);
 283     } else {
 284         int pagefileIndex;
 285
 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);
 292
 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. */
 297             goto done;
 298         Debug("Free disk page at index %d\n", pagefileIndex);
 299
 300         /* Make the page temporarily unpageable (can't let another process steal it) */
 301         page->flags &= ~(PAGE_PAGEABLE);
 302
 303         /* Lock the page so it cannot be freed while we're writing */
 304         page->flags |= PAGE_LOCKED;
 305
 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);
 308         Enable_Interrupts();
 309         Write_To_Paging_File(paddr, page->vaddr, pagefileIndex);
 310         Disable_Interrupts();
 311
 312         /* While we were writing got notification this page isn't even needed anymore */
 313         if (page->flags & PAGE_ALLOCATED)
 314         {
 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! */
 320         }
 321         else
 322         {
 323            /* The page got freed, don't need bookeeping or it on disk */
 324            Free_Space_On_Paging_File(pagefileIndex);
 325
 326            /* Its still allocated though to us now */
 327            page->flags |= PAGE_ALLOCATED;
 328         }
 329
 330         /* Unlock the page */
 331         page->flags &= ~(PAGE_LOCKED);
 332
 333         /* XXX - flush TLB should only flush the one page */
 334         Flush_TLB();
 335     }
 336
 337     /* Fill in accounting information for page */
 338     page->flags |= PAGE_PAGEABLE;
 339     page->entry = entry;
 340     page->entry->kernelInfo = 0;
 341     page->vaddr = vaddr;
 342     KASSERT(page->flags & PAGE_ALLOCATED);
 343
 344 done:
 345     End_Int_Atomic(iflag);
 346     return paddr;
 347 }
 348
 349 /*
 350  * Free a page of physical memory.
 351  */
 352 void Free_Page(void* pageAddr)
 353 {
 354     ulong_t addr = (ulong_t) pageAddr;
 355     struct Page* page;
 356     bool iflag;
 357
 358     iflag = Begin_Int_Atomic();
 359
 360     KASSERT(Is_Page_Multiple(addr));
 361
 362     /* Get the Page object for this page */
 363     page = Get_Page(addr);
 364     KASSERT((page->flags & PAGE_ALLOCATED) != 0);
 365
 366     /* Clear the allocation bit */
 367     page->flags &= ~(PAGE_ALLOCATED);
 368
 369     /* When a page is locked, don't free it just let other thread know its not needed */
 370     if (page->flags & PAGE_LOCKED)
 371       return;
 372
 373     /* Clear the pageable bit */
 374     page->flags &= ~(PAGE_PAGEABLE);
 375
 376     /* Put the page back on the freelist */
 377     Add_To_Back_Of_Page_List(&s_freeList, page);
 378     g_freePageCount++;
 379
 380     End_Int_Atomic(iflag);
 381 }