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

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

[Markus Armbruster]

Reviving a series from 2015 I dropped on the floor.  My apologies.

v2:
* PATCH 1 (was PATCH 2): rebased, R-bys kept
* PATCH 2 (was PATCH 1): rebased, commit message updated, legibility
  improved, R-bys dropped
* PATCH 3: new

Markus Armbruster (3):
  xbzrle: Drop unused cache_resize()
  host-utils: Proactively fix pow2floor(), switch to unsigned
  host-utils: Simplify pow2ceil()

 include/qemu/host-utils.h | 44 ++++++++++++++++++++++---------------
 migration/page_cache.c    | 56 -----------------------------------------------
 migration/page_cache.h    | 11 ----------
 3 files changed, 26 insertions(+), 85 deletions(-)

-- 
2.7.5

[Qemu-devel] [PATCH v2 1/3] xbzrle: Drop unused cache_resize()

[Markus Armbruster]

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

Cc: Juan Quintela <quintela@redhat.com>
Cc: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
Reviewed-by: Amit Shah <amit.shah@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 migration/page_cache.c | 56 --------------------------------------------------
 migration/page_cache.h | 11 ----------
 2 files changed, 67 deletions(-)

diff --git a/migration/page_cache.c b/migration/page_cache.c
index 5f85787..ba984c4 100644
--- a/migration/page_cache.c
+++ b/migration/page_cache.c
@@ -178,59 +178,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;
-}
diff --git a/migration/page_cache.h b/migration/page_cache.h
index 10ed532..4fadd0c 100644
--- a/migration/page_cache.h
+++ b/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
-- 
2.7.5

Re: [Qemu-devel] [PATCH v2 1/3] xbzrle: Drop unused cache_resize()

[Juan Quintela]

Markus Armbruster <armbru@redhat.com> wrote:
> Unused since commit fd8cec XBZRLE: Fix qemu crash when resize the
> xbzrle cache.
>
> Cc: Juan Quintela <quintela@redhat.com>
> Cc: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
> Reviewed-by: Eric Blake <eblake@redhat.com>
> Reviewed-by: Amit Shah <amit.shah@redhat.com>
> Signed-off-by: Markus Armbruster <armbru@redhat.com>

Reviewed-by: Juan Quintela <quintela@redhat.com>

Included for next PULL.  thanks.

> ---
>  migration/page_cache.c | 56 --------------------------------------------------
>  migration/page_cache.h | 11 ----------
>  2 files changed, 67 deletions(-)
>
> diff --git a/migration/page_cache.c b/migration/page_cache.c
> index 5f85787..ba984c4 100644
> --- a/migration/page_cache.c
> +++ b/migration/page_cache.c
> @@ -178,59 +178,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;
> -}
> diff --git a/migration/page_cache.h b/migration/page_cache.h
> index 10ed532..4fadd0c 100644
> --- a/migration/page_cache.h
> +++ b/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

[Qemu-devel] [PATCH v2 2/3] host-utils: 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.

  What sort of works is passing *unsigned* arguments >= 2^63.  The
  implicit conversion to signed is implementation defined, but
  commonly yields the (negative) two's complement.  pow2floor() then
  returns -2^63.  Callers that convert that back to unsigned get the
  correct value 2^63.

* 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 from int64_t to uint64_t and amending the contract to
map zero to zero.

Callers are fine with that:

* memory_access_size()

  This function makes no sense unless the argument is positive and the
  return value fits into int.

* raw_refresh_limits()

  Passes an int between 1 and BDRV_REQUEST_MAX_BYTES.

* iscsi_refresh_limits()

  Passes an integer between 0 and INT_MAX, converts the result to
  uint32_t.  Passing zero would be undefined behavior, but commonly
  yield zero.  The patch gives us the zero without the undefined
  behavior.

* cache_init()

  Passes a positive int64_t argument.

* xbzrle_cache_resize()

  Passes a positive int64_t argument (>= TARGET_PAGE_SIZE, actually).

* spapr_node0_size()

  Passes a positive uint64_t argument, and converts the result to
  hwaddr, i.e. uint64_t.

* spapr_populate_memory()

  Passes a positive hwaddr argument, and converts the result to
  hwaddr.

Cc: Juan Quintela <quintela@redhat.com>
Cc: Dr. David Alan Gilbert <dgilbert@redhat.com>
Cc: Eric Blake <eblake@redhat.com>
Cc: Peter Maydell <peter.maydell@linaro.org>
Cc: Alexey Kardashevskiy <aik@ozlabs.ru>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 include/qemu/host-utils.h | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h
index 95cf4f4..6c6005f 100644
--- a/include/qemu/host-utils.h
+++ b/include/qemu/host-utils.h
@@ -369,13 +369,16 @@ static inline bool is_power_of_2(uint64_t value)
     return !(value & (value - 1));
 }
 
-/* round down to the nearest power of 2*/
-static inline int64_t pow2floor(int64_t value)
+/**
+ * Return @value rounded down to the nearest power of two or zero.
+ */
+static inline uint64_t pow2floor(uint64_t value)
 {
-    if (!is_power_of_2(value)) {
-        value = 0x8000000000000000ULL >> clz64(value);
+    if (!value) {
+        /* Avoid undefined shift by 64 */
+        return 0;
     }
-    return value;
+    return 0x8000000000000000ull >> clz64(value);
 }
 
 /* round up to the nearest power of 2 (0 if overflow) */
-- 
2.7.5

Re: [Qemu-devel] [PATCH v2 2/3] host-utils: Proactively fix pow2floor(), switch to unsigned

[Eric Blake]

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

On 07/27/2017 04:46 AM, Markus Armbruster 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.

Mail quoting gives an interesting rendering of this line; I had to do a
double-take to realize your text is correct.

> 
> Fix by switching from int64_t to uint64_t and amending the contract to
> map zero to zero.

I like it.  And your proof of auditing callers helps.

> ---
>  include/qemu/host-utils.h | 13 ++++++++-----
>  1 file changed, 8 insertions(+), 5 deletions(-)
> 
> diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h
> index 95cf4f4..6c6005f 100644
> --- a/include/qemu/host-utils.h
> +++ b/include/qemu/host-utils.h
> @@ -369,13 +369,16 @@ static inline bool is_power_of_2(uint64_t value)
>      return !(value & (value - 1));
>  }
>  
> -/* round down to the nearest power of 2*/
> -static inline int64_t pow2floor(int64_t value)
> +/**
> + * Return @value rounded down to the nearest power of two or zero.
> + */
> +static inline uint64_t pow2floor(uint64_t value)
>  {
> -    if (!is_power_of_2(value)) {
> -        value = 0x8000000000000000ULL >> clz64(value);
> +    if (!value) {
> +        /* Avoid undefined shift by 64 */
> +        return 0;
>      }
> -    return value;
> +    return 0x8000000000000000ull >> clz64(value);
>  }

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

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org


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

[Qemu-devel] [PATCH v2 3/3] host-utils: Simplify pow2ceil()

[Markus Armbruster]

Cc: Radim Krčmář <rkrcmar@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 include/qemu/host-utils.h | 21 +++++++++++++--------
 1 file changed, 13 insertions(+), 8 deletions(-)

diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h
index 6c6005f..5ac621c 100644
--- a/include/qemu/host-utils.h
+++ b/include/qemu/host-utils.h
@@ -381,18 +381,23 @@ static inline uint64_t pow2floor(uint64_t value)
     return 0x8000000000000000ull >> clz64(value);
 }
 
-/* round up to the nearest power of 2 (0 if overflow) */
+/*
+ * Return @value rounded up to the nearest power of two modulo 2^64.
+ * This is *zero* for @value > 2^63, so be careful.
+ */
 static inline uint64_t pow2ceil(uint64_t value)
 {
-    uint8_t nlz = clz64(value);
+    int n = clz64(value - 1);
 
-    if (is_power_of_2(value)) {
-        return value;
+    if (!n) {
+        /*
+         * @value - 1 has no leading zeroes, thus @value - 1 >= 2^63
+         * Therefore, either @value == 0 or @value > 2^63.
+         * If it's 0, return 1, else return 0.
+         */
+        return !value;
     }
-    if (!nlz) {
-        return 0;
-    }
-    return 1ULL << (64 - nlz);
+    return 0x8000000000000000ull >> (n - 1);
 }
 
 /**
-- 
2.7.5

Re: [Qemu-devel] [PATCH v2 3/3] host-utils: Simplify pow2ceil()

[Eric Blake]

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

On 07/27/2017 04:46 AM, Markus Armbruster wrote:
> Cc: Radim Krčmář <rkrcmar@redhat.com>
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  include/qemu/host-utils.h | 21 +++++++++++++--------
>  1 file changed, 13 insertions(+), 8 deletions(-)
> 

>  
> -/* round up to the nearest power of 2 (0 if overflow) */
> +/*
> + * Return @value rounded up to the nearest power of two modulo 2^64.
> + * This is *zero* for @value > 2^63, so be careful.
> + */
>  static inline uint64_t pow2ceil(uint64_t value)
>  {
> -    uint8_t nlz = clz64(value);
> +    int n = clz64(value - 1);
>  
> -    if (is_power_of_2(value)) {
> -        return value;
> +    if (!n) {
> +        /*
> +         * @value - 1 has no leading zeroes, thus @value - 1 >= 2^63
> +         * Therefore, either @value == 0 or @value > 2^63.
> +         * If it's 0, return 1, else return 0.
> +         */
> +        return !value;

Tricky, but the comment is worth its weight in gold.

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

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org


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