1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0 2a43783aeSArnaldo Carvalho de Melo #include <errno.h> 3fd20e811SArnaldo Carvalho de Melo #include <inttypes.h> 45f86b80bSJiri Olsa #include <linux/list.h> 5cee3ab9cSJiri Olsa #include <linux/compiler.h> 654bf53b1SAlexander Yarygin #include <linux/string.h> 75f86b80bSJiri Olsa #include "ordered-events.h" 85f86b80bSJiri Olsa #include "session.h" 95f86b80bSJiri Olsa #include "asm/bug.h" 105f86b80bSJiri Olsa #include "debug.h" 115f86b80bSJiri Olsa 12cee3ab9cSJiri Olsa #define pr_N(n, fmt, ...) \ 13cee3ab9cSJiri Olsa eprintf(n, debug_ordered_events, fmt, ##__VA_ARGS__) 14cee3ab9cSJiri Olsa 15cee3ab9cSJiri Olsa #define pr(fmt, ...) pr_N(1, pr_fmt(fmt), ##__VA_ARGS__) 16cee3ab9cSJiri Olsa 175f86b80bSJiri Olsa static void queue_event(struct ordered_events *oe, struct ordered_event *new) 185f86b80bSJiri Olsa { 195f86b80bSJiri Olsa struct ordered_event *last = oe->last; 205f86b80bSJiri Olsa u64 timestamp = new->timestamp; 215f86b80bSJiri Olsa struct list_head *p; 225f86b80bSJiri Olsa 235f86b80bSJiri Olsa ++oe->nr_events; 245f86b80bSJiri Olsa oe->last = new; 255f86b80bSJiri Olsa 26cee3ab9cSJiri Olsa pr_oe_time2(timestamp, "queue_event nr_events %u\n", oe->nr_events); 27cee3ab9cSJiri Olsa 285f86b80bSJiri Olsa if (!last) { 295f86b80bSJiri Olsa list_add(&new->list, &oe->events); 305f86b80bSJiri Olsa oe->max_timestamp = timestamp; 315f86b80bSJiri Olsa return; 325f86b80bSJiri Olsa } 335f86b80bSJiri Olsa 345f86b80bSJiri Olsa /* 355f86b80bSJiri Olsa * last event might point to some random place in the list as it's 365f86b80bSJiri Olsa * the last queued event. We expect that the new event is close to 375f86b80bSJiri Olsa * this. 385f86b80bSJiri Olsa */ 395f86b80bSJiri Olsa if (last->timestamp <= timestamp) { 405f86b80bSJiri Olsa while (last->timestamp <= timestamp) { 415f86b80bSJiri Olsa p = last->list.next; 425f86b80bSJiri Olsa if (p == &oe->events) { 435f86b80bSJiri Olsa list_add_tail(&new->list, &oe->events); 445f86b80bSJiri Olsa oe->max_timestamp = timestamp; 455f86b80bSJiri Olsa return; 465f86b80bSJiri Olsa } 475f86b80bSJiri Olsa last = list_entry(p, struct ordered_event, list); 485f86b80bSJiri Olsa } 495f86b80bSJiri Olsa list_add_tail(&new->list, &last->list); 505f86b80bSJiri Olsa } else { 515f86b80bSJiri Olsa while (last->timestamp > timestamp) { 525f86b80bSJiri Olsa p = last->list.prev; 535f86b80bSJiri Olsa if (p == &oe->events) { 545f86b80bSJiri Olsa list_add(&new->list, &oe->events); 555f86b80bSJiri Olsa return; 565f86b80bSJiri Olsa } 575f86b80bSJiri Olsa last = list_entry(p, struct ordered_event, list); 585f86b80bSJiri Olsa } 595f86b80bSJiri Olsa list_add(&new->list, &last->list); 605f86b80bSJiri Olsa } 615f86b80bSJiri Olsa } 625f86b80bSJiri Olsa 6354bf53b1SAlexander Yarygin static union perf_event *__dup_event(struct ordered_events *oe, 6454bf53b1SAlexander Yarygin union perf_event *event) 6554bf53b1SAlexander Yarygin { 6654bf53b1SAlexander Yarygin union perf_event *new_event = NULL; 6754bf53b1SAlexander Yarygin 6854bf53b1SAlexander Yarygin if (oe->cur_alloc_size < oe->max_alloc_size) { 6954bf53b1SAlexander Yarygin new_event = memdup(event, event->header.size); 7054bf53b1SAlexander Yarygin if (new_event) 7154bf53b1SAlexander Yarygin oe->cur_alloc_size += event->header.size; 7254bf53b1SAlexander Yarygin } 7354bf53b1SAlexander Yarygin 7454bf53b1SAlexander Yarygin return new_event; 7554bf53b1SAlexander Yarygin } 7654bf53b1SAlexander Yarygin 7754bf53b1SAlexander Yarygin static union perf_event *dup_event(struct ordered_events *oe, 7854bf53b1SAlexander Yarygin union perf_event *event) 7954bf53b1SAlexander Yarygin { 8054bf53b1SAlexander Yarygin return oe->copy_on_queue ? __dup_event(oe, event) : event; 8154bf53b1SAlexander Yarygin } 8254bf53b1SAlexander Yarygin 83d5ceb62bSJiri Olsa static void __free_dup_event(struct ordered_events *oe, union perf_event *event) 8454bf53b1SAlexander Yarygin { 85d5ceb62bSJiri Olsa if (event) { 8654bf53b1SAlexander Yarygin oe->cur_alloc_size -= event->header.size; 8754bf53b1SAlexander Yarygin free(event); 8854bf53b1SAlexander Yarygin } 8954bf53b1SAlexander Yarygin } 9054bf53b1SAlexander Yarygin 91d5ceb62bSJiri Olsa static void free_dup_event(struct ordered_events *oe, union perf_event *event) 92d5ceb62bSJiri Olsa { 93d5ceb62bSJiri Olsa if (oe->copy_on_queue) 94d5ceb62bSJiri Olsa __free_dup_event(oe, event); 95d5ceb62bSJiri Olsa } 96d5ceb62bSJiri Olsa 975f86b80bSJiri Olsa #define MAX_SAMPLE_BUFFER (64 * 1024 / sizeof(struct ordered_event)) 9854bf53b1SAlexander Yarygin static struct ordered_event *alloc_event(struct ordered_events *oe, 9954bf53b1SAlexander Yarygin union perf_event *event) 1005f86b80bSJiri Olsa { 1015f86b80bSJiri Olsa struct list_head *cache = &oe->cache; 1025f86b80bSJiri Olsa struct ordered_event *new = NULL; 10354bf53b1SAlexander Yarygin union perf_event *new_event; 10453da12e0SJiri Olsa size_t size; 10554bf53b1SAlexander Yarygin 10654bf53b1SAlexander Yarygin new_event = dup_event(oe, event); 10754bf53b1SAlexander Yarygin if (!new_event) 10854bf53b1SAlexander Yarygin return NULL; 1095f86b80bSJiri Olsa 110d5ceb62bSJiri Olsa /* 111d5ceb62bSJiri Olsa * We maintain the following scheme of buffers for ordered 112d5ceb62bSJiri Olsa * event allocation: 113d5ceb62bSJiri Olsa * 114d5ceb62bSJiri Olsa * to_free list -> buffer1 (64K) 115d5ceb62bSJiri Olsa * buffer2 (64K) 116d5ceb62bSJiri Olsa * ... 117d5ceb62bSJiri Olsa * 118d5ceb62bSJiri Olsa * Each buffer keeps an array of ordered events objects: 119d5ceb62bSJiri Olsa * buffer -> event[0] 120d5ceb62bSJiri Olsa * event[1] 121d5ceb62bSJiri Olsa * ... 122d5ceb62bSJiri Olsa * 123d5ceb62bSJiri Olsa * Each allocated ordered event is linked to one of 124d5ceb62bSJiri Olsa * following lists: 125d5ceb62bSJiri Olsa * - time ordered list 'events' 126d5ceb62bSJiri Olsa * - list of currently removed events 'cache' 127d5ceb62bSJiri Olsa * 128d5ceb62bSJiri Olsa * Allocation of the ordered event uses the following order 129d5ceb62bSJiri Olsa * to get the memory: 130d5ceb62bSJiri Olsa * - use recently removed object from 'cache' list 131d5ceb62bSJiri Olsa * - use available object in current allocation buffer 132d5ceb62bSJiri Olsa * - allocate new buffer if the current buffer is full 133d5ceb62bSJiri Olsa * 134d5ceb62bSJiri Olsa * Removal of ordered event object moves it from events to 135d5ceb62bSJiri Olsa * the cache list. 136d5ceb62bSJiri Olsa */ 13753da12e0SJiri Olsa size = sizeof(*oe->buffer) + MAX_SAMPLE_BUFFER * sizeof(*new); 13853da12e0SJiri Olsa 1395f86b80bSJiri Olsa if (!list_empty(cache)) { 1405f86b80bSJiri Olsa new = list_entry(cache->next, struct ordered_event, list); 1415f86b80bSJiri Olsa list_del(&new->list); 1425f86b80bSJiri Olsa } else if (oe->buffer) { 143d5ceb62bSJiri Olsa new = &oe->buffer->event[oe->buffer_idx]; 1445f86b80bSJiri Olsa if (++oe->buffer_idx == MAX_SAMPLE_BUFFER) 1455f86b80bSJiri Olsa oe->buffer = NULL; 14653da12e0SJiri Olsa } else if ((oe->cur_alloc_size + size) < oe->max_alloc_size) { 1475f86b80bSJiri Olsa oe->buffer = malloc(size); 14854bf53b1SAlexander Yarygin if (!oe->buffer) { 14954bf53b1SAlexander Yarygin free_dup_event(oe, new_event); 1505f86b80bSJiri Olsa return NULL; 15154bf53b1SAlexander Yarygin } 1525f86b80bSJiri Olsa 153cee3ab9cSJiri Olsa pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n", 154cee3ab9cSJiri Olsa oe->cur_alloc_size, size, oe->max_alloc_size); 155cee3ab9cSJiri Olsa 1565f86b80bSJiri Olsa oe->cur_alloc_size += size; 1575f86b80bSJiri Olsa list_add(&oe->buffer->list, &oe->to_free); 1585f86b80bSJiri Olsa 159d5ceb62bSJiri Olsa oe->buffer_idx = 1; 160d5ceb62bSJiri Olsa new = &oe->buffer->event[0]; 161cee3ab9cSJiri Olsa } else { 162cee3ab9cSJiri Olsa pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size); 163d5ceb62bSJiri Olsa return NULL; 1645f86b80bSJiri Olsa } 1655f86b80bSJiri Olsa 16654bf53b1SAlexander Yarygin new->event = new_event; 1675f86b80bSJiri Olsa return new; 1685f86b80bSJiri Olsa } 1695f86b80bSJiri Olsa 1704a6b362fSArnaldo Carvalho de Melo static struct ordered_event * 1714a6b362fSArnaldo Carvalho de Melo ordered_events__new_event(struct ordered_events *oe, u64 timestamp, 17254bf53b1SAlexander Yarygin union perf_event *event) 1735f86b80bSJiri Olsa { 1745f86b80bSJiri Olsa struct ordered_event *new; 1755f86b80bSJiri Olsa 17654bf53b1SAlexander Yarygin new = alloc_event(oe, event); 1775f86b80bSJiri Olsa if (new) { 1785f86b80bSJiri Olsa new->timestamp = timestamp; 1795f86b80bSJiri Olsa queue_event(oe, new); 1805f86b80bSJiri Olsa } 1815f86b80bSJiri Olsa 1825f86b80bSJiri Olsa return new; 1835f86b80bSJiri Olsa } 1845f86b80bSJiri Olsa 1855f86b80bSJiri Olsa void ordered_events__delete(struct ordered_events *oe, struct ordered_event *event) 1865f86b80bSJiri Olsa { 187fa4e5c67SJiri Olsa list_move(&event->list, &oe->cache); 1885f86b80bSJiri Olsa oe->nr_events--; 18954bf53b1SAlexander Yarygin free_dup_event(oe, event->event); 1901e0d4f02SDavid Carrillo-Cisneros event->event = NULL; 1915f86b80bSJiri Olsa } 1925f86b80bSJiri Olsa 1934a6b362fSArnaldo Carvalho de Melo int ordered_events__queue(struct ordered_events *oe, union perf_event *event, 194dc83e139SJiri Olsa u64 timestamp, u64 file_offset) 1954a6b362fSArnaldo Carvalho de Melo { 1964a6b362fSArnaldo Carvalho de Melo struct ordered_event *oevent; 1974a6b362fSArnaldo Carvalho de Melo 1984a6b362fSArnaldo Carvalho de Melo if (!timestamp || timestamp == ~0ULL) 1994a6b362fSArnaldo Carvalho de Melo return -ETIME; 2004a6b362fSArnaldo Carvalho de Melo 2014a6b362fSArnaldo Carvalho de Melo if (timestamp < oe->last_flush) { 2024a6b362fSArnaldo Carvalho de Melo pr_oe_time(timestamp, "out of order event\n"); 2034a6b362fSArnaldo Carvalho de Melo pr_oe_time(oe->last_flush, "last flush, last_flush_type %d\n", 2044a6b362fSArnaldo Carvalho de Melo oe->last_flush_type); 2054a6b362fSArnaldo Carvalho de Melo 2069870d780SArnaldo Carvalho de Melo oe->nr_unordered_events++; 2074a6b362fSArnaldo Carvalho de Melo } 2084a6b362fSArnaldo Carvalho de Melo 2094a6b362fSArnaldo Carvalho de Melo oevent = ordered_events__new_event(oe, timestamp, event); 2104a6b362fSArnaldo Carvalho de Melo if (!oevent) { 2114a6b362fSArnaldo Carvalho de Melo ordered_events__flush(oe, OE_FLUSH__HALF); 2124a6b362fSArnaldo Carvalho de Melo oevent = ordered_events__new_event(oe, timestamp, event); 2134a6b362fSArnaldo Carvalho de Melo } 2144a6b362fSArnaldo Carvalho de Melo 2154a6b362fSArnaldo Carvalho de Melo if (!oevent) 2164a6b362fSArnaldo Carvalho de Melo return -ENOMEM; 2174a6b362fSArnaldo Carvalho de Melo 2184a6b362fSArnaldo Carvalho de Melo oevent->file_offset = file_offset; 2194a6b362fSArnaldo Carvalho de Melo return 0; 2204a6b362fSArnaldo Carvalho de Melo } 2214a6b362fSArnaldo Carvalho de Melo 222b7b61cbeSArnaldo Carvalho de Melo static int __ordered_events__flush(struct ordered_events *oe) 2235f86b80bSJiri Olsa { 2245f86b80bSJiri Olsa struct list_head *head = &oe->events; 2255f86b80bSJiri Olsa struct ordered_event *tmp, *iter; 2265f86b80bSJiri Olsa u64 limit = oe->next_flush; 2275f86b80bSJiri Olsa u64 last_ts = oe->last ? oe->last->timestamp : 0ULL; 2285f86b80bSJiri Olsa bool show_progress = limit == ULLONG_MAX; 2295f86b80bSJiri Olsa struct ui_progress prog; 2305f86b80bSJiri Olsa int ret; 2315f86b80bSJiri Olsa 23228083681SArnaldo Carvalho de Melo if (!limit) 2335f86b80bSJiri Olsa return 0; 2345f86b80bSJiri Olsa 2355f86b80bSJiri Olsa if (show_progress) 2365f86b80bSJiri Olsa ui_progress__init(&prog, oe->nr_events, "Processing time ordered events..."); 2375f86b80bSJiri Olsa 2385f86b80bSJiri Olsa list_for_each_entry_safe(iter, tmp, head, list) { 2395f86b80bSJiri Olsa if (session_done()) 2405f86b80bSJiri Olsa return 0; 2415f86b80bSJiri Olsa 2425f86b80bSJiri Olsa if (iter->timestamp > limit) 2435f86b80bSJiri Olsa break; 2449870d780SArnaldo Carvalho de Melo ret = oe->deliver(oe, iter); 2455f86b80bSJiri Olsa if (ret) 2465f86b80bSJiri Olsa return ret; 2475f86b80bSJiri Olsa 2485f86b80bSJiri Olsa ordered_events__delete(oe, iter); 2495f86b80bSJiri Olsa oe->last_flush = iter->timestamp; 2505f86b80bSJiri Olsa 2515f86b80bSJiri Olsa if (show_progress) 2525f86b80bSJiri Olsa ui_progress__update(&prog, 1); 2535f86b80bSJiri Olsa } 2545f86b80bSJiri Olsa 2555f86b80bSJiri Olsa if (list_empty(head)) 2565f86b80bSJiri Olsa oe->last = NULL; 2575f86b80bSJiri Olsa else if (last_ts <= limit) 2585f86b80bSJiri Olsa oe->last = list_entry(head->prev, struct ordered_event, list); 2595f86b80bSJiri Olsa 2605c9ce1e6SArnaldo Carvalho de Melo if (show_progress) 2615c9ce1e6SArnaldo Carvalho de Melo ui_progress__finish(); 2625c9ce1e6SArnaldo Carvalho de Melo 2635f86b80bSJiri Olsa return 0; 2645f86b80bSJiri Olsa } 2655f86b80bSJiri Olsa 266b7b61cbeSArnaldo Carvalho de Melo int ordered_events__flush(struct ordered_events *oe, enum oe_flush how) 2675f86b80bSJiri Olsa { 268cee3ab9cSJiri Olsa static const char * const str[] = { 269b0a45203SJiri Olsa "NONE", 270cee3ab9cSJiri Olsa "FINAL", 271cee3ab9cSJiri Olsa "ROUND", 272cee3ab9cSJiri Olsa "HALF ", 273cee3ab9cSJiri Olsa }; 2745f86b80bSJiri Olsa int err; 2755f86b80bSJiri Olsa 27628083681SArnaldo Carvalho de Melo if (oe->nr_events == 0) 27728083681SArnaldo Carvalho de Melo return 0; 27828083681SArnaldo Carvalho de Melo 2795f86b80bSJiri Olsa switch (how) { 2805f86b80bSJiri Olsa case OE_FLUSH__FINAL: 2815f86b80bSJiri Olsa oe->next_flush = ULLONG_MAX; 2825f86b80bSJiri Olsa break; 2835f86b80bSJiri Olsa 2845f86b80bSJiri Olsa case OE_FLUSH__HALF: 2855f86b80bSJiri Olsa { 2865f86b80bSJiri Olsa struct ordered_event *first, *last; 2875f86b80bSJiri Olsa struct list_head *head = &oe->events; 2885f86b80bSJiri Olsa 2895f86b80bSJiri Olsa first = list_entry(head->next, struct ordered_event, list); 2905f86b80bSJiri Olsa last = oe->last; 2915f86b80bSJiri Olsa 2925f86b80bSJiri Olsa /* Warn if we are called before any event got allocated. */ 2935f86b80bSJiri Olsa if (WARN_ONCE(!last || list_empty(head), "empty queue")) 2945f86b80bSJiri Olsa return 0; 2955f86b80bSJiri Olsa 2965f86b80bSJiri Olsa oe->next_flush = first->timestamp; 2975f86b80bSJiri Olsa oe->next_flush += (last->timestamp - first->timestamp) / 2; 2985f86b80bSJiri Olsa break; 2995f86b80bSJiri Olsa } 3005f86b80bSJiri Olsa 3015f86b80bSJiri Olsa case OE_FLUSH__ROUND: 302b0a45203SJiri Olsa case OE_FLUSH__NONE: 3035f86b80bSJiri Olsa default: 3045f86b80bSJiri Olsa break; 3055f86b80bSJiri Olsa }; 3065f86b80bSJiri Olsa 307cee3ab9cSJiri Olsa pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE %s, nr_events %u\n", 308cee3ab9cSJiri Olsa str[how], oe->nr_events); 309cee3ab9cSJiri Olsa pr_oe_time(oe->max_timestamp, "max_timestamp\n"); 310cee3ab9cSJiri Olsa 311b7b61cbeSArnaldo Carvalho de Melo err = __ordered_events__flush(oe); 3125f86b80bSJiri Olsa 3135f86b80bSJiri Olsa if (!err) { 3145f86b80bSJiri Olsa if (how == OE_FLUSH__ROUND) 3155f86b80bSJiri Olsa oe->next_flush = oe->max_timestamp; 316b0a45203SJiri Olsa 317b0a45203SJiri Olsa oe->last_flush_type = how; 3185f86b80bSJiri Olsa } 3195f86b80bSJiri Olsa 320cee3ab9cSJiri Olsa pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n", 321cee3ab9cSJiri Olsa str[how], oe->nr_events); 322cee3ab9cSJiri Olsa pr_oe_time(oe->last_flush, "last_flush\n"); 323cee3ab9cSJiri Olsa 3245f86b80bSJiri Olsa return err; 3255f86b80bSJiri Olsa } 32636522f5cSJiri Olsa 3279870d780SArnaldo Carvalho de Melo void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t deliver) 32836522f5cSJiri Olsa { 32936522f5cSJiri Olsa INIT_LIST_HEAD(&oe->events); 33036522f5cSJiri Olsa INIT_LIST_HEAD(&oe->cache); 33136522f5cSJiri Olsa INIT_LIST_HEAD(&oe->to_free); 33236522f5cSJiri Olsa oe->max_alloc_size = (u64) -1; 33336522f5cSJiri Olsa oe->cur_alloc_size = 0; 334d10eb1ebSArnaldo Carvalho de Melo oe->deliver = deliver; 33536522f5cSJiri Olsa } 336adc56ed1SJiri Olsa 337d5ceb62bSJiri Olsa static void 338d5ceb62bSJiri Olsa ordered_events_buffer__free(struct ordered_events_buffer *buffer, 339d5ceb62bSJiri Olsa unsigned int max, struct ordered_events *oe) 340d5ceb62bSJiri Olsa { 341d5ceb62bSJiri Olsa if (oe->copy_on_queue) { 342d5ceb62bSJiri Olsa unsigned int i; 343d5ceb62bSJiri Olsa 344d5ceb62bSJiri Olsa for (i = 0; i < max; i++) 345d5ceb62bSJiri Olsa __free_dup_event(oe, buffer->event[i].event); 346d5ceb62bSJiri Olsa } 347d5ceb62bSJiri Olsa 348d5ceb62bSJiri Olsa free(buffer); 349d5ceb62bSJiri Olsa } 350d5ceb62bSJiri Olsa 351adc56ed1SJiri Olsa void ordered_events__free(struct ordered_events *oe) 352adc56ed1SJiri Olsa { 353d5ceb62bSJiri Olsa struct ordered_events_buffer *buffer, *tmp; 354adc56ed1SJiri Olsa 355d5ceb62bSJiri Olsa if (list_empty(&oe->to_free)) 356d5ceb62bSJiri Olsa return; 357d5ceb62bSJiri Olsa 358d5ceb62bSJiri Olsa /* 359d5ceb62bSJiri Olsa * Current buffer might not have all the events allocated 360d5ceb62bSJiri Olsa * yet, we need to free only allocated ones ... 361d5ceb62bSJiri Olsa */ 362d5ceb62bSJiri Olsa list_del(&oe->buffer->list); 363d5ceb62bSJiri Olsa ordered_events_buffer__free(oe->buffer, oe->buffer_idx, oe); 364d5ceb62bSJiri Olsa 365d5ceb62bSJiri Olsa /* ... and continue with the rest */ 366d5ceb62bSJiri Olsa list_for_each_entry_safe(buffer, tmp, &oe->to_free, list) { 367d5ceb62bSJiri Olsa list_del(&buffer->list); 368d5ceb62bSJiri Olsa ordered_events_buffer__free(buffer, MAX_SAMPLE_BUFFER, oe); 369adc56ed1SJiri Olsa } 370adc56ed1SJiri Olsa } 3714532f642SWang Nan 3724532f642SWang Nan void ordered_events__reinit(struct ordered_events *oe) 3734532f642SWang Nan { 3744532f642SWang Nan ordered_events__deliver_t old_deliver = oe->deliver; 3754532f642SWang Nan 3764532f642SWang Nan ordered_events__free(oe); 3774532f642SWang Nan memset(oe, '\0', sizeof(*oe)); 3784532f642SWang Nan ordered_events__init(oe, old_deliver); 3794532f642SWang Nan } 380