misc/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     KASSERT(bootInfo->memSizeKB > 0);
 113
 114     /*
 115      * Before we do anything, switch from setup.asm's temporary GDT
 116      * to the kernel's permanent GDT.
 117      */
 118     Init_GDT();
 119
 120     /*
 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.
 125      */
 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;
 130
 131
 132
 133     /*
 134      * The initial kernel thread and its stack are placed
 135      * just beyond the ISA hole.
 136      */
 137     //KASSERT(ISA_HOLE_END == KERN_THREAD_OBJ);
 138     //KASSERT(KERN_STACK == KERN_THREAD_OBJ + PAGE_SIZE);
 139
 140     /*
 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)
 150      */
 151
 152     /* JRL CHANGE
 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
 160      *
 161      *
 162      */
 163
 164
 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);
 175
 176     Add_Page_Range(kernEnd + KERNEL_HEAP_SIZE, endOfMem, PAGE_AVAIL);
 177
 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);
 180
 181     /* Initialize the kernel heap */
 182     //    Init_Heap(HIGHMEM_START, KERNEL_HEAP_SIZE);
 183     Init_Heap(kernEnd, KERNEL_HEAP_SIZE);
 184
 185     Print("%uKB memory detected, %u pages in freelist, %d bytes in kernel heap\n",
 186         bootInfo->memSizeKB, g_freePageCount, KERNEL_HEAP_SIZE);
 187 }
 188
 189 /*
 190  * Initialize the .bss section of the kernel executable image.
 191  */
 192 void Init_BSS(void)
 193 {
 194     extern char BSS_START, BSS_END;
 195
 196     /* Fill .bss with zeroes */
 197     memset(&BSS_START, '\0', &BSS_END - &BSS_START);
 198 }
 199
 200 /*
 201  * Allocate a page of physical memory.
 202  */
 203 void* Alloc_Page(void)
 204 {
 205     struct Page* page;
 206     void *result = 0;
 207
 208     bool iflag = Begin_Int_Atomic();
 209
 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);
 216
 217         /* Mark page as having been allocated. */
 218         page->flags |= PAGE_ALLOCATED;
 219         g_freePageCount--;
 220         result = (void*) Get_Page_Address(page);
 221     }
 222
 223     End_Int_Atomic(iflag);
 224
 225     return result;
 226 }
 227
 228 /*
 229  * Choose a page to evict.
 230  * Returns null if no pages are available.
 231  */
 232 static struct Page *Find_Page_To_Page_Out()
 233 {
 234     int i;
 235     struct Page *curr, *best;
 236
 237     best = NULL;
 238
 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)) {
 245                 best = curr;
 246             }
 247         }
 248     }
 249
 250     return best;
 251 }
 252
 253 /**
 254  * Allocate a page of pageable physical memory, to be mapped
 255  * into a user address space.
 256  *
 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
 261  */
 262 void* Alloc_Pageable_Page(pte_t *entry, ulong_t vaddr)
 263 {
 264     bool iflag;
 265     void* paddr = 0;
 266     struct Page* page = 0;
 267
 268     iflag = Begin_Int_Atomic();
 269
 270     KASSERT(!Interrupts_Enabled());
 271     KASSERT(Is_Page_Multiple(vaddr));
 272
 273     paddr = Alloc_Page();
 274     if (paddr != 0) {
 275         page = Get_Page((ulong_t) paddr);
 276         KASSERT((page->flags & PAGE_PAGEABLE) == 0);
 277     } else {
 278         int pagefileIndex;
 279
 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);
 286
 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. */
 291             goto done;
 292         Debug("Free disk page at index %d\n", pagefileIndex);
 293
 294         /* Make the page temporarily unpageable (can't let another process steal it) */
 295         page->flags &= ~(PAGE_PAGEABLE);
 296
 297         /* Lock the page so it cannot be freed while we're writing */
 298         page->flags |= PAGE_LOCKED;
 299
 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);
 302         Enable_Interrupts();
 303         Write_To_Paging_File(paddr, page->vaddr, pagefileIndex);
 304         Disable_Interrupts();
 305
 306         /* While we were writing got notification this page isn't even needed anymore */
 307         if (page->flags & PAGE_ALLOCATED)
 308         {
 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! */
 314         }
 315         else
 316         {
 317            /* The page got freed, don't need bookeeping or it on disk */
 318            Free_Space_On_Paging_File(pagefileIndex);
 319
 320            /* Its still allocated though to us now */
 321            page->flags |= PAGE_ALLOCATED;
 322         }
 323
 324         /* Unlock the page */
 325         page->flags &= ~(PAGE_LOCKED);
 326
 327         /* XXX - flush TLB should only flush the one page */
 328         Flush_TLB();
 329     }
 330
 331     /* Fill in accounting information for page */
 332     page->flags |= PAGE_PAGEABLE;
 333     page->entry = entry;
 334     page->entry->kernelInfo = 0;
 335     page->vaddr = vaddr;
 336     KASSERT(page->flags & PAGE_ALLOCATED);
 337
 338 done:
 339     End_Int_Atomic(iflag);
 340     return paddr;
 341 }
 342
 343 /*
 344  * Free a page of physical memory.
 345  */
 346 void Free_Page(void* pageAddr)
 347 {
 348     ulong_t addr = (ulong_t) pageAddr;
 349     struct Page* page;
 350     bool iflag;
 351
 352     iflag = Begin_Int_Atomic();
 353
 354     KASSERT(Is_Page_Multiple(addr));
 355
 356     /* Get the Page object for this page */
 357     page = Get_Page(addr);
 358     KASSERT((page->flags & PAGE_ALLOCATED) != 0);
 359
 360     /* Clear the allocation bit */
 361     page->flags &= ~(PAGE_ALLOCATED);
 362
 363     /* When a page is locked, don't free it just let other thread know its not needed */
 364     if (page->flags & PAGE_LOCKED)
 365       return;
 366
 367     /* Clear the pageable bit */
 368     page->flags &= ~(PAGE_PAGEABLE);
 369
 370     /* Put the page back on the freelist */
 371     Add_To_Back_Of_Page_List(&s_freeList, page);
 372     g_freePageCount++;
 373
 374     End_Int_Atomic(iflag);
 375 }