/* Satoria's malloc intended to be optimized for lpmud.
** this memory manager distinguishes between two sizes
** of blocks: small and large. It manages them separately
** in the hopes of avoiding fragmentation between them.
** It expects small blocks to mostly be temporaries.
** It expects an equal number of future requests as small
** block deallocations.
**
** support for atari st/tt and FAST_FIT by amylaar @cs.tu-berlin.de
**
** adapted by Blackthorn@Genocide to work with MudOS 0.9.15 - 93/01/26
**
** Amiga Lattice support added by Robocoder@TMI-2
*/
#define IN_MALLOC_WRAPPER
#define NO_OPCODES
#include "std.h"
#include "file_incl.h"
#include "lpc_incl.h"
#include "simulate.h"
#include "comm.h"
#if defined(sparc)
#define MALLOC_ALIGN 8
#else
#define MALLOC_ALIGN 4
#endif
#define POINTER void *
#define FREE_RETURN_TYPE void
#define FREE_RETURN return;
#define SFREE_RETURN_TYPE FREE_RETURN_TYPE
#define SFREE_RETURN FREE_RETURN
#define FIT_STYLE_FAST_FIT
#undef LARGE_TRACE
#define fake(s)
#define SMALL_BLOCK_MAX_BYTES 32
#define SMALL_CHUNK_SIZE 0x4000
#define CHUNK_SIZE 0x40000
#define SMALL_BLOCK_MAX (SMALL_BLOCK_MAX_BYTES/SIZEOF_INT)
#define PREV_BLOCK 0x80000000
#define THIS_BLOCK 0x40000000
#define NO_REF 0x20000000 /* check this in gcollect.c */
#define MASK 0x0FFFFFFF
#define MAGIC 0x17952932
/* SMALL BLOCK info */
typedef unsigned int u;
static u *last_small_chunk = 0;
static u *sfltable[SMALL_BLOCK_MAX] =
{0, 0, 0, 0, 0, 0, 0, 0}; /* freed list */
static u *next_unused = 0;
static u unused_size = 0; /* until we need a new chunk */
/* LARGE BLOCK info */
#ifndef FIT_STYLE_FAST_FIT
static u *free_list = 0;
#endif /* FIT_STYLE_FAST_FIT */
static u *start_next_block = 0;
/* STATISTICS */
static int small_count[SMALL_BLOCK_MAX] =
{0, 0, 0, 0, 0, 0, 0, 0};
static int small_total[SMALL_BLOCK_MAX] =
{0, 0, 0, 0, 0, 0, 0, 0};
static int small_max[SMALL_BLOCK_MAX] =
{0, 0, 0, 0, 0, 0, 0, 0};
static int small_free[SMALL_BLOCK_MAX] =
{0, 0, 0, 0, 0, 0, 0, 0};
typedef struct {
unsigned counter, size;
} t_stat;
#define count(a,b) { a.size+=(b); if ((b)<0) --a.counter; else ++a.counter; }
#define count_up(a,b) { a.size+=(b); ++a.counter; }
#define count_back(a,b) { a.size-=(b); --a.counter; }
#if 0
int debugmalloc = 0; /* Only used when debuging malloc() */
#endif
/********************************************************/
/* SMALL BLOCK HANDLER */
/********************************************************/
static char *large_malloc (u, int);
static void large_free (char *);
static int malloc_size_mask (void);
static int malloced_size (POINTER);
static void show_block (u *);
static void remove_from_free_list (u *);
static void add_to_free_list (u *);
static void build_block (u *, u);
static void mark_block (u *);
static char *esbrk (u);
static int resort_free_list (void);
#ifdef DEBUG
static void walk_new_small_malloced (void (*func) (POINTER, int));
#endif
#define s_size_ptr(p) (p)
#define s_next_ptr(p) ((u **) (p+1))
t_stat small_alloc_stat =
{0, 0};
t_stat small_free_stat =
{0, 0};
t_stat small_chunk_stat =
{0, 0};
POINTER CDECL smalloc_malloc (size_t size)
{
/* int i; */
u *temp;
DEBUG_CHECK(size == 0, "Malloc size 0.\n");
if (size > SMALL_BLOCK_MAX_BYTES)
return large_malloc(size, 0);
#if SIZEOF_PTR > SIZEOF_INT
if (size < SIZEOF_PTR)
size = SIZEOF_PTR;
#endif
size = (size + 7) & ~3; /* block size in bytes */
#define SIZE_INDEX(u_array, size) (*(u*) ((char*)u_array-8+size))
#define SIZE_PNT_INDEX(u_array, size) (*(u**)((char*)u_array-8+size))
/* i = (size - 8) >> 2; */
count_up(small_alloc_stat, size);
SIZE_INDEX(small_count, size) += 1; /* update statistics */
SIZE_INDEX(small_total, size) += 1;
if (SIZE_INDEX(small_count, size) > SIZE_INDEX(small_max, size))
SIZE_INDEX(small_max, size) = SIZE_INDEX(small_count, size);
if (temp = SIZE_PNT_INDEX(sfltable, size)) { /* allocate from the
* free list */
count_back(small_free_stat, size);
temp++;
SIZE_PNT_INDEX(sfltable, size) = *(u **) temp;
fake("From free list.");
return (char *) temp;
} /* else allocate from the chunk */
if (unused_size < size) { /* no room in chunk, get another */
/*
* don't waste this smaller block
*/
if (unused_size) {
count_up(small_free_stat, unused_size);
*s_size_ptr(next_unused) = unused_size >> 2;
*s_next_ptr(next_unused) = SIZE_PNT_INDEX(sfltable, unused_size);
SIZE_PNT_INDEX(sfltable, unused_size) = next_unused;
}
fake("Allocating new small chunk.");
next_unused = (u *) large_malloc(SMALL_CHUNK_SIZE + SIZEOF_PTR, 1);
if (next_unused == 0)
return 0;
*next_unused = (u) last_small_chunk;
last_small_chunk = next_unused++;
count_up(small_chunk_stat, SMALL_CHUNK_SIZE + SIZEOF_PTR);
count_up(small_alloc_stat, SIZEOF_PTR);
unused_size = SMALL_CHUNK_SIZE;
} else
fake("Allocated from chunk.");
temp = (u *) s_next_ptr(next_unused);
*s_size_ptr(next_unused) = size >> 2;
unused_size -= size;
if (unused_size < (SIZEOF_INT + SIZEOF_PTR)) {
count_up(small_alloc_stat, unused_size);
if ((size + unused_size) < (SMALL_BLOCK_MAX_BYTES + SIZEOF_INT)) {
/*
* try to avoid waste
*/
size += unused_size;
*s_size_ptr(next_unused) = size >> 2;
}
unused_size = 0;
}
next_unused += size >> 2;
fake("allocation from chunk successful\n");
return (char *) temp;
}
#ifdef DEBUG
char *debug_free_ptr;
#endif /* DEBUG */
static int malloc_size_mask()
{
return MASK;
}
static int malloced_size (POINTER ptr)
{
return (((u *) ptr)[-1] & MASK);
}
SFREE_RETURN_TYPE CDECL smalloc_free (POINTER ptr)
{
u *block;
u i;
if (!ptr)
SFREE_RETURN;
#ifdef DEBUG
debug_free_ptr = ptr;
#endif /* DEBUG */
block = (u *) ptr;
block -= 1;
i = (*s_size_ptr(block) & MASK);
if ((*s_size_ptr(block) & MASK) > SMALL_BLOCK_MAX + 1) {
fake("sfree calls large_free");
large_free(ptr);
SFREE_RETURN
}
count_back(small_alloc_stat, i << 2);
count_up(small_free_stat, i << 2);
i -= 2;
*s_next_ptr(block) = sfltable[i];
sfltable[i] = block;
small_free[i] += 1;
fake("Freed");
SFREE_RETURN
}
/************************************************/
/* LARGE BLOCK HANDLER */
/************************************************/
#define BEST_FIT 0
#define FIRST_FIT 1
#define HYBRID 2
#define fit_style BEST_FIT
/* if this is a constant, evaluate at compile-time.... */
#ifndef fit_style
int fit_style = BEST_FIT;
#endif
#define l_size_ptr(p) (p)
#define l_next_ptr(p) (*((u **) (p+1)))
#define l_prev_ptr(p) (*((u **) ((u **)(p+1)+1)))
#define l_next_block(p) (p + (MASK & (*(p))) )
#define l_prev_block(p) (p - (MASK & (*(p-1))) )
#define l_prev_free(p) (!(*p & PREV_BLOCK))
#define l_next_free(p) (!(*l_next_block(p) & THIS_BLOCK))
static void show_block (u * ptr)
{
printf("[%c%d: %d] ", (*ptr & THIS_BLOCK ? '+' : '-'),
ptr, (*ptr & MASK));
}
#ifdef FIT_STYLE_FAST_FIT
#if defined(atarist) || defined (sun) || defined(AMIGA)
/* there is a type signed char */
typedef SIGNED char balance_t;
#define BALANCE_T_BITS 8
#else
typedef short balance_t;
#define BALANCE_T_BITS 16
#endif
#if (defined(atarist) && !defined(ATARI_TT)) || defined(sparc) || defined(AMIGA)
/* try to avoid multiple shifts, because these are costly */
#define NO_BARREL_SHIFT
#endif
typedef struct free_block_s {
u size;
struct free_block_s *parent, *left, *right;
balance_t balance;
short align_dummy;
} free_block_t;
/* prepare two nodes for the free tree that will never be removed,
so that we can always assume that the tree is and remains non-empty. */
/* some compilers don't understand forward declarations of static vars. */
extern free_block_t dummy2;
static free_block_t dummy = {
/* size */ 0,
/* parent */ &dummy2,
/* left */ 0,
/* right */ 0,
/* balance */ 0
};
free_block_t dummy2 =
{
/* size */ 0,
/* parent */ 0,
/* left */ &dummy,
/* right */ 0,
/* balance */ -1
};
static free_block_t *free_tree = &dummy2;
#ifdef DEBUG_AVL
static int inconsistency = 0;
static int check_avl (free_block_t * parent, free_block_t * p)
{
int left, right;
if (!p)
return 0;
left = check_avl(p, p->left);
right = check_avl(p, p->right);
if (p->balance != right - left || p->balance < -1 || p->balance > 1) {
printf("Inconsistency in avl node!\n");
printf("node:%x\n", p);
printf("size: %d\n", p->size);
printf("left node:%x\n", p->left);
printf("left height: %d\n", left);
printf("right node:%x\n", p->right);
printf("right height: %d\n", right);
printf("alleged balance: %d\n", p->balance);
inconsistency = 1;
}
if (p->parent != parent) {
printf("Inconsistency in avl node!\n");
printf("node:%x\n", p);
printf("size: %d\n", p->size);
printf("parent: %x\n", parent);
printf("parent size: %d\n", parent->size);
printf("alleged parent: %x\n", p->parent);
printf("alleged parent size: %d\n", p->parent->size);
printf("left height: %d\n", left);
printf("right height: %d\n", right);
printf("alleged balance: %d\n", p->balance);
inconsistency = 1;
}
return left > right ? left + 1 : right + 1;
}
/* this function returns a value so that it can be used in ,-expressions. */
static int do_check_avl()
{
check_avl(0, free_tree);
if (inconsistency) {
fflush(stderr);
fflush(stdout);
fatal("Inconsistency could crash the driver\n");
}
return 0;
}
#endif /* DEBUG_AVL */
t_stat large_free_stat;
static void remove_from_free_list (u * ptr)
{
free_block_t *p, *q, *r, *s, *t;
fake((do_check_avl(), "remove_from_free_list called"));
p = (free_block_t *) (ptr + 1);
count_back(large_free_stat, p->size << 2);
#ifdef DEBUG_AVL
printf("node:%x\n", p);
printf("size:%d\n", p->size);
#endif
if (p->left) {
if (q = p->right) {
fake("two childs");
s = q;
for (; r = q, q = r->left;);
if (r == s) {
r->left = s = p->left;
s->parent = r;
if (r->parent = s = p->parent) {
if (p == s->left) {
s->left = r;
} else {
s->right = r;
}
} else {
free_tree = r;
}
r->balance = p->balance;
p = r;
goto balance_right;
} else {
t = r->parent;
if (t->left = s = r->right) {
s->parent = t;
}
r->balance = p->balance;
r->left = s = p->left;
s->parent = r;
r->right = s = p->right;
s->parent = r;
if (r->parent = s = p->parent) {
if (p == s->left) {
s->left = r;
} else {
s->right = r;
}
} else {
free_tree = r;
}
p = t;
goto balance_left;
}
} else { /* no right child, but left child */
/*
* We set up the free list in a way so that there will remain at
* least two nodes, and the avl property ensures that the left
* child is a leaf ==> there is a parent
*/
fake("no right child, but left child");
s = p;
p = s->parent;
r = s->left;
r->parent = p;
if (s == p->left) {
p->left = r;
goto balance_left;
} else {
p->right = r;
goto balance_right;
}
}
} else { /* no left child */
/*
* We set up the free list in a way so that there is a node left of
* all used nodes, so there is a parent
*/
fake("no left child");
s = p;
p = s->parent;
if (q = r = s->right) {
r->parent = p;
}
if (s == p->left) {
p->left = r;
goto balance_left;
} else {
p->right = r;
goto balance_right;
}
}
balance_q:
r = p;
p = q;
if (r == p->right) {
balance_t b;
balance_right:
b = p->balance;
if (b > 0) {
p->balance = 0;
if (q = p->parent)
goto balance_q;
return;
} else if (b < 0) {
r = p->left;
b = r->balance;
if (b <= 0) {
/* R-Rotation */
#ifdef DEBUG_AVL
fake("R-Rotation.");
printf("r->balance: %d\n", r->balance);
#endif
if (p->left = s = r->right) {
s->parent = p;
}
r->right = p;
s = p->parent;
p->parent = r;
b += 1;
r->balance = b;
b = -b;
#ifdef DEBUG_AVL
printf("node r: %x\n", r);
printf("r->balance: %d\n", r->balance);
printf("node p: %x\n", p);
p->balance = b;
printf("p->balance: %d\n", p->balance);
printf("r-height: %d\n", check_avl(r->parent, r));
#endif
if (r->parent = s) {
if (p->balance = b) {
if (p == s->left) {
s->left = r;
return;
} else {
s->right = r;
return;
}
}
if (p == s->left) {
fake("left from parent");
goto balance_left_s;
} else {
fake("right from parent");
p = s;
p->right = r;
goto balance_right;
}
}
p->balance = b;
free_tree = r;
return;
} else { /* r->balance == +1 */
/* LR-Rotation */
balance_t b2;
fake("LR-Rotation.");
t = r->right;
b = t->balance;
if (p->left = s = t->right) {
s->parent = p;
}
if (r->right = s = t->left) {
s->parent = r;
}
t->left = r;
t->right = p;
r->parent = t;
s = p->parent;
p->parent = t;
#ifdef NO_BARREL_SHIFT
b = -b;
b2 = b >> 1;
r->balance = b2;
b -= b2;
p->balance = b;
#else
b2 = (unsigned char) b >> 7;
p->balance = b2;
b2 = -b2 - b;
r->balance = b2;
#endif
t->balance = 0;
#ifdef DEBUG_AVL
printf("t-height: %d\n", check_avl(t->parent, t));
#endif
if (t->parent = s) {
if (p == s->left) {
p = s;
s->left = t;
goto balance_left;
} else {
p = s;
s->right = t;
goto balance_right;
}
}
free_tree = t;
return;
}
} else { /* p->balance == 0 */
p->balance = -1;
return;
}
} else { /* r == p->left */
balance_t b;
goto balance_left;
balance_left_s:
p = s;
s->left = r;
balance_left:
b = p->balance;
if (b < 0) {
p->balance = 0;
if (q = p->parent)
goto balance_q;
return;
} else if (b > 0) {
r = p->right;
b = r->balance;
if (b >= 0) {
/* L-Rotation */
#ifdef DEBUG_AVL
fake("L-Rotation.");
printf("r->balance: %d\n", r->balance);
#endif
if (p->right = s = r->left) {
s->parent = p;
}
fake("subtree relocated");
r->left = p;
s = p->parent;
p->parent = r;
b -= 1;
r->balance = b;
b = -b;
#ifdef DEBUG_AVL
fake("balances calculated");
printf("node r: %x\n", r);
printf("r->balance: %d\n", r->balance);
printf("node p: %x\n", p);
p->balance = b;
printf("p->balance: %d\n", p->balance);
printf("r-height: %d\n", check_avl(r->parent, r));
#endif
if (r->parent = s) {
if (p->balance = b) {
if (p == s->left) {
s->left = r;
return;
} else {
s->right = r;
return;
}
}
if (p == s->left) {
fake("left from parent");
goto balance_left_s;
} else {
fake("right from parent");
p = s;
p->right = r;
goto balance_right;
}
}
p->balance = b;
free_tree = r;
return;
} else { /* r->balance == -1 */
/* RL-Rotation */
balance_t b2;
fake("RL-Rotation.");
t = r->left;
b = t->balance;
if (p->right = s = t->left) {
s->parent = p;
}
if (r->left = s = t->right) {
s->parent = r;
}
t->right = r;
t->left = p;
r->parent = t;
s = p->parent;
p->parent = t;
#ifdef NO_BARREL_SHIFT
b = -b;
b2 = b >> 1;
p->balance = b2;
b -= b2;
r->balance = b;
#else
b2 = (unsigned char) b >> 7;
r->balance = b2;
b2 = -b2 - b;
p->balance = b2;
#endif
t->balance = 0;
if (t->parent = s) {
if (p == s->left) {
p = s;
s->left = t;
goto balance_left;
} else {
s->right = t;
p = s;
goto balance_right;
}
}
free_tree = t;
return;
}
} else { /* p->balance == 0 */
p->balance++;
return;
}
}
}
static void add_to_free_list (u * ptr)
{
u size;
free_block_t *p, *q, *r;
/*
* When there is a distinction between data and address registers and/or
* accesses, gcc will choose data type for q, so an assignmnt to q will
* faciliate branching
*/
fake((do_check_avl(), "add_to_free_list called"));
size = *ptr & MASK;
#ifdef DEBUG_AVL
printf("size:%d\n", size);
#endif
q = (free_block_t *) size; /* this assignment is a hint for
* register choice */
r = (free_block_t *) (ptr + 1);
count_up(large_free_stat, size << 2);
q = free_tree;
for (;; /* p = q */ ) {
p = (free_block_t *) q;
#ifdef DEBUG_AVL
printf("checked node size %d\n", p->size);
#endif
if (size < p->size) {
if (q = p->left) {
continue;
}
fake("add left");
p->left = r;
break;
} else { /* >= */
if (q = p->right) {
continue;
}
fake("add right");
p->right = r;
break;
}
}
r->size = size;
r->parent = p;
r->left = 0;
r->right = 0;
r->balance = 0;
#ifdef DEBUG_AVL
fake("built new leaf.");
printf("p->balance:%d\n", p->balance);
#endif
do {
free_block_t *s;
if (r == p->left) {
balance_t b;
if (!(b = p->balance)) {
#ifdef DEBUG_AVL
printf("p->size: %d\n", p->size);
printf("p->balance: %d\n", p->balance);
printf("p->right-h: %d\n", check_avl(p, p->right));
printf("p->left -h: %d\n", check_avl(p, p->left));
fake("growth propagation from left side");
#endif
p->balance = -1;
} else if (b < 0) {
#ifdef DEBUG_AVL
printf("p->balance:%d\n", p->balance);
#endif
if (r->balance < 0) {
/* R-Rotation */
fake("R-Rotation");
if (p->left = s = r->right) {
s->parent = p;
}
r->right = p;
p->balance = 0;
r->balance = 0;
s = p->parent;
p->parent = r;
if (r->parent = s) {
if (s->left == p) {
s->left = r;
} else {
s->right = r;
}
} else {
free_tree = r;
}
} else { /* r->balance == +1 */
/* LR-Rotation */
balance_t b2;
free_block_t *t = r->right;
#ifdef DEBUG_AVL
fake("LR-Rotation");
printf("t = %x\n", t);
printf("r->balance:%d\n", r->balance);
#endif
if (p->left = s = t->right) {
s->parent = p;
}
fake("relocated right subtree");
t->right = p;
if (r->right = s = t->left) {
s->parent = r;
}
fake("relocated left subtree");
t->left = r;
b = t->balance;
#ifdef NO_BARREL_SHIFT
b = -b;
b2 = b >> 1;
r->balance = b2;
b -= b2;
p->balance = b;
#else
b2 = (unsigned char) b >> 7;
p->balance = b2;
b2 = -b2 - b;
r->balance = b2;
#endif
t->balance = 0;
fake("balances calculated");
s = p->parent;
p->parent = t;
r->parent = t;
if (t->parent = s) {
if (s->left == p) {
s->left = t;
} else {
s->right = t;
}
} else {
free_tree = t;
}
#ifdef DEBUG_AVL
printf("p->balance:%d\n", p->balance);
printf("r->balance:%d\n", r->balance);
printf("t->balance:%d\n", t->balance);
fake((do_check_avl(), "LR-Rotation completed."));
#endif
}
break;
} else { /* p->balance == +1 */
p->balance = 0;
fake("growth of left side balanced the node");
break;
}
} else { /* r == p->right */
balance_t b;
if (!(b = p->balance)) {
fake("growth propagation from right side");
p->balance++;
} else if (b > 0) {
if (r->balance > 0) {
/* L-Rotation */
fake("L-Rotation");
if (p->right = s = r->left) {
s->parent = p;
}
r->left = p;
p->balance = 0;
r->balance = 0;
s = p->parent;
p->parent = r;
if (r->parent = s) {
if (s->left == p) {
s->left = r;
} else {
s->right = r;
}
} else {
free_tree = r;
}
} else { /* r->balance == -1 */
/* RL-Rotation */
balance_t b2;
free_block_t *t = r->left;
#ifdef DEBUG_AVL
fake("RL-Rotation");
printf("t = %x\n", t);
printf("r->balance:%d\n", r->balance);
#endif
if (p->right = s = t->left) {
s->parent = p;
}
fake("relocated left subtree");
t->left = p;
if (r->left = s = t->right) {
s->parent = r;
}
fake("relocated right subtree");
t->right = r;
b = t->balance;
#ifdef NO_BARREL_SHIFT
b = -b;
b2 = b >> 1;
p->balance = b2;
b -= b2;
r->balance = b;
#else
b2 = (unsigned char) b >> 7;
r->balance = b2;
b2 = -b2 - b;
p->balance = b2;
#endif
t->balance = 0;
s = p->parent;
p->parent = t;
r->parent = t;
if (t->parent = s) {
if (s->left == p) {
s->left = t;
} else {
s->right = t;
}
} else {
free_tree = t;
}
fake("RL-Rotation completed.");
}
break;
} else { /* p->balance == -1 */
#ifdef DEBUG_AVL
printf("p->balance: %d\n", p->balance);
printf("p->right-h: %d\n", check_avl(p, p->right));
printf("p->left -h: %d\n", check_avl(p, p->left));
#endif
p->balance = 0;
fake("growth of right side balanced the node");
break;
}
}
r = p;
p = p->parent;
} while (q = p);
fake((do_check_avl(), "add_to_free_list successful"));
}
#else /* FIT_STYLE_FAST_FIT */
void show_free_list()
{
u *p;
p = free_list;
while (p) {
show_block(p);
p = l_next_ptr(p);
}
printf("\n");
}
t_stat large_free_stat;
void remove_from_free_list (u * ptr)
{
count_back(large_free_stat, (*ptr & MASK) << 2);
if (l_prev_ptr(ptr))
l_next_ptr(l_prev_ptr(ptr)) = l_next_ptr(ptr);
else
free_list = l_next_ptr(ptr);
if (l_next_ptr(ptr))
l_prev_ptr(l_next_ptr(ptr)) = l_prev_ptr(ptr);
}
void add_to_free_list (u * ptr)
{
extern int puts();
count_up(large_free_stat, (*ptr & MASK) << 2);
#ifdef DEBUG
if (free_list && l_prev_ptr(free_list))
puts("Free list consistency error.");
#endif
l_next_ptr(ptr) = free_list;
if (free_list)
l_prev_ptr(free_list) = ptr;
l_prev_ptr(ptr) = 0;
free_list = ptr;
}
#endif /* FIT_STYLE_FAST_FIT */
static void build_block ( /* build a properly annotated unalloc block */
u * ptr, u size)
{
u tmp;
tmp = (*ptr & PREV_BLOCK) | size;
*(ptr + size - 1) = size;
*(ptr) = tmp; /* mark this block as free */
*(ptr + size) &= ~PREV_BLOCK; /* unmark previous block */
}
static void mark_block ( /* mark this block as allocated */
u * ptr)
{
*l_next_block(ptr) |= PREV_BLOCK;
*ptr |= THIS_BLOCK;
}
/*
* It is system dependent how sbrk() aligns data, so we simpy use brk()
* to insure that we have enough.
*/
t_stat sbrk_stat;
static char *esbrk (u size)
{
#ifdef SBRK_OK
#ifdef NeXT
void *addr = NULL;
static void *current_break = NULL;
static int anywhere = FALSE;
kern_return_t ret;
/*
* try to extend current break
*/
addr = current_break;
ret = vm_allocate(task_self(), (vm_address_t *) & addr, size, anywhere);
if (ret != KERN_SUCCESS && (anywhere == FALSE)) {
/*
* allocate anywhere
*/
anywhere = TRUE;
ret = vm_allocate(task_self(), (vm_address_t *) & addr, size, TRUE);
if (ret != KERN_SUCCESS)
return (NULL);
}
count_up(sbrk_stat, size);
current_break = (void *) ((char *) addr + size);
return (addr);
#else
#ifndef linux
extern char *sbrkx();
#endif /* linux */
static char *current_break = 0;
if (current_break == 0)
current_break = (char *)sbrkx(0);
if (brk(current_break + size) == -1)
return 0;
count_up(sbrk_stat, size);
current_break += size;
return current_break - size;
#endif /* NeXT */
#else /* not SBRK_OK */
count_up(sbrk_stat, size);
return (char *)malloc(size);
#endif /* SBRK_OK */
}
t_stat large_alloc_stat;
static char *large_malloc (u size, int force_more)
{
u real_size;
u *ptr;
fake("large_malloc called");
#ifdef LARGE_TRACE
printf("request:%d.", size);
#endif
size = (size + 7) >> 2; /* plus overhead */
count_up(large_alloc_stat, size << 2);
retry:
ptr = 0;
if (!force_more) {
#ifdef FIT_STYLE_FAST_FIT
free_block_t *p, *q, *r;
u minsplit;
u tempsize;
ptr++;
minsplit = size + SMALL_BLOCK_MAX + 1;
q = free_tree;
for (;;) {
p = q;
#ifdef DEBUG_AVL
printf("checked node size %d\n", p->size);
#endif
tempsize = p->size;
if (minsplit < tempsize) {
ptr = (u *) p; /* remember this fit */
if (q = p->left) {
continue;
}
/* We don't need that much, but that's the best fit we have */
break;
} else if (size > tempsize) {
if (q = p->right) {
continue;
}
break;
} else { /* size <= tempsize <= minsplit */
if (size == tempsize) {
ptr = (u *) p;
break;
}
/* size < tempsize */
if (q = p->left) {
r = p;
/*
* if r is used in the following loop instead of p, gcc
* will handle q very inefficient throughout the function
* large_malloc()
*/
for (;;) {
p = q;
tempsize = p->size;
if (size < tempsize) {
if (q = p->left) {
continue;
}
break;
} else if (size > tempsize) {
if (q = p->right) {
continue;
}
break;
} else {
ptr = (u *) p;
goto found_fit;
}
}
p = r;
}
tempsize = p->size;
if (minsplit > tempsize) {
if (q = p->right) {
for (;;) {
p = q;
tempsize = p->size;
if (minsplit <= tempsize) {
ptr = (u *) p; /* remember this fit */
if (q = p->left) {
continue;
}
break;
} else { /* minsplit > tempsize */
if (q = p->right) {
continue;
}
break;
}
} /* end inner for */
break;
}
break; /* no new fit */
}
/* minsplit == tempsize ==> best non-exact fit */
ptr = (u *) p;
break;
}
} /* end outer for */
found_fit:
ptr--;
#else /* FIT_STYLE */
u best_size;
u *first, *best;
#ifdef LARGE_TRACE
u search_length = 0;
#endif
first = best = 0;
best_size = MASK;
ptr = free_list;
while (ptr) {
u tempsize;
#ifdef LARGE_TRACE
search_length++;
#endif
/* Perfect fit? */
tempsize = *ptr & MASK;
if (tempsize == size) {
best = first = ptr;
break;
/* always accept perfect fit */
}
/* does it really even fit at all */
if (tempsize >= size + SMALL_BLOCK_MAX + 1) {
/* try first fit */
if (!first) {
first = ptr;
if (fit_style == FIRST_FIT)
break;
/* just use this one! */
}
/* try best fit */
tempsize -= size;
if (tempsize > 0 && tempsize <= best_size) {
best = ptr;
best_size = tempsize;
}
}
ptr = l_next_ptr(ptr);
} /* end while */
#ifdef LARGE_TRACE
printf("search length %d\n", search_length);
#endif
if (fit_style == BEST_FIT)
ptr = best;
else
ptr = first;
/* FIRST_FIT and HYBRID both leave it in first */
#endif /* FIT_STYLE */
} /* end of if (!force_more) */
if (!ptr) { /* no match, allocate more memory */
u chunk_size, block_size;
block_size = size * SIZEOF_INT;
if (force_more || (block_size > CHUNK_SIZE))
chunk_size = block_size;
else
chunk_size = CHUNK_SIZE;
#ifdef SBRK_OK
if (!start_next_block) {
count_up(large_alloc_stat, SIZEOF_INT);
start_next_block = (u *) esbrk(SIZEOF_INT);
if (!start_next_block)
fatal("Couldn't malloc anything");
*(start_next_block) = PREV_BLOCK;
fake("Allocated little fake block");
}
ptr = (u *) esbrk(chunk_size);
#else /* not SBRK_OK */
ptr = (u *) esbrk(chunk_size + SIZEOF_INT);
#endif /* SBRK_OK */
if (ptr == 0) {
extern char *reserved_area;
extern int slow_shut_down_to_do;
static int going_to_exit = 0;
static char mess1[] = "Temporary out of MEMORY. Freeing reserve.\n";
static char mess2[] = "Totally out of MEMORY.\n";
if (going_to_exit)
exit(3);
if (reserved_area) {
smalloc_free(reserved_area);
reserved_area = 0;
write(1, mess1, sizeof(mess1) - 1);
slow_shut_down_to_do = 6;
force_more = 0;
goto retry;
}
if (force_more) {
force_more = 0;
goto retry;
}
going_to_exit = 1;
write(1, mess2, sizeof(mess2) - 1);
(void) dump_trace(0);
exit(2);
}
#ifdef SBRK_OK
ptr -= 1; /* overlap old memory block */
#else /* not SBRK_OK */
if (start_next_block == ptr) {
ptr -= 1; /* overlap old memory block */
chunk_size += SIZEOF_INT;
} else
*ptr = PREV_BLOCK;
start_next_block = (u *) ((char *) ptr + chunk_size);
#endif /* SBRK_OK */
block_size = chunk_size / SIZEOF_INT;
/* configure header info on chunk */
build_block(ptr, block_size);
if (force_more)
fake("Build little block");
else
fake("Built memory block description.");
*l_next_block(ptr) = THIS_BLOCK;
add_to_free_list(ptr);
} /* end of creating a new chunk */
remove_from_free_list(ptr);
real_size = *ptr & MASK;
if (real_size - size) {
/* split block pointed to by ptr into two blocks */
build_block(ptr + size, real_size - size);
fake("Built empty block");
/*
* When we allocate a new chunk, it might differ very slightly in
* size from the desired size.
*/
if (real_size - size >= SMALL_BLOCK_MAX + 1) {
add_to_free_list(ptr + size);
} else {
mark_block(ptr + size);
}
build_block(ptr, size);
}
mark_block(ptr);
fake("built allocated block");
return (char *) (ptr + 1);
}
static void large_free (char * ptr)
{
u size, *p;
p = (u *) ptr;
p -= 1;
size = *p & MASK;
count_back(large_alloc_stat, (size << 2));
if (!(*(p + size) & THIS_BLOCK)) {
remove_from_free_list(p + size);
size += (*(p + size) & MASK);
*p = (*p & PREV_BLOCK) | size;
}
if (l_prev_free(p)) {
remove_from_free_list(l_prev_block(p));
size += (*l_prev_block(p) & MASK);
p = l_prev_block(p);
}
build_block(p, size);
add_to_free_list(p);
}
POINTER CDECL smalloc_realloc (POINTER p, size_t size)
{
unsigned *q, old_size;
char *t;
q = (unsigned *) p;
#if MALLOC_ALIGN > 4
while (!(old_size = *--q));
old_size = ((old_size & MASK) - 1) * SIZEOF_INT;
#else
--q;
old_size = ((*q & MASK) - 1) * SIZEOF_INT;
#endif
if (old_size >= size)
return p;
t = smalloc_malloc(size);
if (t == 0)
return (char *) 0;
memcpy(t, p, old_size);
smalloc_free(p);
return t;
}
static int resort_free_list()
{
return 0;
}
#ifdef DO_MSTATS
#define dump_stat(str,stat) outbuf_addv(ob, str,stat.counter,stat.size)
void show_mstats (outbuffer_t * ob, char * s)
{
outbuf_addv(ob, "Memory allocation statistics %s\n", s);
outbuf_add(ob, "Type Count Space (bytes)\n");
dump_stat("sbrk requests: %8d %10d (a)\n", sbrk_stat);
dump_stat("large blocks: %8d %10d (b)\n", large_alloc_stat);
dump_stat("large free blocks: %8d %10d (c)\n\n", large_free_stat);
dump_stat("small chunks: %8d %10d (d)\n", small_chunk_stat);
dump_stat("small blocks: %8d %10d (e)\n", small_alloc_stat);
dump_stat("small free blocks: %8d %10d (f)\n", small_free_stat);
outbuf_addv(ob,
"unused from current chunk %10d (g)\n\n", unused_size);
outbuf_addv(ob,
" Small blocks are stored in small chunks, which are allocated as\n");
outbuf_addv(ob,
"large blocks. Therefore, the total large blocks allocated (b) plus\n");
outbuf_addv(ob,
"the large free blocks (c) should equal total storage from sbrk (a).\n");
outbuf_addv(ob,
"Similarly, (e) + (f) + (g) equals (d). The total amount of storage\n");
outbuf_addv(ob,
"wasted is (c) + (f) + (g); the amount allocated is (b) - (f) - (g).\n");
}
#endif
/*
* calloc() is provided because some stdio packages uses it.
*/
POINTER CDECL smalloc_calloc (size_t nelem, size_t sizel)
{
char *p;
if (nelem == 0 || sizel == 0)
return 0;
p = smalloc_malloc(nelem * sizel);
if (p == 0)
return 0;
(void) memset(p, '\0', nelem * sizel);
return p;
}
#ifdef DEBUG
/*
* Functions below can be used to debug malloc.
*/
static void walk_new_small_malloced(void (*func) (POINTER, int))
{
int i;
u *p, *q;
for (i = 0; i < SMALL_BLOCK_MAX; i++) {
for (p = sfltable[i]; p; p = *(u **) (p + 1)) {
*s_size_ptr(p) |= NO_REF;
}
}
if (unused_size)
*next_unused = 0;
for (p = last_small_chunk; p; p = *(u **) p) {
u *end = p - 1 + (p[-1] & MASK);
debug_message("scanning chunk %x, end %x\n", (u) (p - 1), (u) end);
for (q = p + 1; q < end;) {
u size = *s_size_ptr(q);
if (!size)
break;
if (!(size & NO_REF)) {
(*func) ((char *) s_next_ptr(q), (size & MASK) << 2);
*s_size_ptr(q) |= NO_REF;
}
q += size & MASK;
}
}
for (i = 0; i < SMALL_BLOCK_MAX; i++) {
for (p = sfltable[i]; p; p = *(u **) (p + 1)) {
*s_size_ptr(p) &= ~NO_REF;
}
}
}
#endif
