[PATCH RESEND 0/4] Change fixed mmio handlers to a variable number

[PATCH RESEND 0/4] Change fixed mmio handlers to a variable number

[Shanker Donthineni]

The maximum number of mmio handlers that are allowed is limited to
a macro MAX_IO_HANDLER(16), which is not enough for supporting per CPU
Redistributor regions. We need at least MAX_IO_HANDLER+CONFIG_NR_CPUS
mmio handlers in order to support ACPI based XEN boot.

This patchset uses the dynamic allocation strategy to allocate memory
resource dynamically depends on the number of Redistributor regions
that are described in the APCI MADT table.

Shanker Donthineni (4):
  arm/io: Use separate memory allocation for mmio handlers
  xen: Add generic implementation of binary search
  xen/arm: io: Use binary search for mmio handler lookup
  arm/vgic: Change fixed number of mmio handlers to variable number

 xen/arch/arm/domain.c      | 12 +++++++----
 xen/arch/arm/io.c          | 53 +++++++++++++++++++++++++++++++---------------
 xen/arch/arm/vgic-v2.c     |  3 ++-
 xen/arch/arm/vgic-v3.c     |  5 ++++-
 xen/arch/arm/vgic.c        | 10 +++------
 xen/common/Makefile        |  1 +
 xen/common/bsearch.c       | 51 ++++++++++++++++++++++++++++++++++++++++++++
 xen/include/asm-arm/mmio.h |  7 ++++--
 xen/include/asm-arm/vgic.h |  5 +++--
 xen/include/xen/bsearch.h  |  9 ++++++++
 10 files changed, 122 insertions(+), 34 deletions(-)
 create mode 100644 xen/common/bsearch.c
 create mode 100644 xen/include/xen/bsearch.h

Changes:
  Resend to fix the Message-ID, References and In-Reply-To fields.

-- 
Qualcomm Datacenter Technologies, Inc. on behalf of the Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project.


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH RESEND 1/4] arm/io: Use separate memory allocation for mmio handlers

[Shanker Donthineni]

The number of mmio handlers are limited to a compile time macro
MAX_IO_HANDLER which is 16. This number is not at all sufficient
to support per CPU distributor regions. Either it needs to be
increased to a bigger number, at least CONFIG_NR_CPUS+16, or
allocate a separate memory for mmio handlers dynamically during
domain build.

This patch uses the dynamic allocation strategy to reduce memory
footprint for 'struct domain' instead of static allocation.

Signed-off-by: Shanker Donthineni <shankerd@codeaurora.org>
Acked-by: Julien Grall <julien.grall@arm.com>
---
 Resend to fix the In-Reply-To/References header feilds.

 xen/arch/arm/domain.c      |  6 ++++--
 xen/arch/arm/io.c          | 13 +++++++++++--
 xen/include/asm-arm/mmio.h |  7 +++++--
 3 files changed, 20 insertions(+), 6 deletions(-)

diff --git a/xen/arch/arm/domain.c b/xen/arch/arm/domain.c
index 61fc08e..0170cee 100644
--- a/xen/arch/arm/domain.c
+++ b/xen/arch/arm/domain.c
@@ -546,7 +546,7 @@ void vcpu_destroy(struct vcpu *v)
 int arch_domain_create(struct domain *d, unsigned int domcr_flags,
                        struct xen_arch_domainconfig *config)
 {
-    int rc;
+    int rc, count;
 
     d->arch.relmem = RELMEM_not_started;
 
@@ -569,7 +569,8 @@ int arch_domain_create(struct domain *d, unsigned int domcr_flags,
     share_xen_page_with_guest(
         virt_to_page(d->shared_info), d, XENSHARE_writable);
 
-    if ( (rc = domain_io_init(d)) != 0 )
+    count = MAX_IO_HANDLER;
+    if ( (rc = domain_io_init(d, count)) != 0 )
         goto fail;
 
     if ( (rc = p2m_alloc_table(d)) != 0 )
@@ -663,6 +664,7 @@ void arch_domain_destroy(struct domain *d)
     free_xenheap_pages(d->arch.efi_acpi_table,
                        get_order_from_bytes(d->arch.efi_acpi_len));
 #endif
+    domain_io_free(d);
 }
 
 void arch_domain_shutdown(struct domain *d)
diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
index 5a96836..40330f0 100644
--- a/xen/arch/arm/io.c
+++ b/xen/arch/arm/io.c
@@ -118,7 +118,7 @@ void register_mmio_handler(struct domain *d,
     struct vmmio *vmmio = &d->arch.vmmio;
     struct mmio_handler *handler;
 
-    BUG_ON(vmmio->num_entries >= MAX_IO_HANDLER);
+    BUG_ON(vmmio->num_entries >= vmmio->max_num_entries);
 
     write_lock(&vmmio->lock);
 
@@ -134,14 +134,23 @@ void register_mmio_handler(struct domain *d,
     write_unlock(&vmmio->lock);
 }
 
-int domain_io_init(struct domain *d)
+int domain_io_init(struct domain *d, int max_count)
 {
     rwlock_init(&d->arch.vmmio.lock);
     d->arch.vmmio.num_entries = 0;
+    d->arch.vmmio.max_num_entries = max_count;
+    d->arch.vmmio.handlers = xzalloc_array(struct mmio_handler, max_count);
+    if ( !d->arch.vmmio.handlers )
+        return -ENOMEM;
 
     return 0;
 }
 
+void domain_io_free(struct domain *d)
+{
+    xfree(d->arch.vmmio.handlers);
+}
+
 /*
  * Local variables:
  * mode: C
diff --git a/xen/include/asm-arm/mmio.h b/xen/include/asm-arm/mmio.h
index 32f10f2..c620eed 100644
--- a/xen/include/asm-arm/mmio.h
+++ b/xen/include/asm-arm/mmio.h
@@ -52,15 +52,18 @@ struct mmio_handler {
 
 struct vmmio {
     int num_entries;
+    int max_num_entries;
     rwlock_t lock;
-    struct mmio_handler handlers[MAX_IO_HANDLER];
+    struct mmio_handler *handlers;
 };
 
 extern int handle_mmio(mmio_info_t *info);
 void register_mmio_handler(struct domain *d,
                            const struct mmio_handler_ops *ops,
                            paddr_t addr, paddr_t size, void *priv);
-int domain_io_init(struct domain *d);
+int domain_io_init(struct domain *d, int max_count);
+void domain_io_free(struct domain *d);
+
 
 #endif  /* __ASM_ARM_MMIO_H__ */
 
-- 
Qualcomm Datacenter Technologies, Inc. on behalf of the Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project.


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH RESEND 2/4] xen: Add generic implementation of binary search

[Shanker Donthineni]

This patch adds the generic implementation of binary search algorithm
whcih is copied from Linux kernel v4.7-rc7. No functional changes.

Signed-off-by: Shanker Donthineni <shankerd@codeaurora.org>
---
 Resend to fix the In-Reply-To/References header feilds.

 xen/common/Makefile       |  1 +
 xen/common/bsearch.c      | 51 +++++++++++++++++++++++++++++++++++++++++++++++
 xen/include/xen/bsearch.h |  9 +++++++++
 3 files changed, 61 insertions(+)
 create mode 100644 xen/common/bsearch.c
 create mode 100644 xen/include/xen/bsearch.h

diff --git a/xen/common/Makefile b/xen/common/Makefile
index dbf00c6..f8123c2 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -43,6 +43,7 @@ obj-y += schedule.o
 obj-y += shutdown.o
 obj-y += softirq.o
 obj-y += sort.o
+obj-y += bsearch.o
 obj-y += smp.o
 obj-y += spinlock.o
 obj-y += stop_machine.o
diff --git a/xen/common/bsearch.c b/xen/common/bsearch.c
new file mode 100644
index 0000000..3bcfd72
--- /dev/null
+++ b/xen/common/bsearch.c
@@ -0,0 +1,51 @@
+/*
+ * A generic implementation of binary search for the Linux kernel
+ *
+ * Copyright (C) 2008-2009 Ksplice, Inc.
+ * Author: Tim Abbott <tabbott@ksplice.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; version 2.
+ */
+
+#include <xen/bsearch.h>
+
+/*
+ * bsearch - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to first element to search
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array.  The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Note that the key need not have the same type as the elements in
+ * the array, e.g. key could be a string and the comparison function
+ * could compare the string with the struct's name field.  However, if
+ * the key and elements in the array are of the same type, you can use
+ * the same comparison function for both sort() and bsearch().
+ */
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt))
+{
+	size_t start = 0, end = num;
+	int result;
+
+	while (start < end) {
+		size_t mid = start + (end - start) / 2;
+
+		result = cmp(key, base + mid * size);
+		if (result < 0)
+			end = mid;
+		else if (result > 0)
+			start = mid + 1;
+		else
+			return (void *)base + mid * size;
+	}
+
+	return NULL;
+}
diff --git a/xen/include/xen/bsearch.h b/xen/include/xen/bsearch.h
new file mode 100644
index 0000000..07cf604
--- /dev/null
+++ b/xen/include/xen/bsearch.h
@@ -0,0 +1,9 @@
+#ifndef __XEN_BSEARCH_H__
+#define __XEN_BSEARCH_H__
+
+#include <xen/types.h>
+
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+	      int (*cmp)(const void *key, const void *elt));
+
+#endif /* __XEN_BSEARCH_H__ */
-- 
Qualcomm Datacenter Technologies, Inc. on behalf of the Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project.


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH RESEND 3/4] xen/arm: io: Use binary search for mmio handler lookup

[Shanker Donthineni]

As the number of I/O handlers increase, the overhead associated with
linear lookup also increases. The system might have maximum of 144
(assuming CONFIG_NR_CPUS=128) mmio handlers. In worst case scenario,
it would require 144 iterations for finding a matching handler. Now
it is time for us to change from linear (complexity O(n)) to a binary
search (complexity O(log n) for reducing mmio handler lookup overhead.

Signed-off-by: Shanker Donthineni <shankerd@codeaurora.org>
---
 Resend to fix the In-Reply-To/References header feilds.

 xen/arch/arm/io.c | 40 +++++++++++++++++++++++++---------------
 1 file changed, 25 insertions(+), 15 deletions(-)

diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
index 40330f0..cdc3aa3 100644
--- a/xen/arch/arm/io.c
+++ b/xen/arch/arm/io.c
@@ -20,6 +20,8 @@
 #include <xen/lib.h>
 #include <xen/spinlock.h>
 #include <xen/sched.h>
+#include <xen/sort.h>
+#include <xen/bsearch.h>
 #include <asm/current.h>
 #include <asm/mmio.h>
 
@@ -70,27 +72,31 @@ static int handle_write(const struct mmio_handler *handler, struct vcpu *v,
                                handler->priv);
 }
 
-static const struct mmio_handler *find_mmio_handler(struct domain *d,
-                                                    paddr_t gpa)
+/* This function assumes that mmio regions are not overlapped */
+static int cmp_mmio_handler(const void *key, const void *elem)
 {
-    const struct mmio_handler *handler;
-    unsigned int i;
-    struct vmmio *vmmio = &d->arch.vmmio;
+    const struct mmio_handler *handler0 = key;
+    const struct mmio_handler *handler1 = elem;
 
-    read_lock(&vmmio->lock);
+    if ( handler0->addr < handler1->addr )
+        return -1;
 
-    for ( i = 0; i < vmmio->num_entries; i++ )
-    {
-        handler = &vmmio->handlers[i];
+    if ( handler0->addr > (handler1->addr + handler1->size) )
+        return 1;
 
-        if ( (gpa >= handler->addr) &&
-             (gpa < (handler->addr + handler->size)) )
-            break;
-    }
+    return 0;
+}
 
-    if ( i == vmmio->num_entries )
-        handler = NULL;
+static const struct mmio_handler *find_mmio_handler(struct domain *d,
+                                                    paddr_t gpa)
+{
+    struct vmmio *vmmio = &d->arch.vmmio;
+    struct mmio_handler key = {.addr = gpa};
+    const struct mmio_handler *handler;
 
+    read_lock(&vmmio->lock);
+    handler = bsearch(&key, vmmio->handlers, vmmio->num_entries,
+                      sizeof(*handler), cmp_mmio_handler);
     read_unlock(&vmmio->lock);
 
     return handler;
@@ -131,6 +137,10 @@ void register_mmio_handler(struct domain *d,
 
     vmmio->num_entries++;
 
+    /* Sort mmio handlers in ascending order based on base address */
+    sort(vmmio->handlers, vmmio->num_entries, sizeof(struct mmio_handler),
+         cmp_mmio_handler, NULL);
+
     write_unlock(&vmmio->lock);
 }
 
-- 
Qualcomm Datacenter Technologies, Inc. on behalf of the Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project.


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

[PATCH RESEND 4/4] arm/vgic: Change fixed number of mmio handlers to variable number

[Shanker Donthineni]

Compute the number of mmio handlers that are required for vGICv3 and
vGICv2 emulation drivers in vgic_v3_init()/vgic_v2_init(). Augment
this variable number of mmio handers to a fixed number MAX_IO_HANDLER
and pass it to domain_io_init() to allocate enough memory.

New code path:
 domain_vgic_register(&count)
   domain_io_init(count + MAX_IO_HANDLER)
     domain_vgic_init()

Signed-off-by: Shanker Donthineni <shankerd@codeaurora.org>
---
 Resend to fix the In-Reply-To/References header fields.

 xen/arch/arm/domain.c      | 12 +++++++-----
 xen/arch/arm/vgic-v2.c     |  3 ++-
 xen/arch/arm/vgic-v3.c     |  5 ++++-
 xen/arch/arm/vgic.c        | 10 +++-------
 xen/include/asm-arm/vgic.h |  5 +++--
 5 files changed, 19 insertions(+), 16 deletions(-)

diff --git a/xen/arch/arm/domain.c b/xen/arch/arm/domain.c
index 0170cee..4e5259b 100644
--- a/xen/arch/arm/domain.c
+++ b/xen/arch/arm/domain.c
@@ -546,7 +546,7 @@ void vcpu_destroy(struct vcpu *v)
 int arch_domain_create(struct domain *d, unsigned int domcr_flags,
                        struct xen_arch_domainconfig *config)
 {
-    int rc, count;
+    int rc, count = 0;
 
     d->arch.relmem = RELMEM_not_started;
 
@@ -569,10 +569,6 @@ int arch_domain_create(struct domain *d, unsigned int domcr_flags,
     share_xen_page_with_guest(
         virt_to_page(d->shared_info), d, XENSHARE_writable);
 
-    count = MAX_IO_HANDLER;
-    if ( (rc = domain_io_init(d, count)) != 0 )
-        goto fail;
-
     if ( (rc = p2m_alloc_table(d)) != 0 )
         goto fail;
 
@@ -609,6 +605,12 @@ int arch_domain_create(struct domain *d, unsigned int domcr_flags,
         goto fail;
     }
 
+    if ( (rc = domain_vgic_register(d, &count)) != 0 )
+        goto fail;
+
+    if ( (rc = domain_io_init(d, count + MAX_IO_HANDLER)) != 0 )
+        goto fail;
+
     if ( (rc = domain_vgic_init(d, config->nr_spis)) != 0 )
         goto fail;
 
diff --git a/xen/arch/arm/vgic-v2.c b/xen/arch/arm/vgic-v2.c
index 6a5e67b..c6d280e 100644
--- a/xen/arch/arm/vgic-v2.c
+++ b/xen/arch/arm/vgic-v2.c
@@ -711,7 +711,7 @@ static const struct vgic_ops vgic_v2_ops = {
     .max_vcpus = 8,
 };
 
-int vgic_v2_init(struct domain *d)
+int vgic_v2_init(struct domain *d, int *mmio_count)
 {
     if ( !vgic_v2_hw.enabled )
     {
@@ -721,6 +721,7 @@ int vgic_v2_init(struct domain *d)
         return -ENODEV;
     }
 
+    *mmio_count = 1; /* Only GICD region */
     register_vgic_ops(d, &vgic_v2_ops);
 
     return 0;
diff --git a/xen/arch/arm/vgic-v3.c b/xen/arch/arm/vgic-v3.c
index be9a9a3..ec038a3 100644
--- a/xen/arch/arm/vgic-v3.c
+++ b/xen/arch/arm/vgic-v3.c
@@ -1499,7 +1499,7 @@ static const struct vgic_ops v3_ops = {
     .max_vcpus = 4096,
 };
 
-int vgic_v3_init(struct domain *d)
+int vgic_v3_init(struct domain *d, int *mmio_count)
 {
     if ( !vgic_v3_hw.enabled )
     {
@@ -1509,6 +1509,9 @@ int vgic_v3_init(struct domain *d)
         return -ENODEV;
     }
 
+    /* GICD region + number of Redistributors */
+    *mmio_count = vgic_v3_rdist_count(d) + 1;
+
     register_vgic_ops(d, &v3_ops);
 
     return 0;
diff --git a/xen/arch/arm/vgic.c b/xen/arch/arm/vgic.c
index a7ccfe7..768cb91 100644
--- a/xen/arch/arm/vgic.c
+++ b/xen/arch/arm/vgic.c
@@ -88,18 +88,18 @@ static void vgic_rank_init(struct vgic_irq_rank *rank, uint8_t index,
         rank->vcpu[i] = vcpu;
 }
 
-static int domain_vgic_register(struct domain *d)
+int domain_vgic_register(struct domain *d, int *mmio_count)
 {
     switch ( d->arch.vgic.version )
     {
 #ifdef CONFIG_HAS_GICV3
     case GIC_V3:
-        if ( vgic_v3_init(d) )
+        if ( vgic_v3_init(d, mmio_count) )
            return -ENODEV;
         break;
 #endif
     case GIC_V2:
-        if ( vgic_v2_init(d) )
+        if ( vgic_v2_init(d, mmio_count) )
             return -ENODEV;
         break;
     default:
@@ -124,10 +124,6 @@ int domain_vgic_init(struct domain *d, unsigned int nr_spis)
 
     d->arch.vgic.nr_spis = nr_spis;
 
-    ret = domain_vgic_register(d);
-    if ( ret < 0 )
-        return ret;
-
     spin_lock_init(&d->arch.vgic.lock);
 
     d->arch.vgic.shared_irqs =
diff --git a/xen/include/asm-arm/vgic.h b/xen/include/asm-arm/vgic.h
index c3cc4f6..300f461 100644
--- a/xen/include/asm-arm/vgic.h
+++ b/xen/include/asm-arm/vgic.h
@@ -304,9 +304,10 @@ extern int vgic_emulate(struct cpu_user_regs *regs, union hsr hsr);
 extern void vgic_disable_irqs(struct vcpu *v, uint32_t r, int n);
 extern void vgic_enable_irqs(struct vcpu *v, uint32_t r, int n);
 extern void register_vgic_ops(struct domain *d, const struct vgic_ops *ops);
-int vgic_v2_init(struct domain *d);
-int vgic_v3_init(struct domain *d);
+int vgic_v2_init(struct domain *d, int *mmio_count);
+int vgic_v3_init(struct domain *d, int *mmio_count);
 
+extern int domain_vgic_register(struct domain *d, int *mmio_count);
 extern int vcpu_vgic_free(struct vcpu *v);
 extern int vgic_to_sgi(struct vcpu *v, register_t sgir,
                        enum gic_sgi_mode irqmode, int virq,
-- 
Qualcomm Datacenter Technologies, Inc. on behalf of the Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project.


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH RESEND 2/4] xen: Add generic implementation of binary search

[Andrew Cooper]

On 15/07/16 18:35, Shanker Donthineni wrote:
> This patch adds the generic implementation of binary search algorithm
> whcih is copied from Linux kernel v4.7-rc7. No functional changes.
>
> Signed-off-by: Shanker Donthineni <shankerd@codeaurora.org>
> ---
>  Resend to fix the In-Reply-To/References header feilds.
>
>  xen/common/Makefile       |  1 +
>  xen/common/bsearch.c      | 51 +++++++++++++++++++++++++++++++++++++++++++++++
>  xen/include/xen/bsearch.h |  9 +++++++++

Having a header file for a single is silly (I have no idea why Linux
does it like that).

I would move it into xen/lib.h which contains a number of other
stdlib.h-like functions.

With that done, Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: [PATCH RESEND 2/4] xen: Add generic implementation of binary search

[Shanker Donthineni]

Hi Andrew,

On 07/15/2016 12:42 PM, Andrew Cooper wrote:
> On 15/07/16 18:35, Shanker Donthineni wrote:
>> This patch adds the generic implementation of binary search algorithm
>> whcih is copied from Linux kernel v4.7-rc7. No functional changes.
>>
>> Signed-off-by: Shanker Donthineni <shankerd@codeaurora.org>
>> ---
>>   Resend to fix the In-Reply-To/References header feilds.
>>
>>   xen/common/Makefile       |  1 +
>>   xen/common/bsearch.c      | 51
> +++++++++++++++++++++++++++++++++++++++++++++++
>>   xen/include/xen/bsearch.h |  9 +++++++++
> Having a header file for a single is silly (I have no idea why Linux
> does it like that).
>
> I would move it into xen/lib.h which contains a number of other
> stdlib.h-like functions.
>
> With that done, Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>

I'll follow your suggestion.

-- 
Shanker Donthineni
Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project.


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel