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 } 312 313 void ordered_events__reinit(struct ordered_events *oe) 314 { 315 ordered_events__deliver_t old_deliver = oe->deliver; 316 317 ordered_events__free(oe); 318 memset(oe, '\0', sizeof(*oe)); 319 ordered_events__init(oe, old_deliver); 320 } 321