1 | // SPDX-License-Identifier: GPL-2.0-or-later |
2 | /* |
3 | * Modules tree lookup |
4 | * |
5 | * Copyright (C) 2015 Peter Zijlstra |
6 | * Copyright (C) 2015 Rusty Russell |
7 | */ |
8 | |
9 | #include <linux/module.h> |
10 | #include <linux/rbtree_latch.h> |
11 | #include "internal.h" |
12 | |
13 | /* |
14 | * Use a latched RB-tree for __module_address(); this allows us to use |
15 | * RCU-sched lookups of the address from any context. |
16 | * |
17 | * This is conditional on PERF_EVENTS || TRACING because those can really hit |
18 | * __module_address() hard by doing a lot of stack unwinding; potentially from |
19 | * NMI context. |
20 | */ |
21 | |
22 | static __always_inline unsigned long __mod_tree_val(struct latch_tree_node *n) |
23 | { |
24 | struct module_memory *mod_mem = container_of(n, struct module_memory, mtn.node); |
25 | |
26 | return (unsigned long)mod_mem->base; |
27 | } |
28 | |
29 | static __always_inline unsigned long __mod_tree_size(struct latch_tree_node *n) |
30 | { |
31 | struct module_memory *mod_mem = container_of(n, struct module_memory, mtn.node); |
32 | |
33 | return (unsigned long)mod_mem->size; |
34 | } |
35 | |
36 | static __always_inline bool |
37 | mod_tree_less(struct latch_tree_node *a, struct latch_tree_node *b) |
38 | { |
39 | return __mod_tree_val(n: a) < __mod_tree_val(n: b); |
40 | } |
41 | |
42 | static __always_inline int |
43 | mod_tree_comp(void *key, struct latch_tree_node *n) |
44 | { |
45 | unsigned long val = (unsigned long)key; |
46 | unsigned long start, end; |
47 | |
48 | start = __mod_tree_val(n); |
49 | if (val < start) |
50 | return -1; |
51 | |
52 | end = start + __mod_tree_size(n); |
53 | if (val >= end) |
54 | return 1; |
55 | |
56 | return 0; |
57 | } |
58 | |
59 | static const struct latch_tree_ops mod_tree_ops = { |
60 | .less = mod_tree_less, |
61 | .comp = mod_tree_comp, |
62 | }; |
63 | |
64 | static noinline void __mod_tree_insert(struct mod_tree_node *node, struct mod_tree_root *tree) |
65 | { |
66 | latch_tree_insert(node: &node->node, root: &tree->root, ops: &mod_tree_ops); |
67 | } |
68 | |
69 | static void __mod_tree_remove(struct mod_tree_node *node, struct mod_tree_root *tree) |
70 | { |
71 | latch_tree_erase(node: &node->node, root: &tree->root, ops: &mod_tree_ops); |
72 | } |
73 | |
74 | /* |
75 | * These modifications: insert, remove_init and remove; are serialized by the |
76 | * module_mutex. |
77 | */ |
78 | void mod_tree_insert(struct module *mod) |
79 | { |
80 | for_each_mod_mem_type(type) { |
81 | mod->mem[type].mtn.mod = mod; |
82 | if (mod->mem[type].size) |
83 | __mod_tree_insert(node: &mod->mem[type].mtn, tree: &mod_tree); |
84 | } |
85 | } |
86 | |
87 | void mod_tree_remove_init(struct module *mod) |
88 | { |
89 | for_class_mod_mem_type(type, init) { |
90 | if (mod->mem[type].size) |
91 | __mod_tree_remove(node: &mod->mem[type].mtn, tree: &mod_tree); |
92 | } |
93 | } |
94 | |
95 | void mod_tree_remove(struct module *mod) |
96 | { |
97 | for_each_mod_mem_type(type) { |
98 | if (mod->mem[type].size) |
99 | __mod_tree_remove(node: &mod->mem[type].mtn, tree: &mod_tree); |
100 | } |
101 | } |
102 | |
103 | struct module *mod_find(unsigned long addr, struct mod_tree_root *tree) |
104 | { |
105 | struct latch_tree_node *ltn; |
106 | |
107 | ltn = latch_tree_find(key: (void *)addr, root: &tree->root, ops: &mod_tree_ops); |
108 | if (!ltn) |
109 | return NULL; |
110 | |
111 | return container_of(ltn, struct mod_tree_node, node)->mod; |
112 | } |
113 | |