Commit | Line | Data |
---|---|---|
9e41a49a PV |
1 | /* |
2 | * Handle caching attributes in page tables (PAT) | |
3 | * | |
4 | * Authors: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com> | |
5 | * Suresh B Siddha <suresh.b.siddha@intel.com> | |
6 | * | |
7 | * Interval tree (augmented rbtree) used to store the PAT memory type | |
8 | * reservations. | |
9 | */ | |
10 | ||
11 | #include <linux/seq_file.h> | |
12 | #include <linux/debugfs.h> | |
13 | #include <linux/kernel.h> | |
14 | #include <linux/module.h> | |
9c079add | 15 | #include <linux/rbtree_augmented.h> |
9e41a49a PV |
16 | #include <linux/sched.h> |
17 | #include <linux/gfp.h> | |
18 | ||
19 | #include <asm/pgtable.h> | |
20 | #include <asm/pat.h> | |
21 | ||
22 | #include "pat_internal.h" | |
23 | ||
24 | /* | |
25 | * The memtype tree keeps track of memory type for specific | |
26 | * physical memory areas. Without proper tracking, conflicting memory | |
27 | * types in different mappings can cause CPU cache corruption. | |
28 | * | |
29 | * The tree is an interval tree (augmented rbtree) with tree ordered | |
30 | * on starting address. Tree can contain multiple entries for | |
31 | * different regions which overlap. All the aliases have the same | |
32 | * cache attributes of course. | |
33 | * | |
34 | * memtype_lock protects the rbtree. | |
35 | */ | |
36 | ||
b945d6b2 | 37 | static struct rb_root memtype_rbroot = RB_ROOT; |
9e41a49a PV |
38 | |
39 | static int is_node_overlap(struct memtype *node, u64 start, u64 end) | |
40 | { | |
41 | if (node->start >= end || node->end <= start) | |
42 | return 0; | |
43 | ||
44 | return 1; | |
45 | } | |
46 | ||
47 | static u64 get_subtree_max_end(struct rb_node *node) | |
48 | { | |
49 | u64 ret = 0; | |
50 | if (node) { | |
51 | struct memtype *data = container_of(node, struct memtype, rb); | |
52 | ret = data->subtree_max_end; | |
53 | } | |
54 | return ret; | |
55 | } | |
56 | ||
9d9e6f97 | 57 | static u64 compute_subtree_max_end(struct memtype *data) |
9e41a49a | 58 | { |
9d9e6f97 | 59 | u64 max_end = data->end, child_max_end; |
9e41a49a | 60 | |
9d9e6f97 | 61 | child_max_end = get_subtree_max_end(data->rb.rb_right); |
9e41a49a PV |
62 | if (child_max_end > max_end) |
63 | max_end = child_max_end; | |
64 | ||
9d9e6f97 | 65 | child_max_end = get_subtree_max_end(data->rb.rb_left); |
9e41a49a PV |
66 | if (child_max_end > max_end) |
67 | max_end = child_max_end; | |
68 | ||
9d9e6f97 ML |
69 | return max_end; |
70 | } | |
71 | ||
3908836a ML |
72 | RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb, |
73 | u64, subtree_max_end, compute_subtree_max_end) | |
9d9e6f97 | 74 | |
9e41a49a PV |
75 | /* Find the first (lowest start addr) overlapping range from rb tree */ |
76 | static struct memtype *memtype_rb_lowest_match(struct rb_root *root, | |
77 | u64 start, u64 end) | |
78 | { | |
79 | struct rb_node *node = root->rb_node; | |
80 | struct memtype *last_lower = NULL; | |
81 | ||
82 | while (node) { | |
83 | struct memtype *data = container_of(node, struct memtype, rb); | |
84 | ||
85 | if (get_subtree_max_end(node->rb_left) > start) { | |
86 | /* Lowest overlap if any must be on left side */ | |
87 | node = node->rb_left; | |
88 | } else if (is_node_overlap(data, start, end)) { | |
89 | last_lower = data; | |
90 | break; | |
91 | } else if (start >= data->start) { | |
92 | /* Lowest overlap if any must be on right side */ | |
93 | node = node->rb_right; | |
94 | } else { | |
95 | break; | |
96 | } | |
97 | } | |
98 | return last_lower; /* Returns NULL if there is no overlap */ | |
99 | } | |
100 | ||
101 | static struct memtype *memtype_rb_exact_match(struct rb_root *root, | |
102 | u64 start, u64 end) | |
103 | { | |
104 | struct memtype *match; | |
105 | ||
106 | match = memtype_rb_lowest_match(root, start, end); | |
107 | while (match != NULL && match->start < end) { | |
108 | struct rb_node *node; | |
109 | ||
110 | if (match->start == start && match->end == end) | |
111 | return match; | |
112 | ||
113 | node = rb_next(&match->rb); | |
114 | if (node) | |
115 | match = container_of(node, struct memtype, rb); | |
116 | else | |
117 | match = NULL; | |
118 | } | |
119 | ||
120 | return NULL; /* Returns NULL if there is no exact match */ | |
121 | } | |
122 | ||
123 | static int memtype_rb_check_conflict(struct rb_root *root, | |
124 | u64 start, u64 end, | |
125 | unsigned long reqtype, unsigned long *newtype) | |
126 | { | |
127 | struct rb_node *node; | |
128 | struct memtype *match; | |
129 | int found_type = reqtype; | |
130 | ||
131 | match = memtype_rb_lowest_match(&memtype_rbroot, start, end); | |
132 | if (match == NULL) | |
133 | goto success; | |
134 | ||
135 | if (match->type != found_type && newtype == NULL) | |
136 | goto failure; | |
137 | ||
138 | dprintk("Overlap at 0x%Lx-0x%Lx\n", match->start, match->end); | |
139 | found_type = match->type; | |
140 | ||
141 | node = rb_next(&match->rb); | |
142 | while (node) { | |
143 | match = container_of(node, struct memtype, rb); | |
144 | ||
145 | if (match->start >= end) /* Checked all possible matches */ | |
146 | goto success; | |
147 | ||
148 | if (is_node_overlap(match, start, end) && | |
149 | match->type != found_type) { | |
150 | goto failure; | |
151 | } | |
152 | ||
153 | node = rb_next(&match->rb); | |
154 | } | |
155 | success: | |
156 | if (newtype) | |
157 | *newtype = found_type; | |
158 | ||
159 | return 0; | |
160 | ||
161 | failure: | |
162 | printk(KERN_INFO "%s:%d conflicting memory types " | |
163 | "%Lx-%Lx %s<->%s\n", current->comm, current->pid, start, | |
164 | end, cattr_name(found_type), cattr_name(match->type)); | |
165 | return -EBUSY; | |
166 | } | |
167 | ||
9e41a49a PV |
168 | static void memtype_rb_insert(struct rb_root *root, struct memtype *newdata) |
169 | { | |
170 | struct rb_node **node = &(root->rb_node); | |
171 | struct rb_node *parent = NULL; | |
172 | ||
173 | while (*node) { | |
174 | struct memtype *data = container_of(*node, struct memtype, rb); | |
175 | ||
176 | parent = *node; | |
9d9e6f97 ML |
177 | if (data->subtree_max_end < newdata->end) |
178 | data->subtree_max_end = newdata->end; | |
9e41a49a PV |
179 | if (newdata->start <= data->start) |
180 | node = &((*node)->rb_left); | |
181 | else if (newdata->start > data->start) | |
182 | node = &((*node)->rb_right); | |
183 | } | |
184 | ||
9d9e6f97 | 185 | newdata->subtree_max_end = newdata->end; |
9e41a49a | 186 | rb_link_node(&newdata->rb, parent, node); |
9d9e6f97 | 187 | rb_insert_augmented(&newdata->rb, root, &memtype_rb_augment_cb); |
9e41a49a PV |
188 | } |
189 | ||
190 | int rbt_memtype_check_insert(struct memtype *new, unsigned long *ret_type) | |
191 | { | |
192 | int err = 0; | |
193 | ||
194 | err = memtype_rb_check_conflict(&memtype_rbroot, new->start, new->end, | |
195 | new->type, ret_type); | |
196 | ||
197 | if (!err) { | |
4daa2a80 PV |
198 | if (ret_type) |
199 | new->type = *ret_type; | |
200 | ||
6a4f3b52 | 201 | new->subtree_max_end = new->end; |
9e41a49a PV |
202 | memtype_rb_insert(&memtype_rbroot, new); |
203 | } | |
204 | return err; | |
205 | } | |
206 | ||
20413f27 | 207 | struct memtype *rbt_memtype_erase(u64 start, u64 end) |
9e41a49a PV |
208 | { |
209 | struct memtype *data; | |
210 | ||
211 | data = memtype_rb_exact_match(&memtype_rbroot, start, end); | |
212 | if (!data) | |
20413f27 | 213 | goto out; |
9e41a49a | 214 | |
9d9e6f97 | 215 | rb_erase_augmented(&data->rb, &memtype_rbroot, &memtype_rb_augment_cb); |
20413f27 XF |
216 | out: |
217 | return data; | |
9e41a49a PV |
218 | } |
219 | ||
220 | struct memtype *rbt_memtype_lookup(u64 addr) | |
221 | { | |
222 | struct memtype *data; | |
223 | data = memtype_rb_lowest_match(&memtype_rbroot, addr, addr + PAGE_SIZE); | |
224 | return data; | |
225 | } | |
226 | ||
227 | #if defined(CONFIG_DEBUG_FS) | |
228 | int rbt_memtype_copy_nth_element(struct memtype *out, loff_t pos) | |
229 | { | |
230 | struct rb_node *node; | |
231 | int i = 1; | |
232 | ||
233 | node = rb_first(&memtype_rbroot); | |
234 | while (node && pos != i) { | |
235 | node = rb_next(node); | |
236 | i++; | |
237 | } | |
238 | ||
239 | if (node) { /* pos == i */ | |
240 | struct memtype *this = container_of(node, struct memtype, rb); | |
241 | *out = *this; | |
242 | return 0; | |
243 | } else { | |
244 | return 1; | |
245 | } | |
246 | } | |
247 | #endif |