]>
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, | |
e00c8cc9 JG |
125 | enum page_cache_mode reqtype, |
126 | enum page_cache_mode *newtype) | |
9e41a49a PV |
127 | { |
128 | struct rb_node *node; | |
129 | struct memtype *match; | |
e00c8cc9 | 130 | enum page_cache_mode found_type = reqtype; |
9e41a49a PV |
131 | |
132 | match = memtype_rb_lowest_match(&memtype_rbroot, start, end); | |
133 | if (match == NULL) | |
134 | goto success; | |
135 | ||
136 | if (match->type != found_type && newtype == NULL) | |
137 | goto failure; | |
138 | ||
139 | dprintk("Overlap at 0x%Lx-0x%Lx\n", match->start, match->end); | |
140 | found_type = match->type; | |
141 | ||
142 | node = rb_next(&match->rb); | |
143 | while (node) { | |
144 | match = container_of(node, struct memtype, rb); | |
145 | ||
146 | if (match->start >= end) /* Checked all possible matches */ | |
147 | goto success; | |
148 | ||
149 | if (is_node_overlap(match, start, end) && | |
150 | match->type != found_type) { | |
151 | goto failure; | |
152 | } | |
153 | ||
154 | node = rb_next(&match->rb); | |
155 | } | |
156 | success: | |
157 | if (newtype) | |
158 | *newtype = found_type; | |
159 | ||
160 | return 0; | |
161 | ||
162 | failure: | |
163 | printk(KERN_INFO "%s:%d conflicting memory types " | |
164 | "%Lx-%Lx %s<->%s\n", current->comm, current->pid, start, | |
165 | end, cattr_name(found_type), cattr_name(match->type)); | |
166 | return -EBUSY; | |
167 | } | |
168 | ||
9e41a49a PV |
169 | static void memtype_rb_insert(struct rb_root *root, struct memtype *newdata) |
170 | { | |
171 | struct rb_node **node = &(root->rb_node); | |
172 | struct rb_node *parent = NULL; | |
173 | ||
174 | while (*node) { | |
175 | struct memtype *data = container_of(*node, struct memtype, rb); | |
176 | ||
177 | parent = *node; | |
9d9e6f97 ML |
178 | if (data->subtree_max_end < newdata->end) |
179 | data->subtree_max_end = newdata->end; | |
9e41a49a PV |
180 | if (newdata->start <= data->start) |
181 | node = &((*node)->rb_left); | |
182 | else if (newdata->start > data->start) | |
183 | node = &((*node)->rb_right); | |
184 | } | |
185 | ||
9d9e6f97 | 186 | newdata->subtree_max_end = newdata->end; |
9e41a49a | 187 | rb_link_node(&newdata->rb, parent, node); |
9d9e6f97 | 188 | rb_insert_augmented(&newdata->rb, root, &memtype_rb_augment_cb); |
9e41a49a PV |
189 | } |
190 | ||
e00c8cc9 JG |
191 | int rbt_memtype_check_insert(struct memtype *new, |
192 | enum page_cache_mode *ret_type) | |
9e41a49a PV |
193 | { |
194 | int err = 0; | |
195 | ||
196 | err = memtype_rb_check_conflict(&memtype_rbroot, new->start, new->end, | |
197 | new->type, ret_type); | |
198 | ||
199 | if (!err) { | |
4daa2a80 PV |
200 | if (ret_type) |
201 | new->type = *ret_type; | |
202 | ||
6a4f3b52 | 203 | new->subtree_max_end = new->end; |
9e41a49a PV |
204 | memtype_rb_insert(&memtype_rbroot, new); |
205 | } | |
206 | return err; | |
207 | } | |
208 | ||
20413f27 | 209 | struct memtype *rbt_memtype_erase(u64 start, u64 end) |
9e41a49a PV |
210 | { |
211 | struct memtype *data; | |
212 | ||
213 | data = memtype_rb_exact_match(&memtype_rbroot, start, end); | |
214 | if (!data) | |
20413f27 | 215 | goto out; |
9e41a49a | 216 | |
9d9e6f97 | 217 | rb_erase_augmented(&data->rb, &memtype_rbroot, &memtype_rb_augment_cb); |
20413f27 XF |
218 | out: |
219 | return data; | |
9e41a49a PV |
220 | } |
221 | ||
222 | struct memtype *rbt_memtype_lookup(u64 addr) | |
223 | { | |
224 | struct memtype *data; | |
225 | data = memtype_rb_lowest_match(&memtype_rbroot, addr, addr + PAGE_SIZE); | |
226 | return data; | |
227 | } | |
228 | ||
229 | #if defined(CONFIG_DEBUG_FS) | |
230 | int rbt_memtype_copy_nth_element(struct memtype *out, loff_t pos) | |
231 | { | |
232 | struct rb_node *node; | |
233 | int i = 1; | |
234 | ||
235 | node = rb_first(&memtype_rbroot); | |
236 | while (node && pos != i) { | |
237 | node = rb_next(node); | |
238 | i++; | |
239 | } | |
240 | ||
241 | if (node) { /* pos == i */ | |
242 | struct memtype *this = container_of(node, struct memtype, rb); | |
243 | *out = *this; | |
244 | return 0; | |
245 | } else { | |
246 | return 1; | |
247 | } | |
248 | } | |
249 | #endif |