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