72346 2011-11-14 19:27:12 -0800 Weak reference harvesters should run to fixpoint 2011-11-15 12:10:22 -0800 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) All All RESOLVED FIXED P2 Normal --- 72312 1 fpizlo webkit-unassigned wingo oldest_to_newest 502594 0 fpizlo 2011-11-14 19:27:12 -0800 The weak reference harvester infrastructure is intended for use with inline caches and DFG optimized code that makes weak references to objects in the JavaScript heap. But there is a special car that requires special treatment: a put_by_id transition refers to two structures, previous and next, and has the semantics of installing the 'next' structure if the previous structure was 'previous'. Consider a sequence of put_by_id transitions as follows: put_by_id empty -> a put_by_id a -> b put_by_id b -> c It may be that this is the only code that refers to structures a and b. 'empty' refers to the global empty structure. Hence, a and b are almost certainly dead during any GC, while empty and c are alive. What we want the weak reference harvester to do is keep a alive so long as empty is alive, and then keep b alive so long as a is alive. The best way to do this is to allow weak reference harvesters to mark objects, and to run them to fix point. 502596 1 115087 fpizlo 2011-11-14 19:43:26 -0800 Created attachment 115087 the patch 502659 2 fpizlo 2011-11-14 23:01:30 -0800 Landed in http://trac.webkit.org/changeset/100242 502784 3 wingo 2011-11-15 03:19:07 -0800 You have probably already seen it, but this could be tangentially relative to ES.next weak maps: http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps They propose an ephemeron-table weak map implementation, that avoids marking the values until a key is known to be alive. 503132 4 fpizlo 2011-11-15 12:10:22 -0800 (In reply to comment #3) > You have probably already seen it, but this could be tangentially relative to ES.next weak maps: > > http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps > > They propose an ephemeron-table weak map implementation, that avoids marking the values until a key is known to be alive. It is related. :-) The big question for me is whether or not it would be wise to expose the O(n^2) implementation in this patch to the wild wild web. My code should work great mainly because its uses will be limited to optimized JIT code, which constitutes a tiny fraction of the heap. Not sure what will happen with these weak map thingies. 115087 2011-11-14 19:43:26 -0800 2011-11-14 21:20:57 -0800 the patch weakfixpoint_patch_1.diff text/plain 4853 fpizlo SW5kZXg6IFNvdXJjZS9KYXZhU2NyaXB0Q29yZS9DaGFuZ2VMb2cKPT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291 cmNlL0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwkocmV2aXNpb24gMTAwMjM0KQorKysgU291cmNl L0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDIzIEBA CisyMDExLTExLTE0ICBGaWxpcCBQaXpsbyAgPGZwaXpsb0BhcHBsZS5jb20+CisKKyAgICAgICAg V2VhayByZWZlcmVuY2UgaGFydmVzdGVycyBzaG91bGQgcnVuIHRvIGZpeHBvaW50CisgICAgICAg IGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD03MjM0NgorCisgICAgICAg IFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgICogaGVhcC9IZWFwLmNwcDoK KyAgICAgICAgKEpTQzo6SGVhcDo6bWFya1Jvb3RzKToKKyAgICAgICAgKiBoZWFwL0xpc3RhYmxl SGFuZGxlci5oOgorICAgICAgICAoSlNDOjpMaXN0YWJsZUhhbmRsZXI6Om5leHQpOgorICAgICAg ICAoSlNDOjpMaXN0YWJsZUhhbmRsZXI6Okxpc3Q6OmhlYWQpOgorICAgICAgICAoSlNDOjpMaXN0 YWJsZUhhbmRsZXI6Okxpc3Q6OnJlbW92ZU5leHQpOgorICAgICAgICAoSlNDOjpMaXN0YWJsZUhh bmRsZXI6Okxpc3Q6OnJlbW92ZUFsbCk6CisgICAgICAgICogaGVhcC9NYXJrU3RhY2suY3BwOgor ICAgICAgICAoSlNDOjpNYXJrU3RhY2tUaHJlYWRTaGFyZWREYXRhOjpyZXNldCk6CisgICAgICAg IChKU0M6OlNsb3RWaXNpdG9yOjpoYXJ2ZXN0V2Vha1JlZmVyZW5jZXMpOgorICAgICAgICAqIGhl YXAvTWFya1N0YWNrLmg6CisgICAgICAgIChKU0M6Ok1hcmtTdGFjazo6aXNFbXB0eSk6CisKIDIw MTEtMTEtMTQgIE9saXZlciBIdW50ICA8b2xpdmVyQGFwcGxlLmNvbT4KIAogICAgICAgICBTdGFy dCBtaWdyYXRpbmcgdHlwZWQgYXJyYXkgaW1wbCB0eXBlcyB0byBXVEYKSW5kZXg6IFNvdXJjZS9K YXZhU2NyaXB0Q29yZS9oZWFwL0hlYXAuY3BwCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJjZS9KYXZhU2Ny aXB0Q29yZS9oZWFwL0hlYXAuY3BwCShyZXZpc2lvbiAxMDAyMjMpCisrKyBTb3VyY2UvSmF2YVNj cmlwdENvcmUvaGVhcC9IZWFwLmNwcAkod29ya2luZyBjb3B5KQpAQCAtNjg0LDEwICs2ODQsMTEg QEAgdm9pZCBIZWFwOjptYXJrUm9vdHMoYm9vbCBmdWxsR0MpCiAgICAgLy8gb3BhcXVlIHJvb3Rz IHRvIGRldGVybWluZSByZWFjaGFiaWxpdHkuCiAgICAgewogICAgICAgICBHQ1BIQVNFKFZpc2l0 aW5nV2Vha0hhbmRsZXMpOwotICAgICAgICBpbnQgbGFzdE9wYXF1ZVJvb3RDb3VudDsKLSAgICAg ICAgZG8gewotICAgICAgICAgICAgbGFzdE9wYXF1ZVJvb3RDb3VudCA9IHZpc2l0b3Iub3BhcXVl Um9vdENvdW50KCk7CisgICAgICAgIHdoaWxlICh0cnVlKSB7CiAgICAgICAgICAgICBtX2hhbmRs ZUhlYXAudmlzaXRXZWFrSGFuZGxlcyhoZWFwUm9vdFZpc2l0b3IpOworICAgICAgICAgICAgaGFy dmVzdFdlYWtSZWZlcmVuY2VzKCk7CisgICAgICAgICAgICBpZiAodmlzaXRvci5pc0VtcHR5KCkp CisgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAg UGFyYWxsZWxNb2RlRW5hYmxlciBlbmFibGVyKHZpc2l0b3IpOwogICAgICAgICAgICAgICAgIHZp c2l0b3IuZG9uYXRlQW5kRHJhaW4oKTsKQEAgLTY5NSwxNiArNjk2LDEwIEBAIHZvaWQgSGVhcDo6 bWFya1Jvb3RzKGJvb2wgZnVsbEdDKQogICAgICAgICAgICAgICAgIHZpc2l0b3IuZHJhaW5Gcm9t U2hhcmVkKFNsb3RWaXNpdG9yOjpNYXN0ZXJEcmFpbik7CiAjZW5kaWYKICAgICAgICAgICAgIH0K LSAgICAgICAgICAgIC8vIElmIHRoZSBzZXQgb2Ygb3BhcXVlIHJvb3RzIGhhcyBncm93biwgbW9y ZSB3ZWFrIGhhbmRsZXMgbWF5IGhhdmUgYmVjb21lIHJlYWNoYWJsZS4KLSAgICAgICAgfSB3aGls ZSAobGFzdE9wYXF1ZVJvb3RDb3VudCAhPSB2aXNpdG9yLm9wYXF1ZVJvb3RDb3VudCgpKTsKKyAg ICAgICAgfQogICAgIH0KICAgICBHQ0NPVU5URVIoVmlzaXRlZFZhbHVlQ291bnQsIHZpc2l0b3Iu dmlzaXRDb3VudCgpKTsKIAotICAgIHsKLSAgICAgICAgR0NQSEFTRShIYXJ2ZXN0V2Vha1JlZmVy ZW5jZXMpOwotICAgICAgICBoYXJ2ZXN0V2Vha1JlZmVyZW5jZXMoKTsKLSAgICB9Ci0KICAgICB2 aXNpdG9yLnJlc2V0KCk7CiAgICAgbV9zaGFyZWREYXRhLnJlc2V0KCk7CiAKSW5kZXg6IFNvdXJj ZS9KYXZhU2NyaXB0Q29yZS9oZWFwL0xpc3RhYmxlSGFuZGxlci5oCj09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNv dXJjZS9KYXZhU2NyaXB0Q29yZS9oZWFwL0xpc3RhYmxlSGFuZGxlci5oCShyZXZpc2lvbiAxMDAy MjMpCisrKyBTb3VyY2UvSmF2YVNjcmlwdENvcmUvaGVhcC9MaXN0YWJsZUhhbmRsZXIuaAkod29y a2luZyBjb3B5KQpAQCAtNDIsNiArNDIsMTEgQEAgcHJvdGVjdGVkOgogICAgIH0KICAgICAKICAg ICB2aXJ0dWFsIH5MaXN0YWJsZUhhbmRsZXIoKSB7IH0KKyAgICAKKyAgICBUKiBuZXh0KCkgY29u c3QKKyAgICB7CisgICAgICAgIHJldHVybiByZWludGVycHJldF9jYXN0PFQqPihtX25leHRBbmRG bGFnICYgfjEpOworICAgIH0KIAogcHJpdmF0ZToKICAgICAvLyBBbGxvdyB0aGVzZSBjbGFzc2Vz IHRvIHVzZSBMaXN0YWJsZUhhbmRsZXI6Okxpc3QuCkBAIC03MiwxNSArNzcsMjYgQEAgcHJpdmF0 ZToKICAgICAgICAgICAgIHJldHVybiAhIW1fZmlyc3Q7CiAgICAgICAgIH0KICAgICAgICAgCisg ICAgICAgIFQqIGhlYWQoKQorICAgICAgICB7CisgICAgICAgICAgICByZXR1cm4gbV9maXJzdDsK KyAgICAgICAgfQorICAgICAgICAKICAgICAgICAgVCogcmVtb3ZlTmV4dCgpCiAgICAgICAgIHsK ICAgICAgICAgICAgIFQqIGN1cnJlbnQgPSBtX2ZpcnN0OwotICAgICAgICAgICAgVCogbmV4dCA9 IHJlaW50ZXJwcmV0X2Nhc3Q8VCo+KGN1cnJlbnQtPm1fbmV4dEFuZEZsYWcgJiB+MSk7CisgICAg ICAgICAgICBUKiBuZXh0ID0gY3VycmVudC0+bmV4dCgpOwogICAgICAgICAgICAgY3VycmVudC0+ bV9uZXh0QW5kRmxhZyA9IDA7CiAgICAgICAgICAgICBtX2ZpcnN0ID0gbmV4dDsKICAgICAgICAg ICAgIHJldHVybiBjdXJyZW50OwogICAgICAgICB9CiAgICAgICAgIAorICAgICAgICB2b2lkIHJl bW92ZUFsbCgpCisgICAgICAgIHsKKyAgICAgICAgICAgIHdoaWxlIChoYXNOZXh0KCkpCisgICAg ICAgICAgICAgICAgcmVtb3ZlTmV4dCgpOworICAgICAgICB9CisgICAgICAgIAogICAgIHByaXZh dGU6CiAgICAgICAgIHZvaWQgYWRkTm90VGhyZWFkU2FmZShUKiBoYW5kbGVyKQogICAgICAgICB7 CkluZGV4OiBTb3VyY2UvSmF2YVNjcmlwdENvcmUvaGVhcC9NYXJrU3RhY2suY3BwCj09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT0KLS0tIFNvdXJjZS9KYXZhU2NyaXB0Q29yZS9oZWFwL01hcmtTdGFjay5jcHAJKHJldmlzaW9u IDEwMDIyMykKKysrIFNvdXJjZS9KYXZhU2NyaXB0Q29yZS9oZWFwL01hcmtTdGFjay5jcHAJKHdv cmtpbmcgY29weSkKQEAgLTI3MSw2ICsyNzEsOCBAQCB2b2lkIE1hcmtTdGFja1RocmVhZFNoYXJl ZERhdGE6OnJlc2V0KCkKICNlbHNlCiAgICAgQVNTRVJUKG1fb3BhcXVlUm9vdHMuaXNFbXB0eSgp KTsKICNlbmRpZgorICAgIAorICAgIG1fd2Vha1JlZmVyZW5jZUhhcnZlc3RlcnMucmVtb3ZlQWxs KCk7CiB9CiAKIHZvaWQgTWFya1N0YWNrOjpyZXNldCgpCkBAIC00NDksOCArNDUxLDggQEAgdm9p ZCBNYXJrU3RhY2s6Om1lcmdlT3BhcXVlUm9vdHMoKQogCiB2b2lkIFNsb3RWaXNpdG9yOjpoYXJ2 ZXN0V2Vha1JlZmVyZW5jZXMoKQogewotICAgIHdoaWxlIChtX3NoYXJlZC5tX3dlYWtSZWZlcmVu Y2VIYXJ2ZXN0ZXJzLmhhc05leHQoKSkKLSAgICAgICAgbV9zaGFyZWQubV93ZWFrUmVmZXJlbmNl SGFydmVzdGVycy5yZW1vdmVOZXh0KCktPnZpc2l0V2Vha1JlZmVyZW5jZXMoKnRoaXMpOworICAg IGZvciAoV2Vha1JlZmVyZW5jZUhhcnZlc3RlciogY3VycmVudCA9IG1fc2hhcmVkLm1fd2Vha1Jl ZmVyZW5jZUhhcnZlc3RlcnMuaGVhZCgpOyBjdXJyZW50OyBjdXJyZW50ID0gY3VycmVudC0+bmV4 dCgpKQorICAgICAgICBjdXJyZW50LT52aXNpdFdlYWtSZWZlcmVuY2VzKCp0aGlzKTsKIH0KIAog dm9pZCBTbG90VmlzaXRvcjo6ZmluYWxpemVVbmNvbmRpdGlvbmFsRmluYWxpemVycygpCkluZGV4 OiBTb3VyY2UvSmF2YVNjcmlwdENvcmUvaGVhcC9NYXJrU3RhY2suaAo9PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBT b3VyY2UvSmF2YVNjcmlwdENvcmUvaGVhcC9NYXJrU3RhY2suaAkocmV2aXNpb24gMTAwMjIzKQor KysgU291cmNlL0phdmFTY3JpcHRDb3JlL2hlYXAvTWFya1N0YWNrLmgJKHdvcmtpbmcgY29weSkK QEAgLTIxOSw2ICsyMTksOCBAQCBuYW1lc3BhY2UgSlNDIHsKICAgICAgICAgdm9pZCBhZGRPcGFx dWVSb290KHZvaWQqKTsKICAgICAgICAgYm9vbCBjb250YWluc09wYXF1ZVJvb3Qodm9pZCopOwog ICAgICAgICBpbnQgb3BhcXVlUm9vdENvdW50KCk7CisgICAgICAgIAorICAgICAgICBib29sIGlz RW1wdHkoKSB7IHJldHVybiBtX3N0YWNrLmlzRW1wdHkoKTsgfQogCiAgICAgICAgIHZvaWQgcmVz ZXQoKTsKIAo=