memory allocation

[Richard Harter]

In article <7105 at cdis-1.uucp> tanner at cdis-1.uucp (Dr. T. Andrews) writes:
>In article <33422 at cca.CCA.COM>, g-rh at cca.CCA.COM (Richard Harter) writes:
>) One point which I feel strongly about is that most allocators use the
>) blocks (free and allocated) to hold control information.  I think that
>) this is a mistake.  I put all control information in structures in a 
>) separate node space.

>Unless you hard-code a limit of <n> allocated blocks, you have to
>allocate the separate node space from the same heap, leaving the
>control information somewhat vulnerable (OK, so now it's arry[-3]
>instead of [-1] that trashes you).

	You are always vulnerable to wild writes unless there is hardware
memory area protection available.  However the vast majority of overwrite
problems come from running over the ends of arrays.  What you do is to
allocate a block of nodes as an array of nodes upon need.If you're feeling
paranoid you put some buffer space at the end of each block of nodes.  The
general idea is to avoid contiguity between user data space and allocator
control space.  The problem with associating control information directly
with allocation blocks is that you when you pass an address back to the
user you are, in effect, also passing back a pointer to the control
information associated with the block.  The control block is immediately
susceptible to damage by the user because you have violated physical
information hiding.

	This is the sort of thing that makes for mystery bugs, to coin
a phrase.  Mystery bugs are, loosely, bugs where you cannot infer the
source of the error logically from the error because the effect of the
error depends on the arcana of the implementation and the actual arrangement
of the code and data.

>I stuck the control information in the blocks, and can still check
>my free() calls.  Two things assist in this.

>On free() calls, I trace the list until I find the block to be freed.
>If it isn't a valid block, it isn't free()d.  As the block is being
>freed, I coalesce the adjacent free block(s).  At most 3 blocks may
>be collected (the freed block and the ones immediately above and
>below).  It seems much better to do this work wen the block is freed
>(if ever) rather than to perform trash-mashing at malloc() time.

	Immediate coalescence is usually the right thing to do.  Your
strategy for validating freed blocks sounds like it is expensive time
wise.  
-- 

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