Bug 192853

Summary: WTF::String and StringImpl overflow MaxLength
Product: WebKit Reporter: Tadeu Zagallo <tzagallo>
Component: JavaScriptCoreAssignee: Tadeu Zagallo <tzagallo>
Status: RESOLVED FIXED    
Severity: Normal CC: benjamin, cdumez, cmarcelo, commit-queue, dbates, ews-watchlist, keith_miller, mark.lam, msaboff, sbarati, webkit-bug-importer
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch
none
Patch
none
Patch for landing none

Description Tadeu Zagallo 2018-12-19 07:02:26 PST
...
Comment 1 Tadeu Zagallo 2018-12-19 07:04:22 PST
<rdar://problem/45726906>
Comment 2 Tadeu Zagallo 2018-12-19 07:11:00 PST
Created attachment 357678 [details]
Patch
Comment 3 Tadeu Zagallo 2018-12-19 15:37:21 PST
Created attachment 357741 [details]
Patch
Comment 4 Keith Miller 2018-12-19 15:45:37 PST
Comment on attachment 357741 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357741&action=review

r=me

> Source/WTF/wtf/text/StringImpl.h:575
> +template<typename CharacterType> size_t reverseFindLineTerminator(const CharacterType*, unsigned length, unsigned index = StringImpl::MaxLength);
> +template<typename CharacterType> size_t reverseFind(const CharacterType*, unsigned length, CharacterType matchCharacter, unsigned index = StringImpl::MaxLength);
> +size_t reverseFind(const UChar*, unsigned length, LChar matchCharacter, unsigned index = StringImpl::MaxLength);
> +size_t reverseFind(const LChar*, unsigned length, UChar matchCharacter, unsigned index = StringImpl::MaxLength);

Nit: You don't need the "StringImpl::" here
Comment 5 Mark Lam 2018-12-19 15:47:07 PST
Comment on attachment 357741 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357741&action=review

> Source/WTF/wtf/text/StringImpl.cpp:196
> +    if (length > std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)))

Would it be possible to use a template function like this?

    template<typename CharacterType>
    constexpr size_t maxUtf8Length() { return std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)); }

constexpr would be nice, but if that doesn't work, just change it to inline instead.  This allows you to define this limit in one place instead of 3.

> Source/WTF/wtf/text/StringImpl.cpp:225
> +    if (length > std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)))

Use maxUtf8Length<CharacterType>() instead.

> Source/WTF/wtf/text/StringImpl.h:957
> +    if (length > std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType))) {

Use maxUtf8Length<CharacterType> instead.
Comment 6 Mark Lam 2018-12-19 15:51:14 PST
Comment on attachment 357741 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357741&action=review

>> Source/WTF/wtf/text/StringImpl.cpp:196
>> +    if (length > std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)))
> 
> Would it be possible to use a template function like this?
> 
>     template<typename CharacterType>
>     constexpr size_t maxUtf8Length() { return std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)); }
> 
> constexpr would be nice, but if that doesn't work, just change it to inline instead.  This allows you to define this limit in one place instead of 3.

I forgot: this should be a static method.
Comment 7 Mark Lam 2018-12-19 16:00:24 PST
Comment on attachment 357741 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357741&action=review

>>> Source/WTF/wtf/text/StringImpl.cpp:196
>>> +    if (length > std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)))
>> 
>> Would it be possible to use a template function like this?
>> 
>>     template<typename CharacterType>
>>     constexpr size_t maxUtf8Length() { return std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)); }
>> 
>> constexpr would be nice, but if that doesn't work, just change it to inline instead.  This allows you to define this limit in one place instead of 3.
> 
> I forgot: this should be a static method.

Wait a minute.  I don't get this.  Why take the min of MaxLength and (std::numeric_limits<unsigned>::max() - sizeof(StringImpl))?
Comment 8 Mark Lam 2018-12-19 16:23:14 PST
Comment on attachment 357741 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=357741&action=review

>>>> Source/WTF/wtf/text/StringImpl.cpp:196
>>>> +    if (length > std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)))
>>> 
>>> Would it be possible to use a template function like this?
>>> 
>>>     template<typename CharacterType>
>>>     constexpr size_t maxUtf8Length() { return std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType)); }
>>> 
>>> constexpr would be nice, but if that doesn't work, just change it to inline instead.  This allows you to define this limit in one place instead of 3.
>> 
>> I forgot: this should be a static method.
> 
> Wait a minute.  I don't get this.  Why take the min of MaxLength and (std::numeric_limits<unsigned>::max() - sizeof(StringImpl))?

OK, I get it:
1. The actual bytes allocated is allocationSize<CharacterType>(length) which adds the sizeof(StringImpl) to length * sizeof(CharacterType).
2. For an 8bit char, the limit we'll use is always MaxLength.
3. For a 16-bit char, the limit can't be MaxLength because at MaxLength, length * sizeof(CharacterType) is already equal to UINT_MAX.  Hence, adding sizeof(StringImpl) would overflow length.

This also means that my choice of name for the method maxUtf8Length() is wrong.  This has nothing to do with utf8 strings.  Can you do use a method instead:

    template<typename CharacterType>
    static constexpr unsigned maxInternalLength()
    {
        // In order to not overflow the unsigned length, the check for (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) is needed when sizeof(CharacterType) == 2.
        return std::min(static_cast<size_t>(MaxLength), (std::numeric_limits<unsigned>::max() - sizeof(StringImpl)) / sizeof(CharacterType));
    }

Sorry for the r- noise earlier.
Comment 9 Tadeu Zagallo 2018-12-20 07:28:55 PST
Created attachment 357811 [details]
Patch for landing
Comment 10 WebKit Commit Bot 2018-12-20 08:06:55 PST
Comment on attachment 357811 [details]
Patch for landing

Clearing flags on attachment: 357811

Committed r239439: <https://trac.webkit.org/changeset/239439>
Comment 11 WebKit Commit Bot 2018-12-20 08:06:57 PST
All reviewed patches have been landed.  Closing bug.