From feeb62d66a3b985d8b8ddc8e5b2f19b1ca4884c5 Mon Sep 17 00:00:00 2001
From: Amos Kong <akong@redhat.com>
Date: Mon, 19 Dec 2011 13:25:12 +0100
Subject: [PATCH 1/3] Use a bitmap for tracking used GSIs

RH-Author: Amos Kong <akong@redhat.com>
Message-id: <20111219132512.7612.87746.stgit@dhcp-8-167.nay.redhat.com>
Patchwork-id: 35881
O-Subject: [RHEL5.9 KVM PATCH 1/2] Use a bitmap for tracking used GSIs
Bugzilla: 761350
RH-Acked-by: Alex Williamson <alex.williamson@redhat.com>
RH-Acked-by: Avi Kivity <avi@redhat.com>
RH-Acked-by: Xiao Wang <jasowang@redhat.com>

Bugzilla: 761350
Upstream: manually cherry-picked from 8ea45650455de769872647900964a406876db405
Test status: Tested in my local machine

We're currently using a counter to track the most recent GSI we've
handed out.  This quickly hits KVM_MAX_IRQ_ROUTES when using device
assignment with a driver that regularly toggles the MSI enable bit
(such as Linux kernels 2.6.21-26).  This can mean only a few minutes
of usable run time.  Instead, track used GSIs in a bitmap.

Signed-off-by: Alex Williamson <alex.williamson@hp.com>
Signed-off-by: Avi Kivity <avi@redhat.com>
Signed-off-by: Amos Kong <akong@redhat.com>
---
 libkvm/kvm-common.h |    3 +-
 libkvm/libkvm.c     |   87 ++++++++++++++++++++++++++++++++++++++++++---------
 2 files changed, 73 insertions(+), 17 deletions(-)

Signed-off-by: Michal Novotny <minovotn@redhat.com>
---
 libkvm/kvm-common.h |    3 +-
 libkvm/libkvm.c     |   87 +++++++++++++++++++++++++++++++++++++++++---------
 2 files changed, 73 insertions(+), 17 deletions(-)

diff --git a/libkvm/kvm-common.h b/libkvm/kvm-common.h
index b344106..d4a7a40 100644
--- a/libkvm/kvm-common.h
+++ b/libkvm/kvm-common.h
@@ -66,7 +66,8 @@ struct kvm_context {
 #ifdef KVM_CAP_IRQ_ROUTING
 	struct kvm_irq_routing *irq_routes;
 	int nr_allocated_irq_routes;
-	int max_used_gsi;
+	void *used_gsi_bitmap;
+	int max_gsi;
 #endif
 };
 
diff --git a/libkvm/libkvm.c b/libkvm/libkvm.c
index 565019f..11bcafe 100644
--- a/libkvm/libkvm.c
+++ b/libkvm/libkvm.c
@@ -61,10 +61,32 @@
 #define DPRINTF(fmt, args...) do {} while (0)
 #endif
 
+#define MIN(x,y) ((x) < (y) ? (x) : (y))
+#define ALIGN(x, y) (((x)+(y)-1) & ~((y)-1))
 
 int kvm_abi = EXPECTED_KVM_API_VERSION;
 int kvm_page_size;
 
+static inline void set_gsi(kvm_context_t kvm, unsigned int gsi)
+{
+	uint32_t *bitmap = kvm->used_gsi_bitmap;
+
+	if (gsi < kvm->max_gsi)
+		bitmap[gsi / 32] |= 1U << (gsi % 32);
+	else
+		DPRINTF("Invalid GSI %d\n");
+}
+
+static inline void clear_gsi(kvm_context_t kvm, unsigned int gsi)
+{
+	uint32_t *bitmap = kvm->used_gsi_bitmap;
+
+	if (gsi < kvm->max_gsi)
+		bitmap[gsi / 32] &= ~(1U << (gsi % 32));
+	else
+		DPRINTF("Invalid GSI %d\n");
+}
+
 struct slot_info {
 	unsigned long phys_addr;
 	unsigned long len;
@@ -285,7 +307,7 @@ kvm_context_t kvm_init(struct kvm_callbacks *callbacks,
 {
 	int fd;
 	kvm_context_t kvm;
-	int r;
+	int r, gsi_count;
 
 	fd = open("/dev/kvm", O_RDWR);
 	if (fd == -1) {
@@ -323,6 +345,23 @@ kvm_context_t kvm_init(struct kvm_callbacks *callbacks,
 	kvm->no_irqchip_creation = 0;
 	kvm->no_pit_creation = 0;
 
+	gsi_count = kvm_get_gsi_count(kvm);
+	if (gsi_count > 0) {
+		int gsi_bits, i;
+
+		/* Round up so we can search ints using ffs */
+		gsi_bits = ALIGN(gsi_count, 32);
+		kvm->used_gsi_bitmap = malloc(gsi_bits / 8);
+		if (!kvm->used_gsi_bitmap)
+			goto out_close;
+		memset(kvm->used_gsi_bitmap, 0, gsi_bits / 8);
+		kvm->max_gsi = gsi_bits;
+
+		/* Mark any over-allocated bits as already in use */
+		for (i = gsi_count; i < gsi_bits; i++)
+			set_gsi(kvm, i);
+	}
+
 	return kvm;
  out_close:
 	close(fd);
@@ -629,9 +668,6 @@ int kvm_get_dirty_pages(kvm_context_t kvm, unsigned long phys_addr, void *buf)
 	return kvm_get_map(kvm, KVM_GET_DIRTY_LOG, slot, buf);
 }
 
-#define ALIGN(x, y)  (((x)+(y)-1) & ~((y)-1))
-#define BITMAP_SIZE(m) (ALIGN(((m)/PAGE_SIZE), sizeof(long) * 8) / 8)
-
 int kvm_get_dirty_pages_range(kvm_context_t kvm, unsigned long phys_addr,
 			      unsigned long len, void *buf, void *opaque,
 			      int (*cb)(unsigned long start, unsigned long len,
@@ -1296,8 +1332,8 @@ int kvm_add_routing_entry(kvm_context_t kvm,
 	new->flags = entry->flags;
 	new->u = entry->u;
 
-	if (entry->gsi > kvm->max_used_gsi)
-		kvm->max_used_gsi = entry->gsi;
+	set_gsi(kvm, entry->gsi);
+
 	return 0;
 #else
 	return -ENOSYS;
@@ -1325,12 +1361,14 @@ int kvm_del_routing_entry(kvm_context_t kvm,
 {
 #ifdef KVM_CAP_IRQ_ROUTING
 	struct kvm_irq_routing_entry *e, *p;
-	int i, found = 0;
+	int i, gsi, found = 0;
+
+	gsi = entry->gsi;
 
 	for (i = 0; i < kvm->irq_routes->nr; ++i) {
 		e = &kvm->irq_routes->entries[i];
 		if (e->type == entry->type
-		    && e->gsi == entry->gsi) {
+		    && e->gsi == gsi) {
 			switch (e->type)
 			{
 			case KVM_IRQ_ROUTING_IRQCHIP: {
@@ -1361,8 +1399,19 @@ int kvm_del_routing_entry(kvm_context_t kvm,
 			default:
 				break;
 			}
-			if (found)
+			if (found) {
+				/* If there are no other users of this GSI
+				 * mark it available in the bitmap */
+				for (i = 0; i < kvm->irq_routes->nr; i++) {
+					e = &kvm->irq_routes->entries[i];
+					if (e->gsi == gsi)
+						break;
+				}
+				if (i == kvm->irq_routes->nr)
+					clear_gsi(kvm, gsi);
+
 				return 0;
+			}
 		}
 	}
 	return -ESRCH;
@@ -1404,13 +1453,19 @@ int kvm_commit_irq_routes(kvm_context_t kvm)
 
 int kvm_get_irq_route_gsi(kvm_context_t kvm)
 {
-	if (kvm->max_used_gsi >= KVM_IOAPIC_NUM_PINS)  {
-	    if (kvm->max_used_gsi <= kvm_get_gsi_count(kvm))
-                return kvm->max_used_gsi + 1;
-            else
-                return -ENOSPC;
-        } else
-            return KVM_IOAPIC_NUM_PINS;
+	int i, bit;
+	uint32_t *buf = kvm->used_gsi_bitmap;
+
+	/* Return the lowest unused GSI in the bitmap */
+	for (i = 0; i < kvm->max_gsi / 32; i++) {
+		bit = ffs(~buf[i]);
+		if (!bit)
+			continue;
+
+		return bit - 1 + i * 32;
+	}
+
+	return -ENOSPC;
 }
 
 #ifdef KVM_CAP_DEVICE_MSIX
-- 
1.7.7.6