Skip to contentSkip to conversation

Use ffs in favor of ffsll

PATCH Superseded Jan Kiszka 6 participants 12 messages Jul 1, 2009 – Jul 4, 2009

lore
Share & tools
lore

Jan Kiszka

author
#0 lore raw

PATCH 1/1 Use ffs in favor of ffsll

Not all host platforms support the ll variant. This is not a critical path, so go the easy way.

---

 target-i386/machine.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)
target-i386/machine.c +3 -3
index 259302c..4ab154c 100644
@@ -147,10 +147,10 @@ void cpu_save(QEMUFile *f, void *opaque)
     /* There can only be one pending IRQ set in the bitmap at a time, so try
        to find it and save its number instead (-1 for none). */
     pending_irq = -1;
-    for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
-        bit = ffsll(env->interrupt_bitmap[i]);
+    for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {
+        bit = ffs(((int *)env->interrupt_bitmap)[i]);
         if (bit) {
-            pending_irq = i * 64 + bit - 1;
+            pending_irq = i * 8 * sizeof(int) + bit - 1;
             break;
         }
     }
#1 lore raw
Quoted 10 lines · Jan Kiszka

Not all host platforms support the ll variant. This is not a critical
path, so go the easy way.

- for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
- bit = ffsll(env->interrupt_bitmap[i]);
+ for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {

 +        bit = ffs(((int *)env->interrupt_bitmap)[i]);
         if (bit) {

- pending_irq = i * 64 + bit - 1;
+ pending_irq = i * 8 * sizeof(int) + bit - 1;

I think this will not work on a big endian host.

author
#2 lore raw
Quoted 12 lines · Blue Swirl
Quoted 10 lines · Jan Kiszka

Not all host platforms support the ll variant. This is not a critical
path, so go the easy way.

- for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
- bit = ffsll(env->interrupt_bitmap[i]);
+ for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {

 +        bit = ffs(((int *)env->interrupt_bitmap)[i]);
         if (bit) {

- pending_irq = i * 64 + bit - 1;
+ pending_irq = i * 8 * sizeof(int) + bit - 1;

Quoted 1 line

I think this will not work on a big endian host.

Right, may theoretically bite us once we are able to migrate between kvm and tcg. Will send a better version nevertheless.

Jan

author
#3 lore raw

PATCH v2 1/1 Use ffs in favor of ffsll

Quoted 11 lines · Jan Kiszka
Quoted 10 lines · Blue Swirl
Quoted 9 lines · Jan Kiszka

Not all host platforms support the ll variant. This is not a critical
path, so go the easy way.
- for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
- bit = ffsll(env->interrupt_bitmap[i]);
+ for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {

 +        bit = ffs(((int *)env->interrupt_bitmap)[i]);
         if (bit) {

- pending_irq = i * 64 + bit - 1;
+ pending_irq = i * 8 * sizeof(int) + bit - 1;

Quoted 5 lines
Quoted 1 line

I think this will not work on a big endian host.

Right, may theoretically bite us once we are able to migrate between kvm and tcg. Will send a better version nevertheless.

I decided that a comment should suffice.

-----

Not all host platforms support the ll variant. This is not a critical path, so go the easy way.

---

 target-i386/machine.c |    8 +++++---
 1 files changed, 5 insertions(+), 3 deletions(-)
target-i386/machine.c +5 -3
index 259302c..1a56b3d 100644
@@ -147,10 +147,12 @@ void cpu_save(QEMUFile *f, void *opaque)
     /* There can only be one pending IRQ set in the bitmap at a time, so try
        to find it and save its number instead (-1 for none). */
     pending_irq = -1;
-    for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
-        bit = ffsll(env->interrupt_bitmap[i]);
+    for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {
+        /* Note: This assumes little endian host, which is true in KVM mode.
+           In TCG mode it must be zero anyway. */
+        bit = ffs(((int *)env->interrupt_bitmap)[i]);
         if (bit) {
-            pending_irq = i * 64 + bit - 1;
+            pending_irq = i * 8 * sizeof(int) + bit - 1;
             break;
         }
     }
#4 lore raw
Quoted 8 lines · Jan Kiszka
Quoted 6 lines · Jan Kiszka
Quoted 1 line · Blue Swirl

I think this will not work on a big endian host.

Right, may theoretically bite us once we are able to migrate between kvm and tcg. Will send a better version nevertheless.

target-i386/machine.c void cpu_save(QEMUFile *f, void *opaque) · line 153

Quoted 6 lines
target-i386/machine.c +4 -2
-    for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
-        bit = ffsll(env->interrupt_bitmap[i]);
+    for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {
+        /* Note: This assumes little endian host, which is true in KVM mode.
+           In TCG mode it must be zero anyway. */
+        bit = ffs(((int *)env->interrupt_bitmap)[i]);

ISTR that some PPC hosts support KVM...

-Nathan

author
#5 lore raw
Quoted 7 lines · Nathan Froyd
Quoted 6 lines · Jan Kiszka
Quoted 5 lines · Jan Kiszka
Quoted 1 line · Blue Swirl

I think this will not work on a big endian host.

Right, may theoretically bite us once we are able to migrate between kvm and tcg. Will send a better version nevertheless.

Quoted 9 lines

target-i386/machine.c void cpu_save(QEMUFile *f, void *opaque) · line 153

Quoted 6 lines
target-i386/machine.c +4 -2
-    for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
-        bit = ffsll(env->interrupt_bitmap[i]);
+    for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {
+        /* Note: This assumes little endian host, which is true in KVM mode.
+           In TCG mode it must be zero anyway. */
+        bit = ffs(((int *)env->interrupt_bitmap)[i]);

ISTR that some PPC hosts support KVM...

...but not for x86 guests. :)

Jan

#6 lore raw
In reply to Nathan Froyd
Quoted 9 lines · Nathan Froyd

target-i386/machine.c void cpu_save(QEMUFile *f, void *opaque) · line 153

Quoted 6 lines · Jan Kiszka
target-i386/machine.c +4 -2
-    for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
-        bit = ffsll(env->interrupt_bitmap[i]);
+    for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {
+        /* Note: This assumes little endian host, which is true in KVM mode.
+           In TCG mode it must be zero anyway. */
+        bit = ffs(((int *)env->interrupt_bitmap)[i]);

ISTR that some PPC hosts support KVM...

FWIW, I notice we currently have a qemu_fls() defined in cutils.c, which uses the clz32() defined in host-utils.h.

qemu_ffsll() could be implemented fairly easily in terms of ctz64(), although note that ffsll(n) == (ctz64(n) + 1) % 65.

Cheers,

Signature · 1 line
Stuart Brady
author
#7 lore raw

PATCH 1/1 Use ctz64 in favor of ffsll

Quoted 8 lines · Stuart Brady
Quoted 7 lines · Nathan Froyd
Quoted 6 lines · Jan Kiszka
(quoted diff) +4 -2
-    for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
-        bit = ffsll(env->interrupt_bitmap[i]);
+    for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {
+        /* Note: This assumes little endian host, which is true in KVM mode.
+           In TCG mode it must be zero anyway. */
+        bit = ffs(((int *)env->interrupt_bitmap)[i]);
Quoted 7 lines
Quoted 1 line

ISTR that some PPC hosts support KVM...

FWIW, I notice we currently have a qemu_fls() defined in cutils.c, which uses the clz32() defined in host-utils.h.

qemu_ffsll() could be implemented fairly easily in terms of ctz64(), although note that ffsll(n) == (ctz64(n) + 1) % 65.

ctz64 - that's what I wanted! (No need to introduce qemu_ffsll, at least not for this use case.)

Jan

--------->

Not all host platforms support ffsll.

---

 target-i386/machine.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)
target-i386/machine.c +3 -3
index 259302c..e4099ca 100644
@@ -148,9 +148,9 @@ void cpu_save(QEMUFile *f, void *opaque)
        to find it and save its number instead (-1 for none). */
     pending_irq = -1;
     for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
-        bit = ffsll(env->interrupt_bitmap[i]);
-        if (bit) {
-            pending_irq = i * 64 + bit - 1;
+        if (env->interrupt_bitmap[i]) {
+            bit = ctz64(env->interrupt_bitmap[i]);
+            pending_irq = i * 64 + bit;
             break;
         }
     }
author
#8 lore raw

PATCH v2 1/1 Use ctz64 in favor of ffsll

Not all host platforms support ffsll.

---

 target-i386/machine.c |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)
target-i386/machine.c +4 -3
index 259302c..2a72b01 100644
@@ -2,6 +2,7 @@
 #include "hw/boards.h"
 #include "hw/pc.h"
 #include "hw/isa.h"
+#include "host-utils.h"
 
 #include "exec-all.h"
 #include "kvm.h"
@@ -148,9 +149,9 @@ void cpu_save(QEMUFile *f, void *opaque)
        to find it and save its number instead (-1 for none). */
     pending_irq = -1;
     for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
-        bit = ffsll(env->interrupt_bitmap[i]);
-        if (bit) {
-            pending_irq = i * 64 + bit - 1;
+        if (env->interrupt_bitmap[i]) {
+            bit = ctz64(env->interrupt_bitmap[i]);
+            pending_irq = i * 64 + bit;
             break;
         }
     }
#9 lore raw

Re: [Qemu-devel] [PATCH v2] Use ctz64 in favor of ffsll

target-i386/machine.c void cpu_save(QEMUFile *f, void *opaque) · line 154

Quoted 5 lines · Jan Kiszka

Not all host platforms support ffsll.

target-i386/machine.c +2 -1
-            pending_irq = i * 64 + bit - 1;
+            bit = ctz64(env->interrupt_bitmap[i]);
+            pending_irq = i * 64 + bit;

Are we sure there is only ever one bit set in interrupt_bitmap? If not does it mater that we're processing them in reverse order?

Paul

author
#10 lore raw

Re: [Qemu-devel] [PATCH v2] Use ctz64 in favor of ffsll

Quoted 8 lines · Paul Brook

target-i386/machine.c void cpu_save(QEMUFile *f, void *opaque) · line 154

Quoted 5 lines · Jan Kiszka

Not all host platforms support ffsll.

target-i386/machine.c +2 -1
-            pending_irq = i * 64 + bit - 1;
+            bit = ctz64(env->interrupt_bitmap[i]);
+            pending_irq = i * 64 + bit;

Are we sure there is only ever one bit set in interrupt_bitmap?

Yes.

Quoted 3 lines

If not does it mater that we're processing them in reverse order?

Paul

Jan

#11 lore raw
In reply to Blue Swirl
Quoted 12 lines · On Wednesday 01 July 2009 22:27:51 Blue Swirl wrote:
Quoted 10 lines · Jan Kiszka

Not all host platforms support the ll variant. This is not a critical
path, so go the easy way.

- for (i = 0; i < ARRAY_SIZE(env->interrupt_bitmap); i++) {
- bit = ffsll(env->interrupt_bitmap[i]);
+ for (i = 0; i < sizeof(env->interrupt_bitmap) / sizeof(int); i++) {

 +        bit = ffs(((int *)env->interrupt_bitmap)[i]);
         if (bit) {

- pending_irq = i * 64 + bit - 1;
+ pending_irq = i * 8 * sizeof(int) + bit - 1;

Quoted 1 line

I think this will not work on a big endian host.

A qemu_ffsll() implementation can be something like this:

int qemu_ffsll(long long mask)

{
      int bit;

      bit = ffs((int)mask);
      if (bit == 0) {
           mask >>= 32;
           bit = ffs((int)mask);
           if (bit) bit += 32;
      }
       return bit;
}

Christoph

Signature · 6 lines
---to satisfy European Law for business letters:
Advanced Micro Devices GmbH
Karl-Hammerschmidt-Str. 34, 85609 Dornach b. Muenchen
Geschaeftsfuehrer: Thomas M. McCoy, Giuliano Meroni
Sitz: Dornach, Gemeinde Aschheim, Landkreis Muenchen
Registergericht Muenchen, HRB Nr. 43632