kernel/core/mm/kmem.c

   1 /*
   2  *  ZeX/OS
   3  *  Copyright (C) 2007  Tomas 'ZeXx86' Jedrzejek (zexx86@zexos.org)
   4  *  Copyright (C) 2008  Tomas 'ZeXx86' Jedrzejek (zexx86@zexos.org)
   5  *  Copyright (C) 2009  Tomas 'ZeXx86' Jedrzejek (zexx86@zexos.org)
   6  *
   7  *  This program is free software: you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation, either version 3 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  This program is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License
  18  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19  */
  20
  21
  22 #include <system.h>
  23 #include <arch/io.h>
  24 #include <string.h>
  25 #include <build.h>
  26 #include <config.h>
  27 #include <mutex.h>
  28
  29 #ifndef CONFIG_MEM_ZALLOC
  30
  31 #define _32BIT  1
  32
  33 /* use small (32K) heap for 16-bit compilers,
  34 large (500K) heap for 32-bit compilers */
  35 #if defined(_32BIT)
  36 #define HEAP_SIZE       0x100000
  37 #else
  38 #define HEAP_SIZE       8192u
  39 #endif
  40
  41 #define MALLOC_MAGIC    0x6D92  /* must be < 0x8000 */
  42
  43 typedef struct _malloc          /* Turbo C      DJGPP/GCC */
  44 {
  45         size_t size;            /* 2 bytes       4 bytes */
  46         struct _malloc *next;   /* 2 bytes       4 bytes */
  47         unsigned magic : 15;    /* 2 bytes total 4 bytes total */
  48         unsigned used : 1;
  49 } malloc_t;             /* total   6 bytes      12 bytes */
  50
  51 static char *g_heap_bot, *g_kbrk, *g_heap_top;
  52
  53 MUTEX_CREATE (mutex_malloc);
  54 MUTEX_CREATE (mutex_free);
  55
  56 /*****************************************************************************
  57 *****************************************************************************/
  58 static void kdump_heap (void)
  59 {
  60         unsigned blks_used = 0, blks_free = 0;
  61         size_t bytes_used = 0, bytes_free = 0;
  62         malloc_t *m;
  63         int total;
  64
  65         for (m = (malloc_t *)g_heap_bot; m != NULL; m = m->next)        {
  66
  67                 DPRINT (DBG_MM | DBG_KMEM, "blk %5p: %6u bytes %s", m,
  68                         m->size, m->used ? "used" : "free");
  69
  70                 if (m->used) {
  71                         blks_used ++;
  72                         bytes_used += m->size;
  73                 } else {
  74                         blks_free ++;
  75                         bytes_free += m->size;
  76                 }
  77         }
  78
  79         DPRINT (DBG_MM | DBG_KMEM, "blks:  %6u used, %6u free, %6u total", blks_used,
  80                 blks_free, blks_used + blks_free);
  81         DPRINT (DBG_MM | DBG_KMEM, "bytes: %6u used, %6u free, %6u total", bytes_used,
  82                 bytes_free, bytes_used + bytes_free);
  83         DPRINT (DBG_MM | DBG_KMEM, "g_heap_bot=0x%p, g_kbrk=0x%p, g_heap_top=0x%p",
  84                 g_heap_bot, g_kbrk, g_heap_top);
  85
  86         total = (bytes_used + bytes_free) +
  87                         (blks_used + blks_free) * sizeof(malloc_t);
  88
  89         if(total != g_kbrk - g_heap_bot)
  90                 DPRINT (DBG_MM | DBG_KMEM, "*** some heap memory is not accounted for");
  91 }
  92
  93 /*****************************************************************************
  94 POSIX sbrk() looks like this
  95         void *sbrk(int incr);
  96 Mine is a bit different so I can signal the calling function
  97 if more memory than desired was allocated (e.g. in a system with paging)
  98 If your kbrk()/sbrk() always allocates the amount of memory you ask for,
  99 this code can be easily changed.
 100
 101                         int brk(        void *sbrk(             void *kbrk(
 102 function                 void *adr);     int delta);             int *delta);
 103 ----------------------  ------------    ------------            -------------
 104 POSIX?                  yes             yes                     NO
 105 return value if error   -1              -1                      NULL
 106 get break value         .               sbrk(0)                 int x=0; kbrk(&x);
 107 set break value to X    brk(X)          sbrk(X - sbrk(0))       int x=X, y=0; kbrk(&x) - kbrk(&y);
 108 enlarge heap by N bytes .               sbrk(+N)                int x=N; kbrk(&x);
 109 shrink heap by N bytes  .               sbrk(-N)                int x=-N; kbrk(&x);
 110 can you tell if you're
 111   given more memory
 112   than you wanted?      no              no                      yes
 113 *****************************************************************************/
 114 static void *kbrk (int *delta)
 115 {
 116         static char heap[HEAP_SIZE];
 117
 118         char *new_brk, *old_brk;
 119
 120         /* heap doesn't exist yet */
 121         if(g_heap_bot == NULL) {
 122                 g_heap_bot = g_kbrk = heap;
 123                 g_heap_top = g_heap_bot + HEAP_SIZE;
 124         }
 125
 126         new_brk = g_kbrk + (*delta);
 127
 128         /* too low: return NULL */
 129         if(new_brk < g_heap_bot)
 130                 return NULL;
 131
 132         /* too high: return NULL */
 133         if(new_brk >= g_heap_top)
 134                 return NULL;
 135
 136         /* success: adjust brk value... */
 137         old_brk = g_kbrk;
 138         g_kbrk = new_brk;
 139
 140         /* ...return actual delta... (for this sbrk(), they are the same)
 141         (*delta) = (*delta); */
 142         /* ...return old brk value */
 143         return old_brk;
 144 }
 145
 146 /*****************************************************************************
 147 kmalloc() and kfree() use g_heap_bot, but not g_kbrk nor g_heap_top
 148 *****************************************************************************/
 149 void *kmalloc (size_t size)
 150 {
 151         //kprintf ("kmalloc (): %d\n", size);
 152
 153         unsigned total_size;
 154         malloc_t *m, *n;
 155         int delta;
 156
 157         if (size == 0)
 158                 return NULL;
 159
 160         mutex_lock (&mutex_malloc);
 161
 162         total_size = size + sizeof (malloc_t);
 163
 164         /* search heap for free block (FIRST FIT) */
 165         m = (malloc_t *) g_heap_bot;
 166
 167         /* g_heap_bot == 0 == NULL if heap does not yet exist */
 168         if (m != NULL) {
 169                 if (m->magic != MALLOC_MAGIC) {
 170                         kprintf ("*** kernel heap is corrupt in kmalloc()\n");
 171                         mutex_lock (&mutex_malloc);
 172                         return NULL;
 173                 }
 174
 175                 for (; m->next != NULL; m = m->next) {
 176                         if (m->used)
 177                                 continue;
 178
 179                         /* prevent before page fault :-B */
 180                         if (m == (malloc_t *) ~0)
 181                                 continue;
 182
 183                         /* size == m->size is a perfect fit */
 184                         if (size == m->size)
 185                                 m->used = 1;
 186                         else {
 187                                 /* otherwise, we need an extra sizeof(malloc_t) bytes for the header
 188                                 of a second, free block */
 189                                 if (total_size > m->size)
 190                                         continue;
 191
 192                                 /* create a new, smaller free block after this one */
 193                                 n = (malloc_t *) ((char *) m + total_size);
 194                                 n->size = m->size - total_size;
 195                                 n->next = m->next;
 196                                 n->magic = MALLOC_MAGIC;
 197                                 n->used = 0;
 198
 199                                 /* reduce the size of this block and mark it used */
 200                                 m->size = size;
 201                                 m->next = n;
 202                                 m->used = 1;
 203                         }
 204
 205                         mutex_unlock (&mutex_malloc);
 206
 207                         return (char *) m + sizeof (malloc_t);
 208                 }
 209         }
 210
 211         /* use kbrk() to enlarge (or create!) heap */
 212         delta = total_size;
 213         n = kbrk (&delta);
 214
 215         /* uh-oh */
 216         if (n == NULL) {
 217                 DPRINT (DBG_MM | DBG_KMEM, "kbrk () == NULL");
 218                 mutex_unlock (&mutex_malloc);
 219                 return NULL;
 220         }
 221
 222         if (m != NULL)
 223                 m->next = n;
 224
 225         n->size = size;
 226         n->magic = MALLOC_MAGIC;
 227         n->used = 1;
 228
 229         /* did kbrk() return the exact amount of memory we wanted?
 230         cast to make "gcc -Wall -W ..." shut the hell up */
 231         if ((int) total_size == delta)
 232                 n->next = NULL;
 233         else {
 234                 /* it returned more than we wanted (it will never return less):
 235                 create a new, free block */
 236                 m = (malloc_t *)((char *)n + total_size);
 237                 m->size = delta - total_size - sizeof(malloc_t);
 238                 m->next = NULL;
 239                 m->magic = MALLOC_MAGIC;
 240                 m->used = 0;
 241
 242                 n->next = m;
 243         }
 244
 245         mutex_unlock (&mutex_malloc);
 246
 247         return (char *) n + sizeof (malloc_t);
 248 }
 249 /*****************************************************************************
 250 *****************************************************************************/
 251 void kfree (void *blk)
 252 {
 253         if (!blk)
 254                 return;
 255
 256         mutex_lock (&mutex_free);
 257
 258         malloc_t *m, *n;
 259
 260         /* get address of header */
 261         m = (malloc_t *)((char *) blk - sizeof(malloc_t));
 262
 263         if (m->magic != MALLOC_MAGIC) {
 264                 kprintf ("*** attempt to kfree() block at 0x%p "
 265                         "with bad magic value\n", blk);
 266                 goto cleanup;
 267         }
 268
 269         /* find this block in the heap */
 270         n = (malloc_t *)g_heap_bot;
 271
 272         if (n->magic != MALLOC_MAGIC) {
 273                 kprintf ("*** kernel heap is corrupt in kfree()\n");
 274                 goto cleanup;
 275         }
 276
 277         for (; n != NULL; n = n->next) {
 278                 if(n == m)
 279                         break;
 280         }
 281
 282         /* not found? bad pointer or no heap or something else? */
 283         if (n == NULL) {
 284                 kprintf ("*** attempt to kfree() block at 0x%p "
 285                         "that is not in the heap\n", blk);
 286
 287                 mutex_unlock (&mutex_free);
 288                 goto cleanup;
 289         }
 290
 291         /* free the block */
 292         m->used = 0;
 293
 294         /* coalesce adjacent free blocks Hard to spell, hard to do */
 295         for (m = (malloc_t *)g_heap_bot; m != NULL; m = m->next) {
 296                 while (!m->used && m->next != NULL && !m->next->used) {
 297                         /* resize this block */
 298                         m->size += sizeof(malloc_t) + m->next->size;
 299                         /* merge with next block */
 300                         m->next = m->next->next;
 301                 }
 302         }
 303
 304 cleanup:
 305         mutex_unlock (&mutex_free);
 306 }
 307 /*****************************************************************************
 308 *****************************************************************************/
 309 void *krealloc (void *blk, size_t size)
 310 {
 311         void *new_blk;
 312         malloc_t *m;
 313
 314         /* size == 0: free block */
 315         if (size == 0) {
 316                 if(blk != NULL)
 317                         kfree (blk);
 318
 319                 new_blk = NULL;
 320         } else {
 321                 /* allocate new block */
 322                 new_blk = kmalloc (size);
 323
 324                 /* if allocation OK, and if old block exists, copy old block to new */
 325                 if (new_blk != NULL && blk != NULL) {
 326                         m = (malloc_t *) ((char *) blk - sizeof (malloc_t));
 327
 328                         if (m->magic != MALLOC_MAGIC) {
 329                                 kprintf ("*** attempt to krealloc() block at 0x%p with bad magic value\n", blk);
 330                                 return NULL;
 331                         }
 332
 333                         /* copy minimum of old and new block sizes */
 334                         if (size > m->size)
 335                                 size = m->size;
 336
 337                         memcpy (new_blk, blk, size);
 338
 339                         /* free the old block */
 340                         kfree (blk);
 341                 }
 342         }
 343         return new_blk;
 344 }
 345
 346
 347 /*****************************************************************************
 348 *****************************************************************************/
 349 unsigned short kmem_get ()
 350 {
 351 #ifdef ARCH_i386
 352         register unsigned long *mem;
 353         unsigned long mem_count, a, mem_end, bse_end;
 354         unsigned short memkb;
 355         unsigned char irq1, irq2;
 356         unsigned long cr0;
 357
 358         /* save IRQ's */
 359         irq1 = inb (0x21);
 360         irq2 = inb (0xA1);
 361
 362         /* kill all irq's */
 363         outb (0x21, 0xFF);
 364         outb (0xA1, 0xFF);
 365
 366         mem_count = 0;
 367         memkb = 0;
 368
 369         // store a copy of CR0
 370         asm volatile ("movl %%cr0, %%eax;" : "=a"(cr0));
 371
 372         // invalidate the cache
 373         // write-back and invalidate the cache
 374         asm volatile ("wbinvd;");
 375
 376         // plug cr0 with just PE/CD/NW
 377         // cache disable(486+), no-writeback(486+), 32bit mode(386+)
 378         asm volatile ("movl %%eax, %%cr0;" ::
 379                              "a" (cr0 | 0x00000001 | 0x40000000 | 0x20000000));
 380
 381         do
 382         {
 383                 memkb ++;
 384                 mem_count += 1024*1024;
 385                 mem = (unsigned long *) mem_count;
 386
 387                 a = *mem;
 388
 389                 *mem = 0x55AA55AA;
 390
 391                 /* the empty asm calls tell gcc not to rely on whats in its registers
 392                    as saved variables (this gets us around GCC optimisations) */
 393                 asm (";" ::: "memory");
 394                 if (*mem != 0x55AA55AA)
 395                         mem_count = 0;
 396                 else
 397                 {
 398                         *mem = 0xAA55AA55;
 399                         asm ("":::"memory");
 400                         if (*mem!=0xAA55AA55)
 401                                 mem_count = 0;
 402                 }
 403
 404                 asm (";":::"memory");
 405                 *mem = a;
 406         } while (memkb < 4096 && mem_count != 0);
 407
 408         asm volatile ("movl %%eax, %%cr0;" :: "a" (cr0));
 409
 410         mem_end = memkb << 20;
 411         mem = (unsigned long *) 0x413;
 412         bse_end = ((*mem) &0xFFFF) << 6;
 413
 414         outb (0x21, irq1);
 415         outb (0xA1, irq2);
 416
 417         return memkb;
 418 #endif
 419         return 0;
 420 }
 421
 422 void *sbrk (int *delta)
 423 {
 424         static char heap[HEAP_SIZE];
 425
 426         char *new_brk, *old_brk;
 427
 428         /* heap doesn't exist yet */
 429         if(g_heap_bot == NULL) {
 430                 g_heap_bot = g_kbrk = heap;
 431                 g_heap_top = g_heap_bot + HEAP_SIZE;
 432         }
 433
 434         new_brk = g_kbrk + (*delta);
 435         /* too low: return NULL */
 436         if(new_brk < g_heap_bot)
 437                 return NULL;
 438
 439         /* too high: return NULL */
 440         if(new_brk >= g_heap_top)
 441                 return NULL;
 442
 443         /* success: adjust brk value... */
 444         old_brk = g_kbrk;
 445         g_kbrk = new_brk;
 446
 447         /* .. return actual delta... (for this sbrk(), they are the same)
 448            .. return old brk value */
 449         return old_brk;
 450 }
 451
 452 /*****************************************************************************
 453 *****************************************************************************/
 454 void util_cmdfree ()
 455 {
 456                 unsigned blks_used = 0, blks_free = 0;
 457                 size_t bytes_used = 0, bytes_free = 0;
 458                 malloc_t *m;
 459                 int total;
 460
 461                 for (m = (malloc_t *)g_heap_bot; m != NULL; m = m->next) {
 462                         /*DPRINT (DBG_MM | DBG_KMEM, "blk %5p: %6u bytes %s\n", m,
 463                                 m->size, m->used ? "used" : "free");*/
 464
 465                         if (m->used) {
 466                                 blks_used++;
 467                                 bytes_used += m->size;
 468                         } else {
 469                                 blks_free++;
 470                                 bytes_free += m->size;
 471                         }
 472                 }
 473
 474                 DPRINT (DBG_MM | DBG_KMEM, "blks:  %6u used, %6u free, %6u total", blks_used,
 475                         blks_free, blks_used + blks_free);
 476                 DPRINT (DBG_MM | DBG_KMEM, "bytes: %6u used, %6u free, %6u total", bytes_used,
 477                         bytes_free, bytes_used + bytes_free);
 478                 DPRINT (DBG_MM | DBG_KMEM, "g_heap_bot=0x%p, g_kbrk=0x%p, g_heap_top=0x%p",
 479                         g_heap_bot, g_kbrk, g_heap_top);
 480
 481                 /* we have to increase used memory from user-space apps */
 482                 bytes_used += umem_used () / 1024;
 483
 484                 printf ("\ttotal\tused\tfree\tshared\tbuffers\tcached\n");
 485                 printf ("Mem: \t%u\t%u\t%u\t%u\t%u\t%u\n",
 486                         mem_ext*1024, bytes_used/1024, mem_ext*1024 - bytes_used/1024, 0, 0, blks_free);
 487 }
 488
 489 /*****************************************************************************
 490 *****************************************************************************/
 491 unsigned int init_mm ()
 492 {
 493         //mem_ext = kmem_get ();        // get extended memory (in Mb)
 494
 495         kdump_heap ();
 496
 497         pmem_init ();
 498         swmem_init ();
 499         umem_init ();
 500
 501         //file_cache = (char *) kmalloc (sizeof (char));
 502
 503         return 1;
 504 }
 505
 506 #endif