update jsdtoa with interesting pieces of more-recent dtoa

RESOLVED FIXED

Status

()

P2
normal
RESOLVED FIXED
11 years ago
8 years ago

People

(Reporter: crowderbt, Assigned: crowderbt)

Tracking

Trunk
Points:
---
Dependency tree / graph
Bug Flags:
wanted1.9.1 +
in-testsuite -
in-litmus -

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(4 attachments, 13 obsolete attachments)

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
(Assignee)

Description

11 years ago
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.
(Assignee)

Updated

11 years ago
Blocks: 156253
(Assignee)

Updated

11 years ago
Assignee: general → crowder
(Assignee)

Updated

11 years ago
Status: NEW → ASSIGNED
(Assignee)

Comment 1

11 years ago
http://netlib2.cs.utk.edu/fp/changes <--- dtoa.c changelog up to 2005.
(Assignee)

Updated

11 years ago
Blocks: 350936
(Assignee)

Comment 2

11 years ago
Created attachment 271553 [details] [diff] [review]
bugzilla as a backup
(Assignee)

Comment 3

11 years ago
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.
(Assignee)

Comment 4

11 years ago
By "memory safety" there, I mostly mean handling OOM gracefully.  Perhaps the dtoa.c folks don't care.
(Assignee)

Comment 5

10 years ago
Created attachment 323164 [details] [diff] [review]
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.
Attachment #271553 - Attachment is obsolete: true
(Assignee)

Updated

10 years ago
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
(Assignee)

Comment 7

10 years ago
Created attachment 324297 [details] [diff] [review]
new rev
Attachment #323164 - Attachment is obsolete: true
(Assignee)

Comment 8

10 years ago
Created attachment 325325 [details] [diff] [review]
checkpoint

Only about 15 test failures now, checkpointing.
Attachment #324297 - Attachment is obsolete: true

Updated

10 years ago
Flags: wanted1.9.1? → wanted1.9.1+
(Assignee)

Comment 9

10 years ago
Created attachment 326817 [details] [diff] [review]
v5

This passes the testsuite and fixes a few other bugs.
Attachment #325325 - Attachment is obsolete: true
(Assignee)

Updated

10 years ago
Attachment #326817 - Attachment description: v4 → v5
Attachment #326817 - Attachment is patch: true
Attachment #326817 - Attachment mime type: application/octet-stream → text/plain
(Assignee)

Updated

10 years ago
Blocks: 338756
(Assignee)

Comment 10

10 years ago
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.
(Assignee)

Comment 11

10 years ago
I experimented with using JSThinLock instead of PRLocks, and failed.  JSThinLocks, at least for this code, were measurably slower.
(Assignee)

Comment 12

10 years ago
Created attachment 328925 [details] [diff] [review]
v6

Fixing some bugs and compiler warnings.  Review request coming soon, I think.  Need to write some more tests.
Attachment #326817 - Attachment is obsolete: true
(Assignee)

Comment 13

10 years ago
Created attachment 329108 [details] [diff] [review]
threadsafety test

This crashes my v6 patch.  Researching now.
(Assignee)

Comment 14

10 years ago
Created attachment 329154 [details] [diff] [review]
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.
Attachment #328925 - Attachment is obsolete: true
(Assignee)

Comment 15

10 years ago
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.
(Assignee)

Comment 16

10 years ago
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)
(Assignee)

Comment 17

10 years ago
Created attachment 329155 [details] [diff] [review]
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.
(Assignee)

Comment 18

10 years ago
Created attachment 329156 [details] [diff] [review]
with context

Woops, how about I share some context?
Attachment #329155 - Attachment is obsolete: true
(Assignee)

Comment 19

10 years ago
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.
(Assignee)

Comment 20

10 years ago
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.
(Assignee)

Comment 21

10 years ago
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)
(Assignee)

Comment 22

10 years ago
Created attachment 329167 [details]
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

10 years ago
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.
(Assignee)

Comment 24

10 years ago
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
(Assignee)

Comment 26

10 years ago
> 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.
(Assignee)

Comment 28

10 years ago
Created attachment 329512 [details] [diff] [review]
v8, with mrbkap's nits and -p
Attachment #329154 - Attachment is obsolete: true
Attachment #329154 - Flags: review?(mrbkap)
Attachment #329154 - Flags: review?(igor)
(Assignee)

Updated

10 years ago
Attachment #329512 - Flags: review?(mrbkap)
(Assignee)

Updated

10 years ago
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+
(Assignee)

Comment 30

10 years ago
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

10 years ago
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.
(Assignee)

Comment 32

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

Comment 33

10 years ago
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.
(Assignee)

Comment 34

10 years ago
Created attachment 330328 [details] [diff] [review]
the changes igor described
(Assignee)

Comment 35

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

Woops, not quite.
Attachment #330328 - Attachment is obsolete: true

Comment 36

10 years ago
(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

10 years ago
(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.
(Assignee)

Comment 38

10 years ago
I have a new patch coming shortly that resolves some try server complaints.  I'll ask for another cursory review before landing.
(Assignee)

Comment 39

10 years ago
Created attachment 331024 [details] [diff] [review]
v9

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 40

10 years ago
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)
(Assignee)

Comment 41

10 years ago
Created attachment 331110 [details] [diff] [review]
v10

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+
(Assignee)

Comment 42

10 years ago
changeset:   16182:a5fc387c4622
Status: ASSIGNED → RESOLVED
Last Resolved: 10 years ago
Resolution: --- → FIXED
(Assignee)

Comment 43

10 years ago
Had to back this out.  :(
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
(Assignee)

Comment 44

10 years ago
Created attachment 331216 [details] [diff] [review]
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+?
Attachment #331110 - Attachment is obsolete: true
Attachment #331216 - Flags: review?(igor)

Comment 45

10 years ago
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.
(Assignee)

Comment 46

10 years ago
Created attachment 331346 [details] [diff] [review]
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.
Attachment #331216 - Attachment is obsolete: true
Attachment #331216 - Flags: review?(igor)
(Assignee)

Comment 47

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

One more spin on review?
Attachment #331346 - Flags: review?(igor)

Comment 48

10 years ago
(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

10 years ago
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+
(Assignee)

Comment 50

10 years ago
One more go at landing:

changeset:   16394:222c29336422
Status: REOPENED → RESOLVED
Last Resolved: 10 years ago10 years ago
Resolution: --- → FIXED

Updated

10 years ago
Depends on: 450392

Updated

10 years ago
Flags: in-testsuite-
Flags: in-litmus-

Updated

10 years ago
Depends on: 469397

Updated

8 years ago
Alias: dtoa
You need to log in before you can comment on or make changes to this bug.