418 lines · c
1// SPDX-License-Identifier: GPL-2.02#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 18static 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's37 * the last queued event. We expect that the new event is close to38 * 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 64static 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 78static 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 84static 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 92static 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))99static 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 ordered113 * 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 of125 * following lists:126 * - time ordered list 'events'127 * - list of currently removed events 'cache'128 *129 * Allocation of the ordered event uses the following order130 * to get the memory:131 * - use recently removed object from 'cache' list132 * - use available object in current allocation buffer133 * - allocate new buffer if the current buffer is full134 *135 * Removal of ordered event object moves it from events to136 * 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 171static struct ordered_event *172ordered_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 186void 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 194int 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 224static 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 267static 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 340int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)341{342 return __ordered_events__flush(oe, how, 0);343}344 345int ordered_events__flush_time(struct ordered_events *oe, u64 timestamp)346{347 return __ordered_events__flush(oe, OE_FLUSH__TIME, timestamp);348}349 350u64 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 361void 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 373static void374ordered_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 387void 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 allocated396 * 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 410void 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