Quoting Tony Balinski <[EMAIL PROTECTED]>:
> Since I find I am unable to add a patch to the sourceforge bug report
> mentioned above (am I missing some privileges here?), I'm sending this
> patch to the list for perusal.
>
> Share and enjoy!
>
> Tony
Oops, didn't notice this wasn't a context diff... sorry. Here's the patch
again!
T
Allow macro data garbage collector to run during macro execution
An old limitation of the garbage collector (GC) is its inability to tidy
during macro execution.
This patch converts NEdit macro's mark/sweep technique so that it can run
during macro execution. What needs to be done is to allow the mark part to
run through the active macro call stacks, allowing marking of function-local
strings and arrays. For this all continuation contexts need to be
accessible. Although this is all quite easy to do, it is not clear how often
it should be done (other than at the end of macro execution). This
implementation invokes the GC following an earlier call after a maximum
number of allocations (MAX_N_ALLOC_LIMIT=10000), or after allocation of a
certain amount of space (SIZE_ALLOC_LIMIT=1MB), along with a minimum number
of allocations (MIN_N_ALLOC_LIMIT=200), has occurred. Since the mark/sweep
itself (particularly for situations where lots of global data are
accessible) itself requires much time, calling the GC shouldn't be performed
too frequently.
diff -U5 -r nedit_official/source/interpret.c nedit_mod/source/interpret.c
--- nedit_official/source/interpret.c 2008-03-09 20:29:38.000000000 +0100
+++ nedit_mod/source/interpret.c 2008-05-15 00:36:28.000000000 +0200
@@ -68,10 +68,14 @@
allowed per program */
#define INSTRUCTION_LIMIT 100 /* Number of instructions the interpreter is
allowed to execute before preempting and
returning to allow other things to run */
+#define MAX_N_ALLOC_LIMIT 10000 /* max num allocs before garbage collect */
+#define MIN_N_ALLOC_LIMIT 200 /* min num allocs before garbage collect */
+#define SIZE_ALLOC_LIMIT 1048576 /* limit on new allocations before GC */
+
/* Temporary markers placed in a branch address location to designate
which loop address (break or continue) the location needs */
#define NEEDS_BREAK 1
#define NEEDS_CONTINUE 2
@@ -160,20 +164,30 @@
#endif /* #ifndef DEBUG_STACK */
/* Global symbols and function definitions */
static Symbol *GlobalSymList = NULL;
+static long numAllocatedSinceLastGC = 0;
+static size_t sizeAllocatedSinceLastGC = 0;
+
+/* structure to link allocated strings */
+typedef struct GCStringTag {
+ struct GCStringTag *next;
+ char buff[1]; /* buff[0] is the same as the inUse flag */
+} GCString;
+
/* List of all memory allocated for strings */
-static char *AllocatedStrings = NULL;
+static GCString *AllocatedStrings = NULL;
typedef struct SparseArrayEntryWrapperTag {
- SparseArrayEntry data; /* LEAVE this as top entry */
+ SparseArrayEntry data; /* LEAVE this as top entry */
int inUse; /* we use pointers to the data to refer to the
entire struct */
struct SparseArrayEntryWrapperTag *next;
} SparseArrayEntryWrapper;
-static SparseArrayEntryWrapper *AllocatedSparseArrayEntries = NULL;
+static SparseArrayEntryWrapper *AllocatedSparseArrayEntries = NULL;
+RestartData *Continuations = NULL;
/* Message strings used in macros (so they don't get repeated every time
the macros are used */
static const char *StackOverflowMsg = "macro stack overflow";
static const char *StackUnderflowMsg = "macro stack underflow";
@@ -456,10 +470,47 @@
else
fprintf(stderr, "NEdit: internal error (uat) in macro parser\n");
}
}
+static void linkContext(RestartData *context)
+{
+ if (Continuations) {
+ /* add context behind Continuations */
+ context->next = Continuations;
+ context->prev = Continuations->prev;
+ context->prev->next = Continuations->prev = context;
+ }
+ else {
+ Continuations = context->next = context->prev = context;
+ }
+}
+static void dropContext(RestartData *context)
+{
+ /* unlink it from the list of continuations */
+ Continuations = context->next;
+
+ context->next->prev = context->prev;
+ context->prev->next = context->next;
+
+ if (Continuations == context)
+ Continuations = 0;
+}
+static RestartData *newContext(WindowInfo *window, Program *prog)
+{
+ RestartData *context;
+
+ context = (RestartData *)XtMalloc(sizeof(RestartData));
+ context->stack = (DataValue *)XtMalloc(sizeof(DataValue) * STACK_SIZE);
+ context->stackP = context->stack;
+ context->pc = prog->code;
+ context->runWindow = window;
+ context->focusWindow = window;
+ linkContext(context);
+ return context;
+}
+
/*
** Execute a compiled macro, "prog", using the arguments in the array
** "args". Returns one of MACRO_DONE, MACRO_PREEMPT, or MACRO_ERROR.
** if MACRO_DONE is returned, the macro completed, and the returned value
** (if any) can be read from "result". If MACRO_PREEMPT is returned, the
@@ -474,17 +525,11 @@
int i;
/* Create an execution context (a stack, a stack pointer, a frame pointer,
and a program counter) which will retain the program state across
preemption and resumption of execution */
- context = (RestartData *)XtMalloc(sizeof(RestartData));
- context->stack = (DataValue *)XtMalloc(sizeof(DataValue) * STACK_SIZE);
- *continuation = context;
- context->stackP = context->stack;
- context->pc = prog->code;
- context->runWindow = window;
- context->focusWindow = window;
+ *continuation = context = newContext(window, prog);
/* Push arguments and call information onto the stack */
for (i=0; i<nArgs; i++)
*(context->stackP++) = args[i];
@@ -556,10 +601,18 @@
FreeRestartData(continuation);
restoreContext(&oldContext);
return MACRO_DONE;
}
}
+ /**/
+ if (numAllocatedSinceLastGC >= MAX_N_ALLOC_LIMIT ||
+ (sizeAllocatedSinceLastGC >= SIZE_ALLOC_LIMIT &&
+ numAllocatedSinceLastGC >= MIN_N_ALLOC_LIMIT)) {
+ saveContext(continuation); /* make sure context is up to date */
+ GarbageCollectStrings();
+ }
+ /**/
/* Count instructions executed. If the instruction limit is hit,
preempt, store re-start information in continuation and give
X, other macros, and other shell scripts a chance to execute */
instCount++;
@@ -607,10 +660,11 @@
}
}
void FreeRestartData(RestartData *context)
{
+ dropContext(context);
XtFree((char *)context->stack);
XtFree((char *)context);
}
/*
@@ -833,61 +887,61 @@
#ifdef TRACK_GARBAGE_LEAKS
static int numAllocatedStrings = 0;
static int numAllocatedSparseArrayElements = 0;
#endif
-/* Allocate a new string buffer of length chars */
+/*
+** Allocate a new string buffer of length chars
+** length does not include terminating null
+*/
char *AllocString(int length)
{
- char *mem;
-
- mem = XtMalloc(length + sizeof(char *) + 1);
- *((char **)mem) = AllocatedStrings;
- AllocatedStrings = mem;
+ GCString *mem;
+ length += sizeof (GCString);
+ mem = (GCString *)XtMalloc(length);
+ if (mem) {
+ mem->next = AllocatedStrings;
+ AllocatedStrings = mem;
#ifdef TRACK_GARBAGE_LEAKS
- ++numAllocatedStrings;
+ ++numAllocatedStrings;
#endif
- return mem + sizeof(char *) + 1;
+ ++numAllocatedSinceLastGC;
+ sizeAllocatedSinceLastGC += length;
+ return &mem->buff[1];
+ }
+ return NULL;
}
/*
* Allocate a new NString buffer of length chars (terminating \0 included),
* The buffer length is initialized to length-1 and the terminating \0 is
* filled in.
*/
int AllocNString(NString *string, int length)
{
- char *mem;
+ string->rep = AllocString(length);
- mem = XtMalloc(length + sizeof(char *) + 1);
- if (!mem) {
- string->rep = 0;
+ if (!string->rep) {
string->len = 0;
return False;
}
-
- *((char **)mem) = AllocatedStrings;
- AllocatedStrings = mem;
-#ifdef TRACK_GARBAGE_LEAKS
- ++numAllocatedStrings;
-#endif
- string->rep = mem + sizeof(char *) + 1;
string->rep[length-1] = '\0'; /* forced \0 */
string->len = length-1;
return True;
}
/* Allocate a new string buffer of length chars, and copy in the string s */
char *AllocStringNCpy(const char *s, int length)
{
char *p = AllocString(length + 1); /* add extra char for forced \0 */
- if (!p)
- return p;
- if (!s)
- s = "";
- p[length] = '\0'; /* forced \0 */
- return strncpy(p, s, length);
+ if (!p) {
+ if (!s)
+ s = "";
+ p[length] = '\0'; /* forced \0 */
+ strncpy(p, s, length);
+ }
+ return p;
}
/*
* Allocate a new NString buffer of length chars (terminating \0 NOT included),
* and copy at most length characters of the given string.
@@ -934,10 +988,12 @@
mem->next = AllocatedSparseArrayEntries;
AllocatedSparseArrayEntries = mem;
#ifdef TRACK_GARBAGE_LEAKS
++numAllocatedSparseArrayElements;
#endif
+ ++numAllocatedSinceLastGC;
+ sizeAllocatedSinceLastGC += sizeof(SparseArrayEntryWrapper);
return(&(mem->data));
}
static void MarkArrayContentsAsUsed(SparseArrayEntry *arrayPtr)
{
@@ -966,61 +1022,102 @@
}
}
}
/*
-** Collect strings that are no longer referenced from the global symbol
-** list. THIS CAN NOT BE RUN WHILE ANY MACROS ARE EXECUTING. It must
-** only be run after all macro activity has ceased.
+** Mark allocated data as active (so the garbage collection doesn't delete any
+** of it)
+*/
+static void garbageCollectMarkDataValue(DataValue *dv)
+{
+ char *s;
+ switch (dv->tag)
+ {
+ case STRING_TAG:
+ /* test first because it may be read-only static string */
+ s = dv->val.str.rep;
+ if (!s[-1])
+ s[-1] = 1;
+ break;
+ case ARRAY_TAG:
+ MarkArrayContentsAsUsed(dv->val.arrayPtr);
+ break;
+ case ARITER_TAG:
+ MarkArrayContentsAsUsed(dv->val.iter.array);
+ break;
+ default:
+ break;
+ }
+}
+
+/*
+** Marks all strings and/or arrays accessible in all active context stacks
+*/
+static void garbageCollectMarkActiveData()
+{
+ RestartData sentinel;
+ RestartData *ctx;
+
+ linkContext(&sentinel);
+ for (ctx = sentinel.next; ctx != &sentinel; ctx = ctx->next) {
+ DataValue *dv;
+ for (dv = ctx->stack; dv != ctx->stackP; ++dv) {
+ garbageCollectMarkDataValue(dv);
+ }
+ }
+ dropContext(&sentinel);
+}
+
+/*
+** Collect strings that are no longer referenced from the global symbol list.
*/
void GarbageCollectStrings(void)
{
SparseArrayEntryWrapper *nextAP, *thisAP;
- char *p, *next;
+ GCString *p;
Symbol *s;
+#ifdef TRACK_GARBAGE_LEAKS
+ long nSinceLastTime = numAllocatedSinceLastGC;
+ long nTidied = 0;
+#endif
/* mark all strings as unreferenced */
- for (p = AllocatedStrings; p != NULL; p = *((char **)p)) {
- *(p + sizeof(char *)) = 0;
+ for (p = AllocatedStrings; p != NULL; p = p->next) {
+ p->buff[0] = 0;
}
for (thisAP = AllocatedSparseArrayEntries;
thisAP != NULL; thisAP = thisAP->next) {
thisAP->inUse = 0;
}
/* Sweep the global symbol list, marking which strings are still
referenced */
for (s = GlobalSymList; s != NULL; s = s->next) {
- if (s->value.tag == STRING_TAG) {
- /* test first because it may be read-only static string */
- if (!(*(s->value.val.str.rep - 1))) {
- *(s->value.val.str.rep - 1) = 1;
- }
- }
- else if (s->value.tag == ARRAY_TAG) {
- MarkArrayContentsAsUsed(s->value.val.arrayPtr);
- }
+ garbageCollectMarkDataValue(&s->value);
}
+ /* Now mark all values in all existing macro run contexts */
+ garbageCollectMarkActiveData();
/* Collect all of the strings which remain unreferenced */
- next = AllocatedStrings;
+ p = AllocatedStrings;
AllocatedStrings = NULL;
- while (next != NULL) {
- p = next;
- next = *((char **)p);
- if (*(p + sizeof(char *)) != 0) {
- *((char **)p) = AllocatedStrings;
- AllocatedStrings = p;
- }
+ while (p != NULL) {
+ GCString *q = p->next;
+ if (p->buff[0]) {
+ p->next = AllocatedStrings;
+ AllocatedStrings = p;
+ }
else {
#ifdef TRACK_GARBAGE_LEAKS
--numAllocatedStrings;
+ ++nTidied;
#endif
- XtFree(p);
+ XtFree((char *)p);
}
+ p = q;
}
nextAP = AllocatedSparseArrayEntries;
AllocatedSparseArrayEntries = NULL;
while (nextAP != NULL) {
@@ -1031,18 +1128,29 @@
AllocatedSparseArrayEntries = thisAP;
}
else {
#ifdef TRACK_GARBAGE_LEAKS
--numAllocatedSparseArrayElements;
+ ++nTidied;
#endif
XtFree((char *)thisAP);
}
}
#ifdef TRACK_GARBAGE_LEAKS
- printf("str count = %d\nary count = %d\n", numAllocatedStrings,
numAllocatedSparseArrayElements);
+ printf("\nNEDIT GARBAGE STATS:\nstrings = %d\narrays = %d\n"
+ "since last time: allocs = %ld - frees = %ld => diff = %ld\n"
+ " new bytes allocated: %lu\n"
+ "Continuations is %sNULL\n",
+ numAllocatedStrings, numAllocatedSparseArrayElements,
+ nSinceLastTime, nTidied, nSinceLastTime - nTidied,
+ (unsigned long)sizeAllocatedSinceLastGC,
+ Continuations ? "not " : "");
+ fflush(stdout);
#endif
+ numAllocatedSinceLastGC = 0;
+ sizeAllocatedSinceLastGC = 0;
}
/*
** Save and restore execution context to data structure "context"
*/
@@ -2514,11 +2622,11 @@
nDim = PC->value;
PC++;
DISASM_RT(PC-2, 1);
- STACKDUMP(nDim, 3);
+ STACKDUMP(nDim+2, 3);
if (nDim > 0) {
POP(srcValue)
errNum = makeArrayKeyFromArgs(nDim, &keyString, 0);
@@ -2634,16 +2742,17 @@
}
else {
return(execError("bad temporary iterator: %s", iterator->name));
}
- iteratorValPtr->tag = INT_TAG;
+ iteratorValPtr->tag = ARITER_TAG;
if (arrayVal.tag != ARRAY_TAG) {
return(execError("can't iterate non-array", NULL));
}
- iteratorValPtr->val.arrayPtr = arrayIterateFirst(&arrayVal);
+ iteratorValPtr->val.iter.array = arrayVal.val.arrayPtr;
+ iteratorValPtr->val.iter.ptr = arrayIterateFirst(&arrayVal);
return(STAT_OK);
}
/*
** copy key to symbol if node is still valid, marked bad by a color of -1
@@ -2702,17 +2811,17 @@
}
else {
return(execError("bad temporary iterator: %s", iterator->name));
}
- thisEntry = iteratorValPtr->val.arrayPtr;
+ thisEntry = iteratorValPtr->val.iter.ptr;
if (thisEntry && thisEntry->nodePtrs.color != -1) {
itemValPtr->tag = STRING_TAG;
itemValPtr->val.str.rep = thisEntry->key;
itemValPtr->val.str.len = strlen(thisEntry->key);
- iteratorValPtr->val.arrayPtr = arrayIterateNext(thisEntry);
+ iteratorValPtr->val.iter.ptr = arrayIterateNext(thisEntry);
}
else {
PC = branchAddr;
}
return(STAT_OK);
diff -U5 -r nedit_official/source/interpret.h nedit_mod/source/interpret.h
--- nedit_official/source/interpret.h 2008-03-09 20:29:38.000000000 +0100
+++ nedit_mod/source/interpret.h 2008-05-14 23:34:15.000000000 +0200
@@ -48,11 +48,11 @@
OP_BRANCH_TRUE, OP_BRANCH_FALSE, OP_BRANCH_NEVER, OP_ARRAY_REF,
OP_ARRAY_ASSIGN, OP_BEGIN_ARRAY_ITER, OP_ARRAY_ITER, OP_IN_ARRAY,
OP_ARRAY_DELETE, OP_PUSH_ARRAY_SYM, OP_ARRAY_REF_ASSIGN_SETUP, OP_PUSH_ARG,
OP_PUSH_ARG_COUNT, OP_PUSH_ARG_ARRAY};
-enum typeTags {NO_TAG, INT_TAG, STRING_TAG, ARRAY_TAG};
+enum typeTags {NO_TAG, INT_TAG, STRING_TAG, ARRAY_TAG, ARITER_TAG};
enum execReturnCodes {MACRO_TIME_LIMIT, MACRO_PREEMPT, MACRO_DONE,
MACRO_ERROR};
#define ARRAY_DIM_SEP "\034"
@@ -73,10 +73,15 @@
typedef struct NStringTag {
char *rep;
size_t len;
} NString;
+typedef struct ArrayIterTag {
+ struct SparseArrayEntryTag *ptr;
+ struct SparseArrayEntryTag *array;
+} ArrayIter;
+
typedef struct DataValueTag {
enum typeTags tag;
union {
int n;
struct NStringTag str;
@@ -84,10 +89,11 @@
struct ProgramTag* prog;
XtActionProc xtproc;
Inst* inst;
struct DataValueTag* dataval;
struct SparseArrayEntryTag *arrayPtr;
+ ArrayIter iter;
} val;
} DataValue;
typedef struct SparseArrayEntryTag {
rbTreeNode nodePtrs; /* MUST BE FIRST ENTRY */
@@ -107,17 +113,19 @@
Symbol *localSymList;
Inst *code;
} Program;
/* Information needed to re-start a preempted macro */
-typedef struct {
+typedef struct RestartDataTag {
DataValue *stack;
DataValue *stackP;
DataValue *frameP;
Inst *pc;
WindowInfo *runWindow;
WindowInfo *focusWindow;
+ struct RestartDataTag *next;
+ struct RestartDataTag *prev;
} RestartData;
void InitMacroGlobals(void);
SparseArrayEntry *arrayIterateFirst(DataValue *theArray);
--
NEdit Develop mailing list - [email protected]
http://www.nedit.org/mailman/listinfo/develop
