Jacob, what rules would have to be added for application writers
to use the GC in lcc-win besides the C standard and "don't invoke
undefined behavior"? Hint: the answer is not "none". And that's
not intended as a put-down of lcc's GC or GC in general.
Or, to put it another way which I'm sure you will still think of
as a personal attack, list the things an application programmer
could do to break GC that no sane programmer would do (someone will
come up with a sane-sounding reason for doing it anyway) but the C
standard still allows. If the C standard calls it undefined behavior
on the part of the application, GC is off the hook.
I'll define "break GC" as any one or more of the following:
- Collecting non-garbage
- Aborting the program with things like segfaults.
- A 1,000,000% slowdown
- A GC so conservative it never collects anything.
in my case, the policy is basically just to give code the choice.
if it wants to use malloc, it can use malloc;
if it wants to use the GC, it can use the GC.
the GC wont generally trace through memory allocated via malloc though.
in my case, there is a "gcmalloc()" call, which is behaviorally similar
to malloc (it wont automatically release the memory), except that the GC
will trace through it.
putting pointers to malloc-managed memory in GC-managed objects works,
just the GC will ignore them.
it is possible to register behavior hooks with the GC to allow
custom-managed memory regions.
usually, the GC wont collect anything until after a certain amount of
memory is used (can be set by the program), so if the app keeps its
memory use below this limit, the GC wont run (this currently leads to a
case of setting the limit at something like 1GB, which makes the GC
running, except in cases where the app "springs a leak" fairly unlikely).
I'm pretty sure that writing pointers to a (potentially terabyte)
temporary file, erasing the pointers from memory, and later reading
the pointers back from the file (all done by the same run of the
same program) will either confuse or horribly slow down GC. And I
think that's perfectly OK with the C standard.
actually, more likely, it will become timing dependent:
if the GC runs during the time the pointers no longer exist, the objects
may be freed;
if it does not, nothing happens (the pointers will just come back in
pointing at the same objects).
in the case where the pointers are read back in for objects which have
been freed, then essentially they are just dangling pointers (and the GC
will either ignore them, or treat them as if they point to whatever new
object was allocated at that address).
this case only really matters if the GC is being used to replace malloc
or similar.
otherwise, a person could declare that the case of temporarily hiding
and then restoring pointers is itself undefined-behavior.
I take that to mean: often an application program will abuse the bottom
couple of bits of pointers to memory with known alignment properties to
store information, and this will break the GC. I think doing that to
pointers invokes undefined behavior, at least if you do stuff like
void *ptr;
ptr |= 3;
or ptr &= ~3;
so the GC has a perfectly good excuse for breaking.
my GC will handle this case just fine (my GC is more conservative, and
so will by-default treat a pointer to anywhere in the object as if it
were a GC reference). likewise, most GC operations will accept these
pointers as well, and there is also a "gcGetBase()" operation mostly
specially for this case: it allows taking a pointer into an object and
getting the starting address of the object.
I don't know how Boehm handles it exactly, but IIRC there are script VMs
which use Boehm and use similar tagging schemes.
I don't personally use this sort of tagging in my VM, instead having the
GC keep track of the type, so whenever the VM needs to do something, it
will fetch the type-name for an object, or maybe fetch an associated
type-vtable (the VM has tables of function-pointers used to represent
common operations on objects of various types).
note that there is also a Class/Instance OO system, but this uses its
own independent vtables, and these objects exist as a single type from
the POV of the GC.
Code protection methods are designed to break the application, but
the C standard doesn't forbid that.
simple: label the case of XOR'ed pointers + GC'ed objects as undefined.
I'm not sure the C standard allows that specific method of disguising
pointers, but I think you are allowed to format a pointer with
sprintf() and %p, erase the original pointer, then later feed the
buffer sprintf() wrote into sscanf() and %p, and get back the same
pointer. While it's in text form, you could do all sorts of things
to it (encrypt, store it in a file, etc.) , as long as it eventually
gets back to the original text.
possible, but this case can also be labeled as undefined with GC
objects, or maybe, it can be restricted to certain cases, such as it is
only allowed if the objects are pinned/locked beforehand, or if they
were allocated either with malloc or a malloc-like call (and so will not
be implicitly freed).
People want to know how to recognize "that kind of code" and not
try to use GC with it, rather than trying it and figuring it out
the hard way. And I don't really see a "don't disguise pointers"
rule as being too onerous if you can clearly define what *ISN'T*
disguised. Probably 99.9% of programs would need no change.
in my case, it is more like:
pointers stored in global variables are visible (1);
pointers stored in stack variables are visible (2);
pointers stored in other GC managed objects.
1: on both Windows and Linux, the GC will walk the list of loaded
modules and scan the ".data" and ".bss" sections and similar. this also
includes any "static" variables within functions.
2: this can be a little harder. in my case, the GC supplies its own
thread-creation functions, but it is possible to do so without doing
this (for example, Boehm walks the OS thread list AFAIK). there is a
difficulty with knowing the exact stack address on WoW64 targets (an
issue for Boehm AFAIK), but my GC uses a different strategy: it just
scans the stack until either the known limit is encountered, or Windows
throws a SEH exception (when the scan function tries to scan into an
uninitialized guard page), which the function catches and handles.
Oh, yes, another rule for a working GC is that the GC has to
occasionally actually collect some garbage if there's any around
to collect. It doesn't have to catch everything immediately, but
code like:
#define malloc(x) gc_malloc(x)
int main(void)
{
while(malloc(6)) { /* loop */ }
}
shouldn't terminate the loop because malloc() eventually returns NULL
due to insufficient collection of garbage.
usually what happens in this case is that the caller thread will block
until the GC thread can run and finish (running out of memory triggers
an immediate GC).