Don't send PP_Vars/V8 values with cycles across PostMessage

ppapi/proxy/raw_var_data.cc

 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ppapi/proxy/raw_var_data.h"
 
 #include <stack>
 
 #include "base/hash_tables.h"
 #include "base/stl_util.h"
@@ skipping 17 matching lines @@
 // memory instead of sending the data over IPC. Light testing suggests
 // shared memory is much faster for 256K and larger messages.
 static const uint32 kMinimumArrayBufferSizeForShmem = 256 * 1024;
 static uint32 g_minimum_array_buffer_size_for_shmem =
     kMinimumArrayBufferSizeForShmem;
 
 void DefaultHandleWriter(IPC::Message* m, const SerializedHandle& handle) {
   IPC::ParamTraits<SerializedHandle>::Write(m, handle);
 }
 
+struct StackEntry {
+  StackEntry(PP_Var v, size_t i) : var(v), data_index(i), sentinel(false) {}
+  PP_Var var;
+  size_t data_index;
+  // Used to track parent nodes on the stack as traversing the graph.

[dmichael (off chromium), 2013/06/04 16:59:10]

nit: as->while

[raymes, 2013/06/04 19:36:06]

Done.

+  bool sentinel;
+};
+
 // For a given PP_Var, returns the RawVarData associated with it, or creates a
 // new one if there is no existing one. The data is appended to |data| if it
 // is newly created. The index into |data| pointing to the result is returned.
-// |id_map| keeps track of RawVarDatas that have already been created.
+// |visited_map| keeps track of RawVarDatas that have already been created.
 size_t GetOrCreateRawVarData(const PP_Var& var,
-                             base::hash_map<int64_t, size_t>* id_map,
+                             base::hash_map<int64_t, size_t>* visited_map,
                              ScopedVector<RawVarData>* data) {
   if (VarTracker::IsVarTypeRefcounted(var.type)) {
-    base::hash_map<int64_t, size_t>::iterator it = id_map->find(
+    base::hash_map<int64_t, size_t>::iterator it = visited_map->find(
         var.value.as_id);
-    if (it != id_map->end()) {
+    if (it != visited_map->end()) {
       return it->second;
     } else {
       data->push_back(RawVarData::Create(var.type));
-      (*id_map)[var.value.as_id] = data->size() - 1;
+      (*visited_map)[var.value.as_id] = data->size() - 1;
     }
   } else {
     data->push_back(RawVarData::Create(var.type));
   }
   return data->size() - 1;
 }
 
 }  // namespace
 
 // RawVarDataGraph ------------------------------------------------------------
 RawVarDataGraph::RawVarDataGraph() {
 }
 
 RawVarDataGraph::~RawVarDataGraph() {
 }
 
 // static
 scoped_ptr<RawVarDataGraph> RawVarDataGraph::Create(const PP_Var& var,
-                                                    PP_Instance instance) {
+                                                    PP_Instance instance,
+                                                    bool allow_cycles) {
   scoped_ptr<RawVarDataGraph> graph(new RawVarDataGraph);
   // Map of |var.value.as_id| to a RawVarData index in RawVarDataGraph.
-  base::hash_map<int64_t, size_t> id_map;
+  base::hash_map<int64_t, size_t> visited_map;
+  base::hash_set<int64_t> parent_ids;
 
-  std::stack<std::pair<PP_Var, size_t> > stack;
-  stack.push(make_pair(var, GetOrCreateRawVarData(var, &id_map,
-                                                  &graph->data_)));
+  std::stack<StackEntry> stack;
+  stack.push(StackEntry(var, GetOrCreateRawVarData(var, &visited_map,
+                                                   &graph->data_)));
 
   // Traverse the PP_Var graph with DFS.
   while (!stack.empty()) {
-    PP_Var current_var = stack.top().first;
-    RawVarData* current_var_data = graph->data_[stack.top().second];
-    stack.pop();
+    PP_Var current_var = stack.top().var;
+    RawVarData* current_var_data = graph->data_[stack.top().data_index];
 
-    // If the node is initialized, it means we have visited it.
-    if (current_var_data->initialized())
+    if (stack.top().sentinel) {
+      stack.pop();
+      if (::ppapi::VarTracker::IsVarTypeRefcounted(var.type))

[dmichael (off chromium), 2013/06/04 16:59:10]

I don't understand why you're looking at the type of |var| here. Did you mean
|current_var|?

(If |var| is not ref-counted, we could avoid pretty much the whole function... 
it doesn't make sense to me to check its type inside the loop.)

[raymes, 2013/06/04 19:36:06]

Yes...good catch. Thanks

+        parent_ids.erase(current_var.value.as_id);
       continue;
+    } else {
+      stack.top().sentinel = true;
+      if (::ppapi::VarTracker::IsVarTypeRefcounted(var.type))
+        parent_ids.insert(current_var.value.as_id);
+    }
+
+    // If the node is initialized, it means we have visited it already.
+    if (current_var_data->initialized()) {
+      continue;
+    }
 
     if (!current_var_data->Init(current_var, instance)) {
       NOTREACHED();
       return scoped_ptr<RawVarDataGraph>();
     }
 
     // Add child nodes to the stack.
     if (current_var.type == PP_VARTYPE_ARRAY) {
       ArrayVar* array_var = ArrayVar::FromPPVar(current_var);
       if (!array_var) {
         NOTREACHED();
         return scoped_ptr<RawVarDataGraph>();
       }
       for (ArrayVar::ElementVector::const_iterator iter =
                array_var->elements().begin();
            iter != array_var->elements().end();
            ++iter) {
-        size_t child_id = GetOrCreateRawVarData(iter->get(), &id_map,
+        const PP_Var& child = iter->get();
+        if (!allow_cycles &&
+            ::ppapi::VarTracker::IsVarTypeRefcounted(child.type) &&
+            parent_ids.count(child.value.as_id) != 0) {
+          return scoped_ptr<RawVarDataGraph>();
+        }
+        size_t child_id = GetOrCreateRawVarData(child, &visited_map,
                                                 &graph->data_);
         static_cast<ArrayRawVarData*>(current_var_data)->AddChild(child_id);
-        stack.push(make_pair(iter->get(), child_id));
+        stack.push(StackEntry(child, child_id));
       }
     } else if (current_var.type == PP_VARTYPE_DICTIONARY) {
       DictionaryVar* dict_var = DictionaryVar::FromPPVar(current_var);
       if (!dict_var) {
         NOTREACHED();
         return scoped_ptr<RawVarDataGraph>();
       }
       for (DictionaryVar::KeyValueMap::const_iterator iter =
                dict_var->key_value_map().begin();
            iter != dict_var->key_value_map().end();
            ++iter) {
-        size_t child_id = GetOrCreateRawVarData(iter->second.get(), &id_map,
+        const PP_Var& child = iter->second.get();
+        if (!allow_cycles &&
+            ::ppapi::VarTracker::IsVarTypeRefcounted(child.type) &&
+            parent_ids.count(child.value.as_id) != 0) {
+          return scoped_ptr<RawVarDataGraph>();
+        }
+        size_t child_id = GetOrCreateRawVarData(child, &visited_map,
                                                 &graph->data_);
         static_cast<DictionaryRawVarData*>(
             current_var_data)->AddChild(iter->first, child_id);
-        stack.push(make_pair(iter->second.get(), child_id));
+        stack.push(StackEntry(child, child_id));
       }
     }
   }
   return graph.Pass();
 }
 
 PP_Var RawVarDataGraph::CreatePPVar(PP_Instance instance) {
   // Create and initialize each node in the graph.
   std::vector<PP_Var> graph;
   for (size_t i = 0; i < data_.size(); ++i)
@@ skipping 495 matching lines @@
       return false;
     if (!m->ReadUInt32(iter, &value))
       return false;
     children_.push_back(make_pair(key, value));
   }
   return true;
 }
 
 }  // namespace proxy
 }  // namespace ppapi