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 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. 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. 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 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 80 SharedMemoryABI::SharedMemoryABI(uint8_t* start, 81 size_t size, 82 size_t page_size) { 83 Initialize(start, size, page_size); 84 } 85 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 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 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 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 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 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 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 297 SharedMemoryABI::Chunk::Chunk(Chunk&& o) noexcept { 298 *this = std::move(o); 299 } 300 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 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