Converting a func() closure into a directly callable function pointer

[Carl]

Hello,

I put up a CL for, amongst other things, a reflect.StructOf implementation where it was pointed out to me that methods inherited from embedded fields require delegate functions in the mtab.

For example:

type X int

func (x X) Ident() X {

return x

}

func f(a struct{X}) X {

return a.Ident()

}

generates the delegate

go.struct { "".X }.Ident t=1 dupok size=48 value=0 args=0x10 locals=0

000000 00000 (<autogenerated>:2) TEXT go.struct { "".X }.Ident+0(SB),38,$0-16

000000 00000 (<autogenerated>:2) MOVQ (TLS),CX

0x0009 00009 (<autogenerated>:2) NOP ,

...

such that a.X.Ident() may be called as a.Ident()

Unfortunately, this means to complete my reflect.StructOf implementation I will need to do some messy code generation. To avoid actually emitting the instructions, I figure I can copy some compiled code which calls a func() closure into a buffer and execute that. My current attempt looks something like this

0x00 [pointer_to_closure]

0x08 [code]

0x10 ...

The pointer value is stored relative to the code entry point, hence it's location can be computed using runtime.getcallerpc without probing it into [code].

However, I am segfaulting when I "call" [code], presumably due to the heap not being executable. The actual trampoline code looks like this

TEXT ·closureWrapper(SB),(NOSPLIT|WRAPPER),$0

        CALL ·closureCall(SB)

        RET ,

TEXT ·closureCall(SB),(NOSPLIT|WRAPPER),$0

        CALL runtime·getcallerpc(SB)

        MOVQ -8(AX),BX // Load pointer_to_closure, -8 not correct offset here

        MOVQ (BX),DX // Load closure to DX

MOVQ (DX),BX // Load closure.fn to BX

CALL BX

RET ,

Before pursuing further pursuing this approach I'd like to get some feedback. To construct a valid mtab for StructOf, I need to somehow generate these delegates, and I feel wrapping a func() in directly callable code is a relatively simple solution. An alternative is to change the runtime such that methods in an mtab are pointers to closures rather than raw function pointers.

Thoughts or Suggestions? I suppose the next step is to work out how to allocate executable heap memory.

Thank you.

--
Carl

[minux]

On Jul 6, 2014 8:57 PM, "Carl" <carlch...@gmail.com> wrote:
> Thoughts or Suggestions? I suppose the next step is to work out how to allocate executable heap memory.

please don't use runtime code generation. we tried very hard to remove that requirement for function closures so that there is one less possible security hole (no writable section is executable), and make it possible to run Go programs on platforms that disallow dynamic code generation (e.g. iOS).

[Carl]

What are your thoughts on closures in the mtabs and itabs? If it is as you say I don't see another option for a complete reflect package.

Carl

2014/07/06 21:10 "minux" <mi...@golang.org>:

[Ingo Oeser]

One very simple solution might be, to just document the constraints under which StructOf doesn't work and make the call fail/panic with an appropriate message.

Once a better solution is found, it can be enhanced. Maybe even in a later version of Go.

Especially considering the (security) price of re-introducing runtime code generation.

[Ian Lance Taylor]

It's not OK to use runtime code generation or to have any memory that
is writable and executable.

Fortunately you don't need it. You can manually construct a closure
that points to constant code such that the closure tells the code what
to do. The closure would presumably contain an offset and a code
pointer. Your function would offset the argument, and jump to the
code pointer.

Look at reflect.MakeFunc for examples of this technique.

I agree with others that the first pass doesn't need to implement
this.

Ian

[Carl]

Hello again,

I believe MakeFunc solves a slightly different problem, where the func value created can only ever be called by the 'CALL DX,BX' convention. I am aware of the technique used, but ultimately it is only possible due to an arbitrary pointer received through DX.

My problem is different, as I need to populate the methods table with function pointers that are called directly, granted a reference to 'this' is received through 0(FP).

In my head I have a somewhat unconvincing proof that with the itab calling convention alone, it is impossible to populate the itab using only compile time code.
1. There is a limited amount of code in an executable.
2. There are infinite structs which can be created at runtime.
3. Therefore there cannot be compiled delegates for all structs.

This only holds true if the compiled delegates receive no information that would allow them to tailor themselves to the delegated method. The information available is merely the underlying struct at 0(FP). The information required is the underlying struct, its type, and the method name. The method name could theoretically be computed by inspecting the stack (callers) but the type is lost.

If I am missing something let me know. The only solution I can think of is to change the calling convention to a combination of '0(FP) this' call and 'CALL DX,BX' for itab methods.

Thank you

Carl

2014/07/07 11:02 "Ian Lance Taylor" <ia...@golang.org>:

[Ian Lance Taylor]

On Mon, Jul 7, 2014 at 10:33 PM, Carl <carlch...@gmail.com> wrote:
>
> I believe MakeFunc solves a slightly different problem, where the func value
> created can only ever be called by the 'CALL DX,BX' convention. I am aware
> of the technique used, but ultimately it is only possible due to an
> arbitrary pointer received through DX.
>
> My problem is different, as I need to populate the methods table with
> function pointers that are called directly, granted a reference to 'this' is
> received through 0(FP).
>
> In my head I have a somewhat unconvincing proof that with the itab calling
> convention alone, it is impossible to populate the itab using only compile
> time code.
> 1. There is a limited amount of code in an executable.
> 2. There are infinite structs which can be created at runtime.
> 3. Therefore there cannot be compiled delegates for all structs.
>
> This only holds true if the compiled delegates receive no information that
> would allow them to tailor themselves to the delegated method. The
> information available is merely the underlying struct at 0(FP). The
> information required is the underlying struct, its type, and the method
> name. The method name could theoretically be computed by inspecting the
> stack (callers) but the type is lost.
>
> If I am missing something let me know. The only solution I can think of is
> to change the calling convention to a combination of '0(FP) this' call and
> 'CALL DX,BX' for itab methods.

Ah, sorry, you're quite right. Method calls don't use a closure
pointer.

I don't know whether it's worth changing the calling convention for
this. It's obviously a very unusual case.

It seems to me that the only way to get and use values of this newly
created struct type are via reflection. And the only time we are
going to get confused is when converting a value of the struct type to
an interface value. Perhaps we could keep track of all struct values
converted to interfaces in this way in a map on the side. That map
could then be used when a method is called to determine the type of
the struct. Then all we need is the method index--not the method
index of the interface, but the method index in the created type. I
suppose we could set a limit on the number of methods we're prepared
to support in a created type, and create stub methods for the first,
say, 256 method indexes. Then creating a type would refer to those
stubs.

It seems pretty baroque and I don't know if it's worth it.

In any case, sorry, no code generation at runtime.

Ian

[Russ Cox]

This is the same reason that there is no reflect.MakeInterface. I don't know what the right answer is. Adding an almost always useless instruction to every call seems like a mistake.

[Ian Lance Taylor]

But to be clear I think it's fine to proceed with MakeStruct as long
as we reject the case where the struct inherits methods from anonymous
fields.

Ian

[Rob Pike]

If it's not worth doing well, it's not worth doing at all.

-rob

> --
> You received this message because you are subscribed to the Google Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Ian Lance Taylor]

On Wed, Jul 9, 2014 at 10:12 AM, Rob Pike <r...@golang.org> wrote:
>
> If it's not worth doing well, it's not worth doing at all.

In general, sure, but not here. I can think of a few reasons to want
to use MakeStruct, but none of them involve having an anonymous field
with methods and having the new struct inherit the methods. Actually
I can't think of any reason why anybody would want that functionality
at all. I can think of reasons to add methods to a type created by
reflect--a functionality we don't and probably won't support--but I
can't think of any reason to make a new struct type that inherits
methods via anonymous fields.

Ian

[Rob Pike]

But the very existence of an inscrutable corner case is an argument
agains the idea, or at least a strong point in favor of proceeding
cautiously.

-rob

[Russ Cox]

I'd really rather not add to reflect in this cycle. We have a lot going on already.

[Ian Lance Taylor]

On Wed, Jul 9, 2014 at 10:36 AM, Rob Pike <r...@golang.org> wrote:
>
> But the very existence of an inscrutable corner case is an argument
> agains the idea, or at least a strong point in favor of proceeding
> cautiously.

I think this is proceeding cautiously. We say that MakeStruct does
not permit anonymous fields. Then there is no problem.

(I'm fine with Russ's request to delay, of course.)

[Gustavo Niemeyer]

On Wed, Jul 9, 2014 at 2:23 PM, Ian Lance Taylor <ia...@golang.org> wrote:
> On Wed, Jul 9, 2014 at 10:12 AM, Rob Pike <r...@golang.org> wrote:
>>
>> If it's not worth doing well, it's not worth doing at all.
>
> In general, sure, but not here. I can think of a few reasons to want
> to use MakeStruct, but none of them involve having an anonymous field
> with methods and having the new struct inherit the methods. Actually
> I can't think of any reason why anybody would want that functionality
> at all. I can think of reasons to add methods to a type created by
> reflect--a functionality we don't and probably won't support--but I
> can't think of any reason to make a new struct type that inherits
> methods via anonymous fields.

Dynamically creating types that satisfy an interface while carrying
additional data?

I agree with Rob. Feels like an implementation detail leaking as an
edge case that disagrees with the spec.


gustavo @ http://niemeyer.net

[Rob Pike]

Taking steps where you don't know how to complete the journey is not
proceeding cautiously. Putting in incomplete support like this feels
very wrong to me.

-rob

[Alan Donovan]

On Wednesday, 9 July 2014 18:50:52 UTC+1, Ian Lance Taylor wrote:

On Wed, Jul 9, 2014 at 10:36 AM, Rob Pike <r...@golang.org> wrote:
>
> But the very existence of an inscrutable corner case is an argument
> agains the idea, or at least a strong point in favor of proceeding
> cautiously.

I think this is proceeding cautiously.  We say that MakeStruct does
not permit anonymous fields.  Then there is no problem.

I think Ian is right here: the limitations are easy to understand, the unimplemented case is not obviously useful, and the basic feature enables things that cannot currently be accomplished within the language, period (e.g. writing a Go interpreter that uses the host garbage collector).

[Carl]

I find myself, a complete newcomer to compiler and language design,
attempting to make my case to some very smart people. There are a few
points to respond to, but let me first pare my argument down to its
simplest form.

The reflect package is incomplete, as it lacks ArrayOf (issue #5996),
FuncOf, IntrefaceOf, StructOf (issue #5748), and NamedOf.

There are several points which if convincingly argued would persuade
me to drop my case entirely:
1. Go doesn't need a complete reflect system
2. Now is not the time to complete the reflect system
3. The overhead of completing the reflect system outweighs the benefit

On Wed, Jul 9, 2014 at 2:09 PM, Alan Donovan <adon...@google.com> wrote:
>
> I think Ian is right here: the limitations are easy to understand, the unimplemented case is not obviously useful, and the basic feature enables things that cannot currently be accomplished within the language, period (e.g. writing a Go interpreter that uses the host garbage collector).
>

Ironically enough, this was exactly what I was doing when I started
hacking on reflect. In other words, I want reflect to do everything. I
also adhere to the "if it's worth doing, do it right" sentiment.

To overcome the current hurdle, I would like to make a proposal that
changes the calling convention with minimal impact on the generated
code and performance. But first let me define the problem by
considering the below code.

type X int
func (x X) Ident() X { return x }

type I interface { Ident() X }

func main() {
// Construct a new struct type containing an anonymous field
xt := reflect.TypeOf(X(0))
ft := reflect.StructField{Type: xt} // Anonymous field of type X
st := reflect.StructOf([]reflect.StructField{ft})
// Create a new st, which should satisfy I.
i = reflect.New(st).Elem().Interface().(I)
}

The itable for i is populated with function pointers, in this case
those functions simply delegate the methods of X to the anonymous
struct field of type X. The problem is that these delegates are
specific to the constructed struct type, and therefore cannot be
generated at compile time. Instead, a generic delegate function can be
used, but at a minimum it must determine
1. The value of the underlying type (easy, as functions in the itab
receive this as their first argument)
2. The type of this value
3. The position of the function called in the struct's mtab
4. The type of this function, for computing stack layout (can be
computed from 2 and 3)

My proposal for point 2 is to change the interface calling convention
to require that a pointer to the itab is passed in an agreed register.
Below is a commented version of the x64 instructions generated by gc
for 'i.Ident()', an interface call on i in the above example. See
6g/ggen.c cgen_callinter()

0x01e1 MOVQ 24(SP),CX // REG = 0(REG) -- i.tab
0x01e6 MOVQ 32(SP),AX // 0(SP) = 8(REG) -- i.data
0x01eb MOVQ AX,"".i+120(SP) // What is this, where did it come from?
0x01f0 MOVQ AX,(SP) // 0(SP) = 8(REG) -- i.data, first argument to
function in mtab
0x01f4 MOVQ CX,"".i+112(SP) // And this?
0x01f9 NOP ,
0x01f9 MOVQ 32(CX),BX // REG = 32+offset(REG) -- i.tab->fun[f]
0x01fd PCDATA $0,$16
0x01fd PCDATA $1,$0
0x01fd CALL ,BX // Call method

Note that CX holds the itab pointer, which contains a pointer to the
dynamic type as required. At some call sites, the fn pointer load is
optimised to MOVQ 32(BX),BX, my proposal is simply to make this
optimisation illegal.

Solving point 3, calculating the function's mtab index, is more
intrusive but I see two options.

a. Generate a large number of trampoline functions which each call the
delegate function with a different index argument. Panic if the number
of methods is greater than the number of trampolines.
pros: no code changes, no overhead
cons: binary bloat, ceiling on number of methods

b. Add the Store the itab->mtab mapping in the Itab struct and pass
the offset in another register. It's going to be trashed anyway right?

pros: does not have limitation in number methods
cons:
requires additional constant MOV instruction. I'm certain people on
this thread have a better understanding of the implications here than
I do.
itab->mtab mapping must be stored, this is already computed but not
stored, and would effectively double the size of the Itab struct.
However, this mapping need only be computed for types created via
reflect.

I am of course in favour of option b, as I said I want everything.


Now going back through a couple of concerns that have been raised.

> Adding an almost always useless instruction to every call seems like a mistake.

Agreed, I suppose the counter argument is that this only applies to
interface calls, which already have significant overhead anyway, the
incremental damage wont be huge (I think (TM) )
There is always the other option of using multiple trampolines, or
something fancy like an INC slide.

> I'd really rather not add to reflect in this cycle. We have a lot going on already.

I believe the changes I have proposed above are relatively
non-intrusive, and would not require any change in how existing
functions receive their arguments. At any rate, I am happy to continue
my fork as long as there is support for integrating it at some point
in the future.


Anyway, this email is already long enough. I have made my case and my
proposal, let me know what you think.

--
Carl