Closed Bug 384244 Opened 13 years ago Closed 11 years ago

update jsdtoa with interesting pieces of more-recent dtoa

Categories

(Core :: JavaScript Engine, defect, P2)

defect

Tracking

()

RESOLVED FIXED

People

(Reporter: crowderbt, Assigned: crowderbt)

References

Details

Attachments

(4 files, 13 obsolete files)

279 bytes, patch
Details | Diff | Splinter Review
8.51 KB, patch
Details | Diff | Splinter Review
66.89 KB, text/plain
Details
158.97 KB, patch
igor
: review+
Details | Diff | Splinter Review
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.
Blocks: 156253
Assignee: general → crowder
Status: NEW → ASSIGNED
http://netlib2.cs.utk.edu/fp/changes <--- dtoa.c changelog up to 2005.
Blocks: 350936
Attached patch bugzilla as a backup (obsolete) — Splinter Review
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.
By "memory safety" there, I mostly mean handling OOM gracefully.  Perhaps the dtoa.c folks don't care.
Attached patch Refactored harder (obsolete) — Splinter Review
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.
Attachment #271553 - Attachment is obsolete: true
Alias: dtoa
Adding this to the 1.9.1 triage queue by marking this wanted1.9.1?.  If this should be a blocker, please mark accordingly.
Flags: wanted1.9.1?
Priority: -- → P2
Attached patch new rev (obsolete) — Splinter Review
Attachment #323164 - Attachment is obsolete: true
Attached patch checkpoint (obsolete) — Splinter Review
Only about 15 test failures now, checkpointing.
Attachment #324297 - Attachment is obsolete: true
Flags: wanted1.9.1? → wanted1.9.1+
Attached patch v5 (obsolete) — Splinter Review
This passes the testsuite and fixes a few other bugs.
Attachment #325325 - Attachment is obsolete: true
Attachment #326817 - Attachment description: v4 → v5
Attachment #326817 - Attachment is patch: true
Attachment #326817 - Attachment mime type: application/octet-stream → text/plain
Blocks: 338756
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.
I experimented with using JSThinLock instead of PRLocks, and failed.  JSThinLocks, at least for this code, were measurably slower.
Attached patch v6 (obsolete) — Splinter Review
Fixing some bugs and compiler warnings.  Review request coming soon, I think.  Need to write some more tests.
Attachment #326817 - Attachment is obsolete: true
This crashes my v6 patch.  Researching now.
Attached patch v7 (obsolete) — Splinter Review
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.
Attachment #328925 - Attachment is obsolete: true
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 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.
Attachment #329154 - Flags: review?(mrbkap)
For posterity and review purposes, these are the changes I made against the "shipping" dtoa.c module.
Attached patch with contextSplinter Review
Woops, how about I share some context?
Attachment #329155 - Attachment is obsolete: true
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.
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 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-
Attachment #329154 - Flags: review?(igor)
This should be useful for checkpointing/diffing against in the future, so here it is.
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.
Igor:  I agree, and tried contacting David Gay, but he did not reply.  I'll try again.
(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
> 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 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.
Attached patch v8, with mrbkap's nits and -p (obsolete) — Splinter Review
Attachment #329154 - Attachment is obsolete: true
Attachment #329154 - Flags: review?(mrbkap)
Attachment #329154 - Flags: review?(igor)
Attachment #329512 - Flags: review?(mrbkap)
Attachment #329512 - Flags: review?(igor)
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.
Attachment #329512 - Flags: review?(mrbkap) → review+
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.
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.
That's one of the main things this patch does (as indicated in comment #20.
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.
Attached patch the changes igor described (obsolete) — Splinter Review
Comment on attachment 330328 [details] [diff] [review]
the changes igor described

Woops, not quite.
Attachment #330328 - Attachment is obsolete: true
(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.
(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.
I have a new patch coming shortly that resolves some try server complaints.  I'll ask for another cursory review before landing.
Attached patch v9 (obsolete) — Splinter Review
This incorporates your suggestion about returning NULL from the buffer-overflow case, and also fixes some warnings revealed by the try-server.
Attachment #329512 - Attachment is obsolete: true
Attachment #331024 - Flags: review?(igor)
Attachment #329512 - Flags: review?(igor)
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.
Attachment #331024 - Flags: review?(igor)
Attached patch v10 (obsolete) — Splinter Review
This is the patch to land, with Igor's remaining suggestions implemented (thanks for the catch on the lock problem).
Attachment #331024 - Attachment is obsolete: true
Attachment #331110 - Flags: review+
changeset:   16182:a5fc387c4622
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Had to back this out.  :(
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Attached patch v11 (obsolete) — Splinter Review
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+?
Attachment #331110 - Attachment is obsolete: true
Attachment #331216 - Flags: review?(igor)
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.
This seems to constitute an actual -bug- in dtoa; am I wrong?  This math seems bogus for 64-bit architectures.
Attachment #331216 - Attachment is obsolete: true
Attachment #331216 - Flags: review?(igor)
Comment on attachment 331346 [details] [diff] [review]
v12, unsigned int len =  size_t len;

One more spin on review?
Attachment #331346 - Flags: review?(igor)
(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 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.
Attachment #331346 - Flags: review?(igor) → review+
One more go at landing:

changeset:   16394:222c29336422
Status: REOPENED → RESOLVED
Closed: 12 years ago11 years ago
Resolution: --- → FIXED
Depends on: 450392
Flags: in-testsuite-
Flags: in-litmus-
Depends on: 469397
Alias: dtoa
You need to log in before you can comment on or make changes to this bug.