| Message ID | 1315983769-8287-1-git-send-email-david@gibson.dropbear.id.au |
|---|---|
| State | New |
| Headers | show |
On 09/14/2011 10:02 AM, David Gibson wrote: > It is quite common to have a MemoryRegion with size of INT64_MAX. > When processing alias regions in render_memory_region() it's quite > easy to find a case where it will construct a temporary AddrRange with > a non-zero start, and size still of INT64_MAX. When means attempting > to compute the end of such a range as start + size will result in > signed integer overflow. > > This integer overflow means that addrrange_intersects() can > incorrectly report regions as not intersecting when they do. For > example consider the case of address ranges {0x10000000000, > 0x7fffffffffffffff} and {0x10010000000, 0x10000000} where the second > is in fact included completely in the first. Good catch, thanks for digging this out. > This patch rearranges addrrange_intersects() to avoid the integer > overflow, correcting this behaviour. I expect that the bad behaviour can still be triggered, for example by pointing aliases towards the end of very large regions. Not that I expect this to occur in practice. I think we should move towards using __int128 internally. Is there any relevant host which does not support __int128? Meanwhile, applied to memory/core, and will request a pull shortly.
On 09/14/2011 11:23 AM, Avi Kivity wrote: > > I think we should move towards using __int128 internally. Is there > any relevant host which does not support __int128? Crap, it's not even supported on i386.
On Wed, Sep 14, 2011 at 11:23:25AM +0300, Avi Kivity wrote: > On 09/14/2011 10:02 AM, David Gibson wrote: > >It is quite common to have a MemoryRegion with size of INT64_MAX. > >When processing alias regions in render_memory_region() it's quite > >easy to find a case where it will construct a temporary AddrRange with > >a non-zero start, and size still of INT64_MAX. When means attempting > >to compute the end of such a range as start + size will result in > >signed integer overflow. > > > >This integer overflow means that addrrange_intersects() can > >incorrectly report regions as not intersecting when they do. For > >example consider the case of address ranges {0x10000000000, > >0x7fffffffffffffff} and {0x10010000000, 0x10000000} where the second > >is in fact included completely in the first. > > Good catch, thanks for digging this out. > > >This patch rearranges addrrange_intersects() to avoid the integer > >overflow, correcting this behaviour. > > I expect that the bad behaviour can still be triggered, for example > by pointing aliases towards the end of very large regions. Not that > I expect this to occur in practice. Well.. I'm pretty sure that particular case can no longer be triggered. But there may be other integer overflow bugs in this code, though I didn't spot them at a glance. > I think we should move towards using __int128 internally. Is there > any relevant host which does not support __int128? Hrm, using a barely supported integer type I'd never previously heard of seems sub-optimal. With appropriate care it ought to be possible to do all the necessary calculations correctly in 64 bits, even if we need a few explicit "if (a + b) < a" tests in some places. > Meanwhile, applied to memory/core, and will request a pull shortly. >
On Thu, Sep 15, 2011 at 12:34:31PM +1000, David Gibson wrote: > On Wed, Sep 14, 2011 at 11:23:25AM +0300, Avi Kivity wrote: > > On 09/14/2011 10:02 AM, David Gibson wrote: > > >It is quite common to have a MemoryRegion with size of INT64_MAX. > > >When processing alias regions in render_memory_region() it's quite > > >easy to find a case where it will construct a temporary AddrRange with > > >a non-zero start, and size still of INT64_MAX. When means attempting > > >to compute the end of such a range as start + size will result in > > >signed integer overflow. > > > > > >This integer overflow means that addrrange_intersects() can > > >incorrectly report regions as not intersecting when they do. For > > >example consider the case of address ranges {0x10000000000, > > >0x7fffffffffffffff} and {0x10010000000, 0x10000000} where the second > > >is in fact included completely in the first. > > > > Good catch, thanks for digging this out. > > > > >This patch rearranges addrrange_intersects() to avoid the integer > > >overflow, correcting this behaviour. > > > > I expect that the bad behaviour can still be triggered, for example > > by pointing aliases towards the end of very large regions. Not that > > I expect this to occur in practice. > > Well.. I'm pretty sure that particular case can no longer be > triggered. But there may be other integer overflow bugs in this code, > though I didn't spot them at a glance. Actually, there definitely are. addrrange_end() should probably be redefined as the inclusive end, rather than the exclusive end, and computed as: (start + size - 1) < start ? INT64_MAX : start + size - 1 Hrm, except that that doesn't handle zero size ranges. And gets a bit weird for INT64_MAX sized regions. Hrm, yeah, these really should be changed to use unsigneds.
On 09/15/2011 05:58 AM, David Gibson wrote: > > Well.. I'm pretty sure that particular case can no longer be > > triggered. But there may be other integer overflow bugs in this code, > > though I didn't spot them at a glance. > > Actually, there definitely are. addrrange_end() should probably be > redefined as the inclusive end, rather than the exclusive end, and > computed as: > > (start + size - 1)< start ? INT64_MAX : start + size - 1 > > Hrm, except that that doesn't handle zero size ranges. And gets a bit > weird for INT64_MAX sized regions. > > Hrm, yeah, these really should be changed to use unsigneds. > Unsigneds don't work because we sometimes subtract values and get into the negative area, due to aliases. We're using values that are close to the end of the 63 or 64 bit range and playing with them. Overflow is always close and we'll always be able to find a way to defeat the code (even if it doesn't occur in practice). I'm tempted to declare that the memory API supports only 60 bits of address space (and s/INT64_MAX/MEMORY_REGION_SIZE_MAX/), that gives us a few levels of wild offsetting before we get confused.
On 09/15/2011 04:34 AM, David Gibson wrote:
> explicit "if (a + b)< a" tests in some places.
Please wrap these in a macro, since the addition has to be done in an
unsigned type. Otherwise overflow is undefined.
Paolo
On 09/15/2011 10:38 AM, Paolo Bonzini wrote: > On 09/15/2011 04:34 AM, David Gibson wrote: >> explicit "if (a + b)< a" tests in some places. > > Please wrap these in a macro, since the addition has to be done in an > unsigned type. Otherwise overflow is undefined. It doesn't help if the overflow is defined but produces an incorrect result. The fact is we need a 64+N bit datatype, where N is the nesting level of MemoryRegions (including aliases). Each nesting level can overflow a bit. Right now the only viable options seems to be #define 64 60, but I'll be happy to consider others.
On Thu, Sep 15, 2011 at 10:28:42AM +0300, Avi Kivity wrote: > On 09/15/2011 05:58 AM, David Gibson wrote: > >> Well.. I'm pretty sure that particular case can no longer be > >> triggered. But there may be other integer overflow bugs in this code, > >> though I didn't spot them at a glance. > > > >Actually, there definitely are. addrrange_end() should probably be > >redefined as the inclusive end, rather than the exclusive end, and > >computed as: > > > > (start + size - 1)< start ? INT64_MAX : start + size - 1 > > > >Hrm, except that that doesn't handle zero size ranges. And gets a bit > >weird for INT64_MAX sized regions. > > > >Hrm, yeah, these really should be changed to use unsigneds. > > > > Unsigneds don't work because we sometimes subtract values and get > into the negative area, due to aliases. I realise that, but I'm fairly confident the order of calculations can be adjusted to cope with those cases, just as we can cope with the overflow cases with care. Remember that because unsigned overflow is defined, and we can use that in some cases. > We're using values that are close to the end of the 63 or 64 bit > range and playing with them. Overflow is always close and we'll > always be able to find a way to defeat the code (even if it doesn't > occur in practice). I'm tempted to declare that the memory API > supports only 60 bits of address space (and > s/INT64_MAX/MEMORY_REGION_SIZE_MAX/), that gives us a few levels of > wild offsetting before we get confused. There is something to be said for that. Although many systems have theoretical 64-bit addressing, on powerpc at least, the biggest actually implemented physical address bus I'm aware of is under 50 bits. Of course, there could be some highly sparse intermediate bus addressing schemes which screw that up.
diff --git a/memory.c b/memory.c index 57f0fa4..101b67c 100644 --- a/memory.c +++ b/memory.c @@ -55,8 +55,8 @@ static AddrRange addrrange_shift(AddrRange range, int64_t delta) static bool addrrange_intersects(AddrRange r1, AddrRange r2) { - return (r1.start >= r2.start && r1.start < r2.start + r2.size) - || (r2.start >= r1.start && r2.start < r1.start + r1.size); + return (r1.start >= r2.start && (r1.start - r2.start) < r2.size) + || (r2.start >= r1.start && (r2.start - r1.start) < r1.size); } static AddrRange addrrange_intersection(AddrRange r1, AddrRange r2)
It is quite common to have a MemoryRegion with size of INT64_MAX. When processing alias regions in render_memory_region() it's quite easy to find a case where it will construct a temporary AddrRange with a non-zero start, and size still of INT64_MAX. When means attempting to compute the end of such a range as start + size will result in signed integer overflow. This integer overflow means that addrrange_intersects() can incorrectly report regions as not intersecting when they do. For example consider the case of address ranges {0x10000000000, 0x7fffffffffffffff} and {0x10010000000, 0x10000000} where the second is in fact included completely in the first. This patch rearranges addrrange_intersects() to avoid the integer overflow, correcting this behaviour. Signed-off-by: David Gibson <david@gibson.dropbear.id.au> --- memory.c | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-)