Introduce `__sanitizer::ArrayRef<T>` type.

[delcypher]

Summary

This type is a light-weight container around a contiguous sequence
of elements of type T.

The type is inspired by LLVM ADT's ArrayRef but has more limited
functionality.

This patch includes tests for the new type but no uses in the runtime
itself. In future patches I will use this type as a foundation for
building a safe abstraction for operating on an environment array.

[dblaikie]

While I'm in favor of this type looking more like llvm's MutableArrayRef (ie: allowing mutability or immutability to be encoded in the type parameter (const T versus non-const T)) rather than needing the two types LLVM has (ArrayRef + MutableArrayRef). I wonder if having this type called "ArrayRef" when it is subtly different from llvm's ArrayRef might be confusing? Wonder if it needs another/better name - though the standard doesn't offer us a great alternative, it seems the standardized equivalent is std::span, which might be sufficiently different not to be a good name to use either? Not sure.

compiler-rt/lib/sanitizer_common/sanitizer_array_ref.h

87 ↗

(On Diff #257090)

Might just be better/easier to use "data_" directly, rather than const_casting+begin?

Or use "data()" instead, like llvm::ArrayRef does?

[delcypher]

In D78050#1979455, @dblaikie wrote:

While I'm in favor of this type looking more like llvm's MutableArrayRef (ie: allowing mutability or immutability to be encoded in the type parameter (const T versus non-const T)) rather than needing the two types LLVM has (ArrayRef + MutableArrayRef). I wonder if having this type called "ArrayRef" when it is subtly different from llvm's ArrayRef might be confusing?

Thank you for raising this. I probably should have said "loosely inspired" by ArrayRef because I wasn't aware of MutableArrayRef and I hadn't noticed that LLVM ADT's ArrayRef was immutable. Given that LLVM's ADT ArrayRef is immutable my choice of naming would certainly be confusing. For my use case I actually only need the underlying data to be mutable so I don't need an immutable version.

Wonder if it needs another/better name - though the standard doesn't offer us a great alternative, it seems the standardized equivalent is std::span, which might be sufficiently different not to be a good name to use either? Not sure.

My early draft name was actually BufferRef<T>. Does that seem any better?

compiler-rt/lib/sanitizer_common/sanitizer_array_ref.h

87 ↗

(On Diff #257090)

Good idea.

[dblaikie]

In D78050#1979667, @delcypher wrote:

In D78050#1979455, @dblaikie wrote:

While I'm in favor of this type looking more like llvm's MutableArrayRef (ie: allowing mutability or immutability to be encoded in the type parameter (const T versus non-const T)) rather than needing the two types LLVM has (ArrayRef + MutableArrayRef). I wonder if having this type called "ArrayRef" when it is subtly different from llvm's ArrayRef might be confusing?

Thank you for raising this. I probably should have said "loosely inspired" by ArrayRef because I wasn't aware of MutableArrayRef and I hadn't noticed that LLVM ADT's ArrayRef was immutable. Given that LLVM's ADT ArrayRef is immutable my choice of naming would certainly be confusing. For my use case I actually only need the underlying data to be mutable so I don't need an immutable version.

Wonder if it needs another/better name - though the standard doesn't offer us a great alternative, it seems the standardized equivalent is std::span, which might be sufficiently different not to be a good name to use either? Not sure.

My early draft name was actually BufferRef<T>. Does that seem any better?

Might be best just to resort to calling it MutableArrayRef to match LLVM's since they're so similar? Maybe one day we can revisit the design decision in LLVM and fix both, etc.

[delcypher]

• Rename ArrayRef<T> -> MutableArrayRef<T>.
• Remove duplicate const returning methods. They don't seem to be needed.
• Add elementTy.
• Add iterator type.

[dblaikie]

Don't suppose there's any sane way to reuse any part of the main llvm version? Might at least be worth a few comments encouraging future developers to try to keep this mostly aligned with the llvm one? (maybe document broadly the features/etc that are omitted from this version but present in the llvm one)

Is this more or less copy/paste, except for some features that aren't supportable/suitable for this usage?

compiler-rt/lib/sanitizer_common/sanitizer_mutable_array_ref.h

82

Going to use data() here?

[delcypher]

Remove unnecessary const_cast<>.

[delcypher]

In D78050#1981672, @dblaikie wrote:

Don't suppose there's any sane way to reuse any part of the main llvm version? Might at least be worth a few comments encouraging future developers to try to keep this mostly aligned with the llvm one? (maybe document broadly the features/etc that are omitted from this version but present in the llvm one)

We can't depend on libcxx in the compiler-rt runtimes. There's probably something crazy we could with macros that fudge the types to make it work but that doesn't sound sane.

Is this more or less copy/paste, except for some features that aren't supportable/suitable for this usage?

Not really. It just has the bare minimum functionality that I needed. I only looked at ArrayRef<> when I needed to do something I didn't know how to implement.

compiler-rt/lib/sanitizer_common/sanitizer_mutable_array_ref.h

82

Oh sorry. I missed this. I'll fix this.

[delcypher]

Abandoning this change in favour of:

• https://reviews.llvm.org/D78178
• https://reviews.llvm.org/D78179

compiler-rt/lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_IMPL_HEADERS
   sanitizer_lfstack.h
   sanitizer_libc.h
   sanitizer_libignore.h
   sanitizer_linux.h
   sanitizer_list.h
   sanitizer_local_address_space_view.h
   sanitizer_mac.h
   sanitizer_malloc_mac.inc
+  sanitizer_mutable_array_ref.h
   sanitizer_mutex.h
   sanitizer_persistent_allocator.h
   sanitizer_placement_new.h
   sanitizer_platform.h
   sanitizer_platform_interceptors.h
   sanitizer_platform_limits_netbsd.h
   sanitizer_platform_limits_openbsd.h
   sanitizer_platform_limits_posix.h

compiler-rt/lib/sanitizer_common/sanitizer_mutable_array_ref.h

+//===-- sanitizer_mutable_array_ref.h ---------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Lightweight reference to a contiguous array of elements
+// of type `T`. It does not own any storage. Consequently
+// care must be taken to ensure the life-time of this object
+// does not outlive the storage it references.
+//
+//===----------------------------------------------------------------------===//
+#ifndef SANITIZER_ARRAY_REF_H
+#define SANITIZER_ARRAY_REF_H
+#include "sanitizer_common.h"
+#include "sanitizer_internal_defs.h"
+#include "sanitizer_libc.h"
+
+namespace __sanitizer {
+
+template <class T>
+class MutableArrayRef {
+ public:
+  explicit MutableArrayRef(T *data, uptr size) : data_(data), size_(size) {}
+  template <uptr N>
+  explicit MutableArrayRef(T (&ptr)[N]) : data_(ptr), size_(N) {}
+
+  using elementTy = T;
+  // TODO(dliew): Consider implementing a smart iterator that tracks if
+  // derefence is safe.
+  using iterator = T *;
+
+  // Accessors
+  T *data() const { return data_; }
+  iterator begin() const { return data_; }
+  iterator end() const {
+    if (size_ == 0)
+      return begin();
+    return &(data_[size_ - 1]);
+  }
+  T &operator[](uptr idx) {
+    CHECK_LT(idx, size_);
+    return data_[idx];
+  }
+
+  // Properties
+  bool containsPtr(T *ptr) const {
+    if (ptr >= begin() && ptr <= end())
+      return true;
+    return false;
+  }
+  bool isValidIndex(uptr idx) const { return idx < size_; }
+  bool overlaps(const MutableArrayRef<T> &other) const {
+    if (begin() <= other.begin() && other.begin() <= end())
+      return true;
+    if (other.begin() <= begin() && other.end() >= begin())
+      return true;
+    return false;
+  }
+  uptr size() const { return size_; }
+
+  // Copy operations
+  void copyFrom(const MutableArrayRef<T> &src) {
+    CHECK_GE(size_, src.size_);
+    CHECK(!overlaps(src));
+    internal_memcpy(data_, src.data_, sizeof(T) * src.size_);
+  }
+
+  uptr truncatedCopyFrom(const MutableArrayRef<T> &src) {
+    CHECK(!overlaps(src));
+    uptr elts_to_copy = Min(size_, src.size_);
+    internal_memcpy(data_, src.data_, sizeof(T) * elts_to_copy);
+    return elts_to_copy;
+  }
+
+  // Return an `MutableArrayRef` that drops the first `n` elements
+  MutableArrayRef<T> slice(uptr n) const {
+    CHECK_LE(n, size());
+    T *slice_begin = data_ + n;
+    uptr slice_size = size() - n;
+    return MutableArrayRef<T>(slice_begin, slice_size);
+  }
+
+ private:
+  T *data_;
+  uptr size_;  // number of elements of type T in buffer.
+};
+
+}  // namespace __sanitizer
+
+#endif

compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt

set(SANITIZER_UNITTESTS
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
   sanitizer_flags_test.cpp
   sanitizer_format_interceptor_test.cpp
   sanitizer_ioctl_test.cpp
   sanitizer_libc_test.cpp
   sanitizer_linux_test.cpp
   sanitizer_list_test.cpp
+  sanitizer_mutable_array_ref_test.cpp
   sanitizer_mutex_test.cpp
   sanitizer_nolibc_test.cpp
   sanitizer_posix_test.cpp
   sanitizer_printf_test.cpp
   sanitizer_procmaps_test.cpp
   sanitizer_ring_buffer_test.cpp
   sanitizer_quarantine_test.cpp
   sanitizer_stackdepot_test.cpp

compiler-rt/lib/sanitizer_common/tests/sanitizer_mutable_array_ref_test.cpp

+//===-- sanitizer_mutable_array_ref_test.cpp ------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of Sanitizer runtime.
+// Tests for sanitizer_bitvector.h.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_mutable_array_ref.h"
+
+#include "gtest/gtest.h"
+#include "sanitizer_common/sanitizer_type_traits.h"
+#include "sanitizer_test_utils.h"
+
+using namespace __sanitizer;
+
+static const char kDeathRegex[] = ".*CHECK failed:.*";
+
+int data[] = {0, 1, 2, 3};
+MutableArrayRef<int> ref(data, ARRAY_SIZE(data));
+
+TEST(MutableArrayRef, CArrayConstructor) {
+  MutableArrayRef<int> other_ref(data);
+  EXPECT_EQ(other_ref.size(), ARRAY_SIZE(data));
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_EQ(ref[index], data[index]);
+  }
+}
+
+TEST(MutableArrayRef, elementTy) {
+  static_assert(
+      __sanitizer::is_same<MutableArrayRef<int>::elementTy, int>::value,
+      "elementTy must be int");
+  static_assert(__sanitizer::is_same<MutableArrayRef<const int>::elementTy,
+                                     const int>::value,
+                "elementTy must be const int");
+}
+
+TEST(MutableArrayRef, IndexOperatorSafeRead) {
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_EQ(ref[index], data[index]);
+  }
+}
+
+TEST(MutableArrayRef, IndexOperatorSafeWrite) {
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    ref[index] = static_cast<int>(index) * 2;
+  }
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_EQ(data[index], static_cast<int>(index) * 2);
+  }
+}
+
+TEST(MutableArrayRef, IndexOperatorBadRead) {
+  EXPECT_DEATH(ref[4], kDeathRegex);
+}
+
+TEST(MutableArrayRef, Size) { EXPECT_EQ(ref.size(), static_cast<uptr>(4)); }
+
+TEST(MutableArrayRef, Data) {
+  MutableArrayRef<int> ref(data, ARRAY_SIZE(data));
+  EXPECT_EQ(ref.data(), &(data[0]));
+}
+
+TEST(MutableArrayRef, Begin) {
+  MutableArrayRef<int> ref(data, ARRAY_SIZE(data));
+  EXPECT_EQ(ref.begin(), &(data[0]));
+}
+
+TEST(MutableArrayRef, End) {
+  MutableArrayRef<int> ref(data, ARRAY_SIZE(data));
+  EXPECT_EQ(ref.end(), &(data[3]));
+}
+
+TEST(MutableArrayRef, LoopCXX98) {
+  // Loop like it's 1998!
+  unsigned index = 0;
+  for (MutableArrayRef<int>::iterator it = ref.begin(), end = ref.end();
+       it != end; ++it) {
+    EXPECT_EQ(*it, (data[index]));
+    ++index;
+  }
+}
+
+TEST(MutableArrayRef, LoopCXX11) {
+  // Loop like it's 2011!
+  unsigned index = 0;
+  for (auto& elt : ref) {
+    EXPECT_EQ(elt, data[index]);
+    ++index;
+  }
+}
+
+TEST(MutableArrayRef, LoopCXX11const) {
+  // Loop like it's 2011!
+  unsigned index = 0;
+  for (const auto& elt : ref) {
+    EXPECT_EQ(elt, data[index]);
+    ++index;
+  }
+}
+
+TEST(MutableArrayRef, IsValidIndex) {
+  unsigned index = 0;
+  for (; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_TRUE(ref.isValidIndex(index));
+  }
+  EXPECT_FALSE(ref.isValidIndex(index));
+}
+
+TEST(MutableArrayRef, OverlapDisjoint) {
+  MutableArrayRef<int> left_ref(data, 2);
+  MutableArrayRef<int> right_ref(&(data[2]), 2);
+  EXPECT_FALSE(left_ref.overlaps(right_ref));
+  EXPECT_FALSE(right_ref.overlaps(left_ref));
+}
+
+TEST(MutableArrayRef, OverlapOneEltOverlap) {
+  MutableArrayRef<int> left_ref(data, 3);
+  MutableArrayRef<int> right_ref(&(data[2]), 2);
+  EXPECT_TRUE(left_ref.overlaps(right_ref));
+  EXPECT_TRUE(right_ref.overlaps(left_ref));
+}
+
+TEST(MutableArrayRef, copyFrom) {
+  int other_data[5] = {0};
+  static_assert(sizeof(other_data) > sizeof(data),
+                "other_data should be larger than data");
+  MutableArrayRef<int> other_ref(other_data, ARRAY_SIZE(other_data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_data[index], 0);
+  }
+  other_ref.copyFrom(ref);
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    if (index < ARRAY_SIZE(data)) {
+      EXPECT_EQ(other_ref[index], data[index]);
+    } else {
+      EXPECT_EQ(other_ref[index], 0);
+    }
+  }
+}
+
+TEST(MutableArrayRef, copyFromUnsafeOverlap) {
+  MutableArrayRef<int> other_ref(data, ARRAY_SIZE(data));
+  EXPECT_DEATH(other_ref.copyFrom(ref), kDeathRegex);
+}
+
+TEST(MutableArrayRef, copyFromUnsafeOverlapOneElt) {
+  MutableArrayRef<int> left_ref(data, 3);
+  MutableArrayRef<int> right_ref(&(data[2]), 2);
+  EXPECT_DEATH(left_ref.copyFrom(right_ref), kDeathRegex);
+}
+
+TEST(MutableArrayRef, copyFromInsufficientSpace) {
+  int other_data[2] = {0};
+  static_assert(sizeof(other_data) < sizeof(data),
+                "other_data should be smaller");
+  MutableArrayRef<int> other_ref(other_data, ARRAY_SIZE(other_data));
+  EXPECT_DEATH(other_ref.copyFrom(ref), kDeathRegex);
+}
+
+TEST(MutableArrayRef, truncatedCopyFrom) {
+  int other_data[ARRAY_SIZE(data) - 2] = {0};
+  MutableArrayRef<int> other_ref(other_data, ARRAY_SIZE(other_data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_data[index], 0);
+  }
+  uptr elts = other_ref.truncatedCopyFrom(ref);
+  EXPECT_EQ(elts, ARRAY_SIZE(other_data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_ref[index], ref[index]);
+  }
+}
+
+TEST(MutableArrayRef, truncatedCopyFromNoTrunc) {
+  int other_data[ARRAY_SIZE(data)] = {0};
+  MutableArrayRef<int> other_ref(other_data, ARRAY_SIZE(other_data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_data[index], 0);
+  }
+  uptr elts = other_ref.truncatedCopyFrom(ref);
+  EXPECT_EQ(elts, ARRAY_SIZE(data));
+  for (unsigned index = 0; index < ARRAY_SIZE(other_data); ++index) {
+    EXPECT_EQ(other_ref[index], ref[index]);
+  }
+}
+
+TEST(MutableArrayRef, truncatedCopyFromUnsafeOverlap) {
+  MutableArrayRef<int> other_ref(data, ARRAY_SIZE(data));
+  EXPECT_DEATH(other_ref.truncatedCopyFrom(ref), kDeathRegex);
+}
+
+TEST(MutableArrayRef, containsPtr) {
+  for (unsigned index = 0; index < ARRAY_SIZE(data); ++index) {
+    EXPECT_TRUE(ref.containsPtr(&(data[index])));
+  }
+  EXPECT_FALSE(ref.containsPtr(&(data[ARRAY_SIZE(data)])));
+  EXPECT_FALSE(ref.containsPtr(nullptr));
+}
+
+TEST(MutableArrayRef, zeroSize) {
+  MutableArrayRef<int*> null_ref(nullptr, 0);
+  EXPECT_EQ(null_ref.size(), (uptr)0);
+  EXPECT_EQ(null_ref.begin(), null_ref.end());
+  EXPECT_EQ(null_ref.begin(), nullptr);
+}
+
+TEST(MutableArrayRef, zeroSizeBadAccess) {
+  MutableArrayRef<int*> null_ref(nullptr, 0);
+  EXPECT_DEATH(null_ref[0], kDeathRegex);
+}
+
+TEST(MutableArrayRef, slice) {
+  auto slice = ref.slice(2);
+  EXPECT_EQ(slice.size(), ref.size() - 2);
+  for (unsigned index = 0; index < slice.size(); ++index) {
+    EXPECT_EQ(slice[index], ref[index + 2]);
+  }
+}
+
+TEST(MutableArrayRef, sliceToZero) {
+  auto slice = ref.slice(ref.size());
+  EXPECT_EQ(slice.size(), static_cast<uptr>(0));
+}
+
+TEST(MutableArrayRef, sliceTooLarge) {
+  EXPECT_DEATH(ref.slice(ref.size() + 1), kDeathRegex);
+}
+
+TEST(MutableArrayRef, assign) {
+  int other_data[2] = {0};
+  MutableArrayRef<int> other_ref(other_data);
+  EXPECT_EQ(other_ref.size(), ARRAY_SIZE(other_data));
+  other_ref = ref;
+  EXPECT_EQ(other_ref.size(), ref.size());
+  EXPECT_EQ(other_ref.data(), ref.data());
+}