Changeset 153635 in webkit

Timestamp:

Aug 1, 2013, 11:01:54 PM (12 years ago)

Author:

mrowe@apple.com

Message:

<rdar://problem/14528244> False-positive leaks from FastMalloc.

A logic error in the page map enumeration code within FastMalloc could result in a subset of the memory regions
owned by FastMalloc being skipped by the malloc zone enumeration code used by leaks and other performance tools.
If the only reference to an allocated object lived within one of the skipped memory regions, leaks would believe
it had been leaked since it would not find any references to the object.

The logic error manifested when a FastMalloc span owned a region of memory that crossed a 16MB address space boundary,
and when there was one or more other spans immediately after it in the address space. Crossing the 16MB address space
boundary means that the start and end points of the span are in different leaf nodes of the page map trie, and the
code within the page map's visitValues method didn't correctly account this case when skipping to the end of the span
after visiting it. It would resume iterating from the start of the next leaf node rather than continuing to skip values
until the end of the span was passed. The value representing the end of the span would then be processed as if it were
the start of a new span, and more values would be skipped even though they may contain actual spans.

The solution is to rework the algorithm used in visitValues so that it will skip the correct number of values even when
some of the values are in different leaf nodes. This is a more involved change than it may seem since it's also necessary
to deal with the case where a memory region spans two separate root nodes, which can happen if the region happens to cross
a 64GB boundary in the address space.

Reviewed by Geoff Garen.

• wtf/TCPageMap.h:

(TCMalloc_PageMap3::visitValues): Use a single loop to iterate, with the loop index being the key in to the page map in the
same form as used by get and set. This allows us to correctly deal with the index being skipped to a different intermediate or
root node as a result of visiting a span that crosses a 16MB boundary in memory.
(TCMalloc_PageMap2::visitValues): Ditto, but without having to deal with intermediate nodes.

Location:

trunk/Source/WTF

Files:

• ChangeLog (modified) (1 diff)
• wtf/TCPageMap.h (modified) (2 diffs)

trunk/Source/WTF/ChangeLog

@@ +1 @@
+2013-08-01  Mark Rowe  <mrowe@apple.com>
+
+        <rdar://problem/14528244> False-positive leaks from FastMalloc.
+
+        A logic error in the page map enumeration code within FastMalloc could result in a subset of the memory regions
+        owned by FastMalloc being skipped by the malloc zone enumeration code used by leaks and other performance tools.
+        If the only reference to an allocated object lived within one of the skipped memory regions, leaks would believe
+        it had been leaked since it would not find any references to the object.
+
+        The logic error manifested when a FastMalloc span owned a region of memory that crossed a 16MB address space boundary,
+        and when there was one or more other spans immediately after it in the address space. Crossing the 16MB address space
+        boundary means that the start and end points of the span are in different leaf nodes of the page map trie, and the
+        code within the page map's visitValues method didn't correctly account this case when skipping to the end of the span
+        after visiting it. It would resume iterating from the start of the next leaf node rather than continuing to skip values
+        until the end of the span was passed. The value representing the end of the span would then be processed as if it were
+        the start of a new span, and more values would be skipped even though they may contain actual spans.
+
+        The solution is to rework the algorithm used in visitValues so that it will skip the correct number of values even when
+        some of the values are in different leaf nodes. This is a more involved change than it may seem since it's also necessary
+        to deal with the case where a memory region spans two separate root nodes, which can happen if the region happens to cross
+        a 64GB boundary in the address space.
+
+        Reviewed by Geoff Garen.
+
+        * wtf/TCPageMap.h:
+        (TCMalloc_PageMap3::visitValues): Use a single loop to iterate, with the loop index being the key in to the page map in the
+        same form as used by get and set. This allows us to correctly deal with the index being skipped to a different intermediate or
+        root node as a result of visiting a span that crosses a 16MB boundary in memory.
+        (TCMalloc_PageMap2::visitValues): Ditto, but without having to deal with intermediate nodes.
+
 2013-08-01  Ruth Fong  <ruth_fong@apple.com>
 

trunk/Source/WTF/wtf/TCPageMap.h

@@ -159 +159 @@
   void visitValues(Visitor& visitor, const MemoryReader& reader)
   {
-    for (int i = 0; i < ROOT_LENGTH; i++) {
-      if (!root_[i])
-        continue;
-
-      Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i]));
-      for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j]))
-        ;
+    const Number leafIndexMask = LEAF_LENGTH - 1;
+
+    const Number maxKey = (1l << BITS) - 1;
+    const Number invalidIndex = maxKey;
+    Number previousRootIndex = invalidIndex;
+
+    Leaf* leaf = 0;
+
+    for (Number key = 0; key < maxKey; ) {
+      const Number rootIndex = key >> LEAF_BITS;
+      const Number leafIndex = key & leafIndexMask;
+
+      if (rootIndex != previousRootIndex) {
+        if (!root_[rootIndex]) {
+          // There's no node at this index. Move on to the next index at the root level,
+          // clearing the leaf index so that we start from the beginning of the next node.
+          key += 1 << LEAF_BITS;
+          key &= ~leafIndexMask;
+          continue;
+        }
+
+        leaf = reader(root_[rootIndex]);
+        previousRootIndex = rootIndex;
+      }
+
+      key += visitor.visit(leaf->values[leafIndex]);
     }
   }
@@ -268 +287 @@
   template<class Visitor, class MemoryReader>
   void visitValues(Visitor& visitor, const MemoryReader& reader) {
+    const Number intermediateIndexMask = (INTERIOR_LENGTH - 1) << LEAF_BITS;
+    const Number leafIndexMask = LEAF_LENGTH - 1;
+
+    const Number maxKey = (1l << BITS) - 1;
+    const Number invalidIndex = maxKey;
+    Number previousRootIndex = invalidIndex;
+    Number previousIntermediateIndex = invalidIndex;
+
+    Node* intermediateNode = 0;
+    Leaf* leaf = 0;
+
     Node* root = reader(root_);
-    for (int i = 0; i < INTERIOR_LENGTH; i++) {
-      if (!root->ptrs[i])
-        continue;
-
-      Node* n = reader(root->ptrs[i]);
-      for (int j = 0; j < INTERIOR_LENGTH; j++) {
-        if (!n->ptrs[j])
+    for (Number key = 0; key < maxKey; ) {
+      const Number rootIndex = key >> (LEAF_BITS + INTERIOR_BITS);
+      const Number intermediateIndex = (key & intermediateIndexMask) >> LEAF_BITS;
+      const Number leafIndex = key & leafIndexMask;
+
+      if (rootIndex != previousRootIndex) {
+        if (!root->ptrs[rootIndex]) {
+          // There's no node at this index. Move on to the next index at the root level, clearing the
+          // intermediate and leaf indices so that we start from the beginning of that next node.
+          key += 1 << (LEAF_BITS + INTERIOR_BITS);
+          key &= ~(leafIndexMask | intermediateIndexMask);
           continue;
-
-        Leaf* l = reader(reinterpret_cast<Leaf*>(n->ptrs[j]));
-        for (int k = 0; k < LEAF_LENGTH; k += visitor.visit(l->values[k]))
-          ;
-      }
+        }
+
+        intermediateNode = reader(root->ptrs[rootIndex]);
+        previousRootIndex = rootIndex;
+
+        // Invalidate the previous intermediate index since we've moved on to a different node.
+        previousIntermediateIndex = invalidIndex;
+      }
+
+      if (intermediateIndex != previousIntermediateIndex) {
+        if (!intermediateNode->ptrs[intermediateIndex]) {
+          // There's no node at this index. Move on to the next index at the intermediate level,
+          // clearing the leaf index so that we start from the beginning of the next node.
+          key += 1 << LEAF_BITS;
+          key &= ~leafIndexMask;
+          continue;
+        }
+
+        leaf = reader(reinterpret_cast<Leaf*>(intermediateNode->ptrs[intermediateIndex]));
+        previousIntermediateIndex = intermediateIndex;
+      }
+
+      key += visitor.visit(leaf->values[leafIndex]);
     }
   }