tools/perf/util/ordered-events.c

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