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