linux-kernel - Re: [PATCH] percpu_counter: return precise count from __percpu_counter

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: <20151002221649.GL27164@dastard>
Date:	Sat, 3 Oct 2015 08:16:49 +1000
From:	Dave Chinner <david@...morbit.com>
To:	Waiman Long <Waiman.Long@....com>
Cc:	Tejun Heo <tj@...nel.org>,
	Christoph Lameter <cl@...ux-foundation.org>,
	linux-kernel@...r.kernel.org, xfs@....sgi.com,
	Scott J Norton <scott.norton@....com>,
	Douglas Hatch <doug.hatch@....com>
Subject: Re: [PATCH] percpu_counter: return precise count from
 __percpu_counter_compare()

On Fri, Oct 02, 2015 at 01:29:57PM -0400, Waiman Long wrote:
> In __percpu_counter_compare(), if the current imprecise count is
> within (batch*nr_cpus) of the input value to be compared, a call
> to percpu_counter_sum() will be made to get the precise count. The
> percpu_counter_sum() call, however, can be expensive especially on
> large systems where there are a lot of CPUs. Large systems also make
> it more likely that percpu_counter_sum() will be called.
> 
> The xfs_mod_fdblocks() function calls __percpu_counter_compare()
> twice. First to see if a smaller batch size should be used for
> __percpu_counter_add() and the second call to compare the actual
> size needed. This can potentially lead to 2 calls to the expensive
> percpu_counter_sum() function.

There should not be that much overhead in __percpu_counter_compare()
through this path in normal operation. The slow path is only taken
as you near ENOSPC...

> This patch added an extra argument to __percpu_counter_compare()
> to return the precise count, if computed. The caller will need to
> initialize it to an invalid value that it can tell if the precise
> count is being returned.

This doesn't work. ENOSPC detection is a lockless algorithm that
requires absolute precision. Assuming the XFS_ALLOC_SET_ASIDE()
definition of ENOSPC is 0 blocks free, your change allows this race:

free space: 1 block

thread 1		thread 2			free space
allocate 1 block	allocate 1 block		  1
sample pcount = 1					  1
			sample pcount = 1		  1
add fdblocks, -1, 1)					  0
			add fdblocks, -1, 1)		  -1
if (pcount - 1 >= 0)	if (pcount - 1 >= 0)
   OK!			    OK!				  -1

So, we've just failed to detect ENOSPC correct. One of those two
threads should have returned ENOSPC and failed the allocation,
but instead we've just allowed XFS to allocate a block that doesn't
exist. Hence we have to resample the percpu counter after the
modification to ensure that we don't miss this race condition.

Sure, the curent code could race on the second comparisions and
return ENOSPC to both threads, but that is a perfectly OK thing
to do. It is vitally important that we don't oversubscribe
filesystem space, because that will lead to all sorts of other
problems (deadlocks, hangs, shutdowns, etc) that are very difficult
to identify the cause of.

FWIW, I'm guessing that you didn't run this patch through xfstests?
xfstests will find these ENOSPC accounting bugs, and usually quite
quickly...

> Running the AIM7 disk workload with XFS filesystem, the jobs/min
> on a 40-core 80-thread 4-socket Haswell-EX system increases from
> 3805k to 4276k (12% increase) with this patch applied. As measured
> by the perf tool, the %CPU cycle consumed by __percpu_counter_sum()
> decreases from 12.64% to 7.08%.

XFS should only hit the slow __percpu_counter_sum() path patch as
the fs gets close to ENOSPC, which for your system will be less
than:

threshold = num_online_cpus * XFS_FDBLOCKS_BATCH * 2 blocks
	  = 80 * 1024 * 2 blocks
	  = 160,000 blocks
	  = 640MB of disk space.

Having less than 1GB of free space in an XFS filesystem is
considered to be "almost ENOSPC" - when you have TB to PB of space,
less than 1GB really "moments before ENOSPC".

XFS trades off low overhead for fast path allocation  with slowdowns
as we near ENOSPC in allocation routines. It gets harder to find
contiguous free space, files get more fragmented, IO takes longer
because we seek more, etc. Hence we accept that performance slows
down as as the need for precision increases as we near ENOSPC.

I'd suggest you retry your benchmark with larger filesystems, and
see what happens...

Cheers,

Dave.
-- 
Dave Chinner
david@...morbit.com
--
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/