On Sun, 04 Jun 2000, Peter T. Breuer wrote:
>> GCC use lexical scoping for nested function, lexical scoping use
>> trampolines... so it will break...
>
>This is goobledegook. Lexical scoping is precisely what I was referring
>to by "a question of namespaces and syntactic scoping". It's a parsing
>detail, or a compiler detail, _not_ an implementation strategy. There
>is no more need to invoke a special implementation strategy for nested
>functions than there is to invoke one for nested blocks.
Wrong. Try generating code for
int C(int (*f)(int), int x)
{
return (*f)(x);
}
int D(int x)
{
return 2 * x;
}
int A(int x)
{
int B(int y)
{
return x + y;
}
return B(1) + C(B, 2) + C(D, 3);
}
int main()
{
printf("Result = %d\n", A(10));
return 0;
}
without making function C aware it calling a nested function one
time and a non-nested function the next one.
(BTW, the result is 29.)
Every syntactic construct requires some semantic support. Some
require essentially nothing that's not already implicit in the
language (nested blocks, is an example), while some require a few
contortions (passing a nested function pointer to another function,
is the example in question).
Just in case the point of this particular piece of code is lost on
some, let me elaborate a bit. When A() calls B(), B() could in
principle find A()'s parameter x in a particular place up its stack
frame. But when C() calls B() indirectly through a pointer, B()'s
stack frame does not contain A()'s x in the "expected" place. In
fact, B() could have been be called via an arbitrarily long and
convoluted series of nested function calls, so there is no way to
know ahead of time where in the stack is A()'s parameter x.
A possible solution could be to, in principle, pass (as a hiddden
argument, for instance) a pointer to A()'s stack frame whenever we
pass B()'s address (in effect extending B()'s passed address with
A()'s frame address and thus creating an "extended" function pointer).
But then what do we do in the case of C(), that is called both with
the B's() address (which ostensibly would require such a hidden
argument) and C()'s address (which doesn't)? Shall we then require
that all function pointers be of the "extended" kind, and therefore
force non-standard semantics and unneeded overhead on all calls to
non-nested function pointers, which are the vast majority of all such
calls? Shall we try to convince language implementors to banish
nested function declaration from all languages that include it? Or
shall we try to find some alternative.
The USENIX paper, after arguing the usefulness of nested functions
(and especially anonymous nested functions), proposes an
implementation. The method consists in creating a "trampoline": a
piece of code that behaves to C() like a regular, non-nested
function, and passing that trampoline address to C(). So, when
C() calls (*f)(), it is actually calling the trampoline and not B().
The trampoline would then call B() with the proper environment (stack
frame, etc.) so that B() executes as if called directly from within
A(). In this way C() doesn't have to "know" about nested and
non-nested functions, and B() doesn't have to know about being called
directly from A() or indirectly through some pointer.
Nice exercise for the student: try to devise an efficient way (other
than the well-known "trampoline" solution) to implement nested
function calls via a pointer without requiring stack manipulations
that could trigger detectors for "stack buffer overrun" (and similar)
attacks. If you succeed, submit the results of your research to both
the GCC maintainers and the implementers of any other language that
includes nested functions and function pointers. And please don't
forget to post a note to LK so we can finally lay this thread to rest.
-- Leo Mauro Seguridad de Redes Dirección de Servicios Telemáticos Universidad Simón Bolívar- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Wed Jun 07 2000 - 21:00:19 EST