* [PATCH V3 1/4] arm/io: Use separate memory allocation for mmio handlers
2016-07-20 13:53 [PATCH V3 0/4] Change fixed mmio handlers to a variable number Shanker Donthineni
@ 2016-07-20 13:53 ` Shanker Donthineni
2016-07-20 13:53 ` [PATCH V3 2/4] xen: Add generic implementation of binary search Shanker Donthineni
` (3 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: Shanker Donthineni @ 2016-07-20 13:53 UTC (permalink / raw)
To: linux-arm-kernel
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>
---
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.
^ permalink raw reply related [flat|nested] 6+ messages in thread* [PATCH V3 2/4] xen: Add generic implementation of binary search
2016-07-20 13:53 [PATCH V3 0/4] Change fixed mmio handlers to a variable number Shanker Donthineni
2016-07-20 13:53 ` [PATCH V3 1/4] arm/io: Use separate memory allocation for mmio handlers Shanker Donthineni
@ 2016-07-20 13:53 ` Shanker Donthineni
2016-07-20 13:53 ` [PATCH V3 3/4] xen/arm: io: Use binary search for mmio handler lookup Shanker Donthineni
` (2 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: Shanker Donthineni @ 2016-07-20 13:53 UTC (permalink / raw)
To: linux-arm-kernel
This patch adds the generic implementation of binary search algorithm
which is copied from Linux kernel v4.7-rc7. No functional changes.
Signed-off-by: Shanker Donthineni <shankerd@codeaurora.org>
Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Reviewed-by: Julien Grall <julien.grall@arm.com>
---
Changes since v2:
Fixed the compilation issue due to a missing ';'.
Fixed typo.
Changes since v1:
Removed the header file xen/include/xen/bsearch.h.
Defined function bsearch() prototype in the header file xen/lib.h.
xen/common/Makefile | 1 +
xen/common/bsearch.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
xen/include/xen/lib.h | 3 +++
3 files changed, 55 insertions(+)
create mode 100644 xen/common/bsearch.c
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..7090930
--- /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/lib.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/lib.h b/xen/include/xen/lib.h
index b1b0fb2..b90d582 100644
--- a/xen/include/xen/lib.h
+++ b/xen/include/xen/lib.h
@@ -153,4 +153,7 @@ void dump_execstate(struct cpu_user_regs *);
void init_constructors(void);
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+ int (*cmp)(const void *key, const void *elt));
+
#endif /* __LIB_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.
^ permalink raw reply related [flat|nested] 6+ messages in thread* [PATCH V3 3/4] xen/arm: io: Use binary search for mmio handler lookup
2016-07-20 13:53 [PATCH V3 0/4] Change fixed mmio handlers to a variable number Shanker Donthineni
2016-07-20 13:53 ` [PATCH V3 1/4] arm/io: Use separate memory allocation for mmio handlers Shanker Donthineni
2016-07-20 13:53 ` [PATCH V3 2/4] xen: Add generic implementation of binary search Shanker Donthineni
@ 2016-07-20 13:53 ` Shanker Donthineni
2016-07-20 13:54 ` [PATCH V3 4/4] arm/vgic: Change fixed number of mmio handlers to variable number Shanker Donthineni
2016-07-20 13:59 ` [PATCH V3 0/4] Change fixed mmio handlers to a " Shanker Donthineni
4 siblings, 0 replies; 6+ messages in thread
From: Shanker Donthineni @ 2016-07-20 13:53 UTC (permalink / raw)
To: linux-arm-kernel
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>
---
xen/arch/arm/io.c | 39 ++++++++++++++++++++++++---------------
1 file changed, 24 insertions(+), 15 deletions(-)
diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
index 40330f0..e8aa7fa 100644
--- a/xen/arch/arm/io.c
+++ b/xen/arch/arm/io.c
@@ -20,6 +20,7 @@
#include <xen/lib.h>
#include <xen/spinlock.h>
#include <xen/sched.h>
+#include <xen/sort.h>
#include <asm/current.h>
#include <asm/mmio.h>
@@ -70,27 +71,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 +136,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.
^ permalink raw reply related [flat|nested] 6+ messages in thread* [PATCH V3 4/4] arm/vgic: Change fixed number of mmio handlers to variable number
2016-07-20 13:53 [PATCH V3 0/4] Change fixed mmio handlers to a variable number Shanker Donthineni
` (2 preceding siblings ...)
2016-07-20 13:53 ` [PATCH V3 3/4] xen/arm: io: Use binary search for mmio handler lookup Shanker Donthineni
@ 2016-07-20 13:54 ` Shanker Donthineni
2016-07-20 13:59 ` [PATCH V3 0/4] Change fixed mmio handlers to a " Shanker Donthineni
4 siblings, 0 replies; 6+ messages in thread
From: Shanker Donthineni @ 2016-07-20 13:54 UTC (permalink / raw)
To: linux-arm-kernel
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>
---
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.
^ permalink raw reply related [flat|nested] 6+ messages in thread* [PATCH V3 0/4] Change fixed mmio handlers to a variable number
2016-07-20 13:53 [PATCH V3 0/4] Change fixed mmio handlers to a variable number Shanker Donthineni
` (3 preceding siblings ...)
2016-07-20 13:54 ` [PATCH V3 4/4] arm/vgic: Change fixed number of mmio handlers to variable number Shanker Donthineni
@ 2016-07-20 13:59 ` Shanker Donthineni
4 siblings, 0 replies; 6+ messages in thread
From: Shanker Donthineni @ 2016-07-20 13:59 UTC (permalink / raw)
To: linux-arm-kernel
Hi All,
I am very sorry, and it is my mistake for sending this patchset to
linux-kernel mailing list. Please don't look at this one.
On 07/20/2016 08:53 AM, Shanker Donthineni wrote:
> 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 | 52 +++++++++++++++++++++++++++++++---------------
> 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/lib.h | 3 +++
> 10 files changed, 115 insertions(+), 34 deletions(-)
> create mode 100644 xen/common/bsearch.c
>
--
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.
^ permalink raw reply [flat|nested] 6+ messages in thread