Bug 217249 - Add maximum depth check to RedBlackTree
Summary: Add maximum depth check to RedBlackTree
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Tadeu Zagallo
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2020-10-02 14:02 PDT by Tadeu Zagallo
Modified: 2020-10-07 11:05 PDT (History)
8 users (show)

See Also:

Attachments
Patch (5.39 KB, patch)
2020-10-02 14:09 PDT, Tadeu Zagallo 		no flags Details | Formatted Diff | Diff
Patch (5.75 KB, patch)
2020-10-02 15:05 PDT, Tadeu Zagallo 		no flags Details | Formatted Diff | Diff
Patch (7.26 KB, patch)
2020-10-05 11:15 PDT, Tadeu Zagallo 		ews-feeder: commit-queue-
Details | Formatted Diff | Diff
Patch (7.26 KB, patch)
2020-10-05 12:08 PDT, Tadeu Zagallo 		ews-feeder: commit-queue-
Details | Formatted Diff | Diff
Patch (7.55 KB, patch)
2020-10-05 17:05 PDT, Tadeu Zagallo 		no flags Details | Formatted Diff | Diff
Patch (5.79 KB, patch)
2020-10-06 17:52 PDT, Tadeu Zagallo 		no flags Details | Formatted Diff | Diff
Show Obsolete (5) View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Tadeu Zagallo 2020-10-02 14:02:52 PDT 
...
Comment 1 Tadeu Zagallo 2020-10-02 14:09:20 PDT 
Created attachment 410368 [details]
Patch
Comment 2 Tadeu Zagallo 2020-10-02 14:10:16 PDT 
<rdar://problem/69432957>
Comment 3 Tadeu Zagallo 2020-10-02 15:05:39 PDT 
Created attachment 410377 [details]
Patch
Comment 4 Mark Lam 2020-10-02 15:39:24 PDT 
Comment on attachment 410377 [details]
Patch

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

> Source/WTF/wtf/RedBlackTree.h:353
> +            RELEASE_ASSERT(++depth <= s_maximumTreeDepth);

I think this is wrong.  This function iterates over the set of all nodes, not the depth of the tree.  So, this check is incorrect.
Comment 5 Tadeu Zagallo 2020-10-05 11:15:27 PDT 
Created attachment 410532 [details]
Patch
Comment 6 Tadeu Zagallo 2020-10-05 12:08:56 PDT 
Created attachment 410537 [details]
Patch
Comment 7 Tadeu Zagallo 2020-10-05 17:05:44 PDT 
Created attachment 410592 [details]
Patch
Comment 8 Saam Barati 2020-10-06 14:15:18 PDT 
Comment on attachment 410592 [details]
Patch

LGTM, but  let's fix iterate with your idea of making it simpler
Comment 9 Tadeu Zagallo 2020-10-06 17:52:20 PDT 
Created attachment 410720 [details]
Patch
Comment 10 Darin Adler 2020-10-06 18:18:27 PDT 
Comment on attachment 410720 [details]
Patch

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

> Source/WTF/ChangeLog:9
> +        We limit all tree traversals to 128 levels deep. That's a very conservative upper bound that

Is this a security hardening measure? What motivated the change?
Comment 11 Saam Barati 2020-10-06 18:53:30 PDT 
Comment on attachment 410720 [details]
Patch

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

r=me

> Source/WTF/wtf/RedBlackTree.h:353
> +            RELEASE_ASSERT(++size < std::numeric_limits<unsigned>::max());

Just use Checked?
Comment 12 EWS 2020-10-07 11:05:14 PDT 
Committed r268135: <https://trac.webkit.org/changeset/268135>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 410720 [details].