3 #include <linux/list.h>
4 #include <linux/compiler.h>
5 #include <linux/string.h>
6 #include "ordered-events.h"
11 #define pr_N(n, fmt, ...) \
12 eprintf(n, debug_ordered_events, fmt, ##__VA_ARGS__)
14 #define pr(fmt, ...) pr_N(1, pr_fmt(fmt), ##__VA_ARGS__)
16 static void queue_event(struct ordered_events *oe, struct ordered_event *new)
18 struct ordered_event *last = oe->last;
19 u64 timestamp = new->timestamp;
25 pr_oe_time2(timestamp, "queue_event nr_events %u\n", oe->nr_events);
28 list_add(&new->list, &oe->events);
29 oe->max_timestamp = timestamp;
34 * last event might point to some random place in the list as it's
35 * the last queued event. We expect that the new event is close to
38 if (last->timestamp <= timestamp) {
39 while (last->timestamp <= timestamp) {
41 if (p == &oe->events) {
42 list_add_tail(&new->list, &oe->events);
43 oe->max_timestamp = timestamp;
46 last = list_entry(p, struct ordered_event, list);
48 list_add_tail(&new->list, &last->list);
50 while (last->timestamp > timestamp) {
52 if (p == &oe->events) {
53 list_add(&new->list, &oe->events);
56 last = list_entry(p, struct ordered_event, list);
58 list_add(&new->list, &last->list);
62 static union perf_event *__dup_event(struct ordered_events *oe,
63 union perf_event *event)
65 union perf_event *new_event = NULL;
67 if (oe->cur_alloc_size < oe->max_alloc_size) {
68 new_event = memdup(event, event->header.size);
70 oe->cur_alloc_size += event->header.size;
76 static union perf_event *dup_event(struct ordered_events *oe,
77 union perf_event *event)
79 return oe->copy_on_queue ? __dup_event(oe, event) : event;
82 static void free_dup_event(struct ordered_events *oe, union perf_event *event)
84 if (event && oe->copy_on_queue) {
85 oe->cur_alloc_size -= event->header.size;
90 #define MAX_SAMPLE_BUFFER (64 * 1024 / sizeof(struct ordered_event))
91 static struct ordered_event *alloc_event(struct ordered_events *oe,
92 union perf_event *event)
94 struct list_head *cache = &oe->cache;
95 struct ordered_event *new = NULL;
96 union perf_event *new_event;
98 new_event = dup_event(oe, event);
102 if (!list_empty(cache)) {
103 new = list_entry(cache->next, struct ordered_event, list);
104 list_del(&new->list);
105 } else if (oe->buffer) {
106 new = oe->buffer + oe->buffer_idx;
107 if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
109 } else if (oe->cur_alloc_size < oe->max_alloc_size) {
110 size_t size = MAX_SAMPLE_BUFFER * sizeof(*new);
112 oe->buffer = malloc(size);
114 free_dup_event(oe, new_event);
118 pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
119 oe->cur_alloc_size, size, oe->max_alloc_size);
121 oe->cur_alloc_size += size;
122 list_add(&oe->buffer->list, &oe->to_free);
124 /* First entry is abused to maintain the to_free list. */
126 new = oe->buffer + 1;
128 pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
131 new->event = new_event;
135 static struct ordered_event *
136 ordered_events__new_event(struct ordered_events *oe, u64 timestamp,
137 union perf_event *event)
139 struct ordered_event *new;
141 new = alloc_event(oe, event);
143 new->timestamp = timestamp;
144 queue_event(oe, new);
150 void ordered_events__delete(struct ordered_events *oe, struct ordered_event *event)
152 list_move(&event->list, &oe->cache);
154 free_dup_event(oe, event->event);
158 int ordered_events__queue(struct ordered_events *oe, union perf_event *event,
159 struct perf_sample *sample, u64 file_offset)
161 u64 timestamp = sample->time;
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);