qapi/range/memory-device: fixes and cleanups

If there are no changes, let's use a const pointer.

Signed-off-by David Hildenbrand <[email protected]>

---
 include/qemu/range.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

include/qemu/range.h +3 -3

index f28f0c1825..7e75f4e655 100644
@@ -39,7 +39,7 @@ struct Range {
     uint64_t upb;        /* inclusive upper bound */
 };
 
-static inline void range_invariant(Range *range)
+static inline void range_invariant(const Range *range)
 {
     assert(range->lob <= range->upb || range->lob == range->upb + 1);
 }

@@ -48,14 +48,14 @@ static inline void range_invariant(Range *range)
 #define range_empty ((Range){ .lob = 1, .upb = 0 })
 
 /* Is @range empty? */
-static inline bool range_is_empty(Range *range)
+static inline bool range_is_empty(const Range *range)
 {
     range_invariant(range);
     return range->lob > range->upb;
 }
 
 /* Does @range contain @val? */
-static inline bool range_contains(Range *range, uint64_t val)
+static inline bool range_contains(const Range *range, uint64_t val)
 {
     return val >= range->lob && val <= range->upb;
 }

Signature · 1 line

2.17.1

Add some more functions that will be used in memory-device context.

range_init(): Init using lower bound and size range_valid(): Check if there would be an overflow when initializin range_size(): Extract the size of a range range_overlaps_range(): Check for overlaps of two ranges range_contains_range(): Check if one range is contained in the other range_starts_before_range(): Check if one range starts before another range_ends_after_range(): Check if one range ends after another

Signed-off-by David Hildenbrand <[email protected]>

---
 include/qemu/range.h | 80 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)

include/qemu/range.h +9 -0

index 7e75f4e655..18e8acf22f 100644
@@ -112,6 +112,86 @@ static inline uint64_t range_upb(Range *range)
     return range->upb;
 }
 
+/*
+ * Initialize @range to span the interval [@lob,@lob + @size - 1].
+ * @size may be 0.
+ */
+static inline void range_init(Range *range, uint64_t lob, uint64_t size)
+{
+    range->lob = lob;
+    range->upb = lob + size - 1;
+    range_invariant(range);

include/qemu/range.h +60 -0

+/*
+ * Get the size of @range.
+ */
+static inline uint64_t range_size(const Range *range)
+{
+    return range->upb - range->lob + 1;
+}
+
+/*
+ * Check if @range1 overlaps with @range2. If one of the ranges is empty,
+ * the result is always "false".
+ */
+static inline bool range_overlaps_range(const Range *range1,
+                                        const Range *range2)
+{
+    if (range_is_empty(range1) || range_is_empty(range2)) {
+        return false;
+    }
+    return !(range2->upb < range1->lob || range1->upb < range2->lob);
+}
+
+/*
+ * Check if @range1 contains @range2. If one of the ranges is empty,
+ * the result is always "false".
+ */
+static inline bool range_contains_range(const Range *range1,
+                                        const Range *range2)
+{
+    if (range_is_empty(range1) || range_is_empty(range2)) {
+        return false;
+    }
+    return range1->lob <= range2->lob && range1->upb >= range2->upb;
+}
+
+/*
+ * Check if @range1 starts before @range2. If one of the ranges is empty,
+ * the result is alsways "false".
+ */
+static inline bool range_starts_before_range(const Range *range1,
+                                             const Range *range2)
+{
+    if (range_is_empty(range1) || range_is_empty(range2)) {
+        return false;
+    }
+    return range1->lob < range2->lob;
+}
+
+/*
+ * Check if @range1 ends after @range2. If one of the ranges is empty,
+ * the result is alsways "false".
+ */
+static inline bool range_ends_after_range(const Range *range1,
+                                          const Range *range2)
+{
+    if (range_is_empty(range1) || range_is_empty(range2)) {
+        return false;
+    }
+    return range1->upb > range2->upb;
+}
+
 /*
  * Extend @range to the smallest interval that includes @extend_by, too.
  */

Signature · 1 line

2.17.1

Quoted 37 lines · * David Hildenbrand ([email protected]) wrote:

Add some more functions that will be used in memory-device context.

range_init(): Init using lower bound and size range_valid(): Check if there would be an overflow when initializin range_size(): Extract the size of a range range_overlaps_range(): Check for overlaps of two ranges range_contains_range(): Check if one range is contained in the other range_starts_before_range(): Check if one range starts before another range_ends_after_range(): Check if one range ends after another

Signed-off-by David Hildenbrand <[email protected]>

---
 include/qemu/range.h | 80 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)

include/qemu/range.h +14 -0

index 7e75f4e655..18e8acf22f 100644
@@ -112,6 +112,86 @@ static inline uint64_t range_upb(Range *range)
     return range->upb;
 }
 
+/*
+ * Initialize @range to span the interval [@lob,@lob + @size - 1].
+ * @size may be 0.
+ */
+static inline void range_init(Range *range, uint64_t lob, uint64_t size)
+{
+    range->lob = lob;
+    range->upb = lob + size - 1;
+    range_invariant(range);
+}
+
+/*
+ * Check if the interval [@lob,@lob + @size - 1] would be valid or not
+ * (result in an overflow).

include/qemu/range.h static inline uint64_t range_upb(Range *range) · line 133

Quoted 5 lines

include/qemu/range.h +5 -0

+ */
+static inline bool range_valid(uint64_t lob, uint64_t size)
+{
+    return lob + size >= lob;
+}

That name confused me, I'd expected that to have taken a range and check it for something (like a non-asserting version of the invariant).

Quoted 38 lines · Dr. David Alan Gilbert

Quoted 37 lines · * David Hildenbrand ([email protected]) wrote:

Add some more functions that will be used in memory-device context.

range_init(): Init using lower bound and size range_valid(): Check if there would be an overflow when initializin range_size(): Extract the size of a range range_overlaps_range(): Check for overlaps of two ranges range_contains_range(): Check if one range is contained in the other range_starts_before_range(): Check if one range starts before another range_ends_after_range(): Check if one range ends after another

Signed-off-by David Hildenbrand <[email protected]>

---
 include/qemu/range.h | 80 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)

include/qemu/range.h +14 -0

index 7e75f4e655..18e8acf22f 100644
@@ -112,6 +112,86 @@ static inline uint64_t range_upb(Range *range)
     return range->upb;
 }
 
+/*
+ * Initialize @range to span the interval [@lob,@lob + @size - 1].
+ * @size may be 0.
+ */
+static inline void range_init(Range *range, uint64_t lob, uint64_t size)
+{
+    range->lob = lob;
+    range->upb = lob + size - 1;
+    range_invariant(range);
+}
+
+/*
+ * Check if the interval [@lob,@lob + @size - 1] would be valid or not
+ * (result in an overflow).

Quoted 8 lines

include/qemu/range.h static inline uint64_t range_upb(Range *range) · line 133

Quoted 5 lines

include/qemu/range.h +5 -0

+ */
+static inline bool range_valid(uint64_t lob, uint64_t size)
+{
+    return lob + size >= lob;
+}

That name confused me, I'd expected that to have taken a range and check it for something (like a non-asserting version of the invariant).

Then we have to remove all the variant asserts from the initializer functions (well, because then it is no longer an invariant then). Other ideas?

Signature · 3 lines

Thanks,

David / dhildenb

Quoted 48 lines · * David Hildenbrand ([email protected]) wrote:

Quoted 46 lines · Dr. David Alan Gilbert

Quoted 32 lines · * David Hildenbrand ([email protected]) wrote:

Add some more functions that will be used in memory-device context.

range_init(): Init using lower bound and size range_valid(): Check if there would be an overflow when initializin range_size(): Extract the size of a range range_overlaps_range(): Check for overlaps of two ranges range_contains_range(): Check if one range is contained in the other range_starts_before_range(): Check if one range starts before another range_ends_after_range(): Check if one range ends after another

Signed-off-by David Hildenbrand <[email protected]>

---
 include/qemu/range.h | 80 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)

include/qemu/range.h +9 -0

index 7e75f4e655..18e8acf22f 100644
@@ -112,6 +112,86 @@ static inline uint64_t range_upb(Range *range)
     return range->upb;
 }
 
+/*
+ * Initialize @range to span the interval [@lob,@lob + @size - 1].
+ * @size may be 0.
+ */
+static inline void range_init(Range *range, uint64_t lob, uint64_t size)
+{
+    range->lob = lob;
+    range->upb = lob + size - 1;
+    range_invariant(range);

include/qemu/range.h static inline uint64_t range_upb(Range *range) · line 133

Quoted 10 lines

include/qemu/range.h +10 -0

+}
+
+/*
+ * Check if the interval [@lob,@lob + @size - 1] would be valid or not
+ * (result in an overflow).
+ */
+static inline bool range_valid(uint64_t lob, uint64_t size)
+{
+    return lob + size >= lob;
+}

That name confused me, I'd expected that to have taken a range and check it for something (like a non-asserting version of the invariant).

Quoted 3 lines

Then we have to remove all the variant asserts from the initializer functions (well, because then it is no longer an invariant then). Other ideas?

My worry here is just the name 'range_valid'.

Dave

Quoted 49 lines · Dr. David Alan Gilbert

Quoted 48 lines · * David Hildenbrand ([email protected]) wrote:

Quoted 46 lines · Dr. David Alan Gilbert

Quoted 32 lines · * David Hildenbrand ([email protected]) wrote:

Add some more functions that will be used in memory-device context.

range_init(): Init using lower bound and size range_valid(): Check if there would be an overflow when initializin range_size(): Extract the size of a range range_overlaps_range(): Check for overlaps of two ranges range_contains_range(): Check if one range is contained in the other range_starts_before_range(): Check if one range starts before another range_ends_after_range(): Check if one range ends after another

Signed-off-by David Hildenbrand <[email protected]>

---
 include/qemu/range.h | 80 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)

include/qemu/range.h +9 -0

index 7e75f4e655..18e8acf22f 100644
@@ -112,6 +112,86 @@ static inline uint64_t range_upb(Range *range)
     return range->upb;
 }
 
+/*
+ * Initialize @range to span the interval [@lob,@lob + @size - 1].
+ * @size may be 0.
+ */
+static inline void range_init(Range *range, uint64_t lob, uint64_t size)
+{
+    range->lob = lob;
+    range->upb = lob + size - 1;
+    range_invariant(range);

include/qemu/range.h static inline uint64_t range_upb(Range *range) · line 133

Quoted 10 lines

include/qemu/range.h +10 -0

+}
+
+/*
+ * Check if the interval [@lob,@lob + @size - 1] would be valid or not
+ * (result in an overflow).
+ */
+static inline bool range_valid(uint64_t lob, uint64_t size)
+{
+    return lob + size >= lob;
+}

That name confused me, I'd expected that to have taken a range and check it for something (like a non-asserting version of the invariant).

Quoted 6 lines

Quoted 3 lines

Then we have to remove all the variant asserts from the initializer functions (well, because then it is no longer an invariant then). Other ideas?

My worry here is just the name 'range_valid'.

hmm "range_would_overflow()" ?

Quoted 1 line

Dave

Signature · 3 lines

Thanks,

David / dhildenb

Quoted 50 lines · * David Hildenbrand ([email protected]) wrote:

Quoted 49 lines · Dr. David Alan Gilbert

Quoted 48 lines · * David Hildenbrand ([email protected]) wrote:

Quoted 46 lines · Dr. David Alan Gilbert

Quoted 32 lines · * David Hildenbrand ([email protected]) wrote:

Add some more functions that will be used in memory-device context.

range_init(): Init using lower bound and size range_valid(): Check if there would be an overflow when initializin range_size(): Extract the size of a range range_overlaps_range(): Check for overlaps of two ranges range_contains_range(): Check if one range is contained in the other range_starts_before_range(): Check if one range starts before another range_ends_after_range(): Check if one range ends after another

Signed-off-by David Hildenbrand <[email protected]>

---
 include/qemu/range.h | 80 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)

include/qemu/range.h +9 -0

index 7e75f4e655..18e8acf22f 100644
@@ -112,6 +112,86 @@ static inline uint64_t range_upb(Range *range)
     return range->upb;
 }
 
+/*
+ * Initialize @range to span the interval [@lob,@lob + @size - 1].
+ * @size may be 0.
+ */
+static inline void range_init(Range *range, uint64_t lob, uint64_t size)
+{
+    range->lob = lob;
+    range->upb = lob + size - 1;
+    range_invariant(range);

include/qemu/range.h static inline uint64_t range_upb(Range *range) · line 133

Quoted 10 lines

include/qemu/range.h +10 -0

+}
+
+/*
+ * Check if the interval [@lob,@lob + @size - 1] would be valid or not
+ * (result in an overflow).
+ */
+static inline bool range_valid(uint64_t lob, uint64_t size)
+{
+    return lob + size >= lob;
+}

That name confused me, I'd expected that to have taken a range and check it for something (like a non-asserting version of the invariant).

Quoted 8 lines

Quoted 6 lines

Quoted 3 lines

Then we have to remove all the variant asserts from the initializer functions (well, because then it is no longer an invariant then). Other ideas?

My worry here is just the name 'range_valid'.

hmm "range_would_overflow()" ?

Yes, a bit long but OK.

But another observation; in the following patch, you're tending to do:

if (!range_valid(...))
moan

range_init(...)

would it make more sense to change range_init so it was:

static inline bool range_init(Range *range, uint64_t lob, uint64_t size)

{
    range->lob = lob;
    range->upb = lob + size - 1;
    return ob + size >= lob;
}

and then in the places you use it, you could do:

if (!range_init(...)
moan

Shorter and easier to read.

Signed-off-by David Hildenbrand <[email protected]>

---
 hw/mem/memory-device.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

hw/mem/memory-device.c +3 -3

index 7de1ccd497..996ad1490f 100644
@@ -120,7 +120,7 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,
     g_assert(address_space_end >= address_space_start);
 
     /* address_space_start indicates the maximum alignment we expect */
-    if (QEMU_ALIGN_UP(address_space_start, align) != address_space_start) {
+    if (!QEMU_IS_ALIGNED(address_space_start, align)) {
         error_setg(errp, "the alignment (0x%" PRIx64 ") is not supported",
                    align);
         return 0;

@@ -131,13 +131,13 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,
         return 0;
     }
 
-    if (hint && QEMU_ALIGN_UP(*hint, align) != *hint) {
+    if (hint && !QEMU_IS_ALIGNED(*hint, align)) {
         error_setg(errp, "address must be aligned to 0x%" PRIx64 " bytes",
                    align);
         return 0;
     }
 
-    if (QEMU_ALIGN_UP(size, align) != size) {
+    if (!QEMU_IS_ALIGNED(size, align)) {
         error_setg(errp, "backend memory size must be multiple of 0x%"
                    PRIx64, align);
         return 0;

Signature · 1 line

2.17.1

Let's rewrite it properly using ranges. This fixes certain overflows that are right now possible. E.g.

qemu-system-x86_64 -m 4G,slots=20,maxmem=40G -M pc \
    -object memory-backend-file,id=mem1,share,mem-path=/dev/zero,size=2G
    -device pc-dimm,memdev=mem1,id=dimm1,addr=-0x40000000

Now properly reports an error instead of succeeding.

"can't add memory device [0xffffffffc0000000:0x80000000], range overflow"

Signed-off-by David Hildenbrand <[email protected]>

---
 hw/mem/memory-device.c | 56 +++++++++++++++++++++++++-----------------
 1 file changed, 33 insertions(+), 23 deletions(-)

hw/mem/memory-device.c +10 -13

index 8be63c8032..1ca9c8e410 100644
@@ -100,9 +100,8 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,
                                             uint64_t align, uint64_t size,
                                             Error **errp)
 {
-    uint64_t address_space_start, address_space_end;
     GSList *list = NULL, *item;
-    uint64_t new_addr = 0;
+    Range as, new = range_empty;
 
     if (!ms->device_memory) {
         error_setg(errp, "memory devices (e.g. for memory hotplug) are not "

@@ -115,13 +114,11 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,
                          "enabled, please specify the maxmem option");
         return 0;
     }
-    address_space_start = ms->device_memory->base;
-    address_space_end = address_space_start +
-                        memory_region_size(&ms->device_memory->mr);
-    g_assert(address_space_end >= address_space_start);
+    range_init(&as, ms->device_memory->base,
+               memory_region_size(&ms->device_memory->mr));
 
-    /* address_space_start indicates the maximum alignment we expect */
-    if (!QEMU_IS_ALIGNED(address_space_start, align)) {
+    /* start of address space indicates the maximum alignment we expect */
+    if (!QEMU_IS_ALIGNED(range_lob(&as), align)) {
         error_setg(errp, "the alignment (0x%" PRIx64 ") is not supported",
                    align);
         return 0;

@@ -145,20 +142,26 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,
     }
 
     if (hint) {
-        new_addr = *hint;
-        if (new_addr < address_space_start) {
+        if (!range_valid(*hint, size)) {
             error_setg(errp, "can't add memory device [0x%" PRIx64 ":0x%" PRIx64
-                       "] before 0x%" PRIx64, new_addr, size,
-                       address_space_start);
+                       "], range overflow", *hint, size);
             return 0;
-        } else if ((new_addr + size) > address_space_end) {
+        }
+        range_init(&new, *hint, size);
+        if (range_starts_before_range(&new, &as)) {

hw/mem/memory-device.c +15 -7

+        range_init(&new, range_lob(&as), size);
     }
 
     /* find address range that will fit new memory device */

@@ -166,30 +169,37 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,
     for (item = list; item; item = g_slist_next(item)) {
         const MemoryDeviceState *md = item->data;
         const MemoryDeviceClass *mdc = MEMORY_DEVICE_GET_CLASS(OBJECT(md));
-        uint64_t md_size, md_addr;
+        uint64_t next_addr;
+        Range tmp;
 
-        md_addr = mdc->get_addr(md);
-        md_size = memory_device_get_region_size(md, &error_abort);
+        range_init(&tmp, mdc->get_addr(md),
+                   memory_device_get_region_size(md, &error_abort));
 
-        if (ranges_overlap(md_addr, md_size, new_addr, size)) {
+        if (range_overlaps_range(&tmp, &new)) {
             if (hint) {
                 const DeviceState *d = DEVICE(md);
                 error_setg(errp, "address range conflicts with memory device"
                            " id='%s'", d->id ? d->id : "(unnamed)");
                 goto out;
             }
-            new_addr = QEMU_ALIGN_UP(md_addr + md_size, align);
+
+            next_addr = QEMU_ALIGN_UP(range_upb(&tmp) + 1, align);
+            if (!range_valid(next_addr, size)) {
+                range_make_empty(&new);
+                break;
+            }
+            range_init(&new, next_addr, size);
         }
     }
 
-    if (new_addr + size > address_space_end) {
+    if (!range_contains_range(&as, &new)) {
         error_setg(errp, "could not find position in guest address space for "
                    "memory device - memory fragmented due to alignments");
         goto out;
     }
 out:
     g_slist_free(list);
-    return new_addr;
+    return range_lob(&new);
 }
 
 MemoryDeviceInfoList *qmp_memory_device_list(void)

Signature · 1 line

2.17.1

Quoted 13 lines

     if (hint) {

hw/mem/memory-device.c +5 -5

-        new_addr = *hint;
-        if (new_addr < address_space_start) {
+        if (!range_valid(*hint, size)) {
             error_setg(errp, "can't add memory device [0x%" PRIx64 ":0x%" PRIx64
-                       "] before 0x%" PRIx64, new_addr, size,
-                       address_space_start);
+                       "], range overflow", *hint, size);
             return 0;
-        } else if ((new_addr + size) > address_space_end) {
+        }
+        range_init(&new, *hint, size);
+        if (range_starts_before_range(&new, &as)) {

hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 159

Quoted 10 lines

hw/mem/memory-device.c +7 -2

+            error_setg(errp, "can't add memory device [0x%" PRIx64 ":0x%" PRIx64
+                       "] before 0x%" PRIx64, range_lob(&new), range_size(&new),
+                       range_lob(&as));
+            return 0;
+        } else if (range_ends_after_range(&new, &as)) {
             error_setg(errp, "can't add memory device [0x%" PRIx64 ":0x%" PRIx64
-                       "] beyond 0x%" PRIx64, new_addr, size,
-                       address_space_end);
+                       "] beyond 0x%" PRIx64, range_lob(&new), range_size(&new),
+                       range_upb(&as));

Would !range_contains_range be easier here?

hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 163

Quoted 6 lines

             return 0;
         }
     } else {

hw/mem/memory-device.c +1 -1

-        new_addr = address_space_start;
+        /* our previous size checks make sure that this never overflows */

Hmm, which one exactly?

Quoted 3 lines

+        range_init(&new, range_lob(&as), size);
     }