gen/libsa/zalloc.c

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