384244 - update jsdtoa with interesting pieces of more-recent dtoa

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Brian Crowder]

bug 379521 has a newer version of David Gray's dtoa.c and diffs between that and our jsdtoa.c .  We should consider integrating useful new pieces and bugfixes, where possible.

Comment 1

[Brian Crowder]

http://netlib2.cs.utk.edu/fp/changes <--- dtoa.c changelog up to 2005.

Comment 2

[Brian Crowder]

Attachment: bugzilla as a backup

Comment 3

[Brian Crowder]

I've taken out some of the memory testing stuff (maybe this should go back in at some point, but for now it's just cruft), and tried to group spidermonkey specific changes into one section.  The private memory stuff should be threadsafe now, I've seen a couple spots where changes from our old version have been made in the newer version that would indicate good bug fixes -- perhaps why our old version wasn't able to use the private memory feature.  Slow work so far, a lot of our changes are integrated throughout the code when they needn't necessarily be.  Other changes include bug fixes that we've handled one way while the author of dtoa.c has handled them another way, and some memory safety fixes that probably ought to get back upstream.

More soon.

Comment 4

[Brian Crowder]

By "memory safety" there, I mostly mean handling OOM gracefully.  Perhaps the dtoa.c folks don't care.

Comment 5

[Brian Crowder]

Attachment: Refactored harder

This builds, but has some issues and very likely introduces or fixes bugs.  Needs lots of testing and more work.  Also, dtoa.c code has a lot of weird patterns that make gcc gripe.

Comment 6

[Damon Sicore (:damons)]

Adding this to the 1.9.1 triage queue by marking this wanted1.9.1?.  If this should be a blocker, please mark accordingly.

Comment 7

[Brian Crowder]

Attachment: new rev

Comment 8

[Brian Crowder]

Attachment: checkpoint

Only about 15 test failures now, checkpointing.

Comment 9

[Brian Crowder]

Attachment: v5

This passes the testsuite and fixes a few other bugs.

Comment 10

[Brian Crowder]

Profiling this with a simplistic microbenchmark shows the new implementation to be a few percent faster than the old in non-threadsafe builds, but as much as 2x as slow in threadsafe builds.  At some point in the past of our original dtoa implementation, the locking was hoisted out of Balloc and Bfree and moved to the top-level callers.  I'll try this strategy next.

Comment 11

[Brian Crowder]

I experimented with using JSThinLock instead of PRLocks, and failed.  JSThinLocks, at least for this code, were measurably slower.

Comment 12

[Brian Crowder]

Attachment: v6

Fixing some bugs and compiler warnings.  Review request coming soon, I think.  Need to write some more tests.

Comment 13

[Brian Crowder]

Attachment: threadsafety test

This crashes my v6 patch.  Researching now.

Comment 14

[Brian Crowder]

Attachment: v7

This fixes the thread-safety issue found by the testcase in 329108, and also corrects some 64-bit violations discovered while testing under valgrind on a 64-bit linux box.

Comment 15

[Brian Crowder]

It's worth noting that dtoa initialization happens explicitly at runtime creation in the v7 patch, and that we no longer follow the weird unbalanced, and less-threadsafe technique used in the previous dtoa code.  This technique still isn't wholly threadsafe, but we already require that runtimes are created serially, as I understand it.

Comment 16

[Brian Crowder]

Comment on attachment 329154 [details] [diff] [review]
v7

I'm feeling pretty good about the state of this code, now.  Mind giving it a gander?  I'll upload a diff of js/src/dtoa.c versus the base one next.

Comment 17

[Brian Crowder]

Attachment: the delta between David Gay's dtoa.c and ours

For posterity and review purposes, these are the changes I made against the "shipping" dtoa.c module.

Comment 18

[Brian Crowder]

Attachment: with context

Woops, how about I share some context?

Comment 19

[Brian Crowder]

Most of my changes quell compiler warnings, two functions are made "static" so that they can be inlined, and don't pollute linker symbols.  Perhaps I should explicitly require inlining, but I don't think it is a significant cost here.

Comment 20

[Brian Crowder]

Philosophically what I've done here is included dtoa.c in jsdtoa.cpp, instead of munging it directly (at least, as much as possible).  I am telling dtoa.c via preprocessor macros that it should consider itself single-threaded.  I do this so that the coarse-grained locking used in the old jsdtoa.c code can be maintained -- it is vastly faster than the fine-grained locking used in Balloc and Bfree when lock macros are provided.  The end result should be the same level of threadsafety and an identical locking scheme.

Comment 21

[Brian Crowder]

Comment on attachment 329154 [details] [diff] [review]
v7

Igor:  I'd appreciate your thoughts on this also.  Here's the hint I gave mrbkap on IRC:

16:40 < mrbkap> crowder: Is there anything in particular I should be reviewing in that giant patch?
16:41 < crowder> mrbkap: Ignore the giant file removal/add (basically took dtoa.c out of jsdtoa.cpp and made it its own file)
16:41 < crowder> Review the rest
16:41 < crowder> and feel free to look at the deltas between dtoa.c and David Gay's dtoa.c
16:41 < crowder> mrbkap: If you're feeling naughty, you could eyeball the diffs between the dtoa I ripped out and the new one
16:41 < crowder> mrbkap: but it's a -lot-

Comment 22

[Brian Crowder]

Attachment: This is the "original" dtoa I worked against.

This should be useful for checkpointing/diffing against in the future, so here it is.

Comment 23

[Igor Bukanov]

Given the majority of changes are warning fixes, we should contact upstream about inclusion them there. At least the part about changing if (x = y) into if ((x = y)) should not be controversial.

Comment 24

[Brian Crowder]

Igor:  I agree, and tried contacting David Gay, but he did not reply.  I'll try again.

Comment 25

[Brendan Eich [:brendan]]

(In reply to comment #15)
> It's worth noting that dtoa initialization happens explicitly at runtime
> creation in the v7 patch, and that we no longer follow the weird unbalanced,
> and less-threadsafe technique used in the previous dtoa code.  This technique
> still isn't wholly threadsafe, but we already require that runtimes are created
> serially, as I understand it.

No, just that the first runtime be created while the embedding app is doing JS API stuff from only one thread.

/be

Comment 26

[Brian Crowder]

> No, just that the first runtime be created while the embedding app is doing JS
> API stuff from only one thread.
> 
> /be

Oh, ok.  My code should still be fine.

Comment 27

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 329154 [details] [diff] [review]
v7

It'd be nice if you could generate this with -p. As this appears to be a mq patch (not a qdiff), you *might* have to do:

[diff]
showfunc = True

in your .hgrc to get it.

>diff --git a/js/src/jsdtoa.cpp b/js/src/jsdtoa.cpp
>+void
>+js_FinishDtoa()
> {
>-    return allocationNum;
>+#ifdef JS_THREADSAFE
>+    if (_dtoainited)
>+        PR_DestroyLock(dtoalock);
>+#endif
> }

Do we allow calling JS_ShutDown multiple times? If so, it might be nice to make this:

if (_dtoainited) {
    PR_DestroyLock(dtoalock);
    dtoalock = NULL;
    _dtoainited = JS_FALSE;
}

so that the process is idempotent (as long as it's balanced).

>@@ -2784,36 +113,55 @@
> JS_FRIEND_API(char *)
> JS_dtostr(char *buffer, size_t bufferSize, JSDToStrMode mode, int precision, double d)
...
>     if (mode == DTOSTR_FIXED && (d >= 1e21 || d <= -1e21))
>-        mode = DTOSTR_STANDARD; /* Change mode here rather than below because the buffer may not be large enough to hold a large integer. */
>+        /*
>+         * Change mode here rather than below because the buffer may not be
>+         * large enough to hold a large integer.
>+         */
>+        mode = DTOSTR_STANDARD;

Nit: braces around the now-"multiline" if statement.

...
>     nDigits = numEnd - numBegin;
>+    memcpy(buffer + 2, numBegin, JS_MIN((size_t) nDigits, bufferSize - 2));

So, here you use JS_MIN...

>+    freedtoa(numBegin);
>+    UNLOCK_DTOA();
>+    numBegin = buffer + 2; /* +2 leaves space for sign and/or decimal point */
>+    numEnd = numBegin + nDigits;
>+    *numEnd = '\0';

But here, you use nDigits without checking. It seems like with the assertion above, the JS_MIN is not necessary and this is safe. If not, this could be bad.

Comment 28

[Brian Crowder]

Attachment: v8, with mrbkap's nits and -p

Comment 29

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 329512 [details] [diff] [review]
v8, with mrbkap's nits and -p

My only other question is whether JS_dtoa and friends should JS_ASSERT(_dtoainited) or otherwise protect themselves from similar errors. I don't think that we really need to, though.

Comment 30

[Brian Crowder]

Yeah, I almost put asserts in the LOCK and UNLOCK macros, but I figure that we'll get a null-pointer crash, if this system is not initialized correctly, which is as good and less code.

Comment 31

[Igor Bukanov]

I would suggest to keep the original source (patched to fix the compilation warnings) in a separated file and just include it to jsdtoa.cpp. This would make the next sync with the upstream much simpler.

Comment 32

[Brian Crowder]

That's one of the main things this patch does (as indicated in comment #20.

Comment 33

[Igor Bukanov]

Comment on attachment 329512 [details] [diff] [review]
v8, with mrbkap's nits and -p

> JS_FRIEND_API(char *)
> JS_dtostr(char *buffer, size_t bufferSize, JSDToStrMode mode, int precision, double d)
> {
>-    JS_ASSERT(bufferSize >= (size_t)(mode <= DTOSTR_STANDARD_EXPONENTIAL ? DTOSTR_STANDARD_BUFFER_SIZE :
>-            DTOSTR_VARIABLE_BUFFER_SIZE(precision)));
>+    JS_ASSERT(bufferSize >= (size_t)(mode <= DTOSTR_STANDARD_EXPONENTIAL ?
>+                                     DTOSTR_STANDARD_BUFFER_SIZE :
>+                                     DTOSTR_VARIABLE_BUFFER_SIZE(precision)));
> 

Nit: the style dictates to place ? and : before the then/else parts like in:

mode <= DTOSTR_STANDARD_EXPONENTIAL 
? DTOSTR_STANDARD_BUFFER_SIZE
: DTOSTR_VARIABLE_BUFFER_SIZE(precision)

>+    LOCK_DTOA();
>+    numBegin = dtoa(d, dtoaModes[mode], precision, &decPt, &sign, &numEnd);
>+    if (!numBegin) {
>+        UNLOCK_DTOA();
>         return 0;
>+    }
> 
>     nDigits = numEnd - numBegin;

Assert here that nDigits <= bufferSize - 2 but for the extra protection add 
if (nDigits > bufferSize - 2) {
    nDigits = bufferSize - 2;
    numEnd = numBegin + nDigits;
}

Then JS_MIN would not be necessary.


r+ is with that but if you split jsdtoa.cpp into the original and js-part, that would be very extra bonus.

Comment 34

[Brian Crowder]

Attachment: the changes igor described

Comment 35

[Brian Crowder]

Comment on attachment 330328 [details] [diff] [review]
the changes igor described

Woops, not quite.

Comment 36

[Igor Bukanov]

(In reply to comment #33)
> Assert here that nDigits <= bufferSize - 2 but for the extra protection add 
> if (nDigits > bufferSize - 2) {
>     nDigits = bufferSize - 2;
>     numEnd = numBegin + nDigits;
> }

Even better would be to return false when the assert fails. If due to a bug nDigits exceeds bufferSize - 2, then we would get an error instead of the wrong number.

Comment 37

[Igor Bukanov]

(In reply to comment #32)
> That's one of the main things this patch does (as indicated in comment #20.

Sorry for the mental blunder. That patch does the very right thing in this regard.

Comment 38

[Brian Crowder]

I have a new patch coming shortly that resolves some try server complaints.  I'll ask for another cursory review before landing.

Comment 39

[Brian Crowder]

Attachment: v9

This incorporates your suggestion about returning NULL from the buffer-overflow case, and also fixes some warnings revealed by the try-server.

Comment 40

[Igor Bukanov]

Comment on attachment 331024 [details] [diff] [review]
v9

> /* Mapping of JSDToStrMode -> js_dtoa mode */
> static const int dtoaModes[] = {
>     0,   /* DTOSTR_STANDARD */
>     0,   /* DTOSTR_STANDARD_EXPONENTIAL, */
>     3,   /* DTOSTR_FIXED, */
>     2,   /* DTOSTR_EXPONENTIAL, */
>     2};  /* DTOSTR_PRECISION */

Rhe existing nit: the size of the array element should be uint8 to minimize the bloat. Of cause, the ultimate solution is to use bit manipulation like in (0x270 >> (mode << 1)) & 3 to encode the mapping avoiding the array altogether, but that would be a maintenance hazard even with static asserts. 

> JS_FRIEND_API(char *)
> JS_dtostr(char *buffer, size_t bufferSize, JSDToStrMode mode, int precision, double d)
> {
...
>+    numBegin = dtoa(d, dtoaModes[mode], precision, &decPt, &sign, &numEnd);
>+    if (!numBegin) {
>+        UNLOCK_DTOA();
>+        return NULL;
>+    }
> 
>     nDigits = numEnd - numBegin;
>+    JS_ASSERT((size_t) nDigits <= bufferSize - 2);
>+    if ((size_t) nDigits > bufferSize - 2)
>+        return NULL;

Missing unlock here. r+ with this fixed.

Comment 41

[Brian Crowder]

Attachment: v10

This is the patch to land, with Igor's remaining suggestions implemented (thanks for the catch on the lock problem).

Comment 42

[Brian Crowder]

changeset:   16182:a5fc387c4622

Comment 43

[Brian Crowder]

Had to back this out.  :(

Comment 44

[Brian Crowder]

Attachment: v11

This fixes a json parsing bug revealed by one of the "make check" tests (shame on me for only running mochi and js/tests a million times, and overlooking those).  Since JS_strtod is now infallible, I need to do *err = 0, for cases where err is non-null.  This also should address all the compiler warnings you saw in that other bug, Igor.  Please try a local build before r+?

Comment 45

[Igor Bukanov]

Comment on attachment 331216 [details] [diff] [review]
v11

>+#define PRIVATE_mem ((PRIVATE_MEM+sizeof(double)-1)/sizeof(double))
>+static double private_mem[PRIVATE_mem], *pmem_next = private_mem;
>+#endif

>+	unsigned int len;
...
>+		len = (sizeof(Bigint) + (x-1)*sizeof(ULong) + sizeof(double) - 1)
>+			/sizeof(double);
>+		if (pmem_next - private_mem + (size_t) len <= (size_t) PRIVATE_mem) {
...
>+			rv = (Bigint*)MALLOC(len*sizeof(double));
>+#endif

My suggestion about 2 casts here was wrong. The exact warning with GCC 4.2 on Linux-64 without the casts is:

dtoa.c:519: warning: comparison between signed and unsigned integer expressions

It comes from the fact that in 

  pmem_next - private_mem + len <= PRIVATE_mem

the types are:

  double* - double* + unsigned <= size_t

where the type of PRIVATE_mem is size_t as it involves sizeof calculations. Sinve ptr* - ptr* is ptrdiff_t, we have:

  ptrdiff_t + unsigned <= size_t.

On 32 platform ptrdiff_t is int and size_t is unsigned so that results in

  int + unsigned <= unsigned or unsigned <= unsigned

That does not produce any warnings. On 64 bit we have:

  long + unsigned <= size_t or long <= size_t

leading to the warning. Thus the right way to fix it is to keep the "if" as is without any casts but change the declaration of len from 

  unsigned int len;

to

  size_t len;

This is especially relevant given that len is initialized using sizeof.

With that all warnings are gone with GCC 4.2 on Linux-64. But with GCC 4.3 on 32-bit Fedora 9 (aka my laptop ;) ) when I pass explicit -Wconversion I got a another bunch:

dtoa.c:2958: warning: conversion to ‘char’ from ‘int’ may alter its value
dtoa.c:2977: warning: conversion to ‘char’ from ‘int’ may alter its value
dtoa.c:3020: warning: conversion to ‘char’ from ‘int’ may alter its value
dtoa.c:3202: warning: conversion to ‘char’ from ‘int’ may alter its value
dtoa.c:3232: warning: conversion to ‘char’ from ‘int’ may alter its value
dtoa.c:3245: warning: conversion to ‘char’ from ‘int’ may alter its value
dtoa.c:3251: warning: conversion to ‘char’ from ‘int’ may alter its value
dtoa.c:3265: warning: conversion to ‘char’ from ‘int’ may alter its value

Some of the warnings comes from assignments like 

  *s++ = '0' + (int)L 

where s is char* and L is Long, others from code like 

  *s++ = dig 

where dif is int. I guess the right way to deal with this is to change the cast from (int)L to (char)L and add use 

  *s++ = (char) dig. 

But here it seems GCC is overzealous. C++ is not Java at the end. So it is OK to ignore this int->char warnings with explicit -Wconversion.

Comment 46

[Brian Crowder]

Attachment: v12, unsigned int len = size_t len;

This seems to constitute an actual -bug- in dtoa; am I wrong?  This math seems bogus for 64-bit architectures.

Comment 47

[Brian Crowder]

Comment on attachment 331346 [details] [diff] [review]
v12, unsigned int len =  size_t len;

One more spin on review?

Comment 48

[Igor Bukanov]

(In reply to comment #46)
> This seems to constitute an actual -bug- in dtoa; am I wrong?  This math seems
> bogus for 64-bit architectures.

AFAICS there is no bug in dtoa code given the actual values of variables, but in a different setup it could be a real problem.

Comment 49

[Igor Bukanov]

Comment on attachment 331346 [details] [diff] [review]
v12, unsigned int len =  size_t len;

The patch compiles without warnings now on Linux-64 with GCC 4.2 even under -Wconversion.

Comment 50

[Brian Crowder]

One more go at landing:

changeset:   16394:222c29336422