kernel/memory.c

   1 /*
   2  *  ZeX/OS
   3  *  Copyright (C) 2007  Tomas 'ZeXx86' Jedrzejek (zexx86@gmail.com)
   4  *
   5  *  This program is free software: you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation, either version 3 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19
  20 #include <system.h>
  21 #include <x86.h>
  22 #include <string.h>
  23
  24 #define _32BIT  1
  25
  26 /* use small (32K) heap for 16-bit compilers,
  27 large (500K) heap for 32-bit compilers */
  28 #if defined(_32BIT)
  29 #define HEAP_SIZE       500000uL
  30 #else
  31 #define HEAP_SIZE       8192u
  32 #endif
  33
  34 #define MALLOC_MAGIC    0x6D92  /* must be < 0x8000 */
  35
  36 typedef struct _malloc          /* Turbo C      DJGPP */
  37 {
  38         size_t size;            /* 2 bytes       4 bytes */
  39         struct _malloc *next;   /* 2 bytes       4 bytes */
  40         unsigned magic : 15;    /* 2 bytes total 4 bytes total */
  41         unsigned used : 1;
  42 } malloc_t;             /* total   6 bytes      12 bytes */
  43
  44 static char *g_heap_bot, *g_kbrk, *g_heap_top;
  45 /*****************************************************************************
  46 *****************************************************************************/
  47 static void kdump_heap (void)
  48 {
  49         unsigned blks_used = 0, blks_free = 0;
  50         size_t bytes_used = 0, bytes_free = 0;
  51         malloc_t *m;
  52         int total;
  53
  54         for (m = (malloc_t *)g_heap_bot; m != NULL; m = m->next)
  55         {
  56                 DPRINT ("blk %5p: %6u bytes %s\n", m,
  57                         m->size, m->used ? "used" : "free");
  58
  59                 if (m->used)
  60                 {
  61                         blks_used++;
  62                         bytes_used += m->size;
  63                 }
  64                 else
  65                 {
  66                         blks_free++;
  67                         bytes_free += m->size;
  68                 }
  69         }
  70
  71         DPRINT ("blks:  %6u used, %6u free, %6u total\n", blks_used,
  72                 blks_free, blks_used + blks_free);
  73         DPRINT ("bytes: %6u used, %6u free, %6u total\n", bytes_used,
  74                 bytes_free, bytes_used + bytes_free);
  75         DPRINT ("g_heap_bot=0x%p, g_kbrk=0x%p, g_heap_top=0x%p\n",
  76                 g_heap_bot, g_kbrk, g_heap_top);
  77
  78         total = (bytes_used + bytes_free) +
  79                         (blks_used + blks_free) * sizeof(malloc_t);
  80
  81         if(total != g_kbrk - g_heap_bot)
  82                 DPRINT ("*** some heap memory is not accounted for\n");
  83 }
  84 /*****************************************************************************
  85 POSIX sbrk() looks like this
  86         void *sbrk(int incr);
  87 Mine is a bit different so I can signal the calling function
  88 if more memory than desired was allocated (e.g. in a system with paging)
  89 If your kbrk()/sbrk() always allocates the amount of memory you ask for,
  90 this code can be easily changed.
  91
  92                         int brk(        void *sbrk(             void *kbrk(
  93 function                 void *adr);     int delta);             int *delta);
  94 ----------------------  ------------    ------------            -------------
  95 POSIX?                  yes             yes                     NO
  96 return value if error   -1              -1                      NULL
  97 get break value         .               sbrk(0)                 int x=0; kbrk(&x);
  98 set break value to X    brk(X)          sbrk(X - sbrk(0))       int x=X, y=0; kbrk(&x) - kbrk(&y);
  99 enlarge heap by N bytes .               sbrk(+N)                int x=N; kbrk(&x);
 100 shrink heap by N bytes  .               sbrk(-N)                int x=-N; kbrk(&x);
 101 can you tell if you're
 102   given more memory
 103   than you wanted?      no              no                      yes
 104 *****************************************************************************/
 105 static void *kbrk (int *delta)
 106 {
 107         static char heap[HEAP_SIZE];
 108 /**/
 109         char *new_brk, *old_brk;
 110
 111 /* heap doesn't exist yet */
 112         if(g_heap_bot == NULL)
 113         {
 114                 g_heap_bot = g_kbrk = heap;
 115                 g_heap_top = g_heap_bot + HEAP_SIZE;
 116         }
 117         new_brk = g_kbrk + (*delta);
 118 /* too low: return NULL */
 119         if(new_brk < g_heap_bot)
 120                 return NULL;
 121 /* too high: return NULL */
 122         if(new_brk >= g_heap_top)
 123                 return NULL;
 124 /* success: adjust brk value... */
 125         old_brk = g_kbrk;
 126         g_kbrk = new_brk;
 127 /* ...return actual delta... (for this sbrk(), they are the same)
 128         (*delta) = (*delta); */
 129 /* ...return old brk value */
 130         return old_brk;
 131 }
 132
 133 /*****************************************************************************
 134 kmalloc() and kfree() use g_heap_bot, but not g_kbrk nor g_heap_top
 135 *****************************************************************************/
 136 void *kmalloc(size_t size)
 137 {
 138         unsigned total_size;
 139         malloc_t *m, *n;
 140         int delta;
 141
 142         if(size == 0)
 143                 return NULL;
 144         total_size = size + sizeof(malloc_t);
 145 /* search heap for free block (FIRST FIT) */
 146         m = (malloc_t *)g_heap_bot;
 147 /* g_heap_bot == 0 == NULL if heap does not yet exist */
 148         if(m != NULL)
 149         {
 150                 if(m->magic != MALLOC_MAGIC)
 151 //                      panic("kernel heap is corrupt in kmalloc()");
 152                 {
 153                         kprintf ("*** kernel heap is corrupt in kmalloc()\n");
 154                         return NULL;
 155                 }
 156                 for(; m->next != NULL; m = m->next)
 157                 {
 158                         if(m->used)
 159                                 continue;
 160 /* size == m->size is a perfect fit */
 161                         if(size == m->size)
 162                                 m->used = 1;
 163                         else
 164                         {
 165 /* otherwise, we need an extra sizeof(malloc_t) bytes for the header
 166 of a second, free block */
 167                                 if(total_size > m->size)
 168                                         continue;
 169 /* create a new, smaller free block after this one */
 170                                 n = (malloc_t *)((char *)m + total_size);
 171                                 n->size = m->size - total_size;
 172                                 n->next = m->next;
 173                                 n->magic = MALLOC_MAGIC;
 174                                 n->used = 0;
 175 /* reduce the size of this block and mark it used */
 176                                 m->size = size;
 177                                 m->next = n;
 178                                 m->used = 1;
 179                         }
 180                         return (char *)m + sizeof(malloc_t);
 181                 }
 182         }
 183 /* use kbrk() to enlarge (or create!) heap */
 184         delta = total_size;
 185         n = kbrk(&delta);
 186 /* uh-oh */
 187         if(n == NULL)
 188                 return NULL;
 189         if(m != NULL)
 190                 m->next = n;
 191         n->size = size;
 192         n->magic = MALLOC_MAGIC;
 193         n->used = 1;
 194 /* did kbrk() return the exact amount of memory we wanted?
 195 cast to make "gcc -Wall -W ..." shut the hell up */
 196         if((int)total_size == delta)
 197                 n->next = NULL;
 198         else
 199         {
 200 /* it returned more than we wanted (it will never return less):
 201 create a new, free block */
 202                 m = (malloc_t *)((char *)n + total_size);
 203                 m->size = delta - total_size - sizeof(malloc_t);
 204                 m->next = NULL;
 205                 m->magic = MALLOC_MAGIC;
 206                 m->used = 0;
 207
 208                 n->next = m;
 209         }
 210         return (char *)n + sizeof(malloc_t);
 211 }
 212 /*****************************************************************************
 213 *****************************************************************************/
 214 void kfree(void *blk)
 215 {
 216         malloc_t *m, *n;
 217
 218 /* get address of header */
 219         m = (malloc_t *)((char *)blk - sizeof(malloc_t));
 220         if(m->magic != MALLOC_MAGIC)
 221 //              panic("attempt to kfree() block at 0x%p "
 222 //                      "with bad magic value", blk);
 223         {
 224                 kprintf ("*** attempt to kfree() block at 0x%p "
 225                         "with bad magic value\n", blk);
 226                 return;
 227         }
 228 /* find this block in the heap */
 229         n = (malloc_t *)g_heap_bot;
 230         if(n->magic != MALLOC_MAGIC)
 231 //              panic("kernel heap is corrupt in kfree()");
 232         {
 233                 kprintf ("*** kernel heap is corrupt in kfree()\n");
 234                 return;
 235         }
 236         for(; n != NULL; n = n->next)
 237         {
 238                 if(n == m)
 239                         break;
 240         }
 241 /* not found? bad pointer or no heap or something else? */
 242         if(n == NULL)
 243 //              panic("attempt to kfree() block at 0x%p "
 244 //                      "that is not in the heap", blk);
 245         {
 246                 kprintf ("*** attempt to kfree() block at 0x%p "
 247                         "that is not in the heap\n", blk);
 248                 return;
 249         }
 250 /* free the block */
 251         m->used = 0;
 252 /* coalesce adjacent free blocks
 253 Hard to spell, hard to do */
 254         for(m = (malloc_t *)g_heap_bot; m != NULL; m = m->next)
 255         {
 256                 while(!m->used && m->next != NULL && !m->next->used)
 257                 {
 258 /* resize this block */
 259                         m->size += sizeof(malloc_t) + m->next->size;
 260 /* merge with next block */
 261                         m->next = m->next->next;
 262                 }
 263         }
 264 }
 265 /*****************************************************************************
 266 *****************************************************************************/
 267 void *krealloc(void *blk, size_t size)
 268 {
 269         void *new_blk;
 270         malloc_t *m;
 271
 272 /* size == 0: free block */
 273         if(size == 0)
 274         {
 275                 if(blk != NULL)
 276                         kfree(blk);
 277                 new_blk = NULL;
 278         }
 279         else
 280         {
 281 /* allocate new block */
 282                 new_blk = kmalloc(size);
 283 /* if allocation OK, and if old block exists, copy old block to new */
 284                 if(new_blk != NULL && blk != NULL)
 285                 {
 286                         m = (malloc_t *)((char *)blk - sizeof(malloc_t));
 287                         if(m->magic != MALLOC_MAGIC)
 288 //                              panic("attempt to krealloc() block at "
 289 //                                      "0x%p with bad magic value", blk);
 290                         {
 291                                 kprintf ("*** attempt to krealloc() block at "
 292                                         "0x%p with bad magic value\n", blk);
 293                                 return NULL;
 294                         }
 295 /* copy minimum of old and new block sizes */
 296                         if(size > m->size)
 297                                 size = m->size;
 298                         memcpy(new_blk, blk, size);
 299 /* free the old block */
 300                         kfree(blk);
 301                 }
 302         }
 303         return new_blk;
 304 }
 305 /*****************************************************************************
 306 *****************************************************************************/
 307
 308 unsigned int init_mm ()
 309 {
 310         kdump_heap ();
 311
 312         //file_cache = (char *) kmalloc (sizeof (char) * 4096);
 313
 314         return 1;
 315 }
 316
 317 #ifdef test
 318
 319 #define SLOTS   17
 320
 321 int main (void)
 322 {
 323         unsigned lifetime[SLOTS];
 324         void *blk[SLOTS];
 325         int i, j, k;
 326
 327         kdump_heap();
 328         memset(lifetime, 0, sizeof(lifetime));
 329         memset(blk, 0, sizeof(blk));
 330         for(i = 0; i < 1000; i++)
 331         {
 332                 kprintf ("Pass %6u\n", i);
 333                 for(j = 0; j < SLOTS; j++)
 334                 {
 335 /* age the block */
 336                         if(lifetime[j] != 0)
 337                         {
 338                                 (lifetime[j])--;
 339                                 continue;
 340                         }
 341 /* too old; free it */
 342                         if(blk[j] != NULL)
 343                         {
 344                                 kfree(blk[j]);
 345                                 blk[j] = NULL;
 346                         }
 347 /* alloc new block of random size
 348 Note that size_t==unsigned, but kmalloc() uses integer math,
 349 so block size must be positive integer */
 350 #if defined(_32BIT)
 351                         k = rand() % 40960 + 1;
 352 #else
 353                         k = rand() % 4096 + 1;
 354 #endif
 355                         blk[j] = kmalloc(k);
 356                         if(blk[j] == NULL)
 357                                 kprintf ("failed to alloc %u bytes\n", k);
 358                         else
 359 /* give it a random lifetime 0-20 */
 360                                 lifetime[j] = rand() % 21;
 361                 }
 362         }
 363 /* let's see what we've wrought */
 364         kprintf ("\n\n");
 365         kdump_heap();
 366 /* free everything */
 367         for(j = 0; j < SLOTS; j++)
 368         {
 369                 if(blk[j] != NULL)
 370                 {
 371                         kfree(blk[j]);
 372                         blk[j] = NULL;
 373                 }
 374                 (lifetime[j]) = 0;
 375         }
 376 /* after all that, we should have a single, unused block */
 377         kdump_heap();
 378         return 0;
 379 }
 380 /*****************************************************************************
 381 *****************************************************************************/
 382
 383 #endif