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