Changeset 21175 in webkit for trunk/JavaScriptCore/wtf

Timestamp:

Apr 28, 2007, 9:25:33 PM (18 years ago)

Author:

darin

Message:

JavaScriptCore:

Reviewed by Maciej.

• fix <rdar://problem/5154144> Hamachi test fails: assertion failure in ListHashSet

Test: fast/forms/add-remove-form-elements-stress-test.html

• wtf/ListHashSet.h: (WTF::ListHashSetNodeAllocator::ListHashSetNodeAllocator): Initialize m_isDoneWithInitialFreeList to false. (WTF::ListHashSetNodeAllocator::allocate): Added assertions based on a debug-only m_isAllocated flag that make sure we don't allocate a block that's already allocated. These assertions helped pinpoint the bug. Set m_isDoneWithInitialFreeList when we allocate the last block of the initial free list. Once we're done with the initial free list, turn off the rule that says that the next node in the pool after the last node in the free list is also free. This rule works because any free nodes are added to the head of the free list, so a node that hasn't been allocated even once is always at the tail of the free list. But it doesn't work any longer once the entire pool has been used at least once. (WTF::ListHashSetNodeAllocator::deallocate): Set the node's m_isAllocated to false. (WTF::ListHashSetNodeAllocator::pastPool): Added. Used above. (WTF::ListHashSetNodeAllocator::inPool): Changed to use the pastPool function. (WTF::ListHashSetNode::ListHashSetNode): Initialize m_isAllocated to true. (WTF::ListHashSetNode::operator new): Removed variable name for unused size parameter. (WTF::ListHashSetNode::destroy): Changed to call the destructor rather than delete -- this gets rid of the need to define an operator delete.

LayoutTests:

Reviewed by Maciej.

• test for <rdar://problem/5154144> Hamachi test fails: assertion failure in ListHashSet

• fast/forms/add-remove-form-elements-stress-test-expected.txt: Added.
• fast/forms/add-remove-form-elements-stress-test.html: Added.

File:

• trunk/JavaScriptCore/wtf/ListHashSet.h (modified) (8 diffs)

trunk/JavaScriptCore/wtf/ListHashSet.h

@@ -1 +1 @@
 // -*- mode: c++; c-basic-offset: 4 -*-
 /*
- * Copyright (C) 2005, 2006, 2007 Apple Inc.
+ * Copyright (C) 2005, 2006, 2007 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
@@ -23 +23 @@
 #define WTF_ListHashSet_h
 
+#include "Assertions.h"
 #include "HashSet.h"
 #include "OwnPtr.h"
@@ -28 +29 @@
 namespace WTF {
 
-    // ListHashSet: just like HashSet, this class provides a Set
+    // ListHashSet: Just like HashSet, this class provides a Set
     // interface - a collection of unique objects with O(1) insertion,
     // removal and test for containership. However, it also has an
@@ -120 +121 @@
         ListHashSetNodeAllocator() 
             : m_freeList(pool())
+            , m_isDoneWithInitialFreeList(false)
         { 
             memset(m_pool.pool, 0, sizeof(m_pool.pool));
@@ -131 +133 @@
                 return static_cast<Node*>(fastMalloc(sizeof(Node)));
 
+            ASSERT(!result->m_isAllocated);
+
             Node* next = result->m_next;
-            if (!next && inPool(result + 1))
+            ASSERT(!next || !next->m_isAllocated);
+            if (!next && !m_isDoneWithInitialFreeList) {
                 next = result + 1;
+                if (next == pastPool()) {
+                    m_isDoneWithInitialFreeList = true;
+                    next = 0;
+                } else {
+                    ASSERT(inPool(next));
+                    ASSERT(!next->m_isAllocated);
+                }
+            }
             m_freeList = next;
-            
+
             return result;
         }
@@ -142 +155 @@
         {
             if (inPool(node)) {
+#ifndef NDEBUG
+                node->m_isAllocated = false;
+#endif
                 node->m_next = m_freeList;
                 m_freeList = node;
@@ -152 +168 @@
     private:
         Node* pool() { return reinterpret_cast<Node*>(m_pool.pool); }
+        Node* pastPool() { return pool() + m_poolSize; }
 
         bool inPool(Node* node)
         {
-            return node >= pool() && node < pool() + m_poolSize;
+            return node >= pool() && node < pastPool();
         }
 
         Node* m_freeList;
+        bool m_isDoneWithInitialFreeList;
         static const size_t m_poolSize = 256;
         union {
@@ -169 +187 @@
         typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;
 
-        ListHashSetNode(ValueArg value) : m_value(value), m_prev(0), m_next(0) {}
-
-        void* operator new(size_t s, NodeAllocator* allocator) { return allocator->allocate(); }
-        void operator delete(void* p) { }
-        void destroy(NodeAllocator* allocator) { delete this; allocator->deallocate(this); }
-        
+        ListHashSetNode(ValueArg value)
+            : m_value(value)
+            , m_prev(0)
+            , m_next(0)
+#ifndef NDEBUG
+            , m_isAllocated(true)
+#endif
+        {
+        }
+
+        void* operator new(size_t, NodeAllocator* allocator)
+        {
+            return allocator->allocate();
+        }
+        void destroy(NodeAllocator* allocator)
+        {
+            this->~ListHashSetNode();
+            allocator->deallocate(this);
+        }
+
         ValueArg m_value;
         ListHashSetNode* m_prev;
         ListHashSetNode* m_next;
+
+#ifndef NDEBUG
+        bool m_isAllocated;
+#endif
     };