From ebfdb7137e608888dc958d3fd32b78944a973588 Mon Sep 17 00:00:00 2001 From: Rick Lavoie Date: Thu, 7 Jul 2016 22:44:37 -0700 Subject: [PATCH] Avoid infinite loops in type-scanners more efficiently Summary: Normally the auto-generated type-scanners do not have to worry about entering into cycles. This is because they, by default, never follow pointers, and thus cannot enter into a cycle. However, there are certain constructs, which despite containing pointers, we want to treat as flat values. Standard library containers are one such example. Since it is possible to enter into a cycle with these, a runtime check needs to be done to avoid looping infinitely. The initial implementation of this check just used a set of visited pointers, which was consulted before scanning a pointer. The problem with this is that very large data structures can cause the visited set to grow very large, and clearing the set after the scan can consume a large amount of time. The visited set has the nice property that we'll never visit a node more than once, but this is strictly unnecessary. The only real requirement is that we don't loop infinitely. It is merely undesirable that work isn't duplicated. For this reason, replace the visited set with a stack of pointers currently being visited. Push a pointer onto the stack when scanning it, and pop it off when done. If a pointer is already on the stack, do not scan it. Since chains of scanned pointers tends to low, linearly searching the stack is sufficient. Reviewed By: edwinsmith Differential Revision: D3521753 fbshipit-source-id: e50abcd8b34a3a73c43c58f08055d3b63c685c13 --- hphp/util/type-scan.h | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) diff --git a/hphp/util/type-scan.h b/hphp/util/type-scan.h index ccacdea3180..5372cb775a0 100644 --- a/hphp/util/type-scan.h +++ b/hphp/util/type-scan.h @@ -277,8 +277,13 @@ struct Scanner { // mutually referential objects. template void scanPtr(const T* ptr, std::size_t size = sizeof(T)) { - if (!m_visited.insert(ptr).second) return; - scan(*ptr, size); + // Scan this pointer only if it already isn't on the visited list. IE, we + // have not already traversed through it to reach here. + if (std::find(m_visited.begin(), m_visited.end(), ptr) == m_visited.end()) { + m_visited.push_back(ptr); + SCOPE_EXIT { m_visited.pop_back(); }; + scan(*ptr, size); + } } // Called once all the scanning is done. Reports enqueued pointers via the @@ -286,12 +291,7 @@ struct Scanner { // callback. Afterwards, all the state is cleared. The Scanner can be re-used // after this. template void finish(F1&& f1, F2&& f2) { - if (m_visited.bucket_count() < 500) { - m_visited.clear(); - } else { - // TODO: #11247510 tune this better - m_visited = std::unordered_set(); - } + assert(m_visited.empty()); for (const auto& p : m_ptrs) if (p) { f1(p); } for (const auto& p : m_conservative) f2(p.first, p.second); m_ptrs.clear(); @@ -302,7 +302,7 @@ struct Scanner { // functions can manipulate them directly. std::vector m_ptrs; std::vector> m_conservative; - std::unordered_set m_visited; + std::vector m_visited; }; /* -- 2.11.4.GIT