5 #include "util/cache.h"
6 #include "util/symbol.h"
7 #include "util/thread.h"
8 #include "util/header.h"
10 #include "util/parse-options.h"
11 #include "util/trace-event.h"
13 #include "util/debug.h"
14 #include "util/data_map.h"
16 #include <linux/rbtree.h>
19 typedef int (*sort_fn_t)(struct alloc_stat *, struct alloc_stat *);
21 static char const *input_name = "perf.data";
23 static struct perf_header *header;
24 static u64 sample_type;
26 static int alloc_flag;
27 static int caller_flag;
29 static int alloc_lines = -1;
30 static int caller_lines = -1;
34 static char default_sort_order[] = "frag,hit,bytes";
39 static int *cpunode_map;
40 static int max_cpu_num;
55 static struct rb_root root_alloc_stat;
56 static struct rb_root root_alloc_sorted;
57 static struct rb_root root_caller_stat;
58 static struct rb_root root_caller_sorted;
60 static unsigned long total_requested, total_allocated;
61 static unsigned long nr_allocs, nr_cross_allocs;
63 struct raw_event_sample {
68 #define PATH_SYS_NODE "/sys/devices/system/node"
70 static void init_cpunode_map(void)
75 fp = fopen("/sys/devices/system/cpu/kernel_max", "r");
81 if (fscanf(fp, "%d", &max_cpu_num) < 1)
82 die("Failed to read 'kernel_max' from sysfs");
85 cpunode_map = calloc(max_cpu_num, sizeof(int));
88 for (i = 0; i < max_cpu_num; i++)
93 static void setup_cpunode_map(void)
95 struct dirent *dent1, *dent2;
97 unsigned int cpu, mem;
102 dir1 = opendir(PATH_SYS_NODE);
107 dent1 = readdir(dir1);
111 if (sscanf(dent1->d_name, "node%u", &mem) < 1)
114 snprintf(buf, PATH_MAX, "%s/%s", PATH_SYS_NODE, dent1->d_name);
119 dent2 = readdir(dir2);
122 if (sscanf(dent2->d_name, "cpu%u", &cpu) < 1)
124 cpunode_map[cpu] = mem;
130 process_comm_event(event_t *event, unsigned long offset, unsigned long head)
132 struct thread *thread = threads__findnew(event->comm.pid);
134 dump_printf("%p [%p]: PERF_RECORD_COMM: %s:%d\n",
135 (void *)(offset + head),
136 (void *)(long)(event->header.size),
137 event->comm.comm, event->comm.pid);
139 if (thread == NULL ||
140 thread__set_comm(thread, event->comm.comm)) {
141 dump_printf("problem processing PERF_RECORD_COMM, skipping event.\n");
148 static void insert_alloc_stat(unsigned long call_site, unsigned long ptr,
149 int bytes_req, int bytes_alloc, int cpu)
151 struct rb_node **node = &root_alloc_stat.rb_node;
152 struct rb_node *parent = NULL;
153 struct alloc_stat *data = NULL;
157 data = rb_entry(*node, struct alloc_stat, node);
160 node = &(*node)->rb_right;
161 else if (ptr < data->ptr)
162 node = &(*node)->rb_left;
167 if (data && data->ptr == ptr) {
169 data->bytes_req += bytes_req;
170 data->bytes_alloc += bytes_req;
172 data = malloc(sizeof(*data));
178 data->bytes_req = bytes_req;
179 data->bytes_alloc = bytes_alloc;
181 rb_link_node(&data->node, parent, node);
182 rb_insert_color(&data->node, &root_alloc_stat);
184 data->call_site = call_site;
185 data->alloc_cpu = cpu;
188 static void insert_caller_stat(unsigned long call_site,
189 int bytes_req, int bytes_alloc)
191 struct rb_node **node = &root_caller_stat.rb_node;
192 struct rb_node *parent = NULL;
193 struct alloc_stat *data = NULL;
197 data = rb_entry(*node, struct alloc_stat, node);
199 if (call_site > data->call_site)
200 node = &(*node)->rb_right;
201 else if (call_site < data->call_site)
202 node = &(*node)->rb_left;
207 if (data && data->call_site == call_site) {
209 data->bytes_req += bytes_req;
210 data->bytes_alloc += bytes_req;
212 data = malloc(sizeof(*data));
215 data->call_site = call_site;
218 data->bytes_req = bytes_req;
219 data->bytes_alloc = bytes_alloc;
221 rb_link_node(&data->node, parent, node);
222 rb_insert_color(&data->node, &root_caller_stat);
226 static void process_alloc_event(struct raw_event_sample *raw,
229 u64 timestamp __used,
230 struct thread *thread __used,
233 unsigned long call_site;
239 ptr = raw_field_value(event, "ptr", raw->data);
240 call_site = raw_field_value(event, "call_site", raw->data);
241 bytes_req = raw_field_value(event, "bytes_req", raw->data);
242 bytes_alloc = raw_field_value(event, "bytes_alloc", raw->data);
244 insert_alloc_stat(call_site, ptr, bytes_req, bytes_alloc, cpu);
245 insert_caller_stat(call_site, bytes_req, bytes_alloc);
247 total_requested += bytes_req;
248 total_allocated += bytes_alloc;
251 node1 = cpunode_map[cpu];
252 node2 = raw_field_value(event, "node", raw->data);
259 static int ptr_cmp(struct alloc_stat *, struct alloc_stat *);
260 static int callsite_cmp(struct alloc_stat *, struct alloc_stat *);
262 static struct alloc_stat *search_alloc_stat(unsigned long ptr,
263 unsigned long call_site,
264 struct rb_root *root,
267 struct rb_node *node = root->rb_node;
268 struct alloc_stat key = { .ptr = ptr, .call_site = call_site };
271 struct alloc_stat *data;
274 data = rb_entry(node, struct alloc_stat, node);
276 cmp = sort_fn(&key, data);
278 node = node->rb_left;
280 node = node->rb_right;
287 static void process_free_event(struct raw_event_sample *raw,
290 u64 timestamp __used,
291 struct thread *thread __used)
294 struct alloc_stat *s_alloc, *s_caller;
296 ptr = raw_field_value(event, "ptr", raw->data);
298 s_alloc = search_alloc_stat(ptr, 0, &root_alloc_stat, ptr_cmp);
302 if (cpu != s_alloc->alloc_cpu) {
305 s_caller = search_alloc_stat(0, s_alloc->call_site,
306 &root_caller_stat, callsite_cmp);
308 s_caller->pingpong++;
310 s_alloc->alloc_cpu = -1;
314 process_raw_event(event_t *raw_event __used, void *more_data,
315 int cpu, u64 timestamp, struct thread *thread)
317 struct raw_event_sample *raw = more_data;
321 type = trace_parse_common_type(raw->data);
322 event = trace_find_event(type);
324 if (!strcmp(event->name, "kmalloc") ||
325 !strcmp(event->name, "kmem_cache_alloc")) {
326 process_alloc_event(raw, event, cpu, timestamp, thread, 0);
330 if (!strcmp(event->name, "kmalloc_node") ||
331 !strcmp(event->name, "kmem_cache_alloc_node")) {
332 process_alloc_event(raw, event, cpu, timestamp, thread, 1);
336 if (!strcmp(event->name, "kfree") ||
337 !strcmp(event->name, "kmem_cache_free")) {
338 process_free_event(raw, event, cpu, timestamp, thread);
344 process_sample_event(event_t *event, unsigned long offset, unsigned long head)
346 u64 ip = event->ip.ip;
350 void *more_data = event->ip.__more_data;
351 struct thread *thread = threads__findnew(event->ip.pid);
353 if (sample_type & PERF_SAMPLE_TIME) {
354 timestamp = *(u64 *)more_data;
355 more_data += sizeof(u64);
358 if (sample_type & PERF_SAMPLE_CPU) {
359 cpu = *(u32 *)more_data;
360 more_data += sizeof(u32);
361 more_data += sizeof(u32); /* reserved */
364 if (sample_type & PERF_SAMPLE_PERIOD) {
365 period = *(u64 *)more_data;
366 more_data += sizeof(u64);
369 dump_printf("%p [%p]: PERF_RECORD_SAMPLE (IP, %d): %d/%d: %p period: %Ld\n",
370 (void *)(offset + head),
371 (void *)(long)(event->header.size),
373 event->ip.pid, event->ip.tid,
377 if (thread == NULL) {
378 pr_debug("problem processing %d event, skipping it.\n",
383 dump_printf(" ... thread: %s:%d\n", thread->comm, thread->pid);
385 process_raw_event(event, more_data, cpu, timestamp, thread);
390 static int sample_type_check(u64 type)
394 if (!(sample_type & PERF_SAMPLE_RAW)) {
396 "No trace sample to read. Did you call perf record "
404 static struct perf_file_handler file_handler = {
405 .process_sample_event = process_sample_event,
406 .process_comm_event = process_comm_event,
407 .sample_type_check = sample_type_check,
410 static int read_events(void)
412 register_idle_thread();
413 register_perf_file_handler(&file_handler);
415 return mmap_dispatch_perf_file(&header, input_name, 0, 0,
419 static double fragmentation(unsigned long n_req, unsigned long n_alloc)
424 return 100.0 - (100.0 * n_req / n_alloc);
427 static void __print_result(struct rb_root *root, int n_lines, int is_caller)
429 struct rb_node *next;
431 printf("%.102s\n", graph_dotted_line);
432 printf(" %-34s |", is_caller ? "Callsite": "Alloc Ptr");
433 printf(" Total_alloc/Per | Total_req/Per | Hit | Ping-pong | Frag\n");
434 printf("%.102s\n", graph_dotted_line);
436 next = rb_first(root);
438 while (next && n_lines--) {
439 struct alloc_stat *data = rb_entry(next, struct alloc_stat,
441 struct symbol *sym = NULL;
446 addr = data->call_site;
448 sym = kernel_maps__find_function(addr, NULL, NULL);
453 snprintf(buf, sizeof(buf), "%s+%Lx", sym->name,
456 snprintf(buf, sizeof(buf), "%#Lx", addr);
457 printf(" %-34s |", buf);
459 printf(" %9llu/%-5lu | %9llu/%-5lu | %6lu | %8lu | %6.3f%%\n",
460 (unsigned long long)data->bytes_alloc,
461 (unsigned long)data->bytes_alloc / data->hit,
462 (unsigned long long)data->bytes_req,
463 (unsigned long)data->bytes_req / data->hit,
464 (unsigned long)data->hit,
465 (unsigned long)data->pingpong,
466 fragmentation(data->bytes_req, data->bytes_alloc));
468 next = rb_next(next);
472 printf(" ... | ... | ... | ... | ... | ... \n");
474 printf("%.102s\n", graph_dotted_line);
477 static void print_summary(void)
479 printf("\nSUMMARY\n=======\n");
480 printf("Total bytes requested: %lu\n", total_requested);
481 printf("Total bytes allocated: %lu\n", total_allocated);
482 printf("Total bytes wasted on internal fragmentation: %lu\n",
483 total_allocated - total_requested);
484 printf("Internal fragmentation: %f%%\n",
485 fragmentation(total_requested, total_allocated));
486 printf("Cross CPU allocations: %lu/%lu\n", nr_cross_allocs, nr_allocs);
489 static void print_result(void)
492 __print_result(&root_caller_sorted, caller_lines, 1);
494 __print_result(&root_alloc_sorted, alloc_lines, 0);
498 struct sort_dimension {
501 struct list_head list;
504 static LIST_HEAD(caller_sort);
505 static LIST_HEAD(alloc_sort);
507 static void sort_insert(struct rb_root *root, struct alloc_stat *data,
508 struct list_head *sort_list)
510 struct rb_node **new = &(root->rb_node);
511 struct rb_node *parent = NULL;
512 struct sort_dimension *sort;
515 struct alloc_stat *this;
518 this = rb_entry(*new, struct alloc_stat, node);
521 list_for_each_entry(sort, sort_list, list) {
522 cmp = sort->cmp(data, this);
528 new = &((*new)->rb_left);
530 new = &((*new)->rb_right);
533 rb_link_node(&data->node, parent, new);
534 rb_insert_color(&data->node, root);
537 static void __sort_result(struct rb_root *root, struct rb_root *root_sorted,
538 struct list_head *sort_list)
540 struct rb_node *node;
541 struct alloc_stat *data;
544 node = rb_first(root);
548 rb_erase(node, root);
549 data = rb_entry(node, struct alloc_stat, node);
550 sort_insert(root_sorted, data, sort_list);
554 static void sort_result(void)
556 __sort_result(&root_alloc_stat, &root_alloc_sorted, &alloc_sort);
557 __sort_result(&root_caller_stat, &root_caller_sorted, &caller_sort);
560 static int __cmd_kmem(void)
570 static const char * const kmem_usage[] = {
571 "perf kmem [<options>] {record}",
575 static int ptr_cmp(struct alloc_stat *l, struct alloc_stat *r)
579 else if (l->ptr > r->ptr)
584 static struct sort_dimension ptr_sort_dimension = {
589 static int callsite_cmp(struct alloc_stat *l, struct alloc_stat *r)
591 if (l->call_site < r->call_site)
593 else if (l->call_site > r->call_site)
598 static struct sort_dimension callsite_sort_dimension = {
603 static int hit_cmp(struct alloc_stat *l, struct alloc_stat *r)
607 else if (l->hit > r->hit)
612 static struct sort_dimension hit_sort_dimension = {
617 static int bytes_cmp(struct alloc_stat *l, struct alloc_stat *r)
619 if (l->bytes_alloc < r->bytes_alloc)
621 else if (l->bytes_alloc > r->bytes_alloc)
626 static struct sort_dimension bytes_sort_dimension = {
631 static int frag_cmp(struct alloc_stat *l, struct alloc_stat *r)
635 x = fragmentation(l->bytes_req, l->bytes_alloc);
636 y = fragmentation(r->bytes_req, r->bytes_alloc);
645 static struct sort_dimension frag_sort_dimension = {
650 static int pingpong_cmp(struct alloc_stat *l, struct alloc_stat *r)
652 if (l->pingpong < r->pingpong)
654 else if (l->pingpong > r->pingpong)
659 static struct sort_dimension pingpong_sort_dimension = {
664 static struct sort_dimension *avail_sorts[] = {
666 &callsite_sort_dimension,
668 &bytes_sort_dimension,
669 &frag_sort_dimension,
670 &pingpong_sort_dimension,
673 #define NUM_AVAIL_SORTS \
674 (int)(sizeof(avail_sorts) / sizeof(struct sort_dimension *))
676 static int sort_dimension__add(const char *tok, struct list_head *list)
678 struct sort_dimension *sort;
681 for (i = 0; i < NUM_AVAIL_SORTS; i++) {
682 if (!strcmp(avail_sorts[i]->name, tok)) {
683 sort = malloc(sizeof(*sort));
686 memcpy(sort, avail_sorts[i], sizeof(*sort));
687 list_add_tail(&sort->list, list);
695 static int setup_sorting(struct list_head *sort_list, const char *arg)
698 char *str = strdup(arg);
704 tok = strsep(&str, ",");
707 if (sort_dimension__add(tok, sort_list) < 0) {
708 error("Unknown --sort key: '%s'", tok);
717 static int parse_sort_opt(const struct option *opt __used,
718 const char *arg, int unset __used)
723 if (caller_flag > alloc_flag)
724 return setup_sorting(&caller_sort, arg);
726 return setup_sorting(&alloc_sort, arg);
731 static int parse_stat_opt(const struct option *opt __used,
732 const char *arg, int unset __used)
737 if (strcmp(arg, "alloc") == 0)
738 alloc_flag = (caller_flag + 1);
739 else if (strcmp(arg, "caller") == 0)
740 caller_flag = (alloc_flag + 1);
746 static int parse_line_opt(const struct option *opt __used,
747 const char *arg, int unset __used)
754 lines = strtoul(arg, NULL, 10);
756 if (caller_flag > alloc_flag)
757 caller_lines = lines;
764 static const struct option kmem_options[] = {
765 OPT_STRING('i', "input", &input_name, "file",
767 OPT_CALLBACK(0, "stat", NULL, "<alloc>|<caller>",
768 "stat selector, Pass 'alloc' or 'caller'.",
770 OPT_CALLBACK('s', "sort", NULL, "key[,key2...]",
771 "sort by keys: ptr, call_site, bytes, hit, pingpong, frag",
773 OPT_CALLBACK('l', "line", NULL, "num",
776 OPT_BOOLEAN(0, "raw-ip", &raw_ip, "show raw ip instead of symbol"),
780 static const char *record_args[] = {
787 "-e", "kmem:kmalloc",
788 "-e", "kmem:kmalloc_node",
790 "-e", "kmem:kmem_cache_alloc",
791 "-e", "kmem:kmem_cache_alloc_node",
792 "-e", "kmem:kmem_cache_free",
795 static int __cmd_record(int argc, const char **argv)
797 unsigned int rec_argc, i, j;
798 const char **rec_argv;
800 rec_argc = ARRAY_SIZE(record_args) + argc - 1;
801 rec_argv = calloc(rec_argc + 1, sizeof(char *));
803 for (i = 0; i < ARRAY_SIZE(record_args); i++)
804 rec_argv[i] = strdup(record_args[i]);
806 for (j = 1; j < (unsigned int)argc; j++, i++)
807 rec_argv[i] = argv[j];
809 return cmd_record(i, rec_argv, NULL);
812 int cmd_kmem(int argc, const char **argv, const char *prefix __used)
816 argc = parse_options(argc, argv, kmem_options, kmem_usage, 0);
818 if (argc && !strncmp(argv[0], "rec", 3))
819 return __cmd_record(argc, argv);
821 usage_with_options(kmem_usage, kmem_options);
823 if (list_empty(&caller_sort))
824 setup_sorting(&caller_sort, default_sort_order);
825 if (list_empty(&alloc_sort))
826 setup_sorting(&alloc_sort, default_sort_order);