effect of free()

[Richard O'Keefe]

In article <14177 at bloom-beacon.MIT.EDU>, scs at hstbme.mit.edu (Steve Summit) writes:
> In article <2059 at munnari.oz.au> ok at cs.mu.oz.au (Richard O'Keefe) writes:
> >    are there code sequences which
> >	(b) can NOT handle ptr1==ptr2 where one of them used to be a valid
> >	    address but isn't just at the moment

One more time:  the great names of comp.lang.c have clearly demonstrated
that there *are*.  That wasn't my question.  My question was (a) *AND*
(b) *AND* (c).  When someone asks whether there is a machine on which
(a) and (b) and (c) don't isolate one of the points as if that was the
whole question.

> In articles too numerous to mention, hordes of people get badly
> upset at the prospect that
> 	p = malloc(size);
> 	free(p);
> 	if (p == NULL)
> might cause ugly, undefined behavior such as traps or exceptions.

Yes, we do.  Before the call to free() we were guaranteed that p was
not NULL.  We had no guarantee about other ordering relations (it was
not defined whether p > NULL, for example), but we _were_ guaranteed
that p == NULL was defined, meaningful, and false.  Furthermore, the
free() procedure has no access to the variable p.  One normally
expects as a matter of course that
	if <expression> is defined and has value <v> here,
	and nothing here has access to any of the variables
	which occur in <expression>,
	then <expression> is still defined and still has value <v> here.
It's as if
	p = 1;
	printf("%d\n", p);
	if (p == 0)
were allowed to blow up.  There are languages (such as Euclid) where this
analogy is precise.  (Yes, I know that C is not Euclid.)  I don't know
about other people.  My perspective is that if a language violates such
an obvious invariance property, I am afraid to use it because I don't
know what other obvious properties it may break.  This particular property
is one which is very important to optimising compilers.  I don't expect to
write one, but I _do_ expect that C compilers I use in the future will have
optimisers which assume this invariance property, and it won't be true.

There is of course the correspondence to IEEE signalling NaNs and
VAX Invalid Operands, but that analogy fails, because those things are
_born_ invalid; you can't get one in the first place without using
machine-specific code.

I can think of several reasonable applications for testing p==NULL after
a call to free(p).  For each of them I can see how to do it safely another
way.  But then any program can be rewritten with one while(), one switch(),
and no gotos or user-defined procedures.

Let's have a bit of a think about the hardware issue.  We would like
free() to be able to release a segment to the operating system, so that
dereferencing it is not legal, but because the address was once legal
we would rather not have future _loads_ trap.  Is this doable?  It depends
on the MMU.  A Page Map Entry on the ELXSI, for example, has three
accessRights bits: readAllowed, writeAllowed, and executeAllowed; these
bits are independent of other bits like inResidentSet, inPhysicalMemory,
and so on.  If I were designing a C system for that machine, I would take
one page of physical memory, and map page 0 of the virtual address space
to that page.  The Page Map Entry for page 0 would refer to a physically
present page, but with no access rights.  Pages which were given back to
the operating system I would treat just the same: there would be a page
map entry indicating that the page existed in the address space but that
the program had no rights to it.  One physical page will serve for all
such "holes" in the page map.  If the ELXSI were to fault when pointer
to a page not in the user's address space were loaded, that would be fine;
a free()d pointer would continue to be valid in _that_ sense, but any
attempt to dereference it would be invalid, and the operating system would
be able to tell whether the page was _really_ there or not by checking
whether it was mapped to the one reserved page.

The problem with address loads trapping is not a hardware problem; it is a
hardware/OS problem.  I have outlined one approach which requires some OS
cooperation, but if the standard required the usual invariance property to
hold, OS vendors just might see an advantage in making C implementation
straightforward.  In the absence of such support, there is no reason why a
C implementation _has_ to give a free()d page or segment back to the 
operating system, thus invalidating the pointer.  I would expect that a
good run-time library would wait for a bit in case the space was needed
again soon.

Give me more information about particular machines, and I'll try to come
up with implementation strategies that don't require the standard to
break one of the few optimiser invariants C _was_ thought to possess.