1 //===-- vector.h ------------------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef SCUDO_VECTOR_H_ 10 #define SCUDO_VECTOR_H_ 11 12 #include "mem_map.h" 13 14 #include <string.h> 15 16 namespace scudo { 17 18 // A low-level vector based on map. It stores the contents inline up to a fixed 19 // capacity, or in an external memory buffer if it grows bigger than that. May 20 // incur a significant memory overhead for small vectors. The current 21 // implementation supports only POD types. 22 // 23 // NOTE: This class is not meant to be used directly, use Vector<T> instead. 24 template <typename T, size_t StaticNumEntries> class VectorNoCtor { 25 public: 26 T &operator[](uptr I) { 27 DCHECK_LT(I, Size); 28 return Data[I]; 29 } 30 const T &operator[](uptr I) const { 31 DCHECK_LT(I, Size); 32 return Data[I]; 33 } push_back(const T & Element)34 void push_back(const T &Element) { 35 DCHECK_LE(Size, capacity()); 36 if (Size == capacity()) { 37 const uptr NewCapacity = roundUpPowerOfTwo(Size + 1); 38 if (!reallocate(NewCapacity)) { 39 return; 40 } 41 } 42 memcpy(&Data[Size++], &Element, sizeof(T)); 43 } back()44 T &back() { 45 DCHECK_GT(Size, 0); 46 return Data[Size - 1]; 47 } pop_back()48 void pop_back() { 49 DCHECK_GT(Size, 0); 50 Size--; 51 } size()52 uptr size() const { return Size; } data()53 const T *data() const { return Data; } data()54 T *data() { return Data; } capacity()55 constexpr uptr capacity() const { return CapacityBytes / sizeof(T); } reserve(uptr NewSize)56 bool reserve(uptr NewSize) { 57 // Never downsize internal buffer. 58 if (NewSize > capacity()) 59 return reallocate(NewSize); 60 return true; 61 } resize(uptr NewSize)62 void resize(uptr NewSize) { 63 if (NewSize > Size) { 64 if (!reserve(NewSize)) { 65 return; 66 } 67 memset(&Data[Size], 0, sizeof(T) * (NewSize - Size)); 68 } 69 Size = NewSize; 70 } 71 clear()72 void clear() { Size = 0; } empty()73 bool empty() const { return size() == 0; } 74 begin()75 const T *begin() const { return data(); } begin()76 T *begin() { return data(); } end()77 const T *end() const { return data() + size(); } end()78 T *end() { return data() + size(); } 79 80 protected: 81 constexpr void init(uptr InitialCapacity = 0) { 82 Data = &LocalData[0]; 83 CapacityBytes = sizeof(LocalData); 84 if (InitialCapacity > capacity()) 85 reserve(InitialCapacity); 86 } destroy()87 void destroy() { 88 if (Data != &LocalData[0]) 89 ExternalBuffer.unmap(ExternalBuffer.getBase(), 90 ExternalBuffer.getCapacity()); 91 } 92 93 private: reallocate(uptr NewCapacity)94 bool reallocate(uptr NewCapacity) { 95 DCHECK_GT(NewCapacity, 0); 96 DCHECK_LE(Size, NewCapacity); 97 98 MemMapT NewExternalBuffer; 99 NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached()); 100 if (!NewExternalBuffer.map(/*Addr=*/0U, NewCapacity, "scudo:vector", 101 MAP_ALLOWNOMEM)) { 102 return false; 103 } 104 T *NewExternalData = reinterpret_cast<T *>(NewExternalBuffer.getBase()); 105 106 memcpy(NewExternalData, Data, Size * sizeof(T)); 107 destroy(); 108 109 Data = NewExternalData; 110 CapacityBytes = NewCapacity; 111 ExternalBuffer = NewExternalBuffer; 112 return true; 113 } 114 115 T *Data = nullptr; 116 uptr CapacityBytes = 0; 117 uptr Size = 0; 118 119 T LocalData[StaticNumEntries] = {}; 120 MemMapT ExternalBuffer; 121 }; 122 123 template <typename T, size_t StaticNumEntries> 124 class Vector : public VectorNoCtor<T, StaticNumEntries> { 125 public: 126 static_assert(StaticNumEntries > 0U, 127 "Vector must have a non-zero number of static entries."); Vector()128 constexpr Vector() { VectorNoCtor<T, StaticNumEntries>::init(); } Vector(uptr Count)129 explicit Vector(uptr Count) { 130 VectorNoCtor<T, StaticNumEntries>::init(Count); 131 this->resize(Count); 132 } ~Vector()133 ~Vector() { VectorNoCtor<T, StaticNumEntries>::destroy(); } 134 // Disallow copies and moves. 135 Vector(const Vector &) = delete; 136 Vector &operator=(const Vector &) = delete; 137 Vector(Vector &&) = delete; 138 Vector &operator=(Vector &&) = delete; 139 }; 140 141 } // namespace scudo 142 143 #endif // SCUDO_VECTOR_H_ 144