[PATCH 1/3] kvm tools: Introduce IRQ registry

[Sasha Levin <levinsasha928@gmail.com>]

Instead of having static definitions of devices, Use a
dynamic registry of pci devices.

The structure is a rbtree which holds device types (net,
blk, etc). Each device entry holds a list of IRQ lines
associated with that device (pin).

Devices dynamically register upon initialization, and receive
a set of: device id, irq pin and irq line.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
 tools/kvm/Makefile               |    2 +
 tools/kvm/include/kvm/irq.h      |   24 +++++++++
 tools/kvm/include/linux/module.h |    6 ++
 tools/kvm/irq.c                  |  107 ++++++++++++++++++++++++++++++++++++++
 4 files changed, 139 insertions(+), 0 deletions(-)
 create mode 100644 tools/kvm/include/kvm/irq.h
 create mode 100644 tools/kvm/include/linux/module.h
 create mode 100644 tools/kvm/irq.c

diff --git a/tools/kvm/Makefile b/tools/kvm/Makefile
index 89c7e3d..fb839fc 100644
--- a/tools/kvm/Makefile
+++ b/tools/kvm/Makefile
@@ -39,6 +39,8 @@ OBJS    += kvm-run.o
 OBJS    += qcow.o
 OBJS    += mptable.o
 OBJS    += threadpool.o
+OBJS    += irq.o
+OBJS    += ../../lib/rbtree.o
 
 DEPS	:= $(patsubst %.o,%.d,$(OBJS))
 
diff --git a/tools/kvm/include/kvm/irq.h b/tools/kvm/include/kvm/irq.h
new file mode 100644
index 0000000..7a75a0c
--- /dev/null
+++ b/tools/kvm/include/kvm/irq.h
@@ -0,0 +1,24 @@
+#ifndef KVM__IRQ_H
+#define KVM__IRQ_H
+
+#include <linux/types.h>
+#include <linux/rbtree.h>
+#include <linux/list.h>
+
+struct irq_line {
+	u8			line;
+	struct list_head	node;
+};
+
+struct pci_dev {
+	struct rb_node		node;
+	u32			id;
+	u8			pin;
+	struct list_head	lines;
+};
+
+int irq__register_device(u32 dev, u8 *num, u8 *pin, u8 *line);
+
+struct rb_node *irq__get_pci_tree(void);
+
+#endif
diff --git a/tools/kvm/include/linux/module.h b/tools/kvm/include/linux/module.h
new file mode 100644
index 0000000..0e4c6a3
--- /dev/null
+++ b/tools/kvm/include/linux/module.h
@@ -0,0 +1,6 @@
+#ifndef KVM__LINUX_MODULE_H
+#define KVM__LINUX_MODULE_H
+
+#define EXPORT_SYMBOL(name)
+
+#endif
diff --git a/tools/kvm/irq.c b/tools/kvm/irq.c
new file mode 100644
index 0000000..4f4305f
--- /dev/null
+++ b/tools/kvm/irq.c
@@ -0,0 +1,107 @@
+#include "kvm/irq.h"
+
+#include <linux/types.h>
+#include <linux/rbtree.h>
+#include <linux/list.h>
+
+#include <stddef.h>
+#include <stdlib.h>
+
+static u8		next_pin	= 1;
+static u8		next_line	= 3;
+static u8		next_dev	= 1;
+static struct rb_root	pci_tree	= RB_ROOT;
+
+static struct pci_dev *search(struct rb_root *root, u32 id)
+{
+	struct rb_node *node = root->rb_node;
+
+	while (node) {
+		struct pci_dev *data = container_of(node, struct pci_dev, node);
+		int result;
+
+		result = id - data->id;
+
+		if (result < 0)
+			node = node->rb_left;
+		else if (result > 0)
+			node = node->rb_right;
+		else
+			return data;
+	}
+	return NULL;
+}
+
+static int insert(struct rb_root *root, struct pci_dev *data)
+{
+	struct rb_node **new = &(root->rb_node), *parent = NULL;
+
+	/* Figure out where to put new node */
+	while (*new) {
+		struct pci_dev *this	= container_of(*new, struct pci_dev, node);
+		int result		= data->id - this->id;
+
+		parent = *new;
+		if (result < 0)
+			new = &((*new)->rb_left);
+		else if (result > 0)
+			new = &((*new)->rb_right);
+		else
+			return 0;
+	}
+
+	/* Add new node and rebalance tree. */
+	rb_link_node(&data->node, parent, new);
+	rb_insert_color(&data->node, root);
+
+	return 1;
+}
+
+int irq__register_device(u32 dev, u8 *num, u8 *pin, u8 *line)
+{
+	struct pci_dev *node;
+
+	node = search(&pci_tree, dev);
+
+	if (!node) {
+		/* We haven't found a node - First device of it's kind */
+		node = malloc(sizeof(*node));
+		if (node == NULL)
+			return -1;
+
+		*node = (struct pci_dev) {
+			.id	= dev,
+			.pin	= next_pin++,
+		};
+
+		INIT_LIST_HEAD(&node->lines);
+
+		if (insert(&pci_tree, node) != 1) {
+			free(node);
+			return -1;
+		}
+	}
+
+	if (node) {
+		/* This device already has a pin assigned, give out a new line and device id */
+		struct irq_line *new = malloc(sizeof(*new));
+		if (new == NULL)
+			return -1;
+
+		new->line	= next_line++;
+		*line		= new->line;
+		*pin		= node->pin;
+		*num		= next_dev++;
+
+		list_add(&new->node, &node->lines);
+
+		return 0;
+	}
+
+	return -1;
+}
+
+struct rb_node *irq__get_pci_tree(void)
+{
+	return rb_first(&pci_tree);
+}
-- 
1.7.5.rc3