[Qemu-devel] [PATCH] memory: use signed arithmetic

[Qemu-devel] [PATCH] memory: use signed arithmetic

[Avi Kivity]

When trying to map an alias of a ram region, where the alias starts at
address A and we map it into address B, and A > B, we had an arithmetic
underflow.  Because we use unsigned arithmetic, the underflow converted
into a large number which failed addrrange_intersects() tests.

The concrete example which triggered this was cirrus vga mapping
the framebuffer at offsets 0xc0000-0xc7fff (relative to the start of
the framebuffer) into offsets 0xa0000 (relative to system addres space
start).

With our favorite analogy of a windowing system, this is equivalent to
dragging a subwindow off the left edge of the screen, and failing to clip
it into its parent window which is on screen.

Fix by switching to signed arithmetic.

Signed-off-by: Avi Kivity <avi@redhat.com>
---
 exec.c   |    2 +-
 memory.c |   18 +++++++++---------
 2 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/exec.c b/exec.c
index 476b507..751fd89 100644
--- a/exec.c
+++ b/exec.c
@@ -3818,7 +3818,7 @@ static void io_mem_init(void)
 static void memory_map_init(void)
 {
     system_memory = qemu_malloc(sizeof(*system_memory));
-    memory_region_init(system_memory, "system", UINT64_MAX);
+    memory_region_init(system_memory, "system", INT64_MAX);
     set_system_memory_map(system_memory);
 }
 
diff --git a/memory.c b/memory.c
index 5f20320..8ef6497 100644
--- a/memory.c
+++ b/memory.c
@@ -23,11 +23,11 @@ unsigned memory_region_transaction_depth = 0;
 typedef struct AddrRange AddrRange;
 
 struct AddrRange {
-    uint64_t start;
-    uint64_t size;
+    int64_t start;
+    int64_t size;
 };
 
-static AddrRange addrrange_make(uint64_t start, uint64_t size)
+static AddrRange addrrange_make(int64_t start, int64_t size)
 {
     return (AddrRange) { start, size };
 }
@@ -37,7 +37,7 @@ static bool addrrange_equal(AddrRange r1, AddrRange r2)
     return r1.start == r2.start && r1.size == r2.size;
 }
 
-static uint64_t addrrange_end(AddrRange r)
+static int64_t addrrange_end(AddrRange r)
 {
     return r.start + r.size;
 }
@@ -56,9 +56,9 @@ static bool addrrange_intersects(AddrRange r1, AddrRange r2)
 
 static AddrRange addrrange_intersection(AddrRange r1, AddrRange r2)
 {
-    uint64_t start = MAX(r1.start, r2.start);
+    int64_t start = MAX(r1.start, r2.start);
     /* off-by-one arithmetic to prevent overflow */
-    uint64_t end = MIN(addrrange_end(r1) - 1, addrrange_end(r2) - 1);
+    int64_t end = MIN(addrrange_end(r1) - 1, addrrange_end(r2) - 1);
     return addrrange_make(start, end - start + 1);
 }
 
@@ -411,8 +411,8 @@ static void render_memory_region(FlatView *view,
     MemoryRegion *subregion;
     unsigned i;
     target_phys_addr_t offset_in_region;
-    uint64_t remain;
-    uint64_t now;
+    int64_t remain;
+    int64_t now;
     FlatRange fr;
     AddrRange tmp;
 
@@ -486,7 +486,7 @@ static FlatView generate_memory_topology(MemoryRegion *mr)
 
     flatview_init(&view);
 
-    render_memory_region(&view, mr, 0, addrrange_make(0, UINT64_MAX));
+    render_memory_region(&view, mr, 0, addrrange_make(0, INT64_MAX));
     flatview_simplify(&view);
 
     return view;
-- 
1.7.5.3

Re: [Qemu-devel] [PATCH] memory: use signed arithmetic

[malc]

On Tue, 2 Aug 2011, Avi Kivity wrote:

> When trying to map an alias of a ram region, where the alias starts at
> address A and we map it into address B, and A > B, we had an arithmetic
> underflow.  Because we use unsigned arithmetic, the underflow converted
> into a large number which failed addrrange_intersects() tests.
> 
> The concrete example which triggered this was cirrus vga mapping
> the framebuffer at offsets 0xc0000-0xc7fff (relative to the start of
> the framebuffer) into offsets 0xa0000 (relative to system addres space
> start).
> 
> With our favorite analogy of a windowing system, this is equivalent to
> dragging a subwindow off the left edge of the screen, and failing to clip
> it into its parent window which is on screen.
> 
> Fix by switching to signed arithmetic.

http://stackoverflow.com/questions/3679047/integer-overflow-in-c-standards-and-compilers

In other words UB land

[..snip..]

-- 
mailto:av1474@comtv.ru

Re: [Qemu-devel] [PATCH] memory: use signed arithmetic

[Avi Kivity]

On 08/03/2011 12:15 AM, malc wrote:
> On Tue, 2 Aug 2011, Avi Kivity wrote:
>
> >  When trying to map an alias of a ram region, where the alias starts at
> >  address A and we map it into address B, and A>  B, we had an arithmetic
> >  underflow.  Because we use unsigned arithmetic, the underflow converted
> >  into a large number which failed addrrange_intersects() tests.
> >
> >  The concrete example which triggered this was cirrus vga mapping
> >  the framebuffer at offsets 0xc0000-0xc7fff (relative to the start of
> >  the framebuffer) into offsets 0xa0000 (relative to system addres space
> >  start).
> >
> >  With our favorite analogy of a windowing system, this is equivalent to
> >  dragging a subwindow off the left edge of the screen, and failing to clip
> >  it into its parent window which is on screen.
> >
> >  Fix by switching to signed arithmetic.
>
> http://stackoverflow.com/questions/3679047/integer-overflow-in-c-standards-and-compilers
>
> In other words UB land
>

No UB land.

Previously, we did something like 0x1000U - 0x2000U = 0xFFFF0000U, later 
checking that 0xFFFF0000U < 0U and failing.

Now, we do something like 0x1000 - 0x2000 = -0x1000, later checking that 
-0x1000 < 0, and suceeding.

In no case was there undefined behaviour involved.  Unsigned underflow 
is defined (and produced bad results for this case), Signed underflow 
isn't defined (but doesn't occur in this case).

-- 
I have a truly marvellous patch that fixes the bug which this
signature is too narrow to contain.

Re: [Qemu-devel] [PATCH] memory: use signed arithmetic

[Richard Henderson]

On 08/02/2011 01:50 PM, Avi Kivity wrote:
>  struct AddrRange {
> -    uint64_t start;
> -    uint64_t size;
> +    int64_t start;
> +    int64_t size;

I'm must say I'm not keen on this.  My primary objection is that
a "range" can no longer properly represent the entire address space.
Or, indeed, anything in the second half of it.

It sounds like your problem would be better solved by re-arranging
things such that you perform X < Y comparisons rather than DELTA < 0.



r~

Re: [Qemu-devel] [PATCH] memory: use signed arithmetic

[Avi Kivity]

On 08/03/2011 12:59 AM, Richard Henderson wrote:
> On 08/02/2011 01:50 PM, Avi Kivity wrote:
> >   struct AddrRange {
> >  -    uint64_t start;
> >  -    uint64_t size;
> >  +    int64_t start;
> >  +    int64_t size;
>
> I'm must say I'm not keen on this.  My primary objection is that
> a "range" can no longer properly represent the entire address space.
> Or, indeed, anything in the second half of it.

I don't think there's any cpu which has a real 64-bit physical address 
space?  Don't they all truncate it?

> It sounds like your problem would be better solved by re-arranging
> things such that you perform X<  Y comparisons rather than DELTA<  0.
>


More like, X + delta < Y + delta, I just get a headache what all those 
deltas mean everywhere.

For reference, the root cause is
static void render_memory_region(FlatView *view,
                                  MemoryRegion *mr,
                                  target_phys_addr_t base,
                                  AddrRange clip)
{
...

     base += mr->addr;

...

     if (mr->alias) {
         base -= mr->alias->addr;
         base -= mr->alias_offset;   // <--- HERE!
         render_memory_region(view, mr->alias, base, clip);
         return;
     }

I could pass alias_offset everywhere and compensate for it.  But 
stealing bit from the address space is easier than adjusting all the 
calculations.

-- 
I have a truly marvellous patch that fixes the bug which this
signature is too narrow to contain.

Re: [Qemu-devel] [PATCH] memory: use signed arithmetic

[Richard Henderson]

On 08/02/2011 03:06 PM, Avi Kivity wrote:
> I don't think there's any cpu which has a real 64-bit physical
> address space? Don't they all truncate it?

I don't know.  You're right that x86_64 does, at 48 bits.
The alpha system I'm trying to emulate does, at 50 bits.

I guess if IBM agrees wrt p-series and z-series emulation, then
I'd be ok, so long as you add a comment above that structure that
says no existing hw implementation actually uses 63 address bits.


r~

Re: [Qemu-devel] [PATCH] memory: use signed arithmetic

[Avi Kivity]

On 08/03/2011 01:15 AM, Richard Henderson wrote:
> On 08/02/2011 03:06 PM, Avi Kivity wrote:
> >  I don't think there's any cpu which has a real 64-bit physical
> >  address space? Don't they all truncate it?
>
> I don't know.  You're right that x86_64 does, at 48 bits.
> The alpha system I'm trying to emulate does, at 50 bits.
>
> I guess if IBM agrees wrt p-series and z-series emulation, then
> I'd be ok, so long as you add a comment above that structure that
> says no existing hw implementation actually uses 63 address bits.

Ben, can you confirm that pseries physical addresses are 63 bits wide or 
smaller?

IIRC zseries has no mmio, and Zettabyte machines are still rare.

-- 
error compiling committee.c: too many arguments to function

Re: [Qemu-devel] [PATCH] memory: use signed arithmetic

[Benjamin Herrenschmidt]

On Wed, 2011-08-03 at 11:26 +0300, Avi Kivity wrote:
> On 08/03/2011 01:15 AM, Richard Henderson wrote:
> > On 08/02/2011 03:06 PM, Avi Kivity wrote:
> > >  I don't think there's any cpu which has a real 64-bit physical
> > >  address space? Don't they all truncate it?
> >
> > I don't know.  You're right that x86_64 does, at 48 bits.
> > The alpha system I'm trying to emulate does, at 50 bits.
> >
> > I guess if IBM agrees wrt p-series and z-series emulation, then
> > I'd be ok, so long as you add a comment above that structure that
> > says no existing hw implementation actually uses 63 address bits.
> 
> Ben, can you confirm that pseries physical addresses are 63 bits wide or 
> smaller?
> 
> IIRC zseries has no mmio, and Zettabyte machines are still rare.

We are fine yes. We might grow to 50 bits but I doubt we'll ever do the
full 64, especially since we have some hard-wired assumptions that in
real mode (MMU off) the top 2 bits are ignored.

Cheers,
Ben.