gen/libsa/zalloc.c

   1 /*
   2  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /*
  26  * Copyright 1993 NeXT Computer, Inc.
  27  * All rights reserved.
  28  *
  29  * Sam's simple memory allocator.
  30  *
  31  */
  32
  33 #import "libsa.h"
  34 #import "memory.h"
  35 #import "zalloc.h"
  36
  37 #define ZDEBUG 0
  38
  39 #if ZDEBUG
  40 int zout;
  41 #endif
  42
  43 typedef struct {
  44         char *start;
  45         int size;
  46 } zmem;
  47
  48 static zmem *zalloced;
  49 static zmem *zavailable;
  50 static short availableNodes, allocedNodes, totalNodes;
  51 static char *zalloc_base;
  52
  53 static void zallocate(char *start,int size);
  54 static void zinsert(zmem *zp, int ndx);
  55 static void zdelete(zmem *zp, int ndx);
  56 static void zcoalesce(void);
  57
  58
  59 // define the block of memory that the allocator will use
  60 void malloc_init(char *start, int size, int nodes)
  61 {
  62         zalloc_base = start;
  63         totalNodes = nodes;
  64         zalloced = (zmem *)zalloc_base;
  65         start += sizeof(zmem) * nodes;
  66         zavailable = (zmem *)start;
  67         start += sizeof(zmem) * nodes;
  68         zavailable[0].start = start;
  69         zavailable[0].size = size;
  70         availableNodes = 1;
  71         allocedNodes = 0;
  72 }
  73
  74 void * malloc(size_t size)
  75 {
  76         int i;
  77         char *ret = 0;
  78 #if 0
  79         extern char     _DATA__end;
  80 #endif
  81         if (!zalloc_base)
  82         {
  83                 // this used to follow the bss but some bios' corrupted it...
  84                 malloc_init((char *)ZALLOC_ADDR, ZALLOC_LEN, ZALLOC_NODES);
  85         }
  86
  87         size = ((size + 0xf) & ~0xf);
  88
  89         for (i=0; i<availableNodes; i++)
  90         {
  91                 // uses first possible node, doesn't try to find best fit
  92                 if (zavailable[i].size == size)
  93                 {
  94                         zallocate(ret = zavailable[i].start, size);
  95                         zdelete(zavailable, i); availableNodes--;
  96                         goto done;
  97                 }
  98                 else if (zavailable[i].size > size)
  99                 {
 100                         zallocate(ret = zavailable[i].start, size);
 101                         zavailable[i].start += size;
 102                         zavailable[i].size -= size;
 103                         goto done;
 104                 }
 105         }
 106
 107 done:
 108 #if 0
 109 /*      if (ret + size >= (char*)_sp()) _stop("stack clobbered"); */
 110         if (ret + size >= (char *)(ZALLOC_ADDR + ZALLOC_LEN))
 111                 _stop("Out of memory");
 112 #endif
 113         if (ret != 0)
 114                 bzero(ret, size);
 115         return (void *)ret;
 116 }
 117
 118 void
 119 free(void *pointer)
 120 {
 121         int i, tsize, found = 0;
 122         char *start = pointer;
 123
 124         if (!start) return;
 125
 126         for (i=0; i<allocedNodes; i++)
 127         {
 128                 if (zalloced[i].start == start)
 129                 {
 130                         tsize = zalloced[i].size;
 131 #if ZDEBUG
 132                         zout -= tsize;
 133                         printf("    zz out %d\n",zout);
 134 #endif
 135                         zdelete(zalloced, i); allocedNodes--;
 136                         found = 1;
 137                         break;
 138                 }
 139         }
 140         if (!found) return;
 141
 142         for (i=0; i<availableNodes; i++)
 143         {
 144                 if ((start+tsize) == zavailable[i].start)  // merge it in
 145                 {
 146                         zavailable[i].start = start;
 147                         zavailable[i].size += tsize;
 148                         zcoalesce();
 149                         return;
 150                 }
 151
 152                 if (i>0 && (zavailable[i-1].start + zavailable[i-1].size ==
 153                                                                     start))
 154                 {
 155                         zavailable[i-1].size += tsize;
 156                         zcoalesce();
 157                         return;
 158                 }
 159
 160                 if ((start+tsize) < zavailable[i].start)
 161                 {
 162                         zinsert(zavailable, i); availableNodes++;
 163                         zavailable[i].start = start;
 164                         zavailable[i].size = tsize;
 165                         return;
 166                 }
 167         }
 168
 169         zavailable[i].start = start;
 170         zavailable[i].size = tsize;
 171         availableNodes++;
 172         zcoalesce();
 173         return;
 174 }
 175
 176
 177 static void
 178 zallocate(char *start,int size)
 179 {
 180 #if ZDEBUG
 181         zout += size;
 182         printf("    alloc %d, total 0x%x\n",size,zout);
 183 #endif
 184         zalloced[allocedNodes].start = start;
 185         zalloced[allocedNodes].size = size;
 186         allocedNodes++;
 187 }
 188
 189 static void
 190 zinsert(zmem *zp, int ndx)
 191 {
 192         int i;
 193         zmem *z1, *z2;
 194
 195         i=totalNodes-2;
 196         z1 = zp + i;
 197         z2 = z1+1;
 198
 199         for (; i>= ndx; i--, z1--, z2--)
 200         {
 201                 z2->start = z1->start;
 202                 z2->size = z1->size;
 203         }
 204 }
 205
 206 static void
 207 zdelete(zmem *zp, int ndx)
 208 {
 209         int i;
 210         zmem *z1, *z2;
 211
 212         z1 = zp + ndx;
 213         z2 = z1+1;
 214
 215         for (i=ndx; i<totalNodes-1; i++, z1++, z2++)
 216         {
 217                 z1->start = z2->start;
 218                 z1->size = z2->size;
 219         }
 220 }
 221
 222 static void
 223 zcoalesce(void)
 224 {
 225         int i;
 226         for (i=0; i<availableNodes-1; i++)
 227         {
 228                 if (zavailable[i].start + zavailable[i].size ==
 229                                                 zavailable[i+1].start)
 230                 {
 231                         zavailable[i].size += zavailable[i+1].size;
 232                         zdelete(zavailable, i+1); availableNodes--;
 233                         return;
 234                 }
 235         }
 236 }
 237
 238 /* This is the simplest way possible.  Should fix this. */
 239 void *realloc(void *start, size_t newsize)
 240 {
 241     void *newstart = malloc(newsize);
 242     bcopy(start, newstart, newsize);
 243     free(start);
 244     return newstart;
 245 }
 246
 247