Re: [PATCH] lib: proportion: fix underflow in prop_norm_percpu()

From: Jiang zhe
Date: Sun Dec 16 2007 - 21:05:41 EST


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 <a.p.zijlstra@xxxxxxxxx>
> Cc: zhejiang <zhe.jiang@xxxxxxxxx>
> ---
> 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 majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/