Skip to contentSkip to conversation

Proactive pow2floor() fix, and dead code removal

PATCH In review Markus Armbruster 4 participants 8 messages Feb 25, 2015 – Mar 5, 2015

lore
Share & tools
lore
#0 lore raw

cover Proactive pow2floor() fix, and dead code removal

I propose to route this through the migration tree, because that's where pow2floor() came from, and where the dead code is removed.

Markus Armbruster (2):
cutils: Proactively fix pow2floor(), switch to unsigned
xbzrle: Drop unused cache_resize()

 include/migration/page_cache.h | 11 ---------
 include/qemu-common.h          |  6 +++--
 page_cache.c                   | 56 ------------------------------------------
 util/cutils.c                  | 11 ++++-----
 4 files changed, 9 insertions(+), 75 deletions(-)
Signature · 1 line
1.9.3
#1 lore raw

PATCH 1/2 cutils: Proactively fix pow2floor(), switch to unsigned

The function's stated contract is simple enough: "round down to the nearest power of 2". Suggests the domain is the representable numbers

Quoted 1 line

= 1, because that's the smallest power of two.

The implementation doesn't check for domain errors, but returns garbage instead:

* For negative arguments, pow2floor() returns -2^63, which is not even a power of two, let alone the nearest one.

* For a zero argument, pow2floor() shifts right by 64. Undefined behavior. Common actual behavior is to shift by 0, yielding -2^63.

Fix by switching to unsigned types and amending the contract to map zero to zero.

Callers are fine with that:

* xbzrle_cache_resize()

Passes an int64_t argument >= TARGET_PAGE_SIZE. Thus, the argument value is representable in uint64_t, and not zero. The result is converted back to int64_t. Safe, because int64_t can represent the value.

No change.

* cache_init()

Likewise, except > 0 instead of >= TARGET_PAGE_SIZE. No change.

* cache_resize()

Unused since commit fd8cec9. Before, its caller passed an int64_t argumet >= 1.

* spapr_node0_size() and spapr_populate_memory()

Argument comes from numa_info[].node_mem. This is uint64_t. Before this patch, we convert it to int64_t for pow2floor(), and convert its result to hwaddr, i.e. back to uint64_t. Not obviously safe. The patch gets rid of the dubious conversions.

The patch also gets rid of undefined behavior on zero, and maps zero to zero instead. Beats mapping it to 2^63, which is what we commonly get from the undefined behavior before the patch.

Thus, the patch is a strict improvement here.

---
 include/qemu-common.h |  6 ++++--
 util/cutils.c         | 11 +++++------
 2 files changed, 9 insertions(+), 8 deletions(-)
include/qemu-common.h +4 -2
index 644b46d..f3ede45 100644
@@ -415,8 +415,10 @@ static inline bool is_power_of_2(uint64_t value)
     return !(value & (value - 1));
 }
 
-/* round down to the nearest power of 2*/
-int64_t pow2floor(int64_t value);
+/**
+ * Return @value rounded down to the nearest power of two or zero.
+ */
+uint64_t pow2floor(uint64_t value);
 
 #include "qemu/module.h"
 
util/cutils.c +5 -6
index dbe7412..4b8c5be 100644
@@ -474,13 +474,12 @@ int qemu_parse_fd(const char *param)
     return fd;
 }
 
-/* round down to the nearest power of 2*/
-int64_t pow2floor(int64_t value)
+/**
+ * Return @value rounded down to the nearest power of two or zero.
+ */
+uint64_t pow2floor(uint64_t value)
 {
-    if (!is_power_of_2(value)) {
-        value = 0x8000000000000000ULL >> clz64(value);
-    }
-    return value;
+    return !value ? 0 : 0x8000000000000000ull >> clz64(value);
 }
 
 /*
Signature · 1 line
1.9.3
Reviewed-by on v1 1/2
#2 lore raw

Re: [Qemu-devel] [PATCH 1/2] cutils: Proactively fix pow2floor(), switch to unsigned

Quoted 83 lines · * Markus Armbruster ([email protected]) wrote:

The function's stated contract is simple enough: "round down to the nearest power of 2". Suggests the domain is the representable numbers

Quoted 1 line

= 1, because that's the smallest power of two.

The implementation doesn't check for domain errors, but returns garbage instead:

* For negative arguments, pow2floor() returns -2^63, which is not even a power of two, let alone the nearest one.

* For a zero argument, pow2floor() shifts right by 64. Undefined behavior. Common actual behavior is to shift by 0, yielding -2^63.

Fix by switching to unsigned types and amending the contract to map zero to zero.

Callers are fine with that:

* xbzrle_cache_resize()

Passes an int64_t argument >= TARGET_PAGE_SIZE. Thus, the argument value is representable in uint64_t, and not zero. The result is converted back to int64_t. Safe, because int64_t can represent the value.

No change.

* cache_init()

Likewise, except > 0 instead of >= TARGET_PAGE_SIZE. No change.

* cache_resize()

Unused since commit fd8cec9. Before, its caller passed an int64_t argumet >= 1.

* spapr_node0_size() and spapr_populate_memory()

Argument comes from numa_info[].node_mem. This is uint64_t. Before this patch, we convert it to int64_t for pow2floor(), and convert its result to hwaddr, i.e. back to uint64_t. Not obviously safe. The patch gets rid of the dubious conversions.

The patch also gets rid of undefined behavior on zero, and maps zero to zero instead. Beats mapping it to 2^63, which is what we commonly get from the undefined behavior before the patch.

Thus, the patch is a strict improvement here.

---
 include/qemu-common.h |  6 ++++--
 util/cutils.c         | 11 +++++------
 2 files changed, 9 insertions(+), 8 deletions(-)
include/qemu-common.h +4 -2
index 644b46d..f3ede45 100644
@@ -415,8 +415,10 @@ static inline bool is_power_of_2(uint64_t value)
     return !(value & (value - 1));
 }
 
-/* round down to the nearest power of 2*/
-int64_t pow2floor(int64_t value);
+/**
+ * Return @value rounded down to the nearest power of two or zero.
+ */
+uint64_t pow2floor(uint64_t value);
 
 #include "qemu/module.h"
 
util/cutils.c +1 -2
index dbe7412..4b8c5be 100644
@@ -474,13 +474,12 @@ int qemu_parse_fd(const char *param)
     return fd;
 }
 
-/* round down to the nearest power of 2*/
-int64_t pow2floor(int64_t value)
+/**

util/cutils.c int qemu_parse_fd(const char *param) · line 483

Quoted 10 lines
util/cutils.c +4 -4
+ * Return @value rounded down to the nearest power of two or zero.
+ */
+uint64_t pow2floor(uint64_t value)
 {
-    if (!is_power_of_2(value)) {
-        value = 0x8000000000000000ULL >> clz64(value);
-    }
-    return value;
+    return !value ? 0 : 0x8000000000000000ull >> clz64(value);
 }

Yes (it's odd that clz returns an int rather than unsigned)

Dave

Quoted 6 lines
util/cutils.c +0 -0
 /*
Signature · 1 line
1.9.3

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK

#3 lore raw

PATCH 2/2 xbzrle: Drop unused cache_resize()

In reply to Markus Armbruster

Unused since commit fd8cec XBZRLE: Fix qemu crash when resize the xbzrle cache.

---
 include/migration/page_cache.h | 11 ---------
 page_cache.c                   | 56 ------------------------------------------
 2 files changed, 67 deletions(-)
include/migration/page_cache.h +0 -11
index 10ed532..4fadd0c 100644
@@ -72,15 +72,4 @@ uint8_t *get_cached_data(const PageCache *cache, uint64_t addr);
 int cache_insert(PageCache *cache, uint64_t addr, const uint8_t *pdata,
                  uint64_t current_age);
 
-/**
- * cache_resize: resize the page cache. In case of size reduction the extra
- * pages will be freed
- *
- * Returns -1 on error new cache size on success
- *
- * @cache pointer to the PageCache struct
- * @num_pages: new page cache size (in pages)
- */
-int64_t cache_resize(PageCache *cache, int64_t num_pages);
-
 #endif
page_cache.c +0 -56

59 lines not on this page · raw message

Signature · 1 line
1.9.3
Reviewed-by on v1 2/2
#4 lore raw

Re: [Qemu-devel] [PATCH 2/2] xbzrle: Drop unused cache_resize()

Quoted 4 lines · * Markus Armbruster ([email protected]) wrote:

Unused since commit fd8cec XBZRLE: Fix qemu crash when resize the xbzrle cache.

Yes, I guess Orit had intended this page_cache to be more general than xbzrle (which is why I hadn't moved it into migration/) so perhaps a user from the future would want that resize, but it's probably best to remove it for now.

Dave

Quoted 93 lines
---
 include/migration/page_cache.h | 11 ---------
 page_cache.c                   | 56 ------------------------------------------
 2 files changed, 67 deletions(-)
include/migration/page_cache.h +0 -11
index 10ed532..4fadd0c 100644
@@ -72,15 +72,4 @@ uint8_t *get_cached_data(const PageCache *cache, uint64_t addr);
 int cache_insert(PageCache *cache, uint64_t addr, const uint8_t *pdata,
                  uint64_t current_age);
 
-/**
- * cache_resize: resize the page cache. In case of size reduction the extra
- * pages will be freed
- *
- * Returns -1 on error new cache size on success
- *
- * @cache pointer to the PageCache struct
- * @num_pages: new page cache size (in pages)
- */
-int64_t cache_resize(PageCache *cache, int64_t num_pages);
-
 #endif
page_cache.c +0 -56
index cf8878d..a00a3d9 100644
@@ -188,59 +188,3 @@ int cache_insert(PageCache *cache, uint64_t addr, const uint8_t *pdata,
 
     return 0;
 }
-
-int64_t cache_resize(PageCache *cache, int64_t new_num_pages)
-{
-    PageCache *new_cache;
-    int64_t i;
-
-    CacheItem *old_it, *new_it;
-
-    g_assert(cache);
-
-    /* cache was not inited */
-    if (cache->page_cache == NULL) {
-        return -1;
-    }
-
-    /* same size */
-    if (pow2floor(new_num_pages) == cache->max_num_items) {
-        return cache->max_num_items;
-    }
-
-    new_cache = cache_init(new_num_pages, cache->page_size);
-    if (!(new_cache)) {
-        DPRINTF("Error creating new cache\n");
-        return -1;
-    }
-
-    /* move all data from old cache */
-    for (i = 0; i < cache->max_num_items; i++) {
-        old_it = &cache->page_cache[i];
-        if (old_it->it_addr != -1) {
-            /* check for collision, if there is, keep MRU page */
-            new_it = cache_get_by_addr(new_cache, old_it->it_addr);
-            if (new_it->it_data && new_it->it_age >= old_it->it_age) {
-                /* keep the MRU page */
-                g_free(old_it->it_data);
-            } else {
-                if (!new_it->it_data) {
-                    new_cache->num_items++;
-                }
-                g_free(new_it->it_data);
-                new_it->it_data = old_it->it_data;
-                new_it->it_age = old_it->it_age;
-                new_it->it_addr = old_it->it_addr;
-            }
-        }
-    }
-
-    g_free(cache->page_cache);
-    cache->page_cache = new_cache->page_cache;
-    cache->max_num_items = new_cache->max_num_items;
-    cache->num_items = new_cache->num_items;
-
-    g_free(new_cache);
-
-    return cache->max_num_items;
-}
Signature · 1 line
1.9.3

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK

Reviewed-by on the v1 series
#5 lore raw
In reply to Markus Armbruster
Quoted 6 lines · Markus Armbruster

I propose to route this through the migration tree, because that's where pow2floor() came from, and where the dead code is removed.

Markus Armbruster (2):
cutils: Proactively fix pow2floor(), switch to unsigned
xbzrle: Drop unused cache_resize()

Quoted 7 lines
 include/migration/page_cache.h | 11 ---------
 include/qemu-common.h          |  6 +++--
 page_cache.c                   | 56 ------------------------------------------
 util/cutils.c                  | 11 ++++-----
 4 files changed, 9 insertions(+), 75 deletions(-)
Signature · 2 lines
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org
Reviewed-by on the v1 series
#6 lore raw
In reply to Markus Armbruster
Quoted 6 lines · Markus Armbruster

I propose to route this through the migration tree, because that's where pow2floor() came from, and where the dead code is removed.

Markus Armbruster (2):
cutils: Proactively fix pow2floor(), switch to unsigned
xbzrle: Drop unused cache_resize()

Amit

#7 lore raw
In reply to Markus Armbruster
Quoted 2 lines · Markus Armbruster

I propose to route this through the migration tree, because that's where pow2floor() came from, and where the dead code is removed.

Self-NAK

There's a simple conflict with a patch from Radim that is in Gerd's spice pull request: "[PULL 3/7] qxl: refactor rounding up to a nearest power of 2".

I intend to rebase this series on top of Gerd's to resolve the conflict, and to clean up some inconsistencies between Radim's pow2ceil() and my pow2floor().