[Qemu-devel] [PATCH 08/14] memory: add memory_region_find_subregion

[Michael Roth]

Similar to memory_region_find, but only search for overlaps among
regions that are a child of the region passed in. This is useful
for finding free ranges within a parent range to map to, in
addition to the use-cases similarly served by memory_region_find.

Signed-off-by: Michael Roth <address@hidden>
---
 include/exec/memory.h |   34 +++++++++++++++++++++++++++++++++
 memory.c              |   50 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 84 insertions(+)

diff --git a/include/exec/memory.h b/include/exec/memory.h
index 480dfbf..784b262 100644
--- a/include/exec/memory.h
+++ b/include/exec/memory.h
@@ -883,6 +883,40 @@ MemoryRegionSection memory_region_find(MemoryRegion *mr,
                                        hwaddr addr, uint64_t size);
 
 /**
+ * memory_region_find_subregion: translate an address/size relative
+ * to a MemoryRegion into a #MemoryRegionSection corresponding to
+ * a child of that region.
+ *
+ * This is similar to memory_region_find, but locates the first
+ * #MemoryRegion within @mr that overlaps the range, as opposed to
+ * the first #MemoryRegion with @mr's address space.
+ *
+ * Returns a #MemoryRegionSection that describes a contiguous overlap.
+ * It will have the following characteristics:
+ *    address@hidden = 0 iff no overlap was found
+ *    address@hidden is non-%NULL iff an overlap was found
+ *
+ * Remember that in the return value the @offset_within_region is
+ * relative to the returned region (in the address@hidden field), not to the
+ * @mr argument.
+ *
+ * Similarly, the address@hidden is relative to the
+ * address space that contains both regions, the passed and the
+ * returned one.  However, in the special case where the @mr argument
+ * has no parent (and thus is the root of the address space), the
+ * following will hold:
+ *    address@hidden >= @addr
+ *    address@hidden + address@hidden <= @addr + @size
+ *
+ * @mr: a MemoryRegion within which @addr is a relative address
+ * @addr: start of the area within @as to be searched
+ * @size: size of the area to be searched
+ */
+MemoryRegionSection memory_region_find_subregion(MemoryRegion *mr,
+                                                 hwaddr addr,
+                                                 uint64_t size);
+
+/**
  * address_space_sync_dirty_bitmap: synchronize the dirty log for all memory
  *
  * Synchronizes the dirty page log for an entire address space.
diff --git a/memory.c b/memory.c
index 28f6449..487e710 100644
--- a/memory.c
+++ b/memory.c
@@ -1574,6 +1574,56 @@ bool memory_region_present(MemoryRegion *parent, hwaddr 
addr)
     return true;
 }
 
+MemoryRegionSection memory_region_find_subregion(MemoryRegion *mr,
+                                                 hwaddr addr, uint64_t size)
+{
+    MemoryRegionSection ret = { 0 };
+    MemoryRegion *submr = NULL;
+
+    QTAILQ_FOREACH(submr, &mr->subregions, subregions_link) {
+        if (!(submr->addr + memory_region_size(submr) - 1 < addr ||
+            submr->addr >= addr + size)) {
+            break;
+        }
+    }
+
+    if (submr) {
+        hwaddr as_addr;
+        MemoryRegion *root;
+        Int128 last_range_addr = int128_make64(addr + size);
+        Int128 last_region_addr =
+            int128_make64(submr->addr + memory_region_size(submr));
+
+        for (root = submr, as_addr = submr->addr; root->parent; ) {
+            root = root->parent;
+            as_addr += root->addr;
+        }
+        ret.mr = submr;
+        ret.size = submr->size;
+        ret.offset_within_address_space = as_addr;
+        /* if the region begins before the range we're checking, subtract the
+         * difference from our offset/size
+         */
+        if (submr->addr <= addr) {
+            ret.offset_within_region = addr - submr->addr;
+            ret.offset_within_address_space += ret.offset_within_region;
+            ret.size = int128_sub(ret.size,
+                                  int128_make64(ret.offset_within_region));
+        }
+        /* if the region extends beyond the range we're checking, subtract the
+         * difference from our size
+         */
+        if (int128_gt(last_region_addr, last_range_addr)) {
+            ret.size = int128_sub(ret.size,
+                                  int128_sub(last_region_addr,
+                                             last_range_addr));
+        }
+        memory_region_ref(ret.mr);
+    }
+
+    return ret;
+}
+
 MemoryRegionSection memory_region_find(MemoryRegion *mr,
                                        hwaddr addr, uint64_t size)
 {
-- 
1.7.9.5