memory: introduce memory_region_find()

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 <avi@redhat.com>

1 files changed, 62 insertions, 0 deletions

diff --git a/memory.c b/memory.c
index 6e6163524b..c3e64ba138 100644
--- a/memory.c
+++ b/memory.c
@@ -515,6 +515,20 @@ static AddressSpace address_space_io = {
     .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.
  */
@@ -1386,6 +1400,54 @@ void memory_region_set_alias_offset(MemoryRegion *mr, target_phys_addr_t offset)
     memory_region_update_topology(mr);
 }
 
+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, .size = 0 };
+
+    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;