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 
queue_event(struct ordered_events * oe,struct ordered_event * new)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 
__dup_event(struct ordered_events * oe,union perf_event * event)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 
dup_event(struct ordered_events * oe,union perf_event * event)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 
__free_dup_event(struct ordered_events * oe,union perf_event * event)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 
free_dup_event(struct ordered_events * oe,union perf_event * event)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))
alloc_event(struct ordered_events * oe,union perf_event * 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 *
ordered_events__new_event(struct ordered_events * oe,u64 timestamp,union perf_event * 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 
ordered_events__delete(struct ordered_events * oe,struct ordered_event * event)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 
ordered_events__queue(struct ordered_events * oe,union perf_event * event,u64 timestamp,u64 file_offset,const char * file_path)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 
do_flush(struct ordered_events * oe,bool show_progress)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 
__ordered_events__flush(struct ordered_events * oe,enum oe_flush how,u64 timestamp)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 
ordered_events__flush(struct ordered_events * oe,enum oe_flush how)340 int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)
341 {
342 	return __ordered_events__flush(oe, how, 0);
343 }
344 
ordered_events__flush_time(struct ordered_events * oe,u64 timestamp)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 
ordered_events__first_time(struct ordered_events * oe)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 
ordered_events__init(struct ordered_events * oe,ordered_events__deliver_t deliver,void * data)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
ordered_events_buffer__free(struct ordered_events_buffer * buffer,unsigned int max,struct ordered_events * oe)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 
ordered_events__free(struct ordered_events * oe)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 
ordered_events__reinit(struct ordered_events * oe)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 }
418