Added beginnings of a proper kmalloc implementation.
authorKevin Klues <klueska@eecs.berkeley.edu>
Wed, 17 Jun 2009 20:44:32 +0000 (13:44 -0700)
committerKevin Klues <klueska@eecs.berkeley.edu>
Wed, 17 Jun 2009 20:55:32 +0000 (13:55 -0700)
Right now the algorithm is vdery simple and there is lots of wasted space.  The goal is to start writing kernel code that can properly use the kmalloc interface and innovate on its implementation as we move forward.

include/kmalloc.h [new file with mode: 0644]
include/pmap.h
kern/src/Makefrag
kern/src/env.c
kern/src/kmalloc.c [new file with mode: 0644]
kern/src/pmap.c

diff --git a/include/kmalloc.h b/include/kmalloc.h
new file mode 100644 (file)
index 0000000..902f3e9
--- /dev/null
@@ -0,0 +1,17 @@
+/* Copyright (c) 2009 The Regents of the University of California. 
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ * 
+ * Kevin Klues <klueska@cs.berkeley.edu>    
+ */
+
+#ifndef KMALLOC_H
+#define KMALLOC_H
+
+#include <arch/types.h>
+
+void  kmalloc_init();
+void* kmalloc(size_t size, int flags);
+void  kfree(void*COUNT(PGSIZE) addr);
+
+#endif //KMALLOC_H
\ No newline at end of file
index d9bf9c4..512794f 100644 (file)
@@ -31,7 +31,7 @@
 #define KADDR(pa)                                              \
 ({                                                             \
        physaddr_t __m_pa = (pa);                               \
-       uint32_t __m_ppn = PPN(__m_pa);                         \
+       size_t __m_ppn = PPN(__m_pa);                           \
        if (__m_ppn >= npage)                                   \
                warn("KADDR called with invalid pa %08lx", __m_pa);\
        (void*TRUSTED) (__m_pa + KERNBASE);                             \
@@ -55,6 +55,7 @@ typedef LIST_ENTRY(Page) page_list_entry_t;
 
 struct Page {
        page_list_entry_t pp_link;      /* free list link */
+       size_t num_cons_links;
 
        // pp_ref is the count of pointers (usually in page table entries)
        // to this page, for pages allocated using page_alloc.
@@ -83,11 +84,13 @@ void        i386_vm_init(void);
 
 void   page_init(void);
 void   page_check(void);
-int    page_alloc(page_t **pp_store);
+int        page_alloc(page_t **pp_store);
+int     page_alloc_specific(page_t **pp_store, size_t ppn);
 void   page_free(page_t *pp);
-int    page_insert(pde_t *COUNT(NPDENTRIES) pgdir, page_t *pp, void *SNT va, int perm);
+int            page_is_free(size_t ppn);
+int        page_insert(pde_t *COUNT(NPDENTRIES) pgdir, page_t *pp, void *SNT va, int perm);
 void   page_remove(pde_t *COUNT(NPDENTRIES) pgdir, void *SNT va);
-page_t *page_lookup(pde_t *COUNT(NPDENTRIES) pgdir, void *va, pte_t **pte_store);
+page_tpage_lookup(pde_t *COUNT(NPDENTRIES) pgdir, void *va, pte_t **pte_store);
 error_t        pagetable_remove(pde_t *COUNT(NPDENTRIES) pgdir, void *va);
 void   page_decref(page_t *pp);
 
@@ -111,6 +114,13 @@ static inline void cacheline_flush(void* addr)
        clflush((uintptr_t*)addr);
 }
 
+static inline page_t* ppn2page(size_t ppn)
+{
+       if( ppn >= npage )
+               warn("ppn2page called with ppn (%08u) larger than npage", ppn);
+       return &(pages[ppn]);
+}
+
 static inline ppn_t page2ppn(page_t *pp)
 {
        return pp - pages;
@@ -133,6 +143,16 @@ static inline void*COUNT(PGSIZE) page2kva(page_t *pp)
        return KADDR(page2pa(pp));
 }
 
+static inline void*COUNT(PGSIZE) ppn2kva(size_t pp)
+{
+       return page2kva(ppn2page(pp));
+}
+
+static inline page_t* kva2page(void* addr) 
+{
+       return pa2page(PADDR(addr));
+}
+
 pte_t *pgdir_walk(pde_t *COUNT(NPDENTRIES) pgdir, const void *SNT va, int create);
 
 #endif /* !ROS_KERN_PMAP_H */
index 1189365..82c9101 100644 (file)
@@ -35,7 +35,8 @@ KERN_SRCFILES := $(KERN_SRC_DIR)/entry.S \
                  $(KERN_SRC_DIR)/printfmt.c \
                  $(KERN_SRC_DIR)/readline.c \
                  $(KERN_SRC_DIR)/string.c \
-                 $(KERN_SRC_DIR)/timer.c
+                 $(KERN_SRC_DIR)/timer.c \
+                 $(KERN_SRC_DIR)/kmalloc.c
 # Only build files if they exist.
 KERN_SRCFILES := $(wildcard $(KERN_SRCFILES))
 
@@ -85,7 +86,7 @@ $(OBJDIR)/$(KERN_DIR)/kernel: $(KERN_LDDEPENDS)
 
 $(OBJDIR)/$(KERN_DIR)/bochs.img: $(OBJDIR)/$(KERN_DIR)/kernel $(OBJDIR)/$(KERN_DIR)/boot
        @echo + mk [KERN] $@
-       $(V)dd if=/dev/zero of=$(OBJDIR)/$(KERN_DIR)/bochs.img~ count=10000 2>/dev/null
+       $(V)dd if=/dev/zero of=$(OBJDIR)/$(KERN_DIR)/bochs.img~ count=10080 2>/dev/null
        $(V)dd if=$(OBJDIR)/$(KERN_DIR)/boot of=$(OBJDIR)/$(KERN_DIR)/bochs.img~ conv=notrunc 2>/dev/null
        $(V)dd if=$(OBJDIR)/$(KERN_DIR)/kernel of=$(OBJDIR)/$(KERN_DIR)/bochs.img~ seek=1 conv=notrunc 2>/dev/null
        $(V)mv $(OBJDIR)/kern/bochs.img~ $(OBJDIR)/kern/bochs.img
index 6c0838c..8e0805a 100644 (file)
@@ -394,8 +394,9 @@ load_icode(env_t *e, uint8_t *COUNT(size) binary, size_t size)
        lcr3(e->env_cr3);
 
        // TODO: how do we do a runtime COUNT?
-       proghdr_t *phdr = (proghdr_t *)(binary + elfhdr->e_phoff);
-       for (i = 0; i < elfhdr->e_phnum; i++, phdr++) { TRUSTEDBLOCK
+       {TRUSTEDBLOCK
+       proghdr_t* phdr = (proghdr_t*)(binary + elfhdr->e_phoff);
+       for (i = 0; i < elfhdr->e_phnum; i++, phdr++) {
         // zra: TRUSTEDBLOCK until validation is done.
                if (phdr->p_type != ELF_PROG_LOAD)
                        continue;
@@ -405,7 +406,7 @@ load_icode(env_t *e, uint8_t *COUNT(size) binary, size_t size)
                segment_alloc(e, (void*SNT)phdr->p_va, phdr->p_memsz);
                memcpy((void*)phdr->p_va, binary + phdr->p_offset, phdr->p_filesz);
                memset((void*)phdr->p_va + phdr->p_filesz, 0, phdr->p_memsz - phdr->p_filesz);
-       }
+       }}
 
        e->env_tf.tf_eip = elfhdr->e_entry;
 
diff --git a/kern/src/kmalloc.c b/kern/src/kmalloc.c
new file mode 100644 (file)
index 0000000..f832c31
--- /dev/null
@@ -0,0 +1,67 @@
+/* Copyright (c) 2009 The Regents of the University of California. 
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ * 
+ * Kevin Klues <klueska@cs.berkeley.edu>    
+ */
+
+#include <arch/types.h>
+#include <ros/error.h>
+#include <pmap.h>
+#include <kmalloc.h>
+
+#define kmallocdebug(args...)  printk(args)
+
+static page_list_t pages_list; //List of physical pages used by kmalloc
+extern size_t naddrpage;
+
+void kmalloc_init() {
+       LIST_INIT(&pages_list);
+}
+
+void* kmalloc(size_t size, int flags) {
+       int npages = ROUNDUP(size, PGSIZE) / PGSIZE;
+       
+       // Find 'npages' free consecutive pages
+       int first = -1;
+       kmallocdebug("naddrpage: %u\n", naddrpage);
+       kmallocdebug("npages: %u\n", npages);
+       for(int i=(naddrpage-1); i>=(npages-1); i--) {
+               int j;
+               for(j=i; j>=i-(npages-1); j--) {
+                       if( !page_is_free(j) )
+                               break;
+               }
+               if( j == i-(npages-1)-1 ) {
+                       first = j+1;
+                       break;
+               }
+       }
+       //If we couldn't find them, return NULL
+       if( first == -1 )
+               return NULL;
+       
+       //Otherwise go ahead and allocate them to ourselves now
+       for(int i=0; i<npages; i++) {
+               page_t* page;
+               page_alloc_specific(&page, first+i);
+               page->num_cons_links = npages-i;
+               LIST_INSERT_HEAD(&pages_list, page, pp_link);
+               kmallocdebug("mallocing page: %u\n", first+i);
+               kmallocdebug("at addr: %p\n", ppn2kva(first+i));
+       }
+       //And return the address of the first one
+       return ppn2kva(first);
+}
+void kfree(void *addr) {
+       kmallocdebug("incoming address: %p\n", addr);
+       page_t* page = kva2page(addr);
+       int num_links = page->num_cons_links;
+       kmallocdebug("getting page: %u\n", page2ppn(page));
+       for(int i=0; i<num_links; i++) {
+               page_t* p = ppn2page((page2ppn(page) + i));
+               LIST_REMOVE(p, pp_link);
+               page_free(p);
+               kmallocdebug("freeing page: %d\n", page2ppn(p));
+       }
+}
\ No newline at end of file
index 3a0aefa..3d944e5 100644 (file)
@@ -745,22 +745,19 @@ page_initpp(page_t *pp)
        memset(pp, 0, sizeof(*pp));
 }
 
-//
-// Allocates a physical page.
-// Does NOT set the contents of the physical page to zero -
-// the caller must do that if necessary.
-//
-// *pp_store -- is set to point to the Page struct of the newly allocated
-// page
-//
-// RETURNS 
-//   0 -- on success
-//   -E_NO_MEM -- otherwise 
-//
-// Hint: use LIST_FIRST, LIST_REMOVE, and page_initpp
-// Hint: pp_ref should not be incremented 
-int
-page_alloc(page_t **pp_store)
+/*
+ * Allocates a physical page.
+ * Does NOT set the contents of the physical page to zero -
+ * the caller must do that if necessary.
+ *
+ * *pp_store   -- is set to point to the Page struct 
+ *                of the newly allocated page
+ *
+ * RETURNS 
+ *   0         -- on success
+ *   -E_NO_MEM -- otherwise 
+ */
+int page_alloc(page_t **pp_store)
 {
        if (LIST_EMPTY(&page_free_list))
                return -E_NO_MEM;
@@ -770,12 +767,41 @@ page_alloc(page_t **pp_store)
        return 0;
 }
 
+/*
+ * Allocates a specific physical page.
+ * Does NOT set the contents of the physical page to zero -
+ * the caller must do that if necessary.
+ *
+ * *pp_store   -- is set to point to the Page struct 
+ *                of the newly allocated page
+ *
+ * RETURNS 
+ *   0         -- on success
+ *   -E_NO_MEM -- otherwise 
+ */
+int page_alloc_specific(page_t **pp_store, size_t ppn)
+{
+       page_t* page = ppn2page(ppn);
+       if( page->pp_ref != 0 )
+               return -E_NO_MEM;
+       *pp_store = page;
+       LIST_REMOVE(*pp_store, pp_link);
+       page_initpp(*pp_store);
+       return 0;
+}
+
+int page_is_free(size_t ppn) {
+       page_t* page = ppn2page(ppn);
+       if( page->pp_ref == 0 )
+               return TRUE;
+       return FALSE;
+}
+
 //
 // Return a page to the free list.
 // (This function should only be called when pp->pp_ref reaches 0.)
 //
-void
-page_free(page_t *pp)
+void page_free(page_t *pp)
 {
        // this check allows us to call this on null ptrs, which helps when
        // allocating and checking for errors on several pages at once