1 /*
2  * Copyright (C) 2019 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef INCLUDE_PERFETTO_BASE_CIRCULAR_QUEUE_H_
18 #define INCLUDE_PERFETTO_BASE_CIRCULAR_QUEUE_H_
19 
20 #include <stdint.h>
21 #include <iterator>
22 
23 #include "perfetto/base/logging.h"
24 #include "perfetto/base/utils.h"
25 
26 namespace perfetto {
27 namespace base {
28 
29 // CircularQueue is a push-back-only / pop-front-only queue with the following
30 // characteristics:
31 // - The storage is based on a flat circular buffer. Beginning and end wrap
32 //   as necessary, to keep pushes and pops O(1) as long as capacity expansion is
33 //   not required.
34 // - Capacity is automatically expanded like in a std::vector. Expansion has a
35 //   O(N) cost.
36 // - It allows random access, allowing in-place std::sort.
37 // - Iterators are not stable. Mutating the container invalidates all iterators.
38 // - It doesn't bother with const-correctness.
39 //
40 // Implementation details:
41 // Internally, |begin|, |end| and iterators use 64-bit monotonic indexes, which
42 // are incremented as if the queue was backed by unlimited storage.
43 // Even assuming that elements are inserted and removed every nanosecond, 64 bit
44 // is enough for 584 years.
45 // Wrapping happens only when addressing elements in the underlying circular
46 // storage. This limits the complexity and avoiding dealing with modular
47 // arithmetic all over the places.
48 template <class T>
49 class CircularQueue {
50  public:
51   class Iterator {
52    public:
53     using difference_type = ptrdiff_t;
54     using value_type = T;
55     using pointer = const T*;
56     using reference = const T&;
57     using iterator_category = std::random_access_iterator_tag;
58 
Iterator(CircularQueue * queue,uint64_t pos,uint32_t generation)59     Iterator(CircularQueue* queue, uint64_t pos, uint32_t generation)
60         : queue_(queue),
61           pos_(pos)
62 #if PERFETTO_DCHECK_IS_ON()
63           ,
64           generation_(generation)
65 #endif
66     {
67       ignore_result(generation);
68     }
69 
70     T* operator->() {
71 #if PERFETTO_DCHECK_IS_ON()
72       PERFETTO_DCHECK(generation_ == queue_->generation());
73 #endif
74       return queue_->Get(pos_);
75     }
76 
77     T& operator*() { return *(operator->()); }
78 
79     const value_type& operator[](difference_type i) const {
80       return *(*this + i);
81     }
82 
83     Iterator& operator++() {
84       Add(1);
85       return *this;
86     }
87 
88     Iterator operator++(int) {
89       Iterator ret = *this;
90       Add(1);
91       return ret;
92     }
93 
94     Iterator& operator--() {
95       Add(-1);
96       return *this;
97     }
98 
99     Iterator operator--(int) {
100       Iterator ret = *this;
101       Add(-1);
102       return ret;
103     }
104 
105     friend Iterator operator+(const Iterator& iter, difference_type offset) {
106       Iterator ret = iter;
107       ret.Add(offset);
108       return ret;
109     }
110 
111     Iterator& operator+=(difference_type offset) {
112       Add(offset);
113       return *this;
114     }
115 
116     friend Iterator operator-(const Iterator& iter, difference_type offset) {
117       Iterator ret = iter;
118       ret.Add(-offset);
119       return ret;
120     }
121 
122     Iterator& operator-=(difference_type offset) {
123       Add(-offset);
124       return *this;
125     }
126 
127     friend ptrdiff_t operator-(const Iterator& lhs, const Iterator& rhs) {
128       return static_cast<ptrdiff_t>(lhs.pos_) -
129              static_cast<ptrdiff_t>(rhs.pos_);
130     }
131 
132     friend bool operator==(const Iterator& lhs, const Iterator& rhs) {
133       return lhs.pos_ == rhs.pos_;
134     }
135 
136     friend bool operator!=(const Iterator& lhs, const Iterator& rhs) {
137       return lhs.pos_ != rhs.pos_;
138     }
139 
140     friend bool operator<(const Iterator& lhs, const Iterator& rhs) {
141       return lhs.pos_ < rhs.pos_;
142     }
143 
144     friend bool operator<=(const Iterator& lhs, const Iterator& rhs) {
145       return lhs.pos_ <= rhs.pos_;
146     }
147 
148     friend bool operator>(const Iterator& lhs, const Iterator& rhs) {
149       return lhs.pos_ > rhs.pos_;
150     }
151 
152     friend bool operator>=(const Iterator& lhs, const Iterator& rhs) {
153       return lhs.pos_ >= rhs.pos_;
154     }
155 
156    private:
Add(difference_type offset)157     inline void Add(difference_type offset) {
158       pos_ = static_cast<uint64_t>(static_cast<difference_type>(pos_) + offset);
159       PERFETTO_DCHECK(pos_ <= queue_->end_);
160     }
161 
162     CircularQueue* queue_;
163     uint64_t pos_;
164 
165 #if PERFETTO_DCHECK_IS_ON()
166     uint32_t generation_;
167 #endif
168   };
169 
170   CircularQueue(size_t initial_capacity = 1024) { Grow(initial_capacity); }
171 
CircularQueue(CircularQueue && other)172   CircularQueue(CircularQueue&& other) noexcept {
173     // Copy all fields using the (private) default copy assignment operator.
174     *this = other;
175     increment_generation();
176     new (&other) CircularQueue();  // Reset the old queue so it's still usable.
177   }
178 
179   CircularQueue& operator=(CircularQueue&& other) {
180     this->~CircularQueue();                      // Destroy the current state.
181     new (this) CircularQueue(std::move(other));  // Use the move ctor above.
182     return *this;
183   }
184 
~CircularQueue()185   ~CircularQueue() {
186     if (!entries_) {
187       PERFETTO_DCHECK(empty());
188       return;
189     }
190     erase_front(size());  // Invoke destructors on all alive entries.
191     PERFETTO_DCHECK(empty());
192     free(entries_);
193   }
194 
195   template <typename... Args>
emplace_back(Args &&...args)196   void emplace_back(Args&&... args) {
197     increment_generation();
198     if (PERFETTO_UNLIKELY(size() >= capacity_))
199       Grow();
200     T* slot = Get(end_++);
201     new (slot) T(std::forward<Args>(args)...);
202   }
203 
erase_front(size_t n)204   void erase_front(size_t n) {
205     increment_generation();
206     for (; n && (begin_ < end_); --n) {
207       Get(begin_)->~T();
208       begin_++;  // This needs to be its own statement, Get() checks begin_.
209     }
210   }
211 
pop_front()212   void pop_front() { erase_front(1); }
213 
at(size_t idx)214   T& at(size_t idx) {
215     PERFETTO_DCHECK(idx < size());
216     return *Get(begin_ + idx);
217   }
218 
begin()219   Iterator begin() { return Iterator(this, begin_, generation()); }
end()220   Iterator end() { return Iterator(this, end_, generation()); }
front()221   T& front() { return *begin(); }
back()222   T& back() { return *(end() - 1); }
223 
empty()224   bool empty() const { return size() == 0; }
225 
size()226   size_t size() const {
227     PERFETTO_DCHECK(end_ - begin_ <= capacity_);
228     return static_cast<size_t>(end_ - begin_);
229   }
230 
capacity()231   size_t capacity() const { return capacity_; }
232 
233 #if PERFETTO_DCHECK_IS_ON()
generation()234   uint32_t generation() const { return generation_; }
increment_generation()235   void increment_generation() { ++generation_; }
236 #else
generation()237   uint32_t generation() const { return 0; }
increment_generation()238   void increment_generation() {}
239 #endif
240 
241  private:
242   CircularQueue(const CircularQueue&) = delete;
243   CircularQueue& operator=(const CircularQueue&) = default;
244 
245   void Grow(size_t new_capacity = 0) {
246     // Capacity must be always a power of two. This allows Get() to use a simple
247     // bitwise-AND for handling the wrapping instead of a full division.
248     new_capacity = new_capacity ? new_capacity : capacity_ * 2;
249     PERFETTO_CHECK((new_capacity & (new_capacity - 1)) == 0);  // Must be pow2.
250 
251     // On 32-bit systems this might hit the 4GB wall and overflow. We can't do
252     // anything other than crash in this case.
253     PERFETTO_CHECK(new_capacity > capacity_);
254     size_t malloc_size = new_capacity * sizeof(T);
255     PERFETTO_CHECK(malloc_size > new_capacity);
256     auto* new_vec = static_cast<T*>(malloc(malloc_size));
257 
258     // Move all elements in the expanded array.
259     size_t new_size = 0;
260     for (uint64_t i = begin_; i < end_; i++)
261       new (&new_vec[new_size++]) T(std::move(*Get(i)));  // Placement move ctor.
262 
263     // Even if all the elements are std::move()-d and likely empty, we are still
264     // required to call the dtor for them.
265     for (uint64_t i = begin_; i < end_; i++)
266       Get(i)->~T();
267     free(entries_);  // It's fine to free(nullptr) (for the ctor call case).
268 
269     begin_ = 0;
270     end_ = new_size;
271     capacity_ = new_capacity;
272     entries_ = new_vec;
273   }
274 
Get(uint64_t pos)275   inline T* Get(uint64_t pos) {
276     PERFETTO_DCHECK(pos >= begin_ && pos < end_);
277     PERFETTO_DCHECK((capacity_ & (capacity_ - 1)) == 0);  // Must be a pow2.
278     auto index = static_cast<size_t>(pos & (capacity_ - 1));
279     return &entries_[index];
280   }
281 
282   // Underlying storage. It's raw malloc-ed rather than being a unique_ptr<T[]>
283   // to allow having uninitialized entries inside it.
284   T* entries_ = nullptr;
285   size_t capacity_ = 0;  // Number of allocated slots (NOT bytes) in |entries_|.
286 
287   // The |begin_| and |end_| indexes are monotonic and never wrap. Modular arith
288   // is used only when dereferencing entries in the vector.
289   uint64_t begin_ = 0;
290   uint64_t end_ = 0;
291 
292 // Generation is used in debug builds only for checking iterator validity.
293 #if PERFETTO_DCHECK_IS_ON()
294   uint32_t generation_ = 0;
295 #endif
296 };
297 
298 }  // namespace base
299 }  // namespace perfetto
300 
301 #endif  // INCLUDE_PERFETTO_BASE_CIRCULAR_QUEUE_H_
302