1
2 /*
3 * Copyright (C) 2024 The Android Open Source Project
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 #include "src/trace_processor/util/trace_blob_view_reader.h"
19
20 #include <algorithm>
21 #include <cstddef>
22 #include <cstdint>
23 #include <cstring>
24 #include <iterator>
25 #include <optional>
26 #include <utility>
27 #include <vector>
28
29 #include "perfetto/base/logging.h"
30 #include "perfetto/public/compiler.h"
31 #include "perfetto/trace_processor/trace_blob.h"
32 #include "perfetto/trace_processor/trace_blob_view.h"
33
34 namespace perfetto::trace_processor::util {
35
PushBack(TraceBlobView data)36 void TraceBlobViewReader::PushBack(TraceBlobView data) {
37 if (data.size() == 0) {
38 return;
39 }
40 const size_t size = data.size();
41 data_.emplace_back(Entry{end_offset_, std::move(data)});
42 end_offset_ += size;
43 }
44
PopFrontUntil(const size_t target_offset)45 bool TraceBlobViewReader::PopFrontUntil(const size_t target_offset) {
46 PERFETTO_CHECK(start_offset() <= target_offset);
47 while (!data_.empty()) {
48 Entry& entry = data_.front();
49 if (target_offset == entry.start_offset) {
50 return true;
51 }
52 const size_t bytes_to_pop = target_offset - entry.start_offset;
53 if (entry.data.size() > bytes_to_pop) {
54 entry.data =
55 entry.data.slice_off(bytes_to_pop, entry.data.size() - bytes_to_pop);
56 entry.start_offset += bytes_to_pop;
57 return true;
58 }
59 data_.pop_front();
60 }
61 return target_offset == end_offset_;
62 }
63
64 template <typename Visitor>
SliceOffImpl(const size_t offset,const size_t length,Visitor & visitor) const65 auto TraceBlobViewReader::SliceOffImpl(const size_t offset,
66 const size_t length,
67 Visitor& visitor) const {
68 // If the length is zero, then a zero-sized blob view is always appropiate.
69 if (PERFETTO_UNLIKELY(length == 0)) {
70 return visitor.OneSlice(TraceBlobView());
71 }
72
73 PERFETTO_DCHECK(offset >= start_offset());
74
75 // Fast path: the slice fits entirely inside the first TBV, we can just slice
76 // that directly without doing any searching. This will happen most of the
77 // time when this class is used so optimize for it.
78 bool is_fast_path =
79 !data_.empty() &&
80 offset + length <= data_.front().start_offset + data_.front().data.size();
81 if (PERFETTO_LIKELY(is_fast_path)) {
82 return visitor.OneSlice(data_.front().data.slice_off(
83 offset - data_.front().start_offset, length));
84 }
85
86 // If we don't have any TBVs or the end of the slice does not fit, then we
87 // cannot possibly return a full slice.
88 if (PERFETTO_UNLIKELY(data_.empty() || offset + length > end_offset_)) {
89 return visitor.NoData();
90 }
91
92 // Find the first block finishes *after* start_offset i.e. there is at least
93 // one byte in that block which will end up in the slice. We know this *must*
94 // exist because of the above check.
95 auto it = std::upper_bound(
96 data_.begin(), data_.end(), offset, [](size_t offset, const Entry& rhs) {
97 return offset < rhs.start_offset + rhs.data.size();
98 });
99 PERFETTO_CHECK(it != data_.end());
100
101 // If the slice fits entirely in the block we found, then just slice that
102 // block avoiding any copies.
103 size_t rel_off = offset - it->start_offset;
104 if (rel_off + length <= it->data.size()) {
105 return visitor.OneSlice(it->data.slice_off(rel_off, length));
106 }
107
108 auto res = visitor.StartMultiSlice(length);
109
110 size_t res_offset = 0;
111 size_t left = length;
112
113 size_t size = it->data.length() - rel_off;
114 visitor.AddSlice(res, res_offset, it->data.slice_off(rel_off, size));
115 left -= size;
116 res_offset += size;
117
118 for (++it; left != 0; ++it) {
119 size = std::min(left, it->data.size());
120 visitor.AddSlice(res, res_offset, it->data.slice_off(0, size));
121 left -= size;
122 res_offset += size;
123 }
124
125 return visitor.Finalize(std::move(res));
126 }
127
SliceOff(size_t offset,size_t length) const128 std::optional<TraceBlobView> TraceBlobViewReader::SliceOff(
129 size_t offset,
130 size_t length) const {
131 struct Visitor {
132 std::optional<TraceBlobView> NoData() { return std::nullopt; }
133
134 std::optional<TraceBlobView> OneSlice(TraceBlobView tbv) {
135 return std::move(tbv);
136 }
137
138 TraceBlob StartMultiSlice(size_t length) {
139 return TraceBlob::Allocate(length);
140 }
141
142 void AddSlice(TraceBlob& blob, size_t offset, TraceBlobView tbv) {
143 memcpy(blob.data() + offset, tbv.data(), tbv.size());
144 }
145
146 std::optional<TraceBlobView> Finalize(TraceBlob blob) {
147 return TraceBlobView(std::move(blob));
148 }
149
150 } visitor;
151
152 return SliceOffImpl(offset, length, visitor);
153 }
154
MultiSliceOff(size_t offset,size_t length) const155 std::vector<TraceBlobView> TraceBlobViewReader::MultiSliceOff(
156 size_t offset,
157 size_t length) const {
158 struct Visitor {
159 std::vector<TraceBlobView> NoData() { return {}; }
160
161 std::vector<TraceBlobView> OneSlice(TraceBlobView tbv) {
162 std::vector<TraceBlobView> res;
163 res.reserve(1);
164 res.push_back(std::move(tbv));
165 return res;
166 }
167
168 std::vector<TraceBlobView> StartMultiSlice(size_t) { return {}; }
169
170 void AddSlice(std::vector<TraceBlobView>& vec, size_t, TraceBlobView tbv) {
171 vec.push_back(std::move(tbv));
172 }
173
174 std::vector<TraceBlobView> Finalize(std::vector<TraceBlobView> vec) {
175 return vec;
176 }
177
178 } visitor;
179
180 return SliceOffImpl(offset, length, visitor);
181 }
182
183 } // namespace perfetto::trace_processor::util
184