[Qemu-devel] [PATCH RFC 0/4] range: Make it simpler & safer

[Qemu-devel] [PATCH RFC 0/4] range: Make it simpler & safer

[Markus Armbruster]

This is an RFC because PATCH 2 adds hackery we might not want to
commit, and PATCH 3 takes it out again.

Prerequisites:
* [PATCH 0/3] log: Fix error handling and a memory leak
* [PATCH 0/2] Clean up around the PCI holes
* [PATCH v2 0/3] Fix leak in handling of integer lists as strings

Markus Armbruster (4):
  log: Clean up misuse of Range for -dfilter
  range: Eliminate direct Range member access
  range: Drop the previous commit's trickery
  range: Replace internal representation of Range

 hw/i386/acpi-build.c         |  35 ++++++++-------
 hw/pci-host/piix.c           |  26 +++++++----
 hw/pci-host/q35.c            |  41 +++++++++++------
 hw/pci/pci.c                 |  17 ++++----
 include/qemu/range.h         | 102 ++++++++++++++++++++++++++++++++++++++-----
 qapi/string-input-visitor.c  |  20 ++++-----
 qapi/string-output-visitor.c |  18 ++++----
 tests/test-logging.c         |  10 +++++
 util/log.c                   |  27 ++++++------
 util/range.c                 |  16 ++-----
 10 files changed, 208 insertions(+), 104 deletions(-)

-- 
2.5.5

[Qemu-devel] [PATCH RFC 1/4] log: Clean up misuse of Range for -dfilter

[Markus Armbruster]

Range encodes an integer interval [a,b] as { begin = a, end = b + 1 },
where a \in [0,2^64-1] and b \in [1,2^64].  Thus, zero end is to be
interpreted as 2^64.

The implementation of -dfilter (commit 3514552) uses Range
differently: it encodes [a,b] as { begin = a, end = b }.  The code
works, but it contradicts the specification of Range in range.h.

Switch to the specified representation.  Since it can't represent
[0,UINT64_MAX], we have to reject that now.  Add a test for it.

While we're rejecting anyway: observe that we reject -dfilter LOB..UPB
where LOB > UPB when UPB is zero, but happily create an empty Range
when it isn't.  Reject it then, too, and add a test for it.

While there, add a positive test for the problematic upper bound
UINT64_MAX.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 tests/test-logging.c | 10 ++++++++++
 util/log.c           | 28 +++++++++++++++-------------
 2 files changed, 25 insertions(+), 13 deletions(-)

diff --git a/tests/test-logging.c b/tests/test-logging.c
index 440e75f..b6fa94e 100644
--- a/tests/test-logging.c
+++ b/tests/test-logging.c
@@ -68,6 +68,16 @@ static void test_parse_range(void)
     g_assert(qemu_log_in_addr_range(0x2050));
     g_assert(qemu_log_in_addr_range(0x3050));
 
+    qemu_set_dfilter_ranges("0xffffffffffffffff-1", &error_abort);
+    g_assert(qemu_log_in_addr_range(UINT64_MAX));
+    g_assert_false(qemu_log_in_addr_range(UINT64_MAX - 1));
+
+    qemu_set_dfilter_ranges("0..0xffffffffffffffff", &err);
+    error_free_or_abort(&err);
+
+    qemu_set_dfilter_ranges("2..1", &err);
+    error_free_or_abort(&err);
+
     qemu_set_dfilter_ranges("0x1000+onehundred", &err);
     error_free_or_abort(&err);
 
diff --git a/util/log.c b/util/log.c
index 32e4160..f811d61 100644
--- a/util/log.c
+++ b/util/log.c
@@ -131,8 +131,8 @@ bool qemu_log_in_addr_range(uint64_t addr)
     if (debug_regions) {
         int i = 0;
         for (i = 0; i < debug_regions->len; i++) {
-            struct Range *range = &g_array_index(debug_regions, Range, i);
-            if (addr >= range->begin && addr <= range->end) {
+            Range *range = &g_array_index(debug_regions, Range, i);
+            if (addr >= range->begin && addr <= range->end - 1) {
                 return true;
             }
         }
@@ -158,7 +158,7 @@ void qemu_set_dfilter_ranges(const char *filter_spec, Error **errp)
     for (i = 0; ranges[i]; i++) {
         const char *r = ranges[i];
         const char *range_op, *r2, *e;
-        uint64_t r1val, r2val;
+        uint64_t r1val, r2val, lob, upb;
         struct Range range;
 
         range_op = strstr(r, "-");
@@ -187,27 +187,29 @@ void qemu_set_dfilter_ranges(const char *filter_spec, Error **errp)
                        (int)(r2 - range_op), range_op);
             goto out;
         }
-        if (r2val == 0) {
-            error_setg(errp, "Invalid range");
-            goto out;
-        }
 
         switch (*range_op) {
         case '+':
-            range.begin = r1val;
-            range.end = r1val + (r2val - 1);
+            lob = r1val;
+            upb = r1val + r2val - 1;
             break;
         case '-':
-            range.end = r1val;
-            range.begin = r1val - (r2val - 1);
+            upb = r1val;
+            lob = r1val - (r2val - 1);
             break;
         case '.':
-            range.begin = r1val;
-            range.end = r2val;
+            lob = r1val;
+            upb = r2val;
             break;
         default:
             g_assert_not_reached();
         }
+        if (lob > upb || (lob == 0 && upb == UINT64_MAX)) {
+            error_setg(errp, "Invalid range");
+            goto out;
+        }
+        range.begin = lob;
+        range.end = upb + 1;
         g_array_append_val(debug_regions, range);
     }
 out:
-- 
2.5.5

[Qemu-devel] [PATCH RFC 2/4] range: Eliminate direct Range member access

[Markus Armbruster]

Users of struct Range mess liberally with its members, which makes
refactoring hard.  Create a set of methods, and convert all users to
call them instead of accessing members.  The methods have carefully
worded contracts, and use assertions to check them.

To help with tracking down the places that access members of struct
Range directly, hide the implementation of struct Range outside of
range.c by trickery.  The trickery will be dropped in the next commit.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 hw/i386/acpi-build.c         |  35 +++++++-------
 hw/pci-host/piix.c           |  26 +++++++----
 hw/pci-host/q35.c            |  41 +++++++++++------
 hw/pci/pci.c                 |  17 +++----
 include/qemu/range.h         | 106 ++++++++++++++++++++++++++++++++++++++++++-
 qapi/string-input-visitor.c  |  20 ++++----
 qapi/string-output-visitor.c |  18 ++++----
 util/log.c                   |   5 +-
 util/range.c                 |   4 +-
 9 files changed, 198 insertions(+), 74 deletions(-)

diff --git a/hw/i386/acpi-build.c b/hw/i386/acpi-build.c
index 02fc534..6c36c24 100644
--- a/hw/i386/acpi-build.c
+++ b/hw/i386/acpi-build.c
@@ -232,18 +232,20 @@ static void acpi_get_pci_holes(Range *hole, Range *hole64)
     pci_host = acpi_get_i386_pci_host();
     g_assert(pci_host);
 
-    hole->begin = object_property_get_int(pci_host,
-                                          PCI_HOST_PROP_PCI_HOLE_START,
-                                          NULL);
-    hole->end = object_property_get_int(pci_host,
-                                        PCI_HOST_PROP_PCI_HOLE_END,
-                                        NULL);
-    hole64->begin = object_property_get_int(pci_host,
-                                            PCI_HOST_PROP_PCI_HOLE64_START,
-                                            NULL);
-    hole64->end = object_property_get_int(pci_host,
-                                          PCI_HOST_PROP_PCI_HOLE64_END,
-                                          NULL);
+    range_set_bounds1(hole,
+                      object_property_get_int(pci_host,
+                                              PCI_HOST_PROP_PCI_HOLE_START,
+                                              NULL),
+                      object_property_get_int(pci_host,
+                                              PCI_HOST_PROP_PCI_HOLE_END,
+                                              NULL));
+    range_set_bounds1(hole64,
+                      object_property_get_int(pci_host,
+                                              PCI_HOST_PROP_PCI_HOLE64_START,
+                                              NULL),
+                      object_property_get_int(pci_host,
+                                              PCI_HOST_PROP_PCI_HOLE64_END,
+                                              NULL));
 }
 
 #define ACPI_PORT_SMI_CMD           0x00b2 /* TODO: this is APM_CNT_IOPORT */
@@ -2015,7 +2017,8 @@ build_dsdt(GArray *table_data, BIOSLinker *linker,
                          0, 0x000A0000, 0x000BFFFF, 0, 0x00020000));
 
     crs_replace_with_free_ranges(mem_ranges,
-                                 pci_hole->begin, pci_hole->end - 1);
+                                 range_lob(pci_hole),
+                                 range_upb(pci_hole));
     for (i = 0; i < mem_ranges->len; i++) {
         entry = g_ptr_array_index(mem_ranges, i);
         aml_append(crs,
@@ -2025,12 +2028,12 @@ build_dsdt(GArray *table_data, BIOSLinker *linker,
                              0, entry->limit - entry->base + 1));
     }
 
-    if (pci_hole64->begin) {
+    if (!range_is_empty(pci_hole64)) {
         aml_append(crs,
             aml_qword_memory(AML_POS_DECODE, AML_MIN_FIXED, AML_MAX_FIXED,
                              AML_CACHEABLE, AML_READ_WRITE,
-                             0, pci_hole64->begin, pci_hole64->end - 1, 0,
-                             pci_hole64->end - pci_hole64->begin));
+                             0, range_lob(pci_hole64), range_upb(pci_hole64), 0,
+                             range_upb(pci_hole64) + 1 - range_lob(pci_hole64)));
     }
 
     if (misc->tpm_version != TPM_VERSION_UNSPEC) {
diff --git a/hw/pci-host/piix.c b/hw/pci-host/piix.c
index 8db0f09..1df327f 100644
--- a/hw/pci-host/piix.c
+++ b/hw/pci-host/piix.c
@@ -221,8 +221,12 @@ static void i440fx_pcihost_get_pci_hole_start(Object *obj, Visitor *v,
                                               Error **errp)
 {
     I440FXState *s = I440FX_PCI_HOST_BRIDGE(obj);
-    uint32_t value = s->pci_hole.begin;
+    uint64_t val64;
+    uint32_t value;
 
+    val64 = range_is_empty(&s->pci_hole) ? 0 : range_lob(&s->pci_hole);
+    value = val64;
+    assert(value == val64);
     visit_type_uint32(v, name, &value, errp);
 }
 
@@ -231,8 +235,12 @@ static void i440fx_pcihost_get_pci_hole_end(Object *obj, Visitor *v,
                                             Error **errp)
 {
     I440FXState *s = I440FX_PCI_HOST_BRIDGE(obj);
-    uint32_t value = s->pci_hole.end;
+    uint64_t val64;
+    uint32_t value;
 
+    val64 = range_is_empty(&s->pci_hole) ? 0 : range_upb(&s->pci_hole) + 1;
+    value = val64;
+    assert(value == val64);
     visit_type_uint32(v, name, &value, errp);
 }
 
@@ -242,10 +250,11 @@ static void i440fx_pcihost_get_pci_hole64_start(Object *obj, Visitor *v,
 {
     PCIHostState *h = PCI_HOST_BRIDGE(obj);
     Range w64;
+    uint64_t value;
 
     pci_bus_get_w64_range(h->bus, &w64);
-
-    visit_type_uint64(v, name, &w64.begin, errp);
+    value = range_is_empty(&w64) ? 0 : range_lob(&w64);
+    visit_type_uint64(v, name, &value, errp);
 }
 
 static void i440fx_pcihost_get_pci_hole64_end(Object *obj, Visitor *v,
@@ -254,10 +263,11 @@ static void i440fx_pcihost_get_pci_hole64_end(Object *obj, Visitor *v,
 {
     PCIHostState *h = PCI_HOST_BRIDGE(obj);
     Range w64;
+    uint64_t value;
 
     pci_bus_get_w64_range(h->bus, &w64);
-
-    visit_type_uint64(v, name, &w64.end, errp);
+    value = range_is_empty(&w64) ? 0 : range_upb(&w64) + 1;
+    visit_type_uint64(v, name, &value, errp);
 }
 
 static void i440fx_pcihost_initfn(Object *obj)
@@ -344,8 +354,8 @@ PCIBus *i440fx_init(const char *host_type, const char *pci_type,
     f->ram_memory = ram_memory;
 
     i440fx = I440FX_PCI_HOST_BRIDGE(dev);
-    i440fx->pci_hole.begin = below_4g_mem_size;
-    i440fx->pci_hole.end = IO_APIC_DEFAULT_ADDRESS;
+    range_set_bounds(&i440fx->pci_hole, below_4g_mem_size,
+                     IO_APIC_DEFAULT_ADDRESS - 1);
 
     /* setup pci memory mapping */
     pc_pci_as_mapping_init(OBJECT(f), f->system_memory,
diff --git a/hw/pci-host/q35.c b/hw/pci-host/q35.c
index 8c2c1db..d200091 100644
--- a/hw/pci-host/q35.c
+++ b/hw/pci-host/q35.c
@@ -73,8 +73,13 @@ static void q35_host_get_pci_hole_start(Object *obj, Visitor *v,
                                         Error **errp)
 {
     Q35PCIHost *s = Q35_HOST_DEVICE(obj);
-    uint32_t value = s->mch.pci_hole.begin;
+    uint64_t val64;
+    uint32_t value;
 
+    val64 = range_is_empty(&s->mch.pci_hole)
+        ? 0 : range_lob(&s->mch.pci_hole);
+    value = val64;
+    assert(value == val64);
     visit_type_uint32(v, name, &value, errp);
 }
 
@@ -83,8 +88,13 @@ static void q35_host_get_pci_hole_end(Object *obj, Visitor *v,
                                       Error **errp)
 {
     Q35PCIHost *s = Q35_HOST_DEVICE(obj);
-    uint32_t value = s->mch.pci_hole.end;
+    uint64_t val64;
+    uint32_t value;
 
+    val64 = range_is_empty(&s->mch.pci_hole)
+        ? 0 : range_upb(&s->mch.pci_hole) + 1;
+    value = val64;
+    assert(value == val64);
     visit_type_uint32(v, name, &value, errp);
 }
 
@@ -94,10 +104,11 @@ static void q35_host_get_pci_hole64_start(Object *obj, Visitor *v,
 {
     PCIHostState *h = PCI_HOST_BRIDGE(obj);
     Range w64;
+    uint64_t value;
 
     pci_bus_get_w64_range(h->bus, &w64);
-
-    visit_type_uint64(v, name, &w64.begin, errp);
+    value = range_is_empty(&w64) ? 0 : range_lob(&w64);
+    visit_type_uint64(v, name, &value, errp);
 }
 
 static void q35_host_get_pci_hole64_end(Object *obj, Visitor *v,
@@ -106,10 +117,11 @@ static void q35_host_get_pci_hole64_end(Object *obj, Visitor *v,
 {
     PCIHostState *h = PCI_HOST_BRIDGE(obj);
     Range w64;
+    uint64_t value;
 
     pci_bus_get_w64_range(h->bus, &w64);
-
-    visit_type_uint64(v, name, &w64.end, errp);
+    value = range_is_empty(&w64) ? 0 : range_upb(&w64) + 1;
+    visit_type_uint64(v, name, &value, errp);
 }
 
 static void q35_host_get_mmcfg_size(Object *obj, Visitor *v, const char *name,
@@ -182,9 +194,9 @@ static void q35_host_initfn(Object *obj)
      * it's not a power of two, which means an MTRR
      * can't cover it exactly.
      */
-    s->mch.pci_hole.begin = MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT +
-        MCH_HOST_BRIDGE_PCIEXBAR_MAX;
-    s->mch.pci_hole.end = IO_APIC_DEFAULT_ADDRESS;
+    range_set_bounds(&s->mch.pci_hole,
+            MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT + MCH_HOST_BRIDGE_PCIEXBAR_MAX,
+            IO_APIC_DEFAULT_ADDRESS - 1);
 }
 
 static const TypeInfo q35_host_info = {
@@ -252,10 +264,7 @@ static void mch_update_pciexbar(MCHPCIState *mch)
         break;
     case MCH_HOST_BRIDGE_PCIEXBAR_LENGTH_RVD:
     default:
-        enable = 0;
-        length = 0;
         abort();
-        break;
     }
     addr = pciexbar & addr_mask;
     pcie_host_mmcfg_update(pehb, enable, addr, length);
@@ -265,9 +274,13 @@ static void mch_update_pciexbar(MCHPCIState *mch)
      * which means an MTRR can't cover it exactly.
      */
     if (enable) {
-        mch->pci_hole.begin = addr + length;
+        range_set_bounds(&mch->pci_hole,
+                         addr + length,
+                         IO_APIC_DEFAULT_ADDRESS - 1);
     } else {
-        mch->pci_hole.begin = MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT;
+        range_set_bounds(&mch->pci_hole,
+                         MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT,
+                         IO_APIC_DEFAULT_ADDRESS - 1);
     }
 }
 
diff --git a/hw/pci/pci.c b/hw/pci/pci.c
index bb605ef..904c6fd 100644
--- a/hw/pci/pci.c
+++ b/hw/pci/pci.c
@@ -2436,13 +2436,13 @@ static void pci_dev_get_w64(PCIBus *b, PCIDevice *dev, void *opaque)
 
         if (limit >= base) {
             Range pref_range;
-            pref_range.begin = base;
-            pref_range.end = limit + 1;
+            range_set_bounds(&pref_range, base, limit);
             range_extend(range, &pref_range);
         }
     }
     for (i = 0; i < PCI_NUM_REGIONS; ++i) {
         PCIIORegion *r = &dev->io_regions[i];
+        pcibus_t lob, upb;
         Range region_range;
 
         if (!r->size ||
@@ -2450,16 +2450,17 @@ static void pci_dev_get_w64(PCIBus *b, PCIDevice *dev, void *opaque)
             !(r->type & PCI_BASE_ADDRESS_MEM_TYPE_64)) {
             continue;
         }
-        region_range.begin = pci_bar_address(dev, i, r->type, r->size);
-        region_range.end = region_range.begin + r->size;
 
-        if (region_range.begin == PCI_BAR_UNMAPPED) {
+        lob = pci_bar_address(dev, i, r->type, r->size);
+        upb = lob + r->size - 1;
+        if (lob == PCI_BAR_UNMAPPED) {
             continue;
         }
 
-        region_range.begin = MAX(region_range.begin, 0x1ULL << 32);
+        lob = MAX(lob, 0x1ULL << 32);
 
-        if (region_range.end - 1 >= region_range.begin) {
+        if (upb >= lob) {
+            range_set_bounds(&region_range, lob, upb);
             range_extend(range, &region_range);
         }
     }
@@ -2467,7 +2468,7 @@ static void pci_dev_get_w64(PCIBus *b, PCIDevice *dev, void *opaque)
 
 void pci_bus_get_w64_range(PCIBus *bus, Range *range)
 {
-    range->begin = range->end = 0;
+    range_make_empty(range);
     pci_for_each_device_under_bus(bus, pci_dev_get_w64, range);
 }
 
diff --git a/include/qemu/range.h b/include/qemu/range.h
index 3970f00..9296ba0 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -30,18 +30,110 @@
  *   - this can not represent a full 0 to ~0x0LL range.
  */
 
+bool range_is_empty(Range *range);
+bool range_contains(Range *range, uint64_t val);
+void range_make_empty(Range *range);
+void range_set_bounds(Range *range, uint64_t lob, uint64_t upb);
+void range_set_bounds1(Range *range, uint64_t lob, uint64_t upb_plus1);
+uint64_t range_lob(Range *range);
+uint64_t range_upb(Range *range);
+void range_extend(Range *range, Range *extend_by);
+#ifdef RANGE_IMPL
+
 /* A structure representing a range of addresses. */
 struct Range {
     uint64_t begin; /* First byte of the range, or 0 if empty. */
     uint64_t end;   /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
 };
 
+static inline void range_invariant(Range *range)
+{
+    assert((!range->begin && !range->end) /* empty */
+           || range->begin <= range->end - 1); /* non-empty */
+}
+
+#define static
+#define inline
+
+/* Compound literal encoding the empty range */
+#define range_empty ((Range){ .begin = 0, .end = 0 })
+
+/* Is @range empty? */
+static inline bool range_is_empty(Range *range)
+{
+    range_invariant(range);
+    return !range->begin && !range->end;
+}
+
+/* Does @range contain @val? */
+static inline bool range_contains(Range *range, uint64_t val)
+{
+    return !range_is_empty(range)
+        && val >= range->begin && val <= range->end - 1;
+}
+
+/* Initialize @range to the empty range */
+static inline void range_make_empty(Range *range)
+{
+    *range = range_empty;
+    assert(range_is_empty(range));
+}
+
+/*
+ * Initialize @range to span the interval [@lob,@upb].
+ * Both bounds are inclusive.
+ * The interval must not be empty, i.e. @lob must be less than or
+ * equal @upb.
+ * The interval must not be [0,UINT64_MAX], because Range can't
+ * represent that.
+ */
+static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
+{
+    assert(lob <= upb);
+    range->begin = lob;
+    range->end = upb + 1;       /* may wrap to zero, that's okay */
+    assert(!range_is_empty(range));
+}
+
+/*
+ * Initialize @range to span the interval [@lob,@upb_plus1).
+ * The lower bound is inclusive, the upper bound is exclusive.
+ * Zero @upb_plus1 is special: if @lob is also zero, set @range to the
+ * empty range.  Else, set @range to [@lob,UINT64_MAX].
+ */
+static inline void range_set_bounds1(Range *range,
+                                     uint64_t lob, uint64_t upb_plus1)
+{
+    range->begin = lob;
+    range->end = upb_plus1;
+    range_invariant(range);
+}
+
+/* Return @range's lower bound.  @range must not be empty. */
+static inline uint64_t range_lob(Range *range)
+{
+    assert(!range_is_empty(range));
+    return range->begin;
+}
+
+/* Return @range's upper bound.  @range must not be empty. */
+static inline uint64_t range_upb(Range *range)
+{
+    assert(!range_is_empty(range));
+    return range->end - 1;
+}
+
+/*
+ * Extend @range to the smallest interval that includes @extend_by, too.
+ * This must not extend @range to cover the interval [0,UINT64_MAX],
+ * because Range can't represent that.
+ */
 static inline void range_extend(Range *range, Range *extend_by)
 {
-    if (!extend_by->begin && !extend_by->end) {
+    if (range_is_empty(extend_by)) {
         return;
     }
-    if (!range->begin && !range->end) {
+    if (range_is_empty(range)) {
         *range = *extend_by;
         return;
     }
@@ -52,8 +144,18 @@ static inline void range_extend(Range *range, Range *extend_by)
     if (range->end - 1 < extend_by->end - 1) {
         range->end = extend_by->end;
     }
+    /* Must not extend to { .begin = 0, .end = 0 }: */
+    assert(!range_is_empty(range));
 }
 
+#undef static
+#undef inline
+#else
+struct Range {
+    uint64_t begin_, end_;
+};
+#endif
+
 /* Get last byte of a range from offset + length.
  * Undefined for ranges that wrap around 0. */
 static inline uint64_t range_get_last(uint64_t offset, uint64_t len)
diff --git a/qapi/string-input-visitor.c b/qapi/string-input-visitor.c
index b546e5f..0690abb 100644
--- a/qapi/string-input-visitor.c
+++ b/qapi/string-input-visitor.c
@@ -59,8 +59,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
         if (errno == 0 && endptr > str) {
             if (*endptr == '\0') {
                 cur = g_malloc0(sizeof(*cur));
-                cur->begin = start;
-                cur->end = start + 1;
+                range_set_bounds(cur, start, start);
                 siv->ranges = range_list_insert(siv->ranges, cur);
                 cur = NULL;
                 str = NULL;
@@ -73,16 +72,14 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
                      end < start + 65536)) {
                     if (*endptr == '\0') {
                         cur = g_malloc0(sizeof(*cur));
-                        cur->begin = start;
-                        cur->end = end + 1;
+                        range_set_bounds(cur, start, end);
                         siv->ranges = range_list_insert(siv->ranges, cur);
                         cur = NULL;
                         str = NULL;
                     } else if (*endptr == ',') {
                         str = endptr + 1;
                         cur = g_malloc0(sizeof(*cur));
-                        cur->begin = start;
-                        cur->end = end + 1;
+                        range_set_bounds(cur, start, end);
                         siv->ranges = range_list_insert(siv->ranges, cur);
                         cur = NULL;
                     } else {
@@ -94,8 +91,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
             } else if (*endptr == ',') {
                 str = endptr + 1;
                 cur = g_malloc0(sizeof(*cur));
-                cur->begin = start;
-                cur->end = start + 1;
+                range_set_bounds(cur, start, start);
                 siv->ranges = range_list_insert(siv->ranges, cur);
                 cur = NULL;
             } else {
@@ -134,7 +130,7 @@ start_list(Visitor *v, const char *name, GenericList **list, size_t size,
     if (siv->cur_range) {
         Range *r = siv->cur_range->data;
         if (r) {
-            siv->cur = r->begin;
+            siv->cur = range_lob(r);
         }
         *list = g_malloc0(size);
     } else {
@@ -156,7 +152,7 @@ static GenericList *next_list(Visitor *v, GenericList *tail, size_t size)
         return NULL;
     }
 
-    if (siv->cur < r->begin || siv->cur >= r->end) {
+    if (!range_contains(r, siv->cur)) {
         siv->cur_range = g_list_next(siv->cur_range);
         if (!siv->cur_range) {
             return NULL;
@@ -165,7 +161,7 @@ static GenericList *next_list(Visitor *v, GenericList *tail, size_t size)
         if (!r) {
             return NULL;
         }
-        siv->cur = r->begin;
+        siv->cur = range_lob(r);
     }
 
     tail->next = g_malloc0(size);
@@ -208,7 +204,7 @@ static void parse_type_int64(Visitor *v, const char *name, int64_t *obj,
             goto error;
         }
 
-        siv->cur = r->begin;
+        siv->cur = range_lob(r);
     }
 
     *obj = siv->cur;
diff --git a/qapi/string-output-visitor.c b/qapi/string-output-visitor.c
index 5ea395a..c6f01f9 100644
--- a/qapi/string-output-visitor.c
+++ b/qapi/string-output-visitor.c
@@ -83,8 +83,8 @@ static void string_output_set(StringOutputVisitor *sov, char *string)
 static void string_output_append(StringOutputVisitor *sov, int64_t a)
 {
     Range *r = g_malloc0(sizeof(*r));
-    r->begin = a;
-    r->end = a + 1;
+
+    range_set_bounds(r, a, a);
     sov->ranges = range_list_insert(sov->ranges, r);
 }
 
@@ -92,28 +92,28 @@ static void string_output_append_range(StringOutputVisitor *sov,
                                        int64_t s, int64_t e)
 {
     Range *r = g_malloc0(sizeof(*r));
-    r->begin = s;
-    r->end = e + 1;
+
+    range_set_bounds(r, s, e);
     sov->ranges = range_list_insert(sov->ranges, r);
 }
 
 static void format_string(StringOutputVisitor *sov, Range *r, bool next,
                           bool human)
 {
-    if (r->end - r->begin > 1) {
+    if (range_lob(r) != range_upb(r)) {
         if (human) {
             g_string_append_printf(sov->string, "0x%" PRIx64 "-0x%" PRIx64,
-                                   r->begin, r->end - 1);
+                                   range_lob(r), range_upb(r));
 
         } else {
             g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64,
-                                   r->begin, r->end - 1);
+                                   range_lob(r), range_upb(r));
         }
     } else {
         if (human) {
-            g_string_append_printf(sov->string, "0x%" PRIx64, r->begin);
+            g_string_append_printf(sov->string, "0x%" PRIx64, range_lob(r));
         } else {
-            g_string_append_printf(sov->string, "%" PRId64, r->begin);
+            g_string_append_printf(sov->string, "%" PRId64, range_lob(r));
         }
     }
     if (next) {
diff --git a/util/log.c b/util/log.c
index f811d61..4da635c 100644
--- a/util/log.c
+++ b/util/log.c
@@ -132,7 +132,7 @@ bool qemu_log_in_addr_range(uint64_t addr)
         int i = 0;
         for (i = 0; i < debug_regions->len; i++) {
             Range *range = &g_array_index(debug_regions, Range, i);
-            if (addr >= range->begin && addr <= range->end - 1) {
+            if (range_contains(range, addr)) {
                 return true;
             }
         }
@@ -208,8 +208,7 @@ void qemu_set_dfilter_ranges(const char *filter_spec, Error **errp)
             error_setg(errp, "Invalid range");
             goto out;
         }
-        range.begin = lob;
-        range.end = upb + 1;
+        range_set_bounds(&range, lob, upb);
         g_array_append_val(debug_regions, range);
     }
 out:
diff --git a/util/range.c b/util/range.c
index 56e6baf..ab5102a 100644
--- a/util/range.c
+++ b/util/range.c
@@ -19,6 +19,7 @@
  */
 
 #include "qemu/osdep.h"
+#define RANGE_IMPL
 #include "qemu/range.h"
 
 /*
@@ -46,8 +47,7 @@ GList *range_list_insert(GList *list, Range *data)
 {
     GList *l;
 
-    /* Range lists require no empty ranges */
-    assert(data->begin < data->end || (data->begin && !data->end));
+    assert(!range_is_empty(data));
 
     for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
         /* Skip all list elements strictly less than data */
-- 
2.5.5

[Qemu-devel] [PATCH RFC 3/4] range: Drop the previous commit's trickery

[Markus Armbruster]

Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 include/qemu/range.h | 21 ---------------------
 util/range.c         |  1 -
 2 files changed, 22 deletions(-)

diff --git a/include/qemu/range.h b/include/qemu/range.h
index 9296ba0..c8c46a9 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -30,16 +30,6 @@
  *   - this can not represent a full 0 to ~0x0LL range.
  */
 
-bool range_is_empty(Range *range);
-bool range_contains(Range *range, uint64_t val);
-void range_make_empty(Range *range);
-void range_set_bounds(Range *range, uint64_t lob, uint64_t upb);
-void range_set_bounds1(Range *range, uint64_t lob, uint64_t upb_plus1);
-uint64_t range_lob(Range *range);
-uint64_t range_upb(Range *range);
-void range_extend(Range *range, Range *extend_by);
-#ifdef RANGE_IMPL
-
 /* A structure representing a range of addresses. */
 struct Range {
     uint64_t begin; /* First byte of the range, or 0 if empty. */
@@ -52,9 +42,6 @@ static inline void range_invariant(Range *range)
            || range->begin <= range->end - 1); /* non-empty */
 }
 
-#define static
-#define inline
-
 /* Compound literal encoding the empty range */
 #define range_empty ((Range){ .begin = 0, .end = 0 })
 
@@ -148,14 +135,6 @@ static inline void range_extend(Range *range, Range *extend_by)
     assert(!range_is_empty(range));
 }
 
-#undef static
-#undef inline
-#else
-struct Range {
-    uint64_t begin_, end_;
-};
-#endif
-
 /* Get last byte of a range from offset + length.
  * Undefined for ranges that wrap around 0. */
 static inline uint64_t range_get_last(uint64_t offset, uint64_t len)
diff --git a/util/range.c b/util/range.c
index ab5102a..ca149a0 100644
--- a/util/range.c
+++ b/util/range.c
@@ -19,7 +19,6 @@
  */
 
 #include "qemu/osdep.h"
-#define RANGE_IMPL
 #include "qemu/range.h"
 
 /*
-- 
2.5.5

[Qemu-devel] [PATCH RFC 4/4] range: Replace internal representation of Range

[Markus Armbruster]

Range represents a range as follows.  Member @start is the inclusive
lower bound, member @end is the exclusive upper bound.  Zero @end is
special: if @start is also zero, the range is empty, else @end is to
be interpreted as 2^64.  No other empty ranges may occur.

The range [0,2^64-1] cannot be represented.  If you try to create it
with range_set_bounds1(), you get the empty range instead.  If you try
to create it with range_set_bounds() or range_extend(), assertions
fail.  Before range_set_bounds() existed, the open-coded creation
usually got you the empty range instead.  Open deathtrap.

Moreover, the code dealing with the janus-faced @end is too clever by
half.

Dumb this down to a more pedestrian representation: members @lob and
@upb are inclusive lower and upper bounds.  The empty range is encoded
as @lob = 1, @upb = 0.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 include/qemu/range.h | 55 +++++++++++++++++++++++++---------------------------
 util/range.c         | 13 +++----------
 2 files changed, 29 insertions(+), 39 deletions(-)

diff --git a/include/qemu/range.h b/include/qemu/range.h
index c8c46a9..06ff361 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -26,37 +26,37 @@
 /*
  * Operations on 64 bit address ranges.
  * Notes:
- *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
- *   - this can not represent a full 0 to ~0x0LL range.
+ * - Ranges must not wrap around 0, but can include UINT64_MAX.
  */
 
-/* A structure representing a range of addresses. */
 struct Range {
-    uint64_t begin; /* First byte of the range, or 0 if empty. */
-    uint64_t end;   /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
+    /*
+     * A non-empty range has @lob <= @upb.
+     * An empty range has @lob == @upb + 1.
+     */
+    uint64_t lob;        /* inclusive lower bound */
+    uint64_t upb;        /* inclusive upper bound */
 };
 
 static inline void range_invariant(Range *range)
 {
-    assert((!range->begin && !range->end) /* empty */
-           || range->begin <= range->end - 1); /* non-empty */
+    assert(range->lob <= range->upb || range->lob == range->upb + 1);
 }
 
 /* Compound literal encoding the empty range */
-#define range_empty ((Range){ .begin = 0, .end = 0 })
+#define range_empty ((Range){ .lob = 1, .upb = 0 })
 
 /* Is @range empty? */
 static inline bool range_is_empty(Range *range)
 {
     range_invariant(range);
-    return !range->begin && !range->end;
+    return range->lob > range->upb;
 }
 
 /* Does @range contain @val? */
 static inline bool range_contains(Range *range, uint64_t val)
 {
-    return !range_is_empty(range)
-        && val >= range->begin && val <= range->end - 1;
+    return val >= range->lob && val <= range->upb;
 }
 
 /* Initialize @range to the empty range */
@@ -71,14 +71,11 @@ static inline void range_make_empty(Range *range)
  * Both bounds are inclusive.
  * The interval must not be empty, i.e. @lob must be less than or
  * equal @upb.
- * The interval must not be [0,UINT64_MAX], because Range can't
- * represent that.
  */
 static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
 {
-    assert(lob <= upb);
-    range->begin = lob;
-    range->end = upb + 1;       /* may wrap to zero, that's okay */
+    range->lob = lob;
+    range->upb = upb;
     assert(!range_is_empty(range));
 }
 
@@ -91,8 +88,12 @@ static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
 static inline void range_set_bounds1(Range *range,
                                      uint64_t lob, uint64_t upb_plus1)
 {
-    range->begin = lob;
-    range->end = upb_plus1;
+    if (!lob && !upb_plus1) {
+        *range = range_empty;
+    } else {
+        range->lob = lob;
+        range->upb = upb_plus1 - 1;
+    }
     range_invariant(range);
 }
 
@@ -100,20 +101,18 @@ static inline void range_set_bounds1(Range *range,
 static inline uint64_t range_lob(Range *range)
 {
     assert(!range_is_empty(range));
-    return range->begin;
+    return range->lob;
 }
 
 /* Return @range's upper bound.  @range must not be empty. */
 static inline uint64_t range_upb(Range *range)
 {
     assert(!range_is_empty(range));
-    return range->end - 1;
+    return range->upb;
 }
 
 /*
  * Extend @range to the smallest interval that includes @extend_by, too.
- * This must not extend @range to cover the interval [0,UINT64_MAX],
- * because Range can't represent that.
  */
 static inline void range_extend(Range *range, Range *extend_by)
 {
@@ -124,15 +123,13 @@ static inline void range_extend(Range *range, Range *extend_by)
         *range = *extend_by;
         return;
     }
-    if (range->begin > extend_by->begin) {
-        range->begin = extend_by->begin;
+    if (range->lob > extend_by->lob) {
+        range->lob = extend_by->lob;
     }
-    /* Compare last byte in case region ends at ~0x0LL */
-    if (range->end - 1 < extend_by->end - 1) {
-        range->end = extend_by->end;
+    if (range->upb < extend_by->upb) {
+        range->upb = extend_by->upb;
     }
-    /* Must not extend to { .begin = 0, .end = 0 }: */
-    assert(!range_is_empty(range));
+    range_invariant(range);
 }
 
 /* Get last byte of a range from offset + length.
diff --git a/util/range.c b/util/range.c
index ca149a0..8359066 100644
--- a/util/range.c
+++ b/util/range.c
@@ -21,21 +21,14 @@
 #include "qemu/osdep.h"
 #include "qemu/range.h"
 
-/*
- * Operations on 64 bit address ranges.
- * Notes:
- *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
- *   - this can not represent a full 0 to ~0x0LL range.
- */
-
 /* Return -1 if @a < @b, 1 if greater, and 0 if they touch or overlap. */
 static inline int range_compare(Range *a, Range *b)
 {
-    /* Zero a->end is 2**64, and therefore not less than any b->begin */
-    if (a->end && a->end < b->begin) {
+    /* Careful, avoid wraparound */
+    if (b->lob && b->lob - 1 > a->upb) {
         return -1;
     }
-    if (b->end && a->begin > b->end) {
+    if (a->lob && a->lob - 1 > b->upb) {
         return 1;
     }
     return 0;
-- 
2.5.5

Re: [Qemu-devel] [PATCH RFC 1/4] log: Clean up misuse of Range for -dfilter

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1246 bytes --]

On 06/15/2016 02:41 PM, Markus Armbruster wrote:
> Range encodes an integer interval [a,b] as { begin = a, end = b + 1 },
> where a \in [0,2^64-1] and b \in [1,2^64].  Thus, zero end is to be
> interpreted as 2^64.
> 
> The implementation of -dfilter (commit 3514552) uses Range
> differently: it encodes [a,b] as { begin = a, end = b }.  The code
> works, but it contradicts the specification of Range in range.h.
> 
> Switch to the specified representation.  Since it can't represent
> [0,UINT64_MAX], we have to reject that now.  Add a test for it.
> 
> While we're rejecting anyway: observe that we reject -dfilter LOB..UPB
> where LOB > UPB when UPB is zero, but happily create an empty Range
> when it isn't.  Reject it then, too, and add a test for it.
> 
> While there, add a positive test for the problematic upper bound
> UINT64_MAX.
> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  tests/test-logging.c | 10 ++++++++++
>  util/log.c           | 28 +++++++++++++++-------------
>  2 files changed, 25 insertions(+), 13 deletions(-)
> 

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH RFC 2/4] range: Eliminate direct Range member access

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 2675 bytes --]

On 06/15/2016 02:41 PM, Markus Armbruster wrote:
> Users of struct Range mess liberally with its members, which makes
> refactoring hard.  Create a set of methods, and convert all users to
> call them instead of accessing members.  The methods have carefully
> worded contracts, and use assertions to check them.
> 
> To help with tracking down the places that access members of struct
> Range directly, hide the implementation of struct Range outside of
> range.c by trickery.  The trickery will be dropped in the next commit.

Can't we just make Range an opaque type, and move its definition into
range.c?  Oh, except we have inline functions that would no longer be
inline, unless we also had a range-impl.h private header.

> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---


> @@ -2015,7 +2017,8 @@ build_dsdt(GArray *table_data, BIOSLinker *linker,
>                           0, 0x000A0000, 0x000BFFFF, 0, 0x00020000));
>  
>      crs_replace_with_free_ranges(mem_ranges,
> -                                 pci_hole->begin, pci_hole->end - 1);
> +                                 range_lob(pci_hole),
> +                                 range_upb(pci_hole));

Changes like this are nice, isolating us from what the actual struct stores.


> +++ b/include/qemu/range.h
> @@ -30,18 +30,110 @@
>   *   - this can not represent a full 0 to ~0x0LL range.
>   */
>  
> +bool range_is_empty(Range *range);
> +bool range_contains(Range *range, uint64_t val);
> +void range_make_empty(Range *range);
> +void range_set_bounds(Range *range, uint64_t lob, uint64_t upb);
> +void range_set_bounds1(Range *range, uint64_t lob, uint64_t upb_plus1);
> +uint64_t range_lob(Range *range);
> +uint64_t range_upb(Range *range);
> +void range_extend(Range *range, Range *extend_by);
> +#ifdef RANGE_IMPL
> +
>  /* A structure representing a range of addresses. */
>  struct Range {
>      uint64_t begin; /* First byte of the range, or 0 if empty. */
>      uint64_t end;   /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
>  };
>  
> +static inline void range_invariant(Range *range)
> +{
> +    assert((!range->begin && !range->end) /* empty */
> +           || range->begin <= range->end - 1); /* non-empty */
> +}
> +
> +#define static
> +#define inline

Yeah, that's a bit of a hack.  I can live with it though.

The other alternative is to squash 2 and 3 into a single patch on
commit; but having them separate was a nice review aid.

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH RFC 3/4] range: Drop the previous commit's trickery

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 448 bytes --]

On 06/15/2016 02:41 PM, Markus Armbruster wrote:
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  include/qemu/range.h | 21 ---------------------
>  util/range.c         |  1 -
>  2 files changed, 22 deletions(-)

As mentioned on 2/4, you may want to squash this in.

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH RFC 4/4] range: Replace internal representation of Range

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1792 bytes --]

On 06/15/2016 02:41 PM, Markus Armbruster wrote:
> Range represents a range as follows.  Member @start is the inclusive
> lower bound, member @end is the exclusive upper bound.  Zero @end is
> special: if @start is also zero, the range is empty, else @end is to
> be interpreted as 2^64.  No other empty ranges may occur.
> 
> The range [0,2^64-1] cannot be represented.  If you try to create it
> with range_set_bounds1(), you get the empty range instead.  If you try
> to create it with range_set_bounds() or range_extend(), assertions
> fail.  Before range_set_bounds() existed, the open-coded creation
> usually got you the empty range instead.  Open deathtrap.
> 
> Moreover, the code dealing with the janus-faced @end is too clever by
> half.
> 
> Dumb this down to a more pedestrian representation: members @lob and
> @upb are inclusive lower and upper bounds.  The empty range is encoded
> as @lob = 1, @upb = 0.

And since all users now go through accessors, we've freed ourselves to
change the underlying representation.

> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  include/qemu/range.h | 55 +++++++++++++++++++++++++---------------------------
>  util/range.c         | 13 +++----------
>  2 files changed, 29 insertions(+), 39 deletions(-)

Not only does it have more power, it takes fewer lines of code!

>  
>  /* Compound literal encoding the empty range */
> -#define range_empty ((Range){ .begin = 0, .end = 0 })
> +#define range_empty ((Range){ .lob = 1, .upb = 0 })

well, one particular representation of the empty range, but the comment
is fine as-is.

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH RFC 2/4] range: Eliminate direct Range member access

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 06/15/2016 02:41 PM, Markus Armbruster wrote:
>> Users of struct Range mess liberally with its members, which makes
>> refactoring hard.  Create a set of methods, and convert all users to
>> call them instead of accessing members.  The methods have carefully
>> worded contracts, and use assertions to check them.
>> 
>> To help with tracking down the places that access members of struct
>> Range directly, hide the implementation of struct Range outside of
>> range.c by trickery.  The trickery will be dropped in the next commit.
>
> Can't we just make Range an opaque type, and move its definition into
> range.c?  Oh, except we have inline functions that would no longer be
> inline, unless we also had a range-impl.h private header.

I'm not sure the inline functions are warranted, but I'd rather not
debate that right now.  So this patch makes Range kind-of opaque
temporarily, by renaming its members outside range.c, just to help me
find their users, and to make it more obvious to you that I found them
all.

>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>> ---
>
>
>> @@ -2015,7 +2017,8 @@ build_dsdt(GArray *table_data, BIOSLinker *linker,
>>                           0, 0x000A0000, 0x000BFFFF, 0, 0x00020000));
>>  
>>      crs_replace_with_free_ranges(mem_ranges,
>> -                                 pci_hole->begin, pci_hole->end - 1);
>> +                                 range_lob(pci_hole),
>> +                                 range_upb(pci_hole));
>
> Changes like this are nice, isolating us from what the actual struct stores.
>
>
>> +++ b/include/qemu/range.h
>> @@ -30,18 +30,110 @@
>>   *   - this can not represent a full 0 to ~0x0LL range.
>>   */
>>  
>> +bool range_is_empty(Range *range);
>> +bool range_contains(Range *range, uint64_t val);
>> +void range_make_empty(Range *range);
>> +void range_set_bounds(Range *range, uint64_t lob, uint64_t upb);
>> +void range_set_bounds1(Range *range, uint64_t lob, uint64_t upb_plus1);
>> +uint64_t range_lob(Range *range);
>> +uint64_t range_upb(Range *range);
>> +void range_extend(Range *range, Range *extend_by);
>> +#ifdef RANGE_IMPL
>> +
>>  /* A structure representing a range of addresses. */
>>  struct Range {
>>      uint64_t begin; /* First byte of the range, or 0 if empty. */
>>      uint64_t end;   /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
>>  };
>>  
>> +static inline void range_invariant(Range *range)
>> +{
>> +    assert((!range->begin && !range->end) /* empty */
>> +           || range->begin <= range->end - 1); /* non-empty */
>> +}
>> +
>> +#define static
>> +#define inline
>
> Yeah, that's a bit of a hack.  I can live with it though.
>
> The other alternative is to squash 2 and 3 into a single patch on
> commit; but having them separate was a nice review aid.

I'm quite willing to squash if my trickery is considered too gross to be
preserved for posterity.  My personal preference is not to squash, for a
full record.

> Reviewed-by: Eric Blake <eblake@redhat.com>

Thanks!

Re: [Qemu-devel] [PATCH RFC 4/4] range: Replace internal representation of Range

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 06/15/2016 02:41 PM, Markus Armbruster wrote:
>> Range represents a range as follows.  Member @start is the inclusive
>> lower bound, member @end is the exclusive upper bound.  Zero @end is
>> special: if @start is also zero, the range is empty, else @end is to
>> be interpreted as 2^64.  No other empty ranges may occur.
>> 
>> The range [0,2^64-1] cannot be represented.  If you try to create it
>> with range_set_bounds1(), you get the empty range instead.  If you try
>> to create it with range_set_bounds() or range_extend(), assertions
>> fail.  Before range_set_bounds() existed, the open-coded creation
>> usually got you the empty range instead.  Open deathtrap.
>> 
>> Moreover, the code dealing with the janus-faced @end is too clever by
>> half.
>> 
>> Dumb this down to a more pedestrian representation: members @lob and
>> @upb are inclusive lower and upper bounds.  The empty range is encoded
>> as @lob = 1, @upb = 0.
>
> And since all users now go through accessors, we've freed ourselves to
> change the underlying representation.
>
>> 
>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>> ---
>>  include/qemu/range.h | 55 +++++++++++++++++++++++++---------------------------
>>  util/range.c         | 13 +++----------
>>  2 files changed, 29 insertions(+), 39 deletions(-)
>
> Not only does it have more power, it takes fewer lines of code!

That's the kind of change I like best :)

>>  /* Compound literal encoding the empty range */
>> -#define range_empty ((Range){ .begin = 0, .end = 0 })
>> +#define range_empty ((Range){ .lob = 1, .upb = 0 })
>
> well, one particular representation of the empty range, but the comment
> is fine as-is.

The only ways to create empty ranges are range_make_empty() and
range_set_bounds1().  Both use macro range_empty below the hood.

Before this patch, there is only one empty range: { .begin=0, .end=0 }.
range_empty is this one empty range:
    #define range_empty ((Range){ .begin = 0, .end = 0 })

range_invariant() enforces it:

    assert((!range->begin && !range->end) /* empty */
           || range->begin <= range->end - 1); /* non-empty */

range_is_empty() relies on it:

    return !range->begin && !range->end;

With this patch, the code treats any range with begin > end as empty.
range_invariant():

    assert(range->lob <= range->upb || range->lob == range->upb + 1);

range_is_empty():

    return range->lob > range->upb;

Nevertheless, you can still create only one:
    #define range_empty ((Range){ .lob = 1, .upb = 0 })

I could tighten range_invariant().  Doesn't feel worthwhile to me.

> Reviewed-by: Eric Blake <eblake@redhat.com>

Thanks!

Re: [Qemu-devel] [PATCH RFC 4/4] range: Replace internal representation of Range

[Michael S. Tsirkin]

On Wed, Jun 15, 2016 at 10:41:50PM +0200, Markus Armbruster wrote:
> Range represents a range as follows.  Member @start is the inclusive
> lower bound, member @end is the exclusive upper bound.  Zero @end is
> special: if @start is also zero, the range is empty, else @end is to
> be interpreted as 2^64.  No other empty ranges may occur.
> 
> The range [0,2^64-1] cannot be represented.  If you try to create it
> with range_set_bounds1(), you get the empty range instead.  If you try
> to create it with range_set_bounds() or range_extend(), assertions
> fail.  Before range_set_bounds() existed, the open-coded creation
> usually got you the empty range instead.  Open deathtrap.
> 
> Moreover, the code dealing with the janus-faced @end is too clever by
> half.
> 
> Dumb this down to a more pedestrian representation: members @lob and
> @upb are inclusive lower and upper bounds.  The empty range is encoded
> as @lob = 1, @upb = 0.
> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>

And now we can create the range [0,2^64-1] without issues. Nice!
Add a test for that then?

> ---
>  include/qemu/range.h | 55 +++++++++++++++++++++++++---------------------------
>  util/range.c         | 13 +++----------
>  2 files changed, 29 insertions(+), 39 deletions(-)
> 
> diff --git a/include/qemu/range.h b/include/qemu/range.h
> index c8c46a9..06ff361 100644
> --- a/include/qemu/range.h
> +++ b/include/qemu/range.h
> @@ -26,37 +26,37 @@
>  /*
>   * Operations on 64 bit address ranges.
>   * Notes:
> - *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
> - *   - this can not represent a full 0 to ~0x0LL range.
> + * - Ranges must not wrap around 0, but can include UINT64_MAX.
>   */
>  
> -/* A structure representing a range of addresses. */
>  struct Range {
> -    uint64_t begin; /* First byte of the range, or 0 if empty. */
> -    uint64_t end;   /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
> +    /*
> +     * A non-empty range has @lob <= @upb.
> +     * An empty range has @lob == @upb + 1.
> +     */
> +    uint64_t lob;        /* inclusive lower bound */
> +    uint64_t upb;        /* inclusive upper bound */
>  };
>  
>  static inline void range_invariant(Range *range)
>  {
> -    assert((!range->begin && !range->end) /* empty */
> -           || range->begin <= range->end - 1); /* non-empty */
> +    assert(range->lob <= range->upb || range->lob == range->upb + 1);
>  }
>  
>  /* Compound literal encoding the empty range */
> -#define range_empty ((Range){ .begin = 0, .end = 0 })
> +#define range_empty ((Range){ .lob = 1, .upb = 0 })
>  
>  /* Is @range empty? */
>  static inline bool range_is_empty(Range *range)
>  {
>      range_invariant(range);
> -    return !range->begin && !range->end;
> +    return range->lob > range->upb;
>  }
>  
>  /* Does @range contain @val? */
>  static inline bool range_contains(Range *range, uint64_t val)
>  {
> -    return !range_is_empty(range)
> -        && val >= range->begin && val <= range->end - 1;
> +    return val >= range->lob && val <= range->upb;
>  }
>  
>  /* Initialize @range to the empty range */
> @@ -71,14 +71,11 @@ static inline void range_make_empty(Range *range)
>   * Both bounds are inclusive.
>   * The interval must not be empty, i.e. @lob must be less than or
>   * equal @upb.
> - * The interval must not be [0,UINT64_MAX], because Range can't
> - * represent that.
>   */
>  static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
>  {
> -    assert(lob <= upb);
> -    range->begin = lob;
> -    range->end = upb + 1;       /* may wrap to zero, that's okay */
> +    range->lob = lob;
> +    range->upb = upb;
>      assert(!range_is_empty(range));
>  }
>  
> @@ -91,8 +88,12 @@ static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
>  static inline void range_set_bounds1(Range *range,
>                                       uint64_t lob, uint64_t upb_plus1)
>  {
> -    range->begin = lob;
> -    range->end = upb_plus1;
> +    if (!lob && !upb_plus1) {
> +        *range = range_empty;
> +    } else {
> +        range->lob = lob;
> +        range->upb = upb_plus1 - 1;
> +    }
>      range_invariant(range);
>  }
>  
> @@ -100,20 +101,18 @@ static inline void range_set_bounds1(Range *range,
>  static inline uint64_t range_lob(Range *range)
>  {
>      assert(!range_is_empty(range));
> -    return range->begin;
> +    return range->lob;
>  }
>  
>  /* Return @range's upper bound.  @range must not be empty. */
>  static inline uint64_t range_upb(Range *range)
>  {
>      assert(!range_is_empty(range));
> -    return range->end - 1;
> +    return range->upb;
>  }
>  
>  /*
>   * Extend @range to the smallest interval that includes @extend_by, too.
> - * This must not extend @range to cover the interval [0,UINT64_MAX],
> - * because Range can't represent that.
>   */
>  static inline void range_extend(Range *range, Range *extend_by)
>  {
> @@ -124,15 +123,13 @@ static inline void range_extend(Range *range, Range *extend_by)
>          *range = *extend_by;
>          return;
>      }
> -    if (range->begin > extend_by->begin) {
> -        range->begin = extend_by->begin;
> +    if (range->lob > extend_by->lob) {
> +        range->lob = extend_by->lob;
>      }
> -    /* Compare last byte in case region ends at ~0x0LL */
> -    if (range->end - 1 < extend_by->end - 1) {
> -        range->end = extend_by->end;
> +    if (range->upb < extend_by->upb) {
> +        range->upb = extend_by->upb;
>      }
> -    /* Must not extend to { .begin = 0, .end = 0 }: */
> -    assert(!range_is_empty(range));
> +    range_invariant(range);
>  }
>  
>  /* Get last byte of a range from offset + length.
> diff --git a/util/range.c b/util/range.c
> index ca149a0..8359066 100644
> --- a/util/range.c
> +++ b/util/range.c
> @@ -21,21 +21,14 @@
>  #include "qemu/osdep.h"
>  #include "qemu/range.h"
>  
> -/*
> - * Operations on 64 bit address ranges.
> - * Notes:
> - *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
> - *   - this can not represent a full 0 to ~0x0LL range.
> - */
> -
>  /* Return -1 if @a < @b, 1 if greater, and 0 if they touch or overlap. */
>  static inline int range_compare(Range *a, Range *b)
>  {
> -    /* Zero a->end is 2**64, and therefore not less than any b->begin */
> -    if (a->end && a->end < b->begin) {
> +    /* Careful, avoid wraparound */
> +    if (b->lob && b->lob - 1 > a->upb) {
>          return -1;
>      }
> -    if (b->end && a->begin > b->end) {
> +    if (a->lob && a->lob - 1 > b->upb) {
>          return 1;
>      }
>      return 0;

It looks like previously, an empty range was considered
overlapping any other range: a->begin and a->end are 0.

After this change, IIUC it is smaller than any other range,
which seems a bit arbitrary (why not greater?),
except for another empty range, for which it is
considered overlapping.

I think it's unlikely to break anything but might be
worth changing to match previous semantics.

> -- 
> 2.5.5

Re: [Qemu-devel] [PATCH RFC 1/4] log: Clean up misuse of Range for -dfilter

[Michael S. Tsirkin]

On Wed, Jun 15, 2016 at 10:41:47PM +0200, Markus Armbruster wrote:
> Range encodes an integer interval [a,b] as { begin = a, end = b + 1 },
> where a \in [0,2^64-1] and b \in [1,2^64].  Thus, zero end is to be
> interpreted as 2^64.
> 
> The implementation of -dfilter (commit 3514552) uses Range
> differently: it encodes [a,b] as { begin = a, end = b }.  The code
> works, but it contradicts the specification of Range in range.h.
> 
> Switch to the specified representation.  Since it can't represent
> [0,UINT64_MAX], we have to reject that now.  Add a test for it.
> 
> While we're rejecting anyway: observe that we reject -dfilter LOB..UPB
> where LOB > UPB when UPB is zero, but happily create an empty Range
> when it isn't.  Reject it then, too, and add a test for it.
> 
> While there, add a positive test for the problematic upper bound
> UINT64_MAX.
> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>

Reviewed-by: Michael S. Tsirkin <mst@redhat.com>

> ---
>  tests/test-logging.c | 10 ++++++++++
>  util/log.c           | 28 +++++++++++++++-------------
>  2 files changed, 25 insertions(+), 13 deletions(-)
> 
> diff --git a/tests/test-logging.c b/tests/test-logging.c
> index 440e75f..b6fa94e 100644
> --- a/tests/test-logging.c
> +++ b/tests/test-logging.c
> @@ -68,6 +68,16 @@ static void test_parse_range(void)
>      g_assert(qemu_log_in_addr_range(0x2050));
>      g_assert(qemu_log_in_addr_range(0x3050));
>  
> +    qemu_set_dfilter_ranges("0xffffffffffffffff-1", &error_abort);
> +    g_assert(qemu_log_in_addr_range(UINT64_MAX));
> +    g_assert_false(qemu_log_in_addr_range(UINT64_MAX - 1));
> +
> +    qemu_set_dfilter_ranges("0..0xffffffffffffffff", &err);
> +    error_free_or_abort(&err);
> +
> +    qemu_set_dfilter_ranges("2..1", &err);
> +    error_free_or_abort(&err);
> +
>      qemu_set_dfilter_ranges("0x1000+onehundred", &err);
>      error_free_or_abort(&err);
>  
> diff --git a/util/log.c b/util/log.c
> index 32e4160..f811d61 100644
> --- a/util/log.c
> +++ b/util/log.c
> @@ -131,8 +131,8 @@ bool qemu_log_in_addr_range(uint64_t addr)
>      if (debug_regions) {
>          int i = 0;
>          for (i = 0; i < debug_regions->len; i++) {
> -            struct Range *range = &g_array_index(debug_regions, Range, i);
> -            if (addr >= range->begin && addr <= range->end) {
> +            Range *range = &g_array_index(debug_regions, Range, i);
> +            if (addr >= range->begin && addr <= range->end - 1) {
>                  return true;
>              }
>          }
> @@ -158,7 +158,7 @@ void qemu_set_dfilter_ranges(const char *filter_spec, Error **errp)
>      for (i = 0; ranges[i]; i++) {
>          const char *r = ranges[i];
>          const char *range_op, *r2, *e;
> -        uint64_t r1val, r2val;
> +        uint64_t r1val, r2val, lob, upb;
>          struct Range range;
>  
>          range_op = strstr(r, "-");
> @@ -187,27 +187,29 @@ void qemu_set_dfilter_ranges(const char *filter_spec, Error **errp)
>                         (int)(r2 - range_op), range_op);
>              goto out;
>          }
> -        if (r2val == 0) {
> -            error_setg(errp, "Invalid range");
> -            goto out;
> -        }
>  
>          switch (*range_op) {
>          case '+':
> -            range.begin = r1val;
> -            range.end = r1val + (r2val - 1);
> +            lob = r1val;
> +            upb = r1val + r2val - 1;
>              break;
>          case '-':
> -            range.end = r1val;
> -            range.begin = r1val - (r2val - 1);
> +            upb = r1val;
> +            lob = r1val - (r2val - 1);
>              break;
>          case '.':
> -            range.begin = r1val;
> -            range.end = r2val;
> +            lob = r1val;
> +            upb = r2val;
>              break;
>          default:
>              g_assert_not_reached();
>          }
> +        if (lob > upb || (lob == 0 && upb == UINT64_MAX)) {
> +            error_setg(errp, "Invalid range");
> +            goto out;
> +        }
> +        range.begin = lob;
> +        range.end = upb + 1;
>          g_array_append_val(debug_regions, range);
>      }
>  out:
> -- 
> 2.5.5

Re: [Qemu-devel] [PATCH RFC 2/4] range: Eliminate direct Range member access

[Michael S. Tsirkin]

On Wed, Jun 15, 2016 at 10:41:48PM +0200, Markus Armbruster wrote:
> Users of struct Range mess liberally with its members, which makes
> refactoring hard.  Create a set of methods, and convert all users to
> call them instead of accessing members.  The methods have carefully
> worded contracts, and use assertions to check them.
> 
> To help with tracking down the places that access members of struct
> Range directly, hide the implementation of struct Range outside of
> range.c by trickery.  The trickery will be dropped in the next commit.
> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>

Reviewed-by: Michael S. Tsirkin <mst@redhat.com>

I guess you want me to merge this because of the changes in pc and pci?

> ---
>  hw/i386/acpi-build.c         |  35 +++++++-------
>  hw/pci-host/piix.c           |  26 +++++++----
>  hw/pci-host/q35.c            |  41 +++++++++++------
>  hw/pci/pci.c                 |  17 +++----
>  include/qemu/range.h         | 106 ++++++++++++++++++++++++++++++++++++++++++-
>  qapi/string-input-visitor.c  |  20 ++++----
>  qapi/string-output-visitor.c |  18 ++++----
>  util/log.c                   |   5 +-
>  util/range.c                 |   4 +-
>  9 files changed, 198 insertions(+), 74 deletions(-)
> 
> diff --git a/hw/i386/acpi-build.c b/hw/i386/acpi-build.c
> index 02fc534..6c36c24 100644
> --- a/hw/i386/acpi-build.c
> +++ b/hw/i386/acpi-build.c
> @@ -232,18 +232,20 @@ static void acpi_get_pci_holes(Range *hole, Range *hole64)
>      pci_host = acpi_get_i386_pci_host();
>      g_assert(pci_host);
>  
> -    hole->begin = object_property_get_int(pci_host,
> -                                          PCI_HOST_PROP_PCI_HOLE_START,
> -                                          NULL);
> -    hole->end = object_property_get_int(pci_host,
> -                                        PCI_HOST_PROP_PCI_HOLE_END,
> -                                        NULL);
> -    hole64->begin = object_property_get_int(pci_host,
> -                                            PCI_HOST_PROP_PCI_HOLE64_START,
> -                                            NULL);
> -    hole64->end = object_property_get_int(pci_host,
> -                                          PCI_HOST_PROP_PCI_HOLE64_END,
> -                                          NULL);
> +    range_set_bounds1(hole,
> +                      object_property_get_int(pci_host,
> +                                              PCI_HOST_PROP_PCI_HOLE_START,
> +                                              NULL),
> +                      object_property_get_int(pci_host,
> +                                              PCI_HOST_PROP_PCI_HOLE_END,
> +                                              NULL));
> +    range_set_bounds1(hole64,
> +                      object_property_get_int(pci_host,
> +                                              PCI_HOST_PROP_PCI_HOLE64_START,
> +                                              NULL),
> +                      object_property_get_int(pci_host,
> +                                              PCI_HOST_PROP_PCI_HOLE64_END,
> +                                              NULL));
>  }
>  
>  #define ACPI_PORT_SMI_CMD           0x00b2 /* TODO: this is APM_CNT_IOPORT */
> @@ -2015,7 +2017,8 @@ build_dsdt(GArray *table_data, BIOSLinker *linker,
>                           0, 0x000A0000, 0x000BFFFF, 0, 0x00020000));
>  
>      crs_replace_with_free_ranges(mem_ranges,
> -                                 pci_hole->begin, pci_hole->end - 1);
> +                                 range_lob(pci_hole),
> +                                 range_upb(pci_hole));
>      for (i = 0; i < mem_ranges->len; i++) {
>          entry = g_ptr_array_index(mem_ranges, i);
>          aml_append(crs,
> @@ -2025,12 +2028,12 @@ build_dsdt(GArray *table_data, BIOSLinker *linker,
>                               0, entry->limit - entry->base + 1));
>      }
>  
> -    if (pci_hole64->begin) {
> +    if (!range_is_empty(pci_hole64)) {
>          aml_append(crs,
>              aml_qword_memory(AML_POS_DECODE, AML_MIN_FIXED, AML_MAX_FIXED,
>                               AML_CACHEABLE, AML_READ_WRITE,
> -                             0, pci_hole64->begin, pci_hole64->end - 1, 0,
> -                             pci_hole64->end - pci_hole64->begin));
> +                             0, range_lob(pci_hole64), range_upb(pci_hole64), 0,
> +                             range_upb(pci_hole64) + 1 - range_lob(pci_hole64)));
>      }
>  
>      if (misc->tpm_version != TPM_VERSION_UNSPEC) {
> diff --git a/hw/pci-host/piix.c b/hw/pci-host/piix.c
> index 8db0f09..1df327f 100644
> --- a/hw/pci-host/piix.c
> +++ b/hw/pci-host/piix.c
> @@ -221,8 +221,12 @@ static void i440fx_pcihost_get_pci_hole_start(Object *obj, Visitor *v,
>                                                Error **errp)
>  {
>      I440FXState *s = I440FX_PCI_HOST_BRIDGE(obj);
> -    uint32_t value = s->pci_hole.begin;
> +    uint64_t val64;
> +    uint32_t value;
>  
> +    val64 = range_is_empty(&s->pci_hole) ? 0 : range_lob(&s->pci_hole);
> +    value = val64;
> +    assert(value == val64);
>      visit_type_uint32(v, name, &value, errp);
>  }
>  
> @@ -231,8 +235,12 @@ static void i440fx_pcihost_get_pci_hole_end(Object *obj, Visitor *v,
>                                              Error **errp)
>  {
>      I440FXState *s = I440FX_PCI_HOST_BRIDGE(obj);
> -    uint32_t value = s->pci_hole.end;
> +    uint64_t val64;
> +    uint32_t value;
>  
> +    val64 = range_is_empty(&s->pci_hole) ? 0 : range_upb(&s->pci_hole) + 1;
> +    value = val64;
> +    assert(value == val64);
>      visit_type_uint32(v, name, &value, errp);
>  }
>  
> @@ -242,10 +250,11 @@ static void i440fx_pcihost_get_pci_hole64_start(Object *obj, Visitor *v,
>  {
>      PCIHostState *h = PCI_HOST_BRIDGE(obj);
>      Range w64;
> +    uint64_t value;
>  
>      pci_bus_get_w64_range(h->bus, &w64);
> -
> -    visit_type_uint64(v, name, &w64.begin, errp);
> +    value = range_is_empty(&w64) ? 0 : range_lob(&w64);
> +    visit_type_uint64(v, name, &value, errp);
>  }
>  
>  static void i440fx_pcihost_get_pci_hole64_end(Object *obj, Visitor *v,
> @@ -254,10 +263,11 @@ static void i440fx_pcihost_get_pci_hole64_end(Object *obj, Visitor *v,
>  {
>      PCIHostState *h = PCI_HOST_BRIDGE(obj);
>      Range w64;
> +    uint64_t value;
>  
>      pci_bus_get_w64_range(h->bus, &w64);
> -
> -    visit_type_uint64(v, name, &w64.end, errp);
> +    value = range_is_empty(&w64) ? 0 : range_upb(&w64) + 1;
> +    visit_type_uint64(v, name, &value, errp);
>  }
>  
>  static void i440fx_pcihost_initfn(Object *obj)
> @@ -344,8 +354,8 @@ PCIBus *i440fx_init(const char *host_type, const char *pci_type,
>      f->ram_memory = ram_memory;
>  
>      i440fx = I440FX_PCI_HOST_BRIDGE(dev);
> -    i440fx->pci_hole.begin = below_4g_mem_size;
> -    i440fx->pci_hole.end = IO_APIC_DEFAULT_ADDRESS;
> +    range_set_bounds(&i440fx->pci_hole, below_4g_mem_size,
> +                     IO_APIC_DEFAULT_ADDRESS - 1);
>  
>      /* setup pci memory mapping */
>      pc_pci_as_mapping_init(OBJECT(f), f->system_memory,
> diff --git a/hw/pci-host/q35.c b/hw/pci-host/q35.c
> index 8c2c1db..d200091 100644
> --- a/hw/pci-host/q35.c
> +++ b/hw/pci-host/q35.c
> @@ -73,8 +73,13 @@ static void q35_host_get_pci_hole_start(Object *obj, Visitor *v,
>                                          Error **errp)
>  {
>      Q35PCIHost *s = Q35_HOST_DEVICE(obj);
> -    uint32_t value = s->mch.pci_hole.begin;
> +    uint64_t val64;
> +    uint32_t value;
>  
> +    val64 = range_is_empty(&s->mch.pci_hole)
> +        ? 0 : range_lob(&s->mch.pci_hole);
> +    value = val64;
> +    assert(value == val64);
>      visit_type_uint32(v, name, &value, errp);
>  }
>  
> @@ -83,8 +88,13 @@ static void q35_host_get_pci_hole_end(Object *obj, Visitor *v,
>                                        Error **errp)
>  {
>      Q35PCIHost *s = Q35_HOST_DEVICE(obj);
> -    uint32_t value = s->mch.pci_hole.end;
> +    uint64_t val64;
> +    uint32_t value;
>  
> +    val64 = range_is_empty(&s->mch.pci_hole)
> +        ? 0 : range_upb(&s->mch.pci_hole) + 1;
> +    value = val64;
> +    assert(value == val64);
>      visit_type_uint32(v, name, &value, errp);
>  }
>  
> @@ -94,10 +104,11 @@ static void q35_host_get_pci_hole64_start(Object *obj, Visitor *v,
>  {
>      PCIHostState *h = PCI_HOST_BRIDGE(obj);
>      Range w64;
> +    uint64_t value;
>  
>      pci_bus_get_w64_range(h->bus, &w64);
> -
> -    visit_type_uint64(v, name, &w64.begin, errp);
> +    value = range_is_empty(&w64) ? 0 : range_lob(&w64);
> +    visit_type_uint64(v, name, &value, errp);
>  }
>  
>  static void q35_host_get_pci_hole64_end(Object *obj, Visitor *v,
> @@ -106,10 +117,11 @@ static void q35_host_get_pci_hole64_end(Object *obj, Visitor *v,
>  {
>      PCIHostState *h = PCI_HOST_BRIDGE(obj);
>      Range w64;
> +    uint64_t value;
>  
>      pci_bus_get_w64_range(h->bus, &w64);
> -
> -    visit_type_uint64(v, name, &w64.end, errp);
> +    value = range_is_empty(&w64) ? 0 : range_upb(&w64) + 1;
> +    visit_type_uint64(v, name, &value, errp);
>  }
>  
>  static void q35_host_get_mmcfg_size(Object *obj, Visitor *v, const char *name,
> @@ -182,9 +194,9 @@ static void q35_host_initfn(Object *obj)
>       * it's not a power of two, which means an MTRR
>       * can't cover it exactly.
>       */
> -    s->mch.pci_hole.begin = MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT +
> -        MCH_HOST_BRIDGE_PCIEXBAR_MAX;
> -    s->mch.pci_hole.end = IO_APIC_DEFAULT_ADDRESS;
> +    range_set_bounds(&s->mch.pci_hole,
> +            MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT + MCH_HOST_BRIDGE_PCIEXBAR_MAX,
> +            IO_APIC_DEFAULT_ADDRESS - 1);
>  }
>  
>  static const TypeInfo q35_host_info = {
> @@ -252,10 +264,7 @@ static void mch_update_pciexbar(MCHPCIState *mch)
>          break;
>      case MCH_HOST_BRIDGE_PCIEXBAR_LENGTH_RVD:
>      default:
> -        enable = 0;
> -        length = 0;
>          abort();
> -        break;
>      }
>      addr = pciexbar & addr_mask;
>      pcie_host_mmcfg_update(pehb, enable, addr, length);
> @@ -265,9 +274,13 @@ static void mch_update_pciexbar(MCHPCIState *mch)
>       * which means an MTRR can't cover it exactly.
>       */
>      if (enable) {
> -        mch->pci_hole.begin = addr + length;
> +        range_set_bounds(&mch->pci_hole,
> +                         addr + length,
> +                         IO_APIC_DEFAULT_ADDRESS - 1);
>      } else {
> -        mch->pci_hole.begin = MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT;
> +        range_set_bounds(&mch->pci_hole,
> +                         MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT,
> +                         IO_APIC_DEFAULT_ADDRESS - 1);
>      }
>  }
>  
> diff --git a/hw/pci/pci.c b/hw/pci/pci.c
> index bb605ef..904c6fd 100644
> --- a/hw/pci/pci.c
> +++ b/hw/pci/pci.c
> @@ -2436,13 +2436,13 @@ static void pci_dev_get_w64(PCIBus *b, PCIDevice *dev, void *opaque)
>  
>          if (limit >= base) {
>              Range pref_range;
> -            pref_range.begin = base;
> -            pref_range.end = limit + 1;
> +            range_set_bounds(&pref_range, base, limit);
>              range_extend(range, &pref_range);
>          }
>      }
>      for (i = 0; i < PCI_NUM_REGIONS; ++i) {
>          PCIIORegion *r = &dev->io_regions[i];
> +        pcibus_t lob, upb;
>          Range region_range;
>  
>          if (!r->size ||
> @@ -2450,16 +2450,17 @@ static void pci_dev_get_w64(PCIBus *b, PCIDevice *dev, void *opaque)
>              !(r->type & PCI_BASE_ADDRESS_MEM_TYPE_64)) {
>              continue;
>          }
> -        region_range.begin = pci_bar_address(dev, i, r->type, r->size);
> -        region_range.end = region_range.begin + r->size;
>  
> -        if (region_range.begin == PCI_BAR_UNMAPPED) {
> +        lob = pci_bar_address(dev, i, r->type, r->size);
> +        upb = lob + r->size - 1;
> +        if (lob == PCI_BAR_UNMAPPED) {
>              continue;
>          }
>  
> -        region_range.begin = MAX(region_range.begin, 0x1ULL << 32);
> +        lob = MAX(lob, 0x1ULL << 32);
>  
> -        if (region_range.end - 1 >= region_range.begin) {
> +        if (upb >= lob) {
> +            range_set_bounds(&region_range, lob, upb);
>              range_extend(range, &region_range);
>          }
>      }
> @@ -2467,7 +2468,7 @@ static void pci_dev_get_w64(PCIBus *b, PCIDevice *dev, void *opaque)
>  
>  void pci_bus_get_w64_range(PCIBus *bus, Range *range)
>  {
> -    range->begin = range->end = 0;
> +    range_make_empty(range);
>      pci_for_each_device_under_bus(bus, pci_dev_get_w64, range);
>  }
>  
> diff --git a/include/qemu/range.h b/include/qemu/range.h
> index 3970f00..9296ba0 100644
> --- a/include/qemu/range.h
> +++ b/include/qemu/range.h
> @@ -30,18 +30,110 @@
>   *   - this can not represent a full 0 to ~0x0LL range.
>   */
>  
> +bool range_is_empty(Range *range);
> +bool range_contains(Range *range, uint64_t val);
> +void range_make_empty(Range *range);
> +void range_set_bounds(Range *range, uint64_t lob, uint64_t upb);
> +void range_set_bounds1(Range *range, uint64_t lob, uint64_t upb_plus1);
> +uint64_t range_lob(Range *range);
> +uint64_t range_upb(Range *range);
> +void range_extend(Range *range, Range *extend_by);
> +#ifdef RANGE_IMPL
> +
>  /* A structure representing a range of addresses. */
>  struct Range {
>      uint64_t begin; /* First byte of the range, or 0 if empty. */
>      uint64_t end;   /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
>  };
>  
> +static inline void range_invariant(Range *range)
> +{
> +    assert((!range->begin && !range->end) /* empty */
> +           || range->begin <= range->end - 1); /* non-empty */
> +}
> +
> +#define static
> +#define inline
> +
> +/* Compound literal encoding the empty range */
> +#define range_empty ((Range){ .begin = 0, .end = 0 })
> +
> +/* Is @range empty? */
> +static inline bool range_is_empty(Range *range)
> +{
> +    range_invariant(range);
> +    return !range->begin && !range->end;
> +}
> +
> +/* Does @range contain @val? */
> +static inline bool range_contains(Range *range, uint64_t val)
> +{
> +    return !range_is_empty(range)
> +        && val >= range->begin && val <= range->end - 1;
> +}
> +
> +/* Initialize @range to the empty range */
> +static inline void range_make_empty(Range *range)
> +{
> +    *range = range_empty;
> +    assert(range_is_empty(range));
> +}
> +
> +/*
> + * Initialize @range to span the interval [@lob,@upb].
> + * Both bounds are inclusive.
> + * The interval must not be empty, i.e. @lob must be less than or
> + * equal @upb.
> + * The interval must not be [0,UINT64_MAX], because Range can't
> + * represent that.
> + */
> +static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
> +{
> +    assert(lob <= upb);
> +    range->begin = lob;
> +    range->end = upb + 1;       /* may wrap to zero, that's okay */
> +    assert(!range_is_empty(range));
> +}
> +
> +/*
> + * Initialize @range to span the interval [@lob,@upb_plus1).
> + * The lower bound is inclusive, the upper bound is exclusive.
> + * Zero @upb_plus1 is special: if @lob is also zero, set @range to the
> + * empty range.  Else, set @range to [@lob,UINT64_MAX].
> + */
> +static inline void range_set_bounds1(Range *range,
> +                                     uint64_t lob, uint64_t upb_plus1)
> +{
> +    range->begin = lob;
> +    range->end = upb_plus1;
> +    range_invariant(range);
> +}
> +
> +/* Return @range's lower bound.  @range must not be empty. */
> +static inline uint64_t range_lob(Range *range)
> +{
> +    assert(!range_is_empty(range));
> +    return range->begin;
> +}
> +
> +/* Return @range's upper bound.  @range must not be empty. */
> +static inline uint64_t range_upb(Range *range)
> +{
> +    assert(!range_is_empty(range));
> +    return range->end - 1;
> +}
> +
> +/*
> + * Extend @range to the smallest interval that includes @extend_by, too.
> + * This must not extend @range to cover the interval [0,UINT64_MAX],
> + * because Range can't represent that.
> + */
>  static inline void range_extend(Range *range, Range *extend_by)
>  {
> -    if (!extend_by->begin && !extend_by->end) {
> +    if (range_is_empty(extend_by)) {
>          return;
>      }
> -    if (!range->begin && !range->end) {
> +    if (range_is_empty(range)) {
>          *range = *extend_by;
>          return;
>      }
> @@ -52,8 +144,18 @@ static inline void range_extend(Range *range, Range *extend_by)
>      if (range->end - 1 < extend_by->end - 1) {
>          range->end = extend_by->end;
>      }
> +    /* Must not extend to { .begin = 0, .end = 0 }: */
> +    assert(!range_is_empty(range));
>  }
>  
> +#undef static
> +#undef inline
> +#else
> +struct Range {
> +    uint64_t begin_, end_;
> +};
> +#endif
> +
>  /* Get last byte of a range from offset + length.
>   * Undefined for ranges that wrap around 0. */
>  static inline uint64_t range_get_last(uint64_t offset, uint64_t len)
> diff --git a/qapi/string-input-visitor.c b/qapi/string-input-visitor.c
> index b546e5f..0690abb 100644
> --- a/qapi/string-input-visitor.c
> +++ b/qapi/string-input-visitor.c
> @@ -59,8 +59,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
>          if (errno == 0 && endptr > str) {
>              if (*endptr == '\0') {
>                  cur = g_malloc0(sizeof(*cur));
> -                cur->begin = start;
> -                cur->end = start + 1;
> +                range_set_bounds(cur, start, start);
>                  siv->ranges = range_list_insert(siv->ranges, cur);
>                  cur = NULL;
>                  str = NULL;
> @@ -73,16 +72,14 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
>                       end < start + 65536)) {
>                      if (*endptr == '\0') {
>                          cur = g_malloc0(sizeof(*cur));
> -                        cur->begin = start;
> -                        cur->end = end + 1;
> +                        range_set_bounds(cur, start, end);
>                          siv->ranges = range_list_insert(siv->ranges, cur);
>                          cur = NULL;
>                          str = NULL;
>                      } else if (*endptr == ',') {
>                          str = endptr + 1;
>                          cur = g_malloc0(sizeof(*cur));
> -                        cur->begin = start;
> -                        cur->end = end + 1;
> +                        range_set_bounds(cur, start, end);
>                          siv->ranges = range_list_insert(siv->ranges, cur);
>                          cur = NULL;
>                      } else {
> @@ -94,8 +91,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
>              } else if (*endptr == ',') {
>                  str = endptr + 1;
>                  cur = g_malloc0(sizeof(*cur));
> -                cur->begin = start;
> -                cur->end = start + 1;
> +                range_set_bounds(cur, start, start);
>                  siv->ranges = range_list_insert(siv->ranges, cur);
>                  cur = NULL;
>              } else {
> @@ -134,7 +130,7 @@ start_list(Visitor *v, const char *name, GenericList **list, size_t size,
>      if (siv->cur_range) {
>          Range *r = siv->cur_range->data;
>          if (r) {
> -            siv->cur = r->begin;
> +            siv->cur = range_lob(r);
>          }
>          *list = g_malloc0(size);
>      } else {
> @@ -156,7 +152,7 @@ static GenericList *next_list(Visitor *v, GenericList *tail, size_t size)
>          return NULL;
>      }
>  
> -    if (siv->cur < r->begin || siv->cur >= r->end) {
> +    if (!range_contains(r, siv->cur)) {
>          siv->cur_range = g_list_next(siv->cur_range);
>          if (!siv->cur_range) {
>              return NULL;
> @@ -165,7 +161,7 @@ static GenericList *next_list(Visitor *v, GenericList *tail, size_t size)
>          if (!r) {
>              return NULL;
>          }
> -        siv->cur = r->begin;
> +        siv->cur = range_lob(r);
>      }
>  
>      tail->next = g_malloc0(size);
> @@ -208,7 +204,7 @@ static void parse_type_int64(Visitor *v, const char *name, int64_t *obj,
>              goto error;
>          }
>  
> -        siv->cur = r->begin;
> +        siv->cur = range_lob(r);
>      }
>  
>      *obj = siv->cur;
> diff --git a/qapi/string-output-visitor.c b/qapi/string-output-visitor.c
> index 5ea395a..c6f01f9 100644
> --- a/qapi/string-output-visitor.c
> +++ b/qapi/string-output-visitor.c
> @@ -83,8 +83,8 @@ static void string_output_set(StringOutputVisitor *sov, char *string)
>  static void string_output_append(StringOutputVisitor *sov, int64_t a)
>  {
>      Range *r = g_malloc0(sizeof(*r));
> -    r->begin = a;
> -    r->end = a + 1;
> +
> +    range_set_bounds(r, a, a);
>      sov->ranges = range_list_insert(sov->ranges, r);
>  }
>  
> @@ -92,28 +92,28 @@ static void string_output_append_range(StringOutputVisitor *sov,
>                                         int64_t s, int64_t e)
>  {
>      Range *r = g_malloc0(sizeof(*r));
> -    r->begin = s;
> -    r->end = e + 1;
> +
> +    range_set_bounds(r, s, e);
>      sov->ranges = range_list_insert(sov->ranges, r);
>  }
>  
>  static void format_string(StringOutputVisitor *sov, Range *r, bool next,
>                            bool human)
>  {
> -    if (r->end - r->begin > 1) {
> +    if (range_lob(r) != range_upb(r)) {
>          if (human) {
>              g_string_append_printf(sov->string, "0x%" PRIx64 "-0x%" PRIx64,
> -                                   r->begin, r->end - 1);
> +                                   range_lob(r), range_upb(r));
>  
>          } else {
>              g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64,
> -                                   r->begin, r->end - 1);
> +                                   range_lob(r), range_upb(r));
>          }
>      } else {
>          if (human) {
> -            g_string_append_printf(sov->string, "0x%" PRIx64, r->begin);
> +            g_string_append_printf(sov->string, "0x%" PRIx64, range_lob(r));
>          } else {
> -            g_string_append_printf(sov->string, "%" PRId64, r->begin);
> +            g_string_append_printf(sov->string, "%" PRId64, range_lob(r));
>          }
>      }
>      if (next) {
> diff --git a/util/log.c b/util/log.c
> index f811d61..4da635c 100644
> --- a/util/log.c
> +++ b/util/log.c
> @@ -132,7 +132,7 @@ bool qemu_log_in_addr_range(uint64_t addr)
>          int i = 0;
>          for (i = 0; i < debug_regions->len; i++) {
>              Range *range = &g_array_index(debug_regions, Range, i);
> -            if (addr >= range->begin && addr <= range->end - 1) {
> +            if (range_contains(range, addr)) {
>                  return true;
>              }
>          }
> @@ -208,8 +208,7 @@ void qemu_set_dfilter_ranges(const char *filter_spec, Error **errp)
>              error_setg(errp, "Invalid range");
>              goto out;
>          }
> -        range.begin = lob;
> -        range.end = upb + 1;
> +        range_set_bounds(&range, lob, upb);
>          g_array_append_val(debug_regions, range);
>      }
>  out:
> diff --git a/util/range.c b/util/range.c
> index 56e6baf..ab5102a 100644
> --- a/util/range.c
> +++ b/util/range.c
> @@ -19,6 +19,7 @@
>   */
>  
>  #include "qemu/osdep.h"
> +#define RANGE_IMPL
>  #include "qemu/range.h"
>  
>  /*
> @@ -46,8 +47,7 @@ GList *range_list_insert(GList *list, Range *data)
>  {
>      GList *l;
>  
> -    /* Range lists require no empty ranges */
> -    assert(data->begin < data->end || (data->begin && !data->end));
> +    assert(!range_is_empty(data));
>  
>      for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
>          /* Skip all list elements strictly less than data */
> -- 
> 2.5.5

Re: [Qemu-devel] [PATCH RFC 3/4] range: Drop the previous commit's trickery

[Michael S. Tsirkin]

On Wed, Jun 15, 2016 at 10:41:49PM +0200, Markus Armbruster wrote:
> Signed-off-by: Markus Armbruster <armbru@redhat.com>

Agree with Eric about squashing this.

Reviewed-by: Michael S. Tsirkin <mst@redhat.com>

> ---
>  include/qemu/range.h | 21 ---------------------
>  util/range.c         |  1 -
>  2 files changed, 22 deletions(-)
> 
> diff --git a/include/qemu/range.h b/include/qemu/range.h
> index 9296ba0..c8c46a9 100644
> --- a/include/qemu/range.h
> +++ b/include/qemu/range.h
> @@ -30,16 +30,6 @@
>   *   - this can not represent a full 0 to ~0x0LL range.
>   */
>  
> -bool range_is_empty(Range *range);
> -bool range_contains(Range *range, uint64_t val);
> -void range_make_empty(Range *range);
> -void range_set_bounds(Range *range, uint64_t lob, uint64_t upb);
> -void range_set_bounds1(Range *range, uint64_t lob, uint64_t upb_plus1);
> -uint64_t range_lob(Range *range);
> -uint64_t range_upb(Range *range);
> -void range_extend(Range *range, Range *extend_by);
> -#ifdef RANGE_IMPL
> -
>  /* A structure representing a range of addresses. */
>  struct Range {
>      uint64_t begin; /* First byte of the range, or 0 if empty. */
> @@ -52,9 +42,6 @@ static inline void range_invariant(Range *range)
>             || range->begin <= range->end - 1); /* non-empty */
>  }
>  
> -#define static
> -#define inline
> -
>  /* Compound literal encoding the empty range */
>  #define range_empty ((Range){ .begin = 0, .end = 0 })
>  
> @@ -148,14 +135,6 @@ static inline void range_extend(Range *range, Range *extend_by)
>      assert(!range_is_empty(range));
>  }
>  
> -#undef static
> -#undef inline
> -#else
> -struct Range {
> -    uint64_t begin_, end_;
> -};
> -#endif
> -
>  /* Get last byte of a range from offset + length.
>   * Undefined for ranges that wrap around 0. */
>  static inline uint64_t range_get_last(uint64_t offset, uint64_t len)
> diff --git a/util/range.c b/util/range.c
> index ab5102a..ca149a0 100644
> --- a/util/range.c
> +++ b/util/range.c
> @@ -19,7 +19,6 @@
>   */
>  
>  #include "qemu/osdep.h"
> -#define RANGE_IMPL
>  #include "qemu/range.h"
>  
>  /*
> -- 
> 2.5.5

Re: [Qemu-devel] [PATCH RFC 2/4] range: Eliminate direct Range member access

[Markus Armbruster]

"Michael S. Tsirkin" <mst@redhat.com> writes:

> On Wed, Jun 15, 2016 at 10:41:48PM +0200, Markus Armbruster wrote:
>> Users of struct Range mess liberally with its members, which makes
>> refactoring hard.  Create a set of methods, and convert all users to
>> call them instead of accessing members.  The methods have carefully
>> worded contracts, and use assertions to check them.
>> 
>> To help with tracking down the places that access members of struct
>> Range directly, hide the implementation of struct Range outside of
>> range.c by trickery.  The trickery will be dropped in the next commit.
>> 
>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>
> Reviewed-by: Michael S. Tsirkin <mst@redhat.com>

Thanks!

> I guess you want me to merge this because of the changes in pc and pci?

Yes, please (whole series, once respun without the RFC).

Re: [Qemu-devel] [PATCH RFC 3/4] range: Drop the previous commit's trickery

[Markus Armbruster]

"Michael S. Tsirkin" <mst@redhat.com> writes:

> On Wed, Jun 15, 2016 at 10:41:49PM +0200, Markus Armbruster wrote:
>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>
> Agree with Eric about squashing this.

Sanity check since Eric wrote "may": I assume you prefer this patch be
squashed into the previous one for the non-RFC respin.  If not, let me
know.

> Reviewed-by: Michael S. Tsirkin <mst@redhat.com>

Thanks!

Re: [Qemu-devel] [PATCH RFC 4/4] range: Replace internal representation of Range

[Markus Armbruster]

"Michael S. Tsirkin" <mst@redhat.com> writes:

> On Wed, Jun 15, 2016 at 10:41:50PM +0200, Markus Armbruster wrote:
>> Range represents a range as follows.  Member @start is the inclusive
>> lower bound, member @end is the exclusive upper bound.  Zero @end is
>> special: if @start is also zero, the range is empty, else @end is to
>> be interpreted as 2^64.  No other empty ranges may occur.
>> 
>> The range [0,2^64-1] cannot be represented.  If you try to create it
>> with range_set_bounds1(), you get the empty range instead.  If you try
>> to create it with range_set_bounds() or range_extend(), assertions
>> fail.  Before range_set_bounds() existed, the open-coded creation
>> usually got you the empty range instead.  Open deathtrap.
>> 
>> Moreover, the code dealing with the janus-faced @end is too clever by
>> half.
>> 
>> Dumb this down to a more pedestrian representation: members @lob and
>> @upb are inclusive lower and upper bounds.  The empty range is encoded
>> as @lob = 1, @upb = 0.
>> 
>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>
> And now we can create the range [0,2^64-1] without issues. Nice!
> Add a test for that then?

Sure!

>> ---
>>  include/qemu/range.h | 55 +++++++++++++++++++++++++---------------------------
>>  util/range.c         | 13 +++----------
>>  2 files changed, 29 insertions(+), 39 deletions(-)
>> 
>> diff --git a/include/qemu/range.h b/include/qemu/range.h
>> index c8c46a9..06ff361 100644
>> --- a/include/qemu/range.h
>> +++ b/include/qemu/range.h
>> @@ -26,37 +26,37 @@
>>  /*
>>   * Operations on 64 bit address ranges.
>>   * Notes:
>> - *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
>> - *   - this can not represent a full 0 to ~0x0LL range.
>> + * - Ranges must not wrap around 0, but can include UINT64_MAX.
>>   */
>>  
>> -/* A structure representing a range of addresses. */
>>  struct Range {
>> -    uint64_t begin; /* First byte of the range, or 0 if empty. */
>> -    uint64_t end;   /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
>> +    /*
>> +     * A non-empty range has @lob <= @upb.
>> +     * An empty range has @lob == @upb + 1.
>> +     */
>> +    uint64_t lob;        /* inclusive lower bound */
>> +    uint64_t upb;        /* inclusive upper bound */
>>  };
>>  
>>  static inline void range_invariant(Range *range)
>>  {
>> -    assert((!range->begin && !range->end) /* empty */
>> -           || range->begin <= range->end - 1); /* non-empty */
>> +    assert(range->lob <= range->upb || range->lob == range->upb + 1);
>>  }
>>  
>>  /* Compound literal encoding the empty range */
>> -#define range_empty ((Range){ .begin = 0, .end = 0 })
>> +#define range_empty ((Range){ .lob = 1, .upb = 0 })
>>  
>>  /* Is @range empty? */
>>  static inline bool range_is_empty(Range *range)
>>  {
>>      range_invariant(range);
>> -    return !range->begin && !range->end;
>> +    return range->lob > range->upb;
>>  }
>>  
>>  /* Does @range contain @val? */
>>  static inline bool range_contains(Range *range, uint64_t val)
>>  {
>> -    return !range_is_empty(range)
>> -        && val >= range->begin && val <= range->end - 1;
>> +    return val >= range->lob && val <= range->upb;
>>  }
>>  
>>  /* Initialize @range to the empty range */
>> @@ -71,14 +71,11 @@ static inline void range_make_empty(Range *range)
>>   * Both bounds are inclusive.
>>   * The interval must not be empty, i.e. @lob must be less than or
>>   * equal @upb.
>> - * The interval must not be [0,UINT64_MAX], because Range can't
>> - * represent that.
>>   */
>>  static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
>>  {
>> -    assert(lob <= upb);
>> -    range->begin = lob;
>> -    range->end = upb + 1;       /* may wrap to zero, that's okay */
>> +    range->lob = lob;
>> +    range->upb = upb;
>>      assert(!range_is_empty(range));
>>  }
>>  
>> @@ -91,8 +88,12 @@ static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
>>  static inline void range_set_bounds1(Range *range,
>>                                       uint64_t lob, uint64_t upb_plus1)
>>  {
>> -    range->begin = lob;
>> -    range->end = upb_plus1;
>> +    if (!lob && !upb_plus1) {
>> +        *range = range_empty;
>> +    } else {
>> +        range->lob = lob;
>> +        range->upb = upb_plus1 - 1;
>> +    }
>>      range_invariant(range);
>>  }
>>  
>> @@ -100,20 +101,18 @@ static inline void range_set_bounds1(Range *range,
>>  static inline uint64_t range_lob(Range *range)
>>  {
>>      assert(!range_is_empty(range));
>> -    return range->begin;
>> +    return range->lob;
>>  }
>>  
>>  /* Return @range's upper bound.  @range must not be empty. */
>>  static inline uint64_t range_upb(Range *range)
>>  {
>>      assert(!range_is_empty(range));
>> -    return range->end - 1;
>> +    return range->upb;
>>  }
>>  
>>  /*
>>   * Extend @range to the smallest interval that includes @extend_by, too.
>> - * This must not extend @range to cover the interval [0,UINT64_MAX],
>> - * because Range can't represent that.
>>   */
>>  static inline void range_extend(Range *range, Range *extend_by)
>>  {
>> @@ -124,15 +123,13 @@ static inline void range_extend(Range *range, Range *extend_by)
>>          *range = *extend_by;
>>          return;
>>      }
>> -    if (range->begin > extend_by->begin) {
>> -        range->begin = extend_by->begin;
>> +    if (range->lob > extend_by->lob) {
>> +        range->lob = extend_by->lob;
>>      }
>> -    /* Compare last byte in case region ends at ~0x0LL */
>> -    if (range->end - 1 < extend_by->end - 1) {
>> -        range->end = extend_by->end;
>> +    if (range->upb < extend_by->upb) {
>> +        range->upb = extend_by->upb;
>>      }
>> -    /* Must not extend to { .begin = 0, .end = 0 }: */
>> -    assert(!range_is_empty(range));
>> +    range_invariant(range);
>>  }
>>  
>>  /* Get last byte of a range from offset + length.
>> diff --git a/util/range.c b/util/range.c
>> index ca149a0..8359066 100644
>> --- a/util/range.c
>> +++ b/util/range.c
>> @@ -21,21 +21,14 @@
>>  #include "qemu/osdep.h"
>>  #include "qemu/range.h"
>>  
>> -/*
>> - * Operations on 64 bit address ranges.
>> - * Notes:
>> - *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
>> - *   - this can not represent a full 0 to ~0x0LL range.
>> - */
>> -
>>  /* Return -1 if @a < @b, 1 if greater, and 0 if they touch or overlap. */
>>  static inline int range_compare(Range *a, Range *b)
>>  {
>> -    /* Zero a->end is 2**64, and therefore not less than any b->begin */
>> -    if (a->end && a->end < b->begin) {
>> +    /* Careful, avoid wraparound */
>> +    if (b->lob && b->lob - 1 > a->upb) {
>>          return -1;
>>      }
>> -    if (b->end && a->begin > b->end) {
>> +    if (a->lob && a->lob - 1 > b->upb) {
>>          return 1;
>>      }
>>      return 0;
>
> It looks like previously, an empty range was considered
> overlapping any other range: a->begin and a->end are 0.
>
> After this change, IIUC it is smaller than any other range,
> which seems a bit arbitrary (why not greater?),
> except for another empty range, for which it is
> considered overlapping.
>
> I think it's unlikely to break anything but might be
> worth changing to match previous semantics.

It can't break anything because the only caller asserts "no empty
ranges".  I'll explain this in the commit message.

I can also make function comment cover empty ranges explicitly.  Would
"unspecified result" be okay with you?