Tarantool development patches archive
 help / color / mirror / Atom feed
From: Vladislav Shpilevoy <v.shpilevoy@tarantool.org>
To: tarantool-patches@dev.tarantool.org, tsafin@tarantool.org,
	alyapunov@tarantool.org
Subject: [Tarantool-patches] [PATCH 02/11] util: introduce double_compare_nint64()
Date: Fri,  5 Jun 2020 01:43:09 +0200	[thread overview]
Message-ID: <ed3f23aa21db4a5ffc7c7b9bc961ccecbcbb2d05.1591313754.git.v.shpilevoy@tarantool.org> (raw)
In-Reply-To: <cover.1591313754.git.v.shpilevoy@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)

  parent reply	other threads:[~2020-06-04 23:43 UTC|newest]

Thread overview: 15+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-06-04 23:43 [Tarantool-patches] [PATCH 00/11] Enable miscelaneous sanitations Vladislav Shpilevoy
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 01/11] cmake: enable misc types of UB detection in clang Vladislav Shpilevoy
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 10/11] sql: fix usage of not initialized index_stat Vladislav Shpilevoy
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 11/11] sql: fix mem_apply_type double type truncation Vladislav Shpilevoy
2020-06-04 23:43 ` Vladislav Shpilevoy [this message]
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 03/11] test: avoid usleep() usage for error injections Vladislav Shpilevoy
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 04/11] vinyl: fix 0 division in case of canceled dump Vladislav Shpilevoy
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 05/11] xrow: don't cast double to float unconditionally Vladislav Shpilevoy
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 06/11] swim: fix zero division Vladislav Shpilevoy
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 07/11] test: fix signed integer overflow in vclock test Vladislav Shpilevoy
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 08/11] digest: eliminate UBs from guava() Vladislav Shpilevoy
2020-06-04 23:43 ` [Tarantool-patches] [PATCH 09/11] salad: fix UB pointer arithmetics in bps_tree Vladislav Shpilevoy
2020-06-05 22:09 ` [Tarantool-patches] [PATCH 00/11] Enable miscelaneous sanitations Timur Safin
2020-06-09  8:19 ` Cyrill Gorcunov
2020-06-09  8:28 ` Kirill Yukhin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=ed3f23aa21db4a5ffc7c7b9bc961ccecbcbb2d05.1591313754.git.v.shpilevoy@tarantool.org \
    --to=v.shpilevoy@tarantool.org \
    --cc=alyapunov@tarantool.org \
    --cc=tarantool-patches@dev.tarantool.org \
    --cc=tsafin@tarantool.org \
    --subject='Re: [Tarantool-patches] [PATCH 02/11] util: introduce double_compare_nint64()' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox