[deliverable/linux.git] / arch / x86 / mm / pat_rbtree.c

/*
 * Handle caching attributes in page tables (PAT)
 *
 * Authors: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com>
 *          Suresh B Siddha <suresh.b.siddha@intel.com>
 *
 * Interval tree (augmented rbtree) used to store the PAT memory type
 * reservations.
 */

#include <linux/seq_file.h>
#include <linux/debugfs.h>
#include <linux/kernel.h>
#include <linux/rbtree_augmented.h>
#include <linux/sched.h>
#include <linux/gfp.h>

#include <asm/pgtable.h>
#include <asm/pat.h>

#include "pat_internal.h"

/*
 * The memtype tree keeps track of memory type for specific
 * physical memory areas. Without proper tracking, conflicting memory
 * types in different mappings can cause CPU cache corruption.
 *
 * The tree is an interval tree (augmented rbtree) with tree ordered
 * on starting address. Tree can contain multiple entries for
 * different regions which overlap. All the aliases have the same
 * cache attributes of course.
 *
 * memtype_lock protects the rbtree.
 */

static struct rb_root memtype_rbroot = RB_ROOT;

static int is_node_overlap(struct memtype *node, u64 start, u64 end)
{
	if (node->start >= end || node->end <= start)
		return 0;

	return 1;
}

static u64 get_subtree_max_end(struct rb_node *node)
{
	u64 ret = 0;
	if (node) {
		struct memtype *data = container_of(node, struct memtype, rb);
		ret = data->subtree_max_end;
	}
	return ret;
}

static u64 compute_subtree_max_end(struct memtype *data)
{
	u64 max_end = data->end, child_max_end;

	child_max_end = get_subtree_max_end(data->rb.rb_right);
	if (child_max_end > max_end)
		max_end = child_max_end;

	child_max_end = get_subtree_max_end(data->rb.rb_left);
	if (child_max_end > max_end)
		max_end = child_max_end;

	return max_end;
}

RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
		     u64, subtree_max_end, compute_subtree_max_end)

/* Find the first (lowest start addr) overlapping range from rb tree */
static struct memtype *memtype_rb_lowest_match(struct rb_root *root,
				u64 start, u64 end)
{
	struct rb_node *node = root->rb_node;
	struct memtype *last_lower = NULL;

	while (node) {
		struct memtype *data = container_of(node, struct memtype, rb);

		if (get_subtree_max_end(node->rb_left) > start) {
			/* Lowest overlap if any must be on left side */
			node = node->rb_left;
		} else if (is_node_overlap(data, start, end)) {
			last_lower = data;
			break;
		} else if (start >= data->start) {
			/* Lowest overlap if any must be on right side */
			node = node->rb_right;
		} else {
			break;
		}
	}
	return last_lower; /* Returns NULL if there is no overlap */
}

enum {
	MEMTYPE_EXACT_MATCH	= 0,
	MEMTYPE_END_MATCH	= 1
};

static struct memtype *memtype_rb_match(struct rb_root *root,
				u64 start, u64 end, int match_type)
{
	struct memtype *match;

	match = memtype_rb_lowest_match(root, start, end);
	while (match != NULL && match->start < end) {
		struct rb_node *node;

		if ((match_type == MEMTYPE_EXACT_MATCH) &&
		    (match->start == start) && (match->end == end))
			return match;

		if ((match_type == MEMTYPE_END_MATCH) &&
		    (match->start < start) && (match->end == end))
			return match;

		node = rb_next(&match->rb);
		if (node)
			match = container_of(node, struct memtype, rb);
		else
			match = NULL;
	}

	return NULL; /* Returns NULL if there is no match */
}

static int memtype_rb_check_conflict(struct rb_root *root,
				u64 start, u64 end,
				enum page_cache_mode reqtype,
				enum page_cache_mode *newtype)
{
	struct rb_node *node;
	struct memtype *match;
	enum page_cache_mode found_type = reqtype;

	match = memtype_rb_lowest_match(&memtype_rbroot, start, end);
	if (match == NULL)
		goto success;

	if (match->type != found_type && newtype == NULL)
		goto failure;

	dprintk("Overlap at 0x%Lx-0x%Lx\n", match->start, match->end);
	found_type = match->type;

	node = rb_next(&match->rb);
	while (node) {
		match = container_of(node, struct memtype, rb);

		if (match->start >= end) /* Checked all possible matches */
			goto success;

		if (is_node_overlap(match, start, end) &&
		    match->type != found_type) {
			goto failure;
		}

		node = rb_next(&match->rb);
	}
success:
	if (newtype)
		*newtype = found_type;

	return 0;

failure:
	pr_info("x86/PAT: %s:%d conflicting memory types %Lx-%Lx %s<->%s\n",
		current->comm, current->pid, start, end,
		cattr_name(found_type), cattr_name(match->type));
	return -EBUSY;
}

static void memtype_rb_insert(struct rb_root *root, struct memtype *newdata)
{
	struct rb_node **node = &(root->rb_node);
	struct rb_node *parent = NULL;

	while (*node) {
		struct memtype *data = container_of(*node, struct memtype, rb);

		parent = *node;
		if (data->subtree_max_end < newdata->end)
			data->subtree_max_end = newdata->end;
		if (newdata->start <= data->start)
			node = &((*node)->rb_left);
		else if (newdata->start > data->start)
			node = &((*node)->rb_right);
	}

	newdata->subtree_max_end = newdata->end;
	rb_link_node(&newdata->rb, parent, node);
	rb_insert_augmented(&newdata->rb, root, &memtype_rb_augment_cb);
}

int rbt_memtype_check_insert(struct memtype *new,
			     enum page_cache_mode *ret_type)
{
	int err = 0;

	err = memtype_rb_check_conflict(&memtype_rbroot, new->start, new->end,
						new->type, ret_type);

	if (!err) {
		if (ret_type)
			new->type = *ret_type;

		new->subtree_max_end = new->end;
		memtype_rb_insert(&memtype_rbroot, new);
	}
	return err;
}

struct memtype *rbt_memtype_erase(u64 start, u64 end)
{
	struct memtype *data;

	/*
	 * Since the memtype_rbroot tree allows overlapping ranges,
	 * rbt_memtype_erase() checks with EXACT_MATCH first, i.e. free
	 * a whole node for the munmap case.  If no such entry is found,
	 * it then checks with END_MATCH, i.e. shrink the size of a node
	 * from the end for the mremap case.
	 */
	data = memtype_rb_match(&memtype_rbroot, start, end,
				MEMTYPE_EXACT_MATCH);
	if (!data) {
		data = memtype_rb_match(&memtype_rbroot, start, end,
					MEMTYPE_END_MATCH);
		if (!data)
			return ERR_PTR(-EINVAL);
	}

	if (data->start == start) {
		/* munmap: erase this node */
		rb_erase_augmented(&data->rb, &memtype_rbroot,
					&memtype_rb_augment_cb);
	} else {
		/* mremap: update the end value of this node */
		rb_erase_augmented(&data->rb, &memtype_rbroot,
					&memtype_rb_augment_cb);
		data->end = start;
		data->subtree_max_end = data->end;
		memtype_rb_insert(&memtype_rbroot, data);
		return NULL;
	}

	return data;
}

struct memtype *rbt_memtype_lookup(u64 addr)
{
	struct memtype *data;
	data = memtype_rb_lowest_match(&memtype_rbroot, addr, addr + PAGE_SIZE);
	return data;
}

#if defined(CONFIG_DEBUG_FS)
int rbt_memtype_copy_nth_element(struct memtype *out, loff_t pos)
{
	struct rb_node *node;
	int i = 1;

	node = rb_first(&memtype_rbroot);
	while (node && pos != i) {
		node = rb_next(node);
		i++;
	}

	if (node) { /* pos == i */
		struct memtype *this = container_of(node, struct memtype, rb);
		*out = *this;
		return 0;
	} else {
		return 1;
	}
}
#endif
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>
9c079add	14	#include <linux/rbtree_augmented.h>
9e41a49a PV	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
b945d6b2	36	static struct rb_root memtype_rbroot = RB_ROOT;
9e41a49a PV	37
	38	static 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
	46	static 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
9d9e6f97	56	static u64 compute_subtree_max_end(struct memtype *data)
9e41a49a	57	{
9d9e6f97	58	u64 max_end = data->end, child_max_end;
9e41a49a	59
9d9e6f97	60	child_max_end = get_subtree_max_end(data->rb.rb_right);
9e41a49a PV	61	if (child_max_end > max_end)
	62	max_end = child_max_end;
	63
9d9e6f97	64	child_max_end = get_subtree_max_end(data->rb.rb_left);
9e41a49a PV	65	if (child_max_end > max_end)
	66	max_end = child_max_end;
	67
9d9e6f97 ML	68	return max_end;
	69	}
	70
3908836a ML	71	RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
3908836a ML	72	u64, subtree_max_end, compute_subtree_max_end)
9d9e6f97	73
9e41a49a PV	74	/* Find the first (lowest start addr) overlapping range from rb tree */
	75	static 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
2039e6ac TK	100	enum {
	101	MEMTYPE_EXACT_MATCH = 0,
	102	MEMTYPE_END_MATCH = 1
	103	};
	104
	105	static struct memtype memtype_rb_match(struct rb_root root,
	106	u64 start, u64 end, int match_type)
9e41a49a PV	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
2039e6ac TK	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))
9e41a49a PV	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
2039e6ac	129	return NULL; /* Returns NULL if there is no match */
9e41a49a PV	130	}
	131
	132	static int memtype_rb_check_conflict(struct rb_root *root,
	133	u64 start, u64 end,
e00c8cc9 JG	134	enum page_cache_mode reqtype,
e00c8cc9 JG	135	enum page_cache_mode *newtype)
9e41a49a PV	136	{
	137	struct rb_node *node;
	138	struct memtype *match;
e00c8cc9	139	enum page_cache_mode found_type = reqtype;
9e41a49a PV	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	}
	165	success:
	166	if (newtype)
	167	*newtype = found_type;
	168
	169	return 0;
	170
	171	failure:
9e76561f LR	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));
9e41a49a PV	175	return -EBUSY;
	176	}
	177
9e41a49a PV	178	static 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;
9d9e6f97 ML	187	if (data->subtree_max_end < newdata->end)
9d9e6f97 ML	188	data->subtree_max_end = newdata->end;
9e41a49a PV	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
9d9e6f97	195	newdata->subtree_max_end = newdata->end;
9e41a49a	196	rb_link_node(&newdata->rb, parent, node);
9d9e6f97	197	rb_insert_augmented(&newdata->rb, root, &memtype_rb_augment_cb);
9e41a49a PV	198	}
9e41a49a PV	199
e00c8cc9 JG	200	int rbt_memtype_check_insert(struct memtype *new,
e00c8cc9 JG	201	enum page_cache_mode *ret_type)
9e41a49a PV	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) {
4daa2a80 PV	209	if (ret_type)
	210	new->type = *ret_type;
	211
6a4f3b52	212	new->subtree_max_end = new->end;
9e41a49a PV	213	memtype_rb_insert(&memtype_rbroot, new);
	214	}
	215	return err;
	216	}
	217
20413f27	218	struct memtype *rbt_memtype_erase(u64 start, u64 end)
9e41a49a PV	219	{
	220	struct memtype *data;
	221
2039e6ac TK	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	}
9e41a49a	251
20413f27	252	return data;
9e41a49a PV	253	}
	254
	255	struct memtype *rbt_memtype_lookup(u64 addr)
	256	{
	257	struct memtype *data;
	258	data = memtype_rb_lowest_match(&memtype_rbroot, addr, addr + PAGE_SIZE);
	259	return data;
	260	}
	261
	262	#if defined(CONFIG_DEBUG_FS)
	263	int rbt_memtype_copy_nth_element(struct memtype *out, loff_t pos)
	264	{
	265	struct rb_node *node;
	266	int i = 1;
	267
	268	node = rb_first(&memtype_rbroot);
	269	while (node && pos != i) {
	270	node = rb_next(node);
	271	i++;
	272	}
	273
	274	if (node) { /* pos == i */
	275	struct memtype *this = container_of(node, struct memtype, rb);
	276	out = this;
	277	return 0;
	278	} else {
	279	return 1;
	280	}
	281	}
	282	#endif