/* -----------------------------------------------------------------------------
- * $Id: BlockAlloc.c,v 1.3 1999/01/13 17:25:37 simonm Exp $
*
+ * (c) The GHC Team 1998-2006
+ *
* The block allocator and free list manager.
*
* This is the architecture independent part of the block allocator.
*
* ---------------------------------------------------------------------------*/
+#include "PosixSource.h"
#include "Rts.h"
#include "RtsFlags.h"
#include "RtsUtils.h"
#include "BlockAlloc.h"
#include "MBlock.h"
+#include "Storage.h"
+
+#include <string.h>
static void initMBlock(void *mblock);
static bdescr *allocMegaGroup(nat mblocks);
static void freeMegaGroup(bdescr *bd);
-static bdescr *free_list;
+// In THREADED_RTS mode, the free list is protected by sm_mutex.
+static bdescr *free_list = NULL;
/* -----------------------------------------------------------------------------
Initialisation
void initBlockAllocator(void)
{
- free_list = NULL;
+ // The free list starts off NULL
}
/* -----------------------------------------------------------------------------
Allocation
-------------------------------------------------------------------------- */
-static inline void
+STATIC_INLINE void
initGroup(nat n, bdescr *head)
{
bdescr *bd;
if (n != 0) {
head->blocks = n;
- head->free = head->start;
+ head->free = head->start;
+ head->link = NULL;
for (i=1, bd = head+1; i < n; i++, bd++) {
bd->free = 0;
+ bd->blocks = 0;
bd->link = head;
}
}
void *mblock;
bdescr *bd, **last;
+ ASSERT_SM_LOCK();
+ ASSERT(n != 0);
+
if (n > BLOCKS_PER_MBLOCK) {
return allocMegaGroup(BLOCKS_TO_MBLOCKS(n));
}
*last = bd->link;
/* no initialisation necessary - this is already a
* self-contained block group. */
+ bd->free = bd->start; /* block isn't free now */
+ bd->link = NULL;
return bd;
}
if (bd->blocks > n) { /* block too big... */
initMBlock(mblock); /* initialise the start fields */
bd = FIRST_BDESCR(mblock);
initGroup(n,bd); /* we know the group will fit */
- initGroup(BLOCKS_PER_MBLOCK-n, bd+n);
- freeGroup(bd+n); /* add the rest on to the free list */
+ if (n < BLOCKS_PER_MBLOCK) {
+ initGroup(BLOCKS_PER_MBLOCK-n, bd+n);
+ freeGroup(bd+n); /* add the rest on to the free list */
+ }
return bd;
}
bdescr *
+allocGroup_lock(nat n)
+{
+ bdescr *bd;
+ ACQUIRE_SM_LOCK;
+ bd = allocGroup(n);
+ RELEASE_SM_LOCK;
+ return bd;
+}
+
+bdescr *
allocBlock(void)
{
return allocGroup(1);
}
+bdescr *
+allocBlock_lock(void)
+{
+ bdescr *bd;
+ ACQUIRE_SM_LOCK;
+ bd = allocBlock();
+ RELEASE_SM_LOCK;
+ return bd;
+}
+
/* -----------------------------------------------------------------------------
Any request larger than BLOCKS_PER_MBLOCK needs a megablock group.
First, search the free list for enough contiguous megablocks to
if (bd->blocks == BLOCKS_PER_MBLOCK) { /* whole megablock found */
- if (grp_start == NULL) { /* is it the first one we've found? */
+ /* is it the first one we've found or a non-contiguous megablock? */
+ if (grp_start == NULL ||
+ bd->start != last->start + MBLOCK_SIZE/sizeof(W_)) {
grp_start = bd;
grp_prev = last;
mbs_found = 1;
* pointer to the newly enlarged group p.
*/
-static inline bdescr *
+STATIC_INLINE bdescr *
coalesce(bdescr *p)
{
bdescr *bd, *q;
- nat i;
+ nat i, blocks;
q = p->link;
if (q != NULL && p->start + p->blocks * BLOCK_SIZE_W == q->start) {
/* can coalesce */
p->blocks += q->blocks;
p->link = q->link;
- for (i = 0, bd = q; i < q->blocks; bd++, i++) {
+ blocks = q->blocks;
+ for (i = 0, bd = q; i < blocks; bd++, i++) {
bd->free = 0;
+ bd->blocks = 0;
bd->link = p;
}
return p;
{
bdescr *bd, *last;
+ ASSERT_SM_LOCK();
+
/* are we dealing with a megablock group? */
if (p->blocks > BLOCKS_PER_MBLOCK) {
freeMegaGroup(p);
return;
}
-#ifdef DEBUG
+
p->free = (void *)-1; /* indicates that this block is free */
p->step = NULL;
- p->gen = NULL;
+ p->gen_no = 0;
/* fill the block group with garbage if sanity checking is on */
IF_DEBUG(sanity,memset(p->start, 0xaa, p->blocks * BLOCK_SIZE));
-#endif
/* find correct place in free list to place new group */
last = NULL;
IF_DEBUG(sanity, checkFreeListSanity());
}
+void
+freeGroup_lock(bdescr *p)
+{
+ ACQUIRE_SM_LOCK;
+ freeGroup(p);
+ RELEASE_SM_LOCK;
+}
+
static void
freeMegaGroup(bdescr *p)
{
nat n;
+ void *q = p;
- n = p->blocks * BLOCK_SIZE / MBLOCK_SIZE + 1;
- for (; n > 0; (W_)p += MBLOCK_SIZE, n--) {
- initMBlock((void *)((W_)p & ~MBLOCK_MASK));
- initGroup(BLOCKS_PER_MBLOCK, p);
- freeGroup(p);
+ n = ((bdescr *)q)->blocks * BLOCK_SIZE / MBLOCK_SIZE + 1;
+ for (; n > 0; q += MBLOCK_SIZE, n--) {
+ initMBlock(MBLOCK_ROUND_DOWN(q));
+ initGroup(BLOCKS_PER_MBLOCK, (bdescr *)q);
+ freeGroup((bdescr *)q);
}
}
}
}
+void
+freeChain_lock(bdescr *bd)
+{
+ ACQUIRE_SM_LOCK;
+ freeChain(bd);
+ RELEASE_SM_LOCK;
+}
+
static void
initMBlock(void *mblock)
{
/* Initialise the start field of each block descriptor
*/
- for (; block <= LAST_BLOCK(mblock); bd += 1, (lnat)block += BLOCK_SIZE) {
+ for (; block <= LAST_BLOCK(mblock); bd += 1, block += BLOCK_SIZE) {
bd->start = block;
}
}
-------------------------------------------------------------------------- */
#ifdef DEBUG
+static void
+checkWellFormedGroup( bdescr *bd )
+{
+ nat i;
+
+ for (i = 1; i < bd->blocks; i++) {
+ ASSERT(bd[i].blocks == 0);
+ ASSERT(bd[i].free == 0);
+ ASSERT(bd[i].link == bd);
+ }
+}
+
void
checkFreeListSanity(void)
{
for (bd = free_list; bd != NULL; bd = bd->link) {
IF_DEBUG(block_alloc,
- fprintf(stderr,"group at 0x%x, length %d blocks\n",
- (nat)bd->start, bd->blocks));
+ debugBelch("group at 0x%p, length %d blocks\n",
+ bd->start, bd->blocks));
ASSERT(bd->blocks > 0);
+ checkWellFormedGroup(bd);
if (bd->link != NULL) {
/* make sure we're fully coalesced */
ASSERT(bd->start + bd->blocks * BLOCK_SIZE_W != bd->link->start);