1 /*
2  * Copyright (C) 2020 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 SRC_PROFILING_PERF_UNWIND_QUEUE_H_
18 #define SRC_PROFILING_PERF_UNWIND_QUEUE_H_
19 
20 #include <array>
21 #include <atomic>
22 
23 #include "perfetto/base/logging.h"
24 
25 namespace perfetto {
26 namespace profiling {
27 
28 struct WriteView {
29   bool valid;  // if false: buffer is full, and |write_pos| is invalid
30   uint64_t write_pos;
31 };
32 
33 struct ReadView {
34   uint64_t read_pos;
35   uint64_t write_pos;
36 };
37 
38 // Single-writer, single-reader ring buffer of fixed-size entries (of any
39 // default-constructible type). Size of the buffer is static for the lifetime of
40 // UnwindQueue, and must be a power of two.
41 // Writer side appends entries one at a time, and must stop if there
42 // is no available capacity.
43 // Reader side sees all unconsumed entries, and can advance the reader position
44 // by any amount.
45 template <typename T, uint32_t QueueSize>
46 class UnwindQueue {
47  public:
UnwindQueue()48   UnwindQueue() {
49     static_assert(QueueSize != 0 && ((QueueSize & (QueueSize - 1)) == 0),
50                   "not a power of two");
51   }
52 
53   UnwindQueue(const UnwindQueue&) = delete;
54   UnwindQueue& operator=(const UnwindQueue&) = delete;
55   UnwindQueue(UnwindQueue&&) = delete;
56   UnwindQueue& operator=(UnwindQueue&&) = delete;
57 
at(uint64_t pos)58   T& at(uint64_t pos) { return data_[pos % QueueSize]; }
59 
BeginWrite()60   WriteView BeginWrite() {
61     uint64_t rd = rd_pos_.load(std::memory_order_acquire);
62     uint64_t wr = wr_pos_.load(std::memory_order_relaxed);
63 
64     PERFETTO_DCHECK(wr >= rd);
65     if (wr - rd >= QueueSize)
66       return WriteView{false, 0};  // buffer fully occupied
67 
68     return WriteView{true, wr};
69   }
70 
CommitWrite()71   void CommitWrite() { wr_pos_.fetch_add(1u, std::memory_order_release); }
72 
BeginRead()73   ReadView BeginRead() {
74     uint64_t wr = wr_pos_.load(std::memory_order_acquire);
75     uint64_t rd = rd_pos_.load(std::memory_order_relaxed);
76 
77     PERFETTO_DCHECK(wr >= rd && wr - rd <= QueueSize);
78     return ReadView{rd, wr};
79   }
80 
CommitNewReadPosition(uint64_t pos)81   void CommitNewReadPosition(uint64_t pos) {
82     rd_pos_.store(pos, std::memory_order_release);
83   }
84 
85  private:
86   std::array<T, QueueSize> data_;
87   std::atomic<uint64_t> wr_pos_{0};
88   std::atomic<uint64_t> rd_pos_{0};
89 };
90 
91 }  // namespace profiling
92 }  // namespace perfetto
93 
94 #endif  // SRC_PROFILING_PERF_UNWIND_QUEUE_H_
95