[Qemu-devel] [PATCH] translate-all: use bitmap helpers for PageDesc's bitmap

[Qemu-devel] [PATCH] translate-all: use bitmap helpers for PageDesc's bitmap

[Emilio G. Cota]

Note that this test
	if (b & ((1 << len) - 1))
can be simplified to
	if (b & 1)
, since we know that iff the first bit of a tb is set,
all other bits from that tb are set too.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 translate-all.c | 39 +++++----------------------------------
 1 file changed, 5 insertions(+), 34 deletions(-)

diff --git a/translate-all.c b/translate-all.c
index 11763c6..749d0f6 100644
--- a/translate-all.c
+++ b/translate-all.c
@@ -59,6 +59,7 @@
 
 #include "exec/cputlb.h"
 #include "translate-all.h"
+#include "qemu/bitmap.h"
 #include "qemu/timer.h"
 
 //#define DEBUG_TB_INVALIDATE
@@ -79,7 +80,7 @@ typedef struct PageDesc {
     /* in order to optimize self modifying code, we count the number
        of lookups we do to a given page to use a bitmap */
     unsigned int code_write_count;
-    uint8_t *code_bitmap;
+    unsigned long *code_bitmap;
 #if defined(CONFIG_USER_ONLY)
     unsigned long flags;
 #endif
@@ -978,39 +979,12 @@ void tb_phys_invalidate(TranslationBlock *tb, tb_page_addr_t page_addr)
     tcg_ctx.tb_ctx.tb_phys_invalidate_count++;
 }
 
-static inline void set_bits(uint8_t *tab, int start, int len)
-{
-    int end, mask, end1;
-
-    end = start + len;
-    tab += start >> 3;
-    mask = 0xff << (start & 7);
-    if ((start & ~7) == (end & ~7)) {
-        if (start < end) {
-            mask &= ~(0xff << (end & 7));
-            *tab |= mask;
-        }
-    } else {
-        *tab++ |= mask;
-        start = (start + 8) & ~7;
-        end1 = end & ~7;
-        while (start < end1) {
-            *tab++ = 0xff;
-            start += 8;
-        }
-        if (start < end) {
-            mask = ~(0xff << (end & 7));
-            *tab |= mask;
-        }
-    }
-}
-
 static void build_page_bitmap(PageDesc *p)
 {
     int n, tb_start, tb_end;
     TranslationBlock *tb;
 
-    p->code_bitmap = g_malloc0(TARGET_PAGE_SIZE / 8);
+    p->code_bitmap = bitmap_new(TARGET_PAGE_SIZE);
 
     tb = p->first_tb;
     while (tb != NULL) {
@@ -1029,7 +1003,7 @@ static void build_page_bitmap(PageDesc *p)
             tb_start = 0;
             tb_end = ((tb->pc + tb->size) & ~TARGET_PAGE_MASK);
         }
-        set_bits(p->code_bitmap, tb_start, tb_end - tb_start);
+        bitmap_set(p->code_bitmap, tb_start, tb_end - tb_start);
         tb = tb->page_next[n];
     }
 }
@@ -1219,7 +1193,6 @@ void tb_invalidate_phys_page_range(tb_page_addr_t start, tb_page_addr_t end,
 void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
 {
     PageDesc *p;
-    int offset, b;
 
 #if 0
     if (1) {
@@ -1235,9 +1208,7 @@ void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
         return;
     }
     if (p->code_bitmap) {
-        offset = start & ~TARGET_PAGE_MASK;
-        b = p->code_bitmap[offset >> 3] >> (offset & 7);
-        if (b & ((1 << len) - 1)) {
+        if (test_bit(start & ~TARGET_PAGE_MASK, p->code_bitmap)) {
             goto do_invalidate;
         }
     } else {
-- 
1.9.1

Re: [Qemu-devel] [PATCH] translate-all: use bitmap helpers for PageDesc's bitmap

[Emilio G. Cota]

On Sat, Mar 21, 2015 at 02:25:42 -0400, Emilio G. Cota wrote:
> Note that this test
> 	if (b & ((1 << len) - 1))
> can be simplified to
> 	if (b & 1)
> , since we know that iff the first bit of a tb is set,
> all other bits from that tb are set too.
> 
> Signed-off-by: Emilio G. Cota <cota@braap.org>
> ---
>  translate-all.c | 39 +++++----------------------------------
>  1 file changed, 5 insertions(+), 34 deletions(-)

*ping*
  http://patchwork.ozlabs.org/patch/452907/

Any takers? get_maintainer.pl doesn't suggest anybody to send this to.

This gets rid of an unnecessary (and hairy) function: bitmap_set().
I even took the time to double-check with a test program that
this function is indeed equivalent to bitmap_set().

Thanks,

		Emilio

Re: [Qemu-devel] [PATCH] translate-all: use bitmap helpers for PageDesc's bitmap

[Paolo Bonzini]

On 03/04/2015 02:08, Emilio G. Cota wrote:
> On Sat, Mar 21, 2015 at 02:25:42 -0400, Emilio G. Cota wrote:
>> Note that this test
>> 	if (b & ((1 << len) - 1))
>> can be simplified to
>> 	if (b & 1)
>> , since we know that iff the first bit of a tb is set,
>> all other bits from that tb are set too.
>>
>> Signed-off-by: Emilio G. Cota <cota@braap.org>
>> ---
>>  translate-all.c | 39 +++++----------------------------------
>>  1 file changed, 5 insertions(+), 34 deletions(-)
> 
> *ping*
>   http://patchwork.ozlabs.org/patch/452907/
> 
> Any takers? get_maintainer.pl doesn't suggest anybody to send this to.
> 
> This gets rid of an unnecessary (and hairy) function: bitmap_set().
> I even took the time to double-check with a test program that
> this function is indeed equivalent to bitmap_set().

Nobody was looking because of the hard freeze, I guess.  The patch looks
good.

Paolo

Re: [Qemu-devel] [PATCH] translate-all: use bitmap helpers for PageDesc's bitmap

[Paolo Bonzini]

On 21/03/2015 07:25, Emilio G. Cota wrote:
> Note that this test
> 	if (b & ((1 << len) - 1))
> can be simplified to
> 	if (b & 1)
> , since we know that iff the first bit of a tb is set,
> all other bits from that tb are set too.

I don't think this optimization is valid, unfortunately.  It is possible
that say a tb starts at 0x12340001 and tb_invalidate_phys_page_fast is
called for the range starting at 0x12340000 and ending at 0x12340003.

In this case you need the full test that was used before.

Therefore, I am unqueuing this patch.  Sorry. :)

Paolo

> Signed-off-by: Emilio G. Cota <cota@braap.org>
> ---
>  translate-all.c | 39 +++++----------------------------------
>  1 file changed, 5 insertions(+), 34 deletions(-)
> 
> diff --git a/translate-all.c b/translate-all.c
> index 11763c6..749d0f6 100644
> --- a/translate-all.c
> +++ b/translate-all.c
> @@ -59,6 +59,7 @@
>  
>  #include "exec/cputlb.h"
>  #include "translate-all.h"
> +#include "qemu/bitmap.h"
>  #include "qemu/timer.h"
>  
>  //#define DEBUG_TB_INVALIDATE
> @@ -79,7 +80,7 @@ typedef struct PageDesc {
>      /* in order to optimize self modifying code, we count the number
>         of lookups we do to a given page to use a bitmap */
>      unsigned int code_write_count;
> -    uint8_t *code_bitmap;
> +    unsigned long *code_bitmap;
>  #if defined(CONFIG_USER_ONLY)
>      unsigned long flags;
>  #endif
> @@ -978,39 +979,12 @@ void tb_phys_invalidate(TranslationBlock *tb, tb_page_addr_t page_addr)
>      tcg_ctx.tb_ctx.tb_phys_invalidate_count++;
>  }
>  
> -static inline void set_bits(uint8_t *tab, int start, int len)
> -{
> -    int end, mask, end1;
> -
> -    end = start + len;
> -    tab += start >> 3;
> -    mask = 0xff << (start & 7);
> -    if ((start & ~7) == (end & ~7)) {
> -        if (start < end) {
> -            mask &= ~(0xff << (end & 7));
> -            *tab |= mask;
> -        }
> -    } else {
> -        *tab++ |= mask;
> -        start = (start + 8) & ~7;
> -        end1 = end & ~7;
> -        while (start < end1) {
> -            *tab++ = 0xff;
> -            start += 8;
> -        }
> -        if (start < end) {
> -            mask = ~(0xff << (end & 7));
> -            *tab |= mask;
> -        }
> -    }
> -}
> -
>  static void build_page_bitmap(PageDesc *p)
>  {
>      int n, tb_start, tb_end;
>      TranslationBlock *tb;
>  
> -    p->code_bitmap = g_malloc0(TARGET_PAGE_SIZE / 8);
> +    p->code_bitmap = bitmap_new(TARGET_PAGE_SIZE);
>  
>      tb = p->first_tb;
>      while (tb != NULL) {
> @@ -1029,7 +1003,7 @@ static void build_page_bitmap(PageDesc *p)
>              tb_start = 0;
>              tb_end = ((tb->pc + tb->size) & ~TARGET_PAGE_MASK);
>          }
> -        set_bits(p->code_bitmap, tb_start, tb_end - tb_start);
> +        bitmap_set(p->code_bitmap, tb_start, tb_end - tb_start);
>          tb = tb->page_next[n];
>      }
>  }
> @@ -1219,7 +1193,6 @@ void tb_invalidate_phys_page_range(tb_page_addr_t start, tb_page_addr_t end,
>  void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
>  {
>      PageDesc *p;
> -    int offset, b;
>  
>  #if 0
>      if (1) {
> @@ -1235,9 +1208,7 @@ void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
>          return;
>      }
>      if (p->code_bitmap) {
> -        offset = start & ~TARGET_PAGE_MASK;
> -        b = p->code_bitmap[offset >> 3] >> (offset & 7);
> -        if (b & ((1 << len) - 1)) {
> +        if (test_bit(start & ~TARGET_PAGE_MASK, p->code_bitmap)) {
>              goto do_invalidate;
>          }
>      } else {
> 

Re: [Qemu-devel] [PATCH] translate-all: use bitmap helpers for PageDesc's bitmap

[Emilio G. Cota]

On Wed, Apr 22, 2015 at 15:13:05 +0200, Paolo Bonzini wrote:
> On 21/03/2015 07:25, Emilio G. Cota wrote:
> > Note that this test
> > 	if (b & ((1 << len) - 1))
> > can be simplified to
> > 	if (b & 1)
> > , since we know that iff the first bit of a tb is set,
> > all other bits from that tb are set too.
> 
> I don't think this optimization is valid, unfortunately.  It is possible
> that say a tb starts at 0x12340001 and tb_invalidate_phys_page_fast is
> called for the range starting at 0x12340000 and ending at 0x12340003.
> 
> In this case you need the full test that was used before.

Good catch, haven't seen this in my tests but it could possibly happen.

v2 coming up.

Thanks,

		Emilio

[Qemu-devel] [PATCH v2] translate-all: use bitmap helpers for PageDesc's bitmap

[Emilio G. Cota]

Here we have an open-coded byte-based bitmap implementation.
Get rid of it since there's a ulong-based implementation to be
used by all code.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 translate-all.c | 40 +++++++---------------------------------
 1 file changed, 7 insertions(+), 33 deletions(-)

diff --git a/translate-all.c b/translate-all.c
index acf792c..9592a3b 100644
--- a/translate-all.c
+++ b/translate-all.c
@@ -59,6 +59,7 @@
 
 #include "exec/cputlb.h"
 #include "translate-all.h"
+#include "qemu/bitmap.h"
 #include "qemu/timer.h"
 
 //#define DEBUG_TB_INVALIDATE
@@ -79,7 +80,7 @@ typedef struct PageDesc {
     /* in order to optimize self modifying code, we count the number
        of lookups we do to a given page to use a bitmap */
     unsigned int code_write_count;
-    uint8_t *code_bitmap;
+    unsigned long *code_bitmap;
 #if defined(CONFIG_USER_ONLY)
     unsigned long flags;
 #endif
@@ -964,39 +965,12 @@ void tb_phys_invalidate(TranslationBlock *tb, tb_page_addr_t page_addr)
     tcg_ctx.tb_ctx.tb_phys_invalidate_count++;
 }
 
-static inline void set_bits(uint8_t *tab, int start, int len)
-{
-    int end, mask, end1;
-
-    end = start + len;
-    tab += start >> 3;
-    mask = 0xff << (start & 7);
-    if ((start & ~7) == (end & ~7)) {
-        if (start < end) {
-            mask &= ~(0xff << (end & 7));
-            *tab |= mask;
-        }
-    } else {
-        *tab++ |= mask;
-        start = (start + 8) & ~7;
-        end1 = end & ~7;
-        while (start < end1) {
-            *tab++ = 0xff;
-            start += 8;
-        }
-        if (start < end) {
-            mask = ~(0xff << (end & 7));
-            *tab |= mask;
-        }
-    }
-}
-
 static void build_page_bitmap(PageDesc *p)
 {
     int n, tb_start, tb_end;
     TranslationBlock *tb;
 
-    p->code_bitmap = g_malloc0(TARGET_PAGE_SIZE / 8);
+    p->code_bitmap = bitmap_new(TARGET_PAGE_SIZE);
 
     tb = p->first_tb;
     while (tb != NULL) {
@@ -1015,7 +989,7 @@ static void build_page_bitmap(PageDesc *p)
             tb_start = 0;
             tb_end = ((tb->pc + tb->size) & ~TARGET_PAGE_MASK);
         }
-        set_bits(p->code_bitmap, tb_start, tb_end - tb_start);
+        bitmap_set(p->code_bitmap, tb_start, tb_end - tb_start);
         tb = tb->page_next[n];
     }
 }
@@ -1205,7 +1179,6 @@ void tb_invalidate_phys_page_range(tb_page_addr_t start, tb_page_addr_t end,
 void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
 {
     PageDesc *p;
-    int offset, b;
 
 #if 0
     if (1) {
@@ -1221,8 +1194,9 @@ void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
         return;
     }
     if (p->code_bitmap) {
-        offset = start & ~TARGET_PAGE_MASK;
-        b = p->code_bitmap[offset >> 3] >> (offset & 7);
+        int nr = start & ~TARGET_PAGE_MASK;
+        int b = p->code_bitmap[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG - 1));
+
         if (b & ((1 << len) - 1)) {
             goto do_invalidate;
         }
-- 
1.9.1

Re: [Qemu-devel] [PATCH v2] translate-all: use bitmap helpers for PageDesc's bitmap

[Paolo Bonzini]

On 22/04/2015 18:53, Emilio G. Cota wrote:
> Here we have an open-coded byte-based bitmap implementation.
> Get rid of it since there's a ulong-based implementation to be
> used by all code.
> 
> Signed-off-by: Emilio G. Cota <cota@braap.org>
> ---
>  translate-all.c | 40 +++++++---------------------------------
>  1 file changed, 7 insertions(+), 33 deletions(-)
> 
> diff --git a/translate-all.c b/translate-all.c
> index acf792c..9592a3b 100644
> --- a/translate-all.c
> +++ b/translate-all.c
> @@ -59,6 +59,7 @@
>  
>  #include "exec/cputlb.h"
>  #include "translate-all.h"
> +#include "qemu/bitmap.h"
>  #include "qemu/timer.h"
>  
>  //#define DEBUG_TB_INVALIDATE
> @@ -79,7 +80,7 @@ typedef struct PageDesc {
>      /* in order to optimize self modifying code, we count the number
>         of lookups we do to a given page to use a bitmap */
>      unsigned int code_write_count;
> -    uint8_t *code_bitmap;
> +    unsigned long *code_bitmap;
>  #if defined(CONFIG_USER_ONLY)
>      unsigned long flags;
>  #endif
> @@ -964,39 +965,12 @@ void tb_phys_invalidate(TranslationBlock *tb, tb_page_addr_t page_addr)
>      tcg_ctx.tb_ctx.tb_phys_invalidate_count++;
>  }
>  
> -static inline void set_bits(uint8_t *tab, int start, int len)
> -{
> -    int end, mask, end1;
> -
> -    end = start + len;
> -    tab += start >> 3;
> -    mask = 0xff << (start & 7);
> -    if ((start & ~7) == (end & ~7)) {
> -        if (start < end) {
> -            mask &= ~(0xff << (end & 7));
> -            *tab |= mask;
> -        }
> -    } else {
> -        *tab++ |= mask;
> -        start = (start + 8) & ~7;
> -        end1 = end & ~7;
> -        while (start < end1) {
> -            *tab++ = 0xff;
> -            start += 8;
> -        }
> -        if (start < end) {
> -            mask = ~(0xff << (end & 7));
> -            *tab |= mask;
> -        }
> -    }
> -}
> -
>  static void build_page_bitmap(PageDesc *p)
>  {
>      int n, tb_start, tb_end;
>      TranslationBlock *tb;
>  
> -    p->code_bitmap = g_malloc0(TARGET_PAGE_SIZE / 8);
> +    p->code_bitmap = bitmap_new(TARGET_PAGE_SIZE);
>  
>      tb = p->first_tb;
>      while (tb != NULL) {
> @@ -1015,7 +989,7 @@ static void build_page_bitmap(PageDesc *p)
>              tb_start = 0;
>              tb_end = ((tb->pc + tb->size) & ~TARGET_PAGE_MASK);
>          }
> -        set_bits(p->code_bitmap, tb_start, tb_end - tb_start);
> +        bitmap_set(p->code_bitmap, tb_start, tb_end - tb_start);
>          tb = tb->page_next[n];
>      }
>  }
> @@ -1205,7 +1179,6 @@ void tb_invalidate_phys_page_range(tb_page_addr_t start, tb_page_addr_t end,
>  void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
>  {
>      PageDesc *p;
> -    int offset, b;
>  
>  #if 0
>      if (1) {
> @@ -1221,8 +1194,9 @@ void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
>          return;
>      }
>      if (p->code_bitmap) {
> -        offset = start & ~TARGET_PAGE_MASK;
> -        b = p->code_bitmap[offset >> 3] >> (offset & 7);
> +        int nr = start & ~TARGET_PAGE_MASK;

This should be unsigned, otherwise the compiler might not make
BIT_WORD(nr) a simple right shift (maybe it can see that nr > 0 thanks
to the AND, but in principle x / 32 is not the same as x >> 5 if x is
signed).

> +        int b = p->code_bitmap[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG - 1));

And this should be unsigned long.

Otherwise looks good.

Paolo

> +
>          if (b & ((1 << len) - 1)) {
>              goto do_invalidate;
>          }
> 

Re: [Qemu-devel] [PATCH v2] translate-all: use bitmap helpers for PageDesc's bitmap

[Emilio G. Cota]

On Wed, Apr 22, 2015 at 22:30:23 +0200, Paolo Bonzini wrote:
> On 22/04/2015 18:53, Emilio G. Cota wrote:
> > @@ -1221,8 +1194,9 @@ void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
> >          return;
> >      }
> >      if (p->code_bitmap) {
> > -        offset = start & ~TARGET_PAGE_MASK;
> > -        b = p->code_bitmap[offset >> 3] >> (offset & 7);
> > +        int nr = start & ~TARGET_PAGE_MASK;
> 
> This should be unsigned, otherwise the compiler might not make
> BIT_WORD(nr) a simple right shift (maybe it can see that nr > 0 thanks
> to the AND, but in principle x / 32 is not the same as x >> 5 if x is
> signed).

OK. Note that all bit{map,ops} helpers take a long as the bit position,
and then do BIT_WORD() on it--I was following that convention wrt sign.

> > +        int b = p->code_bitmap[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG - 1));
> 
> And this should be unsigned long.

Used an int because we only care about the least significant bits (len <= 8):

> >          if (b & ((1 << len) - 1)) {
> >              goto do_invalidate;
> >          }

But yes, an unsigned long here is more appropriate.

Thanks,

		Emilio

[Qemu-devel] [PATCH v3] translate-all: use bitmap helpers for PageDesc's bitmap

[Emilio G. Cota]

Here we have an open-coded byte-based bitmap implementation.
Get rid of it since there's a ulong-based implementation to be
used by all code.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 translate-all.c | 42 +++++++++---------------------------------
 1 file changed, 9 insertions(+), 33 deletions(-)

diff --git a/translate-all.c b/translate-all.c
index acf792c..0004d70 100644
--- a/translate-all.c
+++ b/translate-all.c
@@ -59,6 +59,7 @@
 
 #include "exec/cputlb.h"
 #include "translate-all.h"
+#include "qemu/bitmap.h"
 #include "qemu/timer.h"
 
 //#define DEBUG_TB_INVALIDATE
@@ -79,7 +80,7 @@ typedef struct PageDesc {
     /* in order to optimize self modifying code, we count the number
        of lookups we do to a given page to use a bitmap */
     unsigned int code_write_count;
-    uint8_t *code_bitmap;
+    unsigned long *code_bitmap;
 #if defined(CONFIG_USER_ONLY)
     unsigned long flags;
 #endif
@@ -964,39 +965,12 @@ void tb_phys_invalidate(TranslationBlock *tb, tb_page_addr_t page_addr)
     tcg_ctx.tb_ctx.tb_phys_invalidate_count++;
 }
 
-static inline void set_bits(uint8_t *tab, int start, int len)
-{
-    int end, mask, end1;
-
-    end = start + len;
-    tab += start >> 3;
-    mask = 0xff << (start & 7);
-    if ((start & ~7) == (end & ~7)) {
-        if (start < end) {
-            mask &= ~(0xff << (end & 7));
-            *tab |= mask;
-        }
-    } else {
-        *tab++ |= mask;
-        start = (start + 8) & ~7;
-        end1 = end & ~7;
-        while (start < end1) {
-            *tab++ = 0xff;
-            start += 8;
-        }
-        if (start < end) {
-            mask = ~(0xff << (end & 7));
-            *tab |= mask;
-        }
-    }
-}
-
 static void build_page_bitmap(PageDesc *p)
 {
     int n, tb_start, tb_end;
     TranslationBlock *tb;
 
-    p->code_bitmap = g_malloc0(TARGET_PAGE_SIZE / 8);
+    p->code_bitmap = bitmap_new(TARGET_PAGE_SIZE);
 
     tb = p->first_tb;
     while (tb != NULL) {
@@ -1015,7 +989,7 @@ static void build_page_bitmap(PageDesc *p)
             tb_start = 0;
             tb_end = ((tb->pc + tb->size) & ~TARGET_PAGE_MASK);
         }
-        set_bits(p->code_bitmap, tb_start, tb_end - tb_start);
+        bitmap_set(p->code_bitmap, tb_start, tb_end - tb_start);
         tb = tb->page_next[n];
     }
 }
@@ -1205,7 +1179,6 @@ void tb_invalidate_phys_page_range(tb_page_addr_t start, tb_page_addr_t end,
 void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
 {
     PageDesc *p;
-    int offset, b;
 
 #if 0
     if (1) {
@@ -1221,8 +1194,11 @@ void tb_invalidate_phys_page_fast(tb_page_addr_t start, int len)
         return;
     }
     if (p->code_bitmap) {
-        offset = start & ~TARGET_PAGE_MASK;
-        b = p->code_bitmap[offset >> 3] >> (offset & 7);
+        unsigned int nr;
+        unsigned long b;
+
+        nr = start & ~TARGET_PAGE_MASK;
+        b = p->code_bitmap[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG - 1));
         if (b & ((1 << len) - 1)) {
             goto do_invalidate;
         }
-- 
1.9.1