🚀 go-pugleaf

In article <1992Nov18.104542.8499@thunder.mcrcim.mcgill.edu>, mouse@thunder.mcrcim.mcgill.edu (der Mouse) writes:
: In article <15977@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
: > In article <1992Nov13.184421.11065@taumet.com>, steve@taumet.com (Steve Clamage) writes:
: 
: >> "Data read in from a binary stream shall compare equal to the data
: >> that were earlier written out to the stream, [...]."
: > That is exactly the kind of answer I hoped for when I posted to
: > comp.std.c.  Thank you.  There remains, alas, one fine point of
: > detail.  What does it _mean_ to say "COMPARE EQUAL to the data ..."?
: 
: Let's see if I can bring this into sharper relief by eliminating the
: file.

That actually changes the question in a significant way.
Suppose you have a C interpreter (or compiler + library) which tries to
detect memory leaks by doing garbage collection.  There are garbage
collectors for C. One doesn't need to know for certain that something
_is_ a pointer, only that it _might_ be.  If one finds that there is an
unfreed allocated block to which are there no pointers, not even
possible pointers, then that is certainly a leak.

Now consider
	char *p = malloc(1);

	file = fopen("foo", "wb");
	fwrite(&p, sizeof p, 1, file);
	fclose(file);
	p = NULL;
	/* The garbage collector runs at this point */
	file = fopen("foo", "rb");
	fread(&p, sizeof p, 1, file);
	fclose(file);

The significant thing about the file here is that the reference is now
out in the file system, with no obvious link between the file and the
process.

This example of a garbage collector being used to report memory leaks is
not hypothetical.  See
    Boehm, H., and M. Weiser,
    "Garbage Collection in an Uncooperative Environment",
    Software Practice & Experience, September 1988, pp. 807-820.
The parts of that software which are available over the net do not include
the storage leak detector.  The README file refers to a similar kit written
by Doug McIlroy.

It now appears that if an object which might contain a pointer is written
to a file, this leak detection method won't quite work; it can _warn_ that
a block _may_ be lost, but it mayn't reclaim it.

As long as there _is_ a pointer _in the process_ for the new copy to
"compare equal to", then there isn't a garbage collection problem (only
a compacting problem).

: Since I think we now agree that a block of bytes written out and
: read back must produce a block of bytes with identical bits in them....

Yes.  There is an interesting variant on der Mouse's example.

Consider:
	char *p;
	char buf[1 + sizeof p];

	p = malloc(1);
	memcpy(buf, &p, sizeof p);
	p = NULL;

Now there is a bit-for-bit copy of p in buf, but nowhere else.
If buf happens to be suitably aligned, then a conservative garbage
collector will notice that "possible pointer", and a following

	memcpy(&p, buf, sizeof p);
	*p = 1;
	free(p);

will work.  But now suppose we do

	p = malloc(1);
	memcpy(buf+1, &p, sizeof p);
	p = NULL;
	/* The leak detector runs here */
	memcpy(&p, buf+1, sizeof p);
	*p = 1;
	free(p);

A garbage collector cum leak detector is still possible, but must consider
all possible alignments, not just the natural alignment for a pointer.

Now suppose we do

	p = malloc(1);
	memcpy(buf, &p, sizeof p);
	buf[0] ^= 0x34;
	buf[sizeof p - 1] ^= 0x67;
	p = NULL;
	/* The leak detector runs here */
	buf[sizeof p - 1] ^= 0x67;
	buf[0] ^= 0x34;
	memcpy(&p, buf, sizeof p);
	*p = 1;
	free(p);

This disguises the pointer so thoroughly that it is not reasonable
to expect a leak detector to notice it.

C's pointer arithmetic is not a problem, because a legal pointer value
that refers to (part of) a dynamically allocated object must point within
or just past that block.

Casts aren't a problem, because there is no guaranteed way of getting a
valid pointer _back_ from a cast:  if I do
	char *p = malloc(1);
	unsigned long v = (unsigned long)(p) ^ 0x12345678;
	char *q = (char *)(w ^ 0x12345678);
there is no guarantee that q == p, so a portable program cannot expect
to hide pointers like this anyway.

But memcpy and fwrite+fread _are_ a problem, because they _do_ appear to
give a guaranteed way whereby a pointer can be mangled in any reversible
way and recovered.

For myself, I regard leak detectors as far more valuable than the ability
to mangle pointers.  If it turns out that leak detectors can't be used with
code that uses fwrite+fread on objects that contain pointers (anyone have
any trouble with that phrasing) or with memcpy to unaligned blocks, then
I'll just have to take that much more care not to use those constructs.