projects/linux·blob master · refs

1642 lines · 46.1 KiB

1// SPDX-License-Identifier: GPL-2.0
2/*
3 * C2C function model - function-level cacheline sharing analysis
4 *
5 * Displays a 3-level hierarchy showing which functions share cachelines:
6 * Level 1: Read-side functions sorted by Cycles % (estimated load cycles)
7 * Level 2: Functions sampled writing the shared lines read by level 1
8 * Level 3: The specific cachelines where the two functions contend
9 *
10 * Builds the hierarchy from the existing cacheline histograms
11 * (c2c_hist_entry->hists), reusing the shared c2c data structures.
12 */
13
14#include <errno.h>
15#include <inttypes.h>
16#include <stdlib.h>
17#include <string.h>
18#include <tools/libc_compat.h> /* reallocarray */
19#include <linux/list.h>
20#include <linux/rbtree.h>
21#include <linux/zalloc.h>
22
23#include "addr_location.h"
24#include "c2c.h"
25#include "cacheline.h"
26#include "debug.h"
27#include "dso.h"
28#include "hist.h"
29#include "map.h"
30#include "mem-events.h"
31#include "mem-info.h"
32#include "sort.h"
33#include "symbol.h"
34#include "thread.h"
35
36struct c2c_function_model {
37 struct c2c_hists function_hists;
38 /* Total estimated cycles across all level-1 entries. */
39 u64 total_cycles;
40 /* Source cacheline histograms; not owned here. */
41 struct c2c_hists *cl_hists;
42 /* --coalesce field list, used to require iaddr. */
43 const char *cl_sort;
44 /* Do not cap long symbol names. */
45 bool symbol_full;
46};
47
48static struct c2c_function_model c2c_ext;
49
50static inline u64 c2c_hitm_count(const struct c2c_stats *stats)
51{
52 return stats->tot_hitm;
53}
54
55static int64_t c2c_function_cmp(const struct map_symbol *left,
56 const struct map_symbol *right)
57{
58 const struct dso *left_dso = left->map ? map__dso(left->map) : NULL;
59 const struct dso *right_dso = right->map ? map__dso(right->map) : NULL;
60 int ret;
61
62 if (!left_dso || !right_dso) {
63 if (left_dso != right_dso)
64 return left_dso ? 1 : -1;
65 } else {
66 /*
67 * Use the same DSO name as _sort__dso_cmp() (short name unless
68 * verbose), so this matches the DSO comparison the level-1
69 * entries are deduplicated by; otherwise same-basename DSOs
70 * could be split or merged inconsistently across levels.
71 */
72 const char *left_name = verbose > 0 ?
73 dso__long_name(left_dso) : dso__short_name(left_dso);
74 const char *right_name = verbose > 0 ?
75 dso__long_name(right_dso) : dso__short_name(right_dso);
76
77 ret = strcmp(left_name, right_name);
78 if (ret)
79 return ret;
80 }
81
82 return _sort__sym_cmp(left->sym, right->sym);
83}
84
85static inline u64 hist_entry__iaddr(struct hist_entry *he)
86{
87 if (he->mem_info)
88 return mem_info__iaddr(he->mem_info)->addr;
89 return he->ip;
90}
91
92/*
93 * Hierarchy levels (by depth): L1 = read-side function, L2 = the writing
94 * function it contends with, L3 = the specific shared cacheline.
95 */
96static inline bool hist_entry__is_cacheline(struct hist_entry *he)
97{
98 return he->parent_he && he->parent_he->parent_he; /* level 3: cacheline */
99}
100
101/* Spaces of indent per hierarchy level, like the normal report view. */
102#define C2C_FUNC_INDENT 2
103
104/* Width of the folded-sign prefix ("%c ") each identity cell emits. */
105#define C2C_FUNC_FOLD_WIDTH 2
106
107/*
108 * Write he->depth levels of leading indentation into @buf, so lower-level
109 * entries are visually nested under their parent. Returns bytes written.
110 */
111static int hist_entry__indent(struct hist_entry *he, char *buf, size_t size)
112{
113 int indent = he->depth * C2C_FUNC_INDENT;
114
115 if (indent <= 0 || (size_t)indent >= size)
116 return 0;
117
118 return scnprintf(buf, size, "%*s", indent, "");
119}
120
121static int symbol_width(struct hists *hists, struct sort_entry *se)
122{
123 int width = hists__col_len(hists, se->se_width_idx);
124
125 /*
126 * Cap long symbol names as the cacheline view does. The stored column
127 * length is grown up front to fit the deepest, longest identity cell
128 * (including a level-3 cacheline address), so this cap never shrinks the
129 * column below what the cacheline address needs.
130 */
131 if (!c2c_ext.symbol_full && width > SYMBOL_WIDTH)
132 width = SYMBOL_WIDTH;
133
134 return width;
135}
136
137static struct c2c_dimension dim_symbol_view;
138
139/*
140 * c2c_width - Calculate width for a C2C column in function view
141 */
142static int c2c_width(struct perf_hpp_fmt *fmt,
143 struct perf_hpp *hpp __maybe_unused,
144 struct hists *hists)
145{
146 struct c2c_fmt *c2c_fmt;
147 struct c2c_dimension *dim;
148
149 c2c_fmt = container_of(fmt, struct c2c_fmt, fmt);
150 dim = c2c_fmt->dim;
151
152 if (dim == &dim_symbol_view)
153 return symbol_width(hists, dim->se);
154
155 return dim->se ? hists__col_len(hists, dim->se->se_width_idx) :
156 dim->width;
157}
158
159static int c2c_header(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
160 struct hists *hists, int line, int *span)
161{
162 struct c2c_fmt *c2c_fmt;
163 struct c2c_dimension *dim;
164 const char *text = NULL;
165 int width = c2c_width(fmt, hpp, hists);
166
167 c2c_fmt = container_of(fmt, struct c2c_fmt, fmt);
168 dim = c2c_fmt->dim;
169
170 if (dim->se) {
171 text = dim->header.line[line].text;
172 /* Use the last line from sort_entry if not defined. */
173 if (!text && line == hists->hpp_list->nr_header_lines - 1)
174 text = dim->se->se_header;
175 } else {
176 text = dim->header.line[line].text;
177
178 if (span) {
179 if (*span) {
180 (*span)--;
181 return 0;
182 }
183
184 *span = dim->header.line[line].span;
185 }
186 }
187
188 if (!text)
189 text = "";
190
191 return scnprintf(hpp->buf, hpp->size, "%*s", width, text);
192}
193
194/*
195 * Return the estimated total cycles for a c2c_hist_entry
196 * (rmt_hitm + lcl_hitm + rmt_peer + lcl_peer + other loads).
197 */
198static u64 c2c_hist_entry__cycles(struct c2c_hist_entry *c2c_he)
199{
200 struct compute_stats *cs = &c2c_he->cstats;
201 double cycles = 0;
202
203 /*
204 * compute_stats() in builtin-c2c.c routes each load sample into exactly
205 * one cstats bucket (rmt_hitm, lcl_hitm, rmt_peer, lcl_peer or plain
206 * load), so each bucket's cycle total is its mean times its own sample
207 * count. Summing the per-bucket totals avoids both dropping peer-snoop
208 * cycles and double counting a sample that carries several data-source
209 * flags (e.g. Arm SPE sets HITM and PEER on the same load), which would
210 * happen if the mean were multiplied by the non-exclusive stats counts.
211 */
212 cycles += avg_stats(&cs->rmt_hitm) * cs->rmt_hitm.n;
213 cycles += avg_stats(&cs->lcl_hitm) * cs->lcl_hitm.n;
214 cycles += avg_stats(&cs->rmt_peer) * cs->rmt_peer.n;
215 cycles += avg_stats(&cs->lcl_peer) * cs->lcl_peer.n;
216 cycles += avg_stats(&cs->load) * cs->load.n;
217
218 return (u64)cycles;
219}
220
221/* Sum c2c_hist_entry__cycles() across all level-1 entries. */
222static u64 c2c_ext__total_cycles(void)
223{
224 struct rb_node *nd;
225 u64 total = 0;
226
227 for (nd = rb_first_cached(&c2c_ext.function_hists.hists.entries); nd;
228 nd = rb_next(nd)) {
229 struct c2c_hist_entry *c2c_he =
230 rb_entry(nd, struct c2c_hist_entry, he.rb_node);
231
232 total += c2c_hist_entry__cycles(c2c_he);
233 }
234 return total;
235}
236
237/*
238 * Store count shown in the column: a level-3 cacheline leaf shows its parent
239 * level-2 writer's stores on that line, not all stores on the line. A level-2
240 * writer shows the sum across its level-3 cachelines. A level-1 reader shows
241 * the sum across all included writers on the cachelines it reads; this is not
242 * the reader function's own store count and is not additive across readers.
243 */
244static u64 hist_entry__displayed_stores(struct hist_entry *he)
245{
246 struct c2c_hist_entry *c2c_he = container_of(he, struct c2c_hist_entry, he);
247 struct rb_node *nd;
248 u64 stores = 0;
249
250 /* Level-2/3 entries already aggregate the stores they represent. */
251 if (he->parent_he)
252 return c2c_he->stats.store;
253
254 for (nd = rb_first_cached(&he->hroot_out); nd; nd = rb_next(nd)) {
255 struct c2c_hist_entry *child_c2c =
256 rb_entry(nd, struct c2c_hist_entry, he.rb_node);
257 stores += child_c2c->stats.store;
258 }
259 return stores;
260}
261
262static int
263total_stores_entry(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
264 struct hist_entry *he)
265{
266 int width = c2c_width(fmt, hpp, he->hists);
267 u64 total = hist_entry__displayed_stores(he);
268
269 return scnprintf(hpp->buf, hpp->size, "%*" PRIu64, width, total);
270}
271
272/*
273 * symbol_view_entry - Render the unified, indented identity column.
274 *
275 * All three levels share this single column so the hierarchy reads top-down
276 * with progressive indentation, like the normal report hierarchy view. It is
277 * a function-centric view with no dedicated code-address column. Verbose
278 * function rows can still include a representative address:
279 * L1 read-side function: "- [k] cpupri_set"
280 * L2 writing function: " - [k] pull_rt_task"
281 * L3 shared cacheline: " 0xff2d0082809da080"
282 */
283static int
284symbol_view_entry(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
285 struct hist_entry *he)
286{
287 int width = c2c_width(fmt, hpp, he->hists);
288 int text_width;
289 int ret;
290 char folded_sign;
291
292 ret = hist_entry__indent(he, hpp->buf, hpp->size);
293
294 folded_sign = he->has_children ? (he->unfolded ? '-' : '+') : ' ';
295 ret += scnprintf(hpp->buf + ret, hpp->size - ret, "%c ", folded_sign);
296
297 text_width = width - ret;
298 if (text_width <= 0)
299 return ret;
300
301 if (hist_entry__is_cacheline(he)) {
302 /* Level 3: the shared cacheline address. */
303 u64 addr = he->mem_info ?
304 cl_address(mem_info__daddr(he->mem_info)->addr, chk_double_cl) : 0;
305 char symbuf[32];
306
307 scnprintf(symbuf, sizeof(symbuf), "0x%" PRIx64, addr);
308 ret += scnprintf(hpp->buf + ret, hpp->size - ret, "%-*.*s",
309 text_width, text_width, symbuf);
310 } else {
311 /* Level 1 and level 2 are both functions. */
312 size_t cell_size;
313 int len;
314
315 if ((size_t)ret >= hpp->size)
316 return ret;
317
318 cell_size = min_t(size_t, hpp->size - ret,
319 (size_t)text_width + 1);
320 len = sort_sym.se_snprintf(he, hpp->buf + ret, cell_size,
321 text_width);
322 /*
323 * se_snprintf() accumulates repsep_snprintf() calls, which cap
324 * their return at the remaining size - 1 rather than reporting
325 * what the format would have needed, so len stays below
326 * cell_size. Clamp anyway so ret cannot leave hpp->buf.
327 */
328 if (len < 0)
329 len = 0;
330 else
331 len = min_t(size_t, len, cell_size - 1);
332
333 ret += len;
334 if (len < text_width)
335 ret += scnprintf(hpp->buf + ret, hpp->size - ret, "%*s",
336 text_width - len, "");
337 }
338
339 return ret;
340}
341
342/*
343 * cycles_percent_entry - Render cycles percentage column
344 */
345static int
346cycles_percent_entry(struct perf_hpp_fmt *fmt, struct perf_hpp *hpp,
347 struct hist_entry *he)
348{
349 struct c2c_hist_entry *c2c_he;
350 int width = c2c_width(fmt, hpp, he->hists);
351 u64 fn_cycles, total_cycles;
352 char folded_sign;
353 double pct;
354 int ret, pct_width;
355
356 /* Hide Cycles Percent for child functions and cachelines. */
357 if (he->parent_he)
358 return scnprintf(hpp->buf, hpp->size, "%*s", width, "");
359
360 c2c_he = container_of(he, struct c2c_hist_entry, he);
361 fn_cycles = c2c_hist_entry__cycles(c2c_he);
362 /* Populated by c2c_function__build() once the L1 tree is built. */
363 total_cycles = c2c_ext.total_cycles;
364 pct = total_cycles > 0 ? (double)fn_cycles / total_cycles * 100.0 : 0.0;
365
366 /* Add folded sign only for level-1 entries */
367 folded_sign = he->has_children ? (he->unfolded ? '-' : '+') : ' ';
368 ret = scnprintf(hpp->buf, hpp->size, "%c ", folded_sign);
369
370 pct_width = width - ret;
371 if (pct_width <= 0)
372 return ret;
373 ret += scnprintf(hpp->buf + ret, hpp->size - ret, "%*.2f%%", pct_width - 1, pct);
374 return ret;
375}
376
377/*
378 * cycles_percent_cmp - Comparison function for cycles percentage sorting
379 */
380static int64_t
381cycles_percent_cmp(struct perf_hpp_fmt *fmt __maybe_unused,
382 struct hist_entry *left, struct hist_entry *right)
383{
384 struct c2c_hist_entry *c2c_left = container_of(left, struct c2c_hist_entry, he);
385 struct c2c_hist_entry *c2c_right = container_of(right, struct c2c_hist_entry, he);
386 u64 cycles_left, cycles_right;
387
388 /* Cycles Percent is only shown for level-1 entries; others compare equal. */
389 if (left->parent_he || right->parent_he)
390 return 0;
391
392 cycles_left = c2c_hist_entry__cycles(c2c_left);
393 cycles_right = c2c_hist_entry__cycles(c2c_right);
394
395 return (cycles_left > cycles_right) - (cycles_left < cycles_right);
396}
397
398/*
399 * total_stores_cmp - Comparison function for total stores sorting
400 */
401static int64_t
402total_stores_cmp(struct perf_hpp_fmt *fmt __maybe_unused,
403 struct hist_entry *left, struct hist_entry *right)
404{
405 u64 left_store = hist_entry__displayed_stores(left);
406 u64 right_store = hist_entry__displayed_stores(right);
407
408 return (left_store > right_store) - (left_store < right_store);
409}
410
411/*
412 * Function view dimensions
413 */
414static struct c2c_dimension dim_cycles_percent = {
415 .header = HEADER_BOTH("Cycles", "%"),
416 .name = "cycles_percent",
417 .cmp = cycles_percent_cmp,
418 .entry = cycles_percent_entry,
419 .width = 9,
420};
421
422static struct c2c_dimension dim_total_stores = {
423 .header = HEADER_BOTH("Store", "count"),
424 .name = "total_stores",
425 .cmp = total_stores_cmp,
426 .entry = total_stores_entry,
427 .width = 7,
428};
429
430static struct c2c_dimension dim_symbol_view = {
431 .header = HEADER_LOW("Function / Contending function / Cacheline"),
432 .name = "symbol_view",
433 .se = &sort_sym,
434 .entry = symbol_view_entry,
435 .width = SYMBOL_WIDTH,
436};
437
438static struct c2c_dimension *function_view_dimensions[] = {
439 &dim_cycles_percent,
440 &dim_total_stores,
441 &dim_symbol_view,
442 NULL,
443};
444
445static struct c2c_dimension *get_function_dimension(const char *name)
446{
447 unsigned int i;
448
449 for (i = 0; function_view_dimensions[i]; i++) {
450 struct c2c_dimension *dim = function_view_dimensions[i];
451
452 if (!strcmp(dim->name, name))
453 return dim;
454 }
455
456 return NULL;
457}
458
459/* Wrappers so sort_entry-backed dimensions sort/collapse via their se. */
460static int64_t c2c_se_cmp(struct perf_hpp_fmt *fmt,
461 struct hist_entry *a, struct hist_entry *b)
462{
463 struct c2c_fmt *c2c_fmt = container_of(fmt, struct c2c_fmt, fmt);
464 struct c2c_dimension *dim = c2c_fmt->dim;
465
466 return dim->se->se_cmp(a, b);
467}
468
469static int64_t c2c_se_collapse(struct perf_hpp_fmt *fmt,
470 struct hist_entry *a, struct hist_entry *b)
471{
472 struct c2c_fmt *c2c_fmt = container_of(fmt, struct c2c_fmt, fmt);
473 struct c2c_dimension *dim = c2c_fmt->dim;
474 int64_t (*collapse_fn)(struct hist_entry *a, struct hist_entry *b);
475
476 collapse_fn = dim->se->se_collapse ?: dim->se->se_cmp;
477 return collapse_fn(a, b);
478}
479
480static int64_t c2c_se_sort(struct perf_hpp_fmt *fmt,
481 struct hist_entry *a, struct hist_entry *b)
482{
483 struct c2c_fmt *c2c_fmt = container_of(fmt, struct c2c_fmt, fmt);
484 struct c2c_dimension *dim = c2c_fmt->dim;
485 int64_t (*sort_fn)(struct hist_entry *a, struct hist_entry *b);
486
487 sort_fn = dim->se->se_sort ?: dim->se->se_cmp;
488 return sort_fn(a, b);
489}
490
491/*
492 * Build the c2c_fmt for @name. Returns:
493 * 0 and *fmtp set on success;
494 * -ENOENT and *fmtp = NULL if @name is not a function-view dimension;
495 * -ENOMEM if allocation failed (distinct from -ENOENT so
496 * the caller does not misreport it as an
497 * "invalid field").
498 */
499static int get_function_format(const char *name, struct c2c_fmt **fmtp)
500{
501 struct c2c_dimension *dim = get_function_dimension(name);
502 struct c2c_fmt *c2c_fmt;
503 struct perf_hpp_fmt *fmt;
504
505 *fmtp = NULL;
506
507 if (!dim)
508 return -ENOENT;
509
510 c2c_fmt = zalloc(sizeof(*c2c_fmt));
511 if (!c2c_fmt)
512 return -ENOMEM;
513
514 fmt = &c2c_fmt->fmt;
515
516 c2c_fmt->dim = dim;
517 INIT_LIST_HEAD(&fmt->list);
518 INIT_LIST_HEAD(&fmt->sort_list);
519
520 fmt->cmp = dim->se ? c2c_se_cmp : dim->cmp;
521 fmt->sort = dim->se ? c2c_se_sort : dim->cmp;
522 fmt->color = dim->color;
523 fmt->entry = dim->entry;
524 fmt->header = c2c_header;
525 fmt->width = c2c_width;
526 fmt->collapse = dim->se ? c2c_se_collapse : dim->cmp;
527 fmt->equal = c2c_fmt_equal;
528 fmt->free = c2c_fmt_free;
529
530 *fmtp = c2c_fmt;
531 return 0;
532}
533
534static int
535c2c_function_hists__init_output(struct perf_hpp_list *hpp_list, char *name,
536 struct perf_env *env __maybe_unused)
537{
538 struct c2c_fmt *c2c_fmt;
539 int ret;
540
541 ret = get_function_format(name, &c2c_fmt);
542 if (ret == -ENOMEM)
543 return ret;
544 /* The function view only accepts its own dimensions. */
545 if (ret == -ENOENT)
546 return -EINVAL;
547
548 /*
549 * Mark symbol-backed columns so hists__has(hists, sym) is correct.
550 * Only dim_symbol_view carries a sort_entry (.se); the function
551 * view's field strings are fixed and always include symbol_view, so
552 * this single check is sufficient (unlike the user-configurable
553 * cacheline view, which must also test dim_iaddr).
554 */
555 if (c2c_fmt->dim->se == &sort_sym)
556 hpp_list->sym = 1;
557
558 perf_hpp_list__column_register(hpp_list, &c2c_fmt->fmt);
559 return 0;
560}
561
562static int
563c2c_function_hists__init_sort(struct perf_hpp_list *hpp_list, char *name,
564 struct perf_env *env __maybe_unused)
565{
566 struct c2c_fmt *c2c_fmt;
567 int ret;
568
569 ret = get_function_format(name, &c2c_fmt);
570 if (ret == -ENOMEM)
571 return ret;
572 /* The function view only accepts its own dimensions. */
573 if (ret == -ENOENT)
574 return -EINVAL;
575
576 /* Mark symbol-backed sort keys so hists__has(hists, sym) is correct. */
577 if (c2c_fmt->dim->se == &sort_sym)
578 hpp_list->sym = 1;
579
580 perf_hpp_list__register_sort_field(hpp_list, &c2c_fmt->fmt);
581 return 0;
582}
583
584typedef int (*hpp_list_add_fn)(struct perf_hpp_list *hpp_list, char *name,
585 struct perf_env *env);
586
587static int function_hpp_list__add_tokens(struct perf_hpp_list *hpp_list, char *list,
588 struct perf_env *env, hpp_list_add_fn add)
589{
590 char *tok, *tmp;
591 int ret;
592
593 if (!list)
594 return 0;
595
596 for (tok = strtok_r(list, ", ", &tmp); tok; tok = strtok_r(NULL, ", ", &tmp)) {
597 ret = add(hpp_list, tok, env);
598 if (ret) {
599 if (ret == -EINVAL || ret == -ESRCH)
600 pr_err("Invalid c2c function-view field: %s\n", tok);
601 return ret;
602 }
603 }
604 return 0;
605}
606
607/*
608 * Append the function view's sort keys to its own output fields, mirroring
609 * perf_hpp__setup_output_field() but on the local @list. The shared helper
610 * registers onto the global perf_hpp_list, which would leave this local list
611 * without output columns, so the function view keeps its own copy here.
612 */
613static void c2c_function_hists__setup_output_field(struct perf_hpp_list *list)
614{
615 struct perf_hpp_fmt *fmt;
616
617 perf_hpp_list__for_each_sort_list(list, fmt) {
618 struct perf_hpp_fmt *pos;
619
620 if (!fmt->entry && !fmt->color)
621 continue;
622
623 perf_hpp_list__for_each_format(list, pos) {
624 if (c2c_fmt_equal(fmt, pos))
625 goto next;
626 }
627
628 perf_hpp_list__column_register(list, fmt);
629next:
630 continue;
631 }
632}
633
634static int
635function_hpp_list__parse(struct perf_hpp_list *hpp_list,
636 const char *output_str,
637 const char *sort_str,
638 struct perf_env *env)
639{
640 char *output = output_str ? strdup(output_str) : NULL;
641 char *sort = sort_str ? strdup(sort_str) : NULL;
642 int ret = 0;
643
644 if ((output_str && !output) || (sort_str && !sort)) {
645 ret = -ENOMEM;
646 goto out;
647 }
648
649 ret = function_hpp_list__add_tokens(hpp_list, output, env,
650 c2c_function_hists__init_output);
651 if (ret)
652 goto out;
653
654 ret = function_hpp_list__add_tokens(hpp_list, sort, env,
655 c2c_function_hists__init_sort);
656 if (ret)
657 goto out;
658
659 c2c_function_hists__setup_output_field(hpp_list);
660out:
661 if (ret)
662 perf_hpp__reset_output_field(hpp_list);
663 free(output);
664 free(sort);
665 return ret;
666}
667
668static int
669c2c_function_hists__init(struct c2c_hists *hists,
670 const char *sort,
671 int nr_header_lines,
672 struct perf_env *env)
673{
674 __hists__init(&hists->hists, &hists->list);
675
676 perf_hpp_list__init(&hists->list);
677
678 hists->list.nr_header_lines = nr_header_lines;
679
680 return function_hpp_list__parse(&hists->list, /*output=*/NULL, sort, env);
681}
682
683static int
684c2c_function_hists__reinit(struct c2c_hists *c2c_hists,
685 const char *output,
686 const char *sort,
687 struct perf_env *env)
688{
689 int nr_header_lines = c2c_hists->list.nr_header_lines;
690
691 perf_hpp__reset_output_field(&c2c_hists->list);
692
693 /* Clear stale state flags so a different output/sort set starts fresh. */
694 c2c_hists->list.need_collapse = 0;
695 c2c_hists->list.parent = 0;
696 c2c_hists->list.sym = 0;
697 c2c_hists->list.dso = 0;
698 c2c_hists->list.socket = 0;
699 c2c_hists->list.thread = 0;
700 c2c_hists->list.comm = 0;
701 c2c_hists->list.comm_nodigit = 0;
702 c2c_hists->list.nr_header_lines = nr_header_lines;
703
704 return function_hpp_list__parse(&c2c_hists->list, output, sort, env);
705}
706
707/* Welford online merge of two "stats" (from util/stat.h) accumulators. */
708static void c2c_stats_merge(struct stats *dest, const struct stats *src)
709{
710 double delta;
711
712 if (src->n == 0)
713 return;
714
715 if (dest->n == 0) {
716 *dest = *src;
717 return;
718 }
719
720 delta = src->mean - dest->mean;
721 dest->M2 += src->M2 + delta * delta * dest->n * src->n / (dest->n + src->n);
722 dest->mean = (dest->mean * dest->n + src->mean * src->n) / (dest->n + src->n);
723 dest->n += src->n;
724
725 /* Update min/max */
726 if (src->max > dest->max)
727 dest->max = src->max;
728 if (src->min < dest->min)
729 dest->min = src->min;
730}
731
732/* Merge compute_stats during function aggregation. */
733static void c2c_add_cstats(struct compute_stats *dest,
734 const struct compute_stats *src)
735{
736 c2c_stats_merge(&dest->rmt_hitm, &src->rmt_hitm);
737 c2c_stats_merge(&dest->lcl_hitm, &src->lcl_hitm);
738 c2c_stats_merge(&dest->rmt_peer, &src->rmt_peer);
739 c2c_stats_merge(&dest->lcl_peer, &src->lcl_peer);
740 c2c_stats_merge(&dest->load, &src->load);
741}
742
743static bool hist_entry__add_c2c_stats(struct hist_entry *he,
744 const struct c2c_stats *stats)
745{
746 u64 nr_events = c2c_hitm_count(stats) + stats->rmt_peer + stats->lcl_peer;
747 u64 weight1 = c2c_hitm_count(stats);
748
749 /*
750 * Allocate before touching he->stat, so a failure here leaves the
751 * entry unmodified and the caller can bail out without having
752 * half-updated the statistics.
753 */
754 if (symbol_conf.cumulate_callchain && !he->stat_acc) {
755 he->stat_acc = calloc(1, sizeof(struct he_stat));
756 if (!he->stat_acc)
757 return false;
758 }
759
760 he->stat.nr_events += nr_events;
761 he->stat.period += nr_events;
762 he->stat.weight1 += weight1;
763
764 if (!symbol_conf.cumulate_callchain)
765 return true;
766
767 he->stat_acc->nr_events += nr_events;
768 he->stat_acc->period += nr_events;
769 he->stat_acc->weight1 += weight1;
770
771 return true;
772}
773
774static void c2c_he__free_hierarchy(struct hist_entry *he);
775
776/*
777 * Free a function-view histogram entry (hist_entry_ops::free).
778 */
779static void c2c_function_he_free(void *ptr)
780{
781 struct hist_entry *he = ptr;
782 struct c2c_hist_entry *c2c_he;
783
784 c2c_he = container_of(he, struct c2c_hist_entry, he);
785
786 if (c2c_he->hists) {
787 perf_hpp__reset_output_field(&c2c_he->hists->list);
788 hists__delete_all_entries(&c2c_he->hists->hists);
789 zfree(&c2c_he->hists);
790 }
791
792 c2c_he__free_hierarchy(he);
793
794 free(c2c_he);
795}
796
797static void c2c_he__free_hierarchy(struct hist_entry *he)
798{
799 struct rb_node *nd;
800 struct hist_entry *child_he;
801
802 /*
803 * A leaf entry stores its callchains in the sorted_chain member, which
804 * shares a union with the hroot_in/hroot_out child trees, so its
805 * hroot_out is not a valid subtree to walk. Leaf entries never have a
806 * child hierarchy here, so stop before touching hroot_out.
807 */
808 if (he->leaf)
809 return;
810
811 if (RB_EMPTY_ROOT(&he->hroot_out.rb_root))
812 return;
813
814 nd = rb_first_cached(&he->hroot_out);
815 while (nd) {
816 struct rb_node *next = rb_next(nd);
817
818 child_he = rb_entry(nd, struct hist_entry, rb_node);
819 rb_erase_cached(&child_he->rb_node, &he->hroot_out);
820 hist_entry__delete(child_he);
821
822 nd = next;
823 }
824
825 /* All children erased; clear the tree (and its cached leftmost). */
826 he->hroot_out = RB_ROOT_CACHED;
827}
828
829/*
830 * Drop level-2 writing functions that carry no stores or
831 * no cacheline children. Writers are only added when they store into a shared
832 * line, so this is mainly a safety net. Returns the number of surviving
833 * writers.
834 */
835static int c2c_he__prune_empty_writers(struct hist_entry *l1_he)
836{
837 struct rb_node *nd;
838 int surviving = 0;
839
840 if (!l1_he->has_children)
841 return 0;
842
843 nd = rb_first_cached(&l1_he->hroot_out);
844 while (nd) {
845 struct rb_node *next = rb_next(nd);
846 struct hist_entry *l2_he = rb_entry(nd, struct hist_entry, rb_node);
847
848 if (l2_he->has_children && hist_entry__displayed_stores(l2_he) > 0) {
849 surviving++;
850 } else {
851 rb_erase_cached(&l2_he->rb_node, &l1_he->hroot_out);
852 hist_entry__delete(l2_he);
853 }
854 nd = next;
855 }
856
857 if (!surviving) {
858 l1_he->hroot_out = RB_ROOT_CACHED;
859 l1_he->has_children = false;
860 l1_he->unfolded = false;
861 }
862 return surviving;
863}
864
865static void *c2c_function_he_zalloc(size_t size)
866{
867 struct c2c_hist_entry *c2c_he = zalloc(sizeof(*c2c_he) + size);
868
869 if (!c2c_he)
870 return NULL;
871
872 init_stats(&c2c_he->cstats.lcl_hitm);
873 init_stats(&c2c_he->cstats.rmt_hitm);
874 init_stats(&c2c_he->cstats.lcl_peer);
875 init_stats(&c2c_he->cstats.rmt_peer);
876 init_stats(&c2c_he->cstats.load);
877
878 return &c2c_he->he;
879}
880
881/* Entry operations for function view */
882static struct hist_entry_ops c2c_function_entry_ops = {
883 .new = c2c_function_he_zalloc,
884 .free = c2c_function_he_free,
885};
886
887static struct c2c_hist_entry *
888c2c_child_entry__alloc(struct hist_entry *parent_he, struct hist_entry *src_he,
889 int depth, u64 ip)
890{
891 struct c2c_hist_entry *child_c2c;
892 struct hist_entry *child_he;
893
894 /* Function-view children never own or display callchains. */
895 child_he = c2c_function_he_zalloc(0);
896 if (!child_he)
897 return NULL;
898
899 child_c2c = container_of(child_he, struct c2c_hist_entry, he);
900 child_he->ops = &c2c_function_entry_ops;
901 map_symbol__copy(&child_he->ms, &src_he->ms);
902
903 if (src_he->mem_info) {
904 child_he->mem_info = mem_info__clone(src_he->mem_info);
905 if (!child_he->mem_info)
906 goto out_free;
907 }
908
909 child_he->thread = thread__get(src_he->thread);
910 child_he->cpumode = src_he->cpumode;
911 child_he->cpu = src_he->cpu;
912 child_he->socket = src_he->socket;
913 child_he->level = src_he->level;
914 child_he->ip = ip;
915
916 child_he->parent_he = parent_he;
917 child_he->depth = depth;
918 child_he->leaf = (depth >= 2);
919 child_he->hists = &c2c_ext.function_hists.hists;
920 child_he->filtered = false;
921 child_he->unfolded = false;
922 child_he->has_children = false;
923 child_he->has_no_entry = false;
924 child_he->nr_rows = 0;
925 child_he->row_offset = 0;
926
927 memset(&child_he->stat, 0, sizeof(child_he->stat));
928 child_he->hroot_in = RB_ROOT_CACHED;
929 child_he->hroot_out = RB_ROOT_CACHED;
930 INIT_LIST_HEAD(&child_he->pairs.node);
931 child_he->hpp_list = &c2c_ext.function_hists.list;
932 if (symbol_conf.cumulate_callchain) {
933 child_he->stat_acc = calloc(1, sizeof(struct he_stat));
934 if (!child_he->stat_acc)
935 goto out_free;
936 }
937
938 return child_c2c;
939
940out_free:
941 hist_entry__delete(child_he);
942 return NULL;
943}
944
945static void
946c2c_child_entry__insert(struct hist_entry *parent_he, struct hist_entry *child_he,
947 struct rb_node **p, struct rb_node *rb_parent, bool leftmost)
948{
949 rb_link_node(&child_he->rb_node, rb_parent, p);
950 rb_insert_color_cached(&child_he->rb_node, &parent_he->hroot_out, leftmost);
951
952 parent_he->has_children = true;
953 parent_he->leaf = false;
954}
955
956static struct hist_entry *
957c2c_function_hists__level1_entry(struct symbol *sym,
958 struct hist_entry *detail_he,
959 struct thread *synthetic_thread)
960{
961 struct addr_location al;
962 struct perf_sample sample = {};
963 struct mem_info *mi;
964 struct hist_entry *he;
965 /*
966 * Key the level-1 entry by the function, not by a specific code
967 * address: use the symbol start so every instruction address inside
968 * the same function collapses into one entry. This makes level 1 a
969 * true "function view" rather than a per-code-address view.
970 */
971 u64 sym_start = (sym && detail_he->ms.map) ?
972 map__unmap_ip(detail_he->ms.map, sym->start) : detail_he->ip;
973
974 mi = mem_info__new();
975 if (!mi)
976 return NULL;
977
978 mem_info__iaddr(mi)->addr = sym_start;
979 /* mem_info__put() will map_symbol__exit() these, so take refs. */
980 mem_info__iaddr(mi)->ms.thread = thread__get(detail_he->ms.thread);
981 mem_info__iaddr(mi)->ms.map = map__get(detail_he->ms.map);
982 mem_info__iaddr(mi)->ms.sym = sym;
983 mem_info__daddr(mi)->addr = 0;
984
985 addr_location__init(&al);
986 al.thread = thread__get(synthetic_thread);
987 al.map = map__get(detail_he->ms.map);
988 al.sym = sym;
989 al.addr = sym_start;
990 al.level = detail_he->level;
991 al.cpumode = detail_he->cpumode;
992 al.cpu = 0;
993 al.socket = 0;
994 al.filtered = 0;
995 al.latency = 0;
996
997 /*
998 * Synthetic sample: period/weight are placeholders only. The real
999 * c2c counters live in c2c_hist_entry::stats and are added via
1000 * hist_entry__add_c2c_stats(); no function-view column or sort key
1001 * reads he->stat.period/nr_events, so the +1 that __hists__add_entry()
1002 * accrues on each dedup hit has no effect on what is displayed.
1003 */
1004 sample.period = 1;
1005 sample.weight = 1;
1006 sample.ip = sym_start;
1007 sample.pid = thread__pid(synthetic_thread);
1008 sample.tid = thread__tid(synthetic_thread);
1009 sample.cpu = 0;
1010
1011 /* Add entry - histogram handles dedup */
1012 he = hists__add_entry_ops(&c2c_ext.function_hists.hists,
1013 &c2c_function_entry_ops,
1014 &al, NULL, NULL, mi,
1015 NULL, &sample, true);
1016
1017 addr_location__exit(&al);
1018 mem_info__put(mi);
1019
1020 if (he)
1021 he->hpp_list = &c2c_ext.function_hists.list;
1022
1023 return he;
1024}
1025
1026/*
1027 * Level 2: a function that writes a cacheline the level-1 function reads,
1028 * keyed by the DSO display name and symbol, consistently with perf's symbol
1029 * sort semantics. All code addresses and cachelines for the same writer
1030 * function aggregate into one row.
1031 */
1032static struct c2c_hist_entry *
1033c2c_function_hists__level2_entry(struct c2c_hist_entry *level1_c2c,
1034 struct symbol *sym, struct hist_entry *detail_he)
1035{
1036 struct hist_entry *level1_he = &level1_c2c->he;
1037 struct rb_node **p = &level1_he->hroot_out.rb_root.rb_node;
1038 struct rb_node *parent = NULL;
1039 struct c2c_hist_entry *level2_c2c;
1040 bool leftmost = true;
1041
1042 while (*p) {
1043 struct hist_entry *iter = rb_entry(*p, struct hist_entry, rb_node);
1044 struct map_symbol key = detail_he->ms;
1045 int64_t cmp;
1046
1047 key.sym = sym;
1048 parent = *p;
1049 cmp = c2c_function_cmp(&key, &iter->ms);
1050
1051 if (cmp < 0) {
1052 p = &parent->rb_left;
1053 } else if (cmp > 0) {
1054 p = &parent->rb_right;
1055 leftmost = false;
1056 } else {
1057 return container_of(iter, struct c2c_hist_entry, he);
1058 }
1059 }
1060
1061 /* Key by the function symbol start so all code addresses collapse. */
1062 level2_c2c = c2c_child_entry__alloc(level1_he, detail_he, 1,
1063 (sym && detail_he->ms.map) ?
1064 map__unmap_ip(detail_he->ms.map, sym->start) :
1065 hist_entry__iaddr(detail_he));
1066 if (!level2_c2c)
1067 return NULL;
1068
1069 /* Key this level by the looked-up symbol, not detail_he's. */
1070 level2_c2c->he.ms.sym = sym;
1071 if (level2_c2c->he.mem_info)
1072 mem_info__iaddr(level2_c2c->he.mem_info)->ms.sym = sym;
1073
1074 c2c_child_entry__insert(level1_he, &level2_c2c->he, p, parent, leftmost);
1075
1076 return level2_c2c;
1077}
1078
1079/* Level 3: one source cacheline where the L1/L2 functions contend. */
1080static struct c2c_hist_entry *
1081c2c_function_hists__level3_entry(struct c2c_hist_entry *level2_c2c,
1082 struct c2c_hist_entry *cacheline_src_he)
1083{
1084 struct hist_entry *level2_he = &level2_c2c->he;
1085 struct rb_node **p = &level2_he->hroot_out.rb_root.rb_node;
1086 struct rb_node *parent = NULL;
1087 struct c2c_hist_entry *level3_c2c;
1088 bool leftmost = true;
1089
1090 while (*p) {
1091 struct c2c_hist_entry *iter_c2c =
1092 rb_entry(*p, struct c2c_hist_entry, he.rb_node);
1093
1094 parent = *p;
1095 if (cacheline_src_he->cacheline_idx < iter_c2c->cacheline_idx) {
1096 p = &parent->rb_left;
1097 } else if (cacheline_src_he->cacheline_idx > iter_c2c->cacheline_idx) {
1098 p = &parent->rb_right;
1099 leftmost = false;
1100 } else {
1101 return iter_c2c;
1102 }
1103 }
1104
1105 level3_c2c = c2c_child_entry__alloc(level2_he, &cacheline_src_he->he, 2,
1106 hist_entry__iaddr(&cacheline_src_he->he));
1107 if (!level3_c2c)
1108 return NULL;
1109 level3_c2c->cacheline_idx = cacheline_src_he->cacheline_idx;
1110
1111 c2c_child_entry__insert(level2_he, &level3_c2c->he, p, parent, leftmost);
1112
1113 return level3_c2c;
1114}
1115
1116struct hist_entry *c2c_function__find_cacheline(struct hist_entry *he_selection)
1117{
1118 struct c2c_hist_entry *c2c_he;
1119 struct rb_node *nd;
1120
1121 if (!c2c_ext.cl_hists || !he_selection || !he_selection->parent_he ||
1122 !he_selection->parent_he->parent_he)
1123 return NULL;
1124
1125 c2c_he = container_of(he_selection, struct c2c_hist_entry, he);
1126
1127 for (nd = rb_first_cached(&c2c_ext.cl_hists->hists.entries); nd;
1128 nd = rb_next(nd)) {
1129 struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
1130 struct c2c_hist_entry *cacheline_he;
1131
1132 if (he->filtered)
1133 continue;
1134
1135 cacheline_he = container_of(he, struct c2c_hist_entry, he);
1136 if (cacheline_he->hists &&
1137 cacheline_he->cacheline_idx == c2c_he->cacheline_idx)
1138 return he;
1139 }
1140
1141 return NULL;
1142}
1143
1144/*
1145 * Re-sort child entries of @parent_he by total store count, descending.
1146 */
1147static void c2c_he__resort_by_stores(struct hist_entry *parent_he)
1148{
1149 struct rb_root_cached new_root = RB_ROOT_CACHED;
1150 struct rb_node *nd;
1151
1152 if (!parent_he->has_children)
1153 return;
1154
1155 /* Extract all nodes and re-insert sorted by displayed store count */
1156 while ((nd = rb_first_cached(&parent_he->hroot_out))) {
1157 struct hist_entry *he = rb_entry(nd, struct hist_entry, rb_node);
1158 u64 he_store = hist_entry__displayed_stores(he);
1159 struct rb_node **p = &new_root.rb_root.rb_node;
1160 struct rb_node *parent = NULL;
1161 bool leftmost = true;
1162 int cmp;
1163
1164 /* Remove from current tree */
1165 rb_erase_cached(&he->rb_node, &parent_he->hroot_out);
1166
1167 /*
1168 * Insert sorted by store count, descending. Use the displayed
1169 * store count so a level-1 function and level-2 writer (whose own
1170 * stats.store is 0 / partial) sort by the aggregated write traffic
1171 * beneath them, not by their own store field.
1172 */
1173 while (*p) {
1174 struct hist_entry *iter = rb_entry(*p, struct hist_entry, rb_node);
1175 u64 iter_store = hist_entry__displayed_stores(iter);
1176
1177 parent = *p;
1178 if (he_store != iter_store) {
1179 cmp = he_store > iter_store ? -1 : 1;
1180 } else {
1181 /* Stable tie-break: instruction address, name, then cacheline. */
1182 u64 a = hist_entry__iaddr(he), b = hist_entry__iaddr(iter);
1183
1184 if (a != b)
1185 cmp = a < b ? -1 : 1;
1186 else if (he->ms.sym && iter->ms.sym)
1187 cmp = strcmp(he->ms.sym->name,
1188 iter->ms.sym->name);
1189 else
1190 cmp = (iter->ms.sym ? 1 : 0) - (he->ms.sym ? 1 : 0);
1191
1192 if (!cmp) {
1193 struct c2c_hist_entry *he_c2c;
1194 struct c2c_hist_entry *iter_c2c;
1195
1196 he_c2c = container_of(he, struct c2c_hist_entry, he);
1197 iter_c2c = container_of(iter, struct c2c_hist_entry, he);
1198 if (he_c2c->cacheline_idx != iter_c2c->cacheline_idx)
1199 cmp = he_c2c->cacheline_idx <
1200 iter_c2c->cacheline_idx ? -1 : 1;
1201 }
1202 }
1203
1204 if (cmp < 0) {
1205 p = &parent->rb_left;
1206 } else {
1207 p = &parent->rb_right;
1208 leftmost = false;
1209 }
1210 }
1211
1212 rb_link_node(&he->rb_node, parent, p);
1213 rb_insert_color_cached(&he->rb_node, &new_root, leftmost);
1214 }
1215
1216 parent_he->hroot_out = new_root;
1217}
1218
1219/* Initial per-cacheline capacity for the seen[] set; grown on demand. */
1220#define DEFAULT_SYMBOLS_PER_CL 64
1221
1222struct function_seen {
1223 struct map_symbol ms;
1224};
1225
1226static bool function_seen__find(const struct function_seen *seen, int nr,
1227 const struct map_symbol *ms)
1228{
1229 int i;
1230
1231 for (i = 0; i < nr; i++) {
1232 if (!c2c_function_cmp(&seen[i].ms, ms))
1233 return true;
1234 }
1235 return false;
1236}
1237
1238/* Aggregate stats from the cacheline-side entry @c2c_b into level 2/3 @dst. */
1239static bool c2c_he__add_sharing(struct c2c_hist_entry *dst, struct c2c_hist_entry *src)
1240{
1241 /* Do the fallible update first so a failure leaves dst unmodified. */
1242 if (!hist_entry__add_c2c_stats(&dst->he, &src->stats))
1243 return false;
1244
1245 c2c_add_stats(&dst->stats, &src->stats);
1246 c2c_add_cstats(&dst->cstats, &src->cstats);
1247 return true;
1248}
1249
1250/*
1251 * Process one cacheline: for every function reading it, create/update its
1252 * level-1 function entry, then for each function that writes the line
1253 * add it as a level-2 writer and add this cacheline as a level-3 child.
1254 */
1255static int c2c_function__process_cl(struct c2c_hist_entry *cacheline_he,
1256 struct thread *synthetic_thread)
1257{
1258 struct rb_node *nd_a, *nd_b;
1259 struct function_seen *seen = NULL;
1260 int nr_seen = 0, nr_alloc = 0;
1261 int ret = 0;
1262
1263 for (nd_a = rb_first_cached(&cacheline_he->hists->hists.entries); nd_a;
1264 nd_a = rb_next(nd_a)) {
1265 struct hist_entry *he_a = rb_entry(nd_a, struct hist_entry, rb_node);
1266 struct c2c_hist_entry *c2c_a;
1267 struct hist_entry *level1_he;
1268 struct c2c_hist_entry *level1_c2c;
1269
1270 if (!he_a->ms.sym || he_a->filtered)
1271 continue;
1272
1273 c2c_a = container_of(he_a, struct c2c_hist_entry, he);
1274 if (c2c_a->stats.load == 0)
1275 continue;
1276
1277 level1_he = c2c_function_hists__level1_entry(he_a->ms.sym,
1278 he_a, synthetic_thread);
1279 if (!level1_he) {
1280 ret = -ENOMEM;
1281 goto out;
1282 }
1283
1284 level1_c2c = container_of(level1_he, struct c2c_hist_entry, he);
1285
1286 /*
1287 * Aggregate every source entry into its level-1 function parent.
1288 * level1_he is keyed by symbol, so all code addresses inside the
1289 * same function collapse into one parent. When the cacheline view
1290 * splits a function into siblings (different code addresses, or
1291 * --coalesce pid/tid/dso), each sibling holds a DISJOINT slice of the
1292 * traffic, so summing them here is correct accumulation, not
1293 * double counting. The seen[] set below therefore guards only the
1294 * subtree build (to avoid building a function's level-2/3 subtree
1295 * twice for the same cacheline), never this L1 update. Update
1296 * he->stat first; on failure leave the aggregates untouched.
1297 */
1298 if (!hist_entry__add_c2c_stats(level1_he, &c2c_a->stats)) {
1299 ret = -ENOMEM;
1300 goto out;
1301 }
1302 c2c_add_stats(&level1_c2c->stats, &c2c_a->stats);
1303 c2c_add_cstats(&level1_c2c->cstats, &c2c_a->cstats);
1304 c2c_add_stats(&c2c_ext.function_hists.stats, &c2c_a->stats);
1305
1306 /* Build this function's subtree for this cacheline only once. */
1307 if (function_seen__find(seen, nr_seen, &he_a->ms))
1308 continue;
1309
1310 if (nr_seen == nr_alloc) {
1311 struct function_seen *tmp;
1312 int new_alloc = nr_alloc ? nr_alloc * 2 : DEFAULT_SYMBOLS_PER_CL;
1313
1314 tmp = reallocarray(seen, new_alloc, sizeof(*seen));
1315 if (!tmp) {
1316 ret = -ENOMEM;
1317 goto out;
1318 }
1319 seen = tmp;
1320 nr_alloc = new_alloc;
1321 }
1322 seen[nr_seen].ms = he_a->ms;
1323 nr_seen++;
1324
1325 for (nd_b = rb_first_cached(&cacheline_he->hists->hists.entries); nd_b;
1326 nd_b = rb_next(nd_b)) {
1327 struct hist_entry *he_b = rb_entry(nd_b, struct hist_entry, rb_node);
1328 struct c2c_hist_entry *c2c_b, *level2_c2c, *level3_c2c;
1329
1330 if (!he_b->ms.sym || he_b->filtered)
1331 continue;
1332
1333 c2c_b = container_of(he_b, struct c2c_hist_entry, he);
1334
1335 /*
1336 * The level-1 function contributes read-side load weight for this
1337 * cacheline. Associate it with functions sampled storing to the
1338 * same line.
1339 * The writer can be the same function; after detail coalescing and
1340 * function-level grouping there is not enough identity to attribute
1341 * that case to a specific thread.
1342 * Only writers are contending functions, so keep the ones
1343 * that actually store into the line.
1344 */
1345 if (c2c_b->stats.store == 0)
1346 continue;
1347
1348 /* Level 2: the writing function (aggregated across cachelines). */
1349 level2_c2c = c2c_function_hists__level2_entry(level1_c2c, he_b->ms.sym,
1350 he_b);
1351 if (!level2_c2c || !c2c_he__add_sharing(level2_c2c, c2c_b)) {
1352 ret = -ENOMEM;
1353 goto out;
1354 }
1355
1356 /* Level 3: the specific cacheline they contend over. */
1357 level3_c2c = c2c_function_hists__level3_entry(level2_c2c,
1358 cacheline_he);
1359 if (!level3_c2c || !c2c_he__add_sharing(level3_c2c, c2c_b)) {
1360 ret = -ENOMEM;
1361 goto out;
1362 }
1363 }
1364 }
1365
1366out:
1367 free(seen);
1368 return ret;
1369}
1370
1371/*
1372 * Remove a level-1 function that has no contended cachelines left. It is a
1373 * normal (owned) hist_entry in function_hists, so mirror hists__delete_entry()
1374 * for the no-collapse case: unlink from both trees, fix the counters, then
1375 * delete. Its hroot_out is already empty after pruning.
1376 */
1377static void c2c_function__drop_level1(struct hist_entry *he)
1378{
1379 struct hists *hists = &c2c_ext.function_hists.hists;
1380
1381 rb_erase_cached(&he->rb_node_in, hists->entries_in);
1382 rb_erase_cached(&he->rb_node, &hists->entries);
1383
1384 --hists->nr_entries;
1385 if (!he->filtered)
1386 --hists->nr_non_filtered_entries;
1387
1388 hist_entry__delete(he);
1389}
1390
1391/* Length of the identity text (symbol name or cacheline address) at @he. */
1392static int c2c_function__ident_len(struct hist_entry *he)
1393{
1394 char buf[512];
1395 char *symbuf;
1396 size_t size;
1397 int len;
1398
1399 if (hist_entry__is_cacheline(he)) {
1400 u64 addr = he->mem_info ?
1401 cl_address(mem_info__daddr(he->mem_info)->addr, chk_double_cl) : 0;
1402
1403 return scnprintf(buf, sizeof(buf), "0x%" PRIx64, addr);
1404 }
1405
1406 if (!he->ms.sym)
1407 return 0;
1408
1409 /*
1410 * Match symbol_view_entry(): sort_sym adds the cpumode prefix and, in
1411 * verbose mode, the address and DSO origin before the symbol name.
1412 */
1413 size = strlen(he->ms.sym->name) + 64;
1414 symbuf = malloc(size);
1415 if (!symbuf)
1416 return size - 1;
1417
1418 len = sort_sym.se_snprintf(he, symbuf, size, size - 1);
1419 free(symbuf);
1420 return len;
1421}
1422
1423/*
1424 * Grow the symbol column so the deepest, longest identity cell fits. The
1425 * generic hists__calc_col_len() only measures the top-level (L1) entries; the
1426 * hand-linked L2 writers and L3 cacheline addresses live in hroot_out and are
1427 * never measured, so with a short L1 name the indented L2/L3 text would be
1428 * truncated. Account for the per-level indent and the folded-sign prefix.
1429 */
1430static void c2c_function__update_symbol_width(struct hist_entry *he)
1431{
1432 struct hists *hists = &c2c_ext.function_hists.hists;
1433 int need = he->depth * C2C_FUNC_INDENT + C2C_FUNC_FOLD_WIDTH +
1434 c2c_function__ident_len(he);
1435
1436 if (need > hists__col_len(hists, HISTC_SYMBOL))
1437 hists__set_col_len(hists, HISTC_SYMBOL, need);
1438}
1439
1440/*
1441 * Prune writers with no stores, drop functions left with no contending
1442 * writer, sort the survivors by store count, then compute the global total.
1443 */
1444static void c2c_function__finalize(void)
1445{
1446 struct rb_node *nd_l1;
1447
1448 nd_l1 = rb_first_cached(&c2c_ext.function_hists.hists.entries);
1449 while (nd_l1) {
1450 struct hist_entry *he_l1 = rb_entry(nd_l1, struct hist_entry, rb_node);
1451 struct rb_node *next_l1 = rb_next(nd_l1);
1452 struct rb_node *nd_l2;
1453
1454 /* Drop writers with no stores before sorting. */
1455 if (!he_l1->has_children || !c2c_he__prune_empty_writers(he_l1)) {
1456 /* No contending writer: this function is not shared. */
1457 c2c_function__drop_level1(he_l1);
1458 nd_l1 = next_l1;
1459 continue;
1460 }
1461
1462 c2c_he__resort_by_stores(he_l1);
1463 c2c_function__update_symbol_width(he_l1);
1464
1465 for (nd_l2 = rb_first_cached(&he_l1->hroot_out); nd_l2;
1466 nd_l2 = rb_next(nd_l2)) {
1467 struct hist_entry *he_l2 = rb_entry(nd_l2, struct hist_entry, rb_node);
1468 struct rb_node *nd_l3;
1469
1470 c2c_function__update_symbol_width(he_l2);
1471
1472 if (he_l2->has_children)
1473 c2c_he__resort_by_stores(he_l2);
1474
1475 for (nd_l3 = rb_first_cached(&he_l2->hroot_out); nd_l3;
1476 nd_l3 = rb_next(nd_l3)) {
1477 struct hist_entry *he_l3 = rb_entry(nd_l3, struct hist_entry,
1478 rb_node);
1479
1480 c2c_function__update_symbol_width(he_l3);
1481 }
1482 }
1483
1484 nd_l1 = next_l1;
1485 }
1486
1487 /*
1488 * Compute the Cycles % denominator from the surviving level-1 entries
1489 * after pruning, so the column shows each function's share of the
1490 * functions retained in this table -- not of the whole recording. See
1491 * the Cycles % description in perf-c2c.txt.
1492 */
1493 c2c_ext.total_cycles = c2c_ext__total_cycles();
1494}
1495
1496/*
1497 * Release all per-visit function-view state. Keep the hists object itself
1498 * initialized so its mutex is initialized exactly once across TAB re-entry.
1499 */
1500void c2c_function__reset(void)
1501{
1502 bool saved_use_callchain = symbol_conf.use_callchain;
1503
1504 /*
1505 * Function-view entries never carry callchains. Keep their generic
1506 * destructor independent of the caller's current callchain setting.
1507 */
1508 symbol_conf.use_callchain = false;
1509 hists__delete_all_entries(&c2c_ext.function_hists.hists);
1510 if (c2c_ext.function_hists.list.fields.next)
1511 perf_hpp__reset_output_field(&c2c_ext.function_hists.list);
1512
1513 memset(&c2c_ext.function_hists.stats, 0,
1514 sizeof(c2c_ext.function_hists.stats));
1515 c2c_ext.total_cycles = 0;
1516 c2c_ext.cl_hists = NULL;
1517 c2c_ext.cl_sort = NULL;
1518 c2c_ext.symbol_full = false;
1519 symbol_conf.use_callchain = saved_use_callchain;
1520}
1521
1522static bool c2c_function__has_iaddr(const char *cl_sort)
1523{
1524 const char *field = cl_sort;
1525
1526 while (field && *field) {
1527 const char *end = strchr(field, ',');
1528 size_t len = end ? (size_t)(end - field) : strlen(field);
1529
1530 if (len == sizeof("iaddr") - 1 && !strncmp(field, "iaddr", len))
1531 return true;
1532 field = end ? end + 1 : NULL;
1533 }
1534 return false;
1535}
1536
1537/*
1538 * Build the three-level function view in a single pass over the cacheline
1539 * entries:
1540 * L1: read-side functions (aggregated across all their code addresses)
1541 * L2: writing functions contending with each level-1 function
1542 * L3: shared cachelines for each function pair
1543 */
1544int c2c_function__build(struct c2c_hists *cl_hists, const char *cl_sort,
1545 bool symbol_full, struct hists **hists)
1546{
1547 static const char output_fields[] =
1548 "cycles_percent,total_stores,symbol_view";
1549 static bool hists_initialized;
1550 struct rb_node *nd_cl;
1551 bool saved_use_callchain;
1552 int ret;
1553
1554 if (!hists)
1555 return -EINVAL;
1556 *hists = NULL;
1557
1558 if (!cl_hists || !cl_sort)
1559 return -EINVAL;
1560 if (!c2c_function__has_iaddr(cl_sort))
1561 return -EOPNOTSUPP;
1562
1563 saved_use_callchain = symbol_conf.use_callchain;
1564 symbol_conf.use_callchain = false;
1565 c2c_function__reset();
1566
1567 c2c_ext.cl_hists = cl_hists;
1568 c2c_ext.cl_sort = cl_sort;
1569 c2c_ext.symbol_full = symbol_full;
1570
1571 /*
1572 * __hists__init() (called by c2c_function_hists__init()) also
1573 * mutex_init()s the hists lock, so only run it once for this static
1574 * hists; on re-entry just re-parse the columns via reinit().
1575 */
1576 if (!hists_initialized) {
1577 ret = c2c_function_hists__init(&c2c_ext.function_hists,
1578 "symbol_view", 2, NULL);
1579 hists_initialized = true;
1580 } else {
1581 ret = c2c_function_hists__reinit(&c2c_ext.function_hists,
1582 /*output=*/NULL, "symbol_view", NULL);
1583 }
1584 if (ret)
1585 goto out_reset;
1586
1587 nd_cl = rb_first_cached(&c2c_ext.cl_hists->hists.entries);
1588
1589 /* An empty C2C report yields an empty (but valid) function view. */
1590 for (; nd_cl; nd_cl = rb_next(nd_cl)) {
1591 struct hist_entry *he_cl = rb_entry(nd_cl, struct hist_entry, rb_node);
1592 struct c2c_hist_entry *cacheline_he = container_of(he_cl,
1593 struct c2c_hist_entry, he);
1594 struct thread *synthetic_thread = he_cl->thread;
1595
1596 /*
1597 * Detail hists are finalized only for cachelines retained by the
1598 * top-level C2C filter. Among those, include any line with sharing
1599 * activity, not just HITM.
1600 */
1601 if (he_cl->filtered ||
1602 (c2c_hitm_count(&cacheline_he->stats) == 0 &&
1603 cacheline_he->stats.tot_peer == 0 &&
1604 cacheline_he->stats.store == 0 &&
1605 cacheline_he->stats.load == 0) ||
1606 !cacheline_he->hists ||
1607 RB_EMPTY_ROOT(&cacheline_he->hists->hists.entries.rb_root) ||
1608 !he_cl->mem_info || !synthetic_thread)
1609 continue;
1610
1611 ret = c2c_function__process_cl(cacheline_he, synthetic_thread);
1612 if (ret)
1613 goto out_err;
1614 }
1615
1616 ret = c2c_function_hists__reinit(&c2c_ext.function_hists, output_fields,
1617 "cycles_percent", NULL);
1618 if (ret)
1619 goto out_err;
1620
1621 hists__collapse_resort(&c2c_ext.function_hists.hists, NULL);
1622 hists__output_resort(&c2c_ext.function_hists.hists, NULL);
1623
1624 c2c_function__finalize();
1625
1626 *hists = &c2c_ext.function_hists.hists;
1627 symbol_conf.use_callchain = saved_use_callchain;
1628 return 0;
1629
1630out_err:
1631 /*
1632 * On error, migrate any entries still in entries_in to entries and
1633 * delete them, so a later rebuild does not strand them (the top-level
1634 * __hists__init() memset would otherwise lose the pointers).
1635 */
1636 hists__collapse_resort(&c2c_ext.function_hists.hists, NULL);
1637 hists__output_resort(&c2c_ext.function_hists.hists, NULL);
1638out_reset:
1639 c2c_function__reset();
1640 symbol_conf.use_callchain = saved_use_callchain;
1641 return ret;
1642}