diff options
author | NARUSE, Yui <naruse@airemix.jp> | 2021-03-13 05:11:30 +0900 |
---|---|---|
committer | NARUSE, Yui <naruse@airemix.jp> | 2021-03-13 05:11:30 +0900 |
commit | 6bf32cbed8f3fd0b73b99737d671f833c594d800 (patch) | |
tree | 8386c8baaf64923af62e953cf000e1bcea4f6ba2 /missing | |
parent | 7b122b8af86c155eb23e8cad463cdf2c0bfc1d77 (diff) |
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(-)
Diffstat (limited to 'missing')
-rw-r--r-- | missing/dtoa.c | 108 |
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 |