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
16namespace 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.
24template <typename T> class VectorNoCtor {
25public:
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
75protected:
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
88private:
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
114template <typename T> class Vector : public VectorNoCtor<T> {
115public:
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