1 | // SPDX-License-Identifier: GPL-2.0 |
2 | #include <errno.h> |
3 | #include <inttypes.h> |
4 | #include <linux/list.h> |
5 | #include <linux/compiler.h> |
6 | #include <linux/string.h> |
7 | #include "ordered-events.h" |
8 | #include "session.h" |
9 | #include "asm/bug.h" |
10 | #include "debug.h" |
11 | #include "ui/progress.h" |
12 | |
13 | #define pr_N(n, fmt, ...) \ |
14 | eprintf(n, debug_ordered_events, fmt, ##__VA_ARGS__) |
15 | |
16 | #define pr(fmt, ...) pr_N(1, pr_fmt(fmt), ##__VA_ARGS__) |
17 | |
18 | static void queue_event(struct ordered_events *oe, struct ordered_event *new) |
19 | { |
20 | struct ordered_event *last = oe->last; |
21 | u64 timestamp = new->timestamp; |
22 | struct list_head *p; |
23 | |
24 | ++oe->nr_events; |
25 | oe->last = new; |
26 | |
27 | pr_oe_time2(timestamp, "queue_event nr_events %u\n" , oe->nr_events); |
28 | |
29 | if (!last) { |
30 | list_add(new: &new->list, head: &oe->events); |
31 | oe->max_timestamp = timestamp; |
32 | return; |
33 | } |
34 | |
35 | /* |
36 | * last event might point to some random place in the list as it's |
37 | * the last queued event. We expect that the new event is close to |
38 | * this. |
39 | */ |
40 | if (last->timestamp <= timestamp) { |
41 | while (last->timestamp <= timestamp) { |
42 | p = last->list.next; |
43 | if (p == &oe->events) { |
44 | list_add_tail(new: &new->list, head: &oe->events); |
45 | oe->max_timestamp = timestamp; |
46 | return; |
47 | } |
48 | last = list_entry(p, struct ordered_event, list); |
49 | } |
50 | list_add_tail(new: &new->list, head: &last->list); |
51 | } else { |
52 | while (last->timestamp > timestamp) { |
53 | p = last->list.prev; |
54 | if (p == &oe->events) { |
55 | list_add(new: &new->list, head: &oe->events); |
56 | return; |
57 | } |
58 | last = list_entry(p, struct ordered_event, list); |
59 | } |
60 | list_add(new: &new->list, head: &last->list); |
61 | } |
62 | } |
63 | |
64 | static union perf_event *__dup_event(struct ordered_events *oe, |
65 | union perf_event *event) |
66 | { |
67 | union perf_event *new_event = NULL; |
68 | |
69 | if (oe->cur_alloc_size < oe->max_alloc_size) { |
70 | new_event = memdup(event, event->header.size); |
71 | if (new_event) |
72 | oe->cur_alloc_size += event->header.size; |
73 | } |
74 | |
75 | return new_event; |
76 | } |
77 | |
78 | static union perf_event *dup_event(struct ordered_events *oe, |
79 | union perf_event *event) |
80 | { |
81 | return oe->copy_on_queue ? __dup_event(oe, event) : event; |
82 | } |
83 | |
84 | static void __free_dup_event(struct ordered_events *oe, union perf_event *event) |
85 | { |
86 | if (event) { |
87 | oe->cur_alloc_size -= event->header.size; |
88 | free(event); |
89 | } |
90 | } |
91 | |
92 | static void free_dup_event(struct ordered_events *oe, union perf_event *event) |
93 | { |
94 | if (oe->copy_on_queue) |
95 | __free_dup_event(oe, event); |
96 | } |
97 | |
98 | #define MAX_SAMPLE_BUFFER (64 * 1024 / sizeof(struct ordered_event)) |
99 | static struct ordered_event *alloc_event(struct ordered_events *oe, |
100 | union perf_event *event) |
101 | { |
102 | struct list_head *cache = &oe->cache; |
103 | struct ordered_event *new = NULL; |
104 | union perf_event *new_event; |
105 | size_t size; |
106 | |
107 | new_event = dup_event(oe, event); |
108 | if (!new_event) |
109 | return NULL; |
110 | |
111 | /* |
112 | * We maintain the following scheme of buffers for ordered |
113 | * event allocation: |
114 | * |
115 | * to_free list -> buffer1 (64K) |
116 | * buffer2 (64K) |
117 | * ... |
118 | * |
119 | * Each buffer keeps an array of ordered events objects: |
120 | * buffer -> event[0] |
121 | * event[1] |
122 | * ... |
123 | * |
124 | * Each allocated ordered event is linked to one of |
125 | * following lists: |
126 | * - time ordered list 'events' |
127 | * - list of currently removed events 'cache' |
128 | * |
129 | * Allocation of the ordered event uses the following order |
130 | * to get the memory: |
131 | * - use recently removed object from 'cache' list |
132 | * - use available object in current allocation buffer |
133 | * - allocate new buffer if the current buffer is full |
134 | * |
135 | * Removal of ordered event object moves it from events to |
136 | * the cache list. |
137 | */ |
138 | size = sizeof(*oe->buffer) + MAX_SAMPLE_BUFFER * sizeof(*new); |
139 | |
140 | if (!list_empty(head: cache)) { |
141 | new = list_entry(cache->next, struct ordered_event, list); |
142 | list_del_init(entry: &new->list); |
143 | } else if (oe->buffer) { |
144 | new = &oe->buffer->event[oe->buffer_idx]; |
145 | if (++oe->buffer_idx == MAX_SAMPLE_BUFFER) |
146 | oe->buffer = NULL; |
147 | } else if ((oe->cur_alloc_size + size) < oe->max_alloc_size) { |
148 | oe->buffer = malloc(size); |
149 | if (!oe->buffer) { |
150 | free_dup_event(oe, event: new_event); |
151 | return NULL; |
152 | } |
153 | |
154 | pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n" , |
155 | oe->cur_alloc_size, size, oe->max_alloc_size); |
156 | |
157 | oe->cur_alloc_size += size; |
158 | list_add(new: &oe->buffer->list, head: &oe->to_free); |
159 | |
160 | oe->buffer_idx = 1; |
161 | new = &oe->buffer->event[0]; |
162 | } else { |
163 | pr("allocation limit reached %" PRIu64 "B\n" , oe->max_alloc_size); |
164 | return NULL; |
165 | } |
166 | |
167 | new->event = new_event; |
168 | return new; |
169 | } |
170 | |
171 | static struct ordered_event * |
172 | ordered_events__new_event(struct ordered_events *oe, u64 timestamp, |
173 | union perf_event *event) |
174 | { |
175 | struct ordered_event *new; |
176 | |
177 | new = alloc_event(oe, event); |
178 | if (new) { |
179 | new->timestamp = timestamp; |
180 | queue_event(oe, new); |
181 | } |
182 | |
183 | return new; |
184 | } |
185 | |
186 | void ordered_events__delete(struct ordered_events *oe, struct ordered_event *event) |
187 | { |
188 | list_move(list: &event->list, head: &oe->cache); |
189 | oe->nr_events--; |
190 | free_dup_event(oe, event: event->event); |
191 | event->event = NULL; |
192 | } |
193 | |
194 | int ordered_events__queue(struct ordered_events *oe, union perf_event *event, |
195 | u64 timestamp, u64 file_offset, const char *file_path) |
196 | { |
197 | struct ordered_event *oevent; |
198 | |
199 | if (!timestamp || timestamp == ~0ULL) |
200 | return -ETIME; |
201 | |
202 | if (timestamp < oe->last_flush) { |
203 | pr_oe_time(timestamp, "out of order event\n" ); |
204 | pr_oe_time(oe->last_flush, "last flush, last_flush_type %d\n" , |
205 | oe->last_flush_type); |
206 | |
207 | oe->nr_unordered_events++; |
208 | } |
209 | |
210 | oevent = ordered_events__new_event(oe, timestamp, event); |
211 | if (!oevent) { |
212 | ordered_events__flush(oe, how: OE_FLUSH__HALF); |
213 | oevent = ordered_events__new_event(oe, timestamp, event); |
214 | } |
215 | |
216 | if (!oevent) |
217 | return -ENOMEM; |
218 | |
219 | oevent->file_offset = file_offset; |
220 | oevent->file_path = file_path; |
221 | return 0; |
222 | } |
223 | |
224 | static int do_flush(struct ordered_events *oe, bool show_progress) |
225 | { |
226 | struct list_head *head = &oe->events; |
227 | struct ordered_event *tmp, *iter; |
228 | u64 limit = oe->next_flush; |
229 | u64 last_ts = oe->last ? oe->last->timestamp : 0ULL; |
230 | struct ui_progress prog; |
231 | int ret; |
232 | |
233 | if (!limit) |
234 | return 0; |
235 | |
236 | if (show_progress) |
237 | ui_progress__init(&prog, oe->nr_events, "Processing time ordered events..." ); |
238 | |
239 | list_for_each_entry_safe(iter, tmp, head, list) { |
240 | if (session_done()) |
241 | return 0; |
242 | |
243 | if (iter->timestamp > limit) |
244 | break; |
245 | ret = oe->deliver(oe, iter); |
246 | if (ret) |
247 | return ret; |
248 | |
249 | ordered_events__delete(oe, event: iter); |
250 | oe->last_flush = iter->timestamp; |
251 | |
252 | if (show_progress) |
253 | ui_progress__update(&prog, 1); |
254 | } |
255 | |
256 | if (list_empty(head)) |
257 | oe->last = NULL; |
258 | else if (last_ts <= limit) |
259 | oe->last = list_entry(head->prev, struct ordered_event, list); |
260 | |
261 | if (show_progress) |
262 | ui_progress__finish(); |
263 | |
264 | return 0; |
265 | } |
266 | |
267 | static int __ordered_events__flush(struct ordered_events *oe, enum oe_flush how, |
268 | u64 timestamp) |
269 | { |
270 | static const char * const str[] = { |
271 | "NONE" , |
272 | "FINAL" , |
273 | "ROUND" , |
274 | "HALF " , |
275 | "TOP " , |
276 | "TIME " , |
277 | }; |
278 | int err; |
279 | bool show_progress = false; |
280 | |
281 | if (oe->nr_events == 0) |
282 | return 0; |
283 | |
284 | switch (how) { |
285 | case OE_FLUSH__FINAL: |
286 | show_progress = true; |
287 | fallthrough; |
288 | case OE_FLUSH__TOP: |
289 | oe->next_flush = ULLONG_MAX; |
290 | break; |
291 | |
292 | case OE_FLUSH__HALF: |
293 | { |
294 | struct ordered_event *first, *last; |
295 | struct list_head *head = &oe->events; |
296 | |
297 | first = list_entry(head->next, struct ordered_event, list); |
298 | last = oe->last; |
299 | |
300 | /* Warn if we are called before any event got allocated. */ |
301 | if (WARN_ONCE(!last || list_empty(head), "empty queue" )) |
302 | return 0; |
303 | |
304 | oe->next_flush = first->timestamp; |
305 | oe->next_flush += (last->timestamp - first->timestamp) / 2; |
306 | break; |
307 | } |
308 | |
309 | case OE_FLUSH__TIME: |
310 | oe->next_flush = timestamp; |
311 | show_progress = false; |
312 | break; |
313 | |
314 | case OE_FLUSH__ROUND: |
315 | case OE_FLUSH__NONE: |
316 | default: |
317 | break; |
318 | } |
319 | |
320 | pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE %s, nr_events %u\n" , |
321 | str[how], oe->nr_events); |
322 | pr_oe_time(oe->max_timestamp, "max_timestamp\n" ); |
323 | |
324 | err = do_flush(oe, show_progress); |
325 | |
326 | if (!err) { |
327 | if (how == OE_FLUSH__ROUND) |
328 | oe->next_flush = oe->max_timestamp; |
329 | |
330 | oe->last_flush_type = how; |
331 | } |
332 | |
333 | pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n" , |
334 | str[how], oe->nr_events); |
335 | pr_oe_time(oe->last_flush, "last_flush\n" ); |
336 | |
337 | return err; |
338 | } |
339 | |
340 | int ordered_events__flush(struct ordered_events *oe, enum oe_flush how) |
341 | { |
342 | return __ordered_events__flush(oe, how, timestamp: 0); |
343 | } |
344 | |
345 | int ordered_events__flush_time(struct ordered_events *oe, u64 timestamp) |
346 | { |
347 | return __ordered_events__flush(oe, how: OE_FLUSH__TIME, timestamp); |
348 | } |
349 | |
350 | u64 ordered_events__first_time(struct ordered_events *oe) |
351 | { |
352 | struct ordered_event *event; |
353 | |
354 | if (list_empty(head: &oe->events)) |
355 | return 0; |
356 | |
357 | event = list_first_entry(&oe->events, struct ordered_event, list); |
358 | return event->timestamp; |
359 | } |
360 | |
361 | void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t deliver, |
362 | void *data) |
363 | { |
364 | INIT_LIST_HEAD(list: &oe->events); |
365 | INIT_LIST_HEAD(list: &oe->cache); |
366 | INIT_LIST_HEAD(list: &oe->to_free); |
367 | oe->max_alloc_size = (u64) -1; |
368 | oe->cur_alloc_size = 0; |
369 | oe->deliver = deliver; |
370 | oe->data = data; |
371 | } |
372 | |
373 | static void |
374 | ordered_events_buffer__free(struct ordered_events_buffer *buffer, |
375 | unsigned int max, struct ordered_events *oe) |
376 | { |
377 | if (oe->copy_on_queue) { |
378 | unsigned int i; |
379 | |
380 | for (i = 0; i < max; i++) |
381 | __free_dup_event(oe, event: buffer->event[i].event); |
382 | } |
383 | |
384 | free(buffer); |
385 | } |
386 | |
387 | void ordered_events__free(struct ordered_events *oe) |
388 | { |
389 | struct ordered_events_buffer *buffer, *tmp; |
390 | |
391 | if (list_empty(head: &oe->to_free)) |
392 | return; |
393 | |
394 | /* |
395 | * Current buffer might not have all the events allocated |
396 | * yet, we need to free only allocated ones ... |
397 | */ |
398 | if (oe->buffer) { |
399 | list_del_init(entry: &oe->buffer->list); |
400 | ordered_events_buffer__free(buffer: oe->buffer, max: oe->buffer_idx, oe); |
401 | } |
402 | |
403 | /* ... and continue with the rest */ |
404 | list_for_each_entry_safe(buffer, tmp, &oe->to_free, list) { |
405 | list_del_init(entry: &buffer->list); |
406 | ordered_events_buffer__free(buffer, MAX_SAMPLE_BUFFER, oe); |
407 | } |
408 | } |
409 | |
410 | void ordered_events__reinit(struct ordered_events *oe) |
411 | { |
412 | ordered_events__deliver_t old_deliver = oe->deliver; |
413 | |
414 | ordered_events__free(oe); |
415 | memset(oe, '\0', sizeof(*oe)); |
416 | ordered_events__init(oe, deliver: old_deliver, data: oe->data); |
417 | } |
418 | |