tools/perf/util/ordered-events.c

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