linux-kernel - Re: [PATCH 03/10] lib: dampen the percpu_counter FBC

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <1177153137.2934.31.camel@lappy>
Date:	Sat, 21 Apr 2007 12:58:57 +0200
From:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	linux-mm@...ck.org, linux-kernel@...r.kernel.org,
	miklos@...redi.hu, neilb@...e.de, dgc@....com,
	tomoki.sekiyama.qu@...achi.com, nikita@...sterfs.com,
	trond.myklebust@....uio.no, yingchao.zhou@...il.com
Subject: Re: [PATCH 03/10] lib: dampen the percpu_counter FBC_BATCH

On Sat, 2007-04-21 at 02:55 -0700, Andrew Morton wrote:
> On Fri, 20 Apr 2007 17:51:57 +0200 Peter Zijlstra <a.p.zijlstra@...llo.nl> wrote:
> 
> > With the current logic the percpu_counter's accuracy delta is quadric
> > wrt the number of cpus in the system, reduce this to O(n ln n).
> > 
> > Signed-off-by: Peter Zijlstra <a.p.zijlstra@...llo.nl>
> > ---
> >  include/linux/percpu_counter.h |    7 ++-----
> >  1 file changed, 2 insertions(+), 5 deletions(-)
> > 
> > Index: linux-2.6-mm/include/linux/percpu_counter.h
> > ===================================================================
> > --- linux-2.6-mm.orig/include/linux/percpu_counter.h
> > +++ linux-2.6-mm/include/linux/percpu_counter.h
> > @@ -11,6 +11,7 @@
> >  #include <linux/threads.h>
> >  #include <linux/percpu.h>
> >  #include <linux/types.h>
> > +#include <linux/log2.h>
> >  
> >  #ifdef CONFIG_SMP
> >  
> > @@ -20,11 +21,7 @@ struct percpu_counter {
> >  	s32 *counters;
> >  };
> >  
> > -#if NR_CPUS >= 16
> > -#define FBC_BATCH	(NR_CPUS*2)
> > -#else
> > -#define FBC_BATCH	(NR_CPUS*4)
> > -#endif
> > +#define FBC_BATCH	(8*ilog2(NR_CPUS))
> >  
> >  static inline void percpu_counter_init(struct percpu_counter *fbc, s64 amount)
> >  {
> 
> I worry that this might be too small when there are hundreds of CPUs online.
> 
> With 1024 CPUs we go for the lock once per 80 counts.  That's not much. 
> 
> If we have 1024 CPUs, each one of which is incrementing this counter at N
> Hz, we have 1024/80=12 CPUs all going for the same lock at N Hz.  It could
> get bad.
> 
> But I don't know what the gain is for this loss.  Your changelog should
> have told us.
> 
> What problem is this patch solving?

In 10/10 I introduce bdi_stat_delta() which gives the maximum error of a
single counter. That is used to switch between precise
(percpu_counter_sum) and imprecise (percpu_counter_read) accesses of the
stats.

I worried that the current quadric error would be too large; and as the
ZVC counters also use a logarithmic error bound I thought it would be
good to have here as well.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/