Re: svn commit: r1922994 - /httpd/httpd/trunk/modules/generators/mod_autoindex.c

[Ruediger Pluem]

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 
>>> 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

Re: svn commit: r1922994 - /httpd/httpd/trunk/modules/generators/mod_autoindex.c

[Ruediger Pluem]

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 
> 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

Let's assume x = !'/', y = '/', z = '/'

dsortf(x, y) == 1
dsortf(y, z) == -1
dsortf(x, z) == 1

But as the first two do not deliver the same results it does not matter.

Let's assume x = '/', y = !'/', z = '/'

dsortf(x, y) == -1
dsortf(y, z) == 1
dsortf(x, z) == -1

But as the first two do not deliver the same results it does not matter.

Let's assume x = '/', y = '/', z = !'/'

dsortf(x, y) == -1
dsortf(y, z) == -1
dsortf(x, z) == -1

Transitive

Let's assume x = !'/', y = !'/', z = '/'

dsortf(x, y) ==  whatever
dsortf(y, z) == 1
dsortf(x, z) == 1

If whatever == 1 it is transitive if not it does not matter as the first two do 
not deliver the same results


Let's assume x = '/', y = !'/', z = !'/'

dsortf(x, y) == -1
dsortf(y, z) == whatever
dsortf(x, z) == -1

If whatever == -1 it is transitive if not it does not matter as the first two 
do not deliver the same results

Or did I miss a case related to '/'?


The unpatched version is not reflexive though:

dsortf('/', '/') should be 0 but it is -1. After the patch it is 0.

The unpatched version is also not antisymmetric:

as dsortf('/', '/') != -dsortf('/', '/')

After the patch: dsortf('/', '/') == -dsortf('/', '/')



Regards

Rüdiger