i386/libsa/zalloc.c

   1 /*
   2  * Copyright (c) 1999-2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Portions Copyright (c) 1999-2003 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 2.0 (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         size_t 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 char * zalloc_end;
  51 static void   (*zerror)(char *, size_t);
  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 #if ZDEBUG
  59 size_t zalloced_size;
  60 #endif
  61
  62 #define ZALLOC_NODES    16384
  63
  64 static void malloc_error(char *addr, size_t size)
  65 {
  66 #ifdef i386
  67     asm volatile ("hlt");
  68 #endif
  69 }
  70
  71 // define the block of memory that the allocator will use
  72 void malloc_init(char * start, int size, int nodes, void (*malloc_err_fn)(char *, size_t))
  73 {
  74         zalloc_base         = start ? start : (char *)ZALLOC_ADDR;
  75         totalNodes          = nodes ? nodes : ZALLOC_NODES;
  76         zalloced            = (zmem *) zalloc_base;
  77         zavailable          = (zmem *) zalloc_base + sizeof(zmem) * totalNodes;
  78         zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes;
  79         if (size == 0) size = ZALLOC_LEN;
  80         zavailable[0].size  = size - (zavailable[0].start - zalloc_base);
  81         zalloc_end          = zalloc_base + size;
  82         availableNodes      = 1;
  83         allocedNodes        = 0;
  84         zerror              = malloc_err_fn ? malloc_err_fn : malloc_error;
  85 }
  86
  87 #define BEST_FIT 1
  88
  89 void * malloc(size_t size)
  90 {
  91         int    i;
  92 #if BEST_FIT
  93         int    bestFit;
  94         size_t smallestSize;
  95 #endif
  96         char * ret = 0;
  97
  98         if ( !zalloc_base )
  99         {
 100                 // this used to follow the bss but some bios' corrupted it...
 101                 malloc_init((char *)ZALLOC_ADDR, ZALLOC_LEN, ZALLOC_NODES, malloc_error);
 102         }
 103
 104         size = ((size + 0xf) & ~0xf);
 105
 106         if (size == 0) {
 107             if (zerror) (*zerror)((char *)0xdeadbeef, 0);
 108         }
 109 #if BEST_FIT
 110         smallestSize = 0;
 111         bestFit = -1;
 112 #endif
 113
 114         for (i = 0; i < availableNodes; i++)
 115         {
 116                 // find node with equal size, or if not found,
 117                 // then smallest node that fits.
 118                 if ( zavailable[i].size == size )
 119                 {
 120                         zallocate(ret = zavailable[i].start, size);
 121                         zdelete(zavailable, i); availableNodes--;
 122                         goto done;
 123                 }
 124 #if BEST_FIT
 125                 else
 126                 {
 127                     if ((zavailable[i].size > size) &&
 128                         ((smallestSize == 0) ||
 129                          (zavailable[i].size < smallestSize)))
 130                     {
 131                         bestFit = i;
 132                         smallestSize = zavailable[i].size;
 133                     }
 134                 }
 135
 136 #else
 137                 else if ( zavailable[i].size > size )
 138                 {
 139                         zallocate(ret = zavailable[i].start, size);
 140                         zavailable[i].start += size;
 141                         zavailable[i].size  -= size;
 142                         goto done;
 143                 }
 144 #endif
 145         }
 146 #if BEST_FIT
 147         if (bestFit != -1)
 148         {
 149             zallocate(ret = zavailable[bestFit].start, size);
 150             zavailable[bestFit].start += size;
 151             zavailable[bestFit].size  -= size;
 152         }
 153 #endif
 154
 155 done:
 156         if ((ret == 0) || (ret + size >= zalloc_end))
 157     {
 158                 if (zerror) (*zerror)(ret, size);
 159     }
 160         if (ret != 0)
 161     {
 162                 bzero(ret, size);
 163     }
 164 #if ZDEBUG
 165         zalloced_size += size;
 166 #endif
 167         return (void *) ret;
 168 }
 169
 170 void free(void * pointer)
 171 {
 172         unsigned long rp;
 173         int i, found = 0;
 174         size_t tsize = 0;
 175         char * start = pointer;
 176
 177 #if i386
 178         // Get return address of our caller,
 179         // in case we have to report an error below.
 180         asm volatile ("movl %%esp, %%eax\n\t"
 181             "subl $4, %%eax\n\t"
 182             "movl 0(%%eax), %%eax" : "=a" (rp) );
 183 #else
 184         rp = 0;
 185 #endif
 186
 187         if ( !start ) return;
 188
 189         for (i = 0; i < allocedNodes; i++)
 190         {
 191                 if ( zalloced[i].start == start )
 192                 {
 193                         tsize = zalloced[i].size;
 194 #if ZDEBUG
 195                         zout -= tsize;
 196                         printf("    zz out %d\n",zout);
 197 #endif
 198                         zdelete(zalloced, i); allocedNodes--;
 199                         found = 1;
 200 #if ZDEBUG
 201                         memset(pointer, 0x5A, tsize);
 202 #endif
 203                         break;
 204                 }
 205         }
 206         if ( !found )  {
 207             if (zerror) (*zerror)(pointer, rp);
 208             else return;
 209         }
 210 #if ZDEBUG
 211         zalloced_size -= tsize;
 212 #endif
 213
 214         for (i = 0; i < availableNodes; i++)
 215         {
 216                 if ((start + tsize) == zavailable[i].start)  // merge it in
 217                 {
 218                         zavailable[i].start = start;
 219                         zavailable[i].size += tsize;
 220                         zcoalesce();
 221                         return;
 222                 }
 223
 224                 if ((i > 0) &&
 225                     (zavailable[i-1].start + zavailable[i-1].size == start))
 226                 {
 227                         zavailable[i-1].size += tsize;
 228                         zcoalesce();
 229                         return;
 230                 }
 231
 232                 if ((start + tsize) < zavailable[i].start)
 233                 {
 234                         if (++availableNodes > totalNodes) {
 235                             if (zerror) (*zerror)((char *)0xf000f000, 0);
 236                         }
 237                         zinsert(zavailable, i);
 238                         zavailable[i].start = start;
 239                         zavailable[i].size = tsize;
 240                         return;
 241                 }
 242         }
 243
 244         if (++availableNodes > totalNodes) {
 245             if (zerror) (*zerror)((char *)0xf000f000, 1);
 246         }
 247         zavailable[i].start = start;
 248         zavailable[i].size  = tsize;
 249         zcoalesce();
 250         return;
 251 }
 252
 253 static void
 254 zallocate(char * start,int size)
 255 {
 256 #if ZDEBUG
 257         zout += size;
 258         printf("    alloc %d, total 0x%x\n",size,zout);
 259 #endif
 260         zalloced[allocedNodes].start = start;
 261         zalloced[allocedNodes].size  = size;
 262         if (++allocedNodes > totalNodes) {
 263             if (zerror) (*zerror)((char *)0xf000f000, 2);
 264         };
 265 }
 266
 267 static void
 268 zinsert(zmem * zp, int ndx)
 269 {
 270         int i;
 271         zmem *z1, *z2;
 272
 273         i  = totalNodes-2;
 274         z1 = zp + i;
 275         z2 = z1 + 1;
 276
 277         for (; i >= ndx; i--, z1--, z2--)
 278         {
 279             *z2 = *z1;
 280         }
 281 }
 282
 283 static void
 284 zdelete(zmem * zp, int ndx)
 285 {
 286         int i;
 287         zmem *z1, *z2;
 288
 289         z1 = zp + ndx;
 290         z2 = z1 + 1;
 291
 292         for (i = ndx; i < totalNodes-1; i++, z1++, z2++)
 293         {
 294             *z1 = *z2;
 295         }
 296 }
 297
 298 static void
 299 zcoalesce(void)
 300 {
 301         int i;
 302
 303         for (i = 0; i < availableNodes-1; i++)
 304         {
 305                 if ( zavailable[i].start + zavailable[i].size ==
 306              zavailable[i+1].start )
 307                 {
 308                         zavailable[i].size += zavailable[i+1].size;
 309                         zdelete(zavailable, i+1); availableNodes--;
 310                         return;
 311                 }
 312         }
 313 }
 314
 315 /* This is the simplest way possible.  Should fix this. */
 316 void * realloc(void * start, size_t newsize)
 317 {
 318     void * newstart = malloc(newsize);
 319     bcopy(start, newstart, newsize);
 320     free(start);
 321     return newstart;
 322 }