[Qemu-devel] [PATCH 0/2] Proactive pow2floor() fix, and dead code removal

[Qemu-devel] [PATCH 0/2] Proactive pow2floor() fix, and dead code removal

[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()

 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(-)

-- 
1.9.3

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

[Markus Armbruster]

The function's stated contract is simple enough: "round down to the
nearest power of 2".  Suggests the domain is the representable numbers
>= 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.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 include/qemu-common.h |  6 ++++--
 util/cutils.c         | 11 +++++------
 2 files changed, 9 insertions(+), 8 deletions(-)

diff --git a/include/qemu-common.h b/include/qemu-common.h
index 644b46d..f3ede45 100644
--- a/include/qemu-common.h
+++ b/include/qemu-common.h
@@ -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"
 
diff --git a/util/cutils.c b/util/cutils.c
index dbe7412..4b8c5be 100644
--- a/util/cutils.c
+++ b/util/cutils.c
@@ -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);
 }
 
 /*
-- 
1.9.3

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

[Dr. David Alan Gilbert]

* Markus Armbruster (armbru@redhat.com) wrote:
> The function's stated contract is simple enough: "round down to the
> nearest power of 2".  Suggests the domain is the representable numbers
> >= 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.
> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  include/qemu-common.h |  6 ++++--
>  util/cutils.c         | 11 +++++------
>  2 files changed, 9 insertions(+), 8 deletions(-)
> 
> diff --git a/include/qemu-common.h b/include/qemu-common.h
> index 644b46d..f3ede45 100644
> --- a/include/qemu-common.h
> +++ b/include/qemu-common.h
> @@ -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"
>  
> diff --git a/util/cutils.c b/util/cutils.c
> index dbe7412..4b8c5be 100644
> --- a/util/cutils.c
> +++ b/util/cutils.c
> @@ -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);
>  }

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

Reviewed-by:  Dr. David Alan Gilbert <dgilbert@redhat.com>

Dave

>  
>  /*
> -- 
> 1.9.3
> 
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

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

[Markus Armbruster]

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

Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 include/migration/page_cache.h | 11 ---------
 page_cache.c                   | 56 ------------------------------------------
 2 files changed, 67 deletions(-)

diff --git a/include/migration/page_cache.h b/include/migration/page_cache.h
index 10ed532..4fadd0c 100644
--- a/include/migration/page_cache.h
+++ b/include/migration/page_cache.h
@@ -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
diff --git a/page_cache.c b/page_cache.c
index cf8878d..a00a3d9 100644
--- a/page_cache.c
+++ b/page_cache.c
@@ -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;
-}
-- 
1.9.3

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

[Dr. David Alan Gilbert]

* Markus Armbruster (armbru@redhat.com) wrote:
> Unused since commit fd8cec XBZRLE: Fix qemu crash when resize the
> xbzrle cache.
> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>

Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>

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

> ---
>  include/migration/page_cache.h | 11 ---------
>  page_cache.c                   | 56 ------------------------------------------
>  2 files changed, 67 deletions(-)
> 
> diff --git a/include/migration/page_cache.h b/include/migration/page_cache.h
> index 10ed532..4fadd0c 100644
> --- a/include/migration/page_cache.h
> +++ b/include/migration/page_cache.h
> @@ -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
> diff --git a/page_cache.c b/page_cache.c
> index cf8878d..a00a3d9 100644
> --- a/page_cache.c
> +++ b/page_cache.c
> @@ -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;
> -}
> -- 
> 1.9.3
> 
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

Re: [Qemu-devel] [PATCH 0/2] Proactive pow2floor() fix, and dead code removal

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 770 bytes --]

On 02/25/2015 07:06 AM, Markus Armbruster wrote:
> 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()

Reviewed-by: Eric Blake <eblake@redhat.com>

> 
>  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(-)
> 

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH 0/2] Proactive pow2floor() fix, and dead code removal

[Amit Shah]

On (Wed) 25 Feb 2015 [15:06:30], Markus Armbruster wrote:
> 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()

Reviewed-by: Amit Shah <amit.shah@redhat.com>

		Amit

Re: [Qemu-devel] [PATCH 0/2] Proactive pow2floor() fix, and dead code removal

[Markus Armbruster]

Markus Armbruster <armbru@redhat.com> writes:

> 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().