command_buffer: Implement path rendering functions for CHROMIUM_path_rendering

gpu/command_buffer/service/path_manager.cc

+// Copyright (c) 2015 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 "gpu/command_buffer/service/path_manager.h"
+#include "base/logging.h"
+#include "gpu/command_buffer/common/gles2_cmd_utils.h"
+#include "ui/gl/gl_bindings.h"
+
+namespace {
+void callDeletePaths(GLuint first_id, GLuint range) {

[piman, 2015/06/24 03:27:44]

nit: CallDeletePaths

[Kimmo Kinnunen, 2015/06/24 12:49:02]

Done.

+  while (range > 0) {
+    GLsizei irange;
+    if (range > static_cast<GLuint>(std::numeric_limits<GLsizei>::max()))
+      irange = std::numeric_limits<GLsizei>::max();
+    else
+      irange = static_cast<GLsizei>(range);
+
+    glDeletePathsNV(first_id, irange);
+    range -= irange;
+    first_id += irange + 1;

[piman, 2015/06/24 03:27:44]

Why +1? It doesn't seem right, and on top of it you'd have a guaranteed overflow
if irange == std::numeric_limits<GLsizei>::max()

[Kimmo Kinnunen, 2015/06/24 12:49:02]

Definitely not right, oops.

Done, added a test to test it.

+  }
+}
+}  // anonymous namespace
+
+namespace gpu {
+namespace gles2 {
+
+PathManager::PathManager() {
+}
+
+PathManager::~PathManager() {
+  DCHECK(path_map_.empty());
+}
+
+void PathManager::Destroy(bool have_context) {
+  if (have_context) {
+    for (PathRangeMap::const_iterator it = path_map_.begin();
+         it != path_map_.end(); ++it)
+      callDeletePaths(FirstServiceId(it), RangeSize(it));
+  }
+  path_map_.clear();
+}
+
+void PathManager::CreatePathRange(GLuint first_client_id,
+                                  GLuint last_client_id,
+                                  GLuint first_service_id) {
+  DCHECK(!HasPathsInRange(first_client_id, last_client_id));
+  DCHECK(first_service_id > 0);

[piman, 2015/06/24 03:27:44]

nit: also DCHECK(first_client_id > 0) - this was checked by the decoder.

[Kimmo Kinnunen, 2015/06/24 12:49:02]

Done.

+  bool check_before = false;
+
+  PathRangeMap::iterator it = path_map_.lower_bound(first_client_id);
+  PathRangeMap::iterator next_range = it;
+  if (it != path_map_.begin()) {
+    --it;
+    check_before = true;
+  }
+  if (next_range != path_map_.end()) {
+    GLuint last_service_id =
+        first_service_id + last_client_id - first_client_id;
+    // FirstClientId(next_range) - 1 does not underflow because lower_bound
+    // returns > first_client_id.

[piman, 2015/06/24 03:27:45]

FirstClientId returns something that was guaranteed to be >0 anyway (since it
comes from a value passed by the client, that we checked).

[Kimmo Kinnunen, 2015/06/24 12:49:02]

Done.

+    // It does not return == first_client_id (== 0) because this would
+    // contradict
+    // !HasPathsInRange(first_client_id, last_client_id).
+    // FirstServiceId(next_range) - 1 does not underflow because
+    // first_service_id > 0.

[piman, 2015/06/24 03:27:45]

Can you add DCHECKs for these?

[Kimmo Kinnunen, 2015/06/24 12:49:02]

Done. I removed the middle comment, as I don't even understand why I thought it
would be significant.

+    if (FirstClientId(next_range) - 1 == last_client_id &&
+        FirstServiceId(next_range) - 1 == last_service_id) {
+      last_client_id = LastClientId(next_range);
+      path_map_.erase(next_range);
+    }
+  }
+
+  if (it != path_map_.end() && check_before) {
+    // The last first client id -1 does not underflow because then  lower_bound
+    // would have found something, which contradicts
+    // !HasPathsInRange(first_client_id, last_client_id).
+    // first_service_id -1 does not underflow because first_service_id > 0.
+    if (LastClientId(it) == first_client_id - 1 &&
+        LastServiceId(it) == first_service_id - 1) {
+      LastClientId(it) = last_client_id;
+      return;
+    }
+  }

[piman, 2015/06/24 03:27:45]

I find this all a bit hard to follow. I would like to suggest an alternative:
1- insert the new range, unconditionally - this actually returns an iterator to
the new element
2- merge (if possible) with the previous range
3- merge (if possible) with the next range.

I think the code would be a bit simpler and symmetric, and would allow a single
map traversal (on insert).

[Kimmo Kinnunen, 2015/06/24 12:49:02]

Right..
Current code has the good property that the expected default case never inserts,
so there's no allocations nor destructions. With your proposal, it would always
insert. Most of the time it would end up erasing. Sometimes it would erase
twice.
I don't think there's much difference in the amount of traversals in practice.
This implementation tries to capture the "fast" path for the expected common
case..

Code wise, I think proposal would amount to moving the insert from below to the
top, removing lower_bound and replacing "return" above with erase.

If you still confirm that this is simpler in your eyes, is worth the tradeoff of
"slower" operation and thus has to be done, I will course do it...

[piman, 2015/06/24 22:50:18]

TBH I spent about an hour yesterday reviewing this file. It's too much, and it
would benefit from simplification. Unless we have data that shows that this is
in the critical path (my suspicion is that it's way dominated by the
PathCommands part), I'd rather opt for readable/auditable - this is security
sensitive.

Part of it is that lower_bound returns something that is close but never quite
what we need, so you have to muck with iterators. Maybe there's another way to
write helper functions that wrap lower_bounds give you e.g. the range that
precedes first_client_id or something.

Or even go all the way and say that maybe it's not that useful to keep the
"range" structure and instead simply use a direct client_id->service_id
hash_map. It might even make GetPath (which is in the critical path) more
efficient. RemovePaths can very easily reconstruct ranges (if we want to save
calls to glDeletePathsNV).

[Kimmo Kinnunen, 2015/06/25 12:13:35]

Sorry about spending your time.

I tried to simplify the code. See if it is more readable now, even though it
uses the original logic?
I do not think that will work. When the allocations go past 100k or 1M ids (can
not remember anymore), the per-id hashmap calls never return.

The problem is that the implementation has to support the whole id space in
order for the implementation to gain any sort of trust in quality. This then
necessitates testing the implementation for the whole id space. 

The hashmap does not scale too well, and thus it can not execute many of the
testcases needed to test this implementation. This was already a problem in the
client-side id allocator, which was using per-id mapping. I changed it to use
ranges.

Also in practice Skia will use somewhat big amount of IDs, though of course not
nearly the entire id space.

+
+  path_map_.insert(std::make_pair(
+      first_client_id, PathRangeDescription(last_client_id, first_service_id)));
+}
+
+bool PathManager::HasPathsInRange(GLuint first_client_id,
+                                  GLuint last_client_id) const {
+  PathRangeMap::const_iterator it = path_map_.lower_bound(first_client_id);
+  if (it != path_map_.end() && (FirstClientId(it) == first_client_id ||
+                                FirstClientId(it) <= last_client_id))
+    return true;
+
+  if (it == path_map_.begin())
+    return false;
+
+  --it;
+  return LastClientId(it) >= first_client_id;
+}
+
+bool PathManager::GetPath(GLuint client_id, GLuint* service_id) const {
+  PathRangeMap::const_iterator it = path_map_.lower_bound(client_id);
+  if (it != path_map_.end() && FirstClientId(it) == client_id) {
+    *service_id = FirstServiceId(it);
+    return true;
+  }
+  if (it == path_map_.begin())
+    return false;
+
+  --it;
+  if (LastClientId(it) < client_id)
+    return false;
+
+  *service_id = FirstServiceId(it) + client_id - FirstClientId(it);
+
+  return true;
+}
+
+void PathManager::RemovePaths(GLuint first_client_id, GLuint last_client_id) {
+  PathRangeMap::iterator it = path_map_.lower_bound(first_client_id);
+  if (it == path_map_.end() || FirstClientId(it) != first_client_id) {
+    if (it != path_map_.begin()) {
+      --it;
+      if (LastClientId(it) < first_client_id)
+        ++it;
+    }
+  }
+
+  while (it != path_map_.end() && FirstClientId(it) <= last_client_id) {
+    GLuint delete_first_client_id =
+        std::max(first_client_id, FirstClientId(it));
+    GLuint delete_last_client_id = std::min(last_client_id, LastClientId(it));
+    GLuint delete_first_service_id =
+        FirstServiceId(it) + delete_first_client_id - FirstClientId(it);
+    GLuint delete_range = delete_last_client_id - delete_first_client_id + 1;
+
+    callDeletePaths(delete_first_service_id, delete_range);
+
+    PathRangeMap::iterator current = it;
+    ++it;
+
+    GLuint current_last_client_id = LastClientId(current);
+
+    if (FirstClientId(current) < delete_first_client_id)
+      LastClientId(current) = delete_first_client_id - 1;
+    else
+      path_map_.erase(current);
+
+    if (current_last_client_id > delete_last_client_id) {
+      path_map_.insert(std::make_pair(
+          delete_last_client_id + 1,
+          PathRangeDescription(current_last_client_id,
+                               delete_first_service_id + delete_range)));
+      DCHECK(delete_last_client_id == last_client_id);
+      // This is necessarily the last range to check. Return early due to
+      // consistency. Iterator increment would skip the inserted range. The
+      // algorithm would work ok, but it looks weird.
+      return;
+    }
+  }
+}
+
+}  // namespace gles2
+}  // namespace gpu