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         };
 274         int err;
 275         bool show_progress = false;
 276
 277         if (oe->nr_events == 0)
 278                 return 0;
 279
 280         switch (how) {
 281         case OE_FLUSH__FINAL:
 282                 show_progress = true;
 283                 __fallthrough;
 284         case OE_FLUSH__TOP:
 285                 oe->next_flush = ULLONG_MAX;
 286                 break;
 287
 288         case OE_FLUSH__HALF:
 289         {
 290                 struct ordered_event *first, *last;
 291                 struct list_head *head = &oe->events;
 292
 293                 first = list_entry(head->next, struct ordered_event, list);
 294                 last = oe->last;
 295
 296                 /* Warn if we are called before any event got allocated. */
 297                 if (WARN_ONCE(!last || list_empty(head), "empty queue"))
 298                         return 0;
 299
 300                 oe->next_flush  = first->timestamp;
 301                 oe->next_flush += (last->timestamp - first->timestamp) / 2;
 302                 break;
 303         }
 304
 305         case OE_FLUSH__TIME:
 306                 oe->next_flush = timestamp;
 307                 show_progress = false;
 308                 break;
 309
 310         case OE_FLUSH__ROUND:
 311         case OE_FLUSH__NONE:
 312         default:
 313                 break;
 314         };
 315
 316         pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE  %s, nr_events %u\n",
 317                    str[how], oe->nr_events);
 318         pr_oe_time(oe->max_timestamp, "max_timestamp\n");
 319
 320         err = do_flush(oe, show_progress);
 321
 322         if (!err) {
 323                 if (how == OE_FLUSH__ROUND)
 324                         oe->next_flush = oe->max_timestamp;
 325
 326                 oe->last_flush_type = how;
 327         }
 328
 329         pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n",
 330                    str[how], oe->nr_events);
 331         pr_oe_time(oe->last_flush, "last_flush\n");
 332
 333         return err;
 334 }
 335
 336 int ordered_events__flush(struct ordered_events *oe, enum oe_flush how)
 337 {
 338         return __ordered_events__flush(oe, how, 0);
 339 }
 340
 341 int ordered_events__flush_time(struct ordered_events *oe, u64 timestamp)
 342 {
 343         return __ordered_events__flush(oe, OE_FLUSH__TIME, timestamp);
 344 }
 345
 346 u64 ordered_events__first_time(struct ordered_events *oe)
 347 {
 348         struct ordered_event *event;
 349
 350         if (list_empty(&oe->events))
 351                 return 0;
 352
 353         event = list_first_entry(&oe->events, struct ordered_event, list);
 354         return event->timestamp;
 355 }
 356
 357 void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t deliver,
 358                           void *data)
 359 {
 360         INIT_LIST_HEAD(&oe->events);
 361         INIT_LIST_HEAD(&oe->cache);
 362         INIT_LIST_HEAD(&oe->to_free);
 363         oe->max_alloc_size = (u64) -1;
 364         oe->cur_alloc_size = 0;
 365         oe->deliver        = deliver;
 366         oe->data           = data;
 367 }
 368
 369 static void
 370 ordered_events_buffer__free(struct ordered_events_buffer *buffer,
 371                             unsigned int max, struct ordered_events *oe)
 372 {
 373         if (oe->copy_on_queue) {
 374                 unsigned int i;
 375
 376                 for (i = 0; i < max; i++)
 377                         __free_dup_event(oe, buffer->event[i].event);
 378         }
 379
 380         free(buffer);
 381 }
 382
 383 void ordered_events__free(struct ordered_events *oe)
 384 {
 385         struct ordered_events_buffer *buffer, *tmp;
 386
 387         if (list_empty(&oe->to_free))
 388                 return;
 389
 390         /*
 391          * Current buffer might not have all the events allocated
 392          * yet, we need to free only allocated ones ...
 393          */
 394         if (oe->buffer) {
 395                 list_del(&oe->buffer->list);
 396                 ordered_events_buffer__free(oe->buffer, oe->buffer_idx, oe);
 397         }
 398
 399         /* ... and continue with the rest */
 400         list_for_each_entry_safe(buffer, tmp, &oe->to_free, list) {
 401                 list_del(&buffer->list);
 402                 ordered_events_buffer__free(buffer, MAX_SAMPLE_BUFFER, oe);
 403         }
 404 }
 405
 406 void ordered_events__reinit(struct ordered_events *oe)
 407 {
 408         ordered_events__deliver_t old_deliver = oe->deliver;
 409
 410         ordered_events__free(oe);
 411         memset(oe, '\0', sizeof(*oe));
 412         ordered_events__init(oe, old_deliver, oe->data);
 413 }