linux-kernel - Re: [RFC][PATCH] sched/rt: Use IPI to trigger RT task push migration instead of pulling

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: <20150206135945.GM24151@twins.programming.kicks-ass.net>
Date:	Fri, 6 Feb 2015 14:59:45 +0100
From:	Peter Zijlstra <peterz@...radead.org>
To:	Steven Rostedt <rostedt@...dmis.org>
Cc:	LKML <linux-kernel@...r.kernel.org>,
	Ingo Molnar <mingo@...nel.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Clark Williams <williams@...hat.com>,
	linux-rt-users <linux-rt-users@...r.kernel.org>,
	Mike Galbraith <umgwanakikbuti@...il.com>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Subject: Re: [RFC][PATCH] sched/rt: Use IPI to trigger RT task push migration
 instead of pulling

On Fri, Feb 06, 2015 at 02:23:41PM +0100, Peter Zijlstra wrote:
> A more advanced version might use an LFSR to iterate the mask, where we
> give each cpu a different seed (say its cpuid) -- be careful to
> artificially insert 0 when we loop.

And since I already stared at this longer than I should have... its got
a few quirks and is slower than the regular iteration but it should
still have bounded behaviour.


static unsigned long lfsr_taps;

void __init lfsr_init(void)
{
	int bits = ilog2(nr_cpu_ids) + 1;

	switch (bits) {
		case  1: lfsr_taps = 0x0001; break;
		case  2: lfsr_taps = 0x0001; break;
		case  3: lfsr_taps = 0x0003; break;
		case  4: lfsr_taps = 0x0009; break;
		case  5: lfsr_taps = 0x0012; break;
		case  5: lfsr_taps = 0x0012; break;
		case  6: lfsr_taps = 0x0021; break;
		case  7: lfsr_taps = 0x0041; break;
		case  8: lfsr_taps = 0x008E; break;
		case  9: lfsr_taps = 0x0108; break;
		case 10: lfsr_taps = 0x0204; break;
		case 11: lfsr_taps = 0x0402; break;
		case 12: lfsr_taps = 0x0829; break;
		case 13: lfsr_taps = 0x100D; break;
		case 14: lfsr_taps = 0x2015; break;

		default:
			BUG_ON(1); /* add more numbers */
	}
}

static inline int __lfsr_next(int lfsr)
{
	unsigned int bit = lfsr & 1;
	lfsr >>= 1;
	if (bit)
		lfsr ^= lfsr_taps;
	return lfsr;
}

int cpumask_next_lfsr(int cpu, const struct cpumask *mask, int seed)
{
	seed |= 1; /* must not be 0 */

	/* kick-start, avoid the termination condition */
	if (cpu == -1) {
		cpu = seed;
		goto test;
	}

again:
	/* when we cycle, we're done, test cpu 0 last */
	if (cpu == seed)
		cpu = 0;
	/* if we just tested cpu 0, we're done */
	else if (cpu == 0)
		return nr_cpu_ids;
	/* otherwise, next please! */
	else
		cpu = __lfsr_next(cpu);

test:
	/* cycle through the unused space; <= 2^(n-1) loops */
	if (cpu >= nr_cpu_ids)
		goto again;

	if (!cpumask_test_cpu(cpu), mask)
		goto again;

	return cpu;
}

#define for_each_cpu_lfsr(cpu, mask, seed)				  \
	for ((cpu) = -1; (cpu) = cpumask_next_lfsr((cpu), (mask), (seed)), \
			 (cpu) < nr_cpu_ids;)
--
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/