Patchwork Memory API bugfix - abolish addrrrange_end()

login
register
mail settings
Submitter David Gibson
Date Oct. 12, 2011, 2:37 a.m.
Message ID <1318387026-21569-1-git-send-email-david@gibson.dropbear.id.au>
Download mbox | patch
Permalink /patch/119104/
State New
Headers show

Comments

David Gibson - Oct. 12, 2011, 2:37 a.m.
The memory API currently manipulates address range start and size values
as signed integers.  Because memory ranges with size INT64_MAX are very
common, we must be careful to to trigger integer overflows.  I already
fixed such an integer overflow bug in commit
d2963631dd54ddf0f46c151b7e3013e39bb78d3b, but there are more.

In particular, intermediate steps mean that ranges with size INT64_MAX and
non-zero start are often constructed.  This means that simply computing a
range's end address, as in addrrange_end(), could trigger a signed integer
overflow.  Since the behaviour of signed integer overflow in C is
undefined, this means that *every* usage of addrrange_end() is a bug.

This patch, therefore, replaces every usage of addrange_end() with
arithmetic constructed so as not to cause an overflow.  This fixes real
bugs that have bitten us with upcoming PCI support for the pseries machine.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
 memory.c |   35 ++++++++++++++++++++---------------
 1 files changed, 20 insertions(+), 15 deletions(-)
Avi Kivity - Oct. 16, 2011, 9:56 a.m.
On 10/12/2011 04:37 AM, David Gibson wrote:
> The memory API currently manipulates address range start and size values
> as signed integers.  Because memory ranges with size INT64_MAX are very
> common, we must be careful to to trigger integer overflows.  I already
> fixed such an integer overflow bug in commit
> d2963631dd54ddf0f46c151b7e3013e39bb78d3b, but there are more.
>
> In particular, intermediate steps mean that ranges with size INT64_MAX and
> non-zero start are often constructed.  This means that simply computing a
> range's end address, as in addrrange_end(), could trigger a signed integer
> overflow.  Since the behaviour of signed integer overflow in C is
> undefined, this means that *every* usage of addrrange_end() is a bug.
>
> This patch, therefore, replaces every usage of addrange_end() with
> arithmetic constructed so as not to cause an overflow.  This fixes real
> bugs that have bitten us with upcoming PCI support for the pseries machine.
>
> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
> ---
>  memory.c |   35 ++++++++++++++++++++---------------
>  1 files changed, 20 insertions(+), 15 deletions(-)
>
> diff --git a/memory.c b/memory.c
> index f46e626..6bf9ba5 100644
> --- a/memory.c
> +++ b/memory.c
> @@ -26,6 +26,9 @@ typedef struct AddrRange AddrRange;
>   * Note using signed integers limits us to physical addresses at most
>   * 63 bits wide.  They are needed for negative offsetting in aliases
>   * (large MemoryRegion::alias_offset).
> + *
> + * BEWARE: ranges of sizes INT64_MAX are common, so any arithmetic on
> + * ranges *must* be careful to avoid integer overflow
>   */
>  struct AddrRange {
>      int64_t start;
> @@ -42,11 +45,6 @@ static bool addrrange_equal(AddrRange r1, AddrRange r2)
>      return r1.start == r2.start && r1.size == r2.size;
>  }
>  
> -static int64_t addrrange_end(AddrRange r)
> -{
> -    return r.start + r.size;
> -}
> -
>  static AddrRange addrrange_shift(AddrRange range, int64_t delta)
>  {
>      range.start += delta;
> @@ -61,10 +59,13 @@ static bool addrrange_intersects(AddrRange r1, AddrRange r2)
>  
>  static AddrRange addrrange_intersection(AddrRange r1, AddrRange r2)
>  {
> -    int64_t start = MAX(r1.start, r2.start);
> -    /* off-by-one arithmetic to prevent overflow */
> -    int64_t end = MIN(addrrange_end(r1) - 1, addrrange_end(r2) - 1);
> -    return addrrange_make(start, end - start + 1);
> +    if (r1.start <= r2.start) {
> +        return addrrange_make(r2.start,
> +                              MIN(r2.size, r1.size - (r2.start - r1.start)));
> +    } else {
> +        return addrrange_make(r1.start,
> +                              MIN(r1.size, r2.size - (r1.start - r2.start)));
> +    }
>  }
>  

This is pretty ugly.

>  struct CoalescedMemoryRange {
> @@ -201,7 +202,8 @@ static void flatview_destroy(FlatView *view)
>  
>  static bool can_merge(FlatRange *r1, FlatRange *r2)
>  {
> -    return addrrange_end(r1->addr) == r2->addr.start
> +    assert (r1->addr.start < r2->addr.start);

So is this, to a lesser extent.

Let me see if I can work up a synthetic int128 type.
David Gibson - Oct. 16, 2011, 11:40 a.m.
On Sun, Oct 16, 2011 at 11:56:03AM +0200, Avi Kivity wrote:
> On 10/12/2011 04:37 AM, David Gibson wrote:
[snip]
> >  static AddrRange addrrange_intersection(AddrRange r1, AddrRange r2)
> >  {
> > -    int64_t start = MAX(r1.start, r2.start);
> > -    /* off-by-one arithmetic to prevent overflow */
> > -    int64_t end = MIN(addrrange_end(r1) - 1, addrrange_end(r2) - 1);
> > -    return addrrange_make(start, end - start + 1);
> > +    if (r1.start <= r2.start) {
> > +        return addrrange_make(r2.start,
> > +                              MIN(r2.size, r1.size - (r2.start - r1.start)));
> > +    } else {
> > +        return addrrange_make(r1.start,
> > +                              MIN(r1.size, r2.size - (r1.start - r2.start)));
> > +    }
> >  }
> >  
> 
> This is pretty ugly.

A little, but it's correct...

> >  struct CoalescedMemoryRange {
> > @@ -201,7 +202,8 @@ static void flatview_destroy(FlatView *view)
> >  
> >  static bool can_merge(FlatRange *r1, FlatRange *r2)
> >  {
> > -    return addrrange_end(r1->addr) == r2->addr.start
> > +    assert (r1->addr.start < r2->addr.start);
> 
> So is this, to a lesser extent.

Well, the assert is optional; I basically just put that in to document
the assumptions going into this function.

> Let me see if I can work up a synthetic int128 type.

So.. you think replacing every single basic arithmetic operations with
calls to implement the synthetic type, _and_ imposing the resulting
overhead is _less_ ugly than some slightly fiddly re-ordering of
operations?  Seriously?
Avi Kivity - Oct. 16, 2011, 12:35 p.m.
On 10/16/2011 01:40 PM, David Gibson wrote:
> > Let me see if I can work up a synthetic int128 type.
>
> So.. you think replacing every single basic arithmetic operations with
> calls to implement the synthetic type, _and_ imposing the resulting
> overhead is _less_ ugly than some slightly fiddly re-ordering of
> operations?  Seriously?
>

In terms of how the code looks, it's seriously more ugly (see the
patches I sent out).  Conceptually it's cleaner, since we're not dodging
the issue that we need to deal with a full 64-bit domain.

But my main concern is maintainability.  The 64-bit blanket is to short,
if we keep pulling it in various directions we'll just expose ourselves
in new ways.

The overhead is negligible.  This code comes nowhere near any fast path.
David Gibson - Oct. 17, 2011, 5:31 a.m.
On Sun, Oct 16, 2011 at 02:35:37PM +0200, Avi Kivity wrote:
> On 10/16/2011 01:40 PM, David Gibson wrote:
> > > Let me see if I can work up a synthetic int128 type.
> >
> > So.. you think replacing every single basic arithmetic operations with
> > calls to implement the synthetic type, _and_ imposing the resulting
> > overhead is _less_ ugly than some slightly fiddly re-ordering of
> > operations?  Seriously?
> >
> 
> In terms of how the code looks, it's seriously more ugly (see the
> patches I sent out).  Conceptually it's cleaner, since we're not dodging
> the issue that we need to deal with a full 64-bit domain.

We don't have to dodge that issue.  I know how to remove the
requirement for intermediate negative values, I just haven't made up a
patch yet.  With that we can change to uint64 and cover the full 64
bit range.  In fact I think I can make it so that size==0 represents
size=2^64 and even handle the full 64-bit, inclusive range properly.

> But my main concern is maintainability.  The 64-bit blanket is to short,
> if we keep pulling it in various directions we'll just expose ourselves
> in new ways.

Nonsense, dealing with full X-bit range calculations in X-bit types is
a fairly standard problem.  The kernel does it in VMA handling for
one.  It just requires thinking about overflow cases.

> The overhead is negligible.  This code comes nowhere near any fast path.
Avi Kivity - Oct. 17, 2011, 10:34 a.m.
On 10/17/2011 07:31 AM, David Gibson wrote:
> > 
> > In terms of how the code looks, it's seriously more ugly (see the
> > patches I sent out).  Conceptually it's cleaner, since we're not dodging
> > the issue that we need to deal with a full 64-bit domain.
>
> We don't have to dodge that issue.  I know how to remove the
> requirement for intermediate negative values, I just haven't made up a
> patch yet.  With that we can change to uint64 and cover the full 64
> bit range.  In fact I think I can make it so that size==0 represents
> size=2^64 and even handle the full 64-bit, inclusive range properly.

That means you can't do a real size == 0.

> > But my main concern is maintainability.  The 64-bit blanket is to short,
> > if we keep pulling it in various directions we'll just expose ourselves
> > in new ways.
>
> Nonsense, dealing with full X-bit range calculations in X-bit types is
> a fairly standard problem.  The kernel does it in VMA handling for
> one.  It just requires thinking about overflow cases.

We discovered three bugs already (you found two, and I had one during
development).  Even if it can probably be done with extreme care, but is
it worth spending all that development time on?

I'm not sure there is a parallel with vmas, since we're offsetting in
both the positive and negative directions.
David Gibson - Oct. 18, 2011, 1:38 a.m.
On Mon, Oct 17, 2011 at 12:34:19PM +0200, Avi Kivity wrote:
> On 10/17/2011 07:31 AM, David Gibson wrote:
> > > 
> > > In terms of how the code looks, it's seriously more ugly (see the
> > > patches I sent out).  Conceptually it's cleaner, since we're not dodging
> > > the issue that we need to deal with a full 64-bit domain.
> >
> > We don't have to dodge that issue.  I know how to remove the
> > requirement for intermediate negative values, I just haven't made up a
> > patch yet.  With that we can change to uint64 and cover the full 64
> > bit range.  In fact I think I can make it so that size==0 represents
> > size=2^64 and even handle the full 64-bit, inclusive range properly.
> 
> That means you can't do a real size == 0.

Yeah... a memory range with size 0 has no effect by definition, I
think we can do without it.

> > > But my main concern is maintainability.  The 64-bit blanket is to short,
> > > if we keep pulling it in various directions we'll just expose ourselves
> > > in new ways.
> >
> > Nonsense, dealing with full X-bit range calculations in X-bit types is
> > a fairly standard problem.  The kernel does it in VMA handling for
> > one.  It just requires thinking about overflow cases.
> 
> We discovered three bugs already (you found two, and I had one during
> development).  Even if it can probably be done with extreme care, but is
> it worth spending all that development time on?
> 
> I'm not sure there is a parallel with vmas, since we're offsetting in
> both the positive and negative directions.

I think the so-called "negative offsetting" is just an artifact of our
implementation.  I don't see that it's any different from having a VMA
whose file offset is larger than its memory address.
Avi Kivity - Oct. 18, 2011, 9:49 a.m.
On 10/18/2011 03:38 AM, David Gibson wrote:
> On Mon, Oct 17, 2011 at 12:34:19PM +0200, Avi Kivity wrote:
> > On 10/17/2011 07:31 AM, David Gibson wrote:
> > > > 
> > > > In terms of how the code looks, it's seriously more ugly (see the
> > > > patches I sent out).  Conceptually it's cleaner, since we're not dodging
> > > > the issue that we need to deal with a full 64-bit domain.
> > >
> > > We don't have to dodge that issue.  I know how to remove the
> > > requirement for intermediate negative values, I just haven't made up a
> > > patch yet.  With that we can change to uint64 and cover the full 64
> > > bit range.  In fact I think I can make it so that size==0 represents
> > > size=2^64 and even handle the full 64-bit, inclusive range properly.
> > 
> > That means you can't do a real size == 0.
>
> Yeah... a memory range with size 0 has no effect by definition, I
> think we can do without it.

How do we make sure all callers know this?

> > > > But my main concern is maintainability.  The 64-bit blanket is to short,
> > > > if we keep pulling it in various directions we'll just expose ourselves
> > > > in new ways.
> > >
> > > Nonsense, dealing with full X-bit range calculations in X-bit types is
> > > a fairly standard problem.  The kernel does it in VMA handling for
> > > one.  It just requires thinking about overflow cases.
> > 
> > We discovered three bugs already (you found two, and I had one during
> > development).  Even if it can probably be done with extreme care, but is
> > it worth spending all that development time on?
> > 
> > I'm not sure there is a parallel with vmas, since we're offsetting in
> > both the positive and negative directions.
>
> I think the so-called "negative offsetting" is just an artifact of our
> implementation.  I don't see that it's any different from having a VMA
> whose file offset is larger than its memory address.
>

Consider the vga window at 0xa0000 pointing into the framebuffer at
alias_offset 0x1a0000.  To the system, it looks like a copy of the
framebuffer starts at -0x1000000, becomes visible 0x1a0000 bytes later
(at 0xa0000), then becomes invisible again at 0xa8000.

Yes, it's an artifact, but I don't want to spend too much time worrying
about it, if I can throw a few more bits at the problem.  The API is too
central to make a case by case analysis of where things can go wrong, it
needs to be robust.

Patch

diff --git a/memory.c b/memory.c
index f46e626..6bf9ba5 100644
--- a/memory.c
+++ b/memory.c
@@ -26,6 +26,9 @@  typedef struct AddrRange AddrRange;
  * Note using signed integers limits us to physical addresses at most
  * 63 bits wide.  They are needed for negative offsetting in aliases
  * (large MemoryRegion::alias_offset).
+ *
+ * BEWARE: ranges of sizes INT64_MAX are common, so any arithmetic on
+ * ranges *must* be careful to avoid integer overflow
  */
 struct AddrRange {
     int64_t start;
@@ -42,11 +45,6 @@  static bool addrrange_equal(AddrRange r1, AddrRange r2)
     return r1.start == r2.start && r1.size == r2.size;
 }
 
-static int64_t addrrange_end(AddrRange r)
-{
-    return r.start + r.size;
-}
-
 static AddrRange addrrange_shift(AddrRange range, int64_t delta)
 {
     range.start += delta;
@@ -61,10 +59,13 @@  static bool addrrange_intersects(AddrRange r1, AddrRange r2)
 
 static AddrRange addrrange_intersection(AddrRange r1, AddrRange r2)
 {
-    int64_t start = MAX(r1.start, r2.start);
-    /* off-by-one arithmetic to prevent overflow */
-    int64_t end = MIN(addrrange_end(r1) - 1, addrrange_end(r2) - 1);
-    return addrrange_make(start, end - start + 1);
+    if (r1.start <= r2.start) {
+        return addrrange_make(r2.start,
+                              MIN(r2.size, r1.size - (r2.start - r1.start)));
+    } else {
+        return addrrange_make(r1.start,
+                              MIN(r1.size, r2.size - (r1.start - r2.start)));
+    }
 }
 
 struct CoalescedMemoryRange {
@@ -201,7 +202,8 @@  static void flatview_destroy(FlatView *view)
 
 static bool can_merge(FlatRange *r1, FlatRange *r2)
 {
-    return addrrange_end(r1->addr) == r2->addr.start
+    assert (r1->addr.start < r2->addr.start);
+    return ((r2->addr.start - r1->addr.start) == r1->addr.size)
         && r1->mr == r2->mr
         && r1->offset_in_region + r1->addr.size == r2->offset_in_region
         && r1->dirty_log_mask == r2->dirty_log_mask
@@ -535,11 +537,14 @@  static void render_memory_region(FlatView *view,
 
     /* Render the region itself into any gaps left by the current view. */
     for (i = 0; i < view->nr && remain; ++i) {
-        if (base >= addrrange_end(view->ranges[i].addr)) {
+        AddrRange *vrange = &view->ranges[i].addr;
+
+        if ((base > vrange->start)
+            && ((base - vrange->start) >= vrange->size)) {
             continue;
         }
-        if (base < view->ranges[i].addr.start) {
-            now = MIN(remain, view->ranges[i].addr.start - base);
+        if (base < vrange->start) {
+            now = MIN(remain, vrange->start - base);
             fr.mr = mr;
             fr.offset_in_region = offset_in_region;
             fr.addr = addrrange_make(base, now);
@@ -552,8 +557,8 @@  static void render_memory_region(FlatView *view,
             offset_in_region += now;
             remain -= now;
         }
-        if (base == view->ranges[i].addr.start) {
-            now = MIN(remain, view->ranges[i].addr.size);
+        if (base == vrange->start) {
+            now = MIN(remain, vrange->size);
             base += now;
             offset_in_region += now;
             remain -= now;