[M3devel] function pointers and comparison to nil? mis-typed function pointers?

Mon May 26 07:26:41 CEST 2008

Rodney, this agrees with much of what I figured out and guessed. I did not think of or look into some of what you point out though:
  - what gcc's nested functions look like, and if you can take the address, and what that does 
  - calling Modula-3 nested functions as callbacks from C 

Now, regarding trampolines.
I alluded to them. It should be easy enough to generate them, and this would solve a few problems, but I believe also bring up a new big problem.
Generating trampolines solves at least two problems: 
 - it allows Modula-3 nested function pointers ("closures") to be called from C 
 - it enables removing the check for -1 

I contend that the check for -1 is not good. It is a somewhat risky assumption, that "-1" is not valid code.
You do bring up a nice mitigation -- the assumption that it doesn't begin any functions, which is much narrower than it being valid code anywhere.

For SPARC64_OPENBSD I figured out what the original authors meant to be the fix.
You declare functions as not aligned, leading to the check for -1 first checking alignment (bigger code).
Any pointer not aligned on an integer-sized address is presumed not a closure and not checked for the -1.
This lets SPARC64_OPENBSD get further. Both it and PPC32_OPENBSD now for some reason suffer from an inability to heap allocate anything, failing around the attempt to create a new thread like in RTAllocator_M or so. I'll look into this more later.
Now, the problem of trampolines..I consider the platform-dependent-ness to be surmountable.
But where do you put the generated code? Putting it on the stack is counter to modern (and possibly old) "security" mechanisms.
The stack is not generally executable, and even when it is, best just not do use that imho.

That means, potentially/obviously, the need to heap allocate executable memory, for very small short lived data, quite inefficient.

Is there some other way/place to produce trampolines, efficiently?

In the absence of any good solution, I have to resign myself to assuming that -1 isn't the valid start of a function, and perhaps moving the marker into Target.i3, Target.m3 so that "more obvious" values get chosen. Like a breakpoint. Or "an epilogue", or "a trap instruction". I realize this needs details and is easily seen as "wrong". In particular, a function that does nothing could be termed as only having an "an epilogue".

I know that other systems are "forced" to create "trampolines" so I should look into how they do that.
I know that ATL, a Windows-specific library, is forced to heap allocate small executable chunks of memory and uses an efficient cache to optimize it.

I do find this dependence on -1 not being the valid start of a function rather sleazy and at risk of being wrong.

 - Jay

> Date: Sun, 25 May 2008 22:50:15 -0500> From: rodney.bates at wichita.edu> To: m3devel at elegosoft.com> Subject: Re: [M3devel] function pointers and comparison to nil? mis-typed function pointers?> > I think I can shed some light on this, having spent some time making> m3gdb handle the various operations on nested procedures. As for code> that mixes M3 and C, I believe the following are true:> > - Within M3 code only, the closure system works correctly in all cases.> This answers one of Jay's worries.> > - For values of M3 procedure/C function pointer that are top-level> (nonnested) procedures/functions, M3 and C code (generated by gcc,> at least) are interchangeable. This answers another of Jay's worries.> This will cover that great majority of cases.> > - Standard C has no nested functions. Gcc adds them as a language> extension. Thus, only in gcc-compiled C code do we need to worry> about nested procedures/functions between languages. (Do any other> C compilers exist that also have nested functions?)> > - M3 code should be able to call the value of a procedure variable> that was originally produced by C code as a pointer to a nested> function, and get the environment set up right, so its nonlocal> variable references will work, _if_ the nested function's> environment has not disappeared. This partially answers another> of Jay's worries. But:> > - M3's normal runtime check that precludes assigning a nonlocal> procedure value will not detect a C-code-produced nonlocal value,> thus the environment could indeed have disappeared if the programmer> was not careful. However, gcc-extended C's nested functions have> no protection against this bug when only C code is involved, so> perhaps not detecting it in mixed M3/C is to be expected.> > - C code that attempts to call a function pointer value that was> originally produced by M3 code as a nested procedure value will> almost certainly crash at the time of the call. This is the only> case that presents a significant problem. M3 code will not be> able to give a nested procedure as a callback to a C library.> > M3's mechanism: A value of procedure type is a pointer to either> 1) the first byte of the procedure's machine code, if it is top level, or> 2) A closure.> > A closure is a block of 3 words. The first word contains -1. Assuming> a word of all one bits is not valid machine code on any target machine> (or at least doesn't occur as the first code of any procedure), this can> be used at runtime to detect that this is indeed a closure and not code.> The remaining two words hold the code address and the environment address.> > So, an assignment of a procedure value has to check that it is not a closure,> and raise a runtime error if it is. A call on a procedure value has to check,> and if it is a closure, load/copy its environment pointer value into wherever> the calling convention expects it, then branch to the code address. Passing> a nested procedure constant as a parameter involves constructing a closure for> it and passing its address.> > gcc-C's mechanism: A value of type pointer to function is a pointer to either> 1) the first byte of the function's machine code, if it is top level,> (the same as with M3), or> 2) A trampoline.> > A trampoline is a bit of code that loads/copies an environment pointer (hard> coded into the trampoline) and then branches to the function code.> > Trampolines probably have a small constant-time speed advantage for _calls_,> but would be slower for some of the other operations, and the runtime check> could be tricky. Probably it could be fooled into failing when it shouldn't.> Moreover, trampolines are highly target-machine-dependent. Switching to them> would create a really big problem for m3gdb, which would have to have> different code for each target for each of the nested procedure operations.> > Jay wrote:> > I see somewhat.> > It's stuff around "closure".> > The comparison of code bytes to -1 comes from If_closure for example.> > > > The problem is presumably to come up with a unified representation of > > pointers to functions that may or may not be nested, while avoiding > > runtime codegen, even just a little bit, and for Modula-3 and C function > > pointers to use the same representation.> > I don't think the present solution is really valid, and I am skeptical > > that there is a solution.> > One of the requirements has to be dropped.> > Sniffing code bytes and trying to decide if they are code or not as > > appears to currently happen is bogus.> > > > I think the solution is to remove the requirement that a Modula-3 > > function pointer and a C function pointer are the same.> > Except, well, that probably doesn't work -- it means you need two types > > of function pointers.> > > > Darn this is a hard problem.> > > > The runtime codegen required can be exceedingly simple, fast, and small > > IF it were allowed to be on the stack. But that's a killer these days.> > > > I think you have to give up unification of "closures" and "function > > pointers".> > If you take the address of a nested function and call it, you cannot > > access the locals of the enclosing scopes.> > So in affect, you end up with "two types of function pointers".> > Regular stateless ones and "closures" with some captured state.> > > > Thoughts?> > > > I'm kind of stumped. It's a desirable problem to solve, and there is a > > purported solution in place, but the solution that is there is > > completely bogus, despite appearing to work for a long time, and there > > is no solution. That is my understanding. I could be wrong on any number > > of points but I'm pretty sure.> > > > I think you have to separate out function pointers and closures.> > Sniffing what it pointed to is dubous esp. as currently implemented.> > If this is really the way to go, then signature bytes need to be worked > > out for all architectures that are guaranteed to not look like code.> > Or vice versa -- signature bytes worked out that all functions start > > with, which is viable for Modula-3 but not for interop with C.> > Currently -1 is used, of pointer-size.> > That appears to be reasonable for x86:> > > > 0:000> eb . ff ff ff ff> > 0:000> u .> > ntdll32!DbgBreakPoint:> > 7d61002d ff ???> > 7d61002e ff ???> > 7d61002f ff ???> > 7d610030 ffc3 inc ebx> > > > but the instruction encodings or disassembly on other architectures > > would have to be checked.> > > > - Jay> > > > ------------------------------------------------------------------------> > From: jayk123 at hotmail.com> > To: m3devel at elegosoft.com> > Date: Sun, 25 May 2008 00:16:01 +0000> > Subject: [M3devel] function pointers and comparison to nil?> > mis-typed function pointers?> > > > I'm being lazy...> > > > Tony can you explain this stuff?> > > > Comparison of function pointers..> > What are the various representations and rules?> > > > What does it mean to compare nested functions?> > > > What does it mean to compare a function to NIL?> > > > I'll poke around more.> > > > What I am seeing is that comparison of function pointers to NIL is> > surprisingly> > expensive, and probably somewhat buggy. Or at least some of the runtime> > generated "metadata-ish" stuff is produced or typed incorrectly.> > > > In particular, RTLinker.m3:> > > > PROCEDURE AddUnit (b: RT0.Binder) => > VAR m: RT0.ModulePtr;> > BEGIN> > IF (b = NIL) THEN RETURN END; line 119> > m := b(0); line 120> > IF (m = NIL) THEN RETURN END; line 121> > AddUnitI(m); line 122> > END AddUnit;> > > > generates a lot of code, just for the first line:> > (556) set_source_line > > source line 119 > > (557) load > > m3cg_load (M3_DjPxE5_b): offset 0x0, convert 0xb -> 0xb > > (558) load_nil > > (559) if_eq > > (560) load > > m3cg_load (M3_DjPxE5_b): offset 0x0, convert 0xb -> 0xb > > (561) load_indirect > > load address offset 0x0 src_t 0x5 dst_t 0x5 > > (562) load_integer > > integer n_bytes 0x0 hi 0x0 low 0x1 sign -1 > > (563) if_eq > > (564) set_label > > (565) load_nil > > (566) load > > m3cg_load (M3_DjPxE5_b): offset 0x0, convert 0xb -> 0xb > > (567) if_ne > > (568) set_label > > (569) exit_proc > > (570) set_label > > (571) set_source_line > > source line 120 > > > > The details on the load_integer trace might not be completely> > correct. I will test a fix shortly.> > Esp. that n_bytes gets decremented to zero before the trace.> > > > Ok, I see now why some of the bloat -- because the "then return end"> > is on the same line.> > If it were written as:> > if (b = NIL THEN > > return> > end > > It probably wouldn't look so bad. That took me a while to realize.> > > > The following is generated for SPARC64_OPENBSD:> > > > line 119> > .stabn 68,0,119,.LLM61-.LLFBB4> > .LLM61:> > ldx [%fp+2175], %g1> > brz %g1, .LL26> > nop> > ldx [%fp+2175], %g1> > ldx [%g1], %g1 bus error here? yes, probably this one> > cmp %g1, -1> > be %xcc, .LL27> > nop> > .LL26:> > ldx [%fp+2175], %g1> > brz %g1, .LL33> > nop> > .LL27:> > line 120> > .stabn 68,0,120,.LLM62-.LLFBB4> > .LLM62:> > ldx [%fp+2175], %g1> > stx %g1, [%fp+2007]> > ldx [%fp+2007], %g1> > brz %g1, .LL30> > nop> > ldx [%fp+2007], %g1> > ldx [%g1], %g1 or here ?> > cmp %g1, -1> > bne %xcc, .LL30> > nop> > ldx [%fp+2007], %g1> > add %g1, 16, %g1> > ldx [%g1], %g1 or here?> > stx %g1, [%fp+2015]> > ldx [%fp+2007], %g1> > add %g1, 8, %g1> > ldx [%g1], %g1> > stx %g1, [%fp+2007]> > .LL30:> > ldx [%fp+2007], %g1> > ldx [%fp+2015], %g5> > mov 0, %o0> > call %g1, 0> > nop> > mov %o0, %g1> > stx %g1, [%fp+2023]> > ldx [%fp+2023], %g1> > stx %g1, [%fp+1999]> > > > line 121> > > > .stabn 68,0,121,.LLM63-.LLFBB4> > .LLM63:> > ldx [%fp+1999], %g1> > brz %g1, .LL33> > nop> > .LL32:> > .stabn 68,0,122,.LLM64-.LLFBB4> > .LLM64:> > > > g1 points to RTSignal_I3> > > > (gdb) x/i $pc> > 0x3ff0a8 <RTLinker__AddUnit+28>: ldx [ %g1 ], %g1> > (gdb) x/i $g1> > 0x4021f4 <RTParams_I3>: save %sp, -208, %sp> > > > I am willing to accept that a "function pointer" is a pair of> > pointers, or even three pointers.> > A pointer to code, a pointer to globals for position independent> > code, a frame pointer to locals.> > That equality comparison of function pointers requires comparing two> > (or three) pointers.> > (Though the global pointer shouldn't need comparing.)> > At least for nested functions. Less so for non-nested. ?> > Much less for comparison to NIL. ?> > > > And either way, this code is reading bogus data.> > There isn't a pointer at the function address, there is code.> > > > Something doesn't add up.> > > > I'm going to try setting "aligned procedures" but that's quite bogus> > I think.> > > > EqualExpr.m3 says> > > > Note: procedures pointers are always aligned!> > > > but maybe not?> > > > Yeah yeah I'm being lazy. I'll read more code..> > > > I also wonder if a "function pointer" can be optimized for the case> > of not being to a nested function.> > It looks like calling a function pointer is very inefficient.> > It looks like..am I reading that correctly?.. that if the pointer> > points to -1, then it is nested and> > a pair of pointers, and not otherwise. That -1 is treated specially> > as the first bytes of a function?> > Is that a Modula-3-ism or a SPARC-ism?> > It looks like a Modula-3-ism. And it seems dubious.> > But I'll have to read more..> > > > NT386GNU does the same sort of wrong looking thing:> > > > LFBB4:> > pushl %ebp> > movl %esp, %ebp> > subl $24, %esp> > LBB5:> > .stabn 68,0,117,LM60-LFBB4> > LM60:> > movl $0, -16(%ebp)> > .stabn 68,0,119,LM61-LFBB4> > LM61:> > movl 8(%ebp), %eax> > testl %eax, %eax> > je L26> > movl 8(%ebp), %eax> > movl (%eax), %eax BAD> > cmpl $-1, %eax BAD> > je L27> > L26:> > movl 8(%ebp), %eax> > testl %eax, %eax> > je L33> > L27:> > .stabn 68,0,120,LM62-LFBB4> > LM62:> > > > > > and NT386:> > > > 0:000> u> > cm3!RTLinker__AddUnit:> > 00607864 55 push ebp> > 00607865 8bec mov ebp,esp> > 00607867 81ec0c000000 sub esp,0Ch> > 0060786d 53 push ebx> > 0060786e 56 push esi> > 0060786f 57 push edi> > 00607870 c745fc00000000 mov dword ptr [ebp-4],0> > 00607877 837d0800 cmp dword ptr [ebp+8],0> > 0:000> u> > cm3!RTLinker__AddUnit+0x17:> > 0060787b 0f840f000000 je cm3!RTLinker__AddUnit+0x2c (00607890)> > 00607881 8b7508 mov esi,dword ptr [ebp+8]> > 00607884 8b5e00 mov ebx,dword ptr> > [esi] BAD > > 00607887 83fbff cmp > > ebx,0FFFFFFFFh BAD> > 0060788a 0f840f000000 je cm3!RTLinker__AddUnit+0x3b (0060789f)> > 00607890 837d0800 cmp dword ptr [ebp+8],0> > 00607894 0f8505000000 jne cm3!RTLinker__AddUnit+0x3b (0060789f)> > 0060789a e969000000 jmp cm3!RTLinker__AddUnit+0xa4 (00607908)> > > > cm3!RTLinker__AddUnit+0x20:> > 00607884 8b5e00 mov ebx,dword ptr [esi] > > ds:002b:0062c950=81ec8b55> > 0:000> u @esi> > cm3!RTLinker_I3:> > 0062c950 55 push ebp> > 0062c951 8bec mov ebp,esp> > 0062c953 81ec00000000 sub esp,0> > 0062c959 53 push ebx> > 0062c95a 56 push esi> > 0062c95b 57 push edi> > 0062c95c 837d0800 cmp dword ptr [ebp+8],0> > 0062c960 0f8400000000 je cm3!RTLinker_I3+0x16 (0062c966)> > > > This is just wrong.> > Comparing bytes of code to -1.> > > > I think the likely fix is for the "I3" code to be laid out as a> > "constant function pointer", a pointer to a pair of pointers where> > one points to the code and one is to -1. Something like that. That> > can't be quite correct given that the existing data is callable.> > > > - Jay> > -- > -------------------------------------------------------------> Rodney M. Bates, retired assistant professor> Dept. of Computer Science, Wichita State University> Wichita, KS 67260-0083> 316-978-3922> rodney.bates at wichita.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20080526/089839a1/attachment-0002.html>