#endif
-#if 0
-#define MDBG_POOL
-#endif
-
#if DBG_MEM
int dbg_move_depth;
int dbg_mem = DBG_MEM_START;
-int dbg_collects = 0;
int dbg_validate = 0;
struct ao_lisp_record {
#define AO_LISP_ROOT (sizeof (ao_lisp_root) / sizeof (ao_lisp_root[0]))
+static const void ** const ao_lisp_cache[] = {
+ (const void **) &ao_lisp_cons_free_list,
+ (const void **) &ao_lisp_stack_free_list,
+ (const void **) &ao_lisp_frame_free_list[0],
+ (const void **) &ao_lisp_frame_free_list[1],
+ (const void **) &ao_lisp_frame_free_list[2],
+ (const void **) &ao_lisp_frame_free_list[3],
+};
+
+#if AO_LISP_FRAME_FREE != 4
+#error Unexpected AO_LISP_FRAME_FREE value
+#endif
+
+#define AO_LISP_CACHE (sizeof (ao_lisp_cache) / sizeof (ao_lisp_cache[0]))
+
#define AO_LISP_BUSY_SIZE ((AO_LISP_POOL + 31) / 32)
static uint8_t ao_lisp_busy[AO_LISP_BUSY_SIZE];
};
};
-#define AO_LISP_NCHUNK 32
+#define AO_LISP_NCHUNK 64
static struct ao_lisp_chunk ao_lisp_chunk[AO_LISP_NCHUNK];
/* Offset of an address within the pool. */
static inline uint16_t pool_offset(void *addr) {
+#if DBG_MEM
if (!AO_LISP_IS_POOL(addr))
ao_lisp_abort();
+#endif
return ((uint8_t *) addr) - ao_lisp_pool;
}
* These are used in the chunk code.
*/
static inline ao_poly pool_poly(void *addr) {
+#if DBG_MEM
if (!AO_LISP_IS_POOL(addr))
ao_lisp_abort();
+#endif
return ((uint8_t *) addr) - AO_LISP_POOL_BASE;
}
static int total_marked;
-/*
- * Mark a range of addresses
- */
-static int
-mark_object(uint8_t *tag, void *addr, int size) {
- int base;
- int bound;
-
- MDBG_DO(if (!AO_LISP_IS_POOL((uint8_t *) addr + size - 1))
- ao_lisp_abort());
-
- base = pool_offset(addr);
- bound = base + size;
-
- MDBG_DO(if (bound > ao_lisp_top) ao_lisp_abort());
-
- if (busy(tag, base))
- return 1;
- if (tag == ao_lisp_busy)
- total_marked += size;
- while (base < bound) {
- mark(tag, base);
- base += 4;
- }
- return 0;
-}
-
-MDBG_DO(
-static int
-clear_object(uint8_t *tag, void *addr, int size) {
- int base;
- int bound;
-
- MDBG_DO(if (!AO_LISP_IS_POOL((uint8_t *) addr + size - 1))
- ao_lisp_abort());
-
- base = (uint8_t *) addr - ao_lisp_pool;
- bound = base + size;
-
- base = limit(base);
- bound = limit(bound);
- if (!busy(tag, base))
- return 1;
- total_marked -= size;
- while (base < bound) {
- clear(tag, base);
- base += 4;
- }
- return 0;
-})
-
static void
note_cons(void *addr)
{
if (AO_LISP_IS_POOL(addr)) {
- int offset = (uint8_t *) addr - ao_lisp_pool;
+ int offset = pool_offset(addr);
MDBG_MOVE("note cons %d\n", MDBG_OFFSET(addr));
ao_lisp_cons_noted = 1;
mark(ao_lisp_cons_note, offset);
}
}
-static uint16_t chunk_low;
+static uint16_t chunk_low, chunk_high;
static uint16_t chunk_first, chunk_last;
+static int chunk_busy;
static void
note_chunk(uint16_t addr, uint16_t size)
{
int i;
- if (addr < chunk_low)
+ if (addr < chunk_low || chunk_high < addr)
return;
- for (i = 0; i < AO_LISP_NCHUNK; i++) {
+ for (i = 0; i < chunk_busy; i++) {
if (ao_lisp_chunk[i].size && ao_lisp_chunk[i].old_addr == addr) {
+#if DBG_MEM
if (ao_lisp_chunk[i].size != size)
ao_lisp_abort();
+#endif
return;
}
if (ao_lisp_chunk[i].old_addr > addr) {
+ int end = min(AO_LISP_NCHUNK, chunk_busy + 1);
memmove(&ao_lisp_chunk[i+1],
&ao_lisp_chunk[i],
- (AO_LISP_NCHUNK - (i+1)) * sizeof (struct ao_lisp_chunk));
- ao_lisp_chunk[i].size = 0;
- }
- if (ao_lisp_chunk[i].size == 0) {
- ao_lisp_chunk[i].old_addr = addr;
- ao_lisp_chunk[i].size = size;
- return;
+ (end - (i+1)) * sizeof (struct ao_lisp_chunk));
+ break;
}
}
+ if (i < AO_LISP_NCHUNK) {
+ ao_lisp_chunk[i].old_addr = addr;
+ ao_lisp_chunk[i].size = size;
+ if (chunk_busy < AO_LISP_NCHUNK)
+ chunk_busy++;
+ else
+ chunk_high = ao_lisp_chunk[AO_LISP_NCHUNK-1].old_addr +
+ ao_lisp_chunk[AO_LISP_NCHUNK-1].size;
+ }
+}
+
+static void
+reset_chunks(void)
+{
+ memset(ao_lisp_chunk, '\0', sizeof (ao_lisp_chunk));
+ chunk_high = ao_lisp_top;
+ chunk_busy = 0;
}
/*
memset(ao_lisp_busy, '\0', sizeof (ao_lisp_busy));
memset(ao_lisp_cons_note, '\0', sizeof (ao_lisp_cons_note));
ao_lisp_cons_noted = 0;
- for (i = 0; i < AO_LISP_ROOT; i++) {
+ for (i = 0; i < (int) AO_LISP_ROOT; i++) {
if (ao_lisp_root[i].type) {
void **a = ao_lisp_root[i].addr, *v;
if (a && (v = *a)) {
return ao_lisp_poly_mark(*p, do_note_cons);
}
-void
-ao_lisp_collect(void)
+int ao_lisp_collects[2];
+int ao_lisp_freed[2];
+int ao_lisp_loops[2];
+
+int ao_lisp_last_top;
+
+int
+ao_lisp_collect(uint8_t style)
{
+ int ret;
int i;
int top;
-#if DBG_MEM
int loops = 0;
+#if DBG_MEM
int marked;
int moved;
struct ao_lisp_record *mark_record = NULL, *move_record = NULL;
- ++dbg_collects;
- MDBG_MOVE("collect %d\n", dbg_collects);
+ MDBG_MOVE("collect %d\n", ao_lisp_collects);
marked = moved = 0;
#endif
- chunk_low = 0;
- top = 0;
+
+ /* The first time through, we're doing a full collect */
+ if (ao_lisp_last_top == 0)
+ style = AO_LISP_COLLECT_FULL;
+
+ /* Clear references to all caches */
+ for (i = 0; i < (int) AO_LISP_CACHE; i++)
+ *ao_lisp_cache[i] = NULL;
+ if (style == AO_LISP_COLLECT_FULL) {
+ chunk_low = top = 0;
+ } else {
+ chunk_low = top = ao_lisp_last_top;
+ }
for (;;) {
- MDBG_DO(loops++);
+ loops++;
MDBG_MOVE("move chunks from %d to %d\n", chunk_low, top);
/* Find the sizes of the first chunk of objects to move */
- memset(ao_lisp_chunk, '\0', sizeof (ao_lisp_chunk));
+ reset_chunks();
walk(ao_lisp_mark_ref, ao_lisp_poly_mark_ref);
#if DBG_MEM
marked = total_marked;
if (ao_lisp_chunk[i].old_addr > top)
break;
+#if DBG_MEM
if (ao_lisp_chunk[i].old_addr != top)
ao_lisp_abort();
+#endif
top += size;
MDBG_MOVE("chunk %d %d not moving\n",
ao_lisp_chunk[i].old_addr,
ao_lisp_chunk[i].size);
- chunk_low = ao_lisp_chunk[i].old_addr + size;
}
chunk_first = i;
memmove(&ao_lisp_pool[top],
&ao_lisp_pool[ao_lisp_chunk[i].old_addr],
size);
- MDBG_DO(clear_object(ao_lisp_busy, &ao_lisp_pool[ao_lisp_chunk[i].old_addr], size));
- MDBG_DO(mark_object(ao_lisp_busy, &ao_lisp_pool[top], size));
top += size;
- chunk_low = ao_lisp_chunk[i].old_addr + size;
}
- MDBG_MOVE("after moving objects, busy is now:\n");
- DUMP_BUSY();
chunk_last = i;
if (chunk_first < chunk_last) {
if (chunk_last != AO_LISP_NCHUNK)
break;
+
+ chunk_low = chunk_high;
}
+
+ /* Compute amount of memory freed */
+ ret = ao_lisp_top - top;
+
+ /* Collect stats */
+ ++ao_lisp_collects[style];
+ ao_lisp_freed[style] += ret;
+ ao_lisp_loops[style] += loops;
+
ao_lisp_top = top;
+ if (style == AO_LISP_COLLECT_FULL)
+ ao_lisp_last_top = top;
MDBG_DO(memset(ao_lisp_chunk, '\0', sizeof (ao_lisp_chunk));
walk(ao_lisp_mark_ref, ao_lisp_poly_mark_ref));
-// printf ("collect. top %d loops %d\n", top, loops);
+ return ret;
}
/*
int
ao_lisp_mark_memory(const struct ao_lisp_type *type, void *addr)
{
- int size;
+ int offset;
if (!AO_LISP_IS_POOL(addr))
return 1;
- size = ao_lisp_size(type, addr);
+ offset = pool_offset(addr);
MDBG_MOVE("mark memory %d\n", MDBG_OFFSET(addr));
- if (!mark_object(ao_lisp_busy, addr, size)) {
- note_chunk(pool_offset(addr), size);
- MDBG_DO(ao_lisp_record(type, addr, size));
- return 0;
+ if (busy(ao_lisp_busy, offset)) {
+ MDBG_MOVE("already marked\n");
+ return 1;
}
- MDBG_MOVE("already marked\n");
- return 1;
+ mark(ao_lisp_busy, offset);
+ note_chunk(offset, ao_lisp_size(type, addr));
+ return 0;
}
int
if (type == AO_LISP_OTHER) {
type = ao_lisp_other_type(ao_lisp_poly_other(p));
+#if DBG_MEM
if (type <= AO_LISP_OTHER || AO_LISP_NUM_TYPE <= type)
ao_lisp_abort();
+#endif
}
lisp_type = ao_lisp_types[ao_lisp_poly_type(p)];
ao_lisp_move_memory(const struct ao_lisp_type *type, void **ref)
{
void *addr = *ref;
- int size;
+ int offset;
if (!AO_LISP_IS_POOL(addr))
return 1;
+ (void) type;
+
MDBG_MOVE("move memory %d\n", MDBG_OFFSET(addr));
addr = move_map(addr);
- size = ao_lisp_size(type, addr);
if (addr != *ref) {
MDBG_MOVE("update ref %d %d -> %d\n",
AO_LISP_IS_POOL(ref) ? MDBG_OFFSET(ref) : -1,
MDBG_OFFSET(*ref), MDBG_OFFSET(addr));
*ref = addr;
}
- if (!mark_object(ao_lisp_busy, addr, size)) {
- MDBG_DO(ao_lisp_record(type, addr, size));
- return 0;
+ offset = pool_offset(addr);
+ if (busy(ao_lisp_busy, offset)) {
+ MDBG_MOVE("already moved\n");
+ return 1;
}
- MDBG_MOVE("already moved\n");
- return 1;
+ mark(ao_lisp_busy, offset);
+ MDBG_DO(ao_lisp_record(type, addr, ao_lisp_size(type, addr)));
+ return 0;
}
int
if (!p)
return 1;
- type = ao_lisp_poly_base_type(p);
addr = ao_lisp_ref(p);
if (!AO_LISP_IS_POOL(addr))
return 1;
- if (type == AO_LISP_CONS && do_note_cons) {
-// addr = move_map(addr);
- MDBG_DO(if (addr != move_map(addr)) MDBG_MOVE("noting cons at old addr %d instead of new addr %d\n", MDBG_OFFSET(addr), MDBG_OFFSET(move_map(addr))););
+ type = ao_lisp_poly_base_type(p);
+ if (type == AO_LISP_CONS && do_note_cons) {
note_cons(addr);
addr = move_map(addr);
ret = 1;
if (type == AO_LISP_OTHER) {
type = ao_lisp_other_type(move_map(ao_lisp_poly_other(p)));
+#if DBG_MEM
if (type <= AO_LISP_OTHER || AO_LISP_NUM_TYPE <= type)
ao_lisp_abort();
+#endif
}
lisp_type = ao_lisp_types[type];
return ret;
}
-#ifdef MDBG_POOL
-static int AO_LISP_POOL_CUR = AO_LISP_POOL / 8;
-
-static void
-ao_lisp_poison(void)
-{
- int i;
-
- printf("poison\n");
- ao_lisp_mark_busy();
- for (i = 0; i < AO_LISP_POOL_CUR; i += 4) {
- uint32_t *a = (uint32_t *) &ao_lisp_pool[i];
- if (!busy_object(ao_lisp_busy, a))
- *a = 0xBEEFBEEF;
- }
- for (i = 0; i < AO_LISP_POOL_CUR; i += 2) {
- ao_poly *a = (uint16_t *) &ao_lisp_pool[i];
- ao_poly p = *a;
-
- if (!ao_lisp_is_const(p)) {
- void *r = ao_lisp_ref(p);
-
- if (ao_lisp_pool <= (uint8_t *) r &&
- (uint8_t *) r <= ao_lisp_pool + AO_LISP_POOL_CUR)
- {
- if (!busy_object(ao_lisp_busy, r)) {
- printf("missing reference from %d to %d\n",
- (int) ((uint8_t *) a - ao_lisp_pool),
- (int) ((uint8_t *) r - ao_lisp_pool));
- }
- }
- }
- }
-}
-
-#else
-#define AO_LISP_POOL_CUR AO_LISP_POOL
-#endif
-
#if DBG_MEM
void
ao_lisp_validate(void)
#endif
-
void *
ao_lisp_alloc(int size)
{
MDBG_DO(++dbg_allocs);
MDBG_DO(if (dbg_validate) ao_lisp_validate());
size = ao_lisp_size_round(size);
- if (ao_lisp_top + size > AO_LISP_POOL_CUR) {
-#ifdef MDBG_POOL
- if (AO_LISP_POOL_CUR < AO_LISP_POOL) {
- AO_LISP_POOL_CUR += AO_LISP_POOL / 8;
- ao_lisp_poison();
- } else
-#endif
- ao_lisp_collect();
-#ifdef MDBG_POOL
+ if (ao_lisp_top + size > AO_LISP_POOL) {
+ if (!ao_lisp_collect(AO_LISP_COLLECT_INCREMENTAL) &&
+ !ao_lisp_collect(AO_LISP_COLLECT_FULL))
{
- int i;
-
- for (i = ao_lisp_top; i < AO_LISP_POOL; i += 4) {
- uint32_t *p = (uint32_t *) &ao_lisp_pool[i];
- *p = 0xbeefbeef;
- }
- }
-#endif
-
- if (ao_lisp_top + size > AO_LISP_POOL) {
ao_lisp_error(AO_LISP_OOM, "out of memory");
return NULL;
}
void
ao_lisp_cons_stash(int id, struct ao_lisp_cons *cons)
{
- if (save_cons[id] != NULL)
- ao_lisp_abort();
save_cons[id] = cons;
}
void
ao_lisp_string_stash(int id, char *string)
{
- if (save_cons[id] != NULL)
- ao_lisp_abort();
save_string[id] = string;
}
projects / fw / altos / blobdiff