Re: [patch 06/10] Immediate Value - i386 Optimization

[Mathieu Desnoyers]

* H. Peter Anvin (hpa@xxxxxxxxx) wrote:
> Mathieu Desnoyers wrote:
> > 
> > Hi Peter,
> > 
> > I understand your concern. If you find a way to let the code be compiled
> > by gcc, put at the end of the functions (never being a branch target)
> > and then, dynamically, get the address of the branch instruction and
> > patch it, all that in cooperation with gcc, I would be glad to hear from
> > it. What I found is that gcc lets us do anything that touches
> > variables/registers in an inline assembly, but does not permit to place
> > branch instructions ourselves; it does not expect the execution flow to
> > be changed in inline asms.
> > 
> 
> I believe this is correct.  It probably would require requesting a gcc
> builtin, which might be worthwhile to do if we
> 
> > <branch site>
> >   77:   b8 00 00 00 00          mov    $0x0,%eax
> >   7c:   85 c0                   test   %eax,%eax
> >   7e:   0f 85 16 03 00 00       jne    39a <schedule+0x39a>
> >     here, we just loaded 0 in eax (movl used to make sure we populate the
> >     whole register so we do not stall the pipeline)
> >     When we activate the site,
> >     line 77 becomes: b8 01 00 00 00    mov    $0x1,%eax
> > </branch site>
> 
> One could, though, use an indirect jump to achieve, if not as good, at
> least most of the effect:
> 
> 	movl	$<patchable>,<reg>
> 	jmp	*<reg>
> 

Using a jmp *<reg> will instruct gcc not to inline inline functions and
restrict loop unrolling (but the latter is not used in the linux
kernel). We would have to compute different $<patchable> for every site
generated by putting an immediate in an inline function.

> Some x86 cores will be able to detect the movl...jmp forwarding, and
> collapse it into a known branch target; however, on the ones that can't,
> it might be worse, since one would have to rely on the indirect branch
> predictor.
> 
> This would, however, provide infrastructure that could be combined with
> a future gcc builtin.
> 

If we can change the compiler, here is what we could do:

Tell GCC to put NOPs that could be altered by a branch alternative to
some specified code. We should be able to get the instruction pointers
(think of inlines) to these nop/branch instructions so we can change
them dynamically.

Something like:

immediate_t myfunc_cond;

inline myfunction(void) {
  static void *insn;   /* pointer to nops/branch instruction */
  static void *target_inactive, *target_active;

  __builtin_polymorphic_if(&insn, &myfunc_cond) {
    /* Do something */
  } else {
    ...
  }
}

I could then save all the insns into my immediate value section and
later activate them by looking up all of those who refer to myfunc_cond.

The default behavior would be to branch to the target_inactive, and we
could change insn to jump to target_active dynamically.

Note that we should align the jump instruction so the address could be
changed atomically in the general case (on x86 and x86_64, we have to
use an int3 bypass anyway, so we don't really care).

Also, we should fine a way to let gcc tell us what type of jump it had
to use depending on how far the target of the branch is.

I suspect this would be inherently tricky. If someone is ready to do
this and tells me "yes, it will be there in 1 month", I am more than
ready to switch my markers to this and help, but since the core of my
work is kernel tracing, I don't have the time nor the ressources to
tackle this problem.

In the event that someone answers "we'll do this in the following 3
years", I might consider to change the if (immediate(var)) into an
immediate_if (var) so we can later proceed to the change with simple
ifdefs without rewriting all the kernel code that would use 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 unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/