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