1 #include <errno.h>
2 #include <inttypes.h>
3 #include <asm/bug.h>
4 #include <linux/bitmap.h>
5 #include "mem2node.h"
6 #include "util.h"
7
8 struct phys_entry {
9 struct rb_node rb_node;
10 u64 start;
11 u64 end;
12 u64 node;
13 };
14
phys_entry__insert(struct phys_entry * entry,struct rb_root * root)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
phys_entry__init(struct phys_entry * entry,u64 start,u64 bsize,u64 node)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
mem2node__init(struct mem2node * map,struct perf_env * env)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 || WARN_ON_ONCE(j == 0))
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
mem2node__exit(struct mem2node * map)110 void mem2node__exit(struct mem2node *map)
111 {
112 zfree(&map->entries);
113 }
114
mem2node__node(struct mem2node * map,u64 addr)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