[PATCH v3 0/4] MR1635: jscript: Implement a Garbage Collector to deal with circular references.
Implement a basic GC based on the mark-and-sweep algorithm, without requiring manually specifying "roots", which vastly simplifies the management. For now, it is triggered every 30 seconds since it last finished, on a new object initialization. Better heuristics could be used in the future. The comments in the code should hopefully understand the high level logic of this approach without boilerplate details. I've tested it on FFXIV launcher (along with other patches from Proton to have it work) and it stops the massive memory leak successfully by itself, so at least it does its job properly. The last patch in the MR is just an optimization for a *very* common case. For artificial testing, one could use something like: ```javascript function leak() { var a = {}, b = {}; a.b = b; b.a = a; } ``` which creates a circular ref and will leak when the function returns. It also introduces and makes use of a "heap_stack", which prevents stack overflows on long chains. -- v3: jscript: Create the source function's 'prototype' prop object on demand. jscript: Run the garbage collector every 30 seconds on a new object jscript: Implement CollectGarbage(). jscript: Implement a Garbage Collector to deal with circular references. https://gitlab.winehq.org/wine/wine/-/merge_requests/1635
From: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> Implement a basic GC based on the mark-and-sweep algorithm, without requiring manually specifying "roots", which vastly simplifies the code. Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- dlls/jscript/dispex.c | 240 ++++++++++++++++++++++++++++++++++++++ dlls/jscript/enumerator.c | 11 +- dlls/jscript/function.c | 98 ++++++++++++++-- dlls/jscript/jscript.c | 3 + dlls/jscript/jscript.h | 72 +++++++++++- dlls/jscript/jsregexp.c | 17 ++- dlls/jscript/jsutils.c | 38 ++++++ dlls/jscript/set.c | 37 +++++- dlls/jscript/tests/run.c | 18 +++ 9 files changed, 520 insertions(+), 14 deletions(-) diff --git a/dlls/jscript/dispex.c b/dlls/jscript/dispex.c index 1a7a75875df..f41008afa2d 100644 --- a/dlls/jscript/dispex.c +++ b/dlls/jscript/dispex.c @@ -666,6 +666,243 @@ static HRESULT fill_protrefs(jsdisp_t *This) return S_OK; } +static void unlink_props(jsdisp_t *jsdisp) +{ + dispex_prop_t *prop = jsdisp->props, *end; + + for(end = prop + jsdisp->prop_cnt; prop < end; prop++) { + switch(prop->type) { + case PROP_DELETED: + case PROP_PROTREF: + continue; + case PROP_JSVAL: + jsval_release(prop->u.val); + break; + case PROP_ACCESSOR: + if(prop->u.accessor.getter) + jsdisp_release(prop->u.accessor.getter); + if(prop->u.accessor.setter) + jsdisp_release(prop->u.accessor.setter); + break; + default: + break; + } + prop->type = PROP_JSVAL; + prop->flags &= PROPF_ALL; + prop->flags |= PROPF_CONFIGURABLE | PROPF_WRITABLE; + prop->u.val = jsval_undefined(); + } +} + + + +/* + * To deal with circular refcounts, a basic Garbage Collector is used with a variant of the + * mark-and-sweep algorithm that doesn't require knowing or traversing any specific "roots". + * This works based on the assumption that circular references can only happen when objects + * end up pointing to each other, and each other alone, without any external refs. + * + * An "external ref" is a ref to the object that's not from any other object. Example of such + * refs can be local variables, the script ctx (which keeps a ref to the global object), etc. + * + * At a high level, there are 3 logical passes done on the entire list of objects: + * + * 1. Speculatively decrease refcounts of each linked-to-object from each object. This ensures + * that the only remaining refcount on each object is the number of "external refs" to it. + * At the same time, mark all of the objects so that they can be potentially collected. + * + * 2. For each object with a non-zero "external refcount", clear the mark from step 1, and + * recursively traverse all linked objects from it, clearing their marks as well (regardless + * of their refcount), stopping a given path when the object is unmarked (and then going back + * up the heap stack). This basically unmarks all of the objects with "external refcounts" + * and those accessible from them, and only the leaked dangling objects will still be marked. + * + * 3. For each object that is marked, unlink all of the objects linked from it, because they + * are dangling in a circular refcount and not accessible. This should release them. + * + * This collection process has to be done periodically, but can be pretty expensive so there + * has to be a balance between reclaiming dangling objects and performance. + */ +HRESULT gc_run(script_ctx_t *ctx) +{ + /* Save original refcounts in a linked list of chunks */ + struct chunk + { + struct chunk *next; + LONG ref[1020]; + } *head, *chunk; + jsdisp_t *obj, *obj2, *link, *link2; + struct heap_stack heap_stack = { 0 }; + dispex_prop_t *prop, *props_end; + unsigned chunk_idx = 0; + struct list *iter; + HRESULT hres; + + if(!(head = malloc(sizeof(*head)))) + return E_OUTOFMEMORY; + head->next = NULL; + chunk = head; + + /* 1. Save actual refcounts and decrease them speculatively as-if we unlinked the objects */ + LIST_FOR_EACH_ENTRY(obj, &ctx->objects, jsdisp_t, entry) { + if(chunk_idx == ARRAY_SIZE(chunk->ref)) { + if(!(chunk->next = malloc(sizeof(*chunk)))) { + do { + chunk = head->next; + free(head); + head = chunk; + } while(head); + return E_OUTOFMEMORY; + } + chunk = chunk->next, chunk_idx = 0; + chunk->next = NULL; + } + chunk->ref[chunk_idx++] = obj->ref; + } + LIST_FOR_EACH_ENTRY(obj, &ctx->objects, jsdisp_t, entry) { + for(prop = obj->props, props_end = prop + obj->prop_cnt; prop < props_end; prop++) { + switch(prop->type) { + case PROP_JSVAL: + if(is_object_instance(prop->u.val) && (link = to_jsdisp(get_object(prop->u.val))) && link->ctx == ctx) + link->ref--; + break; + case PROP_ACCESSOR: + if(prop->u.accessor.getter && prop->u.accessor.getter->ctx == ctx) + prop->u.accessor.getter->ref--; + if(prop->u.accessor.setter && prop->u.accessor.setter->ctx == ctx) + prop->u.accessor.setter->ref--; + break; + default: + break; + } + } + + if(obj->prototype && obj->prototype->ctx == ctx) + obj->prototype->ref--; + if(obj->builtin_info->gc_traverse) + obj->builtin_info->gc_traverse(obj, GC_TRAVERSE_SPECULATIVELY, NULL); + obj->gc_marked = TRUE; + } + + /* 2. Clear mark on objects with non-zero "external refcount" and all objects accessible from them */ + chunk = head, chunk_idx = 0; + LIST_FOR_EACH_ENTRY(obj, &ctx->objects, jsdisp_t, entry) { + LONG external_ref = obj->ref; + + obj->ref = chunk->ref[chunk_idx++]; /* restore */ + if(chunk_idx == ARRAY_SIZE(chunk->ref)) { + struct chunk *next = chunk->next; + free(chunk); + chunk = next, chunk_idx = 0; + } + if(!external_ref || !obj->gc_marked) + continue; + + hres = heap_stack_push(&heap_stack, NULL); + if(FAILED(hres)) + goto unwind; + + obj2 = obj; + do + { + obj2->gc_marked = FALSE; + + for(prop = obj2->props, props_end = prop + obj2->prop_cnt; prop < props_end; prop++) { + switch(prop->type) { + case PROP_JSVAL: + if(!is_object_instance(prop->u.val)) + continue; + link = to_jsdisp(get_object(prop->u.val)); + link2 = NULL; + break; + case PROP_ACCESSOR: + link = prop->u.accessor.getter; + link2 = prop->u.accessor.setter; + break; + default: + continue; + } + if(link && link->gc_marked && link->ctx == ctx) { + hres = heap_stack_push(&heap_stack, link); + if(FAILED(hres)) + goto unwind_pop; + } + if(link2 && link2->gc_marked && link2->ctx == ctx) { + hres = heap_stack_push(&heap_stack, link2); + if(FAILED(hres)) + goto unwind_pop; + } + } + + if(obj2->prototype && obj2->prototype->gc_marked && obj2->prototype->ctx == ctx) { + hres = heap_stack_push(&heap_stack, obj2->prototype); + if(FAILED(hres)) + goto unwind_pop; + } + + if(obj2->builtin_info->gc_traverse) { + hres = obj2->builtin_info->gc_traverse(obj2, GC_TRAVERSE, &heap_stack); + if(FAILED(hres)) + goto unwind_pop; + } + + do obj2 = heap_stack_pop(&heap_stack); while(obj2 && !obj2->gc_marked); + } while(obj2); + } + heap_stack_free(&heap_stack); + free(chunk); + + /* 3. Remove all the links from the marked objects, since they are dangling */ + iter = list_head(&ctx->objects); + while(iter) { + obj = LIST_ENTRY(iter, jsdisp_t, entry); + if(!obj->gc_marked) { + iter = list_next(&ctx->objects, iter); + continue; + } + + /* Grab it since it gets removed when unlinked */ + jsdisp_addref(obj); + unlink_props(obj); + + if(obj->prototype) { + jsdisp_release(obj->prototype); + obj->prototype = NULL; + } + + if(obj->builtin_info->gc_traverse) + obj->builtin_info->gc_traverse(obj, GC_TRAVERSE_UNLINK, NULL); + + /* Unlinking possibly removed the next object from the list */ + iter = list_next(&ctx->objects, iter); + jsdisp_release(obj); + } + + return S_OK; + +unwind_pop: + do obj2 = heap_stack_pop(&heap_stack); while(obj2); +unwind: + heap_stack_free(&heap_stack); + + /* Restore refs of remaining objects we haven't processed yet (due to error) */ + for(iter = list_next(&ctx->objects, &obj->entry); iter; iter = list_next(&ctx->objects, iter)) { + obj = LIST_ENTRY(iter, jsdisp_t, entry); + obj->ref = chunk->ref[chunk_idx++]; + if(chunk_idx == ARRAY_SIZE(chunk->ref)) { + struct chunk *next = chunk->next; + free(chunk); + chunk = next, chunk_idx = 0; + } + } + free(chunk); + LIST_FOR_EACH_ENTRY(obj, &ctx->objects, jsdisp_t, entry) + obj->gc_marked = FALSE; + return hres; +} + + + struct typeinfo_func { dispex_prop_t *prop; function_code_t *code; @@ -1848,6 +2085,7 @@ HRESULT init_dispex(jsdisp_t *dispex, script_ctx_t *ctx, const builtin_info_t *b script_addref(ctx); dispex->ctx = ctx; + list_add_tail(&ctx->objects, &dispex->entry); return S_OK; } @@ -1882,6 +2120,8 @@ void jsdisp_free(jsdisp_t *obj) { dispex_prop_t *prop; + list_remove(&obj->entry); + TRACE("(%p)\n", obj); for(prop = obj->props; prop < obj->props+obj->prop_cnt; prop++) { diff --git a/dlls/jscript/enumerator.c b/dlls/jscript/enumerator.c index cce2f2d8ec0..aba4dab02a2 100644 --- a/dlls/jscript/enumerator.c +++ b/dlls/jscript/enumerator.c @@ -88,6 +88,11 @@ static void Enumerator_destructor(jsdisp_t *dispex) free(dispex); } +static HRESULT Enumerator_gc_traverse(jsdisp_t *dispex, enum gc_traverse_op op, void *arg) +{ + return gc_process_linked_val(dispex, &enumerator_from_jsdisp(dispex)->item, op, arg); +} + static HRESULT Enumerator_atEnd(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv, jsval_t *r) { @@ -189,7 +194,11 @@ static const builtin_info_t EnumeratorInst_info = { 0, NULL, Enumerator_destructor, - NULL + NULL, + NULL, + NULL, + NULL, + Enumerator_gc_traverse }; static HRESULT alloc_enumerator(script_ctx_t *ctx, jsdisp_t *object_prototype, EnumeratorInstance **ret) diff --git a/dlls/jscript/function.c b/dlls/jscript/function.c index 8d2b3ed9f4f..3b50a88eb77 100644 --- a/dlls/jscript/function.c +++ b/dlls/jscript/function.c @@ -39,6 +39,7 @@ struct _function_vtbl_t { HRESULT (*toString)(FunctionInstance*,jsstr_t**); function_code_t* (*get_code)(FunctionInstance*); void (*destructor)(FunctionInstance*); + HRESULT (*gc_traverse)(FunctionInstance*,enum gc_traverse_op,void*); }; typedef struct { @@ -72,6 +73,11 @@ typedef struct { static HRESULT create_bind_function(script_ctx_t*,FunctionInstance*,jsval_t,unsigned,jsval_t*,jsdisp_t**r); +static HRESULT no_gc_traverse(FunctionInstance *function, enum gc_traverse_op op, void *arg) +{ + return S_OK; +} + static inline FunctionInstance *function_from_jsdisp(jsdisp_t *jsdisp) { return CONTAINING_RECORD(jsdisp, FunctionInstance, dispex); @@ -108,7 +114,8 @@ static void Arguments_destructor(jsdisp_t *jsdisp) free(arguments->buf); } - jsdisp_release(&arguments->function->function.dispex); + if(arguments->function) + jsdisp_release(&arguments->function->function.dispex); free(arguments); } @@ -166,6 +173,23 @@ static HRESULT Arguments_idx_put(jsdisp_t *jsdisp, unsigned idx, jsval_t val) arguments->function->func_code->params[idx], val); } +static HRESULT Arguments_gc_traverse(jsdisp_t *jsdisp, enum gc_traverse_op op, void *arg) +{ + ArgumentsInstance *arguments = arguments_from_jsdisp(jsdisp); + HRESULT hres; + unsigned i; + + if(arguments->buf) { + for(i = 0; i < arguments->argc; i++) { + hres = gc_process_linked_val(jsdisp, &arguments->buf[i], op, arg); + if(FAILED(hres)) + return hres; + } + } + + return gc_process_linked_obj(jsdisp, &arguments->function->function.dispex, (void**)&arguments->function, op, arg); +} + static const builtin_info_t Arguments_info = { JSCLASS_ARGUMENTS, Arguments_value, @@ -174,7 +198,8 @@ static const builtin_info_t Arguments_info = { NULL, Arguments_idx_length, Arguments_idx_get, - Arguments_idx_put + Arguments_idx_put, + Arguments_gc_traverse }; HRESULT setup_arguments_object(script_ctx_t *ctx, call_frame_t *frame) @@ -548,6 +573,12 @@ static void Function_destructor(jsdisp_t *dispex) free(function); } +static HRESULT Function_gc_traverse(jsdisp_t *dispex, enum gc_traverse_op op, void *arg) +{ + FunctionInstance *function = function_from_jsdisp(dispex); + return function->vtbl->gc_traverse(function, op, arg); +} + static const builtin_prop_t Function_props[] = { {L"apply", Function_apply, PROPF_METHOD|2}, {L"arguments", NULL, 0, Function_get_arguments}, @@ -563,7 +594,11 @@ static const builtin_info_t Function_info = { ARRAY_SIZE(Function_props), Function_props, Function_destructor, - NULL + NULL, + NULL, + NULL, + NULL, + Function_gc_traverse }; static const builtin_prop_t FunctionInst_props[] = { @@ -577,7 +612,11 @@ static const builtin_info_t FunctionInst_info = { ARRAY_SIZE(FunctionInst_props), FunctionInst_props, Function_destructor, - NULL + NULL, + NULL, + NULL, + NULL, + Function_gc_traverse }; static HRESULT create_function(script_ctx_t *ctx, const builtin_info_t *builtin_info, const function_vtbl_t *vtbl, size_t size, @@ -657,7 +696,8 @@ static const function_vtbl_t NativeFunctionVtbl = { NativeFunction_call, NativeFunction_toString, NativeFunction_get_code, - NativeFunction_destructor + NativeFunction_destructor, + no_gc_traverse }; HRESULT create_builtin_function(script_ctx_t *ctx, builtin_invoke_t value_proc, const WCHAR *name, @@ -776,11 +816,32 @@ static void InterpretedFunction_destructor(FunctionInstance *func) scope_release(function->scope_chain); } +static HRESULT InterpretedFunction_gc_traverse(FunctionInstance *func, enum gc_traverse_op op, void *arg) +{ + InterpretedFunction *function = (InterpretedFunction*)func; + + /* Make sure to unlink everything during unlink, including deeper scopes, so + that releasing the function itself won't release any additional objects. */ + if(op == GC_TRAVERSE_UNLINK) { + scope_chain_t *scope_chain = function->scope_chain; + if(scope_chain) { + function->scope_chain = NULL; + scope_release(scope_chain); + } + return S_OK; + } + + /* FIXME: Process the scope_chain->obj somehow. The issue is that the function keeps + a ref to the scope itself, not the actual obj... For now, this will possibly leak. */ + return S_OK; +} + static const function_vtbl_t InterpretedFunctionVtbl = { InterpretedFunction_call, InterpretedFunction_toString, InterpretedFunction_get_code, - InterpretedFunction_destructor + InterpretedFunction_destructor, + InterpretedFunction_gc_traverse }; HRESULT create_source_function(script_ctx_t *ctx, bytecode_t *code, function_code_t *func_code, @@ -870,15 +931,36 @@ static void BindFunction_destructor(FunctionInstance *func) for(i = 0; i < function->argc; i++) jsval_release(function->args[i]); - jsdisp_release(&function->target->dispex); + if(function->target) + jsdisp_release(&function->target->dispex); jsval_release(function->this); } +static HRESULT BindFunction_gc_traverse(FunctionInstance *func, enum gc_traverse_op op, void *arg) +{ + BindFunction *function = (BindFunction*)func; + HRESULT hres; + unsigned i; + + for(i = 0; i < function->argc; i++) { + hres = gc_process_linked_val(&function->function.dispex, &function->args[i], op, arg); + if(FAILED(hres)) + return hres; + } + + hres = gc_process_linked_obj(&function->function.dispex, &function->target->dispex, (void**)&function->target, op, arg); + if(FAILED(hres)) + return hres; + + return gc_process_linked_val(&function->function.dispex, &function->this, op, arg); +} + static const function_vtbl_t BindFunctionVtbl = { BindFunction_call, BindFunction_toString, BindFunction_get_code, - BindFunction_destructor + BindFunction_destructor, + BindFunction_gc_traverse }; static HRESULT create_bind_function(script_ctx_t *ctx, FunctionInstance *target, jsval_t bound_this, unsigned argc, diff --git a/dlls/jscript/jscript.c b/dlls/jscript/jscript.c index b020f24beb3..f5331a13b96 100644 --- a/dlls/jscript/jscript.c +++ b/dlls/jscript/jscript.c @@ -495,6 +495,8 @@ static void decrease_state(JScript *This, SCRIPTSTATE state) } script_globals_release(This->ctx); + gc_run(This->ctx); + /* FALLTHROUGH */ case SCRIPTSTATE_UNINITIALIZED: change_state(This, state); @@ -734,6 +736,7 @@ static HRESULT WINAPI JScript_SetScriptSite(IActiveScript *iface, ctx->html_mode = This->html_mode; ctx->acc = jsval_undefined(); list_init(&ctx->named_items); + list_init(&ctx->objects); heap_pool_init(&ctx->tmp_heap); hres = create_jscaller(ctx); diff --git a/dlls/jscript/jscript.h b/dlls/jscript/jscript.h index e1a3da04097..acdc5652a80 100644 --- a/dlls/jscript/jscript.h +++ b/dlls/jscript/jscript.h @@ -69,6 +69,22 @@ void heap_pool_clear(heap_pool_t*) DECLSPEC_HIDDEN; void heap_pool_free(heap_pool_t*) DECLSPEC_HIDDEN; heap_pool_t *heap_pool_mark(heap_pool_t*) DECLSPEC_HIDDEN; +/* Initialize to zero before use */ +struct heap_stack { + struct heap_stack_chunk *chunk; + struct heap_stack_chunk *next; + unsigned idx; +}; + +HRESULT heap_stack_push(struct heap_stack*,void*) DECLSPEC_HIDDEN; +void *heap_stack_pop(struct heap_stack*) DECLSPEC_HIDDEN; + +/* Make sure the stack is completely popped before calling this */ +static inline void heap_stack_free(struct heap_stack *heap_stack) +{ + free(heap_stack->next); +} + typedef struct jsdisp_t jsdisp_t; extern HINSTANCE jscript_hinstance DECLSPEC_HIDDEN; @@ -140,6 +156,7 @@ typedef struct named_item_t { HRESULT create_named_item_script_obj(script_ctx_t*,named_item_t*) DECLSPEC_HIDDEN; named_item_t *lookup_named_item(script_ctx_t*,const WCHAR*,unsigned) DECLSPEC_HIDDEN; void release_named_item(named_item_t*) DECLSPEC_HIDDEN; +HRESULT gc_run(script_ctx_t*) DECLSPEC_HIDDEN; typedef struct { const WCHAR *name; @@ -149,6 +166,12 @@ typedef struct { builtin_setter_t setter; } builtin_prop_t; +enum gc_traverse_op { + GC_TRAVERSE_UNLINK, + GC_TRAVERSE_SPECULATIVELY, + GC_TRAVERSE +}; + typedef struct { jsclass_t class; builtin_invoke_t call; @@ -159,6 +182,7 @@ typedef struct { unsigned (*idx_length)(jsdisp_t*); HRESULT (*idx_get)(jsdisp_t*,unsigned,jsval_t*); HRESULT (*idx_put)(jsdisp_t*,unsigned,jsval_t); + HRESULT (*gc_traverse)(jsdisp_t*,enum gc_traverse_op,void*); } builtin_info_t; struct jsdisp_t { @@ -166,15 +190,18 @@ struct jsdisp_t { LONG ref; + BOOLEAN extensible; + BOOLEAN gc_marked; + DWORD buf_size; DWORD prop_cnt; dispex_prop_t *props; script_ctx_t *ctx; - BOOL extensible; jsdisp_t *prototype; const builtin_info_t *builtin_info; + struct list entry; }; static inline IDispatch *to_disp(jsdisp_t *jsdisp) @@ -350,6 +377,7 @@ struct _script_ctx_t { struct _call_frame_t *call_ctx; struct list named_items; + struct list objects; IActiveScriptSite *site; IInternetHostSecurityManager *secmgr; DWORD safeopt; @@ -461,6 +489,48 @@ static inline DWORD make_grfdex(script_ctx_t *ctx, DWORD flags) return ((ctx->version & 0xff) << 28) | flags; } +/* + * During unlinking (GC_TRAVERSE_UNLINK), it is important that we unlink *all* linked objects from the + * object, to be certain that releasing the object later will not release any other objects. Otherwise + * calculating the "next" object in the list becomes impossible and can lead to already freed objects. + */ +static inline HRESULT gc_process_linked_obj(jsdisp_t *obj, jsdisp_t *link, void **unlink_ref, enum gc_traverse_op op, void *arg) +{ + if(op == GC_TRAVERSE_UNLINK) { + *unlink_ref = NULL; + jsdisp_release(link); + return S_OK; + } + + if(link->ctx != obj->ctx) + return S_OK; + if(op == GC_TRAVERSE_SPECULATIVELY) + link->ref--; + else if(link->gc_marked) + return heap_stack_push(arg, link); + return S_OK; +} + +static inline HRESULT gc_process_linked_val(jsdisp_t *obj, jsval_t *link, enum gc_traverse_op op, void *arg) +{ + jsdisp_t *jsdisp; + + if(op == GC_TRAVERSE_UNLINK) { + jsval_t val = *link; + *link = jsval_undefined(); + jsval_release(val); + return S_OK; + } + + if(!is_object_instance(*link) || !(jsdisp = to_jsdisp(get_object(*link))) || jsdisp->ctx != obj->ctx) + return S_OK; + if(op == GC_TRAVERSE_SPECULATIVELY) + jsdisp->ref--; + else if(jsdisp->gc_marked) + return heap_stack_push(arg, jsdisp); + return S_OK; +} + #define FACILITY_JSCRIPT 10 #define MAKE_JSERROR(code) MAKE_HRESULT(SEVERITY_ERROR, FACILITY_JSCRIPT, code) diff --git a/dlls/jscript/jsregexp.c b/dlls/jscript/jsregexp.c index 1cbc828ce09..7c5d8964cc6 100644 --- a/dlls/jscript/jsregexp.c +++ b/dlls/jscript/jsregexp.c @@ -548,6 +548,11 @@ static void RegExp_destructor(jsdisp_t *dispex) free(This); } +static HRESULT RegExp_gc_traverse(jsdisp_t *dispex, enum gc_traverse_op op, void *arg) +{ + return gc_process_linked_val(dispex, ®exp_from_jsdisp(dispex)->last_index_val, op, arg); +} + static const builtin_prop_t RegExp_props[] = { {L"exec", RegExp_exec, PROPF_METHOD|1}, {L"global", NULL,0, RegExp_get_global}, @@ -565,7 +570,11 @@ static const builtin_info_t RegExp_info = { ARRAY_SIZE(RegExp_props), RegExp_props, RegExp_destructor, - NULL + NULL, + NULL, + NULL, + NULL, + RegExp_gc_traverse }; static const builtin_prop_t RegExpInst_props[] = { @@ -582,7 +591,11 @@ static const builtin_info_t RegExpInst_info = { ARRAY_SIZE(RegExpInst_props), RegExpInst_props, RegExp_destructor, - NULL + NULL, + NULL, + NULL, + NULL, + RegExp_gc_traverse }; static HRESULT alloc_regexp(script_ctx_t *ctx, jsstr_t *str, jsdisp_t *object_prototype, RegExpInstance **ret) diff --git a/dlls/jscript/jsutils.c b/dlls/jscript/jsutils.c index 8c1eedf4283..42cf44ab81d 100644 --- a/dlls/jscript/jsutils.c +++ b/dlls/jscript/jsutils.c @@ -179,6 +179,44 @@ heap_pool_t *heap_pool_mark(heap_pool_t *heap) return heap; } +struct heap_stack_chunk { + void *data[1020]; + struct heap_stack_chunk *prev; +}; + +HRESULT heap_stack_push(struct heap_stack *heap_stack, void *value) +{ + if(!heap_stack->idx) { + if(heap_stack->next) + heap_stack->chunk = heap_stack->next; + else { + struct heap_stack_chunk *prev, *tmp = malloc(sizeof(*tmp)); + if(!tmp) + return E_OUTOFMEMORY; + prev = heap_stack->chunk; + heap_stack->chunk = tmp; + heap_stack->chunk->prev = prev; + } + heap_stack->idx = ARRAY_SIZE(heap_stack->chunk->data); + heap_stack->next = NULL; + } + heap_stack->chunk->data[--heap_stack->idx] = value; + return S_OK; +} + +void *heap_stack_pop(struct heap_stack *heap_stack) +{ + void *ret = heap_stack->chunk->data[heap_stack->idx]; + + if(++heap_stack->idx == ARRAY_SIZE(heap_stack->chunk->data)) { + free(heap_stack->next); + heap_stack->next = heap_stack->chunk; + heap_stack->chunk = heap_stack->chunk->prev; + heap_stack->idx = 0; + } + return ret; +} + void jsval_release(jsval_t val) { switch(jsval_type(val)) { diff --git a/dlls/jscript/set.c b/dlls/jscript/set.c index 535ecdc49a4..3389d914ecf 100644 --- a/dlls/jscript/set.c +++ b/dlls/jscript/set.c @@ -362,6 +362,31 @@ static void Map_destructor(jsdisp_t *dispex) free(map); } + +static HRESULT Map_gc_traverse(jsdisp_t *dispex, enum gc_traverse_op op, void *arg) +{ + MapInstance *map = (MapInstance*)dispex; + struct jsval_map_entry *entry, *entry2; + HRESULT hres; + + if(op == GC_TRAVERSE_UNLINK) { + LIST_FOR_EACH_ENTRY_SAFE(entry, entry2, &map->entries, struct jsval_map_entry, list_entry) + release_map_entry(entry); + wine_rb_destroy(&map->map, NULL, NULL); + return S_OK; + } + + LIST_FOR_EACH_ENTRY(entry, &map->entries, struct jsval_map_entry, list_entry) { + hres = gc_process_linked_val(dispex, &entry->key, op, arg); + if(FAILED(hres)) + return hres; + hres = gc_process_linked_val(dispex, &entry->value, op, arg); + if(FAILED(hres)) + return hres; + } + return S_OK; +} + static const builtin_prop_t Map_prototype_props[] = { {L"clear", Map_clear, PROPF_METHOD}, {L"delete" , Map_delete, PROPF_METHOD|1}, @@ -390,7 +415,11 @@ static const builtin_info_t Map_info = { ARRAY_SIZE(Map_props), Map_props, Map_destructor, - NULL + NULL, + NULL, + NULL, + NULL, + Map_gc_traverse }; static HRESULT Map_constructor(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv, @@ -545,7 +574,11 @@ static const builtin_info_t Set_info = { ARRAY_SIZE(Map_props), Map_props, Map_destructor, - NULL + NULL, + NULL, + NULL, + NULL, + Map_gc_traverse }; static HRESULT Set_constructor(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv, diff --git a/dlls/jscript/tests/run.c b/dlls/jscript/tests/run.c index f40ffb3a84e..d40b40801c6 100644 --- a/dlls/jscript/tests/run.c +++ b/dlls/jscript/tests/run.c @@ -3446,6 +3446,12 @@ static void test_invokeex(void) static void test_destructors(void) { + static const WCHAR cyclic_refs[] = L"(function() {\n" + "var a = {}, c = { 'a': a, 'ref': Math }, b = { 'a': a, 'c': c };\n" + "Math.ref = { 'obj': testDestrObj, 'ref': Math, 'a': a, 'b': b };\n" + "a.ref = { 'ref': Math, 'a': a }; b.ref = Math.ref;\n" + "a.self = a; b.self = b; c.self = c;\n" + "})(), true"; IActiveScript *script; VARIANT v; HRESULT hres; @@ -3461,6 +3467,18 @@ static void test_destructors(void) CHECK_CALLED(testdestrobj); IActiveScript_Release(script); + + V_VT(&v) = VT_EMPTY; + hres = parse_script_expr(cyclic_refs, &v, &script); + ok(hres == S_OK, "parse_script_expr failed: %08lx\n", hres); + ok(V_VT(&v) == VT_BOOL, "V_VT(v) = %d\n", V_VT(&v)); + + SET_EXPECT(testdestrobj); + hres = IActiveScript_SetScriptState(script, SCRIPTSTATE_UNINITIALIZED); + ok(hres == S_OK, "SetScriptState(SCRIPTSTATE_UNINITIALIZED) failed: %08lx\n", hres); + CHECK_CALLED(testdestrobj); + + IActiveScript_Release(script); } static void test_eval(void) -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1635
From: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- dlls/jscript/global.c | 5 +---- dlls/jscript/tests/run.c | 20 ++++++++++++++++++++ 2 files changed, 21 insertions(+), 4 deletions(-) diff --git a/dlls/jscript/global.c b/dlls/jscript/global.c index c0ed954230b..9dd969aa334 100644 --- a/dlls/jscript/global.c +++ b/dlls/jscript/global.c @@ -549,10 +549,7 @@ static HRESULT JSGlobal_ScriptEngineBuildVersion(script_ctx_t *ctx, jsval_t vthi static HRESULT JSGlobal_CollectGarbage(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv, jsval_t *r) { - static int once = 0; - if (!once++) - FIXME(": stub\n"); - return S_OK; + return gc_run(ctx); } static HRESULT JSGlobal_encodeURI(script_ctx_t *ctx, jsval_t vthis, WORD flags, unsigned argc, jsval_t *argv, diff --git a/dlls/jscript/tests/run.c b/dlls/jscript/tests/run.c index d40b40801c6..9f6834c9d66 100644 --- a/dlls/jscript/tests/run.c +++ b/dlls/jscript/tests/run.c @@ -3452,6 +3452,7 @@ static void test_destructors(void) "a.ref = { 'ref': Math, 'a': a }; b.ref = Math.ref;\n" "a.self = a; b.self = b; c.self = c;\n" "})(), true"; + IActiveScriptParse *parser; IActiveScript *script; VARIANT v; HRESULT hres; @@ -3479,6 +3480,25 @@ static void test_destructors(void) CHECK_CALLED(testdestrobj); IActiveScript_Release(script); + + V_VT(&v) = VT_EMPTY; + hres = parse_script_expr(cyclic_refs, &v, &script); + ok(hres == S_OK, "parse_script_expr failed: %08lx\n", hres); + ok(V_VT(&v) == VT_BOOL, "V_VT(v) = %d\n", V_VT(&v)); + + hres = IActiveScript_QueryInterface(script, &IID_IActiveScriptParse, (void**)&parser); + ok(hres == S_OK, "Could not get IActiveScriptParse: %08lx\n", hres); + + SET_EXPECT(testdestrobj); + V_VT(&v) = VT_EMPTY; + hres = IActiveScriptParse_ParseScriptText(parser, L"Math.ref = undefined, CollectGarbage(), true", + NULL, NULL, NULL, 0, 0, SCRIPTTEXT_ISEXPRESSION, &v, NULL); + ok(hres == S_OK, "ParseScriptText failed: %08lx\n", hres); + ok(V_VT(&v) == VT_BOOL, "V_VT(v) = %d\n", V_VT(&v)); + IActiveScriptParse_Release(parser); + CHECK_CALLED(testdestrobj); + + IActiveScript_Release(script); } static void test_eval(void) -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1635
From: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> Better heuristics can be used in the future. Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- dlls/jscript/dispex.c | 5 +++++ dlls/jscript/jscript.h | 1 + 2 files changed, 6 insertions(+) diff --git a/dlls/jscript/dispex.c b/dlls/jscript/dispex.c index f41008afa2d..a50787a73fe 100644 --- a/dlls/jscript/dispex.c +++ b/dlls/jscript/dispex.c @@ -878,6 +878,7 @@ HRESULT gc_run(script_ctx_t *ctx) jsdisp_release(obj); } + ctx->gc_last_tick = GetTickCount(); return S_OK; unwind_pop: @@ -2061,6 +2062,10 @@ HRESULT init_dispex(jsdisp_t *dispex, script_ctx_t *ctx, const builtin_info_t *b { unsigned i; + /* FIXME: Use better heuristics to decide when to run the GC */ + if(GetTickCount() - ctx->gc_last_tick > 30000) + gc_run(ctx); + TRACE("%p (%p)\n", dispex, prototype); dispex->IDispatchEx_iface.lpVtbl = &DispatchExVtbl; diff --git a/dlls/jscript/jscript.h b/dlls/jscript/jscript.h index acdc5652a80..37fb145dfca 100644 --- a/dlls/jscript/jscript.h +++ b/dlls/jscript/jscript.h @@ -392,6 +392,7 @@ struct _script_ctx_t { jsval_t *stack; unsigned stack_top; + DWORD gc_last_tick; jsval_t acc; jsstr_t *last_match; -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1635
From: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> The 'prototype' prop of a source function is, by default, an empty object with a 'constructor' prop pointing back to the function. Currently, every source function is created in this fashion, which makes it a circular reference and thus prevents it from being freed until the Garbage Collector kicks in. The performance problem is that the function keeps a ref to the enclosing scope, and since the scope is being held by it, the engine will detach the scope, believing it to be used for the time being (until the GC cleans it). This can cause substantial performance issues for such a common case. The FFXIV Launcher, for example, leaks a large amount of such short-lived functions and the enclosing scopes. Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- dlls/jscript/function.c | 67 +++++++++++++++++++++++++++++++---------- 1 file changed, 51 insertions(+), 16 deletions(-) diff --git a/dlls/jscript/function.c b/dlls/jscript/function.c index 3b50a88eb77..53bf9911a0e 100644 --- a/dlls/jscript/function.c +++ b/dlls/jscript/function.c @@ -756,6 +756,55 @@ HRESULT create_builtin_constructor(script_ctx_t *ctx, builtin_invoke_t value_pro return S_OK; } +/* + * Create the actual prototype on demand, since it is a circular ref, which prevents the vast + * majority of functions from being released quickly, leading to unnecessary scope detach. + */ +static HRESULT InterpretedFunction_get_prototype(script_ctx_t *ctx, jsdisp_t *jsthis, jsval_t *r) +{ + jsdisp_t *prototype; + HRESULT hres; + + hres = create_object(ctx, NULL, &prototype); + if(FAILED(hres)) + return hres; + + hres = jsdisp_define_data_property(jsthis, L"prototype", PROPF_WRITABLE, jsval_obj(prototype)); + if(SUCCEEDED(hres)) + hres = set_constructor_prop(ctx, jsthis, prototype); + if(FAILED(hres)) { + jsdisp_release(prototype); + return hres; + } + + *r = jsval_obj(prototype); + return S_OK; +} + +static HRESULT InterpretedFunction_set_prototype(script_ctx_t *ctx, jsdisp_t *jsthis, jsval_t value) +{ + return jsdisp_define_data_property(jsthis, L"prototype", PROPF_WRITABLE, value); +} + +static const builtin_prop_t InterpretedFunction_props[] = { + {L"arguments", NULL, 0, Function_get_arguments}, + {L"length", NULL, 0, Function_get_length}, + {L"prototype", NULL, 0, InterpretedFunction_get_prototype, InterpretedFunction_set_prototype} +}; + +static const builtin_info_t InterpretedFunction_info = { + JSCLASS_FUNCTION, + Function_value, + ARRAY_SIZE(InterpretedFunction_props), + InterpretedFunction_props, + Function_destructor, + NULL, + NULL, + NULL, + NULL, + Function_gc_traverse +}; + static HRESULT InterpretedFunction_call(script_ctx_t *ctx, FunctionInstance *func, jsval_t vthis, unsigned flags, unsigned argc, jsval_t *argv, jsval_t *r) { @@ -848,24 +897,10 @@ HRESULT create_source_function(script_ctx_t *ctx, bytecode_t *code, function_cod scope_chain_t *scope_chain, jsdisp_t **ret) { InterpretedFunction *function; - jsdisp_t *prototype; HRESULT hres; - hres = create_object(ctx, NULL, &prototype); - if(FAILED(hres)) - return hres; - - hres = create_function(ctx, NULL, &InterpretedFunctionVtbl, sizeof(InterpretedFunction), PROPF_CONSTR, - FALSE, NULL, (void**)&function); - if(SUCCEEDED(hres)) { - hres = jsdisp_define_data_property(&function->function.dispex, L"prototype", PROPF_WRITABLE, - jsval_obj(prototype)); - if(SUCCEEDED(hres)) - hres = set_constructor_prop(ctx, &function->function.dispex, prototype); - if(FAILED(hres)) - jsdisp_release(&function->function.dispex); - } - jsdisp_release(prototype); + hres = create_function(ctx, &InterpretedFunction_info, &InterpretedFunctionVtbl, sizeof(InterpretedFunction), + PROPF_CONSTR, FALSE, NULL, (void**)&function); if(FAILED(hres)) return hres; -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1635
I just realized that the bytecode held by the function doesn't actually hold a ref to the script_obj at all. It holds a ref to the named item, but that doesn't hold a ref to the script_obj, and it's ref-counted for the typeinfo (and only its name is needed, that's what's refcounted). So I slightly simplified the interpreted functions to only deal with scopes now since releasing them won't release the script_obj so there's no need to handle it. I also have an idea how to fix the scopes not being collected right now, in `InterpretedFunction_gc_traverse`, which can then simplify it to a couple of lines. But it needs some changes to the scope_chain_t so that it is wrapped in a dummy jsdisp, so I'll keep that for another MR. I will add tests for that too, of course. Anyway just wanted to mention that the `FIXME` there is temporary! -- https://gitlab.winehq.org/wine/wine/-/merge_requests/1635#note_18586
I also have an idea how to fix the scopes not being collected right now, in `InterpretedFunction_gc_traverse`, which can then simplify it to a couple of lines. But it needs some changes to the scope_chain_t so that it is wrapped in a dummy jsdisp, so I'll keep that for another MR. I will add tests for that too, of course. Anyway just wanted to mention that the `FIXME` there is temporary!
A dummy jsdisp sounds worrying and handling things like scopes is an important part of GC, so I'd rather wait and see the whole thing. I'd expect that abstracting "GC thing" instead of binding it so tight to jsdisp_t would be better, especially with Gecko CC integration on the horizon. See how `note_cc_edge()` works, for example. I'm also not sure if you need to modify object refs in GC and restoring them later is needed. You could, for example, store count of noted references to the object in GC and later compare object's ref count to noted ref count. If it's equal, you know you may unlink it. This would avoid modifying objects until we know if we want to unlink them or not. -- https://gitlab.winehq.org/wine/wine/-/merge_requests/1635#note_18624
On Mon Dec 5 15:03:29 2022 +0000, Jacek Caban wrote:
I also have an idea how to fix the scopes not being collected right now, in `InterpretedFunction_gc_traverse`, which can then simplify it to a couple of lines. But it needs some changes to the scope_chain_t so that it is wrapped in a dummy jsdisp, so I'll keep that for another MR. I will add tests for that too, of course. Anyway just wanted to mention that the `FIXME` there is temporary! A dummy jsdisp sounds worrying and handling things like scopes is an important part of GC, so I'd rather wait and see the whole thing. I'd expect that abstracting "GC thing" instead of binding it so tight to jsdisp_t would be better, especially with Gecko CC integration on the horizon. See how `note_cc_edge()` works, for example. I'm also not sure if modifying object refs in GC and restoring them later is needed. You could, for example, store count of noted references to the object in GC and later compare object's ref count to noted ref count. If it's equal, you know you may unlink it. This would avoid modifying objects until we know if we want to unlink them or not. The problem with the noted ref count approach is that I cannot efficiently or easily map between the object and its noted refcount, which is why I'm modifying it directly. In contrast, the saved refs don't have to be randomly accessed, only as we traverse the object list to restore them…
About abstracting the GC, I think that might add management overhead or code complexity. A dummy jsdisp isn't such a big deal, but I can include it in the MR, probably at the beginning of the series so that the GC is simplified to begin with. It basically replaces the "LONG ref" field of the scope_chain_t with a `jsdisp_t` field, which provides the ref itself, and further provides the builtin vtbl that the GC will use. In the vtbl we will traverse the `scope_chain_t` properly. That's all. Note that without scope chain handling it's still correct, it will just leak. The important and necessary part is to unlink all objects during unlinking, which is implemented even without the dummy jsdisp; it must make sure that releasing the object will not release any other object, and that's what happens when the object is completely unlinked from any other ref. Failing to do the other traverse ops will just mean those objects don't get visited, which treats them as "external refs" and so will consider them immune from the gc process, hence leaking, but not crashing. But if I move that patch to the beginning it wouldn't be a problem anymore of course. I will do it since it's simpler. So to summarize: 1) I can't see a way to efficiently refcount the objects without modifying them, unless I store the gc refcount in the objects themselves as an extra field. This would somewhat simplify the `gc_run` function only, but it would waste memory on every single object. There's an alternative here as well: I can traverse the objects and restore them only at the end, instead of during the second stage. This *somewhat* simplifies it, although I still have to use chunks to avoid allocating too much contiguous memory. Do you think this is enough? 2) I think abstracting the GC would lead to more hassle than it's worth, considering that it would only help for scope_chain_t and the fix is relatively simple now. I can add that to the beginning of the patch so you can see why it's pretty simple. I'm not sure about (1) though. -- https://gitlab.winehq.org/wine/wine/-/merge_requests/1635#note_18645
participants (2)
-
Gabriel Ivăncescu -
Jacek Caban (＠jacek)