Received: from eggs.gnu.org ([2001:4830:134:3::10]:35319) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VfuVC-0007XK-TP for qemu-devel@nongnu.org; Mon, 11 Nov 2013 11:38:20 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VfuV6-0000Ok-UW for qemu-devel@nongnu.org; Mon, 11 Nov 2013 11:38:14 -0500 Received: from mx1.redhat.com ([209.132.183.28]:59406) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VfuV6-0000Of-Iz for qemu-devel@nongnu.org; Mon, 11 Nov 2013 11:38:08 -0500 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id rABGc6eo024600 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Mon, 11 Nov 2013 11:38:07 -0500 Received: from redhat.com (vpn1-4-246.ams2.redhat.com [10.36.4.246]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with SMTP id rABGc4gt001733 for ; Mon, 11 Nov 2013 11:38:05 -0500 Date: Mon, 11 Nov 2013 18:41:05 +0200 From: "Michael S. Tsirkin" Message-ID: <1384187560-20557-6-git-send-email-mst@redhat.com> References: <1384187560-20557-1-git-send-email-mst@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1384187560-20557-1-git-send-email-mst@redhat.com> Subject: [Qemu-devel] [PATCH RFC 5/5] exec: memory radix tree page level compression List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org 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, it's a simple matter to detect configurations where a single L2 entry is valid. We can them speed up the lookup by skipping one or more levels. Signed-off-by: Michael S. Tsirkin --- exec.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 71 insertions(+) diff --git a/exec.c b/exec.c index 39f76ee..3ec6c2c 100644 --- a/exec.c +++ b/exec.c @@ -216,6 +216,75 @@ 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 || test_and_set_bit(lp->ptr, compacted)) { + return; + } + + set_bit(lp->ptr, compacted); + + 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); + int i; + + return; + + for (i = 0; i < next_map.nodes_nb; ++i) { + if (d->phys_map.skip) { + phys_page_compact(&d->phys_map, d->nodes, compacted); + } + } +} + static MemoryRegionSection *phys_page_find(PhysPageEntry lp, hwaddr index, Node *nodes, MemoryRegionSection *sections) { @@ -1659,6 +1728,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