[PATCH v2 3/3] wcsmbs: Ensure wcstr worst-case linear execution time (BZ 23865)

[Adhemerval Zanella Netto]

On 01/03/24 16:23, DJ Delorie wrote:
> Adhemerval Zanella Netto <adhemerval.zanella@linaro.org> writes:
>>>> +    for (; repeat > 0; repeat--)
>>>> +      {
>>>> +	FOR_EACH_IMPL (impl, 0)
>>>> +	  check_result (impl, haystack, needle, haystack + 1);
>>>> +      }
>>>
>>> What is the purpose of the repeat loop?  This function is only called
>>> once, and not timed...
>>>
>>> The test itself is OK.
>>
>> I copied this tests from gnulib (9411c5e467cf60f6295b9fed306029f341a0f24f)
>> and my understanding is to enforce that wcsstr won't take too much time
>> by triggering a timeout.  These kind of pattern are slower for newer 
>> implementation compared to the current one.
>>
>> The repeat number is indeed arbitrary and depending of the hardware should 
>> not make any different (on my box I only see some different with way larger
>> inputs).
> 
> My point is, there isn't anything in the test that either (1) computes
> how long the test takes, or (2) has a way to FAIL the test if the
> timings are off.  I.e. you are not testing for the bug you're fixing.
> 
> Given how common it is to set TIMEOUTFACTOR to some large value when
> running tests, I don't think relying on a timeout - for anything other
> than "infinite time" - is reasonable.

Fair enough, although I still some value in adding tests that might trigger
quadratic behavior on possible quadradic implementation.  I agree that the
loop adds little gain and I think it would be better to just remove it.

> 
>>>> +	FOR_EACH_IMPL (impl, 0)
>>>> +	  check_result (impl, haystack, needle, NULL);
>>>> +      }
>>>> +
>>>> +    free (needle);
>>>> +  }
>>>
>>> Test OK but question the repeat look.
> 
> Same here.
> 
>>>> +    FOR_EACH_IMPL (impl, 0)
>>>> +      check_result (impl, haystack, needle, haystack + m);
>>>
>>> Without timing it, how do we test that it is not quadratic?
>>
>> Because on current implementation it takes forever (about 4 minutes
>> on my box) due the input sizes.
> 
> Same here.  Nobody will notice the 4 minute test time in a scripted CI
> environment unless the test returns FAIL.
> 

I think we can still enforce a timer without being subject to TIMEOUTFACTOR
by using support_create_timer.