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