Closed Bug 519476 Opened 12 years ago Closed 12 years ago

replacing JSSTRING_DEFLATED with scanning of rt->deflatedStringCache

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: igor, Assigned: igor)

References

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(3 files, 2 obsolete files)

+++ 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.
Assignee: general → igor
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.
Attachment #429193 - Flags: review?(lw)
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.
Attachment #429199 - Flags: review?(dmandelin)
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 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 on attachment 429193 [details] [diff] [review]
part 1 - using HashMap for dependent strings

Oh yeah, r+ with these changes.
Attachment #429193 - Flags: review?(lw) → review+
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.
Attachment #429193 - Attachment is obsolete: true
Attachment #429562 - Flags: review?(jwalden+bmo)
Attachment #429199 - Attachment is obsolete: true
Attachment #429564 - Flags: review?(dmandelin)
Attachment #429199 - Flags: review?(dmandelin)
Attachment #429564 - Attachment is patch: true
Attachment #429564 - Attachment mime type: application/octet-stream → text/plain
Attachment #429564 - Flags: review?(dmandelin) → review+
jwalden+bmo: review ping
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...
Attachment #429562 - Flags: review?(jwalden+bmo) → review+
(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.
(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.
https://hg.mozilla.org/tracemonkey/rev/0b28c109c213
Whiteboard: fixed-in-tracemonkey
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
(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
(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?
Blocks: 552265
(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.
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)
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.
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.
Attachment #432752 - Attachment is patch: true
Attachment #432752 - Attachment mime type: application/octet-stream → text/plain
Attachment #432752 - Flags: review+
Confirmed working with the MSVC runtime as well -- thanks!
https://hg.mozilla.org/mozilla-central/rev/636836c65832
Status: NEW → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Depends on: 563326
You need to log in before you can comment on or make changes to this bug.