Physical memory init uses multiboot info
authorBarret Rhoden <brho@cs.berkeley.edu>
Sun, 16 Jun 2013 00:20:04 +0000 (17:20 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Sat, 22 Jun 2013 17:29:30 +0000 (10:29 -0700)
The old style of trusting only the BIOS memory detection, would miss out
on pmem above 4GB.  Additionally, we were assuming the area from right
above the kernel til the end of extended memory was free, instead of
checking the mmap ranges.

Now we parse the multiboot info to figure out which memory ranges are
really free.  Additionally, we use the largest range (which might not be
the one the kernel is already sitting in) for our boot allocator.
Systems with obscene amounts of RAM (256GB) will need more RAM than fits
in extended memory (~6GB for the pages array).

Anyway, we try to handle situations whether or not the kernel is in the
boot allocator zone, whether the zone is larger than addressable
physical memory, and a bunch of other things.

18 files changed:
kern/arch/riscv/page_alloc.c
kern/arch/riscv/pmap.c
kern/arch/x86/frontend.c
kern/arch/x86/page_alloc.c
kern/arch/x86/pmap32.c
kern/arch/x86/pmap64.c
kern/arch/x86/ros/mmu32.h
kern/arch/x86/ros/mmu64.h
kern/include/kmalloc.h
kern/include/multiboot.h
kern/include/page_alloc.h
kern/include/pmap.h
kern/include/ros/memlayout.h
kern/src/init.c
kern/src/kmalloc.c
kern/src/multiboot.c
kern/src/page_alloc.c
kern/src/pmap.c

index 3e6a0c4..d76734d 100644 (file)
@@ -29,7 +29,7 @@ spinlock_t colored_page_free_list_lock = SPINLOCK_INITIALIZER_IRQSAVE;
  * to allocate and deallocate physical memory via the 
  * page_free_lists. 
  */
-void page_alloc_init(
+void page_alloc_init(struct multiboot_info *mbi)
 {
        init_once_racy(return);
 
@@ -40,9 +40,9 @@ void page_alloc_init()
        for (size_t i = 0; i < num_colors; i++)
                LIST_INIT(&lists[i]);
        
-       uintptr_t first_free_page = LA2PPN(PADDR(ROUNDUP(boot_freemem, PGSIZE)));
-       uintptr_t first_invalid_page = LA2PPN(maxaddrpa);
-       assert(first_invalid_page == npages);
+       uintptr_t first_free_page = ROUNDUP(boot_freemem, PGSIZE);
+       uintptr_t first_invalid_page = LA2PPN(boot_freelimit);
+       assert(first_invalid_page == max_nr_pages);
 
        // mark kernel pages as in-use
        for (uintptr_t page = 0; page < first_free_page; page++)
@@ -54,6 +54,7 @@ void page_alloc_init()
                page_setref(&pages[page], 0);
                LIST_INSERT_HEAD(&lists[page & (num_colors-1)], &pages[page], pg_link);
        }
+       nr_free_pages = first_invalid_page - first_free_page;
 
        colored_page_free_list = lists;
 }
index 981b43d..4ce640c 100644 (file)
@@ -17,7 +17,6 @@
 
 pde_t* boot_pgdir;             // Virtual address of boot time page directory
 physaddr_t boot_cr3;           // Physical address of boot time page directory
-page_t* pages = NULL;          // Virtual address of physical page array
 
 // --------------------------------------------------------------
 // Set up initial memory mappings and turn on MMU.
index bd4ef0f..72c80ae 100644 (file)
@@ -21,7 +21,7 @@ int handle_appserver_packet(const char* p, size_t size)
 
        uintptr_t paddr = ntohl(packet->header.addr);
        size_t copy_size = ntohl(packet->header.payload_size);
-       if(paddr % 4 || paddr >= maxaddrpa)
+       if(paddr % 4 || paddr >= max_paddr)
                goto fail;
        if(copy_size % 4 || copy_size > APPSERVER_MAX_PAYLOAD_SIZE)
                goto fail;
index 694a0d9..6f8ec8e 100644 (file)
@@ -14,6 +14,7 @@
 #include <page_alloc.h>
 #include <pmap.h>
 #include <kmalloc.h>
+#include <multiboot.h>
 
 spinlock_t colored_page_free_list_lock = SPINLOCK_INITIALIZER_IRQSAVE;
 
@@ -26,72 +27,143 @@ static void page_alloc_bootstrap() {
        page_list_t LCKD(&colored_page_free_list_lock)*tmp =
            (page_list_t*)boot_alloc(list_size,PGSIZE);
        colored_page_free_list = SINIT(tmp);
+       for (int i = 0; i < llc_cache->num_colors; i++)
+               LIST_INIT(&colored_page_free_list[i]);
+}
+
+/* Can do whatever here.  For now, our page allocator just works with colors,
+ * not NUMA zones or anything. */
+static void track_free_page(struct page *page)
+{
+       LIST_INSERT_HEAD(&colored_page_free_list[get_page_color(page2ppn(page),
+                                                               llc_cache)],
+                        page, pg_link);
+       nr_free_pages++;
+}
+
+static struct page *pa64_to_page(uint64_t paddr)
+{
+       return &pages[paddr >> PGSHIFT];
+}
+
+static bool pa64_is_in_kernel(uint64_t paddr)
+{
+       extern char end[];
+       /* kernel is linked and loaded here (in kernel{32,64}.ld */
+       return (EXTPHYSMEM <= paddr) && (paddr <= PADDR(end));
 }
 
-/*
- * Initialize the memory free lists.
- * After this point, ONLY use the functions below
- * to allocate and deallocate physical memory via the 
- * page_free_lists. 
- */
-void page_alloc_init()
+/* Helper.  For every page in the entry, this will determine whther or not the
+ * page is free, and handle accordingly. */
+static void parse_mboot_region(struct multiboot_mmap_entry *entry, void *data)
 {
-       // First Bootstrap the page alloc process
-       static bool RO bootstrapped = FALSE;
-       if (!bootstrapped) {
-               bootstrapped = SINIT(TRUE);
-               page_alloc_bootstrap();
+       physaddr_t boot_freemem_paddr = (physaddr_t)data;
+       bool in_bootzone = (entry->addr <= boot_freemem_paddr) &&
+                          (boot_freemem_paddr < entry->addr + entry->len);
+
+       if (entry->type != MULTIBOOT_MEMORY_AVAILABLE)
+               return;
+       /* TODO: we'll have some issues with jumbo allocation */
+       for (uint64_t i = ROUNDUP(entry->addr, PGSIZE);
+            i < entry->addr + entry->len;
+            i += PGSIZE) {
+               /* Skip pages we'll never map (above KERNBASE).  Once we hit one of
+                * them, we know the rest are too (for this entry). */
+               if (i >= max_paddr)
+                       return;
+               /* Mark low mem as busy (multiboot stuff is there, usually, too).  Since
+                * that memory may be freed later (like the smp_boot page), we'll treat
+                * it like it is busy/allocated. */
+               if (i < EXTPHYSMEM)
+                       goto page_busy;
+               /* Mark as busy pages already allocated in boot_alloc() */
+               if (in_bootzone && (i < boot_freemem_paddr))
+                       goto page_busy;
+               /* Need to double check for the kernel, in case it wasn't in the
+                * bootzone.  If it was in the bootzone, we already skipped it. */
+               if (pa64_is_in_kernel(i))
+                       goto page_busy;
+               track_free_page(pa64_to_page(i));
+               continue;
+page_busy:
+               page_setref(pa64_to_page(i), 1);
        }
+}
 
-       // Then, initialize the array required to manage the colored page free list
-       for (int i = 0; i < llc_cache->num_colors; i++)
-               LIST_INIT(&(colored_page_free_list[i]));
+static void check_range(uint64_t start, uint64_t end, int expect)
+{
+       int ref;
+       if (PGOFF(start))
+               printk("Warning: check_range given an unaligned addr %p\n", start);
+       for (uint64_t i = start; i < end; i += PGSIZE)  {
+               ref = kref_refcnt(&pa64_to_page(i)->pg_kref);
+               if (ref != expect) {
+                       printk("Error: physaddr %p refcnt was %d, expected %d\n", i, ref,
+                              expect);
+                       panic("");
+               }
+       }
+}
 
-       //  Then, mark the pages already in use by the kernel. 
-       //  1) Mark page 0 as in use.
-       //     This way we preserve the real-mode IDT and BIOS structures
-       //     in case we ever need them.  (Currently we don't, but...)
-       //  2) Mark the rest of base memory as free.
-       //  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM).
-       //     Mark it as in use so that it can never be allocated.      
-       //  4) Then extended memory [EXTPHYSMEM, ...).
-       //     Some of it is in use, some is free.
-       int i;
-       extern char (SNT RO end)[];
-       /* TODO 64b Might need to translate to the KERNBASE mapping */
-       physaddr_t physaddr_after_kernel = PADDR(PTRROUNDUP(boot_freemem, PGSIZE));
+static void check_mboot_region(struct multiboot_mmap_entry *entry, void *data)
+{
+       extern char end[];
+       physaddr_t boot_freemem_paddr = (physaddr_t)data;
+       bool in_bootzone = (entry->addr <= boot_freemem_paddr) &&
+                          (boot_freemem_paddr < entry->addr + entry->len);
+       /* Need to deal with 32b wrap-around */
+       uint64_t zone_end = MIN(entry->addr + entry->len, (uint64_t)max_paddr);
 
-       page_setref(&pages[0], 1);
-       // alloc the second page, since we will need it later to init the other cores
-       // probably need to be smarter about what page we use (make this dynamic) TODO
-       page_setref(&pages[1], 1);
-       for (i = 2; i < LA2PPN(IOPHYSMEM); i++) {
-               /* this ought to be unnecessary */
-               page_setref(&pages[i], 0);
-               LIST_INSERT_HEAD(
-                  &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), 
-                                                              llc_cache)]),
-                  &pages[i],
-                  pg_link
-               );
+       if (entry->type != MULTIBOOT_MEMORY_AVAILABLE)
+               return;
+       if (zone_end <= EXTPHYSMEM) {
+               check_range(entry->addr, zone_end, 1);
+               return;
        }
-       for (i = LA2PPN(IOPHYSMEM); i < LA2PPN(EXTPHYSMEM); i++)
-               page_setref(&pages[i], 1);
-       for (i = LA2PPN(EXTPHYSMEM); i < LA2PPN(physaddr_after_kernel); i++)
-               page_setref(&pages[i], 1);
-       for (i = LA2PPN(physaddr_after_kernel); i < LA2PPN(maxaddrpa); i++) {
-               page_setref(&pages[i], 0);
-               LIST_INSERT_HEAD(
-                  &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), 
-                                                              llc_cache)]),
-                  &pages[i],
-                  pg_link
-               );
+       /* this may include the kernel */
+       if (in_bootzone) {
+               /* boot_freemem might not be page aligned.  If it's part-way through a
+                * page, that page should be busy */
+               check_range(entry->addr, ROUNDUP(PADDR(boot_freemem), PGSIZE), 1);
+               check_range(ROUNDUP(PADDR(boot_freemem), PGSIZE), zone_end, 0);
+               assert(zone_end == PADDR(boot_freelimit));
+               return;
+       }
+       /* kernel's range (hardcoded in the linker script).  If we're checking now,
+        * it means the kernel is not in the same entry as the bootzone. */
+       if (entry->addr == EXTPHYSMEM) {
+               check_range(EXTPHYSMEM, PADDR(end), 1);
+               check_range(ROUNDUP(PADDR(end), PGSIZE), zone_end, 0);
+               return;
        }
-       // this block out all memory above maxaddrpa.  will need another mechanism
-       // to allocate and map these into the kernel address space
-       for (i = LA2PPN(maxaddrpa); i < npages; i++)
-               page_setref(&pages[i], 1);
-       printk("Page alloc init successful\n");
 }
 
+/* Initialize the memory free lists.  After this, do not use boot_alloc. */
+void page_alloc_init(struct multiboot_info *mbi)
+{
+       page_alloc_bootstrap();
+       /* To init the free list(s), each page that is already allocated/busy will
+        * get increfed.  All other pages that were reported as 'free' will be added
+        * to a free list.  Their refcnts are all 0 (when pages was memset).
+        *
+        * To avoid a variety of headaches, any memory below 1MB is considered busy.
+        * Likewise, everything in the kernel, up to _end is also busy.  And
+        * everything we've already boot_alloc'd is busy.
+        *
+        * We'll also abort the mapping for any addresses over max_paddr, since
+        * we'll never use them.  'pages' does not track them either.
+        *
+        * One special note: we actually use the memory at 0x1000 for smp_boot.
+        * It'll get set to 'used' like the others; just FYI.
+        *
+        * Finally, if we want to use actual jumbo page allocation (not just
+        * mapping), we need to round up _end, and make sure all of multiboot's
+        * sections are jumbo-aligned. */
+       physaddr_t boot_freemem_paddr = PADDR(PTRROUNDUP(boot_freemem, PGSIZE));
+
+       mboot_foreach_mmap(mbi, parse_mboot_region, (void*)boot_freemem_paddr);
+       printk("Number of free pages: %lu\n", nr_free_pages);
+       /* Test the page alloc - if this gets slow, we can CONFIG it */
+       mboot_foreach_mmap(mbi, check_mboot_region, (void*)boot_freemem_paddr);
+       printk("Page alloc init successful\n");
+}
index b79f9e5..7493651 100644 (file)
@@ -26,9 +26,6 @@
 pde_t* boot_pgdir;             // Virtual address of boot time page directory
 physaddr_t RO boot_cr3;                // Physical address of boot time page directory
 
-// Global variables
-page_t *RO pages = NULL;          // Virtual address of physical page array
-
 // Global descriptor table.
 //
 // The kernel and user segments are identical (except for the DPL).
@@ -259,10 +256,10 @@ vm_init(void)
        if (pse) {
                // map the first 4MB as regular entries, to support different MTRRs
                boot_map_segment(pgdir, KERNBASE, JPGSIZE, 0, PTE_W | PTE_G);
-               boot_map_segment(pgdir, KERNBASE + JPGSIZE, maxaddrpa - JPGSIZE, JPGSIZE,
+               boot_map_segment(pgdir, KERNBASE + JPGSIZE, max_paddr - JPGSIZE, JPGSIZE,
                                 PTE_W | PTE_G | PTE_PS);
        } else
-               boot_map_segment(pgdir, KERNBASE, maxaddrpa, 0, PTE_W | PTE_G);
+               boot_map_segment(pgdir, KERNBASE, max_paddr, 0, PTE_W | PTE_G);
 
        // APIC mapping: using PAT (but not *the* PAT flag) to make these type UC
        // IOAPIC
@@ -355,10 +352,10 @@ check_boot_pgdir(bool pse)
        //for (i = 0; KERNBASE + i != 0; i += PGSIZE)
        // adjusted check to account for only mapping avail mem
        if (pse)
-               for (i = 0; i < maxaddrpa; i += JPGSIZE)
+               for (i = 0; i < max_paddr; i += JPGSIZE)
                        assert(check_va2pa(pgdir, KERNBASE + i) == i);
        else
-               for (i = 0; i < maxaddrpa; i += PGSIZE)
+               for (i = 0; i < max_paddr; i += PGSIZE)
                        assert(check_va2pa(pgdir, KERNBASE + i) == i);
 
        // check for zero/non-zero in PDEs
@@ -373,8 +370,8 @@ check_boot_pgdir(bool pse)
                        //if (i >= PDX(KERNBASE))
                        // adjusted check to account for only mapping avail mem
                        // and you can't KADDR maxpa (just above legal range)
-                       // maxaddrpa can be up to maxpa, so assume the worst
-                       if (i >= PDX(KERNBASE) && i <= PDX(KADDR(maxaddrpa-1)))
+                       // max_paddr can be up to maxpa, so assume the worst
+                       if (i >= PDX(KERNBASE) && i <= PDX(KADDR(max_paddr-1)))
                                assert(pgdir[i]);
                        else
                                assert(pgdir[i] == 0);
@@ -406,7 +403,7 @@ check_boot_pgdir(bool pse)
                }
        }
        // kernel read-write.
-       for (i = ULIM; i <= KERNBASE + maxaddrpa - PGSIZE; i+=PGSIZE) {
+       for (i = ULIM; i <= KERNBASE + max_paddr - PGSIZE; i+=PGSIZE) {
                pte = get_va_perms(pgdir, (void*SAFE)TC(i));
                if ((pte & PTE_P) && (i != VPT+(UVPT>>10))) {
                        assert((pte & PTE_U) != PTE_U);
index 31ab9ca..1c529b8 100644 (file)
@@ -26,9 +26,6 @@
 pde_t* boot_pgdir;             // Virtual address of boot time page directory
 physaddr_t RO boot_cr3;                // Physical address of boot time page directory
 
-// Global variables
-page_t *RO pages = NULL;          // Virtual address of physical page array
-
 // Global descriptor table.
 //
 // The kernel and user segments are identical (except for the DPL).
@@ -181,6 +178,9 @@ boot_map_segment(pde_t *COUNT(NPDENTRIES) pgdir, uintptr_t la, size_t size, phys
 void
 vm_init(void)
 {
+// TODO: do this
+       return;
+
        pde_t* pgdir;
        uint32_t cr0, edx;
        size_t n;
@@ -196,6 +196,7 @@ vm_init(void)
        lcr4(rcr4() | CR4_PGE);
 
        // set up mtrr's for core0.  other cores will do the same later
+       // XXX this will break c89
        setup_default_mtrrs(0);
 
        /*
@@ -261,10 +262,10 @@ vm_init(void)
        if (pse) {
                // map the first 4MB as regular entries, to support different MTRRs
                boot_map_segment(pgdir, KERNBASE, JPGSIZE, 0, PTE_W | PTE_G);
-               boot_map_segment(pgdir, KERNBASE + JPGSIZE, maxaddrpa - JPGSIZE, JPGSIZE,
+               boot_map_segment(pgdir, KERNBASE + JPGSIZE, max_paddr - JPGSIZE, JPGSIZE,
                                 PTE_W | PTE_G | PTE_PS);
        } else
-               boot_map_segment(pgdir, KERNBASE, maxaddrpa, 0, PTE_W | PTE_G);
+               boot_map_segment(pgdir, KERNBASE, max_paddr, 0, PTE_W | PTE_G);
 
        // APIC mapping: using PAT (but not *the* PAT flag) to make these type UC
        // IOAPIC
@@ -359,10 +360,10 @@ check_boot_pgdir(bool pse)
        //for (i = 0; KERNBASE + i != 0; i += PGSIZE)
        // adjusted check to account for only mapping avail mem
        if (pse)
-               for (i = 0; i < maxaddrpa; i += JPGSIZE)
+               for (i = 0; i < max_paddr; i += JPGSIZE)
                        assert(check_va2pa(pgdir, KERNBASE + i) == i);
        else
-               for (i = 0; i < maxaddrpa; i += PGSIZE)
+               for (i = 0; i < max_paddr; i += PGSIZE)
                        assert(check_va2pa(pgdir, KERNBASE + i) == i);
 
        // check for zero/non-zero in PDEs
@@ -378,8 +379,8 @@ check_boot_pgdir(bool pse)
                        //if (i >= PDX(KERNBASE))
                        // adjusted check to account for only mapping avail mem
                        // and you can't KADDR maxpa (just above legal range)
-                       // maxaddrpa can be up to maxpa, so assume the worst
-                       if (i >= PDX(KERNBASE) && i <= PDX(KADDR(maxaddrpa-1)))
+                       // max_paddr can be up to maxpa, so assume the worst
+                       if (i >= PDX(KERNBASE) && i <= PDX(KADDR(max_paddr-1)))
                                assert(pgdir[i]);
                        else
                                assert(pgdir[i] == 0);
@@ -411,7 +412,7 @@ check_boot_pgdir(bool pse)
                }
        }
        // kernel read-write.
-       for (i = ULIM; i <= KERNBASE + maxaddrpa - PGSIZE; i+=PGSIZE) {
+       for (i = ULIM; i <= KERNBASE + max_paddr - PGSIZE; i+=PGSIZE) {
                pte = get_va_perms(pgdir, (void*SAFE)TC(i));
                if ((pte & PTE_P) && (i != VPT+(UVPT>>10))) {
                        assert((pte & PTE_U) != PTE_U);
index 3a74b75..c359a79 100644 (file)
@@ -95,6 +95,7 @@ typedef unsigned long pde_t;
 #define VGAPHYSMEM     0x0A0000
 #define DEVPHYSMEM     0x0C0000
 #define BIOSPHYSMEM    0x0F0000
+#define EXTPHYSMEM     0x100000
 
 /* **************************************** */
 /* Kernel Virtual Memory Mapping  (not really an MMU thing) */
@@ -140,7 +141,7 @@ typedef unsigned long pde_t;
 // use PGADDR(PDX(la), PTX(la), PGOFF(la)).
 
 // page number field of address
-#define LA2PPN(la)     (((uintptr_t) (la)) >> PTXSHIFT)
+#define LA2PPN(la)     (((uintptr_t) (la)) >> PGSHIFT)
 #define PTE2PPN(pte)   LA2PPN(pte)
 #define VPN(la)                PPN(la)         // used to index into vpt[]
 
index 1a98a29..857b2b0 100644 (file)
@@ -145,7 +145,7 @@ typedef unsigned long pde_t;
 // use PGADDR(PDX(la), PTX(la), PGOFF(la)).
 
 // page number field of address
-#define LA2PPN(la)     (((uintptr_t) (la)) >> PTXSHIFT)
+#define LA2PPN(la)     (((uintptr_t) (la)) >> PGSHIFT)
 #define PTE2PPN(pte)   LA2PPN(pte)
 #define VPN(la)                PPN(la)         // used to index into vpt[]
 
index f3bea8d..c2774cf 100644 (file)
@@ -16,9 +16,6 @@
 #define KMALLOC_LARGEST KMALLOC_SMALLEST << NUM_KMALLOC_CACHES
 #define KMALLOC_OFFSET ROUNDUP(sizeof(struct kmalloc_tag), KMALLOC_ALIGNMENT)
 
-void* (DALLOC(n) boot_alloc)(uint32_t n, uint32_t align);
-void* (DALLOC(n*sz) boot_calloc)(uint32_t n, size_t sz, uint32_t align);
-
 void kmalloc_init(void);
 void* (DALLOC(size) kmalloc)(size_t size, int flags);
 void* (DALLOC(size) krealloc)(void* buf, size_t size, int flags);
index 4b55497..dcd2bbe 100644 (file)
@@ -3,11 +3,6 @@
 
 #include <ros/common.h>
 
-extern physaddr_t maxpa;               /* Maximum physical address in the system */
-extern physaddr_t maxaddrpa;   /* Maximum addressable physical address */
-extern size_t npages;                  /* Total number of physical memory pages */
-extern size_t naddrpages;              /* num of addressable physical memory pages */
-
 /* multiboot.h - the header for Multiboot 0.6.96 (diff from MB2) */
 /* Copyright (C) 1999,2003,2007,2008,2009  Free Software Foundation, Inc.
  *
@@ -229,6 +224,13 @@ typedef struct multiboot_mod_list multiboot_module_t;
 
 #endif /* ! ASM_FILE */
 
-void mboot_detect_memory(multiboot_info_t *mbi);
-void mboot_print_mmap(multiboot_info_t *mbi);
+typedef void (*mboot_foreach_t)(struct multiboot_mmap_entry*, void*);
+
+void mboot_detect_memory(struct multiboot_info *mbi);
+void mboot_print_mmap(struct multiboot_info *mbi);
+void mboot_foreach_mmap(struct multiboot_info *mbi, mboot_foreach_t func,
+                        void *data);
+bool mboot_region_collides(struct multiboot_info *mbi, uintptr_t base,
+                           uintptr_t end);
+
 #endif /* !ROS_INC_MULTIBOOT_H */
index 1cb213e..5679d58 100644 (file)
@@ -16,6 +16,7 @@
 #include <process.h>
 #include <kref.h>
 #include <kthread.h>
+#include <multiboot.h>
 
 struct page_map;               /* preprocessor games */
 
@@ -54,7 +55,7 @@ extern page_list_t LCKD(&colored_page_free_list_lock) * RO CT(llc_num_colors)
     colored_page_free_list;
 
 /*************** Functional Interface *******************/
-void page_alloc_init(void);
+void page_alloc_init(struct multiboot_info *mbi);
 void colored_page_alloc_init(void);
 
 error_t upage_alloc(struct proc* p, page_t *SAFE *page, int zero);
index 48d5f02..68d7723 100644 (file)
@@ -4,7 +4,6 @@
  * Actual implementation:
  * Copyright (c) 2009 The Regents of the University of California
  * Barret Rhoden <brho@cs.berkeley.edu>
- * Kevin Klues <klueska@cs.berkeley.edu> (multiboot functions)
  * See LICENSE for details.
  *
  * Physical memory mangement, low-level virtual address space initialization and
 ({                                                             \
        physaddr_t __m_pa = (pa);                               \
        size_t __m_ppn = LA2PPN(__m_pa);                        \
-       if (__m_ppn >= npages)                                  \
+       if (__m_ppn > max_nr_pages)                                     \
                warn("KADDR called with invalid pa %p", __m_pa);\
        (void*TRUSTED) (__m_pa + KERNBASE);                             \
 })
 
+#define KBASEADDR(kla) KADDR(PADDR(kla))
+
 extern char (SNT RO bootstacktop)[], (SNT RO bootstack)[];
 
-// List of physical pages
-extern page_t * RO CT(npages) pages;
+extern physaddr_t max_pmem;            /* Total amount of physical memory */
+extern size_t max_nr_pages;            /* Total number of physical memory pages */
+extern physaddr_t max_paddr;   /* Maximum addressable physical address */
+extern size_t nr_free_pages;
+extern struct multiboot_info *multiboot_kaddr;
+extern uintptr_t boot_freemem;
+extern uintptr_t boot_freelimit;
+
+/* Pages are stored in an array, including for pages that we can never touch
+ * (like reserved memory from the BIOS, fake regions, etc).  Pages are reference
+ * counted, and free pages are kept on a linked list. */
+extern struct page *pages;
 
 extern physaddr_t RO boot_cr3;
 extern pde_t *CT(NPDENTRIES) RO boot_pgdir;
 
-extern char *RO BND(end, maxaddrpa_ptr + IVY_KERNBASE) boot_freemem;
+bool enable_pse(void);
+void vm_init(void);
 
-bool   enable_pse(void);
-void   vm_init(void);
+void pmem_init(struct multiboot_info *mbi);
+void *boot_alloc(size_t amt, size_t align);
+void *boot_zalloc(size_t amt, size_t align);
 
-void   page_init(void);
-void   page_check(void);
-int        page_insert(pde_t *pgdir, struct page *page, void *SNT va, int perm);
-void   page_remove(pde_t *COUNT(NPDENTRIES) pgdir, void *SNT va);
+void page_check(void);
+int     page_insert(pde_t *pgdir, struct page *page, void *SNT va, int perm);
+void page_remove(pde_t *COUNT(NPDENTRIES) pgdir, void *SNT va);
 page_t*COUNT(1) page_lookup(pde_t SSOMELOCK*COUNT(NPDENTRIES) pgdir, void *SNT va, pte_t **pte_store);
 error_t        pagetable_remove(pde_t *COUNT(NPDENTRIES) pgdir, void *SNT va);
 void   page_decref(page_t *COUNT(1) pp);
@@ -75,6 +87,8 @@ void  page_decref(page_t *COUNT(1) pp);
 void setup_default_mtrrs(barrier_t* smp_barrier);
 void   tlb_invalidate(pde_t *COUNT(NPDENTRIES) pgdir, void *SNT va);
 void tlb_flush_global(void);
+bool regions_collide_unsafe(uintptr_t start1, uintptr_t end1, 
+                            uintptr_t start2, uintptr_t end2);
 
 /* Arch specific implementations for these */
 pte_t *pgdir_walk(pde_t *COUNT(NPDENTRIES) pgdir, const void *SNT va, int create);
@@ -82,8 +96,8 @@ int get_va_perms(pde_t *COUNT(NPDENTRIES) pgdir, const void *SNT va);
 
 static inline page_t *SAFE ppn2page(size_t ppn)
 {
-       if( ppn >= npages )
-               warn("ppn2page called with ppn (%08lu) larger than npages", ppn);
+       if (ppn >= max_nr_pages)
+               warn("ppn2page called with ppn (%08lu) larger than max_nr_pages", ppn);
        return &(pages[ppn]);
 }
 
@@ -99,8 +113,8 @@ static inline physaddr_t page2pa(page_t *pp)
 
 static inline page_t*COUNT(1) pa2page(physaddr_t pa)
 {
-       if (LA2PPN(pa) >= npages)
-               warn("pa2page called with pa (%p) larger than npages", pa);
+       if (LA2PPN(pa) >= max_nr_pages)
+               warn("pa2page called with pa (%p) larger than max_nr_pages", pa);
        return &pages[LA2PPN(pa)];
 }
 
index 8a376b1..1b24a96 100644 (file)
  * which vpd is set in entry.S.
  */
 
-#ifdef __IVY__
-#pragma cilnoremove("vpt_lock", "vpd_lock")
-#endif
-extern volatile uint32_t vpt_lock;
-extern volatile uint32_t vpd_lock;
-
 extern volatile pte_t *vpt; // VA of "virtual page table"
 extern volatile pde_t *vpd; // VA of current page directory
 
index 86da899..10f920c 100644 (file)
@@ -55,19 +55,23 @@ void kernel_init(multiboot_info_t *mboot_info)
        extern char (RO BND(__this, end) edata)[], (RO SNT end)[];
 
        memset(edata, 0, end - edata);
-       cons_init();
-       print_cpuinfo();
-
        /* mboot_info is a physical address.  while some arches currently have the
         * lower memory mapped, everyone should have it mapped at kernbase by now.
         * also, it might be in 'free' memory, so once we start dynamically using
         * memory, we may clobber it. */
-       mboot_detect_memory((multiboot_info_t*)((physaddr_t)mboot_info + KERNBASE));
-       mboot_print_mmap((multiboot_info_t*)((physaddr_t)mboot_info + KERNBASE));
+       multiboot_kaddr = (struct multiboot_info*)((physaddr_t)mboot_info
+                                               + KERNBASE);
+       cons_init();
+       print_cpuinfo();
 
-       vm_init();                      // Sets up pages tables, turns on paging
        cache_init();                                   // Determine systems's cache properties
-       page_init();                                    // Initializes free page list, etc
+       pmem_init(multiboot_kaddr);
+
+#ifdef CONFIG_X86_64
+printk("Halting/spinning...\n");
+while (1)
+       asm volatile("hlt");
+#endif
        kmem_cache_init();              // Sets up slab allocator
        kmalloc_init();
        hashtable_init();
@@ -111,9 +115,15 @@ void kernel_init(multiboot_info_t *mboot_info)
 void _panic(const char *file, int line, const char *fmt,...)
 {
        va_list ap;
-       struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
-
+       struct per_cpu_info *pcpui;
+       /* Debug panic, before core_id is available. */
+       if (booting) {
+               printk("Kernel panic at %s:%d\n", file, line);
+               while (1)
+                       cpu_relax();
+       }
        /* We're panicing, possibly in a place that can't handle the lock checker */
+       pcpui = &per_cpu_info[core_id()];
        pcpui->__lock_depth_disabled++;
        va_start(ap, fmt);
        cprintf("kernel panic at %s:%d, from core %d: ", file, line, core_id());
@@ -136,7 +146,7 @@ void _warn(const char *file, int line, const char *fmt,...)
        va_list ap;
 
        va_start(ap, fmt);
-       cprintf("kernel warning at %s:%d, from core %d: ", file, line, core_id());
+       cprintf("kernel warning at %s:%d: ", file, line);
        vcprintf(fmt, ap);
        cprintf("\n");
        va_end(ap);
index 2c60671..f4b6f70 100644 (file)
@@ -2,6 +2,7 @@
  * See the COPYRIGHT files at the top of this source tree for full 
  * license information.
  * 
+ * Barret Rhoden <brho@cs.berkeley.edu>
  * Kevin Klues <klueska@cs.berkeley.edu>    
  */
 
 
 #define kmallocdebug(args...)  //printk(args)
 
-char *RO BND(end, maxaddrpa_ptr + IVY_KERNBASE) boot_freemem;
-
 //List of physical pages used by kmalloc
 static spinlock_t pages_list_lock = SPINLOCK_INITIALIZER;
 static page_list_t LCKD(&pages_list_lock)pages_list;
 
-/*
- * Allocate n bytes of physical memory aligned on an 
- * align-byte boundary.  Align must be a power of two.
- * Return kernel virtual address.  Returned memory is uninitialized.
- *
- * If we're out of memory, boot_alloc should panic.
- * This function may ONLY be used during initialization,
- * before the page_free_list has been set up.
- */
-void* boot_alloc(uint32_t n, uint32_t align)
-{
-       extern char (SNT RO end)[];
-       void *v;
-
-       // Initialize boot_freemem if this is the first time.
-       // 'end' is a magic symbol automatically generated by the linker,
-       // which points to the end of the kernel's bss segment -
-       // i.e., the first virtual address that the linker
-       // did _not_ assign to any kernel code or global variables.
-       if (boot_freemem == 0) {
-               boot_freemem = SINIT(TC(end));
-       }
-
-       //      Step 1: round boot_freemem up to be aligned properly
-       char RO*tmp = PTRROUNDUP(boot_freemem, align);
-       boot_freemem = SINIT(tmp);
-
-       //      Step 2: save current value of boot_freemem as allocated chunk
-       v = boot_freemem;
-       //  Step 2.5: check if we can alloc
-       if (PADDR(boot_freemem + n) > maxaddrpa)
-               panic("Out of memory in boot alloc, you fool!\n");
-       //      Step 3: increase boot_freemem to record allocation
-       boot_freemem = SINIT(boot_freemem + n);
-       //      Step 4: return allocated chunk
-       return v;
-}
-
-void *boot_calloc(uint32_t n, size_t sz, uint32_t align)
-{
-       void *v = boot_alloc(n * sz, align);    
-       memset(v, 0, n * sz);
-       return v;
-}
-
 struct kmem_cache *kmalloc_caches[NUM_KMALLOC_CACHES];
 void kmalloc_init(void)
 {
index 2508cd0..2ebf8f2 100644 (file)
@@ -3,7 +3,7 @@
  * Kevin Klues <klueska@cs.berkeley.edu>
  * See LICENSE for details. 
  *
- * Multiboot parsing. */
+ * Multiboot parsing and helper functions. */
 
 #include <multiboot.h>
 #include <ros/common.h>
 #include <arch/arch.h>
 #include <ros/memlayout.h>
 #include <stdio.h>
+#include <pmap.h>
 
 #ifdef CONFIG_X86
 #include <arch/apic.h>
 #endif
 
-physaddr_t maxpa;              /* Maximum physical address in the system */
-physaddr_t maxaddrpa;  /* Maximum addressable physical address */
-size_t npages;                 /* Total number of physical memory pages */
-size_t naddrpages;             /* num of addressable physical memory pages */
-
-static size_t basemem;  /* Amount of base memory (in bytes) */
-static size_t extmem;   /* Amount of extended memory (in bytes) */
-
 /* This only notices bios detectable memory - there's a lot more in the higher
  * paddrs. */
-void mboot_detect_memory(multiboot_info_t *mbi)
+void mboot_detect_memory(struct multiboot_info *mbi)
 {
+       physaddr_t max_bios_mem;
+       physaddr_t max_bios_addr;
+       size_t basemem;
+       size_t extmem;
        if (!(mbi->flags & MULTIBOOT_INFO_MEMORY)) {
                printk("No BIOS memory info from multiboot, crash impending!\n");
                return;
        }
        /* mem_lower and upper are measured in KB.  They are 32 bit values, so we're
         * limited to 4TB total. */
-       size_t basemem = ROUNDDOWN((size_t)mbi->mem_lower * 1024, PGSIZE);
-       size_t extmem = ROUNDDOWN((size_t)mbi->mem_upper * 1024, PGSIZE);
+       basemem = ROUNDDOWN((size_t)mbi->mem_lower * 1024, PGSIZE);
+       extmem = ROUNDDOWN((size_t)mbi->mem_upper * 1024, PGSIZE);
        /* Calculate the maximum physical address based on whether or not there is
         * any extended memory. */
        if (extmem)
-               maxpa = EXTPHYSMEM + extmem;
+               max_bios_mem = EXTPHYSMEM + extmem;
        else
-               maxpa = basemem;
-       npages = maxpa / PGSIZE;
-       /* KERN_VMAP_TOP - KERNBASE is the max amount of virtual addresses we can
-        * use for the physical memory mapping (aka - the KERNBASE mapping) */
-       maxaddrpa = MIN(maxpa, KERN_VMAP_TOP - KERNBASE);
-       naddrpages = maxaddrpa / PGSIZE;
-       printk("Physical memory: %luK available, ", maxpa / 1024);
-       printk("base = %luK, extended = %luK\n", basemem / 1024, extmem / 1024);
-       printk("Maximum directly addressable physical memory: %luK\n",
-              maxaddrpa / 1024);
+               max_bios_mem = basemem;
+       max_bios_addr = MIN(max_bios_mem, KERN_VMAP_TOP - KERNBASE);
+       printk("Base memory: %luK, Extended memory: %luK\n", basemem / 1024,
+              extmem / 1024);
+       printk("Maximum directly addressable base and extended memory: %luK\n",
+              max_bios_addr / 1024);
+       /* Take a first stab at the max pmem, in case there are no memory mappings
+        * (like in riscv) */
+       max_pmem = max_bios_mem;
 }
 
-/* TODO: Use the info from this for our free pages, instead of just using
- * the extended memory */
-void mboot_print_mmap(multiboot_info_t *mbi)
+void mboot_foreach_mmap(struct multiboot_info *mbi, mboot_foreach_t func,
+                        void *data)
 {
-       multiboot_memory_map_t *mmap_b, *mmap_e, *mmap_i;
+       struct multiboot_mmap_entry *mmap_b, *mmap_e, *mmap_i;
        if (!(mbi->flags & MULTIBOOT_INFO_ELF_SHDR)) {
                printk("No memory mapping info from multiboot\n");
                return;
        }
-       mmap_b = (multiboot_memory_map_t*)((size_t)mbi->mmap_addr + KERNBASE);
-       mmap_e = (multiboot_memory_map_t*)((size_t)mbi->mmap_addr + KERNBASE
+       mmap_b = (struct multiboot_mmap_entry*)((size_t)mbi->mmap_addr + KERNBASE);
+       mmap_e = (struct multiboot_mmap_entry*)((size_t)mbi->mmap_addr + KERNBASE
                                           + mbi->mmap_length);
        printd("mmap_addr = %p, mmap_length = %p\n", mbi->mmap_addr,
               mbi->mmap_length);
-       printd("mmap_b %p, mmap_e %p\n", mmap_b, mmap_e);
        /* Note when we incremement mmap_i, we add in the value of size... */
        for (mmap_i = mmap_b;
             mmap_i < mmap_e;
-            mmap_i = (multiboot_memory_map_t*)((void*)mmap_i + mmap_i->size
-                                               + sizeof(mmap_i->size))) {
-               printk("base = 0x%016llx, length = 0x%016llx : %s\n",
-                      mmap_i->addr, mmap_i->len,
-                      mmap_i->type == MULTIBOOT_MEMORY_AVAILABLE ? "FREE" :
-                                                                   "RESERVED");
+            mmap_i = (struct multiboot_mmap_entry*)((void*)mmap_i + mmap_i->size
+                                                    + sizeof(mmap_i->size))) {
+               func(mmap_i, data);
        }
 }
 
+void mboot_print_mmap(struct multiboot_info *mbi)
+{
+       void print_entry(struct multiboot_mmap_entry *entry, void *data)
+       {
+               printk("Base = 0x%016llx, Length = 0x%016llx : %s\n",
+                      entry->addr, entry->len,
+                      entry->type == MULTIBOOT_MEMORY_AVAILABLE ? "FREE" :
+                                                                  "RESERVED");
+       }
+       mboot_foreach_mmap(mbi, print_entry, 0);
+}
+
+/* Given a range of memory, will tell us if multiboot is using anything we care
+ * about in that range.  It usually uses memory below 1MB, so boot_alloc is
+ * fine.  This is pre, so MBI is still a paddr. */
+bool mboot_region_collides(struct multiboot_info *mbi, uintptr_t base,
+                           uintptr_t end)
+{
+       if (regions_collide_unsafe((uintptr_t)mbi,
+                                  (uintptr_t)mbi + sizeof(struct multiboot_info),
+                                  base, end))
+               return TRUE;
+       if ((mbi->flags & MULTIBOOT_INFO_ELF_SHDR)) {
+               if (regions_collide_unsafe((uintptr_t)mbi->mmap_addr + KERNBASE,
+                                          (uintptr_t)mbi->mmap_addr + KERNBASE
+                                                                    + mbi->mmap_length,
+                                          base, end))
+                       return TRUE;
+       }
+       return FALSE;
+}
index 5185f7e..bf4b082 100644 (file)
@@ -166,6 +166,7 @@ void *get_cont_pages(size_t order, int flags)
 {
        size_t npages = 1 << order;     
 
+       size_t naddrpages = max_paddr / PGSIZE;
        // Find 'npages' free consecutive pages
        int first = -1;
        spin_lock_irqsave(&colored_page_free_list_lock);
index 3f7c6f0..a3adbad 100644 (file)
@@ -1,23 +1,10 @@
-/* See COPYRIGHT for copyright information. */
-
-/** @file 
- * This file is responsible for managing physical pages as they 
- * are mapped into the page tables of a particular virtual address
- * space.  The functions defined in this file operate on these
- * page tables to insert and remove physical pages from them at 
- * particular virtual addresses.
+/* Copyright (c) 2009,13 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details. 
  *
- * @author Kevin Klues <klueska@cs.berkeley.edu>
- * @author Barret Rhoden <brho@cs.berkeley.edu>
- */
-
-#ifdef __SHARC__
-#pragma nosharc
-#endif
-
-#ifdef __DEPUTY__
-#pragma nodeputy
-#endif
+ * Arch independent physical memory and page table management.
+ *
+ * For page allocation, check out the family of page_alloc files. */
 
 #include <arch/arch.h>
 #include <arch/mmu.h>
 #include <process.h>
 #include <stdio.h>
 #include <mm.h>
+#include <multiboot.h>
 
-volatile uint32_t vpt_lock = 0;
-volatile uint32_t vpd_lock = 0;
+physaddr_t max_pmem = 0;       /* Total amount of physical memory (bytes) */
+physaddr_t max_paddr = 0;      /* Maximum addressable physical address */
+size_t max_nr_pages = 0;       /* Number of addressable physical memory pages */
+size_t nr_free_pages = 0;      /* TODO: actually track this, after init */
+struct page *pages = 0;
+struct multiboot_info *multiboot_kaddr = 0;
+uintptr_t boot_freemem = 0;
+uintptr_t boot_freelimit = 0;
+
+static size_t sizeof_mboot_mmentry(struct multiboot_mmap_entry *entry)
+{
+       /* Careful - addr + len is a uint64 (need to cast down for 32 bit) */
+       return (size_t)(entry->addr + entry->len);
+}
+
+static void adjust_max_pmem(struct multiboot_mmap_entry *entry, void *data)
+{
+       if (entry->type != MULTIBOOT_MEMORY_AVAILABLE)
+               return;
+       max_pmem = MAX(max_pmem, sizeof_mboot_mmentry(entry));
+}
 
 /**
- * @brief Initialize the array of physical pages and memory free list.
+ * @brief Initializes physical memory.  Determines the pmem layout, sets up the
+ * array of physical pages and memory free list, and turns on virtual
+ * memory/page tables.
  *
- * The 'pages' array has one 'page_t' entry per physical page.
- * Pages are reference counted, and free pages are kept on a linked list.
- */
-void page_init(void)
+ * Regarding max_pmem vs max_paddr and max_nr_pages: max_pmem is the largest
+ * physical address that is in a FREE region.  It includes RESERVED regions that
+ * are below this point.  max_paddr is the largest physical address, <=
+ * max_pmem, that the KERNBASE mapping can map.  It too may include reserved
+ * ranges.  The 'pages' array will track all physical pages up to max_paddr.
+ * There are max_nr_pages of them.  On 64 bit systems, max_pmem == max_paddr. */
+void pmem_init(struct multiboot_info *mbi)
 {
-       /*
-     * First, make 'pages' point to an array of size 'npages' of
-        * type 'page_t'.
-        * The kernel uses this structure to keep track of physical pages;
-        * 'npages' equals the number of physical pages in memory.
-        * round up to the nearest page
-        */
-       pages = (page_t*)boot_alloc(npages*sizeof(page_t), PGSIZE);
-       memset(pages, 0, npages*sizeof(page_t));
-
-       /*
-     * Then initilaize everything so pages can start to be alloced and freed
-        * from the memory free list
-        */
-       page_alloc_init();
+       mboot_detect_memory(mbi);
+       mboot_print_mmap(mbi);
+       /* adjust the max memory based on the mmaps, since the old detection doesn't
+        * help much on 64 bit systems */
+       mboot_foreach_mmap(mbi, adjust_max_pmem, 0);
+       /* KERN_VMAP_TOP - KERNBASE is the max amount of virtual addresses we can
+        * use for the physical memory mapping (aka - the KERNBASE mapping).
+        * Should't be an issue on 64b, but is usually for 32 bit. */
+       max_paddr = MIN(max_pmem, KERN_VMAP_TOP - KERNBASE);
+       /* Note not all of this memory is free. */
+       max_nr_pages = max_paddr / PGSIZE;
+       printk("Max physical RAM (appx, bytes): %lu\n", max_pmem);
+       printk("Max addressable physical RAM (appx): %lu\n", max_paddr);
+       printk("Highest page number (including reserved): %lu\n", max_nr_pages);
+       pages = (struct page*)boot_zalloc(max_nr_pages * sizeof(struct page),
+                                         PGSIZE);
+       /* Turn on paging before turning on the page allocator, we still use
+        * boot_alloc in vm_init.  Doesn't really matter much either way. */
+       vm_init();
+       page_alloc_init(mbi);
 
        static_assert(PROCINFO_NUM_PAGES*PGSIZE <= PTSIZE);
        static_assert(PROCDATA_NUM_PAGES*PGSIZE <= PTSIZE);
 }
 
+static void set_largest_freezone(struct multiboot_mmap_entry *entry, void *data)
+{
+       struct multiboot_mmap_entry **boot_zone =
+              (struct multiboot_mmap_entry**)data;
+
+       if (entry->type != MULTIBOOT_MEMORY_AVAILABLE)
+               return;
+       if (!*boot_zone || (sizeof_mboot_mmentry(entry) >
+                          sizeof_mboot_mmentry(*boot_zone)))
+               *boot_zone = entry;
+}
+
+/* Initialize boot freemem and its limit.
+ *
+ * "end" is a symbol marking the end of the kernel.  This covers anything linked
+ * in with the kernel (KFS, etc).  However, 'end' is a kernel load address,
+ * which differs from kernbase addrs in 64 bit.  We need to use the kernbase
+ * mapping for anything dynamic (because it could go beyond 1 GB). 
+ *
+ * Ideally, we'll use the largest mmap zone, as reported by multiboot.  If we
+ * don't have one (riscv), we'll just use the memory after the kernel.
+ *
+ * If we do have a zone, there is a chance we've already used some of it (for
+ * the kernel, etc).  We'll use the lowest address in the zone that is
+ * greater than "end" (and adjust the limit accordingly).  */
+static void boot_alloc_init(void)
+{
+       extern char end[];
+       uintptr_t boot_zone_start, boot_zone_end;
+       uintptr_t end_kva = (uintptr_t)KBASEADDR(end);
+       struct multiboot_mmap_entry *boot_zone = 0;
+
+       /* Find our largest mmap_entry; that will set bootzone */
+       mboot_foreach_mmap(multiboot_kaddr, set_largest_freezone, &boot_zone);
+       if (boot_zone) {
+               boot_zone_start = (uintptr_t)KADDR(boot_zone->addr);
+               /* one issue for 32b is that the boot_zone_end could be beyond max_paddr
+                * and even wrap-around.  Do the min check as a uint64_t.  The result
+                * should be a safe, unwrapped 32/64b when cast to physaddr_t. */
+               boot_zone_end = (uintptr_t)KADDR(MIN(boot_zone->addr + boot_zone->len,
+                                                (uint64_t)max_paddr));
+               /* using KERNBASE (kva, btw) which covers the kernel and anything before
+                * it (like the stuff below EXTPHYSMEM on x86) */
+               if (regions_collide_unsafe(KERNBASE, end_kva,
+                                          boot_zone_start, boot_zone_end))
+                       boot_freemem = end_kva;
+               else
+                       boot_freemem = boot_zone_start;
+               boot_freelimit = boot_zone_end;
+       } else {
+               boot_freemem = end_kva;
+               boot_freelimit = max_paddr;
+       }
+       printd("boot_zone: %p, paddr base: 0x%llx, paddr len: 0x%llx\n", boot_zone,
+              boot_zone ? boot_zone->addr : 0,
+              boot_zone ? boot_zone->len : 0);
+       printd("boot_freemem: %p, boot_freelimit %p\n", boot_freemem,
+              boot_freelimit);
+}
+
+/* Low-level allocator, used before page_alloc is on.  Returns size bytes,
+ * aligned to align (should be a power of 2).  Retval is a kernbase addr.  Will
+ * panic on failure. */
+void *boot_alloc(size_t amt, size_t align)
+{
+       uintptr_t retval;
+
+       if (!boot_freemem)
+               boot_alloc_init();
+       boot_freemem = ROUNDUP(boot_freemem, align);
+       retval = boot_freemem;
+       if (boot_freemem + amt > boot_freelimit)
+               panic("Out of memory in boot alloc, you fool!\n");
+       boot_freemem += amt;
+       printd("boot alloc from %p to %p\n", retval, boot_freemem);
+       /* multiboot info probably won't ever conflict with our boot alloc */
+       if (mboot_region_collides(multiboot_kaddr, retval, boot_freemem))
+               panic("boot allocation could clobber multiboot info!  Get help!");
+       return (void*)retval;
+}
+
+void *boot_zalloc(size_t amt, size_t align)
+{
+       /* boot_alloc panics on failure */
+       void *v = boot_alloc(amt, align);
+       memset(v, 0, amt);
+       return v;
+}
+
 /** 
  * @brief Map the physical page 'pp' into the virtual address 'va' in page
  *        directory 'pgdir'
@@ -206,3 +312,20 @@ void tlb_invalidate(pde_t *pgdir, void *va)
        // For now, there is only one address space, so always invalidate.
        invlpg(va);
 }
+
+/* Helper, returns true if any part of (start1, end1) is within (start2, end2).
+ * Equality of endpoints (like end1 == start2) is okay.
+ * Assumes no wrap-around. */
+bool regions_collide_unsafe(uintptr_t start1, uintptr_t end1, 
+                            uintptr_t start2, uintptr_t end2)
+{
+       if (start1 <= start2) {
+               if (end1 <= start2)
+                       return FALSE;
+               return TRUE;
+       } else {
+               if (end2 <= start1)
+                       return FALSE;
+               return TRUE;
+       }
+}