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