Mojo cpp bindings: validation logic for incoming messages

mojo/public/cpp/bindings/lib/bounds_checker.cc

Index: mojo/public/cpp/bindings/lib/bounds_checker.cc
diff --git a/mojo/public/cpp/bindings/lib/bounds_checker.cc b/mojo/public/cpp/bindings/lib/bounds_checker.cc
new file mode 100644
index 0000000000000000000000000000000000000000..26055d7ce1581ecfcf6a58dbdbb00648de9469d4
--- /dev/null
+++ b/mojo/public/cpp/bindings/lib/bounds_checker.cc
@@ -0,0 +1,125 @@
+// Copyright 2014 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 "mojo/public/cpp/bindings/lib/bounds_checker.h"
+
+#include <assert.h>
+
+#include "mojo/public/cpp/system/core.h"
+
+namespace mojo {
+namespace internal {
+
+BoundsChecker::BoundsChecker(const void* data, uint32_t data_num_bytes,
+                             size_t num_handles)
+    : data_begin_(reinterpret_cast<uintptr_t>(data)),
+      data_end_(data_begin_ + data_num_bytes),
+      claimed_handles_(num_handles, false) {
+  if (data_end_ < data_begin_) {
+    // The calculation of |data_end_| overflowed.
+    // It shouldn't happen but if it does, set the range to empty so
+    // IsWithinBounds() and ClaimMemory() always fail.
+    assert(false);  // Not reached.
+    data_end_ = data_begin_;
+  }
+}
+
+BoundsChecker::~BoundsChecker() {
+}
+
+bool BoundsChecker::ClaimMemory(const void* position, uint32_t num_bytes) {
+  uintptr_t begin = reinterpret_cast<uintptr_t>(position);
+  uintptr_t end = begin + num_bytes;
+
+  if (!InternalIsWithinBounds(begin, end))
+    return false;
+
+  if (claimed_ranges_.empty() || begin >= claimed_ranges_.back()) {
+    // This optimization is significant: if the layout of objects in an incoming
+    // message are in the same order as our validation code traverses the
+    // message, we will always hit this code path.
+    InsertOrMergeClaimedRange(claimed_ranges_.end(), begin, end);
+    return true;
+  }
+
+  // Do a binary search to find the smallest index i that satisfies

[Tom Sepez, 2014/05/22 19:39:21]

can we use std::binary_search() instead of re-inventing this?

[yzshen1, 2014/05/22 20:56:22]

std::binary_search() is used to check whether an element exists.
Here, as the comment says, the purpose is different: we need to find the
smallest index i that satisfies |begin| < |claimed_ranges_[i]|.

+  // |begin| < |claimed_ranges_[i]|. (The previous if-block guarantees that such
+  // an index must exist if we reach this point.)
+  size_t index_left = 0;
+  size_t index_right = claimed_ranges_.size() - 1;
+
+  while (index_right > index_left) {
+    size_t index_middle = (index_left + index_right) / 2;
+    if (begin < claimed_ranges_[index_middle])
+      index_right = index_middle;
+    else
+      index_left = index_middle + 1;
+  }
+  assert(index_left == index_right);
+
+  // |index_left| is an odd number means that |begin| lies in a claimed
+  // range.
+  if (index_left % 2)
+    return false;
+  // If |end| is bigger than |claimed_ranges_[index_left]| while |begin| is
+  // smaller, then [|begin|, |end|) overlaps at least one claimed range.
+  if (end > claimed_ranges_[index_left])
+    return false;
+
+  InsertOrMergeClaimedRange(claimed_ranges_.begin() + index_left, begin, end);
+  return true;
+}
+
+bool BoundsChecker::ClaimHandle(const Handle& encoded_handle) {
+  uint32_t index = encoded_handle.value();
+  if (index == static_cast<uint32_t>(-1))

[Tom Sepez, 2014/05/22 19:39:21]

is there a kInvalidHandle constant somewhere?

[yzshen1, 2014/05/22 20:56:22]

We have kInvalidHandleValue but it is the "decoded" invalid handle, whose value
is 0.
Here we are dealing with the "encoded" invalid handle, whose value is -1.
I added a new constants kEncodedInvalidHandleValue.
Thanks!

+    return true;
+
+  if (index >= claimed_handles_.size() || claimed_handles_[index])
+    return false;
+
+  claimed_handles_[index] = true;
+  return true;
+}
+
+bool BoundsChecker::IsWithinBounds(const void* position,
+                                   uint32_t num_bytes) const {
+  uintptr_t begin = reinterpret_cast<uintptr_t>(position);
+  uintptr_t end = begin + num_bytes;
+
+  return InternalIsWithinBounds(begin, end);
+}
+
+const std::vector<uintptr_t>&
+    BoundsChecker::GetClaimedRangesForTesting() const {
+  return claimed_ranges_;
+}
+
+void BoundsChecker::InsertOrMergeClaimedRange(
+    std::vector<uintptr_t>::iterator pos, uintptr_t begin, uintptr_t end) {
+  bool merge_previous = pos != claimed_ranges_.begin() &&
+                        *(pos - 1) == begin;
+  bool merge_next = pos != claimed_ranges_.end() &&
+                    *pos == end;
+
+  if (merge_previous && merge_next) {
+    *(pos - 1) = *(pos + 1);
+    claimed_ranges_.erase(pos, pos + 2);
+  } else if (merge_previous) {
+    *(pos - 1) = end;
+  } else if (merge_next) {
+    *pos = begin;
+  } else {
+    uintptr_t pair[2] = {begin, end};
+    claimed_ranges_.insert(pos, pair, pair + 2);
+  }
+}
+
+bool BoundsChecker::InternalIsWithinBounds(uintptr_t begin,
+                                           uintptr_t end) const {
+  return end > begin && begin >= data_begin_ && end <= data_end_;
+}
+
+}  // namespace internal
+}  // namespace mojo