519476 - replacing JSSTRING_DEFLATED with scanning of rt->deflatedStringCache

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Igor Bukanov]

+++ This bug was initially created as a clone of Bug #517199 +++

Currently to speedup the removal of deflated string bytes for about to be finalized strings the code marks deflated strings with a special flag. The string finalizer then tries to remove the string from the deflated cache only if the flag is set.

This implies that the flag check is done once per each finalized string. With optimizations from the bug 517199 this checks starts to contribute visible cost to the string finalization. Thus we should consider replacing this check with explicit scanning of deflatedStringCache for about to be finalized strings. 

Clearly this alternative also have non-zero costs. In particular, if for a typical browser run the deflated cache contains a lot of long-living entries that survives multiple GCs, then the cost of repeatedly checking for finalized strings on those entries may be greater than the flag check. So some stats should be collected before doing any farther work.

Comment 1

[Igor Bukanov]

Attachment: part 1 - using HashMap for dependent strings

This preparation patch changed JSRuntime::deflatedStringCache to use js::HashMap for JSString* -> char* mapping. 

In the patch I made the deflatedStringCache field to have void * type to avoid putting too much string-specific stuff into jscntxt.h. Another possibility is to add the defines into jsstr.h, but that would require to include that header into jscntxt.h which I prefer not to do.

Comment 2

[Igor Bukanov]

Attachment: part 2 - replacing the deflated flag with the deflated cache sweep

The patch eliminates the deflated string flag in favor of deflated hash sweeping. This eliminates an extra if check in the string finalization. The cost is a repeated enumeration of deflated cache entries during each GC cycle. 

This extra cost should be negligible. For a browser session involving gmail, gdocs, gmaps, social networking cites and some news portals the browser generates less than 2000 long-lived deflated strings. On the other hand, as the data from the bug 548388 indicates, most strings are short-lived and eliminating an extra if check per string finalizer should be a winner here.

Comment 3

[Jeff Walden [:Waldo]]

Comment on attachment 429193 [details] [diff] [review]
part 1 - using HashMap for dependent strings

Can you just add:

namespace js { class DeflatedStringCache; }

to jscntxt.h to address the dependency pain and get type-safety?  (I don't know whether typedefs can be declared in this way or not.)  I'd rather see this typed correctly without requiring all users to cast away from void*, even if it means greater dependencies on jsstr.h bits (or maybe those could be declared in jscntxt.h too?).


>Index: tm/js/src/jsstr.cpp

>+struct DefaltedStringPtrHasher

Typo.


>+typedef HashMap<JSString *,
>+                char *,
>+                DefaltedStringPtrHasher,
>+                SystemAllocPolicy> DeflatedStringCache;
>+
>+}
>+
>+JSBool
>+js_InitDeflatedStringCache(JSRuntime *rt)
>+{
>+    /* Initialize string cache */
>+    JS_ASSERT(!rt->deflatedStringCache);
>+
>+    js::DeflatedStringCache *cache = new js::DeflatedStringCache();
>+    rt->deflatedStringCache = cache;
>+    if (!cache || !cache->init())
>+        return false;
>+
>+#ifdef JS_THREADSAFE
>+    JS_ASSERT(!rt->deflatedStringCacheLock);
>+    rt->deflatedStringCacheLock = JS_NEW_LOCK();
>+    if (!rt->deflatedStringCacheLock)
>+        return false;
>+#endif
>+    return true;
>+}

It seems like JSRuntime::initDeflatedStringCache would be better than a global method like this, ditto for finishDeflatedStringCache.

Comment 4

[Luke Wagner [:luke]]

Comment on attachment 429193 [details] [diff] [review]
part 1 - using HashMap for dependent strings

>-    JSHashTable         *deflatedStringCache;
>+    void                *deflatedStringCache;

I think we already talked about this, but were you able to use a forward declaration to make the DeflatedStringCache typedef into jscntxt.h and give this member a real type?

>+        /*
>+         * We hash only GC-allocated Strings. They are aligned on
>+         * sizeof(JSString) boundary so we can improve hashing by stripping
>+         * initial zeros.
>+         */
>+        const jsuword ALIGN_LOG = (JS_BITS_PER_WORD_LOG2 - 3) + 2;
>+        JS_STATIC_ASSERT(sizeof(JSString) == (size_t(1) << ALIGN_LOG));
>+
>+        jsuword ptr = reinterpret_cast<jsuword>(str);
>+        jsuword key = ptr >> ALIGN_LOG;

Perhaps use

  const jsuword ALIGN_LOG = tl::FloorLog2<sizeof(JSString)>::result;

instead?

>+void
>+js_PurgeDeflatedStringCache(JSRuntime *rt, JSString *str)
>+{
>+    JSHashNumber hash;
>+
>+    hash = js_hash_string_pointer(str);

I think this is deadwood.

>Index: tm/js/src/jsstr.h
>+#include "jshashtable.h"

I think you can put this in jsstr.cpp.  The HashMap forward decl in jsprvtd.h should cover you for the typedef in jscntxt.h.

Comment 5

[Luke Wagner [:luke]]

Comment on attachment 429193 [details] [diff] [review]
part 1 - using HashMap for dependent strings

Oh yeah, r+ with these changes.

Comment 6

[Igor Bukanov]

Attachment: part 1 - using HashMap for dependent strings

The new version uses the js::DeflatedStringCache class that contains both the hashtable and the lock. Among minor changes the patch also eliminates deflatedStringCacheBytes since one can get the same information enumerating the hash entries and calling strlen on values.

The bigger change is making sure that js::DeflatedStringCache::getBytes() does not call OOM reporting outside the table lock. The current code does just that violating the promise that callbacks like error reporting ones are called outside any locks.

Comment 7

[Igor Bukanov]

Attachment: part 2 - replacing the deflated flag with the deflated cache sweep

Comment 8

[Igor Bukanov]

jwalden+bmo: review ping

Comment 9

[Jeff Walden [:Waldo]]

Comment on attachment 429562 [details] [diff] [review]
part 1 - using HashMap for dependent strings

Is there a js_SweepDeflatedString function, or is the signature in jsstr.h in this or the other patch detritus?

Why does JSRuntime::deflatedStringCache need to be a pointer?  Can't it just be a direct member of JSRuntime?  Either I'm missing something, or we should make it a member and avoid an extra allocation.

I vaguely prefer you use 2048 as the literal here, given the comment's text:

>+    /*
>+     * Make room for 2K deflated strings that a typical browser session
>+     * creates.
>+     */
>+    return map.init(1 << 11);

This locking business (especially during sweeping) is sadmaking.  I imagine there's a better way with a threadsafe hash table and some care (and perhaps with JSAPI abuse smackdown), but definitely not for this bug.

Sorry for the delay...

Comment 10

[Igor Bukanov]

(In reply to comment #9)
> (From update of attachment 429562 [details] [diff] [review])
> Is there a js_SweepDeflatedString function, or is the signature in jsstr.h in
> this or the other patch detritus?
> 
> Why does JSRuntime::deflatedStringCache need to be a pointer?  Can't it just be
> a direct member of JSRuntime?  Either I'm missing something, or we should make
> it a member and avoid an extra allocation

The runtime initialization code memsets all its fields to zero. That would kill the initialization done in the hashtable constructor.

Comment 11

[Igor Bukanov]

(In reply to comment #10)
> 
> The runtime initialization code memsets all its fields to zero. That would kill
> the initialization done in the hashtable constructor.

Actually this is wrong. I have missed that this was fixed. Still there is another issue with making the the cache a field in JSRuntime. That would require either to include jsstr.h in jscntxt.h snowballing the number of changes or to move the cache into jscntxt.h meaning that its methods would need to be implemented separately as inlines.

Comment 12

[Igor Bukanov]

https://hg.mozilla.org/tracemonkey/rev/0b28c109c213

Comment 13

[Nicholas Nethercote [inactive]]

Looks like this caused the Mac "Xd" column on TBPL to get a failure?

TEST-UNEXPECTED-FAIL | /builds/slave/tracemonkey-macosx-debug-unittest-xpcshell/build/xpcshell/tests/test_places/expiration/test_pref_interval.js | true == false - See following stack:

http://tinderbox.mozilla.org/showlog.cgi?log=TraceMonkey/1268466972.1268468417.20045.gz

Comment 14

[Igor Bukanov]

(In reply to comment #13)
> Looks like this caused the Mac "Xd" column on TBPL to get a failure?
> 
> TEST-UNEXPECTED-FAIL |
> /builds/slave/tracemonkey-macosx-debug-unittest-xpcshell/build/xpcshell/tests/test_places/expiration/test_pref_interval.js
> | true == false - See following stack:
> 
> http://tinderbox.mozilla.org/showlog.cgi?log=TraceMonkey/1268466972.1268468417.20045.gz

There is a time dependency in the test as it assumes AFAICS that some action will happen within the given time. In principle that may not be true on a very busy box. Given that and that the test has passed on Linux and Windows I have forced tinderbox restart via whitespace-only change: http://hg.mozilla.org/tracemonkey/rev/561f1938366f

Comment 15

[Jeff Walden [:Waldo]]

(In reply to comment #11)
> Actually this is wrong. I have missed that this was fixed. Still there is
> another issue with making the the cache a field in JSRuntime. That would
> require either to include jsstr.h in jscntxt.h snowballing the number of
> changes or to move the cache into jscntxt.h meaning that its methods would need
> to be implemented separately as inlines.

I think we've long since crossed the jsfooinline.h bridge; can you do the latter as a followup?

Comment 16

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

(In reply to comment #12)
> https://hg.mozilla.org/tracemonkey/rev/0b28c109c213

This is causing MSVC runtime assertion failures at free() -- specifically "CRT detected that the application wrote to memory after end of heap buffer", which makes me think that something in this patch is overwriting or twiddling the CRT's sentinel values.  Confirmed via local backout; I couldn't reproduce this with a simple non-threadsafe shell build, but a js shell built as part of the full browser spams CRT errors on any of the js tests.

Comment 17

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Backed out 0b28c:

http://hg.mozilla.org/tracemonkey/rev/22f52049c651

Comment 18

[Julian Seward [:jseward]]

Possibly relevant?

(2) ==9647== Command: ../../../ff-opt/js/src/shell/js -j -f ./shell.js -f ./js1_8_5/shell.js -f ./js1_8_5/extensions/shell.js -f ./js1_8_5/extensions/typedarray.js -f ./js-test-driver-end.js
(2) ==9647== 
(2) ==9647== Invalid write of size 8
(2) ==9647==    at 0x49814D: js::DeflatedStringCache::sweep(JSContext*) (jsgc.h:371)
(2) ==9647==    by 0x441AA2: js_GC (jsgc.cpp:3197)
(2) ==9647==    by 0x41EBA1: js_DestroyContext(JSContext*, JSDestroyContextMode) (jscntxt.cpp:804)
(2) ==9647==    by 0x40F8DF: JS_DestroyContext (jsapi.cpp:912)
(2) ==9647==    by 0x407D3A: main (js.cpp:4924)
(2) ==9647==  Address 0x66e3ff0 is 0 bytes inside a block of size 1 alloc'd
(2) ==9647==    at 0x4C25528: malloc (vg_replace_malloc.c:236)
(2) ==9647==    by 0x60AA1A1: strdup (strdup.c:43)
(2) ==9647==    by 0x4071B7: Options(JSContext*, JSObject*, unsigned int, long*, long*) (js.cpp:911)
(2) ==9647==    by 0x445790: js_Invoke (jsinterp.cpp:1364)
(2) ==9647==    by 0x4F2BDE: js_Interpret (jsops.cpp:2273)
(2) ==9647==    by 0x445024: js_Execute (jsinterp.cpp:1660)
(2) ==9647==    by 0x40CE64: JS_ExecuteScript (jsapi.cpp:4809)
(2) ==9647==    by 0x407908: Process(JSContext*, JSObject*, char*, int) (js.cpp:447)
(2) ==9647==    by 0x40815C: main (js.cpp:792)
(2) ==9647== 
(2) ==9647== Thread 2:
(2) ==9647== Invalid read of size 8
(2) ==9647==    at 0x44319F: JSFreePointerListTask::run() (jsgc.h:378)
(2) ==9647==    by 0x4A0D57: JSBackgroundThread::work() (jstask.cpp:96)
(2) ==9647==    by 0x4A0D8E: start(void*) (jstask.cpp:43)
(2) ==9647==    by 0x5476AF4: _pt_root (ptthread.c:228)
(2) ==9647==    by 0x4E31A03: start_thread (pthread_create.c:300)
(2) ==9647==    by 0x610A80C: clone (clone.S:112)
(2) ==9647==  Address 0x66e4900 is 0 bytes inside a block of size 1 alloc'd
(2) ==9647==    at 0x4C25528: malloc (vg_replace_malloc.c:236)
(2) ==9647==    by 0x60AA1A1: strdup (strdup.c:43)
(2) ==9647==    by 0x4071B7: Options(JSContext*, JSObject*, unsigned int, long*, long*) (js.cpp:911)
(2) ==9647==    by 0x445790: js_Invoke (jsinterp.cpp:1364)
(2) ==9647==    by 0x4F2BDE: js_Interpret (jsops.cpp:2273)
(2) ==9647==    by 0x445024: js_Execute (jsinterp.cpp:1660)
(2) ==9647==    by 0x40CE64: JS_ExecuteScript (jsapi.cpp:4809)
(2) ==9647==    by 0x407908: Process(JSContext*, JSObject*, char*, int) (js.cpp:447)
(2) ==9647==    by 0x40815C: main (js.cpp:792)

Comment 19

[Julian Seward [:jseward]]

Given the invalid reads & write of size 8 (pointer-sized) on a
block of size 1 (the ""), perhaps it's a confusion between the
string and a pointer to it.

Comment 20

[Igor Bukanov]

The bug can also be triggered on Linux with JS_THREADSAFE shell if one sets the MALLOC_CHECK_ environment variable to 2 when running the shell:

~/m/tm/js/src/tests> MALLOC_CHECK_=2 ~/build/js/tdbg/js -f ./shell.js
Aborted (core dumped)

The reason for this is that the patch has switched the deflated string byte deallocation code to use cx->free. That implies that the memory holding bytes will be put initially to the free list that is to be freed later on the background thread. This requires that all allocations must be at least a word in size. This is what cx->malloc ensures.

But the bytes may not be allocated via cx->malloc(). This happens when the application calls JS_NewString(JSContext *cx, char *bytes, size_t len). In this case the deflated string bytes is set to what the application has passed to the function. This is exactly what happens with the example above. There the shell Option function uses strdup to get the malloced bytes. Surely enough that may allocate just single byte leading to the bug.

I will fix this via switching the bytes release code to use js_free as before.

Comment 21

[Igor Bukanov]

Attachment: full patch with the issue from the comment 16 fixed

Comment 22

[Igor Bukanov]

relanded - https://hg.mozilla.org/tracemonkey/rev/636836c65832

Comment 23

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Confirmed working with the MSVC runtime as well -- thanks!

Comment 24

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/0b28c109c213

Comment 25

[Robert Sayre]

https://hg.mozilla.org/mozilla-central/rev/636836c65832