X-Git-Url: https://git.saurik.com/apple/boot.git/blobdiff_plain/75b89a82fae8b6d553467b92cb5431b2b5b4df7e..f083c6c388c9bea8d87e360850329e0c60ce21aa:/i386/libsa/zalloc.c diff --git a/i386/libsa/zalloc.c b/i386/libsa/zalloc.c index 932fdec..5652665 100644 --- a/i386/libsa/zalloc.c +++ b/i386/libsa/zalloc.c @@ -3,21 +3,22 @@ * * @APPLE_LICENSE_HEADER_START@ * - * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights - * Reserved. This file contains Original Code and/or Modifications of - * Original Code as defined in and that are subject to the Apple Public - * Source License Version 1.1 (the "License"). You may not use this file - * except in compliance with the License. Please obtain a copy of the - * License at http://www.apple.com/publicsource and read it before using - * this file. + * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved. + * + * This file contains Original Code and/or Modifications of Original Code + * as defined in and that are subject to the Apple Public Source License + * Version 2.0 (the 'License'). You may not use this file except in + * compliance with the License. Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this + * file. * * The Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT. Please see the - * License for the specific language governing rights and limitations - * under the License. + * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * Please see the License for the specific language governing rights and + * limitations under the License. * * @APPLE_LICENSE_HEADER_END@ */ @@ -40,65 +41,100 @@ int zout; typedef struct { char * start; - int size; + size_t size; } zmem; static zmem * zalloced; static zmem * zavailable; static short availableNodes, allocedNodes, totalNodes; static char * zalloc_base; -static void (*zerror)(); +static char * zalloc_end; +static void (*zerror)(char *, size_t); static void zallocate(char * start,int size); static void zinsert(zmem * zp, int ndx); static void zdelete(zmem * zp, int ndx); static void zcoalesce(void); -#define ZALLOC_NODES 1024 +#if ZDEBUG +size_t zalloced_size; +#endif -static void malloc_error() +#define ZALLOC_NODES 16384 + +static void malloc_error(char *addr, size_t size) { - // printf("Out of memory\n"); +#ifdef i386 + asm("hlt"); +#endif } // define the block of memory that the allocator will use -void malloc_init(char * start, int size, int nodes) +void malloc_init(char * start, int size, int nodes, void (*malloc_err_fn)(char *, size_t)) { - zalloc_base = start; - totalNodes = nodes; + zalloc_base = start ? start : (char *)ZALLOC_ADDR; + totalNodes = nodes ? nodes : ZALLOC_NODES; zalloced = (zmem *) zalloc_base; - start += sizeof(zmem) * nodes; - zavailable = (zmem *) start; - start += sizeof(zmem) * nodes; - zavailable[0].start = start; - zavailable[0].size = size; + zavailable = (zmem *) zalloc_base + sizeof(zmem) * totalNodes;; + zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes; + if (size == 0) size = ZALLOC_LEN; + zavailable[0].size = size - (zavailable[0].start - zalloc_base); + zalloc_end = zalloc_base + size; availableNodes = 1; allocedNodes = 0; - zerror = malloc_error; + zerror = malloc_err_fn ? malloc_err_fn : malloc_error; } +#define BEST_FIT 1 + void * malloc(size_t size) { int i; +#if BEST_FIT + int bestFit; + size_t smallestSize; +#endif char * ret = 0; if ( !zalloc_base ) { // this used to follow the bss but some bios' corrupted it... - malloc_init((char *)ZALLOC_ADDR, ZALLOC_LEN, ZALLOC_NODES); + malloc_init((char *)ZALLOC_ADDR, ZALLOC_LEN, ZALLOC_NODES, malloc_error); } size = ((size + 0xf) & ~0xf); + + if (size == 0) { + if (zerror) (*zerror)((char *)0xdeadbeef, 0); + } +#if BEST_FIT + smallestSize = 0; + bestFit = -1; +#endif for (i = 0; i < availableNodes; i++) { - // uses first possible node, doesn't try to find best fit + // find node with equal size, or if not found, + // then smallest node that fits. if ( zavailable[i].size == size ) { zallocate(ret = zavailable[i].start, size); zdelete(zavailable, i); availableNodes--; goto done; } +#if BEST_FIT + else + { + if ((zavailable[i].size > size) && + ((smallestSize == 0) || + (zavailable[i].size < smallestSize))) + { + bestFit = i; + smallestSize = zavailable[i].size; + } + } + +#else else if ( zavailable[i].size > size ) { zallocate(ret = zavailable[i].start, size); @@ -106,25 +142,49 @@ void * malloc(size_t size) zavailable[i].size -= size; goto done; } - } +#endif + } +#if BEST_FIT + if (bestFit != -1) + { + zallocate(ret = zavailable[bestFit].start, size); + zavailable[bestFit].start += size; + zavailable[bestFit].size -= size; + } +#endif done: - if ((ret == 0) || (ret + size >= (char *)(ZALLOC_ADDR + ZALLOC_LEN))) + if ((ret == 0) || (ret + size >= zalloc_end)) { - if (zerror) (*zerror)(ret); + if (zerror) (*zerror)(ret, size); } if (ret != 0) { bzero(ret, size); } +#if ZDEBUG + zalloced_size += size; +#endif return (void *) ret; } void free(void * pointer) { - int i, tsize = 0, found = 0; + unsigned long rp; + int i, found = 0; + size_t tsize = 0; char * start = pointer; +#if i386 + // Get return address of our caller, + // in case we have to report an error below. + asm("movl %%esp, %%eax\n\t" + "subl $4, %%eax\n\t" + "movl 0(%%eax), %%eax" : "=a" (rp) ); +#else + rp = 0; +#endif + if ( !start ) return; for (i = 0; i < allocedNodes; i++) @@ -138,10 +198,19 @@ void free(void * pointer) #endif zdelete(zalloced, i); allocedNodes--; found = 1; +#if ZDEBUG + memset(pointer, 0x5A, tsize); +#endif break; } } - if ( !found ) return; + if ( !found ) { + if (zerror) (*zerror)(pointer, rp); + else return; + } +#if ZDEBUG + zalloced_size -= tsize; +#endif for (i = 0; i < availableNodes; i++) { @@ -154,7 +223,7 @@ void free(void * pointer) } if ((i > 0) && - (zavailable[i-1].start + zavailable[i-1].size == start)) + (zavailable[i-1].start + zavailable[i-1].size == start)) { zavailable[i-1].size += tsize; zcoalesce(); @@ -163,16 +232,21 @@ void free(void * pointer) if ((start + tsize) < zavailable[i].start) { - zinsert(zavailable, i); availableNodes++; + if (++availableNodes > totalNodes) { + if (zerror) (*zerror)((char *)0xf000f000, 0); + } + zinsert(zavailable, i); zavailable[i].start = start; zavailable[i].size = tsize; return; } } + if (++availableNodes > totalNodes) { + if (zerror) (*zerror)((char *)0xf000f000, 1); + } zavailable[i].start = start; zavailable[i].size = tsize; - availableNodes++; zcoalesce(); return; } @@ -186,7 +260,9 @@ zallocate(char * start,int size) #endif zalloced[allocedNodes].start = start; zalloced[allocedNodes].size = size; - allocedNodes++; + if (++allocedNodes > totalNodes) { + if (zerror) (*zerror)((char *)0xf000f000, 2); + }; } static void @@ -201,8 +277,7 @@ zinsert(zmem * zp, int ndx) for (; i >= ndx; i--, z1--, z2--) { - z2->start = z1->start; - z2->size = z1->size; + *z2 = *z1; } } @@ -217,8 +292,7 @@ zdelete(zmem * zp, int ndx) for (i = ndx; i < totalNodes-1; i++, z1++, z2++) { - z1->start = z2->start; - z1->size = z2->size; + *z1 = *z2; } }