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/rbtree_augmented.h>
 15#include <linux/sched.h>
 16#include <linux/gfp.h>
 17
 18#include <asm/pgtable.h>
 19#include <asm/pat.h>
 20
 21#include "pat_internal.h"
 22
 23/*
 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.
 27 *
 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.
 32 *
 33 * memtype_lock protects the rbtree.
 34 */
 35
 36static struct rb_root memtype_rbroot = RB_ROOT;
 37
 38static int is_node_overlap(struct memtype *node, u64 start, u64 end)
 39{
 40	if (node->start >= end || node->end <= start)
 41		return 0;
 42
 43	return 1;
 44}
 45
 46static u64 get_subtree_max_end(struct rb_node *node)
 47{
 48	u64 ret = 0;
 49	if (node) {
 50		struct memtype *data = container_of(node, struct memtype, rb);
 51		ret = data->subtree_max_end;
 52	}
 53	return ret;
 54}
 55
 56static u64 compute_subtree_max_end(struct memtype *data)
 57{
 58	u64 max_end = data->end, child_max_end;
 59
 60	child_max_end = get_subtree_max_end(data->rb.rb_right);
 61	if (child_max_end > max_end)
 62		max_end = child_max_end;
 63
 64	child_max_end = get_subtree_max_end(data->rb.rb_left);
 65	if (child_max_end > max_end)
 66		max_end = child_max_end;
 67
 68	return max_end;
 69}
 70
 71RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
 72		     u64, subtree_max_end, compute_subtree_max_end)
 73
 74/* Find the first (lowest start addr) overlapping range from rb tree */
 75static struct memtype *memtype_rb_lowest_match(struct rb_root *root,
 76				u64 start, u64 end)
 77{
 78	struct rb_node *node = root->rb_node;
 79	struct memtype *last_lower = NULL;
 80
 81	while (node) {
 82		struct memtype *data = container_of(node, struct memtype, rb);
 83
 84		if (get_subtree_max_end(node->rb_left) > start) {
 85			/* Lowest overlap if any must be on left side */
 86			node = node->rb_left;
 87		} else if (is_node_overlap(data, start, end)) {
 88			last_lower = data;
 89			break;
 90		} else if (start >= data->start) {
 91			/* Lowest overlap if any must be on right side */
 92			node = node->rb_right;
 93		} else {
 94			break;
 95		}
 96	}
 97	return last_lower; /* Returns NULL if there is no overlap */
 98}
 99
100enum {
101	MEMTYPE_EXACT_MATCH	= 0,
102	MEMTYPE_END_MATCH	= 1
103};
104
105static struct memtype *memtype_rb_match(struct rb_root *root,
106				u64 start, u64 end, int match_type)
107{
108	struct memtype *match;
109
110	match = memtype_rb_lowest_match(root, start, end);
111	while (match != NULL && match->start < end) {
112		struct rb_node *node;
113
114		if ((match_type == MEMTYPE_EXACT_MATCH) &&
115		    (match->start == start) && (match->end == end))
116			return match;
117
118		if ((match_type == MEMTYPE_END_MATCH) &&
119		    (match->start < start) && (match->end == end))
120			return match;
121
122		node = rb_next(&match->rb);
123		if (node)
124			match = container_of(node, struct memtype, rb);
125		else
126			match = NULL;
127	}
128
129	return NULL; /* Returns NULL if there is no match */
130}
131
132static int memtype_rb_check_conflict(struct rb_root *root,
133				u64 start, u64 end,
134				enum page_cache_mode reqtype,
135				enum page_cache_mode *newtype)
136{
137	struct rb_node *node;
138	struct memtype *match;
139	enum page_cache_mode found_type = reqtype;
140
141	match = memtype_rb_lowest_match(&memtype_rbroot, start, end);
142	if (match == NULL)
143		goto success;
144
145	if (match->type != found_type && newtype == NULL)
146		goto failure;
147
148	dprintk("Overlap at 0x%Lx-0x%Lx\n", match->start, match->end);
149	found_type = match->type;
150
151	node = rb_next(&match->rb);
152	while (node) {
153		match = container_of(node, struct memtype, rb);
154
155		if (match->start >= end) /* Checked all possible matches */
156			goto success;
157
158		if (is_node_overlap(match, start, end) &&
159		    match->type != found_type) {
160			goto failure;
161		}
162
163		node = rb_next(&match->rb);
164	}
165success:
166	if (newtype)
167		*newtype = found_type;
168
169	return 0;
170
171failure:
172	pr_info("x86/PAT: %s:%d conflicting memory types %Lx-%Lx %s<->%s\n",
173		current->comm, current->pid, start, end,
174		cattr_name(found_type), cattr_name(match->type));
175	return -EBUSY;
176}
177
178static void memtype_rb_insert(struct rb_root *root, struct memtype *newdata)
179{
180	struct rb_node **node = &(root->rb_node);
181	struct rb_node *parent = NULL;
182
183	while (*node) {
184		struct memtype *data = container_of(*node, struct memtype, rb);
185
186		parent = *node;
187		if (data->subtree_max_end < newdata->end)
188			data->subtree_max_end = newdata->end;
189		if (newdata->start <= data->start)
190			node = &((*node)->rb_left);
191		else if (newdata->start > data->start)
192			node = &((*node)->rb_right);
193	}
194
195	newdata->subtree_max_end = newdata->end;
196	rb_link_node(&newdata->rb, parent, node);
197	rb_insert_augmented(&newdata->rb, root, &memtype_rb_augment_cb);
198}
199
200int rbt_memtype_check_insert(struct memtype *new,
201			     enum page_cache_mode *ret_type)
202{
203	int err = 0;
204
205	err = memtype_rb_check_conflict(&memtype_rbroot, new->start, new->end,
206						new->type, ret_type);
207
208	if (!err) {
209		if (ret_type)
210			new->type = *ret_type;
211
212		new->subtree_max_end = new->end;
213		memtype_rb_insert(&memtype_rbroot, new);
214	}
215	return err;
216}
217
218struct memtype *rbt_memtype_erase(u64 start, u64 end)
219{
220	struct memtype *data;
221
222	/*
223	 * Since the memtype_rbroot tree allows overlapping ranges,
224	 * rbt_memtype_erase() checks with EXACT_MATCH first, i.e. free
225	 * a whole node for the munmap case.  If no such entry is found,
226	 * it then checks with END_MATCH, i.e. shrink the size of a node
227	 * from the end for the mremap case.
228	 */
229	data = memtype_rb_match(&memtype_rbroot, start, end,
230				MEMTYPE_EXACT_MATCH);
231	if (!data) {
232		data = memtype_rb_match(&memtype_rbroot, start, end,
233					MEMTYPE_END_MATCH);
234		if (!data)
235			return ERR_PTR(-EINVAL);
236	}
237
238	if (data->start == start) {
239		/* munmap: erase this node */
240		rb_erase_augmented(&data->rb, &memtype_rbroot,
241					&memtype_rb_augment_cb);
242	} else {
243		/* mremap: update the end value of this node */
244		rb_erase_augmented(&data->rb, &memtype_rbroot,
245					&memtype_rb_augment_cb);
246		data->end = start;
247		data->subtree_max_end = data->end;
248		memtype_rb_insert(&memtype_rbroot, data);
249		return NULL;
250	}
251
252	return data;
253}
254
255struct memtype *rbt_memtype_lookup(u64 addr)
256{
257	return memtype_rb_lowest_match(&memtype_rbroot, addr, addr + PAGE_SIZE);
258}
259
260#if defined(CONFIG_DEBUG_FS)
261int rbt_memtype_copy_nth_element(struct memtype *out, loff_t pos)
262{
263	struct rb_node *node;
264	int i = 1;
265
266	node = rb_first(&memtype_rbroot);
267	while (node && pos != i) {
268		node = rb_next(node);
269		i++;
270	}
271
272	if (node) { /* pos == i */
273		struct memtype *this = container_of(node, struct memtype, rb);
274		*out = *this;
275		return 0;
276	} else {
277		return 1;
278	}
279}
280#endif