merge revision(s) 63abb5c227e5c20d18d0debf699251da93ca64b5,34d02631e71209b12abb69d0114601027e485bc9,2adbf01ae14c0a4cf190b7c969b91726966a0e0f,3acc81d9e41b18380b9e0168fe2b5e5e0c727256: [Backport #17612]

	dtoa.c: make compilable independently

	Except for `-Dxmalloc=malloc -Dxfree=free`.
	---
	 missing/dtoa.c | 24 ++++++++++++++++++------
	 1 file changed, 18 insertions(+), 6 deletions(-)

	dtoa.c: constified

	clang seems to locate never modified local data in the const
	segment implicitly.
	---
	 missing/dtoa.c | 2 +-
	 1 file changed, 1 insertion(+), 1 deletion(-)

	dtoa.c: make thread-safe by using atomic CAS

	---
	 common.mk      |  2 ++
	 missing/dtoa.c | 75 ++++++++++++++++++++++++++++++++++++++++++----------------
	 util.c         |  1 +
	 3 files changed, 57 insertions(+), 21 deletions(-)

	Fixed race in dtoa [Bug #17612]

	Fixed the race condition when replacing `freelist` entry with its
	chained next element.  At acquiring an entry, hold the entry once
	with the special value, then release by replacing it with the next
	element again after acquired.  If another thread is holding the
	same entry at that time, spinning until the entry gets released.

	Co-Authored-By: Koichi Sasada <ko1@atdot.net>
	---
	 bootstraptest/test_ractor.rb | 11 +++++++++++
	 missing/dtoa.c               | 13 ++++++++++---
	 2 files changed, 21 insertions(+), 3 deletions(-)

1 files changed, 80 insertions, 28 deletions

diff --git a/missing/dtoa.c b/missing/dtoa.c
index cbee13ee81..a940eabd91 100644
--- a/missing/dtoa.c
+++ b/missing/dtoa.c
@@ -183,12 +183,16 @@
 #undef Long
 #undef ULong
 
-#if SIZEOF_INT == 4
+#include <limits.h>
+
+#if (INT_MAX >> 30) && !(INT_MAX >> 31)
 #define Long int
 #define ULong unsigned int
-#elif SIZEOF_LONG == 4
+#elif (LONG_MAX >> 30) && !(LONG_MAX >> 31)
 #define Long long int
 #define ULong unsigned long int
+#else
+#error No 32bit integer
 #endif
 
 #if HAVE_LONG_LONG
@@ -202,6 +206,11 @@
 #define Bug(x) {fprintf(stderr, "%s\n", (x)); exit(EXIT_FAILURE);}
 #endif
 
+#ifndef ISDIGIT
+#include <ctype.h>
+#define ISDIGIT(c) isdigit(c)
+#endif
+#include <errno.h>
 #include <stdlib.h>
 #include <string.h>
 
@@ -219,6 +228,9 @@ extern void FREE(void*);
 #else
 #define FREE xfree
 #endif
+#ifndef NO_SANITIZE
+#define NO_SANITIZE(x, y) y
+#endif
 
 #ifndef Omit_Private_Memory
 #ifndef PRIVATE_MEM
@@ -280,7 +292,7 @@ extern "C" {
 #endif
 
 #ifndef hexdigit
-static const char hexdigits[] = "0123456789abcdef0123456789ABCDEF";
+static const char hexdigit[] = "0123456789abcdef0123456789ABCDEF";
 #endif
 
 #if defined(IEEE_LITTLE_ENDIAN) + defined(IEEE_BIG_ENDIAN) + defined(VAX) + defined(IBM) != 1
@@ -489,6 +501,19 @@ extern double rnd_prod(double, double), rnd_quot(double, double);
 #define FREE_DTOA_LOCK(n)	/*unused right now*/
 #endif
 
+#ifndef ATOMIC_PTR_CAS
+#define ATOMIC_PTR_CAS(var, old, new) ((var) = (new), (old))
+#endif
+#ifndef LIKELY
+#define LIKELY(x) (x)
+#endif
+#ifndef UNLIKELY
+#define UNLIKELY(x) (x)
+#endif
+#ifndef ASSUME
+#define ASSUME(x) (void)(x)
+#endif
+
 #define Kmax 15
 
 struct Bigint {
@@ -501,6 +526,8 @@ typedef struct Bigint Bigint;
 
 static Bigint *freelist[Kmax+1];
 
+#define BLOCKING_BIGINT ((Bigint *)(-1))
+
 static Bigint *
 Balloc(int k)
 {
@@ -510,22 +537,41 @@ Balloc(int k)
     size_t len;
 #endif
 
+    rv = 0;
     ACQUIRE_DTOA_LOCK(0);
-    if (k <= Kmax && (rv = freelist[k]) != 0) {
-        freelist[k] = rv->next;
+    if (k <= Kmax) {
+        rv = freelist[k];
+        while (rv) {
+            Bigint *rvn = rv;
+            rv = ATOMIC_PTR_CAS(freelist[k], rv, BLOCKING_BIGINT);
+            if (LIKELY(rv != BLOCKING_BIGINT && rvn == rv)) {
+                rvn = ATOMIC_PTR_CAS(freelist[k], BLOCKING_BIGINT, rv->next);
+                assert(rvn == BLOCKING_BIGINT);
+                ASSUME(rv);
+                break;
+            }
+        }
     }
-    else {
+    if (!rv) {
         x = 1 << k;
 #ifdef Omit_Private_Memory
         rv = (Bigint *)MALLOC(sizeof(Bigint) + (x-1)*sizeof(ULong));
 #else
         len = (sizeof(Bigint) + (x-1)*sizeof(ULong) + sizeof(double) - 1)
                 /sizeof(double);
-        if (k <= Kmax && pmem_next - private_mem + len <= PRIVATE_mem) {
-            rv = (Bigint*)pmem_next;
-            pmem_next += len;
+        if (k <= Kmax) {
+            double *pnext = pmem_next;
+            while (pnext - private_mem + len <= PRIVATE_mem) {
+                double *p = pnext;
+                pnext = ATOMIC_PTR_CAS(pmem_next, pnext, pnext + len);
+                if (LIKELY(p == pnext)) {
+                    rv = (Bigint*)pnext;
+                    ASSUME(rv);
+                    break;
+                }
+            }
         }
-        else
+        if (!rv)
             rv = (Bigint*)MALLOC(len*sizeof(double));
 #endif
         rv->k = k;
@@ -539,14 +585,19 @@ Balloc(int k)
 static void
 Bfree(Bigint *v)
 {
+    Bigint *vn;
     if (v) {
         if (v->k > Kmax) {
             FREE(v);
             return;
         }
         ACQUIRE_DTOA_LOCK(0);
-        v->next = freelist[v->k];
-        freelist[v->k] = v;
+        do {
+            do {
+                vn = ATOMIC_PTR_CAS(freelist[v->k], 0, 0);
+            } while (UNLIKELY(vn == BLOCKING_BIGINT));
+            v->next = vn;
+        } while (UNLIKELY(ATOMIC_PTR_CAS(freelist[v->k], vn, v) != vn));
         FREE_DTOA_LOCK(0);
     }
 }
@@ -829,8 +880,9 @@ static Bigint *
 pow5mult(Bigint *b, int k)
 {
     Bigint *b1, *p5, *p51;
+    Bigint *p5tmp;
     int i;
-    static int p05[3] = { 5, 25, 125 };
+    static const int p05[3] = { 5, 25, 125 };
 
     if ((i = k & 3) != 0)
         b = multadd(b, p05[i-1], 0);
@@ -839,17 +891,17 @@ pow5mult(Bigint *b, int k)
         return b;
     if (!(p5 = p5s)) {
         /* first time */
-#ifdef MULTIPLE_THREADS
         ACQUIRE_DTOA_LOCK(1);
         if (!(p5 = p5s)) {
-            p5 = p5s = i2b(625);
+            p5 = i2b(625);
             p5->next = 0;
+            p5tmp = ATOMIC_PTR_CAS(p5s, NULL, p5);
+            if (UNLIKELY(p5tmp)) {
+                Bfree(p5);
+                p5 = p5tmp;
+            }
         }
         FREE_DTOA_LOCK(1);
-#else
-        p5 = p5s = i2b(625);
-        p5->next = 0;
-#endif
     }
     for (;;) {
         if (k & 1) {
@@ -860,17 +912,17 @@ pow5mult(Bigint *b, int k)
         if (!(k >>= 1))
             break;
         if (!(p51 = p5->next)) {
-#ifdef MULTIPLE_THREADS
             ACQUIRE_DTOA_LOCK(1);
             if (!(p51 = p5->next)) {
-                p51 = p5->next = mult(p5,p5);
+                p51 = mult(p5,p5);
                 p51->next = 0;
+                p5tmp = ATOMIC_PTR_CAS(p5->next, NULL, p51);
+                if (UNLIKELY(p5tmp)) {
+                    Bfree(p51);
+                    p51 = p5tmp;
+                }
             }
             FREE_DTOA_LOCK(1);
-#else
-            p51 = p5->next = mult(p5,p5);
-            p51->next = 0;
-#endif
         }
         p5 = p51;
     }
@@ -2520,10 +2572,10 @@ static char *dtoa_result;
 static char *
 rv_alloc(int i)
 {
-    return dtoa_result = xmalloc(i);
+    return dtoa_result = MALLOC(i);
 }
 #else
-#define rv_alloc(i) xmalloc(i)
+#define rv_alloc(i) MALLOC(i)
 #endif
 
 static char *
@@ -2550,7 +2602,7 @@ nrv_alloc(const char *s, char **rve, size_t n)
 static void
 freedtoa(char *s)
 {
-    xfree(s);
+    FREE(s);
 }
 #endif