1 // SPDX-License-Identifier: GPL-2.0
4 #include <linux/list.h>
5 #include <linux/compiler.h>
6 #include <linux/string.h>
7 #include "ordered-events.h"
12 #define pr_N(n, fmt, ...) \
13 eprintf(n, debug_ordered_events, fmt, ##__VA_ARGS__)
15 #define pr(fmt, ...) pr_N(1, pr_fmt(fmt), ##__VA_ARGS__)
17 static void queue_event(struct ordered_events *oe, struct ordered_event *new)
19 struct ordered_event *last = oe->last;
20 u64 timestamp = new->timestamp;
26 pr_oe_time2(timestamp, "queue_event nr_events %u\n", oe->nr_events);
29 list_add(&new->list, &oe->events);
30 oe->max_timestamp = timestamp;
35 * last event might point to some random place in the list as it's
36 * the last queued event. We expect that the new event is close to
39 if (last->timestamp <= timestamp) {
40 while (last->timestamp <= timestamp) {
42 if (p == &oe->events) {
43 list_add_tail(&new->list, &oe->events);
44 oe->max_timestamp = timestamp;
47 last = list_entry(p, struct ordered_event, list);
49 list_add_tail(&new->list, &last->list);
51 while (last->timestamp > timestamp) {
53 if (p == &oe->events) {
54 list_add(&new->list, &oe->events);
57 last = list_entry(p, struct ordered_event, list);
59 list_add(&new->list, &last->list);
63 static union perf_event *__dup_event(struct ordered_events *oe,
64 union perf_event *event)
66 union perf_event *new_event = NULL;
68 if (oe->cur_alloc_size < oe->max_alloc_size) {
69 new_event = memdup(event, event->header.size);
71 oe->cur_alloc_size += event->header.size;
77 static union perf_event *dup_event(struct ordered_events *oe,
78 union perf_event *event)
80 return oe->copy_on_queue ? __dup_event(oe, event) : event;
83 static void free_dup_event(struct ordered_events *oe, union perf_event *event)
85 if (event && oe->copy_on_queue) {
86 oe->cur_alloc_size -= event->header.size;
91 #define MAX_SAMPLE_BUFFER (64 * 1024 / sizeof(struct ordered_event))
92 static struct ordered_event *alloc_event(struct ordered_events *oe,
93 union perf_event *event)
95 struct list_head *cache = &oe->cache;
96 struct ordered_event *new = NULL;
97 union perf_event *new_event;
99 new_event = dup_event(oe, event);
103 if (!list_empty(cache)) {
104 new = list_entry(cache->next, struct ordered_event, list);
105 list_del(&new->list);
106 } else if (oe->buffer) {
107 new = oe->buffer + oe->buffer_idx;
108 if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
110 } else if (oe->cur_alloc_size < oe->max_alloc_size) {
111 size_t size = MAX_SAMPLE_BUFFER * sizeof(*new);
113 oe->buffer = malloc(size);
115 free_dup_event(oe, new_event);
119 pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
120 oe->cur_alloc_size, size, oe->max_alloc_size);
122 oe->cur_alloc_size += size;
123 list_add(&oe->buffer->list, &oe->to_free);
125 /* First entry is abused to maintain the to_free list. */
127 new = oe->buffer + 1;
129 pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
132 new->event = new_event;
136 static struct ordered_event *
137 ordered_events__new_event(struct ordered_events *oe, u64 timestamp,
138 union perf_event *event)
140 struct ordered_event *new;
142 new = alloc_event(oe, event);
144 new->timestamp = timestamp;
145 queue_event(oe, new);
151 void ordered_events__delete(struct ordered_events *oe, struct ordered_event *event)
153 list_move(&event->list, &oe->cache);
155 free_dup_event(oe, event->event);
159 int ordered_events__queue(struct ordered_events *oe, union perf_event *event,
160 u64 timestamp, u64 file_offset)
162 struct ordered_event *oevent;
164 if (!timestamp || timestamp == ~0ULL)
167 if (timestamp < oe->last_flush) {
168 pr_oe_time(timestamp, "out of order event\n");
169 pr_oe_time(oe->last_flush, "last flush, last_flush_type %d\n",
170 oe->last_flush_type);
172 oe->nr_unordered_events++;
175 oevent = ordered_events__new_event(oe, timestamp, event);
177 ordered_events__flush(oe, OE_FLUSH__HALF);
178 oevent = ordered_events__new_event(oe, timestamp, event);
184 oevent->file_offset = file_offset;
188 static int __ordered_events__flush(struct ordered_events *oe)
190 struct list_head *head = &oe->events;
191 struct ordered_event *tmp, *iter;
192 u64 limit = oe->next_flush;
193 u64 last_ts = oe->last ? oe->last->timestamp : 0ULL;
194 bool show_progress = limit == ULLONG_MAX;
195 struct ui_progress prog;
202 ui_progress__init(&prog, oe->nr_events, "Processing time ordered events...");
204 list_for_each_entry_safe(iter, tmp, head, list) {
208 if (iter->timestamp > limit)
210 ret = oe->deliver(oe, iter);
214 ordered_events__delete(oe, iter);
215 oe->last_flush = iter->timestamp;
218 ui_progress__update(&prog, 1);
221 if (list_empty(head))
223 else if (last_ts <= limit)
224 oe->last = list_entry(head->prev, struct ordered_event, list);
227 ui_progress__finish();
232 int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)
234 static const char * const str[] = {
242 if (oe->nr_events == 0)
246 case OE_FLUSH__FINAL:
247 oe->next_flush = ULLONG_MAX;
252 struct ordered_event *first, *last;
253 struct list_head *head = &oe->events;
255 first = list_entry(head->next, struct ordered_event, list);
258 /* Warn if we are called before any event got allocated. */
259 if (WARN_ONCE(!last || list_empty(head), "empty queue"))
262 oe->next_flush = first->timestamp;
263 oe->next_flush += (last->timestamp - first->timestamp) / 2;
267 case OE_FLUSH__ROUND:
273 pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE %s, nr_events %u\n",
274 str[how], oe->nr_events);
275 pr_oe_time(oe->max_timestamp, "max_timestamp\n");
277 err = __ordered_events__flush(oe);
280 if (how == OE_FLUSH__ROUND)
281 oe->next_flush = oe->max_timestamp;
283 oe->last_flush_type = how;
286 pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n",
287 str[how], oe->nr_events);
288 pr_oe_time(oe->last_flush, "last_flush\n");
293 void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t deliver)
295 INIT_LIST_HEAD(&oe->events);
296 INIT_LIST_HEAD(&oe->cache);
297 INIT_LIST_HEAD(&oe->to_free);
298 oe->max_alloc_size = (u64) -1;
299 oe->cur_alloc_size = 0;
300 oe->deliver = deliver;
303 void ordered_events__free(struct ordered_events *oe)
305 while (!list_empty(&oe->to_free)) {
306 struct ordered_event *event;
308 event = list_entry(oe->to_free.next, struct ordered_event, list);
309 list_del(&event->list);
310 free_dup_event(oe, event->event);
315 void ordered_events__reinit(struct ordered_events *oe)
317 ordered_events__deliver_t old_deliver = oe->deliver;
319 ordered_events__free(oe);
320 memset(oe, '\0', sizeof(*oe));
321 ordered_events__init(oe, old_deliver);