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
 22static __always_inline unsigned long __mod_tree_val(struct latch_tree_node *n)
 23{
 24	struct module_layout *layout = container_of(n, struct module_layout, mtn.node);
 25
 26	return (unsigned long)layout->base;
 27}
 28
 29static __always_inline unsigned long __mod_tree_size(struct latch_tree_node *n)
 30{
 31	struct module_layout *layout = container_of(n, struct module_layout, mtn.node);
 32
 33	return (unsigned long)layout->size;
 34}
 35
 36static __always_inline bool
 37mod_tree_less(struct latch_tree_node *a, struct latch_tree_node *b)
 38{
 39	return __mod_tree_val(a) < __mod_tree_val(b);
 40}
 41
 42static __always_inline int
 43mod_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
 59static const struct latch_tree_ops mod_tree_ops = {
 60	.less = mod_tree_less,
 61	.comp = mod_tree_comp,
 62};
 63
 64static noinline void __mod_tree_insert(struct mod_tree_node *node, struct mod_tree_root *tree)
 65{
 66	latch_tree_insert(&node->node, &tree->root, &mod_tree_ops);
 67}
 68
 69static void __mod_tree_remove(struct mod_tree_node *node, struct mod_tree_root *tree)
 70{
 71	latch_tree_erase(&node->node, &tree->root, &mod_tree_ops);
 72}
 73
 74/*
 75 * These modifications: insert, remove_init and remove; are serialized by the
 76 * module_mutex.
 77 */
 78void mod_tree_insert(struct module *mod)
 79{
 80	mod->core_layout.mtn.mod = mod;
 81	mod->init_layout.mtn.mod = mod;
 82
 83	__mod_tree_insert(&mod->core_layout.mtn, &mod_tree);
 84	if (mod->init_layout.size)
 85		__mod_tree_insert(&mod->init_layout.mtn, &mod_tree);
 86
 87#ifdef CONFIG_ARCH_WANTS_MODULES_DATA_IN_VMALLOC
 88	mod->data_layout.mtn.mod = mod;
 89	__mod_tree_insert(&mod->data_layout.mtn, &mod_data_tree);
 90#endif
 91}
 92
 93void mod_tree_remove_init(struct module *mod)
 94{
 95	if (mod->init_layout.size)
 96		__mod_tree_remove(&mod->init_layout.mtn, &mod_tree);
 97}
 98
 99void mod_tree_remove(struct module *mod)
100{
101	__mod_tree_remove(&mod->core_layout.mtn, &mod_tree);
102	mod_tree_remove_init(mod);
103#ifdef CONFIG_ARCH_WANTS_MODULES_DATA_IN_VMALLOC
104	__mod_tree_remove(&mod->data_layout.mtn, &mod_data_tree);
105#endif
106}
107
108struct module *mod_find(unsigned long addr, struct mod_tree_root *tree)
109{
110	struct latch_tree_node *ltn;
111
112	ltn = latch_tree_find((void *)addr, &tree->root, &mod_tree_ops);
113	if (!ltn)
114		return NULL;
115
116	return container_of(ltn, struct mod_tree_node, node)->mod;
117}