lib/malloc.c

   1
   2 #include <inc/lib.h>
   3
   4 /*
   5  * Simple malloc/free.
   6  *
   7  * Uses the address space to do most of the hard work.
   8  * The address space from mbegin to mend is scanned
   9  * in order.  Pages are allocated, used to fill successive
  10  * malloc requests, and then left alone.  Free decrements
  11  * a ref count maintained in the page; the page is freed
  12  * when the ref count hits zero.
  13  *
  14  * If we need to allocate a large amount (more than a page)
  15  * we can't put a ref count at the end of each page,
  16  * so we mark the pte entry with the bit PTE_CONTINUED.
  17  */
  18 enum
  19 {
  20         MAXMALLOC = 1024*1024   /* max size of one allocated chunk */
  21 };
  22
  23 #define PTE_CONTINUED 0x400
  24
  25 static uint8_t *mbegin = (uint8_t*) 0x08000000;
  26 static uint8_t *mend   = (uint8_t*) 0x10000000;
  27 static uint8_t *mptr;
  28
  29 static int
  30 isfree(void *v, size_t n)
  31 {
  32         uintptr_t va, end_va = (uintptr_t) v + n;
  33
  34         for (va = (uintptr_t) v; va < end_va; va += PGSIZE)
  35                 if (va >= (uintptr_t) mend
  36                     || ((vpd[PDX(va)] & PTE_P) && (vpt[VPN(va)] & PTE_P)))
  37                         return 0;
  38         return 1;
  39 }
  40
  41 void*
  42 malloc(size_t n)
  43 {
  44         int i, cont;
  45         int nwrap;
  46         uint32_t *ref;
  47         void *v;
  48
  49         if (mptr == 0)
  50                 mptr = mbegin;
  51
  52         n = ROUNDUP(n, 4);
  53
  54         if (n >= MAXMALLOC)
  55                 return 0;
  56
  57         if ((uintptr_t) mptr % PGSIZE){
  58                 /*
  59                  * we're in the middle of a partially
  60                  * allocated page - can we add this chunk?
  61                  * the +4 below is for the ref count.
  62                  */
  63                 ref = (uint32_t*) (ROUNDUP(mptr, PGSIZE) - 4);
  64                 if ((uintptr_t) mptr / PGSIZE == (uintptr_t) (mptr + n - 1 + 4) / PGSIZE) {
  65                         (*ref)++;
  66                         v = mptr;
  67                         mptr += n;
  68                         return v;
  69                 }
  70                 /*
  71                  * stop working on this page and move on.
  72                  */
  73                 free(mptr);     /* drop reference to this page */
  74                 mptr = ROUNDDOWN(mptr + PGSIZE, PGSIZE);
  75         }
  76
  77         /*
  78          * now we need to find some address space for this chunk.
  79          * if it's less than a page we leave it open for allocation.
  80          * runs of more than a page can't have ref counts so we
  81          * flag the PTE entries instead.
  82          */
  83         nwrap = 0;
  84         while (1) {
  85                 if (isfree(mptr, n + 4))
  86                         break;
  87                 mptr += PGSIZE;
  88                 if (mptr == mend) {
  89                         mptr = mbegin;
  90                         if (++nwrap == 2)
  91                                 return 0;       /* out of address space */
  92                 }
  93         }
  94
  95         /*
  96          * allocate at mptr - the +4 makes sure we allocate a ref count.
  97          */
  98         for (i = 0; i < n + 4; i += PGSIZE){
  99                 cont = (i + PGSIZE < n + 4) ? PTE_CONTINUED : 0;
 100                 if (sys_page_alloc(0, mptr + i, PTE_P|PTE_U|PTE_W|cont) < 0){
 101                         for (; i >= 0; i -= PGSIZE)
 102                                 sys_page_unmap(0, mptr + i);
 103                         return 0;       /* out of physical memory */
 104                 }
 105         }
 106
 107         ref = (uint32_t*) (mptr + i - 4);
 108         *ref = 2;       /* reference for mptr, reference for returned block */
 109         v = mptr;
 110         mptr += n;
 111         return v;
 112 }
 113
 114 void
 115 free(void *v)
 116 {
 117         uint8_t *c;
 118         uint32_t *ref;
 119
 120         if (v == 0)
 121                 return;
 122         assert(mbegin <= (uint8_t*) v && (uint8_t*) v < mend);
 123
 124         c = ROUNDDOWN(v, PGSIZE);
 125
 126         while (vpt[VPN(c)] & PTE_CONTINUED) {
 127                 sys_page_unmap(0, c);
 128                 c += PGSIZE;
 129                 assert(mbegin <= c && c < mend);
 130         }
 131
 132         /*
 133          * c is just a piece of this page, so dec the ref count
 134          * and maybe free the page.
 135          */
 136         ref = (uint32_t*) (c + PGSIZE - 4);
 137         if (--(*ref) == 0)
 138                 sys_page_unmap(0, c);
 139 }
 140