[M3devel] function pointers and comparison to nil? mis-typed function pointers?
Randy Coleburn
rcoleburn at scires.com
Mon May 26 15:54:18 CEST 2008
I'm just "listening" here, but it would seem that much of what Rodney has stated would make for an excellent set of comments to be added to the code source file so that folks reading the code will better understand the reasoning behind what is going on.
--Randy
>>> "Rodney M. Bates" <rodney.bates at wichita.edu> 5/25/2008 11:50 PM >>>
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/6d97d1f2/attachment-0002.html>
More information about the M3devel
mailing list