From mboxrd@z Thu Jan 1 00:00:00 1970 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 From: Avi Kivity 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> Subject: [Qemu-devel] [PATCH 01/23] memory: introduce memory_region_find() List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Stefano Stabellini , qemu-devel@nongnu.org, "Michael S. Tsirkin" Cc: xen-devel@lists.xensource.com, kvm@vger.kernel.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 -- 1.7.7.1