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