[PATCH 1/2 V2] kvm tools: Add interval red-black tree helper

[PATCH 1/2 V2] kvm tools: Add interval red-black tree helper

[Sasha Levin]

Interval rb-tree allows to directly store interval ranges
and quickly lookup an overlap with a single point or a range.

The helper is based on the kernel rb-tree implementation
(located in <linux/rbtree.h>) which alows for the augmention
of the classical rb-tree to be used as an interval tree.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
 tools/kvm/Makefile                      |    1 +
 tools/kvm/include/kvm/rbtree-interval.h |   27 +++++++++
 tools/kvm/util/rbtree-interval.c        |   91 +++++++++++++++++++++++++++++++
 3 files changed, 119 insertions(+), 0 deletions(-)
 create mode 100644 tools/kvm/include/kvm/rbtree-interval.h
 create mode 100644 tools/kvm/util/rbtree-interval.c

diff --git a/tools/kvm/Makefile b/tools/kvm/Makefile
index 64fdcbe..45897d5 100644
--- a/tools/kvm/Makefile
+++ b/tools/kvm/Makefile
@@ -42,6 +42,7 @@ OBJS    += mptable.o
 OBJS    += threadpool.o
 OBJS    += irq.o
 OBJS    += ../../lib/rbtree.o
+OBJS    += util/rbtree-interval.o
 
 DEPS	:= $(patsubst %.o,%.d,$(OBJS))
 
diff --git a/tools/kvm/include/kvm/rbtree-interval.h b/tools/kvm/include/kvm/rbtree-interval.h
new file mode 100644
index 0000000..a6688c4
--- /dev/null
+++ b/tools/kvm/include/kvm/rbtree-interval.h
@@ -0,0 +1,27 @@
+#ifndef KVM__INTERVAL_RBTREE_H
+#define KVM__INTERVAL_RBTREE_H
+
+#include <linux/rbtree.h>
+#include <linux/types.h>
+
+#define RB_INT_INIT(l, h) (struct rb_int_node){.low = l, .high = h}
+
+struct rb_int_node {
+	struct rb_node	node;
+	u64		low;
+	u64		high;
+
+	/* max_high will store the highest high of it's 2 children. */
+	u64		max_high;
+};
+
+/* Return the rb_int_node interval in which 'point' is located. */
+struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 point);
+
+/* Return the rb_int_node in which start:len is located. */
+struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high);
+
+int rb_int_insert(struct rb_root *root, struct rb_int_node *data);
+void rb_int_erase(struct rb_root *root, struct rb_int_node *node);
+
+#endif
diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c
new file mode 100644
index 0000000..b0d36b0
--- /dev/null
+++ b/tools/kvm/util/rbtree-interval.c
@@ -0,0 +1,91 @@
+#include <kvm/rbtree-interval.h>
+#include <stddef.h>
+
+#define rb_int(n) rb_entry(n, struct rb_int_node, node)
+#define max(x, y) ((x) > (y)) ? (x) : (y)
+
+struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 point)
+{
+	struct rb_node *node = root->rb_node;
+	struct rb_node *lowest = NULL;
+
+	while (node) {
+		struct rb_int_node *cur = rb_int(node);
+
+		if (node->rb_left && (rb_int(node->rb_left)->max_high > point)) {
+			node = node->rb_left;
+		} else if (cur->low <= point && cur->high > point) {
+			lowest = node;
+			break;
+		} else if (point > cur->low) {
+			node = node->rb_right;
+		} else {
+			break;
+		}
+	}
+
+	if (lowest == NULL)
+		return NULL;
+
+	return rb_int(lowest);
+}
+
+struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high)
+{
+	struct rb_int_node *range;
+
+	range = rb_int_search_single(root, low);
+	if (range == NULL)
+		return NULL;
+
+	/* We simply verify that 'high' is smaller than the end of the range where 'low' is located */
+	if (range->high < high)
+		return NULL;
+
+	return range;
+}
+
+static void update_node_max_high(struct rb_node *node, void *arg)
+{
+	struct rb_int_node *i_node = rb_int(node);
+
+	i_node->max_high = i_node->high;
+
+	if (node->rb_left)
+		i_node->max_high = max(i_node->max_high, rb_int(node->rb_left)->high);
+	if (node->rb_right)
+		i_node->max_high = max(i_node->max_high, rb_int(node->rb_right)->high);
+}
+
+int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node)
+{
+	struct rb_node **node	= &(root->rb_node), *parent = NULL;
+
+	while (*node) {
+		int result	= i_node->low - rb_int(*node)->low;
+
+		parent = *node;
+		if (result < 0)
+			node	= &((*node)->rb_left);
+		else if (result > 0)
+			node	= &((*node)->rb_right);
+		else
+			return 0;
+	}
+
+	rb_link_node(&i_node->node, parent, node);
+	rb_insert_color(&i_node->node, root);
+
+	rb_augment_insert(*node, update_node_max_high, NULL);
+	return 1;
+}
+
+void rb_int_erase(struct rb_root *root, struct rb_int_node *node)
+{
+	struct rb_node *deepest;
+
+	deepest = rb_augment_erase_begin(&node->node);
+	rb_erase(&node->node, root);
+	rb_augment_erase_end(deepest, update_node_max_high, NULL);
+
+}
-- 
1.7.5.rc3

[PATCH 2/2 V2] kvm tools: Add MMIO address mapper

[Sasha Levin]

When we have a MMIO exit, we need to find which device
has registered to use the accessed MMIO space.

The mapper maps ranges of guest physical addresses to
callback functions.

Implementation is based on an interval red-black tree.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
 tools/kvm/include/kvm/kvm.h |    2 +
 tools/kvm/mmio.c            |   79 +++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 79 insertions(+), 2 deletions(-)

diff --git a/tools/kvm/include/kvm/kvm.h b/tools/kvm/include/kvm/kvm.h
index b310d50..d9943bf 100644
--- a/tools/kvm/include/kvm/kvm.h
+++ b/tools/kvm/include/kvm/kvm.h
@@ -44,6 +44,8 @@ void kvm__stop_timer(struct kvm *kvm);
 void kvm__irq_line(struct kvm *kvm, int irq, int level);
 bool kvm__emulate_io(struct kvm *kvm, u16 port, void *data, int direction, int size, u32 count);
 bool kvm__emulate_mmio(struct kvm *kvm, u64 phys_addr, u8 *data, u32 len, u8 is_write);
+bool kvm__register_mmio(u64 phys_addr, u64 phys_addr_len, void (*kvm_mmio_callback_fn)(u64 addr, u8 *data, u32 len, u8 is_write));
+bool kvm__deregister_mmio(u64 phys_addr);
 
 /*
  * Debugging
diff --git a/tools/kvm/mmio.c b/tools/kvm/mmio.c
index 848267d..ef986bf 100644
--- a/tools/kvm/mmio.c
+++ b/tools/kvm/mmio.c
@@ -1,7 +1,48 @@
 #include "kvm/kvm.h"
+#include "kvm/rbtree-interval.h"
 
 #include <stdio.h>
+#include <stdlib.h>
+
 #include <linux/types.h>
+#include <linux/rbtree.h>
+
+#define mmio_node(n) rb_entry(n, struct mmio_mapping, node)
+
+struct mmio_mapping {
+	struct rb_int_node	node;
+	void			(*kvm_mmio_callback_fn)(u64 addr, u8 *data, u32 len, u8 is_write);
+};
+
+static struct rb_root mmio_tree = RB_ROOT;
+
+static struct mmio_mapping *mmio_search(struct rb_root *root, u64 addr, u64 len)
+{
+	struct rb_int_node *node;
+
+	node = rb_int_search_range(root, addr, addr + len);
+	if (node == NULL)
+		return NULL;
+
+	return mmio_node(node);
+}
+
+/* Find lowest match, Check for overlap */
+static struct mmio_mapping *mmio_search_single(struct rb_root *root, u64 addr)
+{
+	struct rb_int_node *node;
+
+	node = rb_int_search_single(root, addr);
+	if (node == NULL)
+		return NULL;
+
+	return mmio_node(node);
+}
+
+static int mmio_insert(struct rb_root *root, struct mmio_mapping *data)
+{
+	return rb_int_insert(root, &data->node);
+}
 
 static const char *to_direction(u8 is_write)
 {
@@ -11,10 +52,44 @@ static const char *to_direction(u8 is_write)
 	return "read";
 }
 
+bool kvm__register_mmio(u64 phys_addr, u64 phys_addr_len, void (*kvm_mmio_callback_fn)(u64 addr, u8 *data, u32 len, u8 is_write))
+{
+	struct mmio_mapping *mmio;
+
+	mmio = malloc(sizeof(*mmio));
+	if (mmio == NULL)
+		return false;
+
+	*mmio = (struct mmio_mapping) {
+		.node = RB_INT_INIT(phys_addr, phys_addr + phys_addr_len),
+		.kvm_mmio_callback_fn = kvm_mmio_callback_fn,
+	};
+
+	return mmio_insert(&mmio_tree, mmio);
+}
+
+bool kvm__deregister_mmio(u64 phys_addr)
+{
+	struct mmio_mapping *mmio;
+
+	mmio = mmio_search_single(&mmio_tree, phys_addr);
+	if (mmio == NULL)
+		return false;
+
+	rb_int_erase(&mmio_tree, &mmio->node);
+	free(mmio);
+	return true;
+}
+
 bool kvm__emulate_mmio(struct kvm *kvm, u64 phys_addr, u8 *data, u32 len, u8 is_write)
 {
-	fprintf(stderr, "Warning: Ignoring MMIO %s at %016llx (length %u)\n",
-		to_direction(is_write), phys_addr, len);
+	struct mmio_mapping *mmio = mmio_search(&mmio_tree, phys_addr, len);
+
+	if (mmio)
+		mmio->kvm_mmio_callback_fn(phys_addr, data, len, is_write);
+	else
+		fprintf(stderr, "Warning: Ignoring MMIO %s at %016llx (length %u)\n",
+			to_direction(is_write), phys_addr, len);
 
 	return true;
 }
-- 
1.7.5.rc3

Re: [PATCH 1/2 V2] kvm tools: Add interval red-black tree helper

[Ingo Molnar]

* Sasha Levin <levinsasha928@gmail.com> wrote:

> +#define max(x, y) ((x) > (y)) ? (x) : (y)

Please have a look at tools/perf/util/include/linux/kernel.h where we have a 
type-safe version of the same - please put that into a header in tools/kvm/. 

( There was some reason why perf could not use the kernel's min/max
  definitions, the details escape me. )

Looks nice otherwise!

Acked-by: Ingo Molnar <mingo@elte.hu>

	Ingo

Re: [PATCH 2/2 V2] kvm tools: Add MMIO address mapper

[Ingo Molnar]

* Sasha Levin <levinsasha928@gmail.com> wrote:

> When we have a MMIO exit, we need to find which device
> has registered to use the accessed MMIO space.
> 
> The mapper maps ranges of guest physical addresses to
> callback functions.
> 
> Implementation is based on an interval red-black tree.
> 
> Signed-off-by: Sasha Levin <levinsasha928@gmail.com>

Acked-by: Ingo Molnar <mingo@elte.hu>

Btw., you can add acks to the commit and preserve them in future iterations, 
that would save me some typing ;-)

Thanks,

	Ingo

Re: [PATCH 1/2 V2] kvm tools: Add interval red-black tree helper

[Sasha Levin]

On Tue, 2011-05-17 at 12:50 +0200, Ingo Molnar wrote:
> ( There was some reason why perf could not use the kernel's min/max
>   definitions, the details escape me. ) 

perf's min/max are surrounded by #ifdef - unlike the ones in the
kernel's <linux/kernel.h>.
Commit messages didn't mention why, so I'll use the defs as they are in
<linux/kernel.h>.

-- 

Sasha.

Re: [PATCH 1/2 V2] kvm tools: Add interval red-black tree helper

[Ingo Molnar]

* Sasha Levin <levinsasha928@gmail.com> wrote:

> On Tue, 2011-05-17 at 12:50 +0200, Ingo Molnar wrote:
> > ( There was some reason why perf could not use the kernel's min/max
> >   definitions, the details escape me. ) 
> 
> perf's min/max are surrounded by #ifdef - unlike the ones in the
> kernel's <linux/kernel.h>.
> Commit messages didn't mention why, so I'll use the defs as they are in
> <linux/kernel.h>.

I think they were surrounded because in some contexts we could get them from 
kernel headers.

If so then getting rid of the duplicate and sorting out the header dependency 
is the right solution, so i think your approach is the right one :)

Thanks,

	Ingo