Re: [PATCH] lib: proportion: fix underflow in prop_norm_percpu()
On Fri, 2007-12-14 at 17:01 +0100, Peter Zijlstra wrote:
> Subject: lib: proportion: fix underflow in prop_norm_percpu()
>
> Zhe Jiang noticed that its possible to underflow pl->events in
> prop_norm_percpu() when the value returned by percpu_counter_read() is less
> than the error on that read and the period delay > 1. In that case half might
> not trigger the batch increment and the value will be identical on the next
> iteration, causing the same half to be subtracted again and again.
>
> Fix this by rewriting the division as a single subtraction instead of a
> subtraction loop and using percpu_counter_sum() when the value returned
> by percpu_counter_read() is smaller than the error.
>
> The latter is still needed if we want pl->events to shrink properly in the
> error region.
>
> Jiang, can I get a Reviewed-by from you? - if you agree that is :-)
>
> Signed-off-by: Peter Zijlstra <[EMAIL PROTECTED]>
> Cc: zhejiang <[EMAIL PROTECTED]>
> ---
> lib/proportions.c | 36 +++-
> 1 file changed, 15 insertions(+), 21 deletions(-)
>
> Index: linux-2.6/lib/proportions.c
> ===
> --- linux-2.6.orig/lib/proportions.c
> +++ linux-2.6/lib/proportions.c
> @@ -190,6 +190,8 @@ prop_adjust_shift(int *pl_shift, unsigne
> * PERCPU
> */
>
> +#define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
> +
> int prop_local_init_percpu(struct prop_local_percpu *pl)
> {
> spin_lock_init(>lock);
> @@ -230,31 +232,23 @@ void prop_norm_percpu(struct prop_global
>
> spin_lock_irqsave(>lock, flags);
> prop_adjust_shift(>shift, >period, pg->shift);
> +
> /*
>* For each missed period, we half the local counter.
>* basically:
>* pl->events >> (global_period - pl->period);
> - *
> - * but since the distributed nature of percpu counters make division
> - * rather hard, use a regular subtraction loop. This is safe, because
> - * the events will only every be incremented, hence the subtraction
> - * can never result in a negative number.
>*/
> - while (pl->period != global_period) {
> - unsigned long val = percpu_counter_read(>events);
> - unsigned long half = (val + 1) >> 1;
> -
> - /*
> - * Half of zero won't be much less, break out.
> - * This limits the loop to shift iterations, even
> - * if we missed a million.
> - */
> - if (!val)
> - break;
> -
> - percpu_counter_add(>events, -half);
> - pl->period += period;
> - }
> + period = (global_period - pl->period) >> (pg->shift - 1);
> + if (period < BITS_PER_LONG) {
> + s64 val = percpu_counter_read(>events);
> +
> + if (val < (nr_cpu_ids * PROP_BATCH))
> + val = percpu_counter_sum(>events);
> +
> + __percpu_counter_add(>events, -val + (val >> period),
> PROP_BATCH);
> + } else
> + percpu_counter_set(>events, 0);
> +
> pl->period = global_period;
> spin_unlock_irqrestore(>lock, flags);
> }
> @@ -267,7 +261,7 @@ void __prop_inc_percpu(struct prop_descr
> struct prop_global *pg = prop_get_global(pd);
>
> prop_norm_percpu(pg, pl);
> - percpu_counter_add(>events, 1);
> + __percpu_counter_add(>events, 1, PROP_BATCH);
> percpu_counter_add(>events, 1);
> prop_put_global(pd, pg);
> }
>
Reviewed-by: Jiang Zhe <[EMAIL PROTECTED]>
Thanks!
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] lib: proportion: fix underflow in prop_norm_percpu()
On Fri, 2007-12-14 at 17:01 +0100, Peter Zijlstra wrote:
> Subject: lib: proportion: fix underflow in prop_norm_percpu()
>
> Zhe Jiang noticed that its possible to underflow pl->events in
> prop_norm_percpu() when the value returned by percpu_counter_read() is less
> than the error on that read and the period delay > 1. In that case half might
> not trigger the batch increment and the value will be identical on the next
> iteration, causing the same half to be subtracted again and again.
>
> Fix this by rewriting the division as a single subtraction instead of a
> subtraction loop and using percpu_counter_sum() when the value returned
> by percpu_counter_read() is smaller than the error.
>
> The latter is still needed if we want pl->events to shrink properly in the
> error region.
>
> Jiang, can I get a Reviewed-by from you? - if you agree that is :-)
>
> Signed-off-by: Peter Zijlstra <[EMAIL PROTECTED]>
> Cc: zhejiang <[EMAIL PROTECTED]>
> ---
> lib/proportions.c | 36 +++-
> 1 file changed, 15 insertions(+), 21 deletions(-)
>
> Index: linux-2.6/lib/proportions.c
> ===
> --- linux-2.6.orig/lib/proportions.c
> +++ linux-2.6/lib/proportions.c
> @@ -190,6 +190,8 @@ prop_adjust_shift(int *pl_shift, unsigne
> * PERCPU
> */
>
> +#define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
> +
> int prop_local_init_percpu(struct prop_local_percpu *pl)
> {
> spin_lock_init(>lock);
> @@ -230,31 +232,23 @@ void prop_norm_percpu(struct prop_global
>
> spin_lock_irqsave(>lock, flags);
> prop_adjust_shift(>shift, >period, pg->shift);
> +
> /*
>* For each missed period, we half the local counter.
>* basically:
>* pl->events >> (global_period - pl->period);
> - *
> - * but since the distributed nature of percpu counters make division
> - * rather hard, use a regular subtraction loop. This is safe, because
> - * the events will only every be incremented, hence the subtraction
> - * can never result in a negative number.
>*/
> - while (pl->period != global_period) {
> - unsigned long val = percpu_counter_read(>events);
> - unsigned long half = (val + 1) >> 1;
> -
> - /*
> - * Half of zero won't be much less, break out.
> - * This limits the loop to shift iterations, even
> - * if we missed a million.
> - */
> - if (!val)
> - break;
> -
> - percpu_counter_add(>events, -half);
> - pl->period += period;
> - }
> + period = (global_period - pl->period) >> (pg->shift - 1);
> + if (period < BITS_PER_LONG) {
> + s64 val = percpu_counter_read(>events);
> +
> + if (val < (nr_cpu_ids * PROP_BATCH))
> + val = percpu_counter_sum(>events);
> +
> + __percpu_counter_add(>events, -val + (val >> period),
> PROP_BATCH);
> + } else
> + percpu_counter_set(>events, 0);
> +
> pl->period = global_period;
> spin_unlock_irqrestore(>lock, flags);
> }
> @@ -267,7 +261,7 @@ void __prop_inc_percpu(struct prop_descr
> struct prop_global *pg = prop_get_global(pd);
>
> prop_norm_percpu(pg, pl);
> - percpu_counter_add(>events, 1);
> + __percpu_counter_add(>events, 1, PROP_BATCH);
> percpu_counter_add(>events, 1);
> prop_put_global(pd, pg);
> }
>
It's okay! Thanks!
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] lib: proportion: fix underflow in prop_norm_percpu()
On Fri, 2007-12-14 at 17:01 +0100, Peter Zijlstra wrote:
Subject: lib: proportion: fix underflow in prop_norm_percpu()
Zhe Jiang noticed that its possible to underflow pl-events in
prop_norm_percpu() when the value returned by percpu_counter_read() is less
than the error on that read and the period delay 1. In that case half might
not trigger the batch increment and the value will be identical on the next
iteration, causing the same half to be subtracted again and again.
Fix this by rewriting the division as a single subtraction instead of a
subtraction loop and using percpu_counter_sum() when the value returned
by percpu_counter_read() is smaller than the error.
The latter is still needed if we want pl-events to shrink properly in the
error region.
Jiang, can I get a Reviewed-by from you? - if you agree that is :-)
Signed-off-by: Peter Zijlstra [EMAIL PROTECTED]
Cc: zhejiang [EMAIL PROTECTED]
---
lib/proportions.c | 36 +++-
1 file changed, 15 insertions(+), 21 deletions(-)
Index: linux-2.6/lib/proportions.c
===
--- linux-2.6.orig/lib/proportions.c
+++ linux-2.6/lib/proportions.c
@@ -190,6 +190,8 @@ prop_adjust_shift(int *pl_shift, unsigne
* PERCPU
*/
+#define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
+
int prop_local_init_percpu(struct prop_local_percpu *pl)
{
spin_lock_init(pl-lock);
@@ -230,31 +232,23 @@ void prop_norm_percpu(struct prop_global
spin_lock_irqsave(pl-lock, flags);
prop_adjust_shift(pl-shift, pl-period, pg-shift);
+
/*
* For each missed period, we half the local counter.
* basically:
* pl-events (global_period - pl-period);
- *
- * but since the distributed nature of percpu counters make division
- * rather hard, use a regular subtraction loop. This is safe, because
- * the events will only every be incremented, hence the subtraction
- * can never result in a negative number.
*/
- while (pl-period != global_period) {
- unsigned long val = percpu_counter_read(pl-events);
- unsigned long half = (val + 1) 1;
-
- /*
- * Half of zero won't be much less, break out.
- * This limits the loop to shift iterations, even
- * if we missed a million.
- */
- if (!val)
- break;
-
- percpu_counter_add(pl-events, -half);
- pl-period += period;
- }
+ period = (global_period - pl-period) (pg-shift - 1);
+ if (period BITS_PER_LONG) {
+ s64 val = percpu_counter_read(pl-events);
+
+ if (val (nr_cpu_ids * PROP_BATCH))
+ val = percpu_counter_sum(pl-events);
+
+ __percpu_counter_add(pl-events, -val + (val period),
PROP_BATCH);
+ } else
+ percpu_counter_set(pl-events, 0);
+
pl-period = global_period;
spin_unlock_irqrestore(pl-lock, flags);
}
@@ -267,7 +261,7 @@ void __prop_inc_percpu(struct prop_descr
struct prop_global *pg = prop_get_global(pd);
prop_norm_percpu(pg, pl);
- percpu_counter_add(pl-events, 1);
+ __percpu_counter_add(pl-events, 1, PROP_BATCH);
percpu_counter_add(pg-events, 1);
prop_put_global(pd, pg);
}
It's okay! Thanks!
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] lib: proportion: fix underflow in prop_norm_percpu()
On Fri, 2007-12-14 at 17:01 +0100, Peter Zijlstra wrote:
Subject: lib: proportion: fix underflow in prop_norm_percpu()
Zhe Jiang noticed that its possible to underflow pl-events in
prop_norm_percpu() when the value returned by percpu_counter_read() is less
than the error on that read and the period delay 1. In that case half might
not trigger the batch increment and the value will be identical on the next
iteration, causing the same half to be subtracted again and again.
Fix this by rewriting the division as a single subtraction instead of a
subtraction loop and using percpu_counter_sum() when the value returned
by percpu_counter_read() is smaller than the error.
The latter is still needed if we want pl-events to shrink properly in the
error region.
Jiang, can I get a Reviewed-by from you? - if you agree that is :-)
Signed-off-by: Peter Zijlstra [EMAIL PROTECTED]
Cc: zhejiang [EMAIL PROTECTED]
---
lib/proportions.c | 36 +++-
1 file changed, 15 insertions(+), 21 deletions(-)
Index: linux-2.6/lib/proportions.c
===
--- linux-2.6.orig/lib/proportions.c
+++ linux-2.6/lib/proportions.c
@@ -190,6 +190,8 @@ prop_adjust_shift(int *pl_shift, unsigne
* PERCPU
*/
+#define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
+
int prop_local_init_percpu(struct prop_local_percpu *pl)
{
spin_lock_init(pl-lock);
@@ -230,31 +232,23 @@ void prop_norm_percpu(struct prop_global
spin_lock_irqsave(pl-lock, flags);
prop_adjust_shift(pl-shift, pl-period, pg-shift);
+
/*
* For each missed period, we half the local counter.
* basically:
* pl-events (global_period - pl-period);
- *
- * but since the distributed nature of percpu counters make division
- * rather hard, use a regular subtraction loop. This is safe, because
- * the events will only every be incremented, hence the subtraction
- * can never result in a negative number.
*/
- while (pl-period != global_period) {
- unsigned long val = percpu_counter_read(pl-events);
- unsigned long half = (val + 1) 1;
-
- /*
- * Half of zero won't be much less, break out.
- * This limits the loop to shift iterations, even
- * if we missed a million.
- */
- if (!val)
- break;
-
- percpu_counter_add(pl-events, -half);
- pl-period += period;
- }
+ period = (global_period - pl-period) (pg-shift - 1);
+ if (period BITS_PER_LONG) {
+ s64 val = percpu_counter_read(pl-events);
+
+ if (val (nr_cpu_ids * PROP_BATCH))
+ val = percpu_counter_sum(pl-events);
+
+ __percpu_counter_add(pl-events, -val + (val period),
PROP_BATCH);
+ } else
+ percpu_counter_set(pl-events, 0);
+
pl-period = global_period;
spin_unlock_irqrestore(pl-lock, flags);
}
@@ -267,7 +261,7 @@ void __prop_inc_percpu(struct prop_descr
struct prop_global *pg = prop_get_global(pd);
prop_norm_percpu(pg, pl);
- percpu_counter_add(pl-events, 1);
+ __percpu_counter_add(pl-events, 1, PROP_BATCH);
percpu_counter_add(pg-events, 1);
prop_put_global(pd, pg);
}
Reviewed-by: Jiang Zhe [EMAIL PROTECTED]
Thanks!
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH] lib: proportion: fix underflow in prop_norm_percpu()
Subject: lib: proportion: fix underflow in prop_norm_percpu()
Zhe Jiang noticed that its possible to underflow pl->events in
prop_norm_percpu() when the value returned by percpu_counter_read() is less
than the error on that read and the period delay > 1. In that case half might
not trigger the batch increment and the value will be identical on the next
iteration, causing the same half to be subtracted again and again.
Fix this by rewriting the division as a single subtraction instead of a
subtraction loop and using percpu_counter_sum() when the value returned
by percpu_counter_read() is smaller than the error.
The latter is still needed if we want pl->events to shrink properly in the
error region.
Jiang, can I get a Reviewed-by from you? - if you agree that is :-)
Signed-off-by: Peter Zijlstra <[EMAIL PROTECTED]>
Cc: zhejiang <[EMAIL PROTECTED]>
---
lib/proportions.c | 36 +++-
1 file changed, 15 insertions(+), 21 deletions(-)
Index: linux-2.6/lib/proportions.c
===
--- linux-2.6.orig/lib/proportions.c
+++ linux-2.6/lib/proportions.c
@@ -190,6 +190,8 @@ prop_adjust_shift(int *pl_shift, unsigne
* PERCPU
*/
+#define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
+
int prop_local_init_percpu(struct prop_local_percpu *pl)
{
spin_lock_init(>lock);
@@ -230,31 +232,23 @@ void prop_norm_percpu(struct prop_global
spin_lock_irqsave(>lock, flags);
prop_adjust_shift(>shift, >period, pg->shift);
+
/*
* For each missed period, we half the local counter.
* basically:
* pl->events >> (global_period - pl->period);
-*
-* but since the distributed nature of percpu counters make division
-* rather hard, use a regular subtraction loop. This is safe, because
-* the events will only every be incremented, hence the subtraction
-* can never result in a negative number.
*/
- while (pl->period != global_period) {
- unsigned long val = percpu_counter_read(>events);
- unsigned long half = (val + 1) >> 1;
-
- /*
-* Half of zero won't be much less, break out.
-* This limits the loop to shift iterations, even
-* if we missed a million.
-*/
- if (!val)
- break;
-
- percpu_counter_add(>events, -half);
- pl->period += period;
- }
+ period = (global_period - pl->period) >> (pg->shift - 1);
+ if (period < BITS_PER_LONG) {
+ s64 val = percpu_counter_read(>events);
+
+ if (val < (nr_cpu_ids * PROP_BATCH))
+ val = percpu_counter_sum(>events);
+
+ __percpu_counter_add(>events, -val + (val >> period),
PROP_BATCH);
+ } else
+ percpu_counter_set(>events, 0);
+
pl->period = global_period;
spin_unlock_irqrestore(>lock, flags);
}
@@ -267,7 +261,7 @@ void __prop_inc_percpu(struct prop_descr
struct prop_global *pg = prop_get_global(pd);
prop_norm_percpu(pg, pl);
- percpu_counter_add(>events, 1);
+ __percpu_counter_add(>events, 1, PROP_BATCH);
percpu_counter_add(>events, 1);
prop_put_global(pd, pg);
}
signature.asc
Description: This is a digitally signed message part
[PATCH] lib: proportion: fix underflow in prop_norm_percpu()
Subject: lib: proportion: fix underflow in prop_norm_percpu()
Zhe Jiang noticed that its possible to underflow pl-events in
prop_norm_percpu() when the value returned by percpu_counter_read() is less
than the error on that read and the period delay 1. In that case half might
not trigger the batch increment and the value will be identical on the next
iteration, causing the same half to be subtracted again and again.
Fix this by rewriting the division as a single subtraction instead of a
subtraction loop and using percpu_counter_sum() when the value returned
by percpu_counter_read() is smaller than the error.
The latter is still needed if we want pl-events to shrink properly in the
error region.
Jiang, can I get a Reviewed-by from you? - if you agree that is :-)
Signed-off-by: Peter Zijlstra [EMAIL PROTECTED]
Cc: zhejiang [EMAIL PROTECTED]
---
lib/proportions.c | 36 +++-
1 file changed, 15 insertions(+), 21 deletions(-)
Index: linux-2.6/lib/proportions.c
===
--- linux-2.6.orig/lib/proportions.c
+++ linux-2.6/lib/proportions.c
@@ -190,6 +190,8 @@ prop_adjust_shift(int *pl_shift, unsigne
* PERCPU
*/
+#define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
+
int prop_local_init_percpu(struct prop_local_percpu *pl)
{
spin_lock_init(pl-lock);
@@ -230,31 +232,23 @@ void prop_norm_percpu(struct prop_global
spin_lock_irqsave(pl-lock, flags);
prop_adjust_shift(pl-shift, pl-period, pg-shift);
+
/*
* For each missed period, we half the local counter.
* basically:
* pl-events (global_period - pl-period);
-*
-* but since the distributed nature of percpu counters make division
-* rather hard, use a regular subtraction loop. This is safe, because
-* the events will only every be incremented, hence the subtraction
-* can never result in a negative number.
*/
- while (pl-period != global_period) {
- unsigned long val = percpu_counter_read(pl-events);
- unsigned long half = (val + 1) 1;
-
- /*
-* Half of zero won't be much less, break out.
-* This limits the loop to shift iterations, even
-* if we missed a million.
-*/
- if (!val)
- break;
-
- percpu_counter_add(pl-events, -half);
- pl-period += period;
- }
+ period = (global_period - pl-period) (pg-shift - 1);
+ if (period BITS_PER_LONG) {
+ s64 val = percpu_counter_read(pl-events);
+
+ if (val (nr_cpu_ids * PROP_BATCH))
+ val = percpu_counter_sum(pl-events);
+
+ __percpu_counter_add(pl-events, -val + (val period),
PROP_BATCH);
+ } else
+ percpu_counter_set(pl-events, 0);
+
pl-period = global_period;
spin_unlock_irqrestore(pl-lock, flags);
}
@@ -267,7 +261,7 @@ void __prop_inc_percpu(struct prop_descr
struct prop_global *pg = prop_get_global(pd);
prop_norm_percpu(pg, pl);
- percpu_counter_add(pl-events, 1);
+ __percpu_counter_add(pl-events, 1, PROP_BATCH);
percpu_counter_add(pg-events, 1);
prop_put_global(pd, pg);
}
signature.asc
Description: This is a digitally signed message part
