1 // Copyright 2017 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_CONTAINERS_VECTOR_BUFFER_H_ 6 #define BASE_CONTAINERS_VECTOR_BUFFER_H_ 7 8 #include <stdlib.h> 9 #include <string.h> 10 11 #include <type_traits> 12 #include <utility> 13 14 #include "base/check.h" 15 #include "base/check_op.h" 16 #include "base/compiler_specific.h" 17 #include "base/containers/util.h" 18 #include "base/memory/raw_ptr_exclusion.h" 19 #include "base/numerics/checked_math.h" 20 21 namespace base::internal { 22 23 // Internal implementation detail of base/containers. 24 // 25 // Implements a vector-like buffer that holds a certain capacity of T. Unlike 26 // std::vector, VectorBuffer never constructs or destructs its arguments, and 27 // can't change sizes. But it does implement templates to assist in efficient 28 // moving and destruction of those items manually. 29 // 30 // In particular, the destructor function does not iterate over the items if 31 // there is no destructor. Moves should be implemented as a memcpy/memmove for 32 // trivially copyable objects (POD) otherwise, it should be a std::move if 33 // possible, and as a last resort it falls back to a copy. This behavior is 34 // similar to std::vector. 35 // 36 // No special consideration is done for noexcept move constructors since 37 // we compile without exceptions. 38 // 39 // The current API does not support moving overlapping ranges. 40 template <typename T> 41 class VectorBuffer { 42 public: 43 constexpr VectorBuffer() = default; 44 45 #if defined(__clang__) && !defined(__native_client__) 46 // This constructor converts an uninitialized void* to a T* which triggers 47 // clang Control Flow Integrity. Since this is as-designed, disable. 48 __attribute__((no_sanitize("cfi-unrelated-cast", "vptr"))) 49 #endif VectorBuffer(size_t count)50 VectorBuffer(size_t count) 51 : buffer_(reinterpret_cast<T*>( 52 malloc(CheckMul(sizeof(T), count).ValueOrDie()))), 53 capacity_(count) { 54 } VectorBuffer(VectorBuffer && other)55 VectorBuffer(VectorBuffer&& other) noexcept 56 : buffer_(other.buffer_), capacity_(other.capacity_) { 57 other.buffer_ = nullptr; 58 other.capacity_ = 0; 59 } 60 61 VectorBuffer(const VectorBuffer&) = delete; 62 VectorBuffer& operator=(const VectorBuffer&) = delete; 63 ~VectorBuffer()64 ~VectorBuffer() { free(buffer_); } 65 66 VectorBuffer& operator=(VectorBuffer&& other) { 67 free(buffer_); 68 buffer_ = other.buffer_; 69 capacity_ = other.capacity_; 70 71 other.buffer_ = nullptr; 72 other.capacity_ = 0; 73 return *this; 74 } 75 capacity()76 size_t capacity() const { return capacity_; } 77 78 T& operator[](size_t i) { 79 // TODO(crbug.com/817982): Some call sites (at least circular_deque.h) are 80 // calling this with `i == capacity_` as a way of getting `end()`. Therefore 81 // we have to allow this for now (`i <= capacity_`), until we fix those call 82 // sites to use real iterators. This comment applies here and to `const T& 83 // operator[]`, below. 84 CHECK_LE(i, capacity_); 85 return buffer_[i]; 86 } 87 88 const T& operator[](size_t i) const { 89 CHECK_LE(i, capacity_); 90 return buffer_[i]; 91 } 92 begin()93 T* begin() { return buffer_; } end()94 T* end() { return &buffer_[capacity_]; } 95 96 // DestructRange ------------------------------------------------------------ 97 DestructRange(T * begin,T * end)98 void DestructRange(T* begin, T* end) { 99 // Trivially destructible objects need not have their destructors called. 100 if constexpr (!std::is_trivially_destructible_v<T>) { 101 CHECK_LE(begin, end); 102 while (begin != end) { 103 begin->~T(); 104 begin++; 105 } 106 } 107 } 108 109 // MoveRange ---------------------------------------------------------------- 110 // 111 // The destructor will be called (as necessary) for all moved types. The 112 // ranges must not overlap. 113 // 114 // The parameters and begin and end (one past the last) of the input buffer, 115 // and the address of the first element to copy to. There must be sufficient 116 // room in the destination for all items in the range [begin, end). 117 118 // Trivially copyable types can use memcpy. Trivially copyable implies 119 // that there is a trivial destructor as we don't have to call it. 120 121 // Trivially relocatable types can also use memcpy. Trivially relocatable 122 // imples that memcpy is equivalent to move + destroy. 123 124 template <typename T2> 125 static inline constexpr bool is_trivially_copyable_or_relocatable = 126 std::is_trivially_copyable_v<T2> || IS_TRIVIALLY_RELOCATABLE(T2); 127 MoveRange(T * from_begin,T * from_end,T * to)128 static void MoveRange(T* from_begin, T* from_end, T* to) { 129 CHECK(!RangesOverlap(from_begin, from_end, to)); 130 131 if constexpr (is_trivially_copyable_or_relocatable<T>) { 132 memcpy(to, from_begin, 133 CheckSub(get_uintptr(from_end), get_uintptr(from_begin)) 134 .ValueOrDie()); 135 } else { 136 while (from_begin != from_end) { 137 if constexpr (std::move_constructible<T>) { 138 new (to) T(std::move(*from_begin)); 139 } else { 140 new (to) T(*from_begin); 141 } 142 from_begin->~T(); 143 from_begin++; 144 to++; 145 } 146 } 147 } 148 149 private: RangesOverlap(const T * from_begin,const T * from_end,const T * to)150 static bool RangesOverlap(const T* from_begin, 151 const T* from_end, 152 const T* to) { 153 const auto from_begin_uintptr = get_uintptr(from_begin); 154 const auto from_end_uintptr = get_uintptr(from_end); 155 const auto to_uintptr = get_uintptr(to); 156 return !( 157 to >= from_end || 158 CheckAdd(to_uintptr, CheckSub(from_end_uintptr, from_begin_uintptr)) 159 .ValueOrDie() <= from_begin_uintptr); 160 } 161 162 // `buffer_` is not a raw_ptr<...> for performance reasons (based on analysis 163 // of sampling profiler data and tab_search:top100:2020). 164 RAW_PTR_EXCLUSION T* buffer_ = nullptr; 165 size_t capacity_ = 0; 166 }; 167 168 } // namespace base::internal 169 170 #endif // BASE_CONTAINERS_VECTOR_BUFFER_H_ 171