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 <cstring>
23 #include <optional>
24 #include <utility>
25 #include <vector>
26
27 #include "perfetto/base/logging.h"
28 #include "perfetto/public/compiler.h"
29 #include "perfetto/trace_processor/trace_blob.h"
30 #include "perfetto/trace_processor/trace_blob_view.h"
31
32 namespace perfetto::trace_processor::util {
33
PushBack(TraceBlobView data)34 void TraceBlobViewReader::PushBack(TraceBlobView data) {
35 if (data.size() == 0) {
36 return;
37 }
38 const size_t size = data.size();
39 data_.emplace_back(Entry{end_offset_, std::move(data)});
40 end_offset_ += size;
41 }
42
PopFrontUntil(const size_t target_offset)43 bool TraceBlobViewReader::PopFrontUntil(const size_t target_offset) {
44 PERFETTO_CHECK(start_offset() <= target_offset);
45 while (!data_.empty()) {
46 Entry& entry = data_.front();
47 if (target_offset == entry.start_offset) {
48 return true;
49 }
50 const size_t bytes_to_pop = target_offset - entry.start_offset;
51 if (entry.data.size() > bytes_to_pop) {
52 entry.data =
53 entry.data.slice_off(bytes_to_pop, entry.data.size() - bytes_to_pop);
54 entry.start_offset += bytes_to_pop;
55 return true;
56 }
57 data_.pop_front();
58 }
59 return target_offset == end_offset_;
60 }
61
62 template <typename Visitor>
SliceOffImpl(const size_t offset,const size_t length,Visitor & visitor) const63 auto TraceBlobViewReader::SliceOffImpl(const size_t offset,
64 const size_t length,
65 Visitor& visitor) const {
66 // If the length is zero, then a zero-sized blob view is always appropiate.
67 if (PERFETTO_UNLIKELY(length == 0)) {
68 return visitor.OneSlice(TraceBlobView());
69 }
70
71 PERFETTO_DCHECK(offset >= start_offset());
72
73 // Fast path: the slice fits entirely inside the first TBV, we can just slice
74 // that directly without doing any searching. This will happen most of the
75 // time when this class is used so optimize for it.
76 bool is_fast_path =
77 !data_.empty() &&
78 offset + length <= data_.front().start_offset + data_.front().data.size();
79 if (PERFETTO_LIKELY(is_fast_path)) {
80 return visitor.OneSlice(data_.front().data.slice_off(
81 offset - data_.front().start_offset, length));
82 }
83
84 // If we don't have any TBVs or the end of the slice does not fit, then we
85 // cannot possibly return a full slice.
86 if (PERFETTO_UNLIKELY(data_.empty() || offset + length > end_offset_)) {
87 return visitor.NoData();
88 }
89
90 // Find the first block finishes *after* start_offset i.e. there is at least
91 // one byte in that block which will end up in the slice. We know this *must*
92 // exist because of the above check.
93 auto it = std::upper_bound(
94 data_.begin(), data_.end(), offset, [](size_t offset, const Entry& rhs) {
95 return offset < rhs.start_offset + rhs.data.size();
96 });
97 PERFETTO_CHECK(it != data_.end());
98
99 // If the slice fits entirely in the block we found, then just slice that
100 // block avoiding any copies.
101 size_t rel_off = offset - it->start_offset;
102 if (rel_off + length <= it->data.size()) {
103 return visitor.OneSlice(it->data.slice_off(rel_off, length));
104 }
105
106 auto res = visitor.StartMultiSlice(length);
107
108 size_t res_offset = 0;
109 size_t left = length;
110
111 size_t size = it->data.length() - rel_off;
112 visitor.AddSlice(res, res_offset, it->data.slice_off(rel_off, size));
113 left -= size;
114 res_offset += size;
115
116 for (++it; left != 0; ++it) {
117 size = std::min(left, it->data.size());
118 visitor.AddSlice(res, res_offset, it->data.slice_off(0, size));
119 left -= size;
120 res_offset += size;
121 }
122
123 return visitor.Finalize(std::move(res));
124 }
125
SliceOff(size_t offset,size_t length) const126 std::optional<TraceBlobView> TraceBlobViewReader::SliceOff(
127 size_t offset,
128 size_t length) const {
129 struct Visitor {
130 static std::optional<TraceBlobView> NoData() { return std::nullopt; }
131
132 static std::optional<TraceBlobView> OneSlice(TraceBlobView tbv) {
133 return std::move(tbv);
134 }
135
136 static TraceBlob StartMultiSlice(size_t length) {
137 return TraceBlob::Allocate(length);
138 }
139
140 static void AddSlice(TraceBlob& blob, size_t offset, TraceBlobView tbv) {
141 memcpy(blob.data() + offset, tbv.data(), tbv.size());
142 }
143
144 static std::optional<TraceBlobView> Finalize(TraceBlob blob) {
145 return TraceBlobView(std::move(blob));
146 }
147
148 } visitor;
149
150 return SliceOffImpl(offset, length, visitor);
151 }
152
MultiSliceOff(size_t offset,size_t length) const153 std::vector<TraceBlobView> TraceBlobViewReader::MultiSliceOff(
154 size_t offset,
155 size_t length) const {
156 struct Visitor {
157 static std::vector<TraceBlobView> NoData() { return {}; }
158
159 static std::vector<TraceBlobView> OneSlice(TraceBlobView tbv) {
160 std::vector<TraceBlobView> res;
161 res.reserve(1);
162 res.push_back(std::move(tbv));
163 return res;
164 }
165
166 static std::vector<TraceBlobView> StartMultiSlice(size_t) { return {}; }
167
168 static void AddSlice(std::vector<TraceBlobView>& vec,
169 size_t,
170 TraceBlobView tbv) {
171 vec.push_back(std::move(tbv));
172 }
173
174 static 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