From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp51.i.mail.ru (smtp51.i.mail.ru [94.100.177.111]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id CA8AE4696C1 for ; Fri, 5 Jun 2020 02:43:22 +0300 (MSK) From: Vladislav Shpilevoy Date: Fri, 5 Jun 2020 01:43:09 +0200 Message-Id: In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH 02/11] util: introduce double_compare_nint64() List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: tarantool-patches@dev.tarantool.org, tsafin@tarantool.org, alyapunov@tarantool.org Utility module (util.h and util.c) offers a function double_compare_uint64() to compare double and uint64_t in a reliable way, without undefined behaviour, without losses, even if values are about 2^53 - 2^64. There was no a similar function to compare double and int64_t, which is needed when the right value is negative. To workaround it the right value (int64_t) was multiplied by -1 when it was negative to be able to use it in double_compare_uint64(). This led to undefined behaviour, when right value was INT64_MIN, because expression (uint64_t)-value did not help. Firstly -value was calculated, and then it was cast to uint64_t. The first step is detected by the sanitizer as undefined behaviour. Not counting, that it was slower than straightforward comparison of negative int64_t and a double value. Because involved additional negation. Besides, there was an expression: assert((uint64_t)(double)rhs == rhs || rhs > (uint64_t)EXP2_53); Rhs is a uint64_t. And there was hidden an undefined behaviour, when rhs is UINT64_MAX. The problem is that UINT64_MAX is 2^64 - 1. And it can't be stored in a double value without precision loss. It is rounded up to 2^64 = UINT64_MAX + 1. This is what happens in "(double)rhs" expression. And when it is cast back to uint64_t: "(uint64_t)(double)rhs", it explodes. The patch fixes it by simply changing check order. If rhs is bigger than 2^53 (below this border all the integers can be represented), then the cast is not done. Part of #4609 --- src/box/sql/vdbeaux.c | 16 ++++++++-------- src/box/tuple_compare.cc | 9 ++------- src/lib/core/util.c | 22 +++++++++++++++++++++- src/trivia/util.h | 22 ++++++++++++++++++++++ 4 files changed, 53 insertions(+), 16 deletions(-) diff --git a/src/box/sql/vdbeaux.c b/src/box/sql/vdbeaux.c index 71f694b20..bae1a5352 100644 --- a/src/box/sql/vdbeaux.c +++ b/src/box/sql/vdbeaux.c @@ -2876,8 +2876,8 @@ sqlMemCompare(const Mem * pMem1, const Mem * pMem2, const struct coll * pColl) } if ((f1 & MEM_Int) != 0) { if ((f2 & MEM_Real) != 0) { - return double_compare_uint64(-pMem2->u.r, - -pMem1->u.i, 1); + return double_compare_nint64(pMem2->u.r, + pMem1->u.i, -1); } else { return -1; } @@ -2894,8 +2894,8 @@ sqlMemCompare(const Mem * pMem1, const Mem * pMem2, const struct coll * pColl) } if ((f1 & MEM_Real) != 0) { if ((f2 & MEM_Int) != 0) { - return double_compare_uint64(-pMem1->u.r, - -pMem2->u.i, -1); + return double_compare_nint64(pMem1->u.r, + pMem2->u.i, 1); } else if ((f2 & MEM_UInt) != 0) { return double_compare_uint64(pMem1->u.r, pMem2->u.u, 1); @@ -3073,8 +3073,8 @@ sqlVdbeCompareMsgpack(const char **key1, rc = +1; } } else if (pKey2->flags & MEM_Real) { - rc = double_compare_uint64(-pKey2->u.r, - -mem1.u.i, 1); + rc = double_compare_nint64(pKey2->u.r, mem1.u.i, + -1); } else if ((pKey2->flags & MEM_Null) != 0) { rc = 1; } else if ((pKey2->flags & MEM_Bool) != 0) { @@ -3092,8 +3092,8 @@ sqlVdbeCompareMsgpack(const char **key1, mem1.u.r = mp_decode_double(&aKey1); do_float: if ((pKey2->flags & MEM_Int) != 0) { - rc = double_compare_uint64(-mem1.u.r, - -pKey2->u.i, -1); + rc = double_compare_nint64(mem1.u.r, pKey2->u.i, + 1); } else if (pKey2->flags & MEM_UInt) { rc = double_compare_uint64(mem1.u.r, pKey2->u.u, 1); diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc index bc01fe068..d059c709f 100644 --- a/src/box/tuple_compare.cc +++ b/src/box/tuple_compare.cc @@ -168,13 +168,8 @@ static int mp_compare_double_any_int(double lhs, const char *rhs, enum mp_type rhs_type, int k) { - if (rhs_type == MP_INT) { - int64_t v = mp_decode_int(&rhs); - if (v < 0) { - return double_compare_uint64(-lhs, (uint64_t)-v, -k); - } - return double_compare_uint64(lhs, (uint64_t)v, k); - } + if (rhs_type == MP_INT) + return double_compare_int64(lhs, mp_decode_int(&rhs), k); assert(rhs_type == MP_UINT); return double_compare_uint64(lhs, mp_decode_uint(&rhs), k); } diff --git a/src/lib/core/util.c b/src/lib/core/util.c index ffa1d2b51..a65bc496c 100644 --- a/src/lib/core/util.c +++ b/src/lib/core/util.c @@ -327,6 +327,7 @@ fpconv_check() } #define EXP2_53 9007199254740992.0 /* 2.0 ^ 53 */ +#define EXP2_63 9223372036854775808.0 /* 2.0 ^ 63 */ #define EXP2_64 1.8446744073709552e+19 /* 2.0 ^ 64 */ int @@ -378,7 +379,7 @@ double_compare_uint64(double lhs, uint64_t rhs, int k) * rounding happens. */ assert(lhs < EXP2_53); - assert((uint64_t)(double)rhs == rhs || rhs > (uint64_t)EXP2_53); + assert(rhs > (uint64_t)EXP2_53 || (uint64_t)(double)rhs == rhs); return k*COMPARE_RESULT(lhs, (double)rhs); } /* @@ -387,3 +388,22 @@ double_compare_uint64(double lhs, uint64_t rhs, int k) */ return -k; } + +int +double_compare_nint64(double lhs, int64_t rhs, int k) +{ + assert(rhs < 0); + assert(k==1 || k==-1); + if (lhs <= -EXP2_53) { + assert((int64_t)-EXP2_63 == INT64_MIN); + if (lhs < -EXP2_63) + return -k; + assert((double)(int64_t)lhs == lhs); + return k*COMPARE_RESULT((int64_t)lhs, rhs); + } + if (!isnan(lhs)) { + assert(rhs < (int64_t)-EXP2_53 || (int64_t)(double)rhs == rhs); + return k*COMPARE_RESULT(lhs, (double)rhs); + } + return -k; +} diff --git a/src/trivia/util.h b/src/trivia/util.h index 8a3d22b38..973c9df33 100644 --- a/src/trivia/util.h +++ b/src/trivia/util.h @@ -512,6 +512,28 @@ json_escape(char *buf, int size, const char *data); int double_compare_uint64(double lhs, uint64_t rhs, int k); +/** + * The same as double_compare_uint64(), but for negative int64_t + * value. To avoid unnecessary negation for cast to uint64_t to + * be able to use the other function, and to avoid the undefined + * behaviour in it, because "(uint64_t)-value" is UB, if value is + * INT64_MIN. + */ +int +double_compare_nint64(double lhs, int64_t rhs, int k); + +/** + * A shortcut to automatically choose a needed double vs + * int64/uint64 function. + */ +static inline int +double_compare_int64(double lhs, int64_t rhs, int k) +{ + if (rhs >= 0) + return double_compare_uint64(lhs, (uint64_t)rhs, k); + return double_compare_nint64(lhs, rhs, k); +} + #if !defined(__cplusplus) && !defined(static_assert) # define static_assert _Static_assert #endif -- 2.21.1 (Apple Git-122.3)