1 // SPDX-License-Identifier: GPL-2.0
3 * Handle caching attributes in page tables (PAT)
5 * Authors: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com>
6 * Suresh B Siddha <suresh.b.siddha@intel.com>
8 * Interval tree used to store the PAT memory type reservations.
11 #include <linux/seq_file.h>
12 #include <linux/debugfs.h>
13 #include <linux/kernel.h>
14 #include <linux/interval_tree_generic.h>
15 #include <linux/sched.h>
16 #include <linux/gfp.h>
18 #include <asm/pgtable.h>
21 #include "pat_internal.h"
24 * The memtype tree keeps track of memory type for specific
25 * physical memory areas. Without proper tracking, conflicting memory
26 * types in different mappings can cause CPU cache corruption.
28 * The tree is an interval tree (augmented rbtree) with tree ordered
29 * on starting address. Tree can contain multiple entries for
30 * different regions which overlap. All the aliases have the same
31 * cache attributes of course.
33 * memtype_lock protects the rbtree.
35 static inline u64 memtype_interval_start(struct memtype *memtype)
37 return memtype->start;
40 static inline u64 memtype_interval_end(struct memtype *memtype)
42 return memtype->end - 1;
44 INTERVAL_TREE_DEFINE(struct memtype, rb, u64, subtree_max_end,
45 memtype_interval_start, memtype_interval_end,
46 static, memtype_interval)
48 static struct rb_root_cached memtype_rbroot = RB_ROOT_CACHED;
51 MEMTYPE_EXACT_MATCH = 0,
55 static struct memtype *memtype_match(u64 start, u64 end, int match_type)
57 struct memtype *match;
59 match = memtype_interval_iter_first(&memtype_rbroot, start, end);
60 while (match != NULL && match->start < end) {
61 if ((match_type == MEMTYPE_EXACT_MATCH) &&
62 (match->start == start) && (match->end == end))
65 if ((match_type == MEMTYPE_END_MATCH) &&
66 (match->start < start) && (match->end == end))
69 match = memtype_interval_iter_next(match, start, end);
72 return NULL; /* Returns NULL if there is no match */
75 static int memtype_check_conflict(u64 start, u64 end,
76 enum page_cache_mode reqtype,
77 enum page_cache_mode *newtype)
79 struct memtype *match;
80 enum page_cache_mode found_type = reqtype;
82 match = memtype_interval_iter_first(&memtype_rbroot, start, end);
86 if (match->type != found_type && newtype == NULL)
89 dprintk("Overlap at 0x%Lx-0x%Lx\n", match->start, match->end);
90 found_type = match->type;
92 match = memtype_interval_iter_next(match, start, end);
94 if (match->type != found_type)
97 match = memtype_interval_iter_next(match, start, end);
101 *newtype = found_type;
106 pr_info("x86/PAT: %s:%d conflicting memory types %Lx-%Lx %s<->%s\n",
107 current->comm, current->pid, start, end,
108 cattr_name(found_type), cattr_name(match->type));
112 int rbt_memtype_check_insert(struct memtype *new,
113 enum page_cache_mode *ret_type)
117 err = memtype_check_conflict(new->start, new->end, new->type, ret_type);
122 new->type = *ret_type;
124 memtype_interval_insert(new, &memtype_rbroot);
128 struct memtype *rbt_memtype_erase(u64 start, u64 end)
130 struct memtype *data;
133 * Since the memtype_rbroot tree allows overlapping ranges,
134 * rbt_memtype_erase() checks with EXACT_MATCH first, i.e. free
135 * a whole node for the munmap case. If no such entry is found,
136 * it then checks with END_MATCH, i.e. shrink the size of a node
137 * from the end for the mremap case.
139 data = memtype_match(start, end, MEMTYPE_EXACT_MATCH);
141 data = memtype_match(start, end, MEMTYPE_END_MATCH);
143 return ERR_PTR(-EINVAL);
146 if (data->start == start) {
147 /* munmap: erase this node */
148 memtype_interval_remove(data, &memtype_rbroot);
150 /* mremap: update the end value of this node */
151 memtype_interval_remove(data, &memtype_rbroot);
153 memtype_interval_insert(data, &memtype_rbroot);
160 struct memtype *rbt_memtype_lookup(u64 addr)
162 return memtype_interval_iter_first(&memtype_rbroot, addr,
166 #if defined(CONFIG_DEBUG_FS)
167 int rbt_memtype_copy_nth_element(struct memtype *out, loff_t pos)
169 struct memtype *match;
172 match = memtype_interval_iter_first(&memtype_rbroot, 0, ULONG_MAX);
173 while (match && pos != i) {
174 match = memtype_interval_iter_next(match, 0, ULONG_MAX);
178 if (match) { /* pos == i */