mm/malloc.c

   1 /*
   2  * The malloc stuff taken from fstk project
   3  *
   4  * ------------ from fstk ---------------
   5  * The malloc lib for fstk.
   6  *
   7  * Copyright (C) 2009, 2010 Liu Aleaxander -- All rights reserved.
   8  * This file may be redistributed under the terms of the GNU Public License.
   9  */
  10
  11
  12 #include <stdio.h>
  13 #include <string.h>
  14 #include <stdint.h>
  15 #include <malloc.h>
  16
  17 /* First, assume we just need 1M memory */
  18 #define MEM_SIZE 0x100000
  19
  20 /*
  21  * Allocat memory from mem adrress 8M
  22  *
  23  * I will make this much more stable and robust when I'm going to
  24  * implement the whole memory managerment thing
  25  */
  26 #define memory   0x800000
  27
  28 //static char memory[MEM_SIZE];
  29
  30 /* Next free memory address */
  31 static struct mem_struct *next_start = (struct mem_struct *)memory;
  32 static uint32_t mem_end = (uint32_t)(memory + MEM_SIZE);
  33
  34
  35 static inline struct mem_struct *get_next(struct mem_struct *mm)
  36 {
  37         uint32_t next = (uint32_t)mm + mm->size;
  38
  39         if (next >= mem_end)
  40                 return NULL;
  41         else
  42                 return (struct mem_struct *)next;
  43 }
  44
  45 /*
  46  * Here are the _merge_ functions, that merges a adjacent memory region,
  47  * from front, or from back, or even merges both. It returns the headest
  48  * region mem_struct.
  49  *
  50  */
  51
  52 static struct mem_struct *  merge_front(struct mem_struct *mm,
  53                                         struct mem_struct *prev)
  54 {
  55         struct mem_struct *next = get_next(mm);
  56
  57         prev->size += mm->size;
  58         if (next)
  59                 next->prev = prev;
  60         return prev;
  61 }
  62
  63 static struct mem_struct *  merge_back(struct mem_struct *mm,
  64                                        struct mem_struct *next)
  65 {
  66         mm->free = 1;    /* Mark it free first */
  67         mm->size += next->size;
  68
  69         next = get_next(next);
  70         if (next)
  71                 next->prev = mm;
  72         return mm;
  73 }
  74
  75 static struct mem_struct *  merge_both(struct mem_struct *mm,
  76                                        struct mem_struct *prev,
  77                                        struct mem_struct *next)
  78 {
  79         prev->size += mm->size + next->size;
  80
  81         next = get_next(next);
  82         if (next)
  83                 next->prev = prev;
  84         return prev;
  85 }
  86
  87 static inline struct mem_struct *  try_merge_front(struct mem_struct *mm)
  88 {
  89         mm->free = 1;
  90         if (mm->prev->free)
  91                 mm = merge_front(mm, mm->prev);
  92         return mm;
  93 }
  94
  95 static inline struct mem_struct *  try_merge_back(struct mem_struct *mm)
  96 {
  97         struct mem_struct *next = get_next(mm);
  98
  99         mm->free = 1;
 100         if (next->free)
 101                 merge_back(mm, next);
 102         return mm;
 103 }
 104
 105 /*
 106  * Here's the main function, malloc, which allocates a memory rigon
 107  * of size _size_. Returns NULL if failed, or the address newly allocated.
 108  *
 109  */
 110 void *malloc(int size)
 111 {
 112         struct mem_struct *next = next_start;
 113         struct mem_struct *good = next, *prev;
 114         int size_needed = (size + sizeof(struct mem_struct) + 3) & ~3;
 115
 116         while(next) {
 117                 if (next->free && next->size >= size_needed) {
 118                         good = next;
 119                         break;
 120                 }
 121                 next = get_next(next);
 122         }
 123         if (good->size < size_needed) {
 124                 printk("Out of memory, maybe we need append it\n");
 125                 return NULL;
 126         } else if (good->size == size_needed) {
 127                 /*
 128                  * We just found a right memory that with the exact
 129                  * size we want. So we just Mark it _not_free_ here,
 130                  * and move on the _next_start_ pointer, even though
 131                  * the next may not be a right next start.
 132                  */
 133                 good->free = 0;
 134                 next_start = get_next(good);
 135                 goto out;
 136         } else
 137                 size = good->size;  /* save the total size */
 138
 139         /*
 140          * Note: allocate a new memory region will not change
 141          * it's prev memory, so we don't need change it here.
 142          */
 143         good->free = 0;       /* Mark it not free any more */
 144         good->size = size_needed;
 145
 146         next = get_next(good);
 147         if (next) {
 148                 next->size = size - size_needed;
 149                 /* check if it can contain 1 byte allocation at least */
 150                 if (next->size <= (int)sizeof(struct mem_struct)) {
 151                         good->size = size;     /* restore the original size */
 152                         next_start = get_next(good);
 153                         goto out;
 154                 }
 155
 156                 next->prev = good;
 157                 next->free = 1;
 158                 next_start = next; /* Update next_start */
 159
 160                 prev = next;
 161                 next = get_next(next);
 162                 if (next)
 163                         next->prev = prev;
 164         } else
 165                 next_start = (struct mem_struct *)memory;
 166 out:
 167         return (void *)((uint32_t)good + sizeof(struct mem_struct));
 168 }
 169
 170 void free(void *ptr)
 171 {
 172         struct mem_struct *mm = ptr - sizeof(*mm);
 173         struct mem_struct *prev = mm->prev;
 174         struct mem_struct *next = get_next(mm);
 175
 176         if (mm->free == 1)
 177                 return;
 178         if (!prev)
 179                 mm = try_merge_back(mm);
 180         else if (!next)
 181                 mm = try_merge_front(mm);
 182         else if (prev->free && !next->free)
 183                 merge_front(mm, prev);
 184         else if (!prev->free && next->free)
 185                 merge_back(mm, next);
 186         else if (prev->free && next->free)
 187                 merge_both(mm, prev, next);
 188         else
 189                 mm->free = 1;
 190
 191         if (mm < next_start)
 192                 next_start = mm;
 193 }
 194
 195 /*
 196  * The debug function
 197  */
 198 void check_mem(void)
 199 {
 200         struct mem_struct *next = (struct mem_struct *)memory;
 201
 202         printk("____________\n");
 203         while (next) {
 204                 if (next->size == 0) {
 205                         printk(" BAD ");
 206                         break;
 207                 }
 208                 printk("%-6d  %s\n", next->size, next->free ? "Free" : "Notf");
 209                 next = get_next(next);
 210         }
 211         printk("\n");
 212 }
 213
 214 void Debug_mm(void)
 215 {
 216         char *buf;
 217
 218 #include <hexdump.h>
 219 #include <fd.h>
 220         buf = malloc(1024);
 221         printk("malloc returned: %p\n", buf);
 222         floppy_reads(0, buf, 2);
 223         hexdump(buf + 512, 128);
 224 }
 225
 226
 227 void malloc_init(void)
 228 {
 229
 230         struct mem_struct *first = (struct mem_struct *)memory;
 231
 232         first->prev = NULL;
 233         first->size = MEM_SIZE;
 234         first->free = 1;
 235
 236         next_start = first;
 237 }