1 #include <linux/list.h>
2 #include <linux/compiler.h>
3 #include <linux/string.h>
4 #include "ordered-events.h"
9 #define pr_N(n, fmt, ...) \
10 eprintf(n, debug_ordered_events, fmt, ##__VA_ARGS__)
12 #define pr(fmt, ...) pr_N(1, pr_fmt(fmt), ##__VA_ARGS__)
14 static void queue_event(struct ordered_events *oe, struct ordered_event *new)
16 struct ordered_event *last = oe->last;
17 u64 timestamp = new->timestamp;
23 pr_oe_time2(timestamp, "queue_event nr_events %u\n", oe->nr_events);
26 list_add(&new->list, &oe->events);
27 oe->max_timestamp = timestamp;
32 * last event might point to some random place in the list as it's
33 * the last queued event. We expect that the new event is close to
36 if (last->timestamp <= timestamp) {
37 while (last->timestamp <= timestamp) {
39 if (p == &oe->events) {
40 list_add_tail(&new->list, &oe->events);
41 oe->max_timestamp = timestamp;
44 last = list_entry(p, struct ordered_event, list);
46 list_add_tail(&new->list, &last->list);
48 while (last->timestamp > timestamp) {
50 if (p == &oe->events) {
51 list_add(&new->list, &oe->events);
54 last = list_entry(p, struct ordered_event, list);
56 list_add(&new->list, &last->list);
60 static union perf_event *__dup_event(struct ordered_events *oe,
61 union perf_event *event)
63 union perf_event *new_event = NULL;
65 if (oe->cur_alloc_size < oe->max_alloc_size) {
66 new_event = memdup(event, event->header.size);
68 oe->cur_alloc_size += event->header.size;
74 static union perf_event *dup_event(struct ordered_events *oe,
75 union perf_event *event)
77 return oe->copy_on_queue ? __dup_event(oe, event) : event;
80 static void free_dup_event(struct ordered_events *oe, union perf_event *event)
82 if (event && oe->copy_on_queue) {
83 oe->cur_alloc_size -= event->header.size;
88 #define MAX_SAMPLE_BUFFER (64 * 1024 / sizeof(struct ordered_event))
89 static struct ordered_event *alloc_event(struct ordered_events *oe,
90 union perf_event *event)
92 struct list_head *cache = &oe->cache;
93 struct ordered_event *new = NULL;
94 union perf_event *new_event;
96 new_event = dup_event(oe, event);
100 if (!list_empty(cache)) {
101 new = list_entry(cache->next, struct ordered_event, list);
102 list_del(&new->list);
103 } else if (oe->buffer) {
104 new = oe->buffer + oe->buffer_idx;
105 if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
107 } else if (oe->cur_alloc_size < oe->max_alloc_size) {
108 size_t size = MAX_SAMPLE_BUFFER * sizeof(*new);
110 oe->buffer = malloc(size);
112 free_dup_event(oe, new_event);
116 pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
117 oe->cur_alloc_size, size, oe->max_alloc_size);
119 oe->cur_alloc_size += size;
120 list_add(&oe->buffer->list, &oe->to_free);
122 /* First entry is abused to maintain the to_free list. */
124 new = oe->buffer + 1;
126 pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
129 new->event = new_event;
133 static struct ordered_event *
134 ordered_events__new_event(struct ordered_events *oe, u64 timestamp,
135 union perf_event *event)
137 struct ordered_event *new;
139 new = alloc_event(oe, event);
141 new->timestamp = timestamp;
142 queue_event(oe, new);
148 void ordered_events__delete(struct ordered_events *oe, struct ordered_event *event)
150 list_move(&event->list, &oe->cache);
152 free_dup_event(oe, event->event);
156 int ordered_events__queue(struct ordered_events *oe, union perf_event *event,
157 struct perf_sample *sample, u64 file_offset)
159 u64 timestamp = sample->time;
160 struct ordered_event *oevent;
162 if (!timestamp || timestamp == ~0ULL)
165 if (timestamp < oe->last_flush) {
166 pr_oe_time(timestamp, "out of order event\n");
167 pr_oe_time(oe->last_flush, "last flush, last_flush_type %d\n",
168 oe->last_flush_type);
170 oe->nr_unordered_events++;
173 oevent = ordered_events__new_event(oe, timestamp, event);
175 ordered_events__flush(oe, OE_FLUSH__HALF);
176 oevent = ordered_events__new_event(oe, timestamp, event);
182 oevent->file_offset = file_offset;
186 static int __ordered_events__flush(struct ordered_events *oe)
188 struct list_head *head = &oe->events;
189 struct ordered_event *tmp, *iter;
190 u64 limit = oe->next_flush;
191 u64 last_ts = oe->last ? oe->last->timestamp : 0ULL;
192 bool show_progress = limit == ULLONG_MAX;
193 struct ui_progress prog;
200 ui_progress__init(&prog, oe->nr_events, "Processing time ordered events...");
202 list_for_each_entry_safe(iter, tmp, head, list) {
206 if (iter->timestamp > limit)
208 ret = oe->deliver(oe, iter);
212 ordered_events__delete(oe, iter);
213 oe->last_flush = iter->timestamp;
216 ui_progress__update(&prog, 1);
219 if (list_empty(head))
221 else if (last_ts <= limit)
222 oe->last = list_entry(head->prev, struct ordered_event, list);
225 ui_progress__finish();
230 int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)
232 static const char * const str[] = {
240 if (oe->nr_events == 0)
244 case OE_FLUSH__FINAL:
245 oe->next_flush = ULLONG_MAX;
250 struct ordered_event *first, *last;
251 struct list_head *head = &oe->events;
253 first = list_entry(head->next, struct ordered_event, list);
256 /* Warn if we are called before any event got allocated. */
257 if (WARN_ONCE(!last || list_empty(head), "empty queue"))
260 oe->next_flush = first->timestamp;
261 oe->next_flush += (last->timestamp - first->timestamp) / 2;
265 case OE_FLUSH__ROUND:
271 pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE %s, nr_events %u\n",
272 str[how], oe->nr_events);
273 pr_oe_time(oe->max_timestamp, "max_timestamp\n");
275 err = __ordered_events__flush(oe);
278 if (how == OE_FLUSH__ROUND)
279 oe->next_flush = oe->max_timestamp;
281 oe->last_flush_type = how;
284 pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n",
285 str[how], oe->nr_events);
286 pr_oe_time(oe->last_flush, "last_flush\n");
291 void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t deliver)
293 INIT_LIST_HEAD(&oe->events);
294 INIT_LIST_HEAD(&oe->cache);
295 INIT_LIST_HEAD(&oe->to_free);
296 oe->max_alloc_size = (u64) -1;
297 oe->cur_alloc_size = 0;
298 oe->deliver = deliver;
301 void ordered_events__free(struct ordered_events *oe)
303 while (!list_empty(&oe->to_free)) {
304 struct ordered_event *event;
306 event = list_entry(oe->to_free.next, struct ordered_event, list);
307 list_del(&event->list);
308 free_dup_event(oe, event->event);