Bug 235177

Summary: Fix WTF::UUID's potential collision with empty and deleted values
Product: WebKit Reporter: Yusuke Suzuki <ysuzuki>
Component: New BugsAssignee: Yusuke Suzuki <ysuzuki>
Status: RESOLVED FIXED    
Severity: Normal CC: andersca, benjamin, cdumez, cmarcelo, ews-watchlist, mitz, simon.fraser, webkit-bug-importer
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch
none
Patch
ews-feeder: commit-queue-
Patch none

Description Yusuke Suzuki 2022-01-13 04:07:06 PST
Fix WTF::UUID's potential collision with empty and deleted values
Comment 1 Yusuke Suzuki 2022-01-13 04:10:02 PST
Created attachment 449042 [details]
Patch
Comment 2 Yusuke Suzuki 2022-01-13 04:11:24 PST
Created attachment 449043 [details]
Patch
Comment 3 Anders Carlsson 2022-01-13 08:21:36 PST
Wouldn't it be better to instead have WTF:UUID generate Version 4 UUIDs and maybe use two reserved UUIDs as the empty and deleted values?

https://en.wikipedia.org/wiki/Universally_unique_identifier#Version_4_(random)
Comment 4 Yusuke Suzuki 2022-01-13 09:42:57 PST
(In reply to Anders Carlsson from comment #3)
> Wouldn't it be better to instead have WTF:UUID generate Version 4 UUIDs and
> maybe use two reserved UUIDs as the empty and deleted values?
> 
> https://en.wikipedia.org/wiki/
> Universally_unique_identifier#Version_4_(random)

For now, I would like to just fix the serious bug which can corrupt our hash table in this patch.
Comment 5 Chris Dumez 2022-01-13 10:00:52 PST
Comment on attachment 449043 [details]
Patch

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

> Source/WTF/wtf/UUID.cpp:48
>      cryptographicallyRandomValues(reinterpret_cast<unsigned char*>(&m_data), 16);

Could we do something like this instead of hard-coding 2?
```
do {
    cryptographicallyRandomValues(reinterpret_cast<unsigned char*>(&m_data), 16);
} while (m_data == emptyValue || m_data == deletedValue);
```

> Source/WTF/wtf/UUID.h:106
> +    encoder << static_cast<uint64_t>(m_data >> 64) << static_cast<uint64_t>(m_data);

Why is this better?

> Source/WTF/wtf/UUID.h:122
> +    return UUID { (static_cast<UInt128>(*high) << 64) | *low };

ditto.
Comment 6 Yusuke Suzuki 2022-01-13 10:05:21 PST
Comment on attachment 449043 [details]
Patch

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

>> Source/WTF/wtf/UUID.cpp:48
>>      cryptographicallyRandomValues(reinterpret_cast<unsigned char*>(&m_data), 16);
> 
> Could we do something like this instead of hard-coding 2?
> ```
> do {
>     cryptographicallyRandomValues(reinterpret_cast<unsigned char*>(&m_data), 16);
> } while (m_data == emptyValue || m_data == deletedValue);
> ```

Sounds good. Changed.

>> Source/WTF/wtf/UUID.h:106
>> +    encoder << static_cast<uint64_t>(m_data >> 64) << static_cast<uint64_t>(m_data);
> 
> Why is this better?

UInt128High64 / UInt128Low64 are implementation's detail function.
UInt128 is attempting to support native data structure. And using these implementation detail function prevents us from removing these emulation layer when all compiler supports 128bit native integer primitives.

>> Source/WTF/wtf/UUID.h:122
>> +    return UUID { (static_cast<UInt128>(*high) << 64) | *low };
> 
> ditto.

Ditto. It is implementation detail function, which should not be used by user code.
Comment 7 Yusuke Suzuki 2022-01-13 10:09:41 PST
Created attachment 449076 [details]
Patch
Comment 8 Chris Dumez 2022-01-13 10:17:34 PST
Comment on attachment 449076 [details]
Patch

r=me
Comment 9 Chris Dumez 2022-01-14 08:52:34 PST
Are we landing this?
Comment 10 Yusuke Suzuki 2022-01-14 09:57:30 PST
(In reply to Chris Dumez from comment #9)
> Are we landing this?

I was waiting for the complete of all EWS, and it finished. So now, landing...
Comment 11 EWS 2022-01-14 10:12:05 PST
Committed r288020 (246046@main): <https://commits.webkit.org/246046@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 449076 [details].
Comment 12 Radar WebKit Bug Importer 2022-01-14 10:13:17 PST
<rdar://problem/87606347>
Comment 13 Simon Fraser (smfr) 2022-01-14 10:15:38 PST
Comment on attachment 449076 [details]
Patch

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

> Source/WTF/ChangeLog:10
> +        and used, it can break hash tables. This patch avoids that by picking 2 when we generate 0 or 1.

Seems to not match the code? It just generates another one.
Comment 14 Yusuke Suzuki 2022-01-14 10:31:16 PST
Comment on attachment 449076 [details]
Patch

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

>> Source/WTF/ChangeLog:10
>> +        and used, it can break hash tables. This patch avoids that by picking 2 when we generate 0 or 1.
> 
> Seems to not match the code? It just generates another one.

Ah, I forgot updating it while changing the implementation based on Chris's comment.