memory allocation

[Richard Harter]

In article <6913 at cdis-1.uucp> tanner at cdis-1.uucp (Dr. T. Andrews) writes:
>In article <33692 at XAIT.XEROX.COM>, g-rh at XAIT.XEROX.COM (Richard Harter) writes:
>) 	Immediate coalescence is usually the right thing to do.  Your
>) strategy for validating freed blocks sounds like it is expensive time
>) wise.  
>
>Not really.  As I scan and coalesce the blocks, I perform the
>validation.  of the pointers.  It's real simple (one "xor"),
>but catches most errors.  The control block contains only:
>	[0]	back ptr
>	[1]	size of block (is even, the low bit == "in use")
>	[2]	[0] ^ [1]
>
>I don't mind the small expense at free() time, because in general
>that's not done nearly as often as malloc() in my applications.

	This is reasonable -- your original posting talked about
traversing the free list, which is another matter entirely.  I am
not convinced one way or another that this is perfectly safe.  One
thing that should be done in your scheme is to check that the pointers
in the preceding and following blocks point correctly (a length is as
good as a pointer in this context.)  At a miminum you should set the
use bit to free in the returned block.  What you want to catch is 
the multiple returns of a block.  It is unsafe to test on the contents
of a freed location.  However the odds are that the contents of the
old control area in the freed block are either completely changed or
are unaltered.  Pointer checks and use bit checks will catch both.
[I am uncomfortable "the odds are" programming.]  Much safer is to
do a two way check on pointers.  Suppose that I have three successive
blocks, A, B, and C, and that B is freed.  The check is to determine
A and C from the control area for B and then check to make sure that
A and C both point to B.  If you don't do this kind of checking, this
is what can happen.  A and C are free, B allocated.  Return B, leaving
its control area unchanged.  Now A points to D, just past C.  The
control area in C is unaltered since it is part of the free area for A.
Now erroneously free C.  Its control area points to B and D, apparently
in use.  No coalescence is done, but C is entered into the avail list.
In due course both the large block A and the false block C are allocated
with sundry disastrous results.

	The above scenario is not the only one possible.  Pointer checking
may be provably "safe" under the assumption that the control area of
a false return either contains stale pointers or garbage.  However I
don't have a proof at hand.  
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.