158d208deSAaron Tomlin // SPDX-License-Identifier: GPL-2.0-or-later
258d208deSAaron Tomlin /*
358d208deSAaron Tomlin * Modules tree lookup
458d208deSAaron Tomlin *
558d208deSAaron Tomlin * Copyright (C) 2015 Peter Zijlstra
658d208deSAaron Tomlin * Copyright (C) 2015 Rusty Russell
758d208deSAaron Tomlin */
858d208deSAaron Tomlin
958d208deSAaron Tomlin #include <linux/module.h>
1058d208deSAaron Tomlin #include <linux/rbtree_latch.h>
1158d208deSAaron Tomlin #include "internal.h"
1258d208deSAaron Tomlin
1358d208deSAaron Tomlin /*
1458d208deSAaron Tomlin * Use a latched RB-tree for __module_address(); this allows us to use
1558d208deSAaron Tomlin * RCU-sched lookups of the address from any context.
1658d208deSAaron Tomlin *
1758d208deSAaron Tomlin * This is conditional on PERF_EVENTS || TRACING because those can really hit
1858d208deSAaron Tomlin * __module_address() hard by doing a lot of stack unwinding; potentially from
1958d208deSAaron Tomlin * NMI context.
2058d208deSAaron Tomlin */
2158d208deSAaron Tomlin
__mod_tree_val(struct latch_tree_node * n)2258d208deSAaron Tomlin static __always_inline unsigned long __mod_tree_val(struct latch_tree_node *n)
2358d208deSAaron Tomlin {
24*ac3b4328SSong Liu struct module_memory *mod_mem = container_of(n, struct module_memory, mtn.node);
2558d208deSAaron Tomlin
26*ac3b4328SSong Liu return (unsigned long)mod_mem->base;
2758d208deSAaron Tomlin }
2858d208deSAaron Tomlin
__mod_tree_size(struct latch_tree_node * n)2958d208deSAaron Tomlin static __always_inline unsigned long __mod_tree_size(struct latch_tree_node *n)
3058d208deSAaron Tomlin {
31*ac3b4328SSong Liu struct module_memory *mod_mem = container_of(n, struct module_memory, mtn.node);
3258d208deSAaron Tomlin
33*ac3b4328SSong Liu return (unsigned long)mod_mem->size;
3458d208deSAaron Tomlin }
3558d208deSAaron Tomlin
3658d208deSAaron Tomlin static __always_inline bool
mod_tree_less(struct latch_tree_node * a,struct latch_tree_node * b)3758d208deSAaron Tomlin mod_tree_less(struct latch_tree_node *a, struct latch_tree_node *b)
3858d208deSAaron Tomlin {
3958d208deSAaron Tomlin return __mod_tree_val(a) < __mod_tree_val(b);
4058d208deSAaron Tomlin }
4158d208deSAaron Tomlin
4258d208deSAaron Tomlin static __always_inline int
mod_tree_comp(void * key,struct latch_tree_node * n)4358d208deSAaron Tomlin mod_tree_comp(void *key, struct latch_tree_node *n)
4458d208deSAaron Tomlin {
4558d208deSAaron Tomlin unsigned long val = (unsigned long)key;
4658d208deSAaron Tomlin unsigned long start, end;
4758d208deSAaron Tomlin
4858d208deSAaron Tomlin start = __mod_tree_val(n);
4958d208deSAaron Tomlin if (val < start)
5058d208deSAaron Tomlin return -1;
5158d208deSAaron Tomlin
5258d208deSAaron Tomlin end = start + __mod_tree_size(n);
5358d208deSAaron Tomlin if (val >= end)
5458d208deSAaron Tomlin return 1;
5558d208deSAaron Tomlin
5658d208deSAaron Tomlin return 0;
5758d208deSAaron Tomlin }
5858d208deSAaron Tomlin
5958d208deSAaron Tomlin static const struct latch_tree_ops mod_tree_ops = {
6058d208deSAaron Tomlin .less = mod_tree_less,
6158d208deSAaron Tomlin .comp = mod_tree_comp,
6258d208deSAaron Tomlin };
6358d208deSAaron Tomlin
__mod_tree_insert(struct mod_tree_node * node,struct mod_tree_root * tree)64446d5566SChristophe Leroy static noinline void __mod_tree_insert(struct mod_tree_node *node, struct mod_tree_root *tree)
6558d208deSAaron Tomlin {
66446d5566SChristophe Leroy latch_tree_insert(&node->node, &tree->root, &mod_tree_ops);
6758d208deSAaron Tomlin }
6858d208deSAaron Tomlin
__mod_tree_remove(struct mod_tree_node * node,struct mod_tree_root * tree)69446d5566SChristophe Leroy static void __mod_tree_remove(struct mod_tree_node *node, struct mod_tree_root *tree)
7058d208deSAaron Tomlin {
71446d5566SChristophe Leroy latch_tree_erase(&node->node, &tree->root, &mod_tree_ops);
7258d208deSAaron Tomlin }
7358d208deSAaron Tomlin
7458d208deSAaron Tomlin /*
7558d208deSAaron Tomlin * These modifications: insert, remove_init and remove; are serialized by the
7658d208deSAaron Tomlin * module_mutex.
7758d208deSAaron Tomlin */
mod_tree_insert(struct module * mod)7858d208deSAaron Tomlin void mod_tree_insert(struct module *mod)
7958d208deSAaron Tomlin {
80*ac3b4328SSong Liu for_each_mod_mem_type(type) {
81*ac3b4328SSong Liu mod->mem[type].mtn.mod = mod;
82*ac3b4328SSong Liu if (mod->mem[type].size)
83*ac3b4328SSong Liu __mod_tree_insert(&mod->mem[type].mtn, &mod_tree);
84*ac3b4328SSong Liu }
8558d208deSAaron Tomlin }
8658d208deSAaron Tomlin
mod_tree_remove_init(struct module * mod)8758d208deSAaron Tomlin void mod_tree_remove_init(struct module *mod)
8858d208deSAaron Tomlin {
89*ac3b4328SSong Liu for_class_mod_mem_type(type, init) {
90*ac3b4328SSong Liu if (mod->mem[type].size)
91*ac3b4328SSong Liu __mod_tree_remove(&mod->mem[type].mtn, &mod_tree);
92*ac3b4328SSong Liu }
9358d208deSAaron Tomlin }
9458d208deSAaron Tomlin
mod_tree_remove(struct module * mod)9558d208deSAaron Tomlin void mod_tree_remove(struct module *mod)
9658d208deSAaron Tomlin {
97*ac3b4328SSong Liu for_each_mod_mem_type(type) {
98*ac3b4328SSong Liu if (mod->mem[type].size)
99*ac3b4328SSong Liu __mod_tree_remove(&mod->mem[type].mtn, &mod_tree);
100*ac3b4328SSong Liu }
10158d208deSAaron Tomlin }
10258d208deSAaron Tomlin
mod_find(unsigned long addr,struct mod_tree_root * tree)103446d5566SChristophe Leroy struct module *mod_find(unsigned long addr, struct mod_tree_root *tree)
10458d208deSAaron Tomlin {
10558d208deSAaron Tomlin struct latch_tree_node *ltn;
10658d208deSAaron Tomlin
107446d5566SChristophe Leroy ltn = latch_tree_find((void *)addr, &tree->root, &mod_tree_ops);
10858d208deSAaron Tomlin if (!ltn)
10958d208deSAaron Tomlin return NULL;
11058d208deSAaron Tomlin
11158d208deSAaron Tomlin return container_of(ltn, struct mod_tree_node, node)->mod;
11258d208deSAaron Tomlin }
113