Immediate values are used as read mostly variables that are rarely updated. They

use code patching to modify the values inscribed in the instruction stream. It

provides a way to save precious cache lines that would otherwise have to be used

by these variables.
There is a generic _imv_read() version, which uses standard global

variables, and optimized per architecture imv_read() implementations,

which use a load immediate to remove a data cache hit. When the immediate values

functionnality is disabled in the kernel, it falls back to global variables.
It adds a new rodata section "__imv" to place the pointers to the enable

value. Immediate values activation functions sits in kernel/immediate.c.
Immediate values refer to the memory address of a previously declared integer.

This integer holds the information about the state of the immediate values

associated, and must be accessed through the API found in linux/immediate.h.
At module load time, each immediate value is checked to see if it must be

enabled. It would be the case if the variable they refer to is exported from

another module and already enabled.
In the early stages of start_kernel(), the immediate values are updated to

reflect the state of the variable they refer to.
* Why should this be merged *
It improves performances on heavy memory I/O workloads.
An interesting result shows the potential this infrastructure has by

showing the slowdown a simple system call such as getppid() suffers when it is

used under heavy user-space cache trashing:
Random walk L1 and L2 trashing surrounding a getppid() call:

(note: in this test, do_syscal_trace was taken at each system call, see

Documentation/immediate.txt in these patches for details)

- No memory pressure :   getppid() takes  1573 cycles

- With memory pressure : getppid() takes 15589 cycles
We therefore have a slowdown of 10 times just to get the kernel variables from

memory. Another test on the same architecture (Intel P4) measured the memory

latency to be 559 cyc...
[ message continues ]

hi,
In testing this patch, i've run across a deadlock...apply_imv_update() can get

called again before, ipi_busy_loop() has had a chance to finsh, and set

wait_sync back to its initial value. This causes ipi_busy_loop() to get stuck

indefinitely and the subsequent apply_imv_update() hangs. I've shown this

deadlock below using nmi_watchdog=1 in item 1). 
After hitting this deadlock i modified apply_imv_update() to wait for

ipi_busy_loop(), to finish, however this resulted in a 3 way deadlock. Process

A held a read lock on tasklist_lock, then process B called apply_imv_update().

Process A received the IPI and begins executing ipi_busy_loop(). Then process

C takes a write lock irq on the task list lock, before receiving the IPI. Thus,

process A holds up process C, and C can't get an IPI b/c interrupts are

disabled. i believe this is an inherent problem in using smp_call_function, in

that one can't synchronize the processes on each other...you can reproduce

these issues using the test module below item 2)
In order to address these issues, i've modified stop_machine_run() to take an

new third parameter, RUN_ALL, to allow stop_machine_run() to run a function

on all cpus, item 3). I then modified kernel/immediate.c to use this new

infrastructure item 4). the code in immediate.c simplifies quite a bit. This

new code has been robust through all testing thus far.
thanks,
-Jason
1)
 NMI Watchdog detected LOCKUP on CPU 3

CPU 3

Modules linked in: toggle_tester ipt_MASQUERADE iptable_nat nf_nat nf_conntrack_ipv4 xt_state nf]Pid: 0, comm: swapper Not tainted 2.6.24-git12markers #1

RIP: 0010:[<ffffffff8106e7cc>]  [<ffffffff8106e7cc>] ipi_busy_loop+0x19/0x41

RSP: 0018:ffff81007fbdff70  EFLAGS: 00000002

RAX: 0000000000000006 RBX: 0000000000000000 RCX: ffff81007fbd2930

RDX: ffffffff81491b80 RSI: 0000000000000046 RDI: 0000000000000000

RBP: ffff81007fbdff78 R08: ffff81007fbdff78 R09: ffff81007dd91e80

R10: ffff810001030b80 R11: 0000000000000246 R12: ffffffff8106e7b3

R13: ...
[ message continues ]

Why do we now have to declare this static ? Can we pass it as a pointer
Hrm, the semantic of STOPMACHINE_RUN is a bit weird :

- The CPU where the do_stop thread runs will first execute (alone) the

  callback.

- Then, all the other CPUs will execute the callback concurrently.
Given that you use a "started" boolean in the callback, which is ok as

long as there is no concurrent modification (correct given the current

semantic, but fragile), I would tend to document that the first time the

callback is called, it is ran alone, without concurrency, and then all
Note : we really want the sync_core()s to be executed after the

text_poke. This is ok given the implicit RUN_ALL semantic, but I guess

it should be documented in stop_machine that the first callback is

executed alone before all the others.
Thanks!
--

Mathieu Desnoyers

Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal

OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--

Since the other cpus need to access 'fn', i made smdata a global.

stop_machine_run() is system-wide, so we only need one of these...
thanks,
-Jason
--

-Updating immediate values, cannot rely on smp_call_function() b/c synchronizing

 cpus using IPIs leads to deadlocks. Process A held a read lock on

 tasklist_lock, then process B called apply_imv_update(). Process A received the

 IPI and begins executing ipi_busy_loop(). Then process C takes a write lock

 irq on the task list lock, before receiving the IPI. Thus, process A holds up

 process C, and C can't get an IPI b/c interrupts are disabled. Solve this

 problem by using a new 'ALL_CPUS' parameter to stop_machine_run(). Which

 runs a function on all cpus after they are busy looping and have disabled

 irqs. Since this is done in a new process context, we don't have to worry

 about interrupted spin_locks. Also, less lines of code. Has survived 24 hours+

 of testing...
Signed-off-by: Jason Baron <jbaron@redhat.com>
---
 kernel/immediate.c |   80 ++++++++++++++--------------------------------------

 1 files changed, 21 insertions(+), 59 deletions(-)
diff --git a/kernel/immediate.c b/kernel/immediate.c

index 4c36a89..378a452 100644

--- a/kernel/immediate.c

+++ b/kernel/immediate.c

@@ -20,6 +20,7 @@

 #include <linux/immediate.h>

 #include <linux/memory.h>

 #include <linux/cpu.h>

+#include <linux/stop_machine.h>
 #include <asm/cacheflush.h>
@@ -27,48 +28,33 @@

  * Kernel ready to execute the SMP update that may depend on trap and ipi.

  */

 static int imv_early_boot_complete;

+static int wrote_text;
 extern const struct __imv __start___imv[];

 extern const struct __imv __stop___imv[];
+static int stop_machine_imv_update(void *imv_ptr)

+{

+	struct __imv *imv = imv_ptr;

+

+	if (!started) {

+		text_poke((void *)imv->imv, (void *)imv->var, imv->size);

+		wrote_text = 1;

+		smp_wmb(); /* make sure other cpus see that this has run */

+	} else

+		sync_core();

+

+	flush_icache_range(imv->imv, imv->imv + imv->size);

+

+	return 0;

+}

+

 /*

  * imv_mutex nests inside module_mutex. imv_mutex prote...
[ message continues ]

Ok, I am merging it in my patchset. Note that I have additionnal patches

in my LTTng tree that implement the lockless algorithm on top of these

and does not need the stop_machine for the immediate values. Therefore,

I won't be doing much testing of these 2 patches myself.
Thanks for taking care of this,
--

Mathieu Desnoyers

Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal

OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--

-allow stop_mahcine_run() to call a function on all cpus. Calling

 stop_machine_run() with a 'ALL_CPUS' invokes this new behavior.

 stop_machine_run() proceeds as normal until the calling cpu has

 invoked 'fn'. Then, we tell all the other cpus to call 'fn'.
Signed-off-by: Jason Baron <jbaron@redhat.com>
---
 include/linux/stop_machine.h |    8 +++++++-

 kernel/stop_machine.c        |   33 +++++++++++++++++++++++----------

 2 files changed, 30 insertions(+), 11 deletions(-)
diff --git a/include/linux/stop_machine.h b/include/linux/stop_machine.h

index 5bfc553..18af011 100644

--- a/include/linux/stop_machine.h

+++ b/include/linux/stop_machine.h

@@ -8,11 +8,17 @@

 #include <asm/system.h>
 #if defined(CONFIG_STOP_MACHINE) && defined(CONFIG_SMP)

+

+#define ALL_CPUS ~0U

+

 /**

  * stop_machine_run: freeze the machine on all CPUs and run this function

  * @fn: the function to run

  * @data: the data ptr for the @fn()

- * @cpu: the cpu to run @fn() on (or any, if @cpu == NR_CPUS.

+ * @cpu: if @cpu == n, run @fn() on cpu n

+ *       if @cpu == NR_CPUS, run @fn() on any cpu

+ *       if @cpu == ALL_CPUS, run @fn() first on the calling cpu, and then

+ *       concurrently on all the other cpus

  *

  * Description: This causes a thread to be scheduled on every other cpu,

  * each of which disables interrupts, and finally interrupts are disabled

diff --git a/kernel/stop_machine.c b/kernel/stop_machine.c

index 51b5ee5..c75b4f4 100644

--- a/kernel/stop_machine.c

+++ b/kernel/stop_machine.c

@@ -23,9 +23,17 @@ enum stopmachine_state {

 	STOPMACHINE_WAIT,

 	STOPMACHINE_PREPARE,

 	STOPMACHINE_DISABLE_IRQ,

+	STOPMACHINE_RUN,

 	STOPMACHINE_EXIT,

 };
+struct stop_machine_data {

+	int (*fn)(void *);

+	void *data;

+	struct completion done;

+	int run_all;

+} smdata;

+

 static enum stopmachine_state stopmachine_state;

 static unsigned int stopmachine_num_threads;

 static atomic_t stopmachine_thread_ack;

@@ -35,6 +43,7 @@ static int stopmachine(voi...
[ message continues ]

Jason, we're actually trying to reduce the usage of the stop_machine in

general. It's a very big hammer that kills latencies and stuff. It'd be nice

if we did not introduce any more dependencies on it. I guess in some case

there is simply no other way to handle what need to do. But please think twice

(or more :)).
Max
--

Well, by definition modifying an immediate value should be very rare, so it's

a reasonable candidate.
But stop_machine needs work.  It should not be as heavy as it is.
Cheers,

Rusty.

--

please talk in your own name. Stop-machine is a very elegant tool that

simplifies a lot of hard things in the kernel and is reasonably fast as

well. We've just recently added two new usages of it and more are

planned.
_you_ might be the one who wants to 'reduce the usage of stop_machine' -

but that means it is _you_ who first has to convert a number of very

difficult pieces of code to "something else".
	Ingo

--

Sure I started the discussion but I suppose you missed Andi's and other

replies. All I said that people should think twice before relying on it.

btw I'm ok if I _am_ the _one_ who has to convert those pieces of code, that's

part of the fun :). But if people keep adding stuff which uses stom_machine

that may be pretty difficult :).
btw Being an RT guy you do not think that stop machine is evil ? I mean from

the overhead and especially latency perspective. By overhead I mean if you

have 100+ cpu box that Paul and other guys have mentioned here. Every single

CPU has to be frozen. You said it's reasonably fast. I guess it depends what's

reasonable. And from the latency perspective all bets are off. We have no

guaranties whatsoever as to hold long it will take for cpu X to get frozen

(there numerous factors here) and all the other cpus have to wait for it.

As I said for some things there is just no other way but to use the

stop_machine but we should try to minimize that as much as possible.
Max
--

i'm not "an RT guy", -rt is just one of the many projects i've been

involved with.
and no, i dont think stop machine is "evil" - it's currently the best

way to do certain things. If you can solve it better then sure, i'm

awaiting your patches - but the only patch i saw from you so far was the

one that turned off stop-machine for isolated cpus - which was

incredibly broken and ignored the problem altogether.
Right now the answer is: "if you want to do hard RT then avoid doing

things like loading modules". (which you should avoid while doing

hard-RT anyway)
	Ingo

--

Hi Ingo,
     I agree, but Max is doing a service by making more people aware of the

limitations of stop_machine so they don't sprinkle it around like candy :)
I think the module load case can be reasonably fixed; it's in my backlog now.
Cheers,

Rusty.

--

Great. I might get some time later this week to think about this some more and

try things out. So if you have ideas/suggestions let me know.
Max

--

Hmm, might be worth making stop_machine_run take a cpumask: I balked at it

originally, but introducing a section special case crosses the line I think.
Thanks,

Rusty.

--

Are you talking about a mask of which CPUs to stop  ?

That's essentially what I did with the cpu_isolated_map. But as Ingo and

others pointed out it's the wrong thing to do.

Or did you mean something else ?
Max

--

Ingo, I got it. My patch was a hack. Moving on. Seriously there is no need to

say it ten thousand times ;-).
You clipped the part where I elaborated what exactly is evil about the stop

machine. I clearly said that yes for some things there is just no other way

but in general we should _try_ to avoid it. Note that I did not say "we must"

That's just not practical. Sure you can have some kind of stripped down

machine but then you loose a lot of flexibility. Again "should" is the keyword

here. For a lot of workloads hard-RT has to coexist with a bunch of other things.
Max
--

I have a "more complex" immediate value implementation that does not

depend on such heavy lock. I made this simplified version because Rusty

preferred it, although I say from the beginning that it kills interrupt

latency. I could propose the atomic, nmi-safe version directly if enough

people are in favor of it.
Mathieu
--

Mathieu Desnoyers

Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal

OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--

to me the updating of the immdiate values isn't the critical path, but

obviously i'd be in favor of a more efficient implementation.
-Jason

--

Hrm, yes, Jan pointed out the exact same problem in my ltt-test-tsc TSC

test module in LTTng a few days ago. His fix implied to add another

barrier upon which the smp_call_function() caller must wait for the ipis

to finish. Since this immediate value code does the same I did in my

ltt-test-tsc code, the same fix will likely apply.
I'll cook something.
Hrm, does your stop machine implementation disable interrupts while the
--

Mathieu Desnoyers

Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal

OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--

yes. this is how stop_machine is implemented...and I believe is consistent with

the way in which your algorithm disables irqs. The logic to me, is we don't

want any cpus to see the kernel text in an inconsistent state via an irq.
-Jason
--

This should work. Untested for now. Can you give it a try ?
Fix Immediate Deadlock
Jason Baron <jbaron@redhat.com> :
In testing this patch, i've run across a deadlock...apply_imv_update() can get

called again before, ipi_busy_loop() has had a chance to finsh, and set

wait_sync back to its initial value. This causes ipi_busy_loop() to get stuck

indefinitely and the subsequent apply_imv_update() hangs. I've shown this

deadlock below using nmi_watchdog=1 in item 1).
Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca> :
Hrm, yes, Jan pointed out the exact same problem in my ltt-test-tsc TSC

test module in LTTng a few days ago. His fix implied to add another

barrier upon which the smp_call_function() caller must wait for the ipis

to finish. Since this immediate value code does the same I did in my

ltt-test-tsc code, the same fix will likely apply.
Thanks to Jason Baron for finding this bug and proposing an initial

implementation.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>

CC: Jason Baron <jbaron@redhat.com>

---

 kernel/immediate.c |   15 +++++++++++----

 1 file changed, 11 insertions(+), 4 deletions(-)
Index: linux-2.6-lttng/kernel/immediate.c

===================================================================

--- linux-2.6-lttng.orig/kernel/immediate.c	2008-02-26 18:16:10.000000000 -0500

+++ linux-2.6-lttng/kernel/immediate.c	2008-02-26 18:29:32.000000000 -0500

@@ -53,12 +53,12 @@ static void ipi_busy_loop(void *arg)

 	do {

 		/* Make sure the wait_sync gets re-read */

 		smp_mb();

-	} while (atomic_read(&wait_sync) > loop_data.value);

+	} while (atomic_read(&wait_sync) > 2 * loop_data.value);

 	atomic_dec(&wait_sync);

 	do {

 		/* Make sure the wait_sync gets re-read */

 		smp_mb();

-	} while (atomic_read(&wait_sync) > 0);

+	} while (atomic_read(&wait_sync) > loop_data.value);

 	/*

 	 * Issuing a synchronizing instruction must be done on each CPU before

 	 * reenabling interrupts after m...
[ message continues ]

this patch results in the subsequent 3 way deadlock that I described in the

previous mail. smp_call_function() can not be used with a function that

attempts to rendezvous cpus in the manner being done here. The patch I posted

in the previous mail addresses these limitations on smp_call_functions(). trace

of the lockup using this patch is shown below. 
thanks,
-Jason
NMI Watchdog detected LOCKUP on CPU 2

CPU 2

Modules linked in: toggle_tester ipt_MASQUERADE iptable_nat nf_nat nf_conntrack_ipv4 xt_state nf]Pid: 11233, comm: make Not tainted 2.6.24-git12markers #2

RIP: 0010:[<ffffffff811248d9>]  [<ffffffff811248d9>] __write_lock_failed+0x9/0x20

RSP: 0018:ffff81006e025e30  EFLAGS: 00000087

RAX: ffff81006ece8b58 RBX: 0000000000000000 RCX: ffff81006e1f0ec8

RDX: 0000000000000011 RSI: fe60000000000000 RDI: ffffffff813d4000

RBP: ffff81006e025e38 R08: ffff81006e1f0e90 R09: 00000000ffffffff

R10: ffff810072c45e98 R11: 0000000000004111 R12: 00000000fffffff4

R13: ffff81006ece8930 R14: ffff81006818b260 R15: 0000000000000000

FS:  00002b14168b66f0(0000) GS:ffff81007f801980(0000) knlGS:0000000000000000

CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b

CR2: 000000000106f000 CR3: 00000000680d2000 CR4: 00000000000026e0

DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000

DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400

Process make (pid: 11233, threadinfo ffff81006e024000, task ffff81006818b260)

Stack:  ffffffff8127536a ffff81006e025ed8 ffffffff81034260 ffff81006e1f0e80

 0000000000000000 0000000000000000 ffff81006e025f58 00007fff94222fe0

 0000000000004111 ffff81006ece8930 0000000000000000 ffff81006ec6f040

Call Trace:

 [<ffffffff8127536a>] ? _write_lock_irq+0x13/0x15

 [<ffffffff81034260>] copy_process+0xf7c/0x1477

 [<ffffffff81034870>] do_fork+0x75/0x20a

 [<ffffffff8100c0e9>] ? tracesys+0xdc/0xe1

 [<ffffffff8100a3c6>] sys_vfork+0x20/0x22

 [<ffffffff8100c287>] ptregscall_common+0x67/0xb0
Code: e9 07 48 89 11 31 c...
[ message continues ]