Merge tag 'soc-ep93xx-dt-6.12' of git://git.kernel.org/pub/scm/linux/kernel/git/soc/soc
[linux-2.6-block.git] / tools / perf / util / ordered-events.c
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->list, &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->list, &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->list, &last->list);
51         } else {
52                 while (last->timestamp > timestamp) {
53                         p = last->list.prev;
54                         if (p == &oe->events) {
55                                 list_add(&new->list, &oe->events);
56                                 return;
57                         }
58                         last = list_entry(p, struct ordered_event, list);
59                 }
60                 list_add(&new->list, &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(cache)) {
141                 new = list_entry(cache->next, struct ordered_event, list);
142                 list_del_init(&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, 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(&oe->buffer->list, &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(&event->list, &oe->cache);
189         oe->nr_events--;
190         free_dup_event(oe, 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, 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, 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, 0);
343 }
344
345 int ordered_events__flush_time(struct ordered_events *oe, u64 timestamp)
346 {
347         return __ordered_events__flush(oe, 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(&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(&oe->events);
365         INIT_LIST_HEAD(&oe->cache);
366         INIT_LIST_HEAD(&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, 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(&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(&oe->buffer->list);
400                 ordered_events_buffer__free(oe->buffer, 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(&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, old_deliver, oe->data);
417 }