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) {
  86                 oe->cur_alloc_size -= event->header.size;
  87                 free(event);
  88         }
  89 }
  90
  91 static void free_dup_event(struct ordered_events *oe, union perf_event *event)
  92 {
  93         if (oe->copy_on_queue)
  94                 __free_dup_event(oe, event);
  95 }
  96
  97 #define MAX_SAMPLE_BUFFER       (64 * 1024 / sizeof(struct ordered_event))
  98 static struct ordered_event *alloc_event(struct ordered_events *oe,
  99                                          union perf_event *event)
 100 {
 101         struct list_head *cache = &oe->cache;
 102         struct ordered_event *new = NULL;
 103         union perf_event *new_event;
 104         size_t size;
 105
 106         new_event = dup_event(oe, event);
 107         if (!new_event)
 108                 return NULL;
 109
 110         /*
 111          * We maintain the following scheme of buffers for ordered
 112          * event allocation:
 113          *
 114          *   to_free list -> buffer1 (64K)
 115          *                   buffer2 (64K)
 116          *                   ...
 117          *
 118          * Each buffer keeps an array of ordered events objects:
 119          *    buffer -> event[0]
 120          *              event[1]
 121          *              ...
 122          *
 123          * Each allocated ordered event is linked to one of
 124          * following lists:
 125          *   - time ordered list 'events'
 126          *   - list of currently removed events 'cache'
 127          *
 128          * Allocation of the ordered event uses the following order
 129          * to get the memory:
 130          *   - use recently removed object from 'cache' list
 131          *   - use available object in current allocation buffer
 132          *   - allocate new buffer if the current buffer is full
 133          *
 134          * Removal of ordered event object moves it from events to
 135          * the cache list.
 136          */
 137         size = sizeof(*oe->buffer) + MAX_SAMPLE_BUFFER * sizeof(*new);
 138
 139         if (!list_empty(cache)) {
 140                 new = list_entry(cache->next, struct ordered_event, list);
 141                 list_del(&new->list);
 142         } else if (oe->buffer) {
 143                 new = &oe->buffer->event[oe->buffer_idx];
 144                 if (++oe->buffer_idx == MAX_SAMPLE_BUFFER)
 145                         oe->buffer = NULL;
 146         } else if ((oe->cur_alloc_size + size) < oe->max_alloc_size) {
 147                 oe->buffer = malloc(size);
 148                 if (!oe->buffer) {
 149                         free_dup_event(oe, new_event);
 150                         return NULL;
 151                 }
 152
 153                 pr("alloc size %" PRIu64 "B (+%zu), max %" PRIu64 "B\n",
 154                    oe->cur_alloc_size, size, oe->max_alloc_size);
 155
 156                 oe->cur_alloc_size += size;
 157                 list_add(&oe->buffer->list, &oe->to_free);
 158
 159                 oe->buffer_idx = 1;
 160                 new = &oe->buffer->event[0];
 161         } else {
 162                 pr("allocation limit reached %" PRIu64 "B\n", oe->max_alloc_size);
 163                 return NULL;
 164         }
 165
 166         new->event = new_event;
 167         return new;
 168 }
 169
 170 static struct ordered_event *
 171 ordered_events__new_event(struct ordered_events *oe, u64 timestamp,
 172                     union perf_event *event)
 173 {
 174         struct ordered_event *new;
 175
 176         new = alloc_event(oe, event);
 177         if (new) {
 178                 new->timestamp = timestamp;
 179                 queue_event(oe, new);
 180         }
 181
 182         return new;
 183 }
 184
 185 void ordered_events__delete(struct ordered_events *oe, struct ordered_event *event)
 186 {
 187         list_move(&event->list, &oe->cache);
 188         oe->nr_events--;
 189         free_dup_event(oe, event->event);
 190         event->event = NULL;
 191 }
 192
 193 int ordered_events__queue(struct ordered_events *oe, union perf_event *event,
 194                           u64 timestamp, u64 file_offset)
 195 {
 196         struct ordered_event *oevent;
 197
 198         if (!timestamp || timestamp == ~0ULL)
 199                 return -ETIME;
 200
 201         if (timestamp < oe->last_flush) {
 202                 pr_oe_time(timestamp,      "out of order event\n");
 203                 pr_oe_time(oe->last_flush, "last flush, last_flush_type %d\n",
 204                            oe->last_flush_type);
 205
 206                 oe->nr_unordered_events++;
 207         }
 208
 209         oevent = ordered_events__new_event(oe, timestamp, event);
 210         if (!oevent) {
 211                 ordered_events__flush(oe, OE_FLUSH__HALF);
 212                 oevent = ordered_events__new_event(oe, timestamp, event);
 213         }
 214
 215         if (!oevent)
 216                 return -ENOMEM;
 217
 218         oevent->file_offset = file_offset;
 219         return 0;
 220 }
 221
 222 static int do_flush(struct ordered_events *oe, bool show_progress)
 223 {
 224         struct list_head *head = &oe->events;
 225         struct ordered_event *tmp, *iter;
 226         u64 limit = oe->next_flush;
 227         u64 last_ts = oe->last ? oe->last->timestamp : 0ULL;
 228         struct ui_progress prog;
 229         int ret;
 230
 231         if (!limit)
 232                 return 0;
 233
 234         if (show_progress)
 235                 ui_progress__init(&prog, oe->nr_events, "Processing time ordered events...");
 236
 237         list_for_each_entry_safe(iter, tmp, head, list) {
 238                 if (session_done())
 239                         return 0;
 240
 241                 if (iter->timestamp > limit)
 242                         break;
 243                 ret = oe->deliver(oe, iter);
 244                 if (ret)
 245                         return ret;
 246
 247                 ordered_events__delete(oe, iter);
 248                 oe->last_flush = iter->timestamp;
 249
 250                 if (show_progress)
 251                         ui_progress__update(&prog, 1);
 252         }
 253
 254         if (list_empty(head))
 255                 oe->last = NULL;
 256         else if (last_ts <= limit)
 257                 oe->last = list_entry(head->prev, struct ordered_event, list);
 258
 259         if (show_progress)
 260                 ui_progress__finish();
 261
 262         return 0;
 263 }
 264
 265 static int __ordered_events__flush(struct ordered_events *oe, enum oe_flush how,
 266                                    u64 timestamp)
 267 {
 268         static const char * const str[] = {
 269                 "NONE",
 270                 "FINAL",
 271                 "ROUND",
 272                 "HALF ",
 273                 "TOP  ",
 274                 "TIME ",
 275         };
 276         int err;
 277         bool show_progress = false;
 278
 279         if (oe->nr_events == 0)
 280                 return 0;
 281
 282         switch (how) {
 283         case OE_FLUSH__FINAL:
 284                 show_progress = true;
 285                 __fallthrough;
 286         case OE_FLUSH__TOP:
 287                 oe->next_flush = ULLONG_MAX;
 288                 break;
 289
 290         case OE_FLUSH__HALF:
 291         {
 292                 struct ordered_event *first, *last;
 293                 struct list_head *head = &oe->events;
 294
 295                 first = list_entry(head->next, struct ordered_event, list);
 296                 last = oe->last;
 297
 298                 /* Warn if we are called before any event got allocated. */
 299                 if (WARN_ONCE(!last || list_empty(head), "empty queue"))
 300                         return 0;
 301
 302                 oe->next_flush  = first->timestamp;
 303                 oe->next_flush += (last->timestamp - first->timestamp) / 2;
 304                 break;
 305         }
 306
 307         case OE_FLUSH__TIME:
 308                 oe->next_flush = timestamp;
 309                 show_progress = false;
 310                 break;
 311
 312         case OE_FLUSH__ROUND:
 313         case OE_FLUSH__NONE:
 314         default:
 315                 break;
 316         };
 317
 318         pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE  %s, nr_events %u\n",
 319                    str[how], oe->nr_events);
 320         pr_oe_time(oe->max_timestamp, "max_timestamp\n");
 321
 322         err = do_flush(oe, show_progress);
 323
 324         if (!err) {
 325                 if (how == OE_FLUSH__ROUND)
 326                         oe->next_flush = oe->max_timestamp;
 327
 328                 oe->last_flush_type = how;
 329         }
 330
 331         pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n",
 332                    str[how], oe->nr_events);
 333         pr_oe_time(oe->last_flush, "last_flush\n");
 334
 335         return err;
 336 }
 337
 338 int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)
 339 {
 340         return __ordered_events__flush(oe, how, 0);
 341 }
 342
 343 int ordered_events__flush_time(struct ordered_events *oe, u64 timestamp)
 344 {
 345         return __ordered_events__flush(oe, OE_FLUSH__TIME, timestamp);
 346 }
 347
 348 u64 ordered_events__first_time(struct ordered_events *oe)
 349 {
 350         struct ordered_event *event;
 351
 352         if (list_empty(&oe->events))
 353                 return 0;
 354
 355         event = list_first_entry(&oe->events, struct ordered_event, list);
 356         return event->timestamp;
 357 }
 358
 359 void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t deliver,
 360                           void *data)
 361 {
 362         INIT_LIST_HEAD(&oe->events);
 363         INIT_LIST_HEAD(&oe->cache);
 364         INIT_LIST_HEAD(&oe->to_free);
 365         oe->max_alloc_size = (u64) -1;
 366         oe->cur_alloc_size = 0;
 367         oe->deliver        = deliver;
 368         oe->data           = data;
 369 }
 370
 371 static void
 372 ordered_events_buffer__free(struct ordered_events_buffer *buffer,
 373                             unsigned int max, struct ordered_events *oe)
 374 {
 375         if (oe->copy_on_queue) {
 376                 unsigned int i;
 377
 378                 for (i = 0; i < max; i++)
 379                         __free_dup_event(oe, buffer->event[i].event);
 380         }
 381
 382         free(buffer);
 383 }
 384
 385 void ordered_events__free(struct ordered_events *oe)
 386 {
 387         struct ordered_events_buffer *buffer, *tmp;
 388
 389         if (list_empty(&oe->to_free))
 390                 return;
 391
 392         /*
 393          * Current buffer might not have all the events allocated
 394          * yet, we need to free only allocated ones ...
 395          */
 396         if (oe->buffer) {
 397                 list_del(&oe->buffer->list);
 398                 ordered_events_buffer__free(oe->buffer, oe->buffer_idx, oe);
 399         }
 400
 401         /* ... and continue with the rest */
 402         list_for_each_entry_safe(buffer, tmp, &oe->to_free, list) {
 403                 list_del(&buffer->list);
 404                 ordered_events_buffer__free(buffer, MAX_SAMPLE_BUFFER, oe);
 405         }
 406 }
 407
 408 void ordered_events__reinit(struct ordered_events *oe)
 409 {
 410         ordered_events__deliver_t old_deliver = oe->deliver;
 411
 412         ordered_events__free(oe);
 413         memset(oe, '\0', sizeof(*oe));
 414         ordered_events__init(oe, old_deliver, oe->data);
 415 }