From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id 4EEBB24759 for ; Wed, 17 Jul 2019 08:24:48 -0400 (EDT) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xW7HfaAZ_Ej6 for ; Wed, 17 Jul 2019 08:24:48 -0400 (EDT) Received: from smtpng2.m.smailru.net (smtpng2.m.smailru.net [94.100.179.3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id 806532013B for ; Wed, 17 Jul 2019 08:24:47 -0400 (EDT) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\)) Subject: [tarantool-patches] Re: [PATCH 3/6] sql: refactor arithmetic operations to support unsigned ints From: "n.pettik" In-Reply-To: Date: Wed, 17 Jul 2019 15:24:44 +0300 Content-Transfer-Encoding: quoted-printable Message-Id: References: <7d8e776bc82cb9d25460c2104e687540526aa7cd.1559919361.git.korablev@tarantool.org> <9233795e-a77c-565a-9bd5-3712499e7fce@tarantool.org> <53B73D9B-740B-469F-99DC-FF2FA14E16BA@tarantool.org> <46ec2553-ae16-9a9f-8b85-882c2adc6031@tarantool.org> <7AA862F1-50A9-40E4-A054-D42836D125A5@tarantool.org> Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-Help: List-Unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-Subscribe: List-Owner: List-post: List-Archive: To: tarantool-patches@freelists.org Cc: Vladislav Shpilevoy > I did this: >=20 > @@ -4943,7 +4943,7 @@ case OP_OffsetLimit: { /* in1, out2, in3 */ > uint64_t x =3D pIn1->u.u; > uint64_t rhs =3D pIn3->u.u; > bool unused; > - if (x =3D=3D 0 || sql_add_int(x, false, rhs, false, (int64_t *) = &x, > + if (x =3D=3D 0 || sql_add_int(x, true, rhs, false, (int64_t *) = &x, > &unused) !=3D 0) { > /* If the LIMIT is less than or equal to zero, loop = forever. This > * is documented. But also, if the LIMIT+OFFSET exceeds = 2^63 then >=20 > And the tests passed. Looks like a test was not added. Ok, I=E2=80=99ve dived a bit into this code and added auxiliary commit: commit b954fac26809286f764e4509335c0ee7b63d42c2 (HEAD) Author: Nikita Pettik Date: Tue Jul 16 19:25:05 2019 +0300 sql: refactor VDBE opcode OP_OffsetLimit =20 OP_OffsetLimit instruction calculates sum of OFFSET and LIMIT values when they are present. This sum serves as a counter of entries to be inserted to temporary space during VDBE execution. Consider query = like: =20 SELECT * FROM t ORDER BY x LIMIT 5 OFFSET 2; =20 To perform ordering alongside with applying limit and offset restrictions, first 7 (5 + 2) entries are inserted into temporary = space. They are sorted and then first two tuples are skipped according to = offset clause. The rest tuples from temporary space get to result set. =20 When sum of LIMIT and OFFSET values is big enough to cause integer overflow, we can't apply this approach. Previously, counter was = simply set to -1 which means that all entries from base table will be = transferred to ephemeral space. As a result, LIMIT clause was ignored and the = result of query would be incorrect. Motivation for this obviously wrong = step was that to perform query with such huge limit and offset values too = many time is required (like years). What is more, ephemeral spaces support auto-generated IDs in the range up to 2^32, so there's even no = opportunity to process such queries in theory. Nevertheless, to make code = cleaner let's fix this tricky place and just raise an overflow error if = result of addition exceeds integer range. =20 This patch fixes obsolete comments saying that in case of overflow execution won't stop; now limit and offset counter are always >=3D = 0, so removed redundant branching. diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c index 181f71deb..e349af68f 100644 --- a/src/box/sql/vdbe.c +++ b/src/box/sql/vdbe.c @@ -4861,7 +4861,7 @@ case OP_IfPos: { /* jump, in1 */ } =20 /* Opcode: OffsetLimit P1 P2 P3 * * - * Synopsis: if r[P1]>0 then r[P2]=3Dr[P1]+max(0,r[P3]) else r[P2]=3D(-1)= + * Synopsis: r[P2]=3Dr[P1]+r[P3] * * This opcode performs a commonly used computation associated with * LIMIT and OFFSET process. r[P1] holds the limit counter. r[P3] @@ -4870,35 +4870,23 @@ case OP_IfPos: { /* jump, in1 */ * value computed is the total number of rows that will need to be * visited in order to complete the query. * - * If r[P3] is zero or negative, that means there is no OFFSET - * and r[P2] is set to be the value of the LIMIT, r[P1]. - * - * if r[P1] is zero or negative, that means there is no LIMIT - * and r[P2] is set to -1. - * - * Otherwise, r[P2] is set to the sum of r[P1] and r[P3]. + * Otherwise, r[P2] is set to the sum of r[P1] and r[P3]. If the + * sum is larger than 2^63-1 (i.e. overflow takes place) then + * error is raised. */ case OP_OffsetLimit: { /* in1, out2, in3 */ - i64 x; pIn1 =3D &aMem[pOp->p1]; pIn3 =3D &aMem[pOp->p3]; pOut =3D out2Prerelease(p, pOp); assert(pIn1->flags & MEM_Int); assert(pIn3->flags & MEM_Int); - x =3D pIn1->u.i; - if (x<=3D0 || sqlAddInt64(&x, pIn3->u.i>0?pIn3->u.i:0)) { - /* If the LIMIT is less than or equal to zero, loop = forever. This - * is documented. But also, if the LIMIT+OFFSET exceeds = 2^63 then - * also loop forever. This is undocumented. In fact, = one could argue - * that the loop should terminate. But assuming 1 = billion iterations - * per second (far exceeding the capabilities of any = current hardware) - * it would take nearly 300 years to actually reach the = limit. So - * looping forever is a reasonable approximation. - */ - pOut->u.i =3D -1; - } else { - pOut->u.i =3D x; + i64 x =3D pIn1->u.i; + if (sqlAddInt64(&x, pIn3->u.i) !=3D 0) { + diag_set(ClientError, ER_SQL_EXECUTE, "sum of LIMIT and = OFFSET " + "values should not result in integer = overflow"); + goto abort_due_to_error; } + pOut->u.i =3D x; break; } =20 diff --git a/test/sql-tap/limit.test.lua b/test/sql-tap/limit.test.lua index 40b787b52..84d0798db 100755 --- a/test/sql-tap/limit.test.lua +++ b/test/sql-tap/limit.test.lua @@ -1,6 +1,6 @@ #!/usr/bin/env tarantool test =3D require("sqltester") -test:plan(111) +test:plan(113) =20 --!./tcltestrunner.lua -- 2001 November 6 @@ -1354,4 +1354,18 @@ test:do_execsql_test( -- }) =20 +-- Sum of LIMIT and OFFSET values should not cause integer overflow. +-- +test:do_catchsql_test( + "limit-15.1", + [[ + SELECT 1 LIMIT 9223372036854775807 OFFSET 1; + ]], { 1, "Failed to execute SQL statement: sum of LIMIT and OFFSET = values should not result in integer overflow" } ) + +test:do_catchsql_test( + "limit-15.2", + [[ + SELECT 1 LIMIT 1 OFFSET 9223372036854775807; + ]], { 1, "Failed to execute SQL statement: sum of LIMIT and OFFSET = values should not result in integer overflow "} ) + test:finish_test()=