Title: [153662] branches/safari-537-branch/Source/WTF
- Revision
- 153662
- Author
- [email protected]
- Date
- 2013-08-02 12:51:35 -0700 (Fri, 02 Aug 2013)
Log Message
Merged r153635. <rdar://problem/14528244>
Modified Paths
Diff
Modified: branches/safari-537-branch/Source/WTF/ChangeLog (153661 => 153662)
--- branches/safari-537-branch/Source/WTF/ChangeLog 2013-08-02 19:34:49 UTC (rev 153661)
+++ branches/safari-537-branch/Source/WTF/ChangeLog 2013-08-02 19:51:35 UTC (rev 153662)
@@ -1,3 +1,37 @@
+2013-08-02 Lucas Forschler <[email protected]>
+
+ Merge r153635
+
+ 2013-08-01 Mark Rowe <[email protected]>
+
+ <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 Lucas Forschler <[email protected]>
Merge r153514
Modified: branches/safari-537-branch/Source/WTF/wtf/TCPageMap.h (153661 => 153662)
--- branches/safari-537-branch/Source/WTF/wtf/TCPageMap.h 2013-08-02 19:34:49 UTC (rev 153661)
+++ branches/safari-537-branch/Source/WTF/wtf/TCPageMap.h 2013-08-02 19:51:35 UTC (rev 153662)
@@ -158,13 +158,32 @@
template<class Visitor, class MemoryReader>
void visitValues(Visitor& visitor, const MemoryReader& reader)
{
- for (int i = 0; i < ROOT_LENGTH; i++) {
- if (!root_[i])
- continue;
+ const Number leafIndexMask = LEAF_LENGTH - 1;
- Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i]));
- for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j]))
- ;
+ 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]);
}
}
@@ -267,20 +286,53 @@
#ifdef WTF_CHANGES
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;
+ 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;
- Node* n = reader(root->ptrs[i]);
- for (int j = 0; j < INTERIOR_LENGTH; j++) {
- if (!n->ptrs[j])
+ 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]);
}
}
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
