This is the mail archive of the mailing list for the glibc project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH v3] powerpc: strstr optimization

"Carlos O'Donell" <> writes:

> On 07/22/2015 12:12 PM, Joseph Myers wrote:
>> On Thu, 16 Jul 2015, Carlos O'Donell wrote:
>>> On 07/16/2015 03:55 PM, OndÅej BÃlka wrote:
>>>> On Wed, Jul 15, 2015 at 09:40:00PM -0400, Carlos O'Donell wrote:
>>>>> On 07/15/2015 08:43 PM, Carlos O'Donell wrote:
>>>>>>> May I proceed with this commit?
>>>>>> Yes, please commit this for 2.22.
>>>>> For the record I trust IBM to make sure these patches make incremental
>>>>> improvements in performance even if they are not the best possible
>>>>> performance as pointed out by Ondrej Bilka.
>>>> Sorry Carlos, your trust is misplaced. This patch wasn't reviewed at
>>>> all. I did that as test how much we could test IBM to verify patches. 
>>>> I pointed out that it could have possibly quadratic behaviour which
>>>> still does. So please don't accept unreviewed patches next time.
>>> They showed cases for which the code does go faster and objectively
>>> so using the microbenchmark, and that's a win for now. Please continue 
>>> to work with IBM to remove the quadratic worst case.
>>> Tulio, You will need to work out why you have quadratic worst case.
>>> It's certainly something we try to avoid. Did you make a particular
>>> decision not to avoid it?
>> If there's a quadratic worst case newly introduced for 2.22, I'd consider 
>> that a security hole (denial of service) that needs to block the release 
>> of 2.22 until it's fixed (possibly by removing the implementation in 
>> question).

Could you elaborate why a quadratic worst case in a string function can be
considered a denial of service, please?

> Tulio,
> Could you please review the possibility of quadratic behaviour and respond
> prompty? I don't want this to hold up the release.

I confirm this algorithm does have a quadratic worst case, which appears if
needle <= 2048.
If the needle > 2048, it falls back to the previous implementation.

Tulio Magno

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]