bootx.tproj/libclite.subproj/zalloc.c

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