Re: [Qemu-devel] [PATCH] Memory API bugfix - abolish addrrrange_end()
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 0xa pointing into the framebuffer at alias_offset 0x1a. To the system, it looks like a copy of the framebuffer starts at -0x100, becomes visible 0x1a bytes later (at 0xa), 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. -- I have a truly marvellous patch that fixes the bug which this signature is too narrow to contain.
Re: [Qemu-devel] [PATCH] Memory API bugfix - abolish addrrrange_end()
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. -- error compiling committee.c: too many arguments to function
Re: [Qemu-devel] [PATCH] Memory API bugfix - abolish addrrrange_end()
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. -- David Gibson| I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson
Re: [Qemu-devel] [PATCH] Memory API bugfix - abolish addrrrange_end()
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 da...@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.
--
error compiling committee.c: too many arguments to function
Re: [Qemu-devel] [PATCH] Memory API bugfix - abolish addrrrange_end()
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?
--
David Gibson| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_
| _way_ _around_!
http://www.ozlabs.org/~dgibson
Re: [Qemu-devel] [PATCH] Memory API bugfix - abolish addrrrange_end()
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. -- error compiling committee.c: too many arguments to function
Re: [Qemu-devel] [PATCH] Memory API bugfix - abolish addrrrange_end()
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. -- David Gibson| I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson
[Qemu-devel] [PATCH] Memory API bugfix - abolish addrrrange_end()
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 da...@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)));
+}
}
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;
--
1.7.6.3
