tools/perf/util/ordered-events.c

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