Title: [269085] branches/safari-610-branch/Source/WTF
- Revision
- 269085
- Author
- [email protected]
- Date
- 2020-10-27 18:42:45 -0700 (Tue, 27 Oct 2020)
Log Message
Cherry-pick r268135. rdar://problem/70733407
Add maximum depth check to RedBlackTree
https://bugs.webkit.org/show_bug.cgi?id=217249
<rdar://problem/69432957>
Reviewed by Saam Barati.
We limit all tree traversals to 128 levels deep. That's a very conservative upper bound that
would work for a tree that used all of the available address space.
* wtf/RedBlackTree.h:
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@268135 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Modified Paths
Diff
Modified: branches/safari-610-branch/Source/WTF/ChangeLog (269084 => 269085)
--- branches/safari-610-branch/Source/WTF/ChangeLog 2020-10-28 01:36:51 UTC (rev 269084)
+++ branches/safari-610-branch/Source/WTF/ChangeLog 2020-10-28 01:42:45 UTC (rev 269085)
@@ -1,3 +1,34 @@
+2020-10-27 Russell Epstein <[email protected]>
+
+ Cherry-pick r268135. rdar://problem/70733407
+
+ Add maximum depth check to RedBlackTree
+ https://bugs.webkit.org/show_bug.cgi?id=217249
+ <rdar://problem/69432957>
+
+ Reviewed by Saam Barati.
+
+ We limit all tree traversals to 128 levels deep. That's a very conservative upper bound that
+ would work for a tree that used all of the available address space.
+
+ * wtf/RedBlackTree.h:
+
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@268135 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 2020-10-07 Tadeu Zagallo <[email protected]>
+
+ Add maximum depth check to RedBlackTree
+ https://bugs.webkit.org/show_bug.cgi?id=217249
+ <rdar://problem/69432957>
+
+ Reviewed by Saam Barati.
+
+ We limit all tree traversals to 128 levels deep. That's a very conservative upper bound that
+ would work for a tree that used all of the available address space.
+
+ * wtf/RedBlackTree.h:
+
2020-10-15 Russell Epstein <[email protected]>
Cherry-pick r268367. rdar://problem/70321875
Modified: branches/safari-610-branch/Source/WTF/wtf/RedBlackTree.h (269084 => 269085)
--- branches/safari-610-branch/Source/WTF/wtf/RedBlackTree.h 2020-10-28 01:36:51 UTC (rev 269084)
+++ branches/safari-610-branch/Source/WTF/wtf/RedBlackTree.h 2020-10-28 01:42:45 UTC (rev 269085)
@@ -46,6 +46,8 @@
WTF_MAKE_NONCOPYABLE(RedBlackTree);
WTF_MAKE_FAST_ALLOCATED;
private:
+ static constexpr unsigned s_maximumTreeDepth = 128;
+
enum Color {
Red = 1,
Black
@@ -62,7 +64,9 @@
if (x->right())
return treeMinimum(x->right());
const NodeType* y = x->parent();
+ unsigned depth = 0;
while (y && x == y->right()) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
x = y;
y = y->parent();
}
@@ -75,7 +79,9 @@
if (x->left())
return treeMaximum(x->left());
const NodeType* y = x->parent();
+ unsigned depth = 0;
while (y && x == y->left()) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
x = y;
y = y->parent();
}
@@ -163,7 +169,9 @@
treeInsert(x);
x->setColor(Red);
+ unsigned depth = 0;
while (x != m_root && x->parent()->color() == Red) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
if (x->parent() == x->parent()->parent()->left()) {
NodeType* y = x->parent()->parent()->right();
if (y && y->color() == Red) {
@@ -283,7 +291,9 @@
NodeType* findExact(const KeyType& key) const
{
+ unsigned depth = 0;
for (NodeType* current = m_root; current;) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
if (current->key() == key)
return current;
if (key < current->key())
@@ -297,7 +307,9 @@
NodeType* findLeastGreaterThanOrEqual(const KeyType& key) const
{
NodeType* best = nullptr;
+ unsigned depth = 0;
for (NodeType* current = m_root; current;) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
if (current->key() == key)
return current;
if (current->key() < key)
@@ -313,7 +325,9 @@
NodeType* findGreatestLessThanOrEqual(const KeyType& key) const
{
NodeType* best = nullptr;
+ unsigned depth = 0;
for (NodeType* current = m_root; current;) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
if (current->key() == key)
return current;
if (current->key() > key)
@@ -333,8 +347,10 @@
return;
Vector<NodeType*, 16> toIterate;
+ unsigned size = 0;
toIterate.append(m_root);
while (toIterate.size()) {
+ RELEASE_ASSERT(++size < std::numeric_limits<unsigned>::max());
NodeType& current = *toIterate.takeLast();
bool iterateLeft = false;
bool iterateRight = false;
@@ -380,29 +396,41 @@
// node.
static NodeType* treeMinimum(NodeType* x)
{
- while (x->left())
+ unsigned depth = 0;
+ while (x->left()) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
x = x->left();
+ }
return x;
}
static NodeType* treeMaximum(NodeType* x)
{
- while (x->right())
+ unsigned depth = 0;
+ while (x->right()) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
x = x->right();
+ }
return x;
}
static const NodeType* treeMinimum(const NodeType* x)
{
- while (x->left())
+ unsigned depth = 0;
+ while (x->left()) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
x = x->left();
+ }
return x;
}
static const NodeType* treeMaximum(const NodeType* x)
{
- while (x->right())
+ unsigned depth = 0;
+ while (x->right()) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
x = x->right();
+ }
return x;
}
@@ -415,7 +443,9 @@
NodeType* y = nullptr;
NodeType* x = m_root;
+ unsigned depth = 0;
while (x) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
y = x;
if (z->key() < x->key())
x = x->left();
@@ -502,7 +532,9 @@
// supplied.
void removeFixup(NodeType* x, NodeType* xParent)
{
+ unsigned depth = 0;
while (x != m_root && (!x || x->color() == Black)) {
+ RELEASE_ASSERT(++depth <= s_maximumTreeDepth);
if (x == xParent->left()) {
// Note: the text points out that w can not be null.
// The reason is not obvious from simply looking at
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
