Home | History | Annotate | Download | only in core 
      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