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  * 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  *  zalloc.c - malloc functions.
  34  *
  35  *  Copyright (c) 1998-2003 Apple Computer, Inc.
  36  *
  37  *  DRI: Josh de Cesare
  38  */
  39
  40 #include <libclite.h>
  41
  42 #define ZALLOC_NODES    768
  43
  44 #define ZDEBUG 0
  45
  46 #if ZDEBUG
  47 int zout;
  48 #endif
  49
  50 typedef struct {
  51         char *start;
  52         int size;
  53 } zmem;
  54
  55 static int zalloc_addr;
  56 static int zalloc_len;
  57 static zmem *zalloced;
  58 static zmem *zavailable;
  59 static short availableNodes, allocedNodes, totalNodes;
  60 static char *zalloc_base;
  61 static void (*zerror)();
  62
  63 static void zallocate(char *start,int size);
  64 static void zinsert(zmem *zp, int ndx);
  65 static void zdelete(zmem *zp, int ndx);
  66 static void zcoalesce(void);
  67
  68
  69 // define the block of memory that the allocator will use
  70 void malloc_init(char *start, int size)
  71 {
  72         int nodes = ZALLOC_NODES;
  73
  74         zalloc_addr = (int)start;
  75         zalloc_len = size;
  76
  77         zalloc_base = start;
  78         totalNodes = nodes;
  79         zalloced = (zmem *)zalloc_base;
  80         start += sizeof(zmem) * nodes;
  81         zavailable = (zmem *)start;
  82         start += sizeof(zmem) * nodes;
  83         zavailable[0].start = start;
  84         zavailable[0].size = size;
  85         availableNodes = 1;
  86         allocedNodes = 0;
  87 }
  88
  89 void malloc_error_init(void (*error_fn)())
  90 {
  91     zerror = error_fn;
  92 }
  93
  94 void * malloc(size_t size)
  95 {
  96         int i;
  97         char *ret = 0;
  98 #if 0
  99         extern char     _DATA__end;
 100 #endif
 101         if (!zalloc_base) {
 102           // return error until malloc_init is called.
 103           return NULL;
 104         }
 105
 106         size = ((size + 0xf) & ~0xf);
 107
 108         for (i=0; i<availableNodes; i++)
 109         {
 110                 // uses first possible node, doesn't try to find best fit
 111                 if (zavailable[i].size == size)
 112                 {
 113                         zallocate(ret = zavailable[i].start, size);
 114                         zdelete(zavailable, i); availableNodes--;
 115                         goto done;
 116                 }
 117                 else if (zavailable[i].size > size)
 118                 {
 119                         zallocate(ret = zavailable[i].start, size);
 120                         zavailable[i].start += size;
 121                         zavailable[i].size -= size;
 122                         goto done;
 123                 }
 124         }
 125
 126 done:
 127 /*      if (ret + size >= (char*)_sp()) _stop("stack clobbered"); */
 128         if ((ret == 0) || (ret + size >= (char *)(zalloc_addr + zalloc_len)))
 129                 if (zerror)
 130                     (*zerror)(ret);
 131         if (ret != 0)
 132                 bzero(ret, size);
 133         return (void *)ret;
 134 }
 135
 136 void
 137 free(void *pointer)
 138 {
 139         int i, tsize, found = 0;
 140         char *start = pointer;
 141
 142         if (!zalloc_base) {
 143           // return until malloc_init is called.
 144           return;
 145         }
 146
 147         if (!start) return;
 148
 149         for (i=0; i<allocedNodes; i++)
 150         {
 151                 if (zalloced[i].start == start)
 152                 {
 153                         tsize = zalloced[i].size;
 154 #if ZDEBUG
 155                         zout -= tsize;
 156                         printf("    zz out %d\n",zout);
 157 #endif
 158                         zdelete(zalloced, i); allocedNodes--;
 159                         found = 1;
 160                         break;
 161                 }
 162         }
 163         if (!found) return;
 164
 165         for (i=0; i<availableNodes; i++)
 166         {
 167                 if ((start+tsize) == zavailable[i].start)  // merge it in
 168                 {
 169                         zavailable[i].start = start;
 170                         zavailable[i].size += tsize;
 171                         zcoalesce();
 172                         return;
 173                 }
 174
 175                 if (i>0 && (zavailable[i-1].start + zavailable[i-1].size ==
 176                                                                     start))
 177                 {
 178                         zavailable[i-1].size += tsize;
 179                         zcoalesce();
 180                         return;
 181                 }
 182
 183                 if ((start+tsize) < zavailable[i].start)
 184                 {
 185                         zinsert(zavailable, i); availableNodes++;
 186                         zavailable[i].start = start;
 187                         zavailable[i].size = tsize;
 188                         return;
 189                 }
 190         }
 191
 192         zavailable[i].start = start;
 193         zavailable[i].size = tsize;
 194         availableNodes++;
 195         zcoalesce();
 196         return;
 197 }
 198
 199
 200 static void
 201 zallocate(char *start,int size)
 202 {
 203 #if ZDEBUG
 204         zout += size;
 205         printf("    alloc %d, total 0x%x\n",size,zout);
 206 #endif
 207         zalloced[allocedNodes].start = start;
 208         zalloced[allocedNodes].size = size;
 209         allocedNodes++;
 210 }
 211
 212 static void
 213 zinsert(zmem *zp, int ndx)
 214 {
 215         int i;
 216         zmem *z1, *z2;
 217
 218         i=totalNodes-2;
 219         z1 = zp + i;
 220         z2 = z1+1;
 221
 222         for (; i>= ndx; i--, z1--, z2--)
 223         {
 224                 z2->start = z1->start;
 225                 z2->size = z1->size;
 226         }
 227 }
 228
 229 static void
 230 zdelete(zmem *zp, int ndx)
 231 {
 232         int i;
 233         zmem *z1, *z2;
 234
 235         z1 = zp + ndx;
 236         z2 = z1+1;
 237
 238         for (i=ndx; i<totalNodes-1; i++, z1++, z2++)
 239         {
 240                 z1->start = z2->start;
 241                 z1->size = z2->size;
 242         }
 243 }
 244
 245 static void
 246 zcoalesce(void)
 247 {
 248         int i;
 249         for (i=0; i<availableNodes-1; i++)
 250         {
 251                 if (zavailable[i].start + zavailable[i].size ==
 252                                                 zavailable[i+1].start)
 253                 {
 254                         zavailable[i].size += zavailable[i+1].size;
 255                         zdelete(zavailable, i+1); availableNodes--;
 256                         return;
 257                 }
 258         }
 259 }
 260
 261 /* This is the simplest way possible.  Should fix this. */
 262 void *realloc(void *start, size_t newsize)
 263 {
 264     void *newstart;
 265
 266     if (!zalloc_base) {
 267       // return error until malloc_init is called.
 268       return NULL;
 269     }
 270
 271     newstart = malloc(newsize);
 272     bcopy(start, newstart, newsize);
 273     free(start);
 274     return newstart;
 275 }
 276
 277