[mirror_ubuntu-bionic-kernel.git] / arch / x86 / mm / pat_rbtree.c

// SPDX-License-Identifier: GPL-2.0
/*
 * 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 = rb_entry(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 = rb_entry(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 = rb_entry(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 = rb_entry(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 = rb_entry(*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)
{
	return memtype_rb_lowest_match(&memtype_rbroot, addr, addr + PAGE_SIZE);
}

#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 = rb_entry(node, struct memtype, rb);
		*out = *this;
		return 0;
	} else {
		return 1;
	}
}
#endif
Commit	Line	Data
b2441318	1	// SPDX-License-Identifier: GPL-2.0
9e41a49a PV	2	/*
	3	* Handle caching attributes in page tables (PAT)
	4	*
	5	* Authors: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com>
	6	* Suresh B Siddha <suresh.b.siddha@intel.com>
	7	*
	8	* Interval tree (augmented rbtree) used to store the PAT memory type
	9	* reservations.
	10	*/
	11
	12	#include <linux/seq_file.h>
	13	#include <linux/debugfs.h>
	14	#include <linux/kernel.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) {
1013fe32	51	struct memtype *data = rb_entry(node, struct memtype, rb);
9e41a49a PV	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,
3908836a ML	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) {
1013fe32	83	struct memtype *data = rb_entry(node, struct memtype, rb);
9e41a49a PV	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
2039e6ac TK	101	enum {
	102	MEMTYPE_EXACT_MATCH = 0,
	103	MEMTYPE_END_MATCH = 1
	104	};
	105
	106	static struct memtype memtype_rb_match(struct rb_root root,
	107	u64 start, u64 end, int match_type)
9e41a49a PV	108	{
	109	struct memtype *match;
	110
	111	match = memtype_rb_lowest_match(root, start, end);
	112	while (match != NULL && match->start < end) {
	113	struct rb_node *node;
	114
2039e6ac TK	115	if ((match_type == MEMTYPE_EXACT_MATCH) &&
	116	(match->start == start) && (match->end == end))
	117	return match;
	118
	119	if ((match_type == MEMTYPE_END_MATCH) &&
	120	(match->start < start) && (match->end == end))
9e41a49a PV	121	return match;
	122
	123	node = rb_next(&match->rb);
	124	if (node)
1013fe32	125	match = rb_entry(node, struct memtype, rb);
9e41a49a PV	126	else
	127	match = NULL;
	128	}
	129
2039e6ac	130	return NULL; /* Returns NULL if there is no match */
9e41a49a PV	131	}
	132
	133	static int memtype_rb_check_conflict(struct rb_root *root,
	134	u64 start, u64 end,
e00c8cc9 JG	135	enum page_cache_mode reqtype,
e00c8cc9 JG	136	enum page_cache_mode *newtype)
9e41a49a PV	137	{
	138	struct rb_node *node;
	139	struct memtype *match;
e00c8cc9	140	enum page_cache_mode found_type = reqtype;
9e41a49a PV	141
	142	match = memtype_rb_lowest_match(&memtype_rbroot, start, end);
	143	if (match == NULL)
	144	goto success;
	145
	146	if (match->type != found_type && newtype == NULL)
	147	goto failure;
	148
	149	dprintk("Overlap at 0x%Lx-0x%Lx\n", match->start, match->end);
	150	found_type = match->type;
	151
	152	node = rb_next(&match->rb);
	153	while (node) {
1013fe32	154	match = rb_entry(node, struct memtype, rb);
9e41a49a PV	155
	156	if (match->start >= end) /* Checked all possible matches */
	157	goto success;
	158
	159	if (is_node_overlap(match, start, end) &&
	160	match->type != found_type) {
	161	goto failure;
	162	}
	163
	164	node = rb_next(&match->rb);
	165	}
	166	success:
	167	if (newtype)
	168	*newtype = found_type;
	169
	170	return 0;
	171
	172	failure:
9e76561f LR	173	pr_info("x86/PAT: %s:%d conflicting memory types %Lx-%Lx %s<->%s\n",
	174	current->comm, current->pid, start, end,
	175	cattr_name(found_type), cattr_name(match->type));
9e41a49a PV	176	return -EBUSY;
	177	}
	178
9e41a49a PV	179	static void memtype_rb_insert(struct rb_root root, struct memtype newdata)
	180	{
	181	struct rb_node **node = &(root->rb_node);
	182	struct rb_node *parent = NULL;
	183
	184	while (*node) {
1013fe32	185	struct memtype data = rb_entry(node, struct memtype, rb);
9e41a49a PV	186
9e41a49a PV	187	parent = *node;
9d9e6f97 ML	188	if (data->subtree_max_end < newdata->end)
9d9e6f97 ML	189	data->subtree_max_end = newdata->end;
9e41a49a PV	190	if (newdata->start <= data->start)
	191	node = &((*node)->rb_left);
	192	else if (newdata->start > data->start)
	193	node = &((*node)->rb_right);
	194	}
	195
9d9e6f97	196	newdata->subtree_max_end = newdata->end;
9e41a49a	197	rb_link_node(&newdata->rb, parent, node);
9d9e6f97	198	rb_insert_augmented(&newdata->rb, root, &memtype_rb_augment_cb);
9e41a49a PV	199	}
9e41a49a PV	200
e00c8cc9 JG	201	int rbt_memtype_check_insert(struct memtype *new,
e00c8cc9 JG	202	enum page_cache_mode *ret_type)
9e41a49a PV	203	{
	204	int err = 0;
	205
	206	err = memtype_rb_check_conflict(&memtype_rbroot, new->start, new->end,
	207	new->type, ret_type);
	208
	209	if (!err) {
4daa2a80 PV	210	if (ret_type)
	211	new->type = *ret_type;
	212
6a4f3b52	213	new->subtree_max_end = new->end;
9e41a49a PV	214	memtype_rb_insert(&memtype_rbroot, new);
	215	}
	216	return err;
	217	}
	218
20413f27	219	struct memtype *rbt_memtype_erase(u64 start, u64 end)
9e41a49a PV	220	{
	221	struct memtype *data;
	222
2039e6ac TK	223	/*
	224	* Since the memtype_rbroot tree allows overlapping ranges,
	225	* rbt_memtype_erase() checks with EXACT_MATCH first, i.e. free
	226	* a whole node for the munmap case. If no such entry is found,
	227	* it then checks with END_MATCH, i.e. shrink the size of a node
	228	* from the end for the mremap case.
	229	*/
	230	data = memtype_rb_match(&memtype_rbroot, start, end,
	231	MEMTYPE_EXACT_MATCH);
	232	if (!data) {
	233	data = memtype_rb_match(&memtype_rbroot, start, end,
	234	MEMTYPE_END_MATCH);
	235	if (!data)
	236	return ERR_PTR(-EINVAL);
	237	}
	238
	239	if (data->start == start) {
	240	/* munmap: erase this node */
	241	rb_erase_augmented(&data->rb, &memtype_rbroot,
	242	&memtype_rb_augment_cb);
	243	} else {
	244	/* mremap: update the end value of this node */
	245	rb_erase_augmented(&data->rb, &memtype_rbroot,
	246	&memtype_rb_augment_cb);
	247	data->end = start;
	248	data->subtree_max_end = data->end;
	249	memtype_rb_insert(&memtype_rbroot, data);
	250	return NULL;
	251	}
9e41a49a	252
20413f27	253	return data;
9e41a49a PV	254	}
	255
	256	struct memtype *rbt_memtype_lookup(u64 addr)
	257	{
f148b41e	258	return memtype_rb_lowest_match(&memtype_rbroot, addr, addr + PAGE_SIZE);
9e41a49a PV	259	}
	260
	261	#if defined(CONFIG_DEBUG_FS)
	262	int rbt_memtype_copy_nth_element(struct memtype *out, loff_t pos)
	263	{
	264	struct rb_node *node;
	265	int i = 1;
	266
	267	node = rb_first(&memtype_rbroot);
	268	while (node && pos != i) {
	269	node = rb_next(node);
	270	i++;
	271	}
	272
	273	if (node) { /* pos == i */
1013fe32	274	struct memtype *this = rb_entry(node, struct memtype, rb);
9e41a49a PV	275	out = this;
	276	return 0;
	277	} else {
	278	return 1;
	279	}
	280	}
	281	#endif