1 #include <errno.h> 2 #include <inttypes.h> 3 #include <linux/bitmap.h> 4 #include <linux/kernel.h> 5 #include <linux/zalloc.h> 6 #include "debug.h" 7 #include "env.h" 8 #include "mem2node.h" 9 10 struct phys_entry { 11 struct rb_node rb_node; 12 u64 start; 13 u64 end; 14 u64 node; 15 }; 16 17 static void phys_entry__insert(struct phys_entry *entry, struct rb_root *root) 18 { 19 struct rb_node **p = &root->rb_node; 20 struct rb_node *parent = NULL; 21 struct phys_entry *e; 22 23 while (*p != NULL) { 24 parent = *p; 25 e = rb_entry(parent, struct phys_entry, rb_node); 26 27 if (entry->start < e->start) 28 p = &(*p)->rb_left; 29 else 30 p = &(*p)->rb_right; 31 } 32 33 rb_link_node(&entry->rb_node, parent, p); 34 rb_insert_color(&entry->rb_node, root); 35 } 36 37 static void 38 phys_entry__init(struct phys_entry *entry, u64 start, u64 bsize, u64 node) 39 { 40 entry->start = start; 41 entry->end = start + bsize; 42 entry->node = node; 43 RB_CLEAR_NODE(&entry->rb_node); 44 } 45 46 int mem2node__init(struct mem2node *map, struct perf_env *env) 47 { 48 struct memory_node *n, *nodes = &env->memory_nodes[0]; 49 struct phys_entry *entries, *tmp_entries; 50 u64 bsize = env->memory_bsize; 51 int i, j = 0, max = 0; 52 53 memset(map, 0x0, sizeof(*map)); 54 map->root = RB_ROOT; 55 56 for (i = 0; i < env->nr_memory_nodes; i++) { 57 n = &nodes[i]; 58 max += bitmap_weight(n->set, n->size); 59 } 60 61 entries = zalloc(sizeof(*entries) * max); 62 if (!entries) 63 return -ENOMEM; 64 65 for (i = 0; i < env->nr_memory_nodes; i++) { 66 u64 bit; 67 68 n = &nodes[i]; 69 70 for (bit = 0; bit < n->size; bit++) { 71 u64 start; 72 73 if (!test_bit(bit, n->set)) 74 continue; 75 76 start = bit * bsize; 77 78 /* 79 * Merge nearby areas, we walk in order 80 * through the bitmap, so no need to sort. 81 */ 82 if (j > 0) { 83 struct phys_entry *prev = &entries[j - 1]; 84 85 if ((prev->end == start) && 86 (prev->node == n->node)) { 87 prev->end += bsize; 88 continue; 89 } 90 } 91 92 phys_entry__init(&entries[j++], start, bsize, n->node); 93 } 94 } 95 96 /* Cut unused entries, due to merging. */ 97 tmp_entries = realloc(entries, sizeof(*entries) * j); 98 if (tmp_entries) 99 entries = tmp_entries; 100 101 for (i = 0; i < j; i++) { 102 pr_debug("mem2node %03" PRIu64 " [0x%016" PRIx64 "-0x%016" PRIx64 "]\n", 103 entries[i].node, entries[i].start, entries[i].end); 104 105 phys_entry__insert(&entries[i], &map->root); 106 } 107 108 map->entries = entries; 109 return 0; 110 } 111 112 void mem2node__exit(struct mem2node *map) 113 { 114 zfree(&map->entries); 115 } 116 117 int mem2node__node(struct mem2node *map, u64 addr) 118 { 119 struct rb_node **p, *parent = NULL; 120 struct phys_entry *entry; 121 122 p = &map->root.rb_node; 123 while (*p != NULL) { 124 parent = *p; 125 entry = rb_entry(parent, struct phys_entry, rb_node); 126 if (addr < entry->start) 127 p = &(*p)->rb_left; 128 else if (addr >= entry->end) 129 p = &(*p)->rb_right; 130 else 131 goto out; 132 } 133 134 entry = NULL; 135 out: 136 return entry ? (int) entry->node : -1; 137 } 138