[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PULL 13/28] exec: memory radix tree page level compression
From: |
Michael S. Tsirkin |
Subject: |
[Qemu-devel] [PULL 13/28] exec: memory radix tree page level compression |
Date: |
Wed, 11 Dec 2013 20:30:49 +0200 |
At the moment, memory radix tree is already variable width, but it can
only skip the low bits of address.
This is efficient if we have huge memory regions but inefficient if we
are only using a tiny portion of the address space.
After we have built up the map, detect
configurations where a single L2 entry is valid.
We then speed up the lookup by skipping one or more levels.
In case any levels were skipped, we might end up in a valid section
instead of erroring out. We handle this by checking that
the address is in range of the resulting section.
Signed-off-by: Michael S. Tsirkin <address@hidden>
---
exec.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 74 insertions(+), 1 deletion(-)
diff --git a/exec.c b/exec.c
index b528dad..7e5ce93 100644
--- a/exec.c
+++ b/exec.c
@@ -51,6 +51,8 @@
#include "exec/memory-internal.h"
+#include "qemu/range.h"
+
//#define DEBUG_SUBPAGE
#if !defined(CONFIG_USER_ONLY)
@@ -216,6 +218,68 @@ static void phys_page_set(AddressSpaceDispatch *d,
phys_page_set_level(&d->phys_map, &index, &nb, leaf, P_L2_LEVELS - 1);
}
+/* Compact a non leaf page entry. Simply detect that the entry has a single
child,
+ * and update our entry so we can skip it and go directly to the destination.
+ */
+static void phys_page_compact(PhysPageEntry *lp, Node *nodes, unsigned long
*compacted)
+{
+ unsigned valid_ptr = P_L2_SIZE;
+ int valid = 0;
+ PhysPageEntry *p;
+ int i;
+
+ if (lp->ptr == PHYS_MAP_NODE_NIL) {
+ return;
+ }
+
+ p = nodes[lp->ptr];
+ for (i = 0; i < P_L2_SIZE; i++) {
+ if (p[i].ptr == PHYS_MAP_NODE_NIL) {
+ continue;
+ }
+
+ valid_ptr = i;
+ valid++;
+ if (p[i].skip) {
+ phys_page_compact(&p[i], nodes, compacted);
+ }
+ }
+
+ /* We can only compress if there's only one child. */
+ if (valid != 1) {
+ return;
+ }
+
+ assert(valid_ptr < P_L2_SIZE);
+
+ /* Don't compress if it won't fit in the # of bits we have. */
+ if (lp->skip + p[valid_ptr].skip >= (1 << 3)) {
+ return;
+ }
+
+ lp->ptr = p[valid_ptr].ptr;
+ if (!p[valid_ptr].skip) {
+ /* If our only child is a leaf, make this a leaf. */
+ /* By design, we should have made this node a leaf to begin with so we
+ * should never reach here.
+ * But since it's so simple to handle this, let's do it just in case we
+ * change this rule.
+ */
+ lp->skip = 0;
+ } else {
+ lp->skip += p[valid_ptr].skip;
+ }
+}
+
+static void phys_page_compact_all(AddressSpaceDispatch *d, int nodes_nb)
+{
+ DECLARE_BITMAP(compacted, nodes_nb);
+
+ if (d->phys_map.skip) {
+ phys_page_compact(&d->phys_map, d->nodes, compacted);
+ }
+}
+
static MemoryRegionSection *phys_page_find(PhysPageEntry lp, hwaddr addr,
Node *nodes, MemoryRegionSection
*sections)
{
@@ -230,7 +294,14 @@ static MemoryRegionSection *phys_page_find(PhysPageEntry
lp, hwaddr addr,
p = nodes[lp.ptr];
lp = p[(index >> (i * P_L2_BITS)) & (P_L2_SIZE - 1)];
}
- return §ions[lp.ptr];
+
+ if (sections[lp.ptr].size.hi ||
+ range_covers_byte(sections[lp.ptr].offset_within_address_space,
+ sections[lp.ptr].size.lo, addr)) {
+ return §ions[lp.ptr];
+ } else {
+ return §ions[PHYS_SECTION_UNASSIGNED];
+ }
}
bool memory_region_is_unassigned(MemoryRegion *mr)
@@ -1696,6 +1767,8 @@ static void mem_commit(MemoryListener *listener)
next->nodes = next_map.nodes;
next->sections = next_map.sections;
+ phys_page_compact_all(next, next_map.nodes_nb);
+
as->dispatch = next;
g_free(cur);
}
--
MST
- [Qemu-devel] [PULL 02/28] pc: map PCI address space as catchall region for not mapped addresses, (continued)
- [Qemu-devel] [PULL 02/28] pc: map PCI address space as catchall region for not mapped addresses, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 04/28] acpi-test: basic acpi unit-test, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 05/28] MAINTAINERS: update X86 machine entry, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 06/28] pci: fix address space size for bridge, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 08/28] spapr_pci: s/INT64_MAX/UINT64_MAX/, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 07/28] pc: s/INT64_MAX/UINT64_MAX/, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 09/28] split definitions for exec.c and translate-all.c radix trees, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 10/28] exec: replace leaf with skip, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 11/28] exec: extend skip field to 6 bit, page entry to 32 bit, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 12/28] exec: pass hw address to phys_page_find, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 13/28] exec: memory radix tree page level compression,
Michael S. Tsirkin <=
- [Qemu-devel] [PULL 14/28] exec: make address spaces 64-bit wide, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 15/28] exec: reduce L2_PAGE_SIZE, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 16/28] smbios: Set system manufacturer, product & version by default, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 21/28] hpet: inverse polarity when pin above ISA_NUM_IRQS, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 23/28] memory.c: bugfix - ref counting mismatch in memory_region_find, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 24/28] exec: separate sections and nodes per address space, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 22/28] hpet: enable to entitle more irq pins for hpet, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 25/28] acpi unit-test: load and check facs table, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 26/28] acpi unit-test: adjust the test data structure for better handling, Michael S. Tsirkin, 2013/12/11
- [Qemu-devel] [PULL 28/28] pc: use macro for HPET type, Michael S. Tsirkin, 2013/12/11