You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucy.apache.org by nw...@apache.org on 2012/04/07 13:42:40 UTC
[lucy-commits] svn commit: r1310742 - /lucy/trunk/core/Lucy/Util/SortUtils.c
Author: nwellnhof
Date: Sat Apr 7 11:42:39 2012
New Revision: 1310742
URL: http://svn.apache.org/viewvc?rev=1310742&view=rev
Log:
Add index check in quicksort code
A buggy or malicious compare function could make us go past the end of the
input buffer.
Modified:
lucy/trunk/core/Lucy/Util/SortUtils.c
Modified: lucy/trunk/core/Lucy/Util/SortUtils.c
URL: http://svn.apache.org/viewvc/lucy/trunk/core/Lucy/Util/SortUtils.c?rev=1310742&r1=1310741&r2=1310742&view=diff
==============================================================================
--- lucy/trunk/core/Lucy/Util/SortUtils.c (original)
+++ lucy/trunk/core/Lucy/Util/SortUtils.c Sat Apr 7 11:42:39 2012
@@ -302,6 +302,7 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t
i++;
comparison1 = compare(context, elems + i, pivot);
if (comparison1 >= 0) { break; }
+ if (i == right) { break; }
}
// Find an element from the right that is less than or equal to the
@@ -310,7 +311,7 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t
j--;
comparison2 = compare(context, elems + j, pivot);
if (comparison2 <= 0) { break; }
- if (j == left) { break; }
+ if (j == left) { break; }
}
// Bail out of loop when we meet in the middle.
@@ -406,6 +407,7 @@ S_qsort8(EIGHT_BYTE_TYPE *elems, int32_t
i++;
comparison1 = compare(context, elems + i, pivot);
if (comparison1 >= 0) { break; }
+ if (i == right) { break; }
}
// Find an element from the right that is less than or equal to the
@@ -414,7 +416,7 @@ S_qsort8(EIGHT_BYTE_TYPE *elems, int32_t
j--;
comparison2 = compare(context, elems + j, pivot);
if (comparison2 <= 0) { break; }
- if (j == left) { break; }
+ if (j == left) { break; }
}
// Bail out of loop when we meet in the middle.
Re: [lucy-dev] Re: [lucy-commits] svn commit: r1310742 - /lucy/trunk/core/Lucy/Util/SortUtils.c
Posted by Nick Wellnhofer <we...@aevum.de>.
On 10/04/2012 18:03, Marvin Humphrey wrote:
> On Tue, Apr 10, 2012 at 3:21 AM, Nick Wellnhofer<we...@aevum.de> wrote:
>> Well, the compare function can be supplied by the user, and I'd prefer that
>> we never segfault on bogus user input.
>
> I didn't think we'd exposed the SortUtils routines to users yet, but fair
> enough.
VA_Sort uses the object's Compare_To function by default, which can be
overridden by users.
> How about we throw an exception, then?
>
> if (i == right) {
> THROW(ERR, "Element failed to test as equal to itself");
> }
Yes, that's even better than to silently ignore the error.
Nick
Re: [lucy-dev] Re: [lucy-commits] svn commit: r1310742 - /lucy/trunk/core/Lucy/Util/SortUtils.c
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Tue, Apr 10, 2012 at 3:21 AM, Nick Wellnhofer <we...@aevum.de> wrote:
> On 10/04/2012 05:23, Marvin Humphrey wrote:
>>
>> On Sat, Apr 7, 2012 at 4:42 AM,<nw...@apache.org> wrote:
>>>On Tue, Apr 10, 2012 at 3:21 AM, Nick Wellnhofer <we...@aevum.de> wrote:
> On 10/04/2012 05:23, Marvin Humphrey wrote:
>> If compare(pivot, pivot) returns anything other than 0, we've got big
>> problems.
>
> That's what happened with Integer64s.
Heh... so we've detected the error (eventually)... Victory! ;)
>> I don't think it's in our interest to hide such an error -- better
>> to learn about it as quickly as possible by running off the end of the
>> array and segfaulting.
>
>
> Well, the compare function can be supplied by the user, and I'd prefer that
> we never segfault on bogus user input.
I didn't think we'd exposed the SortUtils routines to users yet, but fair
enough.
How about we throw an exception, then?
if (i == right) {
THROW(ERR, "Element failed to test as equal to itself");
}
If equal elements do not test as equal, the sort is unstable. That can lead
to very subtle and difficult to diagnose bugs.
I don't adding the exception block it will interfere with any compiler
optimizations, since it's not within a leaf block -- we already CALL the
comparator.
Marvin Humphrey
Re: [lucy-dev] Re: [lucy-commits] svn commit: r1310742 - /lucy/trunk/core/Lucy/Util/SortUtils.c
Posted by Nick Wellnhofer <we...@aevum.de>.
On 10/04/2012 05:23, Marvin Humphrey wrote:
> On Sat, Apr 7, 2012 at 4:42 AM,<nw...@apache.org> wrote:
>> Author: nwellnhof
>> Date: Sat Apr 7 11:42:39 2012
>> New Revision: 1310742
>>
>> URL: http://svn.apache.org/viewvc?rev=1310742&view=rev
>> Log:
>> Add index check in quicksort code
>>
>> A buggy or malicious compare function could make us go past the end of the
>> input buffer.
>
>> --- lucy/trunk/core/Lucy/Util/SortUtils.c (original)
>> +++ lucy/trunk/core/Lucy/Util/SortUtils.c Sat Apr 7 11:42:39 2012
>> @@ -302,6 +302,7 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t
>> i++;
>> comparison1 = compare(context, elems + i, pivot);
>> if (comparison1>= 0) { break; }
>> + if (i == right) { break; }
>> }
>
> This probably wasn't obvious, but when (i == right), that's the "pivot"
> element. Therefore, the comparison routine is comparing "pivot" against
> itself.
>
> If compare(pivot, pivot) returns anything other than 0, we've got big
> problems.
That's what happened with Integer64s.
> I don't think it's in our interest to hide such an error -- better
> to learn about it as quickly as possible by running off the end of the array
> and segfaulting.
Well, the compare function can be supplied by the user, and I'd prefer
that we never segfault on bogus user input.
Nick
[lucy-dev] Re: [lucy-commits] svn commit: r1310742 - /lucy/trunk/core/Lucy/Util/SortUtils.c
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Sat, Apr 7, 2012 at 4:42 AM, <nw...@apache.org> wrote:
> Author: nwellnhof
> Date: Sat Apr 7 11:42:39 2012
> New Revision: 1310742
>
> URL: http://svn.apache.org/viewvc?rev=1310742&view=rev
> Log:
> Add index check in quicksort code
>
> A buggy or malicious compare function could make us go past the end of the
> input buffer.
> --- lucy/trunk/core/Lucy/Util/SortUtils.c (original)
> +++ lucy/trunk/core/Lucy/Util/SortUtils.c Sat Apr 7 11:42:39 2012
> @@ -302,6 +302,7 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t
> i++;
> comparison1 = compare(context, elems + i, pivot);
> if (comparison1 >= 0) { break; }
> + if (i == right) { break; }
> }
This probably wasn't obvious, but when (i == right), that's the "pivot"
element. Therefore, the comparison routine is comparing "pivot" against
itself.
If compare(pivot, pivot) returns anything other than 0, we've got big
problems. I don't think it's in our interest to hide such an error -- better
to learn about it as quickly as possible by running off the end of the array
and segfaulting.
I also think we should try hard not to make the SortUtils.c code any more
complex than it already is. (I'd love to see us consolidate the "four-byte"
and "eight-byte" sections down to one.)
Marvin Humphrey