/* Copyright (C) 1999 DJ Delorie, see COPYING.DJ for details */
/* Copyright (C) 1998 DJ Delorie, see COPYING.DJ for details */
/* Copyright (C) 1997 DJ Delorie, see COPYING.DJ for details */
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
typedef struct BLOCK {
size_t size;
struct BLOCK *next;
int bucket;
} BLOCK;
#define BEFORE(bp) ((BLOCK *)((char *)bp - *(int *)((char *)bp - 4) - 8))
#define BEFSZ(bp) (*(size_t *)((char *)bp - 4))
#define ENDSZ(bp) (*(size_t *)((char *)bp + bp->size + 4))
#define AFTER(bp) ((BLOCK *)((char *)bp + bp->size + 8))
#define DATA(bp) ((char *)&(bp->next))
#define NUMSMALL 0
#define ALIGN 8
#define SMALL (NUMSMALL*ALIGN)
static int malloc_mutex = 0;
static BLOCK *slop = 0;
static BLOCK *freelist[30];
#if NUMSMALL
static BLOCK *smallblocks[NUMSMALL];
#endif
static inline void malloc_lock(void)
{
while (__sync_lock_test_and_set(&malloc_mutex, 1))
__menuet__delay100(1);
}
static inline void malloc_unlock(void)
{
__sync_lock_release(&malloc_mutex);
}
#define MIN_SAVE_EXTRA 64
#define BIG_BLOCK 4096
#define DEBUG 0
#if DEBUG
static void
check(BLOCK *b)
{
printf("check %08x %d %08x %d\n", b
, b
->size
, &(ENDSZ
(b
)), ENDSZ
(b
));
}
#define CHECK(p) do { check(p); assert(p->size == ENDSZ(p)); consistency(); } while (0)
#define CHECK1(p) do { check(p); assert(p->size == ENDSZ(p)); } while (0)
static void
consistency()
{
#if 0
int b;
BLOCK *bl;
if (slop)
CHECK1(slop);
for (b=0; b<32; b++)
for (bl=freelist[b]; bl; bl=bl->next)
CHECK1(bl);
#endif
}
#else
#define CHECK(p)
#endif
static inline int
size2bucket(size_t size)
{
int rv=0;
size>>=2;
while (size)
{
rv++;
size>>=1;
}
return rv;
}
static inline int
b2bucket(BLOCK *b)
{
if (b->bucket == -1)
b->bucket = size2bucket(b->size);
return b->bucket;
}
static inline BLOCK *
split_block(BLOCK *b, size_t size)
{
BLOCK *rv = (BLOCK *)((char *)b + size+8);
#if DEBUG
printf(" split %u/%08x to %u/%08x, %u/%08x\n",
b->size, b, size, b, b->size - size - 8, rv);
#endif
rv->size = b->size - size - 8;
rv->bucket = -1;
b->size = size;
ENDSZ(b) = b->size;
ENDSZ(rv) = rv->size;
CHECK(b);
CHECK(rv);
return rv;
}
#define RET(rv) CHECK(rv); ENDSZ(rv) |= 1; rv->size |= 1; malloc_unlock(); return DATA(rv)
{
int b, chunk_size;
BLOCK *rv, **prev;
static BLOCK *expected_sbrk = 0;
if (size<ALIGN) size = ALIGN;
size = (size+(ALIGN-1))&~(ALIGN-1);
#if DEBUG
#endif
malloc_lock();
#if NUMSMALL
if (size < SMALL)
{
rv = smallblocks[size/ALIGN];
if (rv)
{
smallblocks[size/ALIGN] = rv->next;
malloc_unlock();
return DATA(rv);
}
}
#endif
if (slop && slop->size >= size)
{
rv = slop;
#if DEBUG
printf(" using slop %u/%08x\n", slop
->size
, slop
);
#endif
if (slop->size >= size+MIN_SAVE_EXTRA)
{
slop = split_block(slop, size);
#if DEBUG
printf(" remaining slop %u/%08x\n", slop
->size
, slop
);
#endif
}
else
slop = 0;
RET(rv);
}
b = size2bucket(size);
prev = &(freelist[b]);
for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next)
{
if (rv->size >= size && rv->size < size+size/4)
{
*prev = rv->next;
RET(rv);
}
}
while (b < 30)
{
prev = &(freelist[b]);
#if DEBUG
printf(" checking bucket %d\n", b
);
#endif
for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next)
if (rv->size >= size)
{
#if DEBUG
printf(" found size %d/%08x\n", rv
->size
, rv
);
#endif
*prev = rv->next;
if (rv->size >= size+MIN_SAVE_EXTRA)
{
#if DEBUG
#endif
if (slop)
{
b = b2bucket(slop);
#if DEBUG
printf(" putting old slop %u/%08x on free list %d\n",
slop->size, slop, b);
#endif
slop->next = freelist[b];
freelist[b] = slop;
}
slop = split_block(rv, size);
#if DEBUG
printf(" slop size %u/%08x\n", slop
->size
, slop
);
#endif
}
RET(rv);
}
b++;
}
chunk_size = size+16; /* two ends plus two placeholders */
rv = (BLOCK *)sbrk(chunk_size);
if (rv == (BLOCK *)(-1)) {
malloc_unlock();
return 0;
}
#if DEBUG
printf("sbrk(%d) -> %08x, expected %08x\n", chunk_size
, rv
, expected_sbrk
);
#endif
if (rv == expected_sbrk)
{
expected_sbrk = (BLOCK *)((char *)rv + chunk_size);
/* absorb old end-block-marker */
#if DEBUG
printf(" got expected sbrk\n");
#endif
rv = (BLOCK *)((char *)rv - 4);
}
else
{
expected_sbrk = (BLOCK *)((char *)rv + chunk_size);
#if DEBUG
printf(" disconnected sbrk\n");
#endif
/* build start-block-marker */
rv->size = 1;
rv = (BLOCK *)((char *)rv + 4);
chunk_size -= 8;
}
rv->size = chunk_size - 8;
ENDSZ(rv) = rv->size;
AFTER(rv)->size = 1;
CHECK(rv);
RET(rv);
}
static inline BLOCK *
merge(BLOCK *a, BLOCK *b, BLOCK *c)
{
int bu;
BLOCK *bp, **bpp;
#if DEBUG
printf(" merge %u/%08x + %u/%08x = %u\n",
a->size, a, b->size, b, a->size+b->size+8);
#endif
CHECK(a);
CHECK(b);
CHECK(c);
if (c == slop)
{
#if DEBUG
printf(" snipping slop %u/%08x\n", slop
->size
, slop
);
#endif
slop = 0;
}
bu = b2bucket(c);
#if DEBUG
printf("bucket for %u/%08x is %d\n", c
->size
, c
, bu
);
#endif
bpp = freelist+bu;
for (bp=freelist[bu]; bp; bpp=&(bp->next), bp=bp->next)
{
#if DEBUG
#endif
if (bp == c)
{
#if DEBUG
printf("\n snipping %u/%08x from freelist[%d]\n", bp
->size
, bp
, bu
);
#endif
*bpp = bp->next;
break;
}
}
CHECK(c);
a->size += b->size + 8;
a->bucket = -1;
ENDSZ(a) = a->size;
CHECK(a);
return a;
}
void
{
int b;
BLOCK *block;
if (ptr == 0)
return;
block = (BLOCK *)((char *)ptr-4);
malloc_lock();
#if NUMSMALL
if (block->size < SMALL)
{
block->next = smallblocks[block->size/ALIGN];
smallblocks[block->size/ALIGN] = block;
malloc_unlock();
return;
}
#endif
block->size &= ~1;
ENDSZ(block) &= ~1;
block->bucket = -1;
#if DEBUG
printf("free(%u/%08x)\n", block
->size
, block
);
#endif
CHECK(block);
if (! (AFTER(block)->size & 1))
{
CHECK(AFTER(block));
}
if (! (BEFSZ(block) & 1))
{
CHECK(BEFORE(block));
block = merge(BEFORE(block), block, BEFORE(block));
}
CHECK(block);
if (! (AFTER(block)->size & 1))
{
CHECK(AFTER(block));
block = merge(block, AFTER(block), AFTER(block));
}
CHECK(block);
b = b2bucket(block);
block->next = freelist[b];
freelist[b] = block;
CHECK(block);
malloc_unlock();
}
void * realloc(void *ptr
, size_t size
)
{
BLOCK *b;
char *newptr;
size_t copysize;
if (ptr
== 0) return malloc(size
);
b = (BLOCK *)((char *)ptr-4);
copysize = b->size & ~1;
if (size <= copysize)
{
return ptr;
copysize = size;
}
newptr
= (char *)malloc(size
);
if (!newptr) return NULL;
memcpy(newptr
, ptr
, copysize
);
return newptr;
}