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