[Commit]
nickle ChangeLog, 1.78, 1.79 Makefile.am, 1.58, 1.59 avl.c,
1.4, NONE avl.h, 1.5, NONE mem.c, 1.18, 1.19 mem.h, 1.13,
1.14 memp.h, 1.5, 1.6
Keith Packard
commit at keithp.com
Tue Aug 10 00:39:58 PDT 2004
- Previous message: [Commit] nickle/debian changelog,1.18,1.19
- Next message: [Commit]
nickle ChangeLog, 1.79, 1.80 mem.c, 1.19, 1.20 mem.h, 1.14,
1.15 memp.h, 1.6, 1.7
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Committed by: keithp
Update of /local/src/CVS/nickle
In directory home.keithp.com:/tmp/cvs-serv23407
Modified Files:
ChangeLog Makefile.am mem.c mem.h memp.h
Removed Files:
avl.c avl.h
Log Message:
2004-08-10 Keith Packard <keithp at keithp.com>
version 2.43
* Makefile.am:
* avl.c:
* avl.h:
Remove avl tree code
* mem.c: (MemHunkMore), (MemAllocateHuge), (tossFree), (busy),
(checkBlockRef), (checkRef), (MemReference),
(MemReferenceNoRecurse), (MemCollect):
* mem.h:
* memp.h:
Rewrite garbage collector to place reference bits right in
each object by stealing the low bit of the type pointer.
Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/nickle/ChangeLog,v
retrieving revision 1.78
retrieving revision 1.79
diff -u -d -r1.78 -r1.79
--- ChangeLog 4 Aug 2004 18:38:53 -0000 1.78
+++ ChangeLog 10 Aug 2004 07:39:55 -0000 1.79
@@ -1,3 +1,19 @@
+2004-08-10 Keith Packard <keithp at keithp.com>
+version 2.43
+
+ * Makefile.am:
+ * avl.c:
+ * avl.h:
+ Remove avl tree code
+
+ * mem.c: (MemHunkMore), (MemAllocateHuge), (tossFree), (busy),
+ (checkBlockRef), (checkRef), (MemReference),
+ (MemReferenceNoRecurse), (MemCollect):
+ * mem.h:
+ * memp.h:
+ Rewrite garbage collector to place reference bits right in
+ each object by stealing the low bit of the type pointer.
+
2004-08-04 Keith Packard <keithp at keithp.com>
* debian/changelog:
Index: Makefile.am
===================================================================
RCS file: /local/src/CVS/nickle/Makefile.am,v
retrieving revision 1.58
retrieving revision 1.59
diff -u -d -r1.58 -r1.59
--- Makefile.am 23 Jun 2004 09:00:45 -0000 1.58
+++ Makefile.am 10 Aug 2004 07:39:55 -0000 1.59
@@ -23,12 +23,12 @@
bin_PROGRAMS = nickle
nickle_SOURCES = \
- alarm.c array.c atom.c avl.c box.c compile.c debug.c \
+ alarm.c array.c atom.c box.c compile.c debug.c \
divide.c edit.c error.c execute.c expr.c file.c float.c \
frame.c func.c gcd.c hash.c int.c integer.c io.c main.c \
mem.c natural.c pretty.c profile.c rational.c ref.c \
refer.c sched.c scope.c stack.c string.c struct.c \
- symbol.c sync.c type.c union.c util.c value.c avl.h \
+ symbol.c sync.c type.c union.c util.c value.c \
mem.h memp.h nickle.h opcode.h ref.h stack.h value.h \
builtin-command.c builtin-debug.c builtin-environ.c \
builtin-file.c builtin-math.c builtin-namespaces.h \
--- avl.c DELETED ---
--- avl.h DELETED ---
Index: mem.c
===================================================================
RCS file: /local/src/CVS/nickle/mem.c,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -d -r1.18 -r1.19
--- mem.c 9 Jul 2004 18:48:35 -0000 1.18
+++ mem.c 10 Aug 2004 07:39:55 -0000 1.19
@@ -28,13 +28,6 @@
* allocBlock() - calls malloc
* disposeBlock() - calls free
*
- * noteBlock(b) - permits address->block translation for these objects
- * unNoteBlock(b) - removes block from data structure
- * addrToBlock(a,bp,ip) - translates address (a) to block (*bp) and index (*ip)
- * blockWalk(f) - calls f with each active block
- *
- * clearRef() - clears all ref bits in the system
- * clearBlockRef(b) - clears all ref bits in a particular block
* tossFree() - erases the free lists
* checkRef() - puts unreferenced hunks on free lists
* checkBlockRef(b) - puts unreferenced hunks in a block on free lists
@@ -55,16 +48,12 @@
#define PtrToInt(p) ((int) (p))
#endif
-static void noteBlock (struct block *);
-static void checkBlockRef (struct block *);
-#ifdef DEBUG
-static void verifyBlock (void);
-#endif
-
int GarbageTime;
void *TemporaryData;
+#undef DEBUG
+
#ifdef DEBUG
int GCdebug;
#endif
@@ -78,9 +67,9 @@
static void **Roots;
static int RootCount;
-struct bfree *lastFree[NUMSIZES];
+struct bfree *lastFree[NUMSIZES];
-struct block *hughFree;
+static struct block *head;
int totalBytesFree;
int totalBytesUsed;
@@ -115,10 +104,8 @@
MemHunkMore (int sizeIndex)
{
unsigned char *new;
- unsigned char *limit;
struct block *b;
- int bsize;
- int dsize;
+ int n;
b = MemNewBlock ((unsigned) BLOCKSIZE, sizeIndex);
if (!b)
@@ -126,30 +113,25 @@
/*
* fill in per-block data fields
*/
- bsize = HUNKSIZE(sizeIndex);
b->sizeIndex = sizeIndex;
- b->bitmap = ((unsigned char *) b) + HEADSIZE;
- b->bitmapsize = BITMAPSIZE(bsize);
- b->data = (unsigned char *)
- ((((PtrInt) (b->bitmap + b->bitmapsize)) + (MINHUNK-1))
- & (~(MINHUNK-1)));
- dsize = (((unsigned char *) b) + BLOCKSIZE) - b->data;
- b->datasize = (dsize / bsize) * bsize;
- /*
- * put this block into the address converter
- */
- noteBlock (b);
+ b->next = head;
+ head = b;
+
/*
* put it's contents on the free list
*/
- limit = b->data + (b->datasize - bsize);
- for (new = b->data; new < limit; new += bsize) {
+ new = HUNKS(b);
+ n = NUMHUNK(sizeIndex) - 1;
+ while (n--)
+ {
+ unsigned char *next = new + HUNKSIZE(sizeIndex);
((struct bfree *) new)->type = 0;
- ((struct bfree *) new)->next = (struct bfree *) (new + bsize);
+ ((struct bfree *) new)->next = (struct bfree *) next;
+ new = next;
}
((struct bfree *) new)->type = 0;
((struct bfree *) new)->next = freeList[sizeIndex];
- return freeList[sizeIndex] = (struct bfree *) b->data;
+ return freeList[sizeIndex] = (struct bfree *) HUNKS(b);
}
/*
@@ -159,17 +141,18 @@
void *
MemAllocateHuge (DataType *type, int size)
{
- struct block *huge;
+ struct block *b;
+ unsigned char *data;
- huge = MemNewBlock ((unsigned) (size + HEADSIZE), -1);
- huge->sizeIndex = NUMSIZES;
- huge->bitmapsize = 0;
- huge->datasize = size;
- huge->bitmap = 0;
- huge->data = (void *) (huge + 1);
- noteBlock (huge);
- *((DataType **) huge->data) = type;
- return huge->data;
+ b = MemNewBlock ((unsigned) (size + HEADSIZE), -1);
+
+ b->sizeIndex = size;
+ b->next = head;
+ head = b;
+
+ data = HUNKS(b);
+ *((DataType **) data) = type;
+ return data;
}
#ifdef MEM_TRACE
@@ -226,345 +209,131 @@
#endif
/*
- * address->(block,index) translation scheme. three routines:
- *
- * noteBlock - install a new block into the database
- * addrToBlock - translate an address into (block, index)
- * blockWalk - call a routine with every referenced block
+ * garbage collection scheme
*/
-static struct block *root;
+#define isReferenced(a) (*((PtrInt *)(a)) & 1)
+#define clrReference(a) (*((PtrInt *)(a)) &= ~1)
+#define setReference(a) (*((PtrInt *)(a)) |= 1)
-static void
-noteBlock (struct block *b)
-{
- (void) tree_insert (&root, b);
-#ifdef DEBUG
- if (GCdebug)
- verifyBlock();
-#endif
-}
+/*
+ * eliminate any remaining free list
+ */
static void
-unNoteBlock (struct block *b)
+tossFree (void)
{
- (void) tree_delete (&root, b);
-#ifdef DEBUG
- if (GCdebug)
- verifyBlock();
-#endif
+ memset (freeList, '\0', NUMSIZES * sizeof(freeList[0]));
}
-#ifdef DEBUG
-static void
-verifyBlock (void)
-{
- if (!tree_verify (root))
- abort ();
-}
-#endif
-
-static void
-blockTreeWalk (struct block *treep,
- void (*function)(struct block *))
+static int
+busy (unsigned char *data)
{
- if (treep) {
- blockTreeWalk (treep->left, function);
- function (treep);
- blockTreeWalk (treep->right, function);
- }
-}
+ DataType *type;
-static void
-blockWalk (void (*function) (struct block *))
-{
- blockTreeWalk (root, function);
+ if (isReferenced (data))
+ return 1;
+ type = TYPE(data);
+ if (!type)
+ return 0;
+ if (!type->Free)
+ return 0;
+ if ((*type->Free) (data))
+ return 0;
+ return 1;
}
-/*
- * garbage collection scheme
- */
-
-/*
- * note that setObjectRef has had addrToBlock inlined for speed
- */
-
static int
-setReference (void *address)
+checkBlockRef (struct block *b)
{
- register struct block *b;
- register int dist;
- register int byte;
- register int bit;
- register int index;
- register unsigned char *map;
- int old;
-
- /*
- * a very simple cache -- this results
- * in about 16% speed increase in this
- * routine best case. Worse case it
- * results in about a 5% decrease from
- * wasted computation
- */
- static struct block *cache;
-
- b = cache;
- if ((b = cache) &&
- (PtrInt) address >= (PtrInt) b->data &&
- (PtrInt) address <= (PtrInt) b->data + b->datasize)
- goto cache_hit;
-
- for (b = root; b;) {
- if ((PtrInt) address < (PtrInt) b->data)
- b = b->left;
- else if ((PtrInt) address >= (PtrInt) b->data + b->datasize)
- b = b->right;
- else {
- cache = b;
- cache_hit: ;
- if ((map = b->bitmap)) {
- dist = (PtrInt) address - (PtrInt) b->data;
- index = dist / HUNKSIZE(b->sizeIndex);
- byte = index >> 3;
- bit = (1 << (index & 7));
- old = map[byte] & bit;
- map[byte] |= bit;
- } else
- old = b->ref;
- b->ref = 1;
+ int sizeIndex = b->sizeIndex;
+ unsigned char *data = HUNKS(b);
+
+ if (sizeIndex >= NUMSIZES)
+ {
+ if (busy (data))
+ {
+ clrReference(HUNKS(b));
+ totalObjectsUsed++;
+ totalBytesUsed += sizeIndex;
+ useMap[NUMSIZES]++;
#ifdef MEM_TRACE
- if (!old)
- MemActiveReference (TYPE(address),
- map ? HUNKSIZE(b->sizeIndex) :
- b->datasize);
+ MemActiveReference (TYPE(data), b->sizeIndex);
#endif
- return old;
+ return 1;
}
- }
- return 1;
-}
-
-/*
- * Verify that address through address+size are in
- * same object as base
- */
-void
-MemCheckPointer (void *base, void *address, int size)
-{
- struct block *b;
- int datasize;
-
- for (b = root; b;) {
- if ((PtrInt) address < (PtrInt) b->data)
- b = b->left;
- else if ((PtrInt) address >= (PtrInt) b->data + b->datasize)
- b = b->right;
else
{
- if (b->bitmap)
- datasize = HUNKSIZE(b->sizeIndex);
- else
- datasize = b->datasize;
- if ((PtrInt) base <= (PtrInt) address &&
- (PtrInt) address + size <= (PtrInt) base + datasize)
- {
- return;
- }
- abort ();
+ totalBytesFree += sizeIndex;
+ totalObjectsFree++;
+ return 0;
}
}
- abort ();
-}
-
-void
-MemFree (void *address, int size)
-{
- int sizeIndex = 0;
-
-#if NUMSIZES > 16
- bad NUMSIZES
-#endif
- if (size)
- {
- if (size > HUNKSIZE(7))
- sizeIndex += 8;
- if (size > HUNKSIZE(sizeIndex+3))
- sizeIndex += 4;
- if (size > HUNKSIZE(sizeIndex+1))
- sizeIndex += 2;
- if (size > HUNKSIZE(sizeIndex))
- sizeIndex += 1;
- }
else
{
- struct block *b;
+ struct bfree *first = 0;
+ struct bfree **prev = &first;
+ int n = NUMHUNK(sizeIndex);
+ int anybusy = 0;
+ int size = HUNKSIZE(sizeIndex);
- for (b = root; b;) {
- if ((PtrInt) address < (PtrInt) b->data)
- b = b->left;
- else if ((PtrInt) address >= (PtrInt) b->data + b->datasize)
- b = b->right;
+ while (n--)
+ {
+ if (busy (data))
+ {
+ clrReference(data);
+#ifdef MEM_TRACE
+ MemActiveReference (TYPE(data), size);
+#endif
+ totalObjectsUsed++;
+ useMap[sizeIndex]++;
+ totalBytesUsed += size;
+ anybusy = 1;
+ }
else
{
- if (b->bitmap)
- sizeIndex = b->sizeIndex;
- else
- sizeIndex = NUMSIZES;
- break;
+ TYPE(data) = 0;
+ *prev = (struct bfree *) data;
+ prev = &((struct bfree *) data)->next;
+ totalBytesFree += size;
+ totalObjectsFree++;
}
+ data += size;
}
- }
-
- if (sizeIndex >= NUMSIZES)
- {
- struct block *b = (struct block *) address - 1;
- unNoteBlock (b);
- free (b);
- }
- else
- {
- struct bfree *old = address;
-
- old->next = freeList[sizeIndex];
- freeList[sizeIndex] = old;
- }
-}
-
-/*
- * clearRef: zero's the reference bit for all objects
- */
-
-static void
-clearBlockRef (struct block *b)
-{
- int i;
-
- if (b->bitmap)
- for (i = 0; i < b->bitmapsize; i++)
- b->bitmap[i] = 0;
- b->ref = 0;
-}
-
-static void
-clearRef (void)
-{
- blockWalk (clearBlockRef);
-}
-
-/*
- * eliminate any remaining free list
- */
-
-static void
-tossFree (void)
-{
- int i;
-
- for (i = 0; i < NUMSIZES; i++)
- freeList[i] = 0;
-}
-
-/*
- * checkRef: rebuild the free lists from unused data
- */
-
-static void
-checkBlockRef (struct block *b)
-{
- int sizeIndex;
- int size;
- unsigned char *byte;
- int bit;
- unsigned char *object, *max;
- struct bfree *thisLast;
- DataType *type;
-
- if (!b->ref) {
-#ifdef DEBUG
- if (GCdebug > 1)
- debug ("unreferenced block at 0x%x\n", b);
-#endif
- if (b->sizeIndex == NUMSIZES)
+ if (anybusy)
{
- object = b->data;
- type = TYPE(object);
- if (type && type->Free)
- {
- if (!(*type->Free) (object))
- goto largeStillBusy;
- }
- TYPE(object) = 0;
- totalBytesFree += b->datasize;
- totalObjectsFree++;
+ *prev = freeList[sizeIndex];
+ freeList[sizeIndex] = first;
+ return 1;
}
else
{
- totalBytesFree += b->datasize;
- totalObjectsFree += b->datasize / HUNKSIZE(b->sizeIndex);
- }
- b->bitmap = (unsigned char *) hughFree;
- hughFree = b;
-
- } else if (b->bitmap) {
- sizeIndex = b->sizeIndex;
- thisLast = lastFree[sizeIndex];
- max = b->data + b->datasize;
- size = HUNKSIZE(sizeIndex);
- byte = b->bitmap;
- bit = 1;
- for (object = b->data; object < max; object += size) {
- if (!(*byte & bit) &&
- (!(type = TYPE(object)) ||
- !type->Free ||
- (*type->Free) (object)))
- {
- TYPE(object) = 0;
- if (thisLast)
- thisLast->next = (struct bfree *) object;
- else
- freeList[sizeIndex] = (struct bfree *) object;
- thisLast = (struct bfree *) object;
- totalBytesFree += size;
- totalObjectsFree++;
- }
- else
- {
- totalObjectsUsed++;
- useMap[sizeIndex]++;
- totalBytesUsed += size;
- }
- bit <<= 1;
- if (bit == (1 << BITSPERCH)) {
- bit = 1;
- byte++;
- }
+ return 0;
}
- if (thisLast)
- thisLast->next = 0;
- lastFree[sizeIndex] = thisLast;
- } else {
-largeStillBusy:
- useMap[NUMSIZES]++;
- totalBytesUsed += b->datasize;
}
}
+/*
+ * checkRef: rebuild the free lists from unused data
+ */
+
static void
checkRef (void)
{
int i;
- struct block *n;
+ struct block *b, **p;
for (i = 0; i < NUMSIZES; i++)
lastFree[i] = 0;
- hughFree = 0;
- blockWalk (checkBlockRef);
- while (hughFree) {
- n = (struct block *) hughFree->bitmap;
- unNoteBlock (hughFree);
- free (hughFree);
- hughFree = n;
+ for (p = &head; (b = *p); )
+ {
+ if (checkBlockRef (b))
+ p = &b->next;
+ else
+ {
+ *p = b->next;
+ free (b);
+ }
}
GarbageTime = GARBAGETIME/* - (totalBytesFree / BLOCKSIZE) */;
if (GarbageTime < 10)
@@ -576,7 +345,7 @@
debug ("GC: free: bytes %7d objects %7d\n",
totalBytesFree, totalObjectsFree);
for (i = 0; i <= NUMSIZES; i++)
- debug ("used %4d: %7d\n",
+ debug ("used %5d: %7d\n",
i == NUMSIZES ? 0 : HUNKSIZE(i), useMap[i]);
debug ("GC: GarbageTime set to %d\n", GarbageTime);
}
@@ -607,14 +376,20 @@
return;
if (PtrToInt(object) & 3)
return;
- if (!setReference (object))
+ if (!isReferenced (object))
{
type = TYPE(object);
+ setReference(object);
if (type && type->Mark)
(*type->Mark) (object);
}
}
+/*
+ * Mark an object but don't recurse, returning
+ * whether the object was previously referenced or not
+ */
+
int
MemReferenceNoRecurse (void *object)
{
@@ -622,7 +397,10 @@
return 1;
if (PtrToInt (object) & 3)
return 1;
- return setReference (object);
+ if (isReferenced (object))
+ return 1;
+ setReference (object);
+ return 0;
}
DataType *
@@ -667,7 +445,6 @@
#ifdef MEM_TRACE
MemActiveReset ();
#endif
- clearRef ();
tossFree ();
#ifdef DEBUG
if (GCdebug)
@@ -680,11 +457,4 @@
if (TemporaryData)
MemReference (TemporaryData);
checkRef ();
-#ifdef DEBUG
- if (GCdebug) {
- debug ("GC: verifyBlock\n");
- verifyBlock ();
- }
-#endif
}
-
Index: mem.h
===================================================================
RCS file: /local/src/CVS/nickle/mem.h,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -d -r1.13 -r1.14
--- mem.h 27 Feb 2004 03:50:16 -0000 1.13
+++ mem.h 10 Aug 2004 07:39:55 -0000 1.14
@@ -43,9 +43,14 @@
struct bfree *next;
};
-/* make sure we can store doubles in blocks */
+typedef unsigned long PtrInt;
-#include "avl.h"
+struct block {
+ struct block *next;
+ int sizeIndex;
+};
+
+/* make sure we can store doubles in blocks */
union block_round {
struct block b;
@@ -57,8 +62,12 @@
# define HUNKSIZE(i) (MINHUNK << (i))
# define MAXHUNK HUNKSIZE(NUMSIZES-1)
+#if HAVE_C_INLINE
+#define USE_C_INLINE 1
+#endif
+
extern void MemInitialize (void);
-#ifndef HAVE_C_INLINE
+#ifndef USE_C_INLINE
extern void *MemAllocate (DataType *type, int size);
extern void *MemAllocateRef (DataType *type, int size);
#endif
@@ -96,13 +105,13 @@
#define RETURN(r) return (STACK_RETURN (MemStack, __stackPointer, (r)))
#define NOREFRETURN(r) return (EXIT(), (r))
-#if defined(HAVE_C_INLINE) || defined(MEM_NEED_ALLOCATE)
+#if defined(USE_C_INLINE) || defined(MEM_NEED_ALLOCATE)
/*
* Allocator entry point
*/
-#ifdef HAVE_C_INLINE
+#ifdef USE_C_INLINE
static inline struct bfree *
#else
static struct bfree *
@@ -142,7 +151,7 @@
return new;
}
-#ifdef HAVE_C_INLINE
+#ifdef USE_C_INLINE
static inline void *
#else
void *
@@ -157,7 +166,7 @@
return (void *) new;
}
-#ifdef HAVE_C_INLINE
+#ifdef USE_C_INLINE
static inline void *
#else
void *
Index: memp.h
===================================================================
RCS file: /local/src/CVS/nickle/memp.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- memp.h 27 Feb 2004 03:50:16 -0000 1.5
+++ memp.h 10 Aug 2004 07:39:55 -0000 1.6
@@ -18,11 +18,9 @@
# define GOODBLOCKSIZE (0x2000)
# define BLOCKSIZE (GOODBLOCKSIZE < MINBLOCKSIZE ? \
MINBLOCKSIZE : GOODBLOCKSIZE)
+# define DATASIZE (BLOCKSIZE - HEADSIZE)
+# define NUMHUNK(i) ((i) >= NUMSIZES ? 1 : (DATASIZE / HUNKSIZE(i)))
-# define GARBAGETIME 1000
-
-# define BITSPERCH (8)
-# define NUMINBLOCK(size) (((BLOCKSIZE - HEADSIZE) * \
- BITSPERCH) / (1 + BITSPERCH * (size)))
-# define BITMAPSIZE(size) ((NUMINBLOCK(size) + (BITSPERCH-1)) / BITSPERCH)
+# define HUNKS(b) ((unsigned char *) (b) + HEADSIZE)
+# define GARBAGETIME 1000
- Previous message: [Commit] nickle/debian changelog,1.18,1.19
- Next message: [Commit]
nickle ChangeLog, 1.79, 1.80 mem.c, 1.19, 1.20 mem.h, 1.14,
1.15 memp.h, 1.6, 1.7
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the Commit
mailing list