Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitdf1a699

Browse files
committed
Fix integer-overflow problems in interval comparison.
When using integer timestamps, the interval-comparison functions triedto compute the overall magnitude of an interval as an int64 number ofmicroseconds. As reported by Frazer McLean, this overflows for intervalsexceeding about 296000 years, which is bad since we nominally allowintervals many times larger than that. That results in wrong comparisonresults, and possibly in corrupted btree indexes for columns containingsuch large interval values.To fix, compute the magnitude as int128 instead. Although some compilershave native support for int128 calculations, many don't, so create ourown support functions that can do 128-bit addition and multiplicationif the compiler support isn't there. These support functions are designedwith an eye to allowing the int128 code paths in numeric.c to be rewrittenfor use on all platforms, although this patch doesn't do that, or evenprovide all the int128 primitives that will be needed for it.Back-patch as far as 9.4. Earlier releases did not guard against overflowof interval values at all (commit146604e fixed that), so it seems notvery exciting to worry about overly-large intervals for them.Before 9.6, we did not assume that unreferenced "static inline" functionswould not draw compiler warnings, so omit functions not directly referencedby timestamp.c, the only present consumer of int128.h. (We could haveomitted these functions in HEAD too, but since they were written anddebugged on the way to the present patch, and they look likely to be neededby numeric.c, let's keep them in HEAD.) I did not bother to try to preventsuch warnings in a --disable-integer-datetimes build, though.Before 9.5, configure will never define HAVE_INT128, so the part ofint128.h that exploits a native int128 implementation is dead code in the9.4 branch. I didn't bother to remove it, thinking that keeping the filelooking similar in different branches is more useful.In HEAD only, add a simple test harness for int128.h in src/tools/.In back branches, this does not change the float-timestamps code path.That's not subject to the same kind of overflow risk, since it computesthe interval magnitude as float8. (No doubt, when this code was originallywritten, overflow was disregarded for exactly that reason.) There is aprecision hazard instead :-(, but we'll avert our eyes from that question,since no complaints have been reported and that code's deprecated anyway.Kyotaro Horiguchi and Tom LaneDiscussion:https://postgr.es/m/1490104629.422698.918452336.26FA96B7@webmail.messagingengine.com
1 parent68ea2b7 commitdf1a699

File tree

5 files changed

+590
-10
lines changed

5 files changed

+590
-10
lines changed

‎src/backend/utils/adt/timestamp.c

Lines changed: 40 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,7 @@
2424
#include"access/hash.h"
2525
#include"access/xact.h"
2626
#include"catalog/pg_type.h"
27+
#include"common/int128.h"
2728
#include"funcapi.h"
2829
#include"libpq/pqformat.h"
2930
#include"miscadmin.h"
@@ -2288,26 +2289,46 @@ timestamptz_cmp_timestamp(PG_FUNCTION_ARGS)
22882289

22892290
/*
22902291
*interval_relop- is interval1 relop interval2
2292+
*
2293+
* Interval comparison is based on converting interval values to a linear
2294+
* representation expressed in the units of the time field (microseconds,
2295+
* in the case of integer timestamps) with days assumed to be always 24 hours
2296+
* and months assumed to be always 30 days. To avoid overflow, we need a
2297+
* wider-than-int64 datatype for the linear representation, so use INT128.
22912298
*/
2292-
staticinlineTimeOffset
2299+
2300+
staticinlineINT128
22932301
interval_cmp_value(constInterval*interval)
22942302
{
2295-
TimeOffsetspan;
2303+
INT128span;
2304+
int64dayfraction;
2305+
int64days;
2306+
2307+
/*
2308+
* Separate time field into days and dayfraction, then add the month and
2309+
* day fields to the days part. We cannot overflow int64 days here.
2310+
*/
2311+
dayfraction=interval->time %USECS_PER_DAY;
2312+
days=interval->time /USECS_PER_DAY;
2313+
days+=interval->month*INT64CONST(30);
2314+
days+=interval->day;
22962315

2297-
span=interval->time;
2298-
span+=interval->month*INT64CONST(30)*USECS_PER_DAY;
2299-
span+=interval->day*INT64CONST(24)*USECS_PER_HOUR;
2316+
/* Widen dayfraction to 128 bits */
2317+
span=int64_to_int128(dayfraction);
2318+
2319+
/* Scale up days to microseconds, forming a 128-bit product */
2320+
int128_add_int64_mul_int64(&span,days,USECS_PER_DAY);
23002321

23012322
returnspan;
23022323
}
23032324

23042325
staticint
23052326
interval_cmp_internal(Interval*interval1,Interval*interval2)
23062327
{
2307-
TimeOffsetspan1=interval_cmp_value(interval1);
2308-
TimeOffsetspan2=interval_cmp_value(interval2);
2328+
INT128span1=interval_cmp_value(interval1);
2329+
INT128span2=interval_cmp_value(interval2);
23092330

2310-
return((span1<span2) ?-1 : (span1>span2) ?1 :0);
2331+
returnint128_compare(span1,span2);
23112332
}
23122333

23132334
Datum
@@ -2384,9 +2405,18 @@ Datum
23842405
interval_hash(PG_FUNCTION_ARGS)
23852406
{
23862407
Interval*interval=PG_GETARG_INTERVAL_P(0);
2387-
TimeOffsetspan=interval_cmp_value(interval);
2408+
INT128span=interval_cmp_value(interval);
2409+
int64span64;
2410+
2411+
/*
2412+
* Use only the least significant 64 bits for hashing. The upper 64 bits
2413+
* seldom add any useful information, and besides we must do it like this
2414+
* for compatibility with hashes calculated before use of INT128 was
2415+
* introduced.
2416+
*/
2417+
span64=int128_to_int64(span);
23882418

2389-
returnDirectFunctionCall1(hashint8,Int64GetDatumFast(span));
2419+
returnDirectFunctionCall1(hashint8,Int64GetDatumFast(span64));
23902420
}
23912421

23922422
/* overlaps_timestamp() --- implements the SQL OVERLAPS operator.

‎src/include/common/int128.h

Lines changed: 276 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,276 @@
1+
/*-------------------------------------------------------------------------
2+
*
3+
* int128.h
4+
* Roll-our-own 128-bit integer arithmetic.
5+
*
6+
* We make use of the native int128 type if there is one, otherwise
7+
* implement things the hard way based on two int64 halves.
8+
*
9+
* See src/tools/testint128.c for a simple test harness for this file.
10+
*
11+
* Copyright (c) 2017, PostgreSQL Global Development Group
12+
*
13+
* src/include/common/int128.h
14+
*
15+
*-------------------------------------------------------------------------
16+
*/
17+
#ifndefINT128_H
18+
#defineINT128_H
19+
20+
/*
21+
* For testing purposes, use of native int128 can be switched on/off by
22+
* predefining USE_NATIVE_INT128.
23+
*/
24+
#ifndefUSE_NATIVE_INT128
25+
#ifdefHAVE_INT128
26+
#defineUSE_NATIVE_INT128 1
27+
#else
28+
#defineUSE_NATIVE_INT128 0
29+
#endif
30+
#endif
31+
32+
33+
#ifUSE_NATIVE_INT128
34+
35+
typedefint128INT128;
36+
37+
/*
38+
* Add an unsigned int64 value into an INT128 variable.
39+
*/
40+
staticinlinevoid
41+
int128_add_uint64(INT128*i128,uint64v)
42+
{
43+
*i128+=v;
44+
}
45+
46+
/*
47+
* Add a signed int64 value into an INT128 variable.
48+
*/
49+
staticinlinevoid
50+
int128_add_int64(INT128*i128,int64v)
51+
{
52+
*i128+=v;
53+
}
54+
55+
/*
56+
* Add the 128-bit product of two int64 values into an INT128 variable.
57+
*
58+
* XXX with a stupid compiler, this could actually be less efficient than
59+
* the other implementation; maybe we should do it by hand always?
60+
*/
61+
staticinlinevoid
62+
int128_add_int64_mul_int64(INT128*i128,int64x,int64y)
63+
{
64+
*i128+= (int128)x*(int128)y;
65+
}
66+
67+
/*
68+
* Compare two INT128 values, return -1, 0, or +1.
69+
*/
70+
staticinlineint
71+
int128_compare(INT128x,INT128y)
72+
{
73+
if (x<y)
74+
return-1;
75+
if (x>y)
76+
return1;
77+
return0;
78+
}
79+
80+
/*
81+
* Widen int64 to INT128.
82+
*/
83+
staticinlineINT128
84+
int64_to_int128(int64v)
85+
{
86+
return (INT128)v;
87+
}
88+
89+
/*
90+
* Convert INT128 to int64 (losing any high-order bits).
91+
* This also works fine for casting down to uint64.
92+
*/
93+
staticinlineint64
94+
int128_to_int64(INT128val)
95+
{
96+
return (int64)val;
97+
}
98+
99+
#else/* !USE_NATIVE_INT128 */
100+
101+
/*
102+
* We lay out the INT128 structure with the same content and byte ordering
103+
* that a native int128 type would (probably) have. This makes no difference
104+
* for ordinary use of INT128, but allows union'ing INT128 with int128 for
105+
* testing purposes.
106+
*/
107+
typedefstruct
108+
{
109+
#ifdefWORDS_BIGENDIAN
110+
int64hi;/* most significant 64 bits, including sign */
111+
uint64lo;/* least significant 64 bits, without sign */
112+
#else
113+
uint64lo;/* least significant 64 bits, without sign */
114+
int64hi;/* most significant 64 bits, including sign */
115+
#endif
116+
}INT128;
117+
118+
/*
119+
* Add an unsigned int64 value into an INT128 variable.
120+
*/
121+
staticinlinevoid
122+
int128_add_uint64(INT128*i128,uint64v)
123+
{
124+
/*
125+
* First add the value to the .lo part, then check to see if a carry needs
126+
* to be propagated into the .hi part. A carry is needed if both inputs
127+
* have high bits set, or if just one input has high bit set while the new
128+
* .lo part doesn't. Remember that .lo part is unsigned; we cast to
129+
* signed here just as a cheap way to check the high bit.
130+
*/
131+
uint64oldlo=i128->lo;
132+
133+
i128->lo+=v;
134+
if (((int64)v<0&& (int64)oldlo<0)||
135+
(((int64)v<0|| (int64)oldlo<0)&& (int64)i128->lo >=0))
136+
i128->hi++;
137+
}
138+
139+
/*
140+
* Add a signed int64 value into an INT128 variable.
141+
*/
142+
staticinlinevoid
143+
int128_add_int64(INT128*i128,int64v)
144+
{
145+
/*
146+
* This is much like the above except that the carry logic differs for
147+
* negative v. Ordinarily we'd need to subtract 1 from the .hi part
148+
* (corresponding to adding the sign-extended bits of v to it); but if
149+
* there is a carry out of the .lo part, that cancels and we do nothing.
150+
*/
151+
uint64oldlo=i128->lo;
152+
153+
i128->lo+=v;
154+
if (v >=0)
155+
{
156+
if ((int64)oldlo<0&& (int64)i128->lo >=0)
157+
i128->hi++;
158+
}
159+
else
160+
{
161+
if (!((int64)oldlo<0|| (int64)i128->lo >=0))
162+
i128->hi--;
163+
}
164+
}
165+
166+
/*
167+
* INT64_AU32 extracts the most significant 32 bits of int64 as int64, while
168+
* INT64_AL32 extracts the least significant 32 bits as uint64.
169+
*/
170+
#defineINT64_AU32(i64) ((i64) >> 32)
171+
#defineINT64_AL32(i64) ((i64) & UINT64CONST(0xFFFFFFFF))
172+
173+
/*
174+
* Add the 128-bit product of two int64 values into an INT128 variable.
175+
*/
176+
staticinlinevoid
177+
int128_add_int64_mul_int64(INT128*i128,int64x,int64y)
178+
{
179+
/* INT64_AU32 must use arithmetic right shift */
180+
StaticAssertStmt(((int64)-1 >>1)== (int64)-1,
181+
"arithmetic right shift is needed");
182+
183+
/*----------
184+
* Form the 128-bit product x * y using 64-bit arithmetic.
185+
* Considering each 64-bit input as having 32-bit high and low parts,
186+
* we can compute
187+
*
188+
* x * y = ((x.hi << 32) + x.lo) * (((y.hi << 32) + y.lo)
189+
* = (x.hi * y.hi) << 64 +
190+
* (x.hi * y.lo) << 32 +
191+
* (x.lo * y.hi) << 32 +
192+
* x.lo * y.lo
193+
*
194+
* Each individual product is of 32-bit terms so it won't overflow when
195+
* computed in 64-bit arithmetic. Then we just have to shift it to the
196+
* correct position while adding into the 128-bit result. We must also
197+
* keep in mind that the "lo" parts must be treated as unsigned.
198+
*----------
199+
*/
200+
201+
/* No need to work hard if product must be zero */
202+
if (x!=0&&y!=0)
203+
{
204+
int64x_u32=INT64_AU32(x);
205+
uint64x_l32=INT64_AL32(x);
206+
int64y_u32=INT64_AU32(y);
207+
uint64y_l32=INT64_AL32(y);
208+
int64tmp;
209+
210+
/* the first term */
211+
i128->hi+=x_u32*y_u32;
212+
213+
/* the second term: sign-extend it only if x is negative */
214+
tmp=x_u32*y_l32;
215+
if (x<0)
216+
i128->hi+=INT64_AU32(tmp);
217+
else
218+
i128->hi+= ((uint64)tmp) >>32;
219+
int128_add_uint64(i128, ((uint64)INT64_AL32(tmp)) <<32);
220+
221+
/* the third term: sign-extend it only if y is negative */
222+
tmp=x_l32*y_u32;
223+
if (y<0)
224+
i128->hi+=INT64_AU32(tmp);
225+
else
226+
i128->hi+= ((uint64)tmp) >>32;
227+
int128_add_uint64(i128, ((uint64)INT64_AL32(tmp)) <<32);
228+
229+
/* the fourth term: always unsigned */
230+
int128_add_uint64(i128,x_l32*y_l32);
231+
}
232+
}
233+
234+
/*
235+
* Compare two INT128 values, return -1, 0, or +1.
236+
*/
237+
staticinlineint
238+
int128_compare(INT128x,INT128y)
239+
{
240+
if (x.hi<y.hi)
241+
return-1;
242+
if (x.hi>y.hi)
243+
return1;
244+
if (x.lo<y.lo)
245+
return-1;
246+
if (x.lo>y.lo)
247+
return1;
248+
return0;
249+
}
250+
251+
/*
252+
* Widen int64 to INT128.
253+
*/
254+
staticinlineINT128
255+
int64_to_int128(int64v)
256+
{
257+
INT128val;
258+
259+
val.lo= (uint64)v;
260+
val.hi= (v<0) ?-INT64CONST(1) :INT64CONST(0);
261+
returnval;
262+
}
263+
264+
/*
265+
* Convert INT128 to int64 (losing any high-order bits).
266+
* This also works fine for casting down to uint64.
267+
*/
268+
staticinlineint64
269+
int128_to_int64(INT128val)
270+
{
271+
return (int64)val.lo;
272+
}
273+
274+
#endif/* USE_NATIVE_INT128 */
275+
276+
#endif/* INT128_H */

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp