qemu/roms/SLOF/lib/libc/stdlib/malloc.c

   1 /******************************************************************************
   2  * Copyright (c) 2004, 2008 IBM Corporation
   3  * All rights reserved.
   4  * This program and the accompanying materials
   5  * are made available under the terms of the BSD License
   6  * which accompanies this distribution, and is available at
   7  * http://www.opensource.org/licenses/bsd-license.php
   8  *
   9  * Contributors:
  10  *     IBM Corporation - initial implementation
  11  *****************************************************************************/
  12
  13
  14 #include "stddef.h"
  15 #include "stdlib.h"
  16 #include "unistd.h"
  17 #include "malloc_defs.h"
  18
  19
  20 static int clean(void);
  21
  22
  23 /* act points to the end of the initialized heap and the start of uninitialized heap */
  24 static char *act;
  25
  26 /* Pointers to start and end of heap: */
  27 static char *heap_start, *heap_end;
  28
  29
  30 /*
  31  * Standard malloc function
  32  */
  33 void *
  34 malloc(size_t size)
  35 {
  36         char *header;
  37         void *data;
  38         size_t blksize;         /* size of memory block including the chunk */
  39
  40         blksize = size + sizeof(struct chunk);
  41
  42         /* has malloc been called for the first time? */
  43         if (act == 0) {
  44                 size_t initsize;
  45                 /* add some space so we have a good initial playground */
  46                 initsize = (blksize + 0x1000) & ~0x0fff;
  47                 /* get initial memory region with sbrk() */
  48                 heap_start = sbrk(initsize);
  49                 if (heap_start == (void*)-1)
  50                         return NULL;
  51                 heap_end = heap_start + initsize;
  52                 act = heap_start;
  53         }
  54
  55         header = act;
  56         data = act + sizeof(struct chunk);
  57
  58         /* Check if there is space left in the uninitialized part of the heap */
  59         if (act + blksize > heap_end) {
  60                 //search at begin of heap
  61                 header = heap_start;
  62
  63                 while ((((struct chunk *) header)->inuse != 0
  64                         || ((struct chunk *) header)->length < size)
  65                        && header < act) {
  66                         header = header + sizeof(struct chunk)
  67                                  + ((struct chunk *) header)->length;
  68                 }
  69
  70                 // check if heap is full
  71                 if (header >= act) {
  72                         if (clean()) {
  73                                 // merging of free blocks succeeded, so try again
  74                                 return malloc(size);
  75                         } else if (sbrk(blksize) == heap_end) {
  76                                 // succeeded to get more memory, so try again
  77                                 heap_end += blksize;
  78                                 return malloc(size);
  79                         } else {
  80                                 // No more memory available
  81                                 return 0;
  82                         }
  83                 }
  84
  85                 // Check if we need to split this memory block into two
  86                 if (((struct chunk *) header)->length > blksize) {
  87                         //available memory is too big
  88                         int alt;
  89
  90                         alt = ((struct chunk *) header)->length;
  91                         ((struct chunk *) header)->inuse = 1;
  92                         ((struct chunk *) header)->length = size;
  93                         data = header + sizeof(struct chunk);
  94
  95                         //mark the rest of the heap
  96                         header = data + size;
  97                         ((struct chunk *) header)->inuse = 0;
  98                         ((struct chunk *) header)->length =
  99                             alt - blksize;
 100                 } else {
 101                         //new memory matched exactly in available memory
 102                         ((struct chunk *) header)->inuse = 1;
 103                         data = header + sizeof(struct chunk);
 104                 }
 105
 106         } else {
 107
 108                 ((struct chunk *) header)->inuse = 1;
 109                 ((struct chunk *) header)->length = size;
 110
 111                 act += blksize;
 112         }
 113
 114         return data;
 115 }
 116
 117
 118 /*
 119  * Merge free memory blocks in initialized heap if possible
 120  */
 121 static int
 122 clean(void)
 123 {
 124         char *header;
 125         char *firstfree = 0;
 126         char check = 0;
 127
 128         header = heap_start;
 129         //if (act == 0)         // This should never happen
 130         //      act = heap_end;
 131
 132         while (header < act) {
 133
 134                 if (((struct chunk *) header)->inuse == 0) {
 135                         if (firstfree == 0) {
 136                                 /* First free block in a row, only save address */
 137                                 firstfree = header;
 138
 139                         } else {
 140                                 /* more than one free block in a row, merge them! */
 141                                 ((struct chunk *) firstfree)->length +=
 142                                     ((struct chunk *) header)->length +
 143                                     sizeof(struct chunk);
 144                                 check = 1;
 145                         }
 146                 } else {
 147                         firstfree = 0;
 148
 149                 }
 150
 151                 header = header + sizeof(struct chunk)
 152                          + ((struct chunk *) header)->length;
 153
 154         }
 155
 156         return check;
 157 }