Patchwork [01/23] memory: introduce memory_region_find()

login
register
mail settings
Submitter Avi Kivity
Date Dec. 19, 2011, 2:13 p.m.
Message ID <1324304024-11220-2-git-send-email-avi@redhat.com>
Download mbox | patch
Permalink /patch/132258/
State New
Headers show

Comments

Avi Kivity - Dec. 19, 2011, 2:13 p.m.
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>
---
 memory.c |   62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 memory.h |   32 ++++++++++++++++++++++++++++++++
 2 files changed, 94 insertions(+), 0 deletions(-)
Anthony Liguori - Dec. 19, 2011, 3:25 p.m.
On 12/19/2011 09:17 AM, Avi Kivity wrote:
> On 12/19/2011 05:10 PM, Anthony Liguori wrote:
>> On 12/19/2011 09:04 AM, Avi Kivity wrote:
>>> On 12/19/2011 04:50 PM, Anthony Liguori wrote:
>>>>> +static int cmp_flatrange_addr(const void *_addr, const void *_fr)
>>>>> +{
>>>>> +    const AddrRange *addr = _addr;
>>>>> +    const FlatRange *fr = _fr;
>>>>
>>>>
>>>> Please don't prefix with an underscore.
>>>
>>> Why not?  It's legal according to the standards, if that's your concern
>>> (only _[_A-Z]+ are reserved).
>>
>> http://www.gnu.org/s/hello/manual/libc/Reserved-Names.html
>>
>> "In addition to the names documented in this manual, reserved names
>> include all external identifiers (global functions and variables) that
>> begin with an underscore (‘_’)"
>>
>> Now that might just mean that you're shadowing a global name, so maybe
>> that's okay, but I think it's easier to just enforce a consistent rule
>> of, "don't start identifiers with an underscore".
>
> I rather like the pattern
>
>     void callback(void *_foo)
>     {
>           Foo *foo = _foo;
>
>           ...
>     }
>
> If the consensus is that we don't want it, I'll change it, but I do
> think it's useful.

I dislike enforcing coding style but it's a necessary evil. I greater prefer 
simple rules to subtle ones as it creates less confusion so I'd prefer you 
change this.

>
>>>>> +MemoryRegionSection memory_region_find(MemoryRegion *address_space,
>>>>> +                                       target_phys_addr_t addr,
>>>>> uint64_t size);
>>>>
>>>>
>>>> Returning structs by value is a bit unexpected.
>>>
>>> It's just prejudice, here's the call sequence:
>>
>> It's not about whether it's fast or slow.  It's just unexpected.
>
> It's plain C, I don't see why it's so unexpected.
>
>>
>> Instead of returning a NULL pointer on error, you set .mr to NULL if
>> an error occurs (which isn't documented by the comment btw).
>> Returning a pointer, or taking a pointer and returning a 0/-1 return
>> value makes for a more consistent semantic with the rest of the code
>> base.
>>
>
> How can I return a pointer?  If I allocate it, someone has to free it.
> If I pass it as a parameter, we end up with a silly looking calling
> convention.  If I return an error code, the caller has to set up an
> additional variable.
>
> The natural check is section.size which is always meaningful -
> memory_region_find() returns a subrange of the input, which may be
> zero.  You're right that I should document it (and I should use it
> consistently).

I'm not going to make a fuss over something like this so if you really prefer 
this style, I'm not going to object strongly.

But it should be at least be documented and used consistently.

Regards,

Anthony Liguori
Avi Kivity - Dec. 19, 2011, 3:28 p.m.
On 12/19/2011 05:25 PM, Anthony Liguori wrote:
>> I rather like the pattern
>>
>>     void callback(void *_foo)
>>     {
>>           Foo *foo = _foo;
>>
>>           ...
>>     }
>>
>> If the consensus is that we don't want it, I'll change it, but I do
>> think it's useful.
>
>
> I dislike enforcing coding style but it's a necessary evil. I greater
> prefer simple rules to subtle ones as it creates less confusion so I'd
> prefer you change this.

Okay.

>> How can I return a pointer?  If I allocate it, someone has to free it.
>> If I pass it as a parameter, we end up with a silly looking calling
>> convention.  If I return an error code, the caller has to set up an
>> additional variable.
>>
>> The natural check is section.size which is always meaningful -
>> memory_region_find() returns a subrange of the input, which may be
>> zero.  You're right that I should document it (and I should use it
>> consistently).
>
> I'm not going to make a fuss over something like this so if you really
> prefer this style, I'm not going to object strongly.
>
> But it should be at least be documented and used consistently.

Will update both.
Avi Kivity - Dec. 19, 2011, 3:52 p.m.
On 12/19/2011 05:28 PM, Avi Kivity wrote:
> >
> > But it should be at least be documented and used consistently.
>
> Will update both.

Updated patchset in qemu-kvm.git page_desc.  Will refrain from reposting
until some time has passed for review.

Patch

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