| Message ID | 1318387026-21569-1-git-send-email-david@gibson.dropbear.id.au |
|---|---|
| State | New |
| Headers | show |
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.
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?
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.
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.
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.
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.
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.
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;
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(-)