On 1/11/25 4:09 AM, Kuan-Wei Chiu wrote:
> Hi Ruediger,
>
> On Thu, Jan 09, 2025 at 08:54:13AM +0100, Ruediger Pluem wrote:
>>
>>
>> On 1/8/25 7:00 PM, jor...@apache.org wrote:
>>> Author: jorton
>>> Date: Wed Jan 8 18:00:29 2025
>>> New Revision: 1922994
>>>
>>> URL: http://svn.apache.org/viewvc?rev=1922994&view=rev
>>> Log:
>>> * modules/generators/mod_autoindex.c (dsortf): Ensure the function
>>> is transitive to avoid undefined behaviour, per:
>>> https://www.qualys.com/2024/01/30/qsort.txt
>>>
>>> Submitted by: Kuan-Wei Chiu <visitorckw gmail.com>
>>> Github: closes #500
>>>
>>> Modified:
>>> httpd/httpd/trunk/modules/generators/mod_autoindex.c
>>>
>>> Modified: httpd/httpd/trunk/modules/generators/mod_autoindex.c
>>> URL:
>>> http://svn.apache.org/viewvc/httpd/httpd/trunk/modules/generators/mod_autoindex.c?rev=1922994&r1=1922993&r2=1922994&view=diff
>>> ==============================================================================
>>> --- httpd/httpd/trunk/modules/generators/mod_autoindex.c (original)
>>> +++ httpd/httpd/trunk/modules/generators/mod_autoindex.c Wed Jan 8
>>> 18:00:29 2025
>>> @@ -1923,8 +1923,13 @@ static int dsortf(struct ent **e1, struc
>>>
>>> /*
>>> * First, see if either of the entries is for the parent directory.
>>> - * If so, that *always* sorts lower than anything else.
>>> + * If so, that *always* sorts lower than anything else. The
>>> + * function must be transitive else behaviour is undefined, although
>>> + * in no real case should both entries start with a '/'.
>>> */
>>> + if ((*e1)->name[0] == '/' && (*e2)->name[0] == '/') {
>>> + return 0;
>>> + }
>>> if ((*e1)->name[0] == '/') {
>>> return -1;
>>> }
>>>
>>>
>>
>> I am fine with the change and sorry for getting into a theoretical
>> discussion here, but I think the function before the patch was
>> transitive (at least regarding to the '/' topic. I have not checked other
>> cases):
>>
>> Let's assume x = '/', y = '/', z = '/'
>>
>> dsortf(x, y) == -1
>> dsortf(y, z) == -1
>> dsortf(x, z) == -1
>>
>> Transitive
>
> Thanks for your review!
>
> I initially didn't think this through carefully. However, I'll include
> in the explanation that violating transitivity considers the following
> case:
>
> x = '/', y = '/', z = '/'
>
> dsortf(x, y) == -1
> dsortf(y, z) == -1
> dsortf(z, x) == -1
>
> This leads to the conclusion x < y && y < z && z < x, which might also
> count as a violation of transitivity since it should ensure z > x ?
But dsortf(x, z) == -1 and hence z > x, but as dsortf(z, x) == -1 => x < z.
The core issue remains that dsortf is not reflexive and not antisymetric.
This leads to the weird situation above that x < z and z < x at the same time.
Regards
Rüdiger
