Mojo cpp bindings: validation logic for incoming messages

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

+// 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/bindings/lib/bindings_serialization.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() {
+}

[Tom Sepez, 2014/05/23 18:18:35]

maybe in debug builds we want to assert that the invariant that the
claimed_range vector is sorted isn't violated.

[yzshen1, 2014/05/23 20:04:07]

Done.

+
+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
+  // |begin| < |claimed_ranges_[i]|. (The previous if-block guarantees that such

[Tom Sepez, 2014/05/23 18:18:35]

std::upper_bound(), no?

[yzshen1, 2014/05/23 20:04:07]

Sounds good. I didn't know about this choice. :)
std::upper_bounds() might come with a slight cost, but we probably shouldn't
reinvent the wheel.

Done.

+  // 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 == kEncodedInvalidHandleValue)
+    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);

[Tom Sepez, 2014/05/23 18:32:34]

this could be really slow if ranges aren't strictly increasing, no?

[yzshen1, 2014/05/23 20:04:07]

I think this should be okay, because in most cases:
- |claimed_ranges_| is relatively short.
- we append/merge to the end.

I feel that:
- using a container that is more efficient for inserting slows down searching.
- introducing a more complex data structure like a tree may just add overhead
without much gain.

If you have good ideas please let me know. Thanks!

+  }
+}
+
+bool BoundsChecker::InternalIsWithinBounds(uintptr_t begin,
+                                           uintptr_t end) const {
+  return end > begin && begin >= data_begin_ && end <= data_end_;
+}
+
+}  // namespace internal
+}  // namespace mojo