mem2node.c 2.8 KB

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