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

Commitc2aa5d0

Browse files
committed
Don't reference out-of-bounds array elements in brin_minmax_multi.c
The primary fix here is to fix has_matching_range() so it does notreference ranges->values[-1] when nranges == 0. Similar problems existedin AssertCheckRanges() too. It does not look like any of these problemscould lead to a crash as the array in question is at the end of the Rangesstruct, and values[-1] is memory that belongs to other fields in thestruct. However, let's get rid of these rather unsafe coding practices.In passing, I (David) adjusted some comments to try to make it more clearwhat some of the fields are for in the Ranges struct. I had to study thecode to find out what nsorted was for as I couldn't tell from thecomments.Author: Ranier VilelaDiscussion:https://postgr.es/m/CAEudQAqJQzPitufX-jR=YUbJafpCDAKUnwgdbX_MzSc93wuvdw@mail.gmail.comBackpatch-through: 14, where multi-range brin was added.
1 parent293a6ac commitc2aa5d0

File tree

1 file changed

+88
-84
lines changed

1 file changed

+88
-84
lines changed

‎src/backend/access/brin/brin_minmax_multi.c‎

Lines changed: 88 additions & 84 deletions
Original file line numberDiff line numberDiff line change
@@ -142,19 +142,23 @@ typedef struct MinMaxMultiOptions
142142
* The Ranges struct stores the boundary values in a single array, but we
143143
* treat regular and single-point ranges differently to save space. For
144144
* regular ranges (with different boundary values) we have to store both
145-
* values, while for "single-point ranges" we only need to save one value.
145+
* the lower and upper bound of the range, while for "single-point ranges"
146+
* we only need to store a single value.
146147
*
147148
* The 'values' array stores boundary values for regular ranges first (there
148149
* are 2*nranges values to store), and then the nvalues boundary values for
149150
* single-point ranges. That is, we have (2*nranges + nvalues) boundary
150151
* values in the array.
151152
*
152-
* +---------------------------------+-------------------------------+
153-
* | ranges (sorted pairs of values) |sortedvalues (single points) |
154-
* +---------------------------------+-------------------------------+
153+
* +-------------------------+----------------------------------+
154+
* | ranges (2 * nranges of) |single pointvalues (nvalues of) |
155+
* +-------------------------+----------------------------------+
155156
*
156157
* This allows us to quickly add new values, and store outliers without
157-
* making the other ranges very wide.
158+
* having to widen any of the existing range values.
159+
*
160+
* 'nsorted' denotes how many of 'nvalues' in the values[] array are sorted.
161+
* When nsorted == nvalues, all single point values are sorted.
158162
*
159163
* We never store more than maxvalues values (as set by values_per_range
160164
* reloption). If needed we merge some of the ranges.
@@ -173,10 +177,10 @@ typedef struct Ranges
173177
FmgrInfo*cmp;
174178

175179
/* (2*nranges + nvalues) <= maxvalues */
176-
intnranges;/* number of ranges in thearray (stored) */
177-
intnsorted;/* number ofsorted values (ranges + points) */
178-
intnvalues;/* number of values inthe dataarray (all) */
179-
intmaxvalues;/*maximumnumber of values (reloption) */
180+
intnranges;/* number of ranges in thevalues[] array */
181+
intnsorted;/* number ofnvalues which are sorted */
182+
intnvalues;/* number ofpointvalues invalues[]array */
183+
intmaxvalues;/* number ofelements in thevalues[] array */
180184

181185
/*
182186
* We simply add the values into a large buffer, without any expensive
@@ -318,102 +322,99 @@ AssertCheckRanges(Ranges *ranges, FmgrInfo *cmpFn, Oid colloid)
318322
* Check that none of the values are not covered by ranges (both sorted
319323
* and unsorted)
320324
*/
321-
for (i=0;i<ranges->nvalues;i++)
325+
if (ranges->nranges>0)
322326
{
323-
Datumcompar;
324-
intstart,
325-
end;
326-
Datumminvalue,
327-
maxvalue;
328-
329-
Datumvalue=ranges->values[2*ranges->nranges+i];
330-
331-
if (ranges->nranges==0)
332-
break;
333-
334-
minvalue=ranges->values[0];
335-
maxvalue=ranges->values[2*ranges->nranges-1];
336-
337-
/*
338-
* Is the value smaller than the minval? If yes, we'll recurse to the
339-
* left side of range array.
340-
*/
341-
compar=FunctionCall2Coll(cmpFn,colloid,value,minvalue);
342-
343-
/* smaller than the smallest value in the first range */
344-
if (DatumGetBool(compar))
345-
continue;
346-
347-
/*
348-
* Is the value greater than the maxval? If yes, we'll recurse to the
349-
* right side of range array.
350-
*/
351-
compar=FunctionCall2Coll(cmpFn,colloid,maxvalue,value);
352-
353-
/* larger than the largest value in the last range */
354-
if (DatumGetBool(compar))
355-
continue;
356-
357-
start=0;/* first range */
358-
end=ranges->nranges-1;/* last range */
359-
while (true)
327+
for (i=0;i<ranges->nvalues;i++)
360328
{
361-
intmidpoint= (start+end) /2;
362-
363-
/* this means we ran out of ranges in the last step */
364-
if (start>end)
365-
break;
329+
Datumcompar;
330+
intstart,
331+
end;
332+
Datumminvalue=ranges->values[0];
333+
Datummaxvalue=ranges->values[2*ranges->nranges-1];
334+
Datumvalue=ranges->values[2*ranges->nranges+i];
366335

367-
/* copy the min/max values from the ranges */
368-
minvalue=ranges->values[2*midpoint];
369-
maxvalue=ranges->values[2*midpoint+1];
336+
compar=FunctionCall2Coll(cmpFn,colloid,value,minvalue);
370337

371338
/*
372-
*Is the value smaller than theminval? If yes, we'll recurse to
373-
*the left sideofrange array.
339+
*If the valueissmaller than thelower bound in the first range
340+
*then it cannot possibly be in anyofthe ranges.
374341
*/
375-
compar=FunctionCall2Coll(cmpFn,colloid,value,minvalue);
376-
377-
/* smaller than the smallest value in this range */
378342
if (DatumGetBool(compar))
379-
{
380-
end= (midpoint-1);
381343
continue;
382-
}
383344

384-
/*
385-
* Is the value greater than the minval? If yes, we'll recurse to
386-
* the right side of range array.
387-
*/
388345
compar=FunctionCall2Coll(cmpFn,colloid,maxvalue,value);
389346

390-
/* larger than the largest value in this range */
347+
/*
348+
* Likewise, if the value is larger than the upper bound of the
349+
* final range, then it cannot possibly be inside any of the
350+
* ranges.
351+
*/
391352
if (DatumGetBool(compar))
392-
{
393-
start= (midpoint+1);
394353
continue;
395-
}
396354

397-
/* hey, we found a matching range */
398-
Assert(false);
355+
/* bsearch the ranges to see if 'value' fits within any of them */
356+
start=0;/* first range */
357+
end=ranges->nranges-1;/* last range */
358+
while (true)
359+
{
360+
intmidpoint= (start+end) /2;
361+
362+
/* this means we ran out of ranges in the last step */
363+
if (start>end)
364+
break;
365+
366+
/* copy the min/max values from the ranges */
367+
minvalue=ranges->values[2*midpoint];
368+
maxvalue=ranges->values[2*midpoint+1];
369+
370+
/*
371+
* Is the value smaller than the minval? If yes, we'll recurse
372+
* to the left side of range array.
373+
*/
374+
compar=FunctionCall2Coll(cmpFn,colloid,value,minvalue);
375+
376+
/* smaller than the smallest value in this range */
377+
if (DatumGetBool(compar))
378+
{
379+
end= (midpoint-1);
380+
continue;
381+
}
382+
383+
/*
384+
* Is the value greater than the minval? If yes, we'll recurse
385+
* to the right side of range array.
386+
*/
387+
compar=FunctionCall2Coll(cmpFn,colloid,maxvalue,value);
388+
389+
/* larger than the largest value in this range */
390+
if (DatumGetBool(compar))
391+
{
392+
start= (midpoint+1);
393+
continue;
394+
}
395+
396+
/* hey, we found a matching range */
397+
Assert(false);
398+
}
399399
}
400400
}
401401

402-
/* and values in the unsorted part must not be in sorted part */
403-
for (i=ranges->nsorted;i<ranges->nvalues;i++)
402+
/* and values in the unsorted part must not be inthesorted part */
403+
if (ranges->nsorted>0)
404404
{
405405
compare_contextcxt;
406-
Datumvalue=ranges->values[2*ranges->nranges+i];
407-
408-
if (ranges->nsorted==0)
409-
break;
410406

411407
cxt.colloid=ranges->colloid;
412408
cxt.cmpFn=ranges->cmp;
413409

414-
Assert(bsearch_arg(&value,&ranges->values[2*ranges->nranges],
415-
ranges->nsorted,sizeof(Datum),
416-
compare_values, (void*)&cxt)==NULL);
410+
for (i=ranges->nsorted;i<ranges->nvalues;i++)
411+
{
412+
Datumvalue=ranges->values[2*ranges->nranges+i];
413+
414+
Assert(bsearch_arg(&value,&ranges->values[2*ranges->nranges],
415+
ranges->nsorted,sizeof(Datum),
416+
compare_values, (void*)&cxt)==NULL);
417+
}
417418
}
418419
#endif
419420
}
@@ -924,8 +925,8 @@ has_matching_range(BrinDesc *bdesc, Oid colloid, Ranges *ranges,
924925
{
925926
Datumcompar;
926927

927-
Datumminvalue=ranges->values[0];
928-
Datummaxvalue=ranges->values[2*ranges->nranges-1];
928+
Datumminvalue;
929+
Datummaxvalue;
929930

930931
FmgrInfo*cmpLessFn;
931932
FmgrInfo*cmpGreaterFn;
@@ -937,6 +938,9 @@ has_matching_range(BrinDesc *bdesc, Oid colloid, Ranges *ranges,
937938
if (ranges->nranges==0)
938939
return false;
939940

941+
minvalue=ranges->values[0];
942+
maxvalue=ranges->values[2*ranges->nranges-1];
943+
940944
/*
941945
* Otherwise, need to compare the new value with boundaries of all the
942946
* ranges. First check if it's less than the absolute minimum, which is

0 commit comments

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