linux-kernel - Re: [PATCH v2 1/2] tmpfs: Quick token library to allow scalable retrieval of tokens from token jar

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-Id: <20100612082757.7238224f.akpm@linux-foundation.org>
Date:	Sat, 12 Jun 2010 08:27:57 -0700
From:	Andrew Morton <akpm@...ux-foundation.org>
To:	Andi Kleen <andi@...stfloor.org>
Cc:	Tim Chen <tim.c.chen@...ux.intel.com>,
	linux-kernel@...r.kernel.org, Andi Kleen <ak@...ux.intel.com>,
	Hugh Dickins <hughd@...gle.com>
Subject: Re: [PATCH v2 1/2] tmpfs: Quick token library to allow scalable
 retrieval of tokens from token jar

On Sat, 12 Jun 2010 09:36:39 +0200 Andi Kleen <andi@...stfloor.org> wrote:

> On Fri, Jun 11, 2010 at 04:54:25PM -0700, Andrew Morton wrote:
> > > >  			spin_lock(&sbinfo->stat_lock);
> > > > -			if (sbinfo->free_blocks <= 1) {
> > > > +			if (percpu_counter_read(&sbinfo->free_blocks) <= 1) {
> > > >  				spin_unlock(&sbinfo->stat_lock);
> > > 
> > > Thanks for pointing me to look at this alternative implementation.
> > > 
> > > However, looking at the percpu counter code, it appears that the
> > > percpu_counter_read is imprecise.
> > 
> > Sure, that's inevitable if we want to avoid one-atomic-op-per-operation.
> 
> Only if you use the wrong primitive.
> It's not inevitable as qtoken has proven.

No it has not.  qtoken is inaccurate.

> > percpu_counters have a precise limit too!  It's
> > percpu_counter_batch*num_online_cpus.  You can implement your own
> > tolerance by not using percpu_counter_batch: pass your own batch into
> > __percpu_counter_add().
> 
> Such a batch could be rather large on a large system.
> 
> e.g. on a 32 CPU system with batch 16 it's already 2MB.

That's not much.

> > There's a trick that can be done to improve accuracy.  When checking to
> > see if the fs is full, use percpu_counter_read().  If the number that
> > percpu_counter_read() returns is "close" to max_blocks, then start
> > using the more expensive percpu_counter_sum().  So the kernel will be
> > fast, until the disk gets to within (batch*num_online_cpus) blocks of
> > being full.
> 
> Ok it would work, but you would get a big dip in performance
> once you're near the limit.
> 
> And the more CPUs you have the larger this window of slowness becomes.
> 
> > 
> > This is not the first time I've seen that requirement, and it would be
> > a good idea to implement the concept within an addition to the
> > percpu_counter library.  Say, percpu_counter_compare().
> 
> But why not just use qtoken which solves this without any hacks?

a) because qtoken needs "hacks" to solve it

b) because the qtoken code is fairly revolting

c) because the facilities which qtoken provides are so darn close to
   those which percpu_counters provide that it's quite unlikely that
   there will be another user of qtoken which couldn't have used
   percpu-counters

d) because the down-counter-like behaviour of qtoken is weird.

> I still think qtoken is a better proposal.

why?

> Even if it's a bit more
> code, but at least it solves this all cleanly without hacks and
> arbitary limits.

Well maybe there are still undiscovered secrets in there.  For its size
this is one of the worst-explained pieces of code I've seen to date.  I
still haven't really worked out the significance of setting the per-cpu
cache to -1.

--
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/