Open JoshEngebretson opened 9 years ago
I'm not a contributor to Duktape, but I've needed a similar thing.
Regarding implementation details, a simple way of doing it is to have a way to obtain the pointer to a Duktape object (and also push such a pointer onto the stack; both as a weak, and as a strong ref).
Then, the task of "cleaning up" dangling pointers goes to the user (which simplifies the implementation Duktape-side). The user would use finalizers to clean up the weak refs (which would exist in exactly one place: the array holding them). It is also more flexible that way, though it could be a bit more error-prone (what if one forgets to clean up a pointer?).
Basically, an API which offers very few safety guarantees, but can be useful. I can write up a small (user-side) example of how such an API would look like, if desired.
Weak references are clearly useful and I'd also like Duktape to offer them, but that probably won't happen in the near future (at least until Duktape 2.x).
There are several alternatives to support them. I haven't had time to investigate the options in detail, but probably something like:
There was some IRC discussion on a simple mark-and-sweep based mechanism which doesn't need changes to refcounting or to heap headers to find weak references pointing to an object about to be swept. The prototype is here:
I didn't have time to test it much so it may be buggy.
Some detail on the changes:
duk_set_weak(ctx, obj)
to set an object weak (there is no reverse operation), and its Ecmascript counterpart Duktape.weak(obj)
.The prototype has several limitations:
The usage for this weak reference model is illustrated by the test cases:
We could avoid a custom weak reference mechanism and implement ES6 WeakMap directly:
The WeakMap objects have object keys (instead of string keys) so this requires a bit more work than just flagging a duk_hobject
weak. On the other hand, ES6 map objects will be needed anyway at some point.
I think the ES6 WeakMap is the way to go. In the meantime, there's a tiny amount of stuff needed to expose duk_get_tval() which allows me to directly look at the script reference count ;)
The downside of going with WeakMap is that it's going to take longer to implement - it needs a new internal data structure and it probably makes sense to implement Map and Set at the same time (or at least make sure they'll fit in later well).
I don't see how duk_tval
could be exposed because it's pretty arcane and changes even between compatible versions :) Peeking a refcount would be of course be possible (though refcounts are not necessarily enabled at all).
This isn't optimal, however it should be quite fast and fit the purpose. If the refcount is 1, I know it is only in the lookup object. In order to get the refcount, it isn't very exotic. This is all that is needed:
// exposed from duktape internals
struct duk_heaphdr {
duk_uint32_t h_flags;
duk_size_t h_refcount;
duk_heaphdr *h_next;
duk_heaphdr *h_prev;
};
typedef struct duk_tval_struct duk_tval;
struct duk_tval_struct {
duk_small_uint_t t;
duk_heaphdr *heaphdr;
};
// need to mark this as not internal for linkage in duktape.c
extern duk_tval *duk_get_tval(duk_context *ctx, duk_idx_t index);
It is so great to be able to dig into some duktape internals... part of the strength of having such a tight JS implementation. Thanks Sami!
Edit: I realize this isn't general purpose... so, I do know that ref counts are enebled :+1:
That looks dangerous, but as long as you're aware of it that's OK :) All of those structs are dependent on the platform and compilation options: for 32-bit environments the duk_tval
is packed to 8 bytes and maps into the IEEE double NaN space; duk_heaphdr
fields depend on GC options and are also different in the upcoming low memory stuff.
If refcount is all you need, would this be good enough?
duk_uint_t duk_get_refcount(duk_context *ctx, duk_idx_t index);
As a sidenote, ideally this would be a macro that would just look into the internals directly so that there'd be no footprint impact and the operation would be very efficient. However, at the moment the public duktape.h
doesn't have the internal struct definitions so public API calls/macros can't peek into the internal structures. I plan to change this when the feature detection is reworked, so that more API calls can be implemented as macros.
Oh yeah, it is plenty dangerous. I will only be using this as long as strictly necessary :)
Hm, I think getting the refcount in that way could be handy. Though, I don't know of a Lua parallel, which makes me think that refcounts should probably remain hidden. This is really the domain of weak references, the refcount is probably only useful in this very limited use case.
I needed limited support for weak references to implement Workers on top of pthreads with a Duktape heap / context for each worker (you want to GC workers once the Worker object is no longer reachable and it has an empty message queue and is paused, otherwise you have problems with the thing that needs to handle replies having disappeared).
For this specific case, I know that I need precisely one weak reference to each object (and I know where it is - in an array in the heap stash), so I can simply iterate over the array once replacing each object pointer with a bare pointer (the heapptr value for the object), then invoke the GC twice, and in the finalizer for the object have it replace the value in the array with undef. Finally, iterate over the array again, remove any undef values and replace each pointer value with a heapptr.
You can implement something more general entirely with the current code by making sure that your WeakMap objects are all visible from somewhere and periodically (e.g. on each 100th insertion or removal into a map) doing the same trick, but wrapping the finalizer of the objects in the maps with one that removes it.
Ideally, this would be integrated with the GC. The simplest method is to add a weak ref count for each object and, once its strong ref count reaches 0 run its finalizer (and remove all of its properties) but don't actually delete it. On each get prop of a weak property, check the strong ref count and if it's zero then remove the reference (you also need to increment it to make sure that you materialise a strong reference from the weak one and temporary refs still count as valid) and decrement the weak ref count, then finally delete the object once the weak ref count.
When tracing, you'd need to have some mechanism for having references that aren't followed. I don't have strong feelings about whether that should be at per-object or per-property granularity.
I'd recommend against exposing the refcount via the public API. Objective-C made this mistake and it's been quite problematic as we've tried to add better memory management to the language. Accessing the refcount is now deprecated.
Thinking about the discussion that ended at https://github.com/svaarala/duktape/pull/982#issuecomment-264607953, it occurs to me that internally, what is needed to support WeakMap in particular isn't really weak references but some kind of system of "half references". That is:
So if both "half references" are alive it amounts to a strong reference but if either one is severed, the other becomes a weak reference and doesn't prevent garbage collection. I can't think of any other way to feasibly implement the required GC semantics.
Just generally speaking key, value, or both could be weak references (not talking about ES6 here), see e.g. https://www.lua.org/pil/17.html.
With a more practical view, the weak references prototype which I implemented a while ago basically integrated into mark-and-sweep:
The downside of this approach is that it's only driven by mark-and-sweep so the semantics can't be made snappy. But that's also good in some ways: it allows the weakly referenced value to (usually) stick around a while and maybe be reused.
For caching (again speaking generally, outside of ES6) there are several variants of weak references; for example, one might want to postpone collection until an emergency GC happened so that a cached object (perhaps expensive to recreate) could be reused whenever possible. This is fine for fixed memory pools, but not necessarily the best approach when sharing the same allocator functions with other application code.
So there's definitely a lot of small details to figure out.
While it's probably preferable to rely on the standard ES6 WeakMap and WeakSet APIs instead of custom data structures (as in the weak reference prototype), having fine grained control over the weak reference behavior at least in the C API might be useful.
Memory management is somewhat of a special case compared to other features: non-standard features like finalizers may be very useful even if not required or supported by the standard (so few would argue that finalizers shouldn't be supported because they're non-standard). Memory management is mostly abstracted outside the standard text on purpose, and contexts vary a great deal in how memory needs to be managed.
Yeah, I was just referring to (what I perceived as) the GC requirements for ES6 WeakMap specifically. For an object which is stored solely in a WeakMap, it is reachable if and only if both the map and key are reachable. The key is weakly referenced by the WeakMap, but the value (conceptually) has a strong reference which is "split" between both the containing map and the associated key. I just thought that was interesting is all. :)
@fatcerberus: So basically WeakMap entries are (weak key, strong value)
pairs, where GCing the key removes the whole pair?
@fatcerberus I think that's quite common for weak references that reside in maps / property tables? In essence, the entry is collected as a unit. Or from another viewpoint, when the weak reference in the entry gets collected, the entry is scrubbed because it no longer needs to exist. This may then cause the strongly referenced part of the entry to get collected too (or not, if there are references elsewhere).
I find it interesting because I'm used to thinking of references in binary terms; that is, reference is either weak (0) or strong (1). But that doesn't work for thinking about weak maps, because you can cause a stored object to become unreachable in two ways:
weakmap = null;
keyObj = null;
Thus the reference graph conceptually looks something like:
map key
| |
0.5r 0.5r
v v
value
Reachability index for 'value':
1.0r (reachable)
Neither reference can be purely strong because that might prevent timely collection (depending on object lifetimes); but neither can they be purely weak because then the object might be collected prematurely. So it's an interesting situation from an implementation perspective.
By the way, I apologize if I'm being annoying here; I just find the theory behind garbage collectors very interesting for whatever reason. :)
By the way, I apologize if I'm being annoying here; I just find the theory behind garbage collectors very interesting for whatever reason. :)
Not at all - it's quite relevant discussion for understanding what Duktape needs to do.
One way to think about this conceptually is that the map entry is a (just conceptually) an object itself. The object can react to a weak key/value being collected by deleting itself from the map.
One way to think about this conceptually is that the map entry is a (just conceptually) an object itself. The object can react to a weak key/value being collected by deleting itself from the map.
Hm, I guess that works. The value is strongly referenced by the entry, which is strongly referenced by the map, but the key is only weakly referenced, so that it can be collected if not needed anywhere else. If it is, the entry then deletes itself automatically, making the value eligible for collection.
Of course that's all conceptual: As far as the concrete implementation goes, the "partial reference" setup described above seems to be the most feasible to me (maybe I'm just not using my imagination enough though). It might become a performance issue if Duktape had to go through every WeakMap/Set looking for collected keys on every GC cycle :)
Actually like I described above, the mark-and-sweep approach pretty much works like the conceptual algorithm: when a weakly referenced object is ready for collection, it is "purged" from whatever maps reference it before being freed. Of course there are several variations on how to do that but the basic approach is like this.
Note that Duktape needs to walk every property table on every mark-and-sweep regardless of weak references. It's then just a matter of doing it again in the sweep cycle - preferably with a fast path which avoids the process if not weak objects are collected. For example, start sweeping and if a weakly referenced object is about to be swept, then purge all objects from any weak references (not just the one encountered) and then finish the sweep phase.
But there are of course many variations to this approach. One approach is to leave the objects in place and sweep them in the next mark cycle unless someone made a strong reference to them again. How to detect that efficiently has some practical questions of course. Another is to leave them in place but ignore the property entries if they're looked up (i.e. pretend they don't exist) and collect them in the next mark cycle.
Anyway, it occurs to me that duk_get_heapptr()
is already a kind of weak reference, the only problem is that it's unsafe (if the object gets collected, it's just a dangling pointer). It might be possible to piggyback on the mark-and-sweep algorithm to determine whether a heap allocation is still valid; the only problem is if the allocator reuses the same address for a new object (which may happen especially with pool allocators). So we obviously couldn't use bare pointers in a true weak reference API.
I'm not sure if the terminology is 100% standardized but Duktape internals use the term "borrowed reference" for duk_get_heapptr()
. It's not a weak reference as such because the reference is entirely invisible to Duktape. At least I would expect a weak reference to be visible to the GC and have some special handling.
It might be possible to piggyback on the mark-and-sweep algorithm to determine whether a heap allocation is still valid.
This is IMO very much infeasible in practice exactly because you would need to guarantee that the address is not reused, potentially indefinitely, which essentially means that the memory can never be freed safely.
Hm, I guess the only special handling would be "if you have a weak reference and try to use it after the referenced object is otherwise unreachable, you get an error". Borrowed references are kind of the same thing--it's just that the error is "segfaulting your application" :)
I'm not sure what special handling is needed beyond that in the general case (for weak maps, etc. of course you have the automatic scrubbing and such, but I'm talking about the basic "weak reference" primitive itself).
Regarding this:
This is IMO very much infeasible in practice exactly because you would need to guarantee that the address is not reused, potentially indefinitely, which essentially means that the memory can never be freed safely.
Yes, I agree. You can't use bare pointers to implement real weak references in the C API - you'd need some sort of handle system instead.
So we obviously couldn't use bare pointers in a true weak reference API.
The minimal baseline would be implementing the ES6 WeakMap/WeakSet, and implementing a similar C API. In those APIs the references themselves would be held by the data structures and you wouldn't hold a weak reference yourself. For example, when you look up a weakly referenced value, the lookup result becomes strongly referenced until you're done with it and the value stack entry is unwound. This is also how weak references work for Ecmascript code - whenever outside the weak reference container they become strong references.
So I wasn't thinking about implementing any weak reference C type at least initially. But I'm probably not understanding your use case? Do you mean something like duk_get_heapptr()
but with some sort of notification when the value goes unreachable?
but I'm talking about the basic "weak reference" primitive itself [...]
This part I didn't understand - just implementing ES6 WeakMap/WeakSet doesn't lead to any need for a weak reference primitive. The weak references are only held inside the WeakMap/WeakSet data structures and the GC is aware of them. Whenever a weakly referenced value is read from the map/set, it becomes strongly referenced while it is being handled by script or C code. This is how weak references work for ES6 script code too.
But I think you're referring to some generic weak reference concept beyond the specific weak reference data structures?
I'm mostly thinking about how weak references would be implemented internally, so not any specific use case other than "how to implement this in Duktape".
As for the talk of a weak reference "primitive", I'm mostly thinking of C#'s WeakReference
:
https://msdn.microsoft.com/en-us/library/system.weakreference(v=vs.110).aspx
If you try to access the weakly referenced object after it's been GC'd, you throw an error.
Ecmascript doesn't have any analogue to this. You have WeakSet, for which you can ask "does my object exist in this set?" and WeakMap, "what value is associated with this object"? There's no way for Ecmascript code to actually hold a weak reference. However, Duktape, at least internally, would need to have such a concept I think.
Internally the most likely implementation is along the lines of the mark-and-sweep weak-reference prototype (https://github.com/svaarala/duktape/tree/weak-references): the GC would be aware of WeakMap and WeakSet specifically, and know how to treat the keys and values (weak or strong). There wouldn't be a separate weak reference value: weak references only really make sense in some container that knows how to deal with them.
It might be possible to add some kind of weak reference type with callback registration and such, but it would be quite inefficient for WeakMap/WeakSet entries to be individually tracked weak references as opposed to the whole data structure being specifically designed for weak references.
Here's the relatively old weak references prototype: https://github.com/svaarala/duktape/tree/weak-references. That doesn't implement WeakSet/WeakMap but just demonstrated how weak references would be handled by GC. In the branch each duk_hobject
can be marked weak, using Duktape.weak()
or duk_set_weak()
.
There's no way for Ecmascript code to actually hold a weak reference. However, Duktape, at least internally, would need to have such a concept I think.
It's not necessary in the mark-and-sweep approach. The data structures would just reference e.g. duk_hstring
s and duk_hobject
s. Code that looks up the values just copies the reference, does an INCREF on the value, and the value is then strongly reachable. The only places aware of the weakness are the map operations and GC, but these operations automatically know they're dealing with a weak structure and the references themselves in the C data structures don't need to be marked or "wrapped" specifically.
The prototype branch https://github.com/svaarala/duktape/compare/weak-references should make it clearer how the mark-and-sweep approach basically works -- it's a mostly functional prototype but doesn't implement the WeakSet / WeakMap API but rather allows any duk_hobject
to be made weak using Duktape.weak()
or duk_set_weak()
.
I'm not suggesting that as a solution baseline as such (it's better to implement WeakMap and WeakSet directly), but the mark-and-sweep technique should be applicable more or less as is.
I think that C#'s WeakReference would more or less map to a WeakMap with a single element? Having a data structure for holding just a single reference might be useful, but it's not a good building block to implement a map with many references (mainly because of the overhead such an approach carries).
I'm no C# expert but I guess with WeakReference you also don't directly hold a weak reference?
Rather, you hold a strong reference to the WeakReference object, which holds the weak reference for you and provides a get/set API for it. This is the same situation as with a WeakMap / WeakSet: strong reference to the holder data structure, and internal weak references that you access through an API.
I think that C#'s WeakReference would more or less map to a WeakMap with a single element?
No, because you can't enumerate the keys of a WeakMap. A WeakMap maps a key to a value - but you need to have a (strong) reference to the key to access the entry at all. WeakReference
gives you direct access to the object (through weakref.Target
) as long as it remains reachable.
So how would that differ from using a WeakMap with a fixed, globally known key?
That's easy: fixedKnownKey=>value is a strong reference. Only the key is weakly referenced.
Ok, I see what you mean.
As described in ES6+, WeakMap is useful for associating global state with an object without preventing the object from being garbage collected. They're not all that useful for, e.g. caching because the cached value itself is strongly referenced by the map.
note: WeakSet is effectively just a WeakMap which maps the keys to true/false (i.e. does it exist in the set or not?)
But in any case, the basic approach I think makes most sense is to:
I'm quite sure that the ES2015 semantics as is won't work for all (or even most) use cases because memory management is a very target specific thing. So if it makes sense, I'd like to:
Adding support for non-standard types like WeakReference seems a bit more uncomfortable, but if there's a really good use case for them, I wouldn't object to that.
Like I said above, I think memory management is one of those areas where custom C features (like finalizer support) may be useful even if it's not mandated in the specification. It's an area which the specification cannot really address in depth because it's so environment specific.
So, you do understand why I said heap pointers are effectively weak references now, yes? They map pretty closely to C# WeakReference, with the caveat that instead of throwing a catchable error, they are completely unsafe and may crash or corrupt your application if you access them postmortem ;-)
I still see them as "borrowed references" because the crucial difference is that GC is entirely unaware of them. For a reference to be weak, GC must necessarily be very much aware of its existence and deal with it specifically.
Borrowed references are of course similar to weak references in that they don't involve a reference count bump. But the similarity ends there becaues of GC involvement, which really is the defining feature of weak references IMO.
@fatcerberus I can try to update that weak-references branch to provide a very rough implementation of WeakMap, maybe next week. It might be more useful to discuss these issues with some running code.
I did look at that prototype by the way - it's actually a bit different from WeakMap because the keys are strings (or Symbols) and the values are weak references. WeakMap is the opposite (weak key, strong value). So it's a lot closer to the use case for WeakReference than any of the ES6 types.
Sure, it's different - but the mark-and-sweep technique is the same. That's the part I've been referring to.
Ah, okay. I'll shut up then, I understand now. :)
To elaborate a bit on the mark-and-sweep technique, it should be relatively easy to support weak keys, weak values, and weak keys+values simply by how the keys/values are marked. It's just a matter what positions are marked or not.
To support weak references that are collected only by emergency GC it might be possible just to treat such references as strong references when emergency GC flag is not set (so they won't be collected) and as weak references when the GC flag is set. This would allow useful cache structures to be built with very few GC changes.
One dependency that's been affecting this work a bit is the necessary data structure changes. Maps accept arbitrary keys and values (duk_tval key, duk_tval value) while WeakMaps only accept object keys (duk_hobject *key, duk_tval value). Similarly for Sets and WeakSets. In the current tagged type model each key/value type pair creates essentially a different structure with respect to memory layout and how the data structure is handled; nothing really difficult, but still some trivia to deal with.
I've been experimenting a bit with using tagged pointers (void *
) for the duk_tval
representation. In essence all values, both heap allocated and primitive, would be tagged pointers. This has a footprint and performance benefits (more natural to pass by value, etc); but also downsides like IEEE doubles becoming heap allocated. Earlier I rejected tagged pointers because of the IEEE double issue, but with Float64Array providing a fast way to manipulate IEEE double data sets (and integers being most common otherwise) it's now a potentially good option.
Coming back to weak references - one upside of tagged pointers is that both Map and WeakMap would then have (void , void ) keys and values. The only difference is that WeakMap keys would be restricted to duk_hobject
pointers whereas Map allows all pointer (and non-pointer) types. This needs some special handling, but as far as allocations, resizing, etc go, WeakMap can be treated as just a restricted Map without any footprint cost. The data structures, their resize algorithms, etc, could then be shared more naturally.
This is not of course a blocker as such, but as always it's nice to try to find an order of implementing things that minimizes mind-numbing rework ;-)
Hello,
We currently have a use case where weak references would useful.
We're using duktape to bind some C++ classes which implement reference counting. These instances can be handed over to duktape wrapped as an Object as the result of a native method call. In order to get the same object back across multiple calls, there is a lookup table held in Javascript with a pointer to instance key and the Object value. So, if the object is already wrapped, script gets back the same JS object which preserves any user added properties and saves cycles as it doesn't need to setup the object every time.
Unfortunately, the value being held in the pointer/object table means that the Object will never be finalized script side, which will never decref the native side. This could be implemented with a weak reference. I am not sure of the implementation details on this, seems like it could be hairy.