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