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