1 /*
2 * Copyright (C) 2017 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
6 * License. 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,
11 * software distributed under the License is distributed on an "AS
12 * IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
13 * express or implied. See the License for the specific language
14 * governing permissions and limitations under the License.
15 */
16 #include "perfetto/tracing/core/shared_memory_abi.h"
17
18 #include "perfetto/base/build_config.h"
19 #include "perfetto/base/time.h"
20
21 #if !PERFETTO_BUILDFLAG(PERFETTO_OS_WIN)
22 #include <sys/mman.h>
23 #endif
24
25 #include "perfetto/base/utils.h"
26 #include "perfetto/tracing/core/basic_types.h"
27
28 namespace perfetto {
29
30 namespace {
31
32 constexpr int kRetryAttempts = 64;
33
WaitBeforeNextAttempt(int attempt)34 inline void WaitBeforeNextAttempt(int attempt) {
35 if (attempt < kRetryAttempts / 2) {
36 std::this_thread::yield();
37 } else {
38 base::SleepMicroseconds((unsigned(attempt) / 10) * 1000);
39 }
40 }
41
42 // Returns the largest 4-bytes aligned chunk size <= |page_size| / |divider|
43 // for each divider in PageLayout.
GetChunkSize(size_t page_size,size_t divider)44 constexpr size_t GetChunkSize(size_t page_size, size_t divider) {
45 return ((page_size - sizeof(SharedMemoryABI::PageHeader)) / divider) & ~3UL;
46 }
47
48 // Initializer for the const |chunk_sizes_| array.
InitChunkSizes(size_t page_size)49 std::array<uint16_t, SharedMemoryABI::kNumPageLayouts> InitChunkSizes(
50 size_t page_size) {
51 static_assert(SharedMemoryABI::kNumPageLayouts ==
52 base::ArraySize(SharedMemoryABI::kNumChunksForLayout),
53 "kNumPageLayouts out of date");
54 std::array<uint16_t, SharedMemoryABI::kNumPageLayouts> res = {};
55 for (size_t i = 0; i < SharedMemoryABI::kNumPageLayouts; i++) {
56 size_t num_chunks = SharedMemoryABI::kNumChunksForLayout[i];
57 size_t size = num_chunks == 0 ? 0 : GetChunkSize(page_size, num_chunks);
58 PERFETTO_CHECK(size <= std::numeric_limits<uint16_t>::max());
59 res[i] = static_cast<uint16_t>(size);
60 }
61 return res;
62 }
63
ClearChunkHeader(SharedMemoryABI::ChunkHeader * header)64 inline void ClearChunkHeader(SharedMemoryABI::ChunkHeader* header) {
65 header->writer_id.store(0u, std::memory_order_relaxed);
66 header->chunk_id.store(0u, std::memory_order_relaxed);
67 header->packets.store({}, std::memory_order_release);
68 }
69
70 } // namespace
71
72 // static
73 constexpr uint32_t SharedMemoryABI::kNumChunksForLayout[];
74 constexpr const char* SharedMemoryABI::kChunkStateStr[];
75 constexpr const size_t SharedMemoryABI::kInvalidPageIdx;
76 constexpr const size_t SharedMemoryABI::kMaxPageSize;
77
78 SharedMemoryABI::SharedMemoryABI() = default;
79
SharedMemoryABI(uint8_t * start,size_t size,size_t page_size)80 SharedMemoryABI::SharedMemoryABI(uint8_t* start,
81 size_t size,
82 size_t page_size) {
83 Initialize(start, size, page_size);
84 }
85
Initialize(uint8_t * start,size_t size,size_t page_size)86 void SharedMemoryABI::Initialize(uint8_t* start,
87 size_t size,
88 size_t page_size) {
89 start_ = start;
90 size_ = size;
91 page_size_ = page_size;
92 num_pages_ = size / page_size;
93 chunk_sizes_ = InitChunkSizes(page_size);
94 static_assert(sizeof(PageHeader) == 8, "PageHeader size");
95 static_assert(sizeof(ChunkHeader) == 8, "ChunkHeader size");
96 static_assert(sizeof(ChunkHeader::chunk_id) == sizeof(ChunkID),
97 "ChunkID size");
98
99 static_assert(sizeof(ChunkHeader::Packets) == 2, "ChunkHeader::Packets size");
100 static_assert(alignof(ChunkHeader) == kChunkAlignment,
101 "ChunkHeader alignment");
102
103 // In theory std::atomic does not guarantee that the underlying type
104 // consists only of the actual atomic word. Theoretically it could have
105 // locks or other state. In practice most implementations just implement
106 // them without extra state. The code below overlays the atomic into the
107 // SMB, hence relies on this implementation detail. This should be fine
108 // pragmatically (Chrome's base makes the same assumption), but let's have a
109 // check for this.
110 static_assert(sizeof(std::atomic<uint32_t>) == sizeof(uint32_t) &&
111 sizeof(std::atomic<uint16_t>) == sizeof(uint16_t),
112 "Incompatible STL <atomic> implementation");
113
114 // Chec that the kAllChunks(Complete,Free) are consistent with the
115 // ChunkState enum values.
116
117 // These must be zero because rely on zero-initialized memory being
118 // interpreted as "free".
119 static_assert(kChunkFree == 0 && kAllChunksFree == 0,
120 "kChunkFree/kAllChunksFree and must be 0");
121
122 static_assert((kAllChunksComplete & kChunkMask) == kChunkComplete,
123 "kAllChunksComplete out of sync with kChunkComplete");
124
125 // Sanity check the consistency of the kMax... constants.
126 static_assert(sizeof(ChunkHeader::writer_id) == sizeof(WriterID),
127 "WriterID size");
128 ChunkHeader chunk_header{};
129 chunk_header.chunk_id.store(static_cast<uint32_t>(-1));
130 PERFETTO_CHECK(chunk_header.chunk_id.load() == kMaxChunkID);
131
132 chunk_header.writer_id.store(static_cast<uint16_t>(-1));
133 PERFETTO_CHECK(kMaxWriterID <= chunk_header.writer_id.load());
134
135 PERFETTO_CHECK(page_size >= base::kPageSize);
136 PERFETTO_CHECK(page_size <= kMaxPageSize);
137 PERFETTO_CHECK(page_size % base::kPageSize == 0);
138 PERFETTO_CHECK(reinterpret_cast<uintptr_t>(start) % base::kPageSize == 0);
139 PERFETTO_CHECK(size % page_size == 0);
140 }
141
GetChunkUnchecked(size_t page_idx,uint32_t page_layout,size_t chunk_idx)142 SharedMemoryABI::Chunk SharedMemoryABI::GetChunkUnchecked(size_t page_idx,
143 uint32_t page_layout,
144 size_t chunk_idx) {
145 const size_t num_chunks = GetNumChunksForLayout(page_layout);
146 PERFETTO_DCHECK(chunk_idx < num_chunks);
147 // Compute the chunk virtual address and write it into |chunk|.
148 const uint16_t chunk_size = GetChunkSizeForLayout(page_layout);
149 size_t chunk_offset_in_page = sizeof(PageHeader) + chunk_idx * chunk_size;
150
151 Chunk chunk(page_start(page_idx) + chunk_offset_in_page, chunk_size,
152 static_cast<uint8_t>(chunk_idx));
153 PERFETTO_DCHECK(chunk.end() <= end());
154 return chunk;
155 }
156
TryAcquireChunk(size_t page_idx,size_t chunk_idx,ChunkState desired_chunk_state,const ChunkHeader * header)157 SharedMemoryABI::Chunk SharedMemoryABI::TryAcquireChunk(
158 size_t page_idx,
159 size_t chunk_idx,
160 ChunkState desired_chunk_state,
161 const ChunkHeader* header) {
162 PERFETTO_DCHECK(desired_chunk_state == kChunkBeingRead ||
163 desired_chunk_state == kChunkBeingWritten);
164 PageHeader* phdr = page_header(page_idx);
165 for (int attempt = 0; attempt < kRetryAttempts; attempt++) {
166 uint32_t layout = phdr->layout.load(std::memory_order_acquire);
167 const size_t num_chunks = GetNumChunksForLayout(layout);
168
169 // The page layout has changed (or the page is free).
170 if (chunk_idx >= num_chunks)
171 return Chunk();
172
173 // Verify that the chunk is still in a state that allows the transition to
174 // |desired_chunk_state|. The only allowed transitions are:
175 // 1. kChunkFree -> kChunkBeingWritten (Producer).
176 // 2. kChunkComplete -> kChunkBeingRead (Service).
177 ChunkState expected_chunk_state =
178 desired_chunk_state == kChunkBeingWritten ? kChunkFree : kChunkComplete;
179 auto cur_chunk_state = (layout >> (chunk_idx * kChunkShift)) & kChunkMask;
180 if (cur_chunk_state != expected_chunk_state)
181 return Chunk();
182
183 uint32_t next_layout = layout;
184 next_layout &= ~(kChunkMask << (chunk_idx * kChunkShift));
185 next_layout |= (desired_chunk_state << (chunk_idx * kChunkShift));
186 if (phdr->layout.compare_exchange_strong(layout, next_layout,
187 std::memory_order_acq_rel)) {
188 // Compute the chunk virtual address and write it into |chunk|.
189 Chunk chunk = GetChunkUnchecked(page_idx, layout, chunk_idx);
190 if (desired_chunk_state == kChunkBeingWritten) {
191 PERFETTO_DCHECK(header);
192 ChunkHeader* new_header = chunk.header();
193 new_header->writer_id.store(header->writer_id,
194 std::memory_order_relaxed);
195 new_header->chunk_id.store(header->chunk_id, std::memory_order_relaxed);
196 new_header->packets.store(header->packets, std::memory_order_release);
197 }
198 return chunk;
199 }
200 WaitBeforeNextAttempt(attempt);
201 }
202 return Chunk(); // All our attempts failed.
203 }
204
TryPartitionPage(size_t page_idx,PageLayout layout)205 bool SharedMemoryABI::TryPartitionPage(size_t page_idx, PageLayout layout) {
206 PERFETTO_DCHECK(layout >= kPageDiv1 && layout <= kPageDiv14);
207 uint32_t expected_layout = 0; // Free page.
208 uint32_t next_layout = (layout << kLayoutShift) & kLayoutMask;
209 PageHeader* phdr = page_header(page_idx);
210 if (!phdr->layout.compare_exchange_strong(expected_layout, next_layout,
211 std::memory_order_acq_rel)) {
212 return false;
213 }
214 return true;
215 }
216
GetFreeChunks(size_t page_idx)217 uint32_t SharedMemoryABI::GetFreeChunks(size_t page_idx) {
218 uint32_t layout =
219 page_header(page_idx)->layout.load(std::memory_order_relaxed);
220 const uint32_t num_chunks = GetNumChunksForLayout(layout);
221 uint32_t res = 0;
222 for (uint32_t i = 0; i < num_chunks; i++) {
223 res |= ((layout & kChunkMask) == kChunkFree) ? (1 << i) : 0;
224 layout >>= kChunkShift;
225 }
226 return res;
227 }
228
ReleaseChunk(Chunk chunk,ChunkState desired_chunk_state)229 size_t SharedMemoryABI::ReleaseChunk(Chunk chunk,
230 ChunkState desired_chunk_state) {
231 PERFETTO_DCHECK(desired_chunk_state == kChunkComplete ||
232 desired_chunk_state == kChunkFree);
233
234 size_t page_idx;
235 size_t chunk_idx;
236 std::tie(page_idx, chunk_idx) = GetPageAndChunkIndex(chunk);
237
238 // Reset header fields, so that the service can identify when the chunk's
239 // header has been initialized by the producer.
240 if (desired_chunk_state == kChunkFree)
241 ClearChunkHeader(chunk.header());
242
243 for (int attempt = 0; attempt < kRetryAttempts; attempt++) {
244 PageHeader* phdr = page_header(page_idx);
245 uint32_t layout = phdr->layout.load(std::memory_order_relaxed);
246 const size_t page_chunk_size = GetChunkSizeForLayout(layout);
247
248 // TODO(primiano): this should not be a CHECK, because a malicious producer
249 // could crash us by putting the chunk in an invalid state. This should
250 // gracefully fail. Keep a CHECK until then.
251 PERFETTO_CHECK(chunk.size() == page_chunk_size);
252 const uint32_t chunk_state =
253 ((layout >> (chunk_idx * kChunkShift)) & kChunkMask);
254
255 // Verify that the chunk is still in a state that allows the transition to
256 // |desired_chunk_state|. The only allowed transitions are:
257 // 1. kChunkBeingWritten -> kChunkComplete (Producer).
258 // 2. kChunkBeingRead -> kChunkFree (Service).
259 ChunkState expected_chunk_state;
260 if (desired_chunk_state == kChunkComplete) {
261 expected_chunk_state = kChunkBeingWritten;
262 } else {
263 expected_chunk_state = kChunkBeingRead;
264 }
265
266 // TODO(primiano): should not be a CHECK (same rationale of comment above).
267 PERFETTO_CHECK(chunk_state == expected_chunk_state);
268 uint32_t next_layout = layout;
269 next_layout &= ~(kChunkMask << (chunk_idx * kChunkShift));
270 next_layout |= (desired_chunk_state << (chunk_idx * kChunkShift));
271
272 // If we are freeing a chunk and all the other chunks in the page are free
273 // we should de-partition the page and mark it as clear.
274 if ((next_layout & kAllChunksMask) == kAllChunksFree)
275 next_layout = 0;
276
277 if (phdr->layout.compare_exchange_strong(layout, next_layout,
278 std::memory_order_acq_rel)) {
279 return page_idx;
280 }
281 WaitBeforeNextAttempt(attempt);
282 }
283 // Too much contention on this page. Give up. This page will be left pending
284 // forever but there isn't much more we can do at this point.
285 PERFETTO_DFATAL("Too much contention on page.");
286 return kInvalidPageIdx;
287 }
288
289 SharedMemoryABI::Chunk::Chunk() = default;
290
Chunk(uint8_t * begin,uint16_t size,uint8_t chunk_idx)291 SharedMemoryABI::Chunk::Chunk(uint8_t* begin, uint16_t size, uint8_t chunk_idx)
292 : begin_(begin), size_(size), chunk_idx_(chunk_idx) {
293 PERFETTO_CHECK(reinterpret_cast<uintptr_t>(begin) % kChunkAlignment == 0);
294 PERFETTO_CHECK(size > 0);
295 }
296
Chunk(Chunk && o)297 SharedMemoryABI::Chunk::Chunk(Chunk&& o) noexcept {
298 *this = std::move(o);
299 }
300
operator =(Chunk && o)301 SharedMemoryABI::Chunk& SharedMemoryABI::Chunk::operator=(Chunk&& o) {
302 begin_ = o.begin_;
303 size_ = o.size_;
304 chunk_idx_ = o.chunk_idx_;
305 o.begin_ = nullptr;
306 o.size_ = 0;
307 o.chunk_idx_ = 0;
308 return *this;
309 }
310
GetPageAndChunkIndex(const Chunk & chunk)311 std::pair<size_t, size_t> SharedMemoryABI::GetPageAndChunkIndex(
312 const Chunk& chunk) {
313 PERFETTO_DCHECK(chunk.is_valid());
314 PERFETTO_DCHECK(chunk.begin() >= start_);
315 PERFETTO_DCHECK(chunk.end() <= start_ + size_);
316
317 // TODO(primiano): The divisions below could be avoided if we cached
318 // |page_shift_|.
319 const uintptr_t rel_addr = static_cast<uintptr_t>(chunk.begin() - start_);
320 const size_t page_idx = rel_addr / page_size_;
321 const size_t offset = rel_addr % page_size_;
322 PERFETTO_DCHECK(offset >= sizeof(PageHeader));
323 PERFETTO_DCHECK(offset % kChunkAlignment == 0);
324 PERFETTO_DCHECK((offset - sizeof(PageHeader)) % chunk.size() == 0);
325 const size_t chunk_idx = (offset - sizeof(PageHeader)) / chunk.size();
326 PERFETTO_DCHECK(chunk_idx < kMaxChunksPerPage);
327 PERFETTO_DCHECK(chunk_idx < GetNumChunksForLayout(GetPageLayout(page_idx)));
328 return std::make_pair(page_idx, chunk_idx);
329 }
330
331 } // namespace perfetto
332