[PATCH 01/10] IOQ: Adding basic definitions for IO-Queue logic

Gregory Haskins
2007-08-16T23:14:02Z

IOQ is a generic shared-memory-queue mechanism that happens to be friendly
to virtualization boundaries. Note that it is not virtualization specific
due to its flexible transport layer.

Signed-off-by: Gregory Haskins <ghaskins-Et1tbQHTxzrQT0dZR+AlfA@public.gmane.org>
---

include/linux/ioq.h | 176 +++++++++++++++++++++++++++++++++++++++
lib/Kconfig | 11 ++
lib/Makefile | 1
lib/ioq.c | 228 +++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 416 insertions(+), 0 deletions(-)

diff --git a/include/linux/ioq.h b/include/linux/ioq.h
new file mode 100644
index 0000000..d3a18a1
--- /dev/null
+++ b/include/linux/ioq.h
@@ -0,0 +1,176 @@
+/*
+ * Copyright 2007 Novell. All Rights Reserved.
+ *
+ * IOQ is a generic shared-memory-queue mechanism that happens to be friendly
+ * to virtualization boundaries. It can be used in a variety of ways, though
+ * its intended purpose is to become the low-level communication path for
+ * paravirtualized drivers. Note that it is not virtualization specific
+ * due to its flexible signaling layer.
+ *
+ * The following are a list of key design points:
+ *
+ * #) All shared-memory is always allocated on explicitly one side of the
+ * link. This typically would be the guest side in a VM/VMM scenario.
+ * #) The code has the concept of "north" and "south" where north denotes the
+ * memory-owner side (e.g. guest).
+ * #) A IOQ is "created" on the north side (which generates a unique ID), and
+ * is "connected" on the remote side via its ID. The facilitates call-path
+ * setup in a manner that is friendly across VM/VMM boundaries.
+ * #) An IOQ is manipulated using an iterator idiom.
+ * #) A "IOQ Manager" abstraction handles the translation between two
+ * endpoints. E.g. allocating "north" memory, signaling, translating
+ * addresses (e.g. GPA to PA)
+ *
+ * Author:
+ * Gregory Haskins <ghaskins-Et1tbQHTxzrQT0dZR+AlfA@public.gmane.org>
+ *
+ * This file is free software; you can redistribute it and/or modify
+ * it under the terms of version 2 of the GNU General Public License
+ * as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef _LINUX_IOQ_H
+#define _LINUX_IOQ_H
+
+#include <linux/sched.h>
+#include <linux/wait.h>
+#include <asm/types.h>
+
+struct ioq_mgr;
+
+/*
+ *---------
+ * The following structures represent data that is shared across boundaries
+ * which may be quite disparate from one another (e.g. Windows vs Linux,
+ * 32 vs 64 bit, etc). Therefore, care has been taken to make sure they
+ * present data in a manner that is independent of the environment.
+ *-----------
+ */
+typedef u64 ioq_id_t;
+
+struct ioq_ring_desc {
+ u64 cookie; /* for arbitrary use by north-side */
+ u64 ptr;
+ u64 len;
+ u64 alen;
+ u8 valid;
+ u8 sown; /* South owned = 1, North owned = 0 */
+};
+
+#define IOQ_RING_MAGIC 0x47fa2fe4
+#define IOQ_RING_VER 1
+
+struct ioq_ring_idx {
+ u32 head; /* 0 based index to head of ptr array */
+ u32 tail; /* 0 based index to tail of ptr array */
+ u8 full;
+};
+
+struct ioq_irq {
+ u8 enabled;
+ u8 pending;
+};
+
+enum ioq_locality {
+ ioq_locality_north,
+ ioq_locality_south,
+};
+
+struct ioq_ring_head {
+ u32 magic;
+ u32 ver;
+ ioq_id_t id;
+ u32 count;
+ u64 ptr; /* ptr to array of ioq_ring_desc[count] */
+ struct ioq_ring_idx idx[2];
+ struct ioq_irq irq[2];
+ u8 padding[16];
+};
+
+/* --- END SHARED STRUCTURES --- */
+
+enum ioq_idx_type {
+ ioq_idxtype_valid,
+ ioq_idxtype_inuse,
+ ioq_idxtype_invalid,
+};
+
+enum ioq_seek_type {
+ ioq_seek_tail,
+ ioq_seek_next,
+ ioq_seek_head,
+ ioq_seek_set
+};
+
+struct ioq_iterator {
+ struct ioq *ioq;
+ struct ioq_ring_idx *idx;
+ u32 pos;
+ struct ioq_ring_desc *desc;
+ int update;
+};
+
+int ioq_iter_seek(struct ioq_iterator *iter, enum ioq_seek_type type,
+ long offset, int flags);
+int ioq_iter_push(struct ioq_iterator *iter, int flags);
+int ioq_iter_pop(struct ioq_iterator *iter, int flags);
+
+struct ioq_notifier {
+ void (*signal)(struct ioq_notifier*);
+};
+
+struct ioq {
+ void (*destroy)(struct ioq *ioq);
+ int (*signal)(struct ioq *ioq);
+
+ ioq_id_t id;
+ enum ioq_locality locale;
+ struct ioq_mgr *mgr;
+ struct ioq_ring_head *head_desc;
+ struct ioq_ring_desc *ring;
+ wait_queue_head_t wq;
+ struct ioq_notifier *notifier;
+};
+
+static inline void ioq_init(struct ioq *ioq)
+{
+ memset(ioq, 0, sizeof(*ioq));
+ init_waitqueue_head(&ioq->wq);
+}
+
+int ioq_start(struct ioq *ioq, int flags);
+int ioq_stop(struct ioq *ioq, int flags);
+int ioq_signal(struct ioq *ioq, int flags);
+void ioq_wakeup(struct ioq *ioq); /* This should only be used internally */
+int ioq_count(struct ioq *ioq, enum ioq_idx_type type);
+int ioq_full(struct ioq *ioq, enum ioq_idx_type type);
+
+static inline int ioq_empty(struct ioq *ioq, enum ioq_idx_type type)
+{
+ return !ioq_count(ioq, type);
+}
+
+
+
+#define IOQ_ITER_AUTOUPDATE (1 << 0)
+int ioq_iter_init(struct ioq *ioq, struct ioq_iterator *iter,
+ enum ioq_idx_type type, int flags);
+
+struct ioq_mgr {
+ int (*create)(struct ioq_mgr *t, struct ioq **ioq,
+ size_t ringsize, int flags);
+ int (*connect)(struct ioq_mgr *t, ioq_id_t id, struct ioq **ioq,
+ int flags);
+};
+
+
+#endif /* _LINUX_IOQ_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index 2e7ae6b..65c6d5d 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -124,4 +124,15 @@ config HAS_DMA
depends on !NO_DMA
default y

+config IOQ
+ boolean "IO-Queue library - Generic shared-memory queue"
+ default n
+ help
+ IOQ is a generic shared-memory-queue mechanism that happens to be
+ friendly to virtualization boundaries. It can be used in a variety
+ of ways, though its intended purpose is to become the low-level
+ communication path for paravirtualized drivers.
+
+ If unsure, say N
+
endmenu
diff --git a/lib/Makefile b/lib/Makefile
index c8c8e20..2bf3b5d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -56,6 +56,7 @@ obj-$(CONFIG_TEXTSEARCH_BM) += ts_bm.o
obj-$(CONFIG_TEXTSEARCH_FSM) += ts_fsm.o
obj-$(CONFIG_SMP) += percpu_counter.o
obj-$(CONFIG_AUDIT_GENERIC) += audit.o
+obj-$(CONFIG_IOQ) += ioq.o

obj-$(CONFIG_SWIOTLB) += swiotlb.o
obj-$(CONFIG_FAULT_INJECTION) += fault-inject.o
diff --git a/lib/ioq.c b/lib/ioq.c
new file mode 100644
index 0000000..b9ef75e
--- /dev/null
+++ b/lib/ioq.c
@@ -0,0 +1,228 @@
+/*
+ * Copyright 2007 Novell. All Rights Reserved.
+ *
+ * See include/linux/ioq.h for documentation
+ *
+ * Author:
+ * Gregory Haskins <ghaskins-Et1tbQHTxzrQT0dZR+AlfA@public.gmane.org>
+ *
+ * This file is free software; you can redistribute it and/or modify
+ * it under the terms of version 2 of the GNU General Public License
+ * as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include <linux/sched.h>
+#include <linux/ioq.h>
+#include <asm/bitops.h>
+#include <linux/module.h>
+
+#ifndef NULL
+#define NULL 0
+#endif
+
+static int ioq_iter_setpos(struct ioq_iterator *iter, u32 pos)
+{
+ struct ioq *ioq = iter->ioq;
+
+ BUG_ON(pos >= ioq->head_desc->count);
+
+ iter->pos = pos;
+ iter->desc = &ioq->ring[pos];
+
+ return 0;
+}
+
+int ioq_iter_seek(struct ioq_iterator *iter, enum ioq_seek_type type,
+ long offset, int flags)
+{
+ struct ioq_ring_head *head_desc = iter->ioq->head_desc;
+ struct ioq_ring_idx *idx = iter->idx;
+ u32 pos;
+
+ switch (type) {
+ case ioq_seek_next:
+ pos = iter->pos + 1;
+ pos %= head_desc->count;
+ break;
+ case ioq_seek_tail:
+ pos = idx->tail;
+ break;
+ case ioq_seek_head:
+ pos = idx->head;
+ break;
+ case ioq_seek_set:
+ if (offset >= head_desc->count)
+ return -1;
+ pos = offset;
+ break;
+ default:
+ return -EINVAL;
+ }
+
+ return ioq_iter_setpos(iter, pos);
+}
+EXPORT_SYMBOL(ioq_iter_seek);
+
+static int ioq_ring_count(struct ioq_ring_idx *idx, int count)
+{
+ if (idx->full && (idx->head == idx->tail))
+ return count;
+ else if (idx->head >= idx->tail)
+ return idx->head - idx->tail;
+ else
+ return (idx->head + count) - idx->tail;
+}
+
+int ioq_iter_push(struct ioq_iterator *iter, int flags)
+{
+ struct ioq_ring_head *head_desc = iter->ioq->head_desc;
+ struct ioq_ring_idx *idx = iter->idx;
+ int ret = -ENOSPC;
+
+ /*
+ * Its only valid to push if we are currently pointed at the head
+ */
+ if (iter->pos != idx->head)
+ return -EINVAL;
+
+ if (ioq_ring_count(idx, head_desc->count) < head_desc->count) {
+ idx->head++;
+ idx->head %= head_desc->count;
+
+ if (idx->head == idx->tail)
+ idx->full = 1;
+
+ mb();
+
+ ret = ioq_iter_seek(iter, ioq_seek_next, 0, flags);
+
+ if (iter->update)
+ ioq_signal(iter->ioq, 0);
+ }
+
+ return ret;
+}
+EXPORT_SYMBOL(ioq_iter_push);
+
+int ioq_iter_pop(struct ioq_iterator *iter, int flags)
+{
+ struct ioq_ring_head *head_desc = iter->ioq->head_desc;
+ struct ioq_ring_idx *idx = iter->idx;
+ int ret = -ENOSPC;
+
+ /*
+ * Its only valid to pop if we are currently pointed at the tail
+ */
+ if (iter->pos != idx->tail)
+ return -EINVAL;
+
+ if (ioq_ring_count(idx, head_desc->count) != 0) {
+ idx->tail++;
+ idx->tail %= head_desc->count;
+
+ idx->full = 0;
+
+ mb();
+
+ ret = ioq_iter_seek(iter, ioq_seek_next, 0, flags);
+
+ if (iter->update)
+ ioq_signal(iter->ioq, 0);
+ }
+
+ return ret;
+}
+EXPORT_SYMBOL(ioq_iter_pop);
+
+int ioq_iter_init(struct ioq *ioq, struct ioq_iterator *iter,
+ enum ioq_idx_type type, int flags)
+{
+ BUG_ON((type < 0) || (type >= ioq_idxtype_invalid));
+
+ iter->ioq = ioq;
+ iter->update = (flags & IOQ_ITER_AUTOUPDATE);
+ iter->idx = &ioq->head_desc->idx[type];
+ iter->pos = -1;
+ iter->desc = NULL;
+
+ return 0;
+}
+EXPORT_SYMBOL(ioq_iter_init);
+
+int ioq_start(struct ioq *ioq, int flags)
+{
+ struct ioq_irq *irq = &ioq->head_desc->irq[ioq->locale];
+
+ irq->enabled = 1;
+ mb();
+
+ if (irq->pending)
+ ioq_wakeup(ioq);
+
+ return 0;
+}
+EXPORT_SYMBOL(ioq_start);
+
+int ioq_stop(struct ioq *ioq, int flags)
+{
+ struct ioq_irq *irq = &ioq->head_desc->irq[ioq->locale];
+
+ irq->enabled = 0;
+ mb();
+
+ return 0;
+}
+EXPORT_SYMBOL(ioq_stop);
+
+int ioq_signal(struct ioq *ioq, int flags)
+{
+ /* Load the irq structure from the other locale */
+ struct ioq_irq *irq = &ioq->head_desc->irq[!ioq->locale];
+
+ irq->pending = 1;
+ mb();
+
+ if (irq->enabled)
+ ioq->signal(ioq);
+
+ return 0;
+}
+EXPORT_SYMBOL(ioq_signal);
+
+int ioq_count(struct ioq *ioq, enum ioq_idx_type type)
+{
+ BUG_ON((type < 0) || (type >= ioq_idxtype_invalid));
+
+ return ioq_ring_count(&ioq->head_desc->idx[type], ioq->head_desc->count);
+}
+EXPORT_SYMBOL(ioq_count);
+
+int ioq_full(struct ioq *ioq, enum ioq_idx_type type)
+{
+ BUG_ON((type < 0) || (type >= ioq_idxtype_invalid));
+
+ return ioq->head_desc->idx[type].full;
+}
+EXPORT_SYMBOL(ioq_full);
+
+void ioq_wakeup(struct ioq *ioq)
+{
+ struct ioq_irq *irq = &ioq->head_desc->irq[ioq->locale];
+
+ irq->pending = 0;
+ mb();
+
+ wake_up(&ioq->wq);
+ if (ioq->notifier)
+ ioq->notifier->signal(ioq->notifier);
+}
+EXPORT_SYMBOL(ioq_wakeup);