[Qemu-devel] Fix ptimer_get_count overflow.

[Qemu-devel] Fix ptimer_get_count overflow.

[Vladimir Prus]

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


At present, ptimers have a slight inaccuracy that can lead to
overflow. The period is stored as 64.32 fixed point number.
ptimer_reload uses both integer and fractional part of the perion
when computing when the next event should happen. ptimer_get_count,
however, uses only integer part of the period. Therefore, when
ptimer_get_count is called very soon after ptimer_reload the value
returned may be greater than the value ptimer_reload has set.
And if the counter was 0xFFFFFFFF, this may result in overflow.

This was observed in SH4A emulation as "time jumps", where system
time gets magically increased by 10 minutes sometimes.

This patch fixes this. The math is not the most accurate possible,
but it's relatively fast and fixes the problems.

- Volodya

[-- Attachment #2: primer_overflow.diff --]
[-- Type: text/x-diff, Size: 2008 bytes --]

commit f1b78f0ca2b7fe12cdaabcb97c08484d3c26b99f
Author: Vladimir Prus <vladimir@codesourcery.com>
Date:   Thu Dec 25 17:20:38 2008 +0300

    Fix ptimer_get_count overflow.
    
    	* hw/ptimer.c (ptimer_get_count): Don't ignore
    	fractional part of period.

diff --git a/hw/ptimer.c b/hw/ptimer.c
index 9d38627..9278f83 100644
--- a/hw/ptimer.c
+++ b/hw/ptimer.c
@@ -7,7 +7,7 @@
  */
 #include "hw.h"
 #include "qemu-timer.h"
-
+#include "host-utils.h"
 
 struct ptimer_state
 {
@@ -78,10 +78,41 @@ uint64_t ptimer_get_count(ptimer_state *s)
         } else {
             uint64_t rem;
             uint64_t div;
+            uint32_t frac;
+            int clz1, clz2;
+            int shift;
+
+            /* We need to divide time by period, where time is stored in
+               rem (64-bit integer) and period is stored in period/period_frac
+               (64.32 fixed point). The result should be rounded down, so that
+               we never get the value greater than the timer's limit.
+
+               We normalize both numerator and demoninator by left-shifting
+               until one of them has non-zero MSB, and then do 64-bit division.
+            */
 
             rem = s->next_event - now;
             div = s->period;
-            counter = rem / div;
+
+            clz1 = clz64(rem);
+            clz2 = clz64(div);
+            shift = clz1 < clz2 ? clz1 : clz2;
+
+            rem <<= shift;
+            div <<= shift;
+            if (shift <= 32)
+                div |= (unsigned long long)(
+                    (s->period_frac >> (32 - shift)) & ((1ull << shift) - 1));
+            else
+                div |= (s->period_frac << (shift - 32));
+            
+            /* Look at remaining bits of period_frac and round div up if 
+               necessary.  */
+            frac = s->period_frac << shift;
+            if (frac)
+                div += 1;
+            
+            counter = rem/div;
         }
     } else {
         counter = s->delta;

[Qemu-devel] Re: Fix ptimer_get_count overflow.

[Vladimir Prus]

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

Vladimir Prus wrote:

> 
> At present, ptimers have a slight inaccuracy that can lead to
> overflow. The period is stored as 64.32 fixed point number.
> ptimer_reload uses both integer and fractional part of the perion
> when computing when the next event should happen. ptimer_get_count,
> however, uses only integer part of the period. Therefore, when
> ptimer_get_count is called very soon after ptimer_reload the value
> returned may be greater than the value ptimer_reload has set.
> And if the counter was 0xFFFFFFFF, this may result in overflow.
> 
> This was observed in SH4A emulation as "time jumps", where system
> time gets magically increased by 10 minutes sometimes.
> 
> This patch fixes this. The math is not the most accurate possible,
> but it's relatively fast and fixes the problems.

Ping?

- Volodya



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: primer_overflow.diff --]
[-- Type: text/x-diff; name="primer_overflow.diff", Size: 2008 bytes --]

commit f1b78f0ca2b7fe12cdaabcb97c08484d3c26b99f
Author: Vladimir Prus <vladimir@codesourcery.com>
Date:   Thu Dec 25 17:20:38 2008 +0300

    Fix ptimer_get_count overflow.
    
    	* hw/ptimer.c (ptimer_get_count): Don't ignore
    	fractional part of period.

diff --git a/hw/ptimer.c b/hw/ptimer.c
index 9d38627..9278f83 100644
--- a/hw/ptimer.c
+++ b/hw/ptimer.c
@@ -7,7 +7,7 @@
  */
 #include "hw.h"
 #include "qemu-timer.h"
-
+#include "host-utils.h"
 
 struct ptimer_state
 {
@@ -78,10 +78,41 @@ uint64_t ptimer_get_count(ptimer_state *s)
         } else {
             uint64_t rem;
             uint64_t div;
+            uint32_t frac;
+            int clz1, clz2;
+            int shift;
+
+            /* We need to divide time by period, where time is stored in
+               rem (64-bit integer) and period is stored in period/period_frac
+               (64.32 fixed point). The result should be rounded down, so that
+               we never get the value greater than the timer's limit.
+
+               We normalize both numerator and demoninator by left-shifting
+               until one of them has non-zero MSB, and then do 64-bit division.
+            */
 
             rem = s->next_event - now;
             div = s->period;
-            counter = rem / div;
+
+            clz1 = clz64(rem);
+            clz2 = clz64(div);
+            shift = clz1 < clz2 ? clz1 : clz2;
+
+            rem <<= shift;
+            div <<= shift;
+            if (shift <= 32)
+                div |= (unsigned long long)(
+                    (s->period_frac >> (32 - shift)) & ((1ull << shift) - 1));
+            else
+                div |= (s->period_frac << (shift - 32));
+            
+            /* Look at remaining bits of period_frac and round div up if 
+               necessary.  */
+            frac = s->period_frac << shift;
+            if (frac)
+                div += 1;
+            
+            counter = rem/div;
         }
     } else {
         counter = s->delta;

Re: [Qemu-devel] Re: Fix ptimer_get_count overflow.

[Paul Brook]

On Wednesday 04 March 2009, Vladimir Prus wrote:
> Vladimir Prus wrote:
> > At present, ptimers have a slight inaccuracy that can lead to
> > overflow. The period is stored as 64.32 fixed point number.
> > ptimer_reload uses both integer and fractional part of the perion
> > when computing when the next event should happen. ptimer_get_count,
> > however, uses only integer part of the period. Therefore, when
> > ptimer_get_count is called very soon after ptimer_reload the value
> > returned may be greater than the value ptimer_reload has set.
> > And if the counter was 0xFFFFFFFF, this may result in overflow.

I think your patch has problems with out of range shift counts, so I applied a 
slightly different version.

Paul