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> 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 } 34 void push_back(const T &Element) { 35 DCHECK_LE(Size, capacity()); 36 if (Size == capacity()) { 37 const uptr NewCapacity = roundUpPowerOfTwo(Size + 1); 38 reallocate(NewCapacity); 39 } 40 memcpy(&Data[Size++], &Element, sizeof(T)); 41 } 42 T &back() { 43 DCHECK_GT(Size, 0); 44 return Data[Size - 1]; 45 } 46 void pop_back() { 47 DCHECK_GT(Size, 0); 48 Size--; 49 } 50 uptr size() const { return Size; } 51 const T *data() const { return Data; } 52 T *data() { return Data; } 53 constexpr uptr capacity() const { return CapacityBytes / sizeof(T); } 54 void reserve(uptr NewSize) { 55 // Never downsize internal buffer. 56 if (NewSize > capacity()) 57 reallocate(NewSize); 58 } 59 void resize(uptr NewSize) { 60 if (NewSize > Size) { 61 reserve(NewSize); 62 memset(&Data[Size], 0, sizeof(T) * (NewSize - Size)); 63 } 64 Size = NewSize; 65 } 66 67 void clear() { Size = 0; } 68 bool empty() const { return size() == 0; } 69 70 const T *begin() const { return data(); } 71 T *begin() { return data(); } 72 const T *end() const { return data() + size(); } 73 T *end() { return data() + size(); } 74 75 protected: 76 constexpr void init(uptr InitialCapacity = 0) { 77 Data = &LocalData[0]; 78 CapacityBytes = sizeof(LocalData); 79 if (InitialCapacity > capacity()) 80 reserve(InitialCapacity); 81 } 82 void destroy() { 83 if (Data != &LocalData[0]) 84 ExternalBuffer.unmap(ExternalBuffer.getBase(), 85 ExternalBuffer.getCapacity()); 86 } 87 88 private: 89 void reallocate(uptr NewCapacity) { 90 DCHECK_GT(NewCapacity, 0); 91 DCHECK_LE(Size, NewCapacity); 92 93 MemMapT NewExternalBuffer; 94 NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached()); 95 NewExternalBuffer.map(/*Addr=*/0U, NewCapacity, "scudo:vector"); 96 T *NewExternalData = reinterpret_cast<T *>(NewExternalBuffer.getBase()); 97 98 memcpy(NewExternalData, Data, Size * sizeof(T)); 99 destroy(); 100 101 Data = NewExternalData; 102 CapacityBytes = NewCapacity; 103 ExternalBuffer = NewExternalBuffer; 104 } 105 106 T *Data = nullptr; 107 uptr CapacityBytes = 0; 108 uptr Size = 0; 109 110 T LocalData[256 / sizeof(T)] = {}; 111 MemMapT ExternalBuffer; 112 }; 113 114 template <typename T> class Vector : public VectorNoCtor<T> { 115 public: 116 constexpr Vector() { VectorNoCtor<T>::init(); } 117 explicit Vector(uptr Count) { 118 VectorNoCtor<T>::init(Count); 119 this->resize(Count); 120 } 121 ~Vector() { VectorNoCtor<T>::destroy(); } 122 // Disallow copies and moves. 123 Vector(const Vector &) = delete; 124 Vector &operator=(const Vector &) = delete; 125 Vector(Vector &&) = delete; 126 Vector &operator=(Vector &&) = delete; 127 }; 128 129 } // namespace scudo 130 131 #endif // SCUDO_VECTOR_H_ 132