From patchwork Mon Dec 19 14:13:22 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Avi Kivity X-Patchwork-Id: 132258 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [140.186.70.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 554C3B6FFE for ; Tue, 20 Dec 2011 02:24:48 +1100 (EST) Received: from localhost ([::1]:52764 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rcdzj-0005Zr-W8 for incoming@patchwork.ozlabs.org; Mon, 19 Dec 2011 09:15:11 -0500 Received: from eggs.gnu.org ([140.186.70.92]:48616) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rcdyn-0002wh-Po for qemu-devel@nongnu.org; Mon, 19 Dec 2011 09:14:20 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Rcdyg-0001tW-0U for qemu-devel@nongnu.org; Mon, 19 Dec 2011 09:14:13 -0500 Received: from mx1.redhat.com ([209.132.183.28]:56042) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rcdyf-0001sx-Oq for qemu-devel@nongnu.org; Mon, 19 Dec 2011 09:14:05 -0500 Received: from int-mx12.intmail.prod.int.phx2.redhat.com (int-mx12.intmail.prod.int.phx2.redhat.com [10.5.11.25]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id pBJEDxKw008933 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Mon, 19 Dec 2011 09:13:59 -0500 Received: from cleopatra.tlv.redhat.com (cleopatra.tlv.redhat.com [10.35.255.11]) by int-mx12.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id pBJEDwM4032280; Mon, 19 Dec 2011 09:13:58 -0500 Received: from s01.tlv.redhat.com (s01.tlv.redhat.com [10.35.255.8]) by cleopatra.tlv.redhat.com (Postfix) with ESMTP id 8BF08250BA0; Mon, 19 Dec 2011 16:13:54 +0200 (IST) From: Avi Kivity To: Stefano Stabellini , qemu-devel@nongnu.org, "Michael S. Tsirkin" Date: Mon, 19 Dec 2011 16:13:22 +0200 Message-Id: <1324304024-11220-2-git-send-email-avi@redhat.com> In-Reply-To: <1324304024-11220-1-git-send-email-avi@redhat.com> References: <1324304024-11220-1-git-send-email-avi@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.25 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 209.132.183.28 Cc: xen-devel@lists.xensource.com, kvm@vger.kernel.org Subject: [Qemu-devel] [PATCH 01/23] memory: introduce memory_region_find() X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Given an address space (represented by the top-level memory region), returns the memory region that maps a given range. Useful for implementing DMA. The implementation is a simplistic binary search. Once we have a tree representation this can be optimized. Signed-off-by: Avi Kivity --- memory.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ memory.h | 32 ++++++++++++++++++++++++++++++++ 2 files changed, 94 insertions(+), 0 deletions(-) diff --git a/memory.c b/memory.c index cbd6988..d8b7c27 100644 --- a/memory.c +++ b/memory.c @@ -514,6 +514,20 @@ static void as_io_ioeventfd_del(AddressSpace *as, MemoryRegionIoeventfd *fd) .ops = &address_space_ops_io, }; +static AddressSpace *memory_region_to_address_space(MemoryRegion *mr) +{ + while (mr->parent) { + mr = mr->parent; + } + if (mr == address_space_memory.root) { + return &address_space_memory; + } + if (mr == address_space_io.root) { + return &address_space_io; + } + abort(); +} + /* Render a memory region into the global view. Ranges in @view obscure * ranges in @mr. */ @@ -1309,6 +1323,54 @@ void memory_region_del_subregion(MemoryRegion *mr, memory_region_update_topology(); } +static int cmp_flatrange_addr(const void *_addr, const void *_fr) +{ + const AddrRange *addr = _addr; + const FlatRange *fr = _fr; + + if (int128_le(addrrange_end(*addr), fr->addr.start)) { + return -1; + } else if (int128_ge(addr->start, addrrange_end(fr->addr))) { + return 1; + } + return 0; +} + +static FlatRange *address_space_lookup(AddressSpace *as, AddrRange addr) +{ + return bsearch(&addr, as->current_map.ranges, as->current_map.nr, + sizeof(FlatRange), cmp_flatrange_addr); +} + +MemoryRegionSection memory_region_find(MemoryRegion *address_space, + target_phys_addr_t addr, uint64_t size) +{ + AddressSpace *as = memory_region_to_address_space(address_space); + AddrRange range = addrrange_make(int128_make64(addr), + int128_make64(size)); + FlatRange *fr = address_space_lookup(as, range); + MemoryRegionSection ret = { .mr = NULL }; + + if (!fr) { + return ret; + } + + while (fr > as->current_map.ranges + && addrrange_intersects(fr[-1].addr, range)) { + --fr; + } + + ret.mr = fr->mr; + range = addrrange_intersection(range, fr->addr); + ret.offset_within_region = fr->offset_in_region; + ret.offset_within_region += int128_get64(int128_sub(range.start, + fr->addr.start)); + ret.size = int128_get64(range.size); + ret.offset_within_address_space = int128_get64(range.start); + return ret; +} + + void set_system_memory_map(MemoryRegion *mr) { address_space_memory.root = mr; diff --git a/memory.h b/memory.h index beae127..1d5c414 100644 --- a/memory.h +++ b/memory.h @@ -146,6 +146,24 @@ struct MemoryRegionPortio { #define PORTIO_END_OF_LIST() { } +typedef struct MemoryRegionSection MemoryRegionSection; + +/** + * MemoryRegionSection: describes a fragment of a #MemoryRegion + * + * @mr: the region, or %NULL if empty + * @offset_within_region: the beginning of the section, relative to @mr's start + * @size: the size of the section; will not exceed @mr's boundaries + * @offset_within_address_space: the address of the first byte of the section + * relative to the region's address space + */ +struct MemoryRegionSection { + MemoryRegion *mr; + target_phys_addr_t offset_within_region; + uint64_t size; + target_phys_addr_t offset_within_address_space; +}; + /** * memory_region_init: Initialize a memory region * @@ -502,6 +520,20 @@ void memory_region_del_subregion(MemoryRegion *mr, MemoryRegion *subregion); /** + * memory_region_find: locate a MemoryRegion in an address space + * + * Locates the first #MemoryRegion within an address space given by + * @address_space that overlaps the range given by @addr and @size. + * + * @address_space: a top-level (i.e. parentless) region that contains + * the region to be found + * @addr: start of the area within @address_space to be searched + * @size: size of the area to be searched + */ +MemoryRegionSection memory_region_find(MemoryRegion *address_space, + target_phys_addr_t addr, uint64_t size); + +/** * memory_region_transaction_begin: Start a transaction. * * During a transaction, changes will be accumulated and made visible