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, const char *file_path) 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 oevent->file_path = file_path; 221 return 0; 222 } 223 224 static int do_flush(struct ordered_events *oe, bool show_progress) 225 { 226 struct list_head *head = &oe->events; 227 struct ordered_event *tmp, *iter; 228 u64 limit = oe->next_flush; 229 u64 last_ts = oe->last ? oe->last->timestamp : 0ULL; 230 struct ui_progress prog; 231 int ret; 232 233 if (!limit) 234 return 0; 235 236 if (show_progress) 237 ui_progress__init(&prog, oe->nr_events, "Processing time ordered events..."); 238 239 list_for_each_entry_safe(iter, tmp, head, list) { 240 if (session_done()) { 241 ret = 0; 242 goto out_progress; 243 } 244 245 if (iter->timestamp > limit) 246 break; 247 ret = oe->deliver(oe, iter); 248 if (ret < 0) 249 goto out_progress; 250 251 ordered_events__delete(oe, iter); 252 oe->last_flush = iter->timestamp; 253 254 if (show_progress) 255 ui_progress__update(&prog, 1); 256 } 257 258 if (list_empty(head)) 259 oe->last = NULL; 260 else if (last_ts <= limit) 261 oe->last = list_entry(head->prev, struct ordered_event, list); 262 263 ret = 0; 264 out_progress: 265 /* 266 * Always pair ui_progress__init() with ui_progress__finish(), the 267 * stdio backend tracks the phases on a stack. 268 */ 269 if (show_progress) 270 ui_progress__finish(); 271 272 return ret; 273 } 274 275 static int __ordered_events__flush(struct ordered_events *oe, enum oe_flush how, 276 u64 timestamp) 277 { 278 static const char * const str[] = { 279 "NONE", 280 "FINAL", 281 "ROUND", 282 "HALF ", 283 "TOP ", 284 "TIME ", 285 }; 286 int err; 287 bool show_progress = false; 288 289 if (oe->nr_events == 0) 290 return 0; 291 292 switch (how) { 293 case OE_FLUSH__FINAL: 294 show_progress = true; 295 fallthrough; 296 case OE_FLUSH__TOP: 297 oe->next_flush = ULLONG_MAX; 298 break; 299 300 case OE_FLUSH__HALF: 301 { 302 struct ordered_event *first, *last; 303 struct list_head *head = &oe->events; 304 305 first = list_entry(head->next, struct ordered_event, list); 306 last = oe->last; 307 308 /* Warn if we are called before any event got allocated. */ 309 if (WARN_ONCE(!last || list_empty(head), "empty queue")) 310 return 0; 311 312 oe->next_flush = first->timestamp; 313 oe->next_flush += (last->timestamp - first->timestamp) / 2; 314 break; 315 } 316 317 case OE_FLUSH__TIME: 318 oe->next_flush = timestamp; 319 show_progress = false; 320 break; 321 322 case OE_FLUSH__ROUND: 323 case OE_FLUSH__NONE: 324 default: 325 break; 326 } 327 328 pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush PRE %s, nr_events %u\n", 329 str[how], oe->nr_events); 330 pr_oe_time(oe->max_timestamp, "max_timestamp\n"); 331 332 err = do_flush(oe, show_progress); 333 334 if (!err) { 335 if (how == OE_FLUSH__ROUND) 336 oe->next_flush = oe->max_timestamp; 337 338 oe->last_flush_type = how; 339 } 340 341 pr_oe_time(oe->next_flush, "next_flush - ordered_events__flush POST %s, nr_events %u\n", 342 str[how], oe->nr_events); 343 pr_oe_time(oe->last_flush, "last_flush\n"); 344 345 return err; 346 } 347 348 int ordered_events__flush(struct ordered_events *oe, enum oe_flush how) 349 { 350 return __ordered_events__flush(oe, how, 0); 351 } 352 353 int ordered_events__flush_time(struct ordered_events *oe, u64 timestamp) 354 { 355 return __ordered_events__flush(oe, OE_FLUSH__TIME, timestamp); 356 } 357 358 u64 ordered_events__first_time(struct ordered_events *oe) 359 { 360 struct ordered_event *event; 361 362 if (list_empty(&oe->events)) 363 return 0; 364 365 event = list_first_entry(&oe->events, struct ordered_event, list); 366 return event->timestamp; 367 } 368 369 void ordered_events__init(struct ordered_events *oe, ordered_events__deliver_t deliver, 370 void *data) 371 { 372 INIT_LIST_HEAD(&oe->events); 373 INIT_LIST_HEAD(&oe->cache); 374 INIT_LIST_HEAD(&oe->to_free); 375 oe->max_alloc_size = (u64) -1; 376 oe->cur_alloc_size = 0; 377 oe->deliver = deliver; 378 oe->data = data; 379 } 380 381 static void 382 ordered_events_buffer__free(struct ordered_events_buffer *buffer, 383 unsigned int max, struct ordered_events *oe) 384 { 385 if (oe->copy_on_queue) { 386 unsigned int i; 387 388 for (i = 0; i < max; i++) 389 __free_dup_event(oe, buffer->event[i].event); 390 } 391 392 free(buffer); 393 } 394 395 void ordered_events__free(struct ordered_events *oe) 396 { 397 struct ordered_events_buffer *buffer, *tmp; 398 399 if (list_empty(&oe->to_free)) 400 return; 401 402 /* 403 * Current buffer might not have all the events allocated 404 * yet, we need to free only allocated ones ... 405 */ 406 if (oe->buffer) { 407 list_del_init(&oe->buffer->list); 408 ordered_events_buffer__free(oe->buffer, oe->buffer_idx, oe); 409 } 410 411 /* ... and continue with the rest */ 412 list_for_each_entry_safe(buffer, tmp, &oe->to_free, list) { 413 list_del_init(&buffer->list); 414 ordered_events_buffer__free(buffer, MAX_SAMPLE_BUFFER, oe); 415 } 416 } 417 418 void ordered_events__reinit(struct ordered_events *oe) 419 { 420 ordered_events__deliver_t old_deliver = oe->deliver; 421 422 ordered_events__free(oe); 423 memset(oe, '\0', sizeof(*oe)); 424 ordered_events__init(oe, old_deliver, oe->data); 425 } 426