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