1 /* 2 * Copyright (C) 2023 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 License. 6 * 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, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef SRC_TRACE_PROCESSOR_SORTER_TRACE_TOKEN_BUFFER_H_ 18 #define SRC_TRACE_PROCESSOR_SORTER_TRACE_TOKEN_BUFFER_H_ 19 20 #include <cstdint> 21 #include <limits> 22 #include <optional> 23 #include <utility> 24 #include <vector> 25 26 #include "perfetto/base/compiler.h" 27 #include "perfetto/ext/base/circular_queue.h" 28 #include "perfetto/ext/base/utils.h" 29 #include "perfetto/trace_processor/trace_blob.h" 30 #include "perfetto/trace_processor/trace_blob_view.h" 31 #include "src/trace_processor/importers/common/parser_types.h" 32 #include "src/trace_processor/util/bump_allocator.h" 33 34 namespace perfetto { 35 namespace trace_processor { 36 37 // Helper class which stores tokenized objects while the corresponding events 38 // are being sorted by TraceSorter. 39 // 40 // This class intrusively compresses the tokenized objects as much as possible 41 // to reduce their memory footprint. This is important to reduce the peak memory 42 // usage of TraceProcessor which is always hit at some point during sorting. 43 // The tokenized objects make up the vast majority of this peak so we trade the 44 // complexity in this class for big reductions in the peak use. 45 // 46 // go/perfetto-tp-memory-use gives an overview of trace processor memory usage. 47 class TraceTokenBuffer { 48 public: 49 // Identifier returned when appending items to this buffer. This id can 50 // later by passed to |Extract| to retrieve the event. 51 struct Id { 52 // The allocation id of the object in the buffer. 53 BumpAllocator::AllocId alloc_id; 54 }; 55 56 // Appends an object of type |T| to the token buffer. Returns an id for 57 // looking up the object later using |Extract|. 58 template <typename T> Append(T object)59 PERFETTO_WARN_UNUSED_RESULT Id Append(T object) { 60 static_assert(sizeof(T) % 8 == 0, "Size must be a multiple of 8"); 61 static_assert(alignof(T) == 8, "Alignment must be 8"); 62 BumpAllocator::AllocId id = AllocAndResizeInternedVectors(sizeof(T)); 63 new (allocator_.GetPointer(id)) T(std::move(object)); 64 return Id{id}; 65 } 66 PERFETTO_WARN_UNUSED_RESULT Id Append(TrackEventData); Append(TracePacketData data)67 PERFETTO_WARN_UNUSED_RESULT Id Append(TracePacketData data) { 68 // While in theory we could add a special case for TracePacketData, the 69 // judgement call we make is that the code complexity does not justify the 70 // micro-performance gain you might hope to see by avoiding the few if 71 // conditions in the |TracePacketData| path. 72 return Append(TrackEventData(std::move(data))); 73 } 74 75 // Gets a pointer an object of type |T| from the token buffer using an id 76 // previously returned by |Append|. This type *must* match the type added 77 // using Append. Mismatching types will caused undefined behaviour. 78 template <typename T> Get(Id id)79 PERFETTO_WARN_UNUSED_RESULT T* Get(Id id) { 80 return static_cast<T*>(allocator_.GetPointer(id.alloc_id)); 81 } 82 83 // Extracts an object of type |T| from the token buffer using an id previously 84 // returned by |Append|. This type *must* match the type added using Append. 85 // Mismatching types will caused undefined behaviour. 86 template <typename T> Extract(Id id)87 PERFETTO_WARN_UNUSED_RESULT T Extract(Id id) { 88 T* typed_ptr = static_cast<T*>(allocator_.GetPointer(id.alloc_id)); 89 T object(std::move(*typed_ptr)); 90 typed_ptr->~T(); 91 allocator_.Free(id.alloc_id); 92 return object; 93 } 94 95 // Returns the "past-the-end" id from the underlying allocator. 96 // The main use of this function is to provide an id which is greater than 97 // all ids previously returned by |Append|. 98 // 99 // This is similar to the |end()| function in standard library vector classes. PastTheEndAllocId()100 BumpAllocator::AllocId PastTheEndAllocId() { 101 return allocator_.PastTheEndId(); 102 } 103 104 // Attempts to free any memory retained by this buffer and the underlying 105 // allocator. The amount of memory free is implementation defined. 106 void FreeMemory(); 107 108 private: 109 struct BlobWithOffset { 110 TraceBlob* blob; 111 size_t offset_in_blob; 112 }; 113 using InternedIndex = size_t; 114 using BlobWithOffsets = std::vector<BlobWithOffset>; 115 using SequenceStates = std::vector<PacketSequenceStateGeneration*>; 116 117 // Functions to intern TraceBlob and PacketSequenceStateGeneration: as these 118 // are often shared between packets, we can significantly reduce memory use 119 // by only storing them once. 120 uint32_t InternTraceBlob(InternedIndex, const TraceBlobView&); 121 uint16_t InternSeqState(InternedIndex, RefPtr<PacketSequenceStateGeneration>); 122 uint32_t AddTraceBlob(InternedIndex, const TraceBlobView&); 123 124 BumpAllocator::AllocId AllocAndResizeInternedVectors(uint32_t size); 125 InternedIndex GetInternedIndex(BumpAllocator::AllocId); 126 127 BumpAllocator allocator_; 128 base::CircularQueue<BlobWithOffsets> interned_blobs_; 129 base::CircularQueue<SequenceStates> interned_seqs_; 130 }; 131 132 // GCC7 does not like us declaring these inside the class so define these 133 // out-of-line. 134 template <> 135 PERFETTO_WARN_UNUSED_RESULT TrackEventData 136 TraceTokenBuffer::Extract<TrackEventData>(Id); 137 template <> 138 PERFETTO_WARN_UNUSED_RESULT inline TracePacketData 139 TraceTokenBuffer::Extract<TracePacketData>(Id id) { 140 // See the comment in Append(TracePacketData) for why we do this. 141 return Extract<TrackEventData>(id).trace_packet_data; 142 } 143 144 } // namespace trace_processor 145 } // namespace perfetto 146 147 #endif // SRC_TRACE_PROCESSOR_SORTER_TRACE_TOKEN_BUFFER_H_ 148