• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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