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 while traversing the graph.
+  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) {
   scoped_ptr<RawVarDataGraph> graph(new RawVarDataGraph);

[dmichael (off chromium), 2013/06/05 17:05:47]

Looking at this algorithm again, it seems like it could be simplified a little
bit. Might lead to a little less code and a little bit better performance (same
complexity, just less revisiting nodes and/or pushing/popping stuff on the
stack)

I sprinkled some comments in below that go together (i.e., some might not make
complete sense without the other suggestions).

Tangentially, you might be able to make the algorithm a little easier to read
and reason about by making the stack slightly more sophisticated:
struct StackFrame {
  size_t parent_index;
  queue<size_t> children;  // stack or vector are fine, too
};
(I think you only need to know index, but you could add PP_Var if it helps with
something).

The idea is you look at the current stack top's children. If it's non-empty, pop
a child from the queue, create a new StackFrame for it, and push it on the
stack. If the queue of children *is* empty, you know you're done with that
StackFrame and can pop it.

I don't know if this will actually be more readable, but it just separates the
"sentinel" values from the non-sentinel ones more explicitly. Feel free to try
it or ignore it.

In either case, a short description of the algorithm somewhere would be helpful.

[raymes, 2013/06/05 22:48:26]

I agree that it's not the easiest to understand. Those changes might improve it
a little, I think it's hard to say without trying it.

I think the biggest way to improve this (in terms of making it easy to
understand/reason about) would be to use the visitor pattern to implement the
algorithm. Basically to pull out the traversal/cycle-detection logic into one
class and the conversion logic into another class. Then we could re-use the
traversal logic for the 3 cases we currently have where we traverse the var
graph and only implement the conversion logic there.

Of course this is at /slight/ odds with making the thing really efficient. For
example, right now we are able to add the children to the ArrayRawVarData during
the traversal (i.e. right before we add them to the stack). If we separated that
logic then we would end up traversing the children during the conversion as
well. I think the tradeoff is worth it though.

I toyed with this idea before I started to write this stuff but thought it might
be overdesigning it a bit. Also, it only helps us in the Var-to-something else
case (e.g. it doesn't help us when going from v8 value back to var unless we
write a visitor for v8 values). But then again there's a bunch of places where
we traverse v8 values and base values so maybe it's just a pattern we should use
more often :)

   // 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) {

[dmichael (off chromium), 2013/06/05 17:05:47]

Can you avoid adding the new "sentinel" thing by just checking whether the item
has been initialized? (This goes along with the comment on 134 below...)

If it's been initialized, its children have already been added, and we can pop
it.

[raymes, 2013/06/05 22:48:26]

Yes, good catch.

+      stack.pop();
+      if (::ppapi::VarTracker::IsVarTypeRefcounted(current_var.type))
+        parent_ids.erase(current_var.value.as_id);

[dmichael (off chromium), 2013/06/05 17:05:47]

Here, if you only put in types that can have children, you don't need to check
if it's ref-counted. Just erase it.

[raymes, 2013/06/05 22:48:26]

But then the base case changes (i.e. you have to make sure the starting node
doesn't have children and initialize it properly which duplicates part of the
body of this loop). I think it's a tradeoff.

       continue;
+    } else {
+      stack.top().sentinel = true;
+      if (::ppapi::VarTracker::IsVarTypeRefcounted(current_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 (::ppapi::VarTracker::IsVarTypeRefcounted(child.type) &&
+            parent_ids.count(child.value.as_id) != 0) {

[dmichael (off chromium), 2013/06/05 17:05:47]

How about an explicit comment here (and below) that this is to detect and
prevent cycles

[raymes, 2013/06/05 22:48:26]

Done.

+          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));

[dmichael (off chromium), 2013/06/05 17:05:47]

How about checking at this point whether or not:
1) The type can have children. If not, no need to push it on the stack.
2) Whether the type is initialized. If so, no need to push it on the stack. It's
already been processed.

[raymes, 2013/06/05 22:48:26]

Even if the node doesn't have children, it has to have Init() called on it. So I
could pull that logic down here, but then the sentinel logic changes :P 

       }
     } 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 (::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