1 #include <linux/list.h>
2 #include <linux/compiler.h>
3 #include <linux/string.h>
4 #include "ordered-events.h"
5 #include "session.h"
6 #include "asm/bug.h"
7 #include "debug.h"
8
9 #define pr_N(n, fmt, ...) \
10 eprintf(n, debug_ordered_events, fmt, ##__VA_ARGS__)
11
12 #define pr(fmt, ...) pr_N(1, pr_fmt(fmt), ##__VA_ARGS__)
13
queue_event(struct ordered_events * oe,struct ordered_event * new)14 static void queue_event(struct ordered_events *oe, struct ordered_event *new)
15 {
16 struct ordered_event *last = oe->last;
17 u64 timestamp = new->timestamp;
18 struct list_head *p;
19
20 ++oe->nr_events;
21 oe->last = new;
22
23 pr_oe_time2(timestamp, "queue_event nr_events %u\n", oe->nr_events);
24
25 if (!last) {
26 list_add(&new->list, &oe->events);
27 oe->max_timestamp = timestamp;
28 return;
29 }
30
31 /*
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
34 * this.
35 */
36 if (last->timestamp <= timestamp) {
37 while (last->timestamp <= timestamp) {
38 p = last->list.next;
39 if (p == &oe->events) {
40 list_add_tail(&new->list, &oe->events);
41 oe->max_timestamp = timestamp;
42 return;
43 }
44 last = list_entry(p, struct ordered_event, list);
45 }
46 list_add_tail(&new->list, &last->list);
47 } else {
48 while (last->timestamp > timestamp) {
49 p = last->list.prev;
50 if (p == &oe->events) {
51 list_add(&new->list, &oe->events);
52 return;
53 }
54 last = list_entry(p, struct ordered_event, list);
55 }
56 list_add(&new->list, &last->list);
57 }
58 }
59
__dup_event(struct ordered_events * oe,union perf_event * event)60 static union perf_event *__dup_event(struct ordered_events *oe,
61 union perf_event *event)
62 {
63 union perf_event *new_event = NULL;
64
65 if (oe->cur_alloc_size < oe->max_alloc_size) {
66 new_event = memdup(event, event->header.size);
67 if (new_event)
68 oe->cur_alloc_size += event->header.size;
69 }
70
71 return new_event;
72 }
73
dup_event(struct ordered_events * oe,union perf_event * event)74 static union perf_event *dup_event(struct ordered_events *oe,
75 union perf_event *event)
76 {
77 return oe->copy_on_queue ? __dup_event(oe, event) : event;
78 }
79
free_dup_event(struct ordered_events * oe,union perf_event * event)80 static void free_dup_event(struct ordered_events *oe, union perf_event *event)
81 {
82 if (event && oe->copy_on_queue) {
83 oe->cur_alloc_size -= event->header.size;
84 free(event);
85 }
86 }
87
88 #define MAX_SAMPLE_BUFFER (64 * 1024 / sizeof(struct ordered_event))
alloc_event(struct ordered_events * oe,union perf_event * event)89 static struct ordered_event *alloc_event(struct ordered_events *oe,
90 union perf_event *event)
91 {
92 struct list_head *cache = &oe->cache;
93 struct ordered_event *new = NULL;
94 union perf_event *new_event;
95
96 new_event = dup_event(oe, event);
97 if (!new_event)
98 return NULL;
99
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)
106 oe->buffer = NULL;
107 } else if (oe->cur_alloc_size < oe->max_alloc_size) {
108 size_t size = MAX_SAMPLE_BUFFER * sizeof(*new);
109
110 oe->buffer = malloc(size);
111 if (!oe->buffer) {
112 free_dup_event(oe, new_event);
113 return NULL;
114 }
115
116 pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
117 oe->cur_alloc_size, size, oe->max_alloc_size);
118
119 oe->cur_alloc_size += size;
120 list_add(&oe->buffer->list, &oe->to_free);
121
122 /* First entry is abused to maintain the to_free list. */
123 oe->buffer_idx = 2;
124 new = oe->buffer + 1;
125 } else {
126 pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
127 }
128
129 new->event = new_event;
130 return new;
131 }
132
133 static struct ordered_event *
ordered_events__new_event(struct ordered_events * oe,u64 timestamp,union perf_event * event)134 ordered_events__new_event(struct ordered_events *oe, u64 timestamp,
135 union perf_event *event)
136 {
137 struct ordered_event *new;
138
139 new = alloc_event(oe, event);
140 if (new) {
141 new->timestamp = timestamp;
142 queue_event(oe, new);
143 }
144
145 return new;
146 }
147
ordered_events__delete(struct ordered_events * oe,struct ordered_event * event)148 void ordered_events__delete(struct ordered_events *oe, struct ordered_event *event)
149 {
150 list_move(&event->list, &oe->cache);
151 oe->nr_events--;
152 free_dup_event(oe, event->event);
153 event->event = NULL;
154 }
155
ordered_events__queue(struct ordered_events * oe,union perf_event * event,struct perf_sample * sample,u64 file_offset)156 int ordered_events__queue(struct ordered_events *oe, union perf_event *event,
157 struct perf_sample *sample, u64 file_offset)
158 {
159 u64 timestamp = sample->time;
160 struct ordered_event *oevent;
161
162 if (!timestamp || timestamp == ~0ULL)
163 return -ETIME;
164
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);
169
170 oe->nr_unordered_events++;
171 }
172
173 oevent = ordered_events__new_event(oe, timestamp, event);
174 if (!oevent) {
175 ordered_events__flush(oe, OE_FLUSH__HALF);
176 oevent = ordered_events__new_event(oe, timestamp, event);
177 }
178
179 if (!oevent)
180 return -ENOMEM;
181
182 oevent->file_offset = file_offset;
183 return 0;
184 }
185
__ordered_events__flush(struct ordered_events * oe)186 static int __ordered_events__flush(struct ordered_events *oe)
187 {
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;
194 int ret;
195
196 if (!limit)
197 return 0;
198
199 if (show_progress)
200 ui_progress__init(&prog, oe->nr_events, "Processing time ordered events...");
201
202 list_for_each_entry_safe(iter, tmp, head, list) {
203 if (session_done())
204 return 0;
205
206 if (iter->timestamp > limit)
207 break;
208 ret = oe->deliver(oe, iter);
209 if (ret)
210 return ret;
211
212 ordered_events__delete(oe, iter);
213 oe->last_flush = iter->timestamp;
214
215 if (show_progress)
216 ui_progress__update(&prog, 1);
217 }
218
219 if (list_empty(head))
220 oe->last = NULL;
221 else if (last_ts <= limit)
222 oe->last = list_entry(head->prev, struct ordered_event, list);
223
224 if (show_progress)
225 ui_progress__finish();
226
227 return 0;
228 }
229
ordered_events__flush(struct ordered_events * oe,enum oe_flush how)230 int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)
231 {
232 static const char * const str[] = {
233 "NONE",
234 "FINAL",
235 "ROUND",
236 "HALF ",
237 };
238 int err;
239
240 if (oe->nr_events == 0)
241 return 0;
242
243 switch (how) {
244 case OE_FLUSH__FINAL:
245 oe->next_flush = ULLONG_MAX;
246 break;
247
248 case OE_FLUSH__HALF:
249 {
250 struct ordered_event *first, *last;
251 struct list_head *head = &oe->events;
252
253 first = list_entry(head->next, struct ordered_event, list);
254 last = oe->last;
255
256 /* Warn if we are called before any event got allocated. */
257 if (WARN_ONCE(!last || list_empty(head), "empty queue"))
258 return 0;
259
260 oe->next_flush = first->timestamp;
261 oe->next_flush += (last->timestamp - first->timestamp) / 2;
262 break;
263 }
264
265 case OE_FLUSH__ROUND:
266 case OE_FLUSH__NONE:
267 default:
268 break;
269 };
270
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");
274
275 err = __ordered_events__flush(oe);
276
277 if (!err) {
278 if (how == OE_FLUSH__ROUND)
279 oe->next_flush = oe->max_timestamp;
280
281 oe->last_flush_type = how;
282 }
283
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");
287
288 return err;
289 }
290
ordered_events__init(struct ordered_events * oe,ordered_events__deliver_t deliver)291 void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t deliver)
292 {
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;
299 }
300
ordered_events__free(struct ordered_events * oe)301 void ordered_events__free(struct ordered_events *oe)
302 {
303 while (!list_empty(&oe->to_free)) {
304 struct ordered_event *event;
305
306 event = list_entry(oe->to_free.next, struct ordered_event, list);
307 list_del(&event->list);
308 free_dup_event(oe, event->event);
309 free(event);
310 }
311 }
312