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_memory *mod_mem = container_of(n, struct module_memory, mtn.node);
 25
 26	return (unsigned long)mod_mem->base;
 27}
 28
 29static __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
 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	for_each_mod_mem_type(type) {
 81		mod->mem[type].mtn.mod = mod;
 82		if (mod->mem[type].size)
 83			__mod_tree_insert(&mod->mem[type].mtn, &mod_tree);
 84	}
 85}
 86
 87void 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(&mod->mem[type].mtn, &mod_tree);
 92	}
 93}
 94
 95void mod_tree_remove(struct module *mod)
 96{
 97	for_each_mod_mem_type(type) {
 98		if (mod->mem[type].size)
 99			__mod_tree_remove(&mod->mem[type].mtn, &mod_tree);
100	}
101}
102
103struct module *mod_find(unsigned long addr, struct mod_tree_root *tree)
104{
105	struct latch_tree_node *ltn;
106
107	ltn = latch_tree_find((void *)addr, &tree->root, &mod_tree_ops);
108	if (!ltn)
109		return NULL;
110
111	return container_of(ltn, struct mod_tree_node, node)->mod;
112}