Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
A question about an implementation of lisp GC and control stack.
101 views
Skip to first unread message
loves...@gmail.com
Dec 20, 2011, 4:02:08 AM12/20/11
to
Hi. Are there any lisp system developers online?
I'm writing my own toy CL-like language, and i'm very interested in GC implementation on x86 and other such systems where lisp control stack is shared with C.
I mean, i cannot understand how the stack is examined - in the presence of FFI, the stack can contain raw C data, and so we cannot distinguish such data from lisp pointers. As i understand, this requires "conservative" garbage collector implementation. But then, how to look for GC roots on the stack, anyway? Can you please point to some articles/books describing such GC implementations(particularly, implementations for lisp-like languages)?
On the other side - if the control stack is separated from "number" stack, how proper unwinding semantics could be implemented(i mean, lisp unwinding should also reflect on C stack, so we can use such things as windows SEH to implement unwind-protect and friends)?
I'm writing my own toy CL-like language, and i'm very interested in GC implementation on x86 and other such systems where lisp control stack is shared with C.
I mean, i cannot understand how the stack is examined - in the presence of FFI, the stack can contain raw C data, and so we cannot distinguish such data from lisp pointers. As i understand, this requires "conservative" garbage collector implementation. But then, how to look for GC roots on the stack, anyway? Can you please point to some articles/books describing such GC implementations(particularly, implementations for lisp-like languages)?
On the other side - if the control stack is separated from "number" stack, how proper unwinding semantics could be implemented(i mean, lisp unwinding should also reflect on C stack, so we can use such things as windows SEH to implement unwind-protect and friends)?
Frode V. Fjeld
Dec 20, 2011, 4:45:19 AM12/20/11
to
loves...@gmail.com writes:
> I'm writing my own toy CL-like language, and i'm very interested in GC
> implementation on x86 and other such systems where lisp control stack
> is shared with C.
I suspect you need some mechanism that clearly marks out the C portions
> I'm writing my own toy CL-like language, and i'm very interested in GC
> implementation on x86 and other such systems where lisp control stack
> is shared with C.
of the stack as part of the FFI calling conventions. This would
presumably include information about (potential) live pointers held by
C, and possibly also you'd want a set of C functions that informs the
lisp runtime of additional live pointers.
--
Frode V. Fjeld
Duane Rettig
Dec 21, 2011, 2:24:03 PM12/21/11
to
Yes. However, I'm not sure how much I can help, since I'm actively
developing and getting to year-end deadlines...
> I'm writing my own toy CL-like language, and i'm very interested in GC implementation on x86 and other such systems where lisp control stack is shared with C.
>
> I mean, i cannot understand how the stack is examined - in the presence of FFI, the stack can contain raw C data, and so we cannot distinguish such data from lisp pointers. As i understand, this requires "conservative" garbage collector implementation. But then, how to look for GC roots on the stack, anyway? Can you please point to some articles/books describing such GC implementations(particularly, implementations for lisp-like languages)?
>
> On the other side - if the control stack is separated from "number" stack, how proper unwinding semantics could be implemented(i mean, lisp unwinding should also reflect on C stack, so we can use such things as windows SEH to implement unwind-protect and friends)?
It seems you have a good understanding of the tradeoffs; the former
has identification problems, and the latter has synchronization
problems, especially during unwinding. It seems to be easiest to push
the stack structure decisions off to gc, rather than to actively
manage the stack at run-time; consider that a gc might not happen
during 10 advances and retreats of the stack, and so all of that stack
management while building and tearing down the stack is wasted.
Better to put as little control data on the stack as possible. and
have the gc do the work, at the time it is actually needed.
Another issue, assuming a decision has been made for a shared control
stack, is how to mark the stack, when C programs know nothing about
such marking. Clearly, unless you want to force C users into a
particular calling discipline (which then locks out the use of other
languages and/or pre-built libraries) the lisp itself has to lay down
the separation markers on the stack.
In Allegro CL, we have a structure on the stack called a clink chain,
which is built and maintained by those lisp functions which perform
the transitions from lisp to foreign code and vice versa. We also
identify functions as being declared "from-c" as opposed to lisp only,
and also a lisp function can make a "c-call" or a lisp call (either
call can be made from any lisp function, due to the way we set up
these clink structures). The information needed in these structures:
1. must be findable by the gc, per thread
2. must be on the stack, so as not to run into the same problem as
would be seen by separating the stacks
3. must be maintained by all lisp functionalities, including
interrupts.
A c-call chains in a new clink before the call is made, setting it to
a state that is identifiable as being "in C". The from-c functions
will immediately mark the top clink as having come back from C, so
that the slink is identifiable as being "in lisp". We also used to
establish a "leaf" state, for C functions which promise never to call
back into lisp, but that proves to be an impractical promise,
especially in the face of debugging, interrupts, and Windows-style
message-passing.
Once the clink chain is established, the gc can walk the stack and
know which sections to ignore. Assuming the gc knows the lisp frame
structures, it can then walk those frames and perform either
conservative or precise gc on the slots therein.
Good luck in your design.
Duane
developing and getting to year-end deadlines...
> I'm writing my own toy CL-like language, and i'm very interested in GC implementation on x86 and other such systems where lisp control stack is shared with C.
>
> I mean, i cannot understand how the stack is examined - in the presence of FFI, the stack can contain raw C data, and so we cannot distinguish such data from lisp pointers. As i understand, this requires "conservative" garbage collector implementation. But then, how to look for GC roots on the stack, anyway? Can you please point to some articles/books describing such GC implementations(particularly, implementations for lisp-like languages)?
>
> On the other side - if the control stack is separated from "number" stack, how proper unwinding semantics could be implemented(i mean, lisp unwinding should also reflect on C stack, so we can use such things as windows SEH to implement unwind-protect and friends)?
has identification problems, and the latter has synchronization
problems, especially during unwinding. It seems to be easiest to push
the stack structure decisions off to gc, rather than to actively
manage the stack at run-time; consider that a gc might not happen
during 10 advances and retreats of the stack, and so all of that stack
management while building and tearing down the stack is wasted.
Better to put as little control data on the stack as possible. and
have the gc do the work, at the time it is actually needed.
Another issue, assuming a decision has been made for a shared control
stack, is how to mark the stack, when C programs know nothing about
such marking. Clearly, unless you want to force C users into a
particular calling discipline (which then locks out the use of other
languages and/or pre-built libraries) the lisp itself has to lay down
the separation markers on the stack.
In Allegro CL, we have a structure on the stack called a clink chain,
which is built and maintained by those lisp functions which perform
the transitions from lisp to foreign code and vice versa. We also
identify functions as being declared "from-c" as opposed to lisp only,
and also a lisp function can make a "c-call" or a lisp call (either
call can be made from any lisp function, due to the way we set up
these clink structures). The information needed in these structures:
1. must be findable by the gc, per thread
2. must be on the stack, so as not to run into the same problem as
would be seen by separating the stacks
3. must be maintained by all lisp functionalities, including
interrupts.
A c-call chains in a new clink before the call is made, setting it to
a state that is identifiable as being "in C". The from-c functions
will immediately mark the top clink as having come back from C, so
that the slink is identifiable as being "in lisp". We also used to
establish a "leaf" state, for C functions which promise never to call
back into lisp, but that proves to be an impractical promise,
especially in the face of debugging, interrupts, and Windows-style
message-passing.
Once the clink chain is established, the gc can walk the stack and
know which sections to ignore. Assuming the gc knows the lisp frame
structures, it can then walk those frames and perform either
conservative or precise gc on the slots therein.
Good luck in your design.
Duane
cju
Dec 22, 2011, 6:40:16 AM12/22/11
to
Hi OpenLisp (www.eligis.com) scans C stack
Very close to main(), I have something like:
char *C_stack_start;
char *C_stack_stop;
int main()
{
char assume_on_C_stack[8];
C_stack_start = &assume_on_C_stack[0];
}
GC()
{
char assume_on_C_stack[8];
C_stack_stop = &assume_on_C_stack[0];
}
When GC occurs, I scan C stack from C_stack_start to a C_stack_stop
taking care of stack alignment and stack direction.
Fortunately, OpenLisp has a function olobjectp(x) which retuns true
iff x is a lisp pointer in current lisp memory.
Well, it is in fact more complex than that because shared library and
especially DLL can make holes between C_stack_start and C_stack_stop.
To solve this problem, OpenLisp manages linked C stacks assigned to
Lisp process.
A set of macro ENTER_LISP, LEAVE_LISP manage this link.
This is a very simplified view of OpenLisp GC which is much more
complex (it uses threads to parallelize GC)
Very close to main(), I have something like:
char *C_stack_start;
char *C_stack_stop;
int main()
{
char assume_on_C_stack[8];
C_stack_start = &assume_on_C_stack[0];
}
GC()
{
char assume_on_C_stack[8];
C_stack_stop = &assume_on_C_stack[0];
}
When GC occurs, I scan C stack from C_stack_start to a C_stack_stop
taking care of stack alignment and stack direction.
Fortunately, OpenLisp has a function olobjectp(x) which retuns true
iff x is a lisp pointer in current lisp memory.
Well, it is in fact more complex than that because shared library and
especially DLL can make holes between C_stack_start and C_stack_stop.
To solve this problem, OpenLisp manages linked C stacks assigned to
Lisp process.
A set of macro ENTER_LISP, LEAVE_LISP manage this link.
This is a very simplified view of OpenLisp GC which is much more
complex (it uses threads to parallelize GC)
cju
Dec 22, 2011, 12:52:45 PM12/22/11
to
If it helps:
/*
* Stack groups
*/
struct olcstack {
LBYTE * sstart; /* stack of spaghetti stack */
LBYTE * send; /* end of spaghetti stack */
};
typedef struct olcstack OLCBSF;
#define OLENTERLISP { LBYTE _olbstack[2]; olentercbsf( __FILE__,
__LINE__, &_olbstack[0] ); {
#define OLLEAVELISP } olleavecbsf( __FILE__, __LINE__,
&_olbstack[0] ); }
#define OLESCAPELISP { LBYTE _olestack[2]; olescapecbsf( __FILE__,
__LINE__, &_olestack[0] ); {
#define OLRESTORELISP } olrestorecbsf( __FILE__, __LINE__,
&_olestack[0] ); }
#define OLWITHLISP(x) OLENTERLISP (x); OLLEAVELISP
#define OLWITHC(x) OLESCAPELISP (x); OLRESTORELISP
#define OLSYNCSTACK { LBYTE _olcstack[2]; olcbsfsync( __FILE__,
__LINE__, &_olcstack[0] ); }
#define OLASSERTLISP(x) olcbsfassert( __FILE__, __LINE__,
OL_CBSF_OPENED )
#define OLASSERTC(x) olcbsfassert( __FILE__, __LINE__,
OL_CBSF_CLOSED )
#define OL_CBSF_NULL 0 /* No current CBSF */
#define OL_CBSF_OPENED 1 /* Current CBSF is open */
#define OL_CBSF_CLOSED 2 /* Current CBSF is close */
> > Duane- Masquer le texte des messages précédents -
>
> - Afficher le texte des messages précédents -
/*
* Stack groups
*/
struct olcstack {
LBYTE * sstart; /* stack of spaghetti stack */
LBYTE * send; /* end of spaghetti stack */
};
typedef struct olcstack OLCBSF;
#define OLENTERLISP { LBYTE _olbstack[2]; olentercbsf( __FILE__,
__LINE__, &_olbstack[0] ); {
#define OLLEAVELISP } olleavecbsf( __FILE__, __LINE__,
&_olbstack[0] ); }
#define OLESCAPELISP { LBYTE _olestack[2]; olescapecbsf( __FILE__,
__LINE__, &_olestack[0] ); {
#define OLRESTORELISP } olrestorecbsf( __FILE__, __LINE__,
&_olestack[0] ); }
#define OLWITHLISP(x) OLENTERLISP (x); OLLEAVELISP
#define OLWITHC(x) OLESCAPELISP (x); OLRESTORELISP
#define OLSYNCSTACK { LBYTE _olcstack[2]; olcbsfsync( __FILE__,
__LINE__, &_olcstack[0] ); }
#define OLASSERTLISP(x) olcbsfassert( __FILE__, __LINE__,
OL_CBSF_OPENED )
#define OLASSERTC(x) olcbsfassert( __FILE__, __LINE__,
OL_CBSF_CLOSED )
#define OL_CBSF_NULL 0 /* No current CBSF */
#define OL_CBSF_OPENED 1 /* Current CBSF is open */
#define OL_CBSF_CLOSED 2 /* Current CBSF is close */
>
> - Afficher le texte des messages précédents -
0 new messages