linux-kernel - Re: [PATCH 11/39] autonuma: CPU follow memory algorithm

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]

Date:	Mon, 26 Mar 2012 21:44:35 +0200
From:	Andrea Arcangeli <aarcange@...hat.com>
To:	Rik van Riel <riel@...hat.com>
Cc:	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	linux-kernel@...r.kernel.org, linux-mm@...ck.org,
	Hillf Danton <dhillf@...il.com>, Dan Smith <danms@...ibm.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...e.hu>, Paul Turner <pjt@...gle.com>,
	Suresh Siddha <suresh.b.siddha@...el.com>,
	Mike Galbraith <efault@....de>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	Lai Jiangshan <laijs@...fujitsu.com>,
	Bharata B Rao <bharata.rao@...il.com>,
	Lee Schermerhorn <Lee.Schermerhorn@...com>,
	Johannes Weiner <hannes@...xchg.org>
Subject: Re: [PATCH 11/39] autonuma: CPU follow memory algorithm

On Mon, Mar 26, 2012 at 03:28:37PM -0400, Rik van Riel wrote:
> Agreed, it looks O(N), but because every CPU will be calling
> it its behaviour will be O(N^2) and has the potential to
> completely break systems with a large number of CPUs.

As I wrote in the comment before the function, math speaking, this
looks like O(N) but it is O(1), not O(N) nor O(N^2). This is because N
= NR_CPUS = 1.

As I also wrote in the comment before the function, this is called at
every schedule in the short term primarily because I want to see a
flood if this algorithm does something wrong after I do.

echo 1 >/sys/kernel/mm/autonuma/debug

 * This has O(N) complexity but N isn't the number of running
 * processes, but the number of CPUs, so if you assume a constant
 * number of CPUs (capped at NR_CPUS) it is O(1). O(1) misleading math
 * aside, the number of cachelines touched with thousands of CPU might
 * make it measurable. Calling this at every schedule may also be
 * overkill and it may be enough to call it with a frequency similar
 * to the load balancing, but by doing so we're also verifying the
 * algorithm is a converging one in all workloads if performance is
 * improved and there's no frequent CPU migration, so it's good in the
 * short term for stressing the algorithm.

Over time (not urgent) this can be called at a regular interval like
load_balance() or be more integrated within CFS so it doesn't need to
be called at all.

For the short term it shall be called at every schedule for debug
reasons so I wouldn't suggest to make an effort to call it at lower
frequency right now. If somebody wants to make an effort to make it
more integrated in CFS that's welcome though, but I would still like a
tweak to force the algorithm synchronously during every schedule
decision like now so I can verify it converges at the scheduler level
and there is not a flood of worthless bounces.
--
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/