/*
- * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 1999-2003 Apple Computer, Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
- * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
+ * Portions 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 1.1 (the "License"). You may not use this file
+ * 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.apple.com/publicsource and read it before using
* this file.
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
+
+#define ZALLOC_NODES 16384
-static void malloc_error()
+static void malloc_error(char *addr, size_t size)
{
- // printf("Out of memory\n");
+#ifdef i386
+ asm volatile ("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);
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 volatile ("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++)
#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++)
{
}
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();
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;
}
#endif
zalloced[allocedNodes].start = start;
zalloced[allocedNodes].size = size;
- allocedNodes++;
+ if (++allocedNodes > totalNodes) {
+ if (zerror) (*zerror)((char *)0xf000f000, 2);
+ };
}
static void
for (; i >= ndx; i--, z1--, z2--)
{
- z2->start = z1->start;
- z2->size = z1->size;
+ *z2 = *z1;
}
}
for (i = ndx; i < totalNodes-1; i++, z1++, z2++)
{
- z1->start = z2->start;
- z1->size = z2->size;
+ *z1 = *z2;
}
}
projects / apple / boot.git / blobdiff